https://github.com/project-everest/hacl-star
Tip revision: f95b54abf9076a7a072a54750b40dc9f85039b74 authored by Dzomo, the Everest Yak on 01 October 2021, 08:30:56 UTC
[CI] regenerate hints and dist
[CI] regenerate hints and dist
Tip revision: f95b54a
Hacl.Hash.MD.fst
module Hacl.Hash.MD
(** The Merkle-Damgård construction. *)
module U8 = FStar.UInt8
module U32 = FStar.UInt32
module U64 = FStar.UInt64
module U128 = FStar.UInt128
module Int = Lib.IntTypes
module Lemmas = FStar.Math.Lemmas
module B = LowStar.Buffer
module S = FStar.Seq
module HS = FStar.HyperStack
module ST = FStar.HyperStack.ST
open Hacl.Hash.Definitions
open Hacl.Hash.Lemmas
open Spec.Hash.Definitions
open FStar.Mul
module HI = Spec.Hash.Incremental
module AH = Spec.Agile.Hash
(** Auxiliary helpers *)
#set-options "--max_fuel 0 --max_ifuel 0 --z3rlimit 100"
let padding_round (a: hash_alg) (len: len_t a): Lemma
((len_v a len + pad_length a (len_v a len)) % block_length a = 0)
=
()
private
val mod_sub_add: a:int -> b:int -> c:int -> d:int -> p:pos -> Lemma
(requires b % p = 0)
(ensures (a - ((b + c) + d)) % p == (a - (c + d)) % p)
let mod_sub_add a b c d p =
calc (==) {
(a - ((b + c) + d)) % p;
== { Math.Lemmas.lemma_mod_sub_distr a ((b + c) + d) p }
(a - ((b + c) + d) % p) % p;
== { Math.Lemmas.lemma_mod_plus_distr_l (b + c) d p }
(a - ((b + c) % p + d) % p) % p;
== { Math.Lemmas.lemma_mod_plus_distr_l b c p }
(a - ((b % p + c) % p + d) % p) % p;
== { }
(a - (c % p + d) % p) % p;
== { Math.Lemmas.lemma_mod_plus_distr_l c d p }
(a - (c + d) % p) % p;
== { Math.Lemmas.lemma_mod_sub_distr a (c + d) p }
(a - (c + d)) % p;
}
let pad0_length_mod (a: hash_alg{is_md a}) (base_len: nat) (len: nat): Lemma
(requires base_len % block_length a = 0)
(ensures pad0_length a (base_len + len) = pad0_length a len)
=
mod_sub_add (block_length a) base_len len (len_length a + 1) (block_length a)
let pad_length_mod (a: hash_alg{is_md a}) (base_len len: nat): Lemma
(requires base_len % block_length a = 0)
(ensures pad_length a (base_len + len) = pad_length a len)
= pad0_length_mod a base_len len
val pad_len_bound :
a : hash_alg ->
prev_len:len_t a { len_v a prev_len % block_length a = 0 } ->
input_len:U32.t { U32.v input_len + len_v a prev_len <= max_input_length a} ->
Lemma(
(U32.v input_len % block_length a) +
pad_length a (len_v a prev_len + U32.v input_len) <= 2 * block_length a)
let pad_len_bound a prev_len input_len = ()
(* Avoiding an ill-formed pattern error... *)
noextract inline_for_extraction
let len_add32 (a: hash_alg{is_md a})
(prev_len: len_t a)
(input_len: U32.t { U32.v input_len + len_v a prev_len <= max_input_length a }):
x:len_t a { len_v a x = len_v a prev_len + U32.v input_len }
=
let open FStar.Int.Cast.Full in
match a with
| SHA2_224 | SHA2_256 | MD5 | SHA1 ->
assert_norm (pow2 61 < pow2 64);
U64.(prev_len +^ uint32_to_uint64 input_len)
| SHA2_384 | SHA2_512 ->
assert_norm (pow2 125 < pow2 128);
U128.(prev_len +^ uint64_to_uint128 (uint32_to_uint64 input_len))
#push-options "--max_fuel 1 --ifuel 1 --z3rlimit 128"
(** Iterated compression function. *)
noextract inline_for_extraction
let mk_update_multi a update s ev blocks n_blocks =
let h0 = ST.get () in
let inv (h: HS.mem) (i: nat) =
let i_block = block_length a * i in
i <= U32.v n_blocks /\
B.live h s /\ B.live h blocks /\
B.(modifies (loc_buffer s) h0 h) /\
(as_seq h s, ev) ==
(Spec.Agile.Hash.update_multi a (as_seq h0 s, ev) (S.slice (B.as_seq h0 blocks) 0 i_block))
in
let f (i:U32.t { U32.(0 <= v i /\ v i < v n_blocks)}): ST.Stack unit
(requires (fun h -> inv h (U32.v i)))
(ensures (fun h0 _ h1 -> inv h0 (U32.v i) /\ inv h1 (U32.v i + 1)))
=
let h1 = ST.get () in
let sz = block_len a in
let blocks0 = B.sub blocks 0ul U32.(sz *^ i) in
let block = B.sub blocks U32.(sz *^ i) sz in
update s ev block;
(**) Spec.Hash.Lemmas.update_multi_update a (as_seq h1 s, ev) (B.as_seq h0 block);
(**) let h2 = ST.get () in
(**) let blocks_v : Ghost.erased _ = B.as_seq h0 blocks in
(**) let block_v : Ghost.erased _ = B.as_seq h0 block in
(**) let blocks0_v : Ghost.erased _ = B.as_seq h0 blocks0 in
assert (
let s1 = B.as_seq h1 s in
let s2 = B.as_seq h2 s in
let i = U32.v i in
let n_blocks = U32.v n_blocks in
block_length a * (i + 1) <= S.length blocks_v /\
(block_length a * (i + 1) - block_length a * i) % block_length a = 0 /\
S.equal block_v (S.slice blocks_v (block_length a * i) (block_length a * (i + 1))) /\
S.equal s2 (fst (Spec.Agile.Hash.update_multi a (s1, ()) block_v))
);
(**) let i_block : Ghost.erased _ = block_length a * (U32.v i) in
(**) Spec.Hash.Lemmas.update_multi_associative a (as_seq h0 s, ev)
(S.slice blocks_v 0 i_block)
block_v
in
assert (B.length blocks = U32.v n_blocks * block_length a);
C.Loops.for 0ul n_blocks inv f;
ev
#pop-options
#push-options "--fuel 0 --ifuel 1 --z3rlimit 400 --z3cliopt smt.arith.nl=false"
(** An arbitrary number of bytes, then padding. *)
noextract inline_for_extraction
let mk_update_last a update_multi =
assert_norm(block_length a > 0);
fun pad s ev prev_len input input_len ->
assert (extra_state a == unit);
ST.push_frame ();
let h0 = ST.get () in
(* Get a series of complete blocks. *)
let blocks_n = U32.(input_len /^ block_len a) in
Math.Lemmas.nat_times_nat_is_nat (UInt32.v blocks_n) (block_length a);
Math.Lemmas.euclidean_division_definition (U32.v input_len) (block_length a);
let blocks_len = U32.(blocks_n *^ block_len a) in
Math.Lemmas.cancel_mul_mod (U32.v blocks_n) (block_length a);
assert (U32.v blocks_len % block_length a = 0);
let blocks = B.sub input 0ul blocks_len in
(* The rest that doesn't make up a complete block *)
let rest_len = U32.(input_len -^ blocks_len) in
assert (U32.v rest_len < block_length a);
let rest = B.sub input blocks_len rest_len in
assert(B.length blocks = U32.v blocks_len);
assert(block_length a * U32.v blocks_n = U32.v blocks_n * block_length a);
update_multi s () blocks blocks_n;
let h1 = ST.get () in
assert (S.equal (B.as_seq h0 input) (S.append (B.as_seq h1 blocks) (B.as_seq h1 rest)));
assert (S.equal (B.as_seq h1 s) (fst (Spec.Agile.Hash.update_multi a (B.as_seq h0 s, ()) (B.as_seq h0 blocks))));
(* Compute the total number of bytes fed. *)
let total_input_len: len_t a = len_add32 a prev_len input_len in
(* Blit the remaining data and the padding together *)
let pad_len = Hacl.Hash.PadFinish.pad_len a total_input_len in
let tmp_len = U32.( rest_len +^ pad_len ) in
assert (len_v a total_input_len = len_v a prev_len + U32.v blocks_len + U32.v rest_len);
Lemmas.modulo_distributivity (len_v a prev_len) (U32.v blocks_len) (block_length a);
Math.Lemmas.lemma_mod_plus_distr_r (len_v a prev_len) (U32.v blocks_len) (block_length a);
assert ((len_v a prev_len + U32.v blocks_len) % block_length a = 0);
pad_length_mod a (len_v a prev_len + U32.v blocks_len) (U32.v rest_len);
padding_round a total_input_len;
assert(FStar.UInt32.v tmp_len % Spec.Hash.Definitions.block_length a = 0);
assert (U32.v tmp_len % block_length a = 0);
pad_len_bound a prev_len input_len;
assert (U32.v tmp_len <= 2 * block_length a);
let tmp_twoblocks = B.alloca (Lib.IntTypes.u8 0) U32.(2ul *^ block_len a) in
let tmp = B.sub tmp_twoblocks 0ul tmp_len in
let tmp_rest = B.sub tmp 0ul rest_len in
let tmp_pad = B.sub tmp rest_len pad_len in
B.blit rest 0ul tmp_rest 0ul rest_len;
pad total_input_len tmp_pad;
let h2 = ST.get () in
assert (S.equal (B.as_seq h2 tmp) (S.append (B.as_seq h2 tmp_rest) (B.as_seq h2 tmp_pad)));
assert (S.equal (B.as_seq h2 tmp_rest) (B.as_seq h1 rest));
assert (S.equal (B.as_seq h2 tmp_pad) (Spec.Hash.PadFinish.pad a (len_v a total_input_len)));
(* Update multi those last few blocks *)
Math.Lemmas.cancel_mul_mod (U32.v tmp_len) (block_length a);
Math.Lemmas.euclidean_division_definition (U32.v tmp_len) (block_length a);
Math.Lemmas.swap_mul (block_length a) (U32.v U32.(tmp_len /^ block_len a));
assert(B.length tmp = block_length a * U32.v U32.(tmp_len /^ block_len a));
update_multi s () tmp U32.(tmp_len /^ block_len a);
let h3 = ST.get () in
assert (S.equal (B.as_seq h3 s)
(fst (Spec.Agile.Hash.update_multi a (Spec.Agile.Hash.update_multi a (B.as_seq h0 s, ()) (B.as_seq h1 blocks))
(S.append (B.as_seq h1 rest) (Spec.Hash.PadFinish.pad a (len_v a total_input_len))))));
assert (
let s1 = B.as_seq h1 blocks in
let s2 = B.as_seq h2 rest in
let s3 = Spec.Hash.PadFinish.pad a (len_v a total_input_len) in
S.equal (S.append s1 (S.append s2 s3)) (S.append (S.append s1 s2) s3));
ST.pop_frame ()
#pop-options
#push-options "--ifuel 1"
noextract inline_for_extraction
let u32_to_len (a: hash_alg{is_md a}) (l: U32.t): l':len_t a { len_v a l' = U32.v l } =
match a with
| SHA2_384 | SHA2_512 ->
FStar.Int.Cast.Full.(uint64_to_uint128 (uint32_to_uint64 l))
| _ -> FStar.Int.Cast.Full.uint32_to_uint64 l
#pop-options
(** split blocks: utility for the complete hash *)
noextract inline_for_extraction
val split_blocks (a : hash_alg) (input:B.buffer Int.uint8)
(input_len : Int.size_t { B.length input = U32.v input_len }) :
ST.Stack (Int.size_t & Int.size_t & B.buffer Int.uint8 & Int.size_t & B.buffer Int.uint8)
(requires fun h -> B.live h input /\ B.length input <= max_input_length a)
(ensures fun h0 (blocks_n, blocks_len, blocks, rest_len, rest) h1 ->
h0 == h1 /\
U32.v blocks_len + U32.v rest_len == U32.v input_len /\
B.length blocks == U32.v blocks_len /\ B.length rest == U32.v rest_len /\
B.as_seq h0 input `S.equal` S.append (B.as_seq h0 blocks) (B.as_seq h0 rest) /\
blocks == Ghost.reveal(B.gsub input 0ul blocks_len) /\
rest == B.gsub input blocks_len rest_len /\
(B.as_seq h0 blocks, B.as_seq h0 rest) ==
Spec.Hash.Incremental.split_blocks a (B.as_seq h0 input) /\
U32.v blocks_len == U32.v blocks_n * block_length a)
#push-options "--ifuel 1"
let split_blocks a input input_len =
let blocks_n = U32.(input_len /^ block_len a) in
let blocks_n = if U32.(input_len %^ block_len a =^ uint_to_t 0) && U32.(blocks_n >^ uint_to_t 0)
then U32.(blocks_n -^ uint_to_t 1) else blocks_n in
let blocks_len = U32.(blocks_n *^ block_len a) in
let blocks = B.sub input 0ul blocks_len in
let rest_len = U32.(input_len -^ blocks_len) in
let rest = B.sub input blocks_len rest_len in
(blocks_n, blocks_len, blocks, rest_len, rest)
#pop-options
(** Complete hash. *)
noextract inline_for_extraction
let mk_hash a alloca update_multi update_last finish input input_len dst =
(**) assert (extra_state a == unit);
(**) let h0 = ST.get () in
ST.push_frame ();
let s, _ = alloca () in
let (blocks_n, blocks_len, blocks, rest_len, rest) = split_blocks a input input_len in
(**) let blocks_v0 : Ghost.erased _ = B.as_seq h0 blocks in
(**) let rest_v0 : Ghost.erased _ = B.as_seq h0 rest in
(**) let input_v0 : Ghost.erased _ = B.as_seq h0 input in
(**) assert(input_v0 `S.equal` S.append blocks_v0 rest_v0);
update_multi s () blocks blocks_n;
update_last s () (u32_to_len a blocks_len) rest rest_len;
finish s () dst;
(**) let h1 = ST.get () in
(**) assert((as_seq h1 s, ()) ==
Spec.Hash.Incremental.update_last a
(Spec.Agile.Hash.(update_multi a (init a) blocks_v0)) (U32.v blocks_len) rest_v0);
(**) assert((as_seq h1 s, ()) ==
Spec.Hash.Incremental.hash_incremental_body a input_v0 (Spec.Agile.Hash.init a));
(**) assert(
B.as_seq h1 dst `S.equal`
Spec.Hash.PadFinish.finish a (
Spec.Hash.Incremental.hash_incremental_body a input_v0 (Spec.Agile.Hash.init a)));
(**) assert(B.as_seq h1 dst `S.equal` Spec.Hash.Incremental.hash_incremental a input_v0);
(**) Spec.Hash.Incremental.hash_is_hash_incremental a input_v0;
ST.pop_frame ()