Ramsey Theory and its `Applications'
There is one topic in the Crypto course that LOOKS really useful but I can't tell if it IS being used, so I inquire of my readers. (I will probably come across others topics like that in the future.)
A Secure Stream Cipher is (informally) a way to, given a seed and optionally an Init Vector (IV), generate bits that look random. Alice and Bob communicate the seed either in person or over a private channel or perhaps by using RSA (or some other public key system) and they then both effectively have a very long string of random bits. They send the IV in the clear. They can then do one-time-pad (really a psuedo-one-time-pad). There are other uses for random-looking bits as well.
So what is needed is a Secure Stream Cipher. Trivium seems to be one such. According to the Trivium wiki
It was submitted to the Profile II (hardware) of the eSTREAM compeition by its authors Christophe De Canniere and Bart Preneel, and has been selected as part of the portfolio for low area hardware ciphers (Profile 2) by the eSTREAM project. It is not patented.
According to these papers: here and here, and the Wikipedia entry, here the following are true:
1) Trivium takes an 80 bits seed and an 80 bit IV
2) The implementation is simple and is already in hardware. Around 3000 logic gates.
3) There are reasons to think its random-looking but no rigorous proof.
4) So far it has not been broken, though its not clear how many people have tried. Thats goes to my question-- how widely used it is it?
5) Trivium need 1152 steps in the init phase. If it only does 799 then The Cube Attack can break it in 2^68 which is better than the naive algorithm of trying every key and IV (2^160) but still not feasible.
6) Trivium is also An American Metal Band and a Medieval theory of education. Its a good name for a band. See my post What Rock Band Name Would you Choose? for fictional good names for bands with a math or theoretical cs connection.
OKAY, back to the main topic:
SO my questions:
Is Trivium used?
If so then by whom and for what (for the psuedo 1-time pad?) ?
If not then why not (e.g., some of of my points above are incorrect)? and should it be instead
of what is being used?
meh squared
ReplyDeleteI take it you are not impressed with Trivium. Can you say why so you can enlightend my readers and I can enlighten my class?
DeleteAn 80-bit key/IV is not secure enough for many modern uses (like encryption on the Internet), though I am not sure what exactly Trivium and other "lightweight ciphers" consider a threat. Their primary intended deployment scenarios are IoT and hardware tokens like auto door locks.
ReplyDeleteIf you are interested in teaching useful (and used) stream ciphers, you could start with RC4, which was widely used in TLS (i.e. encrypting a lot Internet traffic) until it was very badly broken. RC4 exhibits all sorts of interesting weaknesses for teaching, and it is very simple.
My understanding is that the most widely used stream cipher will soon likely be Chacha20 (again for TLS). The authentication mechanism (Poly1305) and other Wegman-Carter-type MACs involve some algebra and probability that are interesting for teaching crypto as well.
1) I am surprised (though I believe you) that 80 bits is not
ReplyDeletethat secure.
2) Great! Yes I will put this in my course this semester. The wikipedia site on Salsa20 (not the dance, the stream cipher)
https://en.wikipedia.org/wiki/Salsa20#ChaCha_variant
seems like a good source for the mechanics of it but I could not
find any source on why it is thought to be secure. Do you know
of any?
The IV is generally assumed to be public, and only the seed is private. So the naive brute-force attack takes time 2^80, not 2^160.
ReplyDelete