Public key cryptography - public key encrypts and cannot decrypt? I understand the basics behind public key cryptography, in that each party has two keys - the public one encrypts, and the private one decrypts. What I cannot figure out is, How does the public key encrypt and not decrypt, but yet the private key can decrypt?I do understand the possibilities of this, but, does anyone know what cipher can do this, and how does this practically operate?

How it works depends on the cipher, but the basic idea is that of a trapdoor function.

  A trapdoor function is a function that is easy to compute in one direction, yet believed to be difficult to compute in the opposite direction (finding its inverse) without special information, called the "trapdoor".

Many number theoretic problems have been used in the past successfully to build such functions, and the wikipedia article is fairly good.

Let's take one as an example, lets say the problem of factoring a number into it's prime factors. Every number can be uniquely broken up into a product of primes. It turns out though, that breaking a number up into its prime factors is difficult if the number is large enough and the factors are large enough, but give me a few large prime numbers and I can easily compute the composite that those numbers make up.

So, how can this be leveraged with cryptography? I choose say two large prime numbers called $p,q$ and set $n=p\cdot q$. I then set $e=65567$ and give you $e,n$. I then use my extra information ($p,q$) to compute $d$ such that $ed\equiv 1\pmod{\phi(n)}$. This can only be efficiently computed if you know $p$ and $q$.

You have $e,n$, so to send me a message $m$ you compute $c=m^e\bmod{n}$ and send $c$ to me. For me to get $m$ back, I must know $d$, I can only know $d$ if I know $p,q$ and you knowing only $n$ and $e$ cannot compute $d$.

To get $m$ back I compute $c^d\equiv (m^e)^d \equiv m^{ed} \equiv m^1 \equiv m\pmod{n}$, so I have successfully used my extra information to recover $m$, something you cannot do without the extra information.

The public key can encrypt (it is the forward direction of the "one-way function"), but cannot decrypt because it does not know the trapdoor information to go in the reverse direction.

The cipher described here is RSA. There are others, but RSA is pretty simplistic.


Cryptography resources for programmers As a senior programmer entering blockchain projects, i'm looking for a comprehensive introduction to relevant cryptographic tools/primitives, preferably one that puts less emphasis on the math and more on the usage.

Are there recommended resources for the mathematically uninitiated?

Sorry, I don't want to be trivial, but, aside from different implementations, interpretations, enhancements, splits, forks and fake actors, imho, I think that the foundations are all in the original Satoshi Nakamoto's Bitcoin paper and relative references.

I think that is the best starting point to understand mechanisms under the hood.

Bitcoin: A Peer-to-Peer Electronic Cash System


SHA1 - SSL/TLS Cipher Suite SHA-1 is on the way to deprecation, in particular for digital certification (x509). But I can't find ressources about SHA-1 deprecation from SSL/TLS Cipher Suites.

Is it implicit, as deprecation implies that SHA-1 usage will be deprecated in all cases ? Or is there a different strategy concerning SHA-1 usage in Cipher suite ?

I also don't understand how attackers could forge SHA1 certificate signature, as the hash is still "protected" by the signature (CA private key). So forging the hash with collisions, ok, but one would detect that hash is not trusted anymore (signature wouldn't be the same). I miss something ?

Ciphers don't use signature schemes. They do use MACs, which are different (and employ HMAC variants of hash functions, e.g. HMAC-SHA1). There is no danger in using SHA1 in this manner (or MD5 either, but I wouldn't advise doing that if you can avoid it). TLS 1.0 and TLS 1.1 also use SHA1 and MD5 internally, but this is still considered secure because they use them differently than certificates do. The main reason SHA1 is becoming deprecated is because  the community believes attackers may someday soon gain the ability to forge SHA1 certificate signatures.


How does pairing letters increase the security of a substitution cipher? Hello can someone help me to understand this :

  One way to reduce this problem is to increase the size of the cipher alphabet. Rather than considering our cipher alphabet to be just the 26 letters, each with a single keyable transformation to ciphertext, we could instead use pairs of those same letters, and have at least 26 x 26 = 676 transformations. This vast increase in keyable transformations makes the code harder to create and store, but also decreases the number of times each individual transformation might be used

In a simple substitution cipher you have a mapping of 26 letters like following:

A -> M
B -> Z
C -> V

The statistics for English texts shows that letter E has frequency 11.162%, T - 9.356%, A - 8.497%, etc. An attacker computes frequency for each letter in the encrypted text. If the text is long enough, then a symbol with frequency about 12% is very probably E, a symbol with frequency  about 8% is very probably A, etc. In the example above suppose the text is long, and the frequency of M is 8.2%. Then the attacker will fist suppose that M in the encrypted text corresponds to A in the original text. The same for other letters. In the reality the frequency will deviate from this, and the attacker will test some other variants. Despite this the number of combinations that he will test will be relatively small, compared to a straightforward brute-forcing of 26! (1x2x3x4x5...x24x35x26).

You text about 26 x 26 means that they suggest not to replace a letter by letter, but a pair of letters to another pair of letters, like following:

AA -> GH
AB -> DT
AC -> LQ
...
BA -> BM
BB -> KA
BC -> OJ
...
ZY -> ZG
ZZ -> WM

There are 26 x 26 = 676 pairs mapped to other pairs.

For pairs the frequencies are also known and in case of long message or if attacker has many short messages, they still can be relatively easy decrypted. But for short texts it it can be hard.

Suppose the message has length 2600 symbols. In case of simple mapping it means that each letter on average is used 100 times. The correlation of frequencies with known values can be very high and decryption can be very quick.

But suppose this message was encrypted with polygraphic substitution of 676 pairs. Each pair will be used on average less than 4 times. That's why deviations of frequency of each pair from the known average values will be high. The attacker will have to test much more candidates for each pair. The amount of computations can be much higher than in case of simple substitution. Thus if the attacker has not sufficient resources (not enough computation power, not enough time), this can help to keep the message encrypted.

In serious cases, when encrypted message is valuable, more resources can be involved and also such cipher can be more or less quickly brute-forced. And an attacker will use of course not only frequency, but all possible information. E.g. the frequency of combinations of 3-4 letters, the frequency of some words in the language.


Decrypting an encrypted text out of order Does there exist a cipher that can be encrypted twice with two different keys and then decrypted twice using either key first?

For example:

Plaintext is "Lemons are great!"
Encode with Key #1
Encode with Key #2
Decode with Key #1
Decode with Key #2
Result is "Lemons are great!"

To my understanding TLS does something like this, but I'm not sure. I've also tried reading about elliptical curve cryptography to no avail (of useful understanding, that is). I've also tried my own tests with OpenSSL but I feel like it's salting things and therefore is making it not work.

I understand this is possible with a ROT(n), but that's of course not considered cryptographically secure.

$\operatorname{ROT}(n)$ is also known as the Caesar cipher.

$\operatorname{ROT}(n)$ can be thought of as a character based stream cipher. It works because addition - the encryption method used - is commutative. In other words

$\operatorname{ROT}(x, \operatorname{ROT}(y, m)) = \operatorname{ROT}(y, \operatorname{ROT}(x, m))$.

Another well known commutative function is $\operatorname{XOR}$. It is used by the one time pad, but - more practically - also for block ciphers in streaming mode.

So you can encrypt using AES in CTR mode using two different keys in any order and get the same ciphertext. And decryption will work in any order as well.

Note that you should use an IV or nonce if you reuse the keys. Reusing a key stream generated from the key and IV breaks confidentiality. Together with $\operatorname{XOR}$ it breaks the scheme as you can XOR out the key stream.


Security proof. Adversary source of random coins. Consider the game-based security proofs, i.e. a game played between the challenger and a PPT adversary.

My question is... what is the source of random coins for the adversary?
Is is valid to say that the challenger provides the coins to the adversary?

"If" the challenger is the one giving the coins to the adversary, then I assume it will be possible for the challenger to initialize the adversary on the "same" coins and expect a deterministic behaviour.

If someone has a link for further explanation it would be really healpul.
Thanks a lot.

It certainly wouldn't make sense for the challenger to provide the coins. If you are working with non-uniform adversaries, then you can assume that the adversary is deterministic. This is due to the fact that $BPP \subset P/poly$. Intuitively, a non-uniform adversary can receive as "advice" the best random coins that maximize its probability of winning the game. However, if you are working with uniform adversaries, then you cannot assume that the adversary is deterministic.

Note, that as part of the proof, if you need to somehow simulate something for the adversary, then you can always fix its random tape to a uniformly chosen string and then work with an effectively deterministic adversary. However, this is different to having the "challenger" in the game provide the coins; that would make no sense.


How do ciphers change plaintext into numeric digits for computing? For example, in RSA, we use this for encryption: $ciphertext = (m^e \mod n)$  and for decryption.

If our message is "hello world", then what number do we have to put as $m$ in the RSA formula?

Say you want to encrypt "Hello World" with RSA.

The first important thing here is the encoding of that text. "Hello World" as such cannot be encrypted since characters are a non-numerical concept.
So an encoding is used convert the characters of that text to numeric values (e.g. the ASCII / Unicode table, but there are many others, especially for non-latin characters). Using Unicode-8, "Hello World" turns into this sequence of bytes (hex-notation):

48 65 6C 6C 6F 20 57 6F 72 6C 64

Such a sequence of bytes can then be interpreted as a number by assigning a most-significant and least-significant byte (e.g. the more left-sided, the more significant). That sequence would then equal the number

0x48656C6C6F20576F726C64 or 87521618088882538408046480

But since such a small number would not produce a secure ciphertext (as @SEJPM already said), a padding is applied. The sequence of bytes then might look something like this:

01 48 65 6C 6C 6F 20 57 6F 72 6C 64 98 9C 38 83 E1 64 E7 0B BC F2 43 C0 6B
26 D4 5E AC 9B C9 DC 2F 1B 87 46 3D 2E 6F 86 66 5E 1B CB 44 DA 5A 50 79 2F
40 79 88 83 84 3E 16 9D 7F 1F 05 2C DF F2 9B 9B 07 11 F6 7A CB 1C 35 9B 76
BD 8D 46 1C E0 09 2A 9F C5 B8 A9 FB 61 41 ... up to the bitsize of N

That sequence is then interpreted as a number and shoved through the algorithm.


Generate random in secure message transfer I’m doing a school assignment about secure communications between a Server and a Client.
Basically, messages are exchanged between the clients and the server and these communications must implement confidentiality, authentication, integrity and non-repudiation.

Imagine I have to send a message from the client to the server. This is what I’ve idealized:

Client and Server both generate their public/private keys;
Their public keys are shared between them;
Client, generates a session key using 'AES';
Client encrypts the message using the session key and sends this to the server;
Client encrypts the session key with the Server public key and send this to the server;
Client creates a hash of the message and encrypts this hash with the client's private key and sends this to the server;
Server uses is private key to get the session key;
Server uses session key to decrypt the message;
Server decrypts the hash with the client's public key;
Server creates hash of message and compares with the above hash.

I’m thinking of creating a new session key every time the Client sends a message to the Server.

Is this the way it should be done?
In the generation of the keys I have to use a random number. How do i do this?

My thoughts for #2 are:

KeyGenerator keygen = KeyGenerator.getInstance("AES");
keygen.init(128,new SecureRandom());

Or this:

KeyGenerator keygen = KeyGenerator.getInstance("AES");
keygen.init(128,  System.nanoTime());

Or should I use other way? I'm asking this because I don't know the best way to generate the seed.

You can use the well established TLS (Transport Layer Security) protocol to achieve the first three properties and modify it to include a digital signature for non-repudiation*. However, strictly speaking, non-repudiation requires the use of certificates from a CA so that the signature can be verified by any third party.


Turning PRPs in PRGs with a counter I am following the Coursera Cryptography I course and I have the following question,

I am a bit perplexed by the statement, in week 2 lecture "What are block cyphers?" that a counter-mode PRF is a secure PRG.

PRPs are PRFs, and PRPs have the property that if (x₁, x₂) ∈ X, x₁ ≠ x₂, then PRP(x₁) ≠ PRP(x₂) -- since they are invertible.

Using a PRP in counter mode results in a series of values which are all different from each other. Now -- this is not random. In fact, we can see that, in the case of a 128 bit PRP, for example, after 2⁶⁴ different output it is actually more likely to get a repeat than not. However the PRG we created won't have this behavior and we would be able to distinguish them.

In other word, wouldn't this PRG susceptible to a birthday attack?

You are quite correct.  A PRP in counter mode is, in fact, distinguishable from a random sequence if you approach the "birthday bound".  We get around this by never generating that much output at once.  With a 128 bit block cipher, an output of $2^{40}$ bytes (which is a lot of output) gives us a distinguishing advantage of about $2^{-56}$ (the probability of a random sequence of blocks of that length would have a repeat) -- this is small enough that we don't worry about it.


Chosen ciphertext insecurity in an ElGamal variant I'm trying to prove something and if I can show that there is a simple way to calculate $(g^a \bmod p)^k$ if I know both $g^k \bmod p$ and $g^a \bmod p$, then (I think) it will help me prove it, but I'm not able to see an obvious way to use the two expressions to calculate the other. Is there a property in modular arithmetic that would allow for that? Or does it seem clearly untrue? I think there may just be some gaps in my knowledge about modular arithmetic so if you have a resource for that you'd like to point me to, that might also help.

If it makes a difference, the broader question I'm trying to solve is the following. We consider a modification of the ElGamal cryptosystem (called the basic ElGamal cryptosystem) where we have $p$, a prime, and $q$, a prime divisor of $p-1$. We have $g$, an element of order $q$ in $\mathbb{Z}^*_p$. The private key is an integer $a$ chosen randomly between $1$ and $q-1$. The public key is $h = g^a \bmod p$. And the ciphertext is $c=\langle c_1, c_2\rangle$ where $c_1 = g^k \bmod p$ and $c_2 = m \, h^k \bmod p$, where $k$ is random between $1$ and $q-1$. I need to prove that this is insecure under a chosen ciphertext attack (and whether it is insecure based on total break, one-way security, semantic security).

Since I know that the regular ElGamal cryptosystem is semantically secure if the Decisional Diffie-Hellman (DDH) assumption holds, I thought that if I can prove that it doesn't hold here, I can show that it is not semantically secure. That's why I wanted to ask this question but if this doesn't make sense as a way to show this, let me know so I can try something else.

There is no known way to compute $(g^a)^k \mod p = g^{ak} \mod p$,

given only

$g^k \mod p$ and

$g^a \mod p$

as per the Decisional Diffie–Hellman assumption. This is roughly equivalent to the discrete log problem. This is described in more detail in this paper.


Non-repudiation isn't a part of cryptography? According to the "Handbook of Applied Cryptography" by Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone (CRC Press, 1997; p.4):

Cryptography is the study of mathematical techniques related to
aspects of information security such as confidentiality, data
integrity, entity authentication, and data origin authentication.

My questions are: Why doesn't non-repudiation appear in that definition? Is it less important? Isn't non-repudiation one of the aspects of information security?

That is clearly a simplified definition, as cryptography encompasses a large number of ideas. It is likely for the same reason that they do not mention zero-knowledge proofs or proof-of-work systems, despite those very often falling squarely in the relm of cryptography.


What does universal look like? What is the complexity(size/depth) of universal circuit I was reading a paper about attribute based encryption. The authors showed that ciphertext-policy ABE can be constructed from key-policy ABE using universal circuit. But the universal circuit should be in the circuit space supported by CP-ABE. So what is the complexity of universal circuits?

The state of the art in optimizing the efficiency of universal circuits is, to my knowledge, this paper. At a high level, a universal circuit to evaluate any size-$s$ circuit has size $O(s\cdot \log s)$ I guess the depth should be roughly similar ($O(s\cdot \log s)$), since a size-$s$ circuit can have depth-$s$ in the worst case, and we do not know of generic techniques to reduce the depth of a circuit while increasing its size by only a logarithmic factor.


Why would you use a weaker hash function than cipher strength? Some cryptographic libraries (like “Bouncy Castle”) support many modes where the maximum number of bits which can be produced by the hash are significantly fewer than the cipher strength.  For example:

MD5 (128 bit max) is paired with 256 Bit AES
SHA1 (160 bit) max is paired with 256 Bit AES

What benefit is derived from using 256 bit AES over 128 Bit AES in cases like this?

Well, firstly, SHA-1 still seems to have 160-bit preimage and second preimage resistance, so using it in HMAC requires more than 128-bit AES keys to get equivalent security.

AES 192 would be sufficient, but isn't used in e.g. TLS – RFC 3268 says:

  The AES supports key lengths of 128, 192 and 256 bits.  However, this
     document only defines ciphersuites for 128- and 256-bit keys.  This
     is to avoid unnecessary proliferation of ciphersuites.

So with AES and SHA-1, you can pick between either MAC security (AES-256) or cipher security (AES-128) being the limiting factor.

As for MD5, there are no TLS cipher suites with AES + MD5 at all. In the case of password-based encryption, where a combination of MD5 and AES-256 is defined in Bouncy Castle, it's definitely a legacy algorithm.

In general, there's a difference between the integrity offered by the MAC (which the hash functions are used for here) and the privacy offered by the cipher. If you valued privacy above integrity, you could have a higher minimum security you desire from the cipher. An attack on the MAC would frequently have to be online, while an attack on the cipher could be done offline, even years after the fact.

Also, the MAC length requires space in each message, while the key length of AES does not, so you might want to use a short MAC even if you were fine with long keys and the resulting processing time.


Information security evaluation I saw this exercise for evaluating the security(confidentiality, integrity, authenticity, and non-repudiation) of some schemes:

ENC(M) || SignA(ENC(M))
ENC(M || SignA(M))
SignA(ENC(M))
ENC(M) || SignA(M)

Where || is concatenation and ENC (is encryption on secure shared key) and SIgnA is RSA Signature of Alice.

My answer is :

Have confidentiality (from ENC), and authenticity from signature, but no integrity because i have the signature of ENC (so someone can use forgery on my signature) and non-reputation i don't think (but i m not sure).
This have all property, because ENC give confidentiality, signature authenticity e non repudation and integrity because i have message and his signature for verify.
In this schema i have confidentiality and authenticity , but no integrity. I m not sure about non-repudation.
With this schema i have confidentiality, integrity and authenticity. I have again doubt about non-repudation.

I m not so clear if autenticity implies non-repudation (using signature).

Anyone can help me on this stuff?

ENC(M) || SignA(ENC(M))
  Have confidentiality (from ENC), and authenticity from signature, but no integrity because i have the signature of ENC (so someone can use forgery on my signature) and non-reputation i don't think (but i m not sure).

Confidentiality is yes because of ENC, correct.

The other's are all linked to each other. They are present if the receiver only accepts signed messages and the verification is performed with the trusted public key of Alice. If a public key of an adversary is accepted then any random ciphertext can be created and signed.

Non-repudiation is not accomplished because the secret key is not signed together with the message. If the receiver uses a different key you'd get a different message after decryption, even though the signature over the ciphertext verifies. So it is NO for non-repudiation and YES for confidentiality and message integrity / authenticity.

  ENC(M || SignA(M))
  This have all property, because ENC give confidentiality, signature authenticity e non repudation and integrity because i have message and his signature for verify.

But yes, basically right. Note that if the encryption scheme is vulnerable against e.g. plaintext / padding oracle attacks that the confidentiality breaks down. This scheme is what we usually do.

  SignA(ENC(M))
  In this schema i have confidentiality and authenticity , but no integrity. I m not sure about non-repudation.

The message is not send (!), so it is kept very confidential. You cannot even guess it, because the signature is over encrypted data. Integrity / authenticity are then of course nonsense. Non-repudiation is also not possible.

Unless somebody is able to get the original message and encrypt it again anyway. But usually only the given message are allowed (or you'd have issues with DoS and replay attacks and whatnot).

  ENC(M) || SignA(M)
  With this schema i have confidentiality, integrity and authenticity. I have again doubt about non-repudation.

Wrong! You can guess the data and verify the signature. If it verifies, you've found the data. We commonly assume that the public key is known to all.

Once you've decrypted you have M, SignA(M) so there is your non-repudiation - and therefore integrity & authenticity.

Again: if the encryption scheme is vulnerable against e.g. plaintext / padding oracle attacks that the confidentiality breaks down (even more significantly for complex messages).

Beware that generally these kind of questions are debated for "perfect" schemes, where E is perfect cipher and SignA cannot be broken. Furthermore, no other communication or actions are allowed other than the one specified.

I've already mentioned the oracle attacks and what could happen if the message was send afterwards. Those situations can and should be disregarded when answering the questions, even if they are definitely worth considering when implementing such a scheme in practice.

The reason is that you first need to get down the security of perfect schemes and can then on designing or analyzing systems based on the security claims. Then the next thing to do is to consider the practical systems. I'm however already very much rooted in practical application, so my brain starts to automatically insert warnings when looking at the schemes.


How to prove the PRF, $F(k,x) = (k \wedge x ) \oplus k$ is PRP? I am trying to understand PRF's and PRP's. I have got a question where I have to decide whether $F(k,x) = (k \wedge x ) \oplus k$ (where $k$ and $x$ are simple $1$ bits (1 or 0)) is PRP or not. I am not sure if I understand PRP's correctly. As I have found:

  A Pseudo Random Permutation is a PRF that happens to have the property that every element in the input domain has a single associated member in the output co-domain and vice versa.

So what I have got in my example.

k x F(k,x)
0 0 0
0 1 0
1 0 1
1 1 0

For each couple, I have an associated member in output co-domain, but for each output 0 and 1. I do not have a unique member in the input domain. So this function is not PRP. Am I right?

Your definition tries to say that a permutation must be invertible.

When the key is $0$, we can not determine the inverse of 0 and the inverse of 1 doesn't exist.


Convert a state-dependent hash-based signature scheme into a stateless message-dependent one Suppose we have an XMSSMT instance that is capable of signing up to 2^60 messages securely when given some state-dependent information, I could envision making it stateless as follow:

Hash the message and truncate the digest $t$ to 60 bits.
Split $t$ into $d$ (Hypertree layers) chunks and interpret as integer leaf indicies at every layer.
At each layer, each leaf signs a WOTS+ public key generated from a seed created by encrypting the leaf index.

Obviously this would reduce the security of the scheme from acceptable to merely 30 bits, because the signing key is selected based on a 60-bit hash digest.

Q1: Can this be salvaged by using some unique-mapping function? Or we have a better chance rely on UTC time or use SPHINCS-family schemes?

Q2: What benefit can we get out of using XMSSMT over SPHINCS-family schemes?

Can this be salvaged by using some unique-mapping function?

A "unique-mapping function"; that is, a hash function that somehow never gets a collision???

  Or we have a better chance rely on UTC time

Which means that it's still stateful (it's just that the state resides in the time)

  Or use SPHINCS-family schemes?

Actually, what you propose isn't that far off of Sphincs+ (or Gravity Sphincs); both take your general approach of taking the message, hashing it, and using that value to select the path through the hypertree (or, as you put it, interpret as integer leaf indicies at every layer).  The difference is that, at the bottom, they use a Few-Time signature scheme rather than a one-time signature scheme (and so the hypertree doesn't have to be so tall as to make collisions improbable; they just need to make sure that you are unlikely to get too many collisions at the same spot).

  What benefit can we get out of using XMSSMT over SPHINCS-family schemes?

Well:

The signatures are considerably smaller
The signature generation time is considerably faster (and the generation time for the related LMS scheme is faster still)


How is HKDF-Expand better than a simple hash? Why do we need HKDF-Expand  if we can simply hash the pseudorandom key to make it longer? The docs (in the link) say:

  The second stage "expands" the pseudorandom key to the desired
  length...

Is it only to allow for longer keys? So that if all we need is, say, 32 bits - we can simply use SHA256? Or is there another need to it?

Short: In some simple cases, hash could be adequate. However, HKDF is intended to be a generic construct you can commonly apply for needs requiring Extract-Expand (such as when you have a shared secret agreed using DH or ECDH). It aims to be largely compatible with existing practices and thus makes it easy to apply the same pattern to multiple uses. It allows simple extensibility (for instance if you need to output more key material in future)

HMAC-based key derivation is commonly used instead of Hash-based key derivation because:

In some uses of Hash-based key derivation there is risk of length extension attack (by choosing $OtherInfo$ field correctly).
When using hash for key derivation there are often multiple fields to concatenate (like previous hash, secret, info, counter). This is bad, because it kind of mixes together key data that is to be protected and other non-critical data (which is often known by the attacker). With PRF (pseudo-random function), it is possible to keep key and the other data separate.
The standard constructs for key expansion, the ones defined in standards like NIST SP 800-108 or IKEv2 already are PRF-based (use HMAC function).
Security features of PRF-based constructs can be easily proven using Random Oracle. (Though such proofs are only approximations of reality if using HMAC-SHA-X.)

In case of HKDF-Expand, using HMAC to implement HKDF-Extract means that both extraction and expansion stages are more similar if both of them are based on HMAC. For using HMAC in HKDF-Extract stage, Krawczyk has provided good rationale in Cryptographic Extraction and Key Derivation: The HKDF Scheme. Especially interesting may be the chapter 8, which compares HKDF against more traditional constructs.

In case of using, HKDF-Expand when the output size is just one block and no info is used (it is empty string), the function will reduce to (assuming 32 bytes output is needed):

$HKDF\text{-}Expand(PRK, info, L) =
HKDF\text{-}Expand(PRK, "", 32) = HMAC\text{-}SHA256(PRK, 0x01)$

This is somewhat more complex, than e.g. $SHA256(PRK)$, but using such as key derivation function would no longer be compliant with the most important standards (NIST SP 800-108, RFC 5869/HKDF).

Overall, this way of doing key expansion appears extensible, good practice, well proven and deployed in practice. I would use HKDF-Expand (or NIST SP 800-108 KBKDF) instead of any home-baked scheme, and feel more secure on selection of algorithm, and know that it will better serve me even if needs will change in the future.


What is the difference between $\in$ and $\in_{\small R}$? I have a simple question about basic math. When I read different papers bout ABE, I see different methods to choose a random exponent.

What is the difference between the following options?

Choose a random exponent $\,a \in \mathbb Z_p$.
Choose a random exponent $\,a \in_{\small R} \mathbb Z_p$.
Choose a random exponent $\,a \in \mathbb Z^*_p$.
Choose a random exponent $\,a \in_{\small R} \mathbb Z^*_p$.

As the comments pointed out $a\in_{R} M$ means picking a sample $a$ uniformly from some set $M$. If a non-uniform distribution is implied, this will be stated.

In case you are also asking about it, $\mathbb{Z}_p^\ast$ is the multiplicative group (nonzero elements) of the integers modulo $p.$ In general
$$
\mathbb{Z}_n^\ast=\{k: k \in \mathbb{Z}_n, \gcd(k,n)=1\}
$$
is the multiplicative group over the integers modulo $n,$ made up of exactly the integers $k$ such that $\gcd(k,n)=1,$ and there are $\varphi(n)$ of them. Of course $\varphi(p)=p-1.$


How to generate a random integer in interval $[1, 2^n-1]$ from random integer in interval $[0, 2^n-1]$? For a project I am working on, I have access to a CSPRNG that outputs a random integer in the interval $[0, 2^n-1]$ for any integer $n$ greater than 0. I cannot use the zero values, so I have my RNG code in a while loop that runs until the random number is !==0. For small $n$ it is very likely that the while loop will run more than once, even more than twice (for $n=8$, the probability is $1/65536$). While this is not the bottleneck in my program, I want to eliminate the while loop and replace it with a linear transformation on the the generated random integer to get the integers I need in $[1, 2^n-1]$.

Is there a transformation that can be performed on the interval $[0, 2^n-1]$ to yield integers in $[1, 2^n-1]$ while retaining the uniform distribution of the random numbers?

(Would this be better posted in math.se?)

Assuming that $n > 1$ so as to avoid a trivial special case,
there is no function $g(\cdot)$ (linear or otherwise)
that will transform a discrete random
variable $X$ uniformly distributed on $\{0,1, 2, \ldots, 2^{n}-1\}$
into a discrete random variable $Y$ uniformly distributed in
$\{1, 2, \ldots, 2^{n}-1\}$. This is because each value of $X$ has probability $2^{-n}$
attached to it, and this gets mapped onto the $Y$ value $g(X)$. Thus, for any
$m \in \{1, 2, \ldots, 2^{n}-1\}$, $P\{Y=m\}$ is necessarily an integer multiple
of $2^{-n}$ including, possibly, a zero multiple.  It follows that the best
one could do is to get a random variable $Y$ that takes on
all values in $\{1, 2, \ldots, 2^{n}-1\}$ except one with equal probability
$2^{-n}$, and this exceptional value occurs with probability $2\times2^{-n}=2^{-(n-1)}$.

On the other hand, if $X$ were a continuous random variable uniformly
distributed on the interval $[0,2^n-1]$, the answer would
be easy: $Y = 1+\frac{2^n-2}{2^n-1}X$ is a continuous random variable uniformly
distributed on the interval $[1,2^n-1]$.


handling junk bytes in chi squared character freq analysis I'm doing the Matasano crypto challenges. After implementing a naive character frequency scoring (that worked), i was looking for something mathematically more precise and found this thread: Developing algorithm for detecting plain text via frequency analysis

While the Chi Squared analysis does work for me, I encountered a problem.
My current code just sets the score to infinity if I encounter a nonprintable character.
I want to avoid doing that, since a possible plaintext could contain a few ascii non printable characters. (for example it is actually unicode and contains a greek word)
But when I ignore every non printable character for scoring, as I already do with chars like ".,!\n\t", I run into the problem that strings with a few high scoring characters and lots of junk get scored better than actual english plaintext.

My current code is as follows: (frequency is a dict that associates ord(character) with its frequency for a-z and space)

import frequency
import copy
from math import inf
from string import printable

def score_string(inp):
exp_dist = copy.deepcopy(frequency.frequency)
length = len(inp)
for key in exp_dist:
    exp_dist[key] *= length
dist = dict.fromkeys(exp_dist.keys(), 0)
for char in inp.lower():
    if chr(char) not in printable:  # This is the part i like to avoid
        return inf
    if char in dist:
        dist[char] += 1
score = 0
for key in exp_dist:
    score += (dist[key]-exp_dist[key])**2/exp_dist[key]
return score

If I understand what is going on correctly, my issue is that for shorter strings (the example i worked with was 34 characters) the negative impact of even a single low scoring printable charater outweights the negative impact of a character that is ignored by the scoring by alot.

I'm looking for an elegant way of guaranteeing that nonprintables affect the score worse than any printable character but don't dismiss them completely.

One approach you might try is applying additive smoothing via pseudocounts.  At its most basic, this can be as simple as adding 1 to the number of times each byte (or $n$-tuple, or whatever) occurs in your corpus before calculating the frequencies.
 This allows you to calculate a non-zero (although possibly very small) likelihood for any decrypted byte string, even those containing bytes that never appear in your original corpus.

So, for example, if you started with a 1,000,000 byte corpus of English text, where the byte e occurs 124,319 times and the byte ` occurs 0 times, you'd increment those counts to 124,320 and 1 respectively, and the total number of bytes observed to 1,000,256, before dividing the counts by this total to obtain the smoothed frequency of each byte in the corpus (e.g. 1 / 1,000,256 ≈ 0.000000997 for the byte `).

The mathematical theory behing why this seemingly arbitrary adjustment makes sense is kind of tricky, but basically it turns out to be a sensible way to adjust the probabilities obtained from a series of observations to account for the possibility that some rare but possible outcomes might simply not have appeared by chance during the finite number of observations made.

(In particular, analyzed in the framework of Bayesian statistics, this smoothing rule turns out to yield the same expected posterior probabilities as we'd get by starting from a "flat prior", i.e. the assumption that any distribution of byte frequencies is equally likely, and repeatedly applying Bayes' theorem to update this belief as we observe new bytes in the corpus.  Furthermore, if we did have reason to believe a priori that some bytes should be more likely than others even before looking at the corpus, we could include this prior information by assigning the more likely bytes pseudocounts higher than 1.)

Of course, if you're using a given table of byte / letter frequences instead of compiling your own, you'd have to guesstimate the amount of smoothing needed yourself.  But you can still do it: just multiply each frequency by some assumed corpus size (e.g. 1,000), increment them by one and (if needed) rescale them back down so that they sum to one again.


Feasibility of finding public key when private key is known We all know that in a public key cryptosystem, given a public key it is extremely hard to compute private key from it.

Is it the same case in reverse?

Given a private key, how easy is it to compute public key out of it?

It would be great to have answers with respect to an algorithm like RSA.

In practice, no.

Firstly, RSA private keys are typically stored together with the public exponent. The standard definition includes the following information:

RSAPrivateKey ::= SEQUENCE {
  version           Version,
  modulus           INTEGER,  -- n
  publicExponent    INTEGER,  -- e
  privateExponent   INTEGER,  -- d
  prime1            INTEGER,  -- p
  prime2            INTEGER,  -- q
  exponent1         INTEGER,  -- d mod (p-1)
  exponent2         INTEGER,  -- d mod (q-1)
  coefficient       INTEGER,  -- (inverse of q) mod p
  otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

Obviously, if this is the information you got, deriving the public key is just a matter of extracting the fields modulus and publicExponent.

Secondly, the public exponent is typically a small pre-defined value, selected for making the public key operation as efficient as possible. Even if all information you got in the private key is modulus and privateExponent, it would be trivial to test the two most common publicExponent values $3$ and $65537$ and see if they check out. If not, the publicExponent is rarely greater than $2^{32}$, so checking every such odd value would still be feasible.

Checking if a known privateExponent matches a guessed publicExponent, is typically just a matter of performing a RSA encryption of arbitrary data with one key, and test if the resulting cipher text can be decrypted with the other.

Thirdly, should the publicExponent deliberatly be selected as a random value roughly the same size as the modulus, then deriving publicExponent from privateExponent and modulus, would indeed be as hard as deriving privateExponent from publicExponent and modulus. This is however not how RSA is typically used or how RSA keys are typically generated.


Why does the PKCS1 RSA private key structure contain more than just exponent and modulus? The ASN.1 spec for the PKCS1 RSA private key format is as follows:

RSAPrivateKey ::= SEQUENCE {
    version           Version,
    modulus           INTEGER,  -- n
    publicExponent    INTEGER,  -- e
    privateExponent   INTEGER,  -- d
    prime1            INTEGER,  -- p
    prime2            INTEGER,  -- q
    exponent1         INTEGER,  -- d mod (p-1)
    exponent2         INTEGER,  -- d mod (q-1)
    coefficient       INTEGER,  -- (inverse of q) mod p
    otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

As far as I understand, only the modulus and public exponent are required for encryption, and only the modulus and private exponent are required for decryption. Why does the key file contain all these additional fields and what are they used for?

It has to do with optimizing RSA.

It turns out that using the Chinese Remainder Theorem with $p$, $q$, $d\pmod{p-1}$, and $d\pmod{q-1}$ (i.e., prime1, prime2, exponent1, exponent2 from the data structure in the question) to run the decryption operation faster than if you only had $d,n$.

For more information on how it is done, I found this reference http://www.di-mgt.com.au/crt_rsa.html


Inverses in Truncated Polynomial Rings I've been trying a long time to understand a thing which is obviously extremely simple, but I just can't get it.
Read this, please:

The NTRUEncrypt PKCS uses the ring of truncated polynomials $R$ combined with the modular arithmetic described in Section 1. These are combined by reducing the coefficients of a polynomial a modulo an integer $q$. Thus the expression $$a \pmod q$$ means to reduce the coefficients of $a$ modulo $q$. That is, divide each coefficient by $q$ and take the remainder. Similarly, the relation $$a \equiv b \pmod q$$ means that every coefficient of the difference $a-b$ is a multiple of $q$.

This is taken from NTRU tutorial and that's quite understandable. But. Take a glance at the next excerpt from the same tutorial:

The inverse modulo $q$ of a polynomial $a$ is a polynomial $A$ with the property that $$a * A \equiv 1 \pmod q.$$
Not every polynomial has an inverse modulo $q$, but it is easy to determine if $a$ has an inverse, and to compute the inverse if it exists. A fast algorithm for computing the inverse is described in NTRU Technical Note 014, and a theoretical discussion of inverses in truncated polynomial rings is given in NTRU Technical Note 009. These notes may be downloaded from the Technical Center.
Example. Take $N=7$, $q=11$, $a=3+2X^2-3X^4+X^6$. The inverse of $a$ modulo 11 is $$A=-2+4X+2X^2+4X^3-4X^4+2X^5-2X^6,$$ since $$(3+2X^2-3X^4+X^6)*(-2+4X+2X^2+4X^3-4X^4+2X^5-2X^6) \\ = -10+22X+22X^3-22X^6 \equiv 1 \pmod{11}."$$

I do not understand how $-10+22X+22X^3-22X^6$ may be 1 (modulo 11). Why???????
The first excerpt adduced says that each coefficient of the polynomial minus 1 must be a quotient of 11. But it's not.  -10? That's not a problem. $-10 - 1 = -11$.  $-11 \bmod 11$ is 0, yes, it works, I agree. But how can it work with 22? $22 - 1 = 21$. $21 \bmod 11 = 10$, not 0. also it doesn't work with $- 22$. $-22 - 1 = -23$. $-23 \bmod 11 = -1$.  Can anyone, please, explain me this example?

$$(-10+22x+22x^3-22x^6) - 1 = -11+22x+22x^3-22x^6 \equiv 0 \mod 11.$$

When substracting a constant from a polynomial, you do not subtract it from every term, only from the constant term.

If you need a refresher, see addition and subtraction of polynomials.


Using the Babai's Naive Rounding algorithm to decode, in the conditions of the SIS problem, is secure? Given the SIS Problem: Given an integer q, a matrix $A \in \mathbb{Z}_q^ {n \times m}$ uniformly random, a real $\beta$, a syndrome $u \in \mathbb{Z}_q^n$, find a nonzero integer $e \in \mathbb{Z}^m$ such that $Ae=u \mod q$ and $ || e||_{2} \leq \beta$.

Sampling an uniform $A \in \mathbb{Z}_q^ {n \times m}$, along with a relatively short full-rank "trapdoor" set of vectors $S \in \Lambda^{\perp}(A)$ as in the paper of Ajtai of 1999 (Generating hard instances of the short basis problem). Choosing $ t \in \mathbb{Z}^m$ via linear algebra such that $At=u \mod q$ and using the Babai naive rounding algorithm with basis $S$ to decode $-t \in \mathbb{Z}^m$ to a point $v \in \Lambda^{\perp}(A) $ yields the solution to the SIS problem $e=t+v$. Therefore it is difficult to obtain $e$ right?

But on the other hand doesn't the attack of Nguyen and Regev of the GGH scheme ( Learning a Parallelepiped:
Cryptanalysis of GGH and NTRU Signatures ) work in this case?
Is this a contradiction to the SIS hardness? I'm wrong somewhere!

The Nguyen-Regev attack on GGH and NTRU works because those schemes were "leaking" the trapdoor S while signing. So after observing a certain number of signatures, their algorithm could recover S. So their attack had nothing to do with solving SIS, but rather with how to use the leaked information to recover a trapdoor (which can then be used to solve SIS). In the regular SIS problem, the S is unknown to the adversary and there is of course no "leakage" coming from anywhere.


Authenticated Encryption with smallest Overhead (Input and Output) I'm searching for the authenticated encryption algorithm that produces/requires the least overhead in total. This includes the authentication tag that it produces and the additional input that has to be sent along the message for a secure use of the algorithm in a communication protocol.

Let's take for instance GCM:
It requires a 96-bit IV which is usually split into a 32-bit explicit nonce and a 64-bit counter. The authentication tag has to be 128 bits long (according to Ferguson). Thus, the total overhead is 196 bits.

But what about other algorithms such as CCM or EAX, etc.? Can they use shorter IVs or are they also secure with 64-bit authentication tags? Do they have other vulnerabilities that affect the overhead? What about an even smaller 32-bit tag?

If there are more authentication encryption algorithms that require the some amount of overhead which is the one with the least computational effort?

I know this question might be related to this post. However, he wants to use AES-CTR and then do his own MAC computation with HMAC instead of using a single authenticated encryption algorithm. I'd just like to use one algorithm like GCM, CCM or EAX.

It (GCM) requires a 96-bit IV which is usually split into a 32-bit explicit nonce and a 64-bit counter.

GCM uses a 96 bit IV internally, but the size of the IV is actually configurable (implementations may vary, of course).

From the specification:

  $1 ≤ \operatorname{len}(IV) ≤ 2^{64}-1$.

however, the same specification also indicates:

  For IVs, it is recommended that implementations restrict support to the length of 96 bits, to promote interoperability, efficiency, and simplicity of design.

  Q: The authentication tag has to be 128 bits long (according to Ferguson). Thus, the total overhead is 196 bits.

The size of the authentication tag is also configurable, ranging from 64 bit to 128 bit in 8 bit increments. The shorter tag is just the leftmost bytes of the full 16 tag, so you can basically allow any size tag. The problem with GCM is that the security of the algorithm quickly diminishes for shorter authentication tags. Other algorithms will fare better.

  The bit length of the tag, denoted $t$, is a security parameter, as discussed in Appendix B. In
  general, $t$ may be any one of the following five values: 128, 120, 112, 104, or 96. For certain
  applications, $t$ may be 64 or 32; guidance for the use of these two tag lengths, including
  requirements on the length of the input data and the lifetime of the key in these cases, is given in
  Appendix C

  But what about other algorithms such as CCM or EAX, etc.? Can they use shorter IVs or are they also secure with 64-bit authentication tags? Do they have other vulnerabilities that affect the overhead?

Most authenticated ciphers - including CCM and EAX - are based upon CTR. They just require a nonce, which you can even send in a single byte or even bit, depending on the number of messages. You should study the specific API's how the IV is interpreted. CCM is a bit special in the sense that it also specifies the packet format, although that format is configurable with regard to various sizes.

CCM and EAX depend on (AES-)CBC-MAC and (AES-)CMAC respectively. These constructions are less vulnerable to smaller authentication tag sizes. Both are considered secure when used correctly.

  If there are more authentication encryption algorithms that require the some amount of overhead which is the one with the least computational effort?

There is always OCB mode. It has one block cipher operation per plaintext block and configurable output size. It is also patented and not available for military use (which means you get into a IP rights minefield if you use it).

Currently there are efforts on the way to use the the Keccak sponge for single pass authenticated encryption. That's still under construction though.

Finally there is SIV mode. SIV mode uses a synthetic IV calculated from the plaintext, which doubles as authentication tag. This means that, as long as your plaintext is unique, the calculated IV is unique and the mode is CPA secure and authenticated. SIV is however two pass, two full passes over the plaintext are needed during encryption. This means it is not online as many other modes.


Is it possible to reduce the size of an RSA key? The details about what an RSA key is made up of are explained succinctly here.

Is it possible to reduce the amount of data that's usually packaged with the (private) key and then derive it later?

If we want to compact an existing RSA private key expressed as $(N,e,d,p,q,d_p,d_q,q_\text{inv})$, we can reduce it to $(e,p,q)$ and easily recompute the rest as:

$\begin{align}
N&=p\cdot q\\
d&=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)\;\text{ or }\;d=e^{-1}\bmod((p-1)\cdot(q-1))\\
d_p&=d\bmod(p-1)\;\text{ or equivalently }\;d_p=e^{-1}\bmod(p-1)\\
d_q&=d\bmod(q-1)\;\text{ or equivalently }\;d_q=e^{-1}\bmod(q-1)\\
q_\text{inv}&=q^{-1}\bmod p
\end{align}$

It is possible to gain a few more bits; for example the low order bits of $p$, $q$ and $e$ are known to be set and need not be stored; further we know that $p\bmod6$ is either $1$ or $5$, thus it is enough to store $\lfloor p/6\rfloor$ and an extra bit, etc.. All in all, any RSA private key with $k$-bit public modulus $N$ and common (small) $e$ can be stored in about $k$ bits.

If we want a compact representation of private keys that we are free to choose, we can fix $e$ (removing need to store it) and decide to generate keys using some well defined deterministic procedure employing some Cryptographically Secure Pseudo Random Number Generator, and store the seeds of that CSPRNG, rather than the private keys. Whenever we need a private key, we (re)generate it from its seed. That has a performance issue, with workaround, see kasperd's answer.

If we'll generate $k$ keys of a certain size, without salt, we want to use use a (truly random) seed of at least $n+\log_2(k)$ bits, where $n$ is the security level corresponding to the public key size (perhaps $n\approx 112$ for 2048-bit RSA): we need to guard against the adversary enumerating seeds, generating the corresponding public modulus, and testing if it matches one of the public keys, which is expected to succeed after enumerating about $1/k$ of the seeds.

We can also use a passphrase, salt (user identifier), and a password-based key generation function, see this answer.


Why would splitting a password output be better than separate HMACs for encryption/authentication key derivation? In a recent question I asked here on crypto.se, an answer was given that surprised me a bit.

As mentioned in the referenced question, I'm looking to derive encryption and authentication keys from the output of scrypt. Since I can use nearly any output size I'd like in generating the output from scrypt. This leaves me two options for deriving the encryption and authentication keys:

HMAC the output in two different ways, ie: hmac(output, "e", sha256), hmac(output, "a", sha256); the e key is for encryption and the a key is for authentication, unsurprisingly.
Generate a very long output from scrypt by asking for a 512-bit output, and then split it for the key derivation for encryption and authentication.

Does any one solution fare better than the other in key derivation? I personally like the idea of using an HMAC better because then both the encryption and authentication keys use the entire key output as an input.

Internally scrypt has a huge state space, from which it derives 256-bit output blocks using PBKDF2-HMAC-SHA2, so it's basically already doing what you suggest as 1., just with much larger inputs. Adding another level of HMAC on top will not help.

In general, you need to be careful when chaining hash functions like $H_1(H_2(x))$. Both collisions in $H_1$ and those in $H_2$ lead to collisions in the combined hash. With a 256-bit hash you are still safe, however, since even doubling collisions gives you plenty of security margin.

If both are secure, but just using scrypt is simpler, why not use what's simple? That makes it less likely there's a mistake.


Cipher suites: same name, different IDs, why? Sorry if I missed with a community to ask.

Recently I stumbled on a fact that the same cipher suite can be designated by two different IDs, and this is not a typo nor single occasion.

For instance:
http://www.thesprawl.org/research/tls-and-ssl-cipher-suites

TLS_ECDH_ECDSA_WITH_NULL_SHA is 0x0047 and 0xC001
TLS_ECDH_ECDSA_WITH_RC4_128_SHA is 0x0048 and 0xC002
SSL_RSA_FIPS_WITH_DES_CBC_SHA is 0xFEFE and 0xFFE1
SSL_RSA_FIPS_WITH_3DES_EDE_CBC_SHA is 0xFEFF and 0xFFE0

And few others more, like TLS_ECDH_ECDSA_WITH_AES_128_CBC_SHA and TLS_ECDH_ECDSA_WITH_AES_256_CBC_SHA.

So, the question is: why two codes are used to designate the same cipher suite? Is it a marker of legacy (broken?) implementation to distinguish? Or just a merge of two standards? Or something else?

These numbers belong to ElasticSearch;

TLS_ECDH_ECDSA_WITH_NULL_SHA is 0x0047
TLS_ECDH_ECDSA_WITH_RC4_128_SHA is 0x0048
SSL_RSA_FIPS_WITH_DES_CBC_SHA is 0xFEFE
SSL_RSA_FIPS_WITH_3DES_EDE_CBC_SHA is 0xFEFF

and 0x0047 has almost 0% at tlsfingerprint.io
The second numbers in SSL/TLS in this format {0xC0,0x01},{0xC0,0x01},{0xFF,0xE1},{0xFF,0xE0}. The first two in rfc4492. These are deprecated in rfc8422. The last two is for private usage.
The implementations can have different control by the maintainers, therefore it is good to have different numbers. It is bad that your original source doesn't list where they took the numbers.

Note: in TLS 1.3, there are only 5 cipher suites with their id's;

{0x13,0x01} - TLS_AES_256_GCM_SHA384
{0x13,0x02} - TLS_CHACHA20_POLY1305_SHA256
{0x13,0x03} - TLS_AES_128_GCM_SHA256
{0x13,0x04} - TLS_AES_128_CCM_8_SHA256
{0x13,0x05} - TLS_AES_128_CCM_SHA256


Why is Approximate GCD a hard problem? There are many Fully Homomorphic Encryption over the Integers schemes whose security is based on the intractability of the Approximate GCD (AGCD) problem.

The paper Algorithms for the Approximate Common Divisor Problem surveys several lattice reduction based algorithms for solving AGCD. All of them require $t > \frac{\gamma - \eta} {\eta - \rho}$ samples to solve the $(\gamma, \eta, \rho)$-AGCD problem by reducing a particular $t \times t$ lattice.

In Section 5.2 of Fully Homomorphic Encryption over the Integers, the authors state a "rule of thumb" that lattice reduction algorithms acting on a $t \times t$ lattice take time roughly $2^{t/k}$ to output a $2^k$ approximation of the shortest vector.

However, LLL lattice reduction is known to run in polynomial time with respect to both the dimension of the lattice and the input sizes. Concretely, for the DGHV scheme where $(\gamma, \eta, \rho)$ ~ $ (\lambda^5, \lambda^2, \lambda)$, a quick estimation yields that $L^2$ lattice reduction can break DGHV in time $\lambda^{25}$ with memory $\lambda^{11}$ given $\lambda^{3}$ samples.

So why does the aforementioned paper treat the runtime of lattice attacks on AGCD as exponential?

The answer is that just because your algorithm is polynomial time doesn't mean it's fast.

The paper Algorithms for the Approximate Common Divisor Problem claims in section 3.1 that a lattice dimension $>800$ "should be large enough to prevent any practical lattice attack".

As a completely non-rigorous yet enlightening demonstration, we can compare the complexity of a brute-force the noise" approach with the lattice-based methods for $(\lambda^5,\lambda^2, \lambda)$-GCD.

The "brute-force the noise" approach involves $\mathcal{\tilde O}(2^{\frac{3}{2} \rho })$ multiplication/remainder operations on numbers with $\approx \gamma$ bits, where $\mathcal{\tilde O}$ is the usual notation hiding poly-logarithmic factors. So let's say it takes time $\propto \gamma \cdot 2^{\frac{3}{2} \rho } \sim\ \lambda^5 \cdot 2^{\frac{3}{2} \lambda } $.

The SDA lattice algorithm using fpLLL (aka $L^2$ lattice reduction) takes time $\mathcal{\tilde O}(\gamma^2 \cdot t^5) \sim \lambda^{25}$, where $t$ is the dimension of the lattice.

Let's compare these two asymptotic results for the choices of parameters in the paper Fully Homomorphic Encryption over the Integers with Shorter Public Keys. (See below for more details.)
At the "small" level, the time estimation for "brute-force the noise" is $6 \cdot 10^{16}$, and for SDA is $4 \cdot 10^{25}$.
At the "large" level, the time estimation for "brute-force the noise" is $7 \cdot 10^{24}$, and for SDA is $2 \cdot 10^{34}$.

So we'd need the coefficient hidden in $\mathcal{\tilde O}$ to be a billion times smaller for SDA than for "brute force" for lattice reduction to be practical -- and we just don't have that.

However, I cannot justify the "rule-of-thumb" asserted in Fully Homomorphic Encryption over the Integers and used in Fully Homomorphic Encryption over the Integers with Shorter Public Keys that LLL takes time exponential in $t$.

Experimentally, the runtime will appear to be exponential until your sizes  are large enough that the asymptotic behavior dominates.

Note that the reason for the inadequacy of LLL is not because it only gives an exponential approximation to the shortest vector. As Nyugen notes in Predicting Lattice Reduction:

  The most important fact is that asymptotically, all the algorithms known seem to only achieve an exponential approximation factor as predicted by theory, but the exponentiation bases turn out to be extremely close to 1, much closer than what theory is able to prove.

Furthermore, Algorithms for the Approximate Common Divisor Problem examine this limitation and find that the only effect is to require a mild increase in the number of samples (and hence the lattice dimension). This is because increasing the lattice dimension increases the size of the second shortest (independent) vector in the lattice. If the ratio between the sizes of the target vector and second shortest vector is sufficiently small, then LLL will find the target vector.

We can see this concretely for the parameters in the paper Fully Homomorphic Encryption over the Integers with Shorter Public Keys.
At the "small" level, $(\gamma, \eta, \rho) = (.86 \cdot 10^5, 1632, 24)$.
Ignoring the exponential approximation factor tells us we need $535$ samples. Accounting for it yields $546$ samples.
At the "large" level, $(\gamma, \eta, \rho) = (19 \cdot 10^6, 2652, 39)$.
Ignoring the exponential approximation factor tells us we need $7272$ samples. Accounting for it yields $9042$ samples.

Thus, for heuristic analysis of the lattice-based algorithms applied to AGCD, we can get away with pretending that LLL solves the Shortest Vector Problem.


What's the alternative should PKI collapse? Premises - please check it and critique if necessary:

If factoring the products of large numbers suddenly becomes simple, PKI goes up in smoke.

Is this correct?

If it is correct, it seems to me that the only alternative is a return to shared secret schemes… is there anything serious out there that still relies on shared secret (and not in a hybrid fashion like SSL)?

No, this is not correct.

Your fallacy here is to assume that a public-key infrastructure implies RSA. RSA is just a way of implementing an PKI.

There are other cryptographic schemes out there that do not reduce to the problem of factoring large numbers.


scrypt and argon2: binary safe? for bcrypt it's probably common knowledge that it isnt binary safe because it uses null termination, which means that when bcrypt is used you need to make sure that no one does these (e.g. by hashing the passwords in a different binary safe function like SHA256 before and encoding the output)

by now we have essentially 2 other ways which can be used for password hashing, scrypt and argon2, and after a quick round of using google I couldnt really find any info on whether these 2 are binary-safe (meaning I can just use them directly on passwords which certainly makes them easier to use) or not.

does anyone know?

BCrypt, Argon2 and scrypt are all "binary-safe".

That is, there is nothing inherent in the algorithms (and their reference C implementations) that would require the "password" input to have any structure.

The only exception maybe being that bcrypt has a 72 bytes input limitation, but that can be worked-around using pre-hashing.

However, particular APIs may wrap things differently and "help" the programmer by cutting off at \0 bytes or similar things. If this is the sort of info you need, you need to consult the documentation / the source code of the relevant wrapper.


The quantum key establishment protocol Consider the quantum key establishment protocol. Assume
that bit values, emitter basis, and receiver lter orientation are selected independently
and uniformly at random (i.e., 50% chance for each of the bit values/
bases/orientations).

  1)What is the joint entropy of the emitter bit value and receiver bit
  value?

My assumption is:
H(X=0,Y=0) = 3/4
H(X=0,Y=1) = 1/4
H(X=1,Y=0) = 1/4
H(X=1,Y=1) = 3/4

H(Y=0,X=0) = 3/4
H(Y=0,X=0) = 1/4
H(Y=0,X=0) = 1/4
H(Y=0,X=0) = 3/4

I could not go further here.

  2)What is the mutual information between the emitter bit value and the
  receiver bit value?

In my opinion, the filters can measure the polarasation of a photon if the filter and the photon do not agree the outcome is uniformly random. So, with respect to receiver bit value and emitter bit value we can find the sifted key.

Note:It is not a homework question.

The protocol is formally known as BB84 protocol.

Your "assumption" are conditional probabilities, and they should be calculated, not "assumed". For example, let Alice sends bit $0$; what is the probability that Bob receives bit $0$? Bob has 2 equally likely choices: either his basis coincides with the Alice's basis or not; in the 1st case Bob receives $0$ bit with probability $1$, in the 2nd case Bob receives $0$ bit with probability $1/2$. So the conditional probability that Bob receives $0$ bit given Alice sent $0$ bit is
$$ P_{X,Y}(0,0|X=0) = 1/2\cdot 1 + 1/2\cdot 1/2 = 3/4$$

Since Alice sends $0$ and $1$ bits equally likely,
$$ P_{X,Y}(0,0) = 1/2\cdot 3/4 = 3/8$$
and this I believe is one of the 4 probabilities that should be inserted into the Joint Entropy Formula


Blockchain cryptography I'm a high school student doing a project about blockchain. I'm trying to figure out why hashing algorithms are crucial for the existence of blockchain and other types of cryptography wouldn't work. However I've learned about pseudo random number generators and they seem to do the job. Any reason why these would not be qualified?

One key difference between cryptographic hash functions and PRGs is this:

Pseudorandom generators (PRGs) are secret key algorithms.  A PRG's user needs to provide it with some random input that must be kept secret from any adversary.  If there is no such input or it's not secret, the adversary can predict the output.
Cryptographic hash functions are (usually) unkeyed algorithms.  They are designed to work in certain scenarios where there is no secret information at all.  It should be hard for example for an adversary to find any input that produces some known output (preimage resistance), or a second input that produces the same output as a known input (second preimage resistance).

If you can grasp this and its implications for your topic you will be well ahead. A key observation is that blockchain is a public ledger.


What is the curve type of SECP256K1? This is possibly a dumb question. I'm trying to input SECP256K1 curve parameters to a system that expects any custom curve. The form is asking for "curve type". It offers three options:

Short Weierstrass
Twisted Edwards
Montgomery

What should I use for SECP256K1? I verified here and here, but they tell that SECP256K1 is a "Koblitz" curve. Is that compatible with any of the expected curve types above?

There are curve types, and equation types.

As algebraic objects, all curves can be expressed with a "Weierstraß equation". Through some changes of variables, that equation can be simplified into a "short Weierstraß format", which, for a finite field of characteristic more than 3, looks like:
$$ Y^2 = X^3 + aX + b $$
for two constants $a$ and $b$. In the case of the secp256k1 curve, the equation is:
$$ Y^2 = X^3 + 7 $$
i.e. the constants are $a = 0$ and $b = 7$.

"Montgomery curves" are curves which can also be expressed (with appropriate changes of variables, again) with another equation:
$$ bY^2 = X^3 + aX^2 + X $$
for some two other constants $a$ and $b$. When a curve can be expressed with such an equation, then it allows computing multiplications of points with the "Montgomery ladder", a mechanism which is simpler to implement, and somewhat faster, than generic code with Weierstraß equations. However, secp256k1 cannot be expressed that way. In fact, it is easily seen that a Montgomery curve necessarily contains the point $(0,0)$, which has order 2 (since its coordinate $Y$ is 0, that point, added to itself, yields the point-at-infinity). No curve with an odd order (and in particular curves whose order is a big prime, such as secp256k1) can have a point of order 2, and thus no such curve can be a Montgomery curve.

"Twisted Edwards curves" work with yet another equation, this time with a degree 4. They are more-or-less equivalent to Montgomery curves. There again, secp256k1 cannot be expressed as a twisted Edwards curve.

"Koblitz curves" (named after Neal Koblitz) are curves whose Weierstraß equation has a special format, which allows for some extra stuff. This terminology has been applied to curves in binary field (fields of characteristic 2, where addition is XOR), with equation:
$$ Y^2 + XY = X^3 + aX^2 + 1 $$
where $a$ is either $0$ or $1$. For finite fields with a large prime characteristic (e.g. integers modulo a given prime $p$), a "Koblitz curve" is a curve with equation:
$$ Y^2 = X^3 + b $$
i.e. a curve with a short Weierstraß equation with $a = 0$.

Koblitz curves have internal endomorphisms that can be leveraged to give a boost to performance (a much larger boost for binary curves). secp256k1 is a Koblitz curve.

Summary: all curves are "Weierstraß curves". For some curves, the Weierstraß equation has a special format, and they are called "Koblitz curves" (this is the case of secp256k1). For some curves, alternate equations can be used (Montgomery, twisted Edwards) with some implementation/performance benefits, but secp256k1 is not one of these curves.


Why was Rijndael the only cipher to have a variable number of rounds? Rijndael was the only AES candidate which defined a different number of rounds for their 128, 192, and 256-bit versions (10, 12, and 14, respectively). The others had a fixed number of rounds (32 for Serpent, 16 for Twofish, etc.) regardless of the key size. Why was this? It may have reflected the intention of having three different security levels and leaning towards speed for the "lower" security level, but that still doesn't explain why only Rijndael did this instead of settling on, say, 14 rounds.
Is there some cryptographic attack which is unique to Rijndael which would warrant this?

The others had a fixed number of rounds (32 for Serpent, 16 for Twofish, etc.) regardless of the key size. Why was this?
Is there some cryptographic attack which is unique to Rijndael which would warrant this?

During the second AES conference, the Rijndael team was asked about this design decision.
They turned it around, and pointed out that smaller keys have a smaller level of security (and hence a lower threshold on what would be considered a break).  After all, an attack that works with effort $O(2^{180})$ would be considered a break against a 256 bit key, but not against a 128 bit key, hence for 128 bit keys, you can get by with fewer rounds.  The same type of reasoning would appear to be applicable to the other candidates (although it would be a tad more complicated with MARS, given that it uses multiple types of rounds internally).
Now, the Serpent team responded that they didn't want to give anyone a reason not to use 256 bit keys, hence they would not consider a faster version for shorter keys.  As for the other three teams (MARS, RC6, Twofish), it appears that it just never occurred to them.


how to choose a random secret key for ECDH I am a beginner, I can understand the basics of ECC and elliptic curve, i can't find where I missed to understand. But I have a great doubt in ECDH regarding below. Could any of you please clarify for me? I will ask with the help of an example.

Example:

Let $G=(1,3)$ be the generator point with order $n=18$ for an elliptic curve $E(13,24)\bmod29$. I want to calculate Public key for both Alice and Bob.
Now Let the secret key of Alice be $A=5$ and of Bob be $B=7$ (such that the scalar which is multiplying with $G$ should be less than the order $n$ of the generator point).
Now the public key of Alice is $P_A=A\cdot G=5\cdot G=5(1,3)=(19,7)$
and the public key of Bob is $P_B=B\cdot G=7\cdot G=7(1,3)=(15,6)$
Now after transmitting the public key mutually, the parties have to calculate the shared secret key.
The shared key of Alice is $S_A=A\cdot P_B=5(15,6)=(23,1)$
and the shared key of Bob is $S_B=B\cdot P_A=7(19,7)=\mathcal O$(Point at infinity).
The shared secret supposed to be the same. But I am getting the point at infinity instead of $(23,1)$. How to overcome this?
My doubt is,if this is the case how can the sender and receiver get the  shared key in ECDH?
If not, kindly quote where I did mistake here and in what i misunderstood?

What curve are you considering, in what field, using what addition formulas?

From the data you provided, I assume you are talking about the curve of the form $y^2 = x^3 +  24x + 13$, in the field $\mathbb{Z}_{29}$ of the integer modulo $29$, because then your generator $G=(1,3)$ is effectively on the curve:
$$1 + 24+ 13 \equiv 9=3^2 \pmod{29}.$$
And the public points you computed, $(19,7)$ and $(15,6)$ are effectively on the curve and correspond to the correct values.

Now, simple addition formulas for such a curve would be, given two points $P=(x_1,y_1)$ and $Q=(x_2,y_2)$,  that we sum together into $R=(x_3,y_3)=P+Q$:
$$ x_3= \left(\frac{y_2-y_1}{x_2-x_1}\right)^2-x_1-x_2 $$
$$ y_3=-y_1+\left(\frac{y_2-y_1}{x_2-x_1}\right)(x_1-x_3) $$
But those are not always working, most notably not if $x_1=x_2$, so we need another formula for point doubling, given $P=(x_1,y_1)$ and $R=(x_2,y_2)=2P$, we have that:
$$ x_2=\left(\frac{3x_1^2+24}{2y_1}\right)^2 -2x_1  $$
$$ y_2=\left(\frac{3x_1^2+24}{2y_1}\right)(x_1-x_2)-y_1$$
and even this would only work if $y_1\neq 0$.
Remark that on that regard, Wikipedia currently forgets to precise that there are such cases where the formulas cannot be used.

Now, you have a mistake in your latest computation: you want to take $P_A=(19,7)$ and multiply by 7 using those two formulas, so:
$$\begin{align}
2P_A&=(4,17)
&\text{doubling}\\
3P_A&=2P_A+P_A=(0,19)
&\text{addition}\\
4P_A&=2(2P_A)=(1,3)
&\text{doubling}\\
7P_A&=4P_A+3P_A=(23,1)
&\text{addition}\end{align}$$

So as you can see, $7(19,7)\neq\mathcal{O}$ as you computed, but it really works and is equal to $(23,1)$.

Note that there exist complete formulas for such curves, see for example this paper, so that you can have just one formulas to do everything.


Division in paillier cryptosystem Is division possible in the Paillier Cryptosystem? i.e. given a the cipher-text $C$ of an integer $M$ the plain-text divisor $D$, and only the public key, can one compute the cipher-text of $M/D$ ?

Yes (and always).

Given $\mathsf{Enc}(a)$ and $b$, you can compute $\mathsf{Enc}(a \cdot b^{-1} \bmod{n})$ by simply computing $\hat{b}=b^{-1} \bmod{n}$ and $Enc(a)^\hat{b} \bmod{n^2}$.

Paillier encryption is built on the bijeective mapping from $(x,y)\in \mathbb{Z}_n \times \mathbb{Z}_n^*$ to:

$E_{g,n}(x,y)=g^x y^n \bmod{n^2}$.

Generator $g$ is chosen to enforce that $x$ remains in $\mathbb{Z}_n$ (i.e., there exists a $y$ that makes $x$ unique in $\mathbb{Z}_n$). Specifically, it has order $\alpha n$ for a positive $\alpha < \mathrm{LCM}(p-1,q-1)$. A simple optimization is to set $\alpha=1$ by choosing $g=n+1$.

Regardless of variant, in the encryption scheme, $x$ is the message and thus $\mathbb{Z}_n$ is the message space. Contrary to the other answers, this allows $b$ to be generally inverted $\bmod{n}$ (except when 0 or in the negligible case that it is either $p$ or $q$).

Given the confusion, I did a sanity check in Mathematica to make sure (I picked small safe primes but you can set them using RandomPrime):

p = 23;
q = 83;
n = p*q;
lam = LCM[p - 1, q - 1];

L[u_] := Quotient[u - 1, n];

Trap[y_] := L[PowerMod[y, lam, n^2]];

g = RandomInteger[{1, n}];
While[GCD[Trap[g], n] != 1, g = RandomInteger[{1, n}]]

Enc[m_] := Module[{r, c},
  r = RandomInteger[{1, n - 1}];
  c = Mod[PowerMod[g, m, n^2]*PowerMod[r, n, n^2], n^2]
  ]

Dec[c_] := Mod[Trap[c]*PowerMod[Trap[g], -1, n], n];

m = RandomInteger[{1, n - 1}];
s = RandomInteger[{1, n - 1}];
si = PowerMod[s, -1, n];
c = PowerMod[Enc[m], si, n^2];
Dec[c] == Mod[m*si, n]

This answer is the result of a crash course in Paillier. I typically work in the discrete logarithm setting. Feel free to edit if there are any errors (you probably do know more than me).


Why does WPA2-PSK use 4-way handshake instead of 2-way handshake I don't seem to grasp why is the handshake for PTK in WPA2-PSK 4-way and not 2-way. Isn't it enough to just have these two steps:

First party sends Nonce1 to the other party
Second party sends to first party Nonce2 and the HMAC(Nonce1, Nonce2, other parameters) using KCK.

I don't understand why does first party have to confirm that it received the nonce and that it knows the shared secret.
In fact, even HMAC(Nonce1, Nonce2, etc.) computation is not extremely necessary. Or is it? I mean even if they don't share the same secret, they wouldn't be able to read each other's messages. Of course, communication wouldn't happen, but there's no information leakage either. Or is there?

No, two messages is not sufficient to achieve what the WPA2-PSK 4WHS is supposed to do: mutual authenticated key-exchange.

The key term here is mutual authentication. Remember, at the start of the WPA2-PSK handshake we have two entities, the access point and the client, holding (hopefully) the same key, also known as the pairwise master key (PMK). Now they want to authenticate themselves by proving that they are both in possession of the PMK. This is the point of the 4WHS (in addition to establishing session keys).

Now let us consider your suggestion: (1) First party (assume this is the access point, as in WPA2) sends a nonce $N_A$ to the other party (the client). (2) Client responds with his own nonce $N_C$, the access point nonce $N_A$ and potentially some other stuff, and computes an HMAC tag on it using PMK. (3) The access point verifies the response from the client using the PMK. At this point, what can the two parties be sure of?

For the client, the answer is: Nothing! Remember, all the client sees is a lonely nonce $N_A$. This could have been created and sent by anyone. Hence the client can have no guarantee that he is actually talking to the right access point.

For the access point, the situation is slightly better. Since he receives back the nonce he himself created ($N_A$), he can be reasonably certain about the freshness of the response (i.e. this is not a replay), and since the HMAC tag checks out he can be certain that the client must also be in possession of the PMK. (Digression: It is however bad form to use long term keys, like the PMK, directly in your cryptographic computations. Usually one derives temporary keys which are used instead. This is also done in WPA2). Hopefully, this also makes it clear why we need the HMAC tag. It is there to convince the other side that it is in possession of the PMK (and of course to detect tampering, but which is aside the point here).

More generally, in an authentication protocol based on nonces, at least three messages are needed in order to establish mutual authentication. With two messages or less, you would also have to use something like a time-stamp in order to ensure mutual authentication (however, this is non-trivial to do correctly in practice and even harder to model theoretically, see for instance: Modelling Time, or A Step Towards Reduction-based Security Proofs for OTP and Kerberos). Why WPA2 uses 4 messages instead of just 3 I am not sure, however it is similar to the 4WHS in TLS, which also uses the last message to "install" the generated keys.


What are the differences between plain and encrypted private keys? It seems like there are different kind of private key formats, namely:

PKCS#5 plain private key
PKCS#8 plain private key
PKCS#5 encrypted private key
PKCS#8 encrypted private key

I have seen these names of keys thrown around in articles and answers I read while searching.
What're the differences between these keys formats? Which one should I know I should use?
And is the encrypted private key actually more secure than the plain version of private key?

There is no such thing as a PKCS#5 plain private key. PKCS#5 defines Password Based Encryption (PBE) and it is noted that this can be used to encrypt a private key.

PKCS#8 does define plain and encrypted private keys. By using a parameterized object identifier that indicates one of the PKCS#5 schemes you can encrypt the private key.

Which one you should use if any is up to you and your requirements.

Encrypted private keys can be used to perform password based decryption where the encryption is performed by the corresponding (unencrypted) public key. The other party in other words don't need to know the password, they just need to have and trust the public key. Arguably PGP would be a better defined / more compatible format for that though.

Another advantage is that the password can be used to encrypt the private key so that the private key can be stored on e.g. a backed up network connection. This would be secure as long as the password used is relatively secure (note that dictionary / brute force attacks are possible in this kind of scheme).

Of course there are certainly other and more secure ways to protect a private key. Plain private keys should normally only be used for testing, although storing them on separate media (a thumbdrive for instance) could give some protection.


CSPRNG that cannot be used as random extractor Are there any specific CSPRNG's that cannot be used as randomness extractor within a TRNG?

In other words, can you simply provide enough entropy gathered from a good entropy source as seed in any CSPRNG, and be done with it?

I've got the strong feeling that the properties of a CSPRNG are largely overlapping that of randomness extraction, but Wikipedia claims that the properties of a (generic) PRNG may not necessarily overlap.

  However, the general PRG definition does not specify that a weakly random source must be used, and while in the case of an extractor, the output should be statistically close to uniform, in a PRG it is only required to be computationally indistinguishable from uniform, a somewhat weaker concept.

I presume that any hash based extractor should work, as it hashes the input. Hashing the entropy is - as far as I understood - considered a good method of extracting the randomness out of the entropy.

The only property that I can come up with that should be required from a CSPRNG is that it has to mix in all the data containing the entropy.

Notes regarding NIST SP 800-90B:

It is not necessary here to let the TRNG be a full entropy source as defined in that document; CSPRNG's are normally used to generate more output than the amount of entropy provided;
Chapter 6.4 contains requirements for the randomness extractor;

There is some relationship between the two notions, but a CSPRNG is designed to be computationally secure (secure against adversaries with bounded computation time), whereas a randomness extractor is required to be information-theoretically secure (unconditionally secure against adversaries with unbounded computation time).  So, they're different primitives.

I would not expect a typical CSPRNG to be a secure randomness extractor.  Typically CSPRNGs use computationally secure primitives, like AES etc.; they don't make any attempt or claims of providing security against adversaries with unlimited computing power.

Also, CSPRNGs are often designed to address other issues as well, such as recovery from state compromise (robustness against state compromise extension attacks), efficient use of the available entropy, and ability to stretch a finite amount of entropy into an unlimited stream of pseudorandom bits (e.g., using a PRG).

CSPRNGs are practical primitives, intended for applied cryptography, and were invented by applied cryptographers.  Randomness extractors have typically been studied in the theoretical literature and are rarely (if ever) used in practice, for a variety of reasons, and were invented by theoreticians for studying fundamental theoretical questions.  These differences reflect differences in the goals and values of those two communities.

We can also compare randomness extractors to pseudorandom generators (PRGs), but again, they're very different.  PRG's are not designed to act as a randomness extractor, so there is no reason whatsoever to expect any particular PRG to do a good job at randomness extraction.  Indeed, I'd expect that many secure PRG's might be perfectly good as a PRG but no good at all as a randomness extractor.  The purpose of a randomness extractor is designed to take a non-uniformly distributed seed and turn it into a uniformly distributed output.  That's very different from the task that PRG's are designed for.  PRG's are designed to be secure if their seed is distributed uniformly at random.  There is no guarantee whatsoever that they will be secure if the seed is distributed non-uniformly, and indeed, for some secure PRGs, they might be insecure when used with a non-uniformly distributed seed.

In short, if you take a CSPRNG or a PRG, I would not expect it to necessarily act as a secure randomness extractor.  They're just different things.


Practical quantum attacks on AES - Is AES-128 used in a block mode vulnerable to attack using quantum algorithms Can Grover's (or similar) algorithm be used to attack AES-128 when used in cipher modes like CTR?  It seems like the answer is no...  Also I have a similar question for SHA256 when used for a MAC.  It looks like using quantum attacks on SHA256-MAC would only produce only a parallel key that generates a collision for a single MAC value.  So the recovered key would be of no real value then right?

The question stems from my use of secure hardware elements for key storage and for AES.  The elements support only AES-128-mode and SHA256 MAC.  So I am being asked if we should consider updating the modules in future designs.  This is an embedded product where cost and power are limited.

Sure, you can use Grover's algorithm to attack AES-128 in CTR mode. Assume the attacker knows a few plaintext blocks and the counter. The AES ciphertext blocks that are generated by encrypting this counter and XOR'ing it with the plaintext. In that case the input and output of the AES-128 block cipher are known and Grover's attack can be applied (as if AES-ECB was used).

Similarly SHA-256 in HMAC mode could well fall for Grover's attack. But Grover's attack only halves the security of the symmetric algorithms. That means that for SHA-256 you would still be left with 128 bits of security for most situations.

However, SHA-512 is actually faster on 64 bit architectures than SHA-256, so it seems a good idea to use that if you can spare the space (and otherwise SHA-512/256 exists as well). Note that later Intel and AMD CPUs may contain Intel SHA-1 and SHA-256 instructions that offer hardware accelleration. So the performance of SHA-256 is much higher, easily beating SHA-512, if those instructions are utilized.

So yes, AES-128 could fall to Grover's attack and although HMAC-SHA256 is considered pretty secure, it does make sense to at least design your protocol in such a way that future updates to the protocol are a possibility. Although there is no pressing need to change from AES-128 or HMAC-SHA256, in general you want your algorithms to be configurable for different versions of the protocol.

The only reason to switch now is to make sure that captured sessions cannot be decrypted in the future. In that case you may also have to look at the way the session keys are calculated. Asymmetric algorithms, for instance, are much more vulnerable to QC crypt-analysis. So if you're dealing with that level of confidentiality you should switch to AES-256 as soon as possible.


ECDSA: Retrieving non-random k I have a question regarding the random $k$ number of ECDSA encryption. As far as I know, it is possible to retrieve $k$ (and thus the private key) from two signed messages if both used the same $k$. This was done for the PlayStation 3 hack. I'm now trying to reproduce it in Python, using this library: https://github.com/warner/python-ecdsa

My problem is that the hack only works in some cases (at least I think so). I've not been able to reproduce it, so I hoped you could help me.

Initially we have two equations:

$s1 = k^-1 * (z1 + y) \space\%\space n$

$s2 = k^-1 * (z2 + y) \space\%\space n$

(where $y = r*privkey$)

We want to get rid of $y$ and figure out $k$. In all explanations I've seen so far, they'll do something like this:

$s1 - s2 = k^{-1} * (z1 + y) - k^{-1} * (z2 + y)$

$s1 - s2 = k^{-1} * (z1 - z2)$

$(s1 - s2) / (z1 - z2) = k^{-1}$

$k = (z1 - z2) / (s1 - s2)$

This doesn't work in my code, because the modulo operation here is just ignored. It actually should look something like this:

$i*n + s1 = k^{-1} * (z1 + y)$

$j*n + s2 = k^{-1} * (z2 + y)$

I got rid of the modulo by adding $x*$n to the left side, where $x$ is unknown. Now I'll just do the same thing as above but keep the $+ x*n$:

$i*n + s1 - j*n - s2 = k^{-1} * (z1 - z2)$

$(s1 - s2) + n*(i-j) / (z1 - z2) = k^{-1}$

$k = (z1 - z2) / ((s1 - s2) + n*(i-j))$

Obviously we do not know $i$ and $j$. We can ignore them if $i == j$ (as we did in the first calculation), which is only the case when $z1$ and $z2$ are close together or $k^{-1}$ is very small (so that it pulls the result down and therefore prevents $z1-2$ from making too much difference).

In theory $k^{-1}$ is pretty small and therfore the exploit works. But in practice I've seen that $k^{-1}$ is not used, but instead the smallest inverse modulo of k%n that is a whole number is used. This number can be really huge, which actually amplifies the difference between $z1$ and $z2$, making $i-j$ pretty large. With this implementation, I can't use the exploit as explained in theory.

My questions are:

Why is it that many implementations use the inverse modulo instead of $1/k$? (I've seen it in two so far)
Wy doesn't it work when I change the implementation to use $1/k$?
Is there another way to retrieve $k$, even if the $k^{-1}$ part is really large?

Since this is part of an assignment for Uni, it has to work somehow. But I already spent too much time on it without any results.
Any gurus out there that can help me? :)

best regards

What you need to know is that all equations in this context are, implicitly, understood to be modulo n. That information alone should answer all of your questions, starting with the equation k = (z1 - z2) / (s1 - s2) (modulo N), which hence means k = ((z1-z2) * modular_inverse_mod_n(s1-s2)) % n, where I tried to copy your modulus (%) operator. Specifically:

Why not 1/k? k^-1 is the way the modular inverse of k is written in your equations, as is the (1/k) which you seem to misunderstand the way a C compiler might.
Why doesn't 1/k work? It would if you teach the audience (interpreter/compiler?) to treat it as modular division or modular inverse.
Is there another way? I'm not aware of a simple other way; however, one can make use of even very small information leakage (i.e. both k values have the same initial bit) to reduce the search space if you really insist on making it hard for yourself.


What does (block cipher) decryption parallelizable mean? I've tried searching this answer on here and on google, but I cant seem to find a succinct answer (maybe because its obvious).

My understanding from wiki/tutorialspoint/ppt is that for CBC/CFB, decryption parallelizable means a plaintext block can be recovered from two adjacent ciphertext block. Is this correct or is there more? I really don't see how the word parallel fits into this at all.
It is stated as advantage for the decryption to be parallelizable, but if an attacker has access to your ciphertext, then couldn't the attacker just decrypt it easily by using adjacent ciphertext blocks.
I've know about C threading, is this related to it? As in you can decrypt the from multiple threads. I don't see how this is possible either because it seems to be done from one chain.

plaintext block can be recovered from two adjacent ciphertext block

You also need the key. For example, for CBC mode, to decrypt block $i$, you need ciphertext block $i$, ciphertext block $i-1$, and the key. You do not have to have made any calls to the cipher on any previous or future blocks in order to decrypt block $i$.

Contrast this with OFB which is not parallelizable. In order to decrypt block $i$, you need to have run the cipher on block $i-1$ first.

  if an attacker has access to your ciphertext, then couldn't the attacker just decrypt it easily by using adjacent ciphertext blocks

No, because the attacker does not have the key.

  I've know about C threading, is this related to it?

Threading is one way to parallelize. In theory, with CBC or any other parallelizable mode, you could decrypt different blocks in different threads, processes, or even different machines.


Is it secure to use the same IV for encrypting a unique private keys? I want to store private keys in the database. I will never store the same private keys twice. As I understand the only reasons behind using a unique IV for each encryption, is that attacker can't see that you have the same data twice.

My server is generating the private keys. My server ensures that each private key will be only once in the database. If so, should I use an IV?

If you are encrypting keys, then you should use a key wrapping method. The SIV standard is the best for this.

Regarding doing something ad-hoc and without an IV, it really depends on the mode of operation. But, I always recommend against doing something non-standard.


Number of keystreams generated in Kreyvium for a single key/IV pair Kreyvium employs 128-bit key and 128-bit IV. By a single initialization procedure using a key/IV pair, how many keystreams can be generated?

Trivium is designed as an 80-bit key and 80-bit $\operatorname{IV}$. Noted in Algorithms, key size and parameters report 2014. Technical report, ENISA - European Union Agency
for Network and Information Security, 2014. increasing the key size was not an easy task.

Kreyvium is defined in Stream ciphers: A Practical Solution for Efficient
Homomorphic-Ciphertext Compression by Canteaut et al. as 128-bit IV and 128-bit key variant of Trivium. Actually they consider a solution to this problem.

  In typical applications of homomorphic encryption, the first step consists for Alice to encrypt some plaintext m under Bob’s public key pk and to send the ciphertext $c = \operatorname{HE}_{pk}(m)$ to some third-party evaluator Charlie. This paper specifically considers that first step, i.e. the problem of transmitting $c$ as efficiently as possible from Alice to Charlie.

They gave the maximum length as

  Our first aim is to offer a variant of Trivium with 128-bit key and $\operatorname{IV}$, without increasing the multiplicative depth of the corresponding circuit. Besides a higher security level, another advantage of this variant is that the number of possible $\operatorname{IVs}$, and then the maximal length of data which can be encrypted under the same key, increases from $2^{80}N_{trivium}(d)$ to $2^{128}N_{kreyvium}(d)$.

Bolds are mine

What is the Kreyvium

A picture can tell a thousand words. From the article;

They added the 256-bit IV and key bits into 288-bit internal state. Full defitinion can be found on the 8th page of the article.


Keys and mixed encoding - security implications Let's say we generate a 256-bit key like: secret = base64(csprng(32)). Assume someone using the secret ascii-decodes the base64-encoded string and uses the output as a key (i.e. ascii_decode(secret)).

Note that in this specific scenario the key is used in a HMAC-SHA256 function.

What are the security implications of doing this? Are there any possible issues?

You only have $6$ bits of entropy in $8$ bits of your output - in general that does not fullfill the requirements for a cryptohraphic key of being drawn uniformly random over the full range. In general, this can potentially be desastorous: You have no security guarantees, because no security proof applies any more. In the worst case such a bias in the key can completely break the system - without anyone noticing.

In a general setting however, you should also notice that those $256$ bit output of the CSPRNG are not $256$ bit any more if you encode it as Base64 and decode as ASCII. It should be $344$ bit output, and that doesn't fit any more, if a $256$ bit key is expected.

In your specific case with HMAC it is probably fine - because HMAC is equipped to handle different keylengths: The first thing HMAC does is to transform the key into the correct length. If the key is too short, it is padded, if it's too long the hash function is used on the key. You have $256$ btis of entropy in a longer string, so this should be fine.

But please note: It is unusual that an cryptographic function is equipped to handle variable keylengths, this is a lucky catch. While it should work in this case, in general it is a really bad idea to neglect the assumptions about the key. The term key implies often, that it is drawn uniformly from a specific range and considered in binary format.


DES 1-bit changes to inputs: why when I change two inputs by only one bit I get predictable results? I expected a 1-bit change to two inputs (same key) would provide differences to 50 per cent of the output bits (on average). But this is not the case when I tested it. However, for two 'identical' inputs but with keys different by one bit, the differences 'were' as expected. Why is this so?

Example 1 (same key, two inputs different by only 1 bit)

Key:    0123456789ABCDEF
Input:  0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF
Output: 56CC09E7CFDC4CEF56CC09E7CFDC4CEF56CC09E7CFDC4CEF

Key:    0123456789ABCDEF
Input:  1123456789ABCDEF0123456789ABCDEF0123456789ABCDEF
Output: 236617CA247292D156CC09E7CFDC4CEF56CC09E7CFDC4CEF

The two outputs are identical from the 17th character onward.

Example 2: (keys different by 1 bit, inputs identical)

Key:    0123456789ABCDEF
Input:  0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF
Output: 56CC09E7CFDC4CEF56CC09E7CFDC4CEF56CC09E7CFDC4CEF

Key:    1123456789ABCDEF
Input:  0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF
Output: 472C14ED890C7CB5472C14ED890C7CB5472C14ED890C7CB5

Here the outputs are completely different. As one would expect.

DES block size is 64 bits, your input is 3 DES blocks, you change 1 bit in the first input block only and encrypt the whole input in ECB mode without padding; the first output block is completely different after the change, the 2nd and 3rd blocks are the same, as it should be.

Here's the ECB mode of operation:


Proactive secret sharing security flaws I read a Shamir secret sharing notes where it mentioned the security flaws of PSS(Proactive Security Sharing) when only one server is responsible for generating $h(x)$.
To give the question a bit context, I try to rephrase the scheme it mentioned as follows:

Consider a (n, t) Shamir secret sharing scheme with the following form
$$f(x)=a_{t-1}x^{t-1}+a_{t-2}x^{t-2}+\cdots+a_1x+s$$
To prevent an adversary from compromising $t$ servers over time, we need to periodically invoke PSS to refresh $s_i(i\in N_t)$. We ask a server to periodically generate a random function
$$h(x)=b_{t-1}x^{t-1}+b_{t-2}x^{t-2}+\cdots+b_1x$$
and calculate $h(i), i\in N_t$, it then sends $h(i)$ to i-th server and ask it to update its secret according to:
$$s'_i=s_i+h(i)$$
After every server updates its secret, PSS completes.

The notes claim that this scheme has security flaws.
Here is what it says:

However, this extension has a severe security flaw.
In cases where t > 2, it is not enough to let only one server select h(x): if the server that picks h(x) is compromised during PSS, then the adversary may know the relationship between new shares and old shares.
More precisely, the knowledge of h(x) may enable the adversary to figure out si from si', even if si has been deleted.
For example, consider a (5,3) sharing. Assume that server 1 (who selects h(x)) is compromised before PSS, and server 3 after.
The adversary knows shares s1 (s1'), s2, and s3'.
Moreover, the adversary can find out s2' from s2 (s2' = f'(2) = f(2) + h(2) = s2 + h(2)).
Then, the adversary has s1', s2', and s3', and consequently, s, even though less than 3 servers are compromised from the start of a PSS to the end of the next PSS.

My question is:
Why would the adversary know s2, given that it has only compromised server1 and server3?

Reading the quoted section and then looking at the notes, it seems that this is not well explained in the notes. However, my assumption is that the adversary has compromised s2 before PSS, but then lost access and therefore does not have access to s2'. If the adversary had access to s2', they wouldn't need to do the attack to get s2'.

So, the adversary has s1 and s2 from before PSS and gets s3' (and s1') after PSS. In neither case does the adversary have the required 3 shares. But, because the adversary knows h(x), it is able to compute s2' from s2. Which allows the adversary to recover s.