Re: questions about RNGs and FIPS 140

2010-09-07 Thread Thierry Moreau

Ben Laurie wrote:

On 27/08/2010 19:38, Joshua Hill wrote:

The fact is that all of the approved deterministic RNGs have places that
you are expected to use to seed the generator.  The text of the standard
explicitly states that you can use non-approved non-deterministic RNGs
to seed your approved deterministic RNG.


This is nice.


It's an even better situation if you look at the modern deterministic RNGs
described in NIST SP800-90. (You'll want to use these, anyway.  They are
better designs and last I heard, NIST was planning on retiring the other
approved deterministic RNGs.) Every design in SP800-90 requires that your
initial seed is appropriately large and unpredictable, and the designs all
allow (indeed, require!) periodic reseeding in similarly reasonable ways.


Given that we seem to have agreed that unpredictable is kinda hard,
I'm amused that SP800-90 requires it. If it is a requirement then I
wonder why NIST didn't specify how to generate and validate such a seed?



Well, I find SP800-90 Annex C (Entropy and Entropy Sources) quite clear 
about the requirements. If nothing is approved, we may guess it's 
because no unpredictable phenomenon has been shown (convincingly) to be 
compliant.


In terms of solution documentation requirements, I see four stages:
1) unpredictable phenomenon,
2) sensor technology,
3) digitalization,
4) conditioning.

I separate 2 and 3 while NIST seems to merge them. I see them separate 
since the sensor technology is seldom developed with the entropy 
collection application in mind (the unpredictable phenomenon is not 
engineered: it just exists). The digitalization refers to the 
algorithmic processing taking raw A-to-D (analog to digital) data and 
giving some discrete measurement of the unpredictable phenomenon. This 
measurement is basically a convenient intermediate representation using 
a physical characteristic that is better understood, for analysis 
purposes, than the raw A-to-D data.


The digitalization algorithm may be the same as for pre-existing uses of 
the sensor technology, in which case an after-the-fact certification is 
challenging.


NIST seems to favor very well defined algorithms for affixing the NIST 
approved mark. The, the digitalization algorithm for a given pair 
unpredictable phenomenon,sensor technology may be challenging.


I released (a few days ago) a specification document for digitalization 
and conditioning algorithms for PUDEC, Practical Use of Dice for Entropy 
Collection, see http://www.connotech.com/doc_pudec_algo.html


Incidentally, another difficulty is that confidence in the entropy 
collection function is difficult to support with boot time / run time 
testing. IIRC, the statistical testing at boot time had to be dropped 
from the FIPS140 requirements because false failures (intrinsic to 
statistical testing) were not manageable in an operational context.


Obviously, there are other considerations to NIST approval because it 
would become a procurement specification for the US Federal government.





Cheers,

Ben.




Regards,

--
- Thierry Moreau

CONNOTECH Experts-conseils inc.
9130 Place de Montgolfier
Montreal, QC, Canada H2M 2A1

Tel. +1-514-385-5691

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: Randomness, Quantum Mechanics - and Cryptography

2010-09-07 Thread Marsh Ray

On 09/06/2010 09:49 PM, John Denker wrote:


If anybody can think of a practical attack against the randomness
of a thermal noise source, please let us know.  By practical I
mean to exclude attacks that use such stupendous resources that
it would be far easier to attack other elements of the system.


Blast it with RF for one.

Typically the natural thermal noise amounts to just a few millivolts, 
and so requires a relatively sensitive A/D converter. This makes it 
susceptible to injected unnatural noise overloading the conversion and 
changing most of the output bits to predictable values.


Using digital outputs from an enclosed module with enough shielding 
could probably prevent it. But there are plenty of environments which 
are too small (e.g., smart cards) or are potentially in the hands of the 
attacker for an extended period of time (smart cards, DRM devices, power 
meters, etc.).


- Marsh

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: Randomness, Quantum Mechanics - and Cryptography

2010-09-07 Thread John Denker
On 09/07/2010 10:21 AM, Marsh Ray wrote:

 If anybody can think of a practical attack against the randomness
 of a thermal noise source, please let us know.  By practical I
 mean to exclude attacks that use such stupendous resources that
 it would be far easier to attack other elements of the system.
 
 Blast it with RF for one.

1) This is not an argument in favor of quantum noise over
thermal noise, because the same attack would be at least
as effective against quantum noise.

2) You can shield things so as to make this attack very,
very difficult.

3) The attack is detectable long before it is effective,
whereupon you can shut down the RNG, so it is at best a
DoS attack.  And then you have to compare it against
other brute-force DoS attacks, such as shooting the
computer with an AK-47.

 Typically the natural thermal noise amounts to just a few millivolts,
 and so requires a relatively sensitive A/D converter. This makes it
 susceptible to injected unnatural noise overloading the conversion and
 changing most of the output bits to predictable values.

Even the cheapest of consumer-grade converters has 16 bits of
resolution, which is enough to resolve the thermal noise and
still have _two or three orders of magnitude_ of headroom.  If
you are really worried about this, studio-grade stuff is still
quite affordable, and has even more headroom and better shielding.

How much RF are we talking about here?  At some point you can
undoubtedly DoS the RNG ... but I suspect the same amount of
RF would fry most of the computers, phones, and ipods in the 
room.

Is the RF attack in any way preferable to the AK-47 attack?

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Fw: Request for Comments - NIST Draft SP 800-135: Recommendation for Application-Specific Key Derivation Functions

2010-09-07 Thread Perry E. Metzger
Forwarded from the saag mailing list:

Begin forwarded message:

Date: Tue, 31 Aug 2010 16:18:48 -0400
From: Russ Housley hous...@vigilsec.com
Subject: [Cfrg] Request for Comments - NIST Draft SP 800-135:
Recommendation for Application-Specific Key Derivation Functions




 Original Message 
Subject: Request for Comments - NIST Draft SP 800-135: Recommendation
for Application-Specific Key Derivation Functions

NIST requests comments on Draft SP 800-135, Recommendation for
Application-Specific Key Derivation Functions.

The document specifies security requirements for existing
application-specific key derivation functions in: American National
Standard (ANS) X9.42-2001-Public Key Cryptography for the Financial
Services Industry: Agreement of Symmetric Keys Using Discrete
Logarithm Cryptography, American National Standard (ANS)
X9.63-2001-Public Key Cryptography for the Financial Services
Industry: Key Agreement and Key Transport Using Elliptic Curve
Cryptography, Internet Key Exchange, Secure Shell, Transport Layer
Security, The Secure Real-time Transport Protocol, User-based
Security Model for version 3 of the Simple Network Management
Protocol , and Trusted Platform Module. The document is available at
  http://csrc.nist.gov/publications/drafts/800-135/draft-sp800-135.pdf.

Please provide comments by September 30th 2010 to quynh.d...@nist.gov
with “Comments on Draft SP 800-135” in the subject line.

For additional questions, please do not use reply.  Contact Quynh Dang
(quynh.d...@nist.gov)

___

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: Randomness, Quantum Mechanics - and Cryptography

2010-09-07 Thread John Denker
On 09/07/2010 11:19 AM, Perry E. Metzger wrote:
  2) You can shield things so as to make this attack very,
  very difficult.
 I suspect that for some apps like smart cards that might be hard.
 OTOH, it might be straightforward to detect the attempt.

We should take the belt-and-suspenders approach:
 a) Do some reasonable amount of shielding, and
 b) detect the attack.

Detecting the attack is utterly straightforward.  

The primary defense is to close the loop around 
the noise-generating element.  That is, we inject 
a known calibration signal on top of the noise ... 
and use that to constantly check that the input
channel gain and bandwidth are correct.

The true noise level depends only on gain, bandwidth,
temperature, and resistance.  Blasting the system
with RF will not lower the temperature, so that's
not a threat.  So unless you have a scenario where
the RF lowers the resistance, lowers the gain,
and/or lowers the bandwidth 
_in a way that the calibrator cannot detect_
then this attack does not rise above the level of
a brute-force DoS attack, in the same category as 
the AK-47 attack or the stomp-the-smart-card-to-dust
attack.

The calibrator idea relies on the fact that the
computer's i/o system has an o as well as an i.

Note that this defense is equally effective against
both
 *) Continuing attacks, where a continuing RF blast
  drives the first stage amplifier into saturation, 
  without necessarily doing irreversible damage, and
 *) One-shot attacks, where a super-large blast does
  irreversible damage to the amplifier.



Secondary defenses, if you want to go to the trouble,
include putting a canary in the coal mine, i.e.
implementing a second sensor with a different gain,
bandwidth, and resistance.  I reckon that attacking
one sensor and getting away with it is only possible
on a set of measure zero, but the chance of attacking
two non-identical sensors without either one of them 
noticing is a set of measure zero squared.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: Randomness, Quantum Mechanics - and Cryptography

2010-09-07 Thread Marsh Ray

On 09/07/2010 12:58 PM, John Denker wrote:

On 09/07/2010 10:21 AM, Marsh Ray wrote:


If anybody can think of a practical attack against the randomness
of a thermal noise source, please let us know.  By practical I
mean to exclude attacks that use such stupendous resources that
it would be far easier to attack other elements of the system.


Blast it with RF for one.


1) This is not an argument in favor of quantum noise over
thermal noise, because the same attack would be at least
as effective against quantum noise.


Agreed.


2) You can shield things so as to make this attack very,
very difficult.


The point is that this it's a generic, relatively low-tech attack that 
is likely to be effective against a straightforward implementation of 
the general idea.



3) The attack is detectable long before it is effective,
whereupon you can shut down the RNG, so it is at best a
DoS attack.


Only if the engineers know about it and spend the resources to build in 
such resistances to it. So the system which consumes the entropy also as 
to look for the I'm not producing any more entropy signal as well. The 
proper operation of this signaling has to part of the test process. So 
now there needs to be a way to simulate the attack scenario for testing. 
Presumably this becomes another input to the system which itself must be 
test. All this adds time, cost, and complexity and it's not surprising 
that they don't always get it perfect.


There is some evidence that engineers designing chips that go into 
actual products (little stuff like girls' toys and smart grid power 
meters) aren't familiar with this:


http://www.flickr.com/photos/travisgoodspeed/4142689541/
This graph shows the counts of individual seed bytes in a poor random 
number generator. The sample width is a single integer, and the RNG byte 
is expected to be one of the very few spikes presented on this graph.


Note that the above description is a little confusing because there are 
multiple problems going on here. The seed bytes are coming from a 
poorly engineered radio source and are also going into a poor random 
number generator.


Here's a better description:
http://rdist.root.org/2010/01/11/smart-meter-crypto-flaw-worse-than-thought/


 And then you have to compare it against
other brute-force DoS attacks, such as shooting the
computer with an AK-47.


Well, the idea of physical stress attacks is that you get the system to 
do something it isn't supposed to do (e.g., sign with a weak nonce).



Typically the natural thermal noise amounts to just a few millivolts,
and so requires a relatively sensitive A/D converter. This makes it
susceptible to injected unnatural noise overloading the conversion and
changing most of the output bits to predictable values.


Even the cheapest of consumer-grade converters has 16 bits of
resolution, which is enough to resolve the thermal noise and
still have _two or three orders of magnitude_ of headroom.


Were they engineered for use with crypto to resist attack? Were they 
tested in an actively hostile RF environment?


It's really unwise to try to reason about the behavior of complex 
systems like digitial circuitry when operated outside of its absolute 
maximum specifications. You'd have to re-qualify them for such use.



If
you are really worried about this, studio-grade stuff is still
quite affordable, and has even more headroom and better shielding.


And it will not get built into any product if it costs $0.01 more unless 
the hardware engineer is unable to justify the additional expense.



How much RF are we talking about here?


Probably very little if the engineer didn't take special precautions.

Also the attacker gets to choose the frequency and direction from which 
the device is most susceptible and combine this will all other 
techniques simultaneously. For example, perhaps would run current 
through the external shielding or expose it to a static magnetic field 
(thus heating it or saturating its magnetic permeability).



At some point you can
undoubtedly DoS the RNG ... but I suspect the same amount of
RF would fry most of the computers, phones, and ipods in the
room.


So the attacker leaves his ipod out of the faraday cage in which he's 
abusing the smart card or DRM device.



Is the RF attack in any way preferable to the AK-47 attack?


The attacker doesn't necessarily have to completely eliminate all 
entropy from the output, just enough that he can make up the difference 
with brute force or analytic techniques.


http://focus.ti.com/docs/prod/folders/print/cc2531.html
Changes from Revision Original (September 2009) to Revision A Removed 
sentence that pseudorandom data can be used for security.


- Marsh

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: Randomness, Quantum Mechanics - and Cryptography

2010-09-07 Thread Perry E. Metzger
On Tue, 07 Sep 2010 11:56:25 -0700 John Denker j...@av8n.com wrote:
 The true noise level depends only on gain, bandwidth,
 temperature, and resistance.  Blasting the system
 with RF will not lower the temperature, so that's
 not a threat.

One could, however, run the card one is trying to attack under reduced
temperature and hit it with RF at the same time.

The question is, can you make it more expensive to do that than to,
say, buy a new parking card or whatever else the smart card is being
used for. If the attack is fairly cheap and repeatable and yields
something reasonably valuable, you have a problem. If you can make the
attack expensive and only yield something cheap, you're doing well.

 So unless you have a scenario where
 the RF lowers the resistance, lowers the gain,
 and/or lowers the bandwidth 
 _in a way that the calibrator cannot detect_

Don't assume, though, that the attacker can't lower the temperature in
most of the circuit, keep the tiny thermometer you included at room
temperature, and inject RF at the same time. Don't even assume they
will need to rip the device apart to do it. The only question is, can
you make it expensive enough to succeed to protect what you're trying
to protect.

Perry
-- 
Perry E. Metzgerpe...@piermont.com

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: Randomness, Quantum Mechanics - and Cryptography

2010-09-07 Thread Marsh Ray

On 09/07/2010 02:18 PM, Perry E. Metzger wrote:


The question is, can you make it more expensive to do that than to,
say, buy a new parking card or whatever else the smart card is being
used for. If the attack is fairly cheap and repeatable and yields
something reasonably valuable, you have a problem. If you can make the
attack expensive and only yield something cheap, you're doing well.


The designer often has wrong information about what the system will be 
used for. Most systems don't see much adoption and are discontinued 
because they don't make any money. Systems that succeed with low-value 
transactions tend to get repurposed for more and more important roles 
until the breaking point. SSL and Zigbee are two examples.


Imagine how much an additional shielded region would cost to a cell 
phone that's expected to sell 50 million units. An engineer is probably 
going to be trading that cost off against some other feature with a 
tangible benefit. When the junior engineer speaks up and says let's 
just use the microphone for entropy gathering instead he's going to be 
considered a hero for saving millions.


An additional consideration is that the device must also operate 
reliably when someone puts popcorn in the microwave or uses an arc 
welder in the next room. The detector must absolutely never create a 
false positive.


Most actual consumer products sold will prefer to continue insecure 
operation rather than shut off. For example, the GSM standard includes a 
mechanism to notify the user on the display if they're connected to a 
cell tower with an unencrypted signal. Cell carriers typically disable 
this notification, presumably because it tangibly increases support 
costs for a benefit that appears highly theoretical. It's usually only 
when it's the interests of the manufacturer that are being protected 
that a device will actually go out of its way to find a reason to cease 
operation (e.g., DRM).


- Marsh

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com