Revision 03d4e3099705095f258c7d37b65ac688553f70d0 authored by Nic Volanschi on 21 February 2024, 20:34:04 UTC, committed by Marge Bot on 22 February 2024, 08:38:38 UTC
1 parent 9ebb46e
timelock_legacy.ml
(*****************************************************************************)
(* *)
(* Open Source License *)
(* Copyright (c) 2020-2021 Nomadic Labs, <contact@nomadic-labs.com> *)
(* *)
(* 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. *)
(* *)
(*****************************************************************************)
open Tezos_hacl
type rsa_secret = {p : Z.t; q : Z.t}
type rsa_public = Z.t (* RSA modulus = p * q*)
type timelock_proof = Z.t
type locked_value = Z.t
type unlocked_value = Z.t
type symmetric_key = Crypto_box.Secretbox.key
type ciphertext = {nonce : Crypto_box.nonce; payload : bytes}
(*Should be sufficient since the public key will not be exposed for a long time*)
let size_modulus = 2048
(* Creates a symmetric key using hash based key derivation from the time locked value*)
let unlocked_value_to_symmetric_key unlocked_value =
let kdf_key = "Tezoskdftimelockv0" in
let to_hash = Z.to_string unlocked_value in
let hash = Blake2B.(to_bytes @@ hash_string ~key:kdf_key [to_hash]) in
Crypto_box.Secretbox.unsafe_of_bytes hash
(* A random Z arith element of size [size] bytes *)
let random_z size = Hacl.Rand.gen size |> Bytes.to_string |> Z.of_bits
let random_prime_z size =
let rec aux () =
let trial = random_z size in
if Z.probab_prime trial 25 = 0 then aux () else trial
in
aux ()
(* Generates and RSA key pair of 2048 bits (= 256 bytes) *)
let gen_rsa_keys () =
(* We divide by 8 to convert to bytes and by 2 because we generate two primes *)
let size = size_modulus / (2 * 8) in
let p = random_prime_z size in
let q = random_prime_z size in
(Z.(p * q), {p; q})
(* Generates almost uniformly a Zarith element between 0 and [public key].
Intended for generating the time lock *)
let gen_locked_value rsa_public =
(* We divide by 8 to convert to bytes *)
Z.erem (random_z ((size_modulus / 8) + 16)) rsa_public
(* The resulting prime has size 256 bits or slightly more. *)
let hash_to_prime rsa_public ~time value key =
let personalization = Bytes.of_string "\032" in
let s =
String.concat
"\xff\x00\xff\x00\xff\x00\xff\x00"
(Int.to_string time :: List.map Z.to_bits [rsa_public; value; key])
in
let (Hacl.Blake2b.Hash hash_result) =
Hacl.Blake2b.direct ~key:personalization (Bytes.of_string s) 32
in
Z.(nextprime (of_bits (Bytes.to_string hash_result)))
let prove_without_secret rsa_public ~time locked_value unlocked_value =
let l = hash_to_prime rsa_public ~time locked_value unlocked_value in
let pow = Z.(pow (of_int 2) time / l) in
Z.powm locked_value pow rsa_public
let prove_with_secret secret ~time locked_value unlocked_value =
let rsa_public = Z.(secret.p * secret.q) in
let l = hash_to_prime rsa_public ~time locked_value unlocked_value in
let phi = Z.((secret.p - one) * (secret.q - one)) in
let pow = Z.(pow (of_int 2) time / l mod phi) in
Z.powm locked_value pow rsa_public
(* The proof is verified by checking that
lv ^ (2 ^ time) = (proof ^ l) * (lv ^ r) mod public
which is equivalent to
2 ^ time = (((2 ^ time) / l) * l) + (2 ^ time mod l) mod phi
see https://eprint.iacr.org/2018/712.pdf section 3.2 for this proof
*)
let verify_timelock rsa_public ~time locked_value unlocked_value proof =
let l = hash_to_prime rsa_public ~time locked_value unlocked_value in
let r = Z.(powm (of_int 2) (Z.of_int time) l) in
unlocked_value
= Z.(powm proof l rsa_public * powm locked_value r rsa_public mod rsa_public)
(* Gives the value that was timelocked from the timelock, the secret and the
time. Works in logarithmic time in [time] *)
let unlock_with_secret secret ~(time : int) (locked_value : locked_value) =
let phi = Z.((secret.p - one) * (secret.q - one)) in
let e = Z.powm (Z.of_int 2) (Z.of_int time) phi in
Z.powm locked_value e Z.(secret.p * secret.q)
let unlock_and_prove_with_secret secret ~(time : int)
(locked_value : locked_value) =
let unlocked_value = unlock_with_secret secret ~time locked_value in
let pi = prove_with_secret secret ~time locked_value unlocked_value in
(unlocked_value, pi)
let locked_value_to_symmetric_key_with_secret secret ~(time : int)
(locked_value : locked_value) : symmetric_key =
unlocked_value_to_symmetric_key (unlock_with_secret secret ~time locked_value)
(* Gives the value that was timelocked from the timelock, the public modulus
and the time. Works in linear time in [time] *)
let unlock_and_prove_without_secret rsa_public ~time locked_value =
let rec aux time v =
if time = 0 then v else aux Int.(pred time) Z.(v * v mod rsa_public)
in
let unlocked_value = aux time locked_value in
let pi = prove_without_secret rsa_public ~time locked_value unlocked_value in
(unlocked_value, pi)
let locked_value_to_symmetric_key_with_proof (rsa_public : rsa_public)
~(time : int) locked_value unlocked_value proof =
if verify_timelock rsa_public ~time locked_value unlocked_value proof then
Some (unlocked_value_to_symmetric_key unlocked_value)
else None
let encrypt symmetric_key plaintext =
let nonce = Crypto_box.random_nonce () in
{
nonce;
payload = Crypto_box.Secretbox.secretbox symmetric_key plaintext nonce;
}
let decrypt symmetric_key ciphertext =
Crypto_box.Secretbox.secretbox_open
symmetric_key
ciphertext.payload
ciphertext.nonce
(* ------------*)
type chest_key = {unlocked_value : unlocked_value; proof : timelock_proof}
type chest = {
locked_value : locked_value;
rsa_public : rsa_public;
ciphertext : ciphertext;
}
let proof_encoding = Data_encoding.n
let chest_key_encoding =
let open Data_encoding in
def "timelock.chest_key"
@@ conv
(fun chest_key -> (chest_key.unlocked_value, chest_key.proof))
(fun (unlocked_value, proof) -> {unlocked_value; proof})
(obj2
(req "unlocked_value" Data_encoding.n)
(req "proof" Data_encoding.n))
let ciphertext_encoding =
let open Data_encoding in
def "timelock.ciphertext"
@@ conv_with_guard
(fun ciphertext -> (ciphertext.nonce, ciphertext.payload))
(fun (nonce, payload) ->
if Bytes.length payload <= Crypto_box.tag_length then
Error "The ciphertext has a negative size"
else Ok {nonce; payload})
(obj2
(req "timelock.nonce" Crypto_box.nonce_encoding)
(req "timelock.payload" bytes))
let min_rsa_modulus = Z.(shift_left (of_int 2) 2000)
let chest_encoding =
let open Data_encoding in
def "timelock.chest"
@@ conv_with_guard
(fun chest -> (chest.locked_value, chest.rsa_public, chest.ciphertext))
(fun (locked_value, rsa_public, ciphertext) ->
if Z.Compare.(locked_value < Z.zero || locked_value >= rsa_public) then
Error "locked value is not in the rsa group"
else if Z.leq rsa_public min_rsa_modulus then
Error "rsa modulus is too small"
else Ok {locked_value; rsa_public; ciphertext})
(obj3
(req "locked_value" n)
(req "rsa_public" n)
(req "ciphertext" ciphertext_encoding))
type opening_result = Correct of Bytes.t | Bogus_cipher | Bogus_opening
let open_chest chest chest_key ~time =
if time < 0 then failwith "Timelock: trying to open with a negative time"
else
let sym_key_opt =
locked_value_to_symmetric_key_with_proof
chest.rsa_public
~time
chest.locked_value
chest_key.unlocked_value
chest_key.proof
in
match sym_key_opt with
| None -> Bogus_opening
| Some sym_key -> (
let plaintext_opt = decrypt sym_key chest.ciphertext in
match plaintext_opt with
| None -> Bogus_cipher
| Some plaintext -> Correct plaintext)
let create_chest_and_chest_key ~payload ~time =
let rsa_public, rsa_secret = gen_rsa_keys () in
let locked_value = gen_locked_value rsa_public in
let unlocked_value, proof =
unlock_and_prove_with_secret rsa_secret ~time locked_value
in
let sym_key = unlocked_value_to_symmetric_key unlocked_value in
let ciphertext = encrypt sym_key payload in
({locked_value; rsa_public; ciphertext}, {unlocked_value; proof})
let create_chest_key chest ~time =
let unlocked_value, proof =
unlock_and_prove_without_secret chest.rsa_public ~time chest.locked_value
in
{unlocked_value; proof}
let get_plaintext_size chest =
Bytes.length chest.ciphertext.payload - Crypto_box.tag_length
(*-------- sampling function for gas benchmarks-----*)
(* Those function are unsafe for wallet usage as they use the OCaml
random generator. This is used to easily reproduce benchmarks. *)
let gen_random_bytes_unsafe size =
Bytes.init size (fun _ -> Char.chr (Random.int 256))
let gen_random_z_unsafe size =
gen_random_bytes_unsafe size |> Bytes.to_string |> Z.of_bits
let gen_random_prime_unsafe size = gen_random_z_unsafe size |> Z.nextprime
let gen_rsa_keys_unsafe () =
let size = size_modulus / (2 * 8) in
let p = gen_random_prime_unsafe size in
let q = gen_random_prime_unsafe size in
(Z.(p * q), {p; q})
let gen_locked_value_unsafe rsa_public =
Z.erem (gen_random_z_unsafe (size_modulus / 8)) rsa_public
let encrypt_unsafe symmetric_key plaintext =
let nonce =
Data_encoding.Binary.of_bytes_exn
Crypto_box.nonce_encoding
(gen_random_bytes_unsafe Crypto_box.nonce_size)
in
{
nonce;
payload = Crypto_box.Secretbox.secretbox symmetric_key plaintext nonce;
}
let chest_sampler ~rng_state ~plaintext_size ~time =
Random.set_state rng_state ;
let plaintext = gen_random_bytes_unsafe plaintext_size in
let rsa_public, rsa_secret = gen_rsa_keys_unsafe () in
let locked_value = gen_locked_value_unsafe rsa_public in
let unlocked_value, proof =
unlock_and_prove_with_secret rsa_secret ~time locked_value
in
let sym_key = unlocked_value_to_symmetric_key unlocked_value in
let ciphertext = encrypt_unsafe sym_key plaintext in
({locked_value; rsa_public; ciphertext}, {unlocked_value; proof})
Computing file changes ...