Probability amplication in OWF without hardcore bits We know that OWF $f$ such that none of its bits are hardcore exists. We also know that given an algorithm that solves a problem with non-negligible probability, we can repeat it many times and take the majority of the answers. Now, to predict $x$ given $f(x)$, we deﬁne predictors $P_i$ for $i$ ∈ $[1..n]$, where $P_i$ predicts the $i$th bit of $x$ with non-negligible probability. We would like to guess all n bits by running $P_1.....P_n$ several times each and taking the majority for each bit.

I want to know does this contradicts the definition of $f$?

No it doesn't.

The problem with the approach you suggest appears if you write down formally what you suggest: you want to repeat many times each predictor, and evaluate a majority over their predictions. However, the randomness must be taken over a random choice of input. Your predictors give approximately good answers, when averaging over all inputs to $f$. This means that there is no way to implement the strategy you suggest for a fixed input $x$.

Essentially, you can imagine a OWF where each $i$th bit predictor would give a good answer for a non-negligible fraction of the inputs (say, some subset $S_i$ of the domain of $f$), but that does not mean that inputs from $S_i$ are inputs for which the other predictors will give good results.

Here is a quick counter example: suppose that we have a length-preserving OWF $g$, with domain $\{0,1\}^n$, whose outputs are uniformly distributed. You can construct such a function easily using a PRG, which in turn can be based on any OWF. Now, let $f$ be defined as follow: consider a natural ordering of the bitstrings in $\{0,1\}^n$, and divide the domain in $n$ blocks $(B_1, \ldots, B_n)$, each containing $2^n/n$ strings. On input $x$, we define $f(x)$ to be the value obtained by replacing the $i$th bit of $g(x)$ by $0$ if the $i$th bit of $x$ is $0$, where $i$ is the index of the block $B_i$ that $x$ belongs to.

I claim that $f$ is one-way if $g$ is. Here is why: on a challenge $y$, given access to an algorithm $A$ that inverts $g$ with non-negligible probability, call $A$ on all values $(y_0,\ldots,y_n)$, where $y_i$ is obtained by replacing the $i$th bit of $y$ by $1$ (and $y_0$ is just $y$). When receiving $A$'th answers $(x_0,\ldots,x_n)$, evaluate $f$ on $(x_0,\ldots,x_n)$; if one of the evaluations (say, on $x_i$) returns $y$, stop and return $x_i$; otherwise, return $\bot$. As one of the $y_i$ is exactly the correct output of $g$ on a preimage of $y$ by $f$, it is easy to see that the probability of successfully inverting is exactly the success probability of $A$.

I claim that there are predictors $P_i$ predicting the $i$th bit of $x$ with non-negligible probability. $P_i$ simply works as follows: on input $y$, return the $i$th bit of $y$. Why does it work? Because a random input belongs to $B_i$ and has his $i$th bit equal to $0$ with probability $1/2n$, in which case the $i$th bit of the output is $0$ and the predictor always succeeds. Otherwise, the $i$th bit is uniformly distributed and the predictor succeeds with probability $1/2$, hence it has non-negligible success probability overall.


Does the following equation hold in bilinear pairings? $e:G_1 \times G_1 \rightarrow G_2$,
where $g$ is a generator of $G_1$.
$\text{H}: \lbrace 0,1\rbrace ^* \rightarrow G_1$.
Is $e(\text{H}(D)g^a,g) == e(\text{H}(D)g,g)^a$ ? where $D$ is a string

Does the following equation hold in bilinear pairings?

No, not in general.
$g$ is posited to be a generator, and so (for any fixed $D$), we have $H(D) = g^b$, for some integer $b$ (which is hard to compute, but we're not going to have to compute it).
So, we have $e(H(D)g^a, g) = e(g^{a+b}, g)$.
If we move the $a$ exponent out, we then get $e(g^{1 + b/a}, g) = e( g \cdot g^{b/a}, g)^a$
Doing the same thing one the other side, we would get $e(H(D)g, g)^a = e(g \cdot g^b, g)^a$
It should be clear that these two terms are not (in general) identical.


Mathematical proof or any reference of "Deterministic random bit generator cannot produce more randomness than the randomness of seed" The heading tells everything. Any proof or any kind of reference is welcome regarding this:

Can we get more randomness from a deterministic random bit generator than the entropy that we feed to the generator?

Define the Mutual Information of a pair of random variables.
$$I(X; Y) = H(X) - H(X\mid Y)$$
For discrete random variables we hae that $H(X\mid X) = 0$, so:
$$I(X; X) = H(X)$$

The Data-Procesing Inequality states that for any function $f$, we have that:
$$I(f(X); f(Y)) \leq I(X; Y)$$
While we won't need it here, this includes randomized functions, provided they use randomness independent of either $X$ or $Y$.
Combining these two, we get that:

$$H(f(X)) - H(f(X)\mid f(X)) \leq H(X) - H(X\mid X)$$
If $f$ is deterministic, I believe the conditional entropies become 0, giving us:
$$H(f(X)) \leq H(X)$$
So the output distribution of a DRBG is always lower entropy than the distribution that its seed is drawn from.


What are advantages of using a HMAC over RSA with SHA-1 hashes? I am currently studying for an exam and this was a previous question:

  Give one advantage of using HMACs over using RSA to sign SHA-1 hashes.

My thoughts are that it has something to do with the fact that HMAC assumes a private key has already been shared so there is no need to use public-private keys.  But wouldn't it be possible for this key to be compromised?

HMAC is much faster to compute. Also, HMAC might still be secure, even if the underlying hash function is broken. This is not true for RSA + a broken hash function.


Collision in Merkle–Damgård without a collision in compression function Is it possible to find a collision in Merkle–Damgård  just by omitting the extra one bit that is appended to each input without having a collision in compression function?

No, it is not possible.

If two inputs with different length produce identical hash outputs, then there would be a collision in the last invocation of the compression function. This is because the last input to the compression function always encodes the length of the original message.

If two inputs with identical length produce identical hash outputs, then there would be a collision in the compression function somewhere along the way. This is because considering the entire Merkle-Damgård hash as a hash tree build up of invocations of the compression function, then you will get two trees with identical structure, but those two trees have different inputs and identical output. By induction it can be shown that at least one of the invocations of the compression function in that tree structure must have a collision.


Oblivious transfer with trusted third party Trent I am trying to solve this exercise.

Assume an oblivious transfer protocol that uses a trusted third party Trent.

Alice's messages $M_0$ and $M_1$ are binary values of length $k$. Bob's message selection bit is $m$.

Trent -> Alice: $R_0, R_1$ where $R_0, R_1$ are random binary values each of length $k$
Trent -> Bob : $t, R_t $ where $t$ is a random bit
Bob -> Alice : $ b = t \oplus m$
Alice -> Bob : $C_0, C_1 $

How should Alice compute $C_0$ and $C_1$? How should Bob compute $M_m$?

I guess that Alice has to compute $K_0, K_1$ as keys (probably inserted into a hash function) and then encrypt $C_0$, $C_1$ like $C_M = E_{k_m}(M_m)$. Bob then can compute $M_m$ by $M_m = D_{k_m}(C_m)$ where $K_m$ is related to $R_t$ in some way. Does anyone have an idea? Thank you

Alice computes $C_0$ and $C_1$ as follows:
If $b=0$ (this means $t=m$), Alice computes $$C_i = M_i \oplus R_i.$$
Otherwise (i.e. when $t=1-m$), Alice computes $$C_i = M_i \oplus R_{1-i},$$
where $i \in \{0,1\}$.

Bob computes $M_m$ as
$C_m\oplus R_t$.


Is there a general method to crack this type of fractionating cipher? I've seen a few puzzles based on a type of cipher in which letters in the plaintext are substituted with groups of characters in the ciphertext.  The ciphertext only uses a handful of unique characters.  For example:

a -> 154
b -> 53
c -> 12
d -> 41
e -> 153
...

In this example, bead is encoded as 5315315441.

Since not all letters are encrypted to have the same length, I can't simply break the message up into pairs of numbers and run frequency analysis.  Once the key is known, however, then the character boundaries are unambiguous.

Difficulties in cryptanalysis also arise when one letter's encryption completely contains another letter's encryption, such as how e 153 contains b 53.  For example, the following is unambiguous given knowledge of the key, yet might not be easy to for an attacker notice:

  4153 -> db
154153 -> ae

Let's say that I have a ciphertext, and I am reasonably sure that it is encoded in this way.  How would I go about cracking it?

The only thing I know to do is to look for repeating patterns, as repeating words in the plaintext also repeat in the ciphertext.  I haven't successfully solved one of these kinds of puzzles, however.

Known plaintext attacks and chosen plain-text attacks

The attack here is straightforward. If you have any known plain-text at all, you can find  codes for all the letters in the plain-text you have. You can then use this knowledge to decrypt other messages whose plain-text is unknown.

A very small number of known plaintexts would completely compromise this scheme.

Ciphertext only attack

Each letter within a language has a certain probablity of occurring. In English, the letter "e" is the most frequently used letters.

This wikipedia article gives a nice table of all the English letters and their frequencies.

The attack is fairly straightforward. Take a given cipher-text and build a frequency table for all one digit strings, two digit strings, three digits strings etc.

Then compare each string's relative frequencies compared to the table linked in the Wikipedia article. If there is a rough correspondence between a given sequence of digits and a given letter, substitute that sequence for the letter in question.

Most of the time, the substitution will be valid and the plaintext will quickly fall in to view.


Authentication in TLS protocol TLS session keys are derived as a result of authenticated key agreement.

Is being able to decrypt a record at an endpoint after receiving change_cipher_spec sufficient guarantee that the endpoint is accepting record from the authenticated peer? I believe 'yes'.

I understand that the verification of TLS finished message ensures that the handshake messages were not tampered by MITM. The decryption of TLS record containing finished message proves the record arrived from authenticated peer.

In the case of extended-master-secret extension, the master secret (and hence session keys too) are derived as a function hash of handshake message (i.e. transcript hash). Therefore, if extended master secret is used, being able to decrypt records after change_cipher_spec should prove both authenticity of peer & non-tampering of handshake messages.

In this case, can the handshake protocol do away with finished message without compromising on the security guarantees?

Probably, yes, just testing the first message is secure.

However, I've seen implicit authentication before in a protocol, and it is not nice to deal with it. Basically, you handle the handshake and report to the user of a library that the handshake has finished and the symmetric session keys have been generated: everything is ready to actually transport data.

If you remove the finished message from the handshake then you don't know that everything is alright. You now have to send or receive the message without knowing it should be OK. Now if you have an error then what are you going to answer to the client? Is it that the channel has become corrupted or that the handshake failed?

In this sense, an explicit verification that the handshake failed is much easier to deal with. After the handshake is verified you can simply notify that the channel has become corrupted if anything happens to it.

So yes, implicit authentication and verification of the handshake is possible. In practice, you really want to implement explicit authentication.

An odd situation is where you would send a byte valued 00 or 01 if a condition is true and nothing if a condition is false. In the false case no data record needs to be send: but that means that the handshake is never verified!


Can you still decrypt XTS if half of the cipher text is deleted? If a part of my data is damaged, corrupted, or deleted, is it then still possible to decrypt the rest of the data if you still have the key?

The situation: a piece of data (something like a document for example) encrypted with AES with a 256-bit key with XTS as the mode of operation.

It depends. (Usual answer to this kind of questions. We would need more details about the data damage to answer)

XTS encryption mode is short for XEX-based tweaked-codebook mode with ciphertext stealing, and XEX stands for Xor-encrypt-xor.

Let's look how the XEX mode is defined:
 (image from wikipedia)

XTS definition changes only how the last block is encrypted, iff the size is not a blocsize multiple.

This mode is a tweakable mode designed to efficient process of consecutive blocks within one data unit. The tweak is represented as a combination of the sector address and index of the block within the sector.

The mode could be defined a tweakable-ECB, so there is no chaining between different blocs. So, you're supposed to recover all sectors that contains no-damaged data. The tweak is given by the sector number and allows to avoid that the same block is encrpyted in the same way if it is stored in different disk sectors, but this mode is deterministic, same data in the same place are always encrypted in the same way.

The problem is that stored and damaged data could be necessary to read the remaining part of the file (a file header, for example).

The ability to decrypt non-damaged sectors is due also to the lack of integrity. Usually if ciphertext has been modified you should not decrypt it at all. And good encryption libraries enforce this binary behaviour.

An image can show how this mode behaves with data modifications:
 (image from this interesting page)

The same page explains how the presence of a diffuser could break your ability to decrypt data for the whole sector even if only a block is damaged.
As far as I know neither dm-crypt nor bitlocker implement a diffuser at the present moment.

So, my final answer is that you're able to recover all sectors containing no-damaged data. If damaged data are all in a small portion of the disk you'll recover the rest of the disk woth no problem, but if the damaged data are sparse, you (probably) will not able to read your data.


Mathematical formula for switching the key for OTP? Instead of generating the random key for the one time pad cipher over and over again, is there a mathematical formula that allows you to switch the key to a new key? The new key must be as random and secure as the original key.

Instead of generating the random key for the one time pad cipher over and over again, is there a mathematical formula that allows you to switch the key to a new key?

No.
(Please keep reading…)

A single mathematical formula won’t cut it. That’s where cryptographic algorithms come in. There are more than a hand full of cryptographically secure pseudo-random number generators, stream ciphers, et al which could be used to create a cryptographically secure key… but when having to fall back on those, you might as well simply use them in the first place and drop your one-time-pad idea.

In fact, I’m wondering a bit: What research have you done? I’m asking because you seem to have skipped some of the important parts of what defines OTP.

Per definition, OTP requires the “key“ to be…

a truly random one-time pad value,
generated and exchanged in a secure way.
at least as long as the message, and
only to be used once.

Related to Point 1: Please note that it says “truly random” and not “pseudorandom”. Fact is that no mathematical function by itself can be truly random. Meaning: if you would use a math function (for example: a multiply-with-carry construction) it would definitely not satisfy the definition of OTP.

In a best case scenario, you would be dealing with a CSPRNG or a stream-cipher alike solution. As you probably know, those do exist and indeed provide cryptographically secure randomness (to some extend), but when thinking along that path you really have to ask yourself if you really want to use a car to ride a horse.

Instead of trying to make a square wheel round, it would be more constructive to revalidate your idea and check on already existing stream ciphers and/or cryptographically secure pseudo-number generators. A simple “it looks random so it must be secure” thing definitely won’t be able to handle the job! In case of doubt, look at the numerous PRNGs which have been cryptographically broken (and practically destroyed by cryptanalysis within the blink of an eye).

Related to Point 2 up to Point 4: That “exchanged in a secure way” is important because OTP can only be as secure as the key exchange procedure, which tends to be a problem when messages or data packages size up to a few megabyte or even gigabytes*.

Surely that’s where your question rooted. Yet, trying to find a way around the problem via a math function is neither OTP. nor cryptographically secure.

Last but not least…

  The new key must be as random and secure as the original key.

I wonder how you are planning to compare that. See, a truly random source is unpredicable. Same goes for things like cryptographically secure random number generators (assuming they’re not flawed or broken in some way).

Wrapping it up:

If you really want to stick with OTP, you’ll have no other choice (thanks to its definition) than to use a truly random, cryptographically secure source.

If that’s not available, you could fall back on something like a CSPRNG, or a stream-cipher alike construction (for example: HMAC-based). As said: a simple “mathematical formula” won’t do it. Only a cryptographic algorithm would come near the term “truly random”.

As an alternative: if you want something that’s both cryptographically secure and practical to use (which you indicate to be your main issue), you should definitely look beyond OTP. For example: stream ciphers like Salsa/Chacha. In the broadest sense, stream ciphers ”simulate” the one-time-pad idea. Using them you wouldn’t need to think about working around OTP annoyances.

Also, I think it is worth noting that there’s nothing wrong using good, well-vetted block cipher like AES/Rijndael.

(Funny enough, you could even use a block cipher like AES to create a CSPRNG construction which you could then abuse to create your one-time pad values. But that’ld be overkill since AES does a good job when it comes to encrypting data – which makes considdering OTP pretty superfluous.)


Constant time comparison for arrays of different lengths I found the following code snippet from the Bouncy Castle C# library, which seems to claim that it's constant time, even when the arrays have different lengths.
/// <summary>
/// A constant time equals comparison - does not terminate early if
/// test will fail.
/// </summary>
/// <param name="a">first array</param>
/// <param name="b">second array</param>
/// <returns>true if arrays equal, false otherwise.</returns>
public static bool ConstantTimeAreEqual(byte[] a, byte[] b)
{
    if (null == a || null == b)
        return false;
    if (a == b)
        return true;

    int len = System.Math.Min(a.Length, b.Length);
    int nonEqual = a.Length ^ b.Length;
    for (int i = 0; i < len; ++i)
    {
        nonEqual |= (a[i] ^ b[i]);
    }
    for (int i = len; i < b.Length; ++i)
    {
        nonEqual |= (b[i] ^ ~b[i]);
    }
    return 0 == nonEqual;
}

However, I've heard that it's not possible to compare arrays of different sizes in constant time. For instance, the Go crypto ConstantTimeCompare() function checks the length of the arrays before the comparison. Some people have complained that this leaks the length of the secret.
func ConstantTimeCompare(x, y []byte) int {
    if len(x) != len(y) { // <--- here
        return 0
    }

    var v byte

    for i := 0; i < len(x); i++ {
        v |= x[i] ^ y[i]
    }

    return ConstantTimeByteEq(v, 0)
}

Which approach should be taken when comparing arrays of different lengths? Or should you just hash the data and then perform the comparison (since the lengths will be the same)?

Assuming the first code extract is translated straightforwardly to machine code (perhaps by blocking some compiler optimizations, or using a relatively dumb compiler) and executed on a CPU that performs no groundbreaking runtime optimization, it it is plausible that execution time has no dependency on the data in the arrays, except perhaps in the final 0 == nonEqual (and that residual timing dependency is a non-issue if the function result is to be used as argument of a conditional operator, as seems likely in the context). It's possible to ascertain this by looking at the generated code and at the characteristics of the CPU, and/or confirm it by careful instrumentation.
But execution time almost certainly depends on the length of the arrays, in several ways:

As noted in another answer, System.Math.Min likely does.
An optimizing compiler is likely to crunch out a lot of the second for loop, since (b[i] ^ ~b[i]) is always ~0. The whole nonEqual |= (b[i] ^ ~b[i]); could be replaced by nonEqual = ~0. It's entirely possible that the full loop is reduced to a test that it runs at least once and a conditional nonEqual = ~0.
Even if somehow the above is  made to not occur, there's no reason to believe each execution of the second loop lasts the same time as the first: the code is not the same; on some architecture the code alignment matters; a data cache or some other CPU optimization is likely to make the two references to b[i] faster than the references to a[i] and b[i]; on some architectures, the ~ has a cost...
When the second loop does not run at all, it's possible the code is not fetched and that it saves some time when the two arrays are exactly the same length.

Can we fix it? Not portably, in C# or in any language I know that targets multiple CPUs.
Does it matter? Perhaps, but only if that's among the smallest timing dependencies on the length of the arrays. Which is unlikely, and hard to assess: there's no portable way to setup an array in time independent of it's size!

Which approach should be taken when comparing arrays of different lengths?

Try to reformulate the problem/method so that the need to perform such comparison in constant time vanishes. E.g. if we want to hide the length of a password, we can turn the password into a hash once in a context where adversaries can't time the hashing operation, then hash the string to be compared and compare the equal-length hashes in constant time. If even that is difficult (a compiler, JIT, or even CPU architecture optimization can optimize the loop in a ConstantTimeCompare into something with a data timing dependency), we can perhaps compare (H)MACs of the hashes computed using the same secret random key.
More generally, demonstrable absence of timing dependency is hard to obtain. It's impossible to obtain from a high level language without exquisite control on the compiler and runtime environment. The best line of action is to reduce to an absolute minimum where in the code that's necessary. Or offload the problem to an environment dedicated to that, like a security CPU, which is designed to prevent timing side channels (including using a CPU having carefully designed and specified timing characteristics making execution time precisely predictable), and other side channels (power analysis, fault injection…).


How to handle entropy and CTR DRBG for TLS on embedded system? I am trying to use mbedTLS on a STM32-Nucleo microcontroller (STM32F746).

The TLS library wants a RNG function (naturaly), the STM32 has a hardware RNG verified according to NIST SP 800-22.

The hardware RNG only outputs unsigned 32 bit integers each call, but several calls could provide 28, 32 and 255 byte random arrays needed by TLS.

Now, can/should I use this RNG function to generate random numbers directly for TLS or should I use this Hardware-RNG as Entropy for mbedTLS CTR-DRBG function?

Unless you have documentation about the RNG interface that states that it's using a cryptographic PRNG seeded by an entropy source, use it only as a seed to a PRNG. (Seed initially, and re-seed from time to time as directed by the PRNG algorithm and possibly by certification requirements. Since you're using an existing PRNG library, just pass it the seed function and let it manage when it seeds.)

A hardware RNG always has biases. Those biases may be negligible or not depending on conditions, for example it may perform poorly at certain temperatures or if the power supply is not optimal. A cryptographic PRNG removes observable correlations from the RNG. Even if the seed is not perfectly uniform, the PRNG hides the biases: either the attacker manages to guess the whole seed (i.e. the whole HRNG output), in which case all is lost anyway, or the attacker only manages a partial observation (e.g. after a 1 bit, there's a 50.1% chance that the next bit is also 1) and the PRNG makes that observation useless on its own.

An ideal system uses a HRNG that's unconditioned, i.e. that has no mechanism to eliminate biases, and runs some basic tests about its output based on the known failure modes (e.g. a particular sensor might return all-bits-0 if not properly initialized). The output is then used to seed a PRNG. When that process is hidden in a black box labeled “RNG”, it's hard to verify that the entropy source is operating correctly.


How Can I decrypt this VNC Authentication handshake? I'm trying to analyze a mobile application and I believe it is is using DES.  Here is a sample of the authentication handshake.

{""id":"handshake","authentication":"vnc","authentication-challenge":"A489C9790FB7C3CE2E56868C788641FC"}

{"id":"handshake","authentication-response":"D33BAD35B07EF500A82329749CEE9192"}

{"id":"handshake","authentication-passed":true}

For simplicity, the password is set to AAAAAAAA.

For authentication, it is identified as "VNC".  This leads me to believe that they are using VNC authentication, as defined by RFC 6143.

https://tools.ietf.org/html/rfc6143#section-7.2.2

The documentation states:

The client encrypts the challenge with DES, using a password supplied
by the user as the key.  To form the key, the password is truncated
to eight characters, or padded with null bytes on the right.  The
client then sends the resulting 16-byte response

So if  I understand correctly, If I were to encrypt "0xA489C9790FB7C3CE2E56868C788641FC" with the key of "AAAAAAAA" it should equal "0xD33BAD35B07EF500A82329749CEE9192".  Is that correct?

Challenge contains:

$ cat  ~/Desktop/challange | xxd -p
a489c9790fb7c3ce2e56868c788641fc

I try to run:

$ openssl des -in ~/Desktop/challange  | xxd -p
enter des-cbc encryption password:
Verifying - enter des-cbc encryption password:
53616c7465645f5f3f72b55c62bf2c9da805942f64f028b090cecc652dde
8cdade63763a253c1d33

Which doesn't prepuce what I am hoping for, which is D33BAD35B07EF500A82329749CEE9192.  What am I doing wrong?

EDIT:

I found this online.

http://www.vidarholen.net/contents/junk/vnc.html

I believe this might explain why I'm having issues.

challenge":"318E90D502A379A7B1583C35DB772138"}
{"id":"handshake","authentication-response":"1D214EF554123712A0DC9BCF003C27F4"}
{"id":"handshake","authentication-passed":true}

Ok, I got it.  Just answering for anyone else who stumbles here.  While not documented, RFB mirrors each bit.  Using the key of all B's, I was able to get my result, as B is a palindrome.


Is it possible to determine the symmetric encryption method used by output size? I'm attempting to identify the method of encryption for a black-box symmetric encryptor that produces blocks of output that are 4 bytes in length (e.g. small inputs fit in 16 bytes, then 20 bytes and 24 bytes as more input characters are added).

It's symmetric encryption and the value is always the same for the same input text. Is it possible to determine which method of encryption is used? I'm assuming it's a block cipher as a result of the blocks of output it produces.

You can try to determine the block size by modifying each byte of the input data, starting from the last one.

A typical block cipher implementation will mix the change into all other bytes in the block, and usually also to all following blocks, but not to blocks that come before it.

So if you observe e.g.:

 Plaintext      Encrypted
 0000 0000      2348 1234
 0000 0001      2348 4292
 0000 0010      2348 9823
 0000 0100      2348 2149
 0000 1000      2348 6785
 0001 0000      8173 1437

you could be quite certain that it is a block cipher with 4-byte blocks.

For comparison, in typical applications of a stream cipher, only a single byte would usually change. If it is a stream cipher, you can obtain the keystream by encoding 000...0000, because it sounds like it doesn't have a random initialization vector.


Extending the Socialist millionaire problem to three parties The usual solution of socialist millionaire problem allows to authenticate whether TWO parties have the same secret information. Are there any natural solution of the same problem for THREE parties?

A tripartite version of EKE would appear to work.  Here's how it works:

We select a pairing friendly elliptic curve, with a point $G$ that generates a prime order subgroup.
We define an invertible keyed hash function $F_k(H)$ that maps (based on the key) a point in the subgroup to a point in the subgroup (and so that, for two different keys $k_1, k_2$, we don't know the discrete log of $F_{k_1}(H)$ to the base of $F_{k_2}(H)$

So, what Alice does is take her networth $n_A$, and selects a random value $a$; she computes $A = F_{n_A}(aG)$ and publishes it.

Similarly, Bob and Carol also publish their $B = F_{n_B}(bG)$ and $C = F_{n_C}(cG)$.

Alice computes $e( F_{n_A}^{-1}(B), F_{n_A}^{-1}(C) )^a$ and publishes that.  Bob and Carol do the same computations and publish their values.

If $n_A = n_B = n_C$, this joint computation is $e( F_{n_A}^{-1}(B), F_{n_A}^{-1}(C) )^a = e(bG, cG)^a = e(G,G)^{abc}$, and hence they will publish the exact same value.

If those three values are not the same, for example, if $n_A \ne n_B$, then $F_{n_A}^{-1}(B) = F_{n_A}^{-1}(F_{n_B}(bG))$ is effectively a random point, and so Alice will generate a value that is distinct from what anyone else generates.

On review, this idea doesn't quite work, if we have $n_A \ne n_B$ and $n_B = n_C$, then B and C will compute the same value.  I believe that, from the problem statement, we want to jointly compute the value $n_A = n_B \land n_B = n_C$; we end up leaking more than that...

I'll leave this answer open in case someone can fix it...


RSA random prime generator What is the current standard of random bit generators? RSA relies on two large prime numbers, and I am wondering what is the algorithm used to generate such numbers?

I'm not sure whether you'd prefer a good academic intro, some practical guides on implementation, or some breaking research in this area, so here are my recommendations for each:

Academic overview: Handbook of Applied Cryptography Chapter 4
Practical implementation guidelines: NIST's Federal Information Processing Standard 186 (especially Appendix B.3.2-6, pp. 53-61), provides several suitable algorithms, very readable, drafted to be easy to follow.
Recent research (including a review of the literature on the topic): Loebenberger and Nüsken compare some available random prime generation methods in "Notions of RSA integers."

As Loebenberger and Nüsken note, several different approaches to RSA key generation are scattered throughout several standards, including IEEE 1363-2000, FIPS 186-3/4, ANSI X9.44, and ISO/IEC 18033-2.

Below is an overview of some of the standards out there, though most readers will be better off stopping here and just reading one of the above three links.

  I. PKCS#1 (aka RFC 3447) (historical note)

PKCS#1--developed by RSA before submission as RFC 3447--is maybe the canonical certification defining RSA implementation, and provides absolutely no guidance on the generation of random primes.

  II. IEEE 1363-2000

I'm reluctant to say too much about 1363-2000 (aka P1363) since the IEEE standard is not free. If you have a copy, key generation for RSA is detailed in Sec. A.16.11, with references to subsections of A.15 for primality testing. Generation of provable primes, probable primes, and recursive construction of primes with an implicit proof of primality are each mentioned, the last of these citing Maurer ("Maurer, U. M. “Fast Generation of Prime Numbers and Secure Public-key Cryptographic Parameters,” Journal of Cryptology 8 (1995), pp. 123-155.") and Mihailescu (Mihailescu, P. “Fast Generation of Provable Primes Using Search in Arithmetic Progressions,” Yvo G. Desmedt, Ed., Advances in Cryptology, CRYPTO ‘94, Lecture Notes in Computer Science 839 (1994), Springer-Verlag, pp. 282-293.) from the mid-90s, as well as Shawe-Taylor (Shawe-Taylor, J. “Generating Strong Primes,” Electronics Letters 22, July 1986, pp. 875-877.), who may also warrant a read for the exhaustive study of the topic.

Most notably, the document recommends a fantastic academic primer to this subject, Chapter 4 of Menezes, van Oorschot, and Vanstone's Handbook of Applied Cryptography (Menezes, A., van Oorschot, P., and Vanstone, S. Handbook of Applied Cryptography, CRC Press, Boca Raton, Florida, 1996.). The HAC, by generosity of the authors and publisher, is available completely free online, and is the best conceptual overview of the issue raised in this question.

Now that I've danced around it enough, the general idea in 1363 is to generate numbers of the form $2k + 1$ for some random $k$ before testing the result for primality. There's a longer algorithm for generating "strong" primes, where a strong prime $p$ satisfies:

$p ≡ 1\ ($mod$\ r)$ for some large prime $r$,
$p ≡{}–1\ ($mod$\ s)$ for some large prime $s$, and
$r ≡ 1\ ($mod$\ t)$ for some large prime $t$.

This maybe begs the question a bit, since you asked about random bit generation, and some random k is required for the basic algorithm here. That part of the algorithm isn't specified likely because it's no longer a component of RSA, we're assuming you have some method to generate random numbers, maybe through a hardware random number generator. This is going to come up in all the methods, generating random bits is prerequisite and separate from generating random primes.

(If you intended to ask primarily about how random bits are generated rather than how random primes are derived from those bits, then at this point you may want to look at hardware random number generators (or more likely your OS, ie, /dev/urandom/ on Unix-like systems or CryptGenRandom in Windows).)

IEEE 1363 also points readers to ANSI X9.31-1998 for "an auditable method of generating primes by incremental search." X9.44 may include the updated version you'd be looking for.

III. FIPS 186-4

(Note: You may see references to 186-3, but this standard was updated in July 2013 to 186-4.)

RSA key generation is introduced in Sec. 5.1 (pp. 22-3), which was updated in -4 to guide the retention (or preferably, destruction) of seeds used to generate random primes. The real meat you're looking for is in Appendix B.3.2-6 (pp. 53-61) though. And while this section is too large to fully detail here, this appendix is probably your best resource for practical implementation guidelines on this question, as it is freely available, clearly written, and very comprehensive as to different methods based on which types of primes you wish to generate (provably prime? probably prime? even... probable primes with conditions based on auxiliary provable primes? et al.). All methods include readable algorithms.

NIST also references ANSI X9.31 and ANSI X9.80, as well as
Special Publication (SP) 800-90A, Recommendation for Random Number Generation
Using Deterministic Random Bit Generators (RBGs), and, SP 800-57, Recommendation for Key Management, further detailing the specifications for suitable RBGs.

In a nutshell, RBGs are rated by security strength, and different applications will require different security strengths. Non-deterministic is better than deterministic? You asked for "state of the art," which could mean the RBGs with the highest security strength, but actually, the real art is allocating the appropriate security strength to the task at hand without going overboard, and in auditing. Auditing isn't sexy, but it's really the important bit.

IV. ANSI X9.44, X9.31, and X9.80, ISO/IEC 18033-2, etc.

Like IEEE 1363-2000, also not free. I think NIST incorporated the relevant ANSI material into FIPS 186-4, though.

NIST's pubs are free, and arguably more straightforward than the publications from the other shops anyway.

V. Other Recent Research

I believe the consensus developed over the last couple decades that the primes should be selected of roughly equal size, as it allows some simplicity in implementation, and the drawbacks have been found insignificant. (I'll dredge up a cite for the comments if there's interest.)

Loebenberger and Nüsken's "Notions for RSA integers" from late 2012 compares some of the methods listed in the standards. It provides a solid baseline for analysis in an area that's easily neglected, and provides through its citations a great review of current literature. It's where I'd head next if I wanted to read every recent piece of research on the topic. Tracked on arXiv as arXiv:1104.4356 [cs.CR].


Could one build a symmetric encryption system that is competitive with the AES by randomly applying Toffoli-like gates? Recall that the Toffoli gate is the mapping $T(x,y,z)=(x,y,(x\wedge y)\oplus z)$. We shall say that a function $T$ is Toffoli-like if
$T(x,y,z)=(x,y,((a\oplus x)\wedge(b\oplus y))\oplus z\oplus c)$ for some $a,b,c\in\{0,1\}$.

Suppose that our key is $m$ bits and the message we want to encrypt $\mathbf{x}$ is $n$ bits. Let $C$ be a circuit on the $m+n$ bits consisting of Toffoli-like gates which are selected at random where either the target is always in the $n$ message input bits or both the control and the target are in the $m$ key bits. Then for each key $\mathbf{b}$ there is some $\mathbf{c}$ along with functions $D_{\mathbf{b}},E_{\mathbf{b}}$ (the encryption and decryption functions) such that $(\mathbf{c},E_{\mathbf{b}}(\mathbf{x}))=C(\mathbf{b},\mathbf{x})$ and $(\mathbf{b},D_{\mathbf{b}}(\mathbf{x}))=C^{-1}(\mathbf{c},\mathbf{x})$.

Is there any symmetric encryption system similar to the above cryptosystem which has been deeply studied or is already in use?

If so, then how does such a cryptosystem compare against the AES or another symmetric cryptosystem?

If there is no such cryptosystem available, then what weaknesses do such cryptosystems have and why are they not in use?

Will such a randomly generated symmetric encryption system be practical once super efficient reversible computers or partially reversible computers hit the market?

In this paper, it takes 109664 reversible gates to implement the 128 bit key AES. By comparison 100,000 Toffoli gates seems to be more than sufficient when one randomly applies Toffoli and Fredkin gate, so I am wondering why this randomly generated symmetric cryptosystem is not in use.

It seems plausible that one builds a symmetric encryption system competitive with AES by randomly applying Toffoli(-like) gates as restricted in the question. I do not know that it has been studied.

Paraphrasing the question, it constructs a block cipher with 128-bit block and 128-bit key similar in function to AES-128 as follows:

number inputs as $b_i$ with $0\le i<128$ for block bits and $128\le i<256$ for key bits
repeat $r$ times

pick random distinct indices $i,j,k$ with $(k\ge128)\implies(i\ge128)\wedge(j\ge128)$
apply a random Toffoli-like gate to $(b_i,b_j,b_k)$

In the end, the result is the 128-bit $x_i$ with $0\le i<128$. The rule $(k\ge128)\implies(i\ge128)\wedge(j\ge128)$ insures that for any fixed key, the block cipher is reversible.

Seen from far away with blurry vision, there are similarities between this construction and AES-128: both are iterated permutation-substitution ciphers with reversible key transformation along the rounds, and 256 variables.  If we chose $i$, $j$, $k$ randomly until acceptable, a key bit is chosen as $z$ (the potentially changed bit) with odds about $1/5$, which grossly mimics AES spending significantly less computational effort on key scheduling than on data encryption.

I do not know the number of rounds $r$ making the block cipher secure; nor a technique to derive this. But I would not be astonished if it was markedly lower than $100000$.


Does selecting a set of random numbers for the key and IV insure security? For AES 256 - if I use a random 32 byte sequence for the 256 bit key and another 16 byte for the 128 bit initialization vector, does this insure that my cipher text cannot be broken in any short amount of time when the byte sequences are only known to me?

Related to this: how would one transmit the key to another party, so he/she may decrypt the cipher text keep it secret? Is there a preferred method, for instance by word of mouth only?

So your question has some holes in them but I will try to fill as much in as possible. If anyone were to see a mistake in my explanation, I would be more than happy if they pointed it out or edited this solution.

AES is a block cipher that has many modes namely: ECB, CBC, OFB etc. each of these have slightly different properties (both cryptographic and non cryptographic) and benefits. That being said, AES-256 is secure (apart from ECB, and I will not dive into different different definitions of security. If interested look into CPA Secure and CCA secure). The matter now becomes which mode to use, for which there is a better explanation explained here

Hopefully that answers your question. Let me know if there is something I missed.

As for your second question you would want to use a public key exchange protocol. I would suggest using Diffie-Hellman Key Exchange


ECDH-ECDSA Combination I am doing research on cryptography primitives at a basic level and I faced a question on encryption methods. I understood that ECDH is an approach to for secure key exchange between two parties before the encryption process begins. It is quite useful in symmetric methods that use the same key for encryption and decryption. But I cannot understand the application of key exchange schemes in public-key encryption methods like ECDSA since only public keys are shared between two parties that does not need secure exchange. But such combination (ECDSA/ECDH) seems to happen in protocols like SSL. In what point does exactly secure key exchange methods like ECDH stands in a public key encryption method specifically ECDSA?

ECDH and ECDSA are two different cryptographic primitives. The one isn't build directly upon the other. ECDH and ECDSA both rely on the same computationally hard problem of elliptic curve cryptography of course.

ECDH is a method of performing key agreement. Both parties can establish a secret value by sending only the public key of their ephemeral or static key pair to the other party. If the key pair of one of the parties is trusted by the other party then that key pair may also be used for authentication. This is however not that common. ECDH is the elliptic curve form of the Diffie-Hellman protocol (the DH in the acronym).

ECDSA is, as the name implies, a digital signature algorithm (DSA). It's the elliptic curve form of DSA. It can be used to authenticate the handshake of the TLS protocol. This authentication includes the key agreement parameters used to derive the master secret. The authentication therefore includes the correctness of the session key.

As you can see above, the actual ECDH and ECDSA may be used together in the handshake of the TLS protocol. They are however independent of each other with regards to operation. This is also why ECDH and RSA combinations can exist. ECDH and ECDSA just happen to share the same cryptographic principles.


Entropy test for AES Key Schedule According to the article "Lest We Remember: Cold Boot Attacks on Encryption Keys" there is a quick and dirty entropy test that can help to find possible AES Key Schedules in memory dumps. Although there are references to this algorithm in blogs of other famouse cryptographers (for example, this post), I haven't been able to find any explanation why it works and why this algorithm is correct. Is there anybody who can provide me with a proof of correctness of this entropy test or can just explain me why it actually works?

The way you worded the question is misleading, as the entropy test is performed AFTER they have extracted an AES key from memory. The test is used to confirm whether it is a likely encryption key or an AES key used for benchmarking or algorithm verification.

The actual procedure involves cycling through the entire memory space, and examining each block of memory that could be the size of a computed key schedule, which may look daunting, but is actually quite fast, due to the simplicity of the key schedule. They cycle through the memory space in word increments and compute the first iteration of the key schedule. If it matches the next words in memory, the entire key schedule is performed and compared. This is about 134 million iterations in total on a 4GB memory space, which only takes a few minutes; it is especially if the testing system has AESNI instructions on multiple cores, the search may only take seconds. The full key schedule is 10 iterations for a 128-bit key.

Update: It looks like they used an automated entropy test to eliminate memory blocks before the final (manual) entropy analysis of the key. This is done by cycling through memory blocks and counting duplicates. If any one byte value comprises 5% or more of the block, it is flagged as non-key. The block search size is 11 round keys or 176 bytes. This is faster than computing the key schedule in their code, but slower if you have code with AESNI instructions (3rd party code to perform the same search).

The only time this becomes slow is when there is memory corruption, such as in a cold boot attack. In that case, the missing bits need to be extrapolated, and a slower algorithm needs to be used to find candidate keys.

The key schedule only performs 4 operations on the master key, and these can be computed forward and reverse at almost any point in the key schedule. Additionally, 3 of the operations are not done on every word of the key. If memory corruption is present, a 4 word block is selected, and the key schedule is computed in both directions (128-bit key). If there are word matches in either direction, that area will be flagged for reconstruction of the entire key space.

Once AES keys are identified, an entropy analysis is performed to determine if it is a likely key for the application using AES. Then the various combinations of found keys are used with the application until a successful decryption is performed.


Can I use different initialization vectors (IV) for the same data in AES-CBC? Every time I encrypt the data, I generate a different IV. Suppose the attacker has access to all files ever encrypted. They don't know the key, but they do know the IV. The problems is: if I save the same data with the same key several times, I generate different encrypted data. Theoretically, this could give the attacker some information about the key or the data, assuming they know that neither have changed. Should I worry about this?

This is mostly a theoretical question. In practice I could simply check if the data or the key have changed. If not, then I don't change the encrypted data.

Yes, this is fine and you should always use a random IV, irregardless of the plaintext.

  The problem is: if I save the same data with the same key several times, I generate different encrypted data.

That's usually a good property to have.

When this property does not hold, it is possible to know when a pair of plaintexts is equal (without knowing the value of plaintexts). That can be a pretty important finding if the set of messages is small (example: something that encrypts "yes" or "no").


OpenPGP/X.509 bridge: how to verify public key? I'd like to use OpenPGP authentication over TLS, but lack of implementations made me use a temporary solution: an OpenPGP/X.509 bridge certificate.

The approach is very similar to the approach used in Foaf:
https://svn.java.net/svn/sommer~svn/trunk/misc/FoafServer/pgpx509/src/net/java/dev/sommer/foafserver/utils/PgpX509Bridge.java

  Basically, you create a certificate request starting from a converted PGP private key, including your converted PGP public key into the certificate request. Then you sign the request with your converted PGP private key.

I'm using the word "converted" because OpenPGP and OpenSSL key formats are incompatible: I have to extract the key parameters from the OpenPGP key and use them to form a new X.509-compatible (OpenSSL) key. Nevertheless, it works as expected.

The result is a X.509 certificate with the PGP public key parameters used in the public key of the X.509 certificate, but without the user IDs and the public key signatures, thus making it unusable for authentication purposes.

The missing piece here is server authentication. The server has previously signed the user's PGP public key, but how do I verify that through the X.509 bridge certificate?

Even if I use my PGP user ID as my CN (Common Name), how do I certify that it's the same user ID used in the originating OpenPGP key?
There are no public key signatures on the X.509 bridge certificate, only the same key parameters. Can I safely just check against those?

If you can put the entire PGP certificate in a proprietary non-critical extension then you don't need to find the PGP certificate in a store. This solution depends on the condition that you are able to create your own OID and insert the PGP certificate in the extension. Furthermore, the server should accept such a certificate and contain methods of validating the PGP certificate as well.

The CA can accept or refuse requests containing a PGP certificate. It should at least check that the key in the PGP certificate matches the one in the signed request. One method of doing this is to validate that the modulus of the PGP and X5.09 public key match.


how to calculate surge of cpu cycles consumption of an ipsec tunnel with aes256/sha512/dhgroup21? The project I'm involved with needs to establish around 2500 simultaneous ipsec connections between roadwarriors clients and the ipsec concentrator/gateway.

In order to be able to estimate the appropriate hardware solution I'd like to be able to calculate the amount of processing power needed to sustain the moment of a surge in computation (like when all clients are connected and the concentrators' link goes down and when it comes back it gets flooded by all 2500 client attempting reconnects).

What would it take for example to carry 2500 simultaneous initiating ipsec connections using aes-256,sha512 and dh group 21 or 24 (as advised on https://supportforums.cisco.com/document/12276506/diffie-hellman-groups)?

The clients won't be generating more than few packets/s once connected (less than 10, for sure)

I've been lookin at this similar question but I'm still confused.

In the scenario of the question, the cryptography involved on the server side will be, for each client connection, and ignoring a number of details like random number generation

Diffie-Hellmann in some group for the generation of session keys
Few SHA-512 as part of that, of relatively negligible computational cost for competent implementation, assuming 1 is in software (or if 2 was in hardware)
Some AES-256 cryptography, as part of packet exchanges, also of relatively negligible computational cost for competent implementation, usual packet size, assuming 1 is in software or 3 is in hardware (including using AES-NI of modern x86 CPUs)
Some other untold assymetric crypto operation (like a few signature verifications), especially if the clients are authenticated by assymetric cryptography; I'll leave that alone, but it could be significant, even dominant.

The groups in the blog post quoted in the question seem to be that of RFC 5114 section 3.2. I thus believe that the blog post makes a serious error when it ranks group 24 as "Next Generation Encryption" and more secure than group 19 ranked "ACCEPTABLE". Group 24 seems to be a Schnorr group with $p$ of 2048 bits and $q$ of 256 bits, quoted as giving 112-bit symmetric security where groups 19, 20 and 21 would be 256-bit, 384-bit and 521-bit elliptic curves with 128, 192 and 256-bit security (taking 192 and 256-bit security with a grain of salt as anything above about 160-bit in that sense could be attackable, with humanly sizable odds of success, only if there was a totally disruptive breakthrough, like quantum computers usable for cryptanalysis; or, regardless of security level, if there's some goof or backdoor in the implementation).

On a nearby VM with openSSL 1.02g installed and lscpu reporting 2 cores at 4 GHz, the command openssl speed reported what could be a passable benchmark for groups 19, 20 and 21 as implemented by openSSL (the last colum is mine, and I have slightly edited the others for legibility)

 256 bit ecdh (nistp256)   18190 op/s   (group 19)
 384 bit ecdh (nistp384)    1980 op/s   (group 20)
 521 bit ecdh (nistp521)    2834 op/s   (group 21)

I'm surprised that nistp521 is shown faster than nistp384; think of it as an illustration that timing varies enormously with the quality of the software implemention (and perhaps, different parameters in benchmarks, which I have not cheked). But these numbers tell us that the 2500 clients reconnecting simultaneously are unlikely to take more than a few seconds of CPU time for the crytography in 1 (thus in 1/2/3), with a competent implementation in software on a powerful x86 CPU, for groups 20 and 21; with group 19 significantly faster (and, as far as we know, unlikely to be an exploitable weakness anytime soon; compromize of the server or its private key is a much more down-to-earth concern).

Beware that an "ipsec concentrator/gateway" typicaly will use something much lesser than a powerful x86 CPU; on the other hand, some have crypto accelerators. The most important thing is how good and trustable is the software; and that's impossible to tell from specs.


How to show that this modification of CBC-MAC is insecure? I'm working on some cryptography problems, found this and I'm not sure how to solve it:

  Modify CBC-MAC so that all blocks $t_1,\dots,t_l$ are output rather than just $t_l$ and prove it is not secure.

Consider the following chosen-plaintext attack on the modified CBC-MAC function:

Send $m_1$, $m_2$, $m_3$, receive $t_1$, $t_2$, $t_3$.

Send $m_1$, $m'_2$, $m'_3$, receive $t'_1$, $t'_2$, $t'_3$.

Send $t'_2 \oplus m''_3$, $m''_2$, $m''_3$, receive $E_k(t'_2 \oplus m''_3)$, $t''_2$, $t''_3$.

Then you know the following (message, tag) pair will verify:

Send $m_1$, $m'_2$, $m''_3$: the tag will be the concatenation of values you have previously queried for: $t_1$, $t'_2$, $E_k(t'_2 \oplus m''_3)$. Therefore you can generate a valid (message, tag) pair that has not yet been sent through the modified CBC-MAC algorithm. This can be generalized for any number of blocks.


Is it possible to build a CPA-secure encryption scheme which remains secure even when the encryption of secret key is given? How can I design a CPA-secure encryption scheme which is secure even after the encryption of secret key is given in the training phase?  I.e., in the training phase, $\mathit{Enc}_{\mathit{pk}}(\mathit{sk})$ is given to the attacker, where $(\mathit{sk},\mathit{pk})$ is the key pair.

You're in luck!  Essentially every secure public-key encryption scheme on bit strings that is actually in use already has this property—and, even better, not just IND-CPA but often IND-CCA2/NM-CCA2*—because they can all be factored into a KEM/DEM structure via a hash function $H$ like SHAKE128:†

(KEM) Generate a uniform random $k$ and encapsulation $y$ using $\mathit{pk}$.

Examples:

RSA-KEM: $\mathit{pk} = n$, a large integer; choose $x$ uniformly at random in $0, 1, 2, \dots, n - 1$, and compute $y = x^3 \bmod n$ and $k = H(x)$.

The recipient will recover $x = y^d \bmod n$ with secret knowledge of $d \equiv e^{-1} \pmod{\lambda(n)}$.
RSA-OAEP KEM: $\mathit{pk} = n$, a large integer; choose $k$ and $r$ uniformly at random, compute $a = k \oplus H(0 \mathbin\| r), b = r \oplus H(1 \mathbin\| a)$ (of appropriate bit lengths so they fill a $\lfloor\log_2 n\rfloor$-bit integer), and $y = (a \mathbin\| b)^3 \bmod n$.

The recipient will recover $a \mathbin\| b = y^d \bmod n$ with secret knowledge of $d \equiv e^{-1} \pmod{\lambda(n)}$, and then solve for $k$.
DH-based KEM: $\mathit{pk} = h$, an element of prime order in a group $G$ generated by a standard base $g$; choose $x$ uniformly at random, and compute $y = g^x$, and $k = H(h^x)$.

The recipient will recover $k = H(y^z)$ with secret knowledge of $z$ such that $h = g^z$, so that $h^x = (g^z)^x = (g^x)^z = y^z$.

(DEM) Use $k$ as a one-time key for a one-time authenticated cipher $\operatorname{AE}$ to encrypt the message $m$ as $c = \operatorname{AE}_k(m)$.

Any authenticated cipher works here, like AES-GCM or crypto_secretbox_xsalsa20poly1305; technically the security requirements of a DEM are lighter than AEAD, e.g. you could just use most of $k$ as a one-time pad and the rest as a one-time authenticator key, but it is simplest—and most common—to use an authenticated cipher.
Transmit $(y, c)$, the encapsulation $y$ of the one-time key $k$ and the authenticated encryption $c$ of the message $m$.

The one-time key $k$ is (effectively) independent of the secret key $\mathit{sk}$, so there is no problem with the symmetric encryption $\operatorname{AE}_k(\mathit{sk})$ used here.

This notion of security is sometimes called circular security or key-dependent message (KDM) security.

In 2001, Camenisch and Lysyanskaya defined circular security and proved that $(m, r) \mapsto E_{\mathit{pk}}(r) \mathbin\| (H(r) \oplus m)$ for uniform random $r$ has it if $E_{\mathit{pk}}$ is semantically secure[1].
Independently, in 2002, Black, Rogaway, and Shrimpton defined the slightly stronger KDM security and suggested but could not prove that KEM/DEM hybrid constructions like this would have it[2].
Then in 2014, Davies and Stam finally found formal techniques to prove that KEM/DEM via $H$ generically has KDM security[3].

Skipping the hash $H$, of course, can ruin the security, as in many cryptosystems.  If for some reason you need a system that is secure even without a hash, then the Camenisch–Lysyanskaya and Black–Rogaway–Shrimpton papers are a good starting point for a literature search, with over a thousand papers citing them, from a cursory glance.

Of course, if you need additional structure—e.g., the homomorphic property of Elgamal encryption $(h^r, g^r m)$ for a highly restricted message space—then the answer may be different, because such additional structure is incompatible with NM-CCA2.  But in that case, you'll need to ask a more specific question about your specific additional structure.

* Well, some of the practical ones fail IND-CCA2/NM-CCA2, like S/MIME and OpenPGP, because their designers made foolish decisions leading to EFAIL[4].  But those particular mistakes don't imply problems with circular/KDM security: they are still effectively factored into KEM/not-quite-DEM.

† In academic cryptography jargon, the security here is usually presented in the ‘random oracle model’.  Essentially, this means that we can prove any attacker that doesn't depend on the details of $H$ can be used, if parametrized by $H$, as a subroutine in a procedure to factor large semiprimes, compute discrete logs, etc.  In principle, it could be that particular choices of hash function $H$ could interact with the public-key mathematical structure to enable other attacks; pathological examples have been exhibited[5] where any choice of hash function is insecure.  But these pathological examples are of little consequence in the real world, and they give no reason to doubt the practical security of the KEMs actually in widespread use today like these; these pathological examples are more of an interesting quirk of the formalism than anything else.  More on the random oracle model.


Question on the disprove of CCA security I have a question on the disprove of the CCA-security given in Katz & Lindell's textbook (2nd edition) in chapter 3.7 on page 97. It works like this:

Consider our construction based on PRFs: $\text{Enc}(k, m) := (r , s) = (r , F (k, r ) \oplus m)$
Set $m_0 = 0^n$ and $m_1 = 1^n$
Adversary A gets $(r , s)$ and flips the first bit of s. Denote the ciphertext by $(r , s' )$
A sends $(r , s' )$ to his decryption oracle
A obtains either $0\mathbin\|1^{n−1}$ or $1\mathbin\|0^{n−1}$ which allows him to win the game

My question: Why does A not obtain $0\mathbin\|1^{n−1}$ and $1\mathbin\|1^{n−1}$ or $0\mathbin\|0^{n−1}$ and $1\mathbin\|0^{n−1}$ and can therefore still distinguish the messages, if $n>2$?

When the oracle gets $(r,s')$ this means that it gets $m'  =  0\mathbin\|1^{n−1}$ or $m' = 1\mathbin\|0^{n−1}$ because the oracle sent the adverary either the encryption of $m_0$ or $m_1$ that is $(r,s)$.
$0\mathbin\|0^{n−1}$ or $1\mathbin\|1^{n−1}$ is not the case since the bit flipping doesn't affect the $F$. The oracle will get $(r,s')$ then it will calculate $F(k,r)$, then the stream will be x-ored with $s'$. If we represent the bits by sub-indexes
$$F(k,r) \oplus s' = \left[F(k,r)_0 \oplus \color{red}{s'_0},F(k,r)_1 \oplus s'_1, \ldots, F(k,r)_{n-1} \oplus s'_{n-1}\right]$$ then we have
$$F(k,r) \oplus s' = \left[F(k,r)_0 \oplus \color{red}{\overline{s_0}},F(k,r)_1 \oplus s_1, \ldots, F(k,r)_{n-1} \oplus s_{n-1}\right]$$
As we can see, only one position has affected, the first position.


How strong is the ECDSA algorithm? Some cryptographic algorithms are as strong as the size of their key is, while other have some weaknesses that limit their strength (such as SHA-1). How strong is the ECDSA algorithm, and does that strength depend on anything (for example, the curve used and so forth)?

First of all, I'm no expert in this area. Generally $n$ bit ECC seems to have a security level of about $n/2$, but I found some claims that it's lower for certain types of curves.

RFC4492 - Elliptic Curve Cryptography (ECC) Cipher Suites contains the following table:

               for Transport Layer Security (TLS)

                Symmetric  |   ECC   |  DH/DSA/RSA
               ------------+---------+-------------
                    80     |   163   |     1024
                   112     |   233   |     2048
                   128     |   283   |     3072
                   192     |   409   |     7680
                   256     |   571   |    15360

It doesn't seem to distinguish between different curve types.

I found an RFC draft (not a real standard RFC) that claims the following security levels:

Symmetric  |  ECC2N  |  ECP  |  DH/DSA/RSA
       80  |   163   |  192  |     1024
      128  |   283   |  256  |     3072
      192  |   409   |  384  |     7680
      256  |   571   |  521  |    15360

This is consistent with other other sources that put the security level of ECC at $n/2$. Binary curves seem to be a bit worse than prime curves.

The blog entry Not every elliptic curve is the same: trough on ECC security elaborates:

  Additionally, something that most people does not know, but that it’s extremely relevant to our analysis, is that there are different kind of ECC curve cryptography and their “size” it’s different depending on the kind of curve:

  ECC Curves over Prime Field (often referred as Elliptic Curve and represented by P-keysize)
  ECC Curves over Binary Field (often referred as Koblitz Curve and represented by K-keysize)

  Given a security strength equivalence the Elliptic Curve and the Kobliz Curve have different key size, for example when we read ECC 571 we are referring to Koblitz Curve with an equivalent strength to ECC 521 Prime curve.

For some curves (like supersingular ones) there are specific attacks, which make them significantly weaker.


Why ISO/IEC 9796 (signature with message recovery) instead of just encrypt the short message with private key? I've had a look at “Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures” and read the very good answer https://crypto.stackexchange.com/a/17846/59673 and I understand that signature and encryption are usually different algorithms. For clarity, here I am just talking of RSA.

For long messages usually a hash is computed, padded, and then encrypted with the private key, and sent along with the message. The receiver can decrypt the signature with the public key and compare with the hash (re)computed on the message (and verify the padding integrity).

For short messages ( m < N ), what I (still) do not understand is the need of complex algorithms like ISO/IEC 9796.

Given that encryption is not the important factor but only verification is needed, the sender could encrypt the whole message with the private key (like it is normally done for the hash). The receiver decrypts the message with the public key, gets the message and implicitly verifies the sender.

Obviously textbook RSA would be subject to existential forgery (which wouldn't be a problem with formatted messages) and maybe to multiplicative forgeries. So one has to add padding, like in standard RSA.

If there are security issues on this mechanism, for what I understand they are exactly the same than for standard signature. So the only downside is that without the public key the receiver cannot get the message.

EDIT:
I'va also read the answers to Why hash the message before signing it with RSA? but as stated, I am asking in case of m < N.

So, are there more reasons not to encrypt the original message + some padding?

I'll be taking the question as: when signing short-enough messages, why don't we simply put the message where there is the message's hash in RSA signature padding like RSASSA-PKCS1-v1_5 or RSASSA-PSS of PKCS1v2.2?

Usual RSA deterministic signature as appendix goes $M\mapsto M\mathbin\|((P(H(M)))^d\bmod N)$ where $M\mapsto P(H(M))$ is a one-way function from the message space to $[0,N)$, built from a reversible injection $P$, and a hash $H$ for the one-wayness. The proposal is to change this to $M\mapsto (P(M))^d\bmod N$. That removes the one-wayness.

We don't have a constructive argument that's secure, and it should be reason enough not to do this. Worse, the gone one-wayness had a security role: preventing turning arithmetic properties of $x\mapsto x^d\bmod N$ into attack, by preventing going from $x$ with suitable arithmetic properties and in the right subset of $[0,N)$, to message $M$ with $P(H(M))=x$ allowing exploitation of said properties.

For some padding shemes, that removal of the one-wayness is enough to allow attack. Consider RSASSA-PKCS1-v1_5: we can obtain the signature of one message from the signature of three chosen ones, which is a break.

With the modification, the signature of $m$-byte message $M$ using private key $(N,d)$ with $n$-bit $N$ is, assimilating bistrings to integers per big-endian convention
$$\begin{align}
\mathcal S(M)&=(\mathtt{00\,01\,FF\dots FF\,00\,XX\dots XX}\mathbin\|M)^d\bmod N\\
&=(R\cdot2^{8m}+M)^d\bmod N\end{align}$$
with some fixed public integer $R\lesssim2^{193}$, when $m=\left\lceil\displaystyle\frac n8\right\rceil-26$. For example, consider message $M$ of $m=230$ bytes signed with $n=2048$-bit (256-byte) RSA key.

Now, if we find 4 distinct $m$-byte messages $M_0$, $M_1$, $M_2$, $M_3$ with $$(R\,2^{8m}+M_0)\,(R\,2^{8m}+M_1)=(R\,2^{8m}+M_2)\,(R\,2^{8m}+M_3)\tag{1}\label{eq1}$$
then it follows that $\mathcal S(M_0)\,\mathcal S(M_1)\equiv\mathcal S(M_2)\,\mathcal S(M_3)\pmod N$, and thus
$$\mathcal S(M_0)=\mathcal S(M_1)^{-1}\,\mathcal S(M_2)\,\mathcal S(M_3)\bmod N$$
which is easy to compute from $N$ and the signatures $\mathcal S(M_1)$, $\mathcal S(M_2)$, $\mathcal S(M_3)$.

We can take
$$\begin{align}
M_0&=R\,((2^{4m+i}+a)\,(2^{4m-i}+b)-2^{8m})\\
M_1&=R\,((2^{4m+i}+c)\,(2^{4m-i}+d)-2^{8m})\\
M_2&=R\,((2^{4m+i}+a)\,(2^{4m-i}+d)-2^{8m})\\\
M_3&=R\,((2^{4m+i}+c)\,(2^{4m-i}+b)-2^{8m})\\
\end{align}$$
which insure $\eqref{eq1}$ holds; and suitably small $i$, $|a|$, $|b|$, $|c|$, $|d|$ so that $0\le M_j<2^{8m}$. For example, $i=0$, $a=b=1$, $c=2$, $d=3$ will do.

Using that large class of messages, we can easily obtain $s$ bogus signatures from $s+3$ signatures of chosen messages. Or/and, since there's considerable freedom in the choice of the messages, we can force some application-imposed bytestring into some section of the messages, bringing that theoretical attack closer to practice. There are further classes of messages allowing other attacks.


Determine LFSR phase quickly? I know it's possible with work backwards from the output bits of an LFSR to determine its feedback polynomial in a O(n) fashion.  I'm also curious if, given an LFSR state and polynomial, is it possible to quickly work out how far the LFSR state is from a given epoch state (eg: the all-ones state).  The only sure-fire method I know of is to run the LFSR forwards/backwards until the state is the epoch state and keep track with a counter.

Edit: thinking about this more, this would be equivalent to solving $S = M^NE$ quickly $N$, where $S$ is your current state, $E$ is the epoch state and $M$ is the companion matrix of the LFSR.  Anyone have a fast solution to the discrete logarithm problem in the ring of $KxK$ $GF(2)$ matrices?

Well, one way to look at this is to notice that, if the feedback polynomial is prime, then the result of starting with state $E$, and then stepping the LFSR forward $N$ steps is the value $2^N \cdot E$, where we do the computation in $GF(2^K)$, using the polynomial representation (with the feedback polynomial being the polynomial).  In addition, I believe that if the feedback polynomial is not prime, then it is possible to factor that polynomial into its primes, solve the equivalent solution modulo each prime factor, and then recombine them.

So, the solving the problem of finding $N$ is equivalent to solving $S = 2^N \cdot E$ in $GF(2^K)$, or in other words, $S/E = 2^N$; that is, this problem can be reduced to solving a discrete log problem in $GF(2^K)$.

What does that rewording of the problem buy us?  Well, it turns out that there are recent results in this area; this paper shows us how this problem can be solved in "quasi-polynomial" time (by which they mean $K^{O(\log K)}$; technically supra-polynomial, but just barely); that paper tells us how to do discrete logs quickly over fields of small characteristic, and a characteristic of 2 is as small as it gets.


How is it possible to detect "unknown SHA-1 cryptanalytic collision attacks given just a single file from a colliding file pair"? The following description from http://shattered.it caught my eye:

  How do I detect this attack?

  You can use the online tool above to submit files and have them checked for a cryptanalytic collision attack on SHA-1. The code behind this was developed by Marc Stevens (CWI) and Dan Shumow (Microsoft) and is publicly available on GitHub.

  It is based on the concept of counter-cryptanalysis and it is able to detect known and unknown SHA-1 cryptanalytic collision attacks given just a single file from a colliding file pair.

I know basically nothing about cryptography, so I don't really know the full meaning of the phrase SHA-1 cryptanalytic collision attacks. The way I read the description, it states that I can analyze an arbitrary file on my hard drive and be told whether that file has been the target of a collision attack. If that is the case and if the tool's only knowledge of the world is the contents of my file, I can't see how such a thing could be possible.

I'm hoping someone can explain, in (relatively) simple terms, why my understanding is wrong or how this is actually possible.

The confusion comes from the following sentence:

  I can analyze an arbitrary file on my hard drive and be told whether
  that file has been the target of a collision attack.

The attack does not target "harmless" files, and generate a collision for them: this would be a second-preimage attack, which is a much harder problem to solve. A collision attack simply produces a pair of files with a collision. But using the current known attack, the pairs produced that way have a very specific structure, which can be easily identified. So, if you check one of your files, it tells whether it has been generated during the process of this attack.

Of course, other attacks can exist, that we are not aware of yet, and the current checker would not be able to tell that your file does not come from such an attack. What it tells you is only whether your files were generated in the process of this particular attack. Another way of saying that is: we have no proof that no second preimage attack exists (even though we have no idea how to build such an attack), but if one existed, it would indeed allow to find collisions for arbitrary files, and so any of your files could have been the subject of an attack of this kind, but no software could see that from your file.


Bellovin ESP Attack on UDP Packets In Bellovin's ESP Attack,
it is stated that:

  If $L_A$, $L_B$ are using UDP, attack is easier:

  Wait till session ends
  Allocate $L_B$'s UDP port to $X_B$
  Replay all packets

So, how does attacker know the UDP port of legitimate user $L$? Isn't it encrypted (because the UDP header encrypted)? How can the attacker obtain it?

Also, if the attacker knows the UDP port number of legitimate user, why should he wait till the end of the session? He can sniff the packets and change the UDP port number. Then he can receive the packages in another port during the session. Is my assumption wrong?

All UDP information (including the port number) is encrypted:
https://tools.ietf.org/html/rfc1827#section-3

(Please note that the link above points to the specification of ESP as it was when Steven Bellovin published his USENIX paper. This RFC is now obsolete.)

Guessing the port number should be quite easy: use the netstat command to list UDP ports in use, ignore the ones with a peer address which does not match, and the ones used by known services.

Actually the answer could be found in the original paper a few lines bellow where the TCP case is discussed.

  Still, on modern high speed net works it isn't that hard to make the
  sequence numbers wrap, and the attacker may be able to learn the
  necessary port numbers by polling via netstat on either machine.

This is very simple: the attack does not require much sophistication on the attacker's part. All that is required is a network capture and basic knowledge of UNIX system utilities such as ps and netstat.

This is Bellovin's point here: in this case tampering of the transmitted data is not even necessary to mount an attack. This is why waiting for the end of the process is mentioned. The attacks which can be performed while the process is still running require more work or more specialized tools. (Bellovin's main attack involves tampering with unauthenticated CBC encrypted data, as pointed out by Poncho in a comment.)


Signal-to-noise ratio in differential cryptanalysis What does signal-to-noise ratio mean in the context of differential cryptanalysis, and how can one use it to derive the number of required plaintext pairs to carry out a successful attack?

The point of differential cryptanalysis is to find a differential characteristic with sufficiently high probability.  You go through plaintexts until you find pairs that give you "enough" of a difference.  You know only plaintext and ciphertext difference and you do not know difference between individual rounds, because cipher is a black box.  (this is called filtration btw)

You use these pairs as a start for "key-recovery" by exploring the probabilities into possible subkeys in order to try to correlate the pairs.  Every pair suggests several subkeys.  Good pair suggests exactly one good subkey and few
wrong subkeys. How many times the correct subkey is more frequent than other subkeys is signal to noise (S/N) ratio.

There's a paper that I read (which currently eludes me) that had a nice description of this where they used about 2GiB of data an javascript to extract the keys from TLS.  You basically will want to look at the cipher of interest, and do a literature review to see how much data you'll need, unless you want to go into the mathematics yourself.


Does secure hashing imply secure symmetric encryption? I was wondering if the mere existence of a (by some definition) secure cryptographic hash function immediately implies an equally secure symmetric encryption scheme.

By my understanding, one could to the following given such a function:

Encryption: Using a shared secret key, we calculate the hash of the key concatenated with the first character of the text, the key concatenated with the first two characters of the text, etc. (every prefix), giving the same number of hashes as characters in the input. This would inflate the size somewhat, but only by a small constant factor.

Decryption: Knowing the key, we can calculate the hash of our key concatenated with every character from the alphabet, and once we find the one that matches the first hash, we can repeat the process with the next hash, until the entire text is found. This would require some more hash calculations than encryption, but only a constant factor, the size of the alphabet (this could be reduced by a bit for bit scheme instead of a character by character scheme).

As far as I know, this incremental series of slightly different inputs to a hash function should not cause the resulting hashes to be predictable, and neither should it leak information about the key.

One weakness I can see is that messages that start out the same and are using the same key will have the beginning of the hash sequence equal up to the point of divergence, but this can easily be mitigated by prefixing the message with a unique ID of some sort, perhaps just a hash of the message itself.

The above is the reasoning that made me think that "hash function" ⇒ "symmetric encryption".

Is there some fundamental principle or scheme that proves/disproves that this is the case?

The existence of a family of collision resistant compressing functions does indeed imply the existence of CPA secure, CCA secure and even authenticated encryption. This follows from several classic results in cryptography.

A family of collision resistant compressing functions is also a family of one-way functions.
By the seminal work of Håstad, Impagliazzo, Levin, and Luby (commonly referred to as HILL) "A Pseudorandom Generator from any One-way Function" [HILL99] any one-way function implies the existence of a pseudorandom generator (PRG).
The equally important work of Goldreich, Goldwasser, and Micali "How to construct random functions" [GGM86] had already established that a PRG was sufficient to construct a pseudorandom function (PRF) via the so-called GGM construction.

Once you have PRFs, you have two things. First the classic example of a CPA secure encryption scheme where the ciphertext is $(r,F_k(r)\oplus m)$ for a uniformly chosen $r$. Second, the PRF itself is also a deterministic message authentication code with canonical verification. Using the encrypt-then-mac construction we can then construct a secure authenticated encryption scheme.


Possible Digital Signature Hack? I am starting to learn more about cryptography and I just read more about how asymmetric keys can make a digital certificate, and I would like if someone could explain me why the following case can't be applied:

Since asymmetric keys rely on a pair of keys, and you use the private key to encrypt the hash of the document you want to sign so someone later can read the encrypted hash using your public key, to look for a match with the document's hash...why can't someone generate another private key that will match your public key and fool the whole process?

Usually every text about asymmetric cryptography focus on how difficult it is to find the original private key or to break the cypher-text, but my point is, in order to make someone believe your document/code/website is legit and certificated, you don't need to find the original private key, any new "malicious" private key that matches the well known public key of the CA (certification Authority) will be able to sign everything you want with this new key, so the public key will match and decrypt it.

I don't know very well the asymmetry keys math, so there might be "something" there that also prevents this, but so far I haven't seen any information, like how unique is the connection between the keys and how difficult it is to generate a key ('A') that will match a previously given key ('B').

why can't someone generate another private key that will match your
  public key and fool the whole process?

Because in most schemes, this is equivalent to recovering the private key from the public key (this can be somewhat easily seen for RSA and trivially for ECC-based schemes). And as we assume that recovering the private key from the public key is hard, finding a secondary private key that matches a given public key can be considered hard as well.


Are there transitive ciphers (either symmetric and asymmetric) Say Alice has information that's already encrypted with Bob's key.
She wants Bob to decrypt it without knowing what he just decrypted.
So she encrypts it with her key and sends it to him, he decrypts with his key, and sends it back and she decrypts it with her key.

Is there a block cipher where this would work?

Actually, there's the Pohlig-Hellman cipher (dating back to the 70's) that can do precisely this; it works like this:

There's a large public prime $p$ (for which the DLOG problem is hard)
The secret key is an integer $x$ that is relatively prime to $p-1$
To encrypt a message $M$ with key $x$, we compute $C = M^x \bmod p$
To decrypt a message $C$ with key $x$, we compute $M = C^{x^{-1} \bmod p-1} \bmod p$

It should be clear that the encryption and decryption processes (for a fixed key) are inverses of each other, and that this allows Alice and Bob to do precisely what you asked for; if Alice has $M^b$, she can give Bob , $(M^b)^a = M^{ab}$; Bob computes $(M^{ab})^{b^{-1}} = M^a$, and send that back to Alice, who can then recover $M$


How does MD5 divide the padded message in 16 words? This is the image from a website that shows all the steps of the MD5 Hashing algorithm:

The original message is 'Hello World!'. I don't understand where these values are coming from:

For example the 1st word '[0]' is 1819043144. What is that number representing from the original message?

1819043144 in decimal is 6c6c6548 in hexadecimal.  In US-ASCII, the letters have the following encodings:

H = 0x48
e = 0x65
l = 0x6c
l = 0x6c
etc.

‘Word’ here means a group of bits of a natural size for a machine, typically larger than a byte; in this case, it's a group of 32 bits.  It does not mean an English word like ‘Hello’.  MD5 breaks the padded message into blocks of 16 words (512 bits) apiece to work on one at a time before moving onto the next block in sequence.


Low Public Exponent Attack for RSA I'm having trouble understanding the algorithm for finding the original message $m$, when there is a small public exponent. Here is the example I'm trying to follow (you can also read it in the 'Low exponent RSA paragraph' of this article- http://www.cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/rsa.pdf):

Someone sends a message, $m$ to 3 people (without any padding) with public keys $n_b$, $n_c$ and $n_d$ and public exponent of 3. The article says:

  By using the Chinese Remainder Theorem, the eavesdropper computes a number $c$ such that $c = m^3 \mod n_b \cdot n_c \cdot n_d$.

Maybe I don't completely understand the Chinese Remainder Theorem, but I don't understand how you could choose a system of congruences to solve that would end up being equivalent to $c = m^3 \mod n_b \cdot n_c \cdot n_d$ when you don't know what $m$ is. Can you please help me understand what to use as the system of congruences to get to that point because I think I understand the rest.

You don't need to know $m$. You know $m^3$ modulo each modulus, which is sufficient. You want to find:

$$c \equiv m^3 \pmod{n_b}$$

$$c \equiv m^3 \pmod{n_c}$$

$$c \equiv m^3 \pmod{n_d}$$

Because $n_b$, $n_c$, $n_d$ are pairwise coprime (assume they have no common factors) a solution must exist.

The Wikipedia page has a nice explanation of the algorithm to find $c$. The actual expression is:

$$c = c_b (n_c \cdot n_d) [ (n_c \cdot n_d)^{-1} ]_{n_b} + c_c (n_b \cdot n_d) [ (n_b \cdot n_d)^{-1} ]_{n_c} + c_d (n_b \cdot n_c) [ (n_b \cdot n_c)^{-1} ]_{n_d}$$

Where $[a^{-1}]_b$ is the multiplicative inverse of $a$ modulo $b$. Note $\gcd{(a, b)} = 1$ is always satisfied. Also, I used the notation $c_b = m^3 ~ \text{mod} ~ n_b$, $c_c = m^3 ~ \text{mod} ~ n_c$, $c_d = m^3 ~ \text{mod} ~ n_d$.

Let's try with some numbers. Suppose someone sends the message $m = 102$ to three different people with textbook RSA, with moduli $n_b = 377$, $n_c = 391$ and $n_d = 589$. So:

$$c_b = 102^3 ~ \text{mod} ~ 377 = 330$$
$$c_c = 102^3 ~ \text{mod} ~ 391 = 34$$
$$c_d = 102^3 ~ \text{mod} ~ 589 = 419$$

So the attacker wants to solve the following system of congruences:

$$c \equiv 330 \pmod{377}$$

$$c \equiv 34 \pmod{391}$$

$$c \equiv 419 \pmod{589}$$

Using the equation above, we obtain (compute each term separately for clarity):

$$t_b = c_b (n_c \cdot n_d) [ (n_c \cdot n_d)^{-1} ]_{n_b} = 330 (391 \times 589) [ (391 \times 589)^{-1}]_{377} = 24471571740$$

$$t_c = c_c (n_b \cdot n_d) [ (n_b \cdot n_d)^{-1} ]_{n_c} = 34 (377 \times 589) [ (377 \times 589)^{-1}]_{391} = 505836734$$

$$t_d = c_d (n_b \cdot n_c) [ (n_b \cdot n_c)^{-1} ]_{n_d} = 419 (377 \times 391) [ (377 \times 391)^{-1}]_{589} = 35452267942$$

$$\therefore c = t_b + t_c + t_d ~ \text{mod} ~ (n_b \cdot n_c \cdot n_d) = 1061208$$

And we get $m = \sqrt[3]{c} = \sqrt[3]{1061208} = 102 = m$.

Note this attack on textbook RSA would work on any exponent given a sufficiently large number of people, of course $e = 3$ is the most realistic setting (and easiest to demonstrate, for obvious reasons).

The idea, of course, being to use these relations with the CRT to manufacture a relation of the form $m^3 \equiv x \pmod{n'}$ where $n'$ is on the order of $n^3$ (and, more crucially, where $1 < m < n$) such that $m^3$ is not reduced (and so you can just take cube roots).


TLS_DH_RSA_* cipher, how can static DH use an RSA certificate? I am confused about TLS_DH_RSA_* ciphers because, for DH to work, the server certificate has to include a DH public key, but for server authentication the server certificate needs an RSA public key. Can an RSA certificate include both a DH public key and an RSA public key?

Can somebody help to explain how DH_RSA key exchange works?

Look at TLS 1.0 Section 7.4.2, DH_RSA means a DH certificate which itself is signed using RSA by a CA.

The server has a static (long term) DH keypair. The public is included in a certificate and signed by a CA using RSA.

In the handshake, the server sends the certificate which includes the server's static DH public, signed by CA using RSA.

The client verifies the cert chain using RSA like normal, generates an ephemeral DH keypair, performs DH computation against the server's static DH public, computes shared premaster secret. The client sends the client's ephemeral DH public in the ClientKeyExchange.

The server receives the ClientKeyExchange, performs a single DH computation, and computes the same shared premaster secret.

There is no asymmetric encryption or online asymmetric digital signature operation in the handshake - only the DH operation.

This is historic, right? You're not going to use it, right?


Zero-knowledge proof for subset sum problem? What is the currently most efficient (interactive) zero knowledge proof/argument for the subset sum problem?

The most recent relevant paper I have found is Efficient Modular NIZK Arguments from Shift and Product - Prastudy Fauzi, Helger Lipmaa, Bingsheng Zhang, but it considers NIZKs and is quite involved.

I assume there are more efficient interactive protocols?

I would suggest rewriting your subset-sum problem as a lattice problem, either Approximate Close Vector Problem (Approx-CVP) either a Bounded Distance Decoding Problem (BDD), depending whether your subset-sum has low density or high density. Then, there should be plenty of litterature for efficient zero-knowledge proofs for lattice problem (like this one, but I'd guess there are more recent work with better efficiency).

To translate the subset-sum instance $t = \sum^n_{i=1} x_i b_i \bmod M$ into a lattice problem, consider the $n$-dimensional lattice $L = \{ \vec v \in \mathbb Z^n | \sum v_i b_i = 0 \bmod M\}$. Choose any $\vec y \in \mathbb Z^n$ (not small) such that $t = \sum^n_{i=1} y_i b_i \bmod M$. Then, solving your subset-sum is equivalent to to writing $\vec y = \vec v + \vec x$ where $\vec v \in L$ and $\vec x$ is small. Depending on how short of an $\vec x$ you expect, this is either an Approx-CVP problem or a BDD problem.


What are "encrypted instruction sets"? In 1999, a news article (Careless mistake reveals subversion of Windows by NSA) discussed "encrypted instruction sets". What exactly are these? Please provide a link so I can find more information.

Does it have anything to do with the following:

A First Practical Fully Homomorphic Crypto-Processor Design

Next-Generation Secure Computing Base

A similar question was asked here some time back (What are 'Encrypted Instruction Sets' ?), but it did not garner any useful responses.

I am already aware of hardware-based encryption & Intel's native support for AES. This one seems very different from the others.

i guess that encrypted instruction set is an encrypted instruction commands for cpu that will only work for encrypted programs.you can steal the program but can't execute it on your normal computer,or you can't hack to that computer because that computer can't run normal standard program unless it switch to normal instruction or translate the program.


Any practical uses of machine learning for cryptography? I am about to go study for my masters in machine learning, data mining and high performance computing, but have recently become very interested in cryptography after taking Dan Boneh's Cryptography course on coursera.com.

I was wondering if there are any practical applications for machine learning in cryptography? A quick google search didn't seem to reveal much for me so i was wondering if someone here knows something.

My first impression would be that machine learning techniques could be used to learn the inverse function for some cipher and passphrase given enough plaintext/ciphertext pairs, but i am not sure how capable things like neural networks are at learning functions which are not linearly separable.

I would personally be very surprised if machine learning was of any use in a known plaintext attack.

We design our ciphers to look a lot like random functions; you give the black box an input, and an output spits out.  You give it a second input (possibly the same input in the case of nondetermanistic encryption), and a second output spits out.  What we try to achieve is that no one can determine whether the black box was our cipher (with an unknown key), or whether it's just spitting out random outputs.

Now, we assume that the attacker has the complete design of our input (apart from the 'key'); in a successful cipher, he still cannot determine it.  In fact, we design things so that the attacker can submit inputs of his own choosing; he still cannot determine whether he's giving inputs to the cipher or a random function.

Now, what machine learning would be trying to do is essentially this, except that you would be ignoring the design (because there's no way to give the design to the machine learning process), and you are limited to a known plaintext attack (because your machine learner has no way to generate the chosen inputs).  In addition, your machine learner would also not have the best asset a cryptanalyst has (which is his cleverness; programs aren't good at 'clever').

Now, I don't know enough about machine learning to say that it can't be used elsewhere (or that a clever cryptanalysis couldn't use a machine learning program to help with his cryptanalysis); however it certainly sounds to me that machine learning would not be enough to do the entire cryptanalysis job.


Does a trace of SSL packets provide a proof of data authenticity? I'm wondering if it would make sense to record a whole HTTPS session,
publish its encryption keys and present it to third parties as a proof
that this particular data was sent by a given server identifying
itself with some signed certificate. Could such proof be forged in any
way?  Should this proof be convincing to third parties who receive it?

To complete what @CodesInChaos explains:

If the server has a RSA key in a certificate which is suitable for encryption, then anybody can forge a completely fake conversation without the server being involved at all. In the SSL/TLS protocol, when using a "RSA" cipher suite, the client generates the random "pre-master secret" which it then encrypts with the server's public key; the server merely decrypts it. The attacker then just has to play the roles of both client and server, and speak with himself. In a normal SSL/TLS situation, outsider cannot fathom the SSL connection because they only observe the encrypted pre-master secret; but our envisioned attacker chose the pre-master secret, so he knows it perfectly. The same reasoning applies to the case of a server with a Diffie-Hellman certificate (but who does that anyway ?).
If the server key is not suitable for encryption, but for signatures (e.g. it is a DSA or ECDSA key, or it is a RSA key but the server's certificate contains a Key Usage extension which restricts it to signatures only), then the attacker must "prime" the attack by contacting the server once. With the "DHE" cipher suites, the server generates an ephemeral Diffie-Hellman key pair, signs the public key, and sends it to the client. Once the attacker has a nice signed DH public key from the server, he can use it to build fake SSL connections (as many as he wishes).

The problem is a bit more interesting in the other direction: the server recording a SSL/TLS connection with certificate-based client authentication, and wanting to use it as a proof. The signature computed by the client happens during the initial handshake, and everything which is sent afterwards is encrypted and MACed with the agreed-upon symmetric key, which both client and server know, so the server could fake it at will. However, what the client signs is a hash of all preceding handshake messages, which includes the server's certificate, and also the client random and server random. An interesting point is that the first four bytes of the "client random" are not random at all; they are supposed to encode the current time, with second accuracy.

Therefore, by recording the handshake messages of a SSL connection with certificate-based client authentication, one obtains a proof that the client did connect to a specific server, and even at what time the connection happened (note that the time is relative to how well the client system clock is adjusted; I have encountered personal computers which were off by several years, to the blissful ignorance of their owners). Of course, it says nothing about the data which was exchanged afterwards.

(Whether this "proof" would have any legal value is another, quite distinct subject; I am only talking about the cryptographic half of the problem.)


Non-standard signature security definition conforming ed25519 malleability According to the paper “High-speed high-security signatures”…

  Malleability. We also see no relevance of "malleability" to the standard definition of signature security.

Aside from the example, how is ed25519 malleable by the non-standard definition of signature security?

To be more specific:

I'd like to know about any malleability with signatures/keys. The example provided seems not to be a risk because the key must also change. If anything's been discovered since this paper, that would also be helpful. I'm concerned with ECDSA type malleabilities and wonder if there's anything “close”.

Ed25519 in the default implementation is malleable.

It includes the public key $A$ in the hashed message, so it cannot be modified
It includes $R$ in the hashed message, so it cannot be modified
$S$ is encoded as a 256 bit. But since it's a scalar, $S^\prime = S + k \cdot l$ is equivalent to $S$ for any integral $k$ (where $l$ is the order of the subgroup, slightly larger than $2^{252}$).

This means that $S$ is malleable if the implementation doesn't verify that $S < l$. I verified this malleability with the Ref10 implementation.
There could be equivalent values for $S$, even when verifying that $0 \leq S < l$. The paper says:

  Malleability. We also see no relevance of “malleability” to the standard definition of signature security. For example, if we slightly modified the system then
  replacing $S$ by $−S$ and replacing $A$ by $−A$ (a slight variant of the “attack”
  of [75]) would convert one valid signature into another valid signature of the
  same message under a new public key; but it would still not accomplish the
  attacker’s goal, namely to forge a signature on a new message under a target
  public key. One such modification would be to omit $\underline{A}$ from the hashing; another
  such modification would be to have $\underline{A}$ encode only |A|, rather than A.

The way I understand this is that there are no such equivalent values.
$S$ malleability is implementation dependent. Other implementations or batch verification might have different properties.