RSA with probable primes I am a bit of a newbie to RSA encryption, so please be patient.

I understand that for a 4096 bit RSA, the numbers p and q should be prime. And to have the best security, the p and q should both be about 2048 bits long.

However, we don't have a way of generating and verifying a 2048 bit prime number with 100% accuracy. The implementation for prime generation that gpg uses goes through 64 rounds of miller-rabin which is enough to give a prime probability of $1 - 2^{-128}$.

Given that these primes are only probabalistically prime, what happens if we selected composite values for p or q?

Does the RSA algo run into any sort of problem?

My guess is that there will be no problem and RSA continues to function normally (encryption and decryption both) because, if there was a problem, we could use that problem as a way to detect that the numbers are not prime. This would give us a really fast way to verify extremely large prime numbers. I am guessing this is not the case.

So, my conclusion is that RSA works with prime or composite p, q... but using composite p, q makes it easy to break the encryption (because its easier to derive p, q from n).

Is this conclusion correct?

The premise "we don't have a way of generating and verifying a 2048-bit prime number with 100% accuracy" is wrong (if we trust the computers performing the operations): it has long been known practicable ways to generate randomly-seeded provable primes, and it is a (somewhat marginal) practice in RSA key generation (see FIPS 186-4 appendix B.3.2). We can even practically prove (or disprove) the primality of an arbitrary 2048-bit integer, using a number of methods, including (as pointed in comment): Daniel J. Bernstein, Proving primality in essentially quartic random time, in Mathematics of Computation 76 (2007), 389–403 (which is a randomized test giving a certainty; only the time it takes to reach certainty depends on the particular randomness used). Or better (as pointed in another comment) APR-CL or ECPP.
However this is complex, and practical cryptography is happy with a simpler probabilistic primality test. Notice that 64 rounds of Miller-Rabin test against a 2048-bit integer one have randomly drawn (which is the case in RSA key generation), rather than received from a potentially hostile party, are way overkill to rule out compositeness with residual odds less than $2^{-128}$; 4 rounds are more than enough, see FIPS 186-4 table C-2, with justification in appendix F and its reference: Ivan Damgard, Peter Landrock, and Carl Pomerance, Average case error estimates for the strong probable prime test, in Mathematics of Computation 61 (1993), 177–194.

If we accidentally try to perform RSA with one of $p$ or $q$ composite (because an error crept in the implementation of the primality test), the usual formulas $\varphi(p\cdot q)=(p-1)\cdot(q-1)$ or $\lambda(p\cdot q)=\operatorname{lcm}(p-1,q-1)$ will lead to an incorrect value, and with overwhelming odds, decryption or signature verification will fail on the first real use (assuming non-malicious choice of $p$ and $q$, and a random message or proper padding is used). In a PKI context, the verification by the certification authority of the public-key certification request (which is customarily self-signed) will almost certainly fail.
That's because successful use of RSA with a random message constitutes a powerful primality test of $p$ and $q$, essentially performing a Fermat test for $p$ and $q$; that is less powerful than a Miller-Rabin test, but still very effective for random $p$ and $q$. However (just as all practical primality tests for large integers), it gives an indication of compositeness, but does not reveal a previously unknown factor; that's where the reasoning/intuition in the question breaks.
More precisely, assume $e$ and $d$ follow the necessary and sufficient condition to be matching public and private exponents in two-primes RSA, that is $e\cdot d\equiv1\pmod{\operatorname{lcm}(p-1,q-1)}$.
Equivalently $\exists u\in\mathbb N, e\cdot d=1+u\cdot\operatorname{lcm}(p-1,q-1)$.
By setting $v=\gcd(p-1,q-1)\cdot(q-1)$, we get $e\cdot d=1+u\cdot v\cdot(p-1)$.
Now if for some random $x<N$, we verify that ${(x^e\bmod N)}^d\bmod N=x$ (that is, textbook RSA encryption then decryption for $x$ yields back $x$), by reducing modulo $p$ we see this implies $x^{e\cdot d}\equiv x\pmod p$, thus $x^{1+u\cdot v\cdot(p-1)}\equiv x\pmod p$, thus (except if $\gcd(x,p)\ne1$, which is improbable) ${(x^{u\cdot v})}^{p-1}\equiv 1\pmod p$.
Our RSA encryption/decryption test has performed a Fermat test for $p$ with witness $x^{u\cdot v}\bmod p$, and this witness is quite random if things are non-maliciously crafted (e.g. $q$ is chosen independently of $p$, and $d<N$).
An exception pointed in comment is when the composite $p$ that crept-in happens to be a Carmichael number. These are (rare) composites such that $x\not\equiv0\pmod p\implies x^{p-1}\equiv 1\pmod p$; that is, no Fermat test can detect that a Carmichael number is composite!
Correspondingly, RSA will "work" with Carmichael numbers instead of primes, but will be arguably less safe than if $p$ was prime because $p\cdot q$ will be relatively easy to factor: if $p$ is 2048-bit, it will have at least one factor of less than 682-bit (or less if $p$ has more than three factors). However this won't happen by chance, because Carmichael numbers are very rare: by far the most abundant kind has three factors, and there are no more than $x^{5/14+\mathcal o(1)}$ of these below $x$ (see R. Balasubramanian and S. V. Nagaraj, Density of Carmichael numbers with three prime factors, in Mathematics of Computation 66 (1997), 1705-1708). A random 2048-bit integer has odds less than $2^{-1300}$ to be a Carmichael number. Hence if $p$ is a Carmichael number, this could only have happened by malicious intend: in addition to the primality test, the random selection of $p$ is intentionally flawed, and the possibility of factorization of $p\cdot q$ using that it has a small prime factor is a comparatively moot issue.


Why use an OTP if you already have a secure channel Let's say I have some sensitive information, and I want to encrypt it with a OTP and send it to the FBI or something. Now, in order for the recipient to successfully decrypt the message, he needs to know the OTP key as well. But, you don't just send the key as plain text to the recipient, this is fairly obvious since an adversary can obtain it with ease. So then what? You use a secure communication channel to share the key. This is where my brains stop working. Why share the key of a OTP through a secure channel, and not just share the sensitive information itself through that secure channel?

First, let's re-iterate that there is no true one-time pad in modern cryptography or any other information system - it's only a hypothetical thinking reference.

The reason to use OTP in this case, would be to maximize the utility of the rare window where there would be a secure channel.

Let's imagine a world without internet and public-key cryptography cannot be carried out efficiently by any instrument available to the people and the enemy, the secure channel is a scarce resource, so a huge OTP stream is exchanged here so that it may be used later over the radio, possibly chunked according to the size of messages.

This way, the time to exchange the actual (encrypted) message can be freely chosen.


How does the ROCA attack work? I have been trying to understand the ROCA attack described here as the "First Attack" and I cannot follow the explaination.

I have been trying to generate a 512-bits key and crack it. As far as I can understand, $p$ and $q$ are $65537^a \bmod L$ where $a$ is random and $L = 2\cdot3\cdot5\cdot7\cdot\dots$. If at one point, I find out what $p$ or $q$ is, than I can find the other one easily and then compute the private key.

Is this correct? I am sorry if I do not make any sense and any hint to the right solution is greatly appreciated.

In the ROCA paper the authors define an integer $M$ (which they call a primorial) as follows:

$$M = \prod_{i=1}^{n} P_i = 2 * 3 * ... * P_n$$

Said another way, $M$ is the product of the first $n$ primes. What the authors observed is that the factors of a vulnerable RSA modulus $N$ have the following form:

$$p = k*M + (65537^a \text{ mod } M)$$

The $65537 (= \mathtt{0x10001})$ might look a little odd hardcoded, but it's a common choice for the public exponent of an RSA key as it has a low hamming weight and thus allows some speed gains in common public key operations.

In the case you are interested in, where $|N| = 512$ bits, we have $n = 39$ and thus $|M| = 219$ bits. Since the size of the prime factors of $N$ is $\frac{|N|}{2} = 256$ bits this implies:

$$|k| = \frac{|N|}{2} - |M| = 256 - 219 = 37$$
$$|a| = \mathbb{log}_{2}(\mathbb{order}_M(65537)) = 62$$

So to generate a vulnerable $512$ bit RSA public key do the following:

Randomly sample a $62$ bit value $a'$ and a $37$ bit value $k'$.
Compute $p' = k'*M + (65537^{a'} \text{ mod } M)$.
Check that $p'$ is prime, if yes it is one of your factors $p$, if not go back to step 1.
Sample another prime $q$ using steps 1-3.

Your vulnerable RSA public key $(N, e) = (p*q, 65537)$.

On to the attack. If $M$ is known, our prime factor $p$ now only has $|k| + |a| = 37 + 62 = 99$ bits of entropy rather than the $256$ bits of entropy that it should. This is not good. The "naive" ROCA attack works in the following way:

Select a guess for the value of $a$ and compute $65537^{a} \text{ mod } M$.
Given $65537^{a} \text{ mod } M$ and the relationship $p = k*M + (65537^a \text{ mod } M)$ use Coppersmith's Algorithm to recover $k$.
Compute $p$ using the recovered $k$ and check if $N \text{ mod } p = 0$. If so, $p$ is a factor of $N$. If not,go back to step 1. and select the next guess for $a$.

The time complexity for this attack is $\mathcal{O}(2^{|a|}) = \mathcal{O}(2^{62})$ since in the worst case we have to check every possible value of $a$. Note that the search space of $a$ is the size of the group that $65537$ generates $\text{ mod } M$.

Now I said "naive" ROCA attack above because the authors optimize this attack by finding a value $M'$ such that the following relationship still holds:

$$p = k*M' + (65537^a \text{ mod } M')$$

But they find $M'$ in such a way that the size of the group $65537$ generates $\text{ mod } M'$ is much smaller than $\text{ mod }M$. Thus the search space for $a$ is also much smaller, and ends up bringing the time complexity down to $\mathcal{O}(2^{20})$. The actual process for finding $M'$ is rather involved, if you'd like to know the details I'd suggest diving into the paper.


Attack against modular inversion operation using side-channels? I'm building a device that performs a modular inversions using a secret modulus. I would like to know if it is possible to recover all or part of this modulus by side-channels (timing, power, EMR, etc.).
All information I found related to side-channels in modular arithmetic applies to modular exponentiation.
The algorithm used for inversion is the standard Extended Euclidean algorithm.
The attacker may be able to measure, for example, computing time. He does not have access to the output, nor to the modulus. He knows only the value that will be inverted.
Update: found a relevant reference

Because the time that the Extended Euclidean algorithm depends on the inputs (and, in particular, is a complex function of the two, depending on the ratio expressed as a continuous fraction), there may be some leakage there.
It occurs to me, however, that there is a very simple countermeasure; assuming that the secret modulus you are inverting by is $p$, and that the value you want to invert is $x$:

Select a random number $r$ that is $0 < r < p$ and is relatively prime to $p$ (and the latter condition is trivial if $p$ is prime)

Compute $blind = r \times x \mod p$

Compute the modulus inverse $blindinv = blind^{-1} \mod p$ (using the Extended Euclidean algorithm)

Return the value $result = r \times blindinv \mod p$

It is easy to see that this computes the modulus inverse correctly, and the value given to the underlying modulus inverse function is uncorrelated to the original value $x$ (and that the additional cost of the two modular multiplications is trivial compared to the cost of the modular inverse).
Is this really required?  I don't know; however, it seems to me that the above is so cheap that even if there is a chance of weakness, this randomization looks warranted.
Now, this hides the value being inverted from the attacker, but it doesn't apply a blinding factor to $p$; however while the time taken on average (given unknown inputs) by the EE algorithm does vary somewhat based on the modulus, it is a much weaker function (and gives far less information).  Blinding $p$ would be considerably more expensive; whether you would want to do so depends on the risk of any such leakage (e.g., if it's the country's missile defense codes, you probably will be willing to pay the additional costs), as well as how much you can afford additional costs.
If you are willing to pay the additional cost, the obvious way would be to select a value $r'$ that's relatively prime to $x$ (e.g., a prime larger than $p$), and in steps two and three, compute
$blind = r \times x$
$blindinv = blind^{-1} \mod (p \times r')$
(and the rest of the algorithm stays the same; the $\bmod$ operation in the next step will discard the extra information included by the $r'$ factor)
Assuming you pick $r'$ values about the same size as $p$ (or slightly larger), you would approximately double the cost.


Security proof of mix net I am writing an exercise in cryptography about anonymous communication. One of the systems I have looked into is the mix net protocol. I want to prove that this is secure. I have seen many different ways of doing this, i.e. using a zero knowledge proof, but I don´t completely understand this.

Is there anyone who has a good explanation of why the mix net is secure?

Security in mixnets usually means two things. Anonymity and integrity.

For anonymity a single honest mix server suffices. Even if all other mix servers cooperate by releasing their permutations a message cannot be tracked, since the honest one does not publish his permutation. As a result it is lost when it reaches it.

For integrity zero knowledge proofs can be used.

Imagine you have a 2x2 reencryption mixnet with inputs:  $C_1 = Enc(m_1,r_1)$ and $C_2 = Enc(m_2,r_2)$.

The mixnet reencrypts the inputs and computes ${C'}_1 = Reenc(C_1)=Enc(m_1,r_1+r_1')$ and ${C'}_2 = Reenc(C_2)=Enc(m_2,r_2+r_2')$.

Then it selects a random bit $b$ and outputs $({C'}_1, {C'}_2)$ if $b=0$ and $({C'}_2, {C'}_1)$ if $b=1$.

In order to prove integrity one must prove that the output is a reencryption of the input without revealing the value of $b$. More specifically the statement $(C'_1 = Reenc(C_1) \wedge C'_2 = Reenc(C_2)) \bigvee (C'_1 = Reenc(C_2) \wedge C'_2 = Reenc(C_1))$ must be proved in zero knowledge.

This can be done using composition of the Chaum - Pedersen Protocol for DLOG equality.

For more details you can check Rivest's course in http://courses.csail.mit.edu/6.897/spring04/materials.html


Why not use `` or `==` in constant time comparison? I am comparing secret data stored in arrays a and b to see which holds a greater value.  My current (pseudo)code looks like this:

unsigned char smaller = 0, bigger = 0;
for (i = 0; i < size; ++i) {
   smaller |= (!bigger)  & (a[i] < b[i]);
   bigger  |= (!smaller) & (a[i] > b[i]);
}
return bigger;

But when I look at (for example) sodium_compare, I see they are not using the < or > operators. Instead they subtract values and do some bit-operations, amongst which shifting a byte by 8 (as a sidenote: doesn't that result in undefined behaviour in C?).

Is there a reason for avoiding the < and > operator?

Similarly, constant-time comparison for equality is usually implemented by taking the byte-wise xor (^) and take the or (|) of all values. Is there a reason for prefering ^ over == in that situation?

C comparison operators (strictly relational < <= > >= and equality == !=) yield 1 if the condition is satisfied and 0 if not. On some implementations (compilers) depending on the CPU and sometimes options, this may be implemented by code something like:

; int a = ..., b = ...;
; int x = a > b;
  move a, r0
  compare r0, b ; sometimes subtract with value ignored and only flags used
  bgtr lab1
    move 0, r1
    br lab2
lab1:
    move 1, r1
lab2:
  move r1, x

This executes a different sequence of instructions depending on whether the condition is true or false. Depending on the CPU, and if it has branch prediction/speculation as many (not all) do today depending on whether the conditional branch is predicted correctly which in turn depends on lots of other factors that are usually impossible to fully analyze, this may take different amounts of time which may be detectable (although typically damn small).

Some modern CPUs have conditional-move instructions, or even logicize-flag(s) instructions, that avoid this problem, but when writing source to be ported to unknown compiler versions and environments you can't be certain these will be present and (if so) used.

Actually you aren't guaranteed that even bitwise operations are constant time but in practice they're your best bet.

Similarly the logical negation operator ! in your code may be implemented by something like this which is not constant time:

move x, r0
test r0 ; sometimes included in the move
bzer lab1   ; (EDIT)
  move 0, r1
  br lab2
lab1:
  move 1, r1
lab2:
; use r1 as result

No Undefined Behavior:

Shifting by a count greater than or equal the width of the left operand is UB. Even when it comes from an unsigned char as in the code you linked, the left operand of a shift is subject to the Integer Promotions of 6.3.1.1 (though NOT the Usual Arithmetic Conversions of 6.3.1.8) and so the left operand always has a width of at least 16 and they shift by 8 which is okay.

Also left shifting a signed type with a negative value or a value that overflows (i.e. at least one of the high N magnitude bits of the input is nonzero) is UB. They don't shift left.

Right shifting a signed type with a negative value is Implementation Defined: the sign bit may propagate or shift out. They do shift right values that are sometimes negative, but they immediately mask the result so that the bits which could be affected by this IB are not used.


Format Preserving Encyption question I've got a theorical question from an exercise.
Here it is:

--- Exercise beginning ---

There are ways to convert a block cypher onto an FPE. One of them is the following:

Let $E_{k}$ a cryptographic primitive with size n.

$FPE_k(x)$ a cryptographic primitive with $P = C = {0,1,..., m-1} $ with $m < 2^n$

The pseudo-code looks like this

fpe = x
do {
     x = fpe
     fpe = Ek(x)
} while(fpe >= m)

It could be interesting to use this functions to create cupon codes.
For example, if we consider cupons as numbers of 20 digits, we could generate 10000 cupons encoding numbers from 0 to 9999.

--- Exercise ending ---

Now my questions are:

1) I do get that encoding numbers from 0 to 9999 you get 10000 possible encodings, what I don't get is that how to you get 20 digit encodings?
As far as I understand with FPE you always get the same length so if you encode numbers from 0 to 9999 you'd get ciphers between the same values.

2) The exercise asks what is the probability of an attacker to generate a valid cupon?

Not sure if I am correct about this, but let me give it my best.

I do get that encoding numbers from 0 to 9999 you get 10000 possible encodings, what I don't get is that how to you get 20 digit encodings? As far as I understand with FPE you always get the same length so if you encode numbers from 0 to 9999 you'd get ciphers between the same values.

It seems that the problem assumes that all numbers are written as 20-digit nature numbers. So for the number 45 you might have '00000000000000000045'. This keeps all of your numbers in the same size and format. It also means that the output space is quite large (10^20).

The exercise asks what is the probability of an attacker to generate a valid cupon?

Well, the attacker doesn't know the values of the input numbers (and the input coupon numbers don't necessarily need to be 0 through 9,999, rather, they can be any 10,000 numbers in the space. So that means that the attacker will likely have to try a random input number and then check with the server if the coupon has value. As there are 10,000 valid coupons (10^4) and a space of 10^20, we can simply divide to get 10^4/10^20. So 1/10^16 chance of hitting a valid coupon code.

Hope that answers your questions.


Possible to determine equivalence of hash codes from different hashing functions? Let $H_{1}(x)$, $H_{2}(x)$, ..., $H_{n}(x)$ be a list of $n$ secure one-way hash functions such that for a given input $x$ each $H_{i}(x) \neq H_{j}(x)$ when $i \neq j$.  Give one hash function to each of $n$ people.  No person should be able to reproduce the output of any other person's hash function.

For any inputs $x,y$ with $x \neq y$, is it possible to define a comparison function $F$ such that $F(H_{i}(x),H_{j}(x)) = true$ and $F(H_{i}(x),H_{j}(y)) = false$?

In other words if each person creates hash codes of the same inputs using different secure one-way hash functions, can I tell what hash codes were derived from the same input?

Actually, if you define the $H_i$ functions properly, it can be done.

I'll make the simplifying assumption that we can treat the $H_i$ and $F$ functions as Oracles (that is, you're not allowed to look inside their implementation); I believe that it's still possible without that assumption (but the solution may be more complex).

For our primitives, we'll use FF1 with a secret key; and define:

$$H_i(x) = FF1_{key}( SHA256(x) || i )$$

This meets all the requirements of a secure hash function (e.g. it is collision resistant if we assume SHA256 is); in addition, the holder of $H_i$ cannot use it as a Oracle to compute $H_j$ for $i \ne j$ (as they don't know the $key$)

And, we can define a function $F$ that uses the secret key to decrypt both encrypted hashes, and compares the SHA256 values.  This will correct tell if the two original messages where the same (unless we happen apon a collision in SHA256)


What is different between a hash function and permutations with repeats Are secure hash function outputs different from permutation sets of the same length and value? If yes please explain how they appear differently.

For example, MD5 would produce

8743b52063cd84097a65d1633f5c74f5

A non standard permutation algorithm that is impossible to inverse without a key would appear to be the same and be just as secure.

Are secure hash function outputs different from permutation sets of the same length and value?

Yes, almost certainly because both tend to produce randomized output, and it is unlikely that they will both end up with the same output for the same input message. In principle they may differ in size of course, SHA-224 output is hard to reproduce using a repetition of a 128 bit block cipher.

  If yes please explain how they appear differently.

Ah, now you're talking about appearance. Well, generally the output is randomized so they will be indistinguishable from each other. Of course, with a hash, if you can guess the input message then you can see if the hash value matches that. For block ciphers we generally assume that the adversary doesn't know the key, so that's not possible.

  A non standard permutation algorithm that is impossible to inverse without a key would appear to be the same and be just as secure.

Why would you use a "non standard permutation algorithm"? Remember Kerckhoff's principle! We generally use a keyed permutation which selects a permutation from a limited set of permutations. Assuming that it is reversible this is called a block cipher.

More importantly, now you are suddenly comparing security properties. So that's the third different comparison: comparing values, comparing appearance and comparing properties!

First of all, you seem to be basically compare a MAC and a non-keyed hash function. The MAC function is generally more secure for most situations, as an adversary cannot perform an offline search for collisions without the key.

Second, just repeating a specific permutation (e.g. twice 64 bits for a 128 bit output) is not a secure MAC. For starters, it doesn't provide compression, and moreover, it leaks information if the message is evenly split into two blocks with the same information. Similarly, these blocks may also be found in previous messages.


Isn't Socialist Millionaires vulnerable if Alice's and Bob's message are picked from a shared list? I'm interested in a situation where Alice and Bob each pick cards from a deck of 52, and want to test if they picked the same card without revealing what the card is (a "mental poker" situation).  The protocol that came to mind was "Socialist Millionaires".

But if I'm correctly understanding the writeup of Socialist Millionaires that's currently on Wikipedia, and if that writeup is accurate, then I think that it's possible for Bob to learn Alice's secret message (and vice versa) if they are both picking their secret messages from a shared list, such as the card-drawing scenario.

The trick I thought of is that, after the protocol is finished, Bob has enough information that he can pick different values of his secret and test them.  If they just picked from 52 cards, he just has to test 52 values of his secret message until he gets a "yes they are equal", and then he'll know what Alice has.

Using the notation from the wiki article, the answer to the question of whether $c = P_aP_b^{-1}$ is equivalent to the answer to the question of $x=y$, where $x$ is Alice's secret message and $y$ is Bob's.

The wiki article says

Note that
:\begin{align}
  P_aP_b^{-1} &= \gamma^r \gamma^{-s} = \gamma^{r - s} \\
              &= h^{\alpha\beta(r - s)}
\end{align}

and therefore
:\begin{align}
  c &= \left(Q_aQ_b^{-1}\right)^{\alpha\beta} \\
    &= \left(h^r g^x h^{-s} g^{-y}\right)^{\alpha\beta}
     = \left(h^{r - s} g^{x - y}\right)^{\alpha\beta} \\
    &= \left(h^{r - s} h^{ab(x - y)}\right)^{\alpha\beta}
     = h^{\alpha\beta(r - s)} h^{\alpha\beta ab(x - y)} \\
    &= \left(P_aP_b^{-1}\right) h^{\alpha\beta ab(x - y)}
\end{align}.

Now, it seems to me that Bob knows $c$ from a Diffie-Hellman Key Exchange they did earlier.

$P_a$ and $P_b$ were transmitted in the clear, so Bob can calculate $\left(P_aP_b^{-1}\right)$.

He knows $h^{ab}$ and $h^{\alpha\beta}$ from two other DHKE's they did.  So Bob can raise one to the power of the other and get $h^{ab\alpha\beta}$.

He knows $y$ because that's his secret message.

So if he wants to test against a new secret message ($y'$) offline, all he has to do is find:

\begin{align}
c_1 &= c\left(P_aP_b^{-1}\right)^{-1} \\
   &= h^{ab\alpha\beta(x-y)}
\end{align}

Then find:

\begin{align}
c_2 &= \left(c_1\right)^{y} \\
    &= h^{ab\alpha\beta x}
\end{align}

Now, Bob wants to test if Alice's card was a particular $y'$ that Bob has chosen.  So he calculates:

\begin{align}
c_3 &= c_2^{\left(y'\right)^{-1}} \\
    &= h^{ab\alpha\beta(x-y')}
\end{align}

Finally, he calculates:

\begin{align}
c_4 &= c_3\left(P_aP_b^{-1}\right) \\
    &= \left(P_aP_b^{-1}\right)h^{ab\alpha\beta(x-y')}
\end{align}

And if $c_4 = P_aP_b^{-1}$, then this means that $x=y'$ and Bob has discovered what Alice's card is.  None of these steps involved receiving new secret numbers from Alice or sending anything to Alice, so he can try for as many new $y'$ as he wants.  Alice can't stop him, or even know that he's doing it.

Bob can try for all 52 cards, and he can discover which one was Alice's secret $x$.

Am I right about this?  Is there something I'm missing?

The attack you are referring to is called an offline dictionary attack, which checks all possible values against a given transcript. However, the typical security notion for the socialist millionaires problem should forbid this attack. In fact, designing a protocol which is secure "except for offline dictionary attacks" is trivial: both players simply hash their input, with some public hash function, and exchange the outputs; if they are equal, then they own the same value; otherwise, they don't. Attacking essentially amounts to hashing all possible messages.

The protocol you describe is more complex, and it is in fact immune to such offline dictionary attacks; it's main purpose is essentially to avoid them. The error in your reasoning is the following sentence:

  He knows $h^{ab}$ and $h^{\alpha\beta}$ from two other DHKE's they did.  So Bob can raise one to the power of the other and get $h^{ab\alpha\beta}$.

This is not true: one can compute $h^{ab\alpha\beta}$ from $h^{ab}$ and $\alpha\beta$, or from $h^{\alpha\beta}$ and $ab$, but not from $h^{ab}$ and $h^{\alpha\beta}$. Computing $h^{ab\alpha\beta}$ from $h^{ab}$ and $h^{\alpha\beta}$ is equivalent to breaking the computational Diffie-Hellman assumption. In fact, under the decisional Diffie-Hellman assumption, $h^{ab\alpha\beta}$ is indistinguishable from random, even given both $h^{ab}$ and $h^{\alpha\beta}$. This is the observation that underlies the security argument for this protocol.


Do aes_256_gcm IVs just need to be unique for that key? I'm using GCM (via openssl's EVP_EncryptInit_ex(ctx, EVP_aes_256_gcm(), NULL, NULL, NULL))).

The IV's default length is 12 bytes.

It says that the IV must be unique, in the context of a particular key.

Does it matter if the IV is smaller or predictable?  I intend re-using a 64-bit sequence number and a 64-bit millisecond timestamp as an 8-byte IV.  So long as a restart introduces a 1ms delay, there can be no duplicate IVs.  (I will guard against 1970 timestamps.)

Is it necessary to add in some random bytes?  (These would need to be transported along with each message; I'm trying to keep the messages as small as is securely possible.)

If so, how many random bytes?

For GCM, IV can be predictable (contrary to some other modes such as CBC, there is no unpredictability or uniformness requirement), but they must not be reused. You are free to use any method you wish to ensure this uniqueness. If an IV is reused, then the "authentication key" is revealed, and the encryption itself becomes an instance of the "two-times pad", i.e. may leak a lot of information on the plaintext, depending on its format.

A timestamp is sort-of fine. The problem with timestamps is that they depend on a local clock, and since there is no such thing as a perfect clock, computers routinely include ways to adjust clocks, either manually or automatically. Note that automatic clock adjustment over the Internet uses NTP, which is usually unprotected (no authentication or encryption). Therefore, remote attackers may feed a connected system with fake NTP packets to force a clock adjustment and possibly an IV reuse.

Using a random value is a common way to achieve uniqueness with a high probability; with 96-bit IV, if you encrypt no more than $2^{32}$ messages with a given key, then probability of an IV collision (assuming a strong random source) will be at most $2^{-32}$, which is low enough to deter attackers (i.e. it's less worthwhile to wait for such an event than to simply buy lottery tickets).

Some extra notes:

GCM actually supports all IV lengths, not just "12 bytes". An IV with length exactly 12 bytes is used "as is" and lets you know exactly if you have a collision or not. If you use a 64-bit timestamp (assumed non-repeating), you are encouraged to "pad it" with 4 extra bytes (e.g. zeros) so that the GCM implementation receives a 12-byte IV (even if you do not actually transmit the padding bytes in the message on the wire).
Conversely, you could use a longer random IV. 16-byte random IV are arguably "better" than 12-byte random IV (it makes risks of collisions lower as long as individual messages are substantially shorter than 64 gigabytes, and collisions are less immediately detectable by attackers). But since you try to reduce on-wire size, I suppose you'd prefer not to do that.
In some contexts, you can get a non-repeating IV "for free". E.g., in a TLS connection, each connection has its own key, so that IV collisions matter only within a given connection. But then, messages ("records" in TLS terminology) are successive; thus, a simple sequence number can be used (first record gets number 0, second record gets number 1, and so on). The sequence number is implicit and thus needs not be transmitted at all.
There may be other solutions. For instance, a possible method would be to replace GCM with the following mode:

Let x be the IV (see below for its length) and m the plaintext to encrypt.
Compute HMAC/SHA-256 over the concatenation of the IV and the plaintext, and truncate it to the AES block size (16 bytes). This yields the authentication tag t.
Use AES-CTR encryption over m with t as IV; this yields the ciphertext m'.
Transmit x, t and m'.

With such a mechanism, you could use a very short IV x, even an empty one (of length 0). Note that this saves space, compared to GCM: with GCM, the encrypted message is sent along with an authentication tag (16 bytes) and an IV; here, I suggest use the HMAC-derived authentication tag as IV for encryption.

If you use that kind of mechanism with an empty IV x, then the whole thing becomes deterministic: if you encrypt twice the exact same message with the same key, then you get the exact same encrypted message. However, this should be the full extent of the leak. A small but non-empty IV x can help in hiding that.

Note that this is an encrypt-and-MAC setup, usually frowned upon for theoretical reasons. It is reasonably safe in this case, because HMAC/SHA-256 also protects confidentiality of the input (this is not necessarily the case of any other MAC mechanism), and CTR decryption implies no padding, and thus can be safely implemented even over unvalidated input data.

Summary: if your timestamp are really unique, then they are enough for GCM, and you can pad them to 12 bytes with zeros (that need not be transmitted along with the message). However, if clocks can be adjusted or rewinded, then you should probably use random IV instead, to get "probabilistic uniqueness"; and, in that case, don't go lower than 12 bytes. If you are desperate for size, then there are other possible avenues, but they are outside of existing published standards, which means that you need more external review and development care.


ElGamal with elliptic curves for security I only know that ElGamal belongs to CPA based on DDH or CDH hard problem.
But, if i want to proof the CPA security for ECC-ElGamal, then, what hard problem should i based?DLP?
ECC-ElGamal algorithm: ElGamal with elliptic curves
It would be better if there is a source of relevant literature!!! Thank you very much!!

But, if i want to proof the CPA security for ECC-ElGamal, then, what hard problem should i based? DLP?

It's fairly easy to show that it is equivalent to the DDH problem.
Reducing CPA security to DDH:
Given a public key $aG$, and the possible encryption of a plaintext $P$, which is $X, Y$; if it is in fact ECC-ElGamal, then $X = bG, Y = abG + P$ for some random $b$.
Then we check whether $aG, X, Y-P$ is an DDH-triplet; it's easy to see that if we were given an ECC-ElGamal ciphertext, then it is.
Reducing DDH to CPA security:
Given a potential DDH-triplet $X, Y, Z$ (which is $aG, bG, abG$ if it is a triplet), then we select an arbitrary plaintext $P$, and pass to our CPA-oracle the public key $X$, and the ciphertext $Y, Z+P$; if it says that this is an El Gamal encryption, then we say that it is a DDH-triplet.


Mixing algorithms for password hashing good or bad? So I've come across the following algorithm for hashing passwords

function hashpassword($str, $salt)
{
$hashed_password = md5($str);
$hash = md5('more_salt');
$hash = sha1($hash.$salt);
$hashed_password = crc32($hashed_password.$hash);
$hashed_password = sha1($hashed_password.$hash);
$hashed_password = md5($hashed_password.$salt);
return $hashed_password;
}

Does mixing hash-algorithms like this increase or reduce the chances of collisions? Doesn't it end up being a case of find the weakest link? The use of crc32 looks like a terrible idea to me since it isn't even meant for this, but I don't understand the maths behind so I can't tell if it is or not.

Does this look like it's done by someone who knows what they're doing or is it just a case of someone throwing all the algorithms they find together and hoping it's a good solution?

What I'm basically asking is, is this strong or weak? Is there an obvious problem with it?

Does this look like it's done by someone who knows what they're doing or is it just a case of someone throwing all the algorithms they find together and hoping it's a good solution?

This is obviously someone who threw something together without knowing what they were doing. If they knew what they were doing, they wouldn't roll their own algorithm (“Dave, you are not a cryptographer. Stop it.”), they'd use one of the standard algorithms such as PBDKF2, bcrypt or scrypt.

PBKDF2 has been in the standard library in PHP since 5.5.0, and there are plenty of open source implementations that are slightly slower but work in earlier versions. It can be debated whether PBKDF2 is the best choice, but it's a reasonable one. There is no excuse to rolling your own.

  The use of crc32 looks like a terrible idea to me

Indeed, the way crc32 is used makes it really terrible. If you replace crc32 by md5, the algorithm is merely bad, because it isn't slow. A password hashing algorithm must be slow to resist brute force guessing attempts. PBKDF2 achieves this by doing something similar to the algorithm you're looking at — repeated hashing — but 1. the hashes are assembled together sensibly and 2. it typically runs for hundreds of thousands of iterations, not a just a couple.

The way the algorithm uses CRC32 is a devastating flaw. It makes it easy to find a password by brute force. There's no guessing involved: a working password can be found in just a few minutes of computer time. This may not be the password that the user chose, but it would be a password that produces the same hash.

The critical issue is that CRC32 only has $2^{32}$ possible values, which is about 4 billion. A CPU performs that many operations in just a few seconds. If you look at the structure of the hash, it's F(CRC32(G(password)), salt). The exact structure of F and G doesn't matter, the issue is that the password only influences what goes into the CRC32 function. It only takes a few minutes to calculate G(P) for a few billion values of P. Some of them will result in CRC32 collisions, but so it'll take more than $2^{32}$ values of P to reach all $2^{32}$ possible values of CRC32(G(P)), but not a lot more. So if you calculate F(CRC32(G(P)), salt) for a little more than 4 billion values of P, one of them will be the target hash.

This doesn't necessarily give you the original password, just one that works on the system that uses this hashing algorithm. If you wanted to find the original password (because users often reuse their passwords, and other sites probably don't use such a broken hashing algorithm), you'd have to work a little harder. But not much harder. When you enumerated all the CRC32 values, you found G(password). The value CRC32(G(P)) that makes the hash pass is equal to CRC32(G(password)) where password is the original password, because the function F doesn't have any “random” collision (in fact, it has no known collision, although MD5 and SHA-1 individually do, and even for those hashes individually, collisions require crafting the two source values, not just one and then looking for a collision). Take a table of MD5 values of common passwords and filter the ones that have the target CRC32; unless the password is too rare to be in the table (and there are techniques to make huge tables), you'll find the original password.

Using multiple hash functions in case a weakness is found in one of them is not a bad idea, but it needs to be done right. PBKDF2 uses the password at each iteration. If the algorithm in this question was modified to use the password in the final SHA-1 and MD5 steps, it would drop back from being extremely bad to merely bad. And although using multiple hash functions is not a bad idea, it is by no means required; in fact, it's probably not worth the added complexity (i.e. the added risk of getting it wrong).


Does using modulo (%) affect quality of randomness? I'm writing a small script that generates random non-signed decimal integers within a certain range of values. I'm using GNU od, with the following command:

od /dev/hwrng --address-radix=n --read-bytes=4 --format=u4

/dev/hwrng is linked to a SoC thermal noise sensor (bcm2708 on Raspberry Pi), so it would return pure random bits.
Once obtained a pure random integer from od, I would use the modulo operator (eg: % in C/C++) to restrict the range of values (eg: 96-127). I have some doubts:

Does modulo affect the quality of randomness, faking in some way the distribution of values?
I'm not sure whether bits gathered from /dev/hwrng can be considered truly random, but I guess so, since its entropy is based on a physical phenomenon
Can I use 2 bytes instead of 4 bytes as int size, assuming that the needed range of generated values is low (eg: maximum value = 200)? I mean, probably 2 bytes are enough for small numbers. I ask this, because of the question (1): probably using bigger ranges in od results in higher quality of randomness when using modulo
Is using /dev/hwrng only for the seed value still true randomness? I would use the default PHP rand() as PRNG.

Let me begin by saying that if you have a hardware source of randomness, you don't need to be stingy with it.

1) Does modulo affect the quality of randomness, faking in some way the distribution of values?

Yes, it does. Or at any rate, it can --- see my answer to (3) below for more details. (I'm assuming by "quality of randomness", you specifically mean that each possible output should be equally likely, and every output should be independent of the others.)

For example, let's say that you wanted to generate a random integer between zero and three. If you did this by rolling a fair six-sided die (with sides labeled zero through five) and taking the result modulo four, what would the resulting distribution look like? Well, rolling either a 0 or a 4 would cause you to output 0, so the probability of outputting a 0 would be 2/6. On the other hand, the only way you'd output a 3 would be if you actually rolled a 3. So the probability of outputting a 3 would be 1/6. This means that you'd output a 0 twice as often as you'd output a 3.

2) I'm not sure whether bits gathered from /dev/hwrng can be considered truly random, but I guess so, since its entropy is based on a physical phenomenon.

The term "truly random" usually means by definition based on some physical source of randomness. But truly random doesn't imply uniformly random. In the example above, the output of a dice roll modulo four was truly random, but some outputs were more likely than others. Physical processes rarely produce a uniform distribution. They have biases -- for example, they might produce a normal distribution -- and often have state (leading to correlations).

It's possible to transform true randomness into uniform randomness using so-called randomness extractors (aka entropy extractors). It's possible that an extractor is already built into the bcm2708. But I'm not aware of any documentation that establishes this.

Various /dev/random implementations include (attempts at) randomness extractors internally. If you trust these algorithms, you can always read bits from /dev/hwrng into /dev/urandom, and then read from /dev/urandom.

3) Can I use 2 bytes instead of 4 bytes as int size, assuming that the needed range of generated values is low (eg: maximum value = 200)? I mean, probably 2 bytes are enough for small numbers. I ask this, because of the question (1): probably using bigger ranges in od results in higher quality of randomness when using modulo

Your intuition is correct here; if you're taking the result modulo some small number, then you can reduce bias to an acceptably small amount by using a really large range of numbers to begin with.

Concretely, if you start with a (uniform) random number in $\{0, 1, \ldots, N - 1\}$ and take the result modulo n, the result will differ from a uniform distribution by statistical distance of less than $(N \mod n)/N$. This is a useful measure because statistical distance is in turn an upperbound on how much you're increasing an attacker's probability of mounting a successful attack. So if you're protecting nuclear launch codes, you'd probably want to keep $(N \mod n)/N < 2^{-80}$. If you're protecting against SSH access to your media server, $(N \mod n)/N < 2^{-30}$ is probably a comfortable security  margin.

Note than if N is divisible by n, there's no bias whatsoever introduced during this step. In your context, N will be a power of two (either $N = 2^{16}$ if you use two bytes, or $N = 2^{32}$ if you use four). So if n is a smaller power of two, you're good.

4) Is using /dev/hwrng only for the seed value still true randomness? I would use the default PHP rand() as PRNG

From the PHP documentation:

  This function [rand()] does not generate cryptographically secure values, and should not be used for cryptographic purposes. If you need a cryptographically secure value, consider using openssl_random_pseudo_bytes() instead.

To answer your more general question, though: No. Given a 128-bit seed, it's mathematically impossible to generate more than 128 bits of "true" randomness (as measured by, e.g., min-entropy). But: Given a 128-bit seed and a cryptographically secure PRNG, this doesn't really matter. A 128 bit seed is plenty for all practical purposes. "True randomness" doesn't really gain you anything after that point.


Relation between attack and attack model for signatures What is the relationship between an attack and an attack model?
For example, let $\Pi$ be the Lamport signature scheme.  This signature has its security based on any one-way function. The Grover algorithm, an attack, inverts this function with complexity $\mathrm{O}(2^{n/3})$. Furthermore, there are algorithms that try to forge a signature, known as adversaries.  Depending on the way they act, we choose an attack model such as the chosen-message-attack model.
Is there any relationship between this model and the attack described above?

I hope I got your point and try to answer your question. Actually, if I understand you right, then what you call an attack actually means an adversary acting in a specific attack model.

To clarify this, we need to review the security models for digital signature schemes and when we have discussed this we can clarify issues. Basically, we have to discuss what an adversary tries to achieve and which environment is given to him.

Goal of an adversary:

We start by discussing the goals of an adversary beginning with the strongest and ending up with the weakest attack goal.

Total break: The adversary is able to obtain the secret signing key. Thus, he is then able to impersonate the signer by signing arbitrary messages in the name of the signer.
Selective forgery: The adversary is able to produce valid signatures for some selected messages or a particular class of messages.
(Weak) Existential forgery: The adversary is able to produce at least one valid signature for a message, for which he has not been given a signature yet (the adversary typically has no control over the choice of this forged message).
Strong existential forgery: The adversary is able to produce a valid signature different from any signature he has seen. In contrast to weak existential unforgeability, the message corresponding to the forged signature may already have been signed. Think of a second valid signature for a message that has already been signed (signatures that are publicly re-randomizable - such as Camenisch Lysyanskaya signatures - can never achieve this level).

Power of an adversary:

After defining the goals, we will take a closer look at the adversary and define his ability or power. This basically defines the environment he is acting in. Thereby, we start with the weakest and end up with the strongest one.

Key-only attack: The adversary solely knows the public-key corresponding to the secret signing key of the signer.
Known-message attack: The adversary has additionally access to a list of message-signature pairs from the signer, whereas he has no influence on the choice of the messages.
Random-message attack: The adversary can obtain signatures for message, whereas the adversary has no control how the messages are chosen (they are randomly chosen by the signer).
Chosen-message attack: The adversary has access to a list of message-signature pairs, whereas the messages were chosen by the adversary before attempting to break the signature scheme.
Adaptively chosen-message attack: The adversary is able to adaptively choose the messages which are signed by the signer during the attack. Thus, he may choose messages depending on the public-key of the signer and also previous messages or signatures, which were obtained during the attack. In other words, the adversary can use the signer as a signing black-box (oracle) throughout the entire attack.

Security as a combination of goals and power:

Now, the combination of the goal and the power of an adversary gives the type of security of a specific scheme. In general, a digital signature scheme is said to be secure if the most powerful adversary cannot even achieve the weakest goal.

Secure Signatures:

In the notation introduced above, a digital signature scheme is considered secure if it is existentially unforgeable under adaptively chosen-message attacks. Typically, here, existentially unforgeable refers to weak existential unforgeability (but there are also some signature schemes whose security is proved with respect to strong existential unforgeability).

Coming back to your question:

Actually, what you describe as an attack, is a total break under a key-only attack. Or you may see it as an adversary mounting an attack (key-only) with this goal (total break).


Why is Fernet only AES-128-CBC? I have a communication system that's currently encrypted using AES-256-CBC. Someone on Information Security StackExchange asked whether I'm using HMAC, so I'm looking into Fernet.

Fernet seems to use AES-128-CBC (link). This seems to me to be a) less secure than what I'm using and b) not sufficient to meet the requirements of some sensitive companies/entities that require AES-192 or AES-256.

Is this a problem? How should I decide whether to stick with my current approach or HMAC w/AES-128-CBC through Fernet?

This seems to me to be less secure...

Do you have a plausible adversary that can break AES-128?  AES-128 is believed (to the best of knowledge) to require $O(2^{128})$ operations (unless someone has a Quantum Computer, in which can it takes $O(2^{64})$ Quantum operations, which might not be any more practical).  For a reference, if an attacker has designed a chip with 1 million cores, and each core can test 1 billion keys per second, and he has 1 billion such chips, it'll still expected to take 4 million years before he happens to stumble across the correct key.  Do you have an adversary who can devote considerably more resources to this task than my rather extreme example?

And, if AES-128 is secure from any plausible adversary you can have, how can you say it is 'less secure'?

In addition, if you're not using some sort of MAC, that means that you are open to adversaries who can modify your data; attackers can cause all sorts of mischief (including deducing the decryption in some cases) by doing that.  That is a practical concern; IMHO, it far outweighs any concern about Space Aliens who could break AES-128.

Now, I have not reviewed Fernet; it could be that they got some details wrong (such as not selecting IVs correctly).  However, we know there are issues if you don't do integrity checking on your ciphertext.


How to generate hard subset sum instances A subset sum problem can be defined as:

Given a set of integers $S$
A target integer $x$
Find some subset of elements $s \in S$ such that $\sum_0^{n}s_i = x$

The "density" of a subset sum problem is defined as: $\text{density} = \frac{k}{\operatorname{log}(\operatorname{max}(S))}$

Where $k$ is the number of elements in the set $S$ and $\operatorname{log}(\operatorname{max}(S))$ is the size of the largest element in the set.

Subset sum problems of density $\lt 0.9408$ can be solved in polynomial time.

I would like to know:

How can we generate hard instances of the subset sum problem that are not solvable in polynomial time, or more specifically, require exponential time to solve?

Is it sufficient to use any size set and with elements such that $\text{density} = 1$? Assume that all set elements are uniformly random and of size $\operatorname{log}(\operatorname{max}(S))$
Is a higher density necessarily more difficult?

Supposing we can generate problems that require exponential time to solve, what parameter is the problem exponential in?

A set of size $8$ with $8$-bit elements has a density of $1$, and so does a set of size $256$ with $256$-bit elements, so if $\text{density} = 1$ is the requirement for hardness then it wouldn't make sense for the running time to be exponential in the density parameter.

How can we generate hard instances of the subset sum problem that are not solvable in polynomial time, or more specifically, require exponential time to solve?
Is it sufficient to use any size set and with elements such that $\text{density}=1$? Assume that all set elements are uniformly random and of size $\operatorname{log}(\operatorname{max}(S))$
Supposing we can generate problems that require exponential time to solve, what parameter is the problem exponential in?

Conditions and Parameters
The hardest instances have $\text{density} = 1$.
An instance of the problem with $\text{density} = 1$ will require time exponential in the number of elements that are summed together.
To generate hard instances of the problem, ensure that:

The number of elements in the set $k$ is equal to the the size of the largest element in the set (in bits)
All elements in the set are approximately that size (you can't have a single element of size $\operatorname{log}(k)$ and the rest of the elements small).
Each instance should sum ($k / 2)$ of the elements of the set together.

If you were to sum $k - 1$ elements of the set together, then you could solve an easier problem (namely: subtract elements from the sum of the entire set until you find which one(s) isn't a member of the target subset)

Cost
Basically, you need $k$ uniformly random elements of size $\operatorname{log}(k)$ for a hard instance of the problem. This implies that a hard instance of the problem will require $O(k^2)$ space.
There is a quantum attack against the subset sum problem that runs in time $O((0.241... + O(1)) * n)$, which we will round to $O(.25 * n)$ to make the following math more convenient:
Assuming the complexity of the quantum attack cited above using the conditions laid out above, the computational cost to solve a subset sum problem of size $k$ is $O(2^{k / 8})$.

To generate instances of the problem that require approximately $O(2^{128})$ computational cost against a quantum adversary, set $k = 1024$.

This will use $1024^2 = 1048576$ bits of space.

Is a higher density necessarily more difficult?

No, instances of the problem with $\text{density} > 1$ are more easily solved.


Is XChaCha20-Poly1305 nonce misuse-resistant? In the Libsodium v1.0.12 and v1.0.13 Security Assessment one can read

  The ChaCha20-Poly1305 implementation combines a stream cipher and is
  resistant to timing attacks by design. In addition, this particular
  construction has two additional variants implemented in libsodium: an
  IETF version [7] and one with an extended nonce (XChaCha20-Poly1305)
  [4]. One benefit of the XChaCha20Poly1305 construction is that it
  enables nonce misuse-resistant schemes.

However, I don't understand how XChaCha20-Poly1305 construction is nonce misuse-resistant.

From my understanding, XChaCha20 works as follows:

Generates a 192-bit random nonce (6 32-bit words $nonce_0,...,nonce_5$)
Build the initial block $B \leftarrow
\begin{matrix}
c_0 & c_1 & c_2 & c_3\\
k_0 & k_1 & k_2 &k_3\\
k_4 & k_5 & k_6 &k_7\\
nonce_0 & nonce_1 & nonce_2 & nonce_3
\end{matrix}$ where $c_i$ are constants and $k_i$ are key words
Runs ChaCha without the final block addition $B' \leftarrow \mathtt{HChaCha20}(B)$
Build the subblock $B'' \leftarrow
\begin{matrix}
c_0 & c_1 & c_2 & c_3\\
B'_0 & B'_1 & B'_2 &B'_3\\
B'_{12} & B'_{13} & B'_{14} &B'_{15}\\
counter_0 & counter_1 & nonce_4 & nonce_5
\end{matrix}$
Runs ChaCha20 using $B''$.

In this way, using the same nonce will output the same keystream.
However, as I understand, nonce-misuse resistance schemes ensure that a repeated random nonce doesn't result in plaintext compromise.

So it seems that when using XChaCha20-Poly1305 with random nonce, one can ensure that the probablity of a repeated nonce is negligible. But this is not the definition of a nonce miseuse-resistant scheme.

How to build a nonce misuse-resistant schemes using XChaCha20Poly1305?

The documentation on libsodium AEAD constructions provides more details.

Namely, it lists Hk(random ‖ m) as a way to compute a synthetic XChaCha20 nonce. Even if random is not unique, the nonce is unlikely to be the same for different messages.

Even more relevant are the sections on nonce-misuse resistance and short nonces.

Note that like all other nonce-misuse resistance schemes, this requires two passes over the data.


Show that G is not a PRF $\DeclareMathOperator{concat}{\|}$
I'm trying to do the following assignment:

Let $F : \{0,1\}^k \times \{0,1\}^n \to \{0,1\}^n$ be a PRF. Define function family $G : \{0,1\}^k \times \{0,1\}^{n-1} \to \{0,1\}^{2n}$, for all $x \in \{0,1\}^{n-1}$, by $$G_K(x) = F_K(0 \concat x) \concat F_K(x \concat 1).$$ Show that $G$ is not a PRF.
[Remark: To do this, design an efficient PRF adversary $B$ that achieves an advantage close to 1. Remember the $B$ is an algorithm. As such it needs to specify precisely: What oracle queries does it make? What does it do with the answers it receives? How does it decide what guess to make?]

I provided an image of what I have attempted.
The symbol $\concat$ means concatenation. Can anyone can please provide some insight on how to solve this problem.

If the adversary takes $x, y \in \{0, 1\}^n$ such that $(0 \parallel x) = (y \parallel 1)$ then

$$G_K(x) = F_K(0 \parallel x) \parallel F_K(x \parallel 1)$$
$$G_K(y) = F_K(0 \parallel y) \parallel F_K(y \parallel 1) = F_K(0 \parallel y) \parallel F_K(0 \parallel x)$$

The left half of $G_K(x)$ is equal to the right half of $G_K(y)$, which lets the adversary distinguish $G$ from a random function.


How much extra information is in an RSA public key? I'm trying to calculate the size of an RSA public key in Ruby. I've retrieved the key in PEM format, and once I've decoded the base64 part from the PEM format, I get the size in bytes. What I find is that what I retrieve and the actual key size is off by 12 bytes, or 96 bits for that matter – for a 1024 bit key, I get 140 bytes (=1120 bits).

I know there is at least always an exponent and the modulus in the public key. My question is:

Is it always a fixed difference (12 bytes), or can the difference vary and if yes - how do I know how big the difference is?

Firstly the length of an RSA key is the length of the modulus and an RSA public key consists of an exponent and a modulus, so there is a couple of bytes there.

Secondly depending on how you created and/or transmit the key it may be wrapped in a SubjectPublicKeyInfo block. It's defined as (RFC 3280):

 SubjectPublicKeyInfo ::= SEQUENCE {
   algorithm AlgorithmIdentifier,
   subjectPublicKey BIT STRING }

 AlgorithmIdentifier ::= SEQUENCE {
   algorithm OBJECT IDENTIFIER,
   parameters ANY DEFINED BY algorithm OPTIONAL }

and is basically a way of telling a receiver what algorithm the public key uses and any additional info that may be of use (probably nothing for RSA keys). So there is possibly a few extra bytes there.

If you're interested in this stuff you can look into ASN1 definitions which describe the structure in which keys and certificates (and many other things) should be passed around. If you want a quick look you can use:

openssl asn1parse -in key.prv -inform pem

to see what is in the file but in short, depending on the encoding I wouldn't make assumptions on the data size.


What are sources for the performance difference in asymmetric and symmetric encryption? I see the claim (which I'm not doubting) that encrypting data using asymmetric algorithms is slower than symmetric algorithms.

But I never see citation on these claims, not here, on wikipedia or even in papers.

It seems in academic papers RSA and the like are for signatures and are never considered when comparing encryption algorithms.

Is there a more comprehensive review I'm missing?

There are three different possible things you are asking for:

Concrete stats and numbers from a benchmark
Analysis of the algorithms in terms of bit operations required
Proof that asymmetric encryption must be more expensive than symmetric encryption

Benchmarks

If you're just looking for actual stats and numbers, there are the SUPERCOP/eBATS benchmarks.

You can also investigate the command openssl speed.

Bit operations

If you're looking for a theoretical analysis of the number bit operations used by asymmetric encryption compared to the number of bit operations used by symmetric encryption, that may be harder to come by in the form of a single paper. You'd need to do an analysis of the number of bit operations of all the relevant $\operatorname{encrypt}$ function (which may be different than the $\operatorname{decrypt}$ function).

For symmetric algorithms, the introductory paper(s) will typically provide a measure in cycles per byte. But cycles per byte are a feature of architecture and implementation, not intrinsic to the abstract algorithm, and so are not useful here.

You would need to know which algorithm is being used to implement the required function. For example, with modular exponentiation the naive algorithms of multiplying $g$ times itself $x$ times will have a drastically different number of bit operations compared to using the square and multiply algorithm.

And on that note, you would also need to know the most optimal algorithm for implementing each functionality to conclusively say that algorithm $A$ requires more bit operations than algorithm $B$. That could prove to be a challenge at the very least, and maybe even prohibitive in the worst case.

Proof it must be this way

If you're looking for a proof that says asymmetric encryption must be slower than symmetric encryption, then I doubt such a result exists.

There is a paper that shows that (secure) key exchange in the random oracle model is impossible.

One supporting argument might Diffie-Hellman and the discrete logarithm problem. There are generic attacks against the discrete logarithm problem which place a minimum on the size of the used group, which consequently raise the cost of using the algorithm.

However, DH is not public-key encryption, it is key agreement, and it is only a single algorithm, so it certainly does not qualify as proof that all asymmetric encryption must be slower than symmetric encryption.

On a related note, in general, asymmetric algorithms (discounting hash-based signatures) have structure, whereas symmetric algorithms (typically) do not. This structure appears to contribute to an increase in the amount of space required to use such algorithms, which again contributes to an increase in the amount of time required to use such algorithms. However, this is again not proof that it must be this way.


current state of 3-SAT problem? In this paper, a quantum algorithm to solve the 3-SAT problem in linear time is presented. Is it true? Did the author make a mistake? What state-of-the-art algorithms exist for this problem?

I do not know if the result is true, since I did not check it, but note that this algorithm is not in the standard model of quantum computation. As the author himself put it:

  The Deutsch model of quantum computation is extended to allow for thermodynamically irreversible operations by allowing the system of interest to interact with an outside reservoir. A set of irreversible logical error correction superoperators are constructed which allow the rapid concentration of probability from an exponentially large search space into a small number of logically defined states. These capabilities are used to construct a linear time solution algorithm for the NP complete problem 3SAT.

Therefore, this result, if true, simply says that in an appropriate extended model of quantum computation, there exists an algorithm that solves 3SAT in linear time. This does not prove BQP = NP (which would be a major breakthrough), nor is it clear whether this model has any concrete value - put otherwise, it is not an algorithm that a quantum computer, if it is ever build and runs as quantum computation experts expect it should run, could ever run.

A few additional notes: algorithms that solve NP-complete problems in extended models of computation are well-known, people have long investigated closed timelike curves, post-selection in quantum computation, and other appropriate modifications of the standard model of quantum computation. More often than not, these modifications make the model much more powerful, able to evaluate much more complex functions (indeed, studying how specific variations of the model deeply change its computational power is one of the ways some researchers use, e.g. Scott Aaronson to name only one, to understand the exact boundaries of BQP). Note also that the paper you link was added to ArXiv in 2015 and, as far as I can see, was never published anywhere - so it does not seem unlikely that it either contains a mistake, or the alternative model investigated there was not judged realistic, useful or interesting by the reviewers.


AES encryption with multiple keys I would like to encrypt some data using a combination of multiple keys. There would be two keys: a client keys that would be generated for each client and a single server/application key used by everyone. The idea is to be able to encrypt/decrypt the data only if we are in possession of both keys. So neither the server nor the client could decrypt the data alone.

I know that I could simply encrypt the data using the client key and then encrypt the data using the server keys, but I was wondering if it was possible to just combine the keys in order to create the common decryption key as I am not fond of multiple encryption... I have looked into Secret Sharing, but from what I experimented with the crypto++ library, I can only generate n keys from a message (the message would be the merged key in my case). I would rather want to generate a client key, then merge this client key with a fixed server key to generate the final key used for encryption.

Is XORing the keys together a good solution ? (I believe if both of them have the same character at the same location, it would reduce the encryption strength of the final key...)

Also, can I only use a single IV for both keys in this context ? The IV would of course be randomly generated for every client.

You asked several questions above.  I will address one in specific that stands out to me, and that is your question about XORing the keys together.  Your statement that they might both have the same character at the same location that would yield a null byte is disconcerting: passwords are not normally used directly as encryption keys.

Mathematically, a string of eight zero bits is not going to reduce the strength of AES, as AES does not have any known weak keys.  However, if an attacker knows you will be using ASCII characters directly as key material, his job of attacking just got that much easier, because he understands the limits imposed by such a restriction.

If you use ASCII characters as your key, you would need to tell your clients they must use exactly a 16 character password, which will limit their creativity (greatly reducing the pool of likely passwords they might choose.)  ASCII severely constrains the number of bits that can change in a given byte: there are few people who could enter a character on a keyboard that is outside the range of the common letters, numbers, and symbols.  By limiting key bytes to exclude values in the ranges of 0x00-0x1F and 0x80-0xFF, you've artificially limited your keys to $96^{16}$ instead of $256^{16}$.  This dangerously weakens your implementation.

Consider using a key derivation function to transform the passwords into the cryptographic key.  Such an algorithm combines all the bits of input and produces a key of the desired length.  By using a key derivation function you could require a 64 character minimum password, and combine all that material to produce a much stronger key - $96^{64}$ is significantly stronger than $96^{16}$.


Any Supersingular Isogeny-based Diffie-Hellman (SIDH) key exchange recommended Curve Domain Parameters? For existing ECDH, I understand that there are recommended Elliptic Curve Domain Parameters. May I know if there are such similar considerations in SIDH? Any recommended Curve Domain Parameters?

All 'good' implementations so far have used the same curve, but there is now variation in the underlying finite field, which affects the other base parameters of the public points for each party and the range of values for the secret scalars. The best reference as yyyyyyy mentioned is the NIST PQC submission for SIKE, which includes valid options for SIDH with some extra protocol stuff on top. The parameter sets in there are p503, p751 (the most studied one) and p964.


Forward-secure static-ephemeral ECDH key agreement protocol The question is whether the following simple key agreement protocol design has good security properties, and how it can or should be improved.

Assumptions

Alice is a persistent entity with a static and well-known public key.
Bob is a transient anonymous party who would like to exchange some private information with Alice over the public Internet in a session of short duration (less than an hour), in a way that is forward-secure (has the forward secrecy or PFS property).
Bob has a good copy of Alice's static public key.
Bob must authenticate Alice, but Alice need not authenticate Bob.
All key and ECDH operations use Curve25519 or another SafeCurve.
The final shared secret that is the outcome of the protocol will be used to secure the data transfer between Alice and Bob (which takes place with a separate protocol) by serving as the key to an Encrypt-then-MAC authenticated encryption (AE) procedure (for example, XSalsa20/Poly1305) that also requires a unique-per-(key, message) nonce as input.
The transport protocol is message-based (not TCP), and protocols such as TLS and DTLS are not applicable.

It is well known that using mature and battle-tested key exchange protocols is usually the right answer, so pointing this out is unnecessary.  Useful answers will provide specifics as to any problems with this protocol and, especially, how they can be corrected.

Protocol

Bob generates an ephemeral (private, public) keypair (b, B).
Bob computes the DH shared secret X using his private key and Alice's static public key A, and then K(X), the result of applying an appropriate key derivation function (KDF) to the combination of A, B, and X.
Bob initiates communication with Alice by sending her a (cleartext) message that contains some fixed protocol information such as a magic number and version, and a copy of Bob's public key B.
Alice receives the message and computes the DH shared secret X using her static private key a and the public key B that Bob sent.  She then computes K(X) as Bob did.
Alice generates an ephemeral (private, public) keypair (e, E).
Alice generates a unique nonce N0 and the ciphertext C that results from applying AE with nonce N0 and key K(X) to her ephemeral public key E.  She then sends N0 and C to Bob.
Bob receives the message and authenticates/decrypts it with AE using the nonce N0 sent in the message and key K(X).
Both Alice and Bob compute the DH shared secret Y using their ephemeral keys (e, E) and (b, B), and then K(Y), the result of applying the KDF to the combination of E, K(X), and Y.  The values X, K(X), and Y are discarded.
At this point the protocol is complete, and data transfer is carried out separately using AE with key K(Y) and a unique nonce sent in the clear with each message.  When the session is finished, the ephemeral keys (b, B), (e, E), and K(Y) are discarded.

The protocol seems secure. Some comments below.

  Bob computes the DH shared secret X using his private key and Alice's static public key, and then K(X), the result of applying an appropriate key derivation function (KDF) to the combination of A, B, and X.

The DH secret X already depends on both key-pairs. Including the public keys in key derivation does not seem to add security.

(Also, in practice Bob should calculate X after sending the ephemeral key to Alice, while waiting for reply, so it is not part of the critical path.)

  Both Alice and Bob compute the DH shared secret Y using their ephemeral keys (e, E) and (b, B), and K(Y), the result of applying the KDF to the combination of E, K(X), and Y.  The values X, K(X), and Y are discarded.

Again, the inclusion of anything but Y in key derivation seems unnecessary.

  [...] When the session is finished, the ephemeral keys (b, B), (e, E), and K(Y) are discarded.

The ephemeral key-pairs (b, B) and (e, E) can be discarded already  in step 8 after Y is calculated. Unless you use them for something else, in which case you need to look at how that might interact with the protocol.


Why is SRP not widely used? SRP seems to be a very good password authentication protocol, compared to any other things used now. So why is there no popular implementations, or even no working secure implementations?

I tried to set up TLS-SRP protocol, but it haven't worked for me.

Haaalp! Someone?

When I learned about SRP we were told it wasn't seeing much deployment due to possibly infringing on EKE patents. Network Computing had this to say in 2002:

  Standards groups have made several attempts to induce Lucent to talk about its EKE patent -- to no avail. Even with Lucent's silence on the topic, few vendors have been willing to use SRP. To further cloud the situation, there's been a new patent issued claiming that it too covers SRP.

The SRP website, however claims

  Since SRP is specifically designed to work around existing patents in the area, it gives everybody access to strong, unencumbered password authentication technology that can be put to a wide variety of uses.

If I had to guess, I'd say patents were part of the original problem and that effect has continued even today. Whether patents are the sole reason for limited deployment or even the major reason is beyond me.


ECDH, x25519 and limitations for securing client-certificates on the server g'day Crypto.SE

I'm working on a practical application of sharing a static key to better-identify a user, between the recipient (server) and the initiator (client ie. user's machine).

My core question is:

For x25519, can multiple PK's resolve to a single SK, or is there ever only one unique PK-SK pair?

I'm wondering whether it's rational to think of x25519 public-keys as holding an "almost" equal share in securing information? By "almost" equal, I mean that I can always derive the PK from the SK.

If I didn't have the PK or the SK, would I be able to produce a message that matched an SK at better probability than a brute-force guess across (half?) the x25519 key-space?

My original q, slightly re-worded and still bl**dy confusing, sorry!

Without either the PK or SK for an x25519 key-pair, is there a greater probability that I can encrypt a message for an unknown SK, than I would otherwise have being able to determine the SK from the PK (if I had the PK).

Specifics for my application handshake is here:

Handshake protocol that uses x25519 and Argon2 to secure user secret-keys on the server

For x25519, can multiple PK's resolve to a single SK, or is there ever only one unique PK-SK pair?

If I wasn't mistaken, there can be atmost 2 PK corresponding to 1 SK in x25519, depending on whether the implicit y-coordinate is internally positive or negative. As for ECDH on the other hand, the mapping is 1:1.

  I'm wondering whether it's rational to think of x25519 public-keys as holding an "almost" equal share in securing information? By "almost" equal, I mean that I can always derive the PK from the SK.

From the way you explain your question, I assume you mean whether the PK and SK are equally essential: yes, the only thing to be noted is that their role is different.

(In the previous form of the question, answerers may confuse your question as asking whether the PK of both parties are equally important).

  If I didn't have the PK or the SK, would I be able to produce a message that matched an SK at better probability than a brute-force guess across (half?) the x25519 key-space?

Do you mean forging a ciphertext that can be decrypted with an SK without knowing its corresponding PK? This type of attack is known as existential forgery - a term usually applied to digital signatures and message authentication codes.

In existential forgery, the attacker produces a message that can be correctly verified (in your case, successfully decrypted) with a key that's possibly unknown. See What do the signature security abbreviations like EUF-CMA mean? and Easy explanation of "IND-" security notions? for further explanation.

  .. is there a greater probability that I can encrypt a message for an unknown SK, than I would otherwise have being able to determine the SK from the PK (if I had the PK).

For elliptic curve key exchange and encryptions, this isn't likely, as the key-recovery complexity and forgery complexity are essentially equal.


Practical lattice based signatures and key exchange with strong security reduction I am looking for practical lattice-based signatures and key exchange with strong security reductions.

Specifically:

Provable security under the relevant standard assumptions.
Fast in software while resistant to timing attacks
At least 128 bits of security

Your best bet at the moment are probably the lattice-based key exchange described in the "Post-quantum key exchange – a new hope" paper. You can also find different implementations. C code can be found on Peter Schwabe's homepage.

For signatures, if you want to use lattices, you will end-up with BLISS or BLISS-B both of which are implemented by various people.

However, a word of warning. While there exist parameter proposals and especially the "new hope" paper is even very conservative regarding the parameter choice, both schemes use ideal lattices. The parameter estimates assume that there exists no significantly better attack for ideal lattices than for random lattices. While this is true at the moment, it is unclear if this will be the case in the long run. As always, there are several researchers that believe it will stay that way and several that believe faster algorithms will be found.

A second issue is that implementation security of these schemes was not really studied so far and is hence not understood.

Anyway, combining these with ECC for example will definitely improve your security.


What is transaction capacity of a POS using 3DES DUKPT? I am looking for the transaction capacity of a Point-Of-Sale device using 3DES DUKPT. Once all keys derived from the future key set are exhausted (1M or 500K?), how will the POS be reloaded with a new set of future keys.  Have not seen many topics on this online.

Is changing the KSI number a widely used industry practice?

How many transactions? It depends on precisely how the 80 bit KSN has been divided between key set ID, and device ID.  There is freedom on this - the spec does not say how it should be done. In practice usually only 64 bits is used, and it is divided 6-5-5, giving 16 million key sets, 500k devices per key set, and 1 million transactions per device.  But you could easily increase that if you needed less key sets/devices.

No, changing the device's serial number is not standard practice. It is intended to remain the same for the life time of the device. It would need to be replaced (via an RMA procedure), or re-injected.


Shannon information entropy value of 64 bit data? So basically i have a set of float data, its value ranges from -1.3117 to 1.7956 and then i convert this data into 64 bit binary value(assuming it is originally 64 bit double float). After that, i convert it into 64 bit integer. I encrypt this data with an encryption algorithm. The cipher histogram shows the distribution of the data are uniform like these.

After that i calculate the cipher data's shannon information entropy value and i got around 15.0525 and 15.497477 for the plain data's shannon information entropy value.
What i want to ask is, from what i know that cipher data consist of 8 bit integer data ideal shannon information entropy value is close to 8 bit, so i thought that this 64 bit integer data ideal shannon information entropy value is must be close to 64 bit right?why did i get shannon information entropy value around 15 bit on both cipher and plain data despite the uniformy distributed histogram of the cipher data? i get that the plain data shannon information entropy value usually not close to the ideal value but i dont get why the cipher data shannon information entropy value is close to 15 bit not close to 64 bit.

I guess that the question's data processing

Uses "64 bit binary value" as symbol of the plaintext.
Enciphers these  with a 64-bit block cipher in ECB mode, and considers the symbols in the encrypted data flow to be the individual outputs of that block cipher.
Assimilates the observed/actual frequency of a symbol $i$ in an experimental data set to the probability $p_i$ it has for the source of that data set. Which of course is an approximation (argument: if we repeat the experiment we'll likely get different frequencies, even if the source is unchanged, thus the probabilities unchanged).
Applies the formula $\displaystyle H\ =\ \sum_{i\text{ with }p_i\ne0}p_i\,\log_2\left(\frac1p_i\right)$ for the per-symbol Shannon entropy of a source of independent symbols of known probabilities $p_i$, even though nothing in the question supports that hypothesis of independence of the symbols produced by the source.

Assuming the above, reversibility of the transformation made on the symbols implies that encryption leaves $H$ exactly unchanged. The $p_i$ summed are the same, only for different $i$. The discrepancy between the reported 15.497477 before encryption and 15.0525 after could come from basing the computation of the second value on output that is not the encryption of the input used for the computation of the first value.
And independently, what's computed is something about the data (I don't know a proper name) produced by a source, but we have no assurance that it's a fair approximation of the Shannon entropy per symbol of the source. Knowing the data set length and the actual number of possible symbols (which depends heavily on how the input symbols are gathered, and what their physical source is) would help build an informed opinion on that.


Why do some block cipher modes of operation only use encryption while others use both encryption and decryption? In Chapter 6, Question 6.8, of his book “Cryptography and Network Security Principles and Practices”, William Stalling asks:

  Why do some block cipher modes of operation only use encryption while others use both encryption and decryption?

ECB and CBC use encryption function and decryption function while CFB, OFB and CTR use encryption function for decryption as well. What is the logic behind it? Is it because ECB and CBC generates output of Block Cipher type – while CFB, OFB and CTR generates output of Stream Cipher type?

That is the general idea of it yes.

Some modes of operation (eg CTR) work in such a way that only known values are ever encrypted, forming a stream of pseudo-random data that is then combined with the plaintext by a keyless reversible operation (often xor) to form the ciphertext.

Other modes (eg CBC) directly encrypt secret (ie plaintext) values, meaning decryption is required to find out what the secret value was.

One of the biggest advantages of a scheme that does not require decryption is that it can be implemented in hardware with reduced footprint (ie it's smaller).  Moreover, for block ciphers such as AES it can often be easier to implement efficient encryption than decryption because the internal coefficients have been optimized for this direction.


Differences between AEAD and ECIES when transmitting secret messages I wonder what are the practical differences between using Authenticated Encryption and then ECIES. It looks like both require communicating the shared secret in some fashion between the parties and both provide encryption and authentication.

To make a concrete example, consider we have a party A, which receives messages {x1, x2, ..., xn} from various other parties, but needs to read the sender from the message itself, because upon receiving a message x, A doesn't know the sender otherwise. Using some AEAD scheme, A could have in an authenticated part the sender in plain text, consequently allowing A to choose the shared secret which to use to authenticate and decrypt the the message it received.

Can ECIES do this and if so, what is the practical difference? If not, well, what could be the purpose of ECIES? There seem to dearth of information on ECIES.

I wonder what are the practical differences between using Authenticated Encryption and then ECIES. It looks like both require communicating the shared secret in some fashion between the parties and both provide encryption and authentication.

ECIES is a specific hybrid encryption scheme using elliptic curve cryptography to enable EC based encryption - that is: encryption using the static public key of the receiver and decryption using the static private key of the receiver.

AEAD is a description of an interface for symmetric encryption with authentication.

ECIES depends on a asymmetric key pair (where the public key is trusted) and AEAD depends on a single symmetric key, which needs to remain secret. ECIES is a specific construct to perform encryption using Elliptic curves, AEAD is a description of an interface for authenticated ciphers. In such, it doesn't make much sense to compare the two.

  To make a concrete example, consider we have a party A, which receives messages {x1, x2, ..., xn} from various other parties, but needs to read the sender from the message itself, because upon receiving a message x A doesn't know the sender. Using some AEAD scheme, A could have a plain-text part in each x telling the sender in an authenticated part and hence would need which shared secret to choose to open the actual message.

You wouldn't really need to authenticate the key identifier; if you'd change the key identifier then the authentication tag is already invalid, as you would use the wrong key to authenticate the ciphertext. You'd only need it if the scheme reuses the key for multiple senders that trust each other (not a common scenario). If this is for transport authentication you'd generally just keep track of a session.

  Can ECIES do this and if so, what is the practical difference? If not, well, what could be the purpose of ECIES? There seem to dearth of information on ECIES.

No, ECIES just performs encryption, and as anybody has the public key, anybody can create a valid ciphertext. It doesn't If you want to add such functionality, you should sign the data, and then encrypt the plaintext and signature.

If you're talking about real time communication between a sender and receiver then you'd just use a transport protocol such as TLS. TLS 1.3 requires AEAD but since there already is a key establishment scheme based on DH, ECIES isn't used.


Understanding the HAIFA (hash iterative framework) structure Unfortunately, this structure doesn't even have a full Wikipedia on it. I'm struggling to understand it. There are no Youtube videos, Lectures, or any educational video on it. I want to understand how the structure works, and I don't care about the maths behind the hash iterative framework. I would also like if someone can provide me with an outline to the structure or any useful links to better understand it.

HAsh Iterative FrAmework (HAIFA) proposed by Biham and Dunkelman, in 2005-2007. The main idea of the work is to fix the flaws of  Merkle and Damgård (MD) construction. Interestingly, Invented by Ralph Merkle and Ivan Damgård working independently and presented in the main Cryptography Conference.

R. Merkle. A certified digital signature, CRYPTO '89.
I. Damgård. A design principle for hash functions, CRYPTO '89.

Flaws in MD constructions are found even the underlying compression function is secure. In MD, the iteration maintains the collision resistance of the compression function proved by both Merkle and Damgård. Over time, it is shown that it not enough;
MD construction problems

fix-point of the compression function can be used in the second-pre-image attack by Dean.
Kelsey, and Schneier same as above with the fixed point assumption is removed in Second Preimages on $n$-bit Hash Functions for Much Less than $2^n$ Work
Chosen target pre-image attack by Kelsey, or known as Herding attack' Herding Hash Functions and the Nostradamus Attack
The well-known length extension attack.
Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions by Joux. Joux showed that finding multiple messages that have the same hash value is almost the same as finding a single collision on iterated hash functions.

HAIFA is designed with these goals

simplicity: this is important since the simple design a better understanding to analyze.
maintaining the collision resistance of the compressions function
increasing the security of iterative hash
functions against (second) pre-image attacks, and
the prevention of easy-to-use fix-points of the compression function. HAIFA also supports variable hash size.

Previous MD modifications
There are patches for MD before HAIFA, and actually HAFAI can use all.

Randomized hashing scheme: They reduced the collision-resistant requirement of the compression function. They randomized the inputs of the compression function so that, the collision of the compression function can be masked.

Enveloped MD construction: This method preserves the collision resistance, the pseudorandom and the pseudorandom family properties of the compression function. This construction can be very useful like the case of a hash function is designed for MACs, since the pseudorandom properties of the compression function is preserved.

Wide pipe: This method uses a larger internal state than the output size. This construction results in finding internal collisions as hard as finding the pre-image of the hash function itself.

HAIFA design
The compression function of HAIFA is designed as
$$C:\{0,1\}^{m_c} \times \{0,1\}^n \times \{0,1\}^b \times \{0,1\}^s  \to \{0,1\}^{m_c}$$ or
$$h_i = C(h_{i-1}, M_i, \#bits, salt)$$ $\#bits$ is the number of bits hashed, $h_0 = IV$, and $salt$ is the usual salt value.

The padding scheme
It is bit padding, add 1 then and as many as 0 then the length encoded in $t$ bits, then the digest size encoded in $r$ bits. Therefore the added 0 is $ \equiv n - (t+r-1) \mod n$
Security

Collision resistance: Similarly to MD, the have proved that if the underlying compression function is collision resistance the HAIFA construction, too.

Fixed point countermeasure: the inclusion of the number of bits hashed so far prevents the fix-ed point attacks.

Randomized hashing is achieved by the salt.

Multi-collision attack: The attack still works, however, the inclusion of the salt prevents pre-computation

Hearding attack: The precomputation is infeasible if the salt is unknown.

Hash Algorithm Based on HAIFA

BLAKE, BLAKE2 uses a simple desing to elimiate the Length extension attack.
SHAvite-3
ECHO
LAKE
Sarmal
SWIFFTX
HNF-256

The first three are in the second round of the SHA-3 competition of NIST.


Dividing a secret into multiple nodes in a blockchain kind of system with time-release? I would like to have these features and want to ask if it is theoretically possible:

a) There is custom software running on nodes in a blockchain style
b) A secret is kept in the blockchain that needs to be released at some point in time (let's say this can be the height of the blockchain).
c) No node and no one can see the whole secret before time since he would need access to all the nodes.
d) The time-lock can be extended by consensus of the network

Questions:

What happens when a node goes offline? The secret is not complete
then.
How is the initial split is happening so the whole secret is not
visible at any point in time? A client maybe that knows all the
nodes and sends them a piece?

I understand what you are thinking, but you are mixing concepts. Just try to put the public parts of your schema at the blockchain... For instance, if you want to implement a PKI scheme without central authority (CA), you could by placing the public certificate at the blockchain. That way by being at the blockchain it is "compliant" with the decentralized CA...


Passwords with same SALT. What does this mean? If the same SALT is used for many passwords on a Linux server, in what way is that a security risk?

Does the mean, that a user (which can change his own password) can calculate other users passwords?

Or is brute forcing a rainbow table still required?

A constant salt (or not using any salt) allows to do the same brute-force or dictionary attack on many passwords at once, instead of only at one at the same time. So you'll get an earlier "first match", and more matches at all for the same amount of work.

If the attacker wants a specific user's password, it is not faster at all (other than allowing precomputation of a hash→password table). Though if this attacked user has the same password with another user, this shows up, and a social (i.e. non-cryptographic) attack on this other user might be doable.


Time taken for Brute Force Attack on DES An attacker is equipped with a computer that performs 10 trillion (1013) DES decryptions per second, what is the average time required, in hours, for a brute force attacker to break DES? Key size is 56 bits.

I tried 256/1013 divided by 3600 but the answer is incorrect.

You got $2^{56}$ different keys and the attacker can test $10^{13}$ keys per second.

In the worst case, the last tested key is the solution. For that you need $2^{56} / 10^{13} \approx 7205$ sec. -> around $2$ hours.

In the best case, the first tested key is the solution. This takes about 1 second.

On Average you need to test half of the keys. That means: $0.5 * (2^{56} / 10^{13}) \approx 1$ hour.


secure integer comparison I have been going through a huge amount of papers to find a simple and a practical method to compare integer numbers without revealing their original values. I know that this falls within the area of secure multi party communication framework. However, I have very limited knowledge in cryptography and I can not really understand much of what the papers explains.

I have already tested the viff (viff.dk/) framework but the computation cost is quite high to compare just 5 numbers (about 500 milliseconds). I am looking for a solution with minimum security guarantees but low computation overhead. I would be grateful if someone point out a simple solution to start with or even an implementation which I can use. I know that my question may seem quite general, but I am kind of lost here and any pointers would help.

-------UPDATE--------

We would like to compare offers of different ISPs (internet service providers) in order to provide the best service to a customer (bidding). The ISPs don't want their offers to be revealed to the other ISPs but they want to know which one of them wins (the one with the best offer). They don't want to use a third party to do the comparison, they want to do it in a multi party fashion. The information provided by the ISPs currently is just a single integer of 8-bits length. The goal is to find the biggest integer. I don't know if this include multiple operations or just a single one !! ... And I guess it needs inequalities ... since this comparison needs to be done as fast as possible within 10th of milliseconds and we assume that the ISPs would be  mostly honest, we are looking for as simple and as practical as possible protocol to do it. Our concern is is speed more than the security.

I would suggest looking into sharemind. Their setup is a little different from VIFF, there are 3 computation servers and everyone shares their inputs with the computation servers. As long as the computation servers don't collude, privacy is guaranteed. They have also optimized many things. So it may work better for you.

That said, there are some optimizations you could do to VIFF to make things faster. I believe VIFF does comparison by splitting the shared secrets into shares of bits of the secrets. In otherwords, if you were sharing 8-bit integers, then instead you would have 8 sharings of the individual bits of each input. Splitting the shares is a costly operation, but once you have shares of the bits, comparison isn't too bad. So, you could just have the parties share the bits in the first place.


Why this complexity defining AES-GCM counter block? AES-GCM counter block is defined as nonce || IV || counter. Why this complexity? Knowing that it does not need to be secret and its only required property is to be unique, why not use a 128 bits true random number for the whole block? The counter instead of starting at 0 will start at some random value, wrapping around when reaching maximum value.

AES-GCM counter block is defined as nonce || IV || counter

That is not true.  AES-GCM effectively has two different versions.  If you have a 96 bit nonce, then the counter block is (by your terminology) $$nonce || counter$$

However, if the nonce is any other size, it computes a temp value $J = GHASH(K, Nonce)$, and then makes the counter block

$$J \boxplus counter$$

(where $\boxplus$ is addition which ignores the carry from bit 31 to bit 32).

As $J$ is effectively a random number, this second possibility is mostly what you are suggesting.

Now, it has since been found to have inferior security properties compared to the first idea (the proof had a flaw), so I don't suggest you actually use it