We have the pleasure to announce that Guillaume Delugré and Gabriel Campana from Sogeti/ESEC France (a really nice R&D company in Security) has won the challenge. They have sent the plaintext text corresponding to the chall3.coded file. Congratulations to them. They did a really nice work which will be very useful for the Perseus project. They will be recently awarded with the prize.
Their attack (more details here) is a clever and nice implementation attack which does not hence put the Perseus (mathematical) concept into question. Their attack shows that going from the theory to implementation is always complex and prone to security weakness.The attack exploits the fact that
- the plaintext is split into blocks of constant size (for performance purposes, it is more practical to consider this approach since forthcoming parallel decoding of blocks will overcome the complexity of the Viterbi decoding) each block being encoded with the same encoder.
- due to a bad (and stupid) bug in our implementation the noise pattern was always the same (by mistake we forgot to declare a few variables as static and then each call to the noise generator resets its state). Ironically, this dramatic weakness could have been detected by our cryptanalysis library Mediggo (tool detectsinglefile.c) which precisely has been designed to detect this kind of flaw. But development speed and security are seldom compatible (shoemakers are often the worst shod -:))
- It seems that implementation of the puncturing is a little faulty as well.
What is clear is that without the help of Guillaume and Gabriel, we would probably never detect this (infamous) bugs. Thousands thanks to them and to their contribution.
The bugs will be of course corrected in the new implementations of the Perseus lib which is under currentl development with the help of DFT-Technologies (which has performed the industrial specifications of LibPerseus and will perform the final code auditing). This implementation is about to be made public and officially presented during the RMLL 2011 in July in Strasbourg. Here are the new features that takes Guillaume and Gabriel's attack into account:
- This implementation considers blocks of variable sizes (ranging from 512 to 4096).
- Each block is encoded with a different encoder.
- The noise pattern of course will be variable itself.
As originally implemented in the Perseus library itself, normally the message should be a single block. We are presently developping a polynomial-memory decoder that will make decoding very quick and will enable to consider message as a single block. More to come...
Of course, we hope that contributors will volunteer to evaluate this implementation. Once again congratulations to Guillaume and Gabriel. We would like also thank all people who support, sponsor the Perseus project and all those who contribute with comments and feedbacks.E.F.