Galois fields in cryptography I don't really understand Galois fields, but I've noticed they're used a lot in crypto. I tried to read into them, but quickly got lost in the mess of heiroglyphs and alien terms. I understand they're sets of the form $GF(p^n)$ for $n\geq1$ where $p$ is prime and $n$ is an integer. From what I can tell, they're defined as the following:

$GF(p^n) = [f(0) \bmod p, f(1) \bmod p, \dotsc, f(p^n-1) \bmod p,  f(p^n) \bmod p]$

for $f(x) = \sum_{i=0}^{n} \space x^ik_i$, i.e. an $n$-order polynomial with constants $K$.

I've seen mention that these fields are bijective, such that for an input set $A$ there is an output set $B$ containing the same values as $A$, but in a different order.

Is this correct? Does this have applications for creating s-boxes?

Update:
Thanks for the answers so far. I now understand that $GF(p^n)$ is an array of size-$n$ vectors, each element of which is computed as the result of some polynomial mod $p$, but I'm still not clear on the rest of it. I mostly understand how vector manipulation can be done on such a field, but I'm still non the wiser as to how I would use such a finite field, let alone impliment them in code. I don't really understand what $GF(p^n)$ looks like in terms of construction, which I guess is what I'm really looking for. If it's an array of vectors, each element of which is computed by some polynomial, how is the input to that polynomial decided? Is $GF$ a function, into which you provide such a value? Is the input value an integer, a vector, etc? If so, what's the meaning of the input value? How does the index of the vector in the set factor into the computation of its values?

For example:

$GF(p^n)[i] = \begin{bmatrix} v_0\\v_1\\v_2\\...\\v_{n-1} \end{bmatrix}$

Where $i$ is some index into the field, how are the vector elements $V$ computed? What inputs are provided?

The $GF$ in $GF(p^n)$ is not a function — it just stands for "Galois field (of $p^n$ elements)".

As for what a Galois field is, it's a finite set of things (which we might represent e.g. with the numbers from $0$ to $p^n-1$), with some mathematical operations (specifically, addition and multiplication, and their inverses) defined on them that let us calculate with these things as if they were ordinary numbers, but so that the results of the calculations always stay inside the finite set.

Specifically, we require the operations defined on the elements of this finite set to satisfy the field axioms, which include the usual associativity, commutativity and distributivity rules you probably learned in high school algebra class.  In particular, we also require every element $a$ to have an additive inverse $-a$ and (if $a \ne 0$) a multiplicative inverse $1/a$, such that $a + (-a) = 0$ and $a \times (1/a) = 1$.  Thus, as long as you just stick to algebraic manipulations using these rules, the Galois fields all look exactly like the field of real numbers you're familiar with.

To learn how to do arithmetic (i.e. actual calculations with actual numbers) in Galois fields, it's probably easiest (particularly if you're already familiar with modular arithmetic) to start with the prime Galois fields $GF(p)$.  Arithmetic in these fields is simply ordinary addition and multiplication of integers modulo some prime $p$.  For example, in $GF(3)$, there are three numbers ($0$, $1$ and $2$) with the following addition and multiplication rules (and their commutative variants):

$$\begin{aligned}
0 + 0 &= 0 & 1 + 1 &= 2 & 0 \times 0 &= 0 & 1 \times 1 &= 1 \\
0 + 1 &= 1 & 1 + 2 &= 0 & 0 \times 1 &= 0 & 1 \times 2 &= 2 \\
0 + 2 &= 2 & 2 + 2 &= 1 & 0 \times 2 &= 0 & 2 \times 2 &= 1 \\
\end{aligned}$$

The only unusual rules here are $1 + 2 = 0$, $2 + 2 = 1$ and $2 \times 2 = 1$; those are the cases where, in normal arithmetic, the result would've been equal to or greater than $3$, so it's "wrapped around" by subtracting $3$.  From these rules, we can also determine the inverses.  It turns out that $-0 = 0$, $-1 = 2$ and $-2 = 1$ (since $1 + 2 = 0$) and $1/1 = 1$ and $1/2 = 2$ (since $2 \times 2 = 1$), so they indeed do exist and belong to the field.  (I'll leave verifying that the inverses are all unique, and that these rules indeed also satisfy all the other field axioms, as an exercise.)

Why do we require $p$ to be prime, then?  Well, it turns out that if a number $m$ is not prime, then some numbers won't have multiplicative inverses modulo $m$:  for example, there is no integer $a$ such that $2 \times a = 1 \pmod 4$.  Thus, the integers modulo $m$ don't actually form a field (but only a ring) unless $m$ is prime.

However, if $m$ is a prime power — i.e. a number of the form $m = p^n$, for some prime $p$ and some positive integer $n$ — then we can still save things by changing the rules on how addition and multiplication work.  This is where all that stuff about the vectors and polynomials comes in.  However, what you should keep in mind is that they don't really represent any added complexity, just alternative ways of looking at things.  Fundamentally, we're still dealing with a set of $p^n$ numbers and some arithmetic operations defined on them — it just turns out that, for example, the multiplication rule we'll need to use is pretty easy to describe if we identify each number in the field with a polynomial, at least if you still remember the rules for adding and multiplying (and dividing) polynomials that you may have also learned in high school.

So, let's start with vectors and addition.  Given a number $a \in \{0, \dotsc, p^n-1\}$, we can represent it in a natural way with $n$ base-$p$ digits $a_0, \dotsc, a_{n-1}$, such that $$a = a_0 + a_1 p + a_2 p^2 + \dotsb + a_{n-1} p^{n-1}.$$

This is exactly how you'd represent a binary number modulo $2^n$ as a string of $n$ bits.  We could also call the string a vector, since that's basically what a vector is: a finite-length sequence of numbers.

Now, when you normally add numbers together digit by digit, you need to keep track of carries.  On the other hand, when you add two vectors together, it's simpler: you just add up the corresponding numbers in each vector separately.  Now, it just turns out that the addition rule we'll need to use, to make the field axioms work in a field with $p^n$ elements, is exactly this "carryless addition".  For example, in $GF(4)$ (which we often write as $GF(2^2)$ to emphasize that $4 = 2^2$ is indeed a prime power) the addition rules look like this:

$$\begin{aligned}
0 + 0 &= 0 & 0 + 2 &= 2 & 1 + 1 &= 0 & 1 + 3 &= 2 & 2 + 3 &= 1 \\
0 + 1 &= 1 & 0 + 3 &= 3 & 1 + 2 &= 3 & 2 + 2 &= 0 & 3 + 3 &= 0 \\
\end{aligned}$$

They look a lot more logical if you write them out in binary:

$$\begin{aligned}
00 + 00 &= 00 & 00 + 10 &= 10 & 01 + 01 &= 00 & 01 + 11 &= 10 & 10 + 11 &= 01 \\
00 + 01 &= 01 & 00 + 11 &= 11 & 01 + 10 &= 11 & 10 + 10 &= 00 & 11 + 11 &= 00 \\
\end{aligned}$$

Here you can see that we're just adding up the digits modulo $2$ and ignoring any carries.  You might also recognize this "addition" rule as the same operation as bitwise XOR.  This is not unique to $GF(4)$; the elements of $GF(2^n)$ for any $n$ can be represented as $n$-bit bitstrings, and their addition as bitwise XOR.

So, now we know how to add numbers in $GF(p^n)$.  What about multiplication, then?  Well, this is where the polynomials come in.  You see, one way to describe the multiplication rule is to imagine that the digits $a_0, \dotsc, a_{n-1}$ of the number $a$ are the coefficients of a polynomial $$a[x] = a_0 + a_1 x + a_2 x^2 + \dotsb + a_{n-1} x^{n-1}$$ with the unknown $x$.  (Here, the variable $x$ is purely a formal placeholder; we'll never assign it a value, so you'll never have to worry about "what's $x$?".  It's just there so that we can use the high school algebra rules for manipulating polynomials in $x$.)

Then, to multiply two numbers $a$ and $b$, we just take their respective polynomials $a[x]$ and $b[x]$, multiply them together using the high school algebra rules (doing all the internal arithmetic modulo $p$), and take the coefficients of the result.  This is all pretty simple: remember that polynomial multiplication is also pretty straightforward, being just like normal digit-by-digit multiplication except that, again, there are no carries.

But wait!  Won't the multiplication sometimes give me terms of order $x^n$ or higher?  If I include them in the digit string, wouldn't that result in a number larger than $p^n-1$?

Well, yes.  That's why there's another step: after the multiplication, we need to reduce the result modulo a suitable polynomial (specifically, an irreducible monic polynomial of order $n$).  That is to say, we take the result of the multiplication and divide it by this reducing polynomial (which we can again do with high school polynomial long division), again remembering to do all arithmetic on the coefficients modulo $p$, and keep the remainder (which will be of order $x^{n-1}$ or less).  Of course, in practice it's usually more efficient to do the reduction during the multiplication, so that you don't need to store lengthy intermediate results.

OK, so where does that reducing polynomial come from?  Well, it turns out that we have some latitude in choosing it, since there are usually several polynomials that will work.  Each of them will give a different multiplication rule, although all the fields so constructed (and, more generally, all finite fields with $p^n$ elements) are isomorphic, in the sense that, for any two Galois fields $A$ and $B$ of $p^n$ elements, there's an invertible function $f: A \to B$ mapping one field to the other so that $f(a + b) = f(a) + f(b)$ and $f(a \times_A b) = f(a) \times_B f(b)$, where $\times_A$ and $\times_B$ denote the multiplication operators of the two fields.  Thus, when we only care about the general algebraic properties of the field, and not about the specific representation of the numbers, it's common to speak of "the" Galois field of order $p^n$, even though it might have multiple representations.

If you're asked to calculate something in a specific Galois field, the reducing polynomial will normally be given for you.  For example, if you're writing an AES implementation, it uses $GF(2^8)$ with the reducing polynomial $x^8 + x^4 + x^3 + x + 1$ (where, since $p=2$, all coefficients are either $0$ or $1$).

If you get to choose your own representation, and thus your own reducing polynomial, you should generally try to pick something that makes the calculations easy, subject to the irreducibility constraints stated above.  Often this means picking something with as few non-zero coefficients as possible, and with all those coefficients occurring on low-order terms (except for the $x^n$ term, which must have a coefficient of $1$ for the polynomial to be monic and of order $n$, of course).

I could go into more detail on how to implement multiplication in binary Galois fields $GF(2^n)$, since what I've written above is still on a rather abstract level, and since — especially to someone coming from a programming background — the theory is often more complicated than the actual code (or at least looks that way).  However, to be honest, I'm more familiar with the theoretical side of things myself, and in any case this answer is already more than long enough.  Wikipedia does have a nice article on finite field arithmetic that you could start with, though.

Oh, and what about Galois fields that are not of order $p^n$ for some prime $p$ and positive integer $n$?  Well, it turns out that there aren't any — you just can't satisfy the field axioms if the number of elements has two distinct prime factors.  So, alas, there's no such thing as $GF(6)$ or $GF(10)$.


What is a simple 8-bit cryptographic hash function that I can use in a quantum simulation of Grover's algorithm? I'm taking a quantum computing course in which, for our final project, we must create a proof-of-concept implementation of Grover Search for finding hash collisions up to a difficulty (similar to blockchain).

I need a (relatively) simple hash function. As this will be running on a quantum simulator, I'm limited in the number of qubits which I can simulate. Ideally, the hash function should output 8-bits for arbitrarily sized input, should not be crackable (trivially, for example by hand), and should be relatively fast as the hash function (although classical) will be implemented with quantum logic gates.

I was considering an 8-bit version of SHA-1, however I'm not sure how adaptable SHA-1 would be in this situation.

Your requirement that it not be trivially crackable is already violated by the premise of an 8-bit hash function: for a uniform random 8-bit function it takes an expected 128 trials to find a preimage, and the time for an expected ${\sim}256/n^3$ trials to find the first preimage among $n$ targets if parallelized $n^2$ ways.  But maybe you meant there are no better-than-generic attacks on it.  (Similarly, it takes an expected ~20 trials to find a collision, although it's not clear that collisions are relevant to your application.)

You could use a Keccak sponge with 1-bit words for a total 25-bit state, 12 rounds, and an 8-bit capacity.  I don't know 25-bit Keccak admits better-than-generic attacks—I wouldn't be surprised if it did—but it is structurally the same as the Keccak permutation used in SHA-3, with 64-bit words, 1600-bit state, 24 rounds, and either $4\lambda$- or $2\lambda$-bit capacity (respectively, for the fixed-size hashes like SHA3-256, or for the extendable-output functions like SHAKE128) for $\lambda$-bit collision resistance and $2\lambda$-bit preimage resistance.

Right now, the best collision attacks on 1600-bit Keccak[1][2] seem to be limited to 6 rounds, which justified the use of 12 rounds for KangarooTwelve.  There are newer attacks on other aspects of Keccak, but 12 seems like a reasonable margin—and it's not clear that those attacks would be cheaper than Grover.  If all you want is preimage resistance, a $\lambda$-bit capacity should suffice for $\lambda$-bit preimage resistance.

One nice thing about a permutation-based sponge like Keccak is that the fixed permutation is, well, a permutation, so it will require no ancillary qubits to implement; the only need for ancillary qubits will arise from xoring the message into the state to hash it.


using elliptic curve point multiplication as a key stretching method My friend came up with the following idea: assuming we agreed on curve parameters, use the following algorithm for key stretching/derivation from user-entered password.

Pad the ascii representation of the password to n bits or use any simple hash function, e.g. MD5 to allow passwords of arbitrary length
Compute the resulting key as a multiplication of the curve generator point by the number we got at step #1.

In other words, we consider the user-entered password to be the private key of ECDSA and use the public key derivation algorithm as a key stretching function.

Now this looks pretty simple and effective (my CPU only manages to do less than a couple thousand multiplications per second and it seems there is no way to get significant speedups using GPUs). Is this algorithm actually used anywhere? If not, what are some obvious flaws that I can point to for my friend and make fun of him?

EDIT: Thanks for answers! Can't upvote yet due to low rep. The idea was to use this method as a slow hash function for password hashing (as a replacement for bcrypt for example). IMPROVED VERSION: Assuming we use SHA256 in the first step to hash the entered password, then multiply with the generator point in the p256 curve and use the X coordinate of the resulting point as a 256-bit hash of the password. Is this hash good enough for this purpose?

This is a purely theoretical question of course, we are not going to actually use any homebrew cryptography in our app!

If I understand correctly is to hash your password $pw$ into a point using either $P=Pad(pw)\cdot P_0$ or $P=MD5(pw)\cdot P_0$ and then use $P$ for cryptographic purpose. The exact security of this proposal depends on what you want to do with $P$ exactly. But in some case, this is not secure. Typically, this mechanism is not a good way to hash a password (even if you add salt by varying $P_0$).

Indeed, in this application, you would know $P$ and $P_0$ and recovering the password $pw$ could be done using a discrete logarithm computation. Since $pw$ is generally quite short, $Pad(pw)$ belongs to a short interval of length $N$ (where $N$ is the number of possible padded passwords). In this case, using Pollard's lambda (i.e. The kangaroo method) allows to compute the discrete logarithm at a cost of $\sqrt{N}$. With $MD5$, $N$ is $2^{128}$ which would give a cost of $2^{64}$ to compute the logarithm, probably not enough.

On the other hand, if your application keeps $P$ secret, this is probably not going to apply. So could you tell more about the exact use of $P$ ?


What is the security risk if an encryption key is not random? Ok, I just jumped into crypto and now struggling with some points…

I read lots of resources, most of them mention how important the strength of the encryption key is. However, I could not find much info about that.

What if the encryption key is not generated randomly and somehow is fixed or easy to be guessed? And what if the key contains lots of zeros in it? What could be the security risks?

A usual approach to security analysis is that the attacker knows everything about the system except the secret key, and often he has access to an "oracle" to produce related data. This is also known as Kerckhoffs's principle. For example in a chosen plaintext attack he can choose some messages, hand them to the oracle which encrypts them under the secret key and gets back the ciphertexts.

Back to your question: If the key is chosen poorly (and if there is some structure, the attacker knows it), it might be possible just to brute force it and try all possible keys. Today's computers can deal with complexities of testing $\approx 2^{64}$, therefore DES is no longer safe to use. If you know the first 100 bit of a 128 bit key are all 0 bits, then you probably are even able to find the key on any modern computer larger than a mobile phone.


What is the mathematical property stating that it is hard to find a collision in the AES algorithm? Finding a collision in the AES algorithm is (apparently) hard. Why ?

What is the mathematical property stating that there is a negligible probability to find a collision by taking two random plaintexts and setting the key ?

Here I mean collisions like : $\operatorname{AES}_{K}(P_1)=\operatorname{AES}_{K}(P_2)$, with $P_1$ and $P_2$ being two random plaintexts and $K$ a 128 bits long fixed key.

In other terms, as AES 128 is mapping a 128 bits input to a 128 bits output, how can we be sure that all the outputs will be reached, for a given key ? What is the mathematical property in the design of AES making it a function "nearly" (fully ?) bijective ?

And, for AES-256, if we now set the plaintext and vary the keys (giving a function with input set size equal to $2^{256}$ and output set size equal to $2^{128}$), why is it difficult to find a collision ?

To clarify: for the last question only, I mean collisions like $\operatorname{AES}_{K1}(P_1)=\operatorname{AES}_{K_2}(P_1)$, with $P_1$ being a plaintext and $K_1, K_2$ two 256 bits long keys.

As mentioned in several of the other answers, AES is a family of permutations indexed by the key. Hence there cannot exist any collision of the form $AES_k(x) = AES_k(x')$ for $x\neq x'$.

On the other hand, if we look at the function $f_x: k \rightarrow AES_k(x)$ we should ideally have a random function. Finding a non-random property of this function would be a major step in cryptanalysis of AES. So, with this reasoning the standard reasoning for random functions applies. For AES this means we have a function that maps 256 (192, or 128) bit strings to 128 bit strings. By the birthday paradox we know that an adversary that evaluates $f_x$ $q$ times has a success probability of $\mathcal{O}(\frac{q^2}{2^{128}})$ and that is also the best one can do without a huge improvement in the cryptanalysis of AES. However, this means one can find collisions of that function in about $2^{64}$ AES evaluations. This is already doable: the bitcoin network currently does about $2^{70}$ SHA2 computations per day!  And AES is faster than SHA2.


What are the negative consequences for choosing 8 S-boxes for DES vs 1 S-box for AES? DES has 8 different S-boxes, and AES has only 1.

What are the negative consequences of such choices?

Implementation complexity in software and constrained hardware.

In Serpent, each round uses the same S-box, even though 8 s-boxes are used. This makes it easier to bitsplice the cipher, or process each 4-bit s-box in parallel.

The minimum gate count for a DES implementation is 2300 gates. For Present it is 1075 gates.

Software and constrained hardware implementations benefit from a cipher that can be easily serialized.

Hash Functions and RFID Tags: Mind the Gap


Privately Sum Values without Dealers, MPC Suppose $n$ actors each hold a plaintext $p_i$. We wish to find $\sum p_i$, without leaking any information about individual $p_i$. Any actor (or any link in the network) could be controlled by an active adversary. The calculations should finish in seconds or minutes for $n = 20$.

The usual approach to this problem is use homomorphic encryption, but homomorphic encryption requires keys to be distributed among the actors. The two approaches to key generation that I found in the literature aren't useful here: there is no trusted party to act as a dealer, and secure multiparty computation is too slow.

Here's the best I can do using my own imagination. I'm curious if there's something in the literature I missed, or if somebody else's imagination is more fertile.

Choose $m > \sum p_i$
Each actor chooses a random $r_i < m$
The actors seed their random number generators using a hard-coded value, and all compute the same random ordering of the actors.
Actor $i$ receives some $e_i$ from the previous actor, and sends $e_{i+1} = p_i + r_i + e_i \mod m \;\;$ to the next actor. $\;\; e_0 = 0 \qquad e_n = \sum p_i + \sum r_i \mod m$
All the actors compute the same, new random ordering of the actors.
Actor $i$ receives some $d_i$ from the previous actor, and sends $\;\;d_{i+1} = d_i - r_i \mod m \;\;$ to the next actor. $\;\; d_0 = e_n \qquad e_n = \sum p_i$.

This is quite fast, requiring $2*n$ network transmissions and negligible computation. The security is good but not ideal. Most seriously, someone eavesdropping on your network connection can learn your $p_i$. Also, if your neighbors in the encryption and decryption processes share data, they can determine your $p_i$. If the adversary controls an actor with probability $p$, your data is leaked with probability $p^4$. An algorithm "better" than this one would maintain the secrecy of an individual $p_i$ even if the network is controlled by the adversary.

I believe the basic idea is the following:

Choose $m$ so that $\: \sum p_i \:$ can be efficiently recovered from $\; \operatorname{mod}\left(\sum p_i\hspace{.03 in},m\right) \:\:$.

Each party $i$ chooses $\:n\hspace{-0.03 in}-\hspace{-0.04 in}1\:$ elements $\:q_{i,\hspace{.03 in}j}\:$ of $\:\{0,\hspace{-0.04 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...,m\hspace{-0.03 in}-\hspace{-0.04 in}2\hspace{.02 in},m\hspace{-0.03 in}-\hspace{-0.04 in}1\hspace{-0.02 in}\}$

independently and almost uniformly, where $j$ ranges over the other parties,
and then sends each to the corresponding other party over a confidential channel.

Each party $i$ lets $S$ be the set of other parties, and then lets $q_{i,i}$ be $\;\; \operatorname{mod}\hspace{.02 in}\left(\left(\hspace{.02 in}p_i-\left(\hspace{.02 in}\displaystyle\sum_{j\hspace{.02 in}\in \hspace{.02 in}S} q_{i,\hspace{.03 in}j}\right)\right),\hspace{.03 in}m\right) \;\;\;$.

Each party $i$ lets $q_i$ be $\; \operatorname{mod}\hspace{.02 in}\left(\left(\displaystyle\sum_j q_{j,i}\right),\hspace{.03 in}m\right) \:\:$,$\:\:$ and the broadcasts $\:q_i\:$.

Now, $\;\; \operatorname{mod}\left(\sum p_i\hspace{.03 in},m\right) \: = \: \operatorname{mod}\left(\sum q_i\hspace{.03 in},m\right) \;\;\;$.

The simplest thing to address is the use of the confidential channel. $\:$ First, if there is any way to

do this against a pure eavesdropper, then key agreement is possible, by letting Alice run one party

with a random $p_i$ from a large range, letting Bob run the others, one of which also has a random

$p_i$ from a large range and the others of which have a $p_i$ of zero, and letting the key be least

significant bits of Alice's $p_i$. $\:$ If secure erasure is allowed, then secure key agreement means

that one can lift from authentic channels to confidential channels. $\:$ If secure erasure is not

allowed, then non-committing key agreement would still suffice for that. $\:$ On the other hand,

if authentic channels are not available, then one must proceed as described in this paper.

The more complicated thing to address is the issue of parties lying about their $\:q_i\:$.

For each ordered pair of parties $\:\langle i\hspace{.01 in},j\hspace{.02 in}\rangle\:$,$\:$ there need to be equivocal commitments to $q_{i,\hspace{.03 in}j}$ such

that no secrets are needed to verify openings and the commitments and the committed values are computationally independent of the other $q_{i,\hspace{.03 in}j}$ values. $\;\;\;$ (For the first part, when $i$ and $j$ are different, just have either of them make the commitments and then send the decommit information to the other

of them over a confidential channel. $\:$ The computational independence part is easier than it would normally be because all relevant parties are in communication with each other.) $\:$ Finally, after the parties broadcast the $q_i$ values, the parties must give simultaneous computational zero knowledge arguments of knowledge of how to decommit the $q_{j,i}$ values in a way that is compatible with $q_i$.


XTEA: patterns in plain text I'm using XTEA to encrypt passwords that I store in a database. (I need to be able to decrypt these passwords later to log in on another system.) But now I have noticed something: if I decrypt a password using a different key I can still see some of the patterns in the plain text. I am not worried about an attack against the XTEA encryption, I am worried about an attack against the other systems that use the encrypted passwords.

For example:

Password A = "111222111"
Password B = "222111222"

I encrypt these with some key, then decrypt them with another key. The output is something like:

A: qqqwwwqqq
B: wwwqqqwww

(Using q and w for readability, it's actually 2 illegible characters.) As you can see, for weak passwords this can reveal a lot of information that can make brute force or dictionary attacks against these passwords a lot easier:

The length of the password.
Patterns of the same character in a password.
Patterns in different passwords.

The assumptions here are:

The attacker has access to several encrypted passwords and salts.
The attacker has no access to the encryption key and this key is sufficiently strong.
The attacker is only interested in the plain-text. Getting the encryption key can be a means but is not an end.
The attacker has decompiled the code, obfuscation won't do any good.
The users are idiots and the passwords are as weak and similar as the above examples.

My questions are :

Can this be considered a weakness in my program? Or can I wash my hands by telling the users to use stronger passwords?
Is this normal behaviour for XTEA, or is there something wrong with the implementation I am using?
Are there other encryption methods that are better suited for this?

XTEA is a block cipher. It requires a block cipher mode of operation to work. Together with a block cipher mode of operation you can generate something that is secure. For this you require at least an IV, as you may otherwise encrypt identical passwords (for different users) to identical values. Or, if you encrypt each character separately, the same character value to the same ciphertext.

A block cipher itself is a PRP, a pseudo random permutation. Given a key, it will always transform one plaintext to the ciphertext associated with it. If you use XTEA in e.g. Block TEA this will not be different; you will always get the same ciphertext.

You can do the following things:

define a character set for your password and possible input values;
encode the password using the said character set
pad the password to a certain maximum length, say 64 bytes to allow for pass phrases (either store the length or use an invalid character such as 00 hex)
generate a 8 byte IV (for a 64 bit block cipher such as XTEA; IV requirements may depend on mode of operation and block size)
encrypt the encoded & padded password using the IV and key
store IV | ciphertext

This should be secure, as long as the mode of operation you choose is secure. You may want to use authenticated encryption (e.g. GCM) for this, but that's not really a requirement.

Usually it is better not to store passwords at all, but this seems a requirement in your case. You may want to check if there are secure password faults available from the runtime environment. If there is no pressing argument for using XTEA, you should be using AES.


Practical consequences of using functional encryption for software obfuscation I came across this article, which describes a method, developed by UCLA CS professor Amit Sahai et al, for using functional encryption in order to achieve software obfuscation. The paper that the article refers to is available here. Has anyone digested the paper and have more information to share? Are the results as ground breaking as the article suggests?

In particular, does anyone have a clear idea regarding exactly what aspect of an implementation the method will potentially obfuscate? Does it only apply to hardware implementations at the integrated circuit level? Does it apply even if the adversary is able to track and map signals once the chip is turned on? Does it apply to software implementations for generic platforms, even if the adversary has full control over the CPU and internal memory (e.g. in case of emulators)?

Are the results as ground breaking as the article suggests?

This result will prove to be a very important one for theoretical crypto. The analogy to fully homomorphic encryption (mentioned above by Samuel) is useful, since that is another well-known result that was hugely groundbreaking from a theoretical point of view, but even years later the constructions are not what one would consider "practical."

  does anyone have a clear idea regarding exactly what aspect of an implementation the method will potentially obfuscate?

The obfuscated program will hide all aspects of the implementation, except for the output. That's the definition of obfuscation. Well, mostly. The most natural definition of obfuscation is impossible to achieve in general. Without getting into too many technical details, this paper shows how to get something weaker called "indistinguishability obfuscation", which is known to be the best possible kind of obfuscation you could hope for in light of the impossibility result. Unfortunately, it's somewhat difficult to interpret exactly what you get from indistinguishability obfuscation. The authors do mention this in their paper.

  Does it only apply to hardware implementations at the integrated circuit level?

There's nothing really specific to hardware in this paper. You can obfuscate any program, hardware or software. But perhaps the confusion comes from the fact that, in order to user their obfuscation, you have to express your program as a boolean circuit (of AND, OR, NOT gates), not as a Turing machine or assembly code or C or whatever. This is pretty standard in the theoretical literature, but a source of a lot of the impracticality of these kinds of constructions.

  Does it apply even if the adversary is able to track and map signals once the chip is turned on? Does it apply to software implementations for generic platforms, even if the adversary has full control over the CPU and internal memory (e.g. in case of emulators)?

There are no such restrictions on the adversary. Thinking at the software level, the obfuscated program is just a big blob of 1s and 0s that you hand over to the adversary. Now the adversary can do whatever it likes with the blob of data. The security guarantee (more or less) is that the only useful information that the adversary can get out of this blob of data is the ability to execute the program on inputs of its choice. Sure, this covers situations where you imagine the adversary to have full control of the hardware on which the obfuscated program is executing.


Is there any reason not to use EdDSA with Weierstrass curves? I'm volunterely working for a crypto library and we're planning on adding Curve25519 support (finally). At the same point I had the idea of adding support for EdDSA in the same run.

Our library is highly modular, so the question needs to be asked:
Is there any (good) reason to limit the use of EdDSA solely to twisted Edwards curves?

According to the paper "EdDSA for more curves" by Bernstein, Lange et al. one can use any odd-prime field, however EdDSA is usually only being talked about in the context of Ed448 and Ed25519.

Strictly speaking EdDSA, as defined in "EdDSA for more curves" by Bernstein, Lange et al., can only work for (twisted) Edwards Curves.

Thus, IMHO, the correct answer your question is no.

In the paper, they define the curve parameters as being the parameters of a (twisted) Edwards curve, the addition law as the addition law on twisted Edwards curves, etc.

Note that even the base point $B$ is defined as lying on the (twisted) Edwards curve. This means that even if you have a curve birationally equivalent to a (twisted) Edwards you can't compute on the original curve, because the $R$ parameter of the signature will be a point lying on the equivalent (twisted) Edwards. (Well, of course you can convert input points on your curve and convert back the output to the twisted Edwards but this, in general, will have performance penalties)

If you, instead, allow a more elastic definition of EdDSA, then yes, the scheme is generic for any group, as Schnorr's signature scheme is (from which EdDSA is derived). The only reasons to stick to (twisted) Edwards are those related the the definition of "safe" curves used in safecurves' website, which, by the way, don't limit to the applicability of EdDSA, and are probably the reasons why the EdDSA authors restricted EdDSA to (twisted) Edwards.

I also believe EdDSA is commonly associated with Ed448 and Ed25519 because it's a new algorithm and it just has been applied to new curves.

But you can apply the same modification to Schnorr's signature scheme as done by EdDSA (e.g. use ECC, signature is $(\underline{R},\underline{S})$, use point encoding/compression, include encoded public key $\underline{A}$ in hash, have a deterministic generation of $r$, use key derivation from "secret key", etc.) without constraining to (twisted) Edwards.

Security proofs rely on the discrete log being hard. Since every curve defined over prime fields can be written in short Weierstrass form, the discrete log  can't be easier for one family of curves, so you can't loose security just by using a non twisted Edwards curve.

Note: above I used "family" to mean the curve's shape. Of course discrete log is easier, in general, for e.g. supersingular of curves (where embedding degree is $\leq 6$ allowing efficient MOV attack), but that's independent of their shape. For example: $y^2 = x^3 + x$ over $\mathbb{F}_{19}$ is supersingular and has a point $(18,6)$ of order $4$, which makes the curve birationally equivalent to an Edwards curve by Theorem 3.3 of the Twisted Edwards Curve paper


How are random numbers for RSA generated? The RSA public key encryption requires two very large prime numbers as part of its encryption process that serve as secrets. These are typically generated with cryptographically secure random number generators of some kind.

However, random number generators generate random bits; they don't specifically generate primes; and proving that a number is prime would require attempting to factor it -- the very problem that makes RSA hard.

How are the prime numbers found for use in RSA?

Very important:

Determining whether an integer is prime is significantly easier than factoring it (at least in the current state of our knowledge). We can easily determine whether integers having thousands of decimal digits are prime, but such integers are far beyond the reach of current factoring algorithms.

Now to answer your question: "plain" RSA does not specify how the prime numbers are to be generated. For any particular implementation, you would need to look at its source code or documentation to see how it does it. A popular method is the "generate-and-test" paradigm:

Generate a random number of appropriate length.
See if it is prime, using either a probabilistic or a deterministic test depending on your level of paranoia. If it is prime, you have your prime. Otherwise, go back to step 1.

A simple application of the prime number theorem can give you an estimate of the probability that the number you picked is prime (depending on its length). This is generally not the same thing as the probability that your primality test will consider it prime, however, if you are using a probabilistic test.

I'll leave it to you as an exercise to implement this in your favourite CAS (e.g., PARI/GP or Sage) and see how it works in practice.

EDIT:

The two "tricks" given in the other answer will not make any difference in most cases.

Ensuring that we only give odd numbers to the primality test is useless: any decent primality test will immediately discard even numbers, precisely so as to not waste time on them.
Adding $2$ to the previous number instead of generating a new one from scratch also does not make any difference (at least on my machine). I can't see any reason to believe it should, either.


What is the difference between ECDSA and EdDSA? As I understand it, both work with elliptic curves, but there seems to be a difference as EdDSA is generally recommended over ECDSA.

Partially covered by does TLS 1.3 use ECDSA-Sig-Value encoded signatures for Ed25519 / Ed448? but to add a little, rfc8032 describes EdDSA's advantages as:

  EdDSA provides high performance on a variety of platforms;
  The use of a unique random number for each signature is not
     required;
  It is more resilient to side-channel attacks;
  EdDSA uses small public keys (32 or 57 bytes) and signatures (64
     or 114 bytes) for Ed25519 and Ed448, respectively;
  The formulas are "complete", i.e., they are valid for all points
     on the curve, with no exceptions.  This obviates the need for
     EdDSA to perform expensive point validation on untrusted public
     values; and
  EdDSA provides collision resilience, meaning that hash-function
     collisions do not break this system (only holds for PureEdDSA).

ECDSA also has small sizes (4) though not exactly the same ones -- and (all? most?) applications use ASN.1 which is variable size and a little more complicated, although the algorithm itself doesn't require that. ECDSA also has good performance (1), although Bernstein et al argue that EdDSA's use of Edwards form makes it easier to get good performance and side-channel resistance (3) and robustness (5) at the same time. EdDSA also uses a different verification equation (pointed out in the link above) that AFAICS is a little easier to check.

Standardized ECDSA does require random per message and fails catastrophically if it repeats for different messages (2); rfc6979 by our very own bear proposes a fix for this but has not been widely adopted, at least not yet. (6) just means the EdDSA standard allows omitting the message hash, which the ECDSA standard officially doesn't but in practice people do anyway, so I consider this difference spurious.

For some more on the differences caused/enabled by Edwards form, see:
Elliptic Curves of different forms
What are the differences between the elliptic curve equations?
What is the curve type of SECP256K1?

There's also the general effect of EdDSA being newer, which has both real advantages (learn from and adapt to field experience, optimize for modern systems and implementation methods) and spurious ones (more fashionable and gives the impression of being 'in with the cool kids'). Plus there's the effect of Bernstein not being the US government, which some people just distrust and/or dislike, for reasons that are mostly out of scope here.


What is the minimum message length to obtain the full potential of a hash? Suppose I want to commit to a uniformly picked nonce of fixed length $n$ bits without revealing the nonce, so I use a secure hash function $H$ mapping messages to digests of length $d$ bits. Suppose $H$ promises a complexity of $\sim 2^d$ for a preimage attack, and $\sim 2^{d/2}$ for a collision attack. Suppose $n$ is publicly known.

Clearly, at least for the preimage attack, the above promise cannot gain you a complexity of more than $2^n$ for $n<d$, because then you can just try out all $2^n$ messages.

My question is: is it considered safe for practical purposes (say, for $H$ from the SHA-2 or SHA-3 family) to use $n=d$ for obtaining the full or almost full complexity of $H$, or should $n$ be even greater?

First of all, the output sizes of SHA2 are 224, 256, 384 or 512-bit and of SHA3  are 224,256, 384, 512-bit.

Normally, hash functions are accepting arbitrary length inputs and producing fixed-length outputs. Hence, collisions are inevitable by the pigeonhole principle. We want them to have collision resistant in a way that even mathematically they exist, it must be hard to find one.

There are no known collisions for SHA2 and SHA3 series (but SHA-1 is shuttered).

If we limit the input size shorter than the output size, it is unlikely that we will find a collision. Consider 128-bit input size, the total inputs are $2^{128}$ and even for today technology, it is far to reach for search. The SHAs will map these $2^{128}$ different inputs into a much larger space as 224, or to 521-bit. Since we don't know how the values are distributed by these hash functions, we cannot prove it but we can say that it very likely that the values are distinct.

We can say similar arguments if the input size equal to output size.


After a diffie hellman key exchange, what is the common secret used for? What is the common secret that is established used for? What types of interactions are now possible?

It can be used as a key for a symmetric key algorithm.

It can be used to derive a key via a standard key derivation mechanism.


Can RSA (theoretically) be used as a block cipher? Assume AES gets a devastating attack making it unusable. Is it possible to use RSA in a secure way that can encrypt data in bulk?

I can't see how RSA (assuming OAEP padding) can be used in normal block cipher modes. Its output is likely not pseudorandom, so it can't be used in CTR, OFB, or CFB mode. Its output is too large to be fed back in, so it can't be used in CBC mode. Using it in ECB mode would have the problem that blocks can be moved, duplicated, deleted, and replaced just like if you use ECB on a normal block cipher.

I've seen this sort of thing asked before, but the answers are always along the lines of "RSA isn't a block cipher, so you shouldn't". This won't be used in practice, it's just a thought experiment.

I can't see how RSA (assuming OAEP padding) can be used in normal block cipher modes. Its output is likely not pseudorandom, so it can't be used in CTR, OFB, or CFB mode. Its output is too large to be fed back in, so it can't be used in CBC mode. Using it in ECB mode would have the problem that blocks can be moved, duplicated, deleted, and replaced just like if you use ECB on a normal block cipher.

You're right about the CBC, OFB and CFB modes. Using RSA as drop in replacement will be troublesome anyway, because it would run into practical issues besides the security related ones already mentioned by fgrieu. Will the padding mode be compatible with such large block sizes? Will the implementations? What about buffers created to be about the same size of the plaintext input?

ECB in my opinion has the best cards. The main issue with ECB is that repeating plaintext blocks will be seen as repeating plaintext blocks by an attacker. This problem however is not present if you'd use RSA with e.g. OAEP padding. OAEP padding already has a random component, so you would not be able to see the repeating pattern.

You also state that ECB allows blocks to be "moved, duplicated, deleted, and replaced". This is however not just a property of ECB mode; it's a property of any mode that doesn't include integrity protection and authentication. You can simply remove this problem by authenticating the ciphertext with a digital signature - the asymmetric equivalent of a MAC. If you assume that you've distributed the full key pair to both parties you may even get away with using the same key pair as the padding would protect you against most if not all attacks.

Using RSA in ECB/OAEP mode of course has huge drawbacks with regards to performance, key management and overhead. It could also drain the secure random generator of the system. Furthermore, it seems that a symmetric cipher like AES is a whole lot more going for it with regards to security. So you'd probably downgrade your security level rather than upgrading it.

So yes, ECB is kind-of possible. If it wasn't you should not be able to encrypt multiple messages. Anybody implementing such a scheme would be considered out of hens mind by the cryptographic community though - and rightly so.

In the comments you further explain that

  ... but the idea is to use it similarly to how we use block ciphers today, as to avoid #1.

This would be impossible. Raw / textbook RSA is horribly insecure. You'd have to perform padding. Using the cipher in block mode of operation doesn't work. Furthermore, there is a problem with the highest bit of the input. With RSA you can deterministically encrypt something of size N - 1. N - 1 will not be on a bit boundary. That means that you'll always have a single bit of overhead. So even if it was possible to create a secure mode, you still could not use it as drop-in replacement.

ECB mode for textbook RSA is often used in textbook examples of RSA encryption with very small primes. After all of the above I hope I don't have to explain how horribly insecure that mode is; it breaks not just one but all of the rules.


HMAC vs MAC functions I've read definitions of MAC and HMAC, but can't say I've completely grasped the differences.

What are principle differences?
When to use one and when the other?(Typical Use Cases)

As Chris Smith notes in the comments, HMAC is a specific MAC algorithm (or, rather, a method for constructing a MAC algorithm out of a cryptographic hash function).  Thus, HMAC can be used for any application that requires a MAC algorithm.

One possible reason for requiring HMAC specifically, as opposed to just a generic MAC algorithm, is that the HMAC construction actually provides (as long as the underlying hash function satisfies the appropriate assumptions) stronger security properties than what's required of a MAC.  For example, nothing in the definition of a secure MAC algorithm (resistance to existential forgery under a chosen-plaintext attack) says that the MAC output can't reveal information about the plaintext to an attacker.  If the plaintext is secret but the MAC is public, that would obviously be bad.  HMAC, however, is guaranteed not to reveal any information about the plaintext as long as the underlying hash function is secure.

In particular, Bellare has shown that HMAC is a pseudo-random function (PRF) as long as the compression function of the underlying hash is also a PRF, and a "privacy-preserving MAC" (PP-MAC) as long as the compression function of the underlying hash is also a PP-MAC.  Both of these are strictly stronger security properties than what's required of a plain MAC; in particular, being a PRF is a very strong security property — it essentially says that there's no practical way for an attacker to say anything about the output of the function based on the input, or vice versa, except for the obvious fact that the same input always yields the same output.  There are many use cases for which a PRF will do whereas a plain MAC may not; HMAC, instantiated with a secure hash function, can be used for those.

Also, as Chris notes, some other MAC algorithms require a random IV to be secure; HMAC does not, so it can be used even in situations where deterministic output is required, or where messages must be kept as short as possible.

As for why you might not want to use HMAC, well, one reason is that it's not really optimized for speed.  Dedicated MAC functions, particularly those based on universal hashing (the Carter–Wegman construction) like UMAC and VMAC, can be significantly faster.  Also, MACs based on block ciphers (such as CMAC) can be very useful on limited platforms where an efficient block cipher primitive (like AES) is available but a secure hash function is not.


How does Output Feedback mode use the initialization vector? How can I process Initialization Vector inside the Block Cipher Encryption box (using for example AES) together with the Key?

Will I encrypt the Initialization Vector like a block of plaintext?
So I can generate a keystream, which I will then XOR  to the plaintext to generate ciphertext?

Will I encrypt the Initialization Vector like a block of plaintext? to generate keystream and I will XOR it to the plaintext to generate ciphertext?

Yes, for the first block of plaintext. For the subsequent blocks, you use the output of the previous encryption (before XOR) as the input to the cipher (along with the same key).


What is the (classical) algorithm of choice for finding discrete logarithms in composite-moduli groups? I've recently written an answer on how to find the factorization of a $n$ if we can find the order(s) of elements in the associated group $\mathbb Z_n^*$. This also lead me to Shor's algorithm which does basically just that: Find the order and then compute the factorization from that.

Now, probably for a learning experience, I've thought about implementing the above factorization method but I'm short of an algorithm to find the discrete logarithm in the generic $\mathbb Z^*_n$ group without factoring $n$ first.

So what is the algorithm with the best run-time complexity that can find discrete logarithms in $\mathbb Z^*_n$ for $n\in\mathbb N_{\geq 2}$ without factoring $n$ first?

Suppose you had a discrete log oracle giving $\mathcal O(n, g, g^x) \equiv x \pmod{\phi(n)}$ with high probability for random $g$ and $x$.  Pick a uniform random $g$ and a large random prime $k$; let $m = \mathcal O(n, g^k, g)$, so that $$(g^k)^m \equiv g \pmod n,$$ or $$g^{k m - 1} \equiv 1 \pmod n;$$ then the order of $g$ modulo $n$ divides $k m - 1$.  This gives an oracle to find the order of a random element (or some multiple of it).  As you observed, this is enough to factor $n$ with modest additional effort.

Hence any algorithm you can use to compute discrete logs modulo a composite $n$ can't be much cheaper than an algorithm to factor $n$: there can't be much to be gained by attacking discrete logs directly.  So it's not surprising that the state of the art for both is some variant of the GNFS.


How do Alice and Bob perform key exchange through a third-party (server) in end-to-end encryption? Understanding end-to-end encryption, I ran into an issue which I wasn't able to find a solution for.

Given three parties: Alice, Bob, the chat endpoints, and the server party owned by Eve. The server party allows Alice and Bob to communicate.

Let's say Alice and Bob wanna start an encrypted chat session with each other. How do they prevent Eve from gaining and replacing the encryption keys (performing the MiTM attack) and compromising the whole session?

A meeting in person to share the secret is not an option.

I have read about OTR and Double Ratchet Algorithm. They claim to be secure and OTR claims to use the Socialist millionaire protocol, which, as I understand, should prevent the conversation to be compromised. But I don't quite understand how it works.

The main question is, is there a way for two parties establish a completely private conversation though a compromised server without using an outside channel?

If Alice and Bob have no relevant secret knowledge not known to eve which controls the communication channel between them, it is impossible to create a seecure communication channel.
Any protocol used, including diffie hellman, double ratchet socialist millioner or anything else can still be used with a MITM attack.

Eve takes the role of Bob when talking to Alice and the role of Bob when talking to Alice. Agreeing on two separate keys. The socialist millionaire will do no good because Bob shares a key with Eve.

To make this work we need either a pre shared public key for at least one party or a secondary communication channel to verify same key is used. We could use a public channel which everyone sees but Eve does not control. We could meet IRL and compare keys. We can use a voice channel assuming Eve won't be able to synethesize our voice in real time to recire a key commitment.(Deep learning is rapidly making the last assumption dubious).

Key exchange protocols work great with a passive eves dropper or when we have an authentication mechanism.


is XOR-hash difference-unpredictable Let $F$ be a PRF.

The $XOR\text{-hash}$ is defined as:

XOR-hash(k, m):    //m=(a₀, a₁, ..., aᵥ)
    t = 0ⁿ
    for each aᵢ ∈ m:
        t = t ⊕ F(k, aᵢ)
    return t

Suppose an attacker $\mathcal{A}$ can send 3-uples $(m_0, m_1, \delta)$.

A function $f$ will be difference-unpredictable if $\mathcal{A}$ cannot guess a 3-uple such that $f(k,m_0) - f(k,m_1) = \delta \;$ with more than negligible chance.

How can I show that $XOR\text{-hash}$ is difference-unpredictable?

I think the argument relies on the fact that $\oplus$ keep all the bits pseudo-random, so that the difference $d$ will look like a subtraction of two random results, hence the probability of some bit of $d$ match some bit of $\delta$ will be $\small\sim$$0.5$ and the probability of $d = \delta$ would be negligible.

You cannot prove that this is difference unpredictable since it is not. Take $\delta=0$ and set $m_0=(a_0,a_1)$ and $m_1=(a_1,a_0)$.


Triple Diffie-Hellman and MITM While reading about Triple Diffie-Hellman, I was wondering how it can prevent MITM if the server decides to spoof key sets.

For example, Alice and Bob are connected using a server.

Alice ----- Server ----- Bob

What if the server, with malicious intention or under government request, tries to spoof the key sets? Is it possible to compromise the communication in such cases even using X3DH?

I'm assuming here that you are talking about this Signal defined protocol.

It depends. It basically hangs on one of the very first security consideration:

Security considerations
4.1. Authentication

Before or after an X3DH key agreement, the parties may compare their identity public keys IKA and IKB through some authenticated channel. For example, they may compare public key fingerprints manually, or by scanning a QR code. Methods for doing this are outside the scope of this document.
If authentication is not performed, the parties receive no cryptographic guarantee as to who they are communicating with.

Now if authentication is not performed for one of the parties then the protocol would allow the impersonation of that party by controlling (or acting as, if this is not protected otherwise) the server. That's not entirely the same as a MiTM attack - only the untrusted party can be impersonated after all.
Only if the public keys of both parties are not trusted can a full MitM attack be performed. An MitM means that both parties are impersonated, after all.

Note by the way that in the rather dumbed-down description of the protocol it seems that Alice is not authenticated. That's not true.
See the following line in the protocol:

$$\mathrm{DH1 = DH(IK_A, SPK_B)}$$

Here $\mathrm{IK_A}$ must clearly be the private key of Alice and $\mathrm{SPK_B}$ must be the public signed prekey of Bob. That's a horrible notation that they use because $\mathrm{IK_A}$ is introduced earlier as a public key and $\mathrm{SP}$ is commonly used to refer to a secret (or private) key. This is all done under the because:

All public keys have a corresponding private key, but to simplify description we will focus on the public keys.

and that led unfortunately to the invalid description of the DH protocol.
Still, that does mean that Alice is authenticated as well, not by using a signature, but by using her authentication key pair as part of the calculation of the shared secret key.
Bob of course needs to use the corresponding public key in his calculations, but that is hidden by the following line:

Using these keys, Bob repeats the DH and KDF calculations from the previous section to derive SK, and then deletes the DH values.

This means that Alice identity is confirmed implicitly by verifying the authenticated, encrypted part of the initial message. It's kind of scary that this part about Alice's authentication is missing entirely from the protocol description; hopefully implementations will handle bad authentication tags within the ciphertext of the initial message as authentication failures.


What does this Big-O notation mean based on appendix? I am reading the following book: Introduction to Modern Cryptography Second Edition by Jonathan Katz and Yehuda Lindell.
I am going through page 533 where they list what some of the notation means, and I came across the following:

$O(·)$, $Θ(·)$, $Ω(·)$, $ω(·)$ see Appendix A.2

I believe the first symbol is the Big-O notation, but what are the other symbols called? Do they all do the same thing?
I found Appendix A.2 mentioned above on page 537 which says:

PROPOSITION A.2 For all $x ≥ 1$ it holds that $(1 − 1/x)^x ≤ e^{−1}$.

However, I have no idea what this appendix definition is trying to say. I could not even begin to guess as I do not know what the e is. Could someone please explain this to me? I am very new to both maths and cryptography.
This video explained things well, especially the second post on the video. However, it did not cover what Big-W does, or even what the "W" symbol is called.

In general these definitions are similar everywhere and you can find a definition on Wikipedia.
Also, there is some silly confusion here. You are looking at the wrong thing! You are looking at "Proposition A.2" but you need Chapter/Section A.2 right below.


Is a random oracle controled by the challenger? When proving a Crypto scheme security under random oracle model, is the random oracle always controlled by the challenger?

What if the Hash is only used by the adversary?

As @xagawa mentioned in his comment, it depends on what you mean by "controled".

In the case of using a programmable random oracle, yes, the reduction (in particular the simulation of the challenger of the real game) decides about what to return as answer to an oracle query. Thereby, the reduction has to guarantee that the "programmed" answers are consistent (identical answers to identical queries) and that the distribution of the answers are uniformly random to the adversary.

Such reductions are the ones typically used for reductionists proofs in the ROM, as it nicely allows the reduction to embed a problem instance into the adversaries queries to make the reduction work.

Typically, the random oracle is also observable, i.e., besides the programmability, the reduction "sees" all oracle queries and thus knows how much queries the adversary has made to the random oracle.

There are also works investigating non-observable reductions, where the random oracle is external to the adversary and the reduction. But they still can provide some means of programmability as the reduction can decide on the turing-machine that is used for the external oracle. In the linked paper you find some results for non-observable but programmable random oracles and also some examples for reductions in the ROM that also work if the observability is removed.

There is also the possibiltiy to have reductions in the ROM which are non-programmable and non-observable, but this enormously reduces the power that the ROM provides you in reductionists proofs.


What is difference between meet in the middle attack and man in the middle attack? From my understanding man-in-the middle attack works as follow:
Alice   and Bob agreed  to  use Diffie-Hellman  using   $a$ and    $q$.   Alice sends $Y_A$.   Before  it  reaches Bob,
Charlie intercepts  it  and sends   $Y_{C1}$ instead.    Bob    believes    to  have    agreed  on  a   key $K_B$ with   Alice,  but
the key is  actually    only    shared  by  Bob and Charlie since   $K_B = a^{X_{C1}X_B} \mod q$.

Bob sends   back    $Y_B$, and   it  is  again   intercepted by  Charlie.    Charlie sends   $Y_{C2}$ instead,   and Alice   sees    that    Bob has replied.    Alice   believes    to  have    agreed  on  a   key $K_A$ with   bob,    but they    key is  actually    only    shared  by  Alice   and Charlie since   $K_A = a^{X_{C1}X_A} \mod q$.

So how does meet-in-the middle attack compare to this example?

These are completely different things:

Man-in-the-middle is an active attack to a cryptographic protocol, where the attacker is, effectively, in between the communications of two users, and is capable of intercepting, relying, and (possibly) altering messages. In this case, the meaning of "in the middle" is direct: the attacker is in the middle of two communicating users.
Meet-in-the-middle is a type of cryptanalytic attack that uses some sort of time-space trade-off to drastically reduce the effort to perform a brute-force attack (e.g., transforming an attack that requires $2^{128}$ time into one that takes $2^{64}$ time and $2^{64}$ space). In this case, the name of the attack comes from the expression "let's meet in the middle", which means "to make a compromise". It may also refer to a type of attack over certain block ciphers, where the attacker decompose the problem in two halves and proceeds on each part separately.

The biggest difference between these attacks is that the first one is interactive (i.e., the attacker must participate in the communication), while the second one isn't.

The confusion may come from the fact that certain protocols could receive both type of attacks. For example, in your question you are talking about the Diffie-Hellman key exchange:

A Man-in-the-middle attack to this protocol is exactly the one you describe
A Meet-in-the-middle attack focus on extracting a private key by finding the discrete logarithm using some time-space trade-off (e.g., baby-step giant-step algorithm)


Elgamal attack example with ciphertexts I am a beginner in cryptography. I studied the Elgamal algorithm.
I know that:

p = A big prime number
g = Generator of p
a = 0<a<p-1
B = g^a mod p
secret key= (p,g,a)
public key= (p,g,B)
Encryption= c1=(g^k mod p) , c2=(m.B^k mod p) // 0<k<p-1

Now, I want to solve an exercise.

pk =9789467
g =10895499
n =16777216

c1 =C763515DF26161E21BAB53C35CE2B3B12419B5F5835D1B7B2FE761C9DF5149F4734C149944EA0B4637BBA71EB163CBA99F87611915038DEBA37650E1D69E1380CE6310D7114FD58BC605F1AF334B7044B1

c2 =C57120363903E441B7C90BEB72AFC48AD13D48D5DBF440602DB5C54CE1B490E1604251A1FF47A1D969831C05FFF7D55EAEE120EE7AECDCB0BDF9C5C9B634CACC79EA34485DAC8449D19947E70F1A276EDD

If g is generator, what is pk and n? pk and n are not prime numbers!

The exercise is not about ElGamal in the slightest. I would even call it bogus:

"$n$" would be the modulus, which is clearly not prime, being divisible by $2$.
The values $pk,g,n$ seem to be in decimal, the values $c_1,c_2$ in hexadecimal - but nowhere stated what kind of encoding is used.
It looks like exponentiation in the integers was used, but $c_1$ isn't a power of $g$
Trying around in WolframAlpha how those values were generated I got nothing, but $c_1$ isn't divisible by $n,pk$ or $g$ when considering them as decimal or hexadecimal encoding.
Is it a coincidence, that if you want to do some WolframAlpha computations with these numbers in decimal, the input field is just not long enough? $c_1$ alone fits, but it leaves you just with 5 more input characters. Using all numbers in hex works, tho.

Since the source you quoted is another question how to interpret this, this is definitely not the author.

At this point I can only suggest looking for reliable sources, e.g. exercise material from universities, textbooks or examples on Wikipedia. Looking at any kind of material where you don't know the author and the background has the potential to actually damage your learning progress.


ECC Point Multiplication of Product I can calculate $Q = a\,b\,G$ in several ways:
$Q = a \, (b \, G)$ or $Q = b \, (a \, G)$. These give the same result, as expected.

But if I do $c = (a \, b) \bmod n$ where $a \, b$ is much greater than $n$, then $Q = c \, G$, I get a different point.

Should I have expected this? Or does this difference indicate a problem in my
code?

To answer your question: it's expected, because you're using the wrong modulus.

CodesInChaos pretty much gave you the correct answer; I'll try to explain in more detail about what's actually going on.

We can define an elliptic curve based on any finite field $GF(p^k)$; in the case of P=256, we have p=FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF (in hex), and k=1.

The points on the elliptic curve are actually solutions to a specific cubic equation within the field (plus an artificial "point at infinity"); these solutions, plus a specific point addition operator +, form a finite mathematical group.

A mathematical group is set along with an operator for which certain identies always hold, such as $(A+B)+C = A+(B+C)$, for any group members $A, B, C$.

Because of these identities, we can uniquely define point multiplication $nG$ as the point $G$ added to itself $n$ times (for example, $5G$ is defined as $G+G+G+G+G$).  And, we have the property $a(bG) = b(aG) = (ab)G$, as you have observed.

Now, for any finite group, if the group has $q$ members (that is, the set that makes up the elements of the group is of size $q$), when we know that $ab \equiv c \ (\bmod\  q)$ implies that $abG = cG$, for any group member $G$.

This value $q$ is known as the order of the curve.  However, $q$ is not the value $p$ we used above; instead, for the curve P-256, it is the value q=FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551 (in hex).

That is, if you compute $c = ab \bmod q$ for that value of $q$, you'll find that $abG = cG$


Rounding function used in Saber Key Exchange In Saber: Module-LWR based key exchange, the authors use a rounding function called $\textit{bits}$, defined (in page 3) as follows:
$bits(x, i, j)$, with $j \leq i$, gives $j$ consecutive bits of a positive integer $x$ ending at the $i$-th index (assuming the least significant bit in the $0$-th index), producing an integer in $\mathbb{Z}_{2^{j}}$.
How does this rounding function actually work? How does it relate to the rounding function typically used in Learning with Rounding, $\left\lfloor x \right\rceil_p = \left\lfloor \frac{p}{q}\cdot x\right\rceil\bmod p$?

If $p$ and $q$ are powers of two, as in Saber, then multiplying and diving by $p$ and $q$ amounts to simple bit shift operations.
In Saber, $p = 2^{10}$ and $q = 2^{13}$. Thus, $p/q = 1/2^3$ and $x/8$ can be computed by a right-shift of 3 bits. Using the $bits$ notation, $\frac{p}{q}x = bits(x, \log(p/q), \log p)$.
But we can do better, and also compute the rounding operation in terms of the bits function. Right-shifting by some bits is equivalent to a floor operation. We can express rounding in terms of flooring, with $\lfloor x \rceil = \lfloor x + 1/2\rfloor$ (where $\lfloor x \rceil$ denotes rounding to the closest integer, and $\lfloor x \rfloor$ is the integer floor of $x$).
The same reasoning can be applied here. We want to add $1/2$ before the flooring operation. Since we are dividing everything by $8$, if we add $4$ to the original value $x$, we obtain $p/q( x + 4) = x/8 + 1/2$, as desired.
Hence, $\left\lfloor \frac{p}{q} x \right\rceil = bits(x + (\log p)/2, \log(p/q), \log p)$.
Note that this works only because $p$ and $q$ are powers of two. If Saber had chosen prime moduli, the scaling and rounding operations would be more involved than a simple addition and bitshift operation.


Some considerations about PRNGs Recently I read about pseudorandom generators and I have some observations:

My conlusion is a such that a secure implementation of a PRNG had to be blocking or returning an error code when it is too little entropy. If a PRNG does not do so it means that it cannot be secure- we cannot be sure that returned pseudorandom bits "comes" from true random bits (achieved with a sufficient entropy). Yes?
The presentation Understanding and Managing Entropy Usage points
PRNG provided by OpenSSL does not reseed itself (a slide 32). Does it mean that in long-running application we have to reseed manually? Otherwise we don't have secure PRNG? If yes, how to reseed? Every minute? Every Hour? Every generated 1024 bytes? How to be sure that a seed was taken when entropy was sufficient?
If you know about books/chapters/blogs that covers my doubts let me know!

Thanks in advance :)

Addressing some of your questions:-

  a secure implementation of a PRNG had to be blocking

A CSPRNG is the cryptographically secure version of a PRNG.  Given a good and unknown (to any attackers) seed, then the CSPRNG can run effectively for ever. ChaCha20 or something based around AES can generate oodlebytes of output.

It's a semantic distinction,but you could say that such CSPRNGs should block at initialisation. They should not output anything unless seeded correctly with adequate entropy.  And since unknown entropy is sometimes difficult to acquire, there might be a delay before the CSPRNG kicks off. Acquisition of 128 or 256 bits of unknown entropy can be lengthy for some implementations such as IoT devices without on board TRNGs.

Reseeding can be useful   however, especially in the case of a desktop computer /server.  Such devices allow other processes to execute alongside the CSPRNG. There are currently 263 running alongside my /dev/urandom device. Anyone of them could be spying on me.  Regular reseeding is an attempt to mitigate a potential compromise of the inner state of the CSPRNG.  If the RNG is running on an IoT fridge in your kitchen, such reseeding is not really necessary.

  ...how to reseed? Every minute? Every Hour?

Well this is the trick.  It will depend on your environment.  The CSPRNG Fortuna uses a horribly convoluted, variable timed reseeding and pooling mechanism. A Quantis quantum key distribution system might re-key the conventional side every few minutes. This answer gives the default reseed rate of /dev/urandom as 1 minute.  I see no reason why an IoT wine cooler has to reseed at all between power cycles. I don't think that anyone can give you a meaningful reseed period. A piece of advice might be that if you have access to some form of TRNG, you might as well capitalise on it as often as possible.

Although   consider that in cryptography rather than simulation, the exact random stream is often closely related to a key and/or IV.   Simply swapping out the CSPRNG's inner state after a protocol has been established will suddenly break the session.  The protocol will have to be re-established. This adds complexity and computational /network overhead and also applies to OpenSSL. Your session would terminate.

As for further reading, this forum of course.  There's much debate under the entropy and CSPRNG tags.


Initial Permutation of DES I'm implementing DES, but I cannot understand example.

  Plaintext: 123456ABCD132536
  After initial permutation: 14A7D67818CA18AD

Plaintext is 64-bits hexadecimal, so each character is 4-bits. The first entry
 of IP(Initial Permutation) table is 58 which means 58-th binary number in the plaintext.

That number is 1 because 58-th binary number is in 3 which is before the last entry 6. Anyway, it means first binary number in plaintext after IP must be 1!

Then, how can 1 is appeared? First hex must be 1*** and it means greater than equal to 8!! What I'm wrong with this?

The DES specification numbers bits form 1 to 64, in reading order of big-endian data.

Bit 58 belongs to the second rightmost hex digit of the plaintext, which contains bits 57 to 60. This hex digit is 3, that is 0011 in binary, and bit 58 is the second 0 in that.


Double DES meet in the middle attack: number of candidate keys I'm new to cryptography and found this statement in a book, which says that when having a message block of $64$ bits and using a key of $56$ bits, we will get $\frac{2^{112}}{2^{64}}=2^{48}$ candidate keys if we encrypt a given plaintext and decrypt the corresponding ciphertext (in double DES).

So, assuming that using one key, each of the $2^{64}$ plaintexts will be mapped to again $2^{64}$ ciphertexts and let's also assume that the function of encryption is such, that there are no repetitive ciphertexts, that being said, the mapping is bijective. Now, if we make a new set of ciphertexts for each key, there will be a total of $2^{56}$ (out of $2^{64}!$ possible permutations) different sets, corresponding to different mappings. My question is, where do we get the $2^{64}$ mentioned in the very first sentence? I get it that there are $2^{64}$ possible ciphertexts, but don't we get a set of $2^{56}$ ciphertexts from encryption, and also that much from decryption? So wouldn't the number of candidate keys be the number of elements of the intersection of these 2 sets?

My question is, where do we get the $2^{64}$ mentioned in the very first sentence?

There are a couple of equivalent ways of looking at the problem.

One way is to treat 2DES with an incorrect key as a completely random mapping; there are $2^{112}$ possible keys, and each incorrect key will map our one known plaintext block to a random ciphertext block; there are $2^{64}$ possible ciphertext blocks (of which 1 is the one which we know is valid); and hence each key will do the mapping correctly is $1 / 2^{64}$; hence the number of keys we expect to happen to get the mapping right is about $2^{112} / 2^{64}$ (as stated in the paragraph).

  So wouldn't the number of candidate keys be the number of elements of the intersection of these 2 sets?

That's another, equally valid way of looking at the problem.

If we treat DES (both encrypt and decrypt) with an incorrect key as a completely random mapping, then both the set of $2^{56}$ ciphertexts from the first level encryption, and the $2^{56}$ plaintexts from the second level decryption, are completely random.  There are $2^{64}$ plaintexts possible from the second level decryption, and so a specific block is a possible second level decryption with probability circa $2^{56}/2^{64} = 2^{-8}$.  There are $2^{56}$ ciphertexts from the first level, and each one happens to be a possible second level decryption with probability $2^{-8}$, and so the expected size of the intersection is, wait for it..., $2^{56} \cdot 2^{-8} = 2^{48}$.


Password vs public key for authentication? What's the difference password and key in terms of authentication?

I think that they are potentially same.
But, in practice, password involves some bias since it is created by human.

On the other hand, some key is produced by computer, which results in pseudo-randomness over some large bit space.

Can anyone explain when to and when not use password and key-based authentication?

We don't want to compare a password and a public key. The password needs to be kept secret from adversaries trying to impersonate its owner, while the public key is intended to be freely disseminated, and is not a mean of authentication.

We want to compare a password and the private key of a public/private key pair (asymmetric cryptography) as mean of authentication. The core difference is that the password has no equivalent to the public key: something that's safe to reveal but allows to check possession of the authentication mean.

Consequently, a huge drawback of the password is that each entity with which the password is used can get to know it. As usually practiced in web server access: just by keeping a copy of the password at registration or log in; and at any time with more work (by trying enough likely passwords and applying at high speed the method normally used to check if the password is right, until hitting the right one; for typical passwords, there's a high risk the password is found with less cost than it is worth, at least for some users; that's including with password protocols like SRP, seldom used). That's one reason it is recommended not to use the same passwords for different servers.

Also, as usually practiced, if an an adversary manages just once to impersonate the legitimate entity that verifies the password (e.g. by making a fake server looking like the original), s/he can receive the password from its unsuspecting owner, and then impersonate the owner at will (including to other servers if the same password was used for different servers, another reason to avoid this).

By contrast, a public/private key pair can safely be used to authenticate with respect to any number of entities/servers, even careless or dishonest. Also, it is possible to obtain a certificate from an authority binding one's public key with an ID (domain name, email, name..); that allows to authenticate as associated to this ID to an entity trusting that authority, without prior enrollment with said entity. A password only allows that if the trusted authority checks the password, and confirms that it did to said entity by some online communication (example: using one's Google ID to authenticate on StackExchange).

A public/private key pair allows the holder of the private key to sign a document/file, offline, in a way verifiable against the public key, so that anyone can check that the document was signed by the holder of the private key. A password does not allow that.

When it comes to trust in the equipment used, authentication by password or private key are about equally vulnerable: if the user's computer manipulating the password or private key is rigged, poof goes security as long as the password or key pair is not revoked. Keeping the private key in a Smart Card improves things because the private key is safe in the Smart Card, but only partly: if the computer is not trusted, while the Smart Card is connected to a rigged computer, the Smart Card can be misused without the legitimate user knowing.

Private keys have one serious drawback compared to password: they are too long to memorize or key-in on a regular basis, even if we use techniques towards that goal. There is a wide a gap between high-level security and the 44-bit XKCD password, or anything a user is willing to type regularly; that gap can't be conveniently bridged with key strengthening, at least on current convenience devices.

As an aside, use of private key as an authentication mean requires complex calculations, versus a minimum of none for password. However that has become a lesser issue with powerful CPUs everywhere.

There's something in-between password and private key as an authentication mean: secret key (of symmetric cryptography), shared with the other party. That has all the worst properties of private key and password combined, with a few exceptions:

Cryptograms necessary for one authentication can be small (like 6 digits), thus can be keyed-in. That's used by authentication dongles.
Secret keys are shorter than typical private keys; but it is equally hard to come-up with a safe and convenient way such that they could be memorized or regularly key-in.
Calculations are slightly less complex than for private key; but they still require a CPU, thus that's an edge only when limited to very lost power/cost CPU.


preferred method for generating k for DSA / ECDSA FIPS 186-4, sections B.2.1 and B.2.2, discuss two different methods for generating k for DSA / ECDSA. Unless I'm mistaken RFC 6979 discusses another method utilizing HMAC_DRBG.

So what method is the preferred method?

FIPS 186-4 was published July 2013. RFC 6979 was published August 2013. So the RFC is newer but not much newer.

The "normal" way of generating the k value is by doing it randomly, which is what FIPS 186 describes. FIPS 186-4 does not conceptually deviate from previous incarnations of FIPS 186 in that respect.

It so happens that having a good random generator is a tough requirement; some systems (especially embedded) do not have such a generator; it can also be quite inconvenient to make an external PRNG available to the signing engine (it's an extra parameter to pass through several API layers).

One particularly vexing characteristic of random number generation is that it cannot be tested. If you implement ECDSA with a poor generator, then signing will still happen, verifiers will verify, and all unit tests will report that everything is fine. This is the perfect setup for wide-scale blunders, and, indeed, it happened.

Derandomization is a generic methodology for fixing such issues in signature algorithms: it removes the need for a source of randomness, and since it makes the signature deterministic, it can be tested: unit test will not only check that the generated signature is a valid one, but also that it is the valid signature that should be produced. RFC 6979 is an incarnation of derandomization for DSA and ECDSA: generated signatures are fully compatible with standard DSA/ECDSA verifiers, but they are also deterministic and thus can be tested against the test vectors provided in the RFC.

I wrote that RFC all by myself, and pushed it as "informational"; it was not a mandate by NIST or ANSI or whatever, and it did not receive any such "official" blessing. It still went through some reviewing: the draft has been around since March 2011, the test vectors have been independently verified, the internal construction uses HMAC_DRBG (which has itself been thoroughly reviewed), and nobody found anything wrong with it (from a cryptographic point of view)*. RFC 6979 has found its way into some well-known cryptographic libraries, such as Crypto++ of Libgcrypt; it has also been deployed in implementations of Bitcoin "wallets", following a number of incidents where bitcoins were siphoned out because of poor PRNG.

One may note that the mechanism described in RFC 6979 more or less follows the generation method described in section B.2.2 of FIPS 186-4: it really is works by "testing candidates", and the candidates are produced by an "approved RBG" (HMAC_DRBG is one of the NIST-approved PRNG construction). The real deviation is that in RFC 6979, the PRNG is not seeded by gathered entropy, but by the concatenation of the private key and the hash of the signed message. Thus, it may be argued that you can implement RFC 6979 and still comply to the letter of FIPS 186-4.

It is possible to use RFC 6979 with the internal HMAC_DRBG seeded with not only the private key and hashed message, but also some gathered entropy, at which point the signatures are no longer deterministic, and you lost the ability to test the implementation against test vectors, but you then are fully back into the NIST fold, which might be convenient if you aim for full formal compliance to some set of regulations.

(*) It has been remarked that HMAC_DRBG is relatively heavy-handed with regards to the number of invocations of the underlying hash function. In practice, the elliptic-curve computations will dominate the overall cost, the hashing cost being typically less than 10% of the total cost.


Appropriate scrypt parameters when generating an scrypt hash What values for CPU, memory and parallel difficulty should be used when generating an scrypt hash? i.e.

$N        The CPU difficulty (must be a power of 2, > 1)
$r        The memory difficulty
$p        The parallel difficulty

I'm using the PHP PECL extension from here to generate my scrypt hashes. Is the following usage slow/secure enough?

Password::hash('ThisIsAnExample');

This produces the following hash:

16384$8$1$pl5s1ZnqC4g=$ba6a283f818789bb2b5dcf1d0fcf73b916f44d18ee52ea517c4d788f6e1d02e5

Also, how can I find the appropriate parameters that my hardware can afford for?

$r$ determines the sequential read size. This should only be changed if you have custom hardware that has a memory subsystem with different characteristics. It takes time to pull data from main memory, and the sequential read size allows the memory latency and CPU processing to be well-balanced on your system. Treat it like a constant unless you know what you're doing. Too large and your hash could be weaker than you expect as it allows an attacker to use a slower, cheaper memory system; too small and your computer will process it inefficiently. May be any positive number. $16$ is probably good today. Also note that $r = 1$ disables a mixing step.

$N$, with $r$, determines the memory block size and hashing iterations ($128\cdot N\cdot r$ bytes, $2\cdot N\cdot r$ rounds of hashing). This is the one you change, and you should make it as big as your usage can handle. Some implementations of the scrypt algorithm only allow powers of $2$, but could be any value greater than or equal to $2$ theoretically.

$p$ determines the number of parallelizable iterations. It allows you to increase hashing power over $N$ alone. Best if you are memory restricted and can't increase $N$ more, or if you want to use multiple processors to compute more hashes in the same time (if you can afford $p$-times more bytes). But you should prefer larger $N$ over larger $p$ in general, as $N$ is responsible for the memory-hardness that makes scrypt unique. May be any positive number.

There are maximum limits to these numbers, but they almost don't need to be worried about because the memory requirements would be astronomical.

Sadly there isn't a lot of discussion or analysis of the parameters, and even fewer about $r$, leading to many misconceptions.


Elliptic Curve vs RSA key length comparison I'm new to ECC.
From this website (GlobalSign Elliptic Curve Cryptography) a 256 elliptic curve key pair provides as much security as a 3072 bit RSA key pair.

My question is: how do experts come to this conclusion? Is there an algorithm that can check or compare the key strengths of both algorithms?
Which parameter of the elliptic curve (a, b, G, P, N, H) determines the most the strength of the elliptic curve?

The comparison can be made according to know attacks and their timings. Your source doesn't provide a reference and date backs to 2015, so that is not a good site as keylength.com. The current values of this answer is taken for 2019.

ECC

For ECC 128 bit security means we need 256-bit curves due to the generic discrete log attacks that have $\mathcal{O}(\sqrt{n})$-time. Your cited page also matches this.

RSA

For RSA it is more complicated since there are different methods around. For example, NIST gives 112-bit for RSA-2048.

There is a good cost estimate with Batch NFS for RSA-2048 in area-time cost per key of about $2^{103}$ taking $o(1)$ as zero, rather than the cost $2^{112}$ advertised by keylength.com, NIST, etc.

Commercial National Security Algorithm, Information Assurance Directorate at the NSA IAD-NSA give 256-bit security for RSA-3072 and ECC with 384 bit.


Key escrow on indistinguishability games Does it mean that when PPT attacker is breaking an indistinguishable based (equivalent with semantic security) game with non negligible probability that he is able to infer the secret keys either on symmetric or asymmetric encryption?

Not always, it depends on the particular encryption scheme.  Strictly speaking, the proofs only say that breaking indistinguishability is equivalent to breaking the hardness assumption they are based on.  There are some cryptosystems, like Rabin's, where the security of the key is equivalent to the security of the ciphertexts, i.e. factoring <=> key recovery <=> message decryption.  However, others like RSA do not have this property.  For RSA, factoring <=> key recovery => message decryption, but it may be possible to decrypt messages without being able to factor.  That is why it is not said to be based on the hardness of factoring, but of the "RSA assumption".  In this situation, the security of the key is greater than or equal to that of the messages.

Long story short, the answer is generally no, but in some particular cases yes.


Can we get the msg when we know tag and key in Poly1305 Assume $tag[i]=\operatorname{MAC}(key[i],msg)$

Now we know:

$tag[0],tag[1],\ldots,tag[n]$
$key[0],key[1],\ldots,key[n]$

Can we get the $msg$ from this?

Or can we get the $tag$ of this $msg$ using a known key?

Can we get the $msg$ from this?

Yes, as long as we know the nonces, and as long as $msg$ is no more than $128n$ bits long, and $n$ isn't too incredibly huge (the latter might not be a required assumption, I just need it for my approach).

Poly1305 can be modeled as computing a tag this way:

$$tag = c_a r^a + c_{a-1} r^{a-1} + … + c_1 r^1 + z - 2^{128} k \bmod {2^{130}-5}$$

where (in your scenario) you know the value $r$ and $z$ (they're a function of the key and the nonce, which you know) and don't know the values $c_a, c_{a-1}, …, c_1$ (that's an encoding of the message) and the value $k$ (which is between 0 and 3); $k$ is here to account for the outer '$\bmod 2^{128}$ operation that Poly1305 performs.

If we have $n$ such tags, we can set this up as $n$ simultaneous linear equations in the unknown $c_a, c_{a-1}, …, c_1$ variables.  We don't know the $k$ variables, hence we would need to go through the $4^{n}$ combinations of the $n$ different $k$ variables, and solve each one individually (and after obtaining a solution, we would check the message to see if Poly1305 processes the message as expected - it may encode the message to a different set of $c$ variables, or assign a different value for a $k$ variable.

If $n \ge a$, this gives us enough equations to find a solution; if $n > a$, this solution is likely to be unique.

This involves assuming $4^{n}$ sets of $n$ linear equations; as long as $n$ isn't too large, this is practical.


CAESAR finalists: Lightweight case (Ascon vs ACORN) The Ascon cipher has been selected as the first choice in lightweight case and ACORN as the second. However according to Face-off between the CAESAR Lightweight Finalists: ACORN vs. Ascon paper, the winner of the face-off is ACORN.

They mentioned that

ACORN-1 and Ascon-small have 18% and 74%, respectively, the area of AES-GCM.
ACORN- 32 and Ascon-large are 23.3 and 2.5 times faster (respectively) than AES-GCM.
ACORN-1, is the most efficient side-channel resistant CAESAR lightweight finalist, in terms of low area, power, and external randomness

Question: What are the strengths of Ascon over ACORN?

Ascon and ACORN both have interesting features. Let's discuss their pros and cons for some properties stated during the CAESAR competition for lightweight AEADs:

Fits into small hardware area and/or small code for 8-bit CPUs

On this point, ACORN is more efficient as its internal state is smaller than the one used by Ascon (293 vs 320 bits). Moreover, thanks to its very compact core function, the code size of ACORN is smaller.

Natural ability to protect against side-channel attacks

Regarding countermeasures against side-channel attacks, both algorithms are efficient. Ascon has been designed with bitslicing in mind, and thus can be easily implemented in a constant time manner. ACORN is also constant time by design as it does not rely on any conditional branch nor look-up tables. Regarding countermeasures against power/electromagnetic side-channels, 1st order threshold implementation can be reached using only three shares for both algorithms. However ACORN seems more efficient in hardware as stated in the paper you mentioned.

Message sizes: usually short (can be under 16 bytes), sometimes longer

This is maybe the main advantage of Ascon over ACORN: it is way more efficient for short messages. This mainly comes from the fact that ACORN is a stream cipher that requires a huge number of steps to initialize its internal state. For instance, this paper reports (page 11) that Ascon outperforms ACORN for small messages (less than 128 bytes with 16 bytes of additional data) on ARM Cortex-M3. Ascon is also very efficient on 64-bit CPUs as by definition, its internal state consists of five 64-bit words. It is an interesting feature for use cases where high end servers have to handle numerous encrypted requests.

Finally, Ascon is based upon the duplex sponge mode whose security has been analyzed in several papers (e.g., https://keccak.team/files/SpongeDuplex.pdf and https://eprint.iacr.org/2015/541.pdf) while ACORN is based upon a new stream cipher construction. This probably influenced the final decision.


Do other one-time signature schemes exist? I'm curious to know if there are any one-time signature schemes other than Lamport's or its variants (Merkle trees are one such variant). The first I've discovered is called "Bins and Balls" which doesn't use a trapdoor function.

Any others? Are they smaller than Lamport signatures? I'd like descriptions, too (also of BiBa).

HORS (Hash to Obtain Random Subset) is a simple few-time signature scheme with smaller signatures than BiBa.

Let $f$ be a one-way function and $H$ be a hash function that outputs a random size $k$ subset of $\{1,2,...,t\}$, where $k$ and $t$ are parameters that affect security with $k < t$.

The signing key is a random tuple $(s_1,...,s_t)$, and the public key is $(f(s_1),...,f(s_t))$. Now
to sign a message $m$, compute the set $S = H(m)$ and output $\{s_i : i \in S\}$. To verify, apply $f$ to each element of the signature and check this matches with the public key.

Each signature reveals $k$ elements of the secret key, so depending on the choice of $k$ and $t$, a few messages can be signed before security is compromised.

This was used as a building block in SPHINCS, which is a stateless hash-based signature scheme that allows unlimited messages to be signed (but is much more complex).


Primality test in GPG/RSA or extract numbers of private key I cannot find if the two numbers for RSA are tested against an elliptic curve primality test. If not, is there a way to extract the two integers of my private key in order to test it by myself?

If this is not an accurate question why?

GPG (1.4.21) does not use an elliptic curve primality test. It uses 5 strong pseudoprime tests, with the first to base 2 and the others to a random base. For factors large enough that the key is secure, odds that a composite creep by chance are entirely negligible in practice (for a quantitative estimate see appendix F.1 in FIPS 186-4). Also, the mere fact that an RSA key allows decryption of messages, or generation of signatures that verify, is a fair probabilistic primality test of its factors.

To dump a private key not protected by a passphrase under gpg 1.4.x, use
gpg --export-secret-key -a "john doe" | gpg --list-packets --debug 2

For a key version 4 algo 1, the factors of the public modulus are skey[3] and skey[4].


Verifying DER encoded DSA/ECDSA signature with extra content? Having a DSA/ECDSA signature which is supposed to be DER encoded as an ASN.1 sequence of $r$ and $s$ (as described in the RFC), and being given some bytes which are "some valid DER encoded ASN.1" || "some extra bytes" – is the correct behavior to error out, or would it be more correct to proceed to attempt to verify just the DER encoded portion of the input (since it's self-delimiting)?

Specifically, I would like to know if there are any implications in relation to cryptographic security.

I don't think there's an exact "correct" behaviour in this case.
It would be up to the implementation to decide, since the spec is only concerned about the DER encoded portion.

If your implementation parses the input as it moves along only, and doesn't concern itself with the overall size, then it would work fine.

Having said that, I believe the best practice is always to verify input boundaries, and in this case, that would mean the trailing extra bytes should get caught. If they have no business being there, then they shouldn't.

There can be security or crypto implications if there's a bug in the parsing of the input.