Tor E. Bjørstad

Tor E. Bjørstad

Personal information

I graduated with an MSc-equivalent (Sivilingeniør / M.Techn.) degree in Industrial Mathematics from the Norwegian University of Science and Technology in 2005, and proceeded to do a PhD in cryptography at the Selmer Center for reliable communication, which is part of the Department of Informatics at the University of Bergen. My advisor was Associate Professor Matthew G. Parker.

I spent the spring of 2009 visiting the COSIC research group at K. U. Leuven. My host was Professor Bart Preneel.

I am currently working at mnemonic as as an IT security consultant. This page will be updated sporadically if at all.

Some media coverage regarding the publication of my thesis at, as well as the press release from UiB (Norwegian only).

Contact information

Email: tor <a> (work) / tor.bjorstad <a> (research) / torebj <a> (private)
Phone: (+47) 97 08 77 22 (mobile).
NB: It is generally preferred (and more reliable) to contact me by email than by phone.

Research information

My research interests concern various forms of cryptology and secure communications. Following my Master's degree I worked mainly on provable security, particularly as applied to hybrid schemes. More recently, I've been focusing on cryptanalysis of symmetric primitives. I've also got a keen interest in privacy-related topics and more applied / practical security issues such as risk management. It is also interesting to follow the interaction between technological development and public policy, from a cryptological point of view issues such as electronic voting, data retention and national identity cards are certainly relevant.

Peer-reviewed publications

This is a list of papers published in peer-reviewed conference proceedings or journals.
Cryptanalysis of Grain using Time / Memory / Data Tradeoffs.
Published in the pre-proceedings of WCC 2009. Journal submission pending.
Grain is one of three portfolio ciphers chosen in the hardware category of the ECRYPT Stream Cipher Project (eSTREAM). In the paper, it is shown that it is possible to perform BSW sampling on the internal state of Grain. This leads to a far wider range of possible time / memory / data tradeoffs than anticipated by the cipher authors, with active complexities for state recovery down to O(2^70) time and memory, and 2^56 bits of keystream (for an 80-bit keylength). However, the required precomputation cost for this tradeoff remains much greater than brute force, and any sane attacker would presumably still prefer to use a parallel brute force search.
Correlated Keystreams in Moustique.
With E. Käsper, V. Rijmen, C. Rechberger, M. Robshaw and G. Sekar.
Published in the proceedings of Africacrypt 2008, Springer LNCS 5023, pp. 246-257.
Moustique was one of the finalists in the hardware category in the eSTREAM stream cipher contest, and the only self-synchronising stream cipher remaining in Phase 3. In the paper, we show that there exist simple related-key phenomena in Moustique, which allow us to break the cipher in O(2^38) steps in the related-key setting, and speed up exhaustive key search by roughly a factor 50.
Efficient KEMs with Partial Message Recovery.
With A. W. Dent and N. P. Smart.
Published in the proceedings of Cryptography and Coding 2007, Springer LNCS 4887, pp. 233-256.
This paper demonstrates how one may embed plaintext and ciphertext data securely in KEMs and Tag-KEMs, obtaining ciphertext expansion that grows linearly in the security parameter (and not linearly in the size of, say, the RSA modulus). This has obvious practical applications when using public-key encryption schemes with large parameters and limited bandwidth.
Building Better Signcryption Schemes with Tag-KEMs (Full version).
With A. W. Dent.
Published in the proceedings of PKC 2006, Springer LNCS 3958, pp. 491-507.
The paper proposes a new generic model for hybrid signcryption based on Tag-KEMs, which gives rise to cleaner and simpler descriptions of insider secure signcryption schemes. We also propose a new signcryption scheme based on Chevallier-Mames signatures, with tight security reductions for confidentiality and authenticity.

Other writings

This is a list of writings and results that have not been through peer-review, but may still be of historical interest.
Practical Attacks on NESHA-256.
With O. Dunkelman.
NESHA-256 was a cryptographic hash function presented at WCC '09. We provide several practical attacks on the algorithm, thus demonstrating that it is insecure.
Equivalence Between Certain Complementary Pairs of Types I and III.
With M. G. Parker.
Published in Post-Proceedings of NATO Advanced Research Workshop, Veliko Tarnovo, Bulgaria, 6-9 October 2008.
This paper is a bit on the side of what I usually do, and my contribution is mostly limited to some proofs. Although it is fairly self-contained, a slightly gentler introduction can be found in Close encounters with Boolean functions of three different kinds by Parker.
A short note on AES-inspired hashes.
I compare a dozen different SHA-3 candidates that use AES-like rounds (i.e. some kind of SubBytes(); MixColumns();-based operation) as their main nonlinear component. This is done, basically, by looking at the number of (generalised) "rounds" per 128-bit block processed by the compression function. While this is a very crude heuristic that ignores a lot of (presumably relevant) algorithm specifics, does shed some light on how and why the different algorithms differ in (apparent) security level and performance.
A note on the Edon80 S-box.
I had a look at the linear properties of the Edon80 ''S-box'' (nonlinear quasigroup permutation), to see if it was possible to find any weaknesses. This is not really the case, but one can make a few interesting observations by looking at several iterations as a larger S-box. Also, a full linear approximation is likely to be independent of the key (because each key bit occurs twice as input). About the same time as I did this (September 2007), Hell and Johansson published a key recovery attack on the cipher, although the effectiveness of this attack has been disputed by the Edon authors.
Provable Security of Signcryption.
My MSc Thesis, from the Norwegian University of Science and Technology.
Submitted 2005-06-24.
My Thesis focused on the provable security of Zheng's signcryption scheme in a hybrid versus a non-hybrid model. It is mostly superseded by the Signcryption Tag-KEM paper (see above), which gives a better hybrid proof of security for Zheng's scheme using SCTKs.

Hash function cryptanalysis

Following the start of the NIST Hash Function Competition in late 2008, the large number of candidates became a natural target for research. Here is some info on various Phase 1 candidates (none of which advanced to Phase 2).
Jean-Philippe Aumasson, Willi Meier and Florian Mendel and myself found a weakness in the PRE-MIXING step of CHI which leads to pseudo-collisions and pseudo-second preimages. This weakness was described in an official comment on the NIST mailing list.
A figure illustrating the data flow in the compression function, which some people may find helpful. The functions f and g are 256/512-bit permutations, defined to be equivalent with what the official specification denotes π12()) and π13()); the additions are wordwise mod 2^32 / 2^64 for the 8-word vectors. I find this representation much more convenient for analysis, than the quasigroup-setting presented in the specification. Also, there's some C code by myself and Sean O'Neil that one might find useful for manipulating the individual building blocks of the permutations.
After talking to Peter Schmidt-Nielsen at the NIST Conference in Leuven, I quickly knocked together some code to verify that his reduced-blank-round distinguisher worked as intended. It can be found (together with his analysis) in the SHA-3 Zoo.
I looked at Sarmal together with Nicky Mouha and Bart Preneel, using an approach based on symmetric differences. As with CHI, we found a differential for the compression function that holds with probability 1 due to the structure of the round function. However, this differential can not occur when using Sarmal in the specified mode of operation, as it requires differences in input fields corresponding to message, IV, salt and block counter. We also look at probabilities for other (possible) characteristics.
Spectral Hash
At an early stage I ran some simple automated tests on the SHA-3 candidates. In the case of Spectral Hash, it was possible to detect very short cycles in the internal state. Unfortunately, this was due to an implementation error in the reference code, and not a bug in the hash itself. Spectral Hash was later broken by Heilman using related (though more sophisticated) techniques.
For StreamHash, the internal state cycles found were even shorter than in Spectral Hash. This leads to very practical collisions for the hash function. As a result of this observation, StreamHash was conceded broken by the designer and withdrawn from the competition.

Other stuff

I am a member of IACR, the Norwegian Polytechnic Society, the Young Liberals of Norway, the European Youth Movement of Norway, Hack Bergen, the Norwegian Support Committee for Western Sahara and the Norwegian Sceptics Society. I play chess on the Internet Chess Club. I regularly read The Economist and Monocle.

Other interests include (but are not limited to) hiking and skiing, cooking, beer and whisky, music (listening, not playing) and reading (pretty much anything). There is a (or to be precise, one-half) blog underway, which will hopefully be ready for public consumption in the near future. Some photos from recent mountaineering trips are available, as well as a summit panorama.

I can also be found (at various levels of activity) on LinkedIn, Facebook and Twitter. Look me up.

Valid CSS! Valid XHTML 1.0 Strict

This page was created with vim. It is best viewed with a standards-compliant web browser.
2006-2010 Tor E. Bjørstad; Last Updated 2010-04-15.