Archive for the ‘misc’ Category

Ron was wrong, Whit is right – Weak keys in the internet

April 6th, 2012 No comments

Today, Maxime Augier gave a great talk about the state of security of the internet PKI infrastructure. The corresponding paper written by Lenstra, Hughes, Augier, Bos, Kleinjung, and Wachter was uploaded to archive a few weeks ago. In a nutshell, they found out that some RSA keys, that is often used in the SSL/TLS protocol to secure internet traffic, are generated by bad pseudo random number generators and can be easily recovered, thous providing no security at all.

The RSA cryptosystem

RSA is one of the oldest and most famous asymmetric encrytion schmes. The key generation for RSA can be summarized as follows:

For a given bitlength l (for example l = 1024 or l = 2048 bits), choose randomly two prime numbers p and q of of bitlength l/2. Choose a number 1 < e < (p-1)*(q-1), that has no divisor in common with (p-1)*(q-1). Many people choose e = 2^{16+1} here for performance reasons, but other choices are valid as well. Now, the number n = p*q and e form the public key, while d = e^{-1} \bmod (p-1)*(q-1) is the private key. Sometimes, the numbers p and q are stored with the private key, because they can be used to accelerated decryption.

To encrypt a message m, one just computes , and to decrypt a message, one computes m = c^d \bmod n. However, we don’t need that for the rest of this text can safely ignore that.

How random do these numbers need to be?

When generating cartographic keys, we need to distinguish between just random numbers and cryptographically secure random numbers. Many computers cannot generate real random numbers, so they generate random numbers in software. For many applications like computer games and for example simmulations of experiments, we only need number that seem to be random. Functions like “rand()” from the standard c library provide such numbers and the generation of these numbers is often initialized from the current system time only.

For cryptographic applications, we need cryptographically secure random numbers. These are numbers that a generated in a way, that there is no efficient algorithm, that distinguish them from real random numbers. Generating such random numbers on a computer can be very hard. In fact, there have been a lot of breaches of devices and programs, that used a bad random number generator for cryptographic applications.

What has been found out?

From my point of view, the paper contains two noteably results:

Many keys are shared by several certificates

6 185 228 X.509 certificates have been collected by the researchers. About 4.3% of them contained an RSA public key, that was also used in another certificate. There could be several reasons for this:

  • After a certificate has expired, another certificate is issued, that contains the same public key. From my point of view, there is nothing wrong with doing that.
  • A company changes their name or is taken over by another company. To reflect that change, a new certificate is issued, that contains another company name, but still uses the same key. I don’t see any problems here either.
  • A product comes with a pre-installed key, and the consumer has to request an certificate for that key. The same key is shipped to several customers. From my point of view, this is really a bad idea
  • Or there might be really a bad random number generator in some key generation routines, that two entities that are not related come up with the same RSA public (and private) key. This is a security nightmare.

Some keys share a common divisor

This is definitely not supposed to happen. If two RSA keys are generated, that share a common divisor by the same or by different key generation routines, the private key for both public keys can be easily determined, and the key generation routine is deeply flawed.

What are the consequences?

For those, who use an RSA public key, that shares a modulus with another different RSA public key, their key provides no protection at all. All implementations, that generated these keys definitely need to be updated and the certificates using the weak keys need to be revoked.

Which devices and vendors are affected?

Because disclosing the list of affected devices and vendors would compromise the security of these systems immediately, and allow everyone to recover their secret RSA keys, this has not been disclosed.

Categories: misc Tags:

GMR-1 cipher specifications are now public

February 7th, 2012 No comments

A reference implementation of the GMR-1 cipher has now been released. You can download the sourcecode from

Here are the most important facts in a nutshell:

  • 4 Linear Feedback Shift registers in Fibonacci configuration.
  • 81 bits of state
  • Registers 1, 2, and 3 of length 19, 22, and 23 bits control the output
  • Register 4 of length 17 bits controls the clocking of registers 1, 2, and 3, and does not contribute to the output
  • Clocking control is a simple majority clocking, so that registers are clocked 0 or 1 times
  • The output combiner is a quadratic function

So in fact, this cipher looks like a A5/2 clone from GSM.

Categories: misc Tags:

Message from your host: Resurrection

January 19th, 2009 No comments

The last post on this blog has been almost a year ago. A lot has changed in my life since. I have long thought about whether I should shut down this blog or resurrect it.

Finally, somewhen this weekend I have decided on resurrecting it after attending the Seminar on Symmetric Cryptography in Dagstuhl last week. A couple of things will change, I will probably relocate to a new server, but everything should be running smoothly again by the end of the week.

Expect new content soon.

Categories: misc Tags:

PolyBoRi has been released

November 23rd, 2007 No comments

Michael Brickenstein and Alexander Dreyer have released the first beta version of PolyBoRi (version 0.1). Congratulations! If you haven’t heard of it yet, here’s the blurb: 

“The core of PolyBoRi is a C++ library, which provides high-level data types for Boolean polynomials and monomials, exponent vectors, as well as for the underlying polynomial rings and subsets of the powerset of the Boolean variables. As a unique approach, binary decision diagrams are used as internal storage type for polynomial structures. On top of this C++-library we provide a Python interface. This allows parsing of complex polynomial systems, as well as sophisticated and extendable strategies for Gröbner base computation. PolyBoRi features a powerful reference implementation for Gröbner basis computation.”

 I expect great things from PolyBori for the field of algebraic cryptanalysis. If you are interested in polynomial system solving, please also make sure to read the paper by the authors on the techniques used in PolyBori in the electronic proceedings of MEGA 2007.

Categories: misc Tags:

Shortcomings of the Windows PRNG

November 7th, 2007 No comments

Leo Dorrendorf, Zvi Gutterman and Benny Pinkas presented interesting research at the ACM CCS 2007 conference lately. An updated version of their paper on attacks against the Windows 2000 PRNG has now appeared on the IACR ePrint archive. Since they only had access to the PRNG DLL binaries, they had to reverse-engineer these first to get started. Their devastating result: The Windows PRNG offers neither forward and backward security, allowing an attacker learning the internal state of the generator to predict 128kBytes of past and future output. The PRNG runs in user-space and each process uses its own instance. If I read the paper correctly, the same PRNG was used for all versions of Windows between Windows 95 up to Windows XP [caveat: they analysed a Windows 2000 build and haven't practically checked their results against other OS versions yet]. Practically speaking, this means that a successful remote exploit against your browser on these platforms is also in the position to reveal 600-1200 of your past SSL session keys by sending out the internal PRNG state. It remains to be seen whether this carries over to Vista – my rather uneducated guess here is that it does not, but that remains to be seen.

Zvi Gutterman has co-authored a number of interesting papers on PRNGs, namely analyses of the Linux PRNG [ePrint version] and of the Java session ID generation.

[Disclaimer: I met Zvi at the first ECRYPT summer school in Samos back in 2005. Way to go, man, way to go!]

Update [2007-11-22]: Apparently Microsoft has admitted that the same flaw still is present in Windows XP. And of course: No, this is no security vulnerability, according to Microsoft, since the attacker must have had access in the first place. Still they claim that Windows Vista does not exhibit the same mistake. This however has not yet been independently verified.

Categories: misc Tags:

Eurocrypt 2007: list of accepted papers is online

February 11th, 2007 2 comments

The list of accepted papers for Eurocrypt 2007 has been announced. The conference will be taking place from May 20th to 24th 2007 in Barcelona, Spain.

Categories: misc Tags:

ECRYPT PhD summer school

February 1st, 2007 No comments

The following announcment just in from several mailing lists. I attended the summer school two years ago and have to say that it was definitely worthwile! Mark your calendars if you’re a PhD student working in the field of cryptology and are interested in cryptanalysis.

Emerging Topics in Cryptographic Design and Cryptanalysis

30 April – 4 May, 2007
Doryssa Seaside Resort – Samos, Greece


Following the great success of the ECRYPT PhD Summer School on
Cryptanalysis in 2005, the Symmetric Techniques and Asymmetric Techniques
Virtual Laboratories are pleased to announce a new joint Summer School on
Emerging topics in Cryptographic Design and Cryptanalysis. Covering
selected topics in both symmetric and asymmetric cryptography, this summer
school will provide a thorough overview of some of the most important
cryptographic design and cryptanalysis techniques that have emerged in
recent years. While the summer school is aimed primarily at postgraduate
students, attendance is open to all.

The ECRYPT Summer School on Emerging Topics in Cryptographic Design and
Cryptanalysis will take place at the Dorissa Seaside Resort, in Samos,
Greece, from April 30th to May 4th, 2007.

The Summer School will cover the following topics:

  • Design and Cryptanalysis of Hash Functions
  • Design and Cryptanalysis of Stream Ciphers
  • Pairing-based Cryptography
  • Gröbner Bases techniques in Cryptography

Preliminary list of speakers

Olivier Billet, France Télécom R&D
Bruno Buchberger, RICAM
Anne Canteaut, INRIA
Carlos Cid, Royal Holloway, University of London
Christophe De Cannière, K.U. Leuven
Jean-Charles Faugère, LIP6/INRIA
Thomas Johansson, Lund University
Lars Knudsen, DTU – Technical University of Denmark
Tanja Lange, TU Eindhoven
Benoît Libert, UCL Crypto Grouo
Christof Paar, Ruhr University Bochum
Kenny Paterson, Royal Holloway, University of London
Ludovic Perret, UCL Crypto Group/LIP6
Bart Preneel, K.U. Leuven
Christian Rechberger, T.U. Graz
Michael Scott, Dublin City University
Nicolas Sendrier, INRIA
Jacques Stern, Ecole Normale Supérieure


A limited number of stipends will be available for students from
non-ECRYPT institutions. Please let us know before April 2nd if you are
interested, by sending a mail to:

Carlos Cid
Information Security Group
Royal Holloway, University of London
Egham, Surrey
TW20 0EX
United Kingdom
Tel: +44 (0)1784 414685
carlos.cid [AT]


Ludovic Perret
Crypto Group
Tel: +32 (0) 10 47 22 84
ludovic.perret [AT]

Categories: misc Tags: