Tor E. Bjørstad

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. This extends to the intersection between technological development (in crypto) and public policy, when it comes to such issues as electronic voting or national identity cards.

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 interest.

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. This is a list of specific candidate functions that I've found something interesting on.

CHI
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. The CHI team intends to issue a patch for the PRE-MIXING step to fix this flaw.

Edon-R
I have spent a large amount of time dealing with Edon-R, and a short paper tentatively entitled Understanding Edon-R is currently in progress. Meanwhile, there is this figure illustrating how the compression function works, 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 π₁(π₂()) and π₁(π₃()); 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 someone might find useful.

LUX
After talking to Peter Schmidt-Nielsen at the NIST Conference in Leuven, I quickly knocked together some code to verify that his reduced-round distinguisher worked as intended. It can be found (together with his analysis) in the SHA-3 Zoo.

Sarmal
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 what appears to be a somewhat similar (though more sophisticated) approach.

StreamHash
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.

Tor E. Bjørstad

Personal information

Contact information

Research information

Peer-reviewed publications

Other writings

Hash function cryptanalysis

Other stuff