From ec251b254c85f6040091ead95cde033445d1e3e4 Mon Sep 17 00:00:00 2001 From: Markus Triska Date: Sat, 24 Feb 2024 08:18:38 +0100 Subject: [PATCH] ENHANCED: Safe HMAC verification, using constant time string comparison. Without this provision, the expected HMAC can be gathered from timing differences depending on the position where the strings first diverge, and hence an attacker can forge an authenticated message by supplying the gathered HMAC. Test case, using exp(E) to succeed exactly 2^E times: exp(E) :- N is 2^E, between(1, N, _). yielding: ?- Options = [algorithm(sha512),hmac([1,2,3])], Ds = "test", crypto_data_hash(Ds, H, Options), phrase((seq(As),seq(Bs)), H), same_length(Bs, Cs), maplist(=(a), Cs), append(As, Cs, H1), time((exp(10),crypto_data_hash(Ds, H1, Options),false)). %@ % CPU time: 0.710s, 7_942_187 inferences %@ % CPU time: 0.713s, 7_942_187 inferences %@ % CPU time: 0.712s, 7_942_187 inferences %@ % CPU time: 0.711s, 7_942_187 inferences %@ % CPU time: 0.710s, 7_942_187 inferences %@ % CPU time: 0.711s, 7_942_187 inferences %@ % CPU time: 0.710s, 7_942_187 inferences ?- length(_, L), time((exp(10),crypto_data_hash("test", "3caebd1a0a2647930319a660b7d3642eb380fbd43202f9f6d08aabaa9ba50c39522a12ead10f0423f0af613cbc6fea74ad682ee11f563cc2e735722004fda2ba", [algorithm(sha512),hmac([0,L])]),false)). %@ % CPU time: 0.733s, 7_878_699 inferences %@ % CPU time: 0.734s, 7_878_699 inferences %@ % CPU time: 0.732s, 7_878_699 inferences %@ % CPU time: 0.733s, 7_878_699 inferences %@ % CPU time: 0.733s, 7_878_699 inferences %@ % CPU time: 0.733s, 7_878_699 inferences %@ % CPU time: 0.733s, 7_878_699 inferences %@ % CPU time: 0.733s, 7_878_699 inferences %@ % CPU time: 0.733s, 7_878_699 inferences %@ % CPU time: 0.733s, 7_878_699 inferences %@ % CPU time: 0.733s, 7_878_699 inferences %@ % CPU time: 0.515s, 5_525_404 inferences %@ error('$interrupt_thrown',repl/0). --- src/lib/crypto.pl | 59 +++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 54 insertions(+), 5 deletions(-) diff --git a/src/lib/crypto.pl b/src/lib/crypto.pl index e76ed7d6..94def2c0 100644 --- a/src/lib/crypto.pl +++ b/src/lib/crypto.pl @@ -91,9 +91,36 @@ bytes_hex([B|Bs]) --> [C0,C1], }, bytes_hex(Bs). +char_hexval(C, H) :- + integer(H), + !, + hexval_char(H, C). char_hexval(C, H) :- nth0(H, "0123456789abcdef", C), !. char_hexval(C, H) :- nth0(H, "0123456789ABCDEF", C), !. +/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - + We specialize char_hexval/2 for use if the value is given, + so that it works in constant time in this case. + + The security of HMAC verification depends on this property. +- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ + +hexval_char(0, '0'). +hexval_char(1, '1'). +hexval_char(2, '2'). +hexval_char(3, '3'). +hexval_char(4, '4'). +hexval_char(5, '5'). +hexval_char(6, '6'). +hexval_char(7, '7'). +hexval_char(8, '8'). +hexval_char(9, '9'). +hexval_char(0xa, a). +hexval_char(0xb, b). +hexval_char(0xc, c). +hexval_char(0xd, d). +hexval_char(0xe, e). +hexval_char(0xf, f). must_be_bytes(Bytes, Context) :- must_be(list, Bytes), @@ -195,7 +222,13 @@ crypto_random_byte(B) :- '$crypto_random_byte'(B). % - `hmac(+Key)` % Compute a hash-based message authentication code (HMAC) using % Key, a list of bytes. This option is currently supported for -% algorithms `sha256`, `sha384` and `sha512`. +% algorithms `sha256`, `sha384` and `sha512`. If `Hash` is +% instantiated, then it is compared with the computed HMAC +% in such a way that no information about the expected HMAC +% is revealed, using a comparison of strings that always takes +% the same time independent of whether and where the strings +% differ. This option can therefore also be used to safely +% _verify_ a given HMAC. % % Example: % @@ -222,10 +255,26 @@ crypto_data_hash(Data0, Hash, Options0) :- ( member(HMAC, Options0), nonvar(HMAC), HMAC = hmac(Ks) -> must_be_bytes(Ks, crypto_data_hash/3), hmac_algorithm(A), - '$crypto_hmac'(Data, Encoding, Ks, HashBytes, A) - ; '$crypto_data_hash'(Data, Encoding, HashBytes, A) - ), - hex_bytes(Hash, HashBytes). + '$crypto_hmac'(Data, Encoding, Ks, HashBytes, A), + ( var(Hash) -> + hex_bytes(Hash, HashBytes) + ; must_be(chars, Hash), + hex_bytes(HashMAC, HashBytes), + chars_equal_constant_time(Hash, HashMAC) + ) + ; '$crypto_data_hash'(Data, Encoding, HashBytes, A), + hex_bytes(Hash, HashBytes) + ). + +chars_equal_constant_time(As, Bs) :- + maplist(chars_xor, As, Bs, Xs), + sum_list(Xs, Sum), + Sum =:= 0. + +chars_xor(A, B, Xor) :- + char_code(A, CA), + char_code(B, CB), + Xor is xor(CA,CB). hmac_algorithm(sha256). hmac_algorithm(sha384). -- 2.54.0