224 lines
7.6 KiB
Go
224 lines
7.6 KiB
Go
// Package sequencer анализирует случайность набора токенов (сессионных
|
||
// ID, CSRF-токенов и т.п.) — аналог вкладки Sequencer в Burp. Реализует
|
||
// классический набор статистических тестов FIPS 140-2 (monobit, poker,
|
||
// runs, long run), исторически применявшийся именно для этой задачи.
|
||
//
|
||
// Тесты определены строго для блоков по 20 000 бит: входные сэмплы
|
||
// склеиваются в один битовый поток и режутся на такие блоки, остаток
|
||
// короче 20 000 бит отбрасывается. Это значит, что для содержательного
|
||
// результата нужно ощутимое количество токенов — AnalyzeConcatenated
|
||
// возвращает понятную ошибку, если данных не хватает даже на один блок.
|
||
package sequencer
|
||
|
||
import (
|
||
"encoding/hex"
|
||
"fmt"
|
||
"strings"
|
||
)
|
||
|
||
const fipsBlockBits = 20000
|
||
|
||
// runInterval — допустимый диапазон количества серий данной длины
|
||
// для теста Runs, согласно таблице FIPS 140-2.
|
||
type runInterval struct{ min, max int }
|
||
|
||
// runIntervals: длины серий 1..5 — точное совпадение по таблице,
|
||
// 6 используется как корзина "6 и длиннее" (в спецификации у неё тот же
|
||
// допустимый интервал, что и у длины 5).
|
||
var runIntervals = map[int]runInterval{
|
||
1: {2343, 2657},
|
||
2: {1135, 1365},
|
||
3: {542, 708},
|
||
4: {251, 373},
|
||
5: {111, 201},
|
||
6: {111, 201},
|
||
}
|
||
|
||
// BlockResult — результат всех четырёх тестов на одном 20 000-битном блоке.
|
||
type BlockResult struct {
|
||
MonobitOnes int
|
||
MonobitPass bool
|
||
|
||
PokerX float64
|
||
PokerPass bool
|
||
|
||
ZeroRuns map[int]int
|
||
OneRuns map[int]int
|
||
RunsPass bool
|
||
|
||
LongRunMax int
|
||
LongRunPass bool
|
||
}
|
||
|
||
// AllPass — блок считается прошедшим анализ, если все четыре теста
|
||
// прошли. Один упавший тест не обязательно означает, что генератор
|
||
// токенов плох — но чем больше блоков не проходят, тем тревожнее.
|
||
func (r BlockResult) AllPass() bool {
|
||
return r.MonobitPass && r.PokerPass && r.RunsPass && r.LongRunPass
|
||
}
|
||
|
||
// ParseSample превращает одну строку ввода в байты для анализа: если
|
||
// строка целиком выглядит как чётная hex-строка (частый формат для
|
||
// сессионных токенов), она декодируется как hex; иначе берутся сырые
|
||
// байты UTF-8 самой строки.
|
||
func ParseSample(line string) []byte {
|
||
line = strings.TrimSpace(line)
|
||
if looksHex(line) {
|
||
if b, err := hex.DecodeString(line); err == nil {
|
||
return b
|
||
}
|
||
}
|
||
return []byte(line)
|
||
}
|
||
|
||
func looksHex(s string) bool {
|
||
if s == "" || len(s)%2 != 0 {
|
||
return false
|
||
}
|
||
for i := 0; i < len(s); i++ {
|
||
c := s[i]
|
||
if !((c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F')) {
|
||
return false
|
||
}
|
||
}
|
||
return true
|
||
}
|
||
|
||
// AnalyzeConcatenated склеивает все сэмплы в один битовый поток, режет
|
||
// на блоки по 20 000 бит и прогоняет каждый через все четыре теста.
|
||
// bitsAvailable — сколько бит суммарно было в сэмплах (для сообщения
|
||
// пользователю, сколько ещё нужно добавить, если блоков получилось 0).
|
||
func AnalyzeConcatenated(samples [][]byte) (results []BlockResult, blocksUsed int, bitsAvailable int, err error) {
|
||
var all []byte
|
||
for _, s := range samples {
|
||
all = append(all, s...)
|
||
}
|
||
|
||
bits := bytesToBits(all)
|
||
bitsAvailable = len(bits)
|
||
blocksUsed = bitsAvailable / fipsBlockBits
|
||
if blocksUsed == 0 {
|
||
return nil, 0, bitsAvailable, fmt.Errorf(
|
||
"нужно минимум %d бит для одного FIPS-блока, есть %d — добавь ещё сэмплов",
|
||
fipsBlockBits, bitsAvailable,
|
||
)
|
||
}
|
||
|
||
results = make([]BlockResult, 0, blocksUsed)
|
||
for b := 0; b < blocksUsed; b++ {
|
||
block := bits[b*fipsBlockBits : (b+1)*fipsBlockBits]
|
||
|
||
ones, monoOK := monobitTest(block)
|
||
x, pokerOK := pokerTest(block)
|
||
zeroRuns, oneRuns, runsOK := runsTest(block)
|
||
maxRun, longOK := longRunTest(block)
|
||
|
||
results = append(results, BlockResult{
|
||
MonobitOnes: ones, MonobitPass: monoOK,
|
||
PokerX: x, PokerPass: pokerOK,
|
||
ZeroRuns: zeroRuns, OneRuns: oneRuns, RunsPass: runsOK,
|
||
LongRunMax: maxRun, LongRunPass: longOK,
|
||
})
|
||
}
|
||
return results, blocksUsed, bitsAvailable, nil
|
||
}
|
||
|
||
// bytesToBits разворачивает байты в отдельные биты, старший бит первым.
|
||
func bytesToBits(data []byte) []byte {
|
||
bits := make([]byte, len(data)*8)
|
||
for i, b := range data {
|
||
for j := 0; j < 8; j++ {
|
||
bits[i*8+j] = (b >> uint(7-j)) & 1
|
||
}
|
||
}
|
||
return bits
|
||
}
|
||
|
||
// monobitTest — доля единиц в блоке должна быть близка к половине.
|
||
// block должен быть длиной ровно fipsBlockBits.
|
||
func monobitTest(block []byte) (ones int, pass bool) {
|
||
for _, b := range block {
|
||
ones += int(b)
|
||
}
|
||
return ones, ones > 9725 && ones < 10275
|
||
}
|
||
|
||
// pokerTest делит блок на 5000 непересекающихся 4-битных сегментов,
|
||
// считает распределение по 16 возможным значениям и проверяет
|
||
// статистику X на попадание в допустимый интервал по таблице FIPS 140-2.
|
||
func pokerTest(block []byte) (x float64, pass bool) {
|
||
var freq [16]int
|
||
for i := 0; i < 5000; i++ {
|
||
v := 0
|
||
for j := 0; j < 4; j++ {
|
||
v = (v << 1) | int(block[i*4+j])
|
||
}
|
||
freq[v]++
|
||
}
|
||
|
||
sumSq := 0.0
|
||
for _, f := range freq {
|
||
sumSq += float64(f) * float64(f)
|
||
}
|
||
x = (16.0/5000.0)*sumSq - 5000.0
|
||
return x, x > 2.16 && x < 46.17
|
||
}
|
||
|
||
// runsTest считает количество серий (подряд идущих одинаковых бит)
|
||
// каждой длины отдельно для серий из нулей и из единиц, и сверяет
|
||
// с допустимыми интервалами runIntervals. Длины 6 и больше — общая
|
||
// корзина.
|
||
func runsTest(block []byte) (zeroRuns, oneRuns map[int]int, pass bool) {
|
||
zeroRuns = map[int]int{}
|
||
oneRuns = map[int]int{}
|
||
|
||
i := 0
|
||
n := len(block)
|
||
for i < n {
|
||
j := i
|
||
for j < n && block[j] == block[i] {
|
||
j++
|
||
}
|
||
length := j - i
|
||
bucket := length
|
||
if bucket > 6 {
|
||
bucket = 6
|
||
}
|
||
if block[i] == 0 {
|
||
zeroRuns[bucket]++
|
||
} else {
|
||
oneRuns[bucket]++
|
||
}
|
||
i = j
|
||
}
|
||
|
||
pass = true
|
||
for length := 1; length <= 6; length++ {
|
||
interval := runIntervals[length]
|
||
if zeroRuns[length] < interval.min || zeroRuns[length] > interval.max {
|
||
pass = false
|
||
}
|
||
if oneRuns[length] < interval.min || oneRuns[length] > interval.max {
|
||
pass = false
|
||
}
|
||
}
|
||
return zeroRuns, oneRuns, pass
|
||
}
|
||
|
||
// longRunTest — блок не должен содержать серию длиной 26 бит и более
|
||
// (ни из нулей, ни из единиц).
|
||
func longRunTest(block []byte) (maxRun int, pass bool) {
|
||
i := 0
|
||
n := len(block)
|
||
for i < n {
|
||
j := i
|
||
for j < n && block[j] == block[i] {
|
||
j++
|
||
}
|
||
if length := j - i; length > maxRun {
|
||
maxRun = length
|
||
}
|
||
i = j
|
||
}
|
||
return maxRun, maxRun < 26
|
||
}
|