[cryptography] Duplicate primes in lots of RSA moduli

Marsh Ray marsh at extendedsubset.com
Wed Feb 22 23:24:57 EST 2012

On 02/22/2012 08:44 PM, Peter Gutmann wrote:
> Marsh Ray<marsh at extendedsubset.com>  writes:
>> Obviously this story is made up and probably not even fully
>> consistent. But having worked a little bit around hardware
>> engineers it seems to me like a very plausible scenario, if not
>> typical.
> It's actually pretty spot-on until about the "I notice the TI CC2530
> uses a LFSR" bit, which I think would be going a bit far for many
> hardware engineers.

I think you're right, it doesn't really fit the narrative.

In fact, I nearly took it out of my story a couple of times while
writing it. But I decided to leave it in because I thought it
illustrated the odd assortment of experience (and data sheets) that 
factor in to the decision process.

The TI CC2530 is an interesting case study in its own right.

It's a lightweight embedded CPU designed for maximally-cheap ZigBee
applications, such as smart grid power meters.

I chose it as an example because it was designed by a leading company
(Texas Instruments) presumably by professional EEs and it also shipped 
with a serious RNG vulnerability.

> http://travisgoodspeed.blogspot.com/2009/12/prng-vulnerability-of-z-stack-zigbee.html

 From the original datasheet:
> The random-number generator uses a 16-bit LFSR to generate
> pseudorandom numbers, which can be read by the CPU or used directly
> by the command strobe processor. The random numbers can, e.g., be
> used to generate random keys used for security.

A chip with a dedicated AES coprocessor and a 16-bit LFSR RNG.
Hmm.. what could possibly go wrong?!

Revision B of the data sheet contains a change notice that it "Removed
sentence that pseudorandom data can be used for security".

> These are guys who pride themselves in being able to construct a
> working PWM from toothpicks, a case of 3/18" boxcar prawns, and
> cannibalised parts from a Speak-n-Spell.

Obviously 99.8% of the certs detected in the scan did not have a
problem. But it all depends on who you get, and there are some
qualified, competent digital engineers who would have difficult time
steering this entropy request through their company's design process.

> A zener and a Schmitt trigger will do fine,

Hmmm. Do you have a circuit diagram for that?

But assuming that works, will a Zener and Schmitt trigger fit within an
all-digital ASIC design process? I don't know about the Schmitt, but I'm
pretty sure the Zener will not.

How much will an external Zener and pullup resistor cost? Probably about
$0.02 per unit (mouser.com), times a few hundred thousand units.

> or clock drift between something and something else.

Sounds like an attractive plan. At least, if you actually have multiple 
clocks available in the design.

> It shouldn't take more than ten minutes to solve, and then we can get
> back to solving real problems like those odd noise spikes in the
> sensor input.
> (I don't mean that in any kind of negative way, an embedded systems
> engineer would - or at least should - be very good at getting
> hardware working under adverse conditions, but shouldn't be expected
> to be a security geek).

I worked at one place where we designed and sold several models of
expensive special purpose PCI cards that went in high capacity servers.

It was all digital. In fact, there was only one multimeter in the entire
company. We know this because an ISO auditor found it and noted that it
did not have a calibration sticker. So the multimeter had to be
effectively kept in a locked cabinet.

When we wanted to recover some very old data from an antique computer, I
had to bring in my own scope and take apart another old monitor in order
to rig up a temporary display for the thing.

Again, these were very high-quality products we made. But it seems that
some computer engineering teams might do almost everything they can to
avoid dealing with any kind of analog signals.
They're just too unpredictable!

>> if *I* had been in that product design meeting, what could I have
>> said to convey the real issue in concrete terms that would have
>> focused the attention where it needed to be in order to avoid the
>> mass vulnerability.
> I've been involved in situations like this, and once you get over a
> very, very small threshold "just make it go" overrides everything
> else.

I figure the voice for security might get about two minutes of real
attention to make his pitch, unless he suggests adding some unfamiliar
discrete circuits to the design, in which case it will be over a lot faster.

> In the end the quality of the RNG often comes down to how much time
> and effort the individual tasked with doing whatever part of the
> system it's associated with decides to invest in it.

Well, it doesn't help to have experts running around telling the
manager things like "It shouldn't take more than ten minutes to solve". :-)

> I've seen the bare minimum, I've seen pretty good (if somewhat
> uninformed) attempts, I've seen people distract themselves for three
>  weeks with Diehard and then cobble something together at the last
> minute, it usually ends up coming down to what one individual feels
> like doing.

Which is really not the way engineering ought to be done, especially
when the consequences of it being wrong bring serious security problems
for the customers (and great costs and potential liabilities for the

But this is actually something that engineering processes are typically
really good at, once it has been explained in a way that the necessity
of the requirement really sinks in.

For this to happen it may take a word better than "entropy", or at least 
a definition we can better relate to.

- Marsh

More information about the cryptography mailing list