«Ідеальне» кидання монети: The NIST Randomness Beacon



Говорячи статистичними мовою — «випадкова змінна — це функція, що видає якесь значення, невідоме до певного часу і постійне після.

З 5 вересня 2013 року NIST кожну хвилину публікує випадкове число розміром 512 біт. Це число, попереднє число, час, коли воно було згенеровано і ще деяка інформація підписуються цифровим підписом NIST, так що можна легко перевірити, що число було згенеровано саме NIST.



NIST Randomness Beacon (далі — «маяк») вирішує три цікаві завдання

  1. Власне, генерує досить якісне псевдовипадкове число
  2. Надає його на загальний огляд (до речі, тому в них великим червоним шрифтом написано «Не використовуйте цей ключ шифрування!»)
  3. Дає можливість перевірити, що число не було скомпрометовано


Розберемося по пунктам

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 байт)
## 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 work, 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 output this value is in the chain.

## If we run this on every entry in the chain, works and all out just fine,
## then we'd know all is well



Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.