«Идеальное» бросание монеты: The NIST Randomness Beacon
Говоря статистическим языком — «случайная переменная» — это функция, выдающая какое-то значение, неизвестное до определенного времени и постоянное после.
C 5 сентября 2013 года NIST каждую минуту публикует случайное число размером 512 бит. Это число, предыдущее число, время, когда оно было сгенерировано и еще кое-какая информация подписываются цифровой подписью NIST, так что можно легко проверить, что число было сгенерировано именно NIST.
NIST Randomness Beacon (далее — «маяк») решает три интересные задачи
Собственно, генерирует довольно качественное псевдослучайное число Предоставляет его на всеобщее обозрение (кстати, поэтому у них большим красным шрифтом написано «Не используйте этот как ключ шифрования!») Дает возможность проверить, что число не было скомпрометировано Разберемся по пунктам
1) Схема довольно простая: Берется выход двух железных генераторов, ксорится, получается Seed Value (он тоже публикуется).Затем конкатенируется со служебными полями, предыдущим значением и прогоняется через SHA-512.Этот хэш подписывается закрытым ключом NIST и уже подпись опять прогоняется через SHA-512, предоставляя нам желаемое псевдослучайное число.
2) В этом смысл случайного маяка, чтобы из любого места можно было получить одинаковые псевдослучайные данные.Например, вы с домашними хотите определить, кому в следующий раз мыть посуду. Нумеруетесь, договариваетесь посмотреть на маяк в 17:00, и в определенное время смотрите кому повезло.
3) Это самое интересное. Схема построена таким образом, чтобы вероятность манипулирования итоговыми данными была очень близка к нулю. То есть, у нас есть полное право не доверять числам от NIST и мы можем убедиться, что на них ничего не повлияло.
Допустим, злоумышленник получил возможность изменять значение Seed. Но между Seed и Output Value два прохода SHA-512 + цифровая подпись. Даже если он получит доступ к закрытому ключу NIST, вряд-ли сможет победить SHA-512.
К тому же, никто не запрещает использовать предыдущие значения для получения Output Value, нужного именно вам. Вы можете брать текущее, ксорить с тем, что было сутки назад и брать как результат. Взломщику в таком случае пришлось бы ломать 2×24 * 60 = 2,880 вызовов SHA-512, что еще хуже.
Даже если предположить, что все это реально, вы все равно легко сможете защититься от такого рода атак, используя свою собственную схему обработки Output Value, главное чтобы она была одинаковой у всех, кто ей пользуется.
Например, взять Output Value как ключ шифрования (не для реального шифрования, а для получения псевдослучайного числа) и зашифровать само себя алгоритмом AES, потом прогнать через SHA-3 и так далее. Злоумышленник очешуеет все это ломать специально из-за вас.
Теперь по поводу настоящей случайности. NIST использует два коммерческих ГСЧ, которые хоть и хардварные, но мы все равно не можем доказать, что там истинно случайные данные. А они хотят. Используя квантовые эффекты и теорему Белла NIST хочет добиться получения данных, которые доказано неизвестны до определенного времени.
Так же, никто не мешает вам самим соорудить и запустить такой маяк и подмешивать его к NIST овскому. Чем больше маяков, тем надежнее случайные числа.
shell скрипт, который верифицирует текущее значение маяка. #!/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
