Zero knowledge proof of the sum of two values Given $v \in Z$, a prover knows $v$ and the verifier knows an encryption of $v$.

The prover provides the verifier with the encryptions of two values $m$ and $n$

How can the verifier verify that $m+n=v$ ?

I cannot find any scheme/algorithm in the literature I have searched, other than range proofs, and I am looking for pointers.

To illustrate, here is a naive (and wrong) approach to the problem.

Assuming a generator $g$ in a group of order $p$, co-primes.

The verifier knows $g^v$, the prover can provide $g^m$ and $g^n$. The verifier then verifies that $g^mg^n=g^{m+n}=g^v \pmod p$.

However if the prover provides $m'$ and $n'$ such that $m'+n'=m+n+k(p-1), k \in Z^*$ then the equation above verifies although $m'+n'> v$

(according to Fermat little's theorem $g^{k(p-1)}=(g^{p-1})^k \equiv 1 \pmod p$)

For this, it suffices to use additively homomorphic encryption. There are two possibilities for this: Paillier and ElGamal in the exponent.

For Paillier, given an encryption of $v$, $m$ and $n$, one can compute an encryption of zero by $v - m - n$. In the Damgard-Jurik paper, there is a very efficient zero-knowledge proof for proving that a ciphertext is an encryption of 0. So, this solves your problem.

For ElGamal, typical encryption is $(g^r,h^r\cdot m)$ where $h$ is the public-key. This is not additively homomorphic. However, you can change this to $(g^r,h^r\cdot g^m)$ and now you can add and subtract ciphertexts. With the same method as above, one can compute $v-m-n$ inside the ciphertext and then get an encryption of 0 which is just $(g^r,h^r)$. This implies that $(g,h,g^r,h^r)$ is a Diffie-Hellman tuple and this can be easily proved using known techniques for Sigma protocols. Note that this scheme is not efficiently decryptable, since decrypting only gives $g^m$ and you need to solve the discrete log problem to find $m$. Thus, if $m$ is from a small range, you can do this. Otherwise you cannot. However, it is an additively homomorphic commitment scheme, which may suffice for your application.


How does the process of creating a new secure Elliptic Curve look like? I'm especially curious about the technique djb would have used to come up with his Curve 25519. Say I have already written down my goals, such as - Twist Secure, Speed, Side Channel resistance, etc. In this case, how do I go about creating new curves? Are there specific algorithms that Cryptographers / Mathematicians use? Or is it just improvising on similar work?

As you said, you need to define the goals. You can take a look at SafeCurves, which is a joint work by Bernstein and Lange to help choose/construct elliptic curves w.r.t. ECDLP difficulty and ECC security. Note that if you need a pairing-friendly elliptic curve you need to look at other criteria related to the embedding degree. You can read this paper by Freeman et al. for different constructions. Now talking about Curve25519, Bernstein explained his choices in his paper. These are some of the main points he mentioned in a talk:

Curve25519 has a large prime char field because current CPU multipliers include fast floaing-point multipliers and extension fields punish CPUs with another multiplier size.
Curve25519 has a Montgomery shape $y^2=x^3+Ax^2+x$ with tiny $A \in 2+4\mathbb{Z}$ because one can do projective $x$-coordinate doubling and addition together using 1 field multiplication by $(A-2)/4$, 4 field squarings and 5 extra field multiplications without needing $y$ coordinate.
Curve25519 uses prime very close to a power of 2. Specifically, $2^{255}-19$ instead of a Solinas prime like $2^{256}-2^{224}+2^{192}+2^{96}-1$ because repeated addition is more costly than multiplication by 19.
Curve25519 uses a secure curve of order $8 \times \text{prime}$ with a secure twist $y^2=x^3+486662x^2+x$ of order $4\times \text{primes}$.
The $A$ is chosen so that $(A-2)/4$ is a small integer to speed up multiplication by $(A-2)/4$ (formulas here) and so that the twisted curve order is either $4 \times primes$ or $8 \times primes$. The smallest positive choices were then 358990, 464586 and 486662. Bernstein rejected 358990 and 464586 because one of their prime factors is slightly smaller than $2^{252}$ and discussing the question on how one should handle the theoretical possibility of a secret key matching the prime is harder than simply moving to the last choice $A=486662$ (Nothing up my sleeve).


ElGamal Encryption over a Subgroup Say for instance we are encrypting over a subgroup of ($Z_{67}^*, \bmod 67$).
To perform a round of El Gamal's encryption scheme we should:

Choose a subgroup of ($Z_{67}^*, \bmod 67$), of prime order.

Choose the parameters of ElGamal's scheme (generator, Bob's secret key, etc.).

Choose three random messages, and Alice's parameters, and describe what Alice transmits to Bob in each round

My question is not necessarily how to encrypt, but how to set up for encryption.
Given that in El Gamal's set-up is traditionally:

$(p, \alpha, \beta)$  is Bob’s public key.

$(a)$ is his private key

What would $p, \alpha, \beta$ be in this case? For example, is result of $(1) = p$? Result of $(2) = \alpha$?

The multiplicative group $\mathbb{Z_{67}}^*$ has 66 elements. By Lagrange theorem, we can say that the order of any subgroup $G$ of $\mathbb{Z_{67}}^*$ must divide the order of the group, 66. The inverse of the theorem doesn't need to be held, therefore one must check that there are subgroups of order 2,3, and 11, and their products.
With the below SageMath you can list the generators and their order;
def findOrder(a,G):
    temp = a
    for i in range (G.order()):
        if temp == G(1):
            return i+1
        temp = temp*a

R = Zmod(67)
grouplist = R.multiplicative_subgroups()
print(grouplist)
for x in grouplist:
    print(x, "order = ", findOrder(R(x[0]),R))

Don't try this code for large groups! This code outputs below with an error for the empty subset!.
( 2,) order =  66
( 4,) order =  33
( 8,) order =  22
(64,) order =  11
(38,) order =  6
(37,) order =  3
(66,) order =  2

Therefore, we have all possible subgroups, no counterexample for the inverse of the Lagrange Theorem.
The only prime orders are 2,3, and 11. For simple security, you need to choose 11. And actually prime is not necessary since ElGamal encryption can be defined over any cyclic group $G$. The security, on the other hand, relies on the Discrete Logarithm problem and when the group is not in prime order, the Pohlig-Hellman enters the game and we are not more secure than the largest prime order.
Ok, let stick with $p=11$ and it has a generator as $g=64$.

Choose a random integer $\alpha$ from $\{1,\ldots, 10\}$
Now, compute $\beta = g^{\alpha}$
The public key $(G,q,g,\beta)$ and the private key is $\alpha$


KDF and salt storage Regardless of the KDF I will use, let's imagine that I have to generate two keys: one for authentication and the other for encryption (which will always remain on the device that generates it until logout). Of course, the key I use to encrypt and decrypt must always be the same.
I read some answers on this site that suggested generating a random salt for both keys and saving it with these (preferably separate). But there is a problem: when the user has to decrypt the data or authenticate himself, he will need this precise salt, which must be taken from the database. Since he isn't yet authenticated, how can I trust those who ask me for this salt? Because if I gave it to anyone who asks for it, it wouldn't make sense to use it.
Maybe I am wrong about some considerations since I am a newbie. If I am not mistaken in my assumptions, how can I resolve this stalemate? I have read that some recommend using the hash of the email or username as a salt in these situations. Is it a good practice?  Consider that anyone on the client-side can see what I do on the data.

Since he isn't yet authenticated, how can I trust those who ask me for this salt? Because if I gave it to anyone who asks for it, it wouldn't make sense to use it.

That's where you went wrong. Salts are public: their purpose is to be unique per derived key, not to be secret. The security analysis of the KDF must assume that any salt used is public, so publishing them to anyone who asks is safe. That's one of the defining properties of a salt, as opposed to a "pepper". Peppers tend to provide no benefit that can't be provided by increasing the cost parameters, and complicate storage, so they're not used much.


DES: how does Richard Outerbridge's Initial Permutation operate? I know how initial permutation works, but I've never heard of this part.
People say it's Richard Outerbridge's initial permutation and that it's faster than usual IP (initial permutation) and simple.

How does this IP work? I've only the source to work with:

work   = ((leftt >>  4) ^ right) & 0x0f0f0f0f;
right ^= work;
leftt ^= (work << 4);

work   = ((leftt >> 16) ^ right) & 0x0000ffff;
right ^= work;
leftt ^= (work << 16);

work   = ((right >>  2) ^ leftt) & 0x33333333;
leftt ^= work;
right ^= (work << 2);

work   = ((right >>  8) ^ leftt) & 0x00ff00ff;
leftt ^= work;
right ^= (work << 8);
right  = (right << 1) | ((right >> 31) & 1);

work   = (leftt ^ right) & 0xaaaaaaaa;
leftt ^= work;
right ^= work;
leftt  = (leftt << 1) | ((leftt >> 31) & 1);

By definition, applying the initial Permutation of DES is shuffling bits per

01 02 03 04 05 06 07 08           58 50 42 34 26 18 10 02
09 10 11 12 13 14 15 16           60 52 44 36 28 20 12 04
17 18 19 20 21 22 23 24      \    62 54 46 38 30 22 14 06
25 26 27 28 29 30 31 32   ----\   64 56 48 40 32 24 16 08
33 34 35 36 37 38 39 40   ----/   57 49 41 33 25 17 09 01
41 42 43 44 45 46 47 48      /    59 51 43 35 27 19 11 03
49 50 51 52 53 54 55 56           61 53 45 37 29 21 13 05
57 58 59 60 61 62 63 64           63 55 47 39 31 23 15 07

where the left table represents, in reading order, bits of the 64-bit input from first (most significant) to last; and the right table represents, in reading order, the Left then Right 32-bit registers, per that same convention.

That transformation has great regularity: each line of the output (in reading order) is a column of the input (from bottom to top). That's a property of a transpose except for inverted order. IP is a mirror of the input according to the / diagonal, followed by a regular shuffling of lines (lines 1 2 3 4 5 6 7 8 go to lines 4 8 3 7 2 6 1 5).

This structure of IP has a hardware rationale: the transpose allows an implementation with Left and Right registers implemented each as four 8-bit shift registers, with 1 bit entering in each of the 8 shift registers for each plaintext octet sequentially fed into the DES hardware. And the shuffling brings next to each others the bits that interact when XORing the Left and Right registers.

The question's code makes use of 5 "Half-Butterfly Permutations" (as I name them by analogy with the butterfly diagram) indexed with $k$ taking all values from 0 to 4. Each splits the 32-bit lleft and right registers into $2^{5-k}$ segments each $2^k$-bit, and exchanges odd-numbered segments of one register with the higher (even-numbered) segment of the other, with thus a shift by $2^k$-bit.

One general HBP is implemented with 3 instructions involving a total of 6 bitwise operations directly supported by C. It uses XOR in a way similar to exchanging x and y with the idiom x^=y; y^=x; x^=y; taking advantage of associativity and commutativity to avoid a work value; but uses one due to the shifting and masking.

There are some irregularities in the code to perform the prescribed shuffling of lines. Also, the code wants to end with the 32-bit lleft and right pre-rotated on the left by 1 bit, because then the low-order 6 bits of these registers are properly aligned to serve as index in an S-box (after XOR with sub-key); and the HBP with $k=0$ is performed between these two rotations, because that removes the shifts in that HBP.

Here is how it goes step by step. We start from

01 02 03 04 05 06 07 08     most  significant byte of lleft
09 10 11 12 13 14 15 16     :
17 18 19 20 21 22 23 24     :
25 26 27 28 29 30 31 32     least significant byte of lleft
33 34 35 36 37 38 39 40     most  significant byte of right
41 42 43 44 45 46 47 48     :
49 50 51 52 53 54 55 56     :
57 58 59 60 61 62 63 64     least significant byte of right

then perform the Half-Butterfly Permutation with $k=2$

work   = ((leftt >> 4) ^ right) & 0x0f0f0f0f;
right ^= work;
leftt ^= (work << 4);

giving

37 38 39 40 05 06 07 08     most  significant byte of lleft
45 46 47 48 13 14 15 16     :
53 54 55 56 21 22 23 24     :
61 62 63 64 29 30 31 32     least significant byte of lleft
33 34 35 36 01 02 03 04     most  significant byte of right
41 42 43 44 09 10 11 12     :
49 50 51 52 17 18 19 20     :
57 58 59 60 25 26 27 28     least significant byte of right

then perform the HBP with $k=4$

work   = ((leftt >> 16) ^ right) & 0x0000ffff;
right ^= work;
leftt ^= (work << 16);

giving

49 50 51 52 17 18 19 20     most  significant byte of lleft
57 58 59 60 25 26 27 28     :
53 54 55 56 21 22 23 24     :
61 62 63 64 29 30 31 32     least significant byte of lleft
33 34 35 36 01 02 03 04     most  significant byte of right
41 42 43 44 09 10 11 12     :
37 38 39 40 05 06 07 08     :
45 46 47 48 13 14 15 16     least significant byte of right

then perform the HBP with $k=1$

work   = ((right >>  2) ^ leftt) & 0x33333333;
leftt ^= work;
right ^= (work << 2);

giving

49 50 33 34 17 18 01 02     most  significant byte of lleft
57 58 41 42 25 26 09 10     :
53 54 37 38 21 22 05 06     :
61 62 45 46 29 30 13 14     least significant byte of lleft
51 52 35 36 19 20 03 04     most  significant byte of right
59 60 43 44 27 28 11 12     :
55 56 39 40 23 24 07 08     :
63 64 47 48 31 32 15 16     least significant byte of right

then perform the HBP with $k=3$

work   = ((right >>  8) ^ leftt) & 0x00ff00ff;
leftt ^= work;
right ^= (work << 8);

giving

49 50 33 34 17 18 01 02     most  significant byte of lleft
51 52 35 36 19 20 03 04     :
53 54 37 38 21 22 05 06     :
55 56 39 40 23 24 07 08     least significant byte of lleft
57 58 41 42 25 26 09 10     most  significant byte of right
59 60 43 44 27 28 11 12     :
61 62 45 46 29 30 13 14     :
63 64 47 48 31 32 15 16     least significant byte of right

then perform the pre-rotation of right by one bit to the left

right  = (right << 1) | ((right >> 31) & 1);

giving

49 50 33 34 17 18 01 02     most  significant byte of lleft
51 52 35 36 19 20 03 04     :
53 54 37 38 21 22 05 06     :
55 56 39 40 23 24 07 08     least significant byte of lleft
58 41 42 25 26 09 10 59     most  significant byte of right
60 43 44 27 28 11 12 61     :
62 45 46 29 30 13 14 63     :
64 47 48 31 32 15 16 57     least significant byte of right

then perform the HBP with $k=0$, eased by the previous rotation

work   = (leftt ^ right) & 0xaaaaaaaa;
leftt ^= work;
right ^= work;

giving

58 50 42 34 26 18 10 02     most  significant byte of lleft
60 52 44 36 28 20 12 04     :
62 54 46 38 30 22 14 06     :
64 56 48 40 32 24 16 08     least significant byte of lleft
49 41 33 25 17 09 01 59     most  significant byte of right
51 43 35 27 19 11 03 61     :
53 45 37 29 21 13 05 63     :
55 47 39 31 23 15 07 57     least significant byte of right

then perform the pre-rotation of leftt by one bit to the left

leftt  = (leftt << 1) | (leftt >> 31) & 1);

giving

50 42 34 26 18 10 02 60     most  significant byte of lleft
52 44 36 28 20 12 04 62     :
54 46 38 30 22 14 06 64     :
56 48 40 32 24 16 08 58     least significant byte of lleft
49 41 33 25 17 09 01 59     most  significant byte of right
51 43 35 27 19 11 03 61     :
53 45 37 29 21 13 05 63     :
55 47 39 31 23 15 07 57     least significant byte of right

Skipping the pre-rotations and accordingly adjusting the HBP with $k=0$ would have given exactly the permutation specified for IP.


Create a ciphertext that decrypt to different plaintexts with different keys in RSA (This is inspired by this question 1; have also read this question 2 but it's one-time pad)

I would like to know, given two message $m_1$ and $m_2$, as well as public keys $(e,n_1)$ and $(e,n_2)$, can I create a ciphertext $C$ such that decryption with private key 1 $(d_1, n_1)$ gives $m_1$ and $(d_2, n_2)$ gives $m_2$?
$$C^{d_1}\equiv m_1\pmod {n_1}$$
$$C^{d_2}\equiv m_2\pmod {n_2}$$

I think it is possible because by Chinese remainder theorem, I can find a unique $C$ for any $m_1\ ^e$, $m_2\ ^e$, and respective coprime $n_1$ and $n_2$, such that
$$C\equiv m_1\ ^e\pmod {n_1}$$
$$C\equiv m_2\ ^e\pmod {n_2}$$

Is it possible? If so are there any significant limitations, or public implementations for this?

For the problem as stated in the question, yes what's asked is possible, exactly per the method stated in the question. For textbook RSA (except with unusually tolerant decryption code), no, that's not possible. For RSA as practiced, there exists solutions or not, and it can be found on not, depending on methods and parameters.

The critical differences are due to different definitions of a valid ciphertext $C$ for a message $m$ and public key $(n,e)$:

In the question's RSA, that's $C\equiv m^e\pmod n$, which allows arbitrary many integers $C$, since that notation only means that $n$ divides $C-m^e$, and implies that if $C$ is valid, then $z\,n+C$ also is for any $z\in\Bbb Z$. Notice that this version of RSA makes $C=m^e$ a valid ciphertext, and this choice of ciphertext allows decryption without the private key, as $m=\sqrt[e]C$.
In textbook RSA, that's $C=m^e\bmod n$, which further implies $0\le C<n$. This should be tested before decryption (and actual implementation often do this, or at least depend on $C$ not having much more bits than $n$). That leaves a single (or relatively few) valid ciphertext for any message $m$. A ciphertext is uniquely defined for $m_1$ with $(n_1,e)$, and there's no way to make it coincide with the uniquely defined ciphertext for $m_2$ with $(n_2,e)$. A spontaneous match won't occur by chance for even half-realistic modulus size.
in RSA as practiced, well there's not a single practice, but at least there again are many ciphertexts for any given plaintext, because the message is always combined with randomness for encryption¹. Block RSA encryption usually has $C=g(r,m)^e\bmod n$ where $r$ is a large random bitstring and $g$ is injective with output domain a subset of $[0,n)$. The size of $m$ is severely restricted compared to textbook RSA. If $r$ has sizably more than half as many bits has $n$, by the birthday bound, it is likely that one of the valid ciphertexts for $m_1$ with $(n_1,e)$ coincides with one of the valid ciphertexts for $m_2$ with $(n_2,e)$, implying there's a solution².

Doing what the question wants is easy: one computes $C_1=m_1^e\bmod n_1$ and $C_2=m_2^e\bmod n_2$ per textbook RSA, then by the Chinese Remainder Theorem one computes a $C$ such that $C\equiv C_1\pmod{n_1}$ and $C\equiv C_2\pmod{n_2}$. There is exactly one such integer $C$ in $[0,n_1\,n_2)$ under the hypothesis that $n_1$ and $n_2$ are coprime, which should hold for proper RSA keys. It can be computed as
$$C=\bigl(({n_2}^{-1}\bmod n_1)(C_1-C_2)\bmod n_1\bigr)\,n_2+C_2$$
This $C$ will decipher to $m_1$ for private key $(n,d_1)$ and to $m_2$ for private key $(n,d_2)$ under implementations of textbook RSA decryption that do not check that their ciphertext input is less than the modulus, and still compute exactly despite the anomalous input.

¹ Deterministic RSA allows anyone to check a guess of the plaintext, e.g. find who's name on a public class roll was encrypted. The addition of randomness fixes that often devastating weakness.

² For PKCS#1 v1.5 encryption padding (but not the better OAEP) it is conceivable to actually exhibit a solution if the message is very short and the corresponding private key is known and of the same size. With $m_1$ short, we compute various ciphertexts for $m_2$ and different random padding, and decipher each under $(n,d_1)$ until that does not cause an error, and the deciphered plaintext has the desired size, and it happens to match $m_1$. For 2048-bit $n_1$ and $n_2$, and $m_1$ of $k$ bytes, this is expected to require on average less than $2^{8k+26}$ attempts.


What is the difference between anomalous elliptic curve and ordinary elliptic curve? Probably this is a silly question but an anomalous curves and ordinary curves are the same things?

Let $E$ be an elliptic curve defined over a field $K$. Let $n$ be a positive integer.
$$E[n] = \{P \in E(\overline{K}) \,|\, [n]P = \infty\}$$
Where $\overline{K}$ is the algebraic closure of $K$ and $E[n]$ include the point with coordinate $\overline{K}$, not just from $K$. The above is the set of  $n$ torsion points on the curve, namely the points of finite order $n$. In Elliptic curves over a finite field, all points are torsion points.

An elliptic curve $E$ in characteristic $p$ is called ordinary curves if $ E[p] \backsimeq \mathbf{Z}/p\mathbf{Z}$
An elliptic curve $E$ in characteristic $p$ is called supersingular curves if $ E[p] \backsimeq 0$, and we know that those curves are not secure.
An elliptic curves $E$ over $F_q$ with  $\#E(\mathbf{F}_q ) = q$ are called anomalous curves. This is suggested to use against the MOV attack. Unfortunately, the discrete log problem for group $E(\mathbf{F}_q )$ can be solved quickly.

Ref: A good textbook: Elliptic Curves Number Theory and Cryptography, Second Edition, by Lawrence Washington.


Different implementations of SHA1, which one is correct? I have noticed that different implementations of SHA1 give different results. As I'm currently programming my own SHA1 implementation (in MATLAB / GNU Octave), I wonder which one should I follow?

There are several implementations of SHA1 in Rosetta Code. Using the message Rosetta Code, most of them give SHA1 hash of 48c98f7e5a6e736d790ab740dfc3f51a61abe2b5.

There is also Tools for Noobs Online sha1() function, that gives the same hash as the examples in Rosetta Code.

In Rosetta Code, there are also two examples of computing SHA1 in Unix shell:

In my own computer (Debian Linux Wheezy amd64),echo 'Rosetta Code' | sha1sum gives a SHA1 hash of d350d93ccda0fbf2d5037dedd2f3763fe880b2c5 and echo 'Rosetta Code' | openssl sha1 also gives the same hash.

However, the Rosetta Code examples of computing SHA1 in Unix Shell use different message: ASCII string . According to Rosetta Code, echo -n 'ASCII string' | sha1 should give 9e9aeefe5563845ec5c42c5630842048c0fc261b, and echo -n 'ASCII string' | openssl sha1 | sed 's/.*= //' should give the same hash. When I try ASCII string as message in Tools for Noobs Online sha1() function, it gives the same hash as the examples of Rosetta Code on computing SHA1 in Unix shell. So I can conclude that all these implementations of SHA1 in Rosetta Code and also Tools for Noobs Online sha1() function give identical hashes.

In my own computer, using the message ASCII string I get the hash 4f9e000b925f5d96def1d9b3e21cdc11f1df6139 either by echo 'ASCII string' | sha1sum or echo 'ASCII string' | openssl sha1.

So, of all these implementations, only my own computer's sha1sum and openssl sha1 differ from the examples of Rosetta Code and Tools for Noobs Online sha1() function. Has this something to do with the UTF-8 vs. ASCII, processor type, endianness, message suffixing differences or is there something wrong in my Linux configuration?

The echo command will include a newline at the end. So when you use echo 'Rosetta Code' | sha1sum you are actually hashing the string Rosetta Code\n.

Do the test using echo -n, the -n flag prevents the trailing newline character. Doing echo -n 'Rosetta Code' | sha1sum gives the same 48c98f7e5a6e736d790ab740dfc3f51a61abe2b5 hash that you were seeing elsewhere.


Can all affine cyphers be expressed with this formula There are $26!$ permutations of the English alphabet.
In Modern Cryptography textbook, William Easttom states that

the basic formula for any affine cipher is $ax + b \equiv \pmod{26}$.

I'm wondering whether this formula can express every possible permutation. It does not seem obvious that for every permutation $\sigma$ there exist $a$ and $b$ capable of expressing it. If this statement is true, what approach can be used to find $a$ and $b$?

$a\cdot x +b $ means affine  not permutation. And $a\cdot x +b \bmod 26$ is modular affine transformation.
$a\cdot x +b \bmod 26$ can have at most $26\cdot 26$  affine transformations some of which have no inverse and therefore without an inverse an affine transformation is not suitable for encryption where it is already not close to the modern encryption methods.
To have an inverse one must have $\gcd(a,26)=1$. This means $a$ cannot be divisible by 2 or 13. To find the actual number we can use Euler's Totient Function that counts the positive integers up to a given integer $n$ that are relatively prime to $n$. Then $$\phi(26) = (13-1)\cdot (2-1) = 13$$ So there are actually $26\cdot 12 =312$ possible affine transformations.
In any case, we have $26! = 403291461126605635584000000$ permutations and $312$ affine transformations, therefore the affine transformation cannot cover all possible permutations. The reverse is correct; the permutations can represent the invertible affine transformations.


CBC related TLS cipher suites to be disabled in the server side I understand the TLS cipher suites using CBC mode are susceptible to timing attacks. From that understanding it seems that the cipher suites using GCM (CTR-based) are safe to use considering they don't need padding.

However, in Java, SunJSSE provider by default enables many cipher suites that are using CBC. And whether those cipher suites will be used or not are determined by the client preference.

While using Chrome and FireFox latest versions, I noticed the cipher suite used is AES_128_GCM.

Now, is it advisable to disable all the CBC related cipher suites in the server to ensure only GCM is used regardless of the client preferences? Is there any limitation with this approach of using only GCM related cipher suites?

Based on the useful comments above, some of the resources I found to provide an insight into the matter is as follows:

TLS Support tells us which browser versions support which TLS versions. Since (as puzzlepalace mentioned) GCM was introduced in TLSv1.2, we get an idea as to what browser versions we'll miss out by supporting only GCM
Qualys (as forest mentioned) shows some of the best SSL configured website and the cipher suites used. This also shows the cipher suites used by your browser. The best practices for TLS deployment and the recommended list of cipher suites are listed here. Finally, this table lists which browser versions support what.

In summary, all major browsers support TLS 1.2 since Oct, 2013 and therefore GCM.

Forward secrecy (ECDHE) is available from even before.


Kerckhoffs’ principles – Why should I make my cipher public? As I understand it, the less people know about the internals of my protocol or cipher, the more secure the protocol is. However Kerckhoffs's principle states that

  A cryptosystem should be secure even if everything about the system, except the key, is public knowledge.

To be more precise, it's the 2nd principle that states

  It must not be required to be secret, and it must be able to fall into the hands of the enemy without inconvenience;

Of course I understand why I should keep the key secret, but publishing my protocol's internals seems counter-intuitive. Why should I do it? Wouldn't that give the advantage to the attacker?

Actually, that wikipedia article you mention in your question already answers your question:

  It is moderately common for companies and sometimes even standards bodies as in the case of the CSS encryption on DVDs – to keep the inner workings of a system secret. Some argue this "security by obscurity" makes the product safer and less vulnerable to attack. A counter argument is that keeping the innards secret may improve security in the short term, but in the long run only systems that have been published and analyzed should be trusted.

But let's dive in deeper anyway...

Kerckhoffs’ principles

For reference purposes, here is Kerckhoffs' original text (from Auguste Kerckhoffs, "La cryptographie militaire", Journal des sciences militaires, vol. IX, pp. 5–38 "II. DESIDERATA DE LA CRYPTOGRAPHIE MILITAIRE.", Jan. 1883):

In plain text, this reads:

  1° Le système doit être matériellement, sinon mathématiquement, indéchiffrable ;
  2° Il faut qu’il n’exige pas le secret, et qu’il puisse sans inconvénient tomber entre les mains de l’ennemi ;
  3° La clef doit pouvoir en être communiquée et retenue sans le secours de notes écrites, et être changée ou modifiée au gré des correspondants ;
  4° Il faut qu’il soit applicable à la correspondance télégraphique ;
  5° Il faut qu’il soit portatif, et que son maniement ou son fonctionnement n’exige pas le concours de plusieurs personnes ;
  6° Enfin, il est nécessaire, vu les circonstances qui en commandent l’application, que le système soit d’un usage facile, ne demandant ni tension d’esprit, ni la connaissance d’une longue série de règles à observer.

And here is my English translation for your convenience:

  The system must be physically, if not mathematically, indecipherable;
  It must not require secrecy, and may not cause inconveniences when it falls into the hands of the enemy;
  The key must be communicated and retained without the aid of written notes, and be changed or modified at the discretion of correspondents;
  It must be applicable to telegraphic correspondence;
  It must be portable, and its usage and its operation does not require the assistance of several people;
  Finally, it is necessary, given the circumstances that control the application, that the system is easy to use, requiring no mental strain, or the knowledge of a long series of rules to be observed.

The enemy knows the system

Kerckhoffs' surviving principle nr. 2 (of initially six design principles for military ciphers) says nothing else than that you have to look at the security of your crypto under the aspects of "the enemy knows the algorithm" and maybe even "the enemy carries the message". The well-known Claude Shannon once simplified Kerckhoffs' principle as: "the enemy knows the system".

The "advantage to the attacker" one might be thinking about when deciding to keep an algo secret, would practically be "just a matter of time for the attacker to find out" since keeping the algorithm secret would be relying on "security through obscurity", which we all know to be a bad idea.

The idea of Kerckhoffs' principle is that if any part of a cryptosystem (except the individual secret key) has to be kept secret then the cryptosystem is not secure. That's because, if the simple act of disclosing some detail of the system were to make it suddenly insecure, then you've got a problem on your hands. The gold standard for any secret keeping system is that all its details should be able to be made public without compromising the security of the system. The security relies on the system itself, not the secrecy of the system.

A good example of why Kerckhoffs' principle makes sense would be the German Enigma machine used in WWII. By stealing machines, the Allies knew everything there was to know about how the Enigma machine worked; they only had to read the manuals, use the code-books and look at the way the machine was constructed and worked. After all, they had a working example in their hands. Throughout history, there are countless examples of secret algorithms falling into wider knowledge, variously through espionage, betrayal and reverse engineering. And on occasion, ciphers have been reconstructed through pure deduction. For example, the German Lorenz cipher and the Japanese Purple code, and a variety of classical schemes.

Therefore, the core idea of Kerckhoffs' 2nd principle is still applied today. The security of HTTPS, SSL and ciphers like AES or RSA rely on the strength of the algorithm, not on keeping them secret. The algorithms are all published and detailed standards have been created which everyone can take a look at. The only "secret" is the key that's chosen when you connect to a secure web site (that's done automatically and randomly by your browser and the server) or when you encrypt a document using a program like GPG.

To recap: why publish the cryptographic algorithm?

Not publishing a cryptographic algorithm doesn’t make much sense as it's just a matter of time for the attacker to find out how your crypto works. Security gain can therefore only be of temporary nature.

On the other hand, publishing of a cryptographic algorithm tends to build trust because the publication of its internals allows the verification of related security claims.

In fact, you can even transport the answer to “why publish the cryptographic algorithm” down to a much simpler level: the security of the lock of your home's door does not depend on keeping the lock hidden and its mechanisms secret. Its security comes from you keeping the key safe. That is one of the most simple examples of Kerckhoffs' 2nd principle in action.

One of many examples

To provide an example, let me point you to — what I would call — an "über-publication": "The Design of Rijndael: AES - The Advanced Encryption Standard" by Joan Daemen and Vincent Rijmen.

This book, written by the designers of the block cipher, presents Rijndael (more commonly known as AES) from scratch. The underlying mathematics and the wide trail strategy as the basic design idea are explained in detail and the basics of differential and linear cryptanalysis are reworked. Subsequent chapters review all known attacks against the Rijndael structure and deal with implementation and optimization issues. Finally, other ciphers related to Rijndael are presented.

As you might have noticed: it didn't hurt the security of Rijndael/AES in any way that all its internals were published. Quite the contrary – related publications only resulted in more confidence in the cipher.


SpongeWrap without padding and frame bit Assuming all inputs are same length as rate except last can be shorter. Is it necessary to pad every input (not just last) to sponge for authenticated encryption to be secure?

Is this just, because it is wrapped around Absorb and Squeeze?

What is purpose of frame bit in SpongeWrap?

Is it necessary to pad every input (not just last) to sponge for authenticated encryption to be secure?

Yes. The purpose of the padding is to make every possible input unique. So a full block must result in a different bitstring than any padded non-full block. There is no way to pad only the incomplete block and still have it differ from all the full blocks.

If you didn't use such padding, two different messages could lead to an equal state.

  What is purpose of frame bit in SpongeWrap?

The purpose of the frame bit is domain separation. To quote the pdf (4.1.5):

  The duplex (or equivalently, sponge) inputs to generate key stream blocks and those to generate tag blocks are in separate domains. Every duplex response that is used to encipher the next block has as input a string ending with a frame bit 1, whereas every duplex response that is used to form a tag has as input a string ending with a frame bit 0.

If this wasn't the case, the authentication tag and the "next block" keystream could be equal. This would allow an attack where you truncate the message and forge an authentication tag from the ciphertext, if you know the plaintext of the last block of the message. Because of the frame bit they are independent, so the ciphertext cannot help you with forgeries.


Is signing a hash instead of the full data considered secure? I reference object in some of my code in hashes. The signature is itself is another object separate from the one I am signing (for obvious reason). I consider simpler to simply sign the reference to my object (its hash), but I wonder if it is considered secure.
Here's a more complete explanation:

A: Is the data object to be hash then signed
H: Is hash(a), the reference to A
S: Is the signature object which contain H and sign(H)
S and A are sent on the network so A can be verified with its signature

This is secure, and a lot of systems actually do signatures this way (for example, PGP). One reason to do this for performance. Signing a hash is much faster than signing your whole message. It is also non-trivial to hash large messages since signature functions usually operate on a bounded size input.

An attacker will have just as much difficulty forging a signature on the hash as they would forging the signature on the message itself.


Short term for "Purposely-slowed hash" When Argon2, Balloon, scrypt, bcrypt¹, PBKDF2… are used for a password, we can call them password hash (for password storage) or password-based key derivation function (for use in encryption).

But that might not be understood when the context involves no passwords. Purposely-slowed hash is more descriptive, but awkward, and I have seldom seen it.

Are there established alternatives? If not, what do you propose?

Addition: I wish the term would be usable for strengthening the $b$-bit hash of a $3b$-bit Schnorr signature against brute force preimage attack. In this usage, there's nothing secret involved.

¹ As rightly pointed in comment, bcrypt can only produce 192 bits of output, which makes is passable for password hashing or short keys, but not a general Key Derivation Function.

1) I don't know any established alternatives.

2) It is not correct to say that such algorithms are purposely-slowed. They not only can be slowed, but also can use much memory. A single word for this would be resources. And I would stress even not resources, but rather the price, because the whole idea is to make the price prohibiting for attackers. I would suggest following terms:

Expensive hashing
Resource intensive
Resource demanding
Resource hard
Resource greedy
Resource hungry

I will put these terms each as a separate comment below my answer. Feel free to vote :) In a couple of weeks we'll see the result.


Where can I find official test vectors for NIST SP 800-56C r1 Single Step KDF NIST 800-56Cr1 describes a single and two (extract-expand) step KDF designed for use in key agreement routines. NIST declares that HKDF (RFC5869) is a version of the two-step variation so test vectors can be found in the RFC. However I am not able to find test vectors for the former, one-step variation.

There are some for KBKDF (aka SP 800-108) in the Cryptographic Algorithm Validation Program, but not for 800-56C specifically. Can someone point me to the official or other test vectors?


XOR PSK with random buffer I need some guidance here:

assuming I have the following:

(PreSharedKey of 32 bytes) XOR (one time Random Buffer of 32 bytes)

The only way to crack this should be brute forcing, correct? One of the issue in sending out the XORed value is to disclose the PSK length. At this point I could add some random bytes at the end of the XORed value to avoid this (the two ends knows the real PSK len). But does it make sense? Or it would be better to just  increase the PSK (and the random buffer) length of the same number of bytes to get more security?

Sorry for the newbie question...

Thanks,

One of the issue in sending out the XORed value is to disclose the PSK length

This is only an issue if you consider the length of the PSK to be a secret and not just the value. In that case you probably should redesign your system to not depend on the length of the PSK being secret, e.g. by always sending an upper-length PSK and also sending the amount of bytes used if you need secret variable length.

  The only way to crack this should be brute forcing, correct?

Assuming an adversary only gets to see $K\oplus B$ with $K$ being your PSK and $B$ being the one-time buffer, this is a one-time pad and an adversary cannot infer anything about the PSK they didn't already know. In particular an adversary cannot infer the concrete value. However this guarantee is void if the same buffer $B$ is used more than once - even with the same key as then the adversary knows the key has been re-used which you may or may not want to leak. And of course note that receiver of this value also has to know $B$ which at this point becomes a one-time-use PSK itself which begs the question why one doesn't use $B$ as the key directly potentially with a more standard symmetric key-exchange protocol to get a fresh session key - which can be as simple as encrypting a monotonic counter and a new key under the PSK.


Can you break a Vigenere cipher with key length of 2 and message/cipher text length of 4? I am currently working on a problem where an attacker knows that a user's password is either "pqrs" or "jmlo" and also knows that the encryption scheme is using the Vigenere cipher with a key length of 2 (Obviously, the attacker also knows the ciphertext). I must either describe how to find out with 100% certainty that the password is either pqrs or jmlo, or describe why this cannot be broken.
After working through it, I cannot see how this would be broken. The plaintext is only 4 characters, so statistical analysis and Kasiskis method of searching for bigrams/trigrams wont work either. Is there anything you can do to crack this encryption scheme?

If I can prove there's no single key that can encrypt to both outputs I can prove with 100% certainty which message it is, but if not I can't.

"pqrs" or "jmlo"

You can identify which password it is by comparing each letter with the corresponding letter once encrypted. For example, compare $P-R$ with $J-L$ (treating each letter as a number

They look like variables in this notation but they're not.

P and R are 2 letters apart; J and L are also 2 letters apart so that's inconclusive.
Q and S are 2 letters apart. M and O are also 2 letters apart; so that's also inconclusive.

This means there exists a 2-character key mapping each password to the same ciphertext (the mathematical relations between the letters are insufficient to distinguish). As such, there's no way in this case to identify which password it is.


What happens when a root CA has its private key compromised? What happens when a root CA has its private key compromised? Then all children in the tree are compromised too? And then all certificates are compromised? What needs to happen then?

Related:
- How can we get CA's public key?
- I've got my private key compromised. How does CRL work?
- What happens when a root CA has its private key compromised?

A lot of sleepless nights for the CA, their customers, web browser and OS developers, and Slashdot users, that's what.
I don't know if a CA has ever had their private keys compromised, but there have been incidents where their systems were broken into and fraudulent certificates were issued. (There's a difference between a private key actually being taken, and an attacker just being able to feed bogus certificates into the system and get them falsely signed -- though both are quite bad enough.)
In 2011, a reseller for Comodo (later renamed to Sectigo, and still one of the largest CAs in existence) was compromised and used to issue several fraudulent certificates for google.com and other major domains. Comodo quickly revoked the certificates and disabled the reseller's account, and as a bonus (since online OCSP and CRL checks can be blocked) web browsers and OSes released updates specifically banning those certs.
Comodo was "encouraged" to be more careful -- indeed, another reseller account was compromised less than two weeks later but the attacker was unable to accomplish anything with it -- but their roots were not revoked and they suffered no major consequences. (The reseller is still around, too.) There was a great deal of handwringing around the Internet about whether this was an appropriate response to a limited breach or whether Comodo had made an unforgivable mistake but received "too big to fail" special treatment.
Later in 2011 (bad year), a CA called DigiNotar was compromised, and hundreds of fake certificates were issued, for Google and all sorts of other domains (again). When web browser and OS companies were eventually informed, they revoked DigiNotar's roots from their certificate stores -- defanging the fraudulent certs but breaking many (largely Dutch) websites in the process.
DigiNotar avoided informing anyone of the incident for more than a month, and were unable to produce a complete list of fraudulent certs. Mozilla, for one, lost confidence in them, and DigiNotar was bankrupt in weeks.


Encrypting serialized data If I want to encrypt structured data composed of key-value pairs of strings, would it be an advantage to use an encoding that stores keys, values and their lengths, and is padded with random numbers, rather than JSON that always starts with {", ends with "} and predictably contains strings enclosed in "..." separated by ,?
I'm thinking of encoding the data like this:
R1
LK1 K1
LV1 V1
LK2 K2
LV2 V2
R2

(where Rn are random numbers of fixed size obtained from a CSPRNG and L.. are the lengths of the data that follow)
instead of:
{ "K1": "V1", "K2": "V2" }

If I want to encrypt structured data composed of key-value pairs of strings, would it be an advantage to use an encoding that stores keys, values and their lengths, and is padded with random numbers?

Generally, no, this is not a good idea. A semantically secure cipher uses an IV or nonce (number used once, a unique number in a statically sized encoding) that randomizes the ciphertext in combination with the key used. There is therefore no need to randomize the data input (the "message") itself.
It very much depends on the mode of operation if the randomization of the message will actually fully randomize the data in the first place. In case of CBC mode a random block with the block size of an IV could be used as an alternative to a random IV. However, it would not really differ from using an IV in the first place; it will actually cost you one additional block to encrypt for no reason at all. On the other hand, if you consider the more modern CTR mode then the key stream will just be XOR-ed with the random input, and it won't influence the rest of the plaintext / ciphertext message. The random data would just be overhead without offering any benefit.
Modern authenticated modes just require a nonce, randomized or not. GCM mode for instance requires a 12 byte nonce. You can safely prefix the IV or nonce to the ciphertext (as the size is commonly known or configured in advance). Note that CBC mode requires an unpredictable (i.e. randomized) IV.


Encryption for a short packet size I have an 8051 microcontroller with a radio that can send packets with up to 32 bytes and I want to have the messages encrypted. It is a sensor network so I really only want to send one packet per message to have the least power usage for the battery operated nodes.

I am trying to figure out how to do something useful and secure, the microcontroller in question has AES acceleration by way of a Galois field calculator so that was my first stop, however the messages are mostly not changing much so ECB mode will expose too much by not changing many times and adding an IV will essentially limit me to 16 byte messages since I'll need 16 bytes for the IV and 16 bytes for the encrypted message.

One option I thought of an believe is insecure except that I don't know by how much is to have 16 bits of a random number and a 16 bit counter in the first 16 bytes, encrypt that as ECB and then chain the output as a bastardized CBC to the second block. This means I will be transmitting 32 bytes all the time and the IV will be faked inside the packet but the internally changing 32 bits do not sound like a good enough protection.

Another option I started to consider is a stream cipher, in this case Salsa20 which seems to have a sufficiently fast and sufficiently small implementation and it only requires 8 byte nonce and I can use it with either 256 bit (32byte) key or a 128 bit (16 byte) key. This means I only lose 8 bytes to the nonce/IV, the block number will always be zero as I never need to send more than 32 bytes out of the 64 byte stream output.

The later sounds like a better compromise overall. I will "lose" the 8 byte nonce from the packet but will probably gain a better security.

I'd appreciate any thoughts on what is preferably between the two and what may be other and better options that I didn't consider.

Dmitry's suggestion to use AES in counter mode sounds good to me, assuming that you only need confidentiality, and not integrity protection.  (Counter mode, like most stream ciphers, is very malleable.)

One trick you can use to save a bit of space is to use the current time as part of the nonce.  (Of course, this only works if your devices have fairly well synchronized clocks.)  To make this scheme more robust against slight clock skew, you should transmit a few of the least significant bits of the timestamp as part of the message, so that the receiver can adjust their timestamp to match it.

For instance, let's say that your devices have clocks that are assumed to be synchronized to within one minute of each other, that they'll need to transmit at most 256 messages per second, and that there are at most 256 devices communicating with each other.  Then you could use the following four-byte header for each message:

Byte 1: Sender ID.
Byte 2: Receiver ID.
Byte 3: Eight least-significant bits of the current time (in seconds since epoch).
Byte 4: An 8-bit message counter, reset whenever byte 3 changes.

This header would be transmitted in the clear, at the beginning of each message.  The remaining 28 bytes can then contain data encrypted using AES-CTR (or some other stream cipher), with a 16-byte IV constructed as follows.

Bytes 1–8: A unique 8-byte identifier for this group of devices.
Bytes 9–10: Sender and receiver IDs (from header bytes 1 & 2; included to ensure that IVs are not reused between different pairs of devices).
Bytes 11–14: A 32-bit timestamp (seconds since epoch; byte 14 = header byte 3).
Byte 15: Message counter (header byte 4).
Byte 16: Within-message block counter (really needs just one bit for two-block messages, but using a whole byte leaves some expansion room).

For the sender, constructing this IV is straightforward.  For the receiver, the only complication is that they'll need to reconstruct the sender's timestamp for bytes 11–14, by picking the nearest time that matches the 8-bit timestamp in the header.  (This might be either in the past or in the future, due to clock skew.)  One way to implement that is as follows:

Initialize message timestamp to current time.
Replace lowest 8 bits of message timestamp with byte 3 from message header.
If message timestamp is more than 128 seconds in the past, increment it by 256 seconds.
If message timestamp is more than 128 seconds in the future, decrement it by 256 seconds.

Optionally, if the reconstructed timestamp is off by more than 64 seconds (or so), the receiver may wish to initiate a time resynchronization protocol.  Note that, with any time resynchronization scheme that potentially involves adjusting clocks backwards by a full second, either the devide ID or the group ID should be changed to prevent IV reuse.

In cases where the clock skew is only slight, it may be preferable to use a gradual adjustment scheme (i.e. telling the skewed device to count seconds a little slower or a little faster) that doesn't involve sudden time jumps.  Or, alternatively, you could always have all the devices adjust their clocks foward to match the fastest-running clock (which might gradually shift them away from "true" time, but would keep them in sync without backwards time jumps).  One way to handle this would be to separately track "true time" and a guaranteed monotonely increasing "message time", storing an offset between these.

Of course, you can adjust this header depending on your timing, message rate and device count needs.  For example:

If you have good clock synchronization, you can increase the clock resolution (to, say, one millisecond) to allow a higher message rate.
If all your devices communicate with a single central controller (and not directly with each other), you can replace the sender and receiver IDs with a single device ID and a single direction bit indicating whether the message is to or from the controller.  (Technically, you don't even need to transmit the direction bit, since the receiver will always know what it should be; but you do still need to include it in the IV.)
If your transmissions are very bursty, you can use more bits for the message counter, and less for the truncated timestamp.  Conversely, if your messages are sent at regular intervals, you can use less bits for the message counter, or even eliminate it entirely.  (Technically, you only need one or two timestamp bits, while the rest can be part of the counter; however, the higher the resolution of the message timestamps is, the easier and safer it is to recover if, say, your device suddenly loses power and forgets the current message counter value.)

The important thing is to ensure that, no matter what happens, the same IV is never used twice.  Also, since CTR mode does not offer integrity protection, you should make sure to design your underlying protocol to be robust against both garbage messages, and messages that might have been deliberately modified by an attacker.  For certain critical messages (like time synchronization commands, or other messages that could be used to adjust encryption or other essential operation parameters), this may require the use of a MAC at a higher protocol level.


How is the inter and the intra distance of a PUF calculated? I was wondering, if I want to calculate the intra distance of a PUF, and I have already measured $n$ times a response to a challenge. Do I choose one reference value and compare the hamming distance of it to all other values $n-1$ comparisons? Or do I compare each response to each other $(n \times(n-1))/2$ comparisons?

The same question for the inter distance. Furthermore would be interesting how great should be $n$ in both cases to get meaningful values? Can this somhow be statistically "proven" by some kind of tests?

I believe Roel Maes gives a very good answer to your question in his PhD thesis, pages 20-23.

In essence, ideally, you need to calculate an array of the Hamming Distance between every pair of responses to the same challenge. Those pairs correspond to either the same chip or different chips depending on if you are looking at intra- or inter- distance.

Both metrics and various statistics based on them are, in principle, characterising the performance of the whole PUF construction. For example, the maximum intra-distance would give an idea of the worst case ('least reliable') response that could be expected. As a result, $n$ should be equal to the maximum number of challenge-response pairs (CRPs) offered by the PUF.

Of course, reading out all the CRPs negates the purpose of the PUF in some scenarios. In practice, one would get hold of a number of instances of the same chip and run some characterisation experiments to get the metrics. After establishing a certain confidence in those metrics a different set of chip instances would be deployed in production.

The whole thesis (with a lot more details and formulas) is freely available at https://lirias.kuleuven.be/handle/123456789/353455


What is the probability of a collision in SHA-512 when the input is 512 bits of data Although this question is strongly related to my previous question, it's certainly not the same:

Suppose the input of SHA-512 is 512 bits of data (so exactly the same size as the output). If I would test every possible permutation (so $2^{512}$ calculations), then will the output also be exactly $2^{512}$ different hashes, or will collisions occur ?

If collisions occur, would the amount of collisions and the 'size' of the collisions (approximately) be the same as statistics would predict after randomly generating $2^{512}$ 512-bit strings ? (With 'size' i mean the amount of times a specific hash occurs)

Suppose the input of SHA-512 is 512 bits of data (so exactly the same size as the output). If I would test every possible combination (so $2^{512}$ calculations), then will the output also be exactly $2^{512}$ different hashes, or will collisions occur?

It would be astonishing if SHA-512 turned out to be a permutation on 512-bit inputs, so no, absent a publication-worthy breakthrough in SHA-512 analysis, the output would not be exactly $2^{512}$ distinct hashes.

  If collisions occur, would the amount of collisions and the 'size' of the collisions (approximately) be the same as statistics would predict after randomly generating $2^{512}$ 512-bit strings? (With 'size' I mean the amount of times a specific hash occurs)

As far as we know, yes.  The usual model is a uniform random function.  Under each distinct input, the output is an independent uniform random bit string.  This model is like writing down a giant book of outputs with $2^{512}$ pages, one page per input having the corresponding 512-bit output, where every output is chosen independently and uniformly at random—which is exactly what you just described.

If we examine the structure of SHA-512 under the hood—a block cipher, which we might call ‘SHACAL-512’ (related to SHACAL-2, which is the block cipher underlying SHA-256), in Davies–Meyer composition—for 512-bit message $m$, we have $H(m) = E_{\operatorname{pad}(m)}(h_0)$ where $h_0$ is the standard initialization vector.  In the ideal cipher model, every distinct 1024-bit string $\operatorname{pad}(m)$ gives rise to an independent uniform random permutation $E_{\operatorname{pad}}(m)$, whose output on a fixed input string $h_0$ is then an independent uniform random 512-bit string.  Absent cryptanalysis of ‘SHACAL-512’, there isn't a much better model for this either.


Little problem with Vernam Cipher We have got a task with the following content:

Given is a language with 3 letters: A, B, C.

The binary expression is:

A = 000, B = 1111 and C = 0011

Two words were encrypted in this language with the same key:

W1 = 0101001110111010101100100
W2 = 1011001010000000000101011

Determine the possible message pair.

How am I able to do this?

I think guessing key bits and checking if the plaintext is valid in both words is the way to go (much like a binary puzzle).

For instance, it is clear that at least one of the words starts with an A because if you take the first 4 bits they are all different except for the last one. That rules out BB, BC, CB or CC as combinations of the first letter, because they don't differ by 3 bits where the final bit is 1. Similarly you should be able to rule out two other combinations, leaving only one combination - unfortunately you don't know yet if it is AX or XA. Similarly, you expect an AA and B combination at the final bits as the bits must be each other complements.

I would implement this using left to right guessing of key bits with backtracking in case the pattern becomes impossible for either W1 or W2. You may even start at each end, but I don't think that is needed. You should be able to do this by hand, but programming it may be fun as well.

In the end I see 13 bits set to 0 and 13 bits set to 1, and I had to backtrack 18 times to find a solution (assuming bits set to 0 before possibly back tracking, simply working from left to right), which is entirely doable for a mere human. Of course giving the key, the pattern of W1 or W2 gives away the entire result, so I won't do that.

The complement of the found key is also a solution in this particular case.

High level design:

create a tree for the key;
create code to perform a breath first search of the key bits;
create a method to check if a given (partial key) could be valid;

create a method that creates a tree of patterns;
check for W1 and W2 - up to the key size - if the key produces a tree up  to a leaf node;
to do this you can search the tree using depth first search;

create checks to see:

if the key is complete;
if there can be a partial match at the end;

Beware to check the end conditions correctly, or you may have to do some manual restructuring at the end.

This is not an easy task to program. Basically you need to create a tree for both the key as well as the resulting plaintext to perform the pattern matching.


Why is pqRSA in the NIST PQC submissions? In the NIST post-quantum cryptography workshop, the round one submissions included pqRSA. If memory serves, this is an implementation of RSA using the product of a very large number of 4096-bit primes to protect against Shor's algorithm. It requires something like a terabyte of private key material. Why was this submitted to NIST given that its impracticality obviously disqualifies it?

[source of information: my interpretation of multiple hallway chats I've had with DJB and Tanja Lange at conferences]

The actual NIST PQC submission was for two reasons:

A joke. Evidence1: DJB yelling from the back of the room "How much RAM does the NIST benchmarking machine have??" Dustin Moody replying "Dan, we're not benchmarking pqRSA!". Evidence2: DJB mercilessly mocking his paper's reviewers on stage: "Of course it's not practical! This guy clearly has a British stiff upper lip".
A template for other submissions. DJB's plan at least was to submit it several months early to iron out the kinks in the submission process, and to make the latex source public for other submitters to re-use the format and the legal boilerplate (I don't know whether he did or not).

The scientific work behind the submission made some very valuable contributions to the field of cryptographic science:

Answer the question:

Question: "Do the honest parties (keygen, encrypt, decrypt) have an asymptotic advantage over a Shor's adversary? If so, how big does the key need to be to get a comfortable amount of quantum security?"
Answer: Yes; 1 TB keys to force a quantum circuit with >= $2^{128}$ gates. This reduces to 1 GB keys if you take into account latency between quantum gates and make a "not before expiry of the universe" type argument.

Modification to the encrypt and decrypt operation to make them more efficient on multi-prime keys.
Batch-prime generation: to optimize keygen of several thousand (million?) 1024-bit primes, they came up with a way to more efficiently generate primes in batches.
Can we save ECC the same way? As part of the same research, effort was put into making a pqECC with a similarly massive key, but they could not find equivalent mathematical tricks that would give the honest parties an asymptotic advantage over a quantum adversary.

Even though the submission will not make it past Round1, it made valuable contributions both to the competition itself, and to cryptographic science as a whole. As @SqueamishOssifrage said in comments:

  The hard work was already done—the paper written, the code tested—so hey, why not submit it?


How to implement a Cryptographic Pseudo Random Function I need three pseudo random functions which all take  a
seed S (t-bits long).

The functions should map from

$d$ bits to $d$ bits
$d$ bits to $1$ bit
$d$ bits to $t$ bits

$d$ is $10$ bits
$t$ is $2048$ bits

Can you link me to some c++ implementation(or any language) or tell me how to implement it?

$f_s: d \rightarrow d$ bits is a Pseudorandom Permutation  (see Luby-Rackoff Constructions)
$f_s: d \rightarrow 1$ bit is a Hardcore bit (see Goldreich Levin Theorem)
$f_s: d \rightarrow t$ bits is a Pseudorandom Generator. (assuming $t$ is a function of $d$)  (see Goldreich Goldwasser Micali)

(All these topics are coved in the Katz-Lindell book.)

With these constructions known, you'll be writing provably secure constructions for the crypto primitives.

Also, please forgive my abuse of notation here, when i write $f_s: x \rightarrow y$, what I really mean is $f: x \times s \rightarrow y$


How to generate a large random number from smaller ones? I'm using a function randInt that takes as input two integers as upper and lower bounds (inclusive) and outputs a pseudorandom number in that interval. Unfortunately, the function's range can be an interval no greater than $10^{14} - 2$ (meaning the difference of the inputs can be no more than that value). As a workaround, I want this function to generate a number in the closed interval $[0, p-2]$ where $p$ is a large prime (for example: 246,494,430,254,053,509,990,478,163,925,484,154,219).

I can't simply break it into digit groups and generate each group randomly because then the generated number could be 246,494,430,... and then all nines. I also want to avoid looping until I get a number smaller than $p$. How can this be done?

Let's assume that randInt gives you cryptographically random (independent) numbers in the range $[0, N)$. Then you can generate a larger number by taking two of those, $x_1$ and $x_2$ and adding $x_1 + x_2 \cdot N$ (which is just bit concatenation if $N = 2^n$). That's a random number in the range $[0, N^2)$, assuming the original numbers were random and independent. If $N=2^n$, you can also drop bits off, i.e. take the value modulo some smaller power of two, without introducing biases.

To get a range that isn't a power of two in size, like a prime, you must use a modulus that's sufficiently small, or the low values will be more likely to show up. I.e. you must first overshoot the prime sufficiently, and then take the modulo. A factor of e.g. $2^{128}$ would be sufficient for 128-bit security. (Alternatively, you can use rejection sampling, but you wished to avoid that.)

If the original range isn't a power of two in size, which seems unlikely with a CSPRNG, you would likewise have to overshoot + modulo to get to a power of two range. Or directly to a prime range.

Now, if randInt isn't a CSPRNG, it may have biases that the above procedure compounds. But then, you shouldn't be using it for cryptography.


What's the difference between polylogarithmic and logarithmic? I can't imagine one that is not polylogarithmic
but logarithmic.

$O(\log N)$ satisfies both.

What about $O(\log^{3}N)$, $O(\log^{100}N)$, and  $O(\log^{10000}N)$ ?

Let's say $N=10^{10}$

Definitions:

An algorithm is said to run in

logarithmic time if $T(n) = O(log(n))$
polylogarithmic time if $T(n) = O(log(n)^k)$ (also written as $T(n) = O(log^k(n))$)

That means they are the same for $k=1$. Otherwise they are different and your other examples are all polylogarithmic.
I'm not sure how exactly to explain what the difference is but maybe a picture will help you:


Cryptography Pseudo Random Generator example question - proof For ii) G2 was proven to be a PRG, and it seems the solution for G5 uses G2.

Can someone try and explain to me the solution that I was given? I specially do not understand how to calculate the given probability:

Also, I understand that to proof something wrong you can just give a counterexample. However is there a more formal way of proving it?

I'll be reading the problem statement as

  $G$ is a PRG. Decide for each $i$ whether $G_i$ is always a PRG and prove the answer:
  (ii)   $G_2(s):=G(s_1\ldots s_{|s|-1})\mathbin\|s_{|s|}$
  (v)   $G_5(s):=G(s)\mathbin\|G(s+1)$ where $+$ denotes addition of binary numbers.

$G_2$ is a PRG. Intuitive argument: if the input of $G_2$ is uniform random bits, then its whole output is indistinguishable from random, because the rightmost bit is directly taken as the rightmost bit of the random input, and all the others bits because they are the output of a PRG seeded with the other input bits (which, critically, are independent). That can be formalized by turning an hypothetical distinguisher for $G_2$ into a distinguisher for $G$ (and showing that the output of $G_2$ is wider than its input, and whatever other technicality is required by the definition of PRG).

The solution quoted starts with

  For every $s$ whose last bit equals zero we have that $G_2(s)\mathbin\|G_2(s+1)=$
  $G(s_1\ldots s_{|s-1|})\mathbin\|0\mathbin\|G(s_1\ldots s_{|s-1|})\mathbin\|1$

but that comes without explanation about notation or intent, and with typos.

On notation: a bitstring $s$ of $|s|$ bits is assimilated to an element of $\Bbb Z_{2^{|s|}}$ per the big-endian convention, with bits numbered starting from 1 for the first/left/most significant:
$$s=\displaystyle\sum_{i=1}^{|s|}\,s_i\,2^{|s|-i}$$

On intent: It is computed what $G_5$ becomes under two hypothesis

it is restricted to input $s$ of $G_5$ that has its last bit equal to zero, meaning $s_{|s|}=0$ or equivalently $s$ is assimilated to an even integer, therefore $s$ and $s+1$ are the same bitstring excepts for bit $s_{|s|}$
and $G_5$ is built from a PRG of the form $G_2$, itself built from a PRG noted $G$ even though it's output is one bit narrower than $G$ of the problem statement in (v)

Replacing $G_5$ then $G_2$ by their definition, it comes

$$\begin{align}G_5(s)&=G_2(s)\mathbin\|G_2(s+1)\\
&=G(s_1\ldots s_{|s|-1})\mathbin\|0\mathbin\|G(s_1\ldots s_{|s|-1})\mathbin\|1 \end{align}$$

On typos: in that formula we twice have $|s|-1$ where the question's solution has $|s-1|$.

It should now be intuitively clear that $G_5$ is not necessarily a PRG. That formula shows that if $G_5$ is built from a PRG of the special form $G_2$, and its input has its last bit equal to zero, then the output of $G_5$ has two identical halves, except for their last bit ($0$ for the left half and $1$ for the right half). This characteristic allows to build a good distinguisher (assuming $|s|\ge2$ at the input of $G_5$). We'll prove this in detail.

A distinguisher is a deterministic algorithm $D$ that accepts as input a bistring as wide as the output of the would-be-PRG under test, and outputs 0 or 1. Its advantage $\operatorname{Adv}(D)$ is, by definition, how much in absolute value the probability that it outputs 1 differs in two situations:

the distinguisher receives as input the output of the would-be-PRG under test, itself receiving truly random input bits as input;
the distinguisher receives truly random bits as input.

As a formula: $\operatorname{Adv}(D)=\big|\,\Pr[D(G(s))=1]-\Pr[D(r)=1]\,\big|$

The left probability is computed over all bitstrings $s$ as wide as the input of the would-be-PRG under test $G$. The right probability is computed over all bitstrings $r$ as wide as the output of $G$. The $|\quad|$ notation stands for absolute value of a real, rather than length of a bitstring $s$ as in $|s|$.

The distinguisher $D$ proposed by the question's solution outputs 1 iff the two halves of its input are identical save for their right bit. When testing a generator $G_5$ of the special form considered, that always occurs when the rightmost bit of the generator's input is $0$, hence $\Pr[D(G_5(s))=1]\ge\frac12$; while if the input of $D$ is $2n$ bits and $n\ge1$, $\Pr[D(r)=1]=2^{-(n-1)}$ (because in the experiment computing that probability, it is compared two random independent bitstrings of $n-1$ bits). Therefore $\operatorname{Adv}(D)\ge\big|\,\frac12-2^{-(n-1)}\,\big|=\frac12\left(1-2^{-(n-2)}\right)$, which is a sizable advantage (at least $\frac14$ for $n\ge3$ ).

The proposed solution states at least $\frac12\left(1-2^{-(n-1)}\right)$, which is a better advantage. That's reachable, but requires computing the advantage exactly, or/and a better distinguisher, which is left as an exercise to the reader.

  I understand that to prove something wrong you can just give a counterexample. However is there a more formal way of proving it?

Counterexample is the simplest and most formal way of disproving something. In cryptography, its the best. There are exceptions in other domains.


Why is the output of a True Random Number Generator (TRNG) insecure after it has been compressed? I came across the following statement regarding true random number generators (TRNG):
A “P1 medium” [AIS31] true random number generator (TRNG) may not be directly used due to cryptographic reasons. Even smart cards or other advanced security solutions which possess high-quality physical sources of randomness usually rely at least on a compression of the TRNG output.
My question is, what is it about the compression of the TRNG output that makes it insecure? I have tried searching, but I cant find anything more information regarding this point wither in the spec the above quote came from, or anywhere I have looked online.
The only thing I can think of is that somehow the result of the compression algorithm can be predicted based on the input. However, if the input was generated randomly, I don't understand how that could matter.

I think you're misinterpreting the source. The source says the TRNGs "rely" on compression (a cryptographic hash would be the compression function, or possibly some simpler function to increase throughput).
The random data isn't insecure after compression, it's insecure before compression.
Why?
When you roll dice there's an equal probability of it being any one of the possible values, but let's say the dice aren't quite perfect - in nature you'll find things are almost always more like weighted dice than perfect RNGs.
If the output is biased it means it's less likely to produce certain outputs, breaking the security of an RNG - for a CSPRNG to be secure it must produce every output with equal probability, and a TRNG isn't exempt from that rule.
The solution is to take more random bytes than you plan to use, then use a compression function to merge them. It could be as simple as XORing every pair of bytes, or as thought-out as a cryptographic hash, but you need something to even out the probabilities.
That said, using a compression function like what's used to shrink your ZIP files would be an easy way to mess with the probabilities in a way you don't want, so that should be avoided, but that's not what they were referring to.


Getting inverse of a transposition key I'm new to security stuff and I have some questions about the keys of transposition cryptography.

If I'm given the encoding key to a transposition cipher, how do I get the decoding key for it? I tried googling but couldn't find any steps on the calculation for it. For example, on several crypto-related websites there are these nifty tools where, when I enter 4 3 1 6 2 5 I would get 3 5 2 1 6 4… but why and how?

The key is obtained by taking the encryption steps in reverse.
For example, let's encrypt the word "United" with that 4 3 1 6 2 5 key.
The first step is to take the 4th letter, a "t" and make it the first.
In the decryption, this first ciphertext letter must go to the 4th place again.
So the fourth step in the decryption, must be to look at what is in the first position - a "t" - and put that back in the fourth place again. Indeed we see in the decryption key that "1" is the value its fourth member.
By continuing these steps, you can derive the inverse key.

Here is a little code snippet that does the calculation.

static int[] inverse_key( int[] key )
{
    int[] inverse_key = new int[ key.length ];
    for ( int i = 0; i < key.length; i++ )
    {
        inverse_key[ key[ i ] - 1 ] = i + 1;
    }
    return inverse_key;
}

The "-1" and "+1" in the code are because arrays in most programming languages are 0-based; they do not relate to the actual algorithm.


ElGamal: Why is reusing the same $k$ not secure? I have a question on the encryption process of ElGamal:
$$
  Y = g ^ a \bmod p \\
  C = g ^ k \bmod p \quad\text{($k$ is chosen randomly)} \\
  D = m \cdot y ^ k \bmod p \\
  \text{Decryption:}\qquad m = C^{(p-1-a)}\cdot D\bmod p
$$

My professor told us we should know why it's bad to use the same values for the variables $a$ and $k$ more than once, but he didn't say why. I guess that if the same values for $a$ and $k$ are used several times, the attacker could calculate the unknown values if he is able to capture the traffic, but I don't know how.

How could an attacker proceed there?

In ElGamal encryption like you said for unknown $m_1$ and known $m_2$ we have:

$m_1: C_1=g^k\ mod\ p,\  D_1=m_1.g^{a.k}$

$m_2: C_2=g^k\ mod\ p,\  D_2=m_2.g^{a.k}$

$k$ is the same in both encryptions, by dividing $D_1$ and $D_2$ we have:

${D_1\over D_2}={m_1\over m_2} => D_1.m_2 = D_2.m_1$

$m_2$ , $D_1$ and $D_2$ and are known so now we can calculate $m_1$. This is how can attacker proceed and find unknown $m_1$.


How are blockchain keypair private keys hidden from miners, and how are they generated in the first place? I don't know how blockchain keypairs are programmatically generated, and equally important - how they are able to verify their keypair using a private key to a remote server - while keeping their private key entirely private.

How are blockchain keypairs generated, and private keys kept hidden by the remote server that is able to authenticate your account with some type of signing?

Is a public key a random hash and a private key the hash that parented the public key? If not, how? And how do they stay hidden the target network?

I am using encryption references in my IDE but am unsure how to utilize them effectively with a blockchain network.

Private Declare Sub MD5Init Lib "cryptdll" (Context As MD5_CTX)
Private Declare Sub MD5Update Lib "cryptdll" (Context As MD5_CTX, ByVal strInput As String, ByVal lLen As Long)
Private Declare Sub MD5Final Lib "cryptdll" (Context As MD5_CTX)

Private Function CalcMD5(sEncryptString As String) As String
    Dim strBuffer As String
    Dim myContext As MD5_CTX
    Dim result As String
    Dim lp As Long
    Dim MD5 As String

    strBuffer = sEncryptString

    MD5Init myContext
    MD5Update myContext, strBuffer, Len(strBuffer)
    MD5Final myContext

    result = StrConv(myContext.digest, vbUnicode)

    For lp = 1 To Len(result)
        CalcMD5 = CalcMD5 & Right("00" & Hex(Asc(Mid(result, lp, 1))), 2)
    Next

End Function

Yes, that's VB Classic. I am old, cut me a break.

I expected to understand keypairs, but I actually had no idea how they worked this entire time.

In blockchain systems, there are no clients and servers, just peer-to-peer nodes. They connect to each other using a TCP/IP connection, but are otherwise equal. Each node does not share its private or public keys with each other. These are kept locally in every node. The node can use their keys for two purposes, both of which are performed locally:

To sign a new transaction in order to make a payment. This signature is computed locally and then broadcast to the network. This does not reveal the private key, only the public key.
To check if a transaction it receives pertains to it. To do this, it checks to see if it matches its public key.

There is no further authentication taking place in the protocol. There are no user accounts, passwords, or any other form of "login".


RSA leak bits to factor N Suppose you randomly generate large primes p and q as in RSA, and then tell me N=pq but not p or q.

Then, you would like to actually let me factor N, except you should tell me as few bits of information as possible. Say p and q are 4096 bits, then how many bits do you need to tell me in order for me to factor N in feasible amount of time?

Note that you can arbitrarily design how these bits are derived, as long as there is a PPT algorithm to compute these bits and there is a PPT algorithm to use these bits to factor N.

I don't believe a lower bound has ever been proven for the "fewest" number of bits needed. Coppersmith showed, however, how given either the $n/4$ least or $n/4$ most significant bits of $p$ where $n$ is the size of the modulus $N=pq$, $N$ can be efficiently factored. Additionally, given the $n/4$ least significant bits of $d$, one can reconstruct $d$ (and therefore factor $N$), if $e<\sqrt{N}$. See Boneh's 20 year survey of attacks on RSA. See that paper and the reference within for the algorithms, etc.

Since then, the bounds for $e$ have been update somewhat, but still requires leaking the same number of bits. Also, random subsets of bits are sufficient to factor where $(1-\frac{H_r}{r})\log{N}$ bits of $p$ are known ($H_r$ is the r-th harmonic number).


Is it possible to derive related signature? For example, the message is a json: {name: john, age: 13}, and is sealed with signature.

Now, is it possible to derive a signature for the new message: john is less than 18 ?

I feel, to achieve that, the less than operator should be well-defined.

Any known research in this field?

Here is one idea about how to do a signature that specifies a specific range (and which makes it easy to enlarge the range):

We will assume a bounded range for the 'age', say, 0 to 150 ($max$), and we assume that $\text{H}$ is a preimage-resistant hash function, and $\text{H}^k$ denotes $\text{H}$ iterated $k$ times.

Then, we have a signature that has several parts:

The values $MinAge, MaxAge$
The value $max = \text{H}^{MaxAge}( r_1 )$
The value $min = \text{H}^{max-MinAge}( r_2 )$
The values $\text{H}^{max}( r_1 ), \text{H}^{max}( r_2 )$
The signature for $\text{H}^{max}( r_1 ), \text{H}^{max}{r_2}$, and the rest of the clause (name: John).

The above signature states that John's age is between MinAge and MaxAge; the original signer (who knows the age) can generate a signature with $MinAge = MaxAge = \text{John's real age}$

This signature can be verified by verifying that $\text{H}^{max - MaxAge}(max)$ matches the $\text{H}^{max}(r_1)$ value, that $\text{H}^{MinAge}(min)$ matches the $\text{H}^{max}(r_2)$ value, and that the signature verifies.

The range that this signature denotes can be enlarged; the MaxAge can be increased to $MaxAge'$ by updating the value $MaxAge$ and replacing the value $max$ by $\text{H}^{MaxAge' - MaxAge}(max)$.  Similarly, the MinAge can be decreased to $MinAge'$ updating the value $MinAge$ and replacing the value $min$ by $\text{H}^{MinAge - MinAge'}(min)$.  Note that the range cannot be decreased, because that would require generating a preimage of $\text{H}$, which we assume is infeasible.


What is the difference between a stream cipher and a one-time-pad? A (synchronous) stream cipher is an algorithm which maps some fixed-length key to an arbitrary-length key-stream (i.e. a sequence of bits): $C : \{0,1\}^k \to \{0,1\}^{\infty}$.

This key-stream is then XOR-ed with the plain text stream, giving the ciphertext stream.
For decrypting, the same key-stream (generated from the key at the receiver side) will be XOR-ed with the ciphertext stream, giving again the key stream.

A One-time pad is an algorithm which takes a key of large size (at least message size), and XORs its start with the plaintext to get the ciphertext. For decryption, we XOR the start of the key with the ciphertext to get back the plaintext.

These look quite similar – could one say that a stream-cipher is a (special way to create/use a) one-time pad, or that the one-time pad is a kind of stream cipher?

Are there any important differences between these two classes of algorithms?

There is no universally accepted definition of the expression "stream cipher"; but the one I most often encounter is the following: a stream cipher is a symmetric encryption algorithm which accepts as inputs arbitrary sequences of bits (or bytes) such that:

the length of the output is equal to the length of the input (no padding);
for any $n$ (possibly any $n$ which is a multiple of 8 if we restrict ourself to bytes), the first $n$ output bits depend only on the key and the first $n$ input bits, regardless of the value of the subsequent input bits.

In that sense, the One-Time Pad is a stream cipher. A block cipher used in CTR mode or CFB mode is also a stream cipher. Note that the latter is not of the kind "XOR with a stream generated from the key independently of the input data". The Wikipedia page you link to talks about "synchronous stream ciphers" and "self-synchronzing stream ciphers".

However, the ultimate security of the One-Time Pad comes from the key size: it is unbreakable because it assumes that the key is as long as the message and was generated by an unpredictable mechanism. If you generate the pad with a more conventional stream cipher, working over a small fixed-size key, then it is no longer a One-Time Pad, just a "regular" stream cipher. The expression "One-Time Pad" refers to, exclusively, the mythical scheme which uses truly random long keys. So while One-Time Pad is a stream ciphers, stream ciphers are not One-Time Pads.


There are technically two ways:

brute-forcing your way to a valid passphrase
having a valid passphrase and using that to decrypt the data

The use of 256-bit AES is cryptographically sound as far as I can tell as a (cryptography) layperson, so there are no other ways.

That said, for Ansible vaults the way I have used them, you have to enter a passphrase. While the actual key is probably still derived from that passphrase, brute-forcing a passphrase may be easier than brute-forcing a lengthy key.

As for the two ways one thing can be encrypted using the same passphrase, this may be owed to salt. For example the current date and time may be part of the encrypted data and the actual vault data gets extracted from that.


Terminology: What is the word describing a hash key, a crypto key, and a certificate? If I want to check the integrity of some piece of data, I can check that a cryptographic hash of the data corresponds to a known hash.

Alternatively I can also check a digital signature on the data and see that it corresponds to a known authority for the data.  I can use certificates or not for this.

I can also verify a MAC for the data using a secret key.

Lastly I can decrypt the data using an authenticating cipher mode using a secret key that is known only by me and the known authority for the data.

In these three cases I have some key or hash material.  What is the word that correctly describes the material I have?

In the case of a digital signature, it was signed with a private key, and you are verifying it with the private key's public key the bits you are authenticating against are the input (encrypted or not) and the digital signature, which is an asymmetrically encrypted cryptographic hash of the input.

For an authenticating cipher mode such as OCB or GCM, the key is simply the cipher key, it is the same used for both authentication and encryption. GCM internally generates a Hash key that is the internal key that performs authentication, and is unique to each cipher key. Other dual key modes exist, in this case the key is generally called the MAC key. Most authenticating cipher modes also require a nonce to be unique and processed as part of either authentication or encryption (or both). The bits you are authenticating against are the inputs (encrypted or not, or both) and the authentication tag.

When using a MAC only construction such as CMAC (OMAC) or HMAC, the key is once again generally called the MAC key, the bits you are authenticating against are the input (encrypted or not) and the message authentication code.

MAC keys, depending on the algorithm, may further be broken down into subkeys, or may be one of the generated subkeys of a larger master key.


ECDSA signature generation and verification latency I am performing some measurements of P256 ecdsa signature generation and verification latency and I was expecting that the signature verification will be faster than the signature generation, but is was not the case.
what makes the signature generation faster ? what is the most computationally expensive operation in signature verification ?

I was expecting that the signature verification will be faster than the signature generation

Because signature verification is faster in RSA?  Well, as you can see, RSA != ECDSA; the operations involved in both signing and verification are completely different.

what makes the signature generation faster ?

Because signature generation involves only one point multiplication (plus a modular inverse; rather cheaper, but not of insignificant cost), while signature verification involves two point multiplcations.
Of course, if you dig beneath the textbook definition, there are available optimizations for both sides:
On the signature side:

The point multiplication $k \times G$ (and I'll be using the notation on the Wikipedia page) uses a fixed (defined by the Elliptic Curve definition) point; there are a number of ways to speed this up considerably by precomputing takes based on $G$.

In addition, the expensive operations involved with the signing operation don't depend on the message being signed.  Hence, if your implementation has some idle time, it could pregenerate $k$ and $r$ values; when it gets the message, it can use those values to sign the message with quite low latency.

Also, a word of warning: if you were thinking of using the same $k, r$ values for signing multiple messages, don't go there - that will leak you private signing key.  You really need a fresh $k$ value selected randomly for each signed message.

On the verification side, the expensive operation is the computation $u_1 \times G + u_2 \times Q_A$

One could use the precomputed table to compute $u_1 \times G$ quickly; this means that the time to compute $u_2 \times Q_A$ is the bulk of the time (and if you know you'll be verifying with a specific public key $Q_A$ lots of times, you could precompute tables based on that - I haven't heard of anyone going to that effort, as you'd need to verify thousands of signatures from that one public key to make it worth while).

Alternatively, there is Shamir's trick, which is a computational method to compute $a \times P + b \times Q$ in not much more time than it takes to compute a single point multiplication.  However, you lose the speed up from a precomputed table.

However, neither of these ideas results in a verification method that is as fast as signing with precomputed tables.


Where is Web of Trust being used? I've been trying to find specific examples of where Web of Trust is being used today, but there seems to be little information about this. Are there any businesses using Web of Trust today? What do they use it for?

I have encountered PGP quite often in the business world, but never any use of the "Web of Trust". People just send each other their public keys over email and then check fingerprints over a phone call, or merely hope for the best. (I really encountered a customer who insisted on checking the fingerprint over a phone call, but that happened only once over the last 15 years.)

The "Web of Trust" mechanism does not map well to the business world. Arguably, it does not map well to the world in general. The main problem with the Web of Trust is that it conflates two concepts into one property: the identity, and the ability to authenticate.

For instance, suppose that Alice sign's Bob's key, then Bob sign's Charlie's key. The "Web of Trust" posits that if I already know Alice's public key, then I can gain some confidence in Bob's and Charlie's public keys. However, this is not really true. I know Alice and I know that she would not sign Bob's key unless she has thoroughly verified that she was talking to the real Bob, and signing a public key that is really under the control of Bob. However, I do not know Bob. For all I know, Bob could be very gullible, or prone to sign keys late at night after too many whiskies. Thus, I cannot really trust that the apparent Charlie's key really belongs to Charlie. In other words, Alice asserts that a given key belongs to Bob, but not that Bob is a reliable person who will apply all proper identity checks before signing other keys.

In the PKI world (X.509 certificates), things are hierarchical, and when a CA signs a key (i.e. issues a certificate), it can make an assertion on the reliability of the target entity: a CA may issue a CA certificate to a sub-CA (the Basic Constraints extension in that certificate will contain the cA flag set to TRUE), or an end-entity certificate (the cA flag is FALSE). In the former case, the CA delegates its power, while in the latter it does not. This is the main difference between X.509 PKI and the PGP Web of Trust. PGP lacks the distinction that is expressed by the cA flag in X.509 certificates. A consequence is that the PGP Web of Trust is rather useless, and this may go a long way towards explaining why nobody uses it.


Name of specific cryptography property of XOR Given

$C$ = M $\oplus$ K1 $\oplus$ K2 $\oplus$ K3

One can decrypt $C$ in any sequence, like:

$C$ $\oplus$ K1 = M  $\oplus$ K2 $\oplus$ K3

$C$ $\oplus$ K1 $\oplus$ K3 = M  $\oplus$ K2

$C$ $\oplus$ K1 $\oplus$ K3 $\oplus$ K2  = M

Or:

$C$ $\oplus$ K2 = M  $\oplus$ K1 $\oplus$ K3

$C$ $\oplus$ K1 $\oplus$ K3 = M  $\oplus$ K2

$C$ $\oplus$ K1 $\oplus$ K3 $\oplus$ K2  = M

Notice that on the 1st decryption we started with XORing with K1, and on the 2nd we started with K2.

If we were to use AES, as far as I understand, you would have to decrypt in the same order as you have encrypted.
Given:

$C$ = $AES(AES(AES(M,K1),K2),K3)$

If you were to decrypt in the following manner for instance you would not get M:

$AES^{-1}((AES^{-1}(AES^{-1}(C,K2), K1)),K3) \neq M$

On the other hand:

$AES^{-1}((AES^{-1}(AES^{-1}(C,K3), K2)),K1) = M$.

My question:

1) What is the name of the property which allows a cypher to be decrypted in any order after encrytpion (like in XOR).

2) Are there common cypher (not including XOR) which contain this property (assuming K1,K2,K3 are known to different actors and cannot be shared).

XOR is a linear operation which is inverse of itself too.

k1 $\oplus$ k1 = 0

It is also commutative.

(k1 $\oplus$ k2) $\oplus$ k3 = k1 $\oplus$ (k2 $\oplus$ k3)

Thats why you can decrypt the way you have shown in question. Where as AES is not a linear operation and it is not inverse of itself. Applying AES encryption twice with same key will not produce the orignal Text.

AES(K1, AES(K1, M)) $\neq$ M

AES is also not Commutative

AES(K1, AES(K2, M)) $\neq$ AES(K2, AES(K1, M))

1) Simple XOR operation is not a cipher until its One Time PAD. Encrypting multiple texts with same keys using XOR will be a total break. Its use of the XOR operation which allows to decrypt the way you have shown because XOR is commutative, associative, and its own inverse.

2) The Block Encryption algorithms will not exhibit properties like commutative, associative, and its own inverse. However Cipher can be used to generate a random key stream (Like Stream Cipher) in CTR mode which is then XOR with the plaintext to make ciphertext. So in the End its commutative and associative operation.


Ciphertext and tag size and IV transmission with AES in GCM mode I am completely new to using AES in GCM mode of operation, and I have not a very large background in cryptography as well. I have been playing with OpenSSL trying to encrypt and decrypt some messages. From my simple experiments rise the following questions:

First of all, I noticed that the size of the output is exactly the same as the input. I am confused. As far as I knew, AES works in blocks of 16 bytes. I am used to CBC mode, where the message needed padding. Does this mean that GCM can work with any size of the input, without having to pad and unpad things?
I read that the IV can be of any size, and that it is sufficient for it to be non-repeating. Does this mean, for example, that I can use a 4 bytes iv with a progressive counter? Is that just as easy as that or are there security issues with short and predictable IVs?
Since I need to generate a new IV for every message, how am I supposed to transfer it? As far as my understanding goes, the secrecy of IVs is not fundamental... does this mean that I can just send each IV in plaintext along with its message? If not, what should I do to let the other endpoint know about my iv?
Are MAC tags always 16 bytes long?

I hope these questions are not exceedingly dumb. They should definitely be simple and quick to answer.

I'll answer in order:

Output size = input size That's correct, GCM uses CTR internally. It encrypts a counter value for each block, but it only uses as many bits as required from the last block. CTR turns the block cipher into a stream cipher. Note that this doesn't include any additional authenticated data (AAD) that needs to be send, the optional inclusion of the (otherwise required) IV nor size of the required authentication tag.

IV of any size For GCM a 12 byte IV is strongly suggested as other IV lengths will require additional calculations. In principle any IV size can be used as long as the IV doesn't ever repeat. NIST however suggests that only an IV size of 12 bytes needs to be supported by implementations.

How to transport IV Yes, generally the IV is prefixed to the ciphertext or calculated using some kind of nonce on both sides. The size of the IV should be defined by the protocol. If it is possible to synchronize a nonce of 12 bytes then the IV doesn't need to be included with the ciphertext.

Size of authentication tags The calculated tag will always be 16 bytes long, but the leftmost bytes can be used. GCM is defined for the tag sizes 128, 120, 112, 104, or 96, 64 and 32. Note that the security of GCM is strongly dependent on the tag size. You should try and use a tag size of 64 bits at the very minimum, but in general a tag size of the full 128 bits should be preferred.

NIST Special Publication 800-38D (page 8) defining GCM has the following on the tag sizes:

The bit length of the tag, denoted $t$, is a security parameter, as discussed in Appendix B.  In general, $t$ may be any one of the following five values: 128, 120, 112, 104, or 96.  For certain applications, $t$ may be 64 or 32; guidance for the use of these two tag lengths, including requirements on the length of the input data and the lifetime of the key in these cases, is given in Appendix C.


Converting common reference string to common random string I listened to a talk on NIZK a while ago and vaguely remembered the speaker mentioned something like - A scheme that is statistically sound and computationally ZK in common reference string model could become computationally sound and statistically ZK in common random string model.
I couldn’t remember the exact talk and speaker, but I’m wondering whether this kind of duality is common in CRS constructions, and if so, how do we convert a scheme in common reference string model into one in common random string model?
Thanks!

There is no generic conversion, but it is a standard property of dual-mode NIZKs. Here, the CRS comes in two indistinguishable modes, where one is structured, but the other is actually a truly random string. Typically, in group-based construction, the random CRS will be a tuple of random group elements, while the structured CRS will be a DDH tuple - both will then be indistinguishable under the DDH assumption.
At a very high level, the reference string will be used as a parameter of some commitment scheme in which you put the witness in the NIZK. Then, using some appropriate construction of commitments, the commitment can be perfectly hiding as long as the CRS is random, but becomes perfectly binding as soon as the CRS is structured. Think for example about Groth-Sahai-style dual-mode commitments, which have a similar property.
Some recent examples of NIZKs with this property include this work.