Hot answers tagged

12

I'll comment only the statement referring to an AES-256 replacement with 4096-bit key: According to our engineers, this will take 23840 times longer to crack than aes256 Bob writing that is not able to correctly transcribe even the numbers that engineer Alice allegedly spelled: most likely, $23840$ is intended to be $2^{3840}$, which is the ratio $2^{...


8

Without a well-designed padding system it may be possible to craft a ciphertext that the decryptor may or may not be able to decrypt properly. Whether the decryptor is able to do so will depend on the private key. The concern is that an attacker may be able to craft a string of ciphertexts, listen in to whether they decrypt properly, and finally deduce the ...


8

My name is Zhenfei Zhang. I work for Security Innovation Inc., which acquired NTRU Inc. in 2010. The R-LWE based key exchange [1] uses a public matrix $a$ which may be manipulated. For instance, if $a$ is an NTRU style public key, i.e., $a = g/f$ where $g$ and $f$ are short, then one can break the system by recovering $f$. In particular, the cited paper ...


7

NTRU, as it was originally introduced, is based on what people now call the "NTRU assumption", which really just assumes that it is difficult to break NTRU. Annoyingly circular, but that's how it is. Similar to how breaking RSA is not provably as hard as factoring (technically it is based on the "RSA assumption"), but people still think it is hard, NTRU ...


7

The open source version of CyaSSL contains code that calls into the commercial NTRU library -- the library itself is missing of course. You might be able to make CyaSSL work with the open source NTRU implementation at https://github.com/tbuktu/libntru ; it's alpha level software though.


7

I am a cryptographic researcher at Security Innovation, which acquired NTRU. Apart from the aforementioned attack, there are two significant attacks, namely a chosen plaintext attack (CPA) and a chosen ciphertext attack (CCA), when a proper padding scheme is not used. Recall that in an IND-CPA game, the challenger is given two plaintexts, suppose they are ...


7

I work for Security Innovation, which owns the NTRU patents. All NTRU-related patents are freely usable under GPL 2.0 and 3.0 -- in other words, they should fit in with your license requirement as given above. If you have specific license requirements beyond GPL please let me know and we'll accommodate them if we can. There's an open-source C and Java ...


7

According to current knowledge, handing out multiple public keys (with independent numerators) for the same private key $f$ is not insecure, as long as the parameters are instantiated appropriately. There is some small loss in concrete security, but nothing like an efficient attack is known. The standard NTRU lattice for just one public key $h$ is \begin{...


6

No, this system is not secure. Knowledge of the private key immediately gives enough of the public key that we can immediately encrypt an arbitrary message. The NTRU decryption key includes a polynomial $f$; the encryption key is essentially $f^{-1}g$, where $g$ is a polynomial with coefficients in the set $(0, p, -p)$. Anyone with the private key can ...


6

Properly speaking, forward secrecy is a property of a protocol. The protocol is forward secret if compromise of the long term keys does not allow an attacker to decipher any past communications. (Occasionally a distinction is made between that and perfect forward secrecy, with the latter secure when the attacker also knows e.g. all other session keys.) You ...


6

An NTRU public key is a polynomial of degree $d-1$ whose coefficients are elements in $\mathbb{Z}_q$. So the number of bits you need to represent it is $d\log{q}$. If q is of the same order as d, then this gives you $d\log{d}$. The private key, on the other hand, can be represented with $O(d)$ bits since the coefficients are all in the set $\{-1,0,1\}$.


5

Usually, in public-key cryptography, the "key size" is implicitly referred to the size of the public key. In the case of NTRU, both public and private keys are conveyed by the same thing: polynomials defined over a specific polynomial ring. These polynomials can be represented as vectors in $\mathbb Z_q$ of size $N$. Therefore, raw public and private key ...


5

According to Wikipedia: Alice, who wants to send a secret message to Bob, puts her message in the form of a polynomial m with coefficients {-1,0,1}. In modern applications of the encryption, the message polynomial can be translated in a binary or ternary representation. So, lets say you have a message encoded in base 2 as 101101, you'd set the ...


5

I've thourgh that 439 would represent the key size in bits. No, NTRU doesn't measure things like that. Instead, it's the number of elements in a ring. In addition, with the current parameter sets, each ring element is a value between 0 and 2047 (11 bits), and the public key consists of one ring, and so it takes up $11 \times 439 = 4829$ bits, which ...


5

Poncho's explanation is correct: the size is $N \log_2(q)$ rather than just $N$. A better open-source implementation to use is here: https://github.com/NTRUOpenSourceProject/ntru-crypto -- this is the implementation endorsed by the inventors of NTRU and by Security Innovation, which owns the NTRU patents (and which I work for). It should be preferred to ...


4

When an embedded device needs asymmetric crypto to encrypt, (e.g. measurements it makes) or check authenticity (e.g. of commands or firmware updates it receives), there is no need for a private key or key generation in the device, and nothing beats RSA and Rabin on simplicity and speed (for RSA: with $e=3$, which is safe when used with proper padding); plus ...


4

The claims made are pretty much all nonsense or do not represent an accurate understanding of the state of the art. I'm not going to go into a point-by-point response; suffice it to say that I would not trust any advice or representations they may make about what is or isn't secure. Their system might be fine, or it might not be, but their public ...


3

No, this result (as it stands) is of no practical use against NTRU as typically used. To quote the paper: Note that there is a large value hidden in the o(1) term, so that our algorithm does not yield practical attacks for recommended NTRU parameters. In addition, while it is subexponential, it's just barely so; they estimate the time as $2^{ (\ln 2/2+o(...


3

I've searched about this problem these two days, considering the paper cygnusv mentioned, and finally after reading the problem related to the pqc implementation, I guess that's the condition which is not formally mentioned in NTRU papers. And this condition $$q > p(6d + 1)$$ must be true in order for the probability of unrecoverable messages to be less ...


3

In NTRUEncrypt, a raw message m of octet string of length l octets is encoded through the following steps: Padded it with a random salt of b byte and a few extra information to form the actual octet string M that is to be encrypted. This M byte string is then converted to a binary string Mbin using octect-string-to-binary-string-primitive (OS2BSP). In ...


3

I am a cryptographic researcher at Security Innovation, which acquired NTRU Cryptosystems. Now, I wonder what is the most efficient attack one could do? Does it have to be comprehensive like the meet-in-the-middle one? The most efficient attack (the terminology "best known attack" is often used here) is the hybrid attack of lattice reduction and meet-in-...


3

Yes, these are public parameters of the system. Note that NTRU is not implemented exactly this way any more. The most up-to-date current spec is EESS#1, which can be obtained from https://github.com/NTRUOpenSourceProject/ntru-crypto/blob/master/doc/EESS1-v3.1.pdf.


3

Might I suggest using traditional hybrid cryptography to cut down on the ciphertext growth size? This is the straight-forward approach where you don't directly encrypt the message with the public key; instead, you pick a random symmetric (e.g. AES) key, encrypt the symmetric with the public key, and then AES encrypt the message with the symmetric key. That ...


3

The decryption error occurs for the following reason. In a classical NTRU decryption you compute $c = e * f \pmod q \pmod p \\ \ \ = p r*h*f + m*f \pmod q \pmod p\\ \ \ = p r*g + m*f \pmod q \pmod p$ By construction $f = 1 \bmod p$. Therefore, if the all the coefficients of $(p r*g + m*f)$ are within the interval of $0$ and $q-1$, (or $-q/2$ and $q/2$, ...


3

what are the major differences between the IEEE 1363.1 NTRU standard vs. the NTRUEncrypt NIST PQ submission The only differences would be the parameters that are standardized. This answer gives one parameter set, specifically EES1087EP2. Unfortunately, the IEEE Std 1363.1-2008 document itself is behind a paywall, so I am unable to view the other parameter ...


2

To encrypt the message "hello world", using the ASCII conversion table (http://www.albany.edu/~yx152122/ASCII.pdf) you get the hexadecimal representation as 68 65 6C 6C 6F 77 6F 72 6C 64 and corresponding binary representation. Then convert to polynomial by adding powers of X h 01101000 X^3+X^5+X^6 e 01100101 1+X^2+X^5+X^6 l 01101100 X^2+X^3+X^5+X^6 l ...


2

Reducing mod 3 means indeed reducing each coefficient mod 3, and again we choose the representatives symmetrically around 0, so each coefficient becomes -1,0 or 1 (instead of, which is also possible, 0,1, and 2, or some other choice). $-7X$ becomes $-X$ because $-7 \equiv -1 \mod 3$. The starting constant 3, becomes 0, and disappears, $-10X^2$ becomes $-X^2$...


2

What you are looking for is explicitly specified in the IEEE Standard 1363.1 [1], which covers NTRU. In particular, encoding a bit string into a polynomial is done in the following manner: Once you have processed the input message, you divide it into blocks of 3 bits, and transform each block in a pair of coefficients of a ternary polynomial according to a ...


2

Yes. I'm not sure why others are saying "no". Forward secrecy is usually done by simply creating ephemeral keys for each connection. Thus, you will simply require a different NTRU keypair for each connection. Another, related, question is "how fast is NTRU keypair generation?" Since forward secrecy requires the frequent creation of ephemeral keys, this ...


2

There is a very easy way to get Perfect Forward Secrecy with the Post Quantum Security of NTRU (if you believe NTRU is secure). However it requires TWO exchanges of information. During Exchange 1 both parties generate and exchange ephemeral NTRU keys. During Exchange 2 both parties generate random numbers and encrypt their random numbers with the other ...


Only top voted, non community-wiki answers of a minimum length are eligible