Insomni’Hack 2011 et CLUSIS

Vendredi prochain 4 mars 2011 aura lieu la 4ème édition d’Insomni’Hack, manifestation sympathique organisée par la société SCRT. À cette occasion, en plus du concours de hacking, une série de conférences aura lieu l’après-midi dès 14h sur le site de l’HEPIA à Genève. J’aurai le privilège de donner un exposé intitulé très, mais alors très pompeusement «La cryptographie» (tout un programme…). Les autres interventions seront données par Axelle Apvrille, Dominique Clementi, Sébastien Bombal, Alexandre Herzog et Bruno Kerouanton.

Quelques jours après, le mardi 8 mars 2011, dès 16h30, dans les locaux de la Fédération des Entreprises Romandes à Genève, j’interviendrai dans le cadre d’une manifestation organisée par le CLUSIS et baptisée «Chiffrer ou ne pas chiffrer, telle est la question ! ». Mon exposé est intitulé «Cryptographie: de la théorie à la pratique» et tentera d’expliquer que, «dans le domaine de la cryptographie, le passage de la théorie à la pratique, du monde académique au monde industriel, n’est pas souvent un long fleuve tranquille, que ce soit au niveau de l’apport d’innovations ou de l’implantation de solutions pratiques.» Les autres intervenants seront Grégoire Ribordy (ID Quantique) et Christian Roch (Pictet).

NIST publishes a Report on the SHA-3 Finalists Selection Process

A few hours ago, but two months after the list of finalists announce, the NIST published a long-awaited report on the SHA-3 finalists selection process. The full 32-pages report is available here. In this post, I would like to emphasize and summarize the more salient facts.

The goal of NIST’s report consists in

[…] explaining the evaluation and selection process for the second round of the competition. A summary of the public analyses of each second-round candidate, and justifications for whether or not a candidate is advanced to the third (and final) round of the competition are provided […].

The NIST mentions some of the information sources used to perform the selection:

For its security evaluations, NIST studied the large amount of feedback received from the cryptographic community via e-mail discussions in the official mailing list, and the SHA-3 Zoo web page, as well as the security arguments presented by the designers. NIST researchers also conducted their own internal cryptanalysis of the candidates.

For its software evaluations, NIST considered various benchmarking comparisons. The primary contributor was the ECRYPT Benchmarking of All Submitted Hashes (eBASH) project that provided speed measurements of the SHA-3 candidates on a wide variety of 32- and 64-bit platforms. Another software-benchmarking project – the eXternal Benchmarking eXtension (XBX) – provided performance results on small devices. […]

NIST’s foremost selection criterion was security, which is not very surprising:

Security was NIST’s primary criterion in selecting the finalists. None of the second-round candidates was completely broken according to the criteria NIST laid out […]. NIST received many security observations, including “partial attacks” on several candidates, i.e., cryptanalysis of weakened variants. Absent more conclusive information on the security of these candidates, a principal concern was the potential for extending these cryptanalyses. NIST tried to extrapolate the severity of any partial attacks, and thus to estimate the “security margin”, as an estimate of susceptibility of the full hash algorithms to future attacks.

An important caveat is that this extrapolation is only meaningful when the algorithm has received a significant amount of cryptanalysis, and when there is a good deal of granularity in choosing any tunable parameter that was provided for the algorithm. […] Algorithms that received very little cryptanalysis, and algorithms without a clearly adjustable security parameter were, therefore, evaluated with more suspicion.

The second main criteria was, also unsurprisingly, performances, with a rather important focus on the software parallelism capabilities of the candidates:

Performance was also important in choosing the finalists. NIST chose finalists that could be implemented on as wide a variety of platforms as possible, while still maintaining reasonably good performance. […]

Discussions included the implementation possibilities for the algorithms: some algorithms allowed very high levels of fine-grain parallelism that could be realized well with hardware, some exploited parallelism with vector units, and some seemed to fully exploit the considerable parallelism that could be achieved by conventional superscalar arithmetic logic units (ALUs) capable of simultaneously launching several instructions per clock cycle.  NIST also noted that several algorithms exploited the power of 64-bit-wide ALUs. Candidates that performed poorly in hardware or on platforms without a specialized AES instruction, for example, were not selected, since many platforms do not provide this capability.

Another selection criterion was the way how the algorithms were tweaked by their designers during the competition:

Although NIST allowed the designers to tweak (i.e., make minor modifications to) their algorithms for the second round, extensive tweaks in order to avoid certain attacks were a cause for concern. NIST was generally comfortable with tweaks to the number of rounds or to constants, but more suspicious of changes that seemed to affect the structure of the compression functions, since these tweaks made much of the first-round cryptanalysis on the algorithms obsolete. However, NIST did consider whether the best attacks on some of the candidates seemed amenable to mitigation by a simple modification.

Provable security was also considered in a positive way, obviously but it is interesting to note that it was not part of the main selection criteria:

NIST also considered positive security arguments and proofs in making its decision. Since block cipher cryptanalysis appears to be more advanced than hash algorithm cryptanalysis, arguments that link the security of the candidates to a component that can be treated as a block cipher or fixed permutation were especially valuable.

Finally, all the exotic features brought by the candidate algorithms were not so important:

Additional design features, such as a built-in pseudorandom function (PRF) or an authenticated encryption mode were also briefly discussed, but played little part in the selection of the finalists.

Here is a copy-paste of the argumentation for the decisions of (non-)selection for each of the 14 semi-finalists:

  • BLAKE was selected as a finalist, due to its high security margin, good performance in software, and its simple and clear design.
  • Although BMW has very good software performance, and good potentials for pipelining and area-efficient high-throughput values, a disadvantage of the algorithm is its irregular and not-well-understood design. Since the compression function of BMW does not have a conventional iterated-round structure, there appears to be no obviously simple way to adjust the security margin, or to trade performance for security. Moreover, the attacks on the algorithm, even after an extensive tweak, did not provide confidence in the security of the algorithm. For these reasons, BMW was not selected as a finalist.
  • CubeHash is a simple, well-understood design that received extensive third-party analysis. The design is suitable for constrained environments, as it requires a small area in hardware, and little RAM or ROM in software. However, it has poor performance without the use of a vector unit, resulting in a large overhead for short messages. Moreover, no single variant for the 512-bit digest size achieves the required theoretical security with acceptable performance. Another disadvantage of the design is the existence of the symmetric properties that are arguably a potential avenue for future attacks. NIST felt that an additional year of study would not be enough to determine whether or not the symmetric properties pose a threat. Therefore, NIST felt that CubeHash could not be chosen as SHA-3 with confidence, and thus should not be selected as a finalist.
  • Although ECHO appears to be a simple secure design, it was not selected as a finalist, due to its all-around poor performance.
  • Fugue is an innovative design and has decent, all-around performance. Its designers also proved that collisions are unlikely to be found using differential cryptanalysis techniques. Nonetheless, Fugue has received only a very small amount of cryptanalysis. The most important published result, Aumasson and Phan’s distinguisher on Fugue’s finalization function, raised some concern. NIST felt that it would not be possible to establish confidence in the hash algorithm after another year of cryptanalysis; therefore, it was not selected as a finalist.
  • Grøstl was selected as a finalist because of its well-understood design and solid performance, especially in hardware. While Grøstl’s security margin is not ideal, NIST views it in light of the extensive amount of cryptanalysis that has been published, both on Grøstl itself and the larger AES structure on which Grøstl is based. Due to the large amount of existing cryptanalysis, NIST feels that future results are less likely to dramatically narrow Grøstl’s security margin than that of the other candidates.
  • Hamsi was not selected as a finalist, mainly due to the second-preimage attacks and high ROM requirements.
  • JH was selected as a finalist because of its solid security margin, good all-around performance, and innovative design.
  • Keccak was selected as a finalist, mainly due to its high security margin, its high throughput and throughput-to-area ratio and the simplicity of its design.
  • Although Luffa is an above-average performer, especially in hardware, it has not received as much cryptanalysis as many of the other second-round candidates. The little cryptanalysis there has been on Luffa, however, raises significant questions about its security; the security margin of the compression function is quite small, and full distinguishers on the sub-permutations have also been discovered. In addition, there is no published security proof showing that even strong sub-permutations would lead to a strong hash function. Therefore, Luffa was not selected as a finalist.
  • Shabal uses a novel design for its mode of iteration and basic building blocks. It was not, however, selected as a finalist, mainly due to security concerns. Although the security of the full hash algorithm was not compromised, the discovery of non-randomness properties with low time complexities raised concerns among NIST’s cryptographers about the possibility of more powerful attacks in the future. While Shabal’s security proof was modified to take known attacks into account, it did not convince NIST’s cryptographers that Shabal would remain secure against future attacks.
  • SHAvite-3 was not selected as a finalist, due to the lack of security in the key schedule of the underlying block cipher, leading to a relatively low security margin for the 512-bit version of the hash function. In addition, SHAvite-3 has a relatively low throughput-to-area ratio.
  • SIMD was not selected as a finalist, due to its large area requirements and the existence of the symmetric states.
  • Skein was selected as a finalist, mainly due to its high security margin and speed in software.

Interestingly, reading this, one can speculate a bit on NIST’s internal discussions based on the length of the justification paragraph: while Blake, JH, Keccak and Skein, as well as ECHO, Hamsi, Shavite-3 and SIMD appear to have been easy candidates for selection and  non-selection, respectively, more justifications are provided for the seemingly borderline candidates BMW, CubeHash, Fugue, Luffa, Shabal and Grøstl, the latter looking like being the more discussed finalist. But this last paragraph is only pure personal speculation, of course !

HEIG-VD IT Security Days – Day #1 Program

IT Security Days @ HEIG-VDI am very happy and excited to announce the program of the first event of the HEIG-VD IT Security Days, devoted to “Ethical Hacking”, which will happen on next Wednesday, February 9th, 2011, on the HEIG-VD campus in Yverdon-les-Bains. Of course, it is not too late to register ! The alert reader will note a small change in the list of speakers: Ivan Buetler will not able to give his talk, and will be replaced by his colleague Walter Sprenger, CEO of Compass Security AG.

  • 08h45: Doors opening and registration
  • 09h15: Welcome words by Christian Kunze, director of HEIG-VD, Pascal Junod, professor of information security at HEIG-VD and co-organizer, and Jacqueline Reigner, president of CLUSIS.
  • 09h30: Marc Ricca, IRIS, CEO, “Smartphone Client-Side Hacking“: Smartphone platforms are increasingly preferred targets for software-based attacks, as they nowadays contain sensitive information similarly to traditional computers, while allowing for numerous additional impact scenarios (audio eavesdropping, communication interception, user tracking, etc.). In this talk, Marco presents the landscape of attack scenarios against popular smartphone devices, and explores possible impacts. Attack vectors and case studies are presented, while spying payloads are demonstrated to the audience.
  • 10h30: Morning break
  • 11h00: Walter Sprenger, Compass Security AG, CEO, “Social Engineering Attacks“: This talk will focus on attack theory, social engineering as well as the benefits of social engineering tests and include a live demo (trojan preparation on a USB stick, trojan execution, and information leak to the attacker).
  • 12h15: Lunch break in the cafeteria l’Orangeraie
  • 14h00: Paul Such, SCRT, CEO, “Ethical Hacking in Romandie, Feedback from the Field“: During this talk we will give a feedback about nearly 10 years of Ethical hacking in Romandie : what are our customers common fears, how they evolved, what are the most common vulnerabilities, what were the major problems we encountered. This talk will also present the evolution of Ethical hacking and will try to highlight the differences in doing ethical hacking for various types of customers.
  • 15h00: Afternoon break
  • 15h30: Martin Vuagnoux, independent consultant, “Security Analysis of the Un-hackable Victorinox Secure Device“: In 2010, Victorinox proposed a new USB storage device with data access secured with biometric fingerprints. According to the press release, this device contains several uncommon protections such as custom fingerprint reader with blood oxygen and temperature sensor, custom designed “MKI Schnuffi-X” chip and self-destruct mechanism if chip is
    physically attacked. In 2010 and 2011, Victorinox organized several challenge contests (Las Vegas, London, Geneva) called “break the code”. The winning prize was up to 250k$ to whom is able to hack the “un-hackable” Victorinox Secure Device. Until today, nobody has won the contest. In this talk, we analyze the security of the “un-hackable” Victorinox Secure Device. We demonstrate that this product does not contain all the security mechanism described in the press release. We also show that the biometric authentication can be easily bypassed with tools such as notepad.exe. Finally we explain why it is very hard to win the contest even if the device is unafe.
  • 16h30 End of manifestation