From 013efaf13987acfa6b41d40f07900c1ea77f5bda Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Thu, 17 Dec 2020 20:03:41 -0700 Subject: std: introduce a thread-local CSPRNG for general use std.crypto.random * cross platform, even freestanding * can't fail. on initialization for some systems requires calling os.getrandom(), in which case there are rare but theoretically possible errors. The code panics in these cases, however the application may choose to override the default seed function and then handle the failure another way. * thread-safe * supports the full Random interface * cryptographically secure * no syscall required to initialize on Linux (AT_RANDOM) * calls arc4random on systems that support it `std.crypto.randomBytes` is removed in favor of `std.crypto.random.bytes`. I moved some of the Random implementations into their own files in the interest of organization. stage2 no longer requires passing a RNG; instead it uses this API. Closes #6704 --- lib/std/crypto.zig | 11 +- lib/std/crypto/25519/ed25519.zig | 8 +- lib/std/crypto/25519/edwards25519.zig | 4 +- lib/std/crypto/25519/x25519.zig | 2 +- lib/std/crypto/bcrypt.zig | 4 +- lib/std/crypto/salsa20.zig | 18 +- lib/std/crypto/tlcsprng.zig | 62 ++++ lib/std/crypto/utils.zig | 8 +- lib/std/fs.zig | 4 +- lib/std/rand.zig | 579 +--------------------------------- lib/std/rand/Gimli.zig | 40 +++ lib/std/rand/Isaac64.zig | 210 ++++++++++++ lib/std/rand/Pcg.zig | 101 ++++++ lib/std/rand/Sfc64.zig | 108 +++++++ lib/std/rand/Xoroshiro128.zig | 133 ++++++++ lib/std/start.zig | 26 ++ lib/std/testing.zig | 3 +- src/Compilation.zig | 7 +- src/glibc.zig | 1 - src/libcxx.zig | 2 - src/libunwind.zig | 1 - src/main.zig | 15 - src/musl.zig | 1 - src/test.zig | 11 +- 24 files changed, 730 insertions(+), 629 deletions(-) create mode 100644 lib/std/crypto/tlcsprng.zig create mode 100644 lib/std/rand/Gimli.zig create mode 100644 lib/std/rand/Isaac64.zig create mode 100644 lib/std/rand/Pcg.zig create mode 100644 lib/std/rand/Sfc64.zig create mode 100644 lib/std/rand/Xoroshiro128.zig diff --git a/lib/std/crypto.zig b/lib/std/crypto.zig index 6eb934473f..e3581cde96 100644 --- a/lib/std/crypto.zig +++ b/lib/std/crypto.zig @@ -134,8 +134,10 @@ pub const nacl = struct { pub const utils = @import("crypto/utils.zig"); +/// This is a thread-local, cryptographically secure pseudo random number generator. +pub const random = &@import("crypto/tlcsprng.zig").interface; + const std = @import("std.zig"); -pub const randomBytes = std.os.getrandom; test "crypto" { inline for (std.meta.declarations(@This())) |decl| { @@ -178,6 +180,13 @@ test "crypto" { _ = @import("crypto/25519/ristretto255.zig"); } +test "CSPRNG" { + const a = random.int(u64); + const b = random.int(u64); + const c = random.int(u64); + std.testing.expect(a ^ b ^ c != 0); +} + test "issue #4532: no index out of bounds" { const types = [_]type{ hash.Md5, diff --git a/lib/std/crypto/25519/ed25519.zig b/lib/std/crypto/25519/ed25519.zig index 842b08d706..7f90ba584c 100644 --- a/lib/std/crypto/25519/ed25519.zig +++ b/lib/std/crypto/25519/ed25519.zig @@ -43,7 +43,7 @@ pub const Ed25519 = struct { pub fn create(seed: ?[seed_length]u8) !KeyPair { const ss = seed orelse ss: { var random_seed: [seed_length]u8 = undefined; - try crypto.randomBytes(&random_seed); + crypto.random.bytes(&random_seed); break :ss random_seed; }; var az: [Sha512.digest_length]u8 = undefined; @@ -179,7 +179,7 @@ pub const Ed25519 = struct { var z_batch: [count]Curve.scalar.CompressedScalar = undefined; for (z_batch) |*z| { - try std.crypto.randomBytes(z[0..16]); + std.crypto.random.bytes(z[0..16]); mem.set(u8, z[16..], 0); } @@ -232,8 +232,8 @@ test "ed25519 batch verification" { const key_pair = try Ed25519.KeyPair.create(null); var msg1: [32]u8 = undefined; var msg2: [32]u8 = undefined; - try std.crypto.randomBytes(&msg1); - try std.crypto.randomBytes(&msg2); + std.crypto.random.bytes(&msg1); + std.crypto.random.bytes(&msg2); const sig1 = try Ed25519.sign(&msg1, key_pair, null); const sig2 = try Ed25519.sign(&msg2, key_pair, null); var signature_batch = [_]Ed25519.BatchElement{ diff --git a/lib/std/crypto/25519/edwards25519.zig b/lib/std/crypto/25519/edwards25519.zig index 008a4535b3..d64f06c421 100644 --- a/lib/std/crypto/25519/edwards25519.zig +++ b/lib/std/crypto/25519/edwards25519.zig @@ -484,8 +484,8 @@ test "edwards25519 packing/unpacking" { test "edwards25519 point addition/substraction" { var s1: [32]u8 = undefined; var s2: [32]u8 = undefined; - try std.crypto.randomBytes(&s1); - try std.crypto.randomBytes(&s2); + std.crypto.random.bytes(&s1); + std.crypto.random.bytes(&s2); const p = try Edwards25519.basePoint.clampedMul(s1); const q = try Edwards25519.basePoint.clampedMul(s2); const r = p.add(q).add(q).sub(q).sub(q); diff --git a/lib/std/crypto/25519/x25519.zig b/lib/std/crypto/25519/x25519.zig index 3b3ff551fe..0bf55d52fc 100644 --- a/lib/std/crypto/25519/x25519.zig +++ b/lib/std/crypto/25519/x25519.zig @@ -34,7 +34,7 @@ pub const X25519 = struct { pub fn create(seed: ?[seed_length]u8) !KeyPair { const sk = seed orelse sk: { var random_seed: [seed_length]u8 = undefined; - try crypto.randomBytes(&random_seed); + crypto.random.bytes(&random_seed); break :sk random_seed; }; var kp: KeyPair = undefined; diff --git a/lib/std/crypto/bcrypt.zig b/lib/std/crypto/bcrypt.zig index 4cec59961b..6813495d25 100644 --- a/lib/std/crypto/bcrypt.zig +++ b/lib/std/crypto/bcrypt.zig @@ -262,7 +262,7 @@ fn strHashInternal(password: []const u8, rounds_log: u6, salt: [salt_length]u8) /// and then use the resulting hash as the password parameter for bcrypt. pub fn strHash(password: []const u8, rounds_log: u6) ![hash_length]u8 { var salt: [salt_length]u8 = undefined; - try crypto.randomBytes(&salt); + crypto.random.bytes(&salt); return strHashInternal(password, rounds_log, salt); } @@ -283,7 +283,7 @@ pub fn strVerify(h: [hash_length]u8, password: []const u8) BcryptError!void { test "bcrypt codec" { var salt: [salt_length]u8 = undefined; - try crypto.randomBytes(&salt); + crypto.random.bytes(&salt); var salt_str: [salt_str_length]u8 = undefined; Codec.encode(salt_str[0..], salt[0..]); var salt2: [salt_length]u8 = undefined; diff --git a/lib/std/crypto/salsa20.zig b/lib/std/crypto/salsa20.zig index dd3e4fe99b..8122e9b25c 100644 --- a/lib/std/crypto/salsa20.zig +++ b/lib/std/crypto/salsa20.zig @@ -571,9 +571,9 @@ test "xsalsa20poly1305" { var key: [XSalsa20Poly1305.key_length]u8 = undefined; var nonce: [XSalsa20Poly1305.nonce_length]u8 = undefined; var tag: [XSalsa20Poly1305.tag_length]u8 = undefined; - try crypto.randomBytes(&msg); - try crypto.randomBytes(&key); - try crypto.randomBytes(&nonce); + crypto.random.bytes(&msg); + crypto.random.bytes(&key); + crypto.random.bytes(&nonce); XSalsa20Poly1305.encrypt(c[0..], &tag, msg[0..], "ad", nonce, key); try XSalsa20Poly1305.decrypt(msg2[0..], c[0..], tag, "ad", nonce, key); @@ -585,9 +585,9 @@ test "xsalsa20poly1305 secretbox" { var key: [XSalsa20Poly1305.key_length]u8 = undefined; var nonce: [Box.nonce_length]u8 = undefined; var boxed: [msg.len + Box.tag_length]u8 = undefined; - try crypto.randomBytes(&msg); - try crypto.randomBytes(&key); - try crypto.randomBytes(&nonce); + crypto.random.bytes(&msg); + crypto.random.bytes(&key); + crypto.random.bytes(&nonce); SecretBox.seal(boxed[0..], msg[0..], nonce, key); try SecretBox.open(msg2[0..], boxed[0..], nonce, key); @@ -598,8 +598,8 @@ test "xsalsa20poly1305 box" { var msg2: [msg.len]u8 = undefined; var nonce: [Box.nonce_length]u8 = undefined; var boxed: [msg.len + Box.tag_length]u8 = undefined; - try crypto.randomBytes(&msg); - try crypto.randomBytes(&nonce); + crypto.random.bytes(&msg); + crypto.random.bytes(&nonce); var kp1 = try Box.KeyPair.create(null); var kp2 = try Box.KeyPair.create(null); @@ -611,7 +611,7 @@ test "xsalsa20poly1305 sealedbox" { var msg: [100]u8 = undefined; var msg2: [msg.len]u8 = undefined; var boxed: [msg.len + SealedBox.seal_length]u8 = undefined; - try crypto.randomBytes(&msg); + crypto.random.bytes(&msg); var kp = try Box.KeyPair.create(null); try SealedBox.seal(boxed[0..], msg[0..], kp.public_key); diff --git a/lib/std/crypto/tlcsprng.zig b/lib/std/crypto/tlcsprng.zig new file mode 100644 index 0000000000..0105cf0ce8 --- /dev/null +++ b/lib/std/crypto/tlcsprng.zig @@ -0,0 +1,62 @@ +// SPDX-License-Identifier: MIT +// Copyright (c) 2015-2020 Zig Contributors +// This file is part of [zig](https://ziglang.org/), which is MIT licensed. +// The MIT license requires this copyright notice to be included in all copies +// and substantial portions of the software. + +//! Thread-local cryptographically secure pseudo-random number generator. +//! This file has public declarations that are intended to be used internally +//! by the standard library; this namespace is not intended to be exposed +//! directly to standard library users. + +const std = @import("std"); +const root = @import("root"); +const mem = std.mem; + +/// We use this as a layer of indirection because global const pointers cannot +/// point to thread-local variables. +pub var interface = std.rand.Random{ .fillFn = tlsCsprngFill }; +pub threadlocal var csprng_state: std.crypto.core.Gimli = undefined; +pub threadlocal var csprng_state_initialized = false; +fn tlsCsprngFill(r: *std.rand.Random, buf: []u8) void { + if (std.builtin.link_libc and @hasDecl(std.c, "arc4random_buf")) { + // arc4random is already a thread-local CSPRNG. + return std.c.arc4random_buf(buf.ptr, buf.len); + } + if (!csprng_state_initialized) { + var seed: [seed_len]u8 = undefined; + // Because we panic on getrandom() failing, we provide the opportunity + // to override the default seed function. This also makes + // `std.crypto.random` available on freestanding targets, provided that + // the `cryptoRandomSeed` function is provided. + if (@hasDecl(root, "cryptoRandomSeed")) { + root.cryptoRandomSeed(&seed); + } else { + defaultSeed(&seed); + } + init(seed); + } + if (buf.len != 0) { + csprng_state.squeeze(buf); + } else { + csprng_state.permute(); + } + mem.set(u8, csprng_state.toSlice()[0..std.crypto.core.Gimli.RATE], 0); +} + +fn defaultSeed(buffer: *[seed_len]u8) void { + std.os.getrandom(buffer) catch @panic("getrandom() failed to seed thread-local CSPRNG"); +} + +pub const seed_len = 32; + +pub fn init(seed: [seed_len]u8) void { + var initial_state: [std.crypto.core.Gimli.BLOCKBYTES]u8 = undefined; + mem.copy(u8, initial_state[0..seed_len], &seed); + mem.set(u8, initial_state[seed_len..], 0); + csprng_state = std.crypto.core.Gimli.init(initial_state); + + // This is at the end so that accidental recursive dependencies result + // in stack overflows instead of invalid random data. + csprng_state_initialized = true; +} diff --git a/lib/std/crypto/utils.zig b/lib/std/crypto/utils.zig index 33ad6360f6..08271ac9f4 100644 --- a/lib/std/crypto/utils.zig +++ b/lib/std/crypto/utils.zig @@ -51,8 +51,8 @@ pub fn secureZero(comptime T: type, s: []T) void { test "crypto.utils.timingSafeEql" { var a: [100]u8 = undefined; var b: [100]u8 = undefined; - try std.crypto.randomBytes(a[0..]); - try std.crypto.randomBytes(b[0..]); + std.crypto.random.bytes(a[0..]); + std.crypto.random.bytes(b[0..]); testing.expect(!timingSafeEql([100]u8, a, b)); mem.copy(u8, a[0..], b[0..]); testing.expect(timingSafeEql([100]u8, a, b)); @@ -61,8 +61,8 @@ test "crypto.utils.timingSafeEql" { test "crypto.utils.timingSafeEql (vectors)" { var a: [100]u8 = undefined; var b: [100]u8 = undefined; - try std.crypto.randomBytes(a[0..]); - try std.crypto.randomBytes(b[0..]); + std.crypto.random.bytes(a[0..]); + std.crypto.random.bytes(b[0..]); const v1: std.meta.Vector(100, u8) = a; const v2: std.meta.Vector(100, u8) = b; testing.expect(!timingSafeEql(std.meta.Vector(100, u8), v1, v2)); diff --git a/lib/std/fs.zig b/lib/std/fs.zig index 8b949a57f1..4c346a2c89 100644 --- a/lib/std/fs.zig +++ b/lib/std/fs.zig @@ -82,7 +82,7 @@ pub fn atomicSymLink(allocator: *Allocator, existing_path: []const u8, new_path: mem.copy(u8, tmp_path[0..], dirname); tmp_path[dirname.len] = path.sep; while (true) { - try crypto.randomBytes(rand_buf[0..]); + crypto.random.bytes(rand_buf[0..]); base64_encoder.encode(tmp_path[dirname.len + 1 ..], &rand_buf); if (cwd().symLink(existing_path, tmp_path, .{})) { @@ -157,7 +157,7 @@ pub const AtomicFile = struct { tmp_path_buf[base64.Base64Encoder.calcSize(RANDOM_BYTES)] = 0; while (true) { - try crypto.randomBytes(rand_buf[0..]); + crypto.random.bytes(rand_buf[0..]); base64_encoder.encode(&tmp_path_buf, &rand_buf); const file = dir.createFile( diff --git a/lib/std/rand.zig b/lib/std/rand.zig index a201968a5f..681c67f22d 100644 --- a/lib/std/rand.zig +++ b/lib/std/rand.zig @@ -4,19 +4,11 @@ // The MIT license requires this copyright notice to be included in all copies // and substantial portions of the software. -//! The engines provided here should be initialized from an external source. For now, randomBytes -//! from the crypto package is the most suitable. Be sure to use a CSPRNG when required, otherwise using -//! a normal PRNG will be faster and use substantially less stack space. -//! -//! ``` -//! var buf: [8]u8 = undefined; -//! try std.crypto.randomBytes(buf[0..]); -//! const seed = mem.readIntLittle(u64, buf[0..8]); -//! -//! var r = DefaultPrng.init(seed); -//! -//! const s = r.random.int(u64); -//! ``` +//! The engines provided here should be initialized from an external source. +//! For a thread-local cryptographically secure pseudo random number generator, +//! use `std.crypto.random`. +//! Be sure to use a CSPRNG when required, otherwise using a normal PRNG will +//! be faster and use substantially less stack space. //! //! TODO(tiehuis): Benchmark these against other reference implementations. @@ -36,6 +28,12 @@ pub const DefaultPrng = Xoroshiro128; /// Cryptographically secure random numbers. pub const DefaultCsprng = Gimli; +pub const Isaac64 = @import("rand/Isaac64.zig"); +pub const Gimli = @import("rand/Gimli.zig"); +pub const Pcg = @import("rand/Pcg.zig"); +pub const Xoroshiro128 = @import("rand/Xoroshiro128.zig"); +pub const Sfc64 = @import("rand/Sfc64.zig"); + pub const Random = struct { fillFn: fn (r: *Random, buf: []u8) void, @@ -491,7 +489,7 @@ test "Random Biased" { // // The number of cycles is thus limited to 64-bits regardless of the engine, but this // is still plenty for practical purposes. -const SplitMix64 = struct { +pub const SplitMix64 = struct { s: u64, pub fn init(seed: u64) SplitMix64 { @@ -525,557 +523,6 @@ test "splitmix64 sequence" { } } -// PCG32 - http://www.pcg-random.org/ -// -// PRNG -pub const Pcg = struct { - const default_multiplier = 6364136223846793005; - - random: Random, - - s: u64, - i: u64, - - pub fn init(init_s: u64) Pcg { - var pcg = Pcg{ - .random = Random{ .fillFn = fill }, - .s = undefined, - .i = undefined, - }; - - pcg.seed(init_s); - return pcg; - } - - fn next(self: *Pcg) u32 { - const l = self.s; - self.s = l *% default_multiplier +% (self.i | 1); - - const xor_s = @truncate(u32, ((l >> 18) ^ l) >> 27); - const rot = @intCast(u32, l >> 59); - - return (xor_s >> @intCast(u5, rot)) | (xor_s << @intCast(u5, (0 -% rot) & 31)); - } - - fn seed(self: *Pcg, init_s: u64) void { - // Pcg requires 128-bits of seed. - var gen = SplitMix64.init(init_s); - self.seedTwo(gen.next(), gen.next()); - } - - fn seedTwo(self: *Pcg, init_s: u64, init_i: u64) void { - self.s = 0; - self.i = (init_s << 1) | 1; - self.s = self.s *% default_multiplier +% self.i; - self.s +%= init_i; - self.s = self.s *% default_multiplier +% self.i; - } - - fn fill(r: *Random, buf: []u8) void { - const self = @fieldParentPtr(Pcg, "random", r); - - var i: usize = 0; - const aligned_len = buf.len - (buf.len & 7); - - // Complete 4 byte segments. - while (i < aligned_len) : (i += 4) { - var n = self.next(); - comptime var j: usize = 0; - inline while (j < 4) : (j += 1) { - buf[i + j] = @truncate(u8, n); - n >>= 8; - } - } - - // Remaining. (cuts the stream) - if (i != buf.len) { - var n = self.next(); - while (i < buf.len) : (i += 1) { - buf[i] = @truncate(u8, n); - n >>= 4; - } - } - } -}; - -test "pcg sequence" { - var r = Pcg.init(0); - const s0: u64 = 0x9394bf54ce5d79de; - const s1: u64 = 0x84e9c579ef59bbf7; - r.seedTwo(s0, s1); - - const seq = [_]u32{ - 2881561918, - 3063928540, - 1199791034, - 2487695858, - 1479648952, - 3247963454, - }; - - for (seq) |s| { - expect(s == r.next()); - } -} - -// Xoroshiro128+ - http://xoroshiro.di.unimi.it/ -// -// PRNG -pub const Xoroshiro128 = struct { - random: Random, - - s: [2]u64, - - pub fn init(init_s: u64) Xoroshiro128 { - var x = Xoroshiro128{ - .random = Random{ .fillFn = fill }, - .s = undefined, - }; - - x.seed(init_s); - return x; - } - - fn next(self: *Xoroshiro128) u64 { - const s0 = self.s[0]; - var s1 = self.s[1]; - const r = s0 +% s1; - - s1 ^= s0; - self.s[0] = math.rotl(u64, s0, @as(u8, 55)) ^ s1 ^ (s1 << 14); - self.s[1] = math.rotl(u64, s1, @as(u8, 36)); - - return r; - } - - // Skip 2^64 places ahead in the sequence - fn jump(self: *Xoroshiro128) void { - var s0: u64 = 0; - var s1: u64 = 0; - - const table = [_]u64{ - 0xbeac0467eba5facb, - 0xd86b048b86aa9922, - }; - - inline for (table) |entry| { - var b: usize = 0; - while (b < 64) : (b += 1) { - if ((entry & (@as(u64, 1) << @intCast(u6, b))) != 0) { - s0 ^= self.s[0]; - s1 ^= self.s[1]; - } - _ = self.next(); - } - } - - self.s[0] = s0; - self.s[1] = s1; - } - - pub fn seed(self: *Xoroshiro128, init_s: u64) void { - // Xoroshiro requires 128-bits of seed. - var gen = SplitMix64.init(init_s); - - self.s[0] = gen.next(); - self.s[1] = gen.next(); - } - - fn fill(r: *Random, buf: []u8) void { - const self = @fieldParentPtr(Xoroshiro128, "random", r); - - var i: usize = 0; - const aligned_len = buf.len - (buf.len & 7); - - // Complete 8 byte segments. - while (i < aligned_len) : (i += 8) { - var n = self.next(); - comptime var j: usize = 0; - inline while (j < 8) : (j += 1) { - buf[i + j] = @truncate(u8, n); - n >>= 8; - } - } - - // Remaining. (cuts the stream) - if (i != buf.len) { - var n = self.next(); - while (i < buf.len) : (i += 1) { - buf[i] = @truncate(u8, n); - n >>= 8; - } - } - } -}; - -test "xoroshiro sequence" { - var r = Xoroshiro128.init(0); - r.s[0] = 0xaeecf86f7878dd75; - r.s[1] = 0x01cd153642e72622; - - const seq1 = [_]u64{ - 0xb0ba0da5bb600397, - 0x18a08afde614dccc, - 0xa2635b956a31b929, - 0xabe633c971efa045, - 0x9ac19f9706ca3cac, - 0xf62b426578c1e3fb, - }; - - for (seq1) |s| { - expect(s == r.next()); - } - - r.jump(); - - const seq2 = [_]u64{ - 0x95344a13556d3e22, - 0xb4fb32dafa4d00df, - 0xb2011d9ccdcfe2dd, - 0x05679a9b2119b908, - 0xa860a1da7c9cd8a0, - 0x658a96efe3f86550, - }; - - for (seq2) |s| { - expect(s == r.next()); - } -} - -// Gimli -// -// CSPRNG -pub const Gimli = struct { - random: Random, - state: std.crypto.core.Gimli, - - pub const secret_seed_length = 32; - - /// The seed must be uniform, secret and `secret_seed_length` bytes long. - /// It can be generated using `std.crypto.randomBytes()`. - pub fn init(secret_seed: [secret_seed_length]u8) Gimli { - var initial_state: [std.crypto.core.Gimli.BLOCKBYTES]u8 = undefined; - mem.copy(u8, initial_state[0..secret_seed_length], &secret_seed); - mem.set(u8, initial_state[secret_seed_length..], 0); - var self = Gimli{ - .random = Random{ .fillFn = fill }, - .state = std.crypto.core.Gimli.init(initial_state), - }; - return self; - } - - fn fill(r: *Random, buf: []u8) void { - const self = @fieldParentPtr(Gimli, "random", r); - - if (buf.len != 0) { - self.state.squeeze(buf); - } else { - self.state.permute(); - } - mem.set(u8, self.state.toSlice()[0..std.crypto.core.Gimli.RATE], 0); - } -}; - -// ISAAC64 - http://www.burtleburtle.net/bob/rand/isaacafa.html -// -// Follows the general idea of the implementation from here with a few shortcuts. -// https://doc.rust-lang.org/rand/src/rand/prng/isaac64.rs.html -pub const Isaac64 = struct { - random: Random, - - r: [256]u64, - m: [256]u64, - a: u64, - b: u64, - c: u64, - i: usize, - - pub fn init(init_s: u64) Isaac64 { - var isaac = Isaac64{ - .random = Random{ .fillFn = fill }, - .r = undefined, - .m = undefined, - .a = undefined, - .b = undefined, - .c = undefined, - .i = undefined, - }; - - // seed == 0 => same result as the unseeded reference implementation - isaac.seed(init_s, 1); - return isaac; - } - - fn step(self: *Isaac64, mix: u64, base: usize, comptime m1: usize, comptime m2: usize) void { - const x = self.m[base + m1]; - self.a = mix +% self.m[base + m2]; - - const y = self.a +% self.b +% self.m[@intCast(usize, (x >> 3) % self.m.len)]; - self.m[base + m1] = y; - - self.b = x +% self.m[@intCast(usize, (y >> 11) % self.m.len)]; - self.r[self.r.len - 1 - base - m1] = self.b; - } - - fn refill(self: *Isaac64) void { - const midpoint = self.r.len / 2; - - self.c +%= 1; - self.b +%= self.c; - - { - var i: usize = 0; - while (i < midpoint) : (i += 4) { - self.step(~(self.a ^ (self.a << 21)), i + 0, 0, midpoint); - self.step(self.a ^ (self.a >> 5), i + 1, 0, midpoint); - self.step(self.a ^ (self.a << 12), i + 2, 0, midpoint); - self.step(self.a ^ (self.a >> 33), i + 3, 0, midpoint); - } - } - - { - var i: usize = 0; - while (i < midpoint) : (i += 4) { - self.step(~(self.a ^ (self.a << 21)), i + 0, midpoint, 0); - self.step(self.a ^ (self.a >> 5), i + 1, midpoint, 0); - self.step(self.a ^ (self.a << 12), i + 2, midpoint, 0); - self.step(self.a ^ (self.a >> 33), i + 3, midpoint, 0); - } - } - - self.i = 0; - } - - fn next(self: *Isaac64) u64 { - if (self.i >= self.r.len) { - self.refill(); - } - - const value = self.r[self.i]; - self.i += 1; - return value; - } - - fn seed(self: *Isaac64, init_s: u64, comptime rounds: usize) void { - // We ignore the multi-pass requirement since we don't currently expose full access to - // seeding the self.m array completely. - mem.set(u64, self.m[0..], 0); - self.m[0] = init_s; - - // prescrambled golden ratio constants - var a = [_]u64{ - 0x647c4677a2884b7c, - 0xb9f8b322c73ac862, - 0x8c0ea5053d4712a0, - 0xb29b2e824a595524, - 0x82f053db8355e0ce, - 0x48fe4a0fa5a09315, - 0xae985bf2cbfc89ed, - 0x98f5704f6c44c0ab, - }; - - comptime var i: usize = 0; - inline while (i < rounds) : (i += 1) { - var j: usize = 0; - while (j < self.m.len) : (j += 8) { - comptime var x1: usize = 0; - inline while (x1 < 8) : (x1 += 1) { - a[x1] +%= self.m[j + x1]; - } - - a[0] -%= a[4]; - a[5] ^= a[7] >> 9; - a[7] +%= a[0]; - a[1] -%= a[5]; - a[6] ^= a[0] << 9; - a[0] +%= a[1]; - a[2] -%= a[6]; - a[7] ^= a[1] >> 23; - a[1] +%= a[2]; - a[3] -%= a[7]; - a[0] ^= a[2] << 15; - a[2] +%= a[3]; - a[4] -%= a[0]; - a[1] ^= a[3] >> 14; - a[3] +%= a[4]; - a[5] -%= a[1]; - a[2] ^= a[4] << 20; - a[4] +%= a[5]; - a[6] -%= a[2]; - a[3] ^= a[5] >> 17; - a[5] +%= a[6]; - a[7] -%= a[3]; - a[4] ^= a[6] << 14; - a[6] +%= a[7]; - - comptime var x2: usize = 0; - inline while (x2 < 8) : (x2 += 1) { - self.m[j + x2] = a[x2]; - } - } - } - - mem.set(u64, self.r[0..], 0); - self.a = 0; - self.b = 0; - self.c = 0; - self.i = self.r.len; // trigger refill on first value - } - - fn fill(r: *Random, buf: []u8) void { - const self = @fieldParentPtr(Isaac64, "random", r); - - var i: usize = 0; - const aligned_len = buf.len - (buf.len & 7); - - // Fill complete 64-byte segments - while (i < aligned_len) : (i += 8) { - var n = self.next(); - comptime var j: usize = 0; - inline while (j < 8) : (j += 1) { - buf[i + j] = @truncate(u8, n); - n >>= 8; - } - } - - // Fill trailing, ignoring excess (cut the stream). - if (i != buf.len) { - var n = self.next(); - while (i < buf.len) : (i += 1) { - buf[i] = @truncate(u8, n); - n >>= 8; - } - } - } -}; - -test "isaac64 sequence" { - var r = Isaac64.init(0); - - // from reference implementation - const seq = [_]u64{ - 0xf67dfba498e4937c, - 0x84a5066a9204f380, - 0xfee34bd5f5514dbb, - 0x4d1664739b8f80d6, - 0x8607459ab52a14aa, - 0x0e78bc5a98529e49, - 0xfe5332822ad13777, - 0x556c27525e33d01a, - 0x08643ca615f3149f, - 0xd0771faf3cb04714, - 0x30e86f68a37b008d, - 0x3074ebc0488a3adf, - 0x270645ea7a2790bc, - 0x5601a0a8d3763c6a, - 0x2f83071f53f325dd, - 0xb9090f3d42d2d2ea, - }; - - for (seq) |s| { - expect(s == r.next()); - } -} - -/// Sfc64 pseudo-random number generator from Practically Random. -/// Fastest engine of pracrand and smallest footprint. -/// See http://pracrand.sourceforge.net/ -pub const Sfc64 = struct { - random: Random, - - a: u64 = undefined, - b: u64 = undefined, - c: u64 = undefined, - counter: u64 = undefined, - - const Rotation = 24; - const RightShift = 11; - const LeftShift = 3; - - pub fn init(init_s: u64) Sfc64 { - var x = Sfc64{ - .random = Random{ .fillFn = fill }, - }; - - x.seed(init_s); - return x; - } - - fn next(self: *Sfc64) u64 { - const tmp = self.a +% self.b +% self.counter; - self.counter += 1; - self.a = self.b ^ (self.b >> RightShift); - self.b = self.c +% (self.c << LeftShift); - self.c = math.rotl(u64, self.c, Rotation) +% tmp; - return tmp; - } - - fn seed(self: *Sfc64, init_s: u64) void { - self.a = init_s; - self.b = init_s; - self.c = init_s; - self.counter = 1; - var i: u32 = 0; - while (i < 12) : (i += 1) { - _ = self.next(); - } - } - - fn fill(r: *Random, buf: []u8) void { - const self = @fieldParentPtr(Sfc64, "random", r); - - var i: usize = 0; - const aligned_len = buf.len - (buf.len & 7); - - // Complete 8 byte segments. - while (i < aligned_len) : (i += 8) { - var n = self.next(); - comptime var j: usize = 0; - inline while (j < 8) : (j += 1) { - buf[i + j] = @truncate(u8, n); - n >>= 8; - } - } - - // Remaining. (cuts the stream) - if (i != buf.len) { - var n = self.next(); - while (i < buf.len) : (i += 1) { - buf[i] = @truncate(u8, n); - n >>= 8; - } - } - } -}; - -test "Sfc64 sequence" { - // Unfortunately there does not seem to be an official test sequence. - var r = Sfc64.init(0); - - const seq = [_]u64{ - 0x3acfa029e3cc6041, - 0xf5b6515bf2ee419c, - 0x1259635894a29b61, - 0xb6ae75395f8ebd6, - 0x225622285ce302e2, - 0x520d28611395cb21, - 0xdb909c818901599d, - 0x8ffd195365216f57, - 0xe8c4ad5e258ac04a, - 0x8f8ef2c89fdb63ca, - 0xf9865b01d98d8e2f, - 0x46555871a65d08ba, - 0x66868677c6298fcd, - 0x2ce15a7e6329f57d, - 0xb2f1833ca91ca79, - 0x4b0890ac9bf453ca, - }; - - for (seq) |s| { - expectEqual(s, r.next()); - } -} - // Actual Random helper function tests, pcg engine is assumed correct. test "Random float" { var prng = DefaultPrng.init(0); @@ -1147,7 +594,7 @@ fn testRangeBias(r: *Random, start: i8, end: i8, biased: bool) void { test "CSPRNG" { var secret_seed: [DefaultCsprng.secret_seed_length]u8 = undefined; - try std.crypto.randomBytes(&secret_seed); + std.crypto.random.bytes(&secret_seed); var csprng = DefaultCsprng.init(secret_seed); const a = csprng.random.int(u64); const b = csprng.random.int(u64); diff --git a/lib/std/rand/Gimli.zig b/lib/std/rand/Gimli.zig new file mode 100644 index 0000000000..32331e7153 --- /dev/null +++ b/lib/std/rand/Gimli.zig @@ -0,0 +1,40 @@ +// SPDX-License-Identifier: MIT +// Copyright (c) 2015-2020 Zig Contributors +// This file is part of [zig](https://ziglang.org/), which is MIT licensed. +// The MIT license requires this copyright notice to be included in all copies +// and substantial portions of the software. + +//! CSPRNG + +const std = @import("std"); +const Random = std.rand.Random; +const mem = std.mem; +const Gimli = @This(); + +random: Random, +state: std.crypto.core.Gimli, + +pub const secret_seed_length = 32; + +/// The seed must be uniform, secret and `secret_seed_length` bytes long. +pub fn init(secret_seed: [secret_seed_length]u8) Gimli { + var initial_state: [std.crypto.core.Gimli.BLOCKBYTES]u8 = undefined; + mem.copy(u8, initial_state[0..secret_seed_length], &secret_seed); + mem.set(u8, initial_state[secret_seed_length..], 0); + var self = Gimli{ + .random = Random{ .fillFn = fill }, + .state = std.crypto.core.Gimli.init(initial_state), + }; + return self; +} + +fn fill(r: *Random, buf: []u8) void { + const self = @fieldParentPtr(Gimli, "random", r); + + if (buf.len != 0) { + self.state.squeeze(buf); + } else { + self.state.permute(); + } + mem.set(u8, self.state.toSlice()[0..std.crypto.core.Gimli.RATE], 0); +} diff --git a/lib/std/rand/Isaac64.zig b/lib/std/rand/Isaac64.zig new file mode 100644 index 0000000000..a079f19b9e --- /dev/null +++ b/lib/std/rand/Isaac64.zig @@ -0,0 +1,210 @@ +// SPDX-License-Identifier: MIT +// Copyright (c) 2015-2020 Zig Contributors +// This file is part of [zig](https://ziglang.org/), which is MIT licensed. +// The MIT license requires this copyright notice to be included in all copies +// and substantial portions of the software. + +//! ISAAC64 - http://www.burtleburtle.net/bob/rand/isaacafa.html +//! +//! Follows the general idea of the implementation from here with a few shortcuts. +//! https://doc.rust-lang.org/rand/src/rand/prng/isaac64.rs.html + +const std = @import("std"); +const Random = std.rand.Random; +const mem = std.mem; +const Isaac64 = @This(); + +random: Random, + +r: [256]u64, +m: [256]u64, +a: u64, +b: u64, +c: u64, +i: usize, + +pub fn init(init_s: u64) Isaac64 { + var isaac = Isaac64{ + .random = Random{ .fillFn = fill }, + .r = undefined, + .m = undefined, + .a = undefined, + .b = undefined, + .c = undefined, + .i = undefined, + }; + + // seed == 0 => same result as the unseeded reference implementation + isaac.seed(init_s, 1); + return isaac; +} + +fn step(self: *Isaac64, mix: u64, base: usize, comptime m1: usize, comptime m2: usize) void { + const x = self.m[base + m1]; + self.a = mix +% self.m[base + m2]; + + const y = self.a +% self.b +% self.m[@intCast(usize, (x >> 3) % self.m.len)]; + self.m[base + m1] = y; + + self.b = x +% self.m[@intCast(usize, (y >> 11) % self.m.len)]; + self.r[self.r.len - 1 - base - m1] = self.b; +} + +fn refill(self: *Isaac64) void { + const midpoint = self.r.len / 2; + + self.c +%= 1; + self.b +%= self.c; + + { + var i: usize = 0; + while (i < midpoint) : (i += 4) { + self.step(~(self.a ^ (self.a << 21)), i + 0, 0, midpoint); + self.step(self.a ^ (self.a >> 5), i + 1, 0, midpoint); + self.step(self.a ^ (self.a << 12), i + 2, 0, midpoint); + self.step(self.a ^ (self.a >> 33), i + 3, 0, midpoint); + } + } + + { + var i: usize = 0; + while (i < midpoint) : (i += 4) { + self.step(~(self.a ^ (self.a << 21)), i + 0, midpoint, 0); + self.step(self.a ^ (self.a >> 5), i + 1, midpoint, 0); + self.step(self.a ^ (self.a << 12), i + 2, midpoint, 0); + self.step(self.a ^ (self.a >> 33), i + 3, midpoint, 0); + } + } + + self.i = 0; +} + +fn next(self: *Isaac64) u64 { + if (self.i >= self.r.len) { + self.refill(); + } + + const value = self.r[self.i]; + self.i += 1; + return value; +} + +fn seed(self: *Isaac64, init_s: u64, comptime rounds: usize) void { + // We ignore the multi-pass requirement since we don't currently expose full access to + // seeding the self.m array completely. + mem.set(u64, self.m[0..], 0); + self.m[0] = init_s; + + // prescrambled golden ratio constants + var a = [_]u64{ + 0x647c4677a2884b7c, + 0xb9f8b322c73ac862, + 0x8c0ea5053d4712a0, + 0xb29b2e824a595524, + 0x82f053db8355e0ce, + 0x48fe4a0fa5a09315, + 0xae985bf2cbfc89ed, + 0x98f5704f6c44c0ab, + }; + + comptime var i: usize = 0; + inline while (i < rounds) : (i += 1) { + var j: usize = 0; + while (j < self.m.len) : (j += 8) { + comptime var x1: usize = 0; + inline while (x1 < 8) : (x1 += 1) { + a[x1] +%= self.m[j + x1]; + } + + a[0] -%= a[4]; + a[5] ^= a[7] >> 9; + a[7] +%= a[0]; + a[1] -%= a[5]; + a[6] ^= a[0] << 9; + a[0] +%= a[1]; + a[2] -%= a[6]; + a[7] ^= a[1] >> 23; + a[1] +%= a[2]; + a[3] -%= a[7]; + a[0] ^= a[2] << 15; + a[2] +%= a[3]; + a[4] -%= a[0]; + a[1] ^= a[3] >> 14; + a[3] +%= a[4]; + a[5] -%= a[1]; + a[2] ^= a[4] << 20; + a[4] +%= a[5]; + a[6] -%= a[2]; + a[3] ^= a[5] >> 17; + a[5] +%= a[6]; + a[7] -%= a[3]; + a[4] ^= a[6] << 14; + a[6] +%= a[7]; + + comptime var x2: usize = 0; + inline while (x2 < 8) : (x2 += 1) { + self.m[j + x2] = a[x2]; + } + } + } + + mem.set(u64, self.r[0..], 0); + self.a = 0; + self.b = 0; + self.c = 0; + self.i = self.r.len; // trigger refill on first value +} + +fn fill(r: *Random, buf: []u8) void { + const self = @fieldParentPtr(Isaac64, "random", r); + + var i: usize = 0; + const aligned_len = buf.len - (buf.len & 7); + + // Fill complete 64-byte segments + while (i < aligned_len) : (i += 8) { + var n = self.next(); + comptime var j: usize = 0; + inline while (j < 8) : (j += 1) { + buf[i + j] = @truncate(u8, n); + n >>= 8; + } + } + + // Fill trailing, ignoring excess (cut the stream). + if (i != buf.len) { + var n = self.next(); + while (i < buf.len) : (i += 1) { + buf[i] = @truncate(u8, n); + n >>= 8; + } + } +} + +test "isaac64 sequence" { + var r = Isaac64.init(0); + + // from reference implementation + const seq = [_]u64{ + 0xf67dfba498e4937c, + 0x84a5066a9204f380, + 0xfee34bd5f5514dbb, + 0x4d1664739b8f80d6, + 0x8607459ab52a14aa, + 0x0e78bc5a98529e49, + 0xfe5332822ad13777, + 0x556c27525e33d01a, + 0x08643ca615f3149f, + 0xd0771faf3cb04714, + 0x30e86f68a37b008d, + 0x3074ebc0488a3adf, + 0x270645ea7a2790bc, + 0x5601a0a8d3763c6a, + 0x2f83071f53f325dd, + 0xb9090f3d42d2d2ea, + }; + + for (seq) |s| { + std.testing.expect(s == r.next()); + } +} diff --git a/lib/std/rand/Pcg.zig b/lib/std/rand/Pcg.zig new file mode 100644 index 0000000000..1bbe8beb63 --- /dev/null +++ b/lib/std/rand/Pcg.zig @@ -0,0 +1,101 @@ +// SPDX-License-Identifier: MIT +// Copyright (c) 2015-2020 Zig Contributors +// This file is part of [zig](https://ziglang.org/), which is MIT licensed. +// The MIT license requires this copyright notice to be included in all copies +// and substantial portions of the software. + +//! PCG32 - http://www.pcg-random.org/ +//! +//! PRNG + +const std = @import("std"); +const Random = std.rand.Random; +const Pcg = @This(); + +const default_multiplier = 6364136223846793005; + +random: Random, + +s: u64, +i: u64, + +pub fn init(init_s: u64) Pcg { + var pcg = Pcg{ + .random = Random{ .fillFn = fill }, + .s = undefined, + .i = undefined, + }; + + pcg.seed(init_s); + return pcg; +} + +fn next(self: *Pcg) u32 { + const l = self.s; + self.s = l *% default_multiplier +% (self.i | 1); + + const xor_s = @truncate(u32, ((l >> 18) ^ l) >> 27); + const rot = @intCast(u32, l >> 59); + + return (xor_s >> @intCast(u5, rot)) | (xor_s << @intCast(u5, (0 -% rot) & 31)); +} + +fn seed(self: *Pcg, init_s: u64) void { + // Pcg requires 128-bits of seed. + var gen = std.rand.SplitMix64.init(init_s); + self.seedTwo(gen.next(), gen.next()); +} + +fn seedTwo(self: *Pcg, init_s: u64, init_i: u64) void { + self.s = 0; + self.i = (init_s << 1) | 1; + self.s = self.s *% default_multiplier +% self.i; + self.s +%= init_i; + self.s = self.s *% default_multiplier +% self.i; +} + +fn fill(r: *Random, buf: []u8) void { + const self = @fieldParentPtr(Pcg, "random", r); + + var i: usize = 0; + const aligned_len = buf.len - (buf.len & 7); + + // Complete 4 byte segments. + while (i < aligned_len) : (i += 4) { + var n = self.next(); + comptime var j: usize = 0; + inline while (j < 4) : (j += 1) { + buf[i + j] = @truncate(u8, n); + n >>= 8; + } + } + + // Remaining. (cuts the stream) + if (i != buf.len) { + var n = self.next(); + while (i < buf.len) : (i += 1) { + buf[i] = @truncate(u8, n); + n >>= 4; + } + } +} + +test "pcg sequence" { + var r = Pcg.init(0); + const s0: u64 = 0x9394bf54ce5d79de; + const s1: u64 = 0x84e9c579ef59bbf7; + r.seedTwo(s0, s1); + + const seq = [_]u32{ + 2881561918, + 3063928540, + 1199791034, + 2487695858, + 1479648952, + 3247963454, + }; + + for (seq) |s| { + std.testing.expect(s == r.next()); + } +} diff --git a/lib/std/rand/Sfc64.zig b/lib/std/rand/Sfc64.zig new file mode 100644 index 0000000000..feba5d884c --- /dev/null +++ b/lib/std/rand/Sfc64.zig @@ -0,0 +1,108 @@ +// SPDX-License-Identifier: MIT +// Copyright (c) 2015-2020 Zig Contributors +// This file is part of [zig](https://ziglang.org/), which is MIT licensed. +// The MIT license requires this copyright notice to be included in all copies +// and substantial portions of the software. + +//! Sfc64 pseudo-random number generator from Practically Random. +//! Fastest engine of pracrand and smallest footprint. +//! See http://pracrand.sourceforge.net/ + +const std = @import("std"); +const Random = std.rand.Random; +const math = std.math; +const Sfc64 = @This(); + +random: Random, + +a: u64 = undefined, +b: u64 = undefined, +c: u64 = undefined, +counter: u64 = undefined, + +const Rotation = 24; +const RightShift = 11; +const LeftShift = 3; + +pub fn init(init_s: u64) Sfc64 { + var x = Sfc64{ + .random = Random{ .fillFn = fill }, + }; + + x.seed(init_s); + return x; +} + +fn next(self: *Sfc64) u64 { + const tmp = self.a +% self.b +% self.counter; + self.counter += 1; + self.a = self.b ^ (self.b >> RightShift); + self.b = self.c +% (self.c << LeftShift); + self.c = math.rotl(u64, self.c, Rotation) +% tmp; + return tmp; +} + +fn seed(self: *Sfc64, init_s: u64) void { + self.a = init_s; + self.b = init_s; + self.c = init_s; + self.counter = 1; + var i: u32 = 0; + while (i < 12) : (i += 1) { + _ = self.next(); + } +} + +fn fill(r: *Random, buf: []u8) void { + const self = @fieldParentPtr(Sfc64, "random", r); + + var i: usize = 0; + const aligned_len = buf.len - (buf.len & 7); + + // Complete 8 byte segments. + while (i < aligned_len) : (i += 8) { + var n = self.next(); + comptime var j: usize = 0; + inline while (j < 8) : (j += 1) { + buf[i + j] = @truncate(u8, n); + n >>= 8; + } + } + + // Remaining. (cuts the stream) + if (i != buf.len) { + var n = self.next(); + while (i < buf.len) : (i += 1) { + buf[i] = @truncate(u8, n); + n >>= 8; + } + } +} + +test "Sfc64 sequence" { + // Unfortunately there does not seem to be an official test sequence. + var r = Sfc64.init(0); + + const seq = [_]u64{ + 0x3acfa029e3cc6041, + 0xf5b6515bf2ee419c, + 0x1259635894a29b61, + 0xb6ae75395f8ebd6, + 0x225622285ce302e2, + 0x520d28611395cb21, + 0xdb909c818901599d, + 0x8ffd195365216f57, + 0xe8c4ad5e258ac04a, + 0x8f8ef2c89fdb63ca, + 0xf9865b01d98d8e2f, + 0x46555871a65d08ba, + 0x66868677c6298fcd, + 0x2ce15a7e6329f57d, + 0xb2f1833ca91ca79, + 0x4b0890ac9bf453ca, + }; + + for (seq) |s| { + std.testing.expectEqual(s, r.next()); + } +} diff --git a/lib/std/rand/Xoroshiro128.zig b/lib/std/rand/Xoroshiro128.zig new file mode 100644 index 0000000000..2cc9bf9070 --- /dev/null +++ b/lib/std/rand/Xoroshiro128.zig @@ -0,0 +1,133 @@ +// SPDX-License-Identifier: MIT +// Copyright (c) 2015-2020 Zig Contributors +// This file is part of [zig](https://ziglang.org/), which is MIT licensed. +// The MIT license requires this copyright notice to be included in all copies +// and substantial portions of the software. + +//! Xoroshiro128+ - http://xoroshiro.di.unimi.it/ +//! +//! PRNG + +const std = @import("std"); +const Random = std.rand.Random; +const math = std.math; +const Xoroshiro128 = @This(); + +random: Random, + +s: [2]u64, + +pub fn init(init_s: u64) Xoroshiro128 { + var x = Xoroshiro128{ + .random = Random{ .fillFn = fill }, + .s = undefined, + }; + + x.seed(init_s); + return x; +} + +fn next(self: *Xoroshiro128) u64 { + const s0 = self.s[0]; + var s1 = self.s[1]; + const r = s0 +% s1; + + s1 ^= s0; + self.s[0] = math.rotl(u64, s0, @as(u8, 55)) ^ s1 ^ (s1 << 14); + self.s[1] = math.rotl(u64, s1, @as(u8, 36)); + + return r; +} + +// Skip 2^64 places ahead in the sequence +fn jump(self: *Xoroshiro128) void { + var s0: u64 = 0; + var s1: u64 = 0; + + const table = [_]u64{ + 0xbeac0467eba5facb, + 0xd86b048b86aa9922, + }; + + inline for (table) |entry| { + var b: usize = 0; + while (b < 64) : (b += 1) { + if ((entry & (@as(u64, 1) << @intCast(u6, b))) != 0) { + s0 ^= self.s[0]; + s1 ^= self.s[1]; + } + _ = self.next(); + } + } + + self.s[0] = s0; + self.s[1] = s1; +} + +pub fn seed(self: *Xoroshiro128, init_s: u64) void { + // Xoroshiro requires 128-bits of seed. + var gen = std.rand.SplitMix64.init(init_s); + + self.s[0] = gen.next(); + self.s[1] = gen.next(); +} + +fn fill(r: *Random, buf: []u8) void { + const self = @fieldParentPtr(Xoroshiro128, "random", r); + + var i: usize = 0; + const aligned_len = buf.len - (buf.len & 7); + + // Complete 8 byte segments. + while (i < aligned_len) : (i += 8) { + var n = self.next(); + comptime var j: usize = 0; + inline while (j < 8) : (j += 1) { + buf[i + j] = @truncate(u8, n); + n >>= 8; + } + } + + // Remaining. (cuts the stream) + if (i != buf.len) { + var n = self.next(); + while (i < buf.len) : (i += 1) { + buf[i] = @truncate(u8, n); + n >>= 8; + } + } +} + +test "xoroshiro sequence" { + var r = Xoroshiro128.init(0); + r.s[0] = 0xaeecf86f7878dd75; + r.s[1] = 0x01cd153642e72622; + + const seq1 = [_]u64{ + 0xb0ba0da5bb600397, + 0x18a08afde614dccc, + 0xa2635b956a31b929, + 0xabe633c971efa045, + 0x9ac19f9706ca3cac, + 0xf62b426578c1e3fb, + }; + + for (seq1) |s| { + std.testing.expect(s == r.next()); + } + + r.jump(); + + const seq2 = [_]u64{ + 0x95344a13556d3e22, + 0xb4fb32dafa4d00df, + 0xb2011d9ccdcfe2dd, + 0x05679a9b2119b908, + 0xa860a1da7c9cd8a0, + 0x658a96efe3f86550, + }; + + for (seq2) |s| { + std.testing.expect(s == r.next()); + } +} diff --git a/lib/std/start.zig b/lib/std/start.zig index 7d3a9c45c7..b6fb7e4dfd 100644 --- a/lib/std/start.zig +++ b/lib/std/start.zig @@ -10,6 +10,7 @@ const std = @import("std.zig"); const builtin = std.builtin; const assert = std.debug.assert; const uefi = std.os.uefi; +const tlcsprng = @import("crypto/tlcsprng.zig"); var argc_argv_ptr: [*]usize = undefined; @@ -215,6 +216,28 @@ fn posixCallMainAndExit() noreturn { std.os.linux.tls.initStaticTLS(); } + { + // Initialize the per-thread CSPRNG since Linux gave us the handy-dandy + // AT_RANDOM. This depends on the TLS initialization above. + var i: usize = 0; + while (auxv[i].a_type != std.elf.AT_NULL) : (i += 1) { + switch (auxv[i].a_type) { + std.elf.AT_RANDOM => { + // "The address of sixteen bytes containing a random value." + const addr = auxv[i].a_un.a_val; + if (addr == 0) break; + const ptr = @intToPtr(*const [16]u8, addr); + var seed: [32]u8 = undefined; + seed[0..16].* = ptr.*; + seed[16..].* = ptr.*; + tlcsprng.init(seed); + break; + }, + else => continue, + } + } + } + // TODO This is disabled because what should we do when linking libc and this code // does not execute? And also it's causing a test failure in stack traces in release modes. @@ -250,6 +273,9 @@ fn callMainWithArgs(argc: usize, argv: [*][*:0]u8, envp: [][*:0]u8) u8 { } fn main(c_argc: i32, c_argv: [*][*:0]u8, c_envp: [*:null]?[*:0]u8) callconv(.C) i32 { + // We do not attempt to initialize tlcsprng from AT_RANDOM here because + // libc owns the start code, not us, and therefore libc ows the random bytes + // from AT_RANDOM. var env_count: usize = 0; while (c_envp[env_count] != null) : (env_count += 1) {} const envp = @ptrCast([*][*:0]u8, c_envp)[0..env_count]; diff --git a/lib/std/testing.zig b/lib/std/testing.zig index 69df01190d..63054892db 100644 --- a/lib/std/testing.zig +++ b/lib/std/testing.zig @@ -303,8 +303,7 @@ fn getCwdOrWasiPreopen() std.fs.Dir { pub fn tmpDir(opts: std.fs.Dir.OpenDirOptions) TmpDir { var random_bytes: [TmpDir.random_bytes_count]u8 = undefined; - std.crypto.randomBytes(&random_bytes) catch - @panic("unable to make tmp dir for testing: unable to get random bytes"); + std.crypto.random.bytes(&random_bytes); var sub_path: [TmpDir.sub_path_len]u8 = undefined; std.fs.base64_encoder.encode(&sub_path, &random_bytes); diff --git a/src/Compilation.zig b/src/Compilation.zig index 356a1cedf6..5e95575642 100644 --- a/src/Compilation.zig +++ b/src/Compilation.zig @@ -74,7 +74,6 @@ zig_lib_directory: Directory, local_cache_directory: Directory, global_cache_directory: Directory, libc_include_dir_list: []const []const u8, -rand: *std.rand.Random, /// Populated when we build the libc++ static library. A Job to build this is placed in the queue /// and resolved before calling linker.flush(). @@ -331,7 +330,6 @@ pub const InitOptions = struct { root_name: []const u8, root_pkg: ?*Package, output_mode: std.builtin.OutputMode, - rand: *std.rand.Random, dynamic_linker: ?[]const u8 = null, /// `null` means to not emit a binary file. emit_bin: ?EmitLoc, @@ -981,7 +979,6 @@ pub fn create(gpa: *Allocator, options: InitOptions) !*Compilation { .self_exe_path = options.self_exe_path, .libc_include_dir_list = libc_dirs.libc_include_dir_list, .sanitize_c = sanitize_c, - .rand = options.rand, .clang_passthrough_mode = options.clang_passthrough_mode, .clang_preprocessor_mode = options.clang_preprocessor_mode, .verbose_cc = options.verbose_cc, @@ -1909,7 +1906,7 @@ fn updateCObject(comp: *Compilation, c_object: *CObject, c_comp_progress_node: * pub fn tmpFilePath(comp: *Compilation, arena: *Allocator, suffix: []const u8) error{OutOfMemory}![]const u8 { const s = std.fs.path.sep_str; - const rand_int = comp.rand.int(u64); + const rand_int = std.crypto.random.int(u64); if (comp.local_cache_directory.path) |p| { return std.fmt.allocPrint(arena, "{}" ++ s ++ "tmp" ++ s ++ "{x}-{s}", .{ p, rand_int, suffix }); } else { @@ -2778,7 +2775,6 @@ fn buildOutputFromZig( .root_name = root_name, .root_pkg = &root_pkg, .output_mode = fixed_output_mode, - .rand = comp.rand, .libc_installation = comp.bin_file.options.libc_installation, .emit_bin = emit_bin, .optimize_mode = optimize_mode, @@ -3152,7 +3148,6 @@ pub fn build_crt_file( .root_name = root_name, .root_pkg = null, .output_mode = output_mode, - .rand = comp.rand, .libc_installation = comp.bin_file.options.libc_installation, .emit_bin = emit_bin, .optimize_mode = comp.bin_file.options.optimize_mode, diff --git a/src/glibc.zig b/src/glibc.zig index 901054176e..15c9d743f9 100644 --- a/src/glibc.zig +++ b/src/glibc.zig @@ -936,7 +936,6 @@ fn buildSharedLib( .root_pkg = null, .output_mode = .Lib, .link_mode = .Dynamic, - .rand = comp.rand, .libc_installation = comp.bin_file.options.libc_installation, .emit_bin = emit_bin, .optimize_mode = comp.bin_file.options.optimize_mode, diff --git a/src/libcxx.zig b/src/libcxx.zig index 39ec776659..8de45a49b2 100644 --- a/src/libcxx.zig +++ b/src/libcxx.zig @@ -162,7 +162,6 @@ pub fn buildLibCXX(comp: *Compilation) !void { .root_name = root_name, .root_pkg = null, .output_mode = output_mode, - .rand = comp.rand, .libc_installation = comp.bin_file.options.libc_installation, .emit_bin = emit_bin, .optimize_mode = comp.bin_file.options.optimize_mode, @@ -281,7 +280,6 @@ pub fn buildLibCXXABI(comp: *Compilation) !void { .root_name = root_name, .root_pkg = null, .output_mode = output_mode, - .rand = comp.rand, .libc_installation = comp.bin_file.options.libc_installation, .emit_bin = emit_bin, .optimize_mode = comp.bin_file.options.optimize_mode, diff --git a/src/libunwind.zig b/src/libunwind.zig index ec8fe990e9..9822016ae1 100644 --- a/src/libunwind.zig +++ b/src/libunwind.zig @@ -95,7 +95,6 @@ pub fn buildStaticLib(comp: *Compilation) !void { .root_name = root_name, .root_pkg = null, .output_mode = output_mode, - .rand = comp.rand, .libc_installation = comp.bin_file.options.libc_installation, .emit_bin = emit_bin, .optimize_mode = comp.bin_file.options.optimize_mode, diff --git a/src/main.zig b/src/main.zig index 0222d499fa..c54cc6515b 100644 --- a/src/main.zig +++ b/src/main.zig @@ -1632,13 +1632,6 @@ fn buildOutputType( }; defer zig_lib_directory.handle.close(); - const random_seed = blk: { - var random_seed: u64 = undefined; - try std.crypto.randomBytes(mem.asBytes(&random_seed)); - break :blk random_seed; - }; - var default_prng = std.rand.DefaultPrng.init(random_seed); - var libc_installation: ?LibCInstallation = null; defer if (libc_installation) |*l| l.deinit(gpa); @@ -1754,7 +1747,6 @@ fn buildOutputType( .single_threaded = single_threaded, .function_sections = function_sections, .self_exe_path = self_exe_path, - .rand = &default_prng.random, .clang_passthrough_mode = arg_mode != .build, .clang_preprocessor_mode = clang_preprocessor_mode, .version = optional_version, @@ -2420,12 +2412,6 @@ pub fn cmdBuild(gpa: *Allocator, arena: *Allocator, args: []const []const u8) !v .directory = null, // Use the local zig-cache. .basename = exe_basename, }; - const random_seed = blk: { - var random_seed: u64 = undefined; - try std.crypto.randomBytes(mem.asBytes(&random_seed)); - break :blk random_seed; - }; - var default_prng = std.rand.DefaultPrng.init(random_seed); const comp = Compilation.create(gpa, .{ .zig_lib_directory = zig_lib_directory, .local_cache_directory = local_cache_directory, @@ -2441,7 +2427,6 @@ pub fn cmdBuild(gpa: *Allocator, arena: *Allocator, args: []const []const u8) !v .emit_h = null, .optimize_mode = .Debug, .self_exe_path = self_exe_path, - .rand = &default_prng.random, }) catch |err| { fatal("unable to create compilation: {}", .{@errorName(err)}); }; diff --git a/src/musl.zig b/src/musl.zig index ac39eb7d74..1a30a6e2b9 100644 --- a/src/musl.zig +++ b/src/musl.zig @@ -200,7 +200,6 @@ pub fn buildCRTFile(comp: *Compilation, crt_file: CRTFile) !void { .root_pkg = null, .output_mode = .Lib, .link_mode = .Dynamic, - .rand = comp.rand, .libc_installation = comp.bin_file.options.libc_installation, .emit_bin = Compilation.EmitLoc{ .directory = null, .basename = "libc.so" }, .optimize_mode = comp.bin_file.options.optimize_mode, diff --git a/src/test.zig b/src/test.zig index 251edc2d34..e0497a8cd5 100644 --- a/src/test.zig +++ b/src/test.zig @@ -467,13 +467,6 @@ pub const TestContext = struct { defer zig_lib_directory.handle.close(); defer std.testing.allocator.free(zig_lib_directory.path.?); - const random_seed = blk: { - var random_seed: u64 = undefined; - try std.crypto.randomBytes(std.mem.asBytes(&random_seed)); - break :blk random_seed; - }; - var default_prng = std.rand.DefaultPrng.init(random_seed); - for (self.cases.items) |case| { if (build_options.skip_non_native and case.target.getCpuArch() != std.Target.current.cpu.arch) continue; @@ -487,7 +480,7 @@ pub const TestContext = struct { progress.initial_delay_ns = 0; progress.refresh_rate_ns = 0; - try self.runOneCase(std.testing.allocator, &prg_node, case, zig_lib_directory, &default_prng.random); + try self.runOneCase(std.testing.allocator, &prg_node, case, zig_lib_directory); } } @@ -497,7 +490,6 @@ pub const TestContext = struct { root_node: *std.Progress.Node, case: Case, zig_lib_directory: Compilation.Directory, - rand: *std.rand.Random, ) !void { const target_info = try std.zig.system.NativeTargetInfo.detect(allocator, case.target); const target = target_info.target; @@ -547,7 +539,6 @@ pub const TestContext = struct { .local_cache_directory = zig_cache_directory, .global_cache_directory = zig_cache_directory, .zig_lib_directory = zig_lib_directory, - .rand = rand, .root_name = "test_case", .target = target, // TODO: support tests for object file building, and library builds -- cgit v1.2.3 From 4dcd1e60597c5bd79eab29f49717a13b1b144c8b Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Thu, 17 Dec 2020 20:35:29 -0700 Subject: start code: overwrite AT_RANDOM after we use it --- lib/std/start.zig | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-) diff --git a/lib/std/start.zig b/lib/std/start.zig index b6fb7e4dfd..6249a6e1ac 100644 --- a/lib/std/start.zig +++ b/lib/std/start.zig @@ -226,11 +226,17 @@ fn posixCallMainAndExit() noreturn { // "The address of sixteen bytes containing a random value." const addr = auxv[i].a_un.a_val; if (addr == 0) break; - const ptr = @intToPtr(*const [16]u8, addr); + const ptr = @intToPtr(*[16]u8, addr); var seed: [32]u8 = undefined; seed[0..16].* = ptr.*; seed[16..].* = ptr.*; tlcsprng.init(seed); + // Overwrite AT_RANDOM after we use it, otherwise our secure + // seed is sitting in memory ready for some other code in the + // program to reuse, and hence break our security. + // We play nice by refreshing it with fresh random bytes + // rather than clearing it. + std.crypto.random.bytes(ptr); break; }, else => continue, -- cgit v1.2.3 From 7dab3ae135bbe388b412f06bcd8910b86565635e Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Thu, 17 Dec 2020 21:09:42 -0700 Subject: update guess number standalone test --- test/standalone/guess_number/main.zig | 10 +--------- 1 file changed, 1 insertion(+), 9 deletions(-) diff --git a/test/standalone/guess_number/main.zig b/test/standalone/guess_number/main.zig index 87f9f9a1e7..ad84860870 100644 --- a/test/standalone/guess_number/main.zig +++ b/test/standalone/guess_number/main.zig @@ -9,15 +9,7 @@ pub fn main() !void { try stdout.print("Welcome to the Guess Number Game in Zig.\n", .{}); - var seed_bytes: [@sizeOf(u64)]u8 = undefined; - std.crypto.randomBytes(seed_bytes[0..]) catch |err| { - std.debug.warn("unable to seed random number generator: {}", .{err}); - return err; - }; - const seed = std.mem.readIntNative(u64, &seed_bytes); - var prng = std.rand.DefaultPrng.init(seed); - - const answer = prng.random.intRangeLessThan(u8, 0, 100) + 1; + const answer = std.crypto.random.intRangeLessThan(u8, 0, 100) + 1; while (true) { try stdout.print("\nGuess a number between 1 and 100: ", .{}); -- cgit v1.2.3 From 228a0937a2bb761b3a63d98ddda5402a1f594fe8 Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Thu, 17 Dec 2020 21:09:54 -0700 Subject: memory fences to make sure TLS init happens --- lib/std/start.zig | 2 ++ 1 file changed, 2 insertions(+) diff --git a/lib/std/start.zig b/lib/std/start.zig index 6249a6e1ac..d3065c7719 100644 --- a/lib/std/start.zig +++ b/lib/std/start.zig @@ -206,6 +206,7 @@ fn posixCallMainAndExit() noreturn { // Do this as early as possible, the aux vector is needed if (builtin.position_independent_executable) { @import("os/linux/start_pie.zig").apply_relocations(); + @fence(.SeqCst); } // Initialize the TLS area. We do a runtime check here to make sure @@ -214,6 +215,7 @@ fn posixCallMainAndExit() noreturn { const is_dynamic = @import("dynamic_library.zig").get_DYNAMIC() != null; if (!is_dynamic) { std.os.linux.tls.initStaticTLS(); + @fence(.SeqCst); } { -- cgit v1.2.3 From 2e4b409f31352ff08dbabf350519ba0f5212218a Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Thu, 17 Dec 2020 22:51:53 -0700 Subject: std: tlcsprng: cleanups & improvements * get rid of the pointless fences * make seed_len 16 instead of 32, which is accurate since it was already padding the rest anyway; now we do 1 pad instead of 2. * secureZero to clear the AT_RANDOM auxval * add a flag root source files can use to disable the start code. This is in case people want to opt out of the initialization when they don't depend on it. --- lib/std/crypto/tlcsprng.zig | 4 ++-- lib/std/start.zig | 38 ++++++++++++++++++++------------------ 2 files changed, 22 insertions(+), 20 deletions(-) diff --git a/lib/std/crypto/tlcsprng.zig b/lib/std/crypto/tlcsprng.zig index 0105cf0ce8..4e3036ecde 100644 --- a/lib/std/crypto/tlcsprng.zig +++ b/lib/std/crypto/tlcsprng.zig @@ -18,7 +18,7 @@ const mem = std.mem; pub var interface = std.rand.Random{ .fillFn = tlsCsprngFill }; pub threadlocal var csprng_state: std.crypto.core.Gimli = undefined; pub threadlocal var csprng_state_initialized = false; -fn tlsCsprngFill(r: *std.rand.Random, buf: []u8) void { +fn tlsCsprngFill(r: *const std.rand.Random, buf: []u8) void { if (std.builtin.link_libc and @hasDecl(std.c, "arc4random_buf")) { // arc4random is already a thread-local CSPRNG. return std.c.arc4random_buf(buf.ptr, buf.len); @@ -48,7 +48,7 @@ fn defaultSeed(buffer: *[seed_len]u8) void { std.os.getrandom(buffer) catch @panic("getrandom() failed to seed thread-local CSPRNG"); } -pub const seed_len = 32; +pub const seed_len = 16; pub fn init(seed: [seed_len]u8) void { var initial_state: [std.crypto.core.Gimli.BLOCKBYTES]u8 = undefined; diff --git a/lib/std/start.zig b/lib/std/start.zig index d3065c7719..25c578c0ef 100644 --- a/lib/std/start.zig +++ b/lib/std/start.zig @@ -206,7 +206,6 @@ fn posixCallMainAndExit() noreturn { // Do this as early as possible, the aux vector is needed if (builtin.position_independent_executable) { @import("os/linux/start_pie.zig").apply_relocations(); - @fence(.SeqCst); } // Initialize the TLS area. We do a runtime check here to make sure @@ -215,10 +214,9 @@ fn posixCallMainAndExit() noreturn { const is_dynamic = @import("dynamic_library.zig").get_DYNAMIC() != null; if (!is_dynamic) { std.os.linux.tls.initStaticTLS(); - @fence(.SeqCst); } - { + if (!@hasDecl(root, "use_AT_RANDOM_auxval") or root.use_AT_RANDOM_auxval) { // Initialize the per-thread CSPRNG since Linux gave us the handy-dandy // AT_RANDOM. This depends on the TLS initialization above. var i: usize = 0; @@ -226,19 +224,7 @@ fn posixCallMainAndExit() noreturn { switch (auxv[i].a_type) { std.elf.AT_RANDOM => { // "The address of sixteen bytes containing a random value." - const addr = auxv[i].a_un.a_val; - if (addr == 0) break; - const ptr = @intToPtr(*[16]u8, addr); - var seed: [32]u8 = undefined; - seed[0..16].* = ptr.*; - seed[16..].* = ptr.*; - tlcsprng.init(seed); - // Overwrite AT_RANDOM after we use it, otherwise our secure - // seed is sitting in memory ready for some other code in the - // program to reuse, and hence break our security. - // We play nice by refreshing it with fresh random bytes - // rather than clearing it. - std.crypto.random.bytes(ptr); + initCryptoSeedFromAuxVal(auxv[i].a_un.a_val); break; }, else => continue, @@ -281,15 +267,31 @@ fn callMainWithArgs(argc: usize, argv: [*][*:0]u8, envp: [][*:0]u8) u8 { } fn main(c_argc: i32, c_argv: [*][*:0]u8, c_envp: [*:null]?[*:0]u8) callconv(.C) i32 { - // We do not attempt to initialize tlcsprng from AT_RANDOM here because - // libc owns the start code, not us, and therefore libc ows the random bytes + // By default, we do not attempt to initialize tlcsprng from AT_RANDOM here because + // libc owns the start code, not us, and therefore libc owns the random bytes // from AT_RANDOM. + if (builtin.os.tag == .linux and + @hasDecl(root, "use_AT_RANDOM_auxval") and + root.use_AT_RANDOM_auxval) + { + initCryptoSeedFromAuxVal(std.c.getauxval(std.elf.AT_RANDOM)); + } var env_count: usize = 0; while (c_envp[env_count] != null) : (env_count += 1) {} const envp = @ptrCast([*][*:0]u8, c_envp)[0..env_count]; return @call(.{ .modifier = .always_inline }, callMainWithArgs, .{ @intCast(usize, c_argc), c_argv, envp }); } +fn initCryptoSeedFromAuxVal(addr: usize) void { + if (addr == 0) return; + const ptr = @intToPtr(*[16]u8, addr); + tlcsprng.init(ptr.*); + // Clear AT_RANDOM after we use it, otherwise our secure + // seed is sitting in memory ready for some other code in the + // program to reuse, and hence break our security. + std.crypto.utils.secureZero(u8, ptr); +} + // General error message for a malformed return type const bad_main_ret = "expected return type of main to be 'void', '!void', 'noreturn', 'u8', or '!u8'"; -- cgit v1.2.3 From d9368d70125abd70be380f7af38b75c152f307aa Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Thu, 17 Dec 2020 22:57:18 -0700 Subject: update test-stack-traces because start.zig updated --- test/stack_traces.zig | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/test/stack_traces.zig b/test/stack_traces.zig index 6aa972b13d..051b5b3489 100644 --- a/test/stack_traces.zig +++ b/test/stack_traces.zig @@ -282,10 +282,10 @@ pub fn addCases(cases: *tests.StackTracesContext) void { \\source.zig:10:8: [address] in main (test) \\ foo(); \\ ^ - \\start.zig:341:29: [address] in std.start.posixCallMainAndExit (test) + \\start.zig:377:29: [address] in std.start.posixCallMainAndExit (test) \\ return root.main(); \\ ^ - \\start.zig:162:5: [address] in std.start._start (test) + \\start.zig:163:5: [address] in std.start._start (test) \\ @call(.{ .modifier = .never_inline }, posixCallMainAndExit, .{}); \\ ^ \\ @@ -294,7 +294,7 @@ pub fn addCases(cases: *tests.StackTracesContext) void { switch (std.Target.current.cpu.arch) { .aarch64 => "", // TODO disabled; results in segfault else => - \\start.zig:162:5: [address] in std.start._start (test) + \\start.zig:163:5: [address] in std.start._start (test) \\ @call(.{ .modifier = .never_inline }, posixCallMainAndExit, .{}); \\ ^ \\ -- cgit v1.2.3 From 2b8dcc76eba92ad44bd88756218de8d2bd8a1c10 Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Fri, 18 Dec 2020 01:38:58 -0700 Subject: take advantage of std.os.linux.getauxval --- lib/std/start.zig | 13 ++----------- 1 file changed, 2 insertions(+), 11 deletions(-) diff --git a/lib/std/start.zig b/lib/std/start.zig index 25c578c0ef..8d5eda6105 100644 --- a/lib/std/start.zig +++ b/lib/std/start.zig @@ -219,17 +219,7 @@ fn posixCallMainAndExit() noreturn { if (!@hasDecl(root, "use_AT_RANDOM_auxval") or root.use_AT_RANDOM_auxval) { // Initialize the per-thread CSPRNG since Linux gave us the handy-dandy // AT_RANDOM. This depends on the TLS initialization above. - var i: usize = 0; - while (auxv[i].a_type != std.elf.AT_NULL) : (i += 1) { - switch (auxv[i].a_type) { - std.elf.AT_RANDOM => { - // "The address of sixteen bytes containing a random value." - initCryptoSeedFromAuxVal(auxv[i].a_un.a_val); - break; - }, - else => continue, - } - } + initCryptoSeedFromAuxVal(std.os.linux.getauxval(std.elf.AT_RANDOM)); } // TODO This is disabled because what should we do when linking libc and this code @@ -284,6 +274,7 @@ fn main(c_argc: i32, c_argv: [*][*:0]u8, c_envp: [*:null]?[*:0]u8) callconv(.C) fn initCryptoSeedFromAuxVal(addr: usize) void { if (addr == 0) return; + // "The address of sixteen bytes containing a random value." const ptr = @intToPtr(*[16]u8, addr); tlcsprng.init(ptr.*); // Clear AT_RANDOM after we use it, otherwise our secure -- cgit v1.2.3 From 53987c932c9d62cc9cdae3d523fb62756ce83ca9 Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Fri, 18 Dec 2020 15:38:38 -0700 Subject: std.crypto.random: introduce fork safety Everybody gets what they want! * AT_RANDOM is completely ignored. * On Linux, MADV_WIPEONFORK is used to provide fork safety. * On pthread systems, `pthread_atfork` is used to provide fork safety. * For systems that do not have the capability to provide fork safety, the implementation falls back to calling getrandom() every time. * If madvise is unavailable or returns an error, or pthread_atfork fails for whatever reason, it falls back to calling getrandom() every time. * Applications may choose to opt-out of fork safety. * Applications may choose to opt-in to unconditionally calling getrandom() for every call to std.crypto.random.fillFn. * Added `std.meta.globalOption`. * Added `std.os.madvise` and related bits. * Bumped up the size of the main thread TLS buffer. See the comment there for justification. * Simpler hot path in TLS initialization. --- lib/std/c.zig | 5 ++ lib/std/c/linux.zig | 6 ++ lib/std/crypto/tlcsprng.zig | 152 +++++++++++++++++++++++++++++++++++--------- lib/std/meta.zig | 8 +++ lib/std/os.zig | 48 ++++++++++++++ lib/std/os/bits/linux.zig | 22 +++++++ lib/std/os/linux.zig | 4 ++ lib/std/os/linux/tls.zig | 39 +++++++----- lib/std/start.zig | 26 -------- test/stack_traces.zig | 2 +- 10 files changed, 241 insertions(+), 71 deletions(-) diff --git a/lib/std/c.zig b/lib/std/c.zig index a8ac19053d..0c691daac7 100644 --- a/lib/std/c.zig +++ b/lib/std/c.zig @@ -264,6 +264,11 @@ pub extern "c" fn pthread_attr_setguardsize(attr: *pthread_attr_t, guardsize: us pub extern "c" fn pthread_attr_destroy(attr: *pthread_attr_t) c_int; pub extern "c" fn pthread_self() pthread_t; pub extern "c" fn pthread_join(thread: pthread_t, arg_return: ?*?*c_void) c_int; +pub extern "c" fn pthread_atfork( + prepare: ?fn () callconv(.C) void, + parent: ?fn () callconv(.C) void, + child: ?fn () callconv(.C) void, +) c_int; pub extern "c" fn kqueue() c_int; pub extern "c" fn kevent( diff --git a/lib/std/c/linux.zig b/lib/std/c/linux.zig index 21124d1030..97a25617ef 100644 --- a/lib/std/c/linux.zig +++ b/lib/std/c/linux.zig @@ -106,6 +106,12 @@ pub extern "c" fn prlimit(pid: pid_t, resource: rlimit_resource, new_limit: *con pub extern "c" fn posix_memalign(memptr: *?*c_void, alignment: usize, size: usize) c_int; pub extern "c" fn malloc_usable_size(?*const c_void) usize; +pub extern "c" fn madvise( + addr: *align(std.mem.page_size) c_void, + length: usize, + advice: c_uint, +) c_int; + pub const pthread_attr_t = extern struct { __size: [56]u8, __align: c_long, diff --git a/lib/std/crypto/tlcsprng.zig b/lib/std/crypto/tlcsprng.zig index 4e3036ecde..384216a81b 100644 --- a/lib/std/crypto/tlcsprng.zig +++ b/lib/std/crypto/tlcsprng.zig @@ -16,47 +16,141 @@ const mem = std.mem; /// We use this as a layer of indirection because global const pointers cannot /// point to thread-local variables. pub var interface = std.rand.Random{ .fillFn = tlsCsprngFill }; -pub threadlocal var csprng_state: std.crypto.core.Gimli = undefined; -pub threadlocal var csprng_state_initialized = false; -fn tlsCsprngFill(r: *const std.rand.Random, buf: []u8) void { + +const os_has_fork = switch (std.Target.current.os.tag) { + .dragonfly, + .freebsd, + .ios, + .kfreebsd, + .linux, + .macos, + .netbsd, + .openbsd, + .solaris, + .tvos, + .watchos, + => true, + + else => false, +}; +const os_has_arc4random = std.builtin.link_libc and @hasDecl(std.c, "arc4random_buf"); +const want_fork_safety = os_has_fork and !os_has_arc4random and + (std.meta.globalOption("crypto_fork_safety", bool) orelse true); +const maybe_have_wipe_on_fork = std.Target.current.os.isAtLeast(.linux, .{ + .major = 4, + .minor = 14, +}) orelse true; + +const WipeMe = struct { + init_state: enum { uninitialized, initialized, failed }, + gimli: std.crypto.core.Gimli, +}; +const wipe_align = if (maybe_have_wipe_on_fork) mem.page_size else @alignOf(WipeMe); + +threadlocal var wipe_me: WipeMe align(wipe_align) = .{ + .gimli = undefined, + .init_state = .uninitialized, +}; + +fn tlsCsprngFill(_: *const std.rand.Random, buffer: []u8) void { if (std.builtin.link_libc and @hasDecl(std.c, "arc4random_buf")) { // arc4random is already a thread-local CSPRNG. - return std.c.arc4random_buf(buf.ptr, buf.len); + return std.c.arc4random_buf(buffer.ptr, buffer.len); } - if (!csprng_state_initialized) { - var seed: [seed_len]u8 = undefined; - // Because we panic on getrandom() failing, we provide the opportunity - // to override the default seed function. This also makes - // `std.crypto.random` available on freestanding targets, provided that - // the `cryptoRandomSeed` function is provided. - if (@hasDecl(root, "cryptoRandomSeed")) { - root.cryptoRandomSeed(&seed); - } else { - defaultSeed(&seed); - } - init(seed); + // Allow applications to decide they would prefer to have every call to + // std.crypto.random always make an OS syscall, rather than rely on an + // application implementation of a CSPRNG. + if (comptime std.meta.globalOption("crypto_always_getrandom", bool) orelse false) { + return fillWithOsEntropy(buffer); } - if (buf.len != 0) { - csprng_state.squeeze(buf); + switch (wipe_me.init_state) { + .uninitialized => { + if (want_fork_safety) { + if (maybe_have_wipe_on_fork) { + if (std.os.madvise( + @ptrCast([*]align(mem.page_size) u8, &wipe_me), + @sizeOf(@TypeOf(wipe_me)), + std.os.MADV_WIPEONFORK, + )) |_| { + return initAndFill(buffer); + } else |_| if (std.Thread.use_pthreads) { + return setupPthreadAtforkAndFill(buffer); + } else { + // Since we failed to set up fork safety, we fall back to always + // calling getrandom every time. + wipe_me.init_state = .failed; + return fillWithOsEntropy(buffer); + } + } else if (std.Thread.use_pthreads) { + return setupPthreadAtforkAndFill(buffer); + } else { + // We have no mechanism to provide fork safety, but we want fork safety, + // so we fall back to calling getrandom every time. + wipe_me.init_state = .failed; + return fillWithOsEntropy(buffer); + } + } else { + return initAndFill(buffer); + } + }, + .initialized => { + return fillWithCsprng(buffer); + }, + .failed => { + if (want_fork_safety) { + return fillWithOsEntropy(buffer); + } else { + unreachable; + } + }, + } +} + +fn setupPthreadAtforkAndFill(buffer: []u8) void { + const failed = std.c.pthread_atfork(null, null, childAtForkHandler) != 0; + if (failed) { + wipe_me.init_state = .failed; + return fillWithOsEntropy(buffer); } else { - csprng_state.permute(); + return initAndFill(buffer); } - mem.set(u8, csprng_state.toSlice()[0..std.crypto.core.Gimli.RATE], 0); } -fn defaultSeed(buffer: *[seed_len]u8) void { - std.os.getrandom(buffer) catch @panic("getrandom() failed to seed thread-local CSPRNG"); +fn childAtForkHandler() callconv(.C) void { + const wipe_slice = @ptrCast([*]u8, &wipe_me)[0..@sizeOf(@TypeOf(wipe_me))]; + std.crypto.utils.secureZero(u8, wipe_slice); } -pub const seed_len = 16; +fn fillWithCsprng(buffer: []u8) void { + if (buffer.len != 0) { + wipe_me.gimli.squeeze(buffer); + } else { + wipe_me.gimli.permute(); + } + mem.set(u8, wipe_me.gimli.toSlice()[0..std.crypto.core.Gimli.RATE], 0); +} + +fn fillWithOsEntropy(buffer: []u8) void { + std.os.getrandom(buffer) catch @panic("getrandom() failed to provide entropy"); +} -pub fn init(seed: [seed_len]u8) void { - var initial_state: [std.crypto.core.Gimli.BLOCKBYTES]u8 = undefined; - mem.copy(u8, initial_state[0..seed_len], &seed); - mem.set(u8, initial_state[seed_len..], 0); - csprng_state = std.crypto.core.Gimli.init(initial_state); +fn initAndFill(buffer: []u8) void { + var seed: [std.crypto.core.Gimli.BLOCKBYTES]u8 = undefined; + // Because we panic on getrandom() failing, we provide the opportunity + // to override the default seed function. This also makes + // `std.crypto.random` available on freestanding targets, provided that + // the `cryptoRandomSeed` function is provided. + if (@hasDecl(root, "cryptoRandomSeed")) { + root.cryptoRandomSeed(&seed); + } else { + fillWithOsEntropy(&seed); + } + + wipe_me.gimli = std.crypto.core.Gimli.init(seed); // This is at the end so that accidental recursive dependencies result // in stack overflows instead of invalid random data. - csprng_state_initialized = true; + wipe_me.init_state = .initialized; + + return fillWithCsprng(buffer); } diff --git a/lib/std/meta.zig b/lib/std/meta.zig index 2cf7f6de81..d51a2744b3 100644 --- a/lib/std/meta.zig +++ b/lib/std/meta.zig @@ -9,6 +9,7 @@ const debug = std.debug; const mem = std.mem; const math = std.math; const testing = std.testing; +const root = @import("root"); pub const trait = @import("meta/trait.zig"); pub const TrailerFlags = @import("meta/trailer_flags.zig").TrailerFlags; @@ -1085,3 +1086,10 @@ test "Tuple" { TupleTester.assertTuple(.{ u32, f16 }, Tuple(&[_]type{ u32, f16 })); TupleTester.assertTuple(.{ u32, f16, []const u8, void }, Tuple(&[_]type{ u32, f16, []const u8, void })); } + +/// TODO: https://github.com/ziglang/zig/issues/425 +pub fn globalOption(comptime name: []const u8, comptime T: type) ?T { + if (!@hasDecl(root, name)) + return null; + return @as(T, @field(root, name)); +} diff --git a/lib/std/os.zig b/lib/std/os.zig index b42cdf756f..fb67b89d0a 100644 --- a/lib/std/os.zig +++ b/lib/std/os.zig @@ -5845,3 +5845,51 @@ pub fn setrlimit(resource: rlimit_resource, limits: rlimit) SetrlimitError!void else => |err| return unexpectedErrno(err), } } + +pub const MadviseError = error{ + /// advice is MADV_REMOVE, but the specified address range is not a shared writable mapping. + AccessDenied, + /// advice is MADV_HWPOISON, but the caller does not have the CAP_SYS_ADMIN capability. + PermissionDenied, + /// A kernel resource was temporarily unavailable. + SystemResources, + /// One of the following: + /// * addr is not page-aligned or length is negative + /// * advice is not valid + /// * advice is MADV_DONTNEED or MADV_REMOVE and the specified address range + /// includes locked, Huge TLB pages, or VM_PFNMAP pages. + /// * advice is MADV_MERGEABLE or MADV_UNMERGEABLE, but the kernel was not + /// configured with CONFIG_KSM. + /// * advice is MADV_FREE or MADV_WIPEONFORK but the specified address range + /// includes file, Huge TLB, MAP_SHARED, or VM_PFNMAP ranges. + InvalidSyscall, + /// (for MADV_WILLNEED) Paging in this area would exceed the process's + /// maximum resident set size. + WouldExceedMaximumResidentSetSize, + /// One of the following: + /// * (for MADV_WILLNEED) Not enough memory: paging in failed. + /// * Addresses in the specified range are not currently mapped, or + /// are outside the address space of the process. + OutOfMemory, + /// The madvise syscall is not available on this version and configuration + /// of the Linux kernel. + MadviseUnavailable, + /// The operating system returned an undocumented error code. + Unexpected, +}; + +/// Give advice about use of memory. +/// This syscall is optional and is sometimes configured to be disabled. +pub fn madvise(ptr: [*]align(mem.page_size) u8, length: usize, advice: u32) MadviseError!void { + switch (errno(system.madvise(ptr, length, advice))) { + 0 => return, + EACCES => return error.AccessDenied, + EAGAIN => return error.SystemResources, + EBADF => unreachable, // The map exists, but the area maps something that isn't a file. + EINVAL => return error.InvalidSyscall, + EIO => return error.WouldExceedMaximumResidentSetSize, + ENOMEM => return error.OutOfMemory, + ENOSYS => return error.MadviseUnavailable, + else => |err| return unexpectedErrno(err), + } +} diff --git a/lib/std/os/bits/linux.zig b/lib/std/os/bits/linux.zig index 583240fd4e..2bcfc89ecf 100644 --- a/lib/std/os/bits/linux.zig +++ b/lib/std/os/bits/linux.zig @@ -2045,3 +2045,25 @@ pub const rlimit = extern struct { /// Hard limit max: rlim_t, }; + +pub const MADV_NORMAL = 0; +pub const MADV_RANDOM = 1; +pub const MADV_SEQUENTIAL = 2; +pub const MADV_WILLNEED = 3; +pub const MADV_DONTNEED = 4; +pub const MADV_FREE = 8; +pub const MADV_REMOVE = 9; +pub const MADV_DONTFORK = 10; +pub const MADV_DOFORK = 11; +pub const MADV_MERGEABLE = 12; +pub const MADV_UNMERGEABLE = 13; +pub const MADV_HUGEPAGE = 14; +pub const MADV_NOHUGEPAGE = 15; +pub const MADV_DONTDUMP = 16; +pub const MADV_DODUMP = 17; +pub const MADV_WIPEONFORK = 18; +pub const MADV_KEEPONFORK = 19; +pub const MADV_COLD = 20; +pub const MADV_PAGEOUT = 21; +pub const MADV_HWPOISON = 100; +pub const MADV_SOFT_OFFLINE = 101; diff --git a/lib/std/os/linux.zig b/lib/std/os/linux.zig index f840f6a255..f252a08fc9 100644 --- a/lib/std/os/linux.zig +++ b/lib/std/os/linux.zig @@ -1351,6 +1351,10 @@ pub fn prlimit(pid: pid_t, resource: rlimit_resource, new_limit: ?*const rlimit, ); } +pub fn madvise(address: [*]u8, len: usize, advice: u32) usize { + return syscall3(.madvise, @ptrToInt(address), len, advice); +} + test "" { if (builtin.os.tag == .linux) { _ = @import("linux/test.zig"); diff --git a/lib/std/os/linux/tls.zig b/lib/std/os/linux/tls.zig index d956266114..6d61e60e95 100644 --- a/lib/std/os/linux/tls.zig +++ b/lib/std/os/linux/tls.zig @@ -327,34 +327,43 @@ pub fn prepareTLS(area: []u8) usize { if (tls_tp_points_past_tcb) tls_image.data_offset else tls_image.tcb_offset; } -var main_thread_tls_buffer: [256]u8 = undefined; +// The main motivation for the size chosen here is this is how much ends up being +// requested for the thread local variables of the std.crypto.random implementation. +// I'm not sure why it ends up being so much; the struct itself is only 64 bytes. +// I think it has to do with being page aligned and LLVM or LLD is not smart enough +// to lay out the TLS data in a space conserving way. Anyway I think it's fine +// because it's less than 3 pages of memory, and putting it in the ELF like this +// is equivalent to moving the mmap call below into the kernel, avoiding syscall +// overhead. +var main_thread_tls_buffer: [0x2100]u8 align(mem.page_size) = undefined; pub fn initStaticTLS() void { initTLS(); - const alloc_tls_area: []u8 = blk: { - const full_alloc_size = tls_image.alloc_size + tls_image.alloc_align - 1; - + const tls_area = blk: { // Fast path for the common case where the TLS data is really small, - // avoid an allocation and use our local buffer - if (full_alloc_size < main_thread_tls_buffer.len) - break :blk main_thread_tls_buffer[0..]; + // avoid an allocation and use our local buffer. + if (tls_image.alloc_align <= mem.page_size and + tls_image.alloc_size <= main_thread_tls_buffer.len) + { + break :blk main_thread_tls_buffer[0..tls_image.alloc_size]; + } - break :blk os.mmap( + const alloc_tls_area = os.mmap( null, - full_alloc_size, + tls_image.alloc_size + tls_image.alloc_align - 1, os.PROT_READ | os.PROT_WRITE, os.MAP_PRIVATE | os.MAP_ANONYMOUS, -1, 0, ) catch os.abort(); - }; - // Make sure the slice is correctly aligned - const begin_addr = @ptrToInt(alloc_tls_area.ptr); - const begin_aligned_addr = mem.alignForward(begin_addr, tls_image.alloc_align); - const start = begin_aligned_addr - begin_addr; - const tls_area = alloc_tls_area[start .. start + tls_image.alloc_size]; + // Make sure the slice is correctly aligned. + const begin_addr = @ptrToInt(alloc_tls_area.ptr); + const begin_aligned_addr = mem.alignForward(begin_addr, tls_image.alloc_align); + const start = begin_aligned_addr - begin_addr; + break :blk alloc_tls_area[start .. start + tls_image.alloc_size]; + }; const tp_value = prepareTLS(tls_area); setThreadPointer(tp_value); diff --git a/lib/std/start.zig b/lib/std/start.zig index 8d5eda6105..01fe43ca35 100644 --- a/lib/std/start.zig +++ b/lib/std/start.zig @@ -216,12 +216,6 @@ fn posixCallMainAndExit() noreturn { std.os.linux.tls.initStaticTLS(); } - if (!@hasDecl(root, "use_AT_RANDOM_auxval") or root.use_AT_RANDOM_auxval) { - // Initialize the per-thread CSPRNG since Linux gave us the handy-dandy - // AT_RANDOM. This depends on the TLS initialization above. - initCryptoSeedFromAuxVal(std.os.linux.getauxval(std.elf.AT_RANDOM)); - } - // TODO This is disabled because what should we do when linking libc and this code // does not execute? And also it's causing a test failure in stack traces in release modes. @@ -257,32 +251,12 @@ fn callMainWithArgs(argc: usize, argv: [*][*:0]u8, envp: [][*:0]u8) u8 { } fn main(c_argc: i32, c_argv: [*][*:0]u8, c_envp: [*:null]?[*:0]u8) callconv(.C) i32 { - // By default, we do not attempt to initialize tlcsprng from AT_RANDOM here because - // libc owns the start code, not us, and therefore libc owns the random bytes - // from AT_RANDOM. - if (builtin.os.tag == .linux and - @hasDecl(root, "use_AT_RANDOM_auxval") and - root.use_AT_RANDOM_auxval) - { - initCryptoSeedFromAuxVal(std.c.getauxval(std.elf.AT_RANDOM)); - } var env_count: usize = 0; while (c_envp[env_count] != null) : (env_count += 1) {} const envp = @ptrCast([*][*:0]u8, c_envp)[0..env_count]; return @call(.{ .modifier = .always_inline }, callMainWithArgs, .{ @intCast(usize, c_argc), c_argv, envp }); } -fn initCryptoSeedFromAuxVal(addr: usize) void { - if (addr == 0) return; - // "The address of sixteen bytes containing a random value." - const ptr = @intToPtr(*[16]u8, addr); - tlcsprng.init(ptr.*); - // Clear AT_RANDOM after we use it, otherwise our secure - // seed is sitting in memory ready for some other code in the - // program to reuse, and hence break our security. - std.crypto.utils.secureZero(u8, ptr); -} - // General error message for a malformed return type const bad_main_ret = "expected return type of main to be 'void', '!void', 'noreturn', 'u8', or '!u8'"; diff --git a/test/stack_traces.zig b/test/stack_traces.zig index 051b5b3489..d9c900ebae 100644 --- a/test/stack_traces.zig +++ b/test/stack_traces.zig @@ -282,7 +282,7 @@ pub fn addCases(cases: *tests.StackTracesContext) void { \\source.zig:10:8: [address] in main (test) \\ foo(); \\ ^ - \\start.zig:377:29: [address] in std.start.posixCallMainAndExit (test) + \\start.zig:342:29: [address] in std.start.posixCallMainAndExit (test) \\ return root.main(); \\ ^ \\start.zig:163:5: [address] in std.start._start (test) -- cgit v1.2.3 From f416535768fc30195cad6cd481f73fd1e80082aa Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Fri, 18 Dec 2020 18:30:06 -0700 Subject: work around compiler bug regarding generic function slice alignment See #7495 --- lib/std/crypto/tlcsprng.zig | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/lib/std/crypto/tlcsprng.zig b/lib/std/crypto/tlcsprng.zig index 384216a81b..ee71d6f13e 100644 --- a/lib/std/crypto/tlcsprng.zig +++ b/lib/std/crypto/tlcsprng.zig @@ -117,7 +117,9 @@ fn setupPthreadAtforkAndFill(buffer: []u8) void { } fn childAtForkHandler() callconv(.C) void { - const wipe_slice = @ptrCast([*]u8, &wipe_me)[0..@sizeOf(@TypeOf(wipe_me))]; + // TODO this is a workaround for https://github.com/ziglang/zig/issues/7495 + var wipe_slice: []u8 = undefined; + wipe_slice = @ptrCast([*]u8, &wipe_me)[0..@sizeOf(@TypeOf(wipe_me))]; std.crypto.utils.secureZero(u8, wipe_slice); } -- cgit v1.2.3