What is Rolling Code in cryptographic terms? My first contact with cryptography was programming Rolling Code keychains. Since then I've been reading about this topic. But is hard to me understand the various types, uses, concerns of cryptography world.
Is Rolling Code a type of Authenticated Message? Or is it a Cryptographic method of dispersion? Is it Block or Stream cipher cryptography?

Edit: This Application Note explains how implement a Rolling Code controller. http://www.atmel.com/Images/Atmel-2600-AVR411-Secure-Rolling-Code-Algorithm-for-Wireless-Link_Application-Note.pdf

A Rolling Code is a method to generate short authenticated messages $M_i$, where $i$ is incremental modulo $n$ (thus rolling after $n$ messages), usually with the additional property that when the receiver has last accepted message $M_i$, it will only accept messages $M_{(i+j)\bmod n}$ for $1\le j\le m$, for some $m\ll n$ (perhaps $m=n/2$). This blocks attacks where a passive eavesdropper replays a message she intercepted, if the legitimate receiver has received that message or a later one, and until at least $n$ codes have been generated. Loss of less than $m$ consecutive messages is tolerated without undue message rejection.

A simple form of $M_i$ could be the concatenation of counter $i$ on $k$ bits (with $n=2^k$), and of a MAC of $i$ using a secret key shared by sender and receiver, obtained using HMAC.
Another option could be that $M_i$ is $i$ as a 128-bit block enciphered using one AES-128; $n$ is $2^{128}$ thus roll over never occurs in practice, and messages are authenticated by using a much smaller $m$, say $2^{48}$.

In the context of a door opener using one-way communication and no shared time reference, this gives useful but imperfect protection. An attack against the protocol (rather than the authenticating cryptography) remains possible by an active adversary:

User wants to open door, activates transmitter, which generates $M_i$.
Adversary intercepts $M_i$, and jams it (perhaps, by sending a strong signal during some fraction of the frame carrying the message, which can be reconstructed; that can be a header, or any fraction of a message shorter than its CRC if the message is protected by CRC).
Since the door does not open, user retries, re-activates transmitter, which generates $M_{i+1}$.
Adversary similarly intercepts and jams $M_{i+1}$.
Adversary immediately send $M_i$; the door opens, legitimate user is happy.
Later, adversary send $M_{i+1}$, door opens, adversary is happy.


Why is PRESENT 31 rounds? I tried a number of different inputs and keys and checked their respective hamming distances after each round. It seems PRESENT has an ideal or near ideal hamming distance (31 to 33) after only a few rounds. Indeed, some of the later rounds have worse hamming distances, e.g. 38 to 41. So why is it necessary to have so many rounds?

I think that the reason for 31 rounds is in their paper, Section 5.1.
 Bogdanov et al. have approximated a small $2^{−43}$ bias that occurs after 28 rounds of linear analysis.  Therefore they added another 3 rounds to arrive at a slightly unusual odd number of rounds.

This is how ciphers are designed.  There are no specific rules passed down through the generations on how many rounds a cipher should have.  We do know that more rounds improves resistance to analysis.  A very simple primitive can be easily strengthened by the addition of more rounds, and this fact is explicitly stated in the design notes for Skien and Threefish.  And preventing a designer from having 1000 rounds is the need to achieve a speed /performance for their target market. So they compromised at 31.

Singular increases in the round count work for PRESENT.  It's worth adding that sometimes its not possible to increase the round count by any arbitrary value.  The number of rounds has to match the key schedule and sometimes the schedule is designed more inflexibly than the main algorithm.


Does Terra Quantum AG break AES and Hash Algorithms? According to this Bloomberg article:

A Swiss Company Says It Found Weakness That Imperils Encryption
Terra Quantum AG has a team of about 80 quantum physicists, cryptographers and mathematicians, who are based in Switzerland, Russia, Finland and the U.S. “What currently is viewed as being post-quantum secure is not post-quantum secure,” said Markus Pflitsch, chief executive officer and founder of Terra Quantum, in an interview. “We can show and have proven that it isn’t secure and is hackable.”
The company said that its research found vulnerabilities that affect symmetric encryption ciphers, including the Advanced Encryption Standard, or AES, which is widely used to secure data transmitted over the internet and to encrypt files. Using a method known as quantum annealing, the company said its research found that even the strongest versions of AES encryption may be decipherable by quantum computers that could be available in a few years from now.
Vinokur said in an interview that Terra Quantum’s team made the discovery after figuring out how to invert what’s called a “hash function,” a mathematical algorithm that converts a message or portion of data into a numerical value.

We have already had limitations due to Grover's Algorithm that are asymptotically optimal. Are we going to have another snake oil sale like Treadwell Stanton DuPont?

Update: It turns out a product advertisement that we don't buy it!

Businesswire: Terra Quantum Makes Electronically Transmitted Communications Unbreakable After Revealing Weakness in ‘post-quantum Cryptography

The onus is on the company to prove their claims, especially when they are extreme. There is also no financial motivation to not prove their claims. I can understand if they say that they want to keep their new "unbreakable algorithm" secret until they patent it, but what reason in the world would there be to not present a break? This is especially the case since it's not something that can be utilized now. Unless, that is, they claim that they can break AES using today's quantum machines in which case I really have to hold back from writing expletives.
In short, this has all of the smell of snake oil with all the motivations of a company trying to get a lot of press and attention, and doing damage while they are at it. It's unfortunate that people don't think that they can make money while keeping their basic ethics.
Of course, one could argue that how can I make this judgment without having seen the details. I guess I'm old enough to not care to be wrong with a 1 in a $2^{40}$ chance. (I just made up that probability but without publishing how I got to it, I guess that no one can challenge me.)


BGV KeyGen-- Can a maliciously-generated secret-shared key break security (e.g. SPDZ)? I was (re)reading the paper "Practical Covertly Secure MPC for Dishonest Majority–or: Breaking the SPDZ Limits".

One of the key points in this paper is that they present a covertly secure BGV key generation protocol (Protocol B1, p15). The public key is revealed, but the secret key is full-threshold secret-shared among the parties.

They achieve covert security by generating multiple keys, and then opening all-but-one (provably) at random and checking that the parameters were generated correctly.

I understand why this is necessary with the $\epsilon_{i, j}$. If the error parameters are too small, then the underlying lattice problem is not hard enough. But it seems this could be fixed by each party adding an error that is large enough for the lattice problem to be hard. Then the security would be satisfied even if $n-1$ parties submit 0 as their error value. And in the honest case the error would be more than necessary, but definitely within the tolerable amount since BGV supports a lot of (homomorphic) ciphertext additions without the ciphertexts stopping to be decryptable.

Why is it necessary to check the $s_{i, j}$ and $b_{i,j}$? Is there an attack that an adversary controlling up to $n-1$ parties could do where they pick bad $s_{i, j}$ or incorrectly compute $b_{i, j}$ such that they can decrypt ciphertexts without collaborating with the honest players? Or in other words, why is this protocol not secure against malicious adversaries?

Short answer: I don't know of any practical attack that exploits a malicious key generation protocol to, say, learn something about an encrypted message. However, I imagine this is highly context-dependent (e.g. it seems hard to attack SPDZ this way, there may be other applications that are vulnerable) and there is no proof that no such attack exists.

Longer answer:
A malformed public key can potentially lead to decryption errors, where the probability of an error depends on some secret information (such as a private key). This allows for selective failure attacks, where the adversary observes whether an error occurs or not to try and learn something about the secret, and makes it difficult to prove the protocol secure.

In general, these kinds of attacks can be very concerning, although in this case it appears harder to exploit.

Consider a malformed public key $pk = (a, \hat b:= b + \hat e) \in R_q^2$, where $(a,b)$ is a correct key and $\hat e$ is some maliciously chosen, large error.

The first component of an honestly generated ciphertext $(c_0,c_1) = Enc_{pk}(m)$ has the form
$$c_0 = \hat b\cdot v + p\cdot e_0 + m$$

where $v$ comes from the ring-LWE secret distribution, and $e_0$ is a noise term (both sampled during encryption).

The malicious $pk$ introduces an additional error $\hat e \cdot v$ into $c_0$. When decrypting the ciphertext, decryption will likely be correct if $\|\hat e \cdot v\|_\infty < q/p$, but otherwise an error will occur.

Now, if decryption succeeds, the adversary will learn one bit of information on the secret $v$, namely that $\|\hat e \cdot v\|_\infty < q/p$. This means we can no longer use the standard technique of showing ciphertexts are pseudorandom under ring-LWE. That's because the proof requires $v$ to be distributed like a ring-LWE secret and completely unknown to $n-1$ parties, so that $(c_0,c_1)$ looks like a valid ring-LWE sample.

Finally, note that it seems very hard to exploit this leakage in a practical attack, particularly since the $v$ value is different with every ciphertext, so the leakage can't be reused. I'd speculate that it might even be possible to prove this secure for SPDZ under some variant of ring-LWE with leaky secrets.


Reversing a hash of known hashing algorithm I am sure this is a very easy thing to do but I am not sure how to go about solving a problem like this,
So there is this hash function which operates on a message which is in the form of a byte array (each element is 8 bits long):

digest [i] = ( (129 * message[i]) XOR message[i-1]) % 256

The value of message[-1] is 0.

Now, I have a few samples :

message = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
digest = [0, 129, 3, 129, 7, 129, 3, 129, 15, 129, 3, 129, 7, 129, 3, 129]

Now I have noticed a few things, $129_{10} = 1000\;0001_2 $
and multiplying it with a number greater than 128, does not change the lower 8 bits at all, except 255 and multiplying it with a number less than 128 does not change the lower 8 bits if it is even, and for odd, the $8^{th}$ bit is one rest is same. First, is this observation correct?

Second, how can one go about reverse engineering a hash function like this, so that given a digest, you can find out the message? Don't give me a direct solution, I am looking for an explanation and algorithmic way of doing it.

Thanks.

EDIT Another piece of information is that the length of message and digest is always 16 (bytes).

The i'th byte of the digest is a function of this byte of the message, and the previous byte.

So, to recover the original message from the digest, we just work our ways across the message, recovering each byte in succession.

First, we need to recover the first byte of the message.  Because there is no previous byte of the message, the formula for the digest simplifies to:

digest[0] = ( (129 * message[0] ) % 256.

Question: since we know the value digest[0], how can we recover message[0],

Next, assume we know the first i bytes of the message, and now we're attempting to recover message[i].  We know the formula:

digest[i] = ( (129 * message[i]) XOR message[i-1]) % 256

And we know the values digest[i] and message[i-1]; how can we use this to recover message[i]?

One hint that may simplify things: if we have $A = 129 * B % 256$, then we also have $B = 129 * A % 256$; that's because $129 * 129 = 1 \pmod{256}$


Primality testing (deterministic vs. non-deterministic) I noticed that non-deterministic primality testing algorithms are more commonly used in practice while there is a deterministic algorithm e.g., AKS which runs in polynomial time? I am right? if so, then why? is there any drawbacks of using AKS?

Thanks,

The simple answer is that AKS horribly inefficient in the real world.
Even the asymptotic complexity is orders of magnitudes higher than the one of probabilistic algorithms. Here is a comparison of AKS with Rabin-Miller and other probabilistic algorithms.
The following table illustrates the problem nicely (The tested number was $10^{
100}
+ 267$:


What encryption to choose from the SSL library in python 3? I've been researching some of the types of encryption that the python SSL library uses.

Among them the best I've seen are:

ECDHE-RSA-AES256-GCM-SHA384

TLSv1.2
Kx = ECDH
Au = RSA
Enc = AESGCM (256)
Mac = AEAD

ECDHE-ECDSA-AES256-GCM-SHA384

TLSv1.2
Kx = ECDH
Au = ECDSA
Enc = AESGCM (256)
Mac = AEAD

TLS_AES_256_GCM_SHA384

TLSv1.3
Kx = any
Au = any
Enc = AESGCM (256)
Mac = AEAD

I have sorted the encryption types according to their level of security, efficiency, and use. (Based on what you can research online, they are the most used and safest, especially the first).

The truth is that I don't know which one to choose for my project.

I would appreciate being guided and advised on which one to choose.

You may need a 1.2 and 1.3 scheme, so I'd include at least one of both, giving priority to 1.3 as it is the latest / greatest protocol.

Then there is ECDSA and RSA, indicating the certificate based authentication used. ECDSA is more performant for similar security (and you may not even get any certificates above RSA-4096). That may be important if you can choose the certificate type. However, once you've chosen your TLS certificate type, you don't get to choose between the two cipher-suites, and you just include the one that is compatible with your certificate.

If you do Business-to-Business (B2B) then I'd choose TLS 1.3 due to the fast session resumption may achieve.


Using Diffie-Hellman secret key to encrypt/decrypt data? My end goal is to encrypt data with AES-128, send it to other process and decrypt it there. While using DH key exchange protocol.

I have used DH to generate a 256 bytes shared secret, but I can't use that key to fit the 128-bit encrypting function.

I read that the secret needs to be fed through a "Key-based key derivation function" (KBKDF), but as I understand that gives you a hash which then you won't be able to dehash... so how does the other program can decrypt the message?

Can I just truncate the secret message to 128-bit? (I don't think this is the right solution though).

How would the encryption and decryption of the hashed secret work?

Side note. I am trying to do all this with OpenSSL library in C

Thanks.

I read that the secret needs to be fed through a "Key based key derivation function" (KBKDF), but as I understand that gives you a hash which then you won't be able to dehash... so how does the other program can decrypt the message?

The encryptor sends the DH shared secret through the KDF, which gives him a key, which he uses as (for example) an AES key, and uses that AES key to encrypt his data.

The decryptor sends the same DH shared secret through the KDF, which gives him the same key, which he uses as an AES key, and uses that AES key to decrypt his data.

There's no need to 'invert' the KDF; both sides use it in the forward direction


Birthday attack for combination of hashes I have to answer the following question for a homework assignment:

  You have a hash algorithm that converts a $2\cdot n$ bit number to an n bit
  number. How many hash values do you have to calculate to find a
  collision for $h(x) \oplus h(y) = h(r) \oplus h(s)$

I know that a you can find a collision after $2^{n/2}$ evaluations. But I don't know how this is affected by the fact that a $2\cdot n$ bit number is hashed to a $n$ bit number and the $\oplus$ of the hashes.

We first need to refine the definition of the problem.

The most natural assumption in a cryptographic context is that "How many hash values do you have to calculate" implies that we consider a strategy that minimizes that number of hashes.

In theoretical cryptography, a common assumption is that we are allowed arbitrarily large amount of memory, and use of arbitrary computing power. We'll assume we use that to cache the hash computation, but healthily check the required amount of memory and processor time in the end, for bonus points.

We'll also assume that we are actually asked the expected number of hash calculations required by one of the best possible strategies. And as common in cryptography, we'll be content with approximations, and/or disregarding low $n$, if that helps.

We need to define "collision". When talking about collision in a hash, it is understood $x$ and $y\ne x$ with $h(x)=h(y)$. But here the later condition is replaced by $h(x)\oplus h(y)=h(r)\oplus h(s)$, so what about the rest? That could be:

$(x,y)\ne(r,s)$. In that case the answer is zero assuming $n>0$ : we take any two distinct $x$ and $r$ and we know that $(x,x)$ and $(r,r)$ is a solution, without making any hash. $(x,r)$ and $(r,x)$ does the trick too. We'll disregard that option 1 from now on.
Distinct $x$, $y$, $r$, $s$; at least four hashes are required.
$x$, $y$, $r$, $s$ such that possible equality between terms does not result in a collision irrespective of the hash lagorithm; for $n=3$ that can be (showing inputs and outputs in binary)

$x=\mathtt{000000}$ with $h(x)=\mathtt{010}$
$y=\mathtt{000001}$ with $h(y)=\mathtt{001}$
$r=\mathtt{000010}$ with $h(r)=\mathtt{010}$
$s=y$; that works specifically because $x=r$.

Options 2 and 3 are not equivalent; option 2 falsely looks simpler (we fall into this trap later..).

The result obviously depends on the particular "hash algorithm", which in a cryptographic context is assumed known. Perhaps we could find an answer by looking at this algorithm. But it is not given in the question, thus in a cryptographic context our default fallback option is to consider that the expected number of hashes is for a random function $h:\{0,1\}^{2n}\to\{0,1\}^n$ (that notation merely states the size in bit of input an output of $h$). There are $2^{(n2^{2n})}$ such functions, thus $2^4=16$ for $n=1$, $2^{32}$ for $n=2$, and a whooping $2^{192}$ for $n=3$.

There's an easy way to plausibly justify that $2^{n/4+1/2}$ hashes allow to find a collision with fair odds for all but small $n$. Argument:

Evaluate $h(i)=h_i$ for $2^{n/4+1/2}$ incremental values of $i$ starting from $0$, assimilating integers to bitstrings in big-endian binary (as common in cryptography); that is, for $n=4$, $h_5=8$ means that $h(\mathtt{00000101})=\mathtt{0100}$.
For all $(x,y)$ with $0\le x<y<2^{n/4+1/2}$ consider $h'(x\|y)\gets h(x)\oplus h(y)$ and tabulate the nearly $2^{n/2}$ values $h'(x\|y)$.
$h'$ is not a random function, but if we nevertheless abuse the birthday problem for cryptographic hashing (a common thing in cryptography), that tells us there are near 40% odds of collision for $h'$ in the standard definition of that for hashes.
Such collision would allow one for $h$ as asked, always matching our option 3.
The collision is not quite always one per option 2; but odds that is does not are vanishingly low, considering that it occurs only if we found a collision for $h$ in the standard definition of that for hashes, after a mere $2^{n/4+1/2}$ hashes.

By turning that strategy into one that searches for collision of $h'$ for incremental values of $i$ (rather than having computed all hashes $h_i$), we can make the resulting strategy optimum for a near complete subset of option 3, including option 2; see below.

We now proceed to reason about what an optimum strategy must do.

It must computes hashes only for different inputs (otherwise we could devise a better strategy that does).
And since the function $h$ is random, what said different inputs are does not matter to the desired expected number of hashes (that is, the mean number of hashes for all possible $h$). So we can restrict to strategies always using inputs in lexicographic orders, as we did in example 3. We can safely state that the "..a $2\cdot n$ bit number.." part of the question is large enough that this strategy won't run out of input values; that would still hold if we removed the factor of two, including for $n=1$.
After having computed $h_i$, the strategy must stop if the computed hashes now allows to exhibit distinct $x$, $y$, $r$, $s$ at most $i$ with $h_x\oplus h_y=h_r\oplus h_s$. At least one of $x$, $y$, $r$, $s$ must be $i$ (otherwise the strategy would not be optimum), and reordering $x$, $y$, $r$, $s$ in non-decreasing order leaves a strategy valid and optimal.
An optimum strategy as restricted must thus try increasing $s$ and stop precisely

for option 2, when $s>2$ and the $h_s$ just computed and cached matches $h_x\oplus h_y\oplus h_r$ for some $x$, $y$, $r$ such that$0\le x<y<r<s$; which case $x$, $y$, $r$, $s$ is a collision.
for option 3, additionaly

when $s\ge2$ and the $h_s$ just computed mathches an earlier $h_r$ with $0<r<s$, in which case $x=0$, $y=0$, $r$, $s$ is a non-trivial collision;
or when $s>1$ and $h_s=h_0$, in which case $x=0$, $y=1$, $r=1$, $s$ is a non-trivial collision;
or when $s=1$ and $h_s=h_0$, in which case $x=0$, $y=0$, $r=0$, $s=1$ is a non-trivial collision.

One implementation option for option 2 is four nested loops with $s$ growing starting from $0$ at the outer, computing and caching $h_s$, then for $r$ from $2$ to $s-1$, $y$ from $1$ to $r-1$, $x$ from $0$ to $y-1$, terminating if the newly computed $h_s=h_x\oplus h_y\oplus h_r$, in which case $x$, $y$, $r$, $s$ is a collision.

There are $s(s-1)(s-2)\over6$ combinations of $x$, $y$, $r$ for a given $s$. Each corresponds to some $h_x\oplus h_y\oplus h_r$, these are not necessarily different, and finding a collision among these does not by itself allow the algorithm to stop. We consider all $h$, thus for each new $h_s$, odds $p_s$ that the strategy stops having computed $h_s$ assuming that it did not previously stop are (at most) $\tilde{p_s}={s(s-1)(s-2)\over6}\,2^{-n}$. It holds that $p_s\lessapprox\tilde{p_s}$, with equality when it happens that the $s(s-1)(s-2)\over6$ values of $h_x\oplus h_y\oplus h_r$ all are distinct.

Odds of stopping before computing $h_j$ (that is, having computed $j$ hashes or less) are
$$q_j\;=\;1-\prod_{3\le s<j}(1-p_s)\;\lessapprox\;\sum_{3\le s<j}p_s\;\lessapprox\;\sum_{3\le s<j}\tilde{p_s}\;\lessapprox\;{6\over2^n}\sum_{3\le s<j}(s-1)(i−2)(i−3)$$
with that approximation tight as long as $j\ge4$ is small enough that $q_s$ remains small and there are few collisions among the $(j-1)(j−2)(j−3)\over6$ values of $h_x\oplus h_y\oplus h_r$ previously computed when $h_{j-1}$ gets computed.

Further, induction shows that
$$\sum_{3\le s<j}(s-1)(i−2)(i−3)\;=\;{j(j-1)(j−2)(j−3)\over4}\lessapprox{j^4\over4}$$
and that approximation is tight for all except small values of $j$.

Therefore odds of stopping having computed $j$ hashes or less are $q_j\lessapprox{3\over2}j^4 2^{-n}$, and this approximation is tight as long as $k$ is not too small, but is small enough that said odds remain small and there are few collisions among the $\approx{j^3\over6}$ values of $h_x\oplus h_y\oplus h_r$ considered.

Thus the best algorithm for option 2 can not find a collision with sizable odds faster than $O(2^{n/4})$; this shows that our simple algorithm has the right assymptotic.

Moreover, $j\le{1\over\sqrt[4]3}2^{n/4}\implies q_j\le{1\over2}$ holds. Beware that this later approximation is far from tight: we expect more than few collisions among the values of $h_x\oplus h_y\oplus h_r$ (by abusing the birthday problem for cryptographic hashing, consciously ignoring the fact that the $\approx{j^3\over6}$ values are not independent); and the approximation where we changed the product into sum is no longer tight. That establises some upper bound (not approximation) for the median of the number of hashes required by any optimum strategy; we aim at the mean, which is slightly higher.

Image credit: Cmglee; source; Creative Commons license.

We have shown nearly rigorously that the expected number of hashes for an optimum strategy and large $n$ must be $k=O(2^{n/4})$ as $n$ grows; and have plausible argument that $2^{n/4+1/2}$ gives nearly 40% odds of collision.

Because that $k$ is well under the birthday bound $\approx2^{n/2}$, it is very unlikely that for large $n$ a hash collision for $h$ alone is reached before $k$ steps, and the distinction between the two definitions of "collision" that we did not reject matters only for small $n$.

We know various strategies leading to the minimum number of hashes according to 2 or 3, plausibly running in $O(2^n)$ time with $O(2^{n/4})$ or $O(2^{n/2})$ words of memory (for a computer with words of at least $n$ bits; beside this, a multiplicative factor of $\log n$ applies for both). We could make exact calculations of the expectancy for very small $n$ (but that will depend on the definition of collision). We could make randomized simulations for up to perhaps $n=32$. Finding strategies requiring less work (perhaps at the expense of more memory, or computing somewhat more hashes than needed) in order to tackle larger $n$ is an interesting problem.

This answer is incomplete (we still miss a rigorous and tight bound), overly long and complex with the potential to be confusing (especially from the moment we seek an optimum strategy), and spoils an interesting homework assignment (asked in vague terms, but perhaps that's on purpose by the teacher, or OP). I hope that at least the redaction will differ, and that the OP will make the aforementioned exact and simulated computations. After all, it is all too possible that I left a serious error somewhere.


Guarding against cryptanalytic breakthroughs: combining multiple hash functions Assume I want to design a protocol (or data format or similar) including some cryptographic hash, and want it to be as future-proof as possible, i.e. I want to avoid that breakthroughs in cryptography make my old data insecure.

If I use only one hash algorithm, I can have bad luck to pick just the one which will be broken after some years.

For example, MD4 (published 1990) had first collision attacks in 1995, and as of 2007 these are even cheaper than calculating the hash itself.

So, the idea would be to combine multiple such algorithms in a way that breaking just one (or some) of them does not compromise the security of the combined construct - breaking all of them would be necessary.

I do not care about efficiency loss from calculating multiple hashes instead of one, I just want to be sure against better cryptanalysis.

So, if I have hash functions $H_1$, $H_2$, ..., $H_n$. How to combine them to form a hash function which is as secure as any of them?

Two basic ideas, which do not work as intended:

simple concatenate the outputs:  $H_1(m) || H_2(m) || ... || H_n(m)$.

This should be quite secure against collision attacks, but is only as
secure to preimage attacks as the weakest of them (and the other ones
then can be used to check if I found the right preimage).
chaining the functions: $H_1(H_2(...(H_n(m)...))$

For preimage attacks, you would now need to break all of them. But a
collision in Hn trivially leads to a collision in the result, too.
(Collisions in the others are less easy to exploit, as you then need
to have to get preimages in the previous ones.)

Any better ways of combining them? Or is this a stupid idea at all?

To clarify: I do not really need more security than the hardest of the component functions, but I want at least that much. (And using more space is not really a problem here.)

And for preimages, I'm now mainly concerned about someone finding the original preimage (which is around the size of the hashes output),  and it looks like this will be at most as difficult as for the weakest hash, in the case of simple concatenation.
I'm not so much concerned about someone constructing a new one - this sounds quite difficult, but is not so much, if the size of the message can grow as needed (one block per bit of hash or such) and we have collision attacks on the compression function, as Joux shows.

Combining is what SSL/TLS does with MD5 and SHA-1, in its definition of its internal "PRF" (which is actually a Key Derivation Function). For a given hash function, TLS defines a KDF which relies on HMAC which relies on the hash function. Then the KDF is invoked twice, once with MD5 and once with SHA-1, and the results are XORed together. The idea was to resist cryptanalytic breaks in either MD5 or SHA-1. Note that XORing the outputs of two hash functions relies on subtle assumptions. For instance, if I define $\mathrm{SHB-}256(m) = \mathrm{SHA-}256(m) \oplus C$, for a fixed constant $C$, then SHB-256 is as good a hash function as SHA-256; but the XOR of both always yields $C$, which is not good at all for hashing purposes. Hence, the construction in TLS in not really sanctioned by the authority of science (it just happens not to have been broken). TLS-1.2 does not use that combination anymore; it relies on the KDF with a single, configurable hash function, often SHA-256 (which is, in 2011, a smart choice).

As @PulpSpy points out, concatenation is not a good generic way of building hash functions. This was published by Joux in 2004 and then generalized by Hoch and Shamir in 2006, for a large class of construction involving iterations and concatenations. But mind the fine print: this is not really about surviving weaknesses in hash functions, but about getting your money worth. Namely, if you take a hash function with a 128-bit output and another with a 160-bit output, and concatenate the results, then collision resistance will be no worse than the strongest of the two; what Joux showed is that it will not be much better either. With $128+160 = 288$ bits of output, you could aim at $2^{144}$ resistance, but Joux's result implies that you will not go beyond about $2^{87}$.

So the question becomes: is there a way, if possible an efficient way, to combine two hash functions such that the result is as collision-resistant as the strongest of the two, but without incurring the output enlargement of concatenation ? In 2006, Boneh and Boyen have published a result which simply states that the answer is no, subject to the condition of evaluating each hash function only once.

Edit: Pietrzak lifted the latter condition in 2007 (i.e. invoking each hash function several times does not help).


Formal definition of "explicit" algorithm? A long time ago, I read that the definition of "cryptographic hash function" is "collision-resistant one-way function". (A similar definition shows up in the FIPS standards for SHA-1 etc.)

But this is not a sufficient property for many of the modern uses of cryptographic hash functions, like Bitcoin. What they really want is for hash functions to act like a "random oracle".

Of course, no deterministic function can be random.

I am taking Dan Boneh's Coursera cryptography class. Most cryptographic primitives we cover assume some sort of secret, and then the definition of "secure" involves probabilities over the space of possible secrets. For example, a secure RNG has a secret seed, and if I (a) pick a seed at random and generate a long pseudo-random string, and (b) pick a long truly random string, then no efficient algorithm should be able to tell them apart with noticeably better than even odds. (With those odds computed over the space of keys and truly random strings.)

In the intro lecture to hash functions (see here or here if you do not want to register), Boneh gives the following definition of "collision resistant" hash function:

  A function $H$ is collision resistant if for all (explicit) "effective"
  algorithms $A$, $$\mathrm{ADV}_\mathrm{CR}[A,H] = \mathrm{Pr}[A\ \mathrm{outputs\ a\ collision\ for\ } H]$$ is "negligible".

Now, obviously, a very simple algorithm exists to output a collision for, say, SHA-256; we just do not know what that algorithm is. And there is no indication in this definition of the space over which we are calculating the probability.

So my question is twofold:

What is the formal definition of "explicit" algorithm? (I assume this is meant to rule out algorithms that we know exist but cannot explicitly describe.)
Over what space is the probability being computed in Boneh's definition?

To clarify: I am aware of the dictionary definition of "explicit". I am asking for a formal definition. I know how to translate a statement like "There exists an algorithm such that..." into (say) the language of ZF set theory, at least in principle. I do not know how to translate "...but nobody knows what it is" into any formal language at all. So I am wondering how a mathematician would think about this sort of definition.

What Dan Boneh says is not a formal definition as you want it. Let me quote Rogaway on this:

  In cryptographic practice, a collision-resistant hash-function (also
  called a collision-free or collision-intractable hash-function) maps
  arbitrary-length strings to fixed-length ones; it’s an algorithm
  $H:\{0,1\}^*\rightarrow \{0,1\}^n$  for some fixed  $n$ (we
  momentarily assume a message space of $\{0,1\}^*$. But in
  cryptographic theory, a collision-resistant hash-function is always
  keyed; now $H:\,\mathcal{K}\times\{0,1\}^*\rightarrow \{0,1\}^n$,
  where each $K\in\mathcal{K}$ names a function $H_K = H(K,\cdot)$ (This
  formalization assumes a concrete-security framework.) In this case $H$
  can be thought of as a collection or family of hash functions
  $\mathcal{H} = \{H_K:\:K\in\mathcal{K}\}$, each key (or index)
  $K\in\mathcal{K}$ naming one. (Note that we call $K$ a key but it is
  not secret; it will be chosen from $\mathcal{K}$ and then made
  public.)

  Why should theoretical treatments be keyed when practical
  constructions are not? The traditional answer is that a rigorous
  treatment of collision resistance for unkeyed hash-functions just
  doesn’t work. At issue is the fact that for any function
  $H:\{0,1\}^*\rightarrow \{0,1\}^n$ there is always a simple and
  compact algorithm that outputs a collision: the algorithm that has one
  “hardwired in.” That is, by the pigeonhole principle there must be
  distinct strings $X$ and $X_0$ of length at most $n$ such that $H(X) = H(X_0)$, and so there’s a short and fast program that outputs such an
  $(X, X_0)$. The difficulty, of course, is that us human beings might
  not know any such pair $(X, X_0)$, so no one can actually write the
  program down.

  Because of the above, what is meant when someone says that a hash
  function $H:\{0,1\}^*\rightarrow \{0,1\}^n$ is collision resistant
  cannot be that there is no efficient adversary that outputs a
  collision in $H$. What is meant is that there is no efficient
  algorithm known to man that outputs a collision in $H$. But such a
  statement would seem to be unformalizable — outside the realm of
  mathematics. One cannot hope to construct a meaningful theory based on
  what humankind currently does or does not know. Regarding a hash
  function like SHA-1 as a random element from a family of hash
  functions has been the traditional way out of this quandary.

Rogaway then demonstrates that even though it is not possible to formally define the collision resistance, it is possible to formally define the requirement for a collision resistant hash function by a higher-level protocol or a construction. This is done by a reduction that shows that if someone can break the protocol in a certain way, then he is able to find a collision for the underlying hash function. This allows to consider the protocol secure as long as collisions have not been explicitly found.


Value of “counter” when decrypting AES in CTR mode? If – when using AES in CTR mode – you decide to use the setup where you combine the IV and the block count value into a single value, as suggested here, the first 12 bytes are your IV and the last 4 bytes the block counter value. But what exactly do you do with block count value in terms of storage and subsequent decryption?

I’ve looked at a number of questions at Crypto.SE and other sources but I can’t seem to find an explicit explanation of this. I’m at a very elementary level of understanding of AES, so maybe some things I’ve read assumed some level of reader knowledge, or it’s figured the answer should be obvious to most.

According to NIST SP800-38A, §6.5, if we let our 12 byte IV be $INPUT\ BLOCK$ in the diagram and our 4 byte block count value be $COUNTER$, the 16 byte IV/block count is incremented by $1$ up to $n$; the number of plaintext blocks you have.

When you are done encrypting and are ready to store the data, do you subtract $n$ from the 16 byte IV/block count (equivalently just storing the 12 byte IV with the ciphertext) or would you store the entire 16 byte IV/block count (not resetting the counter)?

I guess my confusion stems from the fact that – when using CTR mode – the counter just reset to 0 and because decryption with CTR is the same as encryption, decryption starts with the 16 IV/block count? Are all the bits in the 4 byte block count are set to zero since you’re starting over, or does the counter start at $n$?

With a 4 byte counter, it is a representation of a 32-bit unsigned integer. Since the counter increments from 0, there is no need to store it on a per message basis. This then becomes an implementation issue.

A smart AES-CTR implementation would accept ANY initial counter/nonce value, and simply 0-pad it to the desired length. If we supply the cipher only 12 bytes, it would be starting with an initial counter of 0. If we supply 16 bytes, the last 4 would be the start counter (which could be 0).

For storage and transmission of the data stream is outside the scope of the cipher, and the length of IV is up to the implementer. Applications that require a new key for each message may not even store the nonce, and instead start from an all 0 IV every time. 4 bytes is not a lot, so if storage is available, storing the entire 16B counter/nonce value would probably make the most sense. I would assume the majority of applications looking for compatibility would store the whole thing, while those that use a fixed nonce length and do not require compatibility store only the nonce.

Any application that stores the counter along with the nonce would store it in a manner where it would be correct for the first ciphertext block (block 0), it would not store the last counter used during encryption (block n). Hence the term, initial value. During decryption, the keystream generation is seekable by supplying the required block number as the initial counter of the IV.


Paillier estimate attack costs on short keys I was thinking about how to use the homeomorphic property of that cryptosystem to achieve not a "semantic security" but a less ambitous obfuscation of the source code (an ipotetical scenario in which a third party execute the obfuscated code, and get a still obfuscated result).
So i was asking myself how much computation time to break a small keysize? i am sure there is a way to calculate "resistance" per bit but i don't know how.

As far as we know, the most efficient attack against well-implemented Paillier encryption is to factor the public modulus $n$ part of the public key. That's also the best known attack against RSA, thus is well-studied.
For history of factorization open records, see this. In 2020, CADO-NFS has factored a 828-bit $n$ with "roughly 2700 core-years, using Intel Xeon Gold 6130 CPUs as a reference (2.1GHz)".
A smaller data point: CADO-NFS factors a 337 bit $n$ in 5 mn on a single 32-core system.

How much does it cost to break a 64bit keypair? And a 128bit? And so on till 256 or so?

Nothing worth consideration if there is a single such problem to solve.


Is it safe for the ChaCha8 nonce to be deterministic? ChaCha8 takes a 8 byte nonce (or IV) that should not be the same twice for the same key. Generating this nonce randomly makes me very very nervous for collisions.

Is it safe to generate this nonce deterministically?

For example the first 6 bytes could be the number of milliseconds since the Unix epoch, with the last 2 bytes being an unsigned counter wrapping around. This will prevent any collisions from happening for 9000 years if no more than 65535 streams get encrypted in a millisecond (things get more complicated if the same encryption key is being used by multiple machines/threads, but let's ignore that for now).

Yes, it is safe. The only requirement for the nonce in Salsa/Chacha is to be unique; being predictable is not an issue, so a counter is fine.

Like CodesInChaos indicated, I believe extending XSalsa20 to XChaCha20 would also work if you want to a larger nonce, but have nothing concrete so will leave the details to him/her.


What is Associated Data in AEAD? I am trying to understand what is AEAD exactly. I am application developer not a cryptographer. I have been searching online for a while watched a bunch of Youtube videos, read through a couple of books "Serious Cryptography" and "Understanding Cryptography" but found the AEAD explanations to be too terse. My goal is to understand docs when using crypto libraries and they mention AEAD and the pros and cons of various modes for AES. Below are the questions I have about AEAD.

What is an example problem/scenario that AEAD solves? (looking to understand the problem not the solution)
How does AEAD solve this problem? (not the algorithm details but higher level big picture)
What are typical examples of associated data?
If AEAD is not used what are attackers able to do? (a lot of online references talk about a padding  oracle attack I tried to  understand the attack but it seems to require deep  understanding of how AES works)
As a  developer  should  I always use AEAD for everything?
What are typical mistakes developers  make when applying  AEAD?
Is AEAD only required for block ciphers but not required for stream ciphers?
Is AEAD required when  using a public key crypto such as  RSA?

First of all, let us look at what AAD is; it is a string that must be presented both at encryption and decryption; if the decryptor presents the wrong string, the decryption fails.
Why is this useful?  Because AAD can be understood as "encryption context".  We typically use the same keys to encrypt several messages.  What AAD prevents is the attacker taking one of the valid ciphertexts, and replacing another of the ciphertexts (encrypted with the same key) with it; if the decryptor uses different AADs for the two separate contexts, then the decryption will fail (and the attack is thwarted; if the attacker just wanted the decryption to fail, he could just replace the ciphertext with random gibberish).
An alternative approach would be to just use a separate key each time; that'd work, however AAD generally solves the problem with less complexity.
So, to answer your question:

What is an example problem/scenario that AEAD solves?

You asked for one; I'll give you two:

Consider TLS, where individual records are encrypted with the same key.  TLS uses an AAD that includes the record sequence number (which increments with each record); this prevents an attacker from replaying a previously sent record.

Consider database encryption, where we are encrypted individual fields within a database, for example, a database that gives the employee names [1] (unencrypted) and the salary (encrypted).  If the attacker could (say) take Alice's salary, and write that into Bob's row, well, that'd be bad.  By using the employee name as the AAD, the attacker can't do that undetected.

How does AEAD solve this problem? (not the algorithm details but higher level big picture)

What GCM does is stir in the AAD into the tag; if the AAD isn't correct, the tag would not verify (and you're supposed to reject the decryption in that case).

If AEAD is not used what are attackers able to do?

Replace one ciphertext with another

As a developer should I always use AEAD for everything?

Well, if you're using the same key for multiple purposes, you probably should use a distinct AAD for each encryption.  On the other hand, if you're using the key to encrypt only one message (e.g. as the symmetric portion within IES), there is no need

Is AEAD only required for block ciphers but not required for stream ciphers?  Is AEAD required when using a public key crypto such as RSA?

Generally, the replay problem needs to be addressed, however stream ciphers and public key methods generally use different approaches.
With stream ciphers, we often generate a single long string, and use distinct portions to encrypt individual messages - this prevents replay attacks.  Other times (when we need to be able to decrypt messages out of order), we include a nonce as an input to the stream cipher, and have a higher level protocol ensure that a nonce is not reused.
With public key encryption, it's generally handled at a higher level, possibly with a nonce...

[1]: A real database will be more likely to have some sequence number rather than the name; I'll ignore that for this example.


A Question about CCM The following is a quote from Wikipedia:

One key insight is that the same encryption key can be used for both, provided that the counter values used in the encryption do not collide with the (pre-)initialization vector used in the authentication.

The entire article can be found at:
     https://en.wikipedia.org/wiki/CCM_mode

I do not understand what it is saying. I am hoping somebody can explain it to me.

Thanks
Bob

You want both confidentiality and authenticity. You use e.g. encryption for confidentiality and a MAC for authenticity.

There are a host of problem that you can get if you use the same key for both. (This is imho the canonical example.) So that unfortunately in general means you should use two keys or in other words a combined key of twice the size.

The sentence you quote advertises that given certain other assumptions this is unnecessary for CCM.

For reference:
RFC and
Security proof


Encrypt-Mix-Encrypt: Full Diffusion? I've read "A Parallelizable Enciphering Mode" by Halevi and Rogaway about the encrypt-mix-encrypt mode for ciphers and was asking myself if this mode provides "full" diffusion.

So if an attacker alters one bit of the ciphertext, how many bits (all?) get scrambled on decryption? (if using AES and blocks of size 4096 bits (drive sector size))

Or in other words: Does this mode turns a "narrow" block cipher into a "wide"
cipher and hence would be a perfect choice for  full-disk encryption (FDE)?

Yes, EME is a wideblock cipher. Theorem 1 (in Section 4, top of page 5) states that EME is secure as a wideblock (tweakable) cipher under the assumption that AES (or whatever blockcipher you use) is secure.

Specifically, to someone who doesn't know the key, EME will look like a set of random, independent permutations (one for each tweak). This is true even if the attacker can both encrypt and decrypt whatever they wish. This in turn implies that all the bits get scrambled upon decryption if a single ciphertext bit is corrupted. (The definition at the bottom of page two captures these ideas, and then Theorem 1 states that EME meets this definition).


Use cases and implementations of RSA CRT I discovered the chinese remainder theorem (CRT) version of RSA cryptosystem which is used in many crypto libraries (OpenSSL, Java...).

The use of this theorem improves the speed of decryption so, why is it not always applied? What are the disadvantages of this version which would explain that it's not always implemented?

The following potential reasons occur to me why someone might not choose to use the CRT optimization:

The implementor worries about induced faults (but not quite enough to implement the obvious protection against it).  That is, with the CRT optimization, we process the RSA block both mod p and mod q separately, and then combine them.  That means that if the attacker can induce a miscomputation in one of the sides, we'll get the correct answer mod p (say), but not mod q.  This can leak the factorization of the modulus
The CRT optimization requires us to hold the prime factors; perhaps the implementer has restrictions on the amount of memory that can be used for a private key.  Note that it's possible to factor the modulus anyways if you have both the public and private keys, and so security isn't likely to be an issue here.
The implementer doesn't care about performance, and instead values simplicity
The implementer is clueless, and doesn't know about the CRT optimization


Does it take brute force to find a pair of plaintext and ciphertext that each follow a certain condition, given an AES encryption key? Suppose that I have an AES key $K$, and I'm instructed to find a plaintext such that the first 32 bits of the plaintext are some string of bits $S_1$, and the last 32 bits of the ciphertext once the plaintext has been encrypted with $K$ are another string of bits $S_2$.

Is this difficult? Is there a known attack against this that's faster than just fixing one of the $S$'s and brute-force searching for a text with the other $S$?

Well, it's moderately difficult; you couldn't use that as a security assumption; however, it would be too difficult to expect someone to solve during an active protocol.  There's no nonobvious trick to it; the two methods at your disposal would be:

Select random plaintexts with the first 32 bits as $S_1$; encrypt them with key $K$, and check to see if the last 32 bits of the ciphertext happen to be $S_2$
Select random ciphertexts with the last 32 bits as $S_2$; decrypt them with key $K$, and check to see if the first 32 bits of the plaintext happen to be $S_1$

Either approach will take an expected $2^{32}$ random trials before success; at 1 $\mu$sec per AES operation (quite conservative; modern CPUs typically can do several times as fast as that), we're looking at perhaps an hour or two.

Perhaps you were hoping there was some clever way to take advantage of the partly known plaintext/ciphertext; it doesn't work out.  For example, you might be hoping to translate the AES cipher into a large series of boolean operations (with the known key, and known 32 bits of plaintext and ciphertexts), and solve the resulting set of equations.  However, AES has a fairly quick 'avalanche'; very quickly (within two rounds), all the internal bits will depend on all the unknown bits in subtle ways; the resulting set of equations will not have an easier solution than just trying various combinations of the 96 bits on one side (which is effectively what the straight-forward solutions do)


What is the weakpoint of PRNG based encryption? Let's say I used this encryption schema:

In words instead of images:

Hash the encryption key with SHA256
Split it in half, first half use as XOR key for first 128 bit block of plaintext
Hash the second half from previous step with SHA256
Carry the hash to point 2), rinse, repeat.

What are potential problems/weakpoints of such encryption algorithm?

As a stream cipher I don't think there is any direct way to break the cipher.

First of all, it is extremely inefficient, as Richie already mentions. SHA-256 has an input block size of 512 bits, and you're only propagating 128 out of 256 output bits. So you're wasting a lot of input space. In other words, it won't be twice as slow as just SHA-256 due to the limited output being used, it will be about 8 times as slow (!).

One of the problems with your algorithm is that it only propagates 128 bits out of the internal state of the 256 bit internal state of SHA-256. That means that you are more likely to hit a cycle within the hash function. Probably your cipher mode has limited input size because of that. It is probably similar in security to CBC for a normal 128 bit block cipher in that way.

A bit of a unfair problem with it is that it has not received any formal review and that it doesn't have a formal proof. As for practical problems, a hash function input is generally not designed to take any keys, so you need to be aware of that. SHA-256 is fortunately relatively resistant against side channel attacks by itself. One good thing is that the key is not repeated anywhere in the followup hash calls.

As a cipher mode your algorithm is deterministic as it doesn't take an IV. It would however be easy to add a 128 bit IV or (rather) nonce at the start, simply as additional input next to the key. As it stands, it cannot be used as a cipher for repeated messages. You might mitigate the cycle issues by adding a counter to each invocation of SHA-256 as well, there is space enough for another 128 bit value.


Correctly generating cryptographically secure pseudorandom numbers (in C)? I am learning about cryptography, purely for my own interest. As part of that, I am implementing a simple one-time-pad toolset in C.

Naturally, I need to generate random numbers to create the pad, and they need to be cryptographically strong. I know about rand(), but from what I can tell it is not strong.

Is there a standard algorithm (or library) that I should be looking at to accomplish this?

Short answer: Don't do this. The security proof for the One Time Pad requires the use of a True Random Bit Generator. The best you can find on a typical multipurpose system without dedicated hardware support for a TRBG is a Cryptographically Secure Random Bit Generator. The difference is that CSRBG is typically a deterministic algorithm that is seeded with good quality entropy the system is able to collect from various states and events. Because of this, using it for generating an OTP would in fact be no more secure than using a black box stream cipher for generating the key stream.

However, for the sake of argument, let's suppose you are implementing an OTP on a *nix based multipurpose system. What is the best you can hope for?

The key will have to be as long as the message and will have to contain random bits, each with full entropy. This means that the key will have to be stored externally after generation. There will be no way of regenerating the exact same key, except by storing it, transferring it over a secure channel and reloading it. If there is any way at all to regenerate the same key stream from a more compact seed or key (even in theory), it is by definition not an OTP.
/dev/urandom is no better than using a stream cipher. It is unblocking exactly because it is based on an algorithm that generates the output from a small seed. In principle, /dev/random should be implemented to return full entropy bits (which is why it is blocking - it always waits for enough entropy to be generated), but, firstly, there is no guarantee that it estimates the entropy of its input correctly, and, secondly, that it manages to extract that entropy in a completely unbiased manner. In fact, if the extraction is accomplished by e.g. hashing the entropy input, it is even highly unlikely that the extracted entropy will be completely unbiased. It will at best be good enough for all practical purposes, but that doesn't include using it for an OTP.


Generating a cryptographically secure, many-time use, symmetric encryption key I need to generate a 256 bit encryption key described by the adjectives in the title. Currently I intend to create the key using this RNG.

Is this a secure manner of creating the key, given that it has the following properties:

Private key for symmetric encryption
Used many times (of course with unique IV's)

And given the following facts:

I will literally just get the RNG to produce 32 random bytes
not doing anything with (1) SALT (2) Iterations (3) Anything else

Please note that I am only asking if the key, directly after being generated, is secure. Thanks

Short story: Ultimately, your question comes down to a question of the quality of the Windows RNG. Your approach is fine if your RNG is good, but you're trusting the largely opaque Windows RNG to give you a perfect 32 bytes of entropy. I would recommend generating more bytes and then using a hash or KDF to compress it to 32 bytes.

Slightly longer story: All good random keys are generated from the same principle: An $n$ bit key is generated from a source providing $m$ bits of output with $n$ bits of entropy. If the source is high quality entropy output, then at best $n = m$ and the direct output can be used as a key. Otherwise, you would use something like a hash or a KDF to compress the $m$ bits of entropy to an $n$ bit key. Pick a good entropy source, and the random bytes it outputs will be a good key.

In your case, you are using the recommended cryptographic RNG provided by your host OS. This seems like a reasonably secure RNG source, but in general we like to be cautious about these things since there are many practical things that can go wrong. Since Microsoft doesn't publish the details, by default we tend to have more skepticism about it. A series of low entropy bytes might be output, the RNG might be badly constructed and a compromise of our key might lead to a compromise of the system's RNG state and thus future or past keys, and other such problems. To mitigate these failures, generally good practice is to pass RNG output through a hash or KDF before turning it into a key (even if $n = m$).

The Windows CryptGenRandom API is another portal into the Windows RNG, and I would think would work very similarly to the .NET call you referenced. Note that it has been at least in part reverse-engineered and had a few attacks against it, although I don't think low entropy itself is one of them.


Secure multiparty computation of conjunction Suppose Alice and Bob each have bits a and b, respectively. How can Alice and Bob compute the function a and b, without revealing their bits to each other?

EDIT: A paper called Solving the Dating Problem with the SENPAI Protocol came out recently.

They could use 1 out of 2 oblivious transfer. Alice offers the messages $0$ and $a$ and Bob uses $b$ as his choice bit (I.e., choosing the first message if $b = 0$ and the second if $b = 1$.). It should be easy to see that Bob now receives $a \land b$ (if in doubt write down the truth-table). Now Bob can send the result to Alice (or they can do the protocol in reverse).

Of course this assumes passive (semi-honest) adversaries. Also, note that if one party has input 1, then $a \land b$ always reveals the other party's input (this is regardless of the protocol).

Btw, this is known as the "Dating Problem", because it can phrased as follows: Alice and Bob does not want to openly tell each other whether or not they want to go on a date with the other. They fear embarrassment if the other party rejects them. Using the above protocol they can learn if both want to go on a date but will not learn if only the other party wants to go on the date. Essentially what Tinder solves for thousands of people every day! (Although they do it in a totally non-cryptographic way AFAIK)


Why does a non-prime DH modulus creates a "NOBUS" backdoor can't we do a nobus backdoor with DH modulus prime? Some have argued that with a prime modulus you can just get the order by doing p-1 and then factor it, thus it is easy to reverse. I argue that this is not true.

The prime case

Our modulus is a prime $p$ such that the order of the group is $p-1 = p_1^{k_1} \times \cdots \times p_n^{k_n}$

For the backdoor to work, the discrete log should be do-able in groups of order $p_i^{k_i}$

For the NOBUS to work, you shouldn't be able to find the factors $p_i^{k_i}$

The non-prime case

Our modulus is now a composite $n = p_1^{k_1} \times \cdots \times p_n^{k_n}$ such that the order of the group is $p_1^{k_1-1}(p_1-1) \times \cdots \times p_n^{k_n-1}(p_n -1)$

For the backdoor to work, the discrete log should be do-able in groups of order $p_i^{k_i-1}(p_i-1)$

For the NOBUS to work, you shouldn't be able to find the factors $p_i^{k_i}$

The difference?

I see almost no difference between these two problems. It seems like a NOBUS backdoor could as easily be created with a prime modulus as with non-prime one.

Thoughts?

[In the non-prime case] For the backdoor to work, the discrete log should be do-able in $p_i^{k_i-1}(p_i - 1)$

Actually, that's not quite correct, and that's relevant for the answer.

If the factorization of $p_i^{k_i-1}(p_i - 1)$ is $p_i^{k_i-1} q_1^a q_2^b ... q_n^z$, then for NOBUS to work, someone else shouldn't be able to find the factors $q_i$.

Here's why this distinction is important: in the prime case, everyone knows the size of the group $p-1$, and anyone can hand off that value to a factoring method that's good at finding small factors, such as Elliptic Curve Method.  That is an astoundingly good way for find small factors, and for ECM, small can be 128 bits...

So, if $p-1$ consists of factors that are small enough for us to use, ECM can find them without much difficulty.

However, if we use a composite modulus, the size of the group is now secret. In other words, we've shifted the problem to finding the $q_i$ values.  Here, ECM doesn't help us much; unlike the prime case, there isn't a convenient $p-1$ value we can hand to ECM.  And, by making the $p_1, p_2$ values comparatively large, ECM just doesn't work the modulus directly.

What would work (to some extent) is the $p-1$ factoring method.  There, we keep making guesses as to the various primes that make up $q_i$; if we guess all of them on one side (and there's no penalty, apart from wasting time, for incorrect guesses), then we factor.  So, if we have a 64 bit $q_i$ value (and assuming the attacker knows that), he can guess all 64 bit primes; however there's about $2^{58}$ of them, so it'll take a while...


TLS Key Block calculation - What is a PRF? In Section 6.3 of the RFC for TLS 1.2, it is written that the key_block is derived from the following formula:

  key_block = PRF(SecurityParameters.master_secret,
                  "key expansion",
                  SecurityParameters.server_random +
                  SecurityParameters.client_random);

An arbitrary amount of "key_block" formulas are run until enough keying material exists to populate keys for the following six session keys:

  client_write_MAC_key[SecurityParameters.mac_key_length]
  server_write_MAC_key[SecurityParameters.mac_key_length]
  client_write_key[SecurityParameters.enc_key_length]
  server_write_key[SecurityParameters.enc_key_length]
  client_write_IV[SecurityParameters.fixed_iv_length]
  server_write_IV[SecurityParameters.fixed_iv_length]

Unless I'm missing something, since values fed into the Key_block calculation are identical and don't change, the result of each calculation is the exact same string.  Given that, why would the RFC indicate to recalculate the PRF when we could just repeat the same string as necessary to populate the six session keys?

After writing that out, I realized that I'm taking PRF to effectively mean "Hash of the following values".  If I've misinterpreting PRF, then maybe the more appropriate questions would be:
Does each iteration through the Key Block calculation produce different results by nature of what a PRF is?
If so, how does the opposite end of the negotiation come to the same session keys?

Yes, you're misinterpreting the PRF.

It's not just a hash function (and when you hit the end of the function, start back at the beginning).

Instead, it is a function that generates a rather long (actually, infinite) output; we use the first $N$ bits of that output to populate the various key values.

See section 5 of RFC5246; we have:

  TLS's PRF is created by applying P_hash to the secret as:

 PRF(secret, label, seed) = P_<hash>(secret, label + seed)

where

P_hash(secret, seed) = HMAC_hash(secret, A(1) + seed) +
                        HMAC_hash(secret, A(2) + seed) +
                        HMAC_hash(secret, A(3) + seed) + ...

and A() is defined as:

 A(0) = seed
 A(i) = HMAC_hash(secret, A(i-1))

As you can see, until you hit a loop within the internal A function (which is quite unlikely to happen for a while), the PRF output will not repeat itself.

And, to answer your question "does both sides compute the same value", the answer is "this process creates a long output, but deterministically; both sides do generate the same PRF output"


Is hashing large files CPU or I/O bound? For SHA3, if I were to hash large files (> 1GB), would that operation be CPU or I/O bound?

Suppose I were to exploit parallelism and either use multicore/SIMD execution or generate a hash tree, would that also be constrained by the same resource?

Clearly this depends a lot on your setup.

Looking at some numbers:

According to Wikipedia SHA-3 requires 12.5 cbp (cycles per byte) on a Core 2. Let's also assume this Core 2 has 2.4 GHz.
So we get 2.4 GHz / 12.5 cbp = 192 MB/s for the hash calculation.

Let's say you have an SSD with 500 MB/s access speed which is plausible according to the Wikipedia article on SSD and this benchmarking website.

That means the SSD is faster and hashing is CPU constrained.

Additionally, there are faster SSDs and benchmarks usually don't consider only consecutive reads so that could widen the gap.


How to encode messages in $\Bbb Z_p^*$ to be encrypted with ElGamal scheme? In ElGamal encryption scheme, in order to achieve IND-CPA security, one must use a group where the DDH problem is assumed to be hard. As this answer suggests, one way to achieve that is the following:

When working in $\Bbb Z^*_p$, let $p$ be a safe prime $p=2q+1$, where $q$ is also prime, let $g$ be a generator of the cyclic subgroup of quadratic residues of order $q$ and restrict the message space to quadratic residues only.

My question is: lets say my given message space is $\Bbb Z_p^*$, where $p$ is a prime, but not a safe prime. How can I embed this message space into one that can be encrypted with ElGamal scheme so that all the properties of ElGamal (IND-CPA security, homomorphicity) still hold?

ElGamal encryption

Given a prime $p$, a quadratic residue (implicitly: modulo $p$) is defined as an $a\in\Bbb Z_p^*$ such that $\exists b\in\Bbb Z_p^*, a\equiv b^2\pmod p$. Quadratic residuosity is efficiently testable using Euler's criterion $a^{(p-1)/2}\equiv1\pmod p$.

Select a $g\in\Bbb Z_p^*$ that is a generator of the subgroup of quadratic residues, of order $q=(p-1)/2$. That is, $g^q\equiv1\pmod p$; and $g^{q/r}\not\equiv1\pmod p$ for all prime(s) $r$ dividing $q$.

The private key is $x\in\Bbb Z_q$, a secret drawn uniformly randomly.

The public key is $h\in\Bbb Z_p^*$ computed as $h=g^x\bmod p$.

Define encryption of $m\in\Bbb Z_p^*$ as $E(m)=(c_1,c_2)=(g^y\bmod p,h^y\,m\bmod p)$ with $y\in\Bbb Z_q$ drawn uniformly randomly for each encryption, then discarded. And define the matching decryption $D(c_1,c_2)={c_1}^{q-x}\,c_2\bmod p$. It holds $D(E(m))=m$.

The encryption system is multiplicatively homomorphic: multiplying any number of ciphertexts componentwize in $\Bbb Z_p^*$ yields a pair which decrypts to the product of the plaintexts in $\Bbb Z_p^*$.

For strong medium-term security, $p$ should be an at-least 2000-bit prime not generated to have $p=t^k\pm s$ for small $s$ and $t$, and $q=(p-1)/2$ should have an at-least 250-bit prime factor.

When restricting to $m$ that are quadratic residues, ElGamal encryption is then believed to have IND-CPA security. A problem otherwise is that $E(m)$ leaks whether $m$ is a quadratic residue, as the residuosity of $c_2$.

Note: other descriptions of ElGamal encryption make $g$ a generator of the full $\Bbb Z_p^*$, of order $q=p-1$. Similarly, $E(m)$ leaks whether $m$ is a quadratic residue, as the residuosity of $c_1\,c_2\bmod p$.

Fixing the residuosity leak while keeping homomorphicity

Find the smallest $u>1$ that is not a quadratic residue. Check that $u^4<p$, which will hold for overwhelmingly most large $p$.

Define encryption
$$\begin{align}E'(m)&=((c_1,c_2),(c'_1,c'_2))\\
&=\begin{cases}
(E(m),E(1))&\text{when }m\text{ is a quadratic residue}\\
(E(m\,u\bmod p),E(u^2))&\text{otherwise}\\
\end{cases}\end{align}$$
and define $D'((c_1,c_2),(c'_1,c'_2))=D(c_1,c_2)\,\left(\sqrt{D(c'_1,c'_2)}\right)^{-1}\bmod p$, failing if the argument to the square root is not the square of an integer.

For any $m\in\Bbb Z_p^*$ it holds $D'(E'(m))=m$.

The encryption system is multiplicatively homomorphic within a limit: multiplying up to $l=\lfloor\log(p)/2\log(u)\rfloor\ge2$ ciphertexts componentwize in $\Bbb Z_p^*$ yields a pair of pairs which decrypts to the product of the plaintexts in $\Bbb Z_p^*$. If $u=2$ is not a quadratic residue, we can multiply at least 1023 ciphertexts for 2048-bit $p$.

That encryption is CPA-secure, because ElGamal encryption $E$ is only used on messages that are quadratic residues.

Notes:

The detection of decryption failure, if leaked by the decrypter, can be abused into a decryption oracle. Don't allow that!
In homomorphic use, the decrypter (with the private key) can compute how many plaintexts that are not quadratic residues have been multiplicatively combined, as $\log({D(c'_1,c'_2)})/2\log(u)$.

Extensions:

If the later property is undesirable, what the decrypter learns beside the deciphered product can be limited to learning a crude approximation of how many plaintexts that are not quadratic residues have been multiplicatively combined: change $(E(m\,u\bmod p),E(u^2))$ to $(E(m\,u^{-1}\bmod p),E(u^{-2}\bmod p))$ with probability 50%, and adjusts decryption to deal with $D(c'_1,c'_2)^{-1}\bmod p$ being a square (also, the order of $u$ must be large enough). Further, by changing $(E(m),E(1))$ to $(E(m\,u^2\bmod p),E(u^4))$ or $(E(m\,u^{-2}\bmod p),E(u^{-4}\bmod p))$ with probability 25% for each of the alternatives, the proportion of quadratic residues is masked (but $l$ is halved).
It is possible to massively increase $l$ by having the decrypter solve $D(c'_1,c'_2)\equiv(u^2)^x\pmod p$ for small $x$ or $|x|$ (e.g. using Baby Step / Giant Step), then compute $D(c_1,c_2)\,u^{-x}\bmod p$ (also, the order of $u$ must be large enough). Still, homomorphically computing sizable powers (e.g. using square and multiply) is out of reach.
If use of another cryptosystem and key pair is game, we can replace $(c'_1,c'_2)$ with a Paillier ciphertext for plaintext 0 or 1 according to if $m$ is a quadratic residue or not. That simplifies decryption while keeping a multiplicative homomorphic property (with a different modulus for the Paillier component), and $l$ skyrockets. A variant of Paillier accepting negative plaintext can be used to mask from the decrypter the proportion (and to some degree the number) of plaintexts that are not quadratic residues.


Is there a type of asymmetric and symmetric encryption that's fairly easy to crack? I'm looking for a type of asymmetric and symmetric encryption that I can crack fairly easily for a school project. I'm looking to compare the difference between asymmetric and symmetric encryption. I have a VPS with (I 8GB of RAM and an Intel Xeon if that helps.

Preferably it should take no more than 8-10 hours to crack.

Assuming that the root source of secrecy is only an average password, then the choice of cipher does not matter so much. Especially if the key derivation step is not handled well.

Direct your computing power to:

Guess a password
Derive key material using the system parameters
Use that key to attempt decryption of the ciphertext

Authenticated encryption provides an oracle for verifying the key guess

Which system?

This seems like a nice candidate. It uses PBKDF2, which is better than nothing, but it isn't as resource intensive as bcrypt/scrypt/Argon2. It's implemented in python so it shouldn't be too hard to make any necessary modifications.

You can tune the iterations so that it is breakable with your given amount of computing power. As long as the target password isn't too complex, it should be feasible.

How to guess passwords?

There is plenty of software out there already. Some of it will even have nice features like organized word lists, including commonly used passwords and passwords from real breaches.

Depending on how handy you are as a programmer, it may or may not be easy to write your own basic password cracker.


Is this Sigma Protocol zero knowledge or is it just a proof of knowledge? Suppose I have the witness $x$ and need to prove that I correctly computed $(g^x)^x$ to a verifier. $g$ and $g^x$ are public. The verifier asks me for $(g^x)^x$, but wants proof that I've given them the right answer.

Here's my attempt at a solution:

Let $X = g^x$ and $X' = (g^x)^x$

Step 1: Prover chooses a random $r$ and sends $R = g^r$ and $R' = X^r$

Step 2: Verifier sends a random $c$ (challenge)

Step 3: Prover sends $z = r + cx$ (response)

Step 4: Verifier checks if $g^z = RX^c$ and $X^z = R'(X')^c$.

I was wondering whether this is zero knowledge or just a proof of knowledge.

Thanks!

I guess that it's also zero-knowledge, but I'll let you do the proof. However, an easier thing to note is that if $X=g^x$ and $X'=g^{x^2}$ then it follows that $(g,X,X,X')$ is a Diffie-Hellman tuple (i.e., it is of the form $(g,g^a,g^b,g^{ab})$. As such, you could use the standard Diffie-Hellman tuple Sigma protocol as a "black box".

(Note that Sigma protocols are defined as honest-verifier zero-knowledge, so that is the level we are aiming for here.)


Is that possible to prove that 'I do not know something' (i.e, the private key for a Bitcoin wallet) using cryptography? Is that possible to prove that 'I do not know something' (i.e, the private key for a cryptocurrency wallet) using cryptography?

The problem might be nonsense at first glance. But the intuition for this might be to prove that I do not hold the crypto coins under a specific wallet.

You are asking for some cryptographic function whose output changes based on whether or not your mind holds a particular piece of information. There is no function which is capable of knowing what is in your mind. You can cryptographically prove ownership, but you cannot do the opposite.


Is it safe to use same private key in two or more EC signature algorithms? Given two (or more) algorithms:

ed25519

private key is random blob of 32 bytes
public key is encoded point on Edwards 25519 curve.

ECDSA with secp256k1

private key is random blob of 32 bytes
public key is encoded point on secp256k1 curve.

Lets say, we have a message M and we sign it with both algorithms, with the same private key (public keys are calculated deterministically based on private key). Adversary is able to see both signatures, collect history of such signatures for different messages, messages are unencrypted.

Are there any security implications for this scheme?

In general, using the same key in different algorithms is bad practice, and indeed having two public keys on different curves with the same private key could reveal information. I don't know how, but I am sure that you cannot prove a reduction from one to another (unless you can map one group to another, which is doubtful).

Having said the above, if you use the same curve, but just different algorithms for signing, then I believe that one could prove security (but I won't do all the details). This is because EdDSA is actually a Schnorr signature, and so it is a zero-knowledge proof of knowledge of the secret key, secure in the random oracle model. Thus, one could proof that if you can break ECDSA given ECDSA and EdDSA signing oracles, then you could break ECDSA given only an ECDSA signing oracle (by simulating the EdDSA signing oracle yourself in the random oracle model). Thus, if ECDSA is secure then using the same key for Schnorr doesn't harm anything.


Trapdoors for Lattices: CCA-secure encryption In Trapdoors for Lattices:Simpler, Tighter, Faster, Smaller, Micciancio and Peikert proposed a CCA-secure encryption.

However, I am confused about the step in decryption algorithm (p.36 Lemma 6.2.).

That is, $\mathbf{v}^t \begin{bmatrix} R \\I \end{bmatrix} = 2(\mathbf{s}^th(u)\mathbf{G}$ mod $q$) + encode(m) mod $2q$.

And why $2(\mathbf{s}^th(u)\mathbf{G}$ mod $q) = 0$ mod $2q$, such that decode($\mathbf{v}^t \begin{bmatrix} R \\I \end{bmatrix})$ = decode(encode(m)).

You misunderstand what "decode" does. As mentioned earlier in the paper:

  The system has message space $\{0,1\}^{nk}$, which we map bijectively to the cosets of $\Lambda/2\Lambda$ for $\Lambda = \Lambda(G^t)$ via some function encode that is efﬁcient to evaluate and invert. Concretely, letting $S \in\mathbb{Z}^{nk×nk}$ be any basis of $\Lambda$, we can map $m \in\{0,1\}^{nk}$ to $encode(m) = Sm \in\mathbb{Z}^{nk}$.

This is to say that encode is a function from $\{0,1\}^{nk}\to \Lambda/2\Lambda$, and decode is therefore a function from $\Lambda/2\Lambda\to\{0,1\}^{nk}$.
Note that your expression is of the form:

$$\underbrace{2(\overbrace{s^th(u)G\bmod q}^{\in\Lambda})}_{\in 2\Lambda} + \overbrace{encode(m)\bmod 2q}^{\in \Lambda/2\Lambda}$$
Note that $\Lambda/2\Lambda$ is (by construction) invariant under translation by elements of $2\Lambda$. The construction is simply adding an element of $2\Lambda$ to $encode(m)$, which by the aforementioned invariance will not impact decoding.
Note that this may map the particular representative you've chosen of $\Lambda/2\Lambda$ to a different representative, but all of these representatives are viewed as "the same" in $\Lambda/2\Lambda$.

Concretely, consider if you have $\Lambda = \mathbb{Z}$.
Say $encode(m) = b\in\mathbb{Z}/2\mathbb{Z}$. If you add an element of $2\mathbb{Z}$ to this, you'll get something of the form $b + 2k$ for $k\in\mathbb{Z}$ (abbreviated as $b + 2\mathbb{Z}$).
But $decode(b + 2\mathbb{Z})$ is a function from $\mathbb{Z}/2\mathbb{Z}$ to the message space --- it should be the same for any particular representative of an element of $\mathbb{Z}/2\mathbb{Z}$ you give it, so you should freely add any element of $2\mathbb{Z}$ to it without impacting the correctness of decoding.

To be even more concrete, in this situation $decode$ is a function that says "I only care if my input is even or odd, no other details matter". Since adding an even number to any other number doesn't impact its parity, you have that:
$$decode(encode(m) + 2\mathbb{Z}) = m$$
Similarly, in the protocol we have that:
$$decode(encode(m) + 2\Lambda) = m$$


Any algorithm with a master key for decrypting private key encrypted messages? Are there any algorithm out there that implements following scenario?

Create a master private key
Create a private/public key #1 based on the master key
Create a private/public key #2 based on the master key
Encrypt data #1 with public key #1
Encrypt data #2 with public key #2
Possible to decrypt data #1 with both private key #1 and master key
Possible to decrypt data #2 with both private key #2 and master key
Impossible to decrypt data #1 with private key #2
Impossible to decrypt data #2 with private key #1

You're looking for "key escrow", which is often a very bad idea. Even if this fits your use case, you're creating a single point of failure.

I'm sure that there are more sophisticated approaches, but here is a very simple one:

You need a pseudorandom function (PRF) and a public key encryption scheme.

Draw a random key $k$ for the PRF and use it as master key.
Then whenever generating a public/private key pair, take a unique bitstring $id$, compute $PRF(k,id)$ and use the result as randomness for the key generation algorithm of the public key encryption scheme, which gives you a private key $sk$ and a public key $pk$. Store a table that maps $pk$ to $id$.

This fulfills everything that you want: As long as the key $k$ is not revealed, the public key encryption scheme works as intended and is secure. But if I know $k$, I can look $id$ up in the table, recompute $PRF(k,id)$, derive $sk$ and decrypt.

Here, $id$ is a nonce in the weak sense: it can either be fully random or implemented by a counter; you "just" need to make sure that it is never repeated. (If it is a counter, you can also not store the table in the first place, and just try enough counter values until you have the right one, if you need to decrypt rarely with the master key.)


Pre-image attack on MD5 hash I read somewhere MD5 is broken in terms of collision, but I am wondering if it is broken in terms of pre-image resistance?

Given a hash of Md5, is it possible to find the original message of it? If so, what would be the complexity and time to crack it?

The only published faster-than-brute-force preimage attack I can find is this one from 2009 by Yu Sasaki and Kazumaro Aoki.

From their abstract:

  This attack, with a complexity of $2^{116.9}$, generates a pseudo-preimage
  of MD5 and, with a complexity of $2^{123.4}$, generates a preimage of MD5.
  The memory complexity of the attack is $2^{45}\times 11$ words.

In short, this is not practical at all.


Triple DES as cryptographic hash function I need to generate a hash for a small piece of data (~50 bytes). I'd normally use MD5 or SHA but that's not available in the platform I'm programming for.

Luckily, it provides Triple DES and I thought I could use it as cryptographic hash function (pseudo-code):

function MyHash(text)
    data = padded(text, 64)
    key = data[0:8] + data[8:16] + data[16:24]
    encrypted = TripleDES(data, key)
    return encrypted[0:16]

MyHash will produce 128-bit (16-bytes) long hashes for input text.

Is MyHash secure? How does it compare with MD5 and SHA-*?

It is not a secure hash. For example, it is easy to find collisions and second preimages for your hash function if the input is allowed to be longer than 24 bytes, because only the first three 64-bit blocks affect the output.

Additionally, it should not even work with a typical DES implementation. DES keys are 56 bits, encoded as 64-bit values where 8 bits are for parity. Arbitrary inputs will not produce a well formatted key.


Proving membership of a group without revealing identity? I have an interesting problem for which I've failed, so far, to find an elegant solution.

Imagine that a user needs to repeatedly prove to public observers that they are a member of a trusted set but the proof needs to be different each time so that they can't be tracked.

My initial thought was that the set owner publishes the value of an RSA Accumulator which includes all the members and each member possesses the corresponding witness value. They can then reveal the witness, and an observer can confirm that they are indeed included in the accumulator. The problem with this is the witness (proof) is constant so every time they assert their membership, observers can infer their identity. Also any observer can then steal their proof and use it themselves. I don't want the member to have to contact the set owner before each assertion e.g. get them to blind sign each new assertion.

I've also looked at Paillier based homomorphic encryption where the user could deliberately blind a value by adding to it but, here the keys are the wrong way around i.e. public encrypts and private decrypts. The set owner would need the private key. So what I really need is a homomorphic signature where the owner can give the user a signed value which can be blinded for each use.

What would you recommend to solve this problem?

Look at group signatures (but use one of the more modern schemes; they are proven secure). The signature can be applied to a running counter, or a random challenge. Group signatures also give you a lot of "management" options which can be useful depending on the application. If you don't need them, then you can use ring signatures (but the verifier has to check that the ring includes only members of the set, or someone else can easily join).


What is Byzantine Agreement? This was mentioned in a different question.
However Wikipedia states it is proven to be unsolvable.

So I would like to know what it is in this context and - since it is unsolvable - what the protocols trying to achieve it are actually doing.

The problem is proven unsolvable if the number $t$ of faulty machines of total $n$ machines have a ratio $t \geq \frac{n}{3}$. So for $t < \frac{n}{3}$ it can be solved. Or it can be solved if the result does not have to be certain agreement but allows some uncertainty (which should be small), which might allow a higher threshold.


How does compression before encryption leak info about the input? Apparently current best practices recommend that you do not compress before you encrypt.

For example in this blog entry (*):

http://sockpuppet.org/blog/2013/07/22/applied-practical-cryptography/

It is written:

  Developers shouldn’t compress plaintext before encrypting.

Or in this question here on crypto.se:

Is compressing data prior to encryption necessary to reduce plaintext redundancy?

several people answer that compressing before encryption is actually harmful.

What I really don't understand is that apparently the explanation is that the compression algorithms used leak information about the size of the plaintext input!?

But in which way does not using compression before encryption not leak info about the length of the input too?

What additional infos are leaked by compression algorithms that wouldn't be leaked by not doing compression?

If padding is used on plaintext encrypted without compression, couldn't paddding be used too before encrypting compressed data (or data to be compressed)?

Also: is it really a given that the attacks you make possible by using compression before encryption are more of a problem than the attacks made possible by not compressing before encrypting? (the latter being the reason for which, during more than two decades, it was always advised to compress before encryption).

The problem is not with compression and encryption, it is with the protocol that is being used, and the type of data being compressed (or not) prior to encryption.

The most damning leaks are on protocols that were either designed to be compressed without encryption, or encrypted without compression.

The best example I have is VOIP systems that use a variable bitrate compression prior to encryption. Since the gaps between words and even syllables are highly compressed, and the words and syllables themselves are compressed at different rates depending on their content, traffic pattern analysis can be used to accurately detect spoken words and phrases. Public research only began within the last decade, but NSA designed encrypted voice protocols used constant bitrate compression and i/o clocking, meaning the technique was either known or they expected it to be exploited.

An excellent presentation of the subject here, as well as a more detailed initial report from 2008.

When a protocol is properly designed with compression and encryption in mind, it is much more difficult to gain information. For example, an SMS message where the entire message space is encrypted using AES-GCM, and the text is first compressed, allowing potentially more than 160 characters to be included in a single message. Some of the SMS must be used for nonce/auth tag, so the more message it can fit the better. This is of course an additional encryption I am talking about and not part of the SMS protocol. Multiple sequential SMS messages reveal information about the message size (being larger than the limit), and compression can prevent that if done correctly.

Padding any compressed plaintext to a multiple of some given number (say 128 bytes) prior to encryption makes certain attacks less effective, especially if the majority of plaintexts are small (like text messages). The methods used to pad the data are also important, as there are attacks that exploit padding used in various protocols.


How Pairwise Transient Key is derived or generated? I recently study WPA/WPA2 security and I want to know how PTK is derived. I found these parameters in the IEEE 802.11 standard (2012):

PRF - X(PMK, “Pairwise key expansion”, Min(AA,SPA) || Max(AA,SPA) || Min(ANonce,SNonce) || Max(ANonce,SNonce))

where X = 256 + TK_bits. The value of TK_bits is cipher-suite dependent

And only one page is about PRF in the IEEE 802.11 document.

The mystery for me is the PRF or pseudorandom function. How does it work? Does it have any algorithm or method? I have searched, but I have not found any concrete examples with concrete numbers and step by step tutorial or any code implementations.

The page you linked to directly gives the algorith to calculate ${\rm PRF}(K, A, B, Len)$:

$\hspace{2em} \textbf{for }i \leftarrow 0 \textbf{ to } (Len+159)/160 \textbf{ do} \\
\hspace{4em} R \leftarrow R \mathbin\| \text{H-SHA-1}(K, A, B, i) \\
\hspace{2em} \textbf{return } \text{L}(R, 0, Len)$

The helper function $\text{H-SHA-1}$, the string concatenation operator $\|$ and the meaning of the parameters are all defined just above this code on the page.  The helper function $\rm L$ does not seem to be defined on the page you linked to, but from context, it seems likely that ${\rm L}(R, 0, Len)$ is meant to return the first $Len$ bits (i.e. the first $Len/8$ bytes) of the string $R$.  You'll probably find its precise definition somewhere earlier in the document.

(Also, the algorithm as given doesn't specify the initial value of the string $R$, but it seems obvious enough that it's meant to be initially empty.)

Below this algorithm, the page defines five specific "wrapper functions" $\text{PRF-}X$, for $X \in \{128, 192, 256, 384, 512\}$, simply as $$\text{PRF-}X(K, A, B) = \text{PRF}(K, A, B, X).$$  Note, however, that the page also says that different definitions of these wrapper functions, given at the end of the page and the beginning of the next page, are to be used in some cases ("When the negotiated AKM is 00-0F-AC:5 or 00-0F-AC:6...").

In any case, this looks like a common way to extend the HMAC pseudorandom function, which has a variable input length but a fixed output length, into a variable-output-length PRF by repeatedly invoking it with the same input combined with an incrementing counter, and concatenating the results.  It looks quite similar to e.g. HKDF-Expand, although HKDF also feeds the previous HMAC output as input to the next HMAC call in order to (hopefully) make any cryptanalytic weaknesses in the underlying hash function harder to exploit.  (See section 7 of the HKDF paper for the designers' rationale for this.)


Required key size for an ideal cipher with a 32 bit block size For an ideal block cipher, what size key would be required when the cipher has a 32-bit block size?

The size of the key depends on the security level you want, it is not possible to say "you need exactly $n$ key bits if you have a block size of $m$ bits".

Let's assume that for an ideal cipher, a block size of 32 bits means $2^{32}$ possible input values which can be permuted in $(2^{32})!$ ways. That means you would have at most $\log_2(2^{32}!)$ key bits, to avoid equivalent keys. This is a lot, and in practice only a (very!) tiny fraction of that amount of bits would be used. In fact, one could argue that this upper bound on the key size is so ridiculously large that it's almost meaningless.

For a lower bound (this is probably what you are interested in), you need to look at the required security level.
For example, a 10 bit key is easily bruteforced, but a 256 bit key is secure against brute force attacks (assuming of course there are no other attacks on the cipher).


Security of very simple XOR with random? I am currently trying to implement a very fast and simple encryption algorithm in Lua for the purpose of using it with ComputerCraft.

The main problem is that bitwise operations in Lua (5.2 at least) are very slow and the implementation ComputerCraft can only handle 32 bit integers in their bit-library, so implementing standard algorithms isn't easy.

On the other hand this is only a game and encryption is merely used to keep others from simply controlling your devices or reading your messages. There is no critical data associated with this, so the encryption can be very weak.

I currently implemented a combination of XOR and random in the following form (pseudo-code):

random.seed( hash(key) ) -- 32 bit seed
for i = 1 to str.length do
  result[i] = str[i] XOR random.nextByte()
end

The good thing about this is that it only uses a single bit-operation and is guaranteed to never exceed 32 bit. Also this is very fast.

Aside from external problems like random entropy, what is an approximate time someone would need to decrypt this using a standard desktop PC? (sophisticated guess is ok, I just want to get an idea)

And if this is just too weak, is there any other algorithm that is more secure, but fast and can be implemented with a minimum amount of bit operations fitting in 32-bit?

Your cipher is a synchronous stream cipher build on a random number generator.

For cryptographically secure random number generators (CSRNG), this is a secure stream cipher.

The problem is, that your random seed is way too small for any security. Trying all possible seeds and seeing if the decryption result makes some sense (assuming the plaintext makes sense) is possible in some seconds, I guess, even with non-specialized hardware.

Also, the random number generator used by your program is quite likely not a CSRNG (otherwise it would not have a 32-bit seed), so there might even be other ways to attack it.

Also, as you don't have any initialization vector, you have the usual stream cipher problem: As soon as you reuse a key twice, you have the same keystream twice. Then the attacker can XOR both ciphertexts and get $c_1 \oplus c_2 = (p_1 \oplus k) \oplus (p_2 \oplus k) = p_1 \oplus p_2$ – and from this we often can extract parts of the plaintexts, especially if these are longer messages.