Re: using SRAM state as a source of randomness
Aloha! Leichter, Jerry skrev: So presumably the model is: Put each manufactured chip into a testing device that repeatedly power cycles it and reads all of memory. By simply comparing values on multiple cycles, it assigns locations to Class 1 or 2 (or 3, if you like). Once you've done this enough to have reasonable confidence in your assignments, you pick a bunch of Class 1 locations and use them for the id; and a bunch of Class 2 locations and call them the entropy source. You burn the chosen locations into ROM on the chip. At power up, the chip checks the ROM, and constructs an ID from the list of Class 1 locations and a random value from the list of Class 2 locations. (Obviously, you want to be a bit more clever - e.g., if all your Class 1 locations hold the same value on every power up, something is wrong with your assumptions and you reject the chip rather than using an ID of all 0's or all 1's. The paper is asserting that this won't happen often enough to matter.) Yes, that is one way to do it - but its not the way they do it in the paper. Doing it your way, that is writing the bit locations for the ID and RNG sources into an index mem on chip, goes against the purpose of the presented scheme. As they write in the paper: quote The non-volatile approach involves programming an identity into a tag at the time of manufacture using EPROM, EEPROM, flash, fuse, or more exotic strategies. While non-volatile identities are static and fully reliable, they have drawbacks in terms of the process cost and the area cost of supporting circuitry. Even if only a small amount of non-volatile storage is used, the process cost must be paid across the entire chip area. /quote One could also argue that if you add the functionality (the non volatile storage) and take the post-production time (and cost) to write down the locations, you could just as well write down a normal ID. (You have the same conclusion futher down in your mail.) If you do it the way they do it in the paper - communicate the SRAM mem state to an extrnal source to have your ID extracted for you - doesn't that change the ID and authentication protocol? This is only done during manufacturing. Presumably it would be integrated into the testing process, which you're doing anyway. Nope, again the paper is (pretty) clear that the external reader receives the mem dump and then extracts the ID fingerprint using hamming distance to match the mem dump with a DB of known IDs. This also means that your Class 2 bits (the RNG sources) will be communicated, something that I see as a security problem. Finally. I have been in contact with the authors regarding their view on rememanence problemns and they simply wait long enough to allow remanence effects to be nullified. But as I see it the device have no way of knowing that long enough time have passed. And if it hasn't, communicating the SRAM state might lead to appication information leakage. Correct? The unique ID stuff is clever, but it's not clear how much it gains you: Since you need to do some final per-device programming anyway to identify the locations to be used for the ID, why not just burn in a unique ID? Exactly. The random generator is clever, but the question is whether produces an unpredictable result is really a stable characteristic of memory. As Peter Gutmann stated earlier in this thread: RAM state is entropy chicken soup, you may as well use it because it can't make things any worse, but I wouldn't trust it as the sole source of entropy. Device aging, changes is the manufacturing process, electrical and environmental changes (accidental or deliberately) will all affect the RNG, and there is no easy way for the (low cost) device to know how good or bad quality of the RNG is. -- Med vänlig hälsning, Yours Joachim Strömbergson - Alltid i harmonisk svängning. Kryptoblog - IT-säkerhet på svenska http://www.strombergson.com/kryptoblog - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: using SRAM state as a source of randomness
Aloha! Peter Gutmann skrev: So RAM state is entropy chicken soup, you may as well use it because it can't make things any worse, but I wouldn't trust it as the sole source of entropy. Ok, apart from the problems with reliable entropy generation. I'm I right when I get a bad feeling when I think about the implications of how the device ID is established. As I understand it, the device itself doesn't know it's ID. Instead you repeatedly send over mem dumps to the reader which then extracts what it (to some estimated degree) consider to be the correct ID. Wouldn't a simple thing like a challenge response and become much more complicated - and insecure? Basically the device goes from saying: I'm ID XYZ and to prove it by providing the following response to your challange, to I'm an amnesiac device and here are my mem dump, please calculate my ID (please remember to power-cycle me x times) and then I'll send a response. Also, wouldn't the ID-scheme presented in the paper take a very long time. Transferring 256 Bytes * x times + hamming calc (by the host) vs reading 64 bits (or similar ID length)? I give the paper plus marks for novelty, but can't see how to use this in a secure, practical and cost efficient way. -- Med vänlig hälsning, Yours Joachim Strömbergson - Alltid i harmonisk svängning. Kryptoblog - IT-säkerhet på svenska http://www.strombergson.com/kryptoblog - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: using SRAM state as a source of randomness
On Tue, 18 Sep 2007, James A. Donald wrote: Using SRAM as a source of either randomness or unique device ID is fragile. It might well work, but one cannot know with any great confidence that it is going to work. It might work fine for every device for a year, and then next batch arrives, and it completely fails. Worse still, it might work fine on the test batch, and then on the production run fail in ways that are subtle and not immediately obvious. And you might get better results from cheaper ram which may fail more often. (Adding a different sort of randomness.) I have a friend who is a hardware engineer who is preparing a talk on just this sort of issue with the state of DRAM chips. It will be interesting to see what he says. (For those people in Portland, OR, it will be given at the PLUG Advanced Topics meeting sometime early next year.) -- Never trust a queue structure designed by a cryptographer. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: using SRAM state as a source of randomness
On Mon, 17 Sep 2007 11:20:32 -0700 Netsecurity [EMAIL PROTECTED] wrote: Back in the late 60's I was playing with audio and a magazine I subscribed to had a circut for creating warble tones for standing wave and room resonance testing. The relevance of this is that they were using a random noise generating chip that they acknowledged was not random enough for good measurements. The fix suggested was to parallel a number, six as I recall, to improve the randomness by mixing the signals to achieve better randomness. I don't recall the math but the approach improved the randomness by more than an order of magnitude. I have also seen the same effect on reverse biased zener diodes used as random noise generators and that seemed - no real hard measurements that I can recall - to work quite well. Mind you these were not zeners all fabricated on a single chip, but rather individuals soldered together so the charateristics of each were more random because of the semi-randomness of the manufacturing process. This is an old technique. We could even go back to von Neumann's scheme: look at two successive bits. If they're equal, discard them. Otherwise, map 0,1 to 0 and 1,0 to 1. See the section on Software whitening in http://en.wikipedia.org/wiki/Hardware_random_number_generator (which was correct as of when I looked at it, a few minutes before the timestamp on this email; check the Wiki history to be sure). --Steve Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: using SRAM state as a source of randomness
Netsecurity wrote: Back in the late 60's I was playing with audio and a magazine I subscribed to had a circuit for creating warble tones for standing wave and room resonance testing. The relevance of this is that they were using a random noise generating chip that they acknowledged was not random enough for good measurements. The fix suggested was to parallel a number, six as I recall, to improve the randomness by mixing the signals to achieve better randomness. I don't recall the math but the approach improved the randomness by more than an order of magnitude. If one such chip was so non random that the ear could hear the difference from white noise or pink noise, it is most unlikely that six together would be random enough for cryptographic purposes. As has often been stated on this list, the noise source must be understood, so that we have physical theory as to where the noise is coming from, and also tested to make sure it is functioning in accord with theory. No one really understands where zener diode noise is coming from. True entropy in equals true entropy out. You need to be able to determine the true entropy in from physical theory, and be able to test the hardware to check it is working in accordance with theory. To know that a true random number generator is cryptographically secure, you need knowledge of the underlying hardware, knowledge that shows it derives its randomness from the fundamental randomness of the universe, either thermal entropy, (Johnson noise) or quantum indeterminacy (shot noise), knowledge that enables us to determine the good functioning of the underlying noise amplification circuits from the character of the output. A good circuit would simply directly amplify the underlying noise source, so that the entropy of the output would be somewhat less than one entropy bit per signal bit, thus ensuring that any malfunction of the underlying circuit would be obvious, and then pass that output into a hash generator, which emits hash that outputs less bits than the true entropy. Using SRAM as a source of either randomness or unique device ID is fragile. It might well work, but one cannot know with any great confidence that it is going to work. It might work fine for every device for a year, and then next batch arrives, and it completely fails. Worse still, it might work fine on the test batch, and then on the production run fail in ways that are subtle and not immediately obvious. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: using SRAM state as a source of randomness
Udhay Shankar N [EMAIL PROTECTED] writes: Sounds like an interesting idea - using SRAM state as a source of randomness. Any of the folks here willing to comment on this? The paper actually covers two (related) things, fingerprint extraction and using SRAM power-up state as a random number source/seed, I assume your question is about the latter so I'll only address that. In addition I'm not sure if you're looking only at RAM state in limited embedded devices or are wondering whether it's a good source in general, e.g. in desktop PCs, so I'll assume both. The problem with using device state in this manner is that it's *completely* dependent on the device technology and environment in which it's used. Any change in the manufacturing process can change the results. Any change in the environment (temperature, supply voltage, etc) can change the results. A deliberate attack, for example irradiating the device to change the RAM cell threshold, can change the results. Even without deliberate modification, SRAM cells that store a constant value tend to acquire a set over time in which they'll come up in that state when powered on (this has happened with crypto hardware storing keys over long periods of time in SRAM). In a PC, the +5VSB may trickle enough power through the RAM to retain state for some time after the machine is powered off, or possibly more or less indefinitely unless the power is physically removed (I've measure 3-5W power consumption on several PCs in the suppsedly turned-off state, which indicates that the +5VSB is powering parts of the system). ECC memory scrubbing may set the RAM into a predetermined state. A slow memory test during POST (which writes all cells rather than doing a quick test with a large stride) would have the same effect. The list goes on and on... The worst case is a change in the environment or manufacturing process, which typically occurs without the end user even knowing about it. You simply can't guarantee anything about RAM state as an RNG source, you'd have to prove a negative (no change in manufacturing technology or the environment will affect the quality of the source) in order to succeed. It's like the thread-timing- based RNGs, you can never prove that some current variation of or future change to the scheduler won't result in totally predictable random numbers. So RAM state is entropy chicken soup, you may as well use it because it can't make things any worse, but I wouldn't trust it as the sole source of entropy. What I'd use is a device fingerprint (which is never revealed) seeding a PRNG with a counter in nonvolatile memory to ensure the PRNG state never repeats. However the publication of the fingerprint for device ID purposes tends to negate this usage. Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: using SRAM state as a source of randomness
Aloha! Peter Gutmann skrev: The worst case is a change in the environment or manufacturing process, which typically occurs without the end user even knowing about it. You simply can't guarantee anything about RAM state as an RNG source, you'd have to prove a negative (no change in manufacturing technology or the environment will affect the quality of the source) in order to succeed. It's like the thread-timing- based RNGs, you can never prove that some current variation of or future change to the scheduler won't result in totally predictable random numbers. One could add test functionality that checks the randomness of the initial SRAM state after power on. But somehow I don't think a good test suite and extremely low cost devices (for example RFID chips) are very compatible concepts. -- Med vänlig hälsning, Yours Joachim Strömbergson - Alltid i harmonisk svängning. Kryptoblog - IT-säkerhet på svenska http://www.strombergson.com/kryptoblog - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: using SRAM state as a source of randomness
On Sep 12, 2007, at 7:06 AM, Udhay Shankar N wrote: Sounds like an interesting idea - using SRAM state as a source of randomness. Any of the folks here willing to comment on this? If you care about your randomness, you don't want to be making the assumption that a source is random because it sometimes looks that way, sort of. You want to be using a source that's assumed random because, as far as you know, it's very hard for it to be any other way. Clearly, SRAM state falls into the former category, and there are lots and lots of variables keeping it firmly outside the latter. This means the usual wisdom applies: if you really need the extra entropy, mix some of these SRAM state bits into your pool, but make sure you're also feeding the pool from at least one source about whose randomness you can reason strongly. -- Ivan Krstić [EMAIL PROTECTED] | http://radian.org - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: using SRAM state as a source of randomness
Hi. On Sun, 16 Sep 2007, Joachim Strmbergson wrote: One could add test functionality that checks the randomness of the initial SRAM state after power on. But somehow I don't think a good test suite and extremely low cost devices (for example RFID chips) are very compatible concepts. One can test a source of randomness by checking statistics of its few samples, but if I understand the article correctly, in case of SRAM each cell behaves as an independent source of randomness: some bits are almost always stuck at fixed values while others have some freedom. In this case it is pointless to do tests using initial SRAM state after a single power on, because to gather a few samples from each source one needs to repeatedly reset the device. Applying statistical tests to a hash of the whole SRAM does not make much sense either -- a good hash function will give statistically good results even if you give it a counter. -- Regards, ASK - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: using SRAM state as a source of randomness
Aloha! Udhay Shankar N skrev: Sounds like an interesting idea - using SRAM state as a source of randomness. Any of the folks here willing to comment on this? Udhay http://prisms.cs.umass.edu/~kevinfu/papers/holcomb-FERNS-RFIDSec07.pdf IMHO a very interesting paper. But I have a few questions about practical aspects of this (and the paper). First off I don't see any info in the paper about the time between power cycling and reading the memory. Shouldn't the RNG generated by the memory be affected by remanence problems if the power cycle is to short? I.e if the power off state is to short, the bit pattern from one read operation will contain more of the bit pattern from previous power on states. (2) How would one go about extracting the fingerprint/ID? As I see it you would either have to do numerous read operations (with power cycling in between) and then extract the fixed bits on a host. That is, the host reads the whole memory (just like in the paper) and from that extract the ID. This means that the RFID-unit will not know it's own ID. The other way to do it (as I see it), is to do the multiple reads during manufacturing (post production test/configuration), extract the fixed bits and then stor the index to these bits within the RFID chip. This would allow the RFID to assemble the bits and know it's own ID, but then the idea (as presented in the paper) to not have to do post manufacturing work to set the ID is gone. (3) in the opposite situation to (2), how should the RFID unit avoid the fixed bits when generating a key based on the random bits? Would it be ok to simply run the power on memory state through a cryptographic hash function, ignoring the fixed bits? -- Med vänlig hälsning, Yours Joachim Strömbergson - Alltid i harmonisk svängning. Kryptoblog - IT-säkerhet på svenska http://www.strombergson.com/kryptoblog - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
