Open jaromil opened 4 years ago
Could you maybe also add a few test vectors for the SK -> AES-CTR key hmac ?
Sure! They are now included above below the line SK -> PRF (HMAC):
I am still having problems recreating your ephemeral. From issue #57 it was pointed out that the IV starts at 0, but I suspect that you have started from 1 - still this is not the only discrepancy that I am dealing with.
I have included some of these test vectors in the unit tests for the Rust library here : https://github.com/snakehand/dp-3t-client - but the epehemeral IV is is still off by 1 compared to Zenroom.
@jaromil , @snakehand - having trouble generating exactly the same with Apple's crypto.
Could either of you be so kind to describe how this "n * 10000" string is serialised to uint8_t's ?
I.e some slightly lower level pseudo code ?
I think you are looking at older code, the IV is a simple counter now, and nonce=0.
In Rust I do this:
let mut serial = [0u8; 16];
serial[12..16].copy_from_slice(&i.to_be_bytes());
let mut block = GenericArray::clone_from_slice(&serial);
cipher.encrypt_block(&mut block);
I.e just copy the counter to big endian bytes at the end of the 16 byte AES input block.
So I see you do Aes256::new( ... with the key as HMAC of Sk and a password = "Decen.." which yields (for me) 4d91fd2e6c3b27ed696d9a2c971cd148da9d6e13a95749e140d37c3087053ea1 if I do not include the \0.
You then do serial = 16 bytes; top 4 bytes contain a 32 bit/4byte unsigned integer in Big endian order.
And AES encrypt this rolling. And the result is again 16 bytes.
Correct ?
(This comment has been edited to sync to the reference implementation released recently.)
The following Kotlin results in the same output as the reference implementation (see https://github.com/DP-3T/reference_implementation/pull/9).
fun ephIDs(n: Int): List<EphID> {
val sha256_HMAC: Mac = Mac.getInstance("HmacSHA256")
sha256_HMAC.init(SecretKeySpec(sk, "HmacSHA256"))
val prf = sha256_HMAC.doFinal("Broadcast key".toByteArray())
val cipher = Cipher.getInstance("AES/CTR/NoPadding")
val b = ByteArray(16 * n)
cipher.init(Cipher.ENCRYPT_MODE, SecretKeySpec(prf, "AES"), IvParameterSpec(ByteArray(16)))
cipher.update(b, 0, b.size, b, 0)
var out = mutableListOf<EphID>();
for (i in 0 until n) {
out.add(EphID(b.sliceArray(i*16 until i*16+16)));
}
return out
}
This was useful to me in confirming that the performance would be manageable on low-spec Android phones.
Ok - so in C this would be:
uint8_t b[16 = [ 0x0, 0x0 .... 0x0 ];
and I take it that IvParameterSpec(ByteArray(16) is simply an IV of 16 bytes that are 0x0 each ?
And we then create 16 byte of zero's plaintext blocks with cipher.update(). Correct.
What is your second EphiID ?
I am no Java / Kotlin (?) expert but I think MessageDigest.getInstance("SHA-256") yields the wrong digest. You want to somehow use HMAC-SHA256 with SK as the key, and not just feed it into the digest algorithm
To avoid further ambiguity I have updated the first post in this issue with the actual code used and with two columns for the EphID vectors: left shows the counter (used as IV / nonce
) and right shows the result. In all EphID generation the AES-CTR is used with a plaintext all set to zero. It is also true that I start the counter from 01 rather than 00 as indicated in the whitepaper The vectors are now in correct order and starting from 00.
@jaromil I think you have the IVs backwards, your loop is counting down in : https://github.com/DECODEproject/Zenroom/blob/master/src/lua/zencode_dp3t.lua
I updated https://github.com/snakehand/dp-3t-client with a small example that prints some test vectors, including the 0 IV:
eph: 0 - Ephemeral(day:0, token:c7044845a6a0da7a61687e1bb08afca4)
eph: 1 - Ephemeral(day:0, token:a747e729bf2e3de3ec6ecbdb0f889f5b)
eph: 2 - Ephemeral(day:0, token:034015608c5a55672315cb614f5a94a3)
eph: 3 - Ephemeral(day:0, token:6c4902c119d6a7ada139677983ef02b6)
eph: 4 - Ephemeral(day:0, token:c71d3e89927435b2aae42be7e7aea70a)
eph: 5 - Ephemeral(day:0, token:b5ced4fff0f319d40a924f91aecdf1dd)
eph: 6 - Ephemeral(day:0, token:17c93fce14a191a832e217ec2e9347df)
eph: 7 - Ephemeral(day:0, token:282917263748673f63ab3416fc2e3ee9)
Happy to see we aligned! will correct the sorting of my vectors ASAP I have now corrected the vectors above, confirmed also by @snakehand's implementation in Rust.
Lovely - I'll update the C/Swift/ObjC to match.
Meanwhile I've put up a small fork of this repo with a branch with temporary editable version of the 3 documents - so it is easier to make notes about details like this in those documents. Reverse engineered/copy-paste job (https://github.com/dirkx/DP-3T-Documents/tree/editable-version -- directory 'src').
Hmm - not having much luck; the plaintext is 16 x 0 bytes for each Eph_id ?
Below is the code I am using (runnable version at https://gist.github.com/dirkx/53143596fa935b6de96e6521d82797b6)
And correct that the sk is used as the key in the HMAC; and that it sighs the "Decentralized.. " string ? And internally rust/Zenroom does the 14 round cycle on the key to expand it, etc ?
dp3t_err_t generate_ephids(dp3t_skt_t * skt, dp3t_eph_t list[], size_t num) {
uint8_t aes_key[SHA256_DIGEST_LENGTH];
unsigned int len =SHA256_DIGEST_LENGTH;
// local PRF = SHA256:hmac(ACK.secret_day_key, BROADCAST_KEY)
// 446563656e7472616c697a656420507269766163792d50726573657276696e672050726f78696d6974792054726163696e67
// unsigned char *HMAC(const EVP_MD *evp_md, const void *key, int key_len, const unsigned char *d, size_t n, unsigned char *md, unsigned int *md_len);
//
HMAC(EVP_sha256(),
skt->key, SKT_LEN,// HMAC- key (all 0's in this test)
SKT_BROADCAST_KEY, sizeof(SKT_BROADCAST_KEY), // key to be digested and signed
aes_key, &len);
// 83b544f1dfb6564e27f6978f43de6c5dfafc510709f270c91daa553fc11cefe1
//
print_hex(aes_key, SHA256_DIGEST_LENGTH);
for(int i = 0; i < num; i++) {
uint8_t iv[SKT_EHPID_LEN];
bzero(iv,SKT_EHPID_LEN);
*(uint32_t*)(iv+12) = htonl(i); // big endian or network order.
/*
IV: 00000000000000000000000000000000
IV: 00000000000000000000000000000001
IV: 00000000000000000000000000000002
IV: 00000000000000000000000000000003
IV: 00000000000000000000000000000004
IV: 00000000000000000000000000000005
IV: 00000000000000000000000000000006
IV: 00000000000000000000000000000007
IV: 00000000000000000000000000000008
IV: 00000000000000000000000000000009
*/
printf("IV: "); print_hex(iv,16);
const EVP_CIPHER * cipher = EVP_aes_128_ctr();
EVP_CIPHER_CTX * ctx;
assert(ctx = EVP_CIPHER_CTX_new());
EVP_CIPHER_CTX_init(ctx);
assert(1 == EVP_EncryptInit(ctx, cipher, aes_key, iv));
EVP_CIPHER_CTX_set_padding(ctx, 0);
int len = 0, len2 = 0;
unsigned char outptr[ 2 * SKT_EHPID_LEN ];
uint8_t zeros[SKT_EHPID_LEN];
bzero(zeros,SKT_EHPID_LEN);
assert(1 == EVP_EncryptUpdate(ctx, outptr, &len, zeros, SKT_EHPID_LEN));
// assert(len <= SKT_EHPID_LEN);
assert(1 == EVP_EncryptFinal(ctx, outptr + len, &len2));
// assert(len + len2 != SKT_EHPID_LEN);
memcpy(list[i].id,outptr, SKT_EHPID_LEN);
EVP_CIPHER_CTX_cleanup(ctx);
EVP_CIPHER_CTX_free(ctx);
};
return 0;
}
I have now added a C library wrapper to my Rust code (check out clib) https://github.com/snakehand/dp-3t-client - This should make the code that I have very portable, and could possibly be linked straight into a mobile app on Android / iOS. I have tested performance on a Raspberry Pi, and it seems OK. ( This library is self contained and has no dependencies on ssl libraries. )
Also Zenroom is ported to react-native android/iOS and we ran some benchmarks on rpi3. I am curious about performance, would you share benchmarks? my test manages to find a single matching SK among 20.000 others in 11 seconds.
I ran this test on a single core on a Raspberry Pi 4 in around 1 second:
fn speed_test() {
let mut key: [u8; 32] = [0; 32];
let mut total = 0;
for i in 0..1000_u32 {
key[28..32].copy_from_slice(&i.to_be_bytes());
let rp = ReplayKey::new(0, 14, 8, &key);
total += rp.fold(0_u64, |s, _e| s + 1);
}
println!("{} ephemerals", total);
}
This test generates 1000 14 8 ephemeral IDs , but without any lookup. ( Lookup should be a O( log n ) operation, and not add a whole lot time )
I should add that the crypto implementations are constant time to prevent leaking secrets. I am not sure how this affects performance.
@snakehand @jaromil @jeffallen @cascremers @carmelatroncoso - tried to capture all what was said here and on slack in PR https://github.com/DP-3T/documents/pull/117 in terms of test vectors and exact protocol interpretations.
I.e. one that takes away all 'e.g.' in the documents.
With the arrival of the official reference implementation, this issue needs to be updated with test vectors from it, and other implementations should sync to them. See https://github.com/DP-3T/reference_implementation/pull/9 for proposed test vectors to use.
Hi Jeff, yes I see the reference implementation in python now, it generates EphIDs segmenting the output of a bigger chunk of data out of AES-CTR. I will do the same and update my vectors ASAP.
@jaromil, @snakehand - did you manage ?
We cannot get it to work and 3 different people now all independently got the same values, in 3 languages, but not those of the team python output. So either we are all making the exact same mistake/misreading - or python/Crypthome is special.
See https://lists.dlitz.net/pipermail/pycrypto/2020/000909.html for my summary.
Hey @dirkx,
i am following the discussions here with great interest and am really looking forward to see the project evolve further.
Not sure if this is still relevant but from what i understood from your last comment is, that you cannot get the same test vectors in the python version of your code, compared e.g. with the C version.
I think, that you probably have a typo in your AES key definition. If you change key = b"0" * 32
to key = b"\0" * 16
or key = b'\x00' * 16
then i think it is in line with the C version bzero(key,16);
since b"0"
is the byte object representation of the symbol "0" in acsii which is in hex 0x30.
Then in my test run it produces the same test vectors as your other implementations.
I am not a python expert myself, but maybe this helps.
Goodmorning everyone! I have updated the vectors here using both the broadcast key with and without BOM prefix.
@jaromil - where is the code ?
It is in the first post of the issue: Zenroom is a virtual machine without external dependencies using Lua as direct-syntax parser, Milagro as crypto backend and its own Zencode language as DSL. In my issue you see both the Lua and the Zencode sources.
Here you find the Zencode implementation inside Zenroom I paste the Lua code from: https://github.com/DECODEproject/Zenroom/blob/master/src/lua/zencode_dp3t.lua Here you find the compliancy tests running at each commit https://github.com/DECODEproject/Zenroom/tree/master/test/nist
More development information about Zenroom is at https://dev.zenroom.org
And with BOM you mean a UTF-8 like apple has in front of the broadcast key ?
Yes, I provided that too since I noticed their design has changed that detail so useful to have both.
Why is a BOM marker even required ? Should the implementation have to handle different byte orderings ? UTF-8 does not require a BOM, since the byte ordering is unambiguous. UTF-16 and UTF-32 does though, but you also need to specify a word size for a BOM to make sense. What is the word size that this BOM refers to ? 16,32,64,128,256 bits ? - Having to use this type of "solution" at all seems a bit alien to me. It is better to have a solid spec that does not leave any openings for byte ordering ambiguities.
To me too, but then please talk some sense to them, I'm just sticking to my plan to provide test vectors ;^) I have added a note about this weirdness.
The broadcast key used by Zenroom and that used by the DP-3T reference implementation, and the DP-3T app all differ: https://github.com/DECODEproject/Zenroom/blob/master/src/lua/zencode_dp3t.lua#L21 https://github.com/DP-3T/reference_implementation/blob/master/LowCostDP3T.py#L29 https://github.com/DP-3T/dp3t-sdk-android/blob/develop/dp3t-sdk/sdk/src/main/java/org/dpppt/android/sdk/internal/crypto/CryptoModule.java#L44
I just filed an issue about straightening out the latter two, here: https://github.com/DP-3T/reference_implementation/issues/11
(I do not see any indication of BOM in either the spec or the two DP-3T implementations. Where are you guys seeing that?)
I didn't push the dp-3t zenroom scenario update yet, did that in https://github.com/DECODEproject/Zenroom/commit/fc72b3225303db751c9a58f82b2145cede197ef0 the broadcast key is set in zencode (as an external variable lets say).
Regarding:
I confirm running both scripts we have matching vectors! :cowboy_hat_face:
@snakehand w.r.t. to the BOM. Completely agreed. There is no need for that key to be anything but a well defined, easy to not mis-implement, byte sequence (with no entropy requirements).
So having it a pure US-ASCII, 7 bit safe, printable (32 .. 126) thing is goodness. With no \0 or any other termination. So if it is 'Broadcast key' it is exactly those 13 chars from B to and including y. And that is it.
And yes - that does mean that modern fancy languages need to be a bit careful or define it as something like seed = [ 0x42, 0x72, 0x6f, 0x61, 0x64, 0x63, 0x61, 0x73, 0x74, 0x20, 0x6b, 0x65, 0x79 ] if their internal string representation is fancy with BOMs and full unicode normalisation/ligatures/etc.
checking the plain ASCII test vectors we are testing them against a new WolfSSL based implementation by @danielinux and found they are not the same as the ephids given by the reference implementation. So we have known alignment so far only yet (just up until the HMAC).
We realised that there can be confusion, caused by the ambiguity of the white-paper about use of AES or even salsa20; this may be worth a discussion to nail the specification, meanwhile I will see to provide vectors for salsa20 and AES128.
I've double checked my results using an online tool (cryptii.com) and everything looks correct from my side.
My test vector:
SK = { 0, 0, 0, 0, ...}
PRF = HMAC(SK, "Broadcast key") = d59d48e21935f3389e3bd3eb02cf66989190b7b09ed6c0a4b9616f49455c4f9a
EPHID_N = AES128_CTR(key=PRF[0:15], payload={zeroes}, iv = N}
produces these EPHIDs:
[ 000 ] 4d36a58e7117d3822c49479288366fb4
[ 001 ] 862021c13506ea7def1c37141357ba1f
[ 002 ] 7da02c6475306dfd048d2b0327a6a01f
[ 003 ] df96b40bf9e6a644d118cdddb2704187
[ 004 ] 4eb8386371adc6f9f302e6a37ccdf10d
[ 005 ] a869a76e55e2676c397fe17792d717bb
[ 006 ] 8f302d4fc3d1929ac36798631ebda93a
[ 007 ] f075719abe8428be8bb5a619dd4da03b
[ 008 ] c1f74b598fa42a7015309a2964a9fcfb
Still a mistery to me how we are getting these other vectors from @dirkx's python branch, note that PRF is identical, but I am not sure about how Cryptodome's AES parameters work:
PRF: d59d48e21935f3389e3bd3eb02cf66989190b7b09ed6c0a4b9616f49455c4f9a
0 8fd521e6c47060efcbfdb9b801c30743
1 d86e56bb702117b8cf20dc4aadd42310
2 964ae662b3f174814660846d4f9c11e2
3 374d270a0c559ad1e4672fb1688ae5ad
4 b5d017a67940300cd28b59a94f739c0e
5 3208756abf0314be9ffc27a0c391ee91
6 75b14e4879cd0d5b06cf2b460ab5559a
7 6ebfd0d03f8ba78086054f313af52c81
8 c3db7c504dd6172d1e48804bedbaebba
From this website
I've found the issue. Everyone here is using AES256 with a 128bit key, and truncating all the blocks in half. Can you clarify this is the intended behavior? I was simply assuming that AES128 would produce the intended results. In other words, this is what you are doing at the moment:
SK
in half, to get a 128-bit keyFirst 256-bit EPHID as result of the above: 8f d5 21 e6 c4 70 60 ef cb fd b9 b8 01 c3 07 43 d8 6e 56 bb 70 21 17 b8 cf 20 dc 4a ad d4 23 10
Discard the lower 128 bits: 8f d5 21 e6 c4 70 60 ef cb fd b9 b8 01 c3 07 43
Can you please indicate whether this is intended or not, and what is the rationale of using a 256-bit algorithms with all parameters cut down to 128 bits?
Thanks,
/d
Isn't AES block size always 128 bits regardless of key size ?
In my Rust code ( https://github.com/snakehand/dp-3t-client ) I can get both variants by changing between Aes128 and Aes256, but the truncation happens when the SHA256 output is is fed as a 128 bits AES key. ( The Rust AES code will actually cause a panic or fail to compile of I feed it a key of incorrect size, whereas C and possibly python might just silently truncate the key )
The mistake, I think is, I and some others, took the 128 bit as meaning AES128_CTR; whereas in fact it is AES256_CTR with the last 128 bit chopped off.
Will verify and update / describe in the implementation notes.
Thanks for confirming the exact algorithms used.
I've fixed it on decode-proximity-hw, indeed I was assuming AES128 as I was confused by the TRUNCATE_128 method in the reference.
Now the nRF52 device gives the same EphIds:
BLE DP3T service started
All up, running the shell now
> testvec
SK0: 0000000000000000000000000000000000000000000000000000000000000000
Broadcast key: 42726f616463617374206b6579
Zeroes: 0000000000000000000000000000000000000000000000000000000000000000
PRF: d59d48e21935f3389e3bd3eb02cf66989190b7b09ed6c0a4b9616f49455c4f9a
SK Derivation: 66687aadf862bd776c8fc18b8e9f8e20089714856ee233b3902a591d0d5f2925
[ 000 ] 8fd521e6c47060efcbfdb9b801c30743
[ 001 ] d86e56bb702117b8cf20dc4aadd42310
[ 002 ] 964ae662b3f174814660846d4f9c11e2
[ 003 ] 374d270a0c559ad1e4672fb1688ae5ad
[ 004 ] b5d017a67940300cd28b59a94f739c0e
[ 005 ] 3208756abf0314be9ffc27a0c391ee91
[ 006 ] 75b14e4879cd0d5b06cf2b460ab5559a
[ 007 ] 6ebfd0d03f8ba78086054f313af52c81
[ 008 ] c3db7c504dd6172d1e48804bedbaebba
The code to generate EphIds on embedded is here
I''ve brought the C and Python code in line with https://github.com/DP-3T/reference_implementation/pull/10 -- and swift/java are fine too. And https://github.com/dirkx/DP-3T-Documents/commit/9c0823883a2b4766e6ff8ca1c41cd5448d69822b updated too.
To help align with other implementations of this protocol I’m sharing my test vectors for design 1, which are the expected results of two cryptographic transformations in DP3T given known inputs.
Zenroom passes SHA256 FIPS140–2 and AES-CTR NIST compliancy and the vectors below match the reference implementation. :heavy_check_mark:
The Zenroom code used to derive a new SK is:
The Zenroom code used to derive EphIDs (see the dp3t scenario implementation) is:
Zencode used for ephids derivation:
More info about Zenroom is available at https://dev.zenroom.org
Vectors using the public broacast key: "Broadcast key" with BOM, in hexadecimals:
EFBBBF42726f616463617374206b6579
(:warning: its weird to have a BOM)