How should I interpret this note on diffusion of the internal state of a PRNG? This question is about Tyche, a non-cryptographic PRNG. While the PRNG is not cryptographic the analysis and this question surely is heavily involved with cryptography, so I think it's on-topic here.

In short, Tyche is a nonlinear PRNG based on the ChaCha quarter-round function. The state (4 words $a, b, c, d$) gets mixed using the $MIX$ function (which is basically the ChaCha quarter-round), and then a part of the state gets returned. This is the $MIX$ function in pseudocode:

MIX(a, b, c, d):
    a = a + b
    d = (d ^ a) <<< 16
    c = c + d
    b = (b ^ c) <<< 12
    a = a + b
    d = (d ^ a) <<< 8
    c = c + d
    b = (b ^ c) <<< 7

Later the authors propose a faster variant (due to instruction level parallelism), where the inverse of $MIX$ is used, $\textit{MIX-i}$:

MIX-i(a, b, c, d):
    b = (b >>>  7) ^ c; c = c - d
    d = (d >>>  8) ^ a; a = a - b
    b = (b >>> 12) ^ c; c = c - d
    d = (d >>> 16) ^ a; a = a - b

Then the authors note the following (emphasis mine):

  The downside, however, is that $\textit{MIX-i}$ diffuses bits slower than $MIX$
  does: for 1-bit differences in the internal state, 1 $MIX$ call averages
  26 bit flipped bits, while $\textit{MIX-i}$ averages 8.

I don't exactly know how to interpret this note.

Why is this a downside?
Does this mean the quality of the PRNG is less?
By default the initial constant state (in $c$ and $d$) gets mixed with the seed (in $a$ and $b$) using 20 calls to $MIX$. Does it need more iterations to initialize the PRNG when using $\textit{MIX-i}$?
It surely can't affect period length since it's the inverse, right?

I see no issue here about bit diffusion; if $\textit{MIX-i}$ has a problem, so does $\textit{MIX}$.

The reason is simple, $\textit{MIX-i}$ is precisely $\textit{MIX}$, but backwards.  Hence, if $\textit{MIX}$ starting at initial state $S_0$ and ending at final state $S_n$, would generate the output:

$B_0, B_1, B_2, ..., B_{n-2}, B_{n-1}, B_n$

then $\textit{MIX-i}$, starting at initial state $S_n$, would generate the output:

$B_n, B_{n-1}, B_{n-2}, ..., B_2, B_1, B_0$

If the sequence $B_n, B_{n-1}, B_{n-2}, ..., B_2, B_1, B_0$ has a problem (either against a statistical analysis, or against a cryptographical attack), then $B_0, B_1, B_2, ..., B_{n-2}, B_{n-1}, B_n$ should have the same problem.

Now, is $\textit{MIX}$ (or $\textit{MIX-i}$) a good random number generator – either statistically, or as a cryptographically secure random number generator?  Well, I don't know if it's a good statistical rng (it does have an obvious state recovery attack that takes $O(2^{64})$ time, hence I believe it is disqualified from being considered a CSRNG); however the fact that hidden bits from $A, C, D$ are not mixed in as well as they may be are not an automatic disqualification.


Replay attack prevention in connectionless UDP encrypted communication What are the options for replay attack prevention when two parties exchange UDP messages. No connection or session is estabilished. Communicating parties have pre shared key that is used for encryption (aes-256) and authentication (hmac-sha-256).

Communicating devices:

don't have real time clock. Real time can be obtained from NTP, (but what about NTP security?)
have permanent memory
UDP communication is the only option

The simplest way to deal with replay attack prevention (in some narrow sense of that, where the goal is to avoid that the receiver allows the same command to be played to it several times) is to have an incremental counter in an authenticated section of the packet, incremented by the sender before forming a packet to be sent. The receiver checks the authenticity of packets, and discards packets with counter field lower or equal than its own counter, then sets its own counter to the counter just received; initially, the counter is zero on both sides; it must be large enough that it can't overflow, 4 bytes are often enough.

Problems are:

This prevents replay of passively eavesdropped material, but not delayed play of actively eavesdropped and suppressed material. In many adversarial models, that is a devastating issue. Think of a garage door opener: the adversary intercepts "open door" command, count on the user re-issuing another, intercepts that too, plays the first command to garage door, door opens, user is happy; adversary plays the second command later when the user is away. On radio links with a CRC at the end of the packet, the attack can be carried by jamming the end of the CRC so that the receiver ignores the packet, but the eavesdropper has the data, perhaps with a fair amount of error-detection capability.
This requires a reliable atomic counter in sender and receiver, and this is hard, especially in a context where attacker can cut power of the sender or receiver at an instant precisely timed w.r.t. update of the counter. Even static RAM with battery/supercap backup out of reach of an attacker does not provide atomic update beyond wordsize (and then, not all do that, much less give a clear insurance that they do); and things are worse with EEPROM and Flash, which often can only be erased a smaller number of times than the range of the counter, and can enter metastable states where the value read becomes unreliable. That can be solved, but is notoriously difficult to get right.
There must be a distinct counter in the receiver for each sender (it is possible to live with a single counter on the sender side).
Out-of-order delivery of packets, which can occur with UDP, no longer works. This can be fixed with a sliding window, typically in RAM, at the expense of adding complexity (thus risk of error; some briefly crept in earlier versions of the following).
Addition per comment: the receiver maintains a bitmap of $b$ bit(s), for of up to $b$ past counter values less than the current counter that it is willing to accept nevertheless; that bitmap in RAM is initialized to all-zero at reset; and if $0\le j<b$, and bit $j$ in the bitmap is a one, and the receiver's counter is $c$, and $c>j$, then a packet having counter field $c-j-1$ will be accepted (when it would be rejected per the rule in the first paragraph of this answer), and bit $j$ in the bitmap will become zero. The receiver's job on receiving a packet becomes

check size and integrity of packet
extract counter field $x$ of the packet
if $x>c$

if $x-c>b$, set bitmap to all-ones; else shift the bitmap introducing a zero bit at index 0, then $x-c-1$ times (possibly zero) shift the bitmap introducing a one bit at index 0. In C or C++, with $b=32$ and m the bitmap as an uint32_t, this whole step could be: m = (x-c>32) ? 0xFFFFFFFF : ((m+m+1)<<(x-c-1))-1;
$c\gets x$ atomically
accept the packet as received in order (with no earlier packet possibly accepted later when the bitmap is all-zero), done;

else, if $0<c-x\le b$ and if the (now well-defined) bit $c-x-1$ of the bitmap is a one

change said bit to zero
accept the packet as received out of order (which can require special care), done;

else, reject the packet.

As stated in (1), all the above is insecure against an active attacker capable of delaying packets and gaining advantage of that. Alternatives that are secure in this scenario, and do not require the difficult atomic counter, include building a challenge/response protocol on top of UDP, with the challenge good for a certain delay measured by the receiver (which requires the ability to evaluate elapsed time, but not absolute time); main problem is, that requires two-way communication.

It is also possible to use an authenticated source of absolute time; the hard thing is to find a reliable free one, see this.


Sigma protocol when order is unknown In the following paper (page 5) they have a proof that a triple $\left(g,b_{i-1},b_{i}\right)$ is of the form: $\left(g,g^{x},g^{x^{2}}\right)$ for some x.

The relevant text from the paper is as follows:

They say the protocol is based on a classic proof that a tuple is a DH tuple, however I don't agree because I think they're missing a fundamental issue:

In the ZKP of a DH tuple, the order of g is known, however, here - the order of g is not known because it might leak information about $\phi(N)$.

My goal is to turn the protocol in the paper to a Sigma protocol to make it non-interactive.

I tried to construct a witness extraction (to prove the special soundness property) for the protocol in the paper but I constantly hit a wall where I have to know the order of g:

So assume that we have 2 different transcripts with the same $z_{i},w_{i} $ but different challenges $c_{i},c'_{i}$ that the verifier accepts.

Thus, the following equations hold:

$(1)~\,g^{y_{i}}\cdot b_{i-1}^{-c_{i}}=z_{i}$

$(2)~b_{i-1}^{y_{i}}\cdot b_{i}^{-c_{i}}=w_{i}$

$(3)~ g^{y_{i}'}\cdot b_{i-1}^{-c'_{i}}=z'_{i}$

$(4)~ b_{i-1}^{y'_{i}}\cdot b_{i}^{-c'_{i}}=w'_{i}$

From the first equation and the third equation we get that:

$g^{y_{i}}\cdot b_{i-1}^{-c_{i}}=g^{y_{i}'}\cdot b_{i-1}^{-c'_{i}}$ , thus   $g^{y_{i}-y'_{i}}=b_{i-1}^{c_{i}-c'_{i}}. $

However, now I'm stuck because I cannot find $\left(c_{i}-c'_{i}\right)^{-1}mod\,\phi(N)$ because I don't know $\phi(N)$ in the first place  (as an efficient witness extractor), nor I can do some kind of $gcd(a,b)=1$ trick .

At the same time, this paper hints that it's probably not possible to construct a Sigma protocol while working in groups of unknown order.

However, the protocol in the timed commit paper argues that each ZKP of the $(g, g^x, g^{x^2})$ triples has negligible soundness so it seems to have all the preconditions for a candidate for a Sigma protocol.

What am I missing?

How do you prove the soundness property of the ZKP from the paper without witness extraction (which seems not possible)?

(By the way - I am aware of a paper that proves this in a different way, I merely want to understand what I'm missing here).

Many thanks in advance.

How do you prove the soundness property of the ZKP from the paper without witness extraction (which seems not possible)?

It is perfectly possible and you've almost done it already! You are right that unknown order groups make your life very complicated when you want to build proofs of knowledge - we know results in this direction (the one you cite) -- although it should be mentioned that they break down as soon as you use a CRS (e.g. as we did in this paper).

But if you only want soundness and not the stronger knowledge extraction, you do not need to compute this cumbersome $(c_i-c'_i)^{-1}\bmod \varphi(n)$.

Let $z_i \gets y_i - y'_i$ and $d_i \gets c_i - c'_i$.

From equations (1) and (3), you get $g^{z_i} = b_{i-1}^{d_i}$.

From equations (2) and (4), you get $b_{i-1}^{z_i} = b_{i}^{d_i}$.

Therefore, it is necessarily, mathematically true that there exists an exponent $x$ such that $g^x = b_{i-1}$ and $b_{i-1}^x = b_i$. Indeed, this $x$ is equal to $z_i\cdot d_i^{-1}\bmod \varphi(n)$. So sure, you can't compute it - but the fact that it exists suffices to prove soundness of the protocol! In other words, $(z_i, d_i)$ still constitute a certificate that the word is in the language, which you can extract whenever the prover produces an accepting proof. This certificate is not a witness with respect to the target relation, but it's existence still suffices to guarantee membership to the language.

Answering questions from the comments

  Can you please point to the witness that we can extract with their protocol ? (and how? :-) )

Consider the following relation $R$: $(a,b,c)$ is in the language if there exists values $(x,y)$ such that $a^x = b^y$ and $b^x = g^y$. That is, $R((a,b,c), (x,y))$ returns 1 iff $a^x = b^y$ and $b^x = g^y$ (and $0$ otherwise). A witness for this relation is a pair $(x,y)$.

First, observe that the language captured by this relation is exactly the same as the language of tuples $(a,b,c) = (g,g^z,g^{z^2})$. The difference is that in the first case, what you see as a witness is a pair $(x,y)$ such that $a^x = b^y$ and $b^x = g^y$, while in the second case, it is a single exponent $z$ such that $a^z = b$ and $b^z = c$. This correspond to a different relation $R'$ for the same language: $R'((a,b,c), z) = 1$ iff $a^z = b$ and $b^z = c$.

In the protocol above, you indeed extract a pair $(x,y)$, which is a witness according to the relation $R$ (hence suffices to prove knowledge for a witness of membership to this language - but a witness with respect to a different relations compared to the one you had in mind, which is the second one, $R'$). Indeed, just set $y_i - y'_i$ to be the $x$ and $c_i - c'_i$ to be the $y$, and you have exactly your extracted witness (since the extractor knows of course $y_i, y'_i, c_i, c'_i$).

  But what is the proof of this soundness? To prove this, you need to prove that if a cheating prover can convince the verifier that a pair not in the language, is in the language - then it can also do something intractable. Can you perhaps tell how would you prove such a thing?

You are getting confused with the situation where we prove computational soundness using some hard problem. If a protocol is only computationally sound, then a proof will look as follow: suppose the word is not in the language, and the prover manages to provide a convincing proof of membership. Then I can use this prover to break a hard problem.

Here, we are in a scenario where the proof is much more direct: the soundness is unconditional. This means that I do not have to show that a prover that proves membership of a word outside the language can be used to break a hard problem: I can directly show that if any prover provides a successful membership proof, then necessarily, the word has to be in the language. No hard problem involved.

To spell it (a bit more) formally:

soundness: the protocol above is unconditionally sound if there does not exist a malicious prover $P$ (even with unbounded power) and a word $(a,b,c)$ outside of the language $L = \{(a,b,c) = (g,g^z,g^{z^2})\}$ such that $P$ provides a convincing membership proof for $(a,b,c)\in L$.

proof of soundness: Fix any word $(g,b_{i-1},b_i)$, and any prover $P$. Use rewinding; with non-negligible probability, we get values $(y_i, y'_i, c_i, c'_i)$ satisfying equations (1) to (4) of your questions. But this implies that there exists values $(z_i,d_i)$ such that $g^{z_i} = b_{i-1}^{d_i}$ (by 1 and 3) and $b_{i-1}^{z_i} = b_{i}^{d_i}$ (by 2 and 4). But now, those two equations imply that there exists some value $z$ such that $(g,b_{i-1},b_i) = (g, g^z, g^{z^2})$. This $z$ is in fact equal to $z_i/d_i \bmod \varphi(n)$: it exists, but you cannot compute it. But since it exists, we can conclude that the word $(g,b_{i-1},b_i)$ does in fact belong to the language $L$! In other terms: each time the prover produces a convincing proof for $(g,b_{i-1},b_i) \in L$, then it is indeed the case that $(g,b_{i-1},b_i) \in L$ -- hence, the prover cannot possibly produce an accepting proof when $(g,b_{i-1},b_i) \notin L$, which proves soundness.

  If the prover guesses the $c_i$ the verifier would send, it can send $z_i = g^{y_i}\cdot b_{i-1}^{-c_i}$ and $w_i = b_{i-1}^{y_i}\cdot b_{i}^{-c_i}$ and the verifier would accept any $b_i,b_{i-1}$ no? Now if it can do it once, it can do it twice, with probability $1/R^2$ which is negligible but still not exactly   ⇒$(g,b_{i-1},b_i) \in L$... what am I missing?

The above attack you suggest does not work, for the following reason: to execute the attack, you must guess $c_i$ and send $z_i = g^{y_i}\cdot b_{i-1}^{-c_i}$ and $w_i = b_{i-1}^{y_i}\cdot b_{i}^{-c_i}$. Then, you say "if it can do it once, it can do it twice, with probability $1/R^2$". But this is not true! Remember that when rewinding the protocol, the same first flow is reused for the two rewinds. Hence, the prover does not get any occasion to create "another" pair $(z_i, w_i)$ by guessing $c'_i$.

Now, it is still true that the above soundness proof can fail, because there is some probability, when you sample a random $c'_i$, that it is equal to $c_i$; when this happens, $c_i-c'_i = 0$, and therefore the word is not guaranteed anymore to be in the language.

But in fact, the only reason this trivial attack applies is because I decided to keep things simple, for the sake of readability. If you want to understand exactly why this issue is not a real problem, here is a high-level sketch of how the fully formal security analysis would proceed:

Sketch of the Fully Formal Proof

Assume that there is a prover $P$ that can break soundness. What (statistical) soundness formally says is that for any (possibly unbounded) candidate prover $P$ which picks a word $X$ and interacts with the verifier $V$, the probability that ($X \notin L$) AND ($V$ is convinced) must be negligible. So assuming a prover that can break soundness means assuming that there exists a $P$ which outputs a word $X$ and interacts with the honest verifier $V$, such that

$\mathsf{Pr}[X \notin L \wedge V \text{ is convinced}] \geq \varepsilon,$

for some non-negligible quantity $\varepsilon$ (warning: I'm again hiding some technicalities here about the exact quantifiers when defining "negligible" and "non-negligible").

Hence, what we have is a prover that outputs a word $X$ and interacts with $V$ such that it happens simultaneously that $X$ is not in $L$ and $V$ accept the interaction, with some non-negligible probability $\varepsilon$.

The first question is:
How do we extract from this prover the values which satisfy equations (1) to (4) in your question?

The answer I gave before was just "we use rewinding", but this does not explain why it works. A single run of the prover outputs a word $X$ and a transcript $T$ of his interaction with $V$, such that $X \notin L$ and $V$ accepts, with proba $\varepsilon$. But what we want is to get two accepting transcript, with respect to the same word $X \notin L$, and also with respect to the same first flow.

It turns out that there is a simple lemma, the splitting lemma, that allows exactly to do that -- see for example page 10 of my paper (which I already mentioned in this answer). This lemma allows to show that we can fix the word and the first flow, and repeat the rest of the protocol twice; and still, the word $X$ will not be in $L$ yet both transcripts (with the same first flow, but a different second flow) will be accepted, with overall probability at least $\varepsilon^2/4$. This is not too hard, but not entirely trivial either - it's a good exercise in probabilities.

Now, if we found two transcripts as above, then we can do exactly as I said previously and use equations (1) to (4) to verify that $X$ must be in the language, therefore reaching a contradiction (hence such a cheating prover $P$ does not exist). Note that we do not need to find these transcripts with probability 1: the simple fact that we could find them with some non-negligible probability already suffices to reach the contradiction.

Another way to view it is that extracting the witness (for the relation $R$) cannot usually be done with a single run of the protocol: you need to repeat the above procedure on average $4/\varepsilon^2$ times (which is polynomial) to successfully extract a witness by the above procedure. This issue is exactly the reason why the standard definition of proofs of knowledge does not say that the witness can be extracted in strict polynomial time, but rather in expected polynomial time. Here, we can extract a witness successfully, but the running time of the extraction procedure will only be $O(4/\varepsilon^2)$ in expectation.


In RSA. Why is $\phi(n)$ kept secret and $n$ is public? I mean, $n$ can also be easily used to find the factors $p$ and $q$ right?

No, it is not easy! RSA is based on the difficulty of factoring the product $n=pq$ of two large prime numbers. But if you know $\varphi(n)$ for plain RSA you can compute the secret exponent $d=e^{-1}\bmod \varphi(n);\;$ and you can factor $n$ from the two equations $n=pq,\;\varphi(n)=(p-1)(q-1)$.


Known ciphertext, unknown public key Let's say I have ciphertext c = Enc(pk,m), produced by a public-key encryption scheme but I don't know the public key of the sender. Can the sender easily produce another key pair and then claim that the ciphertext actually corresponds to c = Enc(pk',m') or is this computationally impossible?

There are certainly public key schemes where this is possible. The recent CurveBall exploit was essentially able to switch out public keys on an elliptic curve and thus forge signatures. The same trick could be pulled with the elliptic curve El Gamal encryption scheme. It would be trickier to do with RSA (you have to construct a very special public key), but far from infeasible.


Brute forcing Cardan grille Having a "rotating" square Cardan Grill with sides long n cells, how could i determinate the cost of a brute-force attack?
How many configurations should be considered to perform an exhaustive search?

EDIT FOR MORE DETAIL:

This was an exam question so these are all the information given to me, but i think i can suppose that the grille has $(n^2)/4$ holes, the plaintext has $n^2$ letters, letters are not visible in more than one orientation and the grille have to be rotated 4 times.

Are these informations more helpful?

With the extra information you've provided, there are $4^{\left\lfloor \frac{n^2}{4} \right\rfloor}$ possible grilles to consider.

Specifically, consider an $n \times n$ grille with just one hole, and make a mark on the paper through that hole with the grille in each orientation.  If you do that, you'll see that there will always be exactly four marked positions on the paper, placed symmetrically around the center (unless $n$ is odd and the hole is in the middle of the grille, in which case all marks will be in the same position).

Clearly, with the grille in its original orientation, exactly one of these four positions must have a hole: if two or more of them had holes, the same letters would show through all of them, and if none of them had holes, the letters in those positions would not be visible in any orientation (contradicting the claim that the plaintext has $n^2$ letters).

(Incidentally, if the requirement that no letters are visible in more than one orientation is taken strictly, it means that the center position cannot have a hole for odd $n$, meaning that the plaintext length for odd $n$ can be at most $n^2-1$.  So we must either relax one of the requirements or rule out odd $n$.)

Each grille has $n^2$ positions (including the center position for odd $n$) and thus $\left\lfloor \frac{n^2}{4} \right\rfloor$ of these 4-position cycles.  (The floor is there for odd $n$; if $n$ in even, $n^2$ is divisible by 4.)  Assuming maximal plaintext length, each of these cycles must contain a hole (and, as shown above, cannot contain more than one hole).

By symmetry, each of these holes can be in any of the four positions within their respective cycle.  Thus, we have $\left\lfloor \frac{n^2}{4} \right\rfloor$ independent choices, with four options for each choices, giving us a total of $4^{\left\lfloor \frac{n^2}{4} \right\rfloor}$ possible sets of choices.


Generating keys with HKDF from Diffie Hellman agreement In order to generate multiple session keys from a Diffie Hellman key agreement protocol, I'm trying to use the HKDF to generate this session keys. The HKDF algorithm uses an Extraction-Expand procedure. In the extraction procedure, it takes as an input a salt and a source key (in my case it will be the Diffie Hellman generated key). I know that the salt it is a random non-secret value.

My question is: How do I establish this random salt value between two entities? Can I set this value by applying a hash function to my Diffie Hellman key like Salt = HashFunction(DiffieHellmanKey)?

You don't need a salt (it defaults to a zero length salt) if you generated the session keys using Diffie-Hellman. You should however use a different info (octet) string for each key in the expand part of the function.

The idea is that the salt makes sure that the derived keys are different if the input keying material (IKM) repeats. If no salt is used within the key derivation then the session keys would be identical each time the key derivation function is performed. Diffie-Hellman however should never generate identical input keying material (see note).

The info strings should be static for each key, e.g. an ASCII encoding of "enc" for an encryption key would be a good idea.

Here's a link to the RFC for HKDF. Here's a link to Hugo Krawczyk's paper describing HKDF at length.

Note: at least one of the parties in the DH key agreement should generate sufficiently random ephemeral key material. If the random number generator (RNG) is broken then you may get identical input key material. It is not possible to generate a random salt if your RNG is broken though. In other words, you need a good RNG whatever you do.


Order of random element in RSA is big Im trying to understand the proof in "The Discrete Logarithm Modulo a Composite Hides O(n) Bits" by Håstad et al, where he shows that the order of a random element in RSA group is big.
I got the most part but there is one transition that I just cannot see (in Proof of Lemma 1.2):

Any suggestions on how I could approach it?
Edit: F is defined as:

Write $d$ for the order of an element of $(\mathbb Z/P\mathbb Z)^\times$, we know that $d|P-1$, and that there are at most $d$ elements of order exactly $d$ as they all form roots of the polynomial $t^d-1\pmod p$. Then counting the number of elements of order less than some bound $B$ is less than summing $d$ over the divisors of $P-1$ less than $B$. Taking $B=(P-1)/m^\ell$ shows that $F(P-1)$ is an upper bound for the number of elements of order less that $(P-1)/m^\ell$.
Considering all possible $g$ and $P$, we want to know the proportion of $(g,P)$ pairs for which $\mathrm{ord}(g)<B$. We divide into two cases: either we have a $P$ where the number of $g$ of small order is greater than some bound $C$ (this is bounded by $\mathrm{Pr}(F(P-1)>C$), or the chance of picking a $g$ from a set of size less than or equal to $C$ is bounded by $C/X$. Taking $C=X/m^{\ell'}$ gives the formula stated.


Why are twofish or other algorithms not NIST approved, are they still safe? NIST has a total of 3 approved block ciphers on their website: AES, TDES and skipjack.

I get why those are on there (though personally I find TDES a bit iffy) but from my understanding Twofish and Serpent are also good enough to make the list. so why aren't they there? are they too weak? have they been broken to an extend where they are no longer safe to use?

EXTRA:

I'm really interested in knowing why some ciphers are recommended and others aren't. I'm looking for an algorithm to use my self, to do this I want to make a selection of a few algorithms which are safe to use so I have a reason to fall back on when i'm asked why i chose for that specific cipher other than the standard excuse because it's AES (or NIST approved)

Are there credible sources I could quote for other algorithms (such as Twofish) which shows they are still reliable?

The reason NIST chose one algorithm out of the five AES finalists, even though all of them were pretty well-respected (and some were, at the time, considered likely to be more secure then Rijndael) is because NIST is a standards body, and the whole point of the AES project was to find a standard algorithm. The issue with approving lots of algorithms is that you can easily end up with multiple standards-compliant implementations that can't talk to each other because they don't implement the same algorithm. AES is supported everywhere, and is reasonably fast on all platforms (plus, the fact that it's so common makes stuff like AES-NI practical).

These days, it seems to be common to have several algorithms in order to provide a fallback if a flaw is found in one (for instance, that's the point of SHA-3), but that's not the normal way standards agencies work, and even with SHA-3 NIST picked one algorithm. It's not thought of as "good enough to make the list;" the rule is "the algorithm that best meets our goals for this standard."

As for why Rijndael was chosen -- it was a good balance of security, software performance, hardware performance, and ease of implementation (or so it was thought at the time; it's actually kinda tricky to securely implement). Twofish and Serpent were believed more secure at the time, but other things like performance meant they weren't good for all uses. Since the point was creating one standard, they weren't chosen.


I need a pathway for studying Lattice-Based Cryptography I realize that I need a study pathway for post-quantum cryptography.
I started to study post-quantum crypto by reading NIST PQC 3rd-round submissions of the lattice-based schemes (let's start with the most popular ones). I understood Kyber and Saber so that I could implement them. However, I want to understand the design rationales behind them. Why these errors have that length, what is the role of these parameters in practice.
Since the first lattice-based encryption schemes, there must be many improvements done considering speed or security. I need to understand these. Then, I started searching for papers about lattice-based algorithms and their attacks over the history of lattices. I found a large list here, but I could not filter these papers.
How should I start? Is there a good survey for me, or a list of readable papers covering the area?

Katz and Lybushavesky just (yesterday) released a book on lattice based cryptography. My particular copy is still shipping, so I can't mention whether it covers what you are in particular interested in, but as:

Lyubashevesky is a co-author of both the KYBER and DILITHIUM finalists

Katz's prior book (with Yehuda Lindell) Introduction to Modern Cryptography is widely praised for its excellent writing (and Katz is a co-author of the non-lattice Picnic round 3 alternate signature scheme)

It seems quite possible this could be the "goto" recommendation for learning lattice-based cryptography generically, and potentially even have exposition on the NIST candidates --- I won't know until my copy arrives though.
These slides by Daniel Apon (at NIST) regarding why NIST made the particular round 3 selections may also be useful for discussing the "design space" of lattice-based NIST candidates. You can find this kind of exposition elsewhere, for example in this paper of Dan Bernstein --- although I should mention that Dan often disagrees with certain "consensus" viewpoints within lattice cryptography.
The paper is still useful of course, but if I recall Dan in particular has slightly non-consensus views on:

The underlying choice of ring for RLWE (in particular, the size of its Galois group)
Particularities of the definition of security often used in lattice cryptography (the "core-SVP" count)
Certain potential patent issues with various RLWE-type techniques

One can read more about these disagreements on the NIST pqc google group, but I don't know of some short summary of them.


Can quantum hardness be demonstrated? I am disturbed by assertions that this or that classical cryptographic primitive is "quantum resistant", but my understanding is that no one knows yet how to demonstrate quantum hardness, or even if such demonstrations are possible. At best, there may be cryptographic primitives for which no quantum attack has yet been found (but of course the world does not have much experience yet with quantum computers!)

Is this correct? Or, is there a rigorous way to demonstrate quantum hardness that I have not yet seen?

"Classical hardness" is demonstrated in the very same way, namely, we find a problem that is believed to be hard then we reduce the task of breaking the security of the scheme to the task of solving that problem.

So, it is kind of the same situation, because maybe there exist classical polynomial-time solutions to the problem used and those solutions simply were not discovered yet.

The main difference is that, in general, we are far more used to classical computers than to quantum ones and maybe saying that a problem is believed to be classical hard is more meaningful than the quantum analogous because we have really studied those problems a lot in the classical setting...


Performing HMAC with random key before MAC comparison In Laravel (a PHP framework) I can see that they calculate a HMAC with a random key over the final HMAC before comparison. This additional HMAC calculation is of course performed for both the calculated MAC and the received MAC value, using this randomized key.

Does this just supply a method of performing a "constant time" compare? Or does it add other security properties to the MAC calculation. I presume the former, but I want to be sure. Is this a known technique for performing MAC comparisons?

The commit that added this double HMAC only says it improves "valid MAC detection", but it simultaneously adds the constant-time comparison, so likely the reason is indeed defense against timing attacks:

Improve valid MAC detection
Implement constant time string comparison as well as double HMAC
verification for encryption MACs.

Double HMAC is a known technique to avoid the side channel attack, and has been recommended as a more reliable (and "simpler") alternative to constant time comparisons. I am not aware of anyone recommending both, which is pointless (they prevent the same attack) and costs even more than double HMAC - its main downside compared to constant time comparisons. On the other hand, it should not hurt, so perhaps it is done out of an abundance of caution.


Is there a way to inercept encrypted https connections by mimicking a cert authority? In this video, it is shown how encryption can be theoretically intercepted without the client noticing it.

In short something in between the connection could make a handshake with the requested server and mimic a cert authority and create a secure connection with the client.

Could this work in the real world breaking integrity?

Yes, this works, but the trick is that you'd need a certificate and private key signed by a certificate authority that authenticates the specific location you are browsing to. This certificate has to be part of a certificate chain that leads to a CA certificate that has to be trusted by your browser. The video makes you believe that a CA has to say "yes" which is incorrect.

So lets go to real life scenarios. Basically there are two possiblities:

You somehow have a trusted certificate in your browser that authenticates your connection. This could for instance happen if you're browsing through a company proxy that also proxies the HTTPS connections. These proxies exist; they basically look at the content of the connection and then send it through the HTTPS connection to the server. The proxy then acts as a HTTPS client. In general the IT dept makes sure you've got a company or proxy specific certificate in your browser store. The connection would fail if you'd use a stock browser.
A trusted CA is compromised and gives out bad certificates, either deliberately or unintentionally. A good example would be the DigiNotar debacle here in the Netherlands, where DigiNotar signed an end certificate for google.com, among others.

In both cases an unaware user would be tricked into accepting the connection, even though the underlying certificate chain would differ from the original one. Closer inspection could however show that different certificates are being used then the original one.


Is it safe to derive a password from a signature provided by ssh-agent? I'd like to use a password-based system on a remote host (accessed via SSH) without having to copy-and-paste the password and without storing it on disk.  Using the system with some other form of authentication is not an option.

One possible solution is to talk directly to ssh-agent and have it sign a constant token and then use, say, the signature's base64-representation as the password.  This password can always be re-generated, assuming access to the private key and knowledge of the token.

https://gist.github.com/mprymek/10415576 shows that this technique is being used in the wild.

Is this approach (deriving a password from a signature) cryptographically sound?
Is this approach secure?  For example, when SSH agent forwarding is used, is the signing request and response (exchanged between remote host and local ssh agent) safe from eavesdropping?

EDIT: draft-ietf-secsh-agent-02 section 4.2 says that forwarding happens through an SSH channel, and the abstract of RFC 4254 says that "channels are multiplexed into a single encrypted tunnel" which I believe means that agent forwarding is fully encrypted.

Is this approach (deriving a password from a signature) cryptographically sound?

Not in general. There are signature algorithms that are completely deterministic and signature algorithms that aren't. With the latter kind you would be unable to reproduce the password later.

With a deterministic algorithm, yes, the basic idea of using the signature as a password is sound (assuming no attacker can get the signer to sign the same token in some other situation). If it wasn't secure, that would mean the attacker had some way to produce the same signature, which would mean the signature algorithm itself would be broken.

Note that rather than sending a token for the client to sign, an SSH v1 server actually encrypts a token, sends it to the client and stores a hash. The client must decrypt the token and reproduce the same hash in its response. (See section 2.3 of the document you linked.) This is likely why the linked program talks about 160-bit passwords.

A similar argument as above makes this secure: to know the hash an attacker has to either know the original token generated by the server or be able to decrypt the challenge (which they can't do without the key, unless the encryption algorithm is broken).

  Is this approach secure? For example, when SSH agent forwarding is used, is the signing request and response (exchanged between remote host and local ssh agent) safe from eavesdropping?

As for whether that's safe from eavesdroppers... yes, if you assume they are outside the systems involved. An attacker with sufficient control over the final destination machine could eavesdrop the original challenge generation. An attacker with sufficient control over the source machine where you authenticate could similarly eavesdrop the response generation.

I'm not entirely sure whether an attacker on the middle machine would be able to do the same, but I believe so. As I understand the forwarded traffic passes unencrypted from ssh to sshd and is only encrypted between the hosts. That's (one reason) why some people have suggested using more complicated layered ssh connections instead of agent forwarding.


BB84 quantum protocol In BB84 protocol, when Alice and Bob make key distribution, what is the private thing?
They select randomly bases and then make a measurement according to these bases. Used bases are private? I mean that does Eve know which basis was used at each position? If Eve dont know these bases, then How can Alice and Bod share using bases securely? In here, what is public and private?

If we assume that Alice is the one sending the photons, and Bob is the one receiving them, then Bob selects random bases to take the measurements, and then announces them (both to Alice and any potential attacker) after he has taken those measurements. An attacker cannot use that announcement to decide how to take measurements himself, as he doesn't hear it until after the photons have passed.

Now, if the attacker could replace Bob's announcement about the measurements with his own, he could break the system - this would be a simple MITM attack, where Alice communicates to the attacker, and the attacker communicates with Bob.  However, authenticating this communication isn't difficult; it can be done using a universal hash, initially (for the first exchange) a key that was installed in both systems, and for later exchanges, bits that were exchanged during the previous exchange.


Encrypting messages without revealing length? In various messengers, we have end-to-end encryption, making it hard to know what the message said.
But do these messengers have to pad the message to some maximum length every time, in order to hide the length of the message?
In a block cipher, there is a minimum length that you have to pad to, right?
My question is how do WhatsApp, Telegram, and Signal actually do this? How effective are they are hiding the length of the message?
And are there good ways to hide this type of metadata (length of the message and how often it is being sent) by doing some sort of steganography (eg posting message chunks to different endpoints depending on a hash of some variables available only to the participants, and sometimes also posting decoy garbage prefixed with “disregard:” in order to obfuscate patterns, etc.)

This is a complementary answer to the Model Nest's answer, and will concentrate on how to achieve the constant size for messages. We assume that the files have confidentiality, integrity, and authentication while sending/ receiving.
First of all, in the security proofs like the CPA game, we assume the messages have the same length, otherwise, the advantage of the adversary is 1.
With 10 MB file limit

Encryption time
Here we assume that the application limits the message size to 10MB. This makes 10485760 bytes and therefore one needs 655360 AES encryptions per file.
If you have the AES-NI then the time is not the issue see AES-NI can reach 5.4107GB per second on my machine. That is far from the 10MB. Some ARM has the AES-NI instructions, and the performance is not included in this answer.

Sending time The 4G LTE

Download: 20Mbps and theoretical ones of 150Mbps and it will take 4 seconds with 20Mbps to download
Upload: 8Mbps on average and 50Mbps that will make 10 seconds to upload.

If the message size is fixed to 10MB then the chatting will be slow and people will start to complain. An alternative method is using two sizes if the leaked information that is the distinction of a message is sent or a file is sent then this is applicable.
Therefore here we can say that the limit does not come from the encryption time but due to the network speed. 5G calculations are not included.
Padding options

PKCS#7: When we talk about padding the first that comes to mind is the PKCS#7 padding. However, that is not applicable here since it can support up to 256 bytes since each byte represents the length of the padding.

Zero one padding: This is fine as long as the underlying Encryption algorithm is CPA secure and the (Key,IV) is not reused as in AES-GCM. If used this padding will produce a cheap reveal of some part of the messages. One can use a nonce misuses resistant scheme like AES-GCM-SIV or a faster version AES-PMAC-SIV to mitigate this problem.
SHA-3 padding is also applicable

ANSI X9.23 with a little extension this padding can be used; the last 32 bits can represent the padding size and the space between the data and size is filled with 0.

ISO 10126 This is similar to ANSI X9.23 except instead of filling with zero, random bytes are filled. This seems like the best candidate.

Results:

We can hide the length of the messages with a prefixed size.

The encryption time is not an issue if AES-NI is available.

The upload and download time can be the issue of chatting.
As a matter of the fact, constant size is achievable in secure message applications but not preferable for general users.


DSA parameter selection In the Digital Signature Algorithm, is there a reason why the larger prime parameter should be an $N$-bit prime where $N$ is a multiple of 64 ?
Is this strictly necessary for proper working of the algorithm?

The algorithm would work fine without the restriction, although it's debatable whether NIST owns the name DSA and you would have to call it something else, the way non-RSA-licensed implementations of RC4 were for a long time called ARCFOUR (alleged RC4) or similar. How about Schnorr Patent Evading Digital Signature SPEDS?
Why did NIST do it (originally, see next)? AFAICT 'everyone knows' they wanted to reduce the amount of testing needed to ensure that multiple, different implementations would provably meet the standard and (as a result) interoperate with each other reliably, while still allowing designers and possibly users to choose tradeoffs of cost vs security. I don't think I've seen that rationale officially documented anywhere, but they certainly have done essentially the same thing with other algorithms and standards, most notably AES (which supports only 3 key sizes and 1 block size, though the underlying algorithm Rijndael supports quite a few more).
Also note the originally permitted sizes 512 to 1024 by 64 -- which still survive in a good deal of software that hasn't been updated -- have officially been obsolete for a long time. Change Notice 1 to FIPS186-2 in Oct. 2001 restricted p to only 1024 (with q still 160); after a long delay FIPS186-3 in June 2009 added p 2048 or 3072 (with q 224 or 256 in the former case and 256 in the latter) -- while 1024 2048 3072 are multiples of 64, they are not all the multiples of 64 in that range, and do not provide nearly the 'fine tuning' that the old list did.
Although in contrast RSA and DH were defined and usually are implemented for any bit size (sufficiently large to provide the desired security) in practice people almost always use powers of two or 'halfway between' sizes: 512 768 1024 1536 2048 3072 4096 -- and FIPS186-3 specifies key generation for RSA signatures (for US govt use) that only allows n sizes 1024 2048 3072.


How do “modes of operation” with block ciphers like (eg) DES work? When trying to understand how “modes of operation” are applied when using block ciphers like DES, I noticed I must be missing something. Maybe I simply misunderstood or mixed up things somewhere.

How are (keeping the DES example) Feistel structure properties achieved, when a mode of operation such as ECB is used?

The block cipher itself is used as a black box for any mode of operation. The internal design - including if the block cipher uses a Feistel network - is completely tranparent to the mode of operation.

The only thing that matters for the mode of operation is the block size of the block cipher. This, together with any usage limitations, limits the applicability of the block cipher for certain modes of operation. (Tripple) DES is less useful for modes of operation such as CTR and unusable for GCM which requires a 128 bit block size.

Note that the block cipher is basically a configuration parameter for the mode of operation. The block cipher itself doesn't use a mode of operation - it is being used by one.


Why does appending a message to a key before hashing not guarantee integrity? I want to guarantee the integrity of a message $m$. My first thought is to append the message to an integrity key $k$ and hash it as $H(k\,||\,m)$. However, I have been told that this is not totally secure, because an attacker can add more data to the end of $m$ while still generating the correct MAC.

How is it possible for an attacker to modify $H(k\,||\,m)$ such that the message is changed but the MAC is the same?

I was advised to use HMAC instead. Why does HMAC solve this problem?

It depends on the hash function you're using, but some hash functions work like repeated block ciphers (SHA1 and MD5, for example).  The point is (as you've been told), an attacker can use the hash and continue appending data to generate a new and valid MAC.

That is, given $H(k||m)$, a valid MAC for $k||m$, an attacker can generate $H(k||m||m')$, a valid MAC for $k||m||m'$.  This is undesirable behavior.  We want to avoid the possibility of an attacker generating a valid MAC for any message, even if they don't know the key.  This is why it invalidates integrity, because now an attacker can make valid messages and MACs (with limitations) when they don't know the key.

See Length extension attacks.


Can there be a need for 1024-bit (symmetric) encryption? I think we are all aware of the CAESAR-competition. Now the aim of this competition is to select a (portfolio of) winner(s) which provide authenticated encryption.
I'll now assume that the results produced by this competition are very good, meaning the cryptanalysis of the next 50+ (!) years won't yield any significant attacks (speed-up no more than $2^{80}$ compared to brute-force). Further it may be assumed that the scheme has 512-bit keys, to reach 256-bit security against quantum-computers.

So far for the assumptions, now to the background:
I recentely read this text by B. Schneier, where it was stated that the laws of thermodynamics disallow a counter to count to more than $2^{200}$, even in an ideal setting (3.2K, dyson sphere, kT for bit-flip,...). So I asked myself the following question as 512-bit seem to fully suffice forever (if we don't harvest the whole universe's energy...)

Now my question:
Besides performance and flexibility, will there ever be the need for 1024-bit symmetric encryption?

In order to answer this question, we need to understand the basis behind all of modern cryptography, which is computational hardness. Today, we believe that we know how to construct block ciphers that are secure, except for brute force search (or almost that secure). However, we don't really know this. We also think that factoring is hard, and so on. All of these are just assumptions since we don't know how to prove significant algorithmic lower bounds for problems like this. In particular, we don't even know how to prove that $P \neq NP$, and if $P=NP$ then no block cipher will be secure. Note, by the way, that even if $P\neq NP$, this doesn't suffice for crypto (we need one-way functions, which as an assumption is equivalent to pseudorandom functions/permutations).

Coming back to your question: assume that in 100 years it has been proven that $P\neq NP$ and even that one-way functions exist. However, assume also that all problems in $NP$ can be solved in time $2^{\sqrt n}$ where $n$ is the input length. (Note that it is strongly conjectured that $NP$-hard problems cannot be solved in sub-exponential time, but this is also an assumption.) In this case, if we want security against machines running in time $2^{128}$ then we will need keys of size 16384.  Another more likely possibility (but who knows) is that all $NP$ is solvable in time $2^{n/10}$. This would require keys of size $1280$.

Is this a likely event? Do I believe that this is the case? No, I don't! But, if you are asking: will such key lengths ever be needed? Well, no one really knows and the future will tell.

Currently we set key lengths by what we know. RSA needs 2048 bit keys due to the best factoring algorithms, and likewise discrete log and DDH over $\mathbb{Z}_p^*$; ECC needs 256-bit keys since the best algorithms known take time that is a square-root of the group size; symmetric keys need to be 128 bits since the best known attacks are brute force (and when better attacks are known then we phase out the algorithm).


Partial collisions of hashes, why is this important? There's a lot of work finding "partial collisions" in hashes, and "Parallel Collision Search with Cryptanalytic Applications" seems to be the go-to paper for this work.  I'm trying to understand why finding partial collisions, particularly by brute force, is such a topic of interest. As an example, let's say we have a 256-bit hash, and the last 4 bytes are the same for two message.

Is the interest in this work just because it's a useful segue to understand how to make collision?  Is there a condition where one would truncate a longer hash that would cause a partial collision to be a problem?

This seems to boil down to whether or not anyone would have a reason to truncate a hash. The answer is yes, absolutely. For example, someone who needs a 256-bit digest may want to use SHA-512/256 instead of SHA-256 on a 64-bit processor for improved performance (the former uses 64-bit operations whereas the latter uses 32-bit operations). SHA-512/256 is nothing more than regular SHA-512 with a distinct IV, truncated to a 256-bit value. Likewise if someone wants a hash with 280 collision resistance, they would want to truncate a stronger hash like SHA-256 to 160 bits instead of using SHA-1 which has cryptographic weaknesses that allow collisions to be found faster than predicted by the birthday bound.

Another reason someone might want to truncate a Merkle–Damgård hash function is to resist length extension attacks. SHA-256 is vulnerable to them, whereas SHA-512/256 is not, despite being of the same size. An efficient collision against such a truncated hash could then be considered problematic.


Is there way to combine secrets first and later split them? Shamir's Secret Sharing allows a secret to be split into multiple shares so that it can be reconstructed later.

Is there a way to do the reverse? Can we combine a few secrets first and later split them into their original forms? More clearly: given two strings I want to "pack" them into single secret and later split them into respective strings. (I'm not sure how this would be called in literature.)

The simplest solution I could think of is concatenating all of the secrets and storing their relative positions, later string splitting them based on their positions. This would be too naive and there is no space advantage.

On the information theoretic level you can not get a shorter result than the concatenation if you want to be able to recover the original inputs: If there are $k$ shares from a set with $2^{x}$ elements (represented as $x$ bit array), an injective function requires at least $(2^{x})^k = 2^{xk}$ different function values, which requires at least $xk$ bit. If the function combining the different shares has a shorter function value, it is not injective and you can not recover the original shares.

However, since the chosen string has a specific bit representation, you might be able to work with encodings to save space, e.g. Huffman codes, etc.

You might be able to choose your common secret and shares in a way, where the shares are not compressible by much but the common secret is.


How are objects sold as NFT's ("non-fungible tokens")? I'm familiar with "blockchain" and the theory and technology behind cryptocurrencies, tokens, and the economics behind why such things are capable of having monetary value, however I've never been able to wrap my head around "non-fungible tokens" (NFTs).
As I understand it, NFTs and, say, Bitcoin are in principle one and the same. Both are units of data stored on a tamper-resistant public ledger, NFTs being special in that each "token" is "unique" in a way that Bitcoin/etc. are not. That these things can hold value makes some sense. What I don't understand is how NFTs are used to sell "physical" objects (digital art, music files, etc).
Access to the original object or file is not restricted to the owner of the token. As I understand it, the only relationship between the token and the object is that the seller decided to represent the object by the token. And then people are willing to pay absurd amounts of money to "purchase" these objects, in effect receiving only some string of numbers that the seller decided would signify ownership of the object. How is this any different from, say, purchasing some work of art at auction and being handed an ID number, never actually taking possession of the artwork.
How are objects "associated" with these tokens, outside of someone more-or-less deciding that some token will serve as an "identification number" for the object?  I admittedly don't know much about the topic, however I suspect there must be more to it than what I understand.

Usually, the NFT has no ties to the physical object. And anecdotally I have heard of many cases where an NFT represented some intellectual property, but did not come with rights, and if the owner of the NFT tried to distribute the corresponding media, then he/she would be in violation of the copyright.
One could potentially sign a contract saying, "whoever legitimately possesses this NFT has these rights," but I have never heard of that being used for a real world object or intellectual property.
Further more, the cryptographic security provided by the block chain is moot because the original creator of the NFT could create arbitrarily many NFTs for a real world object and dishonestly claim that they are the only NFT for the object.
If there is a painting I liked, and someone gave me the choice of either a corresponding NFT or a fancy looking signed certificate that says "whoever owns this certificate is the honorary (but not actual) owner of [the artwork]," I would take the certificate because I could hang it up on my wall and the physical form may give it a higher resale value.


is this possible to use asymmetric encryption schemes as order preserving encryption Are we able to use order preserving encryption in asymmetric schemes, is this work efficiently. is this secure at any one of the  situations

No, because an adversary can pick an arbitrary plaintext, encrypt it using your public key, and then compute whether his plaintext is "less than" or "greater than" the plaintext corresponding to the ciphertext he wants to decrypt. He can do this intelligently several times to "home in" on your ciphertext's corresponding plaintext using binary search, allowing him to successfully decrypt any ciphertext using only the public key and your order relation in time $O(\log n)$ where $n$ is the size of the plaintext/ciphertext space, breaking the encryption scheme.

If this isn't what you meant, please add more detail to your question, including a list of the security properties desired.


Is my protocol that uses hybrid cryptography and AES-GCM secure? I'm having a lot of trouble trying to understand how to implement AES-GCM.

My usecase: Person A sent me a file with a gauranteed unique name. I want to be assured it was from person A, and that no one saw the contents, and that it wasn't tampered with.

I figured that I would do the following:

Person A would give me a public key offline to which only they have the private key
Person A would encrypt the file with AES-GCM. They would then encrypt the AES-GCM key+nonce+aad with their private key. They would then send me two files: the cipher and the encrypted key+nonce+aad combo.
I would decrypt the key+nonce+aad with their public key, then I would decrypt the AES-GCM cipher using those values.

I figured that I would use these values:

Key: random
Nonce: file name
AAD: file name

I know this is probably a terrible way to do things. It seems overly complicated to me, but I'm not sure how else to achieve my usecase. I have no idea if these are the right values to use for the encryption/decryption, and I have no idea what should be kept secret and what shouldn't be kept secret.

Any guidance would be greatly appreciated. If it helps, it looks like the GSM encryption/decryption will happen in Python.

Typically things would go like this:

A generates a random AES key and encrypts it with the public key.
A encrypts the file contents using AES GCM and that key. Nonce can be random or even zero if the key is only used once. AAD can be empty unless something else needs to be authenticated with the file.
A sends over the encrypted key, the nonce if any, and the ciphertext.

The file name only matters if you need to encrypt it too (simplest: encrypt a tar archive instead) or if you need the name authenticated (include it in the AAD).


Simple commitment scheme using secure hash function Can I create a simple commitment scheme using a secure hash function?

If so, is concatenation with a random secret enough to preserve hiding? (i.e. $C = H( random\_string || message)$)

Thank you

Yes.
If you publish such a commitment. And you model the hash as a random function it willl not only be preimage resistant but there will be many possible pairs of random string and message which will match the commitment.
If the random string is as big as the hash output most possible message values can produce the commitment for some random string. So even an attacker with infinite compute power will not be able to consistently discover the message, while an attacker with bounded computing power won't be able to learn anything about the message.

When the commitment is revealed, we know the attacker didn't cheat because collision resistance means the committer (With bounded conputing resources) won't be able to produce a commitment which matches two distinct known messages.


Quantum algorithm encrypting classical data Are there schemes for encrypting classical ciphertext using quantum algorithms? Specifically, if a public key system exists for classical data, and classical ciphertexts, can this scheme be implemented by quantum algorithms (A quantum algorithm implementing classical public key algorithms)?

Yes, a quantum computer can implement any classical algorithm.

This can be easily proven, because quantum computers are Turing-complete. And if a computer is Turing complete then it can, by definition, run any classical algorithm:

  A universal Turing machine can be used to simulate any Turing machine and by extension the computational aspects of any possible real-world computer.

And that's - as far as I can see - QED.


Making brute force attacks less effective through obfuscation? This page on Wikipedia states

  "Brute-force attacks can be made less effective by obfuscating the
  data to be encoded making it more difficult for an attacker to
  recognize when the code has been cracked or by making the attacker do
  more work to test each guess."

This might make sense, but are there any examples of widely used encryption software doing such a thing?

Since speaking about any software is not showing anything, I'll instead on how they do it and where they do it.

This "obfuscation" is very often done when passwords come into play. There are plenty of good passwords hashing functions, that slow attacker down by "obfuscating" it, then brute-force has to use that same "obfuscation" which is designed to be slow. This is done because users will always generate weak passwords, it isn't something we can fix. But this is still futile attempt at fixing something that is inherently broken (users will always devise poor and short passwords). It is far more effective to make passwords twice as long than making "password check" take twice as long. Increasing key by ONE BIT doubles security. Increasing check time by factor of 2 doubles security.

Apart from passwords, we almost never use such "obfuscations" because they are not effective at stopping attacker. Making key double length will increase security by unimaginable factor, doubling encryption will only double security!

  If I were inventing things instead of asking questions, I would have my software do a block cipher on the plain data and append the key to the newly encrypted data. I'd have it do this at least twice, now the data would look like uniformly distributed random data (because both the key and encrypted message are), and the attacker would have to number crunch at least 1 full decryption of the message for each brute force attempt.

This would not help you. I'd simply take twice as long to decrypt your message. This is not a lot, as computing power increases very fast so at worst I'd wait a year to break your scheme. On the flip side, you would have to take twice as long to encrypt that message. We end up being hit same.

History likes to repeat itself. Germans tried to fix enigma by using more and more complex encoding schemes, it didn't help. RC4 was "fixed" by removing first X bytes, it didn't help in long run (everything before fix was compromised, everything after fix was safe for some years). It's easy to fall into pitfall of "I'll just change it a bit and it will be secure again", truth is we don't know how long it will be secure, so it's best to leave whatever is broken behind, making better, more effective algorithms.

  but they still design systems to be strong against brute force attacks, that is why people keep making keys longer.

Problem is, you are not even making key longer. Key only makes sense if increasing key by X will increase security by larger margin than X. You instead make it so that it takes two times longer for you and attacker. It doesn't make difference in long run for attacker. RSA is special case, because RSA inherently has better factoring algorithms than bruteforce, and we move away from RSA now because it's not efficient enough. If RSA got cracked however, making better algorithms, we would probably totally move away from RSA, because we couldn't make key large enough for attacker to be powerless. RSA is also far different from symmetric ciphers, because of efficiency, breakage method etc. so comparing two isn't correct.


Secondary private key that produces limited certificates I want some notion of a secondary key that behaves like this:

Given a public/private key pair, it is not the private key but rather it is once-removed from it. Like the original private key, it is also not public. Unlike it, it was made for a specific purpose (a string) and has expiration.

The secondary key can produce certificates that prove that the certificate-maker has that secondary key, that the secondary key was produced using the original private key belonging to some public key, for some purpose (a string) with expiration limit, and the token produced is within the expiration limit.

When a user which owns a private key produces a secondary key, they essentially say "I grant the carrier of this token permission to act as me for this purpose for this period of time".

What am I looking for?

Some clarification:

The bearer of the secondary key is some half-trusted code in the user's PC. It cannot carry any secrets other than the secondary key, and it uses it with other users, which are also not trustworthy, so this code cannot pass the secondary key to them, so it needs to be able to generate new certificates from it.

So in diagram it is $A \rightarrow c \rightarrow B$, meaning Alice installs some software $c$ she wants to handle her banking stuff, so she grants a secondary key to $c$ that says they can impersonate her when it comes to banking stuff for a certain amount of time. The code $c$ then interacts with some other user, Bob, producing certificates that means it represents Alice when it comes to banking.

In addition there is no external authority, so everything must be validated locally.

When a user which owns a private key produces a secondary key, they essentially say "I grant the carrier of this token permission to act as me for this purpose for this period of time".

You could use the original private key to sign that message exactly.

The original keyowner Alice signs a message encoding "The carrier of this signed message has permission to act as me (id/pubkey:XXX) with caveats A,B,C (ie. permissions to _, expires at _)", and gives that signed message to Bob. Bob can now make requests to the server and include that signed permission slip in his requests as his authorization to act as Alice.

You could then change the design to be freely re-delegatable by making the message instead be "The user identified as id/pubkey:YYY has permission to act as me (id/pubkey:XXX) and delegate with caveats ...". Alice can create a message like this specifying Bob's public key as YYY, and give the message to Bob. Bob could make requests to the server including this signed message as his authorization, but could also create his own version of this to delegate permission to Alice's account to Charlie. Bob would give Charlie this new message and Alice's original signed message. Charlie could then make requests to the server and present a chain of messages showing the delegation of permission to Alice's account from Alice to Bob to Charlie.

This final design is pretty much equivalent to Macaroons (see also the answer of cypherfox) with the bonus that anyone could verify the permission slips, not just the server. But if you don't need that, macaroons are likely to be much more compact than using asymmetric crypto.


Methods of making ASIC/GPU resistant encryption? Is there way to make encryption scheme ASIC and GPU resistant, besides using a lot of memory?

And what is there ciphers or modes of use for such purpose? Including public keys algorithms maybe too, if there is any methods for them.

Or it's only worth to defend key derivation function? (Like scrypt, but it obviously failed in the case of litecoin.)

Clarification: 'encryption scheme' is protocol and/or system using cryptography to encrypt text. It's meaning opposes single algorithm, like AES or whatever. And it should be resistant against ASIC/FPGA/GPU/crypto-hardware optimized algorithms, like brute-force, or whatever algos there is for such hardware. It should make such attack not orders faster than on standard CPU or orders more expensive.

As pointed in this comment, using a huge random key for a sound block cipher is an excellent defense to resist ASIC/GPU attacks. Each bit added doubles the effort required. If an adversary was able to build $10^{12}$ ASICs each capable of testing $10^{12}$ keys per second, odds of finding a 128-bit key by brute force running that for a decade are less than one in $10^6$. Thus 128 bits of key are good enough to resist ASIC/GPU attacks in the foreseeable future if you discount the possibility that quantum computers will become useful cryptanalytic tools; make it 256 bits if you account for that or a number of other questionable possibilities. Use this as key for a cipher without a backdoor, on a platform with no exploitable side channel: confidentiality problem solved (but neither integrity or anonymity). Fine, but:

Generating a true random secret key is non-trivial; and it is impossible to distinguish from its output that some allegedly true random generator is bad (that's for many incompetently designed/implemented generators, and any competently rigged one).
In many applications, both sides must agree on the secret key (Public Key cryptography can help that, but I won't touch key establishment or distribution here).
Real platforms have side channels, accidental or deliberate.
Typical users have great pain remembering even a 80-bit random key (roughly equivalent to learning three 8-digits phone numbers, not including prefix).

The last issue is often dealt with exclusively by key stretching (also known as password-hashing, or Password-Based Key Derivation Function; you know when a field is immature when its name has not even settled). A PBKDF turns a weak passphrase into a wider key, using as many iterations as practical of some appropriate transformation. This is when (and only when for a proper system, with the possible exception of PK crypto as used in key establishment or distribution) ASICs/FPGAs/GPUs should be a threat.

The current state of art in key-stretching is scrypt. In order to reduce the speedup obtainable at a given cost by using ASICs/FPGAs/GPUs, scrypt strives to make best use of resources available by the legitimate key stretcher with a modern CPU:

considerable memory;
multiple cores;
fast operations (addition, xor, and fixed rotations) so that software performance is not too bad.

How to improve on that is the subject of active research, and the ongoing Password Hashing Competition.


Why is "key-rotation" called key-rotation? The word "rotate" in respect to "key-rotation" has connotations of looping/repeating variable values like a rotor, but as far as I can tell there isn't a single definition available for "key-rotation" that involves re-using a key that was previously replaced.

So why don't we call it key-replacement or something else like that? i.e., why did the cryptography communities decide the more ambiguous word "rotation" was the more appropriate term to describe the act of changing keys?

It just seems a strange phrase to use, especially if you're not a native English speaker.

The only thing I could think of was some sort of an anachronism in reference to oldschool cryptographic key-generators, like the Enigma Machine, or your typical multi-rotor-combo-locks popular for use with bikes & storage lockers.

Purely speculation, but given most cipher usage historically was military, diplomatic and espionage, I wonder if it might be related to the longtime common practice of the military (certainly US, and I believe many others), and to an extent the diplomatic corps at least US, of changing the assignments of individuals to jobs, posts, or duties, and for the military of whole units to missions, on a regular schedule automatically (i.e. not requested by the people involved). This practice is usually called rotation, and a particular (limited-time) assignment is metonymically called a rotation -- e.g. a soldier might speak of 'doing a 3-month rotation in \$job1 and then being moved to \$job2'. Random example To a military comms specialist -- and their commanding officer -- the periodic, scheduled replacement of one key by another would certainly seem similar.


Adding tweak to a block cipher I know there are XEX, XTS and other ways to add tweak to block cipher without modifying cipher itself. However they are quite slow and/or complex.

If we assume we have a secure block cipher round function (like AES) with pseudo-independent round keys (generated with stream cipher). Is it safe to add tweak with same size as block directly (and same value every round) into round function the same way as round keys?

$F()$ = round function
$b$ = block
$k_r$ = round key (same size as block)
$t$ = tweak (same size as block)

$b = F(b)$
$b = b \oplus k_r \oplus t$

How strong tweak schedule should be?

This construction isn't generically secure, you need to analyze it for each blockcipher you want to use it with to see if it's secure.

For example, consider a block cipher that simply xors the key into the state between rounds. In that case your construction is equivalent to xoring the tweak into the key. This has several consequences:

Since we generally assume related and attacker controlled tweaks, this exposes the blockcipher to related key attacks. There are blockciphers which are secure with random keys, but not related keys (e.g. AES)
It enables multi-target attacks, with each tweak acting as a separate target. For example if the attacker sees a 4TiB of known plaintext, that corresponds to $2^{42-4}$ 128 bit blocks, reducing the security level of a 128 bit cipher to 90 bits.

Even if there is no direct interference between the cipher's key schedule and the tweak, the tweak gives an attacker more influence over what happens inside the cipher (assuming random keys but attacker controlled plaintext/ciphertext/tweak). To compensate for that, you need to increase the number of rounds, decreasing performance.

=> This construction might be worth a consideration when designing a new tweakable blockcipher to replace AES, but it's not something you should simply add to an existing cipher, like you can with XTS and similar constructions.


What are the benefits of the two permutation tables in DES? Why do we use a permutation table in the first step of DES algorithm and one at the end of the algorithm?

The initial and final permutation have no influence on security (they are unkeyed and can be undone by anybody). The usual explanation is that they make implementation easier in some contexts, namely a hardware circuit which receives data over a 8-bit bus: it can accumulate the bits into eight shift registers, which is more efficient (in terms of circuit area) than a single 64-bit register. This process "naturally" performs the initial permutation of DES.

In more details: Suppose that you are designing a hardware circuit which should do some encryption with DES, and receives data by blocks of 8 bits. This means that there are 8 "lines", each yielding one bit at each clock. A common device for accumulating data is a shift register: the input line plugs into a one-bit register, which itself plugs into another, which plugs into a third register, and so on. At each clock, each register receives the contents from the previous, and the first register accepts the new bit. Hence, the contents are "shifted".

With an 8-bit bus, you would need 8 shift registers, each receiving 8 bits for an input block. The first register will receive bits 1, 9, 17, 25, 33, 41, 49 and 57. The second register receives bits 2, 10, 18,... and so on. After eight clocks, you have received the complete 64-bit block and it is time to proceed with the DES algorithm itself.

If there was no initial permutation, then the first step of the first round would extract the "left half" (32 bits) which, at that point, would consist of the leftest 4 bits of each of the 8 shift registers. The "right half" would also get bits from the 8 shift registers. If you think of it as wires from the shift registers to the units which use the bits, then you end up with a bunch of wires which heavily cross each other. Crossing is doable but requires some circuit area, which is the expensive resource in hardware designs.

However, if you consider that the wires must extract the input bits and permute them as per the DES specification, you will find out that there is no crossing anymore. In other words, the accumulation of bits into the shift registers inherently performs a permutation of the bits, which is exactly the initial permutation of DES. By defining that initial permutation, the DES standard says: "well, now that you have accumulated the bits in eight shift registers, just use them in that order, that's fine".

The same thing is done again at the end of the algorithm.

Remember that DES was designed at a time when 8-bit bus where the top of the technology, and one thousand transistors were an awfully expensive amount of logic.


If we don't trust current PQ algorithms enough to use them on their own why should we trust them for a hybrid? The second question my students have asked me about PQ/Classical Hybrids is about why we think they are good for protecting information with a long security lifetime.  If we don't trust current PQ schemes enough today to use them to protect information on their own, why should we have any confidence that they would be sufficient to protect information after quantum computers have been realized?  When that happens whatever PQ scheme we used in a hybrid will be the only thing left protecting the information since the classical portion of the hybrid will have been broken.  In the long run using a hybrid scheme to protect long lived information today is equivalent to using only a post quantum algorithm in the future when quantum computers are here.  What is the rationale for choosing some PQ algorithm today and believing it will protect data in the future?

Trusting the algorithms is not a black and white issue. Given that we cannot unequivocally prove the hardness of the problems underlying basic cryptographic primitives, we have no choice but to assume that they are hard. A vast amount of effort in cryptographic research is spent on minimising these assumptions and analysing their hardness. We already have a long track record with lattice-based cryptography and hard problems in lattices. However, we have a far longer track record with problems like RSA and discrete log/Diffie-Hellman assumptions. As such, we have more "trust" in them. Furthermore, key lengths is tricky, and although certain problems may indeed be very hard, understanding how hard they are is crucial for setting key lengths. (This is why Elliptic curve keys can be 256 bits vs RSA key that have be 2048 bits at the very minimum.) With lattice and other assumptions used for PQC, we have less experience with this.

So, we have no reason whatsoever to believe that lattice-based or other PQ proposals will not be good enough in the long term if quantum computers at scale are ever built. However, we also have less history with these assumptions, and the prudent and conservative approach is to take both (with hybrid encryption). As time goes on, we will learn more and more about the lattice and other assumptions, and will feel more comfortable about using them by themselves.


Best way to reduce chance of hash collisions: Multiple hashes, or larger hash? I would like to maintain a list of unique data blocks (up to 1MiB in size), using the SHA-256 hash of the block as the key in the index. Obviously there is a chance of hash collisions, so what is the best way of reducing that risk? If I also calculate the (e.g.) MD-5 hash of the block, and use the combination (SHA-256, MD-5) as the key, is the chance of a collision about the same as some 384-bit hash function, or is it a little bit better because I'm using different hash functions?

Thanks for the info!

Edit: My blocks come from normal user data on hard drives, but it will be many petabytes in total.

Edit2: As a follow-up (just tell me if this should be moved to a different question): Since the blocks can vary in size but can be up to some preconfigured limit (e.g. 1MiB), how will collision resistance be affected if I make the (64-bit) size of the block part of the key? That way you can only have collisions of blocks with the same size...

The risk of collision is only theoretical; it will not happen in practice. Time spent worrying about such a risk of collision is time wasted. Consider that even if you have $2^{90}$ 1MB blocks (that's a billion of billions of billions of blocks -- stored on 1TB hard disks, the disks would make a pile as large of the USA and several kilometers high), risks of having a collision are lower than $2^{-76}$. On the other hand, the risks of being mauled by a gorilla escaped from a zoo are at least $2^{-60}$ per day, i.e. 65000 times more probable than the SHA-256 collision over way more blocks than possibly makes sense. Stated otherwise, before hitting a single collision, you can expect the visit from 65000 successive murderous gorillas. So if you know what's good for you, drop that MD5 and go buy a shotgun.

Now for the suggestion of concatenating the outputs of two distinct hash functions, say SHA-256 and MD5. It turns out that this does not enhance security as much as one could believe. The total size of 384 bits would certainly not provide more security against collisions that what a 384-bit hash function would give; but it actually is much weaker than that: it would not be really much stronger than SHA-256 alone. See this previous question, and this research article for the gory details. This can be summed up as follows: when using several hash functions in parallel and concatenating the outputs, the total is not stronger against collisions than the strongest of the individual functions.

And, of course, MD5 itself is weak against collisions and as such should not be envisioned for newer designs.


Description of signatures with message recovery (as in ISO/IEC 9796-2 and EMV Signatures) I'd like to get an overview of how the signatures with message recovery work, especially in case EMV and other smart card systems. Is there a nice overview available without being required to read the whole ISO/IEC 9796-2?

I've already had a look at the “Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures” paper… but there, only the encoding function was listed and I couldn't really understand how the signature is verified and recovered. Thanks!

Informally, a signature scheme with message recovery is one where some or all of the message is embedded in the signature. That can reduce the size of the signed message, sometime by a proportion approaching 2, e.g. for RSA public-key certificates.
Common practice: Signature scheme with appendix

Space saver: Signature scheme with total message recovery

Best of both worlds: Signature scheme with partial message recovery

$$\begin{array}{ll}
\mathsf{Gen},\mathsf{Sign},\mathsf{Ver}&\text{Key generation, signature, verification algorithms.}\\
\operatorname{Pub}, \operatorname{Priv}&\text{Public and private keys (bitsrings).}\\
M_r&\text{‘Recoverable’ message.}\\
M'_r&\text{‘Recovered’ message, equal to }M_r\text{ on successful verification.}\\
M_n&\text{‘Non-recoverable’ message, equivalently ‘clear’ or ‘visible’.}\\
S&\text{Signature.}\\
\end{array}$$
A signature scheme with total message recovery [some sources make total implicit, e.g. the HAC section 11.2.3] can be formally defined as three functions [easily computable, with a compact and public definition]:

a key generation function

with inputs

some parameters (in particular for key size)
a random bitstring,

with output a public/private key pair $(K_\text{pub},K_\text{priv})$,

a signature function $\mathcal S$

with inputs

same parameters
$K_\text{priv}$ obtained from the output of the key generation function
any message $M$ in some large subset $\mathbb M$ of the set of bitstrings $\{0,1\}^*$
an (optional) random bitstring [that is used in ISO/IEC 9796-2 scheme 2]

with output a bitstring designated as the signed message $S=\mathcal S_{K_\text{priv}}(M)$,

a verification function $\mathcal V$

with inputs

same parameters
$K_\text{pub}$ obtained from the output of the key generation function
any bitstring $S\in\{0,1\}^*$

with output a pair $(b,M)=\mathcal V_{K_\text{pub}}(S)$ with

$b$ a boolean, either $\text{false}$ [bad signature] or $\text{true}$ [good signature]
a bitstring $M$

such that for all parameters and random seed(s), $\forall M\in\mathcal M, V_{K_\text{pub}}(S_{K_\text{priv}}(M))=(\text{true},M)$.
A signature scheme with total message recovery is defined to be existentially secure [or equivalently: secure in a chosen-messages setup] if a computationally bounded adversary, given $K_\text{pub}$ and access to an oracle producing $S_{K_\text{priv}}(M)$ when given any $M\in\mathbb M$, can not with sizable odds exhibit $S\in\{0,1\}^*$ with $V_{K_\text{pub}}(S)=(\text{true},M)$, and such that the oracle was not queried with $M$.
Notice that in a signature scheme with total message recovery, $M$ is an output of the message verification function; when it is an input in a signature scheme with appendix. Recovering $M$ from the signed message $S$ requires evaluating $\mathcal V_{K_\text{pub}}(S)$, and in particular knowledge of $K_\text{pub}$.

For $k$-bit security, the size of signature and message must obey $|M|\le|S|-k$ (for odds of success of a trivial adversary not querying the oracle and trying $S$ at random are at least $2^{|M|-|S|}$, assuming $|S|$ is fixed for a given $|M|$ and all messages of size $|M|$ can be signed).
Some schemes also offer partial message recovery : signature generation breaks the message $M$ into $M_r$ and $M_n$ in a public, scheme-defined manner, with $|M|=|M_r|+|M_n|$; it is assumed that $M_n$ [the non-recoverable part] is made an additional input of the signature verification function (as in signature with appendix); while $M_r$ [the recoverable part] replaces $M$ in the output of the verification function, which becomes $(b,M_r)$.
The correctness requirement becomes that for all parameters and random seed(s), $\forall M\in\mathcal M, V_{K_\text{pub}}(S_{K_\text{priv}}(M),M_n)=(\text{true},M_r)$, where $M_r$ and $M_n$ are extracted from $M$ in a prescribed manner, and can be recombined into $M$.
The security requirement becomes that a computationally bounded adversary, given $K_\text{pub}$ and access to an oracle producing $S_{K_\text{priv}}(M)$ when given any $M\in\mathbb M$, can not with sizable odds exhibit $M_n$ and $S\in\{0,1\}^*$ with $V_{K_\text{pub}}(S,M_n)=(\text{true},M_r)$, and such that the oracle was not queried with $M$ obtained by recombining $M_r$ and $M_n$.
Typically, $|S|$ is fixed for a given public key, but independent of $|M|$; and $|M_n|=0$ for $|M|$ below some threshold. For $k$-bit security, $|M_r|\le|S|-k$ must hold, or equivalently $|M_n|\ge|M|-|S|+k$

The first standard message scheme with message recovery was ISO/IEC 9796:1991 [later renamed ISO/IEC 9796-1, but never approved under this name]. It did not use a hash, because standard hashes where then a novelty. It featured only total message recovery, and had the constraint $|M|\le|S|/2$ (within a few bits). It was broken in a chosen-messages setup [first within 1 bit; then fully but with many messages; then with another attack that obtains the signature of $k$ extra messages from that of $k+2$ chosen other messages for most practical arguments]; and was withdrawn in 2000.
The second standard message scheme was ISO/IEC 9796-2:1997, now known as scheme 1 of ISO/IEC 9796-2. It improves on ISO/IEC 9796:1991 by using a hash, which allows a more compact signed message, and partial message recovery. Scheme 1 of ISO/IEC 9796-2 was broken in a chosen-messages setup [the best known attack is that in the paper (alternate link) noted in the question], but remains secure in practice when the adversary is restricted to obtaining signature of messages not specifically constructed to enable an attack. ISO/IEC 9796-2:2002 enforced a minimum hash width of $h=160$ as a mitigating measure, added schemes 2 and 3 intended to fix security for good, defined the so-called alternative signature production and opening functions that practice demanded, and included as normative the previously informative non-alternative signature production and opening functions. Amendment 1:2008 to ISO/IEC 9796-2:2002 added an ASN.1 module. ISO/IEC 9796-2:2010 makes only purely editorial changes AFAIK, beyond consolidating that amendment.
In ISO/IEC 9796-2, the message $M$ to be signed is subdivided as $M=M_r\|M_n$. The recoverable part $M_r$ is at the beginning of the message, of some maximum size determined by the parameters; it is transmitted embedded into the signature $S$, which has size fixed by public key parameters. The non-recoverable part $M_n$ is empty for short $M$ [and always a byte-string even when $M$ is not, thus $|M_r|\equiv|M|\pmod 8$]; $M_n$ is often transmitted unmodified along the signed message, but could be implicit in whole or in part (e.g. a version number). When $M_n$ is empty [resp. non-empty], the scheme operates in total [resp. partial] recovery mode.
Scheme 1 of ISO/IEC 9796-2 is deterministic. For signature, a message representative is formed by concatenating prescribed padding, $M_r$, the hash of the whole message $M$, and other prescribed padding; the underlying [RSA-like] private-key function is then applied to obtain the signature, which is about the size of the public modulus. For verification of the signature and message recovery, after preliminary checks, the underlying public-key function is applied; the padding in that result is checked; the recovered $M_r$ is extracted from that result; and the hash extracted from that result is compared to the hash of the message reconstructed from the recovered $M_r$ and, for partial message recovery, the non-recovered $M_n$ obtained by other means.
I refer to EMV 4.3, Book 2, Annex A2.1, for a detailed exposition of ISO/IEC 9796-2 scheme 1, restricted to $n\equiv m\equiv 0\pmod 8$, SHA-1 (thus $h=160$), implicit hash identifier, $m\gt n+176$ [that is partial message recovery], and the so-called alternative signature production and opening functions RSASP1 and RSAVP1 in PKCS#1. This parameterization is common in Smart Cards, and directly supported [including with total message recovery] by Java Card 2.2.x/Classic.
Scheme 2 of ISO/IEC 9796-2 is randomized [and correspondingly has the signed message larger than scheme 1 in many use cases], with a security argument resembling that of RSASSA-PSS of PKCS#1, applicable including in a chosen-messages setup. Scheme 3 is a special case of scheme 2 with the random bitstring reduced to empty. The split of message into recoverable and non-recoverable portions is such that scheme 3 can be used as functional equivalent to scheme 1 with restored security in a chosen-messages setup [although I know no formal security argument].
Assuming an $n$-bit public modulus, when sending an $m$-bit message and its signature, the signed message of ISO/IEC 9796-2 schemes 1 or 3 has about $\min(n,m+h+16)$ bits where $h$ is the width of a hash [SHA-1 is popular, giving $h=160$]. This allows a significant [at least when considering proportion] size saving for messages with $m$ commensurate to $n$, such as public-key certificates [compare to $m+n$ bits using the schemes in PKCS#1]. For example: with $n=1984$, $h=160$, $m=2000$ [250 bytes], the signed message may use $2176$ bits [272 bytes, rather than 498 bytes with PKCS#1]: $1984$ bits [248 bytes] for the RSA cryptogram, conveying $1808$ useful bits [226 bytes] forming the recoverable part of the message; and $192$ bits [24 bytes] forming the non-recoverable part of the message.
ISO/IEC 9796-2 has a maze of features and parameters: three schemes; many hashes; optional hash identifier [intended to allow interoperability in contexts where the signer decides which hash is used, without requiring guesswork on the verifier side]; modulus of size not multiple of 8; messages of size not multiple of 8 when the hash allows; total or partial message recovery; either RSA or Rabin signature scheme [an analog with even public exponent]; and two slightly different options of RSA signature production and opening functions: those not designated as alternative sign as $x\mapsto \min(x^d\bmod N, N-(x^d\bmod N))$ which saves one bit over the alternative: PKCS#1's RSASP1. EMV originally referred to ISO/IEC 9796-2:1997, but only uses partial message recovery, the alternative functions not alluded to in this standard, and now refers to ISO/IEC 9796-2:2010 without stating the scheme, functions, or other options. The European Digital Tachograph [annex 1B, appendix 11] does just as EMV when it refers to ISO/IEC 9796-2 in a signature context for certificates, but also refers to ISO/IEC 9796-2 in its authentication and key agreement scheme where it uses scheme 1 with total message recovery [thus different padding than EMV] and the non-alternative signature production and opening functions of that standard [because that enables re-encryption of the signature using a different private key with the same modulus size as the signature key, regardless of which modulus is smaller].
ISO/IEC 9796:1991, ISO/IEC 9796-2, and EMSR3 of P1363a (similar to ISO/IEC 9796-2) use RSA or Rabin as the underlying public-key cryposystem. There's also ISO/IEC 9796-3, the similar EMSR1, and EMSR2, that use the Discrete Logarithm (possibly over an Elliptic Curve group).

Regarding the note in ISO/IEC 9796-2:2010 quoted in that comment to the question:

For practical purposes, an application may wish to structure the message $M$ to ensure that data it wants to be explicitly stored or transmitted (e.g., address information) is allocated to the non-recoverable message part $M_n$

That's intended to draw attention to the fact that only the non-recoverable part of the signed message [if any] is intelligible before verification of the signature. As a consequence, information that needs to be readily available before or absent signature verification is better placed in that non-recoverable part of the message, rather than in the recoverable part.
As a real-life illustration: contrary to the recommendation in this note, in the aforementioned European Digital Tachograph specification, the message in a certificate [defined by Annex 1B, appendix 11, 3.3.1 CSM_017] has the identification [designated CAR] of the public key of the authority that produced that certificate placed near the beginning, thus in the recoverable part of the message, thus unintelligible before signature verification, which can be a problem to decide which public key is appropriate to verify that certificate, absent context. To avoid this, a copy of CAR, designated X.CAR, was appended at the end of the signed certificate [defined in 3.3.2 CSM_018], allowing not reading the certification authority's certificate if it is already known and its public key cached, and giving a chance to know what allegedly generated a certificate even if it fails to verify. That complication increases the certificate size by 8 bytes, and creates confusion about if an hypothetical certificate with its X.CAR not matching CAR is deemed valid, and what/who is deemed to have generated it; that could have been avoided if CAR had been at the end of the certificate data, thus in the non-recoverable portion.


Is SSH public key authentication weakened by 'none' cipher? As far as I know, SSH2 first does a key exchange based on the server host key and brings up transport authentication and encryption derived from this kex. The real authentication (password or public key) is done over this secure transport.

If you set the cipher to 'none', you wouldn't want to allow password authentication because then the password would be sent in plaintext. But what about public key authentication?

I believe pubkey auth works by the server sending a nonce to the client, the client signing it with its private key, and the server verifying the signature. How is the overall system weakened if this exchange happens in the clear?

I can think of at least:

known-plaintext (passively capture (nonce, $D_k(nonce)$) and try to derive k)
chosen-ciphertext (intercept and replace the nonce, capture $D_k(chosen)$)

Is RSA (specifically, the way it's used by the raw SSH public key authentication) vulnerable to either of these?

Edit: my original formulation was incorrect: RSA signs by decryption, not encryption. Which points to an attack on textbook RSA: How does a chosen plaintext attack on RSA work? but NOT on the RSA used in practice in SSH and SSL. PKCS#1 padding protects against this attack.

It is critical to combine both the key exchange and the secure channel, otherwise someone can mount a man-in-the-middle attack.

The way we prevent a man-in-the-middle attack is to do a key exchange, to exchange a session key that both endpoints know but no one else (including the man-in-the-middle) can know, and then authenticate both endpoints.  You seem to suggest that we remove the encryption, remove the secure channel, don't bother negotiating a session key.  If we did that, then the protocol would become vulnerable to man-in-the-middle attacks (active attacks), because nothing binds the signature/authentication phase to the rest of the stuff sent over the SSH channel.