Is there any research about cryptography on nondeterministic Turing machines? I know it's a highly theoretical topic, but I was wondering if there was any research out there about what cryptography would be like assuming that we had access to nondeterministic Turing machines.

It seems to me like you couldn't have the kind of exponential hardness assumptions that we currently have, but the Time Heirarchy Theorem states that we can create functions that require $O(n^k)$ operations for any arbitrary k, which seems like it's almost as good.

Summary. The short answer is: Cryptography would be insecure.  Any encryption you can do with a non-deterministic algorithm, can be broken (in approximately the same running time) by another non-deterministic algorithm.

Non-determinism is extremely powerful.  If you give everyone access to non-determinism, then secure encryption becomes impossible: the cryptanalysts win.

The Time Hierarchy Theorem isn't relevant here.  Roughly speaking, it says that we can make encryption take as long as we want.  However, that's not the relevant question.  The relevant question is the ratio between the time it takes to break a cryptosystem, divided by the time it takes for legitimate participants to use this cryptosystem.  If you give everyone access to non-determinism, this ratio becomes approximately 1.  You can use the Time Hierarchy Theorem to make encryption take twice as long, and then cryptanalysis will take twice as long, but that doesn't really buy you anything: if an attacker can break the encryption as quickly as you can encrypt, you have no security.

This might be counter-intuitive, but hey, that's non-determinism for ya: it's not exactly an intuitive subject.  I'll work out the technical details below for those interested, but I wanted to start with this summary of the bottom line.

Caveat: my answer is limited solely to encryption beyond the unicity distance (i.e., computational cryptography).  The one-time pad remains information-theoretically secure, if you give everyone access to non-determinism: but that's not very helpful, as the one-time pad is not practical to use in most real-life situations.  If we're not in the information-theoretic realm -- if the total amount of plaintext to be encrypted under a single key is much larger than the length of the key -- you are hosed; anything you do, will be breakable.

Intuition. Before diving into the technical details, let me give a crude analogy, for those who prefer to avoid the technical stuff.  In some really loose way, giving Eve access to non-deterministic computation is like giving Eve the power to read minds.

Suppose we live in a world where everyone can read everyone else's mind.  In a society of telepaths, is secure encryption possible?  No, it's not possible.  No matter what crazy stuff Alice does to encrypt her messages to Bob, it'll always be possible for Eve to read Bob's mind and extract the decryption key (or extract all bits necessary to decrypt).  Consequently, in a world of telepaths, encryption as we are familiar with becomes impossible.

What does non-determinism have to do with reading minds?  Well, suppose we think that every person's observable behavior is a known (or knowable) function of their internal brain state (or sequence of brain states).  Imagine that we observe Zach for a long time.  And, suppose we think that, for any set of observed behavior, there's only a single set of brain states that could have given rise to that behavior.  Then a non-deterministic algorithm can infer Zach's brain states based upon Zach's observed behavior, merely by guessing Zach's brain state and checking whether it is consistent with Zach's observed behavior.  In other words, in some really loose sense, a non-deterministic algorithm can read Zach's mind, based upon his observed behavior.  Here Zach's brain state is sorta like the key and other hidden intermediate values/choice bits used by the encryption or decryption algorithm, and Zach's observed behavior is sorta like the set of messages and ciphertexts produced by the encryption scheme.  "Reading Zach's mind" is kinda like recovering the key and hidden non-deterministic bits/intermediate values used during encryption or decryption.  The restriction that there's only a single set of brain states that are consistent with Zach's observed behavior is roughly analogous to the criteria that we are working with computational cryptography, i.e., beyond the unicity distance.

Now keep in mind that this is an extremely loose analogy.  Please don't take it very seriously, and please don't try to draw too many conclusions from it.  I know it is full of holes and can be criticized in all sorts of ways.  It is only intended for those who don't want to read the technical details and are willing to take it on faith that I know what I'm talking about, and want some gist of the idea without getting overwhelmed with the mathematics.  If you start criticizing my analogy, I will have no sympathy whatsoever: I'm just going point you to the mathematics, below.

The technical details. OK, for those who want to see me spell out the justification for my claims in detail, let's dive into the mathematics.

Let's start with a definition of what it means for a non-deterministic algorithm $A$ to compute some value.  We say that $A$ can yield output $y$ on input $x$ if, when you run $A$ on the input $x$, there exists some execution where $A$ accepts and outputs $y$.

Equivalently, you can think of $A$ as a deterministic algorithm $A_\text{det}$ with a side input $w$ to represent the choice bits used along the way (every place where $A$ makes a non-deterministic choice between two possibilities, it reads the next choice bit from $w$ and uses that to make the choice).  Then, $A$ can yield output $y$ on input $x$ if there exists some $w$ such that $A_\text{det}(x;w)=(\text{accept},y)$.  This formulation is easier to think about it, because it relates only to deterministic algorithms.

What about encryption and decryption?  Suppose we have non-deterministic encryption and decryption algorithms $E,D$.  Recall that for decryption to be correct, we need the decryption of an encrypted message to always return the original message.  In other words, if $E(k,m)$ can yield output $c$, and if $D(k,c)$ can yield output $m'$, then we must have $m=m'$.  One consequence is that if we fix a ciphertext $c$ and a key $k$, then there is a single unique message $m$ such that $D(k,c)$ can yield output $m$.  In other words, if we fix $c,k$ where $c$ is an encryption of $m$, then for every $w$ such that $D_\text{det}(k,c;w)=(\text{accept},\text{something})$, we in fact have $D_\text{det}(k,c;w)=(\text{accept},m)$.

What does it mean to be beyond the unicity distance, i.e., that the total lengths of the messages are much longer than the key length?  One consequence is that, if we have a set of known-plaintext/ciphertext pairs $(m_1,c_1),\dots,(m_n,c_n)$ where the sum of lengths of the $m_i$'s is much longer than the key $k$, then there is only a single key that is consistent with all of these pairs.  In other words, there is only a single key $k$ such that $D(k,c_i)=m_i$ for all $i$.  (OK, technically speaking, there might be multiple such keys, but they'll all be "equivalent", in the sense that if you have multiple keys $k,k'$ that are consistent, then they both decrypt most other messages the same way, so recovering either one counts as a "win" for Eve: either one will let Eve decrypt most of the other ciphertexts she sees.  That's a bit of a technical minutae detail which isn't really important here, and which is not specific to anything about non-determinism: it arises in the deterministic setting too.  We can safely ignore it, knowing that it can be fixed up if strictly needed.)  Nothing about this changes in the presence of non-determinism.

These are all preliminaries and set-up.  Now let's get to the proof of the claim I made in the summary.  Suppose Eve has $n$ known plaintext/ciphertext pairs, $(m_1,c_1),\dots,(m_n,c_n)$.  Here is an attack Eve can use:

Eve guesses the key $k$.
For $i=1,\dots,n$, Eve runs the decryption algorithm to compute $D(k,c_i)$ and checks whether $D(k,c_i)=m_i$.  Note that if the decryption algorithm is non-deterministic, this involves Eve making additional guesses for each $i$ (whatever guesses the decryption algorithm calls for you to make).
If there is any $i$ for which $D(k,c_i)\ne m_i$, Eve rejects.  Otherwise, Eve accepts and outputs $k$.

If you prefer to see the determinized version of this algorithm, it works like this.  $\text{Eve}_\text{det}((m_1,c_1),\dots,(m_n,c_n);w)$ is the following:

Parse $w$ as the concatenation $(w_0,w_1,w_2,\dots,w_n)$, where the length of $w_0$ matches the length of the key $k$ and the length of each $w_i$ matches the number of choice bits made during decryption.
Set $k=w_0$  (this corresponds to "guessing" the key $k$).
For $i=1,\dots,n$, run $D_\text{det}(k,c_i;w_i)$ and checks whether $D_\text{det}(k,c_i;w_i)=(\text{accept},m_i)$.
If there is any $i$ for which $D_\text{det}(k,c_i;w_i)\ne (\text{accept},m_i)$, output $\text{reject}$.  Otherwise, output $(\text{accept},k)$.

Notice that $\text{Eve}_\text{det}$ is a deterministic algorithm; it's the equivalent of the non-deterministic algorithm for Eve I gave above.  Eve breaks the cipher if her algorithm accepts and outputs the correct key.  In other words,  Eve breaks the cipher if there exists some $w$ where $\text{Eve}_\text{det}((m_1,c_1),\dots,(m_n,c_n);w)$ accepts and for every $w$ where $\text{Eve}_\text{det}((m_1,c_1),\dots,(m_n,c_n);w)$ accepts, $\text{Eve}_\text{det}((m_1,c_1),\dots,(m_n,c_n);w)=(\text{accept},k)$.

So, does this attack work?  Certainly $k$ is one possible output of the non-deterministic algorithm for Eve; that much is easy to see.  Is it possible that Eve could accept and output some incorrect key $k'$ (where $k'\ne k$)?  No, that's not possible, by my discussion about the unicity distance.  Remember, there's only a single key $k$ that is consistent with all of the $(m_i,c_i)$ pairs.  Also, remember that decryption is correct: given a fixed key and a fixed ciphertext, there's only a single message the decryption algorithm can output (it's not the case that there are multiple possible decryptions).  So, if Eve happens to guess some other incorrect key $k'$, then there will be some known plaintext/ciphertext pair $(m_i,c_i)$ where $D(k',c_i)$ outputs $m'$ where $m'\ne m_i$.  This means that Eve will reject on all execution traces where she guessed that the key was $k'$.

Consequently, we are guaranteed that Eve's algorithm will output the correct key $k$.  And, $k$ is the only thing that her algorithm can output; she'll never output an incorrect key on any accepting execution.  So, Eve breaks the encryption scheme.  The only facts I used about the encryption scheme are that decryption is correct and that we're beyond the unicity distance, so this break is general.

Parting thoughts on the technical details. Phew.  That's a mouthful.  I expect that very few folks have followed to this point.  Let me just give a little bit of intuition about this proof.  I've basically just mimicked the standard proof that any polynomial-time encryption scheme can be broken using an $NP$ algorithm (i.e., non-determinism suffices to break any standard, deterministic encryption algorithm), but making small adjustments to account for the fact that now we want to allow the encryption/decryption scheme to be non-deterministic.  It turns out that this doesn't change anything important.

Let me share with you one more analogy.  The standard way of defining $NP$ is: a language $L$ is in $NP$ if there is a polynomial-time non-deterministic algorithm that recognizes $L$.  Alternatively, we can define $NP$ without reference to non-determinism: roughly, $NP$ is the set of problems where solutions can be recognized in deterministic polynomial time.  Slightly more precisely, a language $L$ is in $NP$ if there is a polynomial-time deterministic algorithm $V$ such that $x\in L$ if and only if there exists $w$ such that $V(x;w)=\text{true}$; we say that $w$ is a witness or proof to $x$ being in $L$, and the verifier $V$'s job is to check the validity of the proof.

What if we were to generalize the latter notion, to talk about the set of problems where solutions can be recognized in non-deterministic polynomial time?  In other words, what if we defined a complexity class just like $NP$, except where now $V$ is allowed to be a non-deterministic algorithm (so you get to use non-determinism in checking the proof)?  Here's the cute answer: what you get is no larger than $NP$; you get exactly $NP$.

The connection to cryptography is that verifying you've broken the cryptosystem correctly (verifying that you have the correct key) is analogous to the role of the verifier $V$ in the definition of $NP$.  Even if you allow encryption and decryption to be polynomial-time non-deterministic algorithms (corresponding to allowing $V$ to be a polynomial-time non-deterministic algorithm), non-determinism still suffices to break everything (corresponding to the fact that $NP$ is still enough to recover all the corresponding languages).  OK, I realize that maybe this didn't help at all.....


Homemade Randomized RSA Considering the following encryption scheme where RSA is used to encrypt a plaintext m and then we choose a random r and compute: $$A = r + m^e \bmod N$$  and $$B = r^e \bmod N$$ So the ciphertext is a pair: $$(A,B)$$ and to recover m we compute: $$m = (B^d - A)^d \bmod N$$ IMHO This scheme has not randomized encryption since this padding approach is wrong, but i cannot figure out why. Can anyone give me a little hint?

Spartacus: Maybe i came out with the solution, since the cryptosystem described above is not CCA-secure, an adversary A can intercept (A,B) and compute a new ciphertext $$C = 2B\bmod N = 2^er^e \bmod N$$ Since he's carring out a CCA-attack he has access to a decryption oracle and since: $$C\neq B$$ the oracle output $$RSA^{-1}(C) = 2^{ed}r^{ed}\bmod N = 2r\bmod N$$ So he can simply recover r by half of computed plaintext, and computing r - A he obtains the deterministic encryption of the message. Is it right?
Artjom-B: You forgot something $2^eB\bmod N=2^er^e\bmod N$. I don't think this is complete, because the decryption oracle would decrypt $(A,C)$ and not $C$ alone.
Spartacus: Maybe it's true but by definition i can't query a decryption oracle with original challenge ciphertext A. If it were possibile we got zero chance of getting a CCA-secure cryptosystem
SEJPM: Hint1: This scheme isn't even IND-CPA secure. Hint2: What Henrick said. Hint 3: Given $(A,B,m,e,N)$, can you somehow recover $r$, possibly using A and m somehow?

Okay, let's prove that the scheme is not IND-CPA secure:

An adversary A outputs two messages $m_0,m_1$.
A uniform bit $b$ is chosen $b \leftarrow \{0,1\}$ and then the challenge ciphertext $C$ is computed as follows: $$ A = r + m_b^e \bmod N$$ $$B = r^e \bmod N.$$
The pair $(A,B)$ is output to the adversary A.
Before guessing the value of $b$ the adversary A still has access to the public key, so he can compute the two deterministic encryptions of $m_0$ and $m_1$ as follows: $$C_0 = m_0^e \bmod N $$ $$C_1 = m_1^e \bmod N$$.
Now he can compute the two possible plaintext values of r as follow  $$P_r^1 = A - C_0 $$ $$P_r^2 = A - C_1.$$
A doesn't know yet which of the two possible computed plaintext values was used, but he has the ciphertext of the right one and the public key, so he computes $$ C_r^1 = (P_r^1)^e \bmod N$$ $$ C_r^2 = (P_r^2)^e \bmod N.$$
Now he can simply compare the ciphertexts as follows:
if $C_r^1 = B$ then use $P_r^1 $, else use $P_r^2 $.
Let $P_r^k$ be the chosen value. Now the adversary can simply compute the deterministic encryption of the challenge ciphertext $C$: $$ C_d = A - P_r^k \bmod N.$$
Now it's easy guess the value of $b$: if $C_d = C_0$ then $b'=0$, else $b'=1$.

So the probability that A output $b'=b$ is equal to $1$; the encryption scheme is not IND-CPA secure.


What is the relation between RSA & Fermat's little theorem? I came across this while refreshing my cryptography brain cells.

From the RSA algorithm I understand that it somehow depends on the fact that, given a large number (A) it is computationally impossible to derive at the two prime numbers (B & C) whose product it is.

But that isn't the Fermat Theorem, is it?
It's something on the lines of showing that there is no solution $n$ ($n > 2$) such that: $X^n + Y^n = Z^n$.

Can someone throw some light on this?

To walk you through RSA from start to end, here's how it works.

Choose two large distinct primes $p$, $q$. Calculate $n=pq$.
Calculate $\phi(pq)$. This happens to be $(p-1)(q-1)$.
Choose $e$ such that $gcd(e, \phi(pq)) = 1$ and $1 < e < \phi(pq)$.
Compute $d$ such that $de = 1 \mod \phi(pq)$.
Do some crypto; $c = t^e \mod n$ and $t = c^d \mod n$.

What you really want to know is why these statements hold. Fermat's little theorem states that $a^p = a \mod(p)$ An alternative, equivalent definition is that $a^{p-1} = 1 \mod(p)$.

Actually, for the purposes of RSA, that's insufficient. What you want is a generalisation called the Euler-Fermat generalisation, which states:

$$a^{\phi(n)} = 1 \mod{n}$$
Next up - what the hell is this $\phi(x)$ function? In plain English, it's the number of numbers less than or equal to $x$ which are also coprime to it. For any given prime $p$, every number less than itself is coprime to it, which means $\phi(p) = p-1$. If you're wondering about why $\phi(1) = 1$, well, $gcd(x, 1) = 1$ is the definition of coprimality, including for 1 itself.

Now, it's also possible to prove that $\phi(xy) = \phi(x)\phi(y)$. Unless someone really wants me to, I'll skip the details (see a textbook on number theory) but, this essentially means $n = pq \Rightarrow \phi(n)=\phi(p)\phi(q) \Rightarrow \phi(n)=(p-1)(q-1)$.

Now, a little group theory too. Multiplication for certain sets of positive integers forms a group under modulo provided all the elements you pick for it are coprime to the modulo you're using. It so happens we've picked $e$ to be co-prime to our modulo $\phi(pq)$. Group theory guarantees us the existence of an integer in the group that acts as an inverse uniquely for that integer and transforms, under multiplication, that integer to the identity. The identity element under multiplication is $1$ and the inverse here is $d$.

So, let's recap: we've got $e$ and we've got $d$. One is the inverse of the other under the group $\phi(n)$. What we need is a link back to the Euler Fermat generalisation showing this:

$$ t = ((t^e)^d) = t^{ed} \mod (n) $$

So, before we do that let's just review what we understand by congruences. If I have the number $4 \mod (9)$, are you happy that $13 = 4 \mod(9)$? And that $22 = 4 \mod 9$? And that $31 = 4 \mod (9)$? You should see a patter emerging here; in fact, your general representation in this case is $4 + 9k$ generates you the set of numbers that are equivalent to $4$ modulo $9$.

So, $de = 1 \mod \phi(pq)$ could be expressed as $de = 1 + k\phi(pq)$, yes? I.e. to 1, I can add multiples of $\phi(pq)$ then apply modulo $phi(pq)$ and it'll be equivalent to 1.
This might take some getting your head around.

Once you've got there, $t^{ed} = t^{1+k\phi(pq)} \mod (pq)$. All I've done is substitute one expression for the other; no magic. Now a little re-arranging: $t^{1+k\phi(pq)} = t^1 t^{k\phi(pq)} \mod (pq)$ then $t^{1}t^{k\phi(pq)} = t^1 (t^{\phi(pq)})^k \mod (pq)$.

Now, we use the Euler-Fermat generalisation. Notice we have $t^{\phi(pq)} \mod (pq)$. Being "under modulo", we can still evaluate this, since the power to the $k$ simply means multiplying $k$ lots of that expression together. So now, apply the theorem:

$$t^{\phi(pq)} = 1 \mod (pq)$$

and we're left with $t^1 (t^{\phi(pq)})^k = t^1 \times (1)^k \mod (pq)$, which as you probably know is just $t$.

So, that is how they relate. This isn't the only way to prove RSA either. The Chinese Remainder Theorem proof I think is nicer, but I also think it is harder to understand.


Can a 3rd party decrypt static Diffie Hellman? Do cipher suites that use static Diffie Hellman (not Ephemeral) allow for the same 3rd party decryption ability as RSA cipher suites?

With RSA key exchange, 3rd parties can gain possession of the plaintext random numbers that flowed in the Client and Server Hello records.

If also in possession of the server's private RSA key, they can decrypt the pre-master secret in the Client Key Exchange, and therefore derive the same master secret and symmetric keys as the client and server.

Building on this question and the general Wireshark documents around DH, I am wondering if static DH allows for the same sequence of 3rd party decryption as RSA?

Is it only the DHE key exchanges that block 3rd parties from performing the above steps, thanks to there being no long-lived key to share with them?

Existing questions and documentation only seem to concern Ephemeral rather than Static DH.

I am wondering if static DH allows for the same sequence of 3rd party decryption as RSA?

Yes, if a third party learns the server's (or the client's) DH private value, they can recover the DH shared secret, and thus recover the premaster secret, the master secret and thus the traffic keys.

This is true for both static and ephemeral DH.  Of course, with ephemeral DH, both sides are supposed to discard their private values immediately after using it (and thus the window of opportunity for the attacker is less).  With static DH, this is obviously not possible (as the server will use the same DH private value for the next negotiation).


How can the identity $\textbf{Pr}[\textbf{y}=y|\textbf{x}=x] = \sum_{\lbrace K:x=d_K(y)\rbrace}\textbf{Pr}[\textbf{K}=K]$ be verified to hold? How can the identity $\textbf{Pr}[\textbf{y}=y|\textbf{x}=x] = \sum_{\lbrace K:x=d_K(y)\rbrace}\textbf{Pr}[\textbf{K}=K]$ be verified to hold for any cryptosystem?

In his book Cryptography, Theory and Practice (3rd edition), Stinson states the equality for $\textbf{Pr}[\textbf{x}=x|\textbf{y}=y]$, which can be seen in the snippet below.

Intuitively, this seems just fine... But given that $\textbf{Pr}[\textbf{x}=x|\textbf{y}=y] = \textbf{Pr}[\textbf{x}=x,\textbf{y}=y] / \textbf{Pr}[\textbf{y}=y]$ by definition, how can I verify that the claim does indeed hold for any cryptosystem?

The operation of the function is completely described by $P(X,Y,K)$ which factorizes as $P(Y|X,K)P(X)P(K)$ under the assumption that $X$ and $K$ are independent and leads to

$$P(Y) = \sum_X\sum_K P(Y|X,K)P(X)P(K)$$

If you restrict $X$ to only the particular one that $K$ maps onto $Y$ (by writing $X = D_k(y)$) then $P(Y|X,K) = 1$ under the assumption that the function is a bijection, then you end up with

$$P(Y=y) = \sum_K P(K=k)P(X=D_k(y))$$

Using the same approach you can prove the conditional statement:

$$P(Y|X) = \sum_K P(Y|X,K)P(K) = \sum_K P(K)$$


Should I use AES CTR mode? I have a question. For example I have text: "The quick brown fox jumps over the dog!"

It has 32 letters. If I encrypt the first 16 letters with key: "11111111111111111111111111111111" and nonce: "1111111111111111" and next 16 letters with the same key and nonce will it be secure?

With AES CTR mode, using the same key and nonce to encrypt multiple blocks of data is a huge security breach:

Ciphertext1 = Plaintext1 XOR Key
Ciphertext2 = Plaintext2 XOR Key

XORing the ciphertexts:

Ciphertext1 XOR Ciphertext2 = Plaintext1 XOR Key XOR Plaintext2 XOR Key

This simplifies to

Plaintext1 XOR Plaintext2

This means that if you knew that the first message of the day (plaintext1) was going to be "weather report" then you could work out what the first 14 bytes of ciphertext2 is, because you could XOR "weather report" with the first 14 bytes of ciphertext1, get the first 14 bytes of the key, and them use this to decrypt the first 14 bytes of ciphertext2, and get the first 14 bytes of plaintext2. Other techniques such as what kelalaka suggested can be used to work out the whole message.

The solution: either encrypt the whole lot of data with the key and nonce, or change the nonce per block of data encrypted - maybe use a counter, because the nonce does not have to be unpredictable, but must be unique.


How to perform the lfsr scrambling used in PCIe for 2 byte input? In PCIe Gen 3 on-wards there is 128b/130b encoding used which scrambles incoming bit using a LFSR with polynomial: $$G(X) = X^{23} + X^ {21} + X^{16} + X^{8} + X^5 + X^2 + 1.$$ Is there any way to perform required scrambling on 2 bit in one clock using parallel scramblers, where output of incoming msb will be dependent on lsb's output.

The online magma calculator

http://magma.maths.usyd.edu.au/calc/

tells me this LFSR corresponds to a primitive polynomial since $$G(X) = X^{23} + X^ {21} + X^{16} + X^{8} + X^5 + X^2 + 1$$
is primitive.

Thus, some phase of the output sequence is given by $$tr(\alpha^t)$$ where $tr:GF(2^{23})\rightarrow GF(2)$ is the trace map and $\alpha \in GF(2^{23})$ is primitive.

The minimal polynomial of $\alpha^2$ is also $G(X)$ and it is the polynomial generating the decimation by 2 (the minimal polynomial of $\alpha^2.$ But this is the same polynomial since an element and its square are conjugates. This is because
$$
G(X)=\prod_{i=1}^{23} (X-\alpha^{2^{i-1}}),
$$
from standard finite field results.

The decimation by 2 is $s(t+2^{22})$ if $s(t)$ is the original sequence in its characteristic phase, i.e., the phase that satisfies $$s(2t)=s(t)$$
for all $t \pmod{2^{23}-1}.$


How would you encrypt-then-MAC when using pen-and-paper and a Caesar cipher? I'll probably get shot for asking this, but I've got some kids (aged 8-10) in my neighbourhood that I've been showing/teaching the simple pen-and-paper Caesar cipher and they're successfully playing with it for more than a week now.

Silly me thought it would be great to now show them the concept of message authentication and how it practically works; especially that it can be used to show if the message has been modified by someone along the way or not. So the plan was set and the promise made as it suddenly dawned upon me that I never used anything else but computational power to calculate (H)MACs… and that's not exactly a pen-and-paper solution for the kids.

Now, the good thing is that they don't need a national-security-level encryption, which means I could use any simple (read: improvised) hashing method as long as it works using pen-and-paper. But such simple hashes are obviously hard to find. So currently, I am thinking of simply replacing the usual hashing with an addition-based checksum thing. That could work, but I'm not so sure that that's really the best option.

Keeping in mind that I need to explain MAC to kids aged 8-10 so they can practically do it themselves using nothing but pen-and-paper, do you have a better idea? How would you encrypt-then-MAC when using pen-and-paper and a Caesar cipher to practically show them a working message authentication?

One option would be to get them to select a one-time MAC of the form:

$mac(m,k_0, k_1) = (k_0 \times m + k_1) \mod p$

You would select $p$ to be something like 29. $k_0$ and $k_1$ would be chosen at random from the values 0-29. $k_0$ has the additional restriction that it can't be 0.

You can aid the computation by giving them a 29x29 matrix of all multiplications mod 29 and a similar table for all additions mod 29.

You'd then work through the message a letter at the time. Suppose these were the letters were numbered: $m_0 \dots m_i$. You'd start at $m_0$, computing the mac equation above. Then you'd feed the mac output in to the $k_1$ position for the next message block:

$mac(m_1, k_0, mac(m_0, k_0, k_1))$

and so on and so on:

$mac(m_i, k_0, mac(m_{i-1}, k_0, \dots))$

The final result is simply the output of the MAC.

Even though it isn't secure it demonstrates at least the idea of a MAC. It also gives them a design that can be trivially extended in to a secure MAC with small alterations.


Is there an asymmetric algorithm that can perform double encryption? I'm looking for any asymmetric algorithm can perform the serial encryption, by serial I mean double or more encryption with different key (same key size). RSA can not do it since the cipher of the first encryption is to long to perform an other encryption with the same key length.

For example (from Yao, Yang & Xiong 2015):

  We use $C = {\{ m\} _y}$ to denote encryption of a plaintext $m$ with a public key $y$. In addition, we use ${\{ m\} _{{y_{1}}:{y_{N}}}}$ to denote a serial of encryptions under multiple public keys, i.e., \begin{equation}{\{ m\} _{{y_1}:{y_{N}}}} = {\{ \ldots{\{ {\{ m\} _{{y_N}}}\} _{{y_{N - 1}}}}\ldots\} _{{y_1}}}.\end{equation}

No.  For semantic security, the encryption of a known plaintext with a given key must be overwhelmingly likely to have high entropy so for most plaintexts and keys, there must be lots of possible encryptions of the plaintext with the key.

So for most keys, the ciphertext space must be significantly larger than the plaintext space.

You might be interested in trapdoor permutations. The only candidates I'm aware of for [such permutations with domain not depending on the public key]
come from multi-variate crypto.

On the other hand, it's easy for symmetric schemes to satisfy the deterministic version of CCA-security.


How to prevent accidental nonce reuse with AEAD cipher I'm trying to correctly implement ChaCha20-Poly1305 in my node.js app (...crypto is hard). I understand that the cipher requires a unique key/nonce pair for each message or the security breaks down.

The nonce doesn't have to be random or unpredictable, so a simple counter is sufficient. My problem is that I can't figure out how to implement an efficient counter that will work with multiple instances of my app running simultaneously on the same machine and guarantee that no nonce will ever be reused.

Basically, I'm wondering how to avoid this footgun.

Some ideas I had:

Use a timestamp. Apparently not a great idea.
Use redis INCR. Complicates development environment (I now need redis installed on every computer I develop on), and I'm still left without strong guarantees that I won't get a duplicate value in case of an unexpected shutdown (even with Redis AOF).
Write to a file or database table every time a nonce is created. This should work, but the performance would not be great, and I'm probably still stuck in the event of an unexpected shutdown.
Use a UUIDv1 or v4 type thing (from the this comment). Initially v1 seemed perfect (guaranteed uniqueness), but it's tied to the system MAC address, so when I spin up multiple copies of the app, I'm probably killing any type of guarantee. Then there's v4, which should be good, but because the nonce is only 96 bits, I would need to truncate the ID and increase my collision probability (same goes for v1 actually). If I went this route, I was looking at nanoid.
Regularly rotate keys. I realize that this needs to be done anyway, but I want to minimize how often it needs to happen.
Something like Twitter's Snowflake. flake-idgen seems well suited for this (guaranteed uniqueness, partitioned by machine/worker or instance id, doesn't require coordination beyond determining instance ids, generates short enough ids).
Use XChaCha20-Poly1305. It's recommended in the libsodium docs specifically for this reason (the nonce is big enough that you can just throw random values at it and not worry). But, it's not a standard (yet?), and it would require bringing libsodium in for crypto instead of relying on node's built in OpenSSL wrapper. This complicates development (dealing with native bindings) and/or undermines security (constant time issues running crypto in js/WebAssembly...way over my pay grade).

Am I missing something obvious? How do people usually solve this kind of problem? Right now, I'm liking flake-idgen, but it doesn't seem like it's gotten a lot of scrutiny, so it seems possible that there are corner cases that could cause a duplicate id (leap seconds, leap year, accidental server clock reset, malicious NTP server, etc.).

Update: Ok, so the consensus seems to be to just use a random nonce and not worry too much about it. For my scale, I think that will be fine.

I found some issues in testing flake-idgen, so I don't think I would actually use that (although it still looks like a cool project).

My alternative plan would be to write a counter implementation that generates a 64bit BigInt counter (support added in Node 12) + a 16 bit instance ID + maybe 16 random bits for fun. I would persist the counter to disk after every X increments so that I'm not constantly writing to the disk. In the event of an unexpected server shutdown, the system would read from the disk file and add X + 1 to the current counter to ensure no-collisions.

Unsolved problems with this implementation: how to handle wrap around? what happens if the server is reset and there is no disk file to read from?

Thanks for your help on this, and if someone wants to post "just use random" as an answer, I'd be happy to accept it.

If you are having a sequential conversation, like TLS where each record is sent in order before sending the next record, you should use message sequence numbers for the nonce.  These will never overflow in ChaCha even if you managed to send one message per nanosecond for four centuries.  As a bonus, you can reject replays and force the attacker to keep up with your conversation, and you can immediately detect incorrect implementations that use nonces insecurely, e.g. because they randomized it or rolled it back.
If, for some reason, you are using a single key for (say) thousands of conversations in parallel, you can carve up the nonce into smaller pieces and assign to each conversation a unique (say) 16-bit number and then use 48-bit message sequence numbers for the rest, which is still a lot of messages, or 32-bit/32-bit, etc.
But if you're not restricted to using the same key—and it seems unlikely that you are, since you get to dictate how the key is used—then you can derive subkeys from a master key with a key derivation function, KDF, such as HKDF-SHA256, in what is sometimes called a cascade.  In fact, this is exactly how XSalsa20 and XChaCha work, using Salsa20/ChaCha itself as a KDF!  (Note: KDF does not just mean password hash; KDFs can be extremely cheap to compute—no costlier than generating a single block of output with ChaCha, for instance!)

For example, if you have a master key $k$ for your application, and many uniquely labelled instances of it, you can use $k_i := \operatorname{HKDF-Expand}_k(L_i)$, where $L_i$ is a unique label called the ‘info’ for the $i^{\mathit{th}}$ instance or purpose.  If you don't have HKDF logic handy, but you do have HMAC, it's easy to implement HKDF in terms of HMAC.

In a pinch, if you need a randomized system, you could just choose a sufficiently long info label at random, say 256 bits, and there will be no danger of collision (unless there's a VM rollback, etc.).  You could also include a time stamp, counter, favorite color, process id, phase of the moon, or anything else you want in the HKDF info string, as long as you can reason yourself into confidence that it will be unique.

Caveats:  In some cryptosystems like AES, there's a high cost to changing keys, and for 128-bit keys, subkey derivation is safe only for a modest number of keys, which is part of why I advise against AES and particularly against AES-128.  But there is zero key setup cost in Salsa20 and ChaCha, and the danger of collision in 256-bit keys is negligible no matter how many subkeys you derive within humanity's capacity for computation.
You may also have the option of generating and storing additional keys, possibly encrypted with a master key, or with a master key pair to separate concerns, or using a deterministic authenticated cipher.  But this is getting a bit far afield of the original already broad question.

(Technical details ahead, not necessary for the principal conclusion above.)

A note on XSalsa20 and XChaCha: If you have a library that computes Salsa20 or ChaCha for arbitrary nonce and block counter, you can easily compute XSalsa20 or XChaCha!

XSalsa20 and XChaCha are defined as follows: for 128-bit $n$ and 64-bit $n'$, the stream $\operatorname{XSalsa20}_k(n \mathbin\| n')$ with 192-bit nonce $n \mathbin\| n'$ is the stream $\operatorname{Salsa20}_{k'}(n')$ where $k' = \operatorname{HSalsa20}_k(n)$, and $\operatorname{HSalsa20}_k(n)$ is defined as a function of the Salsa20 core which is also used to generate the Salsa20 stream.

Specifically, the Salsa20 core $\operatorname{Salsa20}(k, i, \sigma)$ combines a 256-bit/8-word key $k = (k_0, k_1, \dots, k_7)$, a 128-bit/4-word input $i = (i_0, i_1, i_2, i_3)$ (which, for the stream cipher, is composed of a nonce and a block counter), and a 128-bit/4-word constant $\sigma = (\sigma_0, \sigma_1, \sigma_2, \sigma_3)$ into a matrix $$x = \begin{pmatrix} \sigma_0 & k_0 & k_1 & k_2 \\ k_3 & \sigma_1 & i_0 & i_1 \\ i_2 & i_3 & \sigma_2 & k_4 \\ k_5 & k_6 & k_7 & \sigma_3 \end{pmatrix},$$ and returns the 512-bit/16-word string $$\operatorname{Salsa20}(k, i, \sigma) = \pi(x) + x$$ where $\pi$ is a permutation.  HSalsa20, in contrast, computes $$x' = \pi(x) + x - \begin{pmatrix} \sigma_0 & 0 & 0 & 0 \\ 0 & \sigma_1 & i_0 & i_1 \\ i_2 & i_3 & \sigma_2 & 0 \\ 0 & 0 & 0 & \sigma_3 \end{pmatrix},$$ and returns only the 256-bit/8-word string $(x'_{00}, x'_{11}, x'_{12}, x'_{13}, x'_{20}, x'_{21}, x'_{22}, x'_{33})$.  (The indexing is a little different for ChaCha, as is the permutation $\pi$, but that's all.)  Effectively, this is simply returning half the words of just the permutation $\pi(x)$, skipping the additions that Salsa20 does at the end, but the difference between those words of HSalsa20 and those words of Salsa20 depends only on the public nonce $n$ and the public constant $\sigma$ so that breaking HSalsa20 can't be easier than breaking Salsa20.

What this means is if you have a way to generate a single block of output with the Salsa20 or ChaCha stream cipher using a prescribed nonce and block counter, then you can compute HSalsa20 or HChaCha by just subtracting off the nonce/counter and constants to derive an XSalsa20/XChaCha subkey, and from there use your Salsa20/ChaCha code to compute the rest of XSalsa20/XChaCha.


What is the public key and signature sizes for XMSS? This is a follow-up to a recent question of mine.

I am looking to find the public key and signature sizes for the XMSS signature scheme, in terms of the XMSS parameters (length $\ell$, height $h$ and security parameter $n$). I found the following 2 papers that have contradictory answers and I'm confused.

The original XMSS paper on pg.5 says:

  The bit length of the XMSS public key is $(2(h+ \left \lceil log \ell \right \rceil) + 1)n$, an XMSS
  signature has length $(\ell+h)n$ (...)

and a more recent paper on pg.6 says that the public key has length of $4 + 2n$ and the signature size is $4+n(\ell+h+1)$

Can someone explain me which of the two is true and why?

The original XMSS paper (eprint 2011/484) discusses an older version of XMSS, which does use rather larger public keys (and I suspect they got the signature size slightly wrong - they forget the idx_sig part of the signature which specifies which WOTS+ leaf they're using).

The XMSS RFC defines a newer version, with considerably smaller public keys (and slightly larger signatures).  The more recent XMSS/LMS comparison paper which you cited (eprint 2017/349) uses the RFC version of XMSS for the comparison.

I believe that the version defined in the RFC is what people generally use, and so the values in the comparison paper are the ones which are accurate.

As for the differences between the original version of XMSS and the RFC, well,
here's the main difference: in the original paper used masks stored in the public keys to provide randomization; the problem with this is, because they use the same masks in different parts of the Merkle tree, this opens them up to multitarget preimage attacks.  In the RFC version, they compute the masks dynamically (and hence they don't need to be in the public key). Because each mask is now different, multitarget preimage attacks don't apply (at the cost of the computation needed to generate the masks dynamically).

A more minor difference is that the RFC version includes a randomizer 'r' in with the signature (which is hashed along with the message); making this randomizer be unpredictable means that we don't depend on the collision resistance of the hash function (given that we rely on preimage or second preimage resistance everywhere else, this is a win).


Is part of an output of secure PRNG also cryptographically secure? Lets say I generate 192 bits using some secure PRNG. If I now take first 128 bits is it equivalent of generating 128 bits in the first place?

P.S. More practical application for me is that I need a machineKey for the ASP.NET, I use IIS UI for it and it generates a string that corresponds to 192 bit key used for AES, but since AES 128 is good enough as well, but faster, I want to take only the first 128 bits.

Yes. Although the bit values are not identical per se (even given the same seed) you should use any of the 192 bits to form a 128 bit key - as long as you don't reuse any bits of course.

If the 128 bits are not secure, then the 192 bits should also not be secure. AES keys consist of bits that are entirely random and thus unrelated, so generating a 192 bit key and then using the leftmost 128 bits should be OK.


What encryption shoud I use for single char encryption? I'm very new to encryption and I wanted to know if it is secure or just possible to use encryption on single chars. I did some research, but nothing to clear and i'm a bit confused.
The modes I think it is possible to do it with are one-time pad, RSA and AES in counter mode.

These are probably wrong ,but I have no idea why. So please explain me why these can't be used or maybe can be used.

EDIT: since I'm building a keylogger I could just buffer up and encrypt the whole buffer, encrypting a single char is not necessary.

There is no minimal message size. Even an empty message can be securely encrypted, i.e. the ciphertext is indistinguishable from a different encrypted message, as long as the encryption key remains secret.

Can you describe exactly what are want to achieve?

Where will the secret key come from?

Even though minor optimizations are possible with very short messages (in particular, short tags may become acceptable), you should use traditional constructions. ChaCha20-Poly1305 and AES-GCM, in particular, don't require padding, and work with short messages just as well as with long messages.

Edit: since your use case is a key logger, you probably don't need to encrypt individual characters. Buffer them up to a reasonable size (maybe 1KB), and encrypt the buffer once it's full or when the application terminates.


What are the popular modes-of-operation (AES-GCM, AES-SIV, AES-GCM-SIV, etc.) geared for? I'm interested in developing software capable of encrypting personal files (which will ultimately be backed up to the cloud) and have been doing my best to follow best practices.

There are many forms of authenticated encryption. (AES-GCM, AES-SIV, AES-GCM-SIV, CBC + HMAC, CTR + HMAC, etc.) However, I'm having a hard time determining which of these modes-of-operation suits my use-case best. Speaking broadly:

I've heard many times that "GCM is harder to get right" due to the serious risks associated with nonce reuse as well as its predisposition to side-channel attacks if implemented poorly. Although it is fast.

I know AES-SIV is at least utilized by Cryptomator, a tool similar to what I'm trying to develop, (per their architecture docs). AES-SIV has a smaller penalty for nonce reuse compared to GCM but perhaps isn't as fast.

AES-GCM-SIV attempts to combine the positives of both GCM and SIV by being both fast and somewhat resistant to nonce reuse.

As far as CBC + HMAC is concerned, HMAC leverages 256-bit authentication tags over GHASH's weaker 128-bit authentication tags (used by GCM). However, CBC cannot be parallelized in the same way GCM can.

CTR + HMAC can be parallelized in a way similar to GCM but with stronger authentication tags. (Again, HMAC using 256-bit authentication tags over GHASH's 128-bit authentication tags)

Despite the reading I've done so far, I haven't been able to determine why one might choose one of these methods over the other. At the end of the day, I would really just like to secure my files safely in the cloud with at least some assurance that the files I encrypt are authentic and have not been tampered with or corrupted in any way.

I would really appreciate any help that could point me in the right direction.

I went through this decision process about 2 years ago and ended up going with something very conservative: encrypt-then-MAC with AES-256-CBC and HMAC-SHA-512 truncated to 256 bits.

Why SHA-512 over SHA-256?  SHA-512 is faster on 64-bit machines.  (Though recent AMD processors' SHA-256 instructions yield a 4x speed-up: link).
Why AES-256 over AES-128?  https://blog.1password.com/guess-why-were-moving-to-256-bit-aes-keys/

This was fast enough for my use cases, but is much slower than many of the alternatives.  The AES part is fast on Intel processors; hashing ends up taking ~80% of the time on long messages.
Alternatives worth considering today:
Replace HMAC-SHA-512 with keyed BLAKE3 (~2.5x faster for long messages).  BLAKE3 itself is very new, but has a somewhat mature lineage.
XChaCha20-Poly1305 (~2x faster for long messages).  Nonces can be up to 192 bits, so there's less of a risk of collisions.
AES-GCM-SIV (~5x faster for long messages).  Doesn't seem to be widely implemented yet.
Note: These performance estimates are vaguely based on a "typical" 2016 x86-64 processor, which has dedicated AES instructions and some general-purpose SIMD, e.g. AVX.


Is it okay to use a variable-time RSA implementation to verify TLS certificates? RSA as implemented by OpenSSL et al. needs to protect against side channel attacks, at a big performance penalty.

However, TLS certificate validation involves no secrets.  Therefore, I should be able to use a fast variable-time algorithm for this purpose, right?

Is this actually secure, and does anyone actually do this?

Two answers to the question:

It is about principles and reusability of the cryptographic primitives. Once there are implemented by insecure manner, nothing prevents reusing or misusing the insecure functionality later.
TLS validation (during the SSL handshake) involves a secret as well - during the SSL handshake a piece of data is encrypted and sent over to decrypt to proof ownership of the private key. This is the part when the side-channel attack needs to be mitigated.

Carpe diem

g.


Assuming a 1024qb quantum computer, how long to brute force 1024bit RSA, 256bit AES and 512bit SHA512 Assuming in the future there was a functioning 1024 qubit quantum supercomputer and it could run Shor's algorithm or Grover's algorithm to crack encryption very quickly. I'm interested in how the number of qubits translates to performance improvement over a regular 2 bit computer.

For example, if I used Shor's algorithm on a 4 qubit quantum supercomputer, would this take half the time to factor 1024 bit RSA as it would a regular 2 bit supercomputer? Then if we extrapolate upwards to 8 qubit supercomputer through to 512 qubit, 1024 qubit and even 2048 qubit etc. What sort of factorization speed increase would you get from adding more qubits? I originally thought quantum computers could have only 4 qubits. But it seems these days you can keep adding qubits up to the amount you want within technical reason. Does this mean if I had a 1024 qubit supercomputer I could factor RSA 1024 bit in a split second? At what speed could it check possible factorizations?

So I'm interested how long it would "theoretically" take to:

Brute force find the key for a 1024 bit encrypted RSA message using Shor's algorithm.
Brute force find the key for a 256 bit AES encrypted message using Grover's algorithm.
Find a pre-image for a SHA2-512 bit hash.
Construct a rainbow table for a SHA2-512 bit hash.
If people are using 2048 bit RSA now as standard, will it take double the above time?

Some explanation for how to calculate that and a breakdown into the time it would take in seconds, minutes, hours, days or years would be much appreciated.

Adding more qubits does not increase the computation speed. A quantum computer with 4 qubits does not factorize faster than one with 2. The qubits are the "memory" of the quantum computer. More qubits mean you can factor bigger numbers. If I remember correctly, you need a superposition of $\Theta(N^2)$ terms, which means $\Theta(\log(N^2))$ qubits to factor N.
The running time of Shor's algorithm is $O((\log N)^3)$ to factorize $N$. What is important to remember is that Shor's algorithm can only factorize (by solving the discrete log problem). See wikipedia's entry on Shor's algorithm.
As for Grover's algorithm, it provides quadratic advantage over classical computers for "black-box" queries. So a quantum computer could perform a brute-force attack in $O(\sqrt{N})$ trials whereas a classical computer would need $O(N)$ trials. Again, increasing the number of qubits does not lower the running time, but increases the "memory" of the quantum computer. In order to run Grover's algorithm to brute-force a key, you need a superposition of all keys, which requires $\log K$ qubits where $K$ is the number of possible keys.


How is the password sent across for verification? I am familiar with Challenge-Response Authentication scheme.
However I would like to know actual message content sent between client and server for 1 way authentication, over an insecure channel.

When the user enters the password, is the password encrypted and sent, or is the hash of the password encrypted and sent? Is a time-stamp or a nonce used? If the digest of the password is sent, when is the salt added?

Typical scenarios would be login without https.

It depends on the particular scheme. In a simple challenge-response scheme, the server sends a challenge, the client "encrypts" the challenge and the password to form a response, and then the client sends the response over the wire.

However, standard logins typically don't use challenge/response. The password is just sent to the server by the client. When using SSL/HTTPs, the password is protected by the encryption of the channel. When using ordinary HTTP, there's no protection whatsoever. With no security on the channel itself, even with a challenge/response protocol, an attacker can simply proxy the authentication portion of the protocol between the client and server and then takeover the authenticated connection after that phase completes.


Using MITM to attack three keys 3-DES encryption? I know that MITM can break three keys into two parts $(K_1,K_2)$ and $K_3$ where the worst time complexity is $2^{112}$.

My questions is whether we are able to break three keys $(K_1,K_2,K_3)$ into three different parts, then starts to attack each key independently? If we can, will the time complexity and space usage both be $O(2^{56})$? assuming each key size is $56$ bits.

No, we are not able to break 3-keys 3-DES encryption using something similar to Meet-in-the-Midle with cost much lower than $2^{112}$ encryptions; much less triple encryption in general.

In the case of triple encryption with 3 k-bit keys in general, in order to apply MitM, we'd need to group 2 keys together on one side, thus would have cost $O(2^{2k})$ for this half. There's even a formal proof, see this. The space complexity of that MitM remains $O(2^k)$ blocks, since we can chose to pre-compute the values for the side with the shortest key, then perform the search with the other half.

In the case of DES, we know the structure and can open the block cipher, and in particular break the middle cipher into two halves of 8 rounds. However, each of these haves still receives all the keys bits of the midle DES, therefore we can't use that to reduce the complexity of plain MitM to $2^{56+28}$ encryptions on each half, as we could if 28 key bits went exclusively to the first 8 rounds, and the 28 other bits exclusively to the last 8 rounds.

Notice that clever attacks exist against 2-keys 3-DES, and are nearly practical; see this.


The equivalence of SIS and ISIS(Inhomogeneous SIS) I would like to know whether these two problems are equivalent or not, namely:
$SIS_\alpha$: Given $A \in \mathbb{Z}_q^{n\times m}$ find $ e \in  \mathbb{Z}_q^{m}$ such that $ Ae = 0$ and and $\|e\| \le \alpha$.
$ISIS_\alpha$: Given $A \in \mathbb{Z}_q^{n\times m}, y \in \mathbb{Z}_q^{n}$ find $ e \in  \mathbb{Z}_q^{m}$ such that $ Ae = y$ and $\|e\| \le \alpha$.
I did some research and found the following Lemma 10 at second page of the document claiming that an efficient solution to $ISIS_\alpha$ implies an efficient solution to $SIS_\alpha$ but the proof is incorrect since it is not showing that $e' \neq e$.

Write $A = [A_1 ~~ A_2]$ with
$A_1 \in \mathbb{Z}_q^{n\times m'}$
and
$A_2 \in \mathbb{Z}_q^{n\times (m-m')}$.
Likewise, $e = (e_1 ~~ e_2)$ with
$e_1 \in \mathbb{Z}_q^{m'}$
and
$e_2 \in \mathbb{Z}_q^{m-m'}$.
Then,
$$Ae = 0 \bmod q \iff A_2e_2 = -A_1e_1 \bmod q.$$
So, given an instance of SIS, that is, an $n\times m$ matrix $A$,
if you have an oracle to solve ISIS, then you can write $A$ per blocks as above, sample a short $e_1$, define $y := -A_1e_1 \bmod q$, and use the oracle to obtain a short $e_2$ such that $A_2e_2 = y \bmod q$.
Your SIS solution will then be
$e = (e_1 ~~ e_2)$.


What is the maximum cofactor of elliptic curve used for ECDSA? I know that the cofactor of curve 25519 is 8. Is it the maximum factor in the existing curve used for ECDSA?

The X9.62 ECDSA standard does not specify a bound on permissible cofactors (though it only records how to validate cofactors up to about $\sqrt p/4$). The Certicom SEC1 document only allows cofactors up to $2^{t/8}$ where $t$ is the bit size of the field. In theory then, quite large cofactors might be in use somewhere. In practice people almost always preferred to use Weierstrass curves with cofactor 1 a) for efficiency and b) to avoid possible weaknesses with unverified parameters. I believe that all of the NIST standard curves have cofactor 1 for example. By contrast Curve 25519 allows a cofactor so that it can have a compatible Edwards curve representation (Edwards curves are more efficient and have better anti-sidechannel properties; their order over prime fields is always divisible by 4 however). Similarly Curve 448 has a cofactor of 4 and an Edwards form.
ETA: kelalaka points out that 25519 pre-dates Edwards curves; it was a happy coincidence that it was Edwards compatible.
In pairing-friendly cryptography larger cofactors can be quite common as there are very stringent conditions on the curve order. Such curves are however not generally used for ECDSA.


How many oracle calls to break an affine cipher in a chosen plaintext attack? Assuming the ability to launch Chosen Plaintext Attacks (CPA), how many oracle calls does an attacker need to break the affine cipher? How does it work?

The answer is 1 I think because if we apply a chosen plain text attack, then we need at least 2 encrypted alphabets and two plaintext alphabets corresponding to the related encrypted alphabets. Then we will have two variable and two equations.

By solving those you can get the additive key as well as the multiplicative key.


What are the exceptions to Kerckhoffs's principle? Kerckhoffs's principle:  A cryptosystem should be secure even if everything about the system, except the key, is public knowledge.

Yet the following are three exceptions:-

NSA Suite A cryptographic algorithms.  There is an answer here that implies that the Suite B algorithms are broken therefore can be published so that the NSA can listen in on Suite B users. And by not publishing Suite A, no one knows for sure instead relying on security through obscurity.
Banks holding my money.  They haven't published a security architecture diagram of their network, and probably wouldn't tell me over the phone how they've implemented AES.  Perhaps they use ECB mode or even their own Barclay's mode. Banks are civilian organisations, not military like example 1.  They're regulated yes, but (even redacted)  security reports are not published.
Windows' Cryptography API.  This is used by some people and they unknowingly might be using the dodgy  Dual_EC_DRBG, or something even more decrepit.  There is no code audit available to prove any particular mode of operation or algorithm. This particular API could easily be published to assuage users fears without revealing the rest of Windows' internals.

It seems to me that whilst Kerckhoff sounds plausible, many organisations ignore it.  And get away with it.  What are the real world exceptions or rules? Does it for example only apply to amateur cryptography?

Kerckhoffs's principle: A cryptosystem should be secure even if everything about the system, except the key, is public knowledge.

The principle does not state that it is unconditionally unacceptable to keep your algorithm or system a secret. (This answer provides an image of the original text Kerckhoffs used.)

Just keeping the used algorithm a secret is not itself a violation of the principle - as long as it would be secure even if the algorithm was known. AES would be secure even if it is known that you used it, keeping the fact that you used AES a secret does not hurt anything. In fact, it is possible that it could provide an additional layer of security, and can be used to provide "defense in depth".

NSA suite A/suite B is a good example of this: It is not an exception to Kerckhoffs princpiple, because the system would (most likely) be secure even if you knew what algorithms they were using. It simply adds a theoretical additional layer of difficulty if you don't know what they are using.

As for banks, I am not necessarily qualified to speak about their systems, as I do not know them; However, it is plausible that some of them were created quite a while ago, and consequently may not necessarily utilize all the best practices that we would build a new system with today. "It's in production already" can be hard to argue with.

As for Microsoft, well, you say they "get away with it" - many if not most people are not exactly thrilled about their decisions to keep everything a secret; However, they do that for way more then just the crypto API, and such decisions are probably made from a business perspective, rather then a crypto one.

edit: Apparently, if you are really so inclined and willing to sign stuff, you can view some of Microsofts source code. While that's not exactly "open", it implies that you could find out what they were doing if you really wanted to.

However...

Sometimes violation of the principle is simply an attempt to compensate for the inadequacy of the algorithm/system by keeping it a secret from the adversary - this is the situation where the principle will end up making a difference.

This has proven itself to be a poor strategy - instead of allowing the problems to become known so that they can be fixed, they chose to cover them up and hope that nobody finds them. When "hope" appears as an factor in your crypto-system, that's a sure sign of a problem.


Xor'ing sha256 words instead of adding In sha-256, when the words go through the compression function, they get added to the previous hash. In case of the first 64 rounds, they get added to the initial words ($\bmod 2^{32}$ of course). However, would xor'ing instead of adding be more secure, or not?

Any group operation $\odot$ on the set $\{0,1\}^{256}$ equally matches the objective of making the hash round function $F(m,x)=E(m,x)\odot x$ one-way under the assumption that $x\mapsto E(m,x)$ is a random permutation keyed by $m$. Thus under this model, XOR or 32-bit addition does not matter.

  would xor'ing instead of adding be more secure, or not?

For the reason above: That's moot. But if we need to choose, rather not. Argument: addition makes the natural expression of a hash round function as a number of elementary logic gates (or satisfiability equations) slightly more complex than XOR due to the  8×31 carry terms. And absent any other good criteria, it's reasonable to bet that more complex is more secure, because that's demonstrably true for a random arrangement of gates (or satisfiability equations)


Linear feedback shift register combination, secure? I am currently working on a project which consist in the encryption of image using the GPU of a raspberry.

I would like to use LFSR to generate a stream cypher in each Core of the GPU.
In the wikipedia article they recommend to use combination of several LFSR, we could use 2 LFSR, one could tell if we use the current output bit from the other one shrinking generator

It says: "Despite this simplicity, there are currently no known attacks better than exhaustive search when the feedback polynomials are secret"

Do you think it's a good choice ?

Working with image makes me working with large field of data, Kb files.
I saw that if we select a good polynomial we can have a large period, so in theory if i have a 32 bits LFSR register and i use a polynomial from this page
polynomial

Could I generate 2^32 pseudo random bits (not  bytes) ?

Last question, is it okay to use the same polynomial and changes the seed (initial state of the register) for later use or should i change the polynomial each time i want fresh data ?

I think Trivium, and ChaCha20 are excellent choices.

If you insist on using the shrinking generator or the self shrinking generator, you should use them without hiding the polynomials, which would be security by obscurity. I'd suggest that the SSG is probably stronger than the SG, for given keylength. But there are fast correlation and guess and determine attacks on both, so your real strength is only a fraction of the keylength. This would mean using at least 256 bit length LFSRs.

Finally they haven't been designed with modern Key/IV based operation. Key/IV based operation would help you achieve the goals you might have in mind for the question of whether you should change key and/or the secret polynomial.


Semantic security and indistinguishability I have two frames f1 and f2 that are each composed of several elements noted e. Note that, an element can fall into one of those two categories: an identifier or a counter.

What I want is to find a property that verifies indistinguishability of elements between frames. For instance, given the element e as an identifier, if f1.e==f2.e the property is not verified while it is verified if f1.e!=f2.e.

For now, I only suppose that such a property includes probabilities and can be obtained via:

semantically secure block cipher for identifier elements;
PRNG for counter elements.

You could use Format Preserving Encryption for either one of the elements. FPE will create a keyed permuation for a specific domain (presuming that this domain can be practically converted to a number representation). That way your identifier can just be a sequential number.

You could see a block cipher as an FPE for a specific domain with $2^n$ elements, where $n$ is the block size in bits. If you can define your domain to have that many elements (even unused ones) then yes, you could use a block cipher. This could be an issue if you cannot handle a relatively large output size (you cannot store $2^{32}$ bits or more, for instance).

You can also create a random nonce, but due to the birthday problem, you will have to generate a pretty large value to avoid collisions in the element itself (and, of course, the encrypted element as well).


SHA256(RsaPrivateKey) == AES key? I have an RSA private key (more specifically, an SSH key in Putty format, 4096bit) and want to use its SHA256 hash as an AES256 key, instead of using an independent newly generated AES key.

Are there any reasons why doing this might be a (very) bad idea?

In terms of entropy etc., it should be still sufficiently secure for real life (I think?). But are there any pitfalls, like certain properties of good RSA keys that would make the AES key much worse / easy to break (than one directly made by a properly used CSPRNG)?

Both keys are meant to protect the same thing, ie. if an attacker can get one, deriving the other doesn't make the situation worse.

(This not not an XY problem. And I know that this is not the usual use case.)

First of all, the usual way to do this is to generate a new random AES key and then wrap it with the public key. Generally you don't encrypt with the private key at all.

Yes, SHA-256 is a one way hash so you can do this. The problem is that you would still need to encrypt with a public key to let the other party know the AES key (unless you use the key to encrypt for yourself, of course).

There are however a few pitfalls:

the private key needs to be encoded as bytes, and not all encodings are canonical; i.e. you could use different encodings for the same private key. If this ever happens in your scheme you would not be able to generate the same AES key;
you'd need a separate input - e.g. a counter (nonce) - if you want to generate more keys;
SHA-256 is not a KDF, you could use HKDF instead (which just requires a hash function to work).
Sometimes hashes over private keys are used as key identifiers. You must make sure that this is not the case. For RSA however the key identifier is usually generated by a hash just over the public modulus.
You'd forgo the option to store the private key within a security module, as direct access to the components that make up the private key would likely not be available.

The biggest question that you should ask yourself is this: why do you need an AES key for encryption at the location of the private key. That's a strange use case.


Simple One time Pad Probability We have a one time pad where:

We have 8 bits. probability that a bit=0 is p.
The key is common for all 8 bits. It can have a value of 0 or 1 with equal probability.
After applying the XOR operation we take the encrypted result that has n zeros and 8-n ones.

What I am asked to do is calculate the probability that the key used is 0.

Until now I am thinking like this:

There are 2 events:

EventA. We have k zeros in the original 8 bits

EventB. We have k zeros in the encrypted data.

P(A) can be calculated from the binomial distribution
P(B) = 2P(A)
I am searching the probability P(key=0|P(B)).

Is my thinking correct until now? How can i procede from there?

Assume the message is an $n$-bit string with each bit drawn independently with $P(0) = p$.

Let $A$ be the event that the key bit is $0$.

Let $B$ be the event that there are $k$ zeroes in the ciphertext.

Then $P(A) = \frac{1}{2}$ and $P(B) = \frac{1}{2}{{n}\choose{k}}\left(p^k(1-p)^{n-k} + p^{n-k}(1-p)^{k}\right)$, since with equal probability we had $k$ zeroes or $n-k$ zeros in the message.

$P(B | A) = {{n}\choose{k}}p^k(1-p)^{n-k}$ since this occurs exactly when the message originally had $k$ zeros

Then $P(A | B) = \frac{P(A)P(B | A)}{P(B)} = \frac{p^k(1-p)^{n-k}}{p^k(1-p)^{n-k} + p^{n-k}(1-p)^k}$


May an adversary be fooled by a random-looking input that in reality is fixed? I want to prove the EUF-CMA-security of a signature scheme. It is a variation on an established scheme, therefore I would ideally like to reduce the new-scheme-security to the old-scheme-security.
the (very abstract) construction
Let the old scheme be called S and let k denote a number. In S, k is fixed, say k=5. Imagine the new scheme N is identical, only with k becoming random and secret (because it is now related to the key material). So, k=5 is in theory still possible but may just as well be 1,2,3, .. and k=5 is just as likely as k = any other number.
One needs to know k to verify the signature, and k acts similar to a symmetric key. The setting is a group where you want to identify an individual sender but still share symmetric keys.
the reduction attempt
An adversary may query oracles for different values of k and the challenger can simply draw them randomly.
However, in the challenge setting, it may obviously not know k, which is secret.
Now, it would be easy to reduce the security of one scheme to the other if the adversary were to be tricked into outputting a signature for k=5. Then the security of N can be reduced to the security of S.
The adversary can not tell from the key material or the signatures or the verification equation that k=5 (because everything still appears random), except if it can break the DLog assumption.
So the questions are:

An adversary can easily check whether k=5 or k!=5 in the challenge setting by attempting to verify a signature using k=5. Would an adversary realize that it is not interacting with the
scheme but with a "simulation" if it finds out that k=5 in the challenge setting? (In which case, as far as I understand, it would not
output a signature but break off the game.) Or is 5 a good a number as any, from the perspective of the adversary?
I can not play the game differently for different adversaries, depending on whether they compute k or not, because I know nothing about how A works - correct? (See Katz, Lindell, Introduction to Modern Cryptography, pg.59) Or could I play differently for "DLog-Breakers" and "DLog-Ignorants"?

Would an adversary realize that it is not interacting with the scheme but with a "simulation" if it finds out that k=5 in the challenge setting?

This is commonly stated as Kerckhoff's Principal, which I prefer to cite as Shannon's Maxim (they both stated it, and Shannon's Maxim sounds better). The idea is, the adversary should be assumed to know everything about a secure system, except the key, if it is to be considered secure at all. As such, the adversary must be assumed to know that you could lie to them about the value of $k$.
Also, a signature scheme could not be considered secure if it involves an oracle capable of lying about what signatures are valid or invalid. As such, if the system is to be secure at all, it must behave the same for an attacker as if they were a legitimate verifier.


How are certificate status obtained on browsers? There are two ways of checking the status of a digital certificate:-

Offline Authentication (CRL)
Online Authentication (OCSP, SCVP)

Several browsers (like Mozilla Firefox) have given up the use of CRL over OCSP.

OCSP and SCVP are susceptible to MITM attacks.

Then which method is used a primary means of checking the status of a digital certificate?

OCSP is not susceptible per se to MITM attacks, but it does have other problems:

Most browsers used to soft-fail, e.g., if they couldn't get the OCSP response for some reason, it allowed the connection to go through. So the attacker only needed to block the OCSP response.
Privacy issues: an attacker can see the OCSP query going through and can gain some information about your browsing.

This is solved by OCSP stapling, where the server is responsible for getting the OCSP response and sending it to the client (stapling). There is also the must-staple extension that makes stapling mandatory, otherwise a MITM attacker that stole the server private key could just not staple the OCSP response.


Is it possible to combine true streaming with AEAD? It seems there is a difference between "streaming" in cryptographic sense (as in CTR) and "streaming" in general programming sense (as in "accept a file larger than RAM from socket and save it on disk"). It shows when people try to apply AEAD (or in general authenticated encryption) schemes to something like Java's InputStreamReader (e.g. authentication is broken or not enforced enough). To do streaming in a latter sense it would be very useful to have AEAD scheme that provides "intermediate" authentication, that is, for block of encrypted message it should be known if it's genuine up to the point. Granted, later we can discover that there were some meddling and revert all the work already done (or just skip affected part), but it would be simpler compared to what is, in a sense, two-stage scheme (receive an entire message and only then verify it). Is there such schemes out there? Am I missing something that makes the proposed arrangement terribly insecure?

Yes there are such schemes.

However they aren't standardized by any means yet.
The schemes I'm talking about take part in CAESAR-competition.
If you wait ~1 week (hopefully) you'll see if any mode / cipher makes in in the second round.
This paper provides you with a good overview over the ciphers.
The four ciphers you need are:

ICEPOLE (Sponge based)
KETJE (Sponge based)
Keyak (Sponge based)
TriviA-ck (Streamcipher based)

This schemes can be used. But I'd strongly recommend against using them before CAESAR-competitions has further advanced (a few years?). Until then splitting a message stream into pieces with own tags + IVs seem to be the only method one can think of. To ease up IV management, one could use Message numbers as nonces.


One time pad in CBC mode? I have been searching about if it is more secure to use CBC mode in OTP but I can't find anywhere where people have sad that it is more secure.

Question: Is CBC mode in OTP more secure?

Because I have been reading articles like "https://stackoverflow.com/questions/22212407/how-to-alter-cbc-encrypted-text-to-change-the-message" and I have been wondering if it makes OTP more secure on that attack.

For example, let say that you have a message: "100 dollars should be moved." and you encrypt it with OTP. Then everybody can just take the first character "1" and change it to a 9 by XOR the 1 from the cipher-text and then XOR a "9" with the key you got.

BUT if you have it in CBC mode does it make it safer from this kind of attacks? (Known-plaintext-attacks and chosen-plaintext-attacks).

For example, let say that you have a message: "100 dollars should be moved." and you encrypt it with OTP. Then everybody can just take the first character "1" and change it to a 9 by XOR the 1 from the cipher-text and then XOR a "9" with the key you got.

What you are describing is what happens if an attacker introduces changes in the ciphertext by a man-in-the-middle attack. This kind of attack is not protected against by OTP. OTP only provides for confidentiality, not integrity and authenticity. To add integrity and authenticity you need to add a message authentication code or MAC to the ciphertext.

Unfortunately MAC's won't provide perfect integrity or authenticity. In practice this doesn't matter much as - for instance - HMAC is pretty secure. It cannot be proven secure just like OTP however. Ciphers such as AES have the same properties; they are rather secure, but they cannot be proven secure. Generally they are considered secure enough and they are much more practical than OTPs.

OTP doesn't propagate errors introduced to the ciphertext. CBC does propagate errors. If you could reliably detect such errors then you would have integrity protection. This is however not the case:

CBC error propagation is localized to the current block and a single bit of the next block;
CBC decryption always succeeds, you just get incorrect plaintext;
if the plaintext is a padded message then the padding may trigger padding errors, but it may also - by chance - create a valid padding scheme;
if the plaintext is a padded message then plaintext/padding oracle attacks may apply, destroying not just the integrity but also the confidentiality (leaving you with no protection whatsoever).

Nowadays we don't care about error propagation all that much; we apply a (H)MAC over the IV and ciphertext or we apply an authenticated mode of operation (an AEAD cipher) such as GCM. In that case the verification of the authentication tag will fail if any changes are made to the IV, ciphertext or authentication tag.

The CBC mode of operation is defined for keyed block ciphers. OTP however isn't a block cipher, so CBC cannot be directly applied to it. In CBC the block cipher is executed for each block of plaintext. As you should never reuse the key for a one time pad, CBC can not be made applicable to OTP.


Is there a generic attack on encrypted CRC32 when used as a MAC? I am examining a protocol that uses CRC32 as a MAC (see note 1) the weaknesses of this method but I would nevertheless like to see if it is just weak or actually relatively easily to break.

The examined protocol has the format more or less of:

Plaintext = Headers (6 bytes) || CRC (4 bytes) || Data
Ciphertext = 3DES-CBC(Plaintext)

This is used for a Server to send a Client a message and the Client will authenticate the message by decrypting it and checking the CRC. An attacker cannot ask the Server or the Client to encrypt a message, they could predict though the plaintext from a ciphertext.

Searching about it I can see that there is an attack on SSH 1.5 that is similar. To perform the attack the format of the data is put into this format for SSH:

Plaintext = Padding (8 bytes) || Data || CRC (4 bytes)
Ciphertext = 3DES-CBC(Plaintext)

The attack is performed partially by taking advantage of the CBC encryption by changing the first block which is the 8 byte padding in order to manipulate the second 8 byte block. If I was to perform the same attack though on the examined protocol since the 4 byte CRC is split between the first and second protocol it wouldn't work.

Note that the question is not if the protocol is weaker compared to a protocol where a proper MAC like HMAC had been used but if there is any attack that could relatively easily break the authentication.

NOTES

From fgrieu: The terminology is not quite right: CRC32 can't be used as (a weak substitute for) a MAC, for it is a keyless transformation of the message. Rather, here, it is used as (a weak substitute for) a hash in a hash-then-encrypt scheme

Well, 32 bits is somewhat short, so one could just try ciphertexts.

However, there is a much better attack.

Choose M0 arbitrarily, let P be the CBC padding for Headers || CRC || M0,

and choose M1 so that CRC( M0 || P || M1 )  =  CRC(M0).

Submit M0 || P || M1 to be encrypted, truncate the ciphertext to the length of

encryptions of M0, and then output the result. $\:$ That will be a valid encryption of M0.

Even without chosen plaintext, one should be able to change the headers.

Let H be the headers and let CL be the first 16 bits of CRC and let  L be the (bit-)length of Data.

Choose 48 bits X which are not all zero so that the CRC of [X combined with L zero bits

however the protocol does that] ends with the same 16 bits as the CRC of 48+L zero bits.

Xor the IV with [X concatenated with [the xor of the first 16 bits of the two just-mentioned CRCs.

By the affineness of CRC, the result will be a valid ciphertext

with the same Data and header H xor X.


Why is low-degree polynomial preferred on Ring-LWE based somewhat homomorphic encryption? I'm wondering why Ring-LWE based homomorphic encryption (somewhat homomorphic encryption, not fully) requires low-degree polynomial in order to avoid decryption error.
For example, a plaintext $m$ is an element over some polynomial ring, i.e. $m\in \mathbb{Z}_t[X]/(X^N+1)$ where $t$ is a prime and $N$ is a power of two integer.

More redundantly, $m= m_0 + m_1 X + m_2 X^2 + \ldots + m_{N-1}X^{N-1}$.
A noise $e$ is also a polynomial sampled from discrete gaussian distribution.

I do not know why polynomial degree is considered.
Noise amount on each coefficient violates on each coefficient of the plaintext polynomial.
Is this correct?

The ciphertexts contains a certain amount of noise for security reasons. The downside is that if this noise is too big, the decryption will fail. When using homomorphic operations, the noise contained in the output ciphertext will be bigger than the one in the input ciphertexts.

Now when adding ciphertexts, the new noise is just the sum of previous noises, but when doing multiplication, the noise grows faster, and ultimately, only knowing the number of multiplication you're doing is a good approximation to know how to set your parameters.

This is why you prefer low degree polynomials to high degree polynomials, to avoid the noise growing too large.

Second question would be why do we do polynomials? Well, basic operations here are just additions and multiplications, which gives only polynomials - but it can represent any function so it's ok!


How many bits of plaintext are required to verify a stream cipher key? If a stream cipher has an $n$-bit internal state, how many bits of known plaintext are required to confirm that particular key is the key?

I believe that the answer is at least $n$-bit's of plaintext. My reasoning is that an $n$-bit state would allow it to generate at most $2^n$ different key-streams, assuming it was a perfect bijection onto the first $n$-bits - which it probably isn't. Is this correct?

At least $n$ typically more. If you have no IV, as in classical setups, you need to do a state transition analysis. If there is an IV then the (key +IV) mixing phase also needs to be analysed and the answer is most likely probabilistic.

In short, the bijective mapping you're talking about is very very rare in a well designed stream cipher.


UMAC: to what extent is it in use today? Inspired slightly by the Encrypt-then-MAC question. The most obvious message authentication code is probably HMAC or RFC 2104 which is basically a hash of the input, an xor with a key... you get the idea.

However, I've also discovered UMAC which sounds very much like a hash function/lookup table to select an appropriate hash for use in a MAC, via, crucially, "some secret process".

Is selecting an algorithm secretly in this way secure? Is the only secret in UMAC the algorithm in use, or does it combine some known secret as HMAC does? In other words, is it HMAC with a random H?

Finally, is this being used anywhere? HMAC has its own RFC whereas UMAC does not appear to have yet been so well adopted.

UMAC is described in full details in RFC 4418.

When the RFC talks about "secret selection", it really means "there is a secret key involved here". UMAC works with universal hashing, which can be viewed as a family of hash functions, and a key which selects which hash function we are talking of. The term "hash function" might be a bit confusing here, because this is not at all the same kind of beast than, say, SHA-256. These "hash functions" would be utterly weak if left alone in the wild.

So UMAC works like this:

There is a nonce which must be used only once; for each new message a new nonce value must be selected (this is extremely important).
There are two keys $K_1$ and $K_2$. $K_1$ selects the universal hash function $h$ in its family, while $K_2$ is used in a suitable function which can operate on a block; namely, the AES or another block cipher.
The input message is processed with $h$, and the output of $h$ is then encrypted by XORing it with $\mathrm{AES}_{K_2}$ (nonce)_.

The idea is that the hash function $h$ (selected by $K_1$) remains "hidden" by the final encryption. Thanks to the nonce, and assuming that the final encryption is decent, successively MACed messages leak no information whatsoever on $h$ to the attacker. This is valid even in the presence of a very lightweight $h$, much faster than a conventional hash function.

UMAC is not much used by itself, because it is quite recent, and the nonce is a hard requirement, quite similar to IV management for block ciphers. HMAC is much easier, in the sense that it is much harder to get it wrong. UMAC or UMAC-like systems are however quite popular when integrated with encryption, because the nonce/IV requirement can then be shared. This is how OCB and GCM work, for instance.


What happens if I remove client certificate from TLS If I have a TLS authentication process between two entities A and B, like the one outlined below, what would happen to it, if I remove the client's (A) certificate from it? In this case, the certificate of the client is defined as {A,pk(A)}inv(pk(s)).

A->B: A,NA,Sid,PA

B->A: NB,Sid,PB,
  {B,pk(B)}inv(pk(s))
A->B: {A,pk(A)}inv(pk(s))
{PMS}pk(B),
{hash(NB,B,PMS)}inv(pk(A)),
{|hash(prf(PMS,NA,NB),A,B,NA,NB,Sid,PA,PB,PMS)|}
  clientK(NA,NB,prf(PMS,NA,NB))

B->A:   {|hash(prf(PMS,NA,NB),A,B,NA,NB,Sid,PA,PB,PMS)|}
  serverK(NA,NB,prf(PMS,NA,NB))

Of course the client loses it's way of authenticating itself with the server (B), but in what way exactly does this make the message exchanges vulnerable to attacks?

Another way to frame the question would be by looking at the Wiki description of the TLS handshake. In the client-authenticated TLS handshake, what would happen if we omit the client certificate?

As SEJPM already has indicated, if you loose the client certificates the server loses client authentication and thus all the data authenticity and even confidentiality under active (man-in -the-middle) attacks.

On the internet this is usually not a big problem for e-commerce. The client can still authenticate the server and have a secure connection. The server doesn't care too much - it simply authenticates the payment transaction.

On the other hand, for e.g. B2B connections the lack of authentication on one side can be catastrophic.

Note: the client certificates is required for client authentication. If you leave it out you'll end up with regular server authenticated TLS.


Can Shor's algorithm factor multi-prime numbers? I know that Shor's algorithm can factor semi-primes ($N = p \times q \space, \{p, \space q \in \Bbb{P} \space \vert \space p, \space q \gt 0 \} $).

Assuming that all prime numbers are so large that it's infeasible to compute with any known classical algorithm, can Shor's algorithm also factor multi-primes, meaning where $N$ has more than two prime-factors?

Shor's algorithm works by using quantum magic to compute a period of $f\colon x \mapsto a^x \bmod n$ for random $a$; if it gives $2t$ so that $a^{2t} \equiv 1 \pmod n$, and if $a^t \not\equiv -1 \pmod n$, then $\gcd(a^t \pm 1, n)$ is a nontrivial factor of $n$.  (Otherwise, repeat with another $a$.)  If $n = p q r$ and $\gcd(a^t \pm 1, n) = p$, then you can lather, rinse, and repeat for $n' = n/p = q r$.

The cost is dominated by $(\lg n)^{2 + o(1)}$ qubit operations to compute $f$—that is, it is quadratic in the size of the modulus $n$.

Post-quantum RSA chooses $n$ so large that this quadratic gap is infeasible for an attacker (of course, merely using pqRSA is also only barely feasible as a joke for well-funded users), but that's not the only avenue for attack:

If a prime factor is bounded by $y$, then $\gcd(f(n, u), n)$ may be a nontrivial factor of $n$, where $f(n, u)$ is a product of many distinct primes below $y$ modulo $n$, randomized by $u$—e.g., trial division, Pollard's $\rho$, ECM, etc.  If $n = p q r$ and you find $u$ so that $\gcd(f(n, u), n) = p$, then you can lather, rinse, and repeat for $n' = n/p = q r$.

Grover's algorithm finds a preimage of 0 under $u \mapsto [\gcd(n, f(n, u)) = 1]$ in the time for about $\sqrt{y}$ quantum evaluations of $f$.  For the best $f$, ECM, where $u$ is a random curve choice, the combined cost of Grover-ECM is $L^{1 + o(1)}$ where $L = e^{\sqrt{\log y \log \log y}}$—that is, it is superpolynomial but subexponential in the size of the factors $p$, $q$, and $r$.

Consequently, post-quantum RSA chooses $p$, $q$, $r$, and millions of other factors, to be 4096 bits apiece so that this superpolynomial/subexponential gap is infeasible for an attacker while the user can still compute arithmetic modulo $p$, $q$, $r$, and the other factors individually at reasonable cost.


Generating an IV for AES-CBC I am faced with the task of generating a secure 256-bit IV for AES-CBC. I possess the following resources:

A 32-bit microprocessor
A 32-bit PRNG (can read/reseed)
A 64-bit clock counter (can read)

The first one is unpredictable, but repeating. The second is non-repeating, but predictable. I am looking for a computationally lightweight way to combine them to achieve a high degree of unpredictable non-repeatability.

By "computationally lightweight" I mean that no cryptographic or other costly operations may occur. Only arithmetic operations on 32-bit registers, and not a lot of them for each IV.

Some working assumptions:

rate: $10^6$ IVs/second
rekeying: not faster than every few hours

Any pointers?

UPDATE:
The PRNG is an LSFR.
Switching to CTR: I'll think about it.
256-bit IV: Yehuda is right, 128-bit it is.

I'm thinking of something along the lines of reseeding the PRNG with the 32MSB of the clock counter, reading a few values, then reseeding with the 32LSB and reading a few more.

If you have a nonrepeating (but possibly predictable) value, you can convert that into an unpredictable CBC-mode IV at fairly minimal cost.  Here's how:

Prepend the 128 bit nonrepeating value to the message
CBC mode encrypt the (value, message), using any IV that's not correlated to the nonrepeating value (all 0's work)
Use the first 16 bytes of the resulting ciphertext as the 'IV', and the rest of the message as the 'message'; don't send the all 0's IV you actually used.

Surprisingly enough, this works, both in the sense that normal CBC-mode decryption will decrypt the message you sent into the original message, and in the sense that the IV you use is completely unpredictable to anyone who doesn't know the AES key.

CBC mode processes the first block as:

$$C_0 = E_k(IV \oplus P_0)$$

In this case, we have $P_0$ being the nonrepeating value; this remains unrepeated after we xor in the all-0's IV value.  The AES encryption of a value that hasn't been seen before is unpredictable; since $C_0$ is the value we use as our effective IV, we meet the goal.

CBC mode then processes the second block as:

$$C_1 = E_k(C_0 \oplus P_1)$$

Now, $C_0$ is the value we sent as the IV; $P_1$ is the first block of the plaintext message we want to send; this matches up exactly to what we would normally do in CBC mode.

If we continue in the rest of the message, we find that it also matches what normal CBC mode encryption processing would be.


Can keyed CRC be used as a MAC? Consider a "MAC" that uses a symmetric key $K$ to generate an authentication tag $t$ for a message $M$ in the following way:

Concatenate a timestamp with the message (to prevent replay attacks)
$$
m = \mathit{Timestamp}\mathbin\Vert M
$$
Divide into suitable number of blocks.
$$
m = m_0\mathbin\Vert m_1\mathbin\Vert m_2\mathbin\Vert\cdots\mathbin\Vert m_n
$$
Compute CRC of a symmetric key concatenated between each block. (CRC algorithm is known - CRC-16/CCITT/CRC32).
$$
t = \operatorname{CRC}(K\mathbin\Vert m_0\mathbin\Vert K\mathbin\Vert m_1\mathbin\Vert K\mathbin\Vert m_2\mathbin\Vert\cdots\mathbin\Vert K\mathbin\Vert m_n)
$$
Send $C=\mathit{Timestamp}\mathbin\Vert M\mathbin\Vert t$ as the message.

Is this scheme suitable for message authentication against known plaintext attack given a large enough key size, with the assumption that it is infeasible to brute-force all $t$ during the time when $\mathit{Timestamp}$ is valid?

I have seen the following papers, however, they both say that the CRC polynomial must be a secret.

https://eprint.iacr.org/2015/035.pdf

https://eprint.iacr.org/2015/1138.pdf

Slightly related, but it uses an encrypted CRC as a MAC. I'm asking about using CRC as a MAC where the Key is included in the CRC calculations.

Is there a generic attack on encrypted CRC32 when used as a MAC?

Edit: Use case: I have hardware CRC module in a microcontroller that can evaluate CRC asynchronously with the core performing other computations. I am seeing if I can use this CRC module for message authentication as well.

Trivial forgery: If you know the CRC polynomial, then you can add (‘xor’) any multiple of it to the message without changing the CRC.

Short answer.
If the hardware can only evaluate CRCs with fixed polynomials determined by the hardware designer, it's of little use to you for making a MAC.  If you can choose the polynomial and the hardware keeps it secret, well, you've already found some references on how to do this!

The standard way to make a MAC out of a CRC, which we might call a polynomial division MAC and is sometimes called Rabin fingerprinting after a similar idea by Rabin, is to choose a secret irreducible polynomial $g \in \operatorname{GF}(2)[x]$ and a secret polynomial $h \in \operatorname{GF}(2)[x]$ both of degree $d$, uniformly at random; then, to authenticate a single message polynomial $m \in \operatorname{GF}(2)[x]$, transmit the polynomial $h + (m \cdot x^d \bmod g)$ as an authentication tag.

(The Rabin fingerprint is simply $m \bmod g$; it preserves addition of any degree ${<}d$ polynomial to $m$, enabling trivial forgery even if masked by $h$, so it is useless as an in-band authenticator, though it is more convenient for other purposes.)

By a standard result of number theory (alternative exposition), when $d$ is prime, there are $(2^d - 2)/d$ irreducible polynomials of degree $d$; for composite $d$ there are fewer, so prime $d$ gives the most efficient key space.  But this does not cover all $d$-bit strings, and to generate a key, choosing an irreducible polynomial uniformly at random, e.g. using the algorithm in Rabin's paper (pp. 3–4), is costly.  Using a product of irreducible polynomials whose degrees sum to $d$ enables cheaper key generation, but key space and tag space is wasted even more than with an irreducible $g$—the forgery probability is exponential in the number of irreducible factors.

Worse, computing polynomial division in $\operatorname{GF}(2)[x]$ by an arbitrary divisor is costly.  Some CRC hardware admits programmable generator polynomials, but typical hardware uses a fixed polynomial, such as the Intel CRC32 instruction, which is useless for this—not to mention that a 32-bit tag is too small to provide any security.  And in software implementations one is tempted to use table lookups to get any semblance of performance—invariably leaking secrets through timing side channels.  So it's dangerous to design this into any protocols, because you're designing the temptation of timing side channels into the protocols.

There are perfectly good efficient MACs already for hardware and software: polynomial evaluation MACs.  Fix a field $k$; a one-time key is a pair of elements $r, s \in k$ chosen uniformly at random, a message is a polynomial $m$ in $k$ of degree at most $n$, and the authenticator of the message is $t = m(r) + s$.  The adversary's probability of success at forging a tag $t'$ on a message $m' \ne m$ given $m$ and $t$ is no more than $\#k/n$, by a standard argument of counting roots of the polynomial $m'(r) - m(r) + t - t'$ in the variable $r$.  The most common examples are Poly1305, where $k$ is the prime field $\mathbb Z/(2^{130} - 5)\mathbb Z$ convenient in software, and GHASH, where $k$ is the binary field $\operatorname{GF}(2^{128})$ convenient in hardware.

Generating keys—picking elements of a field uniformly at random—is fast: for a binary field, uniform random bit strings work; for a large prime field (${>}2^{128}$), rejection sampling on uniform random bit strings works, and the probability of rejection is so small you can ignore it safely.  Derive $r$ and $s$ from a PRF of a message sequence number or a sufficiently large random token and you get a many-time MAC.

The only reason to reach for a polynomial division MAC instead of a polynomial evaluation MAC is the bizarre scenario where (a) you do not have fast binary polynomial multiplication or integer arithmetic available, yet (b) you do have hardware that can efficiently evaluate polynomial division by arbitrary degree-${\geq}128$ divisors, and these performance constraints override all other considerations in your protocol design.


How small is negligible? When proving theorems in crypto we often make use of the concept of negligible functions or, more simply, negligible parameters.

As a rule of thumb, given today (2018) computational power, what is the smallest inverse power of 2 that we can consider negligible?
I expect this to be something around $2^{-64}$.

Negligible is a human term, not a precise definition.  It refers to things which are sufficiently small that one is willing to ignore it in the interests of expediency.  The threshold varies from person to person: a NSA mathematician will have a different threshold for a property than a CEO of a startup will).  It also varies from topic to topic: $2^{-64}$ solar masses is still a solid quarter of the entire biomass of humans put together!

In my experience, the proof of negligability is often not how small the number is, but how large its inverse is.  Its inverse is often highly associated with some real practical number, like how much energy it takes to crack an algorithm, or how many years.

For example, the risk associated with the brute forcing of a 256-bit key is negligibly small.  This is because we can calculate how much energy it would take to count that high, much less run the algorithm that many times.  I did the numbers once, with ultra-idealized hardware running in the cold of space, it takes about 3/4 of the energy in the galaxy to run that counter from 0 to $2^{255}$