1
$\begingroup$

I've been experimenting with an NTRU open-source C implementation here

I've noticed something (potentionally) strange with a certain set of params: NTRU_EES1087EP2 (defined here).

When generating keys, I seed the DRBG with 64 bytes of entropy (I assume this is enough, as the sample code states that "21 bytes of entropy are needed to instantiate a DRBG with a security strength of 112 bits", and I'm using params for 256-bit security, however if anyone can shed some light onto how this figure is calculated I'd be grateful). However, when I generate the keys - the private key seems to contain long strings of zeros towards the end (see below). Is this normal? It doesn't seem to happen with other parameters.

sample private key... 1718 bytes... concatenated to show the final bytes 156544c00710611967774836b33d4803ce89f7730d29149dfc2bca09fced9739820c831c6eab1e0f3df1d300624037810a3a0d381dd9fba4b2f915a6cf2cb3920f1b18ebe915581429a0722ae2545c2afc521ae6b9dd44b68a5ad411f04279f7880aad0482af693c93eab639fac398c73bd6bfb55aa80854e20598291b591025ace64bd63130abaaeb2d505c54da8d5835d2de210000f1b0006a26300a2013f01a80000a2000200000003060203a23663a2db002d0300060003121bea00a2003f00380200000000250300bd095ba20000870001021b00380101006300bd02ab03391b00cf510005a20000a2513c36adb442000b2dcb00001b6c00003c0912180053099ba20906005100003605a200a2020107001b120c2ed81202090000000900640100da0751bd363601521203381b010002a8010f01541b030101360a0000000006361b36b15a3f38a251000054c11c031c142d00010300000000031e0000540238a2a9010110060000a500db00

$\endgroup$
  • $\begingroup$ The first thing to know would be what kind of binary representation of the private key is that, in order to better find any conclusions about the private key. $\endgroup$ – cygnusv Jan 5 '15 at 17:17
  • $\begingroup$ it's hex (sorry, I neglected to mention that) $\endgroup$ – hunter Jan 5 '15 at 17:19
  • $\begingroup$ Yes, it is clear that it is hexadecimal, but what kind of representation is using? For example, this could be the concatenation of all the coefficients (but in which order?), or if the polynomial is sparse, then you could just store the coefficients different to 0, etc. Moreover, this hex string has 733 characters, which is strange since it is an odd number and a single byte requires 2 hex characters. $\endgroup$ – cygnusv Jan 5 '15 at 17:26
  • $\begingroup$ The string above is just to illustrate the repetition of zeros towards the end of a much larger (and seemingly pseudorandom) key. The key itself is 1718 bytes. As for the representation - I'm not sure how to answer. I'm just using the API - (ntru_crypto_ntru_encrypt_keygen) provided in the implementation, it returns the private key as a byte array (uint8_t). $\endgroup$ – hunter Jan 5 '15 at 17:39
  • $\begingroup$ What is the size of this array? $\endgroup$ – cygnusv Jan 5 '15 at 17:41
1
$\begingroup$

The secret key blob consist of 1718 bytes where the first 1500 indicates the corresponding public key. The last 200 ish bytes store the encoded secret key.

The secret key is a trinary polynomial with coefficients -1,0,1. So we only need to store the position of non-zero coefficients. The last couple of hundreds of bytes in the encoded secret key suggest which coefficients of the secret key polynomial are -1 or 1. For NTRU_EES1087EP2 parameter set, there are roughly 240 non-zero coefficients out of a total 1087 coefficients. Storing those positions requires

  • privkey_packed_trits_len = (p->N + 4) / 5;

which is (1087+4)/5 = 218 bytes. Due to the method that the key is parsed, there ought to be 0s.

see function: ntru_crypto_ntru_encrypt_key_parse


For you other question, "21 bytes of entropy are needed to instantiate a DRBG with a security strength of 112 bits" the bits of entropy required is 1.5 times the bit security strength. i.e. 21 bytes = 168 bits = 112 *1.5 for 256 bites security, you need 48 bytes of entropy.

  • min_bytes_of_entropy = (sec_strength_bits + sec_strength_bits/2) / 8;

See function: sha256_hmac_drbg_instantiate

$\endgroup$
2
$\begingroup$

NTRU private polynomial $f$, as described in Section 9.2.1 of IEEE Std. 1363.1, is computed as $f = 1 + p \cdot F \mod q$, where $F$ is a ternary polynomial of degree $N-1$ with a specific number of coefficients equal to -1, 1, and 0, determined by parameter $d_F$ (i.e., $d_F$ coefficients equal to 1, $d_F$ coefficients equal to -1, and the rest are 0's). In particular, for the EES1087EP2 parameter set ($N = 1087, p = 3, q = 2048, d_F = 120$, etc.), polynomial $F$ is of degree 1086 and has 120 coefficients equal to 1, 120 to -1, and the rest (i.e. 847) are 0's.

Knowing that, the answer to your question is a little bit complex and requires analyzing the code of the NTRU implementation you are using. When you ask for the binary representation of private key (see the code here), the NTRU library does not simply give you the private key. It actually produces a binary structure, with a header with some parameters, the public key and finally the private key, so the actual private key is just the final part of the output. Additionally, in some cases it stores the polynomial $F$ as the private key, since $f$ can be efficiently computed from $F$.

Since the polynomial $F$ is simply composed of $\{-1,0,1\}$ coefficients, then it can be represented in a much more compact way. In particular, they are storing 5 different coefficients per byte, as described here, so in your case your polynomial $F$ of 1087 terms fits in approximately 218 bytes. Since 218 bytes are 436 hexadecimals characters, this means that the polynomial $F$ will be represented in 436 hexadecimal characters. And that is exactly when the "strange behaviour" you describe begins, in the last 436 characters of the private key dump, which correspond to the polynomial $F$, that, as you know, have a lot of zeros.

$\endgroup$
  • $\begingroup$ +1 - thanks! I accepted the other answer because it also addressed the other doubt I had $\endgroup$ – hunter Jan 5 '15 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.