How broken is a xor of two LCGs? Suppose we define a PRG as the xor of two LCGs modulo a 64-bit prime: something like the following Python code.

p = 14692456042302986707
alpha, beta = 1416483285059710267, 1922202445720274864
gamma, delta = 8868330555542893802, 9736145736144160231

def prg(x, y):
    while True:
        x = (alpha * x + beta) % p
        y = (gamma * y + delta) % p
        yield (x ^ y)

To express it more mathematically, starting from a seed $(x_0,y_0)$ the outputs are $z_1, z_2, \ldots$, where

$x_{i+1}=\alpha x_i+\beta\ (\mathrm{mod}\ p)$,
$y_{i+1}=\gamma y_i+\delta\ (\mathrm{mod}\ p)$,
$z_i=x_i\oplus y_i$,

with constants $p=14692456042302986707$, $\alpha=1416483285059710267$, $\beta=1922202445720274864$, $\gamma=8868330555542893802$, and $\delta=9736145736144160231$.

How broken is this construction, in the sense of being predictable given some output? Of course it can be broken in at most p iterations given two consecutive outputs (guess x, derive y from the first output, and check against the second). But is it more broken than that? Can it be predicted in significantly fewer than p iterations given some amount of output? Is there anything in the literature about attacking this construction? It is surely simple enough that it has been considered.

Please forgive this beginner’s question. I have not been able to find an answer online or in the literature, searching under all the search terms I can think of. Nevertheless I suspect the answer is well-known, hence I am asking here.

I should emphasise that I am not proposing to use this construction for anything security-sensitive (nor indeed for anything at all). I am only curious about crypto fundamentals, and this is the simplest LCG-based construction that I cannot easily break, though I do of course suspect it to be breakable.

Update: In response to Thomas’s request for a smaller variant to analyse, here are some 24-bit constants:

$p = 14435129$, $\alpha = 881969$, $\beta=8713582$, $\gamma=12608927$, $\delta=9284034$.

Here $p$ was selected as a random 24-bit prime, then the others as random numbers less than $p$.

Of course this reduced version can be brute-forced very easily, but the question remains of whether there is an even faster attack.

Distinguishing attack. How broken is it?  It is broken.  As fgrieu notes, the high bit is highly biased.  In other words, the high bit is fairly predictable.  This is enough to distinguish the output of this generator from a truly random bitstream.  That means the stream cipher is broken: that's the definition of what it means for a stream cipher to be broken.  The distinguishing attack requires observing a few outputs and requires very little computation, so it is much faster than brute force.

Of course, this is a distinguishing attack, not a state recovery attack.  Nonetheless, that's still a valid break.

State recovery attack.
There is also a state-recovery attack.  For instance, if you can observe $2^{30}$ outputs from the generator, then with about $2^{44}$ steps of computation you can recover the initial state of the stream cipher (and thus predict all of its outputs).  The running time of this attack is faster than brute force.

The attack chains together several observations:

Correlation to the MSB of a single LCG.  Notice that the most significant bit (MSB) of $z_i$ (the $i$th output from the stream cipher) is strongly correlated to the MSB of $x_i$ (the $i$th output from the first LCG).  In other words, $\Pr[z_i=x_i]$ is quite a bit larger than $1/2$: for instance, with your parameters for the 64-bit generator, $\Pr[z_i=x_i]\approx 0.8$.  This happens because the MSB of $y_i$ is more likely to be 0 than to be 1.

The consequence is that, if we can observe $2^{30}$ outputs from the stream cipher, then we observe a sequence that is highly correlated to the MSBs of $2^{30}$ outputs from the first LCG.
Outputs from the LCG are a linear function of the initial state. Notice that $x_i$, the $i$th output from the first LCG, is related to the initial state $x_0$ of that LCG by a simple linear relationship:

$$x_i = c_i x_0 + d_i \bmod p,$$

where $c_i,d_i$ are some known constants that depends only upon the (public) parameters of the LCG but not on the key or state.  (In particular, $c_i=\alpha^i \bmod p$ and $d_i = \beta (\alpha^i-1)/(\alpha-1) \bmod p$.)

This means that the state of the first LCG at any point in time can be related to its initial state through a simple linear relationship.  This will be useful in the remainder of the attack.
Sometimes, the MSB of the output of the 1st LCG can be predicted given only partial knowledge of the initial state.  Suppose we know the top 44 bits of the initial state $x_0$ (i.e., we know all but the bottom 20 bits of $x_0$).  Then there are some time steps where we can predict the MSB of the output completely, given this information, even though we don't know the bottom 20 bits of the initial state.

In particular, consider any time step $i$ where $c_i$ satisfies $c_i < p/2^{22}$.  Then we can predict the MSB of $c_i x_0 + d_i \bmod p$ given knowledge the top 44 bits of $x_0$, and our prediction will be right most of the time (about $7/8$ of the time).  This means we can predict the MSB of $x_i$ (the MSB of the $i$th output) and we'll be right about $7/8$ of the time.

It is easy to predict which time steps satisfy this condition: since all of the $c_i$'s are publicly known, we can easily enumerate which values of $i$ satisfy the condition $c_i < p/2^{22}$.  Among the first $2^{30}$ time steps, we expect to find about $2^8$ good time steps that satisfy the condition, i.e., about $2^8$ time steps where we can predict the MSB of the output of the first LCG, given a guess at the top 44 bits of $x_0$.
We can verify a partial guess at the initial state of the 1st LCG.  Suppose we have a guess at the top 44 bits of $x_0$ (at the top 44 bits of the initial state of the 1st LCG).  Then the above observations give us a way to verify whether this guess is correct.  We focus on the $2^8$ good time steps where $c_i$ is small; we'll analyze the outputs from the stream cipher at those $2^8$ offsets (the rest of the outputs from the stream cipher are simply ignored in this analysis).  Notice that the MSB of each of those outputs from the stream cipher are highly correlated with the MSB of the corresponding output from the first LCG (the MSB of $x_i$).  Now given our guess at the top 44 bits of $x_0$, we can produce excellent predictions for the MSB of $x_i$ at each of those $2^8$ time steps.  So, we can check whether the MSB of the outputs from the stream cipher appears to be well-correlated to the predictions for the MSB of the corresponding $x_i$'s.  If there is a good correlation, then we infer that this partial guess at $x_0$ is (probably) correct.  If there is no apparent correlation, then we can conclude that this guess is probably wrong.

This yields an attack on the stream cipher that is faster than brute force.  We identify the $2^8$ "good" time steps (where $c_i$ is small) in advance, and focus on analyzing those outputs from the stream cipher.  We enumerate all $2^{44}$ guesses for the top 44 bits of $x_0$, and use the observation above to verify which of those guesses appear to be correct.  For each guess that passes the above filter, we then exhaustively enumerate all possibilities for the remaining 20 bits of $x_0$ and then infer $y_0$.  The test described above should eliminate almost all of the incorrect guesses at the top 44 bits of $x_0$, so I expect the total running time to be approximately $2^{44}$ steps of computation.

I have not tried to finely optimize the running time of this attack, and my running time estimates are pretty crude, so a more careful analysis would probably give a better estimate (I would not be surprised if my estimates are off by an order of magnitude).  Nonetheless, it seems quite clear that this will be significantly faster than the brute-force attack you described; that attack requires $2^{64}$ steps of computation, and this is significantly faster.

Related literature. You might enjoy reading about the "Hidden Number Problem", which is the following: given $\text{MSB}(x_i k \bmod p)$ for many random, known values of $x_i$, find $k$.  That's closely related to a key step of my attack above, though my attack above has to work even in the presence of noise (on the other hand, my attack above is not polynomial-time; it is merely better than brute-force).  Past work on the Hidden Number Problem has been used, for instance, to attack certain implementations of DSA.

Performance. It occurs to me that, implicit in your question, is the follow-up question: "If this can't be broken, why isn't it used?"  The answer to that is: this cipher is going to offer poor performance.

Let's break it down.  If we want 128-bit security (which is the standard of comparison right now), we're going to need to use two 128-bit primes.  If we want to eliminate the distinguishing attack, we're going to need to discard some of the most significant bits; so we might get 80-100 bits of pseudorandom output per iteration of the stream cipher.

Now let's look at how long each iteration of the stream cipher will take, with these parameters.  Well, we have to do two 128x128->256 multiply operations, and two 256->128 modular reductions.  No computer chip offers a "multiply two 128-bit numbers" instruction; if you build it out of 32x32->64 multiplies, you're going to need to do 16 of those per 128x128->256 multiply, or 32 of the 32x32->64 multiply instructions per iteration.  The modular reduction is even worse; I'm guessing that might take something like 100 instructions per reduction.  So we're looking at maybe 250 instructions per iteration of the generator, or maybe 25-30 instructions per byte of output.  This is a very rough estimate, and I haven't benchmarked it, but I think this is enough to make clear that this generator is not going to be competitive with state-of-the-art stream ciphers, even if there are no clever shortcut attacks.


Why are the session keys in DHKE for different values of 'a' the same? In a DHKE scheme with the a prime p = 467. an element g = 4. The element 4 has order 233 and generates thus a subgroup with 233 elements.
after Computing the common key for
A. a=400, b=134
B. a=167, b=134
the session keys are identical = 161

Can someone tell me the answer as to why the key is the same for both schemes given different values for a ?

Since $\gcd(2,467)=1$, one can observe using Fermat's little theorem  that $4^{233}\pmod{467}=2^{466}\pmod{467}=1$.

Thus,
$$g^{a_1}=4^{400}=4^{233+167}\equiv\underbrace{1\cdot4^{167}}_{=g^{a_2}}\pmod{467}=89.$$

This results into identical session keys (shared secrets) $S=(g^a)^b=89^{134}\equiv161\pmod{467}$.


Export from US of crypto software with key-size > 56 bits still needs permission? Elsewhere someone stated that he couldn't publish his crypto software on the Internet, because US Export Regulations require approval, if the key size is greater than 56 bits. I know that several decades ago there were such extremely rigorous restrictions. Could anyone kindly check whether that indeed remains so even today?

First of all, this is not legal advice. However, I've been in the unfortunate position where I've had to deal with this legal nightmare. The new agreement which regulates export of cryptography internationally is called the Wassenaar Arrangement. If your product is what is called a mass market product, i.e available for purchase to the general public without restriction, you can ignore any export restrictions. You can also skip this if your software is open source and available for free for everyone. There's more exclusions such as if your only use is in DRM , if the input to the cryptographic algorithms can no be changed.

If you restrict your sales to a select subset of customers or if your product is exclusionary in some attribute, e.g price is too high to be considered mass market, you need to contact your local government body responsible for Wassenaar compliance.

The section you would be interested in is DUAL-USE LIST - CATEGORY 5 – PART 2 – "INFORMATION SECURITY".

If you feel you might fall under this arrangement it's best to follow the following rules:

If your encryption is based on a symmetric algorithm, keep the key size at 56 bits or less. (e.g AES, DES, Blowfish...)
If your encryption is based on the difficulty of factoring integers, keep the key size at 512 bits or less. (e.g RSA)
If your encryption is based on the difficulty of computing discrete logarithms in a multiplicative group of a finite field, keep the size at 512 bits or less. (e.g Diffie Hellman over Z/pZ)
If your encryption is based on discrete logarithms in a group other mentioned previously, keep the size at 112 bits or less. (e.g Diffie-Hellman over an eliptic curve)

If you do not follow these rules you will come under control of the government body responsible for Wassenaar compliance. Which is extremely likely to become a huge bureaucratic burden on your organization as export controls are extremely poorly set up to deal with things like software where you may have many thousands of customers. It is best to avoid it unless cryptography is an integral part of your product. Most companies and individuals are unaffected by the arrangement as it tries to be narrow enough to only capture the companies which trade with foreign governments.

If your system does any sort of cryptoanalytic work it's generally considered even more sensitive and your odds of being in export controlled territory increases.


Why are there no OTP ciphers? We all know the OTP is unbreakable and we all love the OTP (judging by the amount of question on this site).

The strength of the OTP is not that it is unable to find a word without the key but you can find any word. Now obviously if we could create a cipher which output would be only letters and several keys would output several grammatically correct sentences (or what ever output you would expect to be a valid output). But is such a thing possible?

I find it odd the OTP is the only one with this characteristic. If we would take AES with a 128 bit key and encrypt hello world" with AES-CBC and key "Acknowledgement" (nvm the IV)

9e 6c d3 86 33 aa fa 09 59 b1 75 86 85 e1 5a ea

why wouldn't there be keys in the 128 bit space which could decrypt this to valid plain texts other than hello world.

With my above example if there are multiple valid decryptions for the given ciphertext then it won't be every single possibility which would make it weaker than the OTP since an attacker could sort the valid plain text on relevance. But when the valid plain texts are many (just not all possibilities) the chances of an attacker finding the right one are negligible.

lets disregard OTP for a second.

Is it possible to create a cipher with the following requirements:
For each N keys and X valid plaintexts there is a X/N chance of the decryption of the ciphertext resulting in a valid plaintext. Where 1 key can be used to encrypt multiple plaintexts where the key is smaller than the overall lenght of all plaintexts without posing a weakness. (similar to a block cipher) and X/N is sufficiently large for it to be impossible to determine what the correct plain text is.

Example:

Key K = "secret"
Plaintext p = "hello"
Plaintext p2 = "noway"
Ciphertext c = "aqfum"
RandomKey N = "wrong"

Encrypt(p, k) = c;
Decrypt(c, N) = "array"
Decrypt(c, N2) = "pozdi"
Decrypt(c, N3) = "bonus"

Encrypt(p2, k) = C2 = "almost"

Scheme(C2, C) != K

Has anything ever been tried or am I wrong in assuming that this is possible with reuse of the key?

NOTE
With cipher I mean an algorithm in the sense of something similar to a block cipher.

You need to understand that any variation on the OTP would ultimately be equivalent to the OTP security-wise, since it is unconditionally "secure" (the ciphertext leaks zero information about the plaintext or the key), and so you'd just making it harder to compute for now reason. So, sure, you can use the OTP, or some variant thereof, on 128-bit messages with a 128-bit key, but once you use up that key it's gone. With AES you can encrypt way more data with a single key.

So, looking at your question, you could, conceivably, design a cipher that takes in a 128-bit key and a 128-bit plaintext block, and encrypts it so that the 128-bit ciphertext provides exactly zero information on the plaintext or key (making it unconditionally "secure"). AES probably does not quite satisfy this condition, but the OTP does, and you can certainly design (redundant; see above) variants that could achieve the same thing. But the point is that you can only encrypt a single 128-bit block of plaintext with that 128-bit key. Encrypt any more than that, and the multiple ciphertext blocks must together leak sufficient information on the plaintexts for a (computationally unbounded) attacker to retrieve the corresponding key, no matter what cipher you use.

Basically, there is nothing to improve on; what you are asking for is impossible, and you cannot "work around" the OTP's key reuse problem by chopping the plaintext up into 128-bit (or any size) blocks.


Knapsack and block size clarification I am a bit confused about the knapsack implementation regarding the bits and block size for encryption.

In the example from this link (https://nrich.maths.org/2199), the knapsack size is 6 and the String that they encrypt has only 6-bits in 3 blocks.

My understanding is a Char can be represented by 7 to 8-bits (UTF-8) and the knapsack size must be at least of size 8 to encrypt one char. Meaning that if I want to use a knapsack for encryption/decryption I must use a knapsack size of 8. Is my understanding correct?

The example there is instructional, not for implementation. Also, if you only want 26 characters plus a few punctuation marks, 5 or 6 bits would be enough.


How to explain indistinguishability obfuscation (iO) to my grandmother? At the risk of oversimplification, how do I explain indistinguishability obfuscation (iO) to my grandmother?

iO removes all metadata from the program.


probability of N hash digits colliding What is the probability of the first N hash digits colliding? for example i made a script that appends the first  5 digits of the file's sha1 hash to the name of the file.

So will the probability of a collision be 16^5=1048576? Am i properly calculating the probability of a collision.

The birthday problem is the generic name for such questions. You have $n$ values, selected randomly and uniformly in a space of size $t$; the probability that at least two of these values are identical is roughly equal to $n^2/(2t)$. When $n$ becomes close to $\sqrt{t}$, then the probability raises sharply. In your case, with 5 hexadecimal digits, you have a space of size $t = 16^5$, so you can expect your first collision, on average, when you get about 1000 values or so.

An intuitive way to think about it is that $n$ values make about $n^2/2$ pairs, and, "somehow", each pair has probability $1/t$ of being a collision. (The pairs are not independent of each other, but the intuition still works in that case.)


Quantum Random Oracle Model Let $\mathcal{H} : \{0,1\}^* \rightarrow \{1,\cdots,n\}$ be a hash function.

I believe that in the Random Oracle model, the probability that an adversary $A$ can find a message $M$ such that $\mathcal{H}(M) \leq k$ is at most $(q+1) \frac{k}{n}$, where $q$ is the number of queries $A$ makes to $\mathcal{H}$.

What happens for a quantum adversary $B$, which can query $\mathcal{H}$ in superposition? I suspect that the probability that $B$ produces a message $M$ such that $\mathcal{H}(M)\leq k$ is bounded by $c q^2 \frac{k}{n}$, where $q$ i the number of quantum queries that $B$ makes to $\mathcal{H}$ and $c$ some constant.

I suspect this because this can be done with Grover's algorithm and I heard that Grover's Algorithm is optimal in some setting.

Is this true? What values of $c$ would work? How would you prove this?

You are right, the success probability of a $q$-query quantum adversary is $\Theta(\frac{k(q+1)^2}{n})$. You can find a proof of the upper and lower bound in this paper.

The upper bound uses similar tools as for the optimality of Grover. The tricky part is that the proof of optimality for Grover's algorithm is given for the worst-case but I guess you and people in crypto in general are mainly interested in the average case complexity. So you need a more advanced toolkit.

The lower bound is more or less applying Grover and analysing its success probability for the average case.


AES-128-CBC padding size I'm trying to figure out how padding works by seeing what happens when I try to encrypt a 16 byte file with AES-128-CBC. My understanding was if I encrypt a file of size, say, 28, then there would automatically be 4 bytes of padding to make it 32. But when I encrypted my 16-byte file, the size ended up being 48 bytes. I did research and learned that a single padding block is automatically added to direct multiples in order to distinguish the padding from the plaintext, but if that's so, then why is it 48 bytes and not 32 as well (16 plaintext + 16 padding)?

Is your "-K" in the code in uppercase or lowercase? If it is in lowercase, the encryption will automatically add a salt value into your cipher text, causing it to have more than 32 bytes. CBC will pad it until it reaches 48 bytes later(the multiplication of 16).


What does it mean when two encrypted files, encrypted with the same method but with different keys, when xor'd together, produce a repeating pattern? Let's say I have fileA and fileB, both encrypted somehow, but in the same method with different keys.
If I xor them together, they will make a repeating pattern of 32 bytes length.
What does that say about the repeating pattern, the encryption pattern, and the likelihood of the unencrypted files to be identical?
Is there any way to extract the keys used to encrypt them?

Is there a way, other than to open up Ollydbg and try to reverse engineer the decryption procedure?
The program contacts a server, sends a certain unique code, and the server replies back with an md5 hash.  Then the server sends back the encrypted file, which is easily decrypted by the program.  I want to reverse engineer this program and encryption method.
This is not a homework question, this is a real situation that is tormenting me.
The decrypted plaintext is either Lua source or Lua VM bytecode, with a small possibility of being XML.
Edit:  I now realize that the repeating sequence is probably two different MD5 hashes XOR'd with each other.  Is there a method to analyze and try to extract the individual MD5 hashes?

The two plaintexts are almost certainly identical.  At the very least, any difference between them must be representable in 32 bytes, since that's as much information as the XOR of the encrypted files contains.

Assuming that the plaintexts are indeed identical, we can also see that changing the encryption key has a very simple and predictable effect on the ciphertext: every 32nd byte is affected the same way.  Clearly, this cannot be a semantically secure encryption scheme.

Indeed, the most likely explanation of the phenomenon you observe is that:

the two plaintext files are identical, and
the encryption simply consists of taking a 32-byte key (or possibly the 32-byte hash of a key) and XORing it with each 32-byte block of the plaintext.

If true, this is a very weak cipher, and it should not be hard to break.  A couple of methods to try would be:

If you can guess some part of the plaintext, you can immediately get the corresponding part of the key by XORing the guessed plaintext with the ciphertext.  For example, if the plaintext is XML, there's a good chance it'll begin with something like:

<?xml version="1.0" encoding="utf-8" standalone="no"?>

With a bit of luck, this can reveal the entire key!  Similarly, I believe Lua bytecode files should have a more or less fixed header that should also reveal at least part of the key.
Even if you can't directly guess the plaintext, you can make use of the fact that the key repeats, essentially making the cipher a many-time pad.

One way to attack such a many-time pad is to use crib dragging.  Basically, you guess an $n$-byte string that's likely to occur somewhere in the plaintext (such as, say, function in Lua code) and XOR it with each $n$-byte substring of the ciphertext.  Each XOR will yield a candidate $n$-byte substring of the key, which you then XOR with the corresponding parts of the ciphertext.  If the guess was wrong, you'll mostly get garbage, but if and when you guess right, the decrypted plaintext suddenly starts making sense.

Another way to attack such a cipher is to split the ciphertext into 32-byte blocks, take one of the blocks and XOR all the other with it (which cancels out the key, leaving you with an XOR of the plaintext blocks), print out the XORed blocks as a hex+ASCII dump (as with xxd -c 32) and examine the columns.  With the help of an ASCII table, you can infer a lot about the plaintext block you chose to XOR with the others (and thereby about the key).

Alternatively, if you're feeling lazy, you can just download xortool and feed one of the ciphertexts to it.  With a bit of luck (and the right options), it'll spit out the key and the plaintext (or at least something close enough for you to finish the job by hand) for you.


Hashing/encrypting an integer to produce an unique integer in the same range I'm looking for a function or set of functions that can produce a pseudo-random permutation on an input set of arbitrary size.
Given a set of $M$ values in range $0..M-1$, where $M$ is positive integer,
I need a function $I' = F(K,M,I)$, where $I$ is a value in range $0..M-1$, $K$ a key (to be determined) and $I'$ a value in range $0..M-1$.
For each value $I$, there must be only one $I'$ value, and for each $I'$ value, only one $I$ value.
Having the reverse function $I = F'(K,M,I')$ is not strictly needed, but it seems implied by requirement.
So this looks like an encryption function.
If $M$ was $2^{128}$ or $2^{256}$, I could use a block cipher.
If $M$ was a multiple of $256$, I could use a stream cipher (byte oriented).
But $M$ could be any value, without any special properties: it's not required to be odd, even, prime, power of two,...
I'm not aware of such encryption or hash function.
Could you help me to formalize what I need and give me some hints to find an encryption/hash scheme that suits my needs?
I seem to have found what I was looking for: Format Preserving Encryption (FPE), but I need some help to sort this out.
EDIT: In order to be strong, I think it's important the function should not be self-inverse, e.g., given $I' = F(K,M,I)$, $F(K,M,I')$ should not return $I$.

You indeed need Format-Preserving Encryption. It is a pretty easy concept, and this paper by Black and Rogaway should be readable for non-specialists. The simplest method you should be satisfied with is to use a cycle-walking cipher. Suppose :

Take $I'\leftarrow E_K(I)$;
Repeat until $I'\in [0\ldots M-1]$,

where $E_K$ is a conventional cipher with key $K$. However, the block size $n$ of $E$ should only slightly exceed $\log M$, otherwise the procedure would take too long.

If a cipher with such block length is not available, the following construction, known as Swap-or-not cipher, should help:

$E_K(X):$

for $i\leftarrow 1$ to $8 \log M$

$K_i \leftarrow AES_K(i) \pmod{M}$;
$X' \leftarrow K_i-X \pmod{M}$;
$X'' \leftarrow \max(X,X')$;
if ($F_i(K,X'')=1$) then $X \leftarrow X'$.

Here $F_i$ is some key-dependent predicate of $X''$. It must have algebraic degree or higher. For instance, it can be a polynomial of degree 2 over $F_2$, whose coefficients are encryptions of some constants by AES on the key $K$ (similarly to $K_i$).


Tiny Firmware Authentication I am developing a product based on the NXP LPC11C24 microcontroller. It will communicate with PC software to perform its work. I am attempting to build a secure firmware update functionality. The PC program will download firmware images from us and send them to the device, decrypting, verifying, and writing the image to its flash memory.
I want this mechanism to be secure against PC software analysis and trivial attacks on the encryption. Assuming the attacker has full knowledge of the device and PC protocol, uploading an unauthorized firmware image should be more difficult than, e.g., defeating the chip's code protection, clock glitching, side-channel attacks, or similar.
The difficulty is space limitations. I have a hard limit of 4KB of ROM (ARM Cortex-M0 code, for size reference) and a firm limit of 1KB of RAM, of which I can budget perhaps 2.5KB and 600 bytes, respectively, to the decryption and authentication process. In light of this, I chose AES-128 CBC encryption with CRC-32 authentication. My method is to create a random IV, split up the firmware image into 256-byte blocks, and add a CRC-32 checksum after each block, repeated four times to pad to the AES block size, then encrypt the 272-byte block. The checksum is to catch data corruption during the transfer from PC to device (the PC can use SHA-256 to verify integrity from the web) and to authenticate the block. The PC cannot do the authentication because the PC-to-device protocol would be trivial to intercept.
The firmware update process would be as follows:

Enter firmware update mode
Receive IV, initialize AES
Receive encrypted 272-byte block
Decrypt block with AES-128 CBC
CRC-32 checksum first 256 bytes, verify checksum matches last 16 bytes
If verification fails, stop the process. If successful, write 256 bytes to flash.
Repeat from 3 while blocks remain

I have done some research, and it seems this CRC then AES method is trivially vulnerable (detailed in this other answer), but the attacks rely on known or chosen plaintext, which will not be the case here. Only us, the manufacturer, will be releasing updates, and they will always be encrypted. Is this then sufficient protection for my scenario, or at least harder to break than decapping the chip or exploiting the chip manufacturer's code protection system? Is there a better way that will fit the extremely tight memory requirements?

The title says authentication, that is we want only the real firmware to load and run, unmodified. There are fast, practical code signature techniques for that. Most importantly they require no secret in the target device.

The baseline would be that the target contains an RSA 2048-bit public key with $e=3$, and uses that to verify an RSASSA-PKCS1-v1_5 signature with SHA-256 of the firmware. RSASSA-PSS would be nice, at a slight expense in code complexity.

Given that the firmware won't fit in RAM, signature verification must be after writing the firmware in Flash but before running it. That check could be at each startup, if we can afford to save the 256-byte signature in Flash, and some milliseconds of startup delay.

This can be done with 2kB byte of Flash, including public key (256 bytes, can get down to <100 with special generation techniques), and within the stated RAM budget. Using Rabin signature (similar to RSA but with $e=2$) can save some time, RAM, and even code.

This is quite secure against all except attacks that modify what the hardware does (e.g. with a JTAG probe, or power supply glitch). For proper implementation, and if the whole firmware is secure (free from buffer overflows and similar), there is excellent insurance general users can't reproduce the attack on their device.

For secrecy of the code, as in the body of the question, there must be a secret in the target. Serious adversaries will manage to extract that secret, and will be able to decipher the code. My advice: use encryption, but know it's breakable.

I see no reason to use AES, unless it is required in the application AND the loader's AES code is reused by the application. ChaCha seems a better choice.

I won't comment on the proposed solution beyond stating that:

It is inconsistently described: CRC-32 is 4-byte, leaving how that "matches last 16 bytes" a mystery.
It writes the firmware by small 256-byte chunks, therefore it gives no insurance that it leaves the firmware as a whole in a consistent state in case on interrupted download. This is a tried and tested avenue to disaster.

The correct solution to issue 2 is:

Invalidate the current firmware when firmware download is initiated, leaving only the bootloader running at next reset; this insures that download can be started over in case of power loss.
Have the bootloader download the code in Flash.
When download is done, check the signature of the whole firmware just downloaded and written, and if OK re-enable the firmware to run at reset.
Optionally, the signature can be part of what's written in Flash, and the check performed again at each reset.

The bootloader can use the whole device's RAM, thus the technique works down to 1kB RAM total (rather than 8kB here).


Re-encryption without knowing the secret Which encryption algorithms could be used for the following scenario?

A user stores a file encrypted by someone else
Then the user is asked to re-encrypt the file with a new secret
The user stays unaware about the clear text every moment

To achieve that the user can be provided with a kind of "diff" secret, I suppose. It may be a password based algorithm.

This is possible with the Integrated Encryption System

In this system, there are global values $p$ (a large prime) and $g$ (a generator of a prime subgroup in $\mathbb{Z}_p^*$).  A private key is a value $x$ and the corresponding public key is the value $y = g^x \bmod p$.

To encrypt a message $M$ using the public key $y$, you select a random value $r$, and publish the pair $(C, D)$ with $C = g^r \bmod p$ and $D = E_{y^r \bmod p}( M )$ (where $E_k(M)$ is the message $M$ encrypted using the key $k$ with some symmetric cipher).

To decrypt a message $(C, D)$ using the public key $x$, you just compute $C^x \bmod p$; this is the value $y^r \bmod p$, which you can then use as the key for the symmetric cipher in $D$.

Now, here comes the interesting part; to update the key from $x$ to $x'$, what the holder of the private key would do is compute $s = x x'^{-1} \bmod p-1$; he then sends it to the user.  The user then replaces $(C, D)$ with $(C^s \bmod p, D)$

We can see that the updated ciphertext $(C^s \bmod p, D)$ is a valid ciphertext to the new public key $y' = g^{x'} \bmod p$; the decryption computes $(C^s)^{x'} = C^{x}$, which is the same key that was originally used to encrypt D, hence decryption works as expected.


In RSA, the keys do not consist of a single value; they consist of multiple values:

the public key consists of the modulus and the public exponent;
the private key consists of the modulus and the private exponent.

So there are two exponents: one for the public and one for the private key. You perform modular exponentiation with the public exponent for encryption or verification and modular exponentiation with the private exponent for decryption or signature generation.

The public exponent is deliberately kept small to have more efficient public key operations. Generally it is just set to the fifth prime of Fermat, called F4. It only has two bits set to 1 to further optimize the calculations.

It might be that the more efficient Chinese Remainder Theorem (CRT) parameters are included in the private key. These are basically the parameters from which the modulus and exponents are derived such as the prime numbers P and Q. It is possible to speed up RSA private key calculations using these parameters. To speed calculations even more it may be that more than two prime numbers are used, resulting in multi-prime RSA.

Your posted RSA PRIVATE KEY is a private key whose format is specified in PKCS#1, which is the RSA standard used in most applications:

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

You can see its contents here. Alternatively you can view it using the command line openssl asn1parse:

    0:d=0  hl=4 l=1188 cons: SEQUENCE
    4:d=1  hl=2 l=   1 prim: INTEGER           :00
    7:d=1  hl=4 l= 257 prim: INTEGER           :D75430BE504D406163BD9C496689A5488A596B85897375040DA621E7200F091A040B95499B8F4CB195348215CD3639EFE3426396EE9686F42860F454BAAEEEA3B274C753C519D76C869D77E7B3FA8EDAF9EBB7B401C40DD65828B5BE068158D3101E78AB87149FBC3F5DB8BCBB5B2200CB6594995B64D5C5570A53F3805B1888F4A829D6D8D3449DFA6E09C3799078A56DA2AB92E8AC2CF0DC67A158F8F453F99F71CEC2FAEA3736378DF7128E6518738DA6E4F2B0B686711A49E639E8B80D04018E1B6F608FE5E86072B2F27E4FD4BD2788F998B320762F8654B5EF9D7ACAD5F71AD8F64C46330932F45C4DF5FD2E932DE6A36786A7C82F5B755F4F7C4C08B3
  268:d=1  hl=2 l=   3 prim: INTEGER           :010001
  273:d=1  hl=4 l= 256 prim: INTEGER           :3ABBC81FE11F71341F5494D0A09B62EE0A6EA19967088B1E73EAA0CCBE3DDBA9B0F8C7DBB006C2509DF6189581C80CBD962B81A6A5A581620FB18273AA081527A98198ED0C9223E48243697555EE3E1114A26B153A7613A027A3D30EE60F59FF1822779FB1D4BA4D4AAB71BC690E4E9410E6C045A45C38C2FF1EDE0F492F8FDD2B54749B5403F17C25153F6B347AB7DFC034623EF7A94BD2907C31A833596FFD3C3D32788822D97C4403911DE89040CC6A96FD91C5172E853AE39A189645A1EA077E40B64CD203EF55542202C458E8016BDA31FE7B767B1EDC1304A1427450D58E605D08C297D6D50866B8BE51D04A567D8F77D4A6293CEF2C6C60D9DB272821
  533:d=1  hl=3 l= 129 prim: INTEGER           :F35A0E03E3A004A0E42A9FD1CC470492E0227654DB00B734EE45525866587C3F97948D7102B72CDCBFF2C68292423A23ADB75BFB0A7DF61C37B93EFF18664A0ADFA24353FFBF5E9E1BE03E766A87E7F0B50C19A94CE870A3E40B7CBDDDD091A7D940D181F3493F0876DBEAD275EFA27EE60C69A76599566B35FF14B95CDEF1BF
  665:d=1  hl=3 l= 129 prim: INTEGER           :E285460B8B85C62534B7DD312603555549723219E1541C250A81D3AA4A107B3B9A4DA9F3D0BD6A068E76F8674A20196B43D8BBE1ABEF886BA9E655D3C164D5985C4A03EBC0EE88C29A37F4DF6E2DD3CA286CFB13ECE0E9EA64734269BA50A46358238844DD6B42C15537C2CF62491005461B1B9E21A8D61EFA81802BF9F2BE0D
  797:d=1  hl=3 l= 129 prim: INTEGER           :DC25E3F7F0BC9A7352F69C8E9756C7F4777FB5BD1E428F7AFAF30B839D52FF542834E3A010ECD550FEF50A50A52FF498C256D6874CFE96DF002A3DAB58CF70BC5583DD94E8109FF03917AC6A44059EF64B531F03E1E785BF3E56860ADDD8096CE7459443136C77F198556B21EA3F57A9A5442570A2A10D64FFFC3B2B55B0FAD1
  929:d=1  hl=3 l= 128 prim: INTEGER           :78E68F2B2C4DBB23328F0C04E67812FC9155DCFDC9315E503ADA6E41CE841B72057A7C4240E0480DB5CE33E8D53C6AB4C0A2962CEDDACC2242AD4893DBFDD8AF185AFCDAC0BFCFC8A60D45AA5721289016A18C24E76268170D842327512527884A8BB478A50151C0E49DFD6138E12C26D473357B6215BE2B0CA33FE8B8E061A5
 1060:d=1  hl=3 l= 129 prim: INTEGER           :88EE8B43C85D95C6B0DA7E574D3DEA4769521535E41F2FC24883850164238AF30DB07D826829452345740B1D7CB1C689729A04A95FEAF5DD32AC1847148FC7BC503ED43DA2378F82B3A06D877972ADC01CB32B99F2504EF78759EE1A5D5E4776CFA4B2D2FE7957F7C6F60ED2683DBBCAEC55A296AA41832D38DFECEA61484102

As it is quite tricky to parse these kind of formats, it is best to use a library that already contains an encoder. Implementing a full ASN.1 decoder requires knowledge about compilers, parsers and code generation. It's interesting enough, but it is hard to do as well.

Note that PKCS#1 specifies a structure. This structure is encoded using BER / DER, the basic or distinguished encoding rules. These are however binary encodings. What you've specified is obviously text. This text is called PEM for privacy enhanced mail. Mail is a text format, so it cannot deal with binary. For that reason the binary is base 64 encoded and a header and footer line are added so that the type of key is known. OpenSSL uses this as default format for keys.


Is K=1 a valid random integer in ElGamal signature? In the ElGamal signature scheme, in addition to the public/private keypair, a random integer $K$ such that $\operatorname{gcd}(K,p-1)=1$ is chosen in the range $[1,p-1]$.

This clearly excludes $K=p-1$, because $\operatorname{gcd}(x,x)=1$ for any $x$, but not $K=1$.

However, if $K=1$, the first part of the signature is $S_1 \equiv g^1 \bmod p\equiv g \bmod p\equiv g$, and the attacker knows it. Even worse, the attacker can use $S_2$ to obtain the private key.

Why is $K=1$ a valid choice? No source that I know of mentions this. Is it something considered so trivial that is not worth mentioning, or did I miss some mistake in my reasoning?

I understand that the probability to choose $K=1$, for a large prime, is vanishingly small, but in my opinion one shouldn't leave these things to chance.

Why $K=1$ is not excluded? You can also ask why $K=2$ is not excluded. It always possible to calculate $g^2$ and by keeping $(g^2,2)$ in a lookup table, you can also recover the secret key if you see $S_1 = g^2$, in which case $K$ happen to be 2. So as $K =3$, $K= 4$ and so on so forth. As you can see, 1 is not that special.

The reason why they are not excluded is because that $K$ is chosen at uniformly random from the range. For an adversary who has only limited computational capacity, it can only guess polynomial number of $K$ and does the computation, but if the signer picks his $K$ at uniformly random, the probability of the adversary guessing the right $K$ is negligible. So as long as the signer does his job properly, we don't need to worry about $K$ being a specific value.


/dev/random only needed for key generation / CPU pattern encryption Consider the following scenarios:

using OpenSSL to encrypt a file with Rijndael-256
using LUKS to encrypt a hard-drive that is used every day

Exactly when is entropy from /dev/random needed for a crypto process?
Is it only needed for the key generation or is it also needed for the encryption process itself?

When the CPU is executing a crypto process (key generation or encryption) for a program, does the CPU cause some kind of pattern (like a fingerprint of the encrypted data) as it processes? Can this "processing pattern" then be used to break the encryption and see the plaintext?

This first scenario: it depends on the specific command, but it should need randomness when generating the key (or when deriving the key from a password, when generating the salt) and when generating the initialization vector for encryption.

The second scenario: when generating the master key, and when generating the salt used with the user's password to encrypt the master key. It does not need randomness for encryption, since there is no place to store initalization vectors. The algorithms usually try to compensate for this by using the index of the disk sector in the algorithm.

Also, I'm not sure if /dev/random is used; I think that at least OpenSSL uses /dev/urandom/.

For the second question, there are side channel attacks as mentioned. Depending on the implementation, it may be possible to retrieve keys by analyzing timings or energy consumption.


What makes a hash function good for password hashing? Using a cryptographic hash to store e.g. passwords in a database is considered good practice (as opposed to storing them plaintext), but is subject to attacks on said cryptographic hash, assuming the database is compromised.

Which properties of a cryptographic hash function make it suitable for hashing passwords and the like?

Which functions are secure enough, while still being widely available, without patent issues and not too computationally intensive?

For password-hashing, you should not use a normal cryptographic hash, but something made specially to protect passwords, like bcrypt.

See How to safely store a password for details (this article advocates the use of bcrypt).

The important point is that password crackers don't have to bruteforce the hash output space ($2^{160}$ for SHA-1), but only the password space, which is much much smaller (depending on your password rules – and dictionaries often help). Thus we don't want a fast hash function, but a slow one. So your not too computationally expensive requirement is actually not possible to met. Bcrypt and friends* are designed for this.

*Bcrypt and friends: All slow hash functions. There is PBKDF-2 (which basically just iterates a fast hash with salt some configurable large amount of rounds, and thus the brute force can be easily parallelized - but it is mentioned in a NIST standard, which might be important for certain uses), bcrypt (which additionally needs 4 KB of memory, which makes parallelization (of the brute force) on standard GPUs quite slow, but can be still attacked on custom hardware with 4KB cache per processing unit), and scrypt (which takes not only a configurable amount of time, but also a configurable amount of space to execute (with a possible trade-off to time), and thus brute-forcing can not be easily (cheaply) parallelized).

Of course, you always should use a salted hash (a salt is automatically included in bcrypt). A salt is stored together with the hash in the database (e.g. it is not more secret than the hash), and will be hashed together with the password to produce the hash.

A salt alone does not help against a brute-force attack against specifically your password, but it helps against rainbow table attacks (i.e. attacks with precomputed hash lists), which can attack with the same effort all passwords everywhere at the same time, instead of only all passwords with the same salt (which should be about only one).

There is also the concept of a "secret salt" (also known as pepper), which is not stored together with the password, but at some other location not accessible by a possible attacker. (You would then usually use the pepper, as a non-user-specific piece of information, together with a normal salt.)

This does work only for some attack scenarios, where the attacker does have only (reading) access on the database (or maybe some less secured backup copy on it), but not on this pepper data (i.e. we have an attacker who can't yet execute arbitrary code on the server).

Another possibility would be to use some kind of cryptographic hardware (a token) attached on the server with an embedded key, which does some hashing operation on salt, key and password to produce the hash. Make sure to rate-limit this in case it is stolen, and make sure it does not have an interface to retrieve the secret key, otherwise your attacker (if she succeeds to gain execute access on the server) can use this, too.


When do I need to use hybrid cryptography? I need to provide confidentiality for a protocol. The protocol message size is between 100 bytes to 500 bytes. Do I need to use asymmetric encryption or hybrid cryptography?

The protocol message size is between 100 bytes to 500 bytes. Do I need
  to use asymmetric encryption or hybrid cryptography?

To support 500 byte messages, you need about your (direct) encryption scheme to work on about 5000 bits (e.g. for RSA, Paillier, ElGamal) to provide room for the padding to gain CCA2 security. At 5000 bits, these schemes become somewhat slow, so you should definitely make a measurement in either case between a hybrid and a direct solution (using e.g. RSA-5000 with OAEP and maybe the exponents 3, 17 and 65537).

  What about Curve25519?

If you could reversible encode your message onto an elliptic curve point (not easy), you could use ElGamal or Cramer-Shoup on Curve25519 to encrypt messages of up to 32 bytes. Of course 32 bytes is much less than you want to encrypt so direct encryption is out.

Normally with Curve25519 and the other schemes you will do hybrid encryption, either as ECIES or directly by encrypting a symmetric key (using a CCA2 secure or specialized scheme like RSA-KEM) and AE encrypting the message. As an additional bonus you can then potentially re-use this shared key for multiple messages if you can do the neccessary nonce / IV management, i.e. you can guarantee that you can come up with a unique nonce for each message.


RSA: Given (e,c,d) is possible to solve? is it possible to solve RSA without n?

I know e, c and d

No, it would appear to be a hard problem; being able to recover the plaintext allows us to recover $n$ (at least, for small $e$), and recovering $n$ would appear to be difficult.

Knowing $e, d$, we know that $ed \equiv 1 \pmod{ \text{lcm}(p-1, q-1)}$, or equivalently, $ed - 1 = \frac{k}{\text{gcd}(p-1, q-1)} (p-1)(q-1)$, for some integer $k$.

As both $k$ and $\text{gcd}(p-1, q-1)$ are likely to be small (and from $c$, we can get a rough idea about the size of $n$), we are likely to be able to have a plausible guess to $(p-1)(q-1)$.

However, to convert that to $pq$, we'll need to factor $(p-1)(q-1)$; while $p-1, q-1$ both a likely to have some small factors (allowing us to reduce the size of the problem a bit), however, it appears likely that there won't be enough small factors to reduce the size enough; performing a complete factorization won't be all that much easier than the original 'factor $pq$' problem...


Differential bound of the S-Box in GOST R34.11-2012 In Russian GOST R34.11-2012 LPS-transformation is used. LPS gets all of its non-linearity from the 8-bit S-box S, which apparently has been designed to offer resistance against classical methods of cryptanalysis. Its differential bound is P = $8/256$ and best linear approximation holds with P = $28/128$ . There seem to be no exploitable algebraic weaknesses.

Can you explain what is "differential bound of the S-Box"? I think that it's a probability: P(S($x_1$) $\oplus$ S($x_2$) = b | $x_1$ $\oplus$ $x_2$ = a) for random $a, b$. Is it a correct definition? And LPS seems to be no exploitable algebraic weaknesses because there are 64 S-Boxes and so, differential probability of the LPS at all is $(8/256)^{64}$?

Differential bound of the sbox is an upper bound on the probability of the differential characteristic below, i.e.,
$$P(S(x_1) \oplus S(x_2) = b | x_1 \oplus x_2 = a)\leq \frac{8}{256},$$
for all $a,b.$

A differential used for cryptanalysis is assembled by joining different differential characteristics from different rounds. This results in a number of Sboxes being 'active', i.e., taking part in the overall differential.

However the probability of a differential would be upper bounded only by
$$(8/256)^k$$
where $k$ is the number of active sboxes that are part of the differential. If there are nontrivial attacks, this $k$ will be much smaller than 64.


Why can ECDSA public keys be sent over an insecure network, while ECDSA is used to sign ECDH public keys to securely be transported over the network? Basically the title says it all. I am trying to develop and understand an ECDH-ECDSA encryption.

My current approach to provide some form of authentication to the ECDH is to use ECDSA to sign the public key of ECDH before sending it over the network, in order to allow the receiver to verify the sender.

However, after reading up on some ECDSA implementations, I am quite confused about the way ECDSA public keys are being handled.

In my implementation, I wanted to hardcode a static key pair into both sides, as I am not planning on making it a high scale public implementation. That way I don't have to expose my keys and fear any man in the middle attacks - given I understood everything correct.

However, most solutions seem to simply send the ECDSA public key over an insecure channel.

But isn't this what ECDSA is trying to prevent? Why is the algorithm doing exactly what it is trying to prevent itself?

The attack that we're trying to prevent is a Man-in-the-Middle attack; this is one where an attacker (who is assumed to be able to modify messages) can step into a negotiation.  In effect, when Alice tries to negotiate with Bob, Mallet steps in, and so Alice actually negotiates with Mallet.  Mallet can then negotiate with Bob (posing as Alice), and then, forward any traffic he gets from Alice to Bob, and any traffic he gets from Bob to Alice.  As far as Alice and Bob are concerned, it looks like they have a secure connection (but Mallet can listen in to all their traffic, and also modify it at will).

To prevent this from being a possibility, Alice and Bob need to be able to do something that Mallet cannot.  There are a couple of possible ways, including:

Alice already knows Bob's public key, and Bob already has Alice's public key.
Alice and Bob both have a certificate from a trusted certificate authority.

There are other possibilities; hwoever these two are relevant to your question.

  However, most solutions seem to simply send the ECDSA public key over an insecure channel.

I would certainly hope not; as you can see, Mallet can generate his own ECDSA public key, and so this would do nothing to prevent a MITM attack.

What these solutions do is actually have Alice and Bob have certificates.  What a certificate is is essentially a message "Alice's public key is [this], signed Trent" (where Trent is the friendly neighborhood CA).  Trent gives Alice her certificate (based on Alice's public key) before negotiation ever happens, and Trent also gives Alice his public key.  During negotiation, Alice gives Bob her certificate; Bob can then verify that a) the identity listed in the certificate is the perform Bob thinks he's talking to, and b) it actually is signed by Trent.  If both are true, Bob then knows Alice's public key, and that can be used in the protocol.  Mallet cannot generate such a certificate; Trent won't give a certificate to Mallet that lists Alice as the owner; Mallet cannot reuse Alice's certificate (as he doesn't know Alice's private key); Mallet cannot generate his own certificate (as he doesn't know Trent's private key).

So, once Bob knows Alice's public key (and similarly, Alice knows Bob's), they can then use the each other's public key to authenticate the ECDH exchange, and all is well.

One other thing I want to bring up:

  In my implementation, I wanted to hardcode a static key pair into both sides

If you're not actually using a certificate authority, then you could have both sides generate a long term ECDH key pair, and just install Alice's public key on Bob, and Bob's public key on Alice.  This would also foil a MITM attack (as Mallet can't replace the public keys with his own).  There is an issue about updating the keys (we never want an immortal key; every key ought to have an expiry date), and there's no obvious way to update keys here.

Of course, if that's what you're doing, and you're happy with it, then it's not clear why you actually need to bring public key crypto onto the table.  If Alice and Bob both share a Message Authentication Code (MAC) key, then during negotation, Alice and Bob can exchange nonces, and then both compute $\text{MAC}_{key}( Nonce_{Alice} | Nonce_{Bob} )$; that's a shared secret that's a whole lot faster and easier than ECDH.

The other concern is a potential device compromise attack (which may or may not be relevant to you).  In this attack, we assume Mallet breaks into Alice, and learns all her secrets.  Now, going forward, Mallet can then pretend to be Alice (and there's nothing we can do about that).  However, with the ECDH preconfigured private keys (or the shared MAC key), what Mallet can do is go back and decrypt previously recorded communicates by Alice (because Mallet now keys Alice's private key).  In contrast, in an ECDSA/ECDH scenario (where Alice and Bob select the ECDH keys randomly each time), he cannot (assuming Alice zeroizes all her keying material when she's done with it).

Now, obviously, and ECDSA/ECDH protocol will be more complicated then one just using ECDH.  Is the extra complication warranted in your case?  That, you have to decide for yourself.


What is a generator? I am trying to read up on the math behind DH and ran into the word generator used a lot. I am not sure what it means. Can someone explain?

I see this question where the OP talks about g as the generator. The accepted answer does not make me understand what a generator is. I always thought g is just a large prime in group. What is the generator and how is it different from the DH parameters?

A generator of a finite group is a value $g$ such that all elements of the group can be represented as $g^k$ for some integer $k$.  Another key of looking at it is that if we consider the sequence $g,\ \  g \cdot g,\ \  g \cdot g \cdot g, ...$, saying $g$ is a generator means that all values in the group will appear somewhere in the sequence.

Now, when it comes to Diffie-Hellman, generator is used in two slightly different meanings (and that may be what is confusing you).

In the first meaning, a "generator" is defined to be an element that generates the entire group.  That is, when we talk about DH (and thus the group $\mathbb{Z}_p^*$), we say that $g$ generates the entire group means $g^k \bmod p$ can take on any value between 1 and $p-1$.

In the second meaning, we say that an element $g$ "generates" a subgroup.  That is, when we consider all the possible values $g^k \bmod p$, those possible values also form a group (which may be $\mathbb{Z}_p^*$, and may be a strictly smaller group), and it makes sense to consider the Diffie-Hellman operation over this subgroup.  In this case, we may call $g$ the "generator" (even if it doesn't generate the full group).  Now, this doesn't denote anything special about $g$ (because all elements generate some subgroup by this meaning), instead we call $g$ the generator to denote that it's the element we have chosen to use.

As I pointed out in my answer to the cited question, using a "generator" for the entire group is often not wise; it often makes more sense to deliberately use an element that generates a prime-sized subgroup.

As to whether $g$ itself is prime or not, well, that's actually not very relevant.  After all, $g$ is actually a member of $\mathbb{Z}_p^*$; whether it corresponds to a prime when it is mapped into $\mathbb{Z}$ using the obvious mapping is not that important.


HMACSHA256 2.5 times faster than HMACSHA512 According to the answers to a previous question,  the 512 version should be faster on x64 devices. And even if it were executed on an x86 (32 bit) device - there shouldn't be such a big difference.

Is there some explanation for this difference? (Or must it be an implementation issue.)

The following code returns almost 5 seconds for the HMACSHA512, and almost 2 seconds for HMACSHA256: (It's run on a Samsung J5 (2015) which has a Snapdragon 410 Processor  with "CPU Bit Architecture 64-bit". Using Xamarin.Forms PCL, the Droid project.):

private void Button_Clicked(object sender, EventArgs e)
{
    ICrypto crypto = DependencyService.Get<ICrypto>();
    Stopwatch watch = new Stopwatch();

    byte[] b = new byte[64];
    watch.Start();
    for (int i = 0; i < 10000; i++)
    {
        b = crypto.CalculateHmac512(b);
    }
    watch.Stop();
    label.Text = watch.ElapsedMilliseconds.ToString();
}

And

class Crypto : ICrypto
{
    //HMACSHA256 hmac = new HMACSHA256();
    HMACSHA512 hmac = new HMACSHA512();

    public byte[] CalculateHmac512(byte[] m)
    {
        return hmac.ComputeHash(m);
    }
}

(On a 64 bit PC for 100,000 iterations I get around 200ms for 512, and around 130ms for 256. So I guess that Xamarin itself is 32 bit. But that still doesn't explain the x2.5 difference on Android.)

SHA-512 internally hashes blocks of 128 octets, versus 64 for SHA-256. That can give a speed advantage on 64-bit CPUs in term of octets hashed per second, but only for large messages. I'd try 8192 where there is 64, and 200 where there is 10000.

The SHA-512 compression function typically requires significantly more time than that of SHA-256: structure is close, with variables twice the size, and there are 80 rounds versus 64 (25% more). There's also about twice as much data moved, and that typically incurs some penalty. However the time required overall can be less than twice as much, and since twice as much message is hashed, there can be some benefit overall for large message.

The question compares HMAC-SHA-512 to HMAC-SHA-256. The HMAC construction adds at least 3 compressions (more so for long keys) compared to a straight hash, which further increases the message size threshold before the 64-bit version can have an edge. With a 64-octet message, HMAC-SHA-512 performs 4 compressions, and HMAC-SHA-256 performs 5 (320 rounds for both). For a 8192-octet message, that goes 68 vs 132 compressions (5440 vs 8448 rounds), which gives HMAC-SHA-512 a chance.

Also, speed of algorithms, especially crypto, depends a lot on the quality of their implementation and how well it is tailored to the hardware at hand. From where we stand, we can't even tell if HMACSHA512 or HMACSHA256 are native code, Just-In-Time-compiled, or interpreted. Benchmarking anything but native code is both rather pointless (if performance really matters, the critical section should be native) and harder (results tend to be unstable).


Identification of correct plaintext after decryption in Rabin cryptosystem In the Rabin cryptosystem, decrypting a message can produce four different outputs, of which only one is the correct plaintext.  How can one know which of the outputs is the correct one?

This is a solution that should work with very high probability, but possibly can fail. As a bonus it also resists tampering with the ciphertext.

As encrypter generate a random key (say a 128-bit key for AES128-CTR) and encrypt the plaintext using that key. Then compute a MAC over the ciphertext (for example using HMAC-SHA1) using the same key. Finally you encrypt the randomly generated key using the Rabin cryptosystem. You then send $encrypted\_key || MAC || ciphertext$ to the receiver.

The receiver first decrypts the encrypted key to get 4 potential keys. For each key he computes the MAC over the ciphertext and see if it equals the sent MAC. If yes he proceeds to decrypt the ciphertext using that key.

Another bonus of this system is authentication. If you have a shared secret/token of sufficient cryptographic length (say 128 bits) between sender and receiver you can use that as the key for the MAC instead of the randomly generated key.


Analyzing ECB's and CBC's resistence to a known-plaintext attack I'm trying to analyze the strength of a block cipher with CBC mode or with ECB mode on the scenario of an exhaustive search attack with knowledge of pairs of plaintext – ciphertext (known plaintext attack).

I understand that, for a block cipher that receives a key of $k$ bits and processes blocks of $n$ bits ($n>k$), on ECB mode, Oscar would find false keys and because of that he would need to check more than one pair (i.e. two or three for DES).

But how would this attack work in a block cipher that uses CBC mode? I suppose Oscar still needs to deal with false keys, but now a encryption operation over block $i$ needs the knowledge of block $i-1$ and possibly the knowledge of $IV$. This is confusing to me.

I understand that, for a block cipher that receives a key of k bits and processes blocks of n bits (n>k), on ECB mode, Oscar would find false keys and because of that he would need to check more than one pair (i.e. two or three for DES).

That doesn't sound right; if you are assuming that the attacker (Oscar) has a plaintext block $P$ and a ciphertext block $C$, and searches for all keys $K$ to find one that satisfies $C = E_K(P)$, well, if the size of the key space $k$ is smaller than the block size $n$, then one would expect that there would be at most one key $K$ that satifies this relationship.  That is, if we assume that $E$ acts independently with different keys, then $E_K(P)$ is effectively a set of independent variables based on the various values of $K$; since $K$ can take on $2^k$ different values, $E_K(P)$ can take on up to $2^n$ different values.  We're looking for a value $K$ for which $E_K(P)$ is a particular value (C); we know that there is one value $K$ (the correct one) for which this is true; the probability that there is a second (false) key for which this is true is at most $(2^k-1)/2^n$, which is fairly small if $k$ is larger than $n$.

However, on to your real question:

  But how would this attack work in a block cipher that uses CBC mode?

Pretty much the exact same way as it does in ECB; CBC mode is defined as:

$C_i = E_K( P_i \oplus C_{i-1} )$

(where $C_{-1}$ is taken to be the IV)

When the attacker has a known plaintext (that is, he has a plaintext message and its corresponding ciphertext), then the attacker knows the values $C_i$, $P_i$, and $C_{i-1}$, and he can look for a key $K$ that satisfies the value relation exactly as he would with ECB mode.  In addition, if he happens to find two keys $K^1$, $K^2$ that encrypts that block in the exact same way, then he can handle it just like in ECB mode, he steps to another block and does a test encryption (or decryption; whichever is most convienent) on that as well.

  I suppose Oscar still needs to deal with false keys, but now a encryption operation over block i needs the knowledge of block i−1 and possibly the knowledge of IV.

We always assume that the attacker sees the entire ciphertext; hence he sees ciphertext block $i-1$.  It's possible that he doesn't know the IV (we typically send the IV with the message, however that's not a requirement); if he doesn't, all the attacker does is not use the first block for his brute force attack.


Cryptographic random number on interval $[0,n]$ from bytes I really like this answer: Creating a small number from a random octet string

While this works, is it safe to generate random number like so?

I am looking for a number on interval $[0,203]$
Generate crypto random secure 8 bits
convert to a decimal variable $d$
final answer $=\frac{d}{255}* 203$

Is this safe and does it work?  Is it better or worse (maybe performance wise) than the answer in the other SE post?

Is this safe and does it work?

Well, it works in the sense that it doesn't pagefault or anything; however its output will be strongly biased.  When you think about it, it takes a value $d$ between 0 and 255, and based on that input, outputs a value between 0 and 203; that means that, for at least least 52 pairs of $d$ values will result in the same output, and so those output values will happen with significantly more probability than expected.

The post you linked gave several viable options; I will second those and add one further one (which doesn't give a precisely uniform distribution, but one that is close enough):

The general idea is to generate a (say) 64 bit random number $r$, and compute $r % 204$, and output that.  Again, this won't be exactly uniform; however an observer would need circa $2^{128}$ outputs before he can distinguish it from random, and so it's pretty good.

And, if you're afraid of the bignum math, actually it's fairly simple (given a 16 bit modulo an 8 bit operation); here's some simple pseudocode:

uint_8 r = 0;
for (i=0; i<8; i))
    uint_16 temp = (256 * r + crypto_rng());
        /* We assume that crypto_rng generates 8 bits */
    r = temp % 204;
/* result in r */

It does use up more random bits than other methods; however it is constant time (assuming the modulo operation is constant time), and that can be important.


Addition step in MD5 implementation In MD5, there are four rounds. After every round, why do we need to add the computed $Q$ values to the initial values and then take this value as input to the next round. For example after the first round, we compute
$$Q^{\text{new}}_1=Q_{60}+Q_{-4}, \ Q^{\text{new}}_2=Q_{61}+Q_{-3}, \  Q^{\text{new}}_3=Q_{62}+Q_{-2}, \  Q^{\text{new}}_4=Q_{63}+Q_{-1}$$
Why cant we directly take the computed values as the input to the next round without adding them to the initial values ?

The reason we, at the end of the compression function, add the input to the compression function, well, that's because otherwise the compression function would be invertible, and that would be bad.

Without that final step, the compression function would be invertible in this sense: given a desired compression function output and a message block, we would be able to find the compression function input.  We would be able to do this because the MD5 compression function is made of 64 steps, and each step is itself easily invertible.  Adding in the compression input at the very end breaks up this invertibility, because the analyst is unable to invert that final step (because he doesn't know the compression function input yet).  He could guess the input at that stage, and then run the rest of the compression function backwards; this turns out to be no more efficient that just guessing the compression function input, and running it forwards.

This invertibility would be bad, because it allows an attacker to do tricks we'd prefer him not to.  For example, we'd want a preimage attack (that is, given a hash value, give me a message that hashes to that) to take (with a 128 bit hash like MD5) roughly $2^{128}$ steps; that is, there is no method that is drastically more efficient that trying random messages and hashing them until you stumble across one with the correct hash.  However, if the compression function is invertible, here is what that attacker can do, given a $Target$ hash value:

Generate $2^{64}$ message prefixes, and generate the partial hashes to that point
Generate $2^{64}$ message suffixes.  When these, he would start with the $Target$ hash value, and compute the hash backwards until he gets the inverse partial hash (having first applied the MD5 final padding).
Given those two lists of 128 bit items, he then looks for a match (and, by the birthday paradox, there's a good chance of being one.

And, if the partial hash of $P_i$ is the same as the inverse partial hash of $S_j$, then he knows that $Hash( P_i || S_j ) = Target$.  This is because, when we evaluate the hash, we first run the compression function on the blocks from $P_i$; at the end of this evaluation, he would come up with the common partial hash value.  Then, he would run the compression function on the blocks from $S_j$ after padding; he knows that, starting at this common value, that results in $Target$.

So, because of this, an attack we had hoped would take $2^{128}$ steps could be done with roughly $2^{64}$ steps.  Making the compression function noninvertible (which the real MD5 does) prevents this line of attack.


Where is HChaCha20 formally defined? I stumbled upon the Q&A “Advantages of HS1-SIV over ChaCha20-Poly1305-SIV?” which mentions “HChaCha20” in the question.

Trying to look it up via the usual research sources, I failed to find an according paper handling HChaCha20. The only places where it seems to be mentioned and implemented are some github projects (like libsodium – but the libsodium docs likewise fail mentioning a paper of alike reference) and some back-and-forth discussions at twitter (which also fail to point to any paper).

Since even some well-known and respected security libs like libsodium know about HChaCha20 and implemented it, I just have to ask: Where is HChaCha20 formally defined?

Note that I'm asking if any paper exist which formally handles the definition, description, and security analysis of HChaCha20 and where I might find it. I'm not interested in related implementations and/or explanations describing how it practically works. I can read the sourcecode, but I'ld like to check the according paper that should exist as a base for those HChaCha20 implementations. After all, verification and validation requires a formal basis.

If such a paper does not exist, can we even assume HChaCha20 and related implementations to be cryptographically secure? If, on what basis? How and where has that basis' cryptographic security formally been analyzed and verified? Or is HChaCha20 bluntly relying on the ChaCha20 core to be secure, without taking another look at the HChaCha20 specifics that differ from ChaCha20's security assumptions? If the later is the case, can we really assume HChaCha20 to be secure? After all, that would mean there isn't a formal analysis & verification of such claims.

Doing further research accross multiple scientific portals and cryptography-related forums, it turns out that no formal specification exists… at all.

HChaCha20 can be constructed exactly the same way as HSalsa20, but has not really been specified or analysed to the full extend we usually expect cryptographic designs to be specified and analysed.

In this relation, it seems to make sense to also quote what CodesInChaos commented:

  I don't think such a spec exists. For the security, you can just directly transfer the "if Salsa20 is secure so is HSalsa20" proof to "if ChaCha is secure, so is HChaCha". Related: Can I use the ChaCha core as a 256-bit to 256-bit one-way function?

The same conclusion can be drawn from postings to the Cfrg mailing list (example):

  …
  The proof for XSalsa20/HSalsa20 should work for XChaCha20/HChaCha20 too
  afaics. (http://cr.yp.to/snuffle/xsalsa-20110204.pdf
  on http://cr.yp.to/snuffle.html)
  …


Salary Negotiation Problem Imagine Alice is applying for a new job. Alice has an idea of the minimum salary that she is willing to accept—let's call this value A. Bob, the hiring manager for a company that Alice is applying to, also has a number in mind: the maximum acceptable salary that he is willing to pay to fill the position—let's call this value B.

Bob wants be sure that at least B >= A is true before spending the time to interview Alice.
Bob does not want Alice to know the exact value of B, because then she would be in a superior position to negotiate a salary as close to B as possible.
Alice would also like to know if B >= A is true, for the same reasons as Bob.
Likewise, Alice does not want Bob to know the exact value of A, because then Bob would be in a superior position to negotiate a salary as close to A as possible.

I'm curious if there is a known cryptographic protocol that would allow Alice and Bob to exchange some information and conclusively determine the result of B >= A, without revealing any information about the actual value of B to Alice or the value of A to Bob.

Caveats:

The use of a third party is not allowed.
Ignore the fact that the repeated use of such an algorithm with different values of A would allow Alice could learn the approximate value of B. Assume that neither party is allowed to change their value.

Does such an algorithm exist? If not, is such a solution even possible?

Solutions to Yao's Millionaire's Problem should suffice for this computation. In that setup, there are two parties each with an input. The output reveals whose input is larger, and nothing else.

So Alice and Bob just run the protocol with their respective inputs A and B.


Is this API for ECDSA signature verification consistent with NIST test vectors? I'm trying to use code from "Easy ECC" package (a github project), for ECDSA-verifying a signature.
The problem I'm facing is that the API assumes a public key length of N+1, which is different than NIST test vectors, where the public key is composed of 2 components (Qx, Qy) which are N bytes each.
(N is the number of bytes for the chosen derivative. For example, for P-256, N is 32).

To be specific, here is the API (ECC_BYTES is 32):

int ecdsa_verify(const uint8_t p_publicKey[ECC_BYTES+1],
    const uint8_t p_hash[ECC_BYTES],
    const uint8_t p_signature[ECC_BYTES*2]);

and the corresponding NIST "verify" test vectors are:

P-256,SHA-256
Msg = (omitted)
Qx = e424dc61d4bb3cb7ef4344a7f8957a0c5134e16f7a67c074f82e6e12f49abf3c (32 bytes)
Qy = 970eed7aa2bc48651545949de1dddaf0127e5965ac85d1243d6f60e7dfaee927 (32 bytes)
R = bf96b99aa49c705c910be33142017c642ff540c76349b9dab72f981fd9347f4f (32 bytes)
S = 17c55095819089c2e03b9cd415abdf12444e323075d98f31920b9e0f57ec871c (32 bytes)
Result = P (0 )

R and S are 32 bytes each and this is consistent with the API signature length of 2*N = 64 bytes.
Qx and Qy are also 32 bytes each and this is not consistent with the API's public key length of N+1 (33 bytes)

My question is: Does this API conform to ECDSA standard ? Eventually, I will have to test it with test vectors like the NIST one above.

Public keys in this system are very sparse: for any $x$ value there are at most two possible $y$ values satisfying $y^2 = x^3 + ax + b$ where $a$ and $b$ are the curve parameters, since the equation is quadratic in $y$.  (And $x^3 + ax + b$ has a square root at all only for some values of $x$; by Hasse's theorem, the number of points on the curve can't be very far from the number of elements in the coordinate field, so only about half of the possible $x$ values work.)

The signature API you're using presumably deals only in compressed public keys, which have maybe some formatting metadata and likely a single bit determining $y$ in one byte, together with 32 bytes to determine $x$.  For example, in the ANSI X9.62 format, the first byte is 0x02 for an even $y$ value, or 0x03 for an odd $y$ value; then the remaining 32 bytes encode $x$.


Is it possible to reduce the tail's file of accumulators for large data set I am working on a proof of concept around cryptographic accumulators. The following is my understanding so far

delta : the current size of the tails file in the accumulator.
witness : the current value of the accumulator when the entry of your number was made.
index : the actual index that is added to the accumulator.
tails file :list of all witnesses.

When an index is added to the accumulator, the witness and delta are shared with the prover.

When the prover wants to prove to a verifier that the index is part of the accumulator he updates the witness using the delta(and tails file) and shares the updated witness with the verifier which allows for verification.

My question is: Wouldn't the tails file become very large as the number of entries increase slowing down the process of proof and verification?

Is there a solution to this?

I've read a little about this area years ago. The naive example of an accumulator is simply multiplying primes together into the accumulator, which can then be checked for their presence simply by division. This obviously results in persistent growth of the accumulator.

I looked for an accumulator that addressed the endless growth issue, but I was never able to find one. However, I was more concerned about the increasing storage capacity required. It seems unlikely to me that one could exist, for they store information after all. It would be magical if it could continuously store information without growing in size.

However, as far as time complexity is concerned, it may be a different matter. The name of what you want would be something like "constant time cryptographic accumulator." For example, a bloom filter allows -- at increasing risk of false positives, but never with false negatives -- for O(1) membership querying on a set of recorded values, which means that time to (probabilistically) determine membership or (with certainty) a lack thereof doesn't grow with the number of elements added.

I would probably look for an accumulator built on a bloom filter if I were worried about time to query and could accept a small risk of false positives.


Why does the one-time pad not imply $P \not= NP$? I apologize that this is a rather trivial question, but I haven't been able to find an answer anywhere.  If the one-time pad is unconditionally secure and impossible to crack (with just ciphertext), why does this not imply $P \not= NP$?  If not the one-time pad, what properties would a cryptographic system need to exhibit in order to imply $P \not= NP$?

A one time pad is secure regardless of complexity. When you have a ciphertext all plaintexts are equally likely and you have no way to verify a guess. Even an attacker which enumerates all possible keys will not learn anything he didn't know already. Thus it doesn't have anything to do with complexity.

A one way function on the other hand implies $P \ne NP$. Any function which is easy to compute in one direction but hard to find a pre image. Since finding a preimage of a polynomial time function is in $NP$.

Note it is possible that no one way functions exist and and still $P$ does not equal $NP$.

A one time pad is not a one way function. It is trivial to find a preimage We can find as many preimages as we want we can't tell them apart.


Symmetric-key login protocol I'm trying to analyze a login protocol based on symmetric key cryptography. I'm just starting out, so this may very likely be a very bad idea, but nonetheless I'd like to hear your thoughts on it.

The protocol assumes the existence (and agreement on) the following:

A symmetric-key algorithm $E$ / $D$.
A key derivation function $KDF$.
A "strong" hash function $H$.

Additionally, the server $S$ has a secret key $k_{S}$.

When a user $U$ wants to register on a server $S$, the following happens:

$S$ generates a random bit string $b_{S}$.
$S$ encrypts $b_{S}$, yielding $v_{S} = E_{k_{S}} (b_{S})$.
$S$ computes $h_{S} = H(b_{S})$.
$S$ sends the pair $\langle v_{S}, h_{S} \rangle$ to the user (this is the server's "verification pair").
$U$ chooses a password $p$ and uses $KDF$ to get $k_{U} = KDF(p)$, its secret key.
$U$ generates a random bit string $b_{U}$.
$U$ encrypts $\langle b_{U}, v_{S}, h_{S} \rangle$ yielding $v_{U} = E_{k_{U}} (\langle b_{U}, v_{S}, h_{S} \rangle)$.
$U$ computes $h_{U} = H(b_{U})$.
$U$ sends the pair $\langle v_{U}, h_{U} \rangle$ to the server.
$S$ stores $v_{U}$ and $h_{U}$, associating them to $U$'s username (or whatever means of identification is used).

Now, in order for a user to authenticate to a server, the protocol proceeds as follows:

$U$ "requests" a login from $S$.
$S$ responds with $v_{U}$.
$U$ decrypts $v_{U}$ getting $\langle b_{U}, v_{S}. h_{S} \rangle = D_{k_{U}} (v_{U})$.
$U$ verifies the server's identity:

$U$ sends $v_{S}$ to the server.
$S$ decrypts $v_{S}$ getting $b_{S} = D_{k_{S}}(v_{S})$.
$S$ generates a random bit string $b'_{S}$.
$S$ encrypts $b'_{S}$, yielding $v'_{S} = E_{k_{S}} (b'_{S})$.
$S$ computes $h'_{S} = H(b'_{S})$.
$S$ sends $\langle b_{S}, v'_{S}, h'_{S} \rangle$ back.
$U$ verifies $H(b_{S}) = h_{S}$.

If the above procedure was successful, $U$ continues, otherwise, $U$ aborts.
$U$ generates a random bit string $b'_{U}$.
$U$ encrypts $\langle b'_{U}, v'_{S}, h'_{S} \rangle$ yielding $v'_{U} = E_{k_{U}} (\langle b'_{U}, v'_{S}, h'_{S} \rangle)$.
$U$ computes $h'_{U} = H(b'_{U})$.
$U$ sends the triplet $\langle b_{U}, v'_{U}, h'_{U} \rangle$ to the server.
$S$ verifies $H(b_{U}) = h_{U}$.
If the above procedure was successful, $S$ continues (logging $U$ in), otherwise, $S$ aborts.
$S$ replaces $v_{U}$ with $v'_{U}$ and $h_{U}$ with $h'_{U}$ for the user.

I know this looks involved, but it's actually pretty simple. The proof $U$ gives to $S$ is knowing how to decrypt a ciphertext into a plaintext with a given (known to $S$) hash. In order to avoid having to persist state on the user's side, more information is encrypted inside $v_{U}$ so that the user may verify the server is who he says it is (by the very same means as he, the user,  authenticates to him, the server).

One of the properties I find interesting of this protocol in particular is the fact that no keys need be exchanged at all (something like Shamir's 3-way protocol), and that the server stores no password-equivalent information, furthermore, it resembles (somewhat) Lamport's chained hash login (S/KEY).

So my questions are:

Does this work?
Are there any evident attacks on it?
Is this any better / worse (probably worse) than any other authentication protocol?
what can be said about the security provided by this protocol?

Furthermore, I'd like to keep it strictly symmetric-cipher + hash based.

Sorry for the lengthy description, I'd welcome an edit by someone more knowledgeable.

I think my definition of 'simple' is different from yours. : )

  Are there any evident attacks on it?

It's vulnerable to man-in-the-middle attacks, like:

Step 9: M replaces $\langle b_{U}, v'_{U}, h'_{U} \rangle$ with $\langle b_{U}, v_{M}, h_{M} \rangle$, where they've calculated their own random bit string and used their own key to encrypt it. Now M can log in as U (and U can't).

That means it's probably no more secure than if you left out the server identification in step 4. and all the related $v_S$ and $h_S$. The identification isn't strong, because there's no authentication for any of the other data exchanged.


Multi-target attacks on AES-CTR with a random nonce 128-bit block ciphers are vulnerable to multi-target attacks where the attacker seeks to attack a collection of keys instead of a single key.  A simple example:

Generate keys $k_1, k_2, ...,k_{2^{40}}$.
Pick a 128-bit message block $m$ and provide $m$ to the attacker.
Compute $E(k_1, m), E(k_2, m), ..., E(k_{2^{40}}, m)$ and provide these ciphertexts to the attacker.
The attacker can compute $E(k, m)$ for various keys $k$ finding a ciphertext that matches one of the ciphertexts provided.  This will take $2^{87}$ evaluations of $E$ on average.

I'm interested in what practical impact this has on the CTR mode of operation.  Some amount of known or controlled plaintext is clearly required for the attacker to get the block cipher output.  More importantly, this attack depends on the block cipher being fed the same plaintext block across many keys.

CTR mode encrypts blocks as $E(k, n \| c) \oplus P$, where $P$ is the plaintext block, $n$ is the nonce and $c$ is the block index.  Protocols that generate nonces deterministically would seem to be vulnerable to this attack.

My question: is it possible to adapt this attack to work against protocols that use CTR mode with a random nonce?  Does randomizing the nonce successfully protect CTR mode from multi-target attacks?

Some amount of known or controlled plaintext is clearly required for the attacker to get the block cipher output.

Actually, that's not much of an issue; we can often get a reasonable amount of known plaintext from real encrypted messages.  In fact, the known plaintext for each message doesn't have to be the same, and you don't have to have completely known plaintexts; a sufficient number of linear equations in the plaintext will work.

  More importantly, this attack depends on the block cipher being fed the same plaintext block across many keys.

Yes, that is key.  CTR encryption is:

$$C = AES_k(n) \oplus P$$

This multitarget attack works by evaluating (for a test $k$) $AES_k(n)$ once, and then using that to check all plaintext, ciphertext pairs in parallel (say, by comparing that value to the list of $C_i \oplus P_i$ values you have precompiled.

However, this works only if every plaintext/ciphertext pair had the same $n$.  If each one used a different $n$, then you'd have to evaluate $AES_k(n)$ separately for each plaintext/ciphertext pair; in that case, you're no better off than picking one message, and just bruteforcing that.

This protection isn't a novel idea; for both TLS and IPsec, the GCM RFC's ask that 32 bits of random (actually, KDF derived) salt is included in the nonce, specifically to frustrate this type of attack.


Decision-LWE to Search-LWE Regev requires $q$ to be prime on lemma 4.2 of his paper for LWE.

Why does he require that and how this effect the proof of lemma 4.2?

He needs to add something uniformly random to the second coordinate, to get a distribution that is uniformly random. (The idea is that if he guesses the correct key, his rerandomization turns real instances into real instances. If he guesses the wrong key, his rerandomization should turn real instances into random instances.)

If $p$ is a prime, then multiplication by any non-zero value is a bijection, so a uniformly distributed $l$ maps to a uniformly distributed product $l(k-s_1)$.

If $p$ is composite, then multiplication by a value that isn't relatively prime to $p$ would not be a bijection, so a uniformly distributed $l$ might not map to a uniformly distributed product $l(k-s_1)$.


Relationship between existence of OWFs and OWPs OWPs are bijective OWFs, so every OWP is a OWF, but not the other way around.

However, I'm wondering what the relationship between the existence of both types of functions is. Obviously if one assumes OWPs to exist, OWFs will also exist.

But: Does the existence of OWFs imply the existence of OWPs?

Short answer: "No".

The standard way to establish a statement of the form if a primitive $B$ exists then another primitive $A$ also exists is through a black-box reduction. This involves two steps:

Constructing an instance $\alpha$ of $A$ given black-box access to an instance $\beta$ of $B$ --- this is denoted by $\alpha^\beta$, where $\beta$ in the superscript refers to $\alpha$ having only oracle-access to $\beta$; and
Showing that $\alpha^\beta$ is hard to break assuming $\beta$ is --- this, in turn, is accomplished through a reduction algorithm $\mathcal{B}$ that breaks $\beta$ given an adversary $\mathcal{A}$ that breaks $\alpha$. ($\mathcal{B}$ only has black-box access to $\mathcal{A}$.)

Primitive $A$ is said to be black-box-reduced to primitive $B$. (Henceforth, by reduced, we mean black-box-reduced.)

Rudich showed$^*$ in his PhD thesis that one-way permutations ($OWPs$) cannot be reduced to one-way functions ($OWFs$) --- i.e., given a $OWF$ $f$, one cannot construct a $OWP$ $\pi$ in the manner described above. In particular, what he showed is that Step 2 is not possible: i.e., there cannot exist a reduction algorithm $\mathcal{B}$ that breaks $f$ given an adversary $\mathcal{A}$ that breaks $\pi^f$.

Note that the above is a very strong statement: we are ruling out all reduction algorithms $\mathcal{B}$. One way to do this is through an "oracle separation".  What Rudich showed is that there exists an oracle $\mathcal{O}$ relative to which $OWFs$ exist, but any construction of OWP $\pi$ that uses $\mathcal{O}$ can be broken using an algorithm $\mathcal{A}^*$ that makes only a "few" (polynomially-many) queries to $\mathcal{O}$. The oracle $\mathcal{O}$ was chosen by Rudich as the random oracle, which is one-way with high probability -- in particular, it takes any algorithm "many" (nearly exponential) queries to a random oracle to invert it. The workings of $\mathcal{A}^*$ is a bit involved, but the high-level idea is it iteratively queries $\mathcal{O}$ on a "few" points in such a manner that it learns something new in every iteration. Since the implementation of $\pi$ is efficient, $\mathcal{A}^*$ can successfully invert $\pi$ using only a polynomial queries to $\mathcal{O}$. Note that $\mathcal{A}^*$ is only query-efficient, and runs in polynomial time only if it has access to a $\mathsf{PSPACE}$ oracle. But there is no way reduction $B$ could break the OWF ($\mathcal{O}$, i.e.) using $\mathcal{A}^*$ as the latter makes only a few queries to $\mathcal{O}$.

Matsuda and Matsuura strengthened the above result to show that a $OWP$ cannot be reduced even to injective $OWFs$ (arguably the closest primitive to $OWPs$). §1.2 in that paper contains a more detailed (although still intuitive) explanation of the Rudich separation .

P.S. Oracle separations have been used extensively in cryptography. Some other examples are:

Public-key cryptography cannot be based on OWFs: Impagliazzo and Rudich
Collision-resistant hash functions also cannot be based on OWFs: Simon

Other ways to rule out reductions are the so-called "meta-reduction" technique and the two-oracle technique.
Fischlin has a nice exposition on these techniques: that should be a good starting point for further reading. You can read more about black-box reductions in this paper by Trevisan, Reingold and Vadhan.

$^*$Rudich's result was modulo a conjecture, which was proved later by Kahn et al..


Public key decryption? In the article How Does the Blockchain Work? the writer makes the following statements:

Since only you should be able to spend your bitcoins, each wallet is protected by a special cryptographic method that uses a unique pair of distinct but connected keys: a private and a public key.
If a message is encrypted with a specific public key, only the owner of the paired private key can decrypt and read the message. The reverse is also true: If you encrypt a message with your private key, only the paired public key can decrypt it. When David wants to send bitcoins, he needs to broadcast a message encrypted with the private key of his wallet. As David is the only one who knows the private key necessary to unlock his wallet, he is the only one who can spend his bitcoins. Each node in the network can cross-check that the transaction request is coming from David by decrypting the message with the public key of his wallet.

Specifically this: If you encrypt a message with your private key, only the paired public key can decrypt it.
Is it true that you can encrypt a string with a private key and only the public key can decrypt it? I was aware of the reverse, obviously, but this just doesn't seem right.

Indeed the text quoted is wrong; at the very least, by using incorrect vocabulary. That should be: if you sign a message with your private key, the paired public key can be used to verify the signed message's integrity and origin.
What small amount of truth there is in the original statement boils down to: in some asymmetric cryptosystems, including RSA¹ (but not including ECDSA used in bitcoin and many other protocols), the sign operation includes a step similar to a step used in encryption, except with the private key instead of the public key; and that's undone in the verify operation, which includes a step similar to a step used in decryption, except with the public key instead of the private key.

¹ And then not the variant of RSA most used in practice for performance reasons, which uses the Chinese Remainder Theorem in private-key operations. That has no equivalent for public-key operations, and uses the private key in a form that makes it not interchangeable with the public key. That makes the twist in the text quoted unworkable.


How does recovering a message from a signature, as described by RSA, prove that the message was signed with a private key? In the original RSA paper, in the section that describes digital signatures, the authors write, “He [Bob] need not send M as well; it can be computed from S.” Then, a few sentences later, “Bob cannot later deny having sent Alice this message, since no one else could have created S = DB(M).”
But Bob’s encryption procedure EB can be applied to any S to produce some M. That is, S could be manufactured from whole cloth, and you’d still get an M from EB(S), albeit gibberish.
How then does merely recovering M from S, as described by the authors, prove that DB was applied to M to produce S? Is legibility alone a strong enough proof of M having been signed by DB?
If M (or a hash of M if you want to nitpick) were included in the message alongside S, then you'd have something to compare the result of EB(S) to. But if only S is given, I don’t understand where the proof comes from.
This question is purely academic. I have no intention of using digital signature as conceived in the original paper in a practical implementation.

How then does merely recovering $M$ from $S$, as described by the authors, prove that $D_B$ was applied to $M$ to produce $S$?

It does not¹. As pointed in the question, $M$ could have been produced from a random $S$.

Is legibility alone a strong enough proof of $M$ having been signed by $D_B$?

No. It's easy to build counterexamples, for various plausible definitions of legibility. My favorite is that it can efficiently be built four pronounceable ASCII² byte strings $M_i$ of same sizable length with $M_0\,M_1=M_2\,M_3$, and then it is trivial to find $S_0$ from $S_1,S_2,S_3$. Thus the private key holder having signed $M_1,M_2,M_3$ can be wrongly accused of having signed $M_0$.

If $M$ (or a hash of $M$ if you want to nitpick) were included in the message alongside $S$, then you'd have something to compare the result of $E(S)$ to.

No. Sending $(M,S)$ and/or $(H(M),S)$ with $S$ computed as $S\gets M^d\bmod N$ does not help at all improve security: again, just pick a random $S$, compute $M\gets S^e\bmod N$, send $(M,S)$ or $(H(M),S)$. The verifier will accept it.
What does help is sending $(M,S')$ with $S'$ computed as $S'\gets H(M)^d\bmod N$, when $H$ is a wide hash. Verifier checks $S'\bmod N=H(M)$. That's the principle of Full Domain Hash, aka RSA-FDH. It's secure; but because an earlier (quantitatively weaker) security proof of RSA-FDH was deemed not strong enough, it was devised RSA-PSS, and its derivative  RSASSA-PSS is used in practice.

¹ Academic cryptography was in its infancy, and back then it was considered acceptable to present as fact some bold, unproven, and occasionally wrong statement. Another claim in the paper was later disproved by ElGamal and Schnorr signature:

To implement signatures the public-key cryptosystem must be implemented with trap-door one-way permutations (…)

² That could perhaps even be made borderline meaningful. It would actually make a nice CTF, that I have not seen implemented: server textbook-RSA-signs (with 2048-bit and $e=2^{16}+1$ ) any ASCII/UTF8 byte string that some criteria (or "AI") deems acceptable, but not if it's on the tune of IOU$ followed by digits; the winner is who get the highest amount signed.