From 1bfa87ee64dba7085b2d4182c5be6d6cfb7019fd Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Rapha=C3=ABl=20Proust?= Date: Tue, 21 Jan 2020 12:36:29 -0300 Subject: [PATCH 1/6] Crypto: offer seeded hash alternatives to normal hashes --- src/lib_crypto/blake2B.ml | 23 ++++++++++++++++++----- src/lib_crypto/chain_id.ml | 7 +++++++ src/lib_crypto/helpers.ml | 10 ++++++++-- src/lib_crypto/s.ml | 4 +++- src/lib_crypto/signature.ml | 4 ++++ src/lib_requester/requester.ml | 2 +- src/lib_requester/requester.mli | 2 +- src/lib_shell/distributed_db_requester.ml | 4 ++-- 8 files changed, 44 insertions(+), 12 deletions(-) diff --git a/src/lib_crypto/blake2B.ml b/src/lib_crypto/blake2B.ml index 3c7f160c7a20..8c60b2560b52 100644 --- a/src/lib_crypto/blake2B.ml +++ b/src/lib_crypto/blake2B.ml @@ -188,12 +188,21 @@ struct let open Data_encoding in conv to_bytes of_bytes_exn (Fixed.bytes size) - let hash = - if Compare.Int.(size >= 8) then fun h -> + let seeded_hash = + let open Compare.Int + (* shadowing comparators *) in + if size > 8 then fun seed h -> + Int64.to_int (TzEndian.get_int64 (to_bytes h) (seed mod (size - 8))) + else if size = 8 && Sys.word_size = 64 then fun _seed h -> + (* NOTE: we do not use the seed here because we have a _perfect_ hash: we + get the whole value. (Technically we ignore one bit because of the + conversion from Int64 to int. *) Int64.to_int (TzEndian.get_int64 (to_bytes h) 0) - else if Compare.Int.(size >= 4) then fun h -> - Int32.to_int (TzEndian.get_int32 (to_bytes h) 0) - else fun h -> + else if size > 4 then fun seed h -> + Int32.to_int (TzEndian.get_int32 (to_bytes h) (seed mod (size - 4))) + else fun _seed h -> + (* Here again we have a perfect hash. (Technically again we ignore one bit + on 32-bit machines if size = 4.) *) let r = ref 0 in let h = to_bytes h in for i = 0 to size - 1 do @@ -201,6 +210,8 @@ struct done ; !r + let hash = seeded_hash 0 + type Base58.data += Data of t let b58check_encoding = @@ -227,6 +238,8 @@ struct let equal = equal let hash = hash + + let seeded_hash = seeded_hash end) end diff --git a/src/lib_crypto/chain_id.ml b/src/lib_crypto/chain_id.ml index d9034470fbe6..57b175ca8560 100644 --- a/src/lib_crypto/chain_id.ml +++ b/src/lib_crypto/chain_id.ml @@ -131,8 +131,13 @@ let raw_encoding = let open Data_encoding in conv to_bytes of_bytes_exn (Fixed.bytes size) +(* NOTE: we ignore hashing because identity is a perfect hash. (Technically we + ignore one bit on 32-bit machines because of the conversion from Int32 to + int.) *) let hash h = Int32.to_int (TzEndian.get_int32 (to_bytes h) 0) +let seeded_hash _seed h = hash h + let of_block_hash bh = hash_bytes [Block_hash.to_bytes bh] include Compare.Make (struct @@ -157,4 +162,6 @@ include Helpers.Make (struct let equal = equal let hash = hash + + let seeded_hash = seeded_hash end) diff --git a/src/lib_crypto/helpers.ml b/src/lib_crypto/helpers.ml index 7cff72157550..e1be57168f1d 100644 --- a/src/lib_crypto/helpers.ml +++ b/src/lib_crypto/helpers.ml @@ -191,6 +191,10 @@ module MakeIterator (H : sig val equal : t -> t -> bool val hash : t -> int + + (* [seeded_hash] is a seeded alternative to [hash] meant to be used to create + seeded hashtables. Check {!Stdlib.Hashtbl.MakeSeeded} for details. *) + val seeded_hash : int -> t -> int end) = struct module Set = struct @@ -224,10 +228,10 @@ struct end module Table = struct - include Hashtbl.Make (struct + include Hashtbl.MakeSeeded (struct type t = H.t - let hash = H.hash + let hash = H.seeded_hash let equal = H.equal end) @@ -295,6 +299,8 @@ module Make (H : sig val equal : t -> t -> bool val hash : t -> int + + val seeded_hash : int -> t -> int end) = struct include MakeB58 (H) diff --git a/src/lib_crypto/s.ml b/src/lib_crypto/s.ml index 2a43d4d74d1a..d4a0ea38b472 100644 --- a/src/lib_crypto/s.ml +++ b/src/lib_crypto/s.ml @@ -138,6 +138,8 @@ module type INDEXES = sig val hash : t -> int + val seeded_hash : int -> t -> int + val to_path : t -> string list -> string list val of_path : string list -> t option @@ -163,7 +165,7 @@ module type INDEXES = sig end module Table : sig - include Hashtbl.S with type key = t + include Hashtbl.SeededS with type key = t val encoding : 'a Data_encoding.t -> 'a t Data_encoding.t end diff --git a/src/lib_crypto/signature.ml b/src/lib_crypto/signature.ml index 54099d8b4873..06d096aa77e6 100644 --- a/src/lib_crypto/signature.ml +++ b/src/lib_crypto/signature.ml @@ -210,6 +210,8 @@ module Public_key_hash = struct let prefix_path _ = assert false (* unused *) + let seeded_hash = Hashtbl.seeded_hash + let hash = Hashtbl.hash include Compare.Make (struct @@ -252,6 +254,8 @@ module Public_key_hash = struct let hash = hash + let seeded_hash = seeded_hash + let compare = compare let equal = equal diff --git a/src/lib_requester/requester.ml b/src/lib_requester/requester.ml index f3eefe382fa5..f4e1d89c07f1 100644 --- a/src/lib_requester/requester.ml +++ b/src/lib_requester/requester.ml @@ -104,7 +104,7 @@ module type MEMORY_TABLE = sig type key - val create : int -> 'a t + val create : ?random:bool -> int -> 'a t val find : 'a t -> key -> 'a option diff --git a/src/lib_requester/requester.mli b/src/lib_requester/requester.mli index cd142e1463f9..a7e31d7dde31 100644 --- a/src/lib_requester/requester.mli +++ b/src/lib_requester/requester.mli @@ -189,7 +189,7 @@ module type MEMORY_TABLE = sig type key - val create : int -> 'a t + val create : ?random:bool -> int -> 'a t val find : 'a t -> key -> 'a option diff --git a/src/lib_shell/distributed_db_requester.ml b/src/lib_shell/distributed_db_requester.ml index 5f4f53cbcbd9..b016ecd61b62 100644 --- a/src/lib_shell/distributed_db_requester.ml +++ b/src/lib_shell/distributed_db_requester.ml @@ -199,10 +199,10 @@ module Raw_block_header = let precheck _ _ v = Some v end) -module Operations_table = Hashtbl.Make (struct +module Operations_table = Hashtbl.MakeSeeded (struct type t = Block_hash.t * int - let hash = Hashtbl.hash + let hash = Hashtbl.seeded_hash let equal (b1, i1) (b2, i2) = Block_hash.equal b1 b2 && i1 = i2 end) -- GitLab From d9e3bb89085f1b61a6552160e9e8f7321f2fa432 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Rapha=C3=ABl=20Proust?= Date: Tue, 25 Aug 2020 18:41:56 +0200 Subject: [PATCH 2/6] Everywhere: use randomised, seeded hash-tables --- src/lib_base/p2p_point.ml | 11 ++++++++--- src/lib_base/p2p_point.mli | 2 +- src/lib_client_base/client_confirmations.ml | 2 +- src/lib_p2p/p2p_acl.ml | 2 +- src/lib_p2p/p2p_connect_handler.ml | 2 +- src/lib_p2p/p2p_pool.ml | 10 +++++----- src/lib_requester/requester.ml | 7 ++++--- src/lib_requester/requester.mli | 12 +++++++++--- src/lib_requester/test/test_requester.ml | 4 ++-- src/lib_shell/distributed_db.ml | 6 +++--- src/lib_shell/distributed_db_requester.ml | 4 ++-- 11 files changed, 37 insertions(+), 25 deletions(-) diff --git a/src/lib_base/p2p_point.ml b/src/lib_base/p2p_point.ml index 3363d01587aa..e4ae04175a4b 100644 --- a/src/lib_base/p2p_point.ml +++ b/src/lib_base/p2p_point.ml @@ -33,8 +33,6 @@ module Id = struct let equal p1 p2 = compare p1 p2 = 0 - let hash = Hashtbl.hash - let pp ppf (addr, port) = match Ipaddr.v4_of_v6 addr with | Some addr -> @@ -140,7 +138,14 @@ end module Map = Map.Make (Id) module Set = Set.Make (Id) -module Table = Hashtbl.Make (Id) + +module Table = Hashtbl.MakeSeeded (struct + type t = Id.t + + let equal = Id.equal + + let hash = Hashtbl.seeded_hash +end) module Filter = struct type t = Requested | Accepted | Running | Disconnected diff --git a/src/lib_base/p2p_point.mli b/src/lib_base/p2p_point.mli index dab4a169b8bf..9bd0d4afc3b1 100644 --- a/src/lib_base/p2p_point.mli +++ b/src/lib_base/p2p_point.mli @@ -58,7 +58,7 @@ module Map : Map.S with type key = Id.t module Set : Set.S with type elt = Id.t -module Table : Hashtbl.S with type key = Id.t +module Table : Hashtbl.SeededS with type key = Id.t module Filter : sig type t = Requested | Accepted | Running | Disconnected diff --git a/src/lib_client_base/client_confirmations.ml b/src/lib_client_base/client_confirmations.ml index 8b29fb42c467..0c25f0f8e0eb 100644 --- a/src/lib_client_base/client_confirmations.ml +++ b/src/lib_client_base/client_confirmations.ml @@ -51,7 +51,7 @@ let wait_for_operation_inclusion (ctxt : #Client_context.full) ~chain if the `hash` contains the operation in list `i` at position `j` and if `hash` denotes the `n-th` predecessors of the block. *) let blocks : ((Block_hash.t * int * int) * int) option Block_hash.Table.t = - Block_hash.Table.create confirmations + Block_hash.Table.create ~random:true confirmations in (* Fetch _all_ the 'unknown' predecessors af a block. *) let fetch_predecessors (hash, header) = diff --git a/src/lib_p2p/p2p_acl.ml b/src/lib_p2p/p2p_acl.ml index 9bffe129861b..fccfe0be9de8 100644 --- a/src/lib_p2p/p2p_acl.ml +++ b/src/lib_p2p/p2p_acl.ml @@ -126,7 +126,7 @@ let create size = greylist_ips = IpSet.empty; greylist_peers = PeerFIFOCache.create size; banned_ips = IpTable.create 53; - banned_peers = P2p_peer.Table.create 53; + banned_peers = P2p_peer.Table.create ~random:true 53; } (* Check if an ip is banned. Priority is given to the static diff --git a/src/lib_p2p/p2p_connect_handler.ml b/src/lib_p2p/p2p_connect_handler.ml index bd18332078cb..f840db3fdb27 100644 --- a/src/lib_p2p/p2p_connect_handler.ml +++ b/src/lib_p2p/p2p_connect_handler.ml @@ -72,7 +72,7 @@ let create ?(p2p_versions = P2p_version.supported) config pool message_config message_config.P2p_params.distributed_db_versions ~p2p_versions; custom_p2p_versions = p2p_versions; - incoming = P2p_point.Table.create 53; + incoming = P2p_point.Table.create ~random:true 53; io_sched; encoding = P2p_message.encoding message_config.P2p_params.encoding; triggers; diff --git a/src/lib_p2p/p2p_pool.ml b/src/lib_p2p/p2p_pool.ml index 82f17702d973..a59bea6b938d 100644 --- a/src/lib_p2p/p2p_pool.ml +++ b/src/lib_p2p/p2p_pool.ml @@ -453,11 +453,11 @@ let create config peer_meta_config triggers ~log = { config; peer_meta_config; - my_id_points = P2p_point.Table.create 7; - known_peer_ids = P2p_peer.Table.create 53; - connected_peer_ids = P2p_peer.Table.create 53; - known_points = P2p_point.Table.create 53; - connected_points = P2p_point.Table.create 53; + my_id_points = P2p_point.Table.create ~random:true 7; + known_peer_ids = P2p_peer.Table.create ~random:true 53; + connected_peer_ids = P2p_peer.Table.create ~random:true 53; + known_points = P2p_point.Table.create ~random:true 53; + connected_points = P2p_point.Table.create ~random:true 53; triggers; acl = P2p_acl.create 1023; log; diff --git a/src/lib_requester/requester.ml b/src/lib_requester/requester.ml index f4e1d89c07f1..3635a004624e 100644 --- a/src/lib_requester/requester.ml +++ b/src/lib_requester/requester.ml @@ -77,6 +77,7 @@ module type FULL_REQUESTER = sig val pending_requests : t -> int val create : + ?random_table:bool -> ?global_input:(key * value) Lwt_watcher.input -> request_param -> store -> @@ -458,7 +459,7 @@ end = struct { param; queue = Lwt_pipe.create (); - pending = Table.create 17; + pending = Table.create ~random:true 17; events = Lwt.return_nil; canceler = Lwt_canceler.create (); worker = Lwt.return_unit; @@ -707,9 +708,9 @@ end = struct let watch s = Lwt_watcher.create_stream s.input - let create ?global_input request_param disk = + let create ?random_table:random ?global_input request_param disk = let scheduler = Scheduler.create request_param in - let memory = Memory_table.create 17 in + let memory = Memory_table.create ?random 17 in let input = Lwt_watcher.create_input () in {scheduler; disk; memory; input; global_input} diff --git a/src/lib_requester/requester.mli b/src/lib_requester/requester.mli index a7e31d7dde31..46203849145e 100644 --- a/src/lib_requester/requester.mli +++ b/src/lib_requester/requester.mli @@ -158,9 +158,15 @@ module type FULL_REQUESTER = sig (** Returns the number of requests currently pending *) val pending_requests : t -> int - (** [create ?global_input r s] creates a requester. [r] is the - configuration parameter passed to [Request] functions. *) + (** [create ?random_table ?global_input r s] creates a requester. [r] is the + configuration parameter passed to [Request] functions. + + The value for [random_table] determines whether the underlying hashtable + randomises its hash (see {!Stdlib.Hashtbl.create} and specifically the + documentation of the [random] parameter). The default depends on + environment variables and {!Stdlib.Hashtbl.randomize} has been called. *) val create : + ?random_table:bool -> ?global_input:(key * value) Lwt_watcher.input -> request_param -> store -> @@ -184,7 +190,7 @@ module type DISK_TABLE = sig end module type MEMORY_TABLE = sig - (** subtypes Hashtbl.S *) + (** subtypes {!Hashtbl.SeededS} *) type 'a t type key diff --git a/src/lib_requester/test/test_requester.ml b/src/lib_requester/test/test_requester.ml index e8ceab9fdd53..397ced0668e5 100644 --- a/src/lib_requester/test/test_requester.ml +++ b/src/lib_requester/test/test_requester.ml @@ -81,10 +81,10 @@ module Test_disk_table_hash = struct let read_opt st k = Lwt.return (find st k) end -module Test_memory_table = Hashtbl.Make (struct +module Test_memory_table = Hashtbl.MakeSeeded (struct type t = test_key - let hash = Hashtbl.hash + let hash = Hashtbl.seeded_hash let equal s1 s2 = s1 = s2 end) diff --git a/src/lib_shell/distributed_db.ml b/src/lib_shell/distributed_db.ml index 6962f8a6b185..d394539ba0d4 100644 --- a/src/lib_shell/distributed_db.ml +++ b/src/lib_shell/distributed_db.ml @@ -125,8 +125,8 @@ let create disk p2p = let protocol_db = Distributed_db_requester.Raw_protocol.create global_request disk in - let active_chains = Chain_id.Table.create 17 in - let p2p_readers = P2p_peer.Table.create 17 in + let active_chains = Chain_id.Table.create ~random:true 17 in + let p2p_readers = P2p_peer.Table.create ~random:true 17 in let block_input = Lwt_watcher.create_input () in let operation_input = Lwt_watcher.create_input () in let db = @@ -197,7 +197,7 @@ let activate operations_db; callback = noop_callback; active_peers; - active_connections = P2p_peer.Table.create 53; + active_connections = P2p_peer.Table.create ~random:true 53; } in let sends = diff --git a/src/lib_shell/distributed_db_requester.ml b/src/lib_shell/distributed_db_requester.ml index b016ecd61b62..3fe1c11b30ef 100644 --- a/src/lib_shell/distributed_db_requester.ml +++ b/src/lib_shell/distributed_db_requester.ml @@ -126,8 +126,8 @@ end) scheduler_length; } - let create ?global_input request_param disk = - Table.create ?global_input request_param disk + let create ?random_table ?global_input request_param disk = + Table.create ?random_table ?global_input request_param disk let shutdown t = Requester_event.(emit shutting_down_requester) () -- GitLab From c034cb59c025d3a169b8eae0f7e5e5ff54427ccf Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Rapha=C3=ABl=20Proust?= Date: Fri, 28 Aug 2020 09:17:20 +0200 Subject: [PATCH 3/6] Crypto: safety test for seeded_hash --- src/lib_crypto/test/dune | 7 ++++ src/lib_crypto/test/test_ids.ml | 57 +++++++++++++++++++++++++++++++++ 2 files changed, 64 insertions(+) create mode 100644 src/lib_crypto/test/test_ids.ml diff --git a/src/lib_crypto/test/dune b/src/lib_crypto/test/dune index 7ac8114317d1..07b5e995fdd1 100644 --- a/src/lib_crypto/test/dune +++ b/src/lib_crypto/test/dune @@ -4,6 +4,7 @@ test_base58 test_ed25519 test_blake2b + test_ids test_pvss test_crypto_box test_deterministic_nonce) @@ -23,6 +24,7 @@ test_base58.exe test_ed25519.exe test_blake2b.exe + test_ids.exe test_pvss.exe test_crypto_box.exe test_deterministic_nonce.exe)) @@ -47,6 +49,10 @@ (name runtest_blake2b) (action (run %{exe:test_blake2b.exe}))) +(alias + (name runtest_ids) + (action (run %{exe:test_ids.exe}))) + (alias (name runtest_pvss) (action (run %{exe:test_pvss.exe}))) @@ -67,6 +73,7 @@ (alias runtest_base58) (alias runtest_ed25519) (alias runtest_blake2b) + (alias runtest_ids) (alias runtest_pvss) (alias runtest_crypto_box) (alias runtest_deterministic_nonce))) diff --git a/src/lib_crypto/test/test_ids.ml b/src/lib_crypto/test/test_ids.ml new file mode 100644 index 000000000000..cef8986d1e5f --- /dev/null +++ b/src/lib_crypto/test/test_ids.ml @@ -0,0 +1,57 @@ +(*****************************************************************************) +(* *) +(* Open Source License *) +(* Copyright (c) 2020 Nomadic Labs *) +(* *) +(* Permission is hereby granted, free of charge, to any person obtaining a *) +(* copy of this software and associated documentation files (the "Software"),*) +(* to deal in the Software without restriction, including without limitation *) +(* the rights to use, copy, modify, merge, publish, distribute, sublicense, *) +(* and/or sell copies of the Software, and to permit persons to whom the *) +(* Software is furnished to do so, subject to the following conditions: *) +(* *) +(* The above copyright notice and this permission notice shall be included *) +(* in all copies or substantial portions of the Software. *) +(* *) +(* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR*) +(* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, *) +(* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL *) +(* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER*) +(* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING *) +(* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER *) +(* DEALINGS IN THE SOFTWARE. *) +(* *) +(*****************************************************************************) + +let test_seeded_hash (module H : S.HASH) seed input = + ignore @@ H.seeded_hash seed @@ H.hash_string input + +let hashes = + [ (module Chain_id : S.HASH); + (module Block_hash : S.HASH); + (module Operation_hash : S.HASH); + (module Protocol_hash : S.HASH); + (module Context_hash : S.HASH); + (module Crypto_box.Public_key_hash : S.HASH) ] + +let seeds = Array.init 256 (fun i -> i - 128) + +let inputs = + [ []; + [""]; + ["0"]; + ["lkjahflkjahdlfkajshlfkjlfjhalsdfjhlasdjfhlasdjfhlasjdfhlajdflajshdflaksf"]; + ["asldkfj"; "alksjdhfl"; "lkajshdlfkasj"]; + [""; ""; ""; ""; ""; ""]; + ["\x00"; "\x00"; "a"; "\x00"; "a"; "a"] ] + +let seeded_hash_safety () = + ListLabels.iter hashes ~f:(fun hash -> + ArrayLabels.iter seeds ~f:(fun seed -> + ListLabels.iter inputs ~f:(fun input -> + test_seeded_hash hash seed input))) + +let seeded_hash_safety_test = + [("seeded_hash safety", `Quick, seeded_hash_safety)] + +let () = Alcotest.run "tezos-crypto" [("INDEXES", seeded_hash_safety_test)] -- GitLab From ffba342eb5ba23ac65be6246e396c8a8c01098c9 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Rapha=C3=ABl=20Proust?= Date: Fri, 28 Aug 2020 09:21:43 +0200 Subject: [PATCH 4/6] Crypto: take absolute value of seed to avoid negative indexes --- src/lib_crypto/blake2B.ml | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/src/lib_crypto/blake2B.ml b/src/lib_crypto/blake2B.ml index 8c60b2560b52..a5ee5cb089e0 100644 --- a/src/lib_crypto/blake2B.ml +++ b/src/lib_crypto/blake2B.ml @@ -192,14 +192,16 @@ struct let open Compare.Int (* shadowing comparators *) in if size > 8 then fun seed h -> - Int64.to_int (TzEndian.get_int64 (to_bytes h) (seed mod (size - 8))) + Int64.to_int + (TzEndian.get_int64 (to_bytes h) (abs @@ (seed mod (size - 8)))) else if size = 8 && Sys.word_size = 64 then fun _seed h -> (* NOTE: we do not use the seed here because we have a _perfect_ hash: we get the whole value. (Technically we ignore one bit because of the conversion from Int64 to int. *) Int64.to_int (TzEndian.get_int64 (to_bytes h) 0) else if size > 4 then fun seed h -> - Int32.to_int (TzEndian.get_int32 (to_bytes h) (seed mod (size - 4))) + Int32.to_int + (TzEndian.get_int32 (to_bytes h) (abs @@ (seed mod (size - 4)))) else fun _seed h -> (* Here again we have a perfect hash. (Technically again we ignore one bit on 32-bit machines if size = 4.) *) -- GitLab From df0b2bee89756e59adb5b8daea4174b2cdfe16ae Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Rapha=C3=ABl=20Proust?= Date: Wed, 2 Sep 2020 16:26:19 +0200 Subject: [PATCH 5/6] Crypto: reduce seeded hash size to int32 --- src/lib_crypto/blake2B.ml | 14 +++----------- 1 file changed, 3 insertions(+), 11 deletions(-) diff --git a/src/lib_crypto/blake2B.ml b/src/lib_crypto/blake2B.ml index a5ee5cb089e0..5df1f243e70d 100644 --- a/src/lib_crypto/blake2B.ml +++ b/src/lib_crypto/blake2B.ml @@ -189,22 +189,14 @@ struct conv to_bytes of_bytes_exn (Fixed.bytes size) let seeded_hash = + (* NOTE: we hash to small integers (32bit) because the OCaml hashtable only + cares about a few bits *) let open Compare.Int (* shadowing comparators *) in - if size > 8 then fun seed h -> - Int64.to_int - (TzEndian.get_int64 (to_bytes h) (abs @@ (seed mod (size - 8)))) - else if size = 8 && Sys.word_size = 64 then fun _seed h -> - (* NOTE: we do not use the seed here because we have a _perfect_ hash: we - get the whole value. (Technically we ignore one bit because of the - conversion from Int64 to int. *) - Int64.to_int (TzEndian.get_int64 (to_bytes h) 0) - else if size > 4 then fun seed h -> + if size > 4 then fun seed h -> Int32.to_int (TzEndian.get_int32 (to_bytes h) (abs @@ (seed mod (size - 4)))) else fun _seed h -> - (* Here again we have a perfect hash. (Technically again we ignore one bit - on 32-bit machines if size = 4.) *) let r = ref 0 in let h = to_bytes h in for i = 0 to size - 1 do -- GitLab From 3880ade6344f1883f62ab1efb82bdca7e4b680dc Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Rapha=C3=ABl=20Proust?= Date: Mon, 7 Sep 2020 15:25:24 +0200 Subject: [PATCH 6/6] Crypto: use seed to rotate hash extracts --- src/lib_crypto/blake2B.ml | 17 ++++++++++++++--- src/lib_crypto/chain_id.ml | 18 ++++++++++++------ 2 files changed, 26 insertions(+), 9 deletions(-) diff --git a/src/lib_crypto/blake2B.ml b/src/lib_crypto/blake2B.ml index 5df1f243e70d..916d1c282cad 100644 --- a/src/lib_crypto/blake2B.ml +++ b/src/lib_crypto/blake2B.ml @@ -188,15 +188,26 @@ struct let open Data_encoding in conv to_bytes of_bytes_exn (Fixed.bytes size) + let int_rotate offset i = + let open Stdlib in + assert (0 <= offset) ; + assert (offset < 32) ; + (i lsl offset) lor (i lsr (32 - offset)) + let seeded_hash = (* NOTE: we hash to small integers (32bit) because the OCaml hashtable only cares about a few bits *) let open Compare.Int (* shadowing comparators *) in if size > 4 then fun seed h -> - Int32.to_int - (TzEndian.get_int32 (to_bytes h) (abs @@ (seed mod (size - 4)))) - else fun _seed h -> + let seed = abs seed in + int_rotate (seed mod 32) + @@ Int32.to_int + @@ TzEndian.get_int32 (to_bytes h) (seed mod (size - 4)) + else fun seed h -> + let seed = abs seed in + int_rotate (seed mod 32) + @@ let r = ref 0 in let h = to_bytes h in for i = 0 to size - 1 do diff --git a/src/lib_crypto/chain_id.ml b/src/lib_crypto/chain_id.ml index 57b175ca8560..6cb49e413570 100644 --- a/src/lib_crypto/chain_id.ml +++ b/src/lib_crypto/chain_id.ml @@ -131,12 +131,18 @@ let raw_encoding = let open Data_encoding in conv to_bytes of_bytes_exn (Fixed.bytes size) -(* NOTE: we ignore hashing because identity is a perfect hash. (Technically we - ignore one bit on 32-bit machines because of the conversion from Int32 to - int.) *) -let hash h = Int32.to_int (TzEndian.get_int32 (to_bytes h) 0) - -let seeded_hash _seed h = hash h +let int_rotate offset i = + let open Stdlib in + assert (0 <= offset) ; + assert (offset < 32) ; + (i lsl offset) lor (i lsr (32 - offset)) + +let seeded_hash seed h = + int_rotate (abs seed mod 32) + @@ Int32.to_int + @@ TzEndian.get_int32 (to_bytes h) 0 + +let hash h = seeded_hash 0 h let of_block_hash bh = hash_bytes [Block_hash.to_bytes bh] -- GitLab