1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
|
// Copyright (c) 2020 Apple Inc.
// SPDX-License-Identifier: MPL-2.0
//! Tool for generating pseudorandom field elements.
//!
//! NOTE: The public API for this module is a work in progress.
use crate::field::{FieldElement, FieldError};
use crate::vdaf::prg::SeedStream;
#[cfg(feature = "crypto-dependencies")]
use crate::vdaf::prg::SeedStreamAes128;
#[cfg(feature = "crypto-dependencies")]
use getrandom::getrandom;
use std::marker::PhantomData;
const BUFFER_SIZE_IN_ELEMENTS: usize = 128;
/// Errors propagated by methods in this module.
#[derive(Debug, thiserror::Error)]
pub enum PrngError {
/// Failure when calling getrandom().
#[error("getrandom: {0}")]
GetRandom(#[from] getrandom::Error),
}
/// This type implements an iterator that generates a pseudorandom sequence of field elements. The
/// sequence is derived from the key stream of AES-128 in CTR mode with a random IV.
#[derive(Debug)]
pub(crate) struct Prng<F, S> {
phantom: PhantomData<F>,
seed_stream: S,
buffer: Vec<u8>,
buffer_index: usize,
output_written: usize,
}
#[cfg(feature = "crypto-dependencies")]
impl<F: FieldElement> Prng<F, SeedStreamAes128> {
/// Create a [`Prng`] from a seed for Prio 2. The first 16 bytes of the seed and the last 16
/// bytes of the seed are used, respectively, for the key and initialization vector for AES128
/// in CTR mode.
pub(crate) fn from_prio2_seed(seed: &[u8; 32]) -> Self {
let seed_stream = SeedStreamAes128::new(&seed[..16], &seed[16..]);
Self::from_seed_stream(seed_stream)
}
/// Create a [`Prng`] from a randomly generated seed.
pub(crate) fn new() -> Result<Self, PrngError> {
let mut seed = [0; 32];
getrandom(&mut seed)?;
Ok(Self::from_prio2_seed(&seed))
}
}
impl<F, S> Prng<F, S>
where
F: FieldElement,
S: SeedStream,
{
pub(crate) fn from_seed_stream(mut seed_stream: S) -> Self {
let mut buffer = vec![0; BUFFER_SIZE_IN_ELEMENTS * F::ENCODED_SIZE];
seed_stream.fill(&mut buffer);
Self {
phantom: PhantomData::<F>,
seed_stream,
buffer,
buffer_index: 0,
output_written: 0,
}
}
pub(crate) fn get(&mut self) -> F {
loop {
// Seek to the next chunk of the buffer that encodes an element of F.
for i in (self.buffer_index..self.buffer.len()).step_by(F::ENCODED_SIZE) {
let j = i + F::ENCODED_SIZE;
if let Some(x) = match F::try_from_random(&self.buffer[i..j]) {
Ok(x) => Some(x),
Err(FieldError::ModulusOverflow) => None, // reject this sample
Err(err) => panic!("unexpected error: {}", err),
} {
// Set the buffer index to the next chunk.
self.buffer_index = j;
self.output_written += 1;
return x;
}
}
// Refresh buffer with the next chunk of PRG output.
self.seed_stream.fill(&mut self.buffer);
self.buffer_index = 0;
}
}
}
impl<F, S> Iterator for Prng<F, S>
where
F: FieldElement,
S: SeedStream,
{
type Item = F;
fn next(&mut self) -> Option<F> {
Some(self.get())
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{
codec::Decode,
field::{Field96, FieldPrio2},
vdaf::prg::{Prg, PrgAes128, Seed},
};
use std::convert::TryInto;
#[test]
fn secret_sharing_interop() {
let seed = [
0xcd, 0x85, 0x5b, 0xd4, 0x86, 0x48, 0xa4, 0xce, 0x52, 0x5c, 0x36, 0xee, 0x5a, 0x71,
0xf3, 0x0f, 0x66, 0x80, 0xd3, 0x67, 0x53, 0x9a, 0x39, 0x6f, 0x12, 0x2f, 0xad, 0x94,
0x4d, 0x34, 0xcb, 0x58,
];
let reference = [
0xd0056ec5, 0xe23f9c52, 0x47e4ddb4, 0xbe5dacf6, 0x4b130aba, 0x530c7a90, 0xe8fc4ee5,
0xb0569cb7, 0x7774cd3c, 0x7f24e6a5, 0xcc82355d, 0xc41f4f13, 0x67fe193c, 0xc94d63a4,
0x5d7b474c, 0xcc5c9f5f, 0xe368e1d5, 0x020fa0cf, 0x9e96aa2a, 0xe924137d, 0xfa026ab9,
0x8ebca0cc, 0x26fc58a5, 0x10a7b173, 0xb9c97291, 0x53ef0e28, 0x069cfb8e, 0xe9383cae,
0xacb8b748, 0x6f5b9d49, 0x887d061b, 0x86db0c58,
];
let share2 = extract_share_from_seed::<FieldPrio2>(reference.len(), &seed);
assert_eq!(share2, reference);
}
/// takes a seed and hash as base64 encoded strings
#[cfg(feature = "prio2")]
fn random_data_interop(seed_base64: &str, hash_base64: &str, len: usize) {
let seed = base64::decode(seed_base64).unwrap();
let random_data = extract_share_from_seed::<FieldPrio2>(len, &seed);
let random_bytes = FieldPrio2::slice_into_byte_vec(&random_data);
let digest = ring::digest::digest(&ring::digest::SHA256, &random_bytes);
assert_eq!(base64::encode(digest), hash_base64);
}
#[test]
#[cfg(feature = "prio2")]
fn test_hash_interop() {
random_data_interop(
"AAECAwQFBgcICQoLDA0ODxAREhMUFRYXGBkaGxwdHh8=",
"RtzeQuuiWdD6bW2ZTobRELDmClz1wLy3HUiKsYsITOI=",
100_000,
);
// zero seed
random_data_interop(
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA=",
"3wHQbSwAn9GPfoNkKe1qSzWdKnu/R+hPPyRwwz6Di+w=",
100_000,
);
// 0, 1, 2 ... seed
random_data_interop(
"AAECAwQFBgcICQoLDA0ODxAREhMUFRYXGBkaGxwdHh8=",
"RtzeQuuiWdD6bW2ZTobRELDmClz1wLy3HUiKsYsITOI=",
100_000,
);
// one arbirtary fixed seed
random_data_interop(
"rkLrnVcU8ULaiuXTvR3OKrfpMX0kQidqVzta1pleKKg=",
"b1fMXYrGUNR3wOZ/7vmUMmY51QHoPDBzwok0fz6xC0I=",
100_000,
);
// all bits set seed
random_data_interop(
"//////////////////////////////////////////8=",
"iBiDaqLrv7/rX/+vs6akPiprGgYfULdh/XhoD61HQXA=",
100_000,
);
}
fn extract_share_from_seed<F: FieldElement>(length: usize, seed: &[u8]) -> Vec<F> {
assert_eq!(seed.len(), 32);
Prng::from_prio2_seed(seed.try_into().unwrap())
.take(length)
.collect()
}
#[test]
fn rejection_sampling_test_vector() {
// These constants were found in a brute-force search, and they test that the PRG performs
// rejection sampling correctly when raw AES-CTR output exceeds the prime modulus.
let seed_stream = PrgAes128::seed_stream(
&Seed::get_decoded(&[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 95]).unwrap(),
b"",
);
let mut prng = Prng::<Field96, _>::from_seed_stream(seed_stream);
let expected = Field96::from(39729620190871453347343769187);
let actual = prng.nth(145).unwrap();
assert_eq!(actual, expected);
}
}
|
