Lower bound of key space size with relaxed perfect secrecy My apologies, I'm quite new to cryptography.

If we relax the definition of perfect secrecy such that
for cyphertext $c$, messages $m_0$ and $m_1$, and constant $E$:

$P[c|m_0] \le E * P[c|m_1]$

Using this, Can I prove a lower bound on the size of the key space as a function of the size of the message space?

I don't understand how I can know anything about the size of the key space without further knowledge of the encryption procedure used and the size of messages and keys.

Oddly enough, if the equation holds for any $m_0, m_1$ of the appropriate length, it would appear that relaxing this requirement doesn't allow us to shrink the key size at all (!).  That is, the key size must still be as long as the plaintext size (or, more precisely, there must be at least as many possible keys are there plaintexts).  Allowing a value of $E > 1$ turns out not to allow us to use smaller keys; OTP is still an optimal solution for the requirement.

Here's why: this requirements still requires plaintext $m_1$ to have nonzero probability (as if it doesn't, then the equation can't hold if $m_0$ is any plausible plaintext).  Any, if there were fewer keys then plaintexts, that would mean that some plaintext is impossible (and hence have zero probability).  Because that can't happen, that means that there must be at least as many keys as plaintexts.


Secure order preserving hash function Is there a construction of an order preserving hash function that keeps the preimage property of a crypto hash function? By order preserving hash function (OPHF) i mean for $x<y$ then $OPHF(x) < OPHF(y)$

The problem with a hash function like you ask for is that, if you hash an $n$-bit string and give the hash to someone else, they can recover the string using $n$ hash calculations with a binary search.

For a simple example, let's say the $n=8$, your string is $01011001$ in binary, and its hash is $Y = H(01011001)$.

To recover the string from the hash, I start by calculating $X_1 = H(10000000)$ and comparing it with $Y$.  Since $10000000 > 01011001$, and since $H$ is order-preserving, $X_1 > Y$ and I therefore now know that the first bit of your string is $0$.
Next, I'll calculate $X_2 = H(01000000)$ and again compare it with $Y$.  Since $01000000 < 01011001$, this time $X_2 < Y$, and thus I now know that the first two bits of your string are $01$.
Using this knowledge, the next hash I'll calculate will be $X_3 = H(01100000)$.  Since $01100000 > 01011001$, now $X_3 > Y$, and thus I know that the first three bits of your string are $010$.
The next hash I'll calculate will be $X_4 = H(01010000)$, which I'll compare with $Y$ to find the fourth bit of your string, and so on, until I've recovered every bit of your string.

This flaw is inherent in the idea of order-preserving hashing: if I can obtain the hash of any valid string, then I can always carry out such a search.  In fact, even if I can't get the actual hashes, but can only ask you for the result of the comparison between $H(s)$ and $Y$ for some input string $s$, I can still recover your original string without even seeing its hash value!

Basically, if you ever played the "guess what number I'm thinking of?" game as a child, this is exactly the same situation.  You have a secret string, and I get to guess a string and see if it's less than or greater than your secret.  As in the game, with the right guessing strategy I won't need too many guesses to find the right answer.


ECDSA Verification - Last Steps Reaching the end of an ECDSA signature verification, we need to compute multiple point multiplication and addition as following: $R=(x_R, y_R) = u_1G + u_2Q$, where $u_1$ and $u_2$ are scalars, $G$ is the curve generator and $Q$ is the public key point. As we're using elliptic curve operations we're computing our curve operations $\mod q$, with $q$ being the field order.

If $R$ is a valid point on the curve and $R \neq\infty$, we need to compute $x_R\mod n$, with $n$ representing the order of the generator, and compare that to the $r$-part of the signature. Why do we need another reduction $\mod q$ if we have already reduced $\mod n$ after the multiplication part?

There are two different primes being used here.

Using your notation, $q$ should be the prime defining the field $\mathbb{F}_q$ over which the curve is defined.

$n$, instead, indicates the (prime) order of your generator $G$.

The coordinates of points, and therefore the computations of scalar multiplications and point addition, are done in $\mathbb{F}_q$.

So, your point $R$ will have coordinates $\bmod q$. But you still need to apply the modular reduction with respect to $n$ to $x_R$ in order to make verification work.
This is because the $r$-part of the signature is also computed $\bmod n$ and $n$ is allowed to be smaller than $q$.


Is every output of a hash function possible? Is every output of a hash function (e.g. SHA1, MD5, etc) guaranteed to be possible, or, conversely, are there any output values that cannot possibly be created from any input? In other words, are hash functions surjective?

If so, what guarantees this? If not, is it possible to discover such impossible outputs via an attack faster than brute force?

There is no proof that every output of common hash functions is reachable for some input, but it is expected to be true. No method better than brute force is known to check this, and brute force is entirely impractical.

By the coupon's collector argument, it is expected to require $2^n\cdot(n\cdot\ln(2)+\gamma)+1/2+o(1)$ random values to reach all $n$-bit values, with $\gamma\approx 0.577216$.

Translated to hashes, about $2^{134.5}$ (for MD5) or $2^{166.8}$ (for SHA-1) distinct messages are expected to be required to reach all output values, on the assumption that these hashes behave as random functions. This assumption is reasonable, as it is the design goal of the round function of these hashes.

Update: as stated by Jon Callas in an other answer, it is possible to construct hash functions which demonstrably do not reach all their output; and even some that are computationally secure. One example is $\mathcal{H'}=\mathcal{H}(\mathcal{H}(m)|1)$ where $|$ is bitwise OR, and $\mathcal{H}$ is a common hash function. $\mathcal{H'}$ reaches markedly less than half of its output space, but is likely as fine as $\mathcal{H}$ by all other experimental metrics except speed.


GCM Construction of table M0 I am reading the paper on GCM  The  Galois/Counter  Mode  of  Operation  (GCM)  . I have some doubts about the implementation of table M0 and R.

When I have to multiply by the variable P it is nothing more than a shift to the indexes. At the top of page 10 I have the example of multiplication by X · P and I suppose the one below is to multiply two elements.

  Z ← 0, V ← X
  for i =0 to 127 do
  if Yi =1 then
  Z ← Z ⊕ V
  end if
  V ← V · P
  end for
  return Z

From what I understand:

  V ← V · P

Is equal to:

  if V127 =0 then
  V ← rightshift(V )
  else
  V ← rightshift(V ) ⊕ R

According to the examples on page 9 in formulas (3) (5), would they be the same, right?

Well already on page 11 in the example of the deconposition of X (7), xi refers to 1 byte of X, but my doubt is in P ^ 8i, in the first for 8 · i would give zero and at the end when i is 15 would be 120. That part I don't really understand.

Going to algorithm 3 and its explanation above:

  while i> 0 do
  M ← M[2i] · P
  i ←li/2J

Assuming that the value of i is 64, that cycle would multiply by P eight times if I am not mistaken.

Well and in the part of the multiplication by P:

  M ← M[2i] · P

Is equal to:

  if  M[2i]127 =0 then
  M ← rightshift(M[2i])
  else
  M ← rightshift(M[2i]) ⊕ R
  end if

And the 247 additions would be:

  M[i + j]= M ⊕M[j]

Everything explained above is fine, it would be enough to build table M0 and R? But I don't understand the following elevation P^8(i+1) and P^128.

Thanks.

This is one of the most poorly written "mainstream" crypto papers I've read. Sorry, McGrew and Viega.

Field representation and bit order

GCM works in the binary field $GF(2^{128})$. Elements of this field can be represented as polynomials with binary coefficients (i.e. 0 or 1).

Using the notation of the paper, here are some examples of field elements:

$1$ (note that this is $0\alpha^{127} + 0\alpha^{126} + \ldots + 0\alpha^1 + 1$; we simply don't writte the coefficients with 0).
$\alpha^1 + 1$
$\alpha^2 + \alpha$
$\alpha^{127} + \alpha^{64} + 1$
$\alpha^{127}$

Cool. So how do we represent this in memory, since we only have bits and bytes, and not actually polynomials? The straightforward way is to simply group the coefficients in groups of eight, inside bytes. Which raises the question: how to order the bits inside the byte? And how to order the bytes inside the 16-byte buffer (totaling 128 bits)?

One straightforward answer is to use little endian for both bits and bytes; i.e the least significant bit of the byte (i.e. what you get with x & 0x01, note that calling this "little endian" it not that usual but I need to call it something) is the least significant bit of the 8-bit group; and the least significant byte of the buffer (i.e. what you get with b[0]) is the least significant 8-bit group of the 16 groups.  So these examples would be encoded as:

$1$: 0x01 0x00 ... 0x00
$\alpha^1 + 1$: 0x03 0x00 ... 0x00
$\alpha^2 + \alpha$: 0x06 0x00 ... 0x00
$\alpha^{127} + \alpha^{64} + 1$: 0x01 0x00 ... 0x01 ... 0x00 0x80
$\alpha^{127}$: 0x00 ... 0x00 0x80

This seems natural (at least it does for me); but you could make a convicing argument for a "little-endian" bit order and big-endian byte order since it looks more like the way we write the polynomials. That's OK. Is that what GCM does? No, it isn't.

GCM uses "big-endian" for bits, and little-endian for bytes. Our examples become:

$1$: 0x80 0x00 ... 0x00
$\alpha^1 + 1$: 0xC0 0x00 ... 0x00
$\alpha^2 + \alpha$: 0x06 0x00 ... 0x00
$\alpha^{127} + \alpha^{64} + 1$: 0x80 0x00 ... 0x80 ... 0x00 0x01
$\alpha^{127}$: 0x00 ... 0x00 0x01

So there's that.

Now actually answering the question

  According to the examples on page 9 in formulas (3) (5), would they be the same, right?

Yes.

  Well already on page 11 in the example of the deconposition of X (7), xi refers to 1 byte of X, but my doubt is in P ^ 8i, in the first for 8 · i would give zero and at the end when i is 15 would be 120. That part I don't really understand.

As I described, the coefficients of the polynomials are grouped into 16 bytes with 8 bits each. Formula (7) is just the mathematical way of saying that. Note that $P = \alpha$. Why not call the same thing by two different names?

For example, take the field element $X = \alpha^{15} + 1$. This is represented by the byte buffer 0x80 0x01. So in the decomposition, we have:

$x_0$ = $1$ = 0x80
$x_1$ = $\alpha^7$ = 0x01 (we're looking at it as a 8-bit polynomial)

and then, $X = \bigoplus\limits_{i=0}^{15} x_iP^{8i} =  \bigoplus\limits_{i=0}^{15} x_i\alpha^{8i} = x_0\alpha^0 + x_1\alpha^8 + ...$ = $1\alpha^0 + (\alpha^7)\alpha^8 = 1 + \alpha^{15}$.

  Assuming that the value of i is 64, that cycle would multiply by P eight times if I am not mistaken.

Table $M$ contains $M[x] = xH$ for all 8-bit polynomials and the 128-bit polynomial $H$ (which is computed from the key).

That cycle multiplies by $P$ seven times. That loop is computing $M[128], M[64], M[32], ... M[1]$. Recall that the index is actually a polynomial, so that's the same as $M[1], M[\alpha], M[\alpha^2], ..., M[\alpha^7]$. Yes, $128 = 0x80$ (the number) is equal to $1$ (the polynomial). Welcome to GCM.

  Everything explained above is fine, it would be enough to build table M0 and R? But I don't understand the following elevation P^8(i+1) and P^128.

I think what I've explained covers the rest of your question, but I'm not sure. Feel free to ask for clarifications and I'll edit the answer.


How to cipher bocks with RSA in ECB mode? I'm trying to implement a very basic RSA with functions that should generate RSA keys and cipher some text. GenKey function returns a tuple (p,q,n,e,d) like the following.

p,q large prime numbers with 1024bits each
n = p*q
phi(n)=(p-1)(q-1)
e as gcd(phi(n),e)=1 and 1 < e < phi(n)
d = e⁻1 (mod phi(n))

At the end I'll get a public key like kp={e,n} and a private one ks={d,n}. So far everything is working as expected.

Now suppose that cipher function receives a string of binary data as the plaintext to cipher and outputs a ciphered text in ECB mode(a binary string aswell). I Know that in order to cipher I can do the following: C = M^e (mod n) if M is an integer. If it's not I think I have to break my binary string into say 32bit length substrings, calculate it's integer value, apply C = M^e (mod n), get the new integer and last represent it back into binary. Please correct me If I'm wrong at this point.Am I thinking it right?

So my question is, when calculating C is it possible that returned value is too bigger for representing (as binary) on my block size decision (those 32bit). How block size should be picked?

Securely enciphering text with RSA is typically done in one of three ways:

The most usual one is with the help of a symmetric cipher: RSA is used to establish a symmetric key, and the text itself is enciphered with the symmetric cipher. That's a hybrid cryptosystem. One way is that the sender generates a uniformly random $x$ in range $[0..N)$, enciphers it with the textbook RSA public-key function $x\to x^e\bmod N$ and sends the results (of 256 octets) which the receiver can decipher; then both extract the (say) 192 low-order bits of $x$ and use it as key for AES-CTR, which enciphers the text.
RSA-ECB with random padding: the text is broken into pieces significantly smaller than the public modulus (e.g. 190 octets pieces for 2048-bit RSA); each block associated with some randomness and redundancy (e.g. 32+34 octets) into a padded block, by some algorithm (e.g. RSA(ES)-OAEP) typically involving a hash (e.g. SHA-256); each result $x_i$ is enciphered with the textbook RSA public-key function $x_i\to{x_i}^e\bmod N$; the results are concatenated. Decryption undoes that and discards the randomness. This option has huge drawbacks when more than one block is involved: slow decryption, sizable ciphertext expansion (e.g. +15% for large text). In practice, it is thus used only for small amount of data (e.g. the secret PIN number of a credit card).
RSA is used (possibly multiple times) to establish a shared secret random keystream as long as the plaintext, then used to encipher the plaintext with XOR (or other equivalent information-thoretically perfect cipher). E.g the sender generates uniformly random $x_i$ in range $[0..2^{2040})$ (enough that the 255-octet $x_i$ concatenated are at least as long as the plaintext), enciphers them with the textbook RSA public-key function $x_i\to{x_i}^e\bmod N$; the results are concatenated and sent, as well as the plaintext XORed with the keystream. This is nearly as slow as 2 (there are almost as many RSA decryption to perform), has significantly worse ciphertext expansion (ciphertext is over twice as large as plaintext), but requires no keyed cipher (as 1 does) or padding function (as 2 does).

In 2, cutting corners on randomness would allow an adversary to check a guess of a plaintext (that's a disaster for a PIN number, or the name of someone on the public class roll). Cutting corners on the padding function leads to other, more subtle security issues. Some introductory material uses 2, cuts corners on both randomness and padding, and uses very small $p$ and $q$. That's justifiable only for teaching purposes and with ample warnings (sadly often skipped or/and forgotten).

For large $p$ and $q$, the only recommendable options are 1; 2 exclusively limited to short plaintext and with decent randomness and padding function; or 3 for something which for some reason (e.g. pedagogical, conceptual simplicity, code size..) must use neither a keyed cipher nor a hash.

Note: none of these options provide message integrity of any kind. Since the public key is known to attackers, they can generate messages with any deciphered content they will. Upgrading option 1 with authenticated symmetric encryption does not satisfactory solve that issue (it only ensures that an adversary can not alter part of a message while leaving some unknown portion unchanged).

  I know that in order to cipher I can do the following: C = M^e (mod n) if M is an integer.

That's textbook RSA, is cutting on both randomness and padding, and thus is unsafe. For a start, any guess of M can be checked, and that's an unwanted property in encryption.

As an aside, I read C = M^e (mod n) as $C\equiv M^e\pmod N$ which means that $N$ divides $M^e-C$, and that is not satisfactory (in particular it allows $C=M^e$ which allows recovery of $M$ from $C$ as $M=\sqrt[e]C$ ). The proper equation is $C=M^e\bmod N$ , additionally meaning that $0\le C<N$ ; notice there is no opening parenthesis before $\bmod$ , making it an operator similar to the % operator of C, Java, Go, rather than implying that the previous equality is modulo $N$ (which is the case with  an opening parenthesis before $\bmod$ ).

  If it's not I think I have to break my binary string into say 32bit length substrings, calculate it's integer value, apply C = M^e (mod n), get the new integer and last represent it back into binary.

The general idea of cutting in blocks is right if choosing option 2, but doing so in the manner stated is very unsafe due to the lack of added randomness, allowing to find each 32-bit integer by trial and error. Further, if $e<{2048/32}=64$, there is an attack without trial and error due to lack of padding (computing $\sqrt[e]C$ will always reveal $M$ ). Further, the ciphertext expansion is by a factor of ${2048/32}=64$, which is wasteful; and decryption will be dead slow. Larger blocks somewhat improve things, but what's really needed is randomness and proper padding; or better, getting rid of option 2 / RSA-ECB altogether.

  How should block size be picked?

If using RSA-ECB (which again is reasonable only for short messages, needing a single block), the choice is dictated by the padding algorithm used. In all such algorithms, that can be at most $\lfloor\log_2N\rfloor-r$ bits, where $r$ is the number of random bits added, which determines the security level against confirming a guess of $M$; $r\ge128$ is recommandable. For $N$ of $8b$ bits, a hash of $8h$ bits, RSAES-OAEP allows block size up to $b-2h-2$ octets. For $8b=2048$ and $8h=256$, that's $190$ octets. It is a tad wasteful, but RSAES-OAEP (also known as PKCS#1v2 encryption padding) is the only RSA encryption padding with both a security proof and good support in common crypto libraries.


Why develop Edward curve formulas that deviate from unification? Edward curves were considered initially because they provide a unified formula for both doubling and addition, thus having inherent side-channel resistance. But a lot of work has been done recently involving construction of a different class of addition and doubling formula (e.g. differential addition formula, w-coordinate formula), particularly concerning efficiency of these formulas in terms of the number of field multiplications/squarings. Thus, the point of unification becomes invalid.

Please can anybody explain/cite some relevant papers which address this issue?

Edwards curves can be implemented using a unified formula for addition and doubling; i.e., one can implement addition such that
$$\mathrm{dbl}(P)=\mathrm{add}(P,P).$$
Performance wise it is however more efficient to consider both functions separately, since the doubling can be implemented more efficiently than the addition.

Depending on the representation and the formulas, the unification property will be preserved or not. For instance, in "Twisted Edwards curves" by Berstein et al., there is a formula for $\mathrm{add}(P,Q)$ and a faster one for $\mathrm{dbl}(P)$, but the above property still holds. In "Twisted Edwards curves revisited" by Hisil et al., there are also two separate formulas, but the above property doesn't hold anymore.

I think the unification property looks great in a paper as it makes the description cleaner; however one does not necessarily need it in practice. Some examples:

Example 1: "Scalar multiplication (based on Exponentation by squaring)". When the factor is lower than the order of the group, you know that the next doubling is always higher than the accumulated value, so that an addition will always take place between two different points.
Example 2: "Addition of random points". The order of the group is in general so large, that the probabilty that two randomly chosen points are equal is negligible.

So in many situations the absence of the unification property does not seem to be an issue. It will of course depend on what precisely you are doing with the curve.


Why use Needham-Schroeder if we have Diffie-Hellman? If we want to establish secret symmetric key between two entities, why use Needham-Schroeder if we have Diffie-Hellman? With DH we don't need to have any trusted party, so what's the point of NS?

Both Needham-Schroeder (N-S) and Diffie-Hellman (D-H) are one of the earliest proposed key exchange protocols and thus they are usually used as classical textbook examples.
However, the originally proposed protocols have some flaws. The N-S Symmetric Key Protocol is vulnerable to a replay attack, the N-S Public-Key Protocol is vulnerable to a man-in-the-middle attack and the D-H is also vulnerable to a man-in-the-middle attack.

Therefore, improved schemes such as Kerberos (for N-S) and the Station-to-Station (STS) protocol (for D-H) were proposed.
The N-S makes use of a trusted server for authentication while the improved D-H or STS protocol uses public key certificates for authentication.
With STS, we are still making use of a trusted party which is the Certificate Authority for authentication.
Even though the web of trust concept (in PGP) may be used, it may not be scalable.

So the main differences between the two protocols would be:

To trust a single trusted party which you can maintain yourself or to trust the public Certificate Authorities.
To depend on the security of the underlying encryption schemes (such as AES for Kerberos) or to depend on the assumption of the discrete logarithm problem (for D-H).


(Why) should I avoid using a randomized IV for CTR mode? I'm currently reading the chapter of Cryptographic Engineering (Ferguson, Schneier, Kohno 2010) about block cipher modes of operation. They have recommended CBC with random IV instead of CTR due to the difficulty of generating nonces for CTR:

  In the first edition of this book, we recommended CTR. However, we are always learning more, and we now recommend CBC with random IV. [...] CTR is a very good mode, but only if the application can guarantee that the nonce is unique, even when the system is under attack. That turns out to be a major source of problems and security weaknesses. CBC with random IV has some disadvantages [...], but it is robust and stands up well to abuse. Nonce generation turns out to be a really hard problem in many systems, so we do not recommend exposing to application developers any mode that uses nonces.

To me this seems to be ignoring an obvious solution: use CTR with a random IV instead of a generated nonce. This would let us avoid these problems and keep the random-access fun of CTR. This possibility being ignored implies there's some issue with it, but nothing I've read suggests one to me.

I know that the value is used differently in the different modes...

CBC: the IV or previous output block are XORed with input block, then ciphered
CTR: the nonce is combined/XORed with the counter, then ciphered, then XORed with the input block

...but I don't see how this would prevent a random IV from being as secure as a properly-chosen nonce. It would also be unique, and would provide more bits of randomness than a nonce system (though I think this shouldn't be significant unless the cipher were  weak).

You say that a random IV "would also be unique", but really that is the crux of the problem.  The problem with counter mode is that it is secure unless the same counter is used twice; if it is, it is likely that an attacker will be able to recover both plaintext messages.  This contrasts with CBC mode, which if you repeat an IV, it has the relatively benign failure mode of allowing an attacker to detect whether or not the initial blocks of the messages are the same.

So, with random IVs, is the probability of a repeat sufficiently negligible that we can live with the possibility?  Well, that depends on the size of the IV, the total number of messages we're talking about (and our tolerance to risk; how small is negligible).  With 8 byte IVs, well, we're likely to see repeats (because of the Birthday Paradox) after a few billion messages (and have nontrivial probability of repeats before then); I would consider that too high of a risk to live with.  With 12 byte IVs, it's unlikely we'll see a repeat before a few trillion messages, but for very long-lived keys, perhaps this is unacceptable.  With 16 byte IVs, it is unlikely to ever see a true repeat, however now we'll need to worry about partial overlaps (where two different IVs generate the same block cipher input after combining with the counter for different parts of the messages).

In contrast, with CBC mode, we don't have to worry about any of this.  Once we make sure that the IVs are generated unpredictably (and we check the integrity of the encrypted text, a requirement of CTR mode as well), we're golden.  I believe Ferguson et al recommend CBC mode specifically because it is more foolproof and less fragile.


Generate a random number $r \in \{1,2, \dots , k\}$, where $k$ is not public and is distributedly held A set of parties can securely generate a random number $r \in \{1,2,3,\dots, k\}$ when $k$ is publicly known. However, can we generate the random number $r$ if $k$ is not publicly known and is held by the parties using a VSS scheme?

Can you point me to any Multiparty Computation literature which looks at the above question?

You can do anything in MPC, as long as you can express it in a circuit. I assume that there is a known upper bound on $k$ (otherwise you can't even share it). In that case, all you need to do is to take enough randomness (security parameter number of bits more than the upper bound) and then compute the sum of the randomness held by each party modulo $k$ (plus 1). This can certainly be done via a circuit.


How to effectively apply combination of Block and Stream Cipher? I have used TrueCrypt but it uses a cascaded encryption. I want to know about encrypting a file using two ciphers with each cipher having different key.

Cipher A (Block Cipher) - with Key KA

Cipher B (Stream Cipher) - with Key KB

First I am encrypting a file with Cipher A (KA). Again I am encrypting a file using Cipher B (KB).

Does this, in any way, make the final encrypted file vulnerable? Or, rather, leave some loopholes.

One other approach I thought is to compress a file before applying second cipher so as to make it more random.

Cipher A -> ZIP -> Cipher B

How secure is this and in which mode the two ciphers be operated to achieve high security?

** Edited **

Both the keys are different. Encrypted file also does not contain any key.

What you can do is convert the block cipher into a stream cipher. You can do this by using it as primitive for a stream cipher mode of encryption such as CTR. Then you can use the resulting key streams of cipher A and B and XOR them together with the plaintext.

In principle you can also encrypt it using a block cipher mode of encryption or stream cipher in any order. This should not leave loopholes.

Compression or no compression is a tricky question. I'd say that no compression is better. As long as your plaintext doesn't leak information through the size of the plaintext, you're OK. The amount of compression is dependent on the contents and size of the plaintext.

The problem with this is that the compression factor may differ for slightly different plaintext. This means that it will become next to impossible to not leak information.

It's good if the keys are not related to each other. For best security it would also be wise to make sure that the algorithms are not related either.

The use of two ciphers to achieve confidentiality is an operation with questionable returns. Often it is more useful to e.g. use public key cryptography (in a hybrid scheme, so that the private key is not required during encryption) and/or authenticated ciphers.


Relationship between Fibonacci LFSR and Galois LFSR I'm studying about LFSR and have some troubles understanding LFSRs.

For Galois LFSR, it is clear that LFSR just multiplies $x$, the primitive element of $GF(2^n)$, so that it makes all the elements in $GF(2^n)$.

But for Fibonacci LFSR, it seems somewhat awkward.

In the answer at math.stackexchange, it says each register of Fibonacci LFSR is the dual basis of Galois LFSR, but can't we express it in the polynomial term?

And I also wonder whether the 'mirror' polynomial scheme, like $x^4+x^2+x^1+1$ vs $x^4+x^3+x^2+1=x^4(x^{-4}+x^{-2}+x^{-1}+1)$ can help to understand Fibonacci and Galois LFSR.

Consider a Galois LFSR with feedback polynomial $x^3 + x + 1$ and initialization $1 + 0x + 0x^2$, that is, the shift register shifts its initial content $(1,0,0)$ rightwards, and the output bit (the rightmost bit) is fed back into the shift register into the $1$ and the $x$ position.  The initial loading of the LFSR is the Galois field element $1$, and successive contents are as follows:

$$\begin{array}[ccl]{3}
(1,0,0) &= 1 + 0x + 0x^2 &= 1\\
(0,1,0) &= 0 + 1x + 0x^2 &= x\\
(0,0,1) &= 0 + 0x + 1x^2 &= x^2\\
(1,1,0) &= 1 + 1x + 0x^2 &= x^3 ~~~ \text{remember that} ~x^3 = x + 1\\
(0,1,1) &= 0 + 1x + 1x^2 &= x^4\\
(1,1,1) &= 1 + 1x + 1x^2 &= x^5\\
(1,0,1) &= 1 + 0x + 1x^2 &= x^6\\
(1,0,0) &= 1 + 0x + 0x^2 &= x^7~~~ \text{remember that} ~x^7 = 1\\
\end{array}
$$
The LFSR output is the (periodic) sequence leaving the right end of the LFSR and is thus $(0,0,1,0,1,1,1)$ at which point the sequence repeats (the period is $7$). Notice that if we look at the successive contents of the leftmost bit in the LFSR,
they are $(1,0,0,1,0,1,1)$ which is just the output sequence shifted right cyclically by 1 bit while the middle bit is $(0,1,0,1,1,1,0)$ which is just the output sequence shifted left cyclically by one bit.

With the Fibonacci LFSR, there are two conventions as to what the feedback polynomial means. We can take $x^3+x+1$ to mean that the LFSR shifts right while the (XOR) sum of the current values of the output cell and the leftmost cell are fed back into the leftmost cell, or that the XOR sum of the two rightmost cells is fed back into the leftmost cell.  The corresponding LFSR contents are
$$\begin{array}[ccc]{3}
\text{output plus leftmost} & \quad & \text{two rightmost}\\
(1,0,0) & &(1,0,0)\\
(1,1,0) & &(0,1,0)\\
(1,1,1) & &(1,0,1)\\
(0,1,1) & &(1,1,0)\\
(1,0,1) & &(1,1,1)\\
(0,1,0) & &(0,1,1)\\
(0,0,1) & &(0,0,1)\\
(1,0,0) & &(1,0,0)
\end{array}
$$

Note that in the righthand column, the output sequence is $(0,0,1,0,1,1,1)$ which is identical to the output sequence of the Galois LFSR while in the lefthand column, the output sequence is $(0,1,1,1,0,1,0)$ which is just a reversed and shifted version of the output sequence of the Galois LFSR. Now, all this can be explained in great generality with reference to dual polynomial bases etc (as I did in my answer to the math.SE question cited by the OP), but the point is that the Fibonacci LFSR produces the same sequences as those produced by the Galois field LFSR, and that the reciprocal polynomial can be useful in explaining why this is so depending on the convention used to map the polynomial onto the circuit connections.

As a final note, Fibonacci LFSRs are vastly preferable to Galois LFSRs because the latter require Exclusive-OR gates between the "cells" of the LFSR while the former don't. Some modern hardware implementations of Fibonacci LFSRs don't actually store the data in the cells in a shift-register where the data goes ka-chunking from cell to cell as the register shifts (each transition costs energy!) even though that's what is always shown in illustrations and diagrams in textbooks and papers.  Instead, each cell content is stored in sRAM and accessed as and when needed (e.g. to participate in a XOR to be fed back to the "left-most" cell). What changes from clock cycle to clock cycle is the mental image (or memory map) of where the LFSR contents are stored in sRAM. The data itself does not move at all though one sRAM storage cell (the current "left-most" cell as per the memory map) gets its contents modified in each clock cycle. In a Galois LFSR implementation, many cells would need to be modified in each clock cycle leading to vastly increased complexity if everything is done in parallel or slowing down of the implementation so that the updates can be done sequentially in the time available for one "clock cycle" of the LFSR.


Computing a sextic twist Let $(x,y) \in E'_{\mathbb{F}_{p^2}}$ be a point of the sextic twist.

I am currently trying to compute:

$\psi : (x, y) \leftarrow (\mu^2x,\mu^3y)$ with $\mu \in \mathbb{F}_{p^{12}}$ the root of $(Y^2 - \xi)$ with $\xi = 1+i \in \mathbb{F}_{p^{2}}$.

From the original curve over $\mathbb{F}_{p^{12}}$ (that is $y² = x³ + 2$) I found the twisted curve over $\mathbb{F}_{p^{2}}$ (that is $y² = x³ + (1-i)$) so I am currently able to easily find points in the twisted curve. However I don't really understand how I am supposed to compute $\mu$ in order to compute $\psi$ and get my point in $\mathbb{F}_{p^{12}}$.

Does anyone have any idea of how I can find $\mu$? I mean is there an algorithm that computes $\mu$? I know that $\mu^6=1+i$ but how do I compute $\mu$?

Thank you very much!

The correct answer depends on the way the towering is done (if any towering was done). I used the following towering:

$\mathbb{F}_{p^{2}}/(i^2+1)$

$\mathbb{F}_{p^{6}}/(y^3+\xi)$ with $\xi \in \mathbb{F}_{p^{2}}$

$\mathbb{F}_{p^{12}}/(x^2+\xi)$ with $\xi \in \mathbb{F}_{p^{2}}$

For this towering, $\mu^2=y$ and $\mu^3=x$.


A standard extension of ECIES for multiple recipients (broadcast / multiparty)? I have one sender, and a small number (~5) of recipients. The sender knows each recipient's public EC key. I want the sender to broadcast a single message in such a way that any one of the recipients can decrypt it. For reasons that aren't completely technical, I'd like the security properties of the encryption algorithm to be as similar as possible to those of Bitmessage, which uses ECIES, with AES and HMACSHA256 as the symmetric cipher and MAC. I'd like the encrypted message to be as small as possible.

After a brief search, I couldn't find any "standard" (well-studied, or used somewhere high-profile) extension of ECIES for this case. I can obviously:

Choose a random session symmetric encryption key and session MAC key.
Symmetrically encrypt and MAC the message.
Asymmetrically encrypt the session keys with ECIES, once per recipient.

Then I can broadcast a concatenation of the encrypted message and encrypted session keys, and any recipient can decrypt his copy of the session keys and decrypt the message. That adds a lot of overhead, though. So, using Wikipedia's variable names:

When I do ECIES, can I omit the MAC $d$? An attacker doesn't gain anything by tampering with the session key, since that just causes the inner decryption or MAC check to fail. The answer is "no" here if we naively encrypt-then-MAC the inner message, more complicated otherwise as discussed below.
Can I use the same ephemeral EC pair $R = rG$ for all recipients?
Can I use the same IV for all invocations of the symmetric cipher (once per recipient in ECIES, plus once for the message itself)?
If the total length of my session keys is the same as the length  of my $KDF()$ output, then can I get rid of the symmetric cipher $E(k_E;m)$ used within ECIES entirely, and replace it with $k_E \oplus m$? That would obviously render question 3 irrelevant.

I think the answer is "yes to all", but some of these look potentially subtle. Thanks!

When I do ECIES, can I omit the MAC $d$? An attacker doesn't gain
  anything by tampering with the session key, since that just causes the
  inner decryption or MAC check to fail.

I wouldn't rely on that property. Please don't do this.

  Can I use the same ephemeral EC pair $R=rG$ for all recipients?

Yes, you can do this. NaCl in principle does the same thing, but uses your own (static) private key for the key-agreement, while you make the $r$ temporarily your private key (for this message).

  Can I use the same IV for all invocations of the symmetric cipher
  (once per recipient in ECIES, plus once for the message itself)?

Yes you can do this, guaranteed that you always have distinct keys. The DH-style key agreements will guarentee the different symmetric keys for each recipient. The encapsulated symmetric message key will also be distinct so it's safe to re-use IVs here. An alternative suggestion would be to re-use the IV, but add some small value (like 0 for the actual message, 1 for the first recipient in the list, etc.) Generally you shouldn't re-use IVs if you're not sure whether all keys are unique.

  If the total length of my session keys is the same as the length of my
  $KDF()$ output, then can I get rid of the symmetric cipher $E(k_E;m)$ used
  within ECIES entirely, and replace it with $k_E\oplus m$?

I'm surprised you don't already do this. You can let your KDF generate a stream of key bytes (KDFs can output arbitrary length keys) and use them as stream cipher. This is an acknowledged variant of ECIES and is actually standardized and implemented for example in Crypto++ and BouncyCastle.


HMAC-SHA1 input size I know that the HMAC is a message authentication code that uses a cryptographic key in conjunction with a hash function (SHA1 , MD5, etc.). The HMAC output is 160 bits for HMAC-SHA160 and 256 bits for HMAC-SHA256 bits that can be truncated according to the intented application. My quesion is about input...

What is the maximum input size of HMAC-SHA160 and HMAC-SHA256 ?

Well, SHA-1 and SHA-256 are both limited to inputs of no more than $2^{64}-1$ bits; the HMAC architecture itself prepends a logical IPAD (which is 512 bits); hence both HMAC-SHA160 and HMAC-SHA256 are both limited to inputs of no more than $2^{64} - 513$ bits, which is about 2 exabytes.

I rather suspect that this is not a serious limitation to your application...

As for potential security weaknesses if you hash messages this large, I am unaware of anything significant.  Here is the most serious I can think of: if we assume HMAC-SHA160, and modify the first block of a $2^{55}$ block message (where each block is 512 bits), we might run into an internal hash collision (which would mean that the HMAC result wouldn't be affected); if the attacker asks us to HMAC $2^{53}$ such huge messages (all of which are the same except for the first block), then there is a good probability of having an internal collision somewhere (and this collision is detectable because the HMACs will be exactly the same); this collision would allow him to generate two other messages that will HMAC to the same value).

However, the amount of work this would take is huge (we're talking about HMACing a total of $2^{114}$ bytes of chosen text; that in itself is totally unrealistic).


Efficiency of chaining AES "groups" of blocks From ISO/IEC 23001-7:2012/Amd 1:2012 10.2.2 Creation of Initialization Vector (Informative)

  Decryption efficiency may be improved if subsequent initialization vectors use the value of the last cipher block at the end of the previous sample so that multiple samples may be decrypted as continuous chain.

The algorithm is AES-128-CBC.

My question is: Can this really be true?

My understanding of efficiency is decryption time. For each group of blocks where a new IV would be needed the only reduction in time would be the read time of the IV (assuming the last block is kept in memory to be used as IV). But this reduction would so small in comparison to the read+decryption time of the actual blocks that I wouldn't even mention it.

The size on the other hand would be reduced as many IVs are not needed. But this depends on how many blocks are in each sample.

Well, if you have hardware which you can give it a long ciphertext block, and say "decrypt this block in one shot", well, one could argue that reusing the last ciphertext block as the next IV might give some minimal amount of gain; you would concatinate all the ciphertexts in order, and ask for the hardware to decrypt the entire thing -- the result will be the plaintexts all concatinated.  On the other hand, even if you used independent IVs, you could concatinate the blocks as series of [IV, ciphertext blocks] vectors, and so you could still use your fancy hardware to decrypt it all in one shot.

However, arguing about minor efficiency gains misses a larger point -- it is known that generating IVs this way (or in any way where the next IV can be predicted by someone in the middle) can cause cryptographical weakness; that is, someone who can insert their own text can game the system to decrypt low entropy (that is, mostly guessable) texts.  In case you think this is an entirely theoretical attack, well, this is precisely how the Beast attack worked in SSL.

Now, I don't know where an attacker can plausibly inject chosen plaintext into the encryption stream; however it strikes me as likely enough to reject this rather minimal performance gain.


How to apply two consecutive Paillier encryptions? The plaintext space for Paillier encryption is $\mathbb{Z}_n$ and the ciphertext space is $\mathbb{Z}_{n^2}$. How can I apply two consecutive encryptions?

I mean, if $c$ is the ciphertext of $m$, how to encrypt $c$?

I do not know what would be the purpose of doing so, but there are two simple solutions:

The ciphertext $c\in\mathbb{Z}_{n^2}$ is $2\log_2(n)$-bit long, so you can simply interpret it as a pair $(c_0,c_1)$ of $\log_2(n)$-bit string, that can in turn be seen as elements of $\mathbb{Z}_n$. Then, you can encrypt each component $(c_0,c_1)$ using Paillier again.
There is a natural generalization of Paillier to longer plaintexts, the Damgård–Jurik cryptosystem. It allows to encrypt plaintexts from $\mathbb{Z}_{n^s}$, with a ciphertext in $\mathbb{Z}_{n^{s+1}}$, for any $s$ (Paillier is just the case $s=1$). Hence, you can directly encrypt $c\in\mathbb{Z}_{n^2}$ with the Damgård–Jurik scheme for $s=2$, and get a ciphertext in $\mathbb{Z}_{n^{3}}$. This approach gives a result more compact than the previous one ($3\log_2(n)$ bits in total, as opposed to $4\log_2(n)$ bits with the previous approach).


Does Keccak have an eTCR mode? On page 7 of NIST's views on SHA-3's security requirements and Evaluation of attacks, I see that, at least at this point, NIST planned on offering SHA-3 having eTCR security (defined on page 3):

  eTCR: Find $M$ and then for a randomly chosen $r$, find $M’$
  and $r’$ s.t. $H_r(M) = H_{r’}(M’), (r,M) ≠ (r’,M’)$ where
  $H_r$ is the randomized hash.

However, I never saw any subsequent references to the eTCR property for the SHA-3 candidates.

Does SHA-3 have an eTCR mode?

SHA-3 is conjectured to be collision-resistant, which is enough for $H(r \mathbin\| m)$ to be eTCR; if SHA-3 fell to a collision attack like MD5 and SHA-1 before it, it would nevertheless be surprising and remarkable and worthy of publication for SHA-3 to fall to a target collision attack as neither MD5 nor SHA-1 to my knowledge has, but one can only speculate about hypothetical developments past the failure of what is already only a conjecture.

The NIST-recommended ‘keyed hash’ function associated with SHA-3 is KMAC of NIST SP 800-185, of course.  If you're still not comfortable with that, the NIST-recommended randomized hash for collision-resilient signatures is RMX of NIST SP 800-106, which you could use with SHA-3 out of an abundance of paranoia, but I have never heard of anyone bothering to do that.


Symmetric vs non-symmetric pairing based crypto I am trying to find a comparison of how different pairing-friendly elliptic curves perform (in terms of security) in real world applications;

I am using PBC library, and it has type A curves and type D curves (also , i am having hard time understanding how pairing types depend on underlying curve types, and which of them have been broken/ or are considered insecure at the moment;

Type A

Type D

At first glance, there are 3 types of pairings, type 1(symmetric), type 2 (g1!=g2, g2->g1) and type 3; i understand that different algorithms require pairings to be either of type1 or type2 or type3;

I would also like to know more about why some algorithms are limited to certain pairing types.
Any references would be greatly welcome

This lecture by Dan Boneh should answer all your questions and more:

https://www.youtube.com/watch?v=F4x2kQTKYFY

ps. I saw you also had a question about NIZK proofs, so you should check out the full list of videos

https://www.youtube.com/playlist?list=PLXF_IJaFk-9C4p3b2tK7H9a9axOm3EtjA

which has almost 3 hours of lectures on Groth-Sahai proofs by Jens Groth which might interest you.


Is there a SHA-256 value which hashes to itself? Getting curious about SHA-256 cycles (what happens if you hash a value repeatedly), I came across this question:

Cycles in SHA256

The first answer suggests that using a 7-bit hash, it's possible to find a value that hashes to itself. See the red dot which isn't part of a loop but on its own:

I assume from the diagram, this means if I apply the 7-bit hashing function to this value, the output matches the input. So my question is if such values are possible in SHA-256, and if anyone knows what value(s) hash to themselves or has ever found one of those values.

This question here gives the probability of such a value, called a "fixed point" existing as 63% (based on assuming a "random" property of SHA256):

Cryptographic hash where the hashing function input is similar to the result

There is at least one such "fixed point" of the compression function that the SHA256 algorithm uses. An example is here:

Fixed point of the SHA-256 compression function

As explained in that answer, "[e]asy to find fixed-points are a known property of this construction", therefore this isn't a problem.


Does Linear Cramer-Shoup have pseudo-random ciphertexts? "Linear Cramer-Shoup" is defined on pages 4 and 5 of $\:$ eprint.iacr.org/2007/074.pdf .

Are the ciphertexts in Linear Cramer-Shoup computationally indistinguishable from uniform
under a chosen-ciphertext attack? $\:$ (We can assume without loss of generality either that

$M$ is the identity element or that $M$ is a a random element unknown to the adversary.)

This is not homework, and is relevant to a Zero Knowledge

Proof of Knowledge protocol I'm thinking about.

The security claim on page 5 of the Linear Cramer-Shoup paper is that their modified scheme is CCA secure, which is weaker than the IND-CCA2 security of the original DDH based Cramer-Shoup scheme. However, from the outline of the security proof, it seems the author actually means the LCS scheme is CCA2 secure.

Also note the first sentence on page 6:

"Clearly, if $A$ has a different advantage in guessing the bit $b$ when $B$ is run with a Linear tuple $(g_1,g_2,g_3,g_1^{r_1},g_2^{r_2},g_3^{r_1+r_2})$ and when $B$ is run with a random tuple $(g_1,g_2,g_3,g_1^{r_1},g_2^{r_2},\eta)$, we obtain a distinguisher for the Linear problem."

The cipher text $(u_1,u_2,u_3,e,v)$ consists of the last three elements of such a linear tuple, plus a blinded message $e$ and a verifier $v$.

Since $u_1 = g_1^{r_1}$ and $u_2 = g_2^{r_2}$ and $r_1, r_2$ are selected at random, these two values are trivially indistinguishable from uniform, because they are uniform. Since $u_3 = g_3^{r_1 + r_2}$, this value is indistinguishable from uniform by the Linear assumption.

The blinded value $e$ is proven to be "independent of the view of the adversary", which I interpret as being indistinguishable from uniform. The proof is interesting. Basically, it is based on the following derived problem:

Given $(g^s,g^t,g^{sa},g^{tb},g^{a+b},g^{ad+be+cf})$ and any number of points on the "plane" $P(x,y) = g^{xd+ye+(x+y)f}$ except $P(a,b)$, output yes if $c = a + b$, no otherwise.

The uniformity of $v$ might be derived using the same technique. Set $g = g_3, g^z = g_1, g^w = g_2$. We then have:

$v^\prime = g^{r_1z(x_1+\alpha{y_1}) + r_2w(x_2+\alpha{y_2}) + r_3(x_3+\alpha{y_3})}$, where $v^\prime = v \iff r_3 = r_1 + r_2$.

Clearly, if $r_3$ is selected uniformly at random, $v^\prime$ is also uniform, so if you are unable to tell if $r_3 = r_1 + r_2$, you are unable to distinguish $v$ from uniform.


How to obtain 256-bit security from Ed25519? It is said that breaking Ed25519 has similar difficulty to breaking RSA with ~3000-bit keys" 1

When using RSA, I prefer 4096-bit keys, but I would like to use Ed25519.

If I wanted to double the security level - similar to RSA with ~6000 bits - what are my options?

Do we have to wait for a new standard to be published?

Could we easily hack libsodium/nacl in the mean time?

It is not possible to double security level of Ed25519 any trivial way. Instead, doubling security level requires using another curve that is approximately 512 bit curve.

In systems compliant with RFC 7748, i.e. some of IETF specifications, there is Curve448 curve (Ed448-goldilocks). It is almost twice as strong as Curve25519 (its strength is 224 bits). This is often convenient alternative, because it is already available on some of the systems.

Widely deployed alternatives that are 256-bit security: Of course there are also BrainpoolP512 and NIST P-521 curves, which in theory provide 256 bit security. However, BrainpoolP512 and NIST P-521 are not considered to be as good as Ed25519 in all aspects possible (see e.g. https://safecurves.cr.yp.to/).

M-511 and E-521 are curves similar to Curve25519, which offer around 256-bit security level. However, because it is wide spread to consider security level 128 - 192 sufficiently strong for now, so larger curves are not used often in practice. For instance, NSA suite B site suggests that they consider 192-bit security level (i.e. 384-bit elliptic curves) to be sufficient to protect TOP SECRET materials.

Any optimized curve specific implementation of elliptic curves, such as the implementation of Curve25519 in lib sodium/NaCL is hard to replace efficiently with curve of different size. However, the API level of lib sodium/NaCL allows easy replacement of cryptographic primitives. Therefore, the "right" way to "hack libsodium/NACL" would probably be to provide the necessary curve(s) implementation(s) in API that is compatible with NaCL API. This usually requires use of different implementation rather than tweak of code implementing Curve25519. And some API work to adapt the API, as most Elliptic Curve implementations have APIs somewhat different from API in libsodium/NaCL.


Definition of support in the context of an encryption scheme and usage of P = NP assumption in lemma 9.2 (Arora, Barak) EDIT: I've migrated the question by deleting the same question I asked on mathematics stackexchange.

2 questions: (1) I am confused about the definition of support used in the proof given in the textbook Computational Complexity: A Modern Approach lemma 9.2 by Arora and Barak (2) The usage of the assumption that $\boldsymbol{\mathbf{P}} = \boldsymbol{\mathbf{NP}}$

Lemma 9.2 states that

  if $\boldsymbol{\mathbf{P}} = \boldsymbol{\mathbf{NP}}$, then given
  any polynomial-time computable encryption scheme $(E, D)$ with key
  length $n$ shorter than the message length $m$ and where $E$ and $D$
  are each poly-time computable functions satisfying $D_k(E_k(x)) = x$
  for plaintext $x$, we can construct a polynomial-time algorithm $A$
  such that for every input length $m$ we can construct a pair of
  messages $x_0, x_1 \in \{0, 1\}^m$ satisfying that the algorithm $A$
  distinguishes any given encryption of either $x_0$ or $x_1$ with
  probability greater than $\frac{3}{4}$.

(1) In the proof, they write:

  Let $S \subseteq \{0, 1\}^*$ denote the support of $E_{U_n}(0^m)$

where $U_n$ is the uniform distribution on  $\{0, 1\}^n$ and then they state:

  Note that $y \in S$ if and only if $y = E_k(0^m)$; hence if
  $\boldsymbol{\mathbf{P}} = \boldsymbol{\mathbf{NP}}$
  then membership in $S$ can be efficiently verified.

But the definition of a support as I have known is that the support of a function is the smallest closed set of inputs where the function does not vanish. But $y$ is the output of the encryption function so how can it be in defined to be in the support of the function in the definition I'm using? How is the support defined properly in this case?

(2) My second confusion is on the statement

  Note that $y \in S$ if and only if $y = E_k(0^m)$; hence if
  $\boldsymbol{\mathbf{P}} = \boldsymbol{\mathbf{NP}}$ then membership
  in $S$ can be efficiently verified.

It seems that verification is efficient since in this case given a witness, a key $k$, one can encrypt $0^m$ with key $k$ and compare the output with $y$ and encryption is a poly-time computable function. Where does the assumption $\boldsymbol{\mathbf{P}} = \boldsymbol{\mathbf{NP}}$ come into play?

If you read the statements carefully, you see that $E_{U_n}(0^m)$ does not denote the encryption of $0^m$ with a specific key. It is function applied to a probability distribution - so $y$ is actually a probability distribution itself.

And this means, the word support fits to your understanding: It is the minimal set in the codomain (seeing $E$ as a function), where the probability is not 0 for any input from $U_n$ (side-note: the term closed doesn't really do anything for discrete or finite sets) - it is precisely the image of $E$ for this specific key length.

Another way to see this: The set $S$ is the image of the encryption function - for the specific parameters $m,n$.

Regarding this statement:

  Note that $y \in S$ if and only if $y = E_k(0^m)$; hence if
  $\boldsymbol{\mathbf{P}} = \boldsymbol{\mathbf{NP}}$
  then membership in $S$ can be efficiently verified.

This sentence might be missing something: It should state for claraification, that this is true for some key $k$ taken from $U_n$.

Regarding your 2nd question: For any $NP$ problem, verifying a witness if polynomial. But given some value in the codomain of $E$, you can't decide if it belongs to $S$ or not. However, if $P=NP$ you can find a witness in polynomial time. If for some potential witness exists, it is in $S$, and if no witness exists, it is not in $S$.


Reducing the output of AES to 64 bit Is it possible to reduce the output of AES after encryption into 64 bit with the possibility of a reversible before decryption Without any error

There is no way to reduce the output of a single AES encryption operation to 64 bits with the possibility of decryption without error.

There are however ways to use AES to build a 64-bit cryptogram that can be decrypted without error. The simplest is: encipher the constant zero with AES, keep the first 64 bits, XOR with the plaintext to get the cryptogram. Problem is, that's insecure if the AES key is used more than once.

There are ways to allow several uses with the same key:

If an initial IV setup is tolerable (e.g. the IV overhead negligible compared to many later 64-bit cryptograms delivered in order), CTR mode is fine, as noted by Thomas M. DuBuisson.
Construct a 64-bit symmetric Feistel cipher using AES encryption for the round function (AES-encipher the concatenation of the round number and 32-bit input); with 10 rounds for good measure, and perhaps using addition modulo $2^{32}$ rather than XOR for combination of the output of the round function (so that the cipher is not always an even permutation, which would be noticeable after $2^{64}-2$ plaintext/ciphertext pairs), that's a secure 64-bit block cipher. Beware however that with this method (or any 64-bit block cipher) alone, identical 64-bit plaintexts will be recognizable as identical 64-bit ciphertexts.
FFX mode is another possibility, as noted by CodesInChaos.


md5sum collision question I've been reading the wikipedia page, trying to get a better understanding of how to produce a collision.

http://en.wikipedia.org/wiki/MD5#Collision_vulnerabilities

The wikipedia page above states:
"two colliding files is a template file with a 128-byte block of data, aligned on a 64-byte boundary that can be changed freely"

What does 64-byte boundary mean, Does that mean I can't change byte 64 but I can change the other bytes in the 128-byte block of data?

Furthermore, how do I verify that two different files generates the same md5 without using a program, just by looking at the bits?  (This part is a homework question, if you guys can point me in the right direction, that would be great).

They mean that you send a message template to anybody you want to fool, say, a certificate request to a certificate authority. You make sure that the MD5 is calculated over N 64 byte blocks of data generated by the other party, and then the 128 byte block you pre-calculated.

Now you receive back the data generated by the other party, ending with your 128 byte block, aligned on 64 bytes. In our example that would be a certificate. Now you can simply replace all the data generated by the other party, recalculate your 128 byte block and get the same MD5.

The other party, for instance the certificate authority, could use the generated MD5 to generate an MD5 with RSA signature. As the signature only depends on the private key of the other party and the MD5, the signature would be valid for both the original and the "fake" certificate.


Is there a standard for public key encrypting and signing short messages? Some systems, that operate over flaky bearers, need to send signed, encrypted messages that are entirely self contained - i.e. send a single 300 byte UDP rather than have a 10Kb, two-way, certificate conversation over TCP.

Assume the destination has a private key and already knows the source's public key, and the source has a private key and already knows the destination's public key.

Given this assumption, is there a standard for encrypting/signing a small, but arbitrary length, message?

(I'm well aware of the dangers of rolling my own encryption scheme.)

Would there be a minimum ciphertext size that is related to the public key size?

(I'm thinking plain PKI encryption for plaintexts shorter than the key, and a PKI encrypted AES key for longer plaintexts.)

Would there be a minimum ciphertext size that is related to the public key size?

It depends on the algorithms used. An RSA signature, without any bells and whistles, is equal to the key length in size (i.e. 2048 bits for 2048-bit RSA). Likewise raw RSA encryption adds the same. So if you just use both, you add twice the key length, or 512 bytes for a 2048-bit key size.

Elliptic curves allow much more compact signatures and encryption. An 256-bit ECDSA signature is usually 512 bits. With NaCL, using Curve25519 and hybrid encryption, you can get authenticated encryption using only 40 bytes of extra space. That's what I would likely use with small messages.

If even elliptic curve algorithms add too much, you could use symmetric algorithms, with an occasional session key exchanged using the public key system. If many messages are exchanged using, say, AES GCM your per message overhead is about nonce size + authentication tag size (e.g. 192 bits total). Even less if you can use some existing counter as the nonce.


Public Key Encryption with forward secrecy Is there a known non-trivial system with plausibly secure public key encryption where:

the time function is efficiently computable;
the [pubkey,privkey] pairs are generated with time(privkey) = 0;
when encrypting under pubkey, the encryptor chooses a value of t in the appropriate range;
given privkey0 and t such that time(privkey0) < t and t is in the appropriate range, one can efficiently compute privkey1 such that time(privkey1) = t;
given privkey' generated from the original privkey by zero or more more applications of (4), and a message encrypted under pubkey with t = time(privkey'), one can efficiently decrypt the message;
given privkey' generated from the original privkey by one or more applications of 4, and a message encrypted under pubkey with t < time(privkey'), it is infeasible to learn anything about the message?

The trivial system is generating keys with privkey as 0 paired with a (randomly chosen) state for a forward-secure pseudo-random number generator, and pubkey as a list of public keys for an ordinary PKE system generated using the pseudo-random output from the state.

The time function is taking the first entry in the pair. The range for t values is non-negative integers less than the number of (ordinary) public keys in the list. Encryption under pubkey is the pair of t together with (ordinary) encryption under the t'th (ordinary) public key in the list.

The step 4 updating is changing the first part of privkey to t and changing the state to what it was after generating the first t (ordinary) public keys.

The step 5 decryption is by using the known state to regenerate the (ordinary) private key for the t'th (ordinary) public key in the list, and using that private key to decrypt the second part of the encrypted message.

The problem with the trivial system is that the size of pubkey grows linearly with the desired size of the range for t values.

One approach can be found in this paper by Canetti, Halevi and Katz.  To summarize the approach:

This generate a tree of private keys; from a node, you can generate private keys downwards (to child nodes), but you cannot compute upwards (to the parent nodes).  This achieves forward secrecy by generating child nodes and erasing parent nodes.
The public key can be used to encrypt to any private key node; if we have the private key for that node (or we can generate it because we have one of its parents), we can decrypt the message; if the private key for that node has already been erased, we cannot.
The size of the public key is constant (that is, independent of the number of time steps supported).
The size of an encrypted message is $O(\log t)$ (where $t$ is the number of time steps supported).
The size of the private key for the entire system is $O(\log t)$; this includes the number of private keys nodes stored in memory at any one time.
Encryption and decryption both take $O(\log t)$ time.
The algorithm uses a bilinear mapping that meets the BDH (Bilinear Diffie-Hellman) assumption.


Is concatenated data hashed with scrypt vulunarable to a length extension attack? scrypt takes a salt, and a password plus some cost paramters to generate a key. So say we define it as this:

key = scrypt(password, salt, cost)

I am interested in using it for generating passwords deterministically. E.g. to create a password for amazon or apple I would so something like:

amazonpassword = base64(scrypt("username" + "masterpassword", "amazon", cost))
applepassword  = base64(scrypt("username" + "masterpassword", "apple", cost))

So I wonder if this is suspectable to a length extenson attack. E.g. if an attack found out what:

scrypt("masterpassword", "amazon", cost)

is, could they then use that as a basis for guessing what:

scrypt("username" + "masterpassword", "amazon", cost)

is? If so what is the best approach for avoiding this problem? Should I use a HMAC to generate the masterpassword string?

No, scrypt in not vulnerable to password extension attacks.

Internally, scrypt passes the password to PBKDF2, which uses it as a key for the HMAC function -- hence they've effectively already done the workaround you thought of.


How WhatsApp users authenticate themselves in end-to-end encryption? I read the WhatsApp Security Whitepaper and I want to know how a user A, which uses ECDH (Elliptic Curve Diffie-Hellman) to compute a master_secret, can be sure that the public keys for the recipient B used in the exchange belong to B and they have not been replaced by someone else.
A uses B (public) Identity Key, Signed Pre Key and One-Time Pre Key, all stored on the server at the moment of B's registration: how can A be sure that they are actually his recipient's keys?

(ECDH is an anonymous protocol, therefore authentication must be achieved someway else)

Basically the way WhatsApp and many other end-to-end encrypted messaging platforms work is that your device generates a public/private key pair. The public key is uploaded to the server and the private key is maintained. It is typically recommended that you do an "out-of-band" authentication of public keys with anyone you want to communicate with. This is often done by meeting in person. You can display your public key on your device, which they can see what public key they have for you (from the server) and compare. If you both see the same public key, all is well.

The reason and "out-of-band" mechanism is needed is that you cannot trust the WhatsApp channel for security yet, since security is being provided via the crypto. In theory, if you had some other trusted channel, you could use that. But if you already had a trusted channel, why use WhatsApp (or any other application)? This is why "in person" is typically the way this happens. You could do it over a phone call, or maybe even SMS, and feel sufficiently certain that correct public keys were exchanged. The beauty of how these apps work is that they allow you to decide that. That is also the disadvantage. If users don't fully understand the implications, they may be more risky than they would be otherwise.

This public/private key pair is used to sign partial ECDH key exchanges. You upload your half, signed by your private key to the server. The person who wants to communicate with you downloads one of the partial exchanges, verifies it with your public key. Completes the key exchange and uses the resulting key to encrypt the contents of the message. They then upload the other half of the key exchange, signed with their public key, and the encrypted message. Finally, you download all that info and are on your way.


Why can an arbitrary compression function mapping $\{0,1\}^{m+2^m} \rightarrow \{0,1\}^m$ not seriously be considered collision resistant? I recently got a question that I’ld like to share here, since answers might be useful (or at least interesting) for people diving into Merkle-Damgård hash constructions for the first time.

We know that the Merkle-Damgård hash function is based on a fixed size $\{0,1\}^{m+t} \rightarrow \{0,1\}^m$ compression function.

Why can an arbitrary compression function mapping $\{0,1\}^{m+2^m} \rightarrow \{0,1\}^m$ not seriously be considered collision resistant?

There are two cases. In the first case, $m$ is very small, and in such a case you can find collisions by the birthday paradox. In the second case, $m$ is not very small, and $2^m$ is too large to be considered feasible. This argument is obvious in the concrete setting (consider $m=64$; this is ridiculously small and collisions can be found in just $2^{32}$ time, but a message of $2^{64}$ size is not feasible).

Asymptotically, the same argument can be made. In order for the function to be collision resistant, you must have $m=\omega(\log n)$, where $n$ is the security parameter.  This is necessary since otherwise $\sqrt{2^m} = \sqrt{n}$ which is very small (in particular, it's polynomial). Otherwise, just to be concrete, consider $m=\log n\log\log n$. In this case $2^m = 2^{\log n\log\log n} = n^{\log n}$, which is not polynomial. However, this means that it's not possible to run the function with an input of length $2^m$.


Stream ciphers based on discrete logs Blum Blum Shub is a stream cipher that is provably reducible to the difficulty of factoring integers.

I'm wondering whether there is a similar construction for discrete logs?

For example, I could imagine having something like this being the update function for the internal state:

$x_{i+1} = g^{x_i} \mod p$

And then you just XOR the least significant byte with the plain-text.

Does anyone know of analysis of these type of constructions?

The Blum-Blum-Schub construction is a PRNG rather than a stream-cipher. (A stream cipher differs from a PRNG in that it provides for a loading mechanism for the key and an IV.)

There is a similar proposal for a PRNG based on the hardness of computing discrete logarithms by Blum and Micali (How to Generate Cryptographically Strong Sequences of Pseudorandom Bits, 1984). The extraction from the internal state $x_i$ consists in a bit the value reflecting the outcome of the test $[x_i < {p-1\over 2}]$.

Please note that the construction you propose cannot be proven secure with the standard methodology in that the lowest significant bit of $x$ can always be determined given the value of $g^x\mod p$, so that it cannot be proven to be a hard-core bit for the corresponding one-way function — and even less so the simultaneous bits forming the least significant byte(s).

Gennaro (2000) proposes to extract a number of low significant bits from the state (starting from the second).

Now many authors proposed an analysis of the concrete security of this (or similar schemes), and of course, you can always take "another look" at it.


Hash functions throughput performance Without taking into account security, which hash function is the fastest one among the following:

MD5, SHA-1, SHA-2 (for various internal size), Keccak, and other… ?

The performance of the hash depends on the environment it is used in.

Keccak excels in ASIC type hardware designs, whereas Blake and Skein excel in x86 and x86-64 environments.

MD5 is still quite fast in software, but newer algorithms take advantage of SIMD instructions on newer processors.

There is also the question of performance on a per invocation basis or on a per byte basis for larger messages. Keccak also has different speeds that depend on the security level (and message size).

SHA512 operates on a maximum message size of 885 bits before more than 1 invocation of the hash is required to process it, whereas SHA256 has a maximum size of 447 bits. That means a hash of a 128-bit message will be faster on SHA256, but a hash on a 128MB message may be quite faster with SHA512. SHA512 is about 50% faster on larger messages, but can be half as fast on small ones. This type of performance will vary with CPU type.

Performance comparisons with multiple message sizes and CPU types can be found here: http://bench.cr.yp.to/results-sha3.html


Performance consideration in XEdDSA and VXEdDSA Signature Schemes Can someone please explain the below paragraph from section 7 in The XEdDSA and VXEdDSA Signature Schemes?

The below para states that we are hashing twice (I am not able to get that). How pre-hashing will help in this case.

  Pre-hashing: Except for XEdDSA verification, the signing and
  verification algorithms hash the input message twice. For large
  messages this could be expensive, and would require either large
  buffers or more complicated APIs.

  To prevent this, APIs may wish to specify a maximum message size that
  all implementations must be capable of buffering. Protocol designers
  can specify "pre-hashing" of message fields to fit within this.
  Designers are encouraged to use pre-hashing selectively, so as to
  limit the potential impact from collision attacks (e.g. pre-hashing
  the attachments to a message but not the message header or body).

Note the following three lines in XEdDSA:
$\newcommand{\opn}{\operatorname}$

  $r=\opn{hash}(a\parallel M\parallel Z)\bmod q$
  $R=rB$
  $h=\opn{hash}(R\parallel A\parallel M)\bmod q$

As you can see, the hash input of the third instruction depends on the hash output of the first instruction. And even worse you can't "just append" said output, it ahs to come first.

Now assume that you have a large message (like one gigabyte in size). While you could stream-process the first hash easily, you would have to buffer the full message so that you can feed it into the second hash invocation, requiring you to either a) have a stupid large statically-allocated buffer or b) significantly limit message size or c) use dynamic allocation (which is really slow).

So how can we fix this? Pre-Hashing. Assume that the "$M$" for the signing algorithm isn't actually the 1GB M, but rather the fixed-size $\opn{hash}(M)$. Now we can use a small, constant-sized buffer to store the "$M$" and we can just stream-compute $\opn{hash}(M)$, meaning we don't need unnecessarily large buffers there either. However the obvious downside of doing pre-hashing is that a collision on the hash easily translates into a forgery attack on the signature scheme (as $\opn{hash}(M)$ and $\opn{hash}(M')$ have the same hash, they are essentially the same message for the signature algorithm even though $M\neq M'$).

I said "stream-process" here multiple times, so I'll give you a quick understanding what it means. In actual implementations of hash functions you usually find the following three functions:

hash_init(context*)
hash_update(context*,byte* data)
hash_final(context*,byte* digest)

So you normally initialize some context for the hash, then you update the context with data a few times and finally extract the hash value (the digest) out of the context. Most hash functions are designed to support this style of implementation and allow context to be a compile-time-sized structure so that if you get a stream of data, you can continually call hash_update and then discard the message part's buffer (if you have no further use for it, that is). So in this case, you end up with a small context structure, a small message-part buffer as opposed to one giant full-message-buffer.


How was the AES MixColumns matrix constructed? How was the constant matrix in AES MixColumns constructed?

\begin{bmatrix}
02 & 03 & 01 & 01 \\
01 & 02 & 03 & 01 \\
01 & 01 & 02 & 03 \\
03 & 01 & 01 & 02 \\
\end{bmatrix}

How can I construct in $GF(2^4)$ an invertible matrix for the MixColumns step?

Any full rank $n \times n$ circulant matrix $A$ with all entries nonzero generates an MDS code. The entries here were picked for efficient fast multiplication, as far as I can recall.

Do refer to the book suggested by @SEJPM for more.


What is the difference between known-plaintext attack and chosen-plaintext attack? I am very confused between the concept of known-plaintext attack and chosen-plaintext attack. It seems to me that these two are the same thing, but it definitely is not.

Can anyone explain to me how these two differ?

It's the difference between an active and a passive attacker:

Known plaintext attack: The attacker knows at least one sample of both the plaintext and the ciphertext. In most cases, this is recorded real communication. If the XOR cipher is used for example, this will reveal the key as plaintext xor ciphertext.
Chosen plaintext attack: The attacker can specify his own plaintext and encrypt or sign it. He can carefully craft it to learn characteristics about the algorithm. For example he can provide an empty text, a text which consists of one "a", two "aa", ... For example: if the Vigenère cipher is used, it is very easy to extract the key length and recover the key by repeating one letter.

So the second type of attack is a lot more powerful.


While encrypting what can happen between words From some time I am working with "pen and paper" encrypted text.
Keys are not known, algorithm is not known.

I managed to find simple algorithm and key that seems to be nearly perfect.
Nearly perfect means that using this algorithm and key I can decrypt part of the encryption into meaningful text (~10 consecutive letters that create words). The composition of the algorithm, the length of the decrypted text and the text itself are definitely not coincidence. It seems that something changes beetween sentence/list of words because the rest of the text cannot be decrypted using simply the same method/key.

What is used in cryptography that could make such outcome?

e.g. If I use simple cipher: Add A letter to decrypted text I would get

DECRYPTEDTEXT
AAAAAAAAAAAAA
EFDSZQUFEUFYU

but in order to make it harder I could add consecutive letters to consecutive words

DECRYPTEDTEXT
AAAAAAAAABBBB
EFDSZQUFEVGZV

another example would be encryption using Caesar:

DECRYPTEDTEXT
CAESARCAESARC
.............

but in order to make it more difficult I could add X as space, encrypt and then remove encrypted letter that corresponds to X from encryption string:

DECRYPTEDXTEXT
CAESARCAESARCA
it would then be changed to:
DECRYPTEDTEXT <- X removed
CAESARCAEARCA <- S removed - corresponds to X

Are there any known and used methods that happen every word or every sentence?

Keys are not known, algorithm is not known.

Wrong initial assumption. The only secret must be the key by Kerckhoffs's_principle.

  but in order to make it harder I could add consecutive letters to consecutive words

and

  another example would be encryption using Caesar...

This is not new, this is nearly 600 years old, it is commonly called Vigenère Cipher and it is super weak with nowadays assumption such as Chosen Plaintext Attacks.

  Are there any known and used methods that happen every word or every sentence?

Yes, for example Cipher Block Chaining. Note that sentences are not composed of words anymore but seen a bit-string that you are splitting into blocks (sort of words) of the same length.


Block Ciphers and (Non-)Generic Attacks I am currently reading through Cryptography Engineering and came across this definition of block cipher security:

  Definition 2 An attack on a block cipher is a non-generic method of
  distinguishing the block cipher from an ideal block cipher.

Reading further, I find myself struggling to understand what the authors mean by a "non-generic attack" (and, conversely, a "generic attack"), which may be explained by what they say near the end of the relevant section:

  That's why nobody has been able to formalise a definition of generic
  attacks and block cipher security.

Would anyone like a shot at attempting a definition of a generic attack and of a non-generic attack, particularly with respect to block ciphers?

As explained in a comment: A generic attack is one that works against all block-ciphers (with a given block and key size), without consideration about the structure of the block-cipher.

One generic attack for a block cipher of a given block size $b$ bits builds a dictionary of input/output pairs (e.g. from past plaintext/ciphertext), for a fixed key. When an input or output in that dictionary gets reused, the adversary gains an advantage. In many scenarios, that's expected after about $2^{b/2}$ blocks (less in ECB mode, more in CTR mode). Such attack works for any block cipher, including an hypothetical one implemented as a random permutation.

If we in addition consider the key size of $k$ bits, another generic attack, brute force key search, enumerates the keys. With at least $k/b+1$ input/output pairs, that's likely to find the key after about $2^{k-1}$ attempts.

Sometime we have a generic attack against a whole category of block ciphers sharing a common characteristic. For example, there's a generic attack against all Feistel ciphers, based on the fact that for any key, they implement an even permutation; this allows an adversary having built a dictionary of all input/output pairs except two of these, to deduce the remaining two with certainty. Another example (given in that answer) is an enhanced brute force key search removing most of the work associated to the first and/or last round in a Feistel cipher.


Is PBKDF2/RFC 2898 broken because SHA1 is broken? I was attempting to re-implement the ASP.NET Identity password hash algorithm in PHP. It uses RFC 2898, which uses HMAC SHA1. SHA1 has been broken by google. Does this mean that RFC 2898 in general and the current ASP.NET Identity password hash format in particular are broken?

That particular usage of SHA-1 uses HMAC, and then iterates that as part of PBKDF2 (which is actually defined for any PRF, not just HMAC-SHA1).

As of this date (2017-05-18) HMAC-SHA1 is unbroken in terms of collisions and other attacks, so PBKDF2-HMAC-SHA1 is still considered safe. The HMAC construction, along with the many iterations in PBKDF2, protects against the Google collision attack on SHA1.

However, new applications should move to at least SHA2-256 or SHA3-256 as a hashing primitive and not implement anything using SHA1 at all unless strictly necessary for compatibility with other systems.

In your case, you need compatibility with older systems, so go ahead, but build in code and make a transition plan to use newer hash function in the near future. Adding simple version field alongside the password hash will suffice in most cases.


Do ciphertexts leak information about their algorithmic creators? If an adversary holds thousands of encrypted files that were encrypted with the same cipher, can he determine which cipher method had been used on the files?
Assume that the adversary has no prior knowledge about the encryption environment.

Details:
Let's say I have a encryption program that allows me to select 1 out of 5 well established and well implemented encryption algorithms. I use that program to encrypt thousands of file, using always the same block cipher, while following proper cryptographic procedures (e.g. use different passwords every n files encrypted). The files are stored off-site, and an adversary gets a hold of the files. I wonder if by selecting a less common algorithm, e.g. Serpent, I would increase the workload of the adversary by factor of 5, or encryption algorithms do leak some information, some recurring properties, that will help the adversary to identify the encryption method I had used?

A good block cipher should be indistinguishable from a random permutation (otherwise it is considered broken). A consequence of this is that two good block ciphers are indistinguishable from each other (with at most a doubling of the adversary's advantage).

In your scenario, it means that finding a way to succeed in learning which algorithm has been used implies finding a cryptanalytic attack on at least one of the algorithms you are considering.

[Note that this answer disregard any implementation flaw in your program that would leak the algorithm being used.]


security in the standard model → random oracle model? Can a protocol proved secure in the standard model be considered secure in the random oracle model?

As correctly pointed out by Ricky Demer it is not necessarily true. However, this implication does not hold for very specific cases. In the case of random oracle gates the existence of the RO changes the functionality of the "scheme", since with RO there are RO-Gates and without there aren't.

In most cases the existence of the RO does not affect the functionality of the scheme, meaning that with and without RO you have the exact same functionality. In these cases this implication holds I think.
The ROM, in comparison to the standard model, provides you with an additional oracle that realizes a truly random function, i.e. a function where the input and output are absolutely unrelated.
If you have proven something secure in the standard model, then you didn't need this additional oracle. The exact same proof will so to speak also hold in the ROM but will not use the oracle.

Even though an adversary might use the RO too, I don't see how this would help him if it doesn't affect the functionality of the scheme, since in this case the scheme and the proof are completely unrelated to the RO.


How do you interpret the p-values from the Dieharder testsuite to evaluate an RNG? #=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
   rng_name    |rands/second|   Seed   |
stdin_input_raw|  3.91e+06  |3556676169|
#=============================================================================#
        test_name   |ntup| tsamples |psamples|  p-value |Assessment
#=============================================================================#
   diehard_birthdays|   0|       100|    1000|0.04228375|  PASSED
      diehard_operm5|   0|   1000000|    1000|0.19715383|  PASSED
  diehard_rank_32x32|   0|     40000|    1000|0.46351097|  PASSED
    diehard_rank_6x8|   0|    100000|    1000|0.95836167|  PASSED
   diehard_bitstream|   0|   2097152|    1000|0.48181370|  PASSED
        diehard_opso|   0|   2097152|    1000|0.30244550|  PASSED
        diehard_oqso|   0|   2097152|    1000|0.94656094|  PASSED
         diehard_dna|   0|   2097152|    1000|0.02404047|  PASSED
diehard_count_1s_str|   0|    256000|    1000|0.45401565|  PASSED
diehard_count_1s_byt|   0|    256000|    1000|0.48456168|  PASSED

Feeding a stream of random numbers to the Dieharder testsuite invokes a list of tests. Each test returns a p-value. As I understand it, the p-value tells you the chance that the stream really is just random noise (or not noise). But I've read that a good RNG will have a range of p-values that follows a uniform distribution; values between 0 and 1 should happen with about equal probability. Why should that be so? Why is a uniform distribution desirable here, what does it mean, and how can you measure the "uniformity" of a distribution?

I've read that a good RNG will have a range of p-values that follows a uniform distribution; values between 0 and 1 should happen with about equal probability. Why should that be so?

It comes straight from the definition of p-values. The p-value indicates the probability you'd get at least that skewed a result if the source is truly random.

So you expect a p-value $\le 0.05$ 5% of the time. You expect a p-value $\le 0.10$ 10% of the time. Thus, you expect a p-value in the interval $[0.05, 0.10]$ 5% of the time. Similarly for any other intervals between zero and one.

Of course, a uniform distribution will not produce an equal number of results in each range, so you will always get a randomly skewed distribution of p-values as well. In practice, you can probably just rely on dieharder to tell you you've passed the tests... keeping in mind that it does not prove you have a good (cryptographic) random number generator.


How to detect what crypto-method is used by Filecoder.Q? I have 2 different images, one original, and one locked by a malware detected by eset as "Win32/Filecoder.Q".

How to detect the encryption method that is used and the key, that is not using any public key/rsa/rc4 algorithm. There is diff:

If needed I can attached files (locked and original).

Filecoder.Q ransomware used one of three encryption algorithms: XOR ,Tiny Encryption Algorithm(TEA) and AES,but this ransomware does not encrypt beginning of the files so in your picture beginning of original and locked file are equal.if this ransomware uses XOR Algorithm then you can decrypt locked file with XORing original file and locked file(key Extraction) else if it uses TEA Algorithm then decryption of file is hard(but possible),but decryption of file when it uses AES is impossible.


Understanding the "cube-root math" behind an RSA signature forgery I'm trying to understand the math outlined in this paper on a RSA signature forgery attack. I understand it except for one aspect of how the cube root (that makes the forged signature) is computed.

On page 8, it's shown that this expression (the forged block that needs to be cube-rooted):
$\sqrt[3]{2^{3057} - N*2^{2072} + G}$

is supposed to be equivalent this one after its simplified:
$2^{1019} - (N * 2^{34}/3)$

It's not clear to me how the $2^{34}$ was determined in the second expression. It looks like everything's being divided by 3, but since the exponent $2072$ doesn't divide perfectly by 3, something was done to it. Can anyone explain?


RSA signature send signature with encrypted message? What is the correct procedure in sending an authenticated message, I've been researching and have been getting different answers, such as hash-then-sign [1], [2]
, sign-then-encrypt [3] (but the link wasn't specific for RSA).

Do I send the hash-then-sign (with something like RSA-PSS PKCS#1) and attach it to the message or encrypted message?
Do I use sign-then-encrypt, I tried searching "sign then encrypt rsa", with no result on the scheme used, what cryptographic scheme would I use? Would I just use RSA-sign and RSA-encrypt?
Do I combine them and use hash-then-sign-then-encrypt and just send it as one, is there a cryptographic scheme for this?

The archetypal mistake would be to send in clear the signature of (the hash of) the message itself, for it would allow to check a guess of the message.

This leaves us with (at least) two general safe sketches (the first having advantages including allowing earlier elimination of bogus messages on the receiver side)

encrypt, then sign the whole encrypted message;
sign, then encrypt the whole signed message.

In both cases

encrypt can be: draw a random key, then apply encryption padding, then apply the RSA exponentiation with a receiver's trusted public key, then append to that cryptogram the encryption of the input with a symmetric cryptosystem using said random key;
sign can be: hash he input, then apply a signature padding, then apply the RSA exponentiation with a sender's private key, then append that signature to the input.


Parallel variant of Carter-Wegman MAC with incremental property Is there any variant of the Carter-Wegman MAC algorithm that is fast, parallel and has the property of incremental crypto?

How about GMAC?  It's a Carter-Wegman MAC that meets the requirements of being fast to compute, and parallelizable.

In addition, it can be securely updated, that is, given a long message, you can compute the MAC of a modified version of that message faster than recomputing the entire MAC. For example, suppose you have a message/nonce/tag triple of $(N, M, T)$, and you want to change block $i$ of the message $M$ from the value $a$ to the value $b$ (where $i$ counts backwards; $i=0$ is the last block, $i=1$ is the next to last block).  To do that, you create a fresh (never used before) nonce $N'$, and compute:

$T' = T \oplus (H^{i+2} \times (a \oplus b)) \oplus AES_k(Pad(N)) \oplus AES_k(Pad(N'))$

With the result being the triple $(N', M', T')$, where:

$k$ and $H$ are the key and secret values within GMAC
$\times$ and $H^{i+2}$ are computed within $GF(2^{128})$
$\oplus$ is exclusive or (which is addition within $GF(2^{128})$)
$i+2$ is computed with normal addition (not $GF(2^{128})$ addition).
$AES_k(X)$ is the AES block encryption (ECB mode) of the 128 bit block $X$
$Pad$ converts the nonce into a 128 bit value (for 96 bit nonces, this is just postpending 4 0x00 bytes; for other sizes, it's more complicated).

This takes $O(\log(i))$ time (and can be done faster if you precompute $H^x$ of various values of $x$), which I believe meets the incremental requirement.


RSA algorithm: Must $e$ be less than $\varphi(N)$? I understand why $e$ must be co-prime to the totient of $N$, but I see in many explanations of RSA that $e$ should be less than $\varphi(N)$. Is there a reason for this? Is it for ease of a small number or is there some law in play here?

First, the Euler's theorem

if $n$ and $a$ are coprime positive integers then
$$a^{\varphi(n)} \equiv 1 \pmod n$$ where $\varphi(n)$ is Euler's totient function.

Take $e> \varphi(n)$. Then, there exists $e' < \varphi(n)$ such that: $$e \equiv e' \pmod {\varphi(n)}$$
Then, we can write $$e = e' + k \cdot \varphi(n).$$
This $e'$ is the smaller representation of $e$ that does the same job.
$$a^{e} \equiv  a^{e' + k \cdot \varphi(n)} \equiv a^{e'} a^{k \cdot \varphi(n)}  \equiv   a^{e'} (a^{\varphi(n)})^k  \equiv a^{e'} (1)^k  \equiv a^{e'} \pmod n$$ Therefore, there is no need for $e > \varphi(n)$.
We choose $e$ small so that the encryption can take a small amount. This is what we can control. We don't want the private exponent $d$ small, since it is insecure. If we take a random $e$, then we will not have the benefit.
Commonly used $e$'s are $\{3, 5, 17, 257\text{ or }65537\}$ and there is no danger even with $e=3$, as long as correct padding is used.
For encryption: Use Optimal Asymmetric Encryption Padding (OAEP) (RSA-OAEP) or RSA PKCS#1 v1.5 padding, the former is easier to implement, the later had many attacks due to improper implementations.
For signatures: Use Probabilistic Signature Scheme (PSS) and known as RSA-PSS.

Note 1: We first choose the $e$, then we choose the primes, not the reverse, since we may not get $\gcd(e,\varphi(n)) =1$  for all $n = p \cdot q$ is product of two distinct primes $p$ and $q$.
Note 2: We use Carmichael lambda $\lambda$ instead of $\varphi$, since it can produce smaller $d$s, since $\lambda(n)∣\varphi(n)$


When do clients use TLS in PSK mode? The TLS protocol can perform the handshake in different modes. Either fresh handshake where new keys are generated, or using Pre Shared Keys (PSK) or what was know as Session Resumption in previous versions.

My question is: In practice, when do clients such as web browsers for example use TLS in PSK mode? Does the existence of a website in the browser History entails the use of PSK mode? Can you list the cases where clients will use PSK instead of exchanging fresh keys?

Pre-shared keys aren't used on the web. Using asymmetric cryptography and a public-key infrastructure has huge advantages: there's no need to exchange long-term secrets at any point, all the security relies on a few public values (the root CA public keys). Commonly-used web browsers do not support PSK ciphersuites.

Pre-shared keys are meant for embedded clients that have very limited computing power, that only talk to a very small number of servers. Symmetric cryptography is significantly cheaper than asymmetric cryptography, so it's the only way to have secure communication with devices that simply can't perform a signature or signature verification in a reasonable time, or where it would consume a too big fraction of the battery reserved, or where there isn't enough room for the extra code. If a device only communicates to a very small number of peers over its lifetime, it only needs to store those peers' keys, so PKI wouldn't be an advantage on that side. What is saved on the client side has a cost on the server side: the server needs to store all the clients' secret keys and not just one private key.

Pre-shared keys may also be used if some key exchange or key distribution takes place using a protocol other than TLS, and then the exchanged symmetric key is used for TLS. I don't think this is very common though.

Browsers do use session resumption as a performance optimization. Session resumption is effectively equivalent to having a pre-shared key, but this key was shared through a previous TLS session. On the web, the original session always used asymmetric cryptography. Session resumption means that one or both sides of the communication store some confidential data from which the next session's key can be derived. Generally the burden is on the client: the server sends the client a ticket, which is some encrypted and signed data, and the client stores both this ticket and the shared secret for the next session (premaster secret in TLS terminology). To resume a session, the client sends the ticket back to the server, and the server verifies the signature and decrypts the ticket to obtain a copy of the premaster secret.

Saving a session in this way keeps the advantages of the public-key infrastructure. As in any communication system based on hybrid cryptography, the payload is protected using symmetric keys which are ultimately obtained using key establishment methods based on asymmetric cryptography. The client does have the burden of storing the secret key securely between sessions, but this burden is made easier because the client can fail safe and erase the session data whenever it wants: erasing session data is only a small loss of performance, unlike the PSK-only scenario where it means losing the ability to communicate.

Session resumption was added to TLS 1.0 as an afterthought. In TLS 1.3, the key exchange protocol has been revamped, and session resumption is now merged with pre-shared keys. The same principles apply: a web browser would only ever use PSK as a way to resume a session that was started with asymmetric cryptography, whereas tiny embedded systems may support nothing but PSK.