15/09/2016 – Talk by Matus Nemec

Title: The Million-Key Question – Investigating the Origins of RSA Public Keys
Time: 10:45
Location: Meeting room
Type: Research Result
Speaker: Matus Nemec
Abstract: Can bits of an RSA public key leak information about design and implementation choices such as the prime generation algorithm? We analysed over 60 million freshly generated key pairs from 22 open- and closed source libraries and from 16 different smartcards, revealing significant leakage. The bias introduced by different choices is sufficiently large to classify a probable library or smartcard with high accuracy based only on the values of public keys. Such a classification can be used to decrease the anonymity set of users of anonymous mailers or operators of linked Tor hidden services, to quickly detect keys from the same vulnerable library or to verify a claim of use of secure hardware by a remote party.

Our broad inspection provides a sanity check and deep insight regarding which of the recommendations for RSA key pair generation are followed in practice, including closed-source libraries and smartcards. The classification of the key origins of more than 10 million RSA-based IPv4 TLS keys and 1.4 million PGP keys also provides an independent estimation of the libraries that are most commonly used to generate the keys found on the Internet.

Talk based on: https://www.usenix.org/conference/usenixsecurity16/technical-sessions/presentation/svenda

Title: EACirc – Advancing cryptanalytic methods through evolutionary computing
Time: 11:30
Location: Meeting room
Type: Research Result
Speaker: Matus Nemec
Abstract:Cryptographic algorithms (primitives and protocols) always have to go through elaborate testing by skilled experts to assert their overall security. The history carries many examples of serious flaws in cryptographic algorithms that rise concerns about the design and strength of the primitives.

Some automation is possible in the first phases of a cryptanalysis, e.g., by using randomness testing suites. These tools can be applied to check statistical properties of cryptographic algorithm output, to look for a deviation from randomness. Such a defect signalizes a potential flaw in the algorithm design. Yet such testing suites are limited only to predefined pattern testing for certain statistical defects, therefore others will go unnoticed.

We propose a more open approach based on an automatically generated distinguisher in the form of a multiple-output logic function (MOLF) designed by evolutionary algorithms to search for undesired statistical anomalies in the algorithm output. With contrast to the fixed sets of tests, our approach builds a distinguisher automatically, on-the-fly and adaptively to the evaluated algorithm output. This opens up new possibilities for discovering potential weaknesses that remained hidden from statistical tests and even cryptanalyst sights.