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
forskning.no, as well as
the press release
from UiB (Norwegian only).
Contact information
Email:
tor <a> mnemonic.no (work) /
tor.bjorstad <a> ii.uib.no (research) /
torebj <a> gmail.com (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.
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).
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.
Edon-R
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
π
1(π
2()) and π
1(π
3());
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.
LUX
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.
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 related (though more
sophisticated) techniques.
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.
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.