How to prove a function is pseudorandom function? I am currently enrolled in a cryptography course, which uses the book by Katz and Lindell.

I am using a function having $F_{k}$ = $A_{k}(B_{k}(r,m),r)$, the random number is generated using the Linear feedback shift register, A and B are the functions such that the output of B and a random number r is taken as input to A. I have the following doubts:

Is the above function using A and B a pseudorandom function as it is using LFSR to produce cipher text?
If the above function is pseudorandom then how to prove it mathematically?
Can any function which uses LFSR as the random number generator be considered CPA secure?

As it is, there is not enough information, in particular on functions A and B, to answer. However, here are elements that may help:

  Is the above function using A and B a pseudorandom function as it is using LFSR to produce cipher text?

As mentioned in the comments, even if the LFSR does outputs completely random numbers (which I doubt), there is no guarantee that F is pseudorandom. As far as we know, A and B could be deterministic functions, always outputting, say 42.

  If the above function is pseudorandom then how to prove it mathematically?

You would have to use a proof by reduction, such as one depicted in this video tutoral. That is, you do not prove directly that your function F is pseudo-random. Rather, you would prove, in your case, that IF the LFSR function (or function B maybe) is pseudo-random, THEN F is pseudo-random.

  Can any function which uses LFSR as the random number generator be considered CPA secure?

IND-CPA is a property for encryption. There is some relation between encryption and pseudo-randomness, but not as you seem to be saying. Generally, an encryption scheme need to use a good pseudo-random number generator (or a truly random number generator) when used in practice, but that does not take part in the cryptographic proof of IND-CPA. Thus, short answer here would be: no, even if LFSR is somehow truly random. You need other assumptions, and to study a particular, fully defined encryption scheme.

Hope this helps. It may be possible to answer more clearly if the functions $A$ and $B$ were defined.


Collisions in Diffie-Hellman private keys Given a generator $g$, a large, safe prime $P$ and a result of the DH key exchange $g^{xy} \mod P$, how would I come up with two different $x', y'$ s.t. $g^{x'y'} = g^{xy} \mod P$

In DHKE, Alice and Bob chooses random $x$ and $y$, $1 \leq x,y < n$, respectively.

For simplicity assume that $x$ is a product of two primes $x = r \cdot s$

Then set $ x' = r \neq x$ and $y' = s  \cdot y \neq x$ then $g^{x'y'} = g^{rsy}=g^{xy}$ will be another pair.

if $x$ and $y$ are primes then there are two cases $xy < \varphi(P)$ and $xy > \varphi(P)$ that will result in the same equation that need to be solved.

$$xy \equiv x' y' \mod \varphi{(P)}\;\;, 1 \leq x',y < n$$


How to determine the RSA Private key size from the Public.key file? Question: How to determine the RSA Private key size from the Public.key file? Just roughly, how big it could be?

$ ls -la Public.key
    -rw-r--r--. 1 user user 498 Sep  4 15:31 Public.key
    $

The Public.key was generated using the Java API (which defaults to the X509 SubjectPublicKeyInfo structure with embedded PKCS#1 public key in a BIT STRING).

Assumption: you've saved the RSA public key using the default encoding in Java (for the SUNRSA provider), as in:

KeyPairGenerator kgen = KeyPairGenerator.getInstance("RSA");
kgen.initialize(1024);
KeyPair kp = kgen.generateKeyPair();
Files.write(new File("Public.key").toPath(), kp.getPublic().getEncoded());

This generates an X.509 ASN.1 SubjectPublicKeyInfo structure encoded using DER.

In that case you can retrieve the information from the public key using the following OpenSSL command:

openssl rsa -pubin -inform DER -in Public.key -text -noout

This will show the following output:

Public-Key: (1024 bit)
Modulus:
    00:c3:7e:ea:ba:9d:55:81:ec:80:8b:68:fb:7b:80:
    14:d4:66:45:0e:ba:6e:45:98:23:dc:24:26:a4:30:
    0e:20:48:12:23:b3:8b:5e:ed:c2:a5:cf:5e:32:43:
    00:9b:61:6e:e7:a6:f4:01:55:e9:cc:a8:c7:29:24:
    fd:29:7b:a1:b9:4b:1c:4c:de:cc:f6:d0:7e:75:a6:
    5f:28:09:65:67:76:1c:e8:f5:ae:85:ad:4a:dc:48:
    ca:82:46:25:e1:17:f8:3b:0c:53:30:c4:bb:08:5a:
    75:43:8a:d3:26:97:35:a7:2f:61:c6:68:06:24:b3:
    c8:42:e1:53:40:39:95:46:c9
Exponent: 65537 (0x10001)

As you can see, the key size is in the first line of the output.


can you suggest any applicayion for implementing threshold homomorphic encryption cryptosystem(Paillier cryptosystem) I want to implement one project in multi party homomorphic encryption using paillier. Can you suggest any application for implementation.

How about this: an electronic voting scheme. Votes are cast onto a publicly readable but append-only bulletin board as encryptions under the system public (Paillier) key. Anyone can homomorphically compute the sum of the cast votes. The vote admins each hold a share in the secret key; they must cooperate in order to decrypt anything. In this way, as long as there is one honest administrator, he can ensure that only the correct ciphertext (the one corresponding to the sum of all votes and not the vote of any one individual) is decrypted.

Basically, this boils down to the CGS scheme (link) but for Paillier encryption. Furthermore, you will want to use zero-knowledge proofs tailored for Paillier threshold decryption and encryption; these are presented in the paper by Damgård and Jurik (link).

Another suggestion is this: multi-party computation for calculating not just the sum of some private inputs, but for calculating any function of the private inputs while keeping those inputs themselves hidden. The BeDOZa protocol (link) explicitly covers using Paillier encryption for the offline part (precomputation phase), even though all values in the online part (actual computation phase) are information-theoretically private.


Understanding the elliptic curve equation by example I'm trying to follow this tutorial and wonder how the author get the list of points in the elliptic curve. For example, why when you input x=1 you'll get y=7 in point (1,7) and (1,16)?

on intuitive level, I'll do:

x=1, 1^3+1+1 mod 23

= 3mod23 = 3 so why we get (1,7) & (1,16).

As fgrieu already mentioned, you forgot that the $y$ term in the elliptic curve equation is squared, so for $x= 1$ you have $y^2 = 1^3 + 1 + 1 = 3 \text{ mod } 23$. In order to solve the congruence $y^2 = n \text{ mod } p$ (where $p$ is a prime) you can use the following algorithm (Tonelli-Shanks):

Factor the powers of $2$ out of $p-1$, so in your case write $p-1 = 22 = Q2^S = 11 * 2^1$
Pick a value $z$ that is not a quadratic residue modulo $p$ i.e. there exists no $x$ such that $z = x^2 \text{ mod } p$. I picked $7$ at random and verified it's not a quadratic residue via Euler's criterion ($7^{\frac{23-1}{2}} = 22 = -1 \text{ mod } 23$)
Set the following values (all calculations done modulo $p$): $$M \gets S(=1)$$ $$c \gets z^Q(7^{11}=22)$$ $$t \gets n^Q(3^{11}=1)$$ $$R \gets n^{\frac{Q+1}{2}}(3^{\frac{11+1}{2}}=16)$$
This step involves looping until $t = 1$, which in our case is already true going into this step, so we have $y = R = 16$ as one of our solutions. The other solution can be found by computing $p - R = 23 - 16 = 7$.

Hence we have the two solutions $y = 16, y = 7$ when $x = 1$, yielding the points $(1, 16), (1, 7)$ as expected.


Background for modular arithmetic function I'm investigating this function:

$a := ((b\cdot c) \bmod k) - (b \cdot c)/k$

where $/$ indicates integer division.

Two things I've noticed:

It's equivalent to multiplying a·b, and then subtracting the high digits from the low digits (in a radix which divides k)
It's completely linear and can be inverted (that is, given a and b, determine c) in constant time.

Is there any background on this function? Does anyone discuss it, or similar functions? Does it belong to a known family? Does it have any known applications?

In short: Where can I look to find out more about it? I'm especially interested in applications for cryptography.

As discovered by D.W., this is in fact part of recommended IDEA implementation.  IDEA uses $a\cdot b \bmod (2^{16}+1)$, with a special case of handling $0$ as $2^{16}$.  From the Handbook of Applied Cryptography, note 7.016:

  Note (implementing $ab \bmod 2^{n}+1$) Multiplication $\bmod 2^{16}+1$ may be
  efficiently implemented as follows, for $0 \leq a, b \leq 2^{16}$ (cf. §14.3.4).
  Let $c = ab = c_0·2^{32} +c_H·2^{16} +c_L$, where $c_0 \in \{ 0, 1\}$ and
   $0 \leq c_L, c_H < 2^{16}$. To compute $c' = c \bmod (2^{16} + 1)$, first
  obtain $c_L$ and $c_H$ by standard multiplication. For $a = b = 2^{16}$, note
  that $c_0 = 1$, $c_L = c_H = 0$, and $c' = (−1)(−1) = 1$, since
  $2^{16} \equiv −1 \mod (2^{16}+1)$; otherwise, $c_0 = 0$. Consequently,
  $c' = c_L − c_H + c_0$ if $c_L \geq c_H$, while $c' = c_L − c_H + (2^{16} + 1)$ if
  $c_L < c_H$ (since then $−2^{16} < c_L − c_H < 0$).

Which is exactly consistent.

This of course leaves me with some greater questions, such as how IDEA is secure with only linear operations, and where I can read more about it (there's precious little deep discussion online), but those are for a different post.  One other interesting thing is that, unlike other ciphers with constant tables, it's not trivial to look at binary code and recognize IDEA.  You can scan for $2^{16}+1$, but that's not as certain as for instance finding the md5 table.


How to interpret the article claiming NIST P-256 curve to be unsafe? Here: http://safecurves.cr.yp.to/ , I read that the NIST P-256 elliptic-curve is not safe.

The article lists several aspects (off-curve point, side-channel, etc.) where implementing P256 can fail the security, how should we understand these?

I think this is valid for encrypting, but are these also valid for signing?

Quoting CodesInChaos:

  P256 is secure, it just lacks some nice-to-have features that make writing a fast and secure implementation easier.


Prove that a function is PRF? Let $F\colon K×K \rightarrow \{0,1\}^{128}$ be a $\mathit{PRF}$ function. Is $F'$ a $\mathit{PRF}$ ?

\begin{equation*}
 F'(x) =
  \begin{cases}
    0^{128}       & \quad \text{if $x = 0$} \\
    F_k(x)        & \quad \text{otherwise}
  \end{cases}
\end{equation*}

EDIT:
I know that a $\mathit{PRF}$ over $(K,X,Y)$ is a bijective function $F\colon K×K \rightarrow Y$ that satisfies the following properties:

Efficiency: $∀k ∈ K, x ∈ X, ∃ $ an algorithm to compute $F_k(x)$
Pseudorandomness: $∀$  $\mathit{PPT}$ $D$ algorithm, $∃$ a negligible function so that:
$|\Pr[D(r) = 1] - \Pr[D(F(.)) = 1]| < \mathit{negl}(n)$ where $r \leftarrow^R \mathrm{Func}(X,Y), k \leftarrow^RK$

You have listed two properties for something to be a PRF, efficiency and pseudorandomness.

The function $F'$ is clearly efficient as $F$ is efficient and $F'$ calls $F$ in just about every case. The one case where it doesn't is a very easily computable case too.

So, that leaves pseudorandomness. What that property is basically saying is imagine you are given a black box. You can feed it inputs (the x and k values) and see the outputs. If there exists a probabilistic polynomial time (PPT) algorithm that can, given the outputs, decide whether or not the black box implements $F'$ vs a random function, you do not have a PRF. On the other hand, if such a PPT algorithm does not exist, then you do have a PRF.

So, ultimately, the question is asking whether or not you can construct a PPT algorithm that can distinguish the outputs of $F'$ from outputs of a random function. If you can construct such an algorithm (fairly easy in this case), then you have proved that it is not a PRF.

Let's suppose, however, that the problem were setup differently and in fact $F'$ were a PRF. How would you prove that? You can't go through every possible PPT algorithm and show that it cannot distinguish outputs of $F'$ from outputs of a random function. Instead, you would assume that $F'$ is not a PRF and show how this would lead to a conclusion that $F$ is also not a PRF. In other words, a proof by contradiction.


Can TLS session resumption work after client dropped connection & reconnected to server? I'm developing a sensor node and investigating TLS/OpenSSL. The network the node runs behind could drop and reconnect a lot. The node has limited data plan so data overhead is the key where TLS handshake is a big contributor as I understand.

Can session resumption be used after each network drop & reconnection? Or full handshake is needed in this case?

A TLS session can be resumed once both sides know of the session. The exchange of the necessary information (i.e. session identifier or session ticket) is done within the initial handshake. This means a session can already be re-used within other connections once this initial handshake is done.

How long the session information are kept and if they are discarded if a connection is closed uncleanly depends on the specific implementation and is unrelated to the cryptography itself.


Two rounds of SHA-256 HMAC? In a project we are working on, we have two applications within our datacenter that exchange messages. The messages are protected by an HMAC, and the secret key is stored on a SafeNet device.

Update

This is not a hardware token - it is a hardened network storage device called "StorageSecure". The secret key is stored in a SafeNet "cryptainer" on the SafeNet appliance.

The secret key is retrieved by Application #1 from SafeNet to compute the HMAC on the messages that are exchanged with Application #2.  App #2 also has read access to the same SafeNet device, and retrieves the same secret to validate the HMAC of the messages received from App #1.

To protect the process against the SafeNet secret being compromised and the potential injection of a bogus message by a bad actor, I would like to investigate adding an additional “factor” in the process.  Would there be any benefit in adding a 2nd round of HMAC in the formula in both App #1 and App #2 using perhaps a static key value in code used for the key in a 2nd HMAC such as:

HMAC(HMAC(Message,SafeNetSecretKey),StaticKey)

Or would it be better to use the static key as a salt added to the message:

HMAC(Message+StaticKey,SafeNetSecretKey)

Update

Or since these messages are sent by App1 to App2 via web services, could we consider having App1 compute a nonce and use the nonce in the computation of  the HMAC such as HMAC(SafeNet_K1 || Nonce, Message) and pass the nonce to app2 in the body of the Https request?

Any advice is much appreciated!

First, you should always use HMAC with the secret data as the key and the (possibly) public data as the message. The proof of its security relies on that. So rather than concatenating the static key to the message, you might want to consider concatenating it to the secret key.

Second, the extra hash doesn't add any security. Anyone who knows the secret key would be able to calculate it just as easily as the HMAC alone. It is only a small layer of obfuscation – you are relying on the attacker not trying it.

So, denoting the "secret key" $k_1$ and the "shared key" $k_2$, there are at least three options:

$H_{k_2}(H_{k_1}(m))$, where you use the secret key first, then the shared.
$H_{k_1}(H_{k_2}(m))$, where you do the opposite.
$H_{k_1||k_2}(m)$, where the keys are concatenated.

The first two differ in the order you use the keys. The reason this matters is that an attacker knowing the inner key could use a collision search to attack the whole MAC. If the inner HMAC collides, the outer one does as well. This only matters if the HMAC hash lacks collision resistance, but collision resistance is not normally required so it is theoretically weaker than necessary even with something like SHA-256.

The last is the most frugal, since you only need one HMAC call. It should be secure even against an attacker who knows one of the keys. It is the one I would recommend.

The nonce idea does not add security, unless you can check its uniqueness, in which case you would avoid replay attacks. With random nonces you would need to store them all to check they are unique, or you could have App2 generate it and send it for App1 to use, adding latency. With an incrementing counter only the previous value needs to be stored (but you need to handle lost messages somehow).

In a replay attack an authenticated message without context information can be copied and sent by an attacker at a later time. Whether you need the nonce to avoid it depends on what information your messages contain and whether sending one of them again would amount to an attack.

If you do use a nonce, it should probably be concatenated with the message rather than the key, since a nonce is public information.


What values constitute failing for ENT tests? The dieharder tests give a clear PASSED, WEAK, etc and I'm wondering what those thresholds might be for the ent tests. While I'm sure a subjective and holistic reading of results is also helpful (especially for someone who knows a lot about RNGs and their tests), are there values that could be considered passing?

I know, for example, that the Monte Carlo Pi test should ideally be 3.143580574, but would a 4 be considered passing?

Edit: the question is better worded as failing the tests, rather than passing (see answer below).

Failing ENT output is a little like the length of string; elusive.  So I offer an anti-answer.  The following is the output from running the code below and shows a random sequence passing ENT.  You'll have to use some judement to weigh output diverging from this reference test.

The code executed for 1 MB, 10MB, 100MB, 1GB and 2GB random files using a decent cryptographic PRNG:-

public class SHA1 {

public static void main(String[] args) throws Exception {
    try (DataOutputStream dos = new DataOutputStream(
            new BufferedOutputStream(
                    new FileOutputStream(
                            new File("c:\\scratch\\SHA1-1GB.bin"))))) {
        SecureRandom sr = new SecureRandom(new byte[]{42});
        byte[] data = new byte[1_000_000];

        for (long i = 0; i < 1000; i++) {
            System.out.println(i);
            sr.nextBytes(data);
            dos.write(data);
        }
    }
}
}

C:\scratch>ent sha1-1mb.bin
Entropy = 7.999807 bits per byte.

Optimum compression would reduce the size
of this 1000000 byte file by 0 percent.

Chi square distribution for 1000000 samples is 268.02, and randomly
would exceed this value 27.54 percent of the times.

Arithmetic mean value of data bytes is 127.6351 (127.5 = random).
Monte Carlo value for Pi is 3.135252541 (error 0.20 percent).
Serial correlation coefficient is -0.001522 (totally uncorrelated = 0.0).

C:\scratch>ent sha1-10mb.bin
Entropy = 7.999982 bits per byte.

Optimum compression would reduce the size
of this 10000000 byte file by 0 percent.

Chi square distribution for 10000000 samples is 251.25, and randomly
would exceed this value 55.46 percent of the times.

Arithmetic mean value of data bytes is 127.5007 (127.5 = random).
Monte Carlo value for Pi is 3.140763656 (error 0.03 percent).
Serial correlation coefficient is 0.000043 (totally uncorrelated = 0.0).

C:\scratch>ent sha1-100mb.bin
Entropy = 7.999998 bits per byte.

Optimum compression would reduce the size
of this 100000000 byte file by 0 percent.

Chi square distribution for 100000000 samples is 241.51, and randomly
would exceed this value 71.86 percent of the times.

Arithmetic mean value of data bytes is 127.4998 (127.5 = random).
Monte Carlo value for Pi is 3.141108366 (error 0.02 percent).
Serial correlation coefficient is -0.000179 (totally uncorrelated = 0.0).

C:\scratch>ent sha1-1gb.bin
Entropy = 8.000000 bits per byte.

Optimum compression would reduce the size
of this 1000000000 byte file by 0 percent.

Chi square distribution for 1000000000 samples is 234.14, and randomly
would exceed this value 82.14 percent of the times.

Arithmetic mean value of data bytes is 127.5055 (127.5 = random).
Monte Carlo value for Pi is 3.141422821 (error 0.01 percent).
Serial correlation coefficient is 0.000024 (totally uncorrelated = 0.0).

C:\scratch>ent sha1-2gb.bin
Entropy = 8.000000 bits per byte.

Optimum compression would reduce the size
of this 2000000000 byte file by 0 percent.

Chi square distribution for 2000000000 samples is 231.40, and randomly
would exceed this value 85.30 percent of the times.

Arithmetic mean value of data bytes is 127.5032 (127.5 = random).
Monte Carlo value for Pi is 3.141451323 (error 0.00 percent).
Serial correlation coefficient is 0.000034 (totally uncorrelated = 0.0).

You will see both the pi approximation and chi squared values converging.  For another truly random sample (pi out to 2.5 trillion places), chi is 12 as all digits become fairly equally distributed.

(Apologies for the formatting spaghetti)


Is this Bleichenbacher '06 style signature forgery possible? (Or more like, why isn't it?) I assume that most of you know this, but just for the sake of context; Bleichenbacher's signature forgery (https://www.ietf.org/mail-archive/web/openpgp/current/msg00999.html) basically abuses implementations that do not check that the PKCS#1 1.5 padding of a decrypted signature is correctly layed out. Most vulnerable implementations accept cases where the embedded hash is not right-justified. With a reduced padding, the hash can be moved forward (more to the left) then the remaining bytes can be treated as "garbage", which in turn make enough room for organizing so that this number is a perfect cube. In case of public exponent 3, it means that the cuberoot of the latter number is a valid signature as seen by the wrong implementation. Actually what happens is that you're basically good with the rounded cube root of a number of your choice of the form (line29, https://github.com/akalin/cryptopals-python3/blob/master/challenge42.py), and cubing it only messes up the garbage digits/places anyway.

Now, I'm wondering about the case where an implementation does check that the hash is right-justified, but doesn't check the previous bytes at all. Assuming that we're still talking about exponent 3, someone could imagine that there might be a way to find a perfect cube that ends with that particular hash, thereby utilizing the more significant digits that are not checked by the code. On the other hand, the ending digits are already restricted just by the value being a cube number.
Let hashlen be the length of the hash in bits, and rsalen the much bigger length of the signature. Giving up on forging a signature for a particular hash, my intuition would tell me that if you take the last hashlen bits of the possible cube numbers for the signature (for which there are possibilities on the order of 2^1/3*rsalen*) then this set would have a non-negligible intersection/overlap with the possible hash values of size hashlen. Is it possible to sign some message feasibly by somehow utilizing the structure of the particular hash in context of these (hash, perfect cube) pairs?
Conversely, is there a quick and profound argument that shows that the outlined "signature checking" (looking at only the hash at the end) does not weaken the implementation?

Now, I'm wondering about the case where an implementation does check that the hash is right-justified, but doesn't check the previous bytes at all.

That case is completely broken for $e=3$

  Assuming that we're still talking about exponent 3, someone could imagine that there might be a way to find a perfect cube that ends with that particular hash, thereby utilizing the more significant digits that are not checked by the code.

That actually pretty easy, with the assumption that the lsbit of the hash is a 1 (or more generally, that the number of 0's at the end of the hash is a multiple of 3); this assumption is necessary, because if it is not true, no perfect cube will exist.  It turns out if this assumption is true, then a cube will always exist.

The most straight-forward approach to find it is to do it iteratively; if we have a value $x^3 = h \pmod{2^n}$, then we can easily find a value $y^3 = h \pmod {2^{n+1}}$, as either $y = x$ or $y = x + 2^n$, and it's easy to check which one it is.  So, we just start with a small $n$, and just repeatedly add bits to $x$ until, when cubed, it generates the entire hash in its $n$ least significant bits.

  Is it possible to sign some message feasibly by somehow utilizing the structure of the particular hash in context of these (hash, perfect cube) pairs?

The above procedure works for more than half of all possible messages (assuming the hash function acts as random), hence the attacker can easily pick a message that he likes.


Is it possible to get an RSA encryption key by comparing the unencrypted and encrypted file? Exactly what the title says. If I have a RSA encrypted file, and the exact same file but decrypted, can I tell the key that was used from that information?

No, if the RSA cryptosystem is secure, i.e. when it uses random padding such as PKCS#1 v1.5 padding or OAEP, then you cannot. As Stephen already mused, it is pretty likely that you can find out the key simply because it is included or can be derived; generally public keys are not meant to be secure.

If textbook (raw modular exponentiation) RSA is used then you can encrypt with the public key. If you get the same value then it is pretty likely that you've found the public key. But usually textbook RSA isn't used because it is insecure in several other ways as well. Ciphertext distinguishablity is just one of the problems.

Now some information can of course still be extracted from the ciphertext. First of all, the length of the RSA ciphertext is generally identical to the key size. So you can distinguish between keys of several lengths. Furthermore, if you find an RSA ciphertext that is higher than the modulus of the public key then that key is certainly not used to generate the ciphertext.

You explicitly asked for the encryption key which is the public key. If you meant the private decryption key then, no, the key cannot be derived except for the little amount of data also available for the public key.

Note that RSA is never directly used to encrypt files. Instead a hybrid cryptosystem needs to be used. The usual RSA schemes are not secure to encrypt data larger than the modulus minus the padding overhead. Furthermore, encrypting large amounts of data with RSA would be very CPU intensive and decrypting it would be worse.


How is McEliece chosen plaintext secure? Suppose a challenger creates a McEliece encryption system where there is a public key consisting of a matrix $G$ representing some linear code, and a number $t$ for the number of errors.

Then the adversary takes two messages $m_0$ and $m_1$ and uses the public key matrix $G$ to find $c_0=Gm_0$ and $c_1=Gm_1$. Then the adversary sends $m_0$ and $m_1$ to the challenger.

Then the challenger picks $b$ at random and creates $c=Gm_b+e$, and $e$ has at most $t$ errors. Then they send $c$ to the adversary. The adversary calculates:
$$e_0=c-c_0=Gm_b+e-Gm_0=G(m_b-m_0)+e$$
$$e_1=c-c_1=Gm_b+e-Gm_1=G(m_b-m_1)+e$$
Since $m_b$ is one of the two messages, then either $e_0=e$ or $e_1=e$. The adversary knows when this happens because $e$ has $t$ or fewer non-zero terms. Further, the other $e_i$ will consist of a non-zero codeword plus the error. Since the minimum distance of the code is greater than or equal to $2t+1$, then this codeword will have at least $2t+1$ non-zero terms; when $e$ is subtracted from this, there will be at least $t+1$ non-zero terms, so the adversary is sure that this was not the message. Hence, the adversary has a 100% chance of correctly guessing $b$.

Does this attack work? Is there some other aspect to the McEliece system that I don't know about that stops this attack?

Does this attack work?

Yes, it works.
However, "textbook" McEliece was never claimed to be IND-CPA.
In fact, it was already published in 2008 by Nojima et. al. in "Semantic Security for the McEliece Cryptosystem without Random Oracles" (PDF).

They also propose a mitigation in the paper, which is to simply front-pad the message with sufficiently many random bits and later simply ignore those bits at decryption.


Length extension attacks, Merkle–Damgård constructions, and HMACs The wikipedia page for Length Extension Attacks says "Note that since HMAC doesn't use [Merkle–Damgård constructions], HMAC hashes are not prone to length extension attacks."

However, HMACs can be constructed with hashing algorithms such as MD-5, SHA-1, and SHA-256 which use these constructions. I understand that HMACs are secure even when constructed from these hashing algorithms, but is it accurate to say that HMACs don't use Merkle–Damgård constructions? And if so, why not?

Your quote is wrong:

  The wikipedia page for Length Extension Attacks says "Note that since HMAC doesn't use [Merkle–Damgård constructions], HMAC hashes are not prone to length extension attacks."

The part that you've paraphrased in square brackets is a misreading of the original, which reads (my boldface):

  When a Merkle–Damgård based hash is misused as a message authentication code with construction $H(\mathrm{secret} ‖ \mathrm{message})$, and message and the length of secret is known, a length extension attack allows anyone to include extra information at the end of the message and produce a valid hash without knowing the secret. Note that since HMAC doesn't use this construction, HMAC hashes are not prone to length extension attacks.

The antecedent of "this construction" in the final sentence isn't the Merkle–Damgård construction, but rather the secret prefix MAC construction.


What if an attacker knows 1 bit of a OTP ciphertext I want to know the  answer for the question above, given that we encrypt a message that ends with a "0" and the encryption key is concatenated with a "0" to, in that case that case the cyphertext would also end with a zero, knowing that the attacker would know that the last bit of the key and the message is the same, would that cause a problem in case we're using a OTP to encrypt our messages?

No, this wouldn't cause problems.
The reason for this is the way how perfect secrecy is defined.
The definition says that a scheme is perfectly secret if an attacker doesn't learn anything new about the message when giving a cipher text, also see my other answer for a more "mathy" formulation.

So an attacker knows a certain bit is fixed, thus he can't ever learn anything new about it from the cipher text. And he also can't learn anything new about the rest of the message because only the corresponding key bit is fixed and the rest of the key stream is still uniformly and independently random and is thus still an OTP.


What is linearization attack I know that

  In cryptography, the linearization attack is a method of cryptanalysis
  for block ciphers

I am looking for an example of linearization attack couldn't find it online

Could anyone please explain it with an example?

A cryptosystem can be represented by multivariate equations and the analyzer tries to solve these equations efficiently in order to mount the algebraic attack. It is known that this is an NP-hard problem.

Linearization is a method for solving these where the degree of monomials is at most two. It first appears in Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization by Kipnis and Shamir. It is simply renaming the variables and solving the new system and then determining the real solutions to the original problem.

Linearization is well written in Bard's book

Given a quadratic system of $m$ equations in $n$ variables;

\begin{align*}
x_1 + x_2 x_3  &= 1\\
x_1 x_2 + x_1 x_3 + x_1
 & = 0\\
x_2 x_3 + x_2
 & = 0\\
x_1 x_2 + x_1 + x_3 + x_2
 & = 0\\
x_1 + x_1 x_2 + x_3
 & = 0\\
x_2 x_3 + x_1 + x_2 &=1
\end{align*}

we are renaming the total ${n \choose 2}$ quadratic monomials and $n$ linear monomials. With renaming (linearization);

\begin{align*}
x_1 &= y_1\\
x_2 &= y_2\\
 x_3 &= y_3\\
x_1 x_2 &= y_4\\
x_1 x_3 &= y_5\\
x_2 x_3 &=y_6
\end{align*}

we get a linear system;

\begin{align*}
y_1 + y_6 &= 1 \\
y_4 + y_5 + y_1 &= 0\\
y_6 + y_2 &= 0\\
y_4 + y_1 + y_3 + y_2 &= 0\\
y_1 + y_4 + y_3 &= 0\\
y_6 + y_1 + y_2 &= 1
\end{align*}

Now one can perfrom the Gaussian Elimination  to get;
\begin{align*}
y_1 & = 1\\
y_2 & = 0\\
y_3 & = y_5\\
y_4 & = y_5 + 1\\
y_5 & = \text{free}\\
y_6 & = 0\\
\end{align*}

This gives out two solutions  $(1, 0, 0, 1, 0, 0)$ and $(1, 0, 1, 0, 1, 0)$. One is valid and one is not (left to reader). This is due to the fact that linearization destroy information. Therefore;

The solution of the original system of equation is also the solution of its linearization but the reverse will be not correct.

What is the benefit of the linearization?

If one can given $m = (n^2+n)/2$ equations the linearization will yield a few candiate solutions.
if $m \approx n' \approx n^2/2$ then the system will have too much information that will yield numerous spurious solutions.


How to prove secret value in Pedersen commitment is equal to secret value in Fujisaki commitment? We have Pedersen commitment C to the secret value x, and Fujisake commitment C' to the secret value x. How can we make a zero-knowledge proof of equality for x value in the commitments?

This may look like a homework, so I would not present any complete "Ctrl-C Ctrl-V" -style solution.

A proof for equality of logarithms was introduced at Chaum, Evertse and van de Graaf paper, "An Improved Protocol for Demonstrating Possession of Discrete Logarithms and Some Generalizations", Eurocrypt 1987. At the core, Prover shows that the same single response would open both commitments.

According to http://kodu.ut.ee/~lipmaa/crypto/link/commitment/,
Fujisaki-Okamoto commitment scheme (spelling warning) is somewhat similar to Pedersen.
Major difference is operating with a group of an order hidden from Prover, which makes it acceptable to commit to integers (not only elements of a field of residue classes modulo prime group order).
This difference does not prevent from using the same response, as was stated.

Having said this, I would encourage to do it yourself.


What is the difference between RSASSA-PSS signing and RSA-PSS signing? I read the RFC 8017 and understood the pkcsv1.5 and pss padding techniques. I understood that in RSASSA-PSS signing scheme the signature will be appended at the end of M.

In some websites I read both RSASSA-PSS and RSA-PSS both are same, is it true? If not what is the fundamental difference between RSASSA-PSS and RSA-PSS, can you also please provide me the API's to sign and verify using  OpenSSL for RSASSA-PSS.

Thank You.

Some authors draw a distinction between:

RSA-PSS, analyzed by Bellare and Rogaway in 1996[1] and proposed for IEEE P1363 in 1998[2], which is roughly defined in terms of $H(r \mathbin\| m)$, and
RSASSA-PSS, standardized in IEEE P1363-2000 and RSA PKCS #1 v2.1, which is roughly defined in terms of $H(r \mathbin\| H(m))$.

This distinction is significant: RSA-PSS relies only on target collision resistance[3] (or universal one-way hash function…ness[4]) of $H$, while RSASSA-PSS relies on full collision resistance of $H$.

Another way to view it is that RSASSA-PSS—like RSASSA-PKCS1-v1_5 and any other signature scheme where the message figures in only via $H(m)$—is vulnerable to collisions in $H$.  This spells bad news when $H$ is MD5, as many people used in practice for many years.  Academic cryptographers publicly demonstrated certificate forgery using an MD5 collision attack on RSASSA-PKCS1-v1_5[5][6]; the United States and Israel forged a Microsoft software update signing certificate using an independently developed MD5 collision attack[7] to sabotage Iran's nuclear program.  But as far as anyone can tell, MD5's target collision resistance still holds up to this day, so RSA-PSS would have thwarted this entire avenue for certificate forgery even with MD5.

Why IEEE P1363-2000 and RSA PKCS #1 v2.1 standardized $H(r \mathbin\| H(m))$ instead of $H(r \mathbin\| m)$ is a mystery to me.  Coincidentally, this standardization happened around the same time that RSA, Inc., accepted a 10e6 USD bribe from the NSA to deploy Dual_EC_DRBG to all their RSA-BSAFE customers[8].

Modern signature schemes like Ed25519 use the design principle $H(r \mathbin\| m)$ in order to rely only on the weaker property target collision resistance like PSS or at least enhanced target collision resistance[9], and as such are advertised to have collision resilience.  (More on the history of these and related concepts in a previous answer.)


Probability of same input as output in AES 256 Note: I am assuming that, when entering in the key and plaintext, they are formatted in the same manner as the output of an AES-256 encrypted text.

What is the probability, if any, that you could enter in a key that ends up being the exact same as the output after AES-256 encryption?

and alternatively:

What is the probability, if any, that you could enter in a plaintext (pre-encryption message) that ends up being the exact same as the output after AES-256 encryption?

Normally you don't enter keys at all. Maybe you enter passwords which then get transformed into keys. The only time anyone normally enters keys is during testing and possibly during key management (e.g. backing up a key in multiple parts, printing it on paper).

Even if AES does output the same bytes as the key, it doesn't matter as long as the bytes are random; the attacker would never know about it. So the only reason to even worry about this is when you want to use AES to derive keys. The output of AES is a pseudo random permutation where each result is as likely as the other. AES has no "weak keys" where the output has special properties, so you cannot enter a weak key by mistake.

As already indicated, AES has an output of 128 bits, so it will never output 256 bits by itself. You'd need a mode of operation such as ECB, CBC or CTR to do so. The output of AES with a mode of operation depends on the protocol and mode of operation itself.

To derive keys you'd better use a Key Derivation Function (KDF) though. Password Based KDF's are used to turn passwords into keys. Well known ones are scrypt, bcrypt, PBKDF2. If you want to derive other keys from a master key, you can use a Key Based KDF such as HKDF. If you must use AES, use a counter mode KDF specified in NIST SP-800 108.

One of the good things about KDF's is that you can specify the output size to be 256 bits. There are other properties such as having a label, performing key stretching and optionally using a salt that make them much better than a plain hash or block cipher to derive keys.

Beware to never mix up text and binary. All modern cryptographic primitives operate on bytes. You need character-encoding (e.g. UTF-8) and possibly encoding (e.g. base 64) operations to convert between text and binary.


Help with linear approximation of DES(I don't understand some part of it ) I will make a presentation about Linear approximation (Matsui's paper 1993 Linear Cryptanalysis Method for DES Cipher ) of DES and I don't understand some parts of it.
Here my questions :

In the linear approximation of $S$ boxes we had lemma 1 and it says $NS(a,b)$  is even
I saw the topic about lemma 1 but I don't understand the explanation either :(

On the Same page as lemma 1 we have table 1. I understand the idea of the table and bias etc. but in the table, if we add the values in every row we get 0. I cannot understand the reason for it.

(I have an idea :For example when we add all rows for α=16 we have $$\mathtt{X4=8Y3\oplus8Y2\oplus8Y1\oplus8Y0}$$
and since we multiply with 8 to each bit in the right side we have 0 in the right side so probability of x4 being 0 is 1/2 therefore we had 0 bias)

For breaking 16 round DES we are using algorithm 2 but I cannot understand how we get 14 key bits?

We are saying the only nonlinear part of the DES is S boxes. By saying linear or nonlinear what we mean is like linearity in functions in mathematics?

In algorithm 2 we are applying algorithm for each key candidate. I understand the algorithm but ı don't understand how are we finding these candidate keys.If we are trying all possible candidates then this will make process very long.

And what advantages or disadvantages this nonlinearity give us?

Definition: $$NS_a(\alpha,\beta) = \# \{x| 0 \leq x < 64, (\oplus_{s=0}^{5}(x[s] \bullet \alpha[s])) = (\oplus_{t=0}^{3}(S_{a}(x)[t] \bullet \beta[t]))\}$$

Here, $x$ is your input to the S-box, and $S_a(x)$ is the output of the corresponding S-box. $\alpha$ and $\beta$ are the masks. Then, $NS_a(\alpha,\beta)$ is the number of coincidences that exor of input bits masked by $\alpha$ and exor of output bits masked by $\beta$. Take a look at the following example, where $\alpha = 16$ and $\beta = 15$, namely, $\alpha = 010000$ and $\beta = 1111$, and input is $x=011100$ where we consider fifth S-box: $$011100 \xrightarrow{\text{5'th S-box}} 1110$$
$$\oplus_{s=0}^{5}(x[s] \bullet \alpha[s]) = x[4] \bullet \alpha[4] = 1$$
since $\bullet$ is the bitwise 'and' operation, $x \bullet 0 = 0$ and $0 \oplus x = x$.
$$\oplus_{t=0}^{3}(S_{a}(x)[t] \bullet \beta[t]) = (S_{a}(x)[1] \bullet \beta[1])\oplus(S_{a}(x)[2] \bullet \beta[2])\oplus(S_{a}(x)[3] \bullet \beta[3]) = 1$$
Then, we increment $NS_a(16,15)$ by 1. If you repeat this for all possible inputs(i.e. $0 \leq x < 64$), $NS_a(16,15)$ turns out to be 12 indeed.
So, we keep $\alpha$ constant while we go through each 64 possible input. Since each input bit would be '1' 32 times, and '0' 32 times, this idea sums up to the fact we would always have 32 1's and 32 0's on the left hand side of the equation. Another way to convince, is just ordering the inputs in Gray code order, and omitting every non-masked bit, and since Gray codes toggle 1 bit at a time, our exor would change for each input, thus we would have 32-32 distribution on the left hand side of the equation. For the right hand side of the equation, the same holds, and we would have 32 zeros and 32 ones. Here, think S-boxes as boxes assigning 32 zeros and 32 ones on the left hand side to 32 zeros and 32 ones on the right hand side, and further assume all zeros are assigned to ones and all ones are assigned to zeros. Then, we slightly change our Sbox, to assign a zero to another zero, which is basically swapping 2 outputs of the Sbox, to align two zeros; which then would imply two ones are also assigned to each other. This is somehow a cumbersome way of explaining it, but when I studied Matsui's attack, I convinced myself this way.
In other words, we have 32 inputs with odd number of 1's and 32 with even number of 1's in it's binary representation.   , Then, we have 32 zeros, and 32 ones on the left hand side of the equation. Since for each S-box, there are

I think I have an intuitive way to see this, but I should have a look at my notes, I'll try to edit this section as soon as possible.

Actually, we get 7 key bits, then reverse the process, i.e. begin decrypting the ciphertext in the reverse order, with reordering round keys and using the same structure to obtain 7 more bits. Here, when we reverse the whole scheme, we obtain another best expression with different masks on plaintext and ciphertext for some specific expressions, -not all of them, as far as I know-, where we can express their characteristic by just changing plaintexts to ciphertexts and ciphertexts to plaintexts in the given linear approximation of DES. So, how to obtain 7 key bits? From algorithm 1, or any n-round expression Matsui gave for an n-round DES, we can obtain 1 bit of information directly. If we introduce (n-1)-round best expression to an n-round DES, as you probably noticed, we are left with an expression in terms of plaintext, ciphertext and $F(X,K)$. making use of the term $F(X,K)$, -note each round key is 48 bits, which is 6 key bits effecting an S-box-, we can recover these 6 key bits. Algorithm 2 is the algorithm for searching these 6 key bits. When you recover 7 bits using Algorithms 1 and 2, just reverse the order, and starting from the ciphertext, start decrypting, and apply the analysis algorithm again to recover another 7 bits.

I'm not a mathematician, so I'd rather not talk about "linearity/nonlinearity" in the sense of functions in mathematics, but keep in mind that the linearity of S-boxes add confusion, thus strenghtens it's security, while P-boxes add diffusion, which makes key bits and plaintext bits get in each other as fast and as well as possible.

Note: I'm not an experienced cryptographer, but I'm reading and studying these basic attacks nowadays, if I'm mistaken, I'm sorry.


Why are AES keys increments of 64-bits? Why are AES keys increments of 64-bits? Rijndael, which subsequently became AES, allowed key increments in 32-bits (128, 160, 192, 224, and 256 bits).  However, AES made it 128, 192, or 256.

My guess would be that a 64-bit default increment may be good to increase the lifetime of a particular key size for a particular application.  For example, assume that an application is using 128-bits and then the application owners feel they have to increase key size because of threats.  An increase to 192-bits (cf. 160-bits) may give this upgrade a longer life before technology advancement catches up and the application owners have to change again.  Is this speculation in the right direction?

When NIST made the call for AES, they were trying to address short comings of DES that had a 56-bit key (64-bits with parity).  I got the following information from NIST while at the NIST 8114 conferences because I was complaining about having to keep 192-bit key compatibility in my SIMON hardware when no one would likely use it.

The summary:

In 1997, the idea was to double the key length (to 128-bits) and then double the key length again (to 256-bits).  The reason that 192 bits was there was because it was thought that an intermediate key length would be good for systems that couldn't handle the complete 256-bit length.  You need to keep in mind that at the time of specifying 128/192/256 bits, and algorithm had not yet been picked.  On 1997 hardware, 192-bits takes more time than 256-bits, and it was hoped that by having a larger key size the life of AES would be more than 20-years, unlike DES.

As mentioned in the comments, retrospectively, the 192-bit requirement was likely not optimal as pretty much no one uses it.  You have to include a 192-bit key option in your hardware cores for complete AES compatibility.  I had a bug in my netlist verification for AES-192 for 10 years, and I only found it recently, which really means... no one every uses AES-192.


Why should one prefer Salsa20 over ChaCha? We are all aware of Google's approach to introduce ChaCha/Poly1305 as TLS cipher suite. The rationale seems clear: ChaCha is newer and seems to provide better security (and maybe speed?) gained from the experiences of the design of Salsa20.

But in his "recent" paper McBits: fast constant-time code-based cryptography (basically code-based ECIES) Bernstein (the inventor of Salsa20 and ChaCha), Chou and Schwabe used Salsa20 as standard primitive for McBits and not ChaCha.

So what are the reasons to prefer Salsa20 over ChaCha?

I agree that conservatism is the likely reason for the choice in McBits.

ChaCha was published while eSTREAM was still running. Salsa20/12 is now in the final eSTREAM portfolio. Even in the XSalsa paper on constructing a larger nonce, Bernstein makes no mention of ChaCha.

  So what are the reasons to prefer Salsa20 over ChaCha?

Wanting to use a standardized algorithm is one reason. Choosing the more exhaustively studied algorithm is another good one.

If you have your tinfoil hat on, you might also prefer to avoid any tweaks in the absence of real breaks. After all, tweaking the cipher would be an opportunity to introduce new back doors.


Multiple random keys vs multiple keys derived from master key If Alice is going to share a symmetric encryption key and a kmac key with Bob using asymmetric encryption (sign with static key, encrypt with ephemeral keys - an authenticated KEM), what are the advantages and/or disadvantages of sending 2 random keys (signed, encrypted assymetrically), compared to sending 1 master key (signed, encrypted assymetrically), where multiple keys can be derived from it using something like kmac or hkdf?

If we put algorithmic details aside, the two have little to no difference.

But in reality, public-key encryption and key exchange algorithms are limited in the length of data they can directly exchange. For example, the size of the key that can be exchanged with ECC is directly related to the base-2 logarithm of the order of the curve being used.

Next, if we do exchange over-sized symmetric key with, say, bigger curves, we may not necessarily be able to use the entropy present in the exchanged key - the security of the whole cryptosystem is limited to its weakest component. Therefore, encrypting with a 256-bit key then MAC'ing it with another 256-bit key give you only 256-bit security, not 512-bit.

To summarize: Exchanging over-sized key is neither necessarily viable nor necessarily useful. Do use HKDF for saving communication overhead.


Authenticated, Quantum-resistant GPG2? GPG2 does not provide authentication. It still uses SHA-1 by default. It does not seem to get any stronger as time goes by.
If one were to pass a randomly-generated symmetric key (from a TRNG) over the
entire encypted and signed GPG data block + HMAC of that GPG data block
would there be any advantage, by a computionally unbounded adversary, to forge a message because they know the underlying structure of the GPG message in detail? Let's say they have known plaintext. Will they be able to flip any bits without the receiver knowing?
So, the user employs GPG2 normally, let's say with RSA and then AES-256 and SHA-512 to encrypt and sign a message. Then the user burns some of the key pad material with the HMAC, using SHA-512.  The symmetric key is just as long as this concatenated block. The symmetric key material has already been shared in a secure manner, of course (an OTP).
Let's say the adversary knows the entire plaintext. Will they be able to flip any bits without the receiver knowing; that is, at better odds than what the security of the HMAC promises? I think not, but I would enjoy hearing an expert opinion.

GPG doesn't use post-quantum signatures, so any current implementation of GPG would be unable to provide such security; regardless of the hashing algorithm used.
However, let's assume we have post-quantum signatures in our GPG implementation:
If the hash is sufficiently large, and the hash itself is secure, an attacker not knowing the HMAC key would be unable to forge a message. The issue is, for a quantum computer to be unable to do this, the hash must be at least 512 bits long.
For quantum computers a 512-bit hash behaves (approximately) like a 256-bit hash does on classical computers; while the birthday paradox states that even on classical computers a 256-bit hash ensures only 128 bits of security.
Note: for those who care, a 512-bit hash would behave with slightly more security than a 256-bit hash would for classical computers; the bits of security is relative to the cube-root of $2^k$ (where $k$ is the hash's bit length), not the square-root of the square-root.
Also, the HMAC key must be able to provide (ideally) 128 bits of security, in order to not be compromised by any attack; this applies to classical computers, as well. That means, the HMAC key must act as a 256-bit key to not be broken. This means you should choose a secure password, if you use a password for the HMAC key... But you already knew that.
Once the HMAC key is broken, the security of the hash reverts to the security of the underlying hashing algorithm.
The security of a signature depends only partly on the hash. The rest is up to the signature algorithm; since a weak signature scheme would allow me to sign whatever I want, anyway.
But my real question is "why do you think HMAC is a good idea for a signature scheme?" Doing this would allow only the people with knowledge of the HMAC key to verify signatures; and as such, anyone able to verify messages would be able to forge messages the same as a normal signature scheme.
Another note: You only HMAC the already-signed message. As such, the ability to forge signatures is unaffected; since forging a signature doesn't require the attacker to change the signature, just to collide the signature, which will inevitably lead to the same HMAC as well under your scheme, effectively removing the HMAC's security from the question.


How can you derive a P-256 public key from the X and Y points Deriving a secp256k1 public key is also possible.  For whatever reason, I'm only being provided X and Y, not the public portion.

I just need to get the binary representation of the public key given that I am provided X and Y.

There are multiple ways of encoding a EC public key in binary as well.

Probably the most compatible one is a description of the generic SubjectPublicKeyInfo as used in X.509 certificates. The encoding scheme with the ASN.1 description can be found in RFC 5480. Now you "just" need an implementation for encoding / decoding such structures (using the ASN.1 distinguished encoding rules or DER).

Note that the most compatible public point encoding is the uncompressed point encoding, consisting of an identifer byte with value 04, followed by a statically sized (32 byte) encoding of the X coordinate as unsigned big integer, followed by the identically encoded Y coordinate.

Here is the encoding of a EC key:

SEQUENCE (2 elem)
  SEQUENCE (2 elem)
    OBJECT IDENTIFIER 1.2.840.10045.2.1 ecPublicKey (ANSI X9.62 public key type)
    OBJECT IDENTIFIER 1.2.840.10045.3.1.7 prime256v1 (ANSI X9.62 named elliptic curve)
  BIT STRING (520 bit) 0000010011011011100101100101010011000111100010000110001111111011011100…

Here is the hexadecimal encoding, with the X and Y coordinate shown:

30 59
    30 13
        06 07 2A 86 48 CE 3D 02 01
        06 08 2A 86 48 CE 3D 03 01 07
    03 42 00

        04

        DB 96 54 C7 88 63 FB 73 26 BD C8 2A A4 28 8F 3B
        B6 9C 96 4C B2 E1 8F 39 A4 3A 96 6F 87 2E 9C 79

        B1 F8 FB F7 84 A4 9C AF 10 17 92 4D F6 8E D7 43
        63 9F 9C 76 01 2C AC DE 86 72 7D 85 FD 23 F3 DF

As all the sizes are static, you should be able to simply create a statically sized, unsigned, big endian encoding of X and Y and place them after the header - which is anything before the X and the Y coordinates above, of course.

Possibly you may only require the encoding of the point, 04 with the X and Y coordinate following that as displayed above. That's a binary encoding as well, that can be used if the algorithm and curve is already known.

Beware that the statically encoded size of the points very much depends on the field size of the curve; this answer is therefore only valid for this particular curve.


How can one build $2^{c/2}$ attack on sponge hash? Let $H$ be a sponge hash with rate $r$ and capacity $c$, built from a permutation $\pi: \{0, 1\}^n \rightarrow \{0, 1\}^n$, where $n = r + c$.

Assuming $r \ge 2c$, how can I find a collision with probability at least $0.5$ in time $O(2^{c/2})$.
The colliding messages can be $2r$ bits each.

I'm pretty sure I have to use birthday paradox, but I still don't know how to apply it.

The hash function, by definition of rate, processes messages in $r$ bit long blocks. Generate about $2^{c/2}$ ($r$ bit) message blocks until you a pair of messages, say $m$ and $m'$ such that you get a collision in the $c$ bits associated with capacity. That is $T_c(\pi(iv \oplus (0^c \| m)) = T_c(\pi(iv \oplus (0^c \| m'))$ where $T_c$ is a function that truncates* the $n$ bit output of $\pi$ to $c$ bits, $iv$ is the internal state of the hash function prior to absorbing any message, $0^c$ is a string of c zero bits, and $\|$ is the concatenation operator.

The internal state of two instances of the hash function after one absorbs $m$ and the other $m'$ now have identical capacity bits, but $\pi(iv \oplus (0^c \| m)) \neq \pi(iv \oplus (0^c \| m'))$ because $m \neq m'$ and $\pi$ is a permutation. Select any value $m_2$ for the second message block for the first instance of the hash function. Then select $m_2'$ for the second block of the second hash such that $m_2 \oplus m_2' = \pi(iv \oplus (0^c \| m)) \oplus \pi(iv \oplus (0^c \| m'))$.

Prior to absorbing the second message block both instances have just their capacity bits identical. You select the second message block to cancel the remaining $r$ unequal bits before the second time $\pi$ gets applied. Since the inputs to $\pi$ are the same, so are the outputs. Now you have a full internal collision. For this reason, just requesting the output of the hash function at this point will yield an output collision. But a collision in a hash function's internal state is more powerful than just a collision between outputs. You can keep generating collisions by choosing a different $m_2$ or by extending the input to both hash functions with new identical message blocks.

The reason you (may) need $2r$ bits of input is so you can cancel the difference in the non-capacity part of the sponge's state. A sponge based hash can be defined such that the last step isn't necessary. Note that once you have a collision in the capacity bits it's trivial to choose the next message block values such that you have a collision.

The algorithm can be defined such that instead of remembering all $n$ bits of output from $\pi$ it only stores the capacity bits. This changes the algorithm. The outputs of two hash functions that differ only by this detail will be different, but the collision resistance of the two is the same.

It may be defined such that performs state updates as in $h_{i} = \pi(h_{i-1} \oplus (0^c \| m_i))$. Where $h$ is the $n$ bit state of the hash function, $m_i$ is the $i$th r-bit long message block, and $0^c \| m_i$ is n bits because $|0^c| + |m_i| = c + r = n$.

Or it could also be defined to do updates as in $h_i = T_c(\pi((h_{i-1} \| m_i))$. Where  $h_i$ is instead $c$ bits long.

Intuitively the difference is that the latter definition overwrites the new message block bits into the sponge state and the former XORs bits into the sponge state. Whether a sponge based hash function is defined one way or the other has no affect on its collision resistance.

TLDR: Just brute force the first message block such that the capacity bits match. Then just pick the second message block to cancel out the remaining r-bit difference.

* In this case discarding the last $r$ bits. I chose to assume in this answer that the hash function was defined such that the rate bits of the sponger were the last $r$ bits and the capacity bits were the first $c$ bits)


Can Shannon's proof be applied to all ciphers I have been studying Shannon's proof of Vernams (1917) unbreakable cipher. Can His proof be applied to positional ciphers?

Can his proof be applied to positional ciphers.

Shannon's proof requires that there be at least as many possible keys as possible plaintexts; unless your positional cipher has that property, then no, it cannot.

(I'm not sure what you're referring to as a 'position cipher' - would that be a transposition cipher?)


Inverse of an element in a RSA group Consider a RSA group $Z_N$ for $N=pq$, where $p,q$ are large prime numbers. Under strong RSA assumption, can an adversary efficiently compute the inverse of a random element $z$ from $Z_N$ without access to $p,q, \phi(N)$? Mathematically does there exists efficient algorithm $\mathcal{A}$ s.t

$$
\mathbb{P}\left( z.u=1,\quad z \leftarrow Z_N,\; u=\mathcal{A}(x,N) \right) \geq \text{neglible}?
$$

PS: I am learning cryptography so my notations are quite shaky.

Mathematically does there exists efficient algorithm $\mathcal{A}$

Yes; the Extended Euclidean algorithm can be used to efficiently compute multiplicative inverses modulo $N$, without knowledge of the factorization of $N$.


Determining if Server/Client's TLS configuration is Vulnerable to SLOTH In the context of SSL/TLS protocol and SLOTH vulnerability. I want to find out if certain websites(webservers) or applications that use TLS are vulnerable. I need some guidance for this.

My idea is to develop/find a tool(maybe openssl) that connects to the servers and in the client hello asks for RSA-MD5 SignatureAndHashAlgorithm to test if the server sends the corresponding certificate under this configuration and conclude that the server is vulnerable.

Likewise for the client certificates, I want to ask for client certificates signed by RSA-MD5 and if the client sends its certificates under this setup I'll conclude that the client is vulnerable to SLOTH.

First, is my approach right? or am I off the road?

Second, what types of tools do I need to use? Is openssl capable of producing such requests and responses?

It doesn't seem that openssl is capable of doing this itself, especially against servers that don't advertise RSA-MD5 support but will still accept it (e.g. OpenSSL pre-1.0.1e).
But see https://securitypitfalls.wordpress.com/2016/01/06/testing-for-sloth/ which appears to provide a handcrafted TLS1.2 client that will test for the broken behaviour.  I haven't tested it personally yet, but it looks like exactly the sort of tool that I was looking for to perform exactly the testing you describe.

Thus, to test properly if a server is vulnerable against this attack, we need a client that is misbehaving.
For easy writing of such test cases I have been working on the tlsfuzzer. Just released version of it was extended to be able test servers for vulnerability against the SLOTH attack (to be more precise, just the client impersonation attack – the most severe of the described ones).


Salsa20 / ChaCha with 128 bit keys According to wikipedia both Salsa20 and ChaCha support both 128 and 256-bit keys.

The initial state for each has 8 words of key, where each word is 32 bits. 32*8 = 256. My question is...  how is one supposed to expand a 128-bit key to fill in the 256-bits needed for the initial state?

The most obvious way would be to just append the 128-bit key to itself but in some ciphers, like RC2 or RC4 or Blowfish or the key goes through a key expansion step to expand the key to whatever size is ultimately needed - a key expansion step that doesn't simply append the orig key to itself.

As Luis Casillas said in his comment, the spec of Salsa is short and well explained. Namely, if you are interested in the expansion function, you can find a description with two examples (one with a 32-byte key, and one with a 16-byte key).

Short answer: when dealing with a 16-byte key, you only have to change a constant and append the key to itself.

More details bellow.

Salsa keystream generator, noted $Salsa20_k(n)$ for a key $k$ and a nonce $n$, is based on a hash function : $hSalsa20$ (called $Salsa20$ in the spec). This hash function works as follow :
if $x$ is a 64-byte sequence, $hSalsa20(x)$ is a 64-byte sequence.

Now, let's see the role of the key and how it is managed. Whether you're using a 32-byte key or a 16-byte key, there is no real key expansion as you can find in Blowfish. Instead, the key $k$ is divided in two 16-bytes subkeys $k_0$ and $k_1$ (if $k$ is 16 bytes long, $k_1 = k_0$). Then, a 16-byte constant is added to the state, and that's where there is a difference : the value is not the same depending on the key size:

for a 16-byte key, this constant is "expand 16-byte k"
for a 32-byte key, this constant is "expand 32-byte k"

This constant is divided into 4 equal part, let's call them $\sigma_0,\sigma_1,\sigma_2$ and $\sigma_3$, 4-byte each.

The keystream is produced as follow :
$$Salsa20_k(n) = hSalsa20(\sigma_0\ ||\ k_0\ ||\ \sigma_1\ ||\ n\ ||\ \sigma_2\ ||\ k_1 || \sigma_3)$$
 where $||$ denotes the concatenation.

Notice that in both case, the argument of $hSalsa20$ is 64-byte, so 64-byte of keystream is produced. You only have to increment the nonce, and start over to generate more keystream.


Yao's Millionaires' Problem without knowledge of plaintext I have two integers $x,y$ which are encrypted using a homomorphic cryptosystem, probably Paillier.
I am looking for a (one-party) protocol that, given $enc(x)$ and $enc(y)$, returns a bit $b = 1 \iff x \geq y$ (b plaintext) without knowledge of the private key.
I found several solutions for Yao's Millionaires' Problem, however most of them are for two parties and require that each party knows the plaintext value of their input.
Is this possible with the constraint that both integer values are positive and small ($0 \leq x,y \leq 1000$) and complexity is not the main issue?
Right now I have something like this: Create a set containing the numbers $0,1,2,...,1000$. For each entry $i$ calculate $(enc(x) - enc(y) - enc(i)) * r$ then shuffle the results and check if one entry equals zero. (Lets assume there is an algorithm available that answers "equals zero" requests).

What you are asking for is impossible, because it would immediately break the cryptosystem.

Let's assume for a moment, that such a function exists and we know how it works. And we get a challenge ciphertext $c = enc(x)$. We know the public key, because it's public. And if we assume the set of messages to be $0,1,\dots,1000$, we then just encrypt $500$ and then apply the function to get $x \geq 500$. If it is true, we apply the algorithm to $c$ and $enc(750)$ and otherwise to $c$ and $enc(250)$. This is just a binary search, and this way we can efficiently find out what $x$ is - without knowing the decryption key. And that would mean, there is no security at all.


The definition and origin of Schnorr groups? Wanting to write something on Schnorr groups in a publication I realised how hard it is to find anything citable about them on the internet. Who can help me with the following questions?

What (and where) is the actual definition of a Schnorr group? Are all of its criteria fulfilled if it is a multiplicative finite cyclic group with a prime order? In the answer to What is a cyclic group of prime order q such that the DLP is hard? it sounds like it is only a Schnorr Group if the $r$ in $p = qr + 1$ is $r>2$?
Where have Schnorr groups first been introduced and who called them Schnorr groups? I checked the references in Security of Schnorr signature versus DSA and DLP, but I could not find anything useful in Schnorr's patents and his papers start off directly with:

  The KAC chooses primes $p$ and $q$ such that $q \mid p - 1, q \le 2^{214}, p > 2^{512}$, $\alpha \in \mathbb{Z}_p$ with order $q$, i.e., $\alpha^q = 1 \pmod{p}$, $\alpha \neq 1$

So they already use Schnorr groups, but neither do they call them that nor do they give a procedure how to generate them. Which leads into my next question:
Where was a procedure to generate Schnorr groups first published? The Wikipedia article only gives a procedure without source, which is basically the same as in FIPS PUB 186-4, A.1 even though there it is not even called Schnorr group (proably due to patent reasons?).

UPDATE: Digging deeper I found this in PS96:

  results for other signature schemes like Schnorr's are considered as folklore results but have never appeared in the literature

"Folklore results"? Maybe that's why Schnorr groups are so difficult to grasp.

What (and where) is the actual definition of a Schnorr group?
  Where have Schnorr groups first been introduced and who called them Schnorr groups?

I don't know who first used the term—the earliest use I can dig up quickly is actually the Wikipedia article, initially drafted in November 2004 by Paul Crowley[1], who also used it a year earlier on sci.crypt[2].  What it means is a subgroup of prime order $q$ of the multiplicative group of the finite field $\mathbb Z/p\mathbb Z$, where $p$ is large enough (say 2048 bits) to resist index calculus on the field and $q$ is large enough (say 256 bits) to resist Pollard's $\rho$ or other generic discrete log attacks on the subgroup.

Cryptosystems defined in terms of Schnorr groups usually do not involve furnishing adversaries with oracles for $h \mapsto h^x$ for secret $x$, so minimizing $(p - 1)/q$ is not important as it is for, e.g., Diffie–Hellman; instead we make $q$ as small as we safely can to improve exponentiation performance.  So usually we don't consider the order-$q$ subgroup of $(\mathbb Z/p\mathbb Z)^\times$ with a safe prime $p = 2q + 1$ to be a Schnorr group.  But you wouldn't be disinvited from parties if you called it a trivial case of a Schnorr group with bad performance.

  Where was a procedure to generate Schnorr groups first published?

The generation procedure—randomly choose prime $q$ of appropriate size, randomly choose $k$ of appropriate size until $p := kq + 1$ is prime, and randomly choose $h$ until you find a generator $g := h^k \not\equiv 1 \pmod p$—is obvious enough that it's easy to imagine that nobody bothered to write it down in a paper to publish in an academic venue.

    results for other signature schemes like Schnorr's are considered as folklore results but have never appeared in the literature

What the ‘folklore’ comment means is that everyone tacitly felt they understood the result to be (perhaps intuitively or obviously) true, but nobody bothered to write a proof down or publish it, so there was nothing in the literature to formally cite.


How to prove the hardness of Rabin's function? I am unable to prove the following theorem:

  If for a $1/(\log(n))$ fraction of the quadratic residues $q\pmod n$ one could find a square root of $q$, then one could factor $n$ in random polynomial time.
  $n$ is the product of two large distinct primes.

Let $\mathcal A$ be the hypothetical algorithm in the question, with input $(n,q)$, output $r$, such that $r^2\equiv q\pmod n$ for a $1/(\log(n))$ fraction of the quadratic residues $q\pmod n$, running in random polynomial time w.r.t. $\log(n)$, restricting to $n$ product of two large distinct primes.

Let $\mathcal F$ be the following algorithm with input $n$ restricted as above, and output $d$:

select a random $s$ evenly distributed on $\{1\dots n-1\}$;
compute $q=s^2\bmod n$;
compute $r=\mathcal A(n,q)$; if algorithm $\mathcal A$ gives an indication of failure, loop at 1;
compute $d=\gcd(n,r+s)$ and if $d=1$ or $d=n$, loop at 1;
output $d$.

This factors $n$ because

Given that factors of $n$ are large, the proportion of $q$ that share a factor with $n$ is so low that they can't constitute a significant share of the $1/(\log(n))$ success rate of algorithm $\mathcal A$ over the whole set of $q$, thus the success rate of $\mathcal A$ is near $1/(\log(n))$ including for other $q$.
When step 2 of algorithm $\mathcal F$ invokes $\mathcal A$ with $q$ coprime with $n$ (that is on iterations with $s$ coprime with $n$, which are the vast majority), $q$ is evenly distributed over these other $q$, hence $\mathcal A$ will succeed with odds next to $1/(\log(n))$.
When $\mathcal A$ succeeds with $q$ coprime with $n$, and since $n$ has two factors, there are four square roots of $q$; since $s$ is random and was not an input of $\mathcal A$, which root $r$ was output by $\mathcal A$ is independent of which root $s$ is. For two out of these four possible $s$, thus with odds $1/2$, step 4 will compute a $d$ that is a nontrivial factor of $n$.

This proves that for $n$ as restricted of unknown factorization, inverting $r\to q=r^2\bmod n$ for random $r$ (or random $q$) is of hardness comparable to factorization of $n$.

Detailed proof with explicit bound on how large the factors of $n$ need be:

Let $p_1$ and $p_2$ be the two large (thus odd) distinct primes with $n=p_1p_2$. The $n-1$ possible values of $s$ can be split into two categories, which together form the whole set of quadratic residues $q$:

$p_1+p_2-1$ values with $\gcd(n,s)\ne1$, which generate $(p_1+p_2-2)/2$ quadratic residues $q$ with $\gcd(n,q)=1$,
$(p_1-1)(p_2-1)$ values with $\gcd(n,s)\ne1$, which generate $(p_1-1)(p_2-1)/4$ quadratic residues $q$ with $\gcd(n,q)\ne1$.

That gives us a total of $(p_1+1)(p_2+1)/4-1$ quadratic residues $q$. Algorithm $\mathcal A$ succeeds for at least an $1/(\log(n))$ fraction of this total, among which at least $((p_1+1)(p_2+1)/4-1)/\log n-(p_1+p_2-2)/2$ values of $q$ in the second category.
We can assume $\min(p_1,p_2)>4\log(n)$ (noticing that otherwise trial division would factor $n$ in polynomial time w.r.t. $\log(n)$ anyway). With that bound and even distribution of $s$, $\gcd(n,q)\ne1$ and $q$ is among those for which $\mathcal A$ succeeds for at least an $1/(2\log(n))$ fraction of $s$.
When this happens, we have $r^2\equiv q\equiv s^2\pmod n$, thus $(r-s)(r+s)\equiv0\pmod n$, thus $(r-s)(r+s)\equiv0\pmod{p_1}$ and $(r-s)(r+s)\equiv0\pmod{p_2}$, thus $r-s\equiv0\pmod{p_1}$ or $r+s\equiv0\pmod{p_1}$, and $r-s\equiv0\pmod{p_2}$ or $r+s\equiv0\pmod{p_2}$.
When this happens, $\mathcal A$ has worked without knowing $s$ randomly chosen at step 1; hence each of the four $s$ possible for the $q$ handed to $\mathcal A$ is equally likely, and with odds $1/4$ we have $r+s\equiv0\pmod{p_1}$ and $r+s\not\equiv0\pmod{p_2}$, thus $d=p_1$ at step 4; and with odds $1/4$ we have $r+s\not\equiv0\pmod{p_1}$ and $r+s\equiv0\pmod{p_2}$, thus $d=p_2$ at step 4.
It follows that algorithm $\mathcal F$ is expected to reach the final step 5 after no more than $\mathcal O(4\log(n))$ iterations, with each step of each iteration running in random polynomial time w.r.t. $\log(n)$; so the whole algorithm does, and outputs a factor of $n$, Q.E.D.


Is this client-side password hash scheme secure? I want to build an app that uses client-side encryption for storing encrypted data on the server. A user-specific master key would be used, so to easily share it between devices a encrypted version of it would be stored on the server.

The user's passphrase would be used for both 1) encrypting the master key and 2) authenticating the user. For this reason the server must not know the passphrase.

The passphrase would be used twice for stretching with PBKDF2, HMAC-SHA256 and a good number of iterations:

First, the encryption key used to encrypt the master key would be derived. A random salt would be used here (also stored on the server with the encrypted key).
Second, a hashed version of the passphrase would be derived. The user email would be the salt.

The stretched passphrase (#2) is then sent to the server instead of the plain passphrase. The server would then use bcrypt to further secure that hash and authenticate the user.

Assuming that all communication happens over HTTPS and the user is forced to pick a strong passphrase, I don't think there is anything wrong with this. Am I wrong?

This is far from secure, assuming a passphrase that a human can remember. The main thing you have to note is that an offline brute force attack on the password can be carried out. This is because the server can guess the password and follow the same procedure and see if decryption works. It is possible to buy a machine that computes billions of hashes a second (for a few thousand dollars). Very few passwords will be strong enough to resist such an attack.

If you can't do anything better than encrypting with a password, then at least it's something. But I wouldn't trust such a solution (not for passwords that I can remember). I suggest finding a different way to propagate a secret key for the client, rather than storing it on the server. (I know that this will be less usable, but security costs...)


On countermeasures for replay attacks. Does this one require plaint text password storage? I was reading this wiki section on the countermeasures against replay attacks and it basically suggests that:

If Bob wants to confirm Alice's identity he can send a one-time token (I think it should be called a 'salt') to Alice which she appends to her password and hashes it before sending it back to Bob, who in turn also does the same operation and compares the results.

But if Bob must perform the same operation i.e. append that token to Alice's password and hash it, then he must also have the original password stored, right?  Isn't this a security risk?

So the question is:  Does Bob have to have a plain text version of Alice's password and if not, how does he avoid this requirement?

Yes, that is a problem.  There are protocols like SRP that both eliminate the need for Bob to store the password in plaintext and prevent replay attacks.


Simplified universal composability (SUC): can I model the use of encryption? Can I prove fairness? I have been reading Canetti, Cohen and Lindell's paper, "A Simpler Variant of Universally Composable Security for Standard Multiparty Computation", and there are some parts that I didn't understand.

In page eight the authors mention that

  we cannot guarantee fairness in the SUC framework, nor model local
  computation via an ideal functionality (as is used to model digital
  signatures and public-key encryption in the UC framework).

Since fairness cannot be modeled, does that mean I cannot prove that a voting scheme, for example is fair (that is, that either the protocol finishes execution and everybody learns the result or nobody learns  anything)?

And does the second part of the quotation mean that I cannot model the use of encryption and signatures in whatever protocol I'm using? I doubt that, but the wording used in the article got me a bit confused.

Since fairness cannot be modeled, does that mean I cannot prove that a voting scheme, for example is fair (that is, that either the protocol finishes execution and everybody learns the result or nobody learns anything)?

In the UC model, fairness is a property of the ideal functionality itself. A "fair functionality" is one that gives output to everybody or to nobody. If a protocol securely realizes a "fair functionality", then you would say that the protocol is "fair."

In SUC you are not even allowed to talk about a fair functionality. All communication from the functionality is inherently "unfair" as part of the underlying communication model. So you are correct, you cannot prove fairness properties in SUC.

  And does the second part of the quotation mean that I cannot model the use of encryption and signatures in whatever protocol I'm using? I doubt that, but the wording used in the article got me a bit confused.

The short answer is, no you are not prevented from using encryption/signatures in your protocols.

The long answer is: we don't typically define security of encryption/signatures using the language of MPC, since these schemes consist of noninteractive algorithms. Yet it is possible to define an ideal functionality $F$ with the following property: "an encryption scheme is CCA secure if and only if that scheme is a secure protocol for $F$ (after translating some syntax appropriately)."

Such a functionality $F$ is really weird compared to typical MPC functionalities. When party $P$ talks to $F$, the response only goes to party $P$, and the adversary gets no notification about this exchange between $P$ and $F$! This models the fact that when $P$ wants to encrypt, he does so inside his head, and doesn't have to talk to anyone (how can an adversary know when I'm encrypting stuff in the privacy of my own brain?).

The SUC model can't handle this kind of functionality. In SUC, when a functionality generates an output for a party, the adversary must always learn the fact that output was produced (maybe he/she doesn't see the contents of the output). So in SUC you can only write a functionality for an interactive "traditional MPC" kind of thing.

So all this is saying is that you can't talk about weird UC functionalities that try to characterize CCA encryption / existentially unforgeable signatures. Again, this is a restriction on the kinds of functionalities you can write in SUC. There is no restriction on the kind of protocol you can write. You can definitely use encryption/signatures in your protocol. In that case, your security proof should then use the standard, game-based definitions of security.


Why ``adversary'' and ``challenger'' and what are typical roles of those? I'm confused with words adversary and challenger, that are used in proof of security of some cryptosystems.
For example, adversary and challenger appear in the formal definitions of IND-CPA, IND-CCA, etc.

What are typical roles of adversary and challenger?

From my understanding, adversary refers to a player who tries to break the system while challenger refers to a player who provides something but does not try to break the system.

Are these correct?

Also, I'm wondering why challenger is not called as helper since it does not try to break the system. Rather, it is there to help the proof.
The word challenger seems like an attacker.

Suppose you are a member of a mailing list or of an anonymous cryptographic site. Now suppose there is some "new guy" who just joined and makes bold claims about having broken some cryptosystem. Now of course because you don't know anything about the "new guy" you don't believe them. Naturally they're really insistent, so you agree to challenge their claim that the cryptosystem is broken. This makes you, the skeptical person, the challenger.

Of course because the other is trying to break the cryptosystem they're the adversary against which the cryptosystem tries to hold up. Now of course you, the challenger, know that a total and complete break of any cryptosystem (e.g. ciphertext-only attack) is an unrealistic capture of the reality, so you agree to provide the adversary with some ressources, e.g. answering requests for encryptions.

So in a sense security games are protocols that allow adversaries to convince challengers that they broke a security property in the most reproducible and convincing way (e.g. because the adversary clearly at no point has access to the key).


Birthday problem applied to hash function with partition of the input set I am not able to understand why if we consider a regular hash function, it is possible to say that we are partitioning the starting set and then apply the the birthday paradox/problem. Can anyone explain?

Consider the classical birthday problem, where in a group (say, of students in a course) we want to know how (im)probable it is that there are at least two students with their birthday on the same day. A mathematical analysis tells that, under the assumption that the birthday is a uniform random variable (a fair approximation), and with only two inputs: the number $n$ of persons in the group, and the number $k$ of possible birthdays (about 365).

When selecting a partition of that group (say, for a lab class with limited capacity), that mathematical analysis will apply to the subgroup with $n'\ll n$, or not, depending on how the selection is made. If that's from a list sorted by birthday and split in intervals, the analysis can fail miserably. However, if the partition is random, or made with no clue about the birthdays (say from a list initially sorted alphabetically not showing the birthday), the analysis stands.

We can model a hash function as a (uniformly selected) random function from its input/starting set (perhaps, the infinite set of all bitstrings $\{0,1\}^*$ or finite subset of that) to its output set of $b$-bit bitstrings $\{0,1\}^b$ (with $k=2^b$ elements). When partitioning the starting set, if the selection is random, or made with no clue about the hash value of an element selected, then the mathematical analysis of the birthday problem applies (the basics are in this answer).

For a given hash function, it is easy to build a partition of $\{0,1\}^*$ such that this analysis fails, with collisions either much more or much less likely than predicted. To avoid this, we often use hash functions with internal parameter(s) (often called Initialization Vector) and a proof/argument that an adversary ignoring the IV would be unable to build a partition defeating the analysis better than by chance. We then pick the IV as a nothing-up-my-sleeves number, and can be confident that the mathematical analysis applies to any selection method making no reference to the IV (such as: the set of bitstrings that are the binary representation of the square of integers less than a billion).


What information about the ciphertext can an attacker discern if a key is used too many times? Suppose that I use Blowfish or XTEA (both secure block ciphers with 64-bit block size) in CTR mode.

In these cases, I need to change the key after $2^{16}$ blocks to avoid leaking information with probability less than $2^{-32}$.

However, suppose that I make a mistake and use the key to encrypt a $2^{33}$-block ($2^{36}$ byte) plaintext.  What information can an attacker, knowing only the ciphertext, discern about the plaintext?

If you are sending a single message, then you are basically fine. Of course, there is a very small amount of bias that can be leaked (for example, if two ciphertext blocks have the same value - and there's actually a very good chance that this is the case - then since you are using a permutation this leaks the fact that those two plaintext blocks are different).

However, the situation is very different if you encrypt many plaintext. This is because if there is a collision on the input, then the attacker will be able to get the XOR of the plaintexts (in which case it learns everything). Thus, this reduces to the question of whether or not a random counter repeats.
If you are sending many small messages, then there is a good chance that this will happen, so this is disastrous. If you are sending two messages, each of length $2^{32}$ blocks and you use a fully random CTR, then the question becomes what the probability is that the counters used in the two messages will "overlap". This is equivalent to the question of what the probability is that the two messages are of distance at least $2^{32}$ apart. This is actually very easy to compute for 2 messages: fix the first counter $CTR_1$ and then note that the next counter can be anywhere except for in the range of $CTR_1-2^{32}$ and $CTR_2+2^{32}$ (where addition is modulo $2^{64}$). This probability is easily computed at $2^{31}$. However, it is important to be aware that the probability degrades fast when you have more messages.

For the above reason, a better strategy for CTR mode is to break the counter up into two parts: the first part is chosen at random, and the second part is then what is incremented. This is often what is done for AES with the first part being 96 bits and the second part being 32 bits. This means that you can only encrypt message of length $2^{32}$ at maximum (otherwise, you break them into two and use a new counter). However, with a 64-bit block you still get very weak bounds. However, if you KNOW that you are encrypting only a few very long messages, then you can do something like this. If you KNOW that you are encrypting many short messages then you are in trouble.

Bottom line, 64-bit blocks these days are a problem...


Why is MixColumns omitted from the last round of AES? All rounds of AES (and Rijndael) have a MixColumns step, save the last round which omits it.  DES has a similar feature where the last round differs slightly.  The rationale, if I recall correctly, was to "make the cipher appear similar in reverse as it does in the forward direction."

Why does this make AES$^{-1}$ look similar to AES?  And how does this help in implementing the block cipher?

Having taken The Design of Rijndael from the library just yesterday, I had a look on this problem, too. Fixee wrote in a comment:

  However, my question is not so much about security implications, but rather
  "how does omissions of MixColumns make the inverse cipher similar to the cipher?"
  and "how does this help in implementing the cipher?"

The encryption has these steps in each round (List 3.2, page 34), with an additional AddRoundKey at the beginning and a shorter round at the end:

Round(State, ExpandedKey[i]) {
    SubBytes(State);
    ShiftRows(State);
    MixColumns(State);
    AddRoundKey(State, ExpandedKey[i]);
}

The decryption looks this way, when done in a straightforward way (List 3.5, page 47) (with a shorter initial round):

InvRound(State, ExpandedKey[i]) {
    AddRoundKey(State, ExpandedKey[i]);
    InvMixColumns(State);
    InvShiftRows(State);
    InvSubBytes(State);
}

As mentioned in a comment, without the omission of the one MixColumns step all 10 rounds would be identical (like the ones above), and we could do the total encryption and decryption as

AddRoundKey(ExpandedKey[0])
for i = 1 .. 10:
    Round(State, ExpandedKey[i])

for i = 10 .. 1:
    InvRound(State, ExpandedKey[i])
AddRoundKey(ExpandedKey[0])

If we move the AddRoundKey to the end of the inverse function, it would look like this:

InvRound'(State, ExpandedKey[i]) {
    InvMixColumns(State);
    InvShiftRows(State);
    InvSubBytes(State);
    AddRoundKey(State, ExpandedKey[i]);
}

AddRoundKey(ExpandedKey[10])
for i = 9 .. 0:
    InvRound'(State, ExpandedKey[i])

In this form, we would have a similar global structure of the encryption and function, but the round functions for encryption and decryption are still structurally different. We (as hypothetical re-inventors of Rijndael) can do better.

Back to our (naive) inverse round function:

InvRound(State, ExpandedKey[i]) {
    AddRoundKey(State, ExpandedKey[i]);
    InvMixColumns(State);
    InvShiftRows(State);
    InvSubBytes(State);
}

By swapping InvMixColumns and AddRoundKey with a modified ExpandedKey) and also swapping InvShiftRows and InvSubBytes (as one of them works on each byte individually, and the other one just transposes whole bytes), we see this is  equivalent to this one:

InvRound(State, ExpandedKey[i]) {
    InvMixColumns(State);
    AddRoundKey(State, InvMixColumns(ExpandedKey[i]));
    InvSubBytes(State);
    InvShiftRows(State);
}

(We still have a shorter group at the beginning, and a final AddRoundKey at the end.)

Now by using a grouping that uses both InvMixColums and AddRoundKey at the end of the round, we will swap the positions of InvSubBytes with InvShiftRows and swap the positions of InvMixColumns with AddRoundKey to get this equivalent description instead (List 3.8, page 49), with again a shorter last round, and an initial AddRoundKey:

EqRound (State, EqExpandedKey[i]) {
    InvSubBytes(State);
    InvShiftRows(State);
    InvMixColumns(State);
    AddRoundKey(State, EqExpandedKey[i]);
}

But as it stands, this round structure, combined with the initial AddRoundKey, is not the inverse of the encryption. The last MixColumns of encryption has no corresponding InvMixColumns, and the last InvMixColumns of decryption has no corresponding MixColumns. We will solve this by omitting the MixColumns step from the last encryption round and the InvMixColums step from the last decryption round. With that change, since both encryption and decryption omit of the MixColumns / InvMixColumns step of the last round, their round structure remains the same and decryption is the inverse of encryption.

This combination of substitution, row-shifting and column-mixing (in this order) looks quite similar to the operation sequence for encrypting, and is now assumed to be more efficiently implemented than the inverse sequence used in the straightforward inversion.

Also, we can share some of the code (for software implementations) or chip area (for hardware implementations) for encryption and decryption.

Of course, we now need a tweak to the key schedule for decryption: apply InvMixColumns on each round key, other than the first and last. As the key schedule is only done once for many blocks, this is not a big overhead.

On 32-bit (or larger) processors with some fast cache (or ROM), one can implement this sequence of substitution, row-shifting and column-mixing (which is independent of any key) for each 32-bit column by looking up four 32-bit values (depending on different bytes in the old state) in four 1kB lookup tables and XORing these together. By using different rotations after the lookup, we can use just one of those tables (1 kB). (Details are in section 4.2, pages 58/59 in the book.)  A part of this table can be used for the final round, too (where there is no column mixing).

Here we can use the same code with different (sets of) tables for both decryption and encryption. (These tables don't change with different keys, so we put them in ROM, or calculate them when first needed.)

(These lookup tables open the way to timing attacks if they don't fit completely in the processor cache, and/or are removed from the cache by other programs running concurrently.)


What does it mean if second half of 8-char string encrypted in 3DES is always identical? In the recent Adobe passwords leak, presumably encrypted in 3DES ECB, second half of all 8-character passwords is identical: ioxG6CatHBw==

Source: http://pastebin.com/iDTFARwq (guesses based on obvious password hints)

L8qbAD3jl3jioxG6CatHBw== password
BB4e6X+b2xLioxG6CatHBw== adobe123
j9p+HwtWWT/ioxG6CatHBw== 12345678
rpkvF+oZzQvioxG6CatHBw== iloveyou
2dJY5hIJ4FHioxG6CatHBw== sunshine
Ttgs5+ZAZM7ioxG6CatHBw== princess
Dts8klglTQDioxG6CatHBw== computer
y7F6CyUyVM/ioxG6CatHBw== superman
2hD1nmJUmh3ioxG6CatHBw== asdfasdf
cSZM/nlchzzioxG6CatHBw== 1q2w3e4r
e+4n2zDarnvioxG6CatHBw== 1qaz2wsx
ueE89xIj8RTioxG6CatHBw== internet
ietF94QrMIbioxG6CatHBw== michelle
ecW6IyEemknioxG6CatHBw== football
lVwka/Mn8TPioxG6CatHBw== baseball
ghrvkwCcX4bioxG6CatHBw== jennifer
eOsrbcW/PeTioxG6CatHBw== abcd1234
Nz4/TI6o5RrioxG6CatHBw== trustno1
iMhaearHXjPioxG6CatHBw== whatever
OPQxDLW2L+DioxG6CatHBw== 11111111

Does it allow for guessing the keying option used or other 3DES encryption properties?

DES has a block size of 8 bytes. Two blocks therefore come to 16 bytes.

It looks like Adbobe were encrypting passwords using two blocks of 3-DES in ECB mode.

Because all these passwords are eight bytes long, the second block is empty and is just filled with zeros. The second block gets started at all because of the string-terminating NUL character at the position 9 of the password. The character that the rest of the block is padded with is also NUL. Because we're in ECB mode, this block encrypts to the same value each time.

That's why all these passwords have the same eight trailing bytes: ioxG6CatHBw==. This is just the sequence of bytes you get when you encrypt 64 zero bits using their key.


Are ciphertext-only attacks on LFSRs possible? Reading about LFSR, I know that breaking an LFSR by knowing it's design and having enough (plaintext, ciphertext) pairs is an relatively easy task but let's assume we know the design of LFSR and a just a long ciphertext, which is the result of xoring plaintext and LFSR output. Is there any way to decrypt the ciphertext?

For example suppose we have an LFSR with primitive characteristic polynomial $x^{51}+x^{9}+1$ and a 5600 bit ciphertext, is there any way to obtain plaintext which we already know is an English plaintext?

One brute-force approach is to try all $2^{51}$ possible seed values, xoring ciphertext with LFSR output and check if resulting plaintext has normal english letter entropy, but this approach gets harder and harder having a larger LFSR degree.

For text known to be ASCII encoded as octets with high-order bit of octets at zero, that reveals one bit of the output of the LFSR out of 8. It allows finding the original state of the LFSR from (say) the first 51 octets of the ciphertext by merely solving a system of linear boolean equations; then decipher the rest. There is no guesswork involved.

For 7-bit plus parity (where the high-order bit of each octet is the eXlusive-OR of the 7 others, or the complement of that), linear algebra works too.

Things get more difficult as the plaintext becomes less redundant. With 7-bit ASCII, noticing that space, digits, common punctuation and all lowercase letters are in range $[\mathtt{0x20}\dots\mathtt{0x3F}]\cup[\mathtt{0x60}\dots\mathtt{0x7F}]$, we know that every such 7-bit symbol has bit with weight 5 set, and there is fair chance that 51 such characters occur in a row somewhere in the 800-character plaintext. A guess of where allows to decode the rest, and it is easy to detect if the guess was right or not, thanks to characteristics of English text.

More generally, if 51 bits at almost any position can be guessed, then the rest is uniquely determined with basic linear algebra, and the guess is verifiable by checking that the resulting plaintext is appropriately redundant. An LFSR is such that a bad guess is weeded out with very high likelihood using very simple tests, unlikely to falsely rule out a bad guess. We can even do with a lenient chi-squared test that the plaintext resulting from a guess is random, and when it's not, it will be correct. This has the advantage of working regardless of language.

As long as enough bits can be guessed, these techniques work with LFSRs of hundreds of bits, including with unknown feedback polynomial (just add the taps as additional unknowns).


Attacks on WinRAR volumes reusing same password? I have quite a few WinRAR volumes that are all encrypted with the same password. The password is long and unbruteforceable, but I recently read that WinRAR uses PBDKF2 as its key-derivation function instead of generating a new volume key every time like TrueCrypt, which means that in essence all of these volumes have the same 256-bit key.

Does that mean that if attackers got ahold of these volumes, they can use techniques similar to crib-dragging to extract the master password? Also, are these kind of attacks practical (i.e. have there been published success stories of such attacks)? I tried searching on Google but found nothing close to what I wanted.

The RAR5 archive format encrypts file data using AES in CBC mode, and generates a 256-bit key using PBDKF2-HMAC-SHA256 (32768 iterations default?).

If an attacker is able to view many files encrypted this way all with the same key, the attack is to recover the key from the ciphertext. This is not an easy task, even if the IV was reused. In WinRAR, the IV should be pseudorandom, preventing the same (or similar) plaintext from generating the same ciphertext blocks.

Additionally, a 128-bit salt is provided during key generation, which should prevent the generated key from being the same for 2 different archives, even if the password is the same. For decryption the salt is extracted from the archive header.

While there is no documentation I can find that specifically says the salt and IVs are pseudorandom, I would assume that it is, meaning that for a given file/password combination, the chances of the archive ciphertext being the same are near 0.

Clarification from RARLAB on exactly how they are generated will help. In the windows UnRAR utility, there is a fallback from CryptGenRandom to using the system time to generate random bytes, which is not acceptable during archive creation, but may be reasonable during decompression for whatever reason. Password data is encrypted in memory and cleared using appropriate methods. I also find it curious why there is a separate salt value in the file record header, as the one in the archive header should be used for KDF.