“Ideal” coin toss: The NIST Randomness Beacon

  • Tutorial


In statistical language, a “random variable” is a function that produces a value that is unknown before a certain time and constant after.

Starting September 5, 2013, NIST publishes a random number of 512 bits every minute . This is the number, the previous number, the time when it was generated, and some other information is digitally signed by NIST, so you can easily verify that the number was generated precisely by NIST.



NIST Randomness Beacon (hereinafter referred to as the “lighthouse") solves three interesting problems.

  1. Actually, generates a fairly high-quality pseudo-random number
  2. Provides it for all to see (by the way, that’s why they have a large red font saying "Do not use this as an encryption key!")
  3. Allows you to verify that the number has not been compromised


Let's take a look at paragraphs

1) The scheme is quite simple: the output of two iron generators is taken, the quarrels are obtained, Seed Value is obtained (it is also published).
It is then concatenated with service fields, the previous value, and run through SHA-512.
This hash is signed with the NIST private key and the signature is again run through SHA-512, providing us with the desired pseudo-random number.

2) This is the meaning of a random beacon so that the same pseudo-random data can be obtained from anywhere.
For example, you and your family want to determine who next time to wash the dishes. Numbering, agree to look at the lighthouse at 17:00, and at certain times, see who is lucky.

3) This is the most interesting. The scheme is constructed in such a way that the probability of manipulating the resulting data is very close to zero. That is, we have every right to not trust the numbers from NIST and we can make sure that nothing affected them.

Let's say an attacker got the opportunity to change the value of Seed. But between the Seed and the Output Value there are two passes SHA-512 + digital signature. Even if he gains access to the NIST private key, he is unlikely to be able to defeat SHA-512.

In addition, no one forbids using the previous values ​​to get the Output Value that you need. You can take the current one, quarrel with what happened a day ago and take as a result. In this case, an attacker would have to break 2 * 24 * 60 = 2,880 SHA-512 calls, which is even worse.

Even assuming that all this is real, you can still easily defend against this kind of attack using your own Output Value processing scheme, the main thing is that it be the same for everyone who uses it.

For example, take the Output Value as an encryption key (not for real encryption, but to get a pseudo-random number) and encrypt itself with the AES algorithm, then run it through SHA-3 and so on. An attacker will scratch all this specially because of you.

Now about the real accident. NIST uses two commercial RNGs that are hard-wired, but we still cannot prove that there is truly random data. And they want to . Using quantum effects and Bell's theorem, NIST wants to achieve data thatproven unknown until a certain time.

Also, no one bothers you to build and launch such a lighthouse yourself and mix it with NIST ovsky. The more beacons, the more reliable random numbers.

shell script that verifies the current value of the beacon.
#!/bin/sh
## NIST Randomness Beacon verification routine
## Only slightly adapted by Elliot Williams
## from code provided by Lawrence Bassham, NIST
## The UNIX time that you'd like to test:
##
whichRecord=1400878200 
## --------------- Utility Functions ----------------
## Extracts specified record from xml file
getValue() {
 xmllint --xpath "/record/$1/text()" $2
}
## Converts little-endian to big-endian
byteReverse() {
 len=${#1}
 for((i=${len}-2; i>=0; i=i-2)) do
 rev="$rev${1:$i:2}"
 done
 echo ${rev}
}
## ---------------- Get an arbitrary record -----------------
echo "Downloading data for: ${whichRecord}"
curl -s https://beacon.nist.gov/rest/record/${whichRecord} -o rec.xml
## ------------- Pack data into correct format --------------
echo
echo "## Create a summary of all of the data, save as beacon.bin"
## Strangest choice of format ever!
## Version number (ascii text)
## Update frequency (4 bytes)
## Time Stamp (8 bytes)
## The HW RNG seedValue (64 bytes)
## The previous output value, does the chaining (64 bytes)
## Status code (4 bytes)
getValue version rec.xml > beacon.bin
printf "%.8x" `getValue frequency rec.xml` | xxd -r -p >> beacon.bin
printf "%.16x" `getValue timeStamp rec.xml` | xxd -r -p >> beacon.bin
getValue seedValue rec.xml | xxd -r -p >> beacon.bin
getValue previousOutputValue rec.xml | xxd -r -p >> beacon.bin
printf "%.8x" `getValue statusCode rec.xml` | xxd -r -p >> beacon.bin
## ------------------ Verify signature on data --------------------
echo "## Verify that the signature and NIST's public key correctly SHA512 sign the data"
## Download Beacon's public key
echo "Downloading Beacon's public key"
curl -s https://beacon.nist.gov/certificate/beacon.cer -o beacon.cer
## Create a bytewise reversed version of the listed signature
## This is necessary b/c Beacon signs with Microsoft CryptoAPI which outputs
## the signature as little-endian instead of big-endian like many other tools
## This may change (personal communication) in a future revision of the Beacon
signature=`getValue signatureValue rec.xml`
byteReverse ${signature} | xxd -r -p > beacon.sig
## Pull public key out of certificate
/usr/bin/openssl x509 -pubkey -noout -in beacon.cer > beaconpubkey.pem
## Test signature / key on packed data
/usr/bin/openssl dgst -sha512 -verify beaconpubkey.pem -signature beacon.sig beacon.bin
echo
echo
## ------------------ Verify Signature -> Output and Chaining ------------
echo "The following three values should match: "
echo " a direct SHA512 of the extracted signature"
echo " the reported output value"
echo " next record's previous output value"
echo
## Just print output value
echo "Reported output value"
getValue outputValue rec.xml
echo
## Now turn the signature into the output value: again SHA512
echo "SHA512 of the signature"
getValue signatureValue rec.xml | xxd -r -p | sha512sum
## Now test chaining
## Get next record
echo "Downloading the next record"
curl -s https://beacon.nist.gov/rest/record/next/${whichRecord} -o next.xml
## Make sure that this period's output shows up as next period's "previous output"
echo "Next value's reported previous output (test of forward chaining)"
getValue previousOutputValue next.xml
echo
echo
## --------------------- The End -----------------------------------------
## If this all worked, we've verified that the signature (plus NIST's key)
## sign the hash of the random number and its support info
## _and_ we've verified that the outputValue is derived from them,
## so we know that this output value is in the chain.
## If we run this on every entry in the chain, and all works out just fine,
## then we'd know all is well


Also popular now: