Relation between $N = P \times Q$, and $\Phi(N)$ When studying RSA, and proving simple concepts to myself, I went and understood groups and rings, but I failed to understand Lagrange's theorem.

I did understand how from invertible finite groups I could derive Euler's theorem and Fermat's little theorem, etc. But one point remained...

When extracting the invertibles from $N \rightarrow U(N)$, we get the elements which form a group. I also saw that the order of any element in that belongs to $U(N)$, which is the order of $U(N)$. For example, if the number $10$ is $N$, $1,3,7,9$, it forms a group under multiplication $\bmod 10$. Now any element $a$, let it be $7$, the order of $7$, is $4$, which is also the sum total of the co-primes or the order of $U(N)$. This proves Euler's theorem, and thus, Fermat's as well. But when doing RSA, we do the same thing; however,  during key generation, we choose a number that is a co-prime to the order of $U(N)$, which also does from an invertible group $1$ and $4$.

Therein lies the rub, which I don't understand at this moment. What does the order of $U(N)$ have to do with key generation?

I have been unable to find a direct visual link. Ultimately, we are not choosing an element $E$ that belongs to $U(N)$, but an element that forms a group under $U|U(N)|$. And again, when encrypting, we are doing $M^{ed} \bmod N$.

I am not getting the relation between $U(N)$ and the number of elements in $U(N)$ when we are not using the order as an exponent to any element within $U(N)$ to get $1$ or something like that. Why are we generating the key from the number of elements in $U(N)$, and why does it work? What's the relation?

What does the order of $U(N)$ has to do with RSA key generation?

The usual notation is $\Bbb Z_N^*$ for the multiplicative group modulo $N$, that the question names $U(N)$, and $\Phi(N)$ or equivalently $\varphi(N)$ for its order (number of elements), as given by Euler's totient function.

$\forall x\in\Bbb Z_N^*$, it holds $x^{\Phi(N)}\equiv1\pmod N$. This implies:
$$\forall x\in\Bbb Z_N^*,\ \forall k\in\Bbb N,\ \text{ it holds }\ x^{(k\,\Phi(N)+1)}\equiv x\pmod N\tag{1}\label{eq1}$$

We want the RSA encryption exponent $e$ and decryption exponent $d$ (both strictly positive integers) to be such that textbook RSA encryption of a plaintext $m$ followed by decryption consistently returns the original plaintext. That is, we want that $\forall m\in[0,N)$, it holds $((m^e)\bmod N)^d\bmod N=m$. We can write this goal as:
$$\forall m\in[0,N),\ \text{ it holds }\ m^{(e\,d)}\bmod N=m\tag{2}\label{eq2}$$

We can now see what $\Phi(N)$ has to do with RSA key generation: if
$$e\,d\equiv 1\bmod\Phi(N)\tag{3}\label{eq3}$$
then by definition of that, and given that $e$ and $d$ are strictly positive integers, $\exists k\in N$ such that $e\,d=k\,\Phi(N)+1$, and we nearly can use $\eqref{eq1}$ to prove that $\eqref{eq2}$ holds. The one gap is that we only prove the weaker
$$\forall m\in[0,N),\ \text{ if }\ \gcd(m,N)=1\ \text{ then }\ m^{(e\,d)}\bmod N=m\tag{2'}\label{eq2'}$$

We have proven that condition $\eqref{eq3}$ is sufficient to insure that textbook RSA encryption of a plaintext $m$ followed by decryption returns the original plaintext, at least when $\gcd(m,N)=1$. Since $N$ is the product of large primes, $\gcd(m,N)=1$ holds for most $m$.

Further, under the extra condition that $N$ is squarefree (including $ N=p\,q$ with $p$ and $q$ distinct primes), it can be proven that for all $m$ textbook RSA encryption followed by decryption returns the original plaintext.

Otherwise said: one way to see RSA is as working with message and ciphertext in the group $(\Bbb Z_N^*,*)$, but that restricts the message space. It can be extended to $(\Bbb Z_N,*)$ when $N$ is squarefree, that is when $N$ is not divisible by the square of any prime.

We first prove that $\eqref{eq3}$ implies that $m^{(ed)}-m\equiv0\pmod{p_i}$ for each prime $p_i$ dividing $N$, by treating separately the case $m\equiv 0\pmod{p_i}$. The integer $m^{(ed)}-m$ is thus divisible by each $p_i$, thus by their product, which is $N$ when $N$ is squarefree, thus $m^{(ed)}-m\equiv0\pmod N$.

Notice that the condition $\eqref{eq3}$ is sufficient, but not necessary. For a necessary and sufficient condition, we want
$$e\,d\equiv 1\bmod\lambda(N)\tag{3'}\label{eq3'}$$
where $\lambda$ is the Carmichael function.

Notations:

$\forall$ is read "for all". $\in$ is read "in". $\exists$ is read "exists".
$\Bbb N$ is the set of natural numbers: $\Bbb N=\{0,1,2,3,4,5,\ldots\}$.
$\Bbb P$ is the subset of $\Bbb N$ consisting of primes: $\Bbb P=\{2,3,5,7,11,\ldots\}$.
$\Bbb Z$ is the set of (signed) integers: $\Bbb Z=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$.
$(\Bbb Z,+)$ is a group.
$x\equiv y\pmod n$ is read "$x$ is equivalent to $y$ modulo $n$".
It means that $n$ exactly divides $x-y$ (for $n$ a strictly positive integer).
Alternative notations are $x\equiv y\ \ [n]$ or $x=y\pmod n$ or $x=y\ \ [n]$.
$x=y\bmod n$ is read "$x$ is set to $y$ modulo $n$" or "$x$ equals $y$ modulo $n$".
It means that (after the setting, if any) $0\le x<n$ and $x\equiv y\pmod n$ (see above for the meaning).
When $y\ge0$, the quantity $y\bmod n$ is the remainder of the Euclidean division of $y$ by $n$. The quantity $y\bmod n$ is $0$ when $n$ divides $y$ (and the C programmer writesx = y % n for a computation orx == y % n for a test). When $y<0$, we can compute $y\bmod n$ as $n-1-((-y-1)\bmod n)$.
Note: Textbook RSA encryption and decryption reduce their result $\bmod N$, ensuring that the ciphertext and the deciphered plaintext are in $[0,N)$.
$\Bbb Z_n$ is the finite set of integers modulo $n$. That is, the elements of $\Bbb Z$ equivalent modulo $n$ are regrouped into a single element of $\Bbb Z_n$. Thus $\Bbb Z_n$ has $n$ elements.
$(\Bbb Z_n,+)$ is a group. With multiplication noted $*$ when not omitted, it becomes the ring $(\Bbb Z_n,+,*)$.
When the modulo $n$ is prime, $(\Bbb Z_n,+,*)$ is a field, because all elements except $0$ have a multiplicative inverse. As practice of notation: $\forall p\in\Bbb P$, $\forall x\in\Bbb Z_p$, if $x\ne0$ then $\exists y\in\Bbb Z_p$ such that $x*y=1\pmod p$ (also noted $x\,y=1\pmod p$ as a shortcut).
$\Bbb Z_n^*$ is the set of the elements of $\Bbb Z_n$ that have an inverse under multiplication, that is the set of $x$ with $n$ and $x$ having no common positive divisor beyond $1$, that is $\gcd(x,n)=1$.
$(\Bbb Z_n^*,*)$ is a group including when $n$ is not prime. It has $\Phi(n)$ elements.


Solving Vigenère Encryption I'm trying to crack a cypher that I believe is Vigenère encrypted and I'm currently stuck.

I calculated the key length by finding repeated sequences in the cypher and calculating the the common factors.

Word    distance factors
agzd    16       2,4,8,16
zna     92       2,4,23,46,92
zdc     54       2,3,6,9,18,27,54
csio    44       2,4,11,22,44
omy     46       2,23,46
zab     5        5

I assume the key-length is 4 as these are the once that are common factors, but from here on trying to map the correct caesar shiffre for each position I'm stuck.

Can somebody confirm that my key-length calculation has no errors which would explain why I can't solve the cypher.

Here is the cypher:

jD 2GSA 7HNA ZNA w.m. V7KXA 36HBM MKE5 /H SGP9 +R GKKJ 2I A4OTC KDBCUR. 19+R 8Y TKJ JG4 IGO6 6U4T OJ hH/BIK. 196 qFKT+9 BNJK ZD6+Q AGZD. kJ'R EaOP6 4NCR ZK 36 / AGZD6C/HOIE2D. x0ZNAC2S8IO8DI HB xX8D4D 0XK O66M 0Y MN62S 8TZABBD2Za8BI. lBJ HA+DF 6UU/ 2J /FOZDC6S8I OJ kDC8G OO 2BLCYZ O66M 0Y G 925F4 UL J2JHCTGH FHH3K

First, you should start by guessing which symbols in the ciphertext are actually enciphered, and which are simply written in plain.  (Don't worry if you guess wrong, you can always make several guesses.)  For a Vigenère cipher, one also needs to guess whether any non-encrypted characters should advance the key position or not (usually they do not).

For your example ciphertext, it seems likely that spaces, and probably also periods, commas and apostrophes are written in plain — they occur at places where they would in natural English text.  On the other hand, the letters are certainly in cipher, and so are most likely the numbers and the plus signs and slashes too, since they seem to be scattered randomly among the words.

(A curious feature to note at this point is that the lowercase letters in the ciphertext seem to occur at places where an uppercase letter would be plausible in plain English text.  This suggests that letter case may simply be trivially flipped.)

The next step I'd suggest, after initially guessing the cipher alphabet, is to compute the index of coincidence for various key lengths.  In particular, if you do that for various choices of ciphertext alphabet, you'll notice that, for the alphabet consisting of letters (ignoring case), numbers, + and /, the plot of IoC (scaled here for an assumed plaintext alphabet of 26 letters) as a function of key length looks pretty striking:

 1: 0.826  ################
 2: 0.816  ################
 3: 0.825  ################
 4: 0.781  ###############
 5: 0.867  #################
 6: 0.847  ################
 7: 1.822  ####################################
 8: 0.778  ###############
 9: 0.771  ###############
10: 0.860  #################
11: 0.816  ################
12: 0.743  ##############
13: 0.786  ###############
14: 1.812  ####################################
15: 0.791  ###############
16: 0.640  ############
17: 0.803  ################
18: 0.693  #############
19: 0.734  ##############
20: 0.671  #############
21: 1.985  #######################################
22: 0.745  ##############
23: 0.840  ################
24: 0.766  ###############
25: 0.688  #############
26: 0.672  #############
27: 0.567  ###########
28: 1.669  #################################
29: 0.786  ###############
30: 0.777  ###############

Notice the sharp peaks at multiples of 7, strongly suggesting that the key is seven characters long.  In particular, the IoC for those values is close to 1.7, which is considered a typical value for English text.

So let's see what happens if we assume that the key is seven characters long. We'll write down the ciphertext in seven-character blocks (omitting spaces and punctuation) and print out the character histogram of each column:

Column 1:                                 Column 2:
        |
        |
        |            |                     |
        |      |     |                     |                 |
|       |    | |   |||                     |             |   |     |   ||
|   | |||    | |   |||                     |             | | |   |||  |||
|   | |||    |||   |||  |                  |          |||| |||   |||  ||| || |
3   2 227    314   335  1                  5          1113 214   223  233 11 1
+/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ    +/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ

Column 3:                                 Column 4:

          |                                                     |
  |   |   |  ||                                             | | |             |
  |   |   | |||                                             | | |   |    ||   ||
  | | |   | |||  | |                                        | | |   |    ||  |||
  | ||| ||| ||| |||| |                                |     | ||| | |  ||||  |||
  4 214 115 344 1212 1                                1     4 415 1 3  1133  243
+/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ    +/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ

Column 5:                                 Column 6:
                                     |
                                     |                |
                          |          |                |
                  |       |          |                |  |     |    |
                  |   |   |    |     |              | |  |     ||   |
                  |   | |||    |   | |       |      | |  |     ||   ||
            |     ||| |||||  ||||  | |    || |      ||| |||  | ||  |||
            1     411 31225  1131  2 7    11 2      316 141  1 43  142
+/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ    +/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ

Column 7:
        |
    |   |
    |   |
    |   |  |
    |   |  |          |
    ||  |  | |||      |
|   ||  || | ||||| | ||           |
1   62  71 4 22211 1 13           1
+/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ

The first remarkable feature to note is that, even though the cipher alphabet has 26 + 10 + 2 = 38 characters, none of the columns features even half that many character.  This is quite plausible, assuming that the plaintext mostly consists of letters, and keeping in mind that the English letter frequency distribution is quite skewed.

Also, the numbers seem to mostly appear in the columns whose letters are mostly from the beginning of the alphabet, suggesting that they may indeed be sorted before the letters in the cipher alphabet.  (It's not so clear where the + and / characters should belong, but we can try to figure that out later.)

Finally, looking at the letter frequencies within each column, we may note some distinctive peaks.  For example, in column 5 (which, conveniently, has only letters), the most common characters are G, K, O, T and Z.  Shift those six places back in the alphabet, and you get A, E, I, N and T — five of the most common letters in English (only O is missing from the top six).  This gives us a pretty good guess for one key value out of seven already.

Can you finish the decoding from here?

(Ps. I haven't, so my apologies if it turns out I've led you down a false trail.  But I'm pretty sure I haven't.)

Pps. I did eventually solve this puzzle, and it turns out that one of the early assumptions I made above was wrong.  However, you can still decode most of the text despite the wrong assumption, and, once you do, it's not hard to figure out what the mistake is.

Specifically, I was wrong about letter case being simply flipped.  Instead, the correct cipher alphabet has 64 characters: A–Z, a–z, 0–9, + and /, in this order.  (This is, in fact, the same alphabet as used for base64 encoding.)  It just happens that, with this particular alphabet and key, most lowercase letters are encrypted to uppercase ones, and vice versa.


A feasible approach for AEAD on an ethernet link? The setup is shortly this: There are two custom switches (think of an FPGA for example), both are handling 10-100 Gb/s orders of traffic from their outside facing interfaces. This is normal traffic. Then, they have a link between each other. I want to apply AEAD to secure this link, so that an eavesdropper will not be able to analyse the traffic. The restriction is this: The traffic is streaming fast and obviously there is not much time to encrypt or authenticate.

I own both switches, so pre-configuring certificates, symmetric-keys etc. are all allowed. After bootstrapping, I can asynchronously exchange keys in-band, but no out-of-band exchange is allowed.

I am not looking for an unbreakable system, I just want to protect the traffic as much as possible.

What would be the best approach in this case? So far my approach is: I can install certificates to both sides (for authentication), I do not know if or how I should renew them as time goes by. For encryption, I will XOR the plaintext with symmetric keys on both sides (I guess this is the fastest way). However, I consume keys much faster than I can produce. Somehow I should stretch keys or find a way to produce key streams very fast. After this point I get lost.

Don't roll your own crypto

So far my approach is: I can install certificates to both sides (for authentication), I do not know if or how I should renew them as time goes by.

This does not provide authentication in a cryptographic sense. A MITM attacker will still be able to modify data on the wire at will if the underlying encryption is not authenticated. Alone, a certificate can only be used to sign a very small value, the size of a symmetric key. It takes more than the presence of a certificate to ensure that data cannot be tampered with on the wire. For example, you would need to sign an HMAC key which ensures integrity of the messages. If this is not obvious to you, then you should not be trying to design your own cryptosystem!

I will XOR the plaintext with symmetric keys on both sides (I guess this is the fastest way).

This is called an XOR cipher and is extremely insecure, requiring just a tiny amount of known plaintext to break (the same amount as the size of the key). When you have known plaintext the same size as the key, you can simply XOR the known plaintext with the observed ciphertext to recover the key itself. Not to mention, it is highly malleable and does not provide any authentication, even if it was secure.

However, I consume keys much faster than I can produce. Somehow I should stretch keys or find a way to produce key streams very fast.

You have just invented a stream cipher. This is a cipher that takes a single key and expands it to a virtually unlimited stream of pseudorandom data called the keystream which is then added to the plaintext or ciphertext, usually via the XOR operation. A raw stream cipher, like ChaCha20 or AES in CTR mode, is malleable and not authenticated, making it insecure for your purposes. It is so malleable, in fact, that toggling a single ciphertext bit will toggle the corresponding plaintext bit. Such tampering would not be detected or prevented without a properly-implemented authentication algorithm like HMAC, GCM, or Poly1305.
Just use MACsec!
All is not lost! There is already a solution, called MACsec (IEEE 802.1ae). This is an extension to the Ethernet protocol which allows end-to-end authenticated encryption at a low computational cost. It uses AES as a cipher, run in the GCM mode for authentication. It is supported by a number of switches, routers, and operating systems, and is considered very secure.
If you are writing the HDL for the FPGAs, you can use pre-designed IP cores for MACsec, for example this FPGA core. You can also implement MACsec yourself from the published standard if you are confident in your FPGA design skills or can hire someone who is.
An additional benefit of MACsec is that, because this is a standard, it will work out-of-the-box with other compatible switches, such as Cisco's Catalyst 4500. You will not be limited to only using in-house custom switches with your own FPGAs and will not need to go through extensive and expensive cryptanalysis of your own protocol.
Any mentions of or links to commercial products should not be construed as an endorsement of the product of company.


Encrypting a string of arbitrary size with a big integer I am currently writing Python script that initiates a secure handshake. I am kind of reinventing the wheel here, so that I can properly learn it.

Now, I have Diffie-Hellman mostly working from scratch, and both client and server has agreed on a key to use. This key is an integer of ~2048 bits (2047 most of the time. 2046 is the lowest I've seen). The question then is, which cipher do I chose for encryption data of arbitrary length with this key?

Also, when the client and the server later has exchanged public keys, is there any reason why I should/should rely on said public key encryption alone, and not use the above mentioned integer as well?

When you use Diffie-Hellman key agreement protocol, both sides reach the equal keys. Then, you can use it with private key encryption methods, not public ones (like AES or one-time-pad).

One philosophy of public key encryptions is for avoiding key exchanges or key agreements. They are also called asymmetric encryption methods, because the sender and the receiver of the messages have different keys.


Hybrid authenticated protocol Let's suppose that two entities, A and B, are establishing a secure channel and then require a mutual authentication.

A has only a RSA key pair and B has an ECDSA key pair. Both of them trust the public key of each other.

Do you feel comfortable with having A signing it's message with RSA and B signing its message with ECDSA ?

They do have an equivalent key length for both key pairs (keylength.com)

Yes, given the following conditions:

A trusts the public key of B belonging to B
B trusts the public key of A belonging to A
A trusts the signing algorithm ECDSA used by B
B trusts the signing algorithm RSA used by A
A trusts the key length of B
B trusts the key length of A

Normally, the condition 3,4 use the same algorithm, but if both A and B put trust in the other's algorithm then there is no reason not to trust the authenticity.

As you said 1,2 and 5,6 are true.


Proving the possession of signature in zero-knowledge Does anybody know an efficient mechanism to prove the possession of a digital signature (e.g. RSA) on a certain attribute (message) in zero-knowledge? That is, without revealing the actual signature (against tracking, for privacy) prove that you have one? Thanks a lot in advance!

Guillou and Quisquater (link) present a zero-knowledge proof of an RSA signature. Basically, the scheme is as follows:

Public knowledge: RSA modulus $n$, public RSA exponent $v$, preimage $X$.

Secret knowledge for prover: $A$, such that $A^v = X \mod n$.

$$
\begin{matrix}
\mathcal{P} & & \mathcal{V} \\
r \xleftarrow{\$} \mathbb{Z}_n^* \phantom{\mod n} & & \\
T \leftarrow r^v \mod n & & \\
 & \xrightarrow{\quad{}T\quad{}} & \\
 & & d \xleftarrow{\$} \{0,1,\ldots,v-1\} \\
 & \xleftarrow{d} & \\
 t \leftarrow A^dr \mod n & & \\
 & \xrightarrow{\quad{}t\quad} & \\
 & & t^v \stackrel{?}{=} X^{d}T \mod n
\end{matrix}
$$

In this diagram, $\leftarrow$ denotes assignment of a value to a variable and $\xleftarrow{\$}$ denotes uniformly random selection from a finite set.


How feasible would it be to generate 300 million public key pairs in 8 hours? Assume there is a hypothetical situation where one would need to generate hundreds of millions of public key pairs of reasonable strength in a limited time.

What would be required in terms of entropy and how long would it take? Could it be acheived on a single computer? How few computers could one get away with?

If the demand for the public keys was not uniform, how many keys could be generated in a burst?

What effect would different algorithms (RSA, DSA, EC) have?

It is feasible to generate 300 million public key pairs of reasonable strength in 8 hours on a single computer, easily with ECDSA using a single core/thread, and even with DSA using quite a common multi-core computer.

RSA would require many standard computers (baring hardware accelerators for modular exponentiation), assuming all the public keys are made public (see Poncho's answer otherwise, applicable for example if you wanted to generate a single PGP RSA key pair of reasonable security and having the same 32-bit key id as one in 6 pre-existing PGP keys, which is likely achieved with 800 million randomly generated keys).

Generating an ECDSA keys pair is as simple a generating a random private key (of e.g. 256 bits for the common P-256 parameters), and doing one point multiplication. These benchmarks show ecdonaldp256 key generation requires about 300 thousands cycles on a single core and thread of a 3.5GHz CPU, giving more than 10 thousands keys per second, over twice the requirement. And then ed25519 is more than 4 times faster.

Entropy is not an issue, we can even use manual dice throws to seed a CSPRNG, and discard the seed. Also, many modern CPUs have built-in hardware RNG with high throughput, and we can use this if we frown at having all the keys depending on the same seed (but then we still have all the keys depending on the integrity of the same computer, and what's connected to it, which is more of a security concern IMHO).

We can use several cores in parallel, and/or several computers (we can use the same seed on each job, just use the job number as an extension of the seed).

DSA key generation is significantly slower for comparable security, mostly because we need 2048-bit modulus, when P-256 works with 256-bit modulus (and only a few times more such operations). The same benchmarks show donald2048 about 4 times slower than ecdonaldp256 for key generation, and reaching the performance goal with a single computer will require some level of parallelization, but we still reach about twice the stated goal with all 4 cores of some of the CPUs benchmarked. And then high-end single-board servers may have 8 CPUs each with 18 cores.

RSA key generation is much slower for comparable security. The same benchmarks show ronald2048 as more than 1000 times slower than ecdonaldp256 for key generation. That's mostly because RSA key generation requires generating random primes, thus trial and error. Effort is dominated by failed primality tests, and attempts to reduce these. If we pre-select for testing integers not divisible by any of the 54 primes less than 256, that is about $1/10$ of integers, we still need to test about $1024\log(2)/10\approx71$ integers to find a 1024-bit prime. That 1024-bit prime generation algorithm will be dominated by about 75 executions of $x\gets a^d\bmod n$ steps in Miller-Rabin tests, each costing a 1024-bit exponentiation to nearly 1024-bit exponent; so key generation will be in the order of 75 times as costly as the exponentiations dominating an RSA signature using CRT.


What does the acronym "CRT" stand for in the PKCS #1 specification? What does the acronym "CRT" stand for in the PKCS #1 specification?  Does it stand for "Chinese Remainder Theorem"?

Thanks,

Pete

Yes. I haven't heard any other possible CRT acronym in direct relation to RSA. Sometimes it is used as file extension for certificates, but those are not addressed in the PKCS#1 standard.

  This specification supports so-called "multi-prime" RSA where the
     modulus may have more than two prime factors.  The benefit of multi-
     prime RSA is lower computational cost for the decryption and
     signature primitives, provided that the CRT (Chinese Remainder
     Theorem) is used.

Besides that, CRT is always used when pointing out the CRT parameters throughout the standard.


What is the difference between Argon2d and Argon2i? I know that Argon2d accesses the memory array in a password dependent order and Argon2i accesses the memory array in a password independent order. What is the difference in computational complexity?

As @sejpm already hinted in his comment: both scale the same when it comes to the parameters.

You might still want to read the RFC to get the complete picture, but the general differences can be quickly summarized:

Argon2i

Argon2i is invulnerable to side-channel timing attacks, but is weaker against time-memory trade-off (TMTO) attacks.

Argon2i uses data-independent memory access, which is preferred for things like password hashing and password-based key derivation.

Argon2d

Argon2d is vulnerable to side-channel timing attacks, but offers the best resistance to TMTO attacks.

Argon2d uses data-depending memory access, which makes it more suitable for things like cryptocurrencies and proof-of-work (POW) applications with no threats from side-channel timing attacks.


Why does SpongeWrap not need a Nonce? The AEAD scheme SpongeWrap based on the sponge construction gets only a header (additional data), a body (the message) and a key as input values, according to the paper where it is defined.

What is missing compared to other AEAD schemes is a nonce to make the key stream unique. I am wondering, why this is possible. The way I understand it, the sponge state for the first message block only depends on the key and the AD, thus an adversary is able to decrypt at least that first block, if key and AD are reused.

Indeed, the SpongeWrap paper does not claim CPA security (or, really, any kind of privacy protection at all) unless a nonce is included in the associated data, or the associated data can otherwise be guaranteed to be unique for each message.  In particular, if you look closely at section 2.2, you'll find the following note at the end of page 3:

  For privacy, we consider only adversaries who respect the nonce requirement. For a single header-body pair, it means that, for any two queries $(A, B)$ and $(A′, B′)$, we have $A = A′ ⇒ B = B′$. In general, the nonce requirement specifies that for any two queries $(\overline{A, B})$ and $(\overline{A′, B′})$ of equal length $n$, we have $${\rm pre}(\overline{A, B}) = {\rm pre}(\overline{A′, B′}) ⇒ B^{(n)} = B′^{(n)},$$ with ${\rm pre}(\overline{A, B}) = (A^{(1)}, B^{(1)}, A^{(2)}, \dots , B^{(n−1)}, A^{(n)})$ the sequence with the last body omitted. As for a stream cipher, not respecting the nonce requirement means that the adversary can learn the bitwise difference between two plaintext bodies.


Does a playlist of songs or movies mixed together contain enough random enough for OTP key material? Ok hypothetical scenario. Lets say I want to generate a lot of key material quickly for a one-time pad. This key material will be divided up and used for many different messages in the future.

I select 50-100+ songs out of a custom playlist of all my music. The music has been converted to basic Waveform Audio File Format (.wav). The music could be a mix of rock, pop, classical, techno etc just whatever I selected.
I extract every song's raw music data out into one big file and remove null bytes. Now I have a single big file with all of the song data in it.
I randomize all of the song data so all the song data is blended together into an unintelligible sequence of bits. The user can provide some input using their mouse/keyboard which will provide some entropy into the randomizing function.
I loop through all the data in the file, taking every ~7th byte (or bit) and put it into another file which is now my new key material. This step could be altered so the user can provide a variable sample rate, e.g. they can change it to every 10th byte or 100th byte.

Now... is that file of key material sufficiently random for one-time pad use?

What about if I changed out music songs and use 10+ full length movies or TV shows instead?

The bits are not independent from each other, at least within an individual song, so the pad is not truly random, thus this is not a one-time-pad. Perhaps a hash-based approach would fix this, but...

... there are a limited number of songs available, a simple attack would then be to enumerate every song (in the same format you describe) and try to decrypt a portion of the ciphertext (e.g. try bits 0 to 10, then try bits 1 to 11, etc... until you get something meaningful). Therefore the ciphertext can be broken by brute force, it is then not a one-time-pad by definition.

You'll notice your initial permutation had no effect on the efficiency of this attack. But even if it did, you must use some source of randomness to shuffle your song list, right? If you used a PRNG, someone could break that, and deduce the permutation you used. That's another dangerous "moving part". And if you had a true randomness source, then why not use it to create the pad in the first place?

Also, presumably you don't want to destroy your music after you've made it into a "one-time-pad", so your pad would also exist in its more explicit form on your hard drive -> big security risk (it considerably simplifies the attack above, as we now know exactly which songs to try to decrypt the ciphertext with).

Bits are bits, and entropy is entropy. It doesn't matter whether the data represents music or TV shows - those are human concepts whereas theoretical cryptography is intrinsically an abstract science.


Initialization vector in symmetric-key encryption Can we use symmetric-key algorithms without an initialization vector?

I am making an app where both the sender and receiver share a key and there is no way to create an initialization vector for each encryption. So I was thinking about setting the initialization vector to NULL while encrypting. Am I allowed to set the IV to NULL or can I use symmetric-key algorithms without an initialization vector?

If you really can't use an IV (why?), then just about the best thing you can do is use something like SIV mode (RFC 5297).  SIV is a "maximally misuse-resistant" authenticated encryption mode which provides the following characteristics:

If every message is tagged with a unique nonce, SIV provides full IND-CCA2 security (up to the usual limits; i.e. it still leaks the length of the message).
Without a nonce, SIV remains IND-CCA2 secure as long as the same message is never encrypted twice (with the same associated data, if any).
If a message is encrypted twice without a nonce (or with an accidentally reused nonce), the only thing an attacker can learn is that those two messages are the same.

The down side of SIV mode is that it's a two-pass encryption mode: the encryption code must process the message twice.  Thus, it is best suited for fairly short messages that can be held entirely in memory.  Basically, on the first pass, SIV computes a secure message authentication code of the plaintext and any associated data (including the nonce, if provided); on the second pass, the message is encrypted using conventional CTR mode encryption, with the MAC from the first pass used as a "synthetic IV" (whence the name of the mode).

Also, to allow the message to be decrypted (and its authenticity verified), the 128-bit MAC/IV must be transmitted along with the message.  Thus, SIV adds an unavoidable 16-byte overhead to each message, and is therefore not suited for format-preserving encryption.  Of course, the same is true of every authenticated encryption mode, and indeed of every mode capable of providing semantic security, whether authenticated or not.


Does changing the random number selected for each message increase security in Schnorr's scheme? I was reading about Schnorr's scheme and in that for signing the signer generates a random

number and continues with his operation. I am trying to implement this in a scenario where

the signature length is small and the number of possible messages is also very small.

Is generating a random number and signing, for each message also a good option in this case?

A small message space is no problem and I do not really know what you mean by "signature length is very small".

However, it is not only a good idea to choose independent and fresh randomness for every signature, it is (as Alex mentioned in his comment) necessary. Otherwise anyone who gets two signatures of you computed with same randomness for different messages can extract your private signing key with overwhelming probability.

I'm using the notation from the Wikipedia article of Schnorr signatures.

Assume you have two signatures $(s,e)$ and $(s',e')$ for two messages $M\neq M'$. Using the same randomness means that $r=r'$ (since $k=k'$) and since $M\neq M'$ in practice we will have that $s\neq s'$ ($H$ is a secure cryptographic hash function and would need to collide).

Now, we know that $s\equiv k-xe \pmod q$ and $s'\equiv k-xe' \pmod q$.

Consequently, since $k$ (the randomness) is identical for both signatures, we have that

$s+xe \equiv s'+xe' \pmod q$ and thus $s-s' \equiv x(e'-e) \pmod q$ and thus

$x\equiv (s-s')(e'-e)^{-1} \pmod q$.

Ignoring the very unlikely cases where $s-s'$ and $e'-e$ are $0$, and since $(e'-e)^{-1}$ thus always exists, the attacker can extract $x$, which is the private key.

So, when using Schnorr's signature, it is essential, that the value $k$ is chosen independently and randomly for every signature such that these "randomness collisions" do not happen.

All ElGamal type signatures (such as DSA/ECDSA) suffer from the same problem when re-using the randomness $k$ and actually this is what doomed Sony's private key back in 2010/2011 (i.e., they re-used $k$ over different signatures).


Multiple sender single receiver Encryption I had this article given to me by my teacher, and I would like to enhance it.
It's titled Modified El Gamal Algorithm for Multiple Senders and Single Receiver Encryption.
I planned on having the algorithm accommodate multiple senders and receivers.

But I got really confused, and I would like to ask for some help in the encryption part of this modified algorithm.

[Key Generation]

receiver generates {P,g,a}, and sends {P,g,b} to public(?) for the senders to get.
P = prime
g = generator
a = private key of receiver
b = g^a

[Encryption]

Sender 1
generate R1 (private key)
computes c11 = g^R1

Sender 2
generate R2 (private key)
computes c12 = g^R2

Sender 3
generate R3 (private key)
computes c13 = g^R3

Message(m) is encrypted using this formula:

c2 = m*b^R2 / b^R1*b^R3

The cipher keys {c11,c12,c13,c2} are then sent to the receiver.

[Decryption]

m = c2*c11*c13 / c12

I would like to ask: how did the other senders get hold of the private keys of the other senders? I think I'm missing something.

They do not share their private keys, but they do have to share b^R(i) for each sender i.

What they might do is, the first sender supplies mb^R(1), the second will supply mb^R(1)^R(2) and so on for the numerator round (two rounds). To do this they need to come together (in your paper there is, "Simultaneously, the senders compute for the value of c2 using the formula...").


Berlekamp-Massey algorithm: case when sequence length is less than double the length of the LFSR Suppose that we have a sequence of $N$ digits which is produced by a Linear Feedback Shift Register (LFSR) and the shortest such LFSR is of length $L$. A very important tool in cryptanalysis of stream ciphers (among many other things) is the Berlekamp-Massey algorithm; if $2L\leq N$, this algorithm will produce the unique shortest LFSR of length $L$ that generates the given sequence.

I just knew this as a fact but never really gave a look at the algorithm. Now I'm reading the paper by Massey that presents the algorithm and I was kind of surprised to realize that the algorithm returns a desired LFSR in any case, even if $2L>N$, however in that case we don't have a unique LFSR that generates the sequence, but $2L-N$ of them (in the binary case).

So why do we always refer to the Berlekamp-Massey algorithm only for the case when $2L\leq N$? Practically speaking, what kind of lengths $L$ do we use in cryptosystems, and can the algorithm be used when $2L>N$ and $N$ is "reasonably" close to $2L$? Or is the algorithm useless in that case regardless?

The Berlekamp-Massey algorithm find the shortest LFSR that can produce the given sequence.
Formally, if the sequence has $n$ elements $S_0, S_1, \ldots, S_{n-1}$, then the
algorithm finds $\lambda_1, \lambda_2, \ldots, \lambda_t$ such that for
$i = t, t+1, \ldots, {n-1}$, the following equation holds:
$$
S_{i} +S_{i-1}\lambda_{1} + S_{i-2}\lambda_2 + \cdots + S_{i-t}\lambda_t = 0,
\tag{1}
$$
that is,
$$S_i = -\bigr(S_{i-1}\lambda_{1} + S_{i-2}\lambda_2 + \cdots + S_{i-t}\lambda_t
\bigr).
\tag{2}$$
Note that for $i=t$, we have
$$S_{t} = -\bigr(S_{t-1}\lambda_{1} + S_{t-2}\lambda_2 + \cdots + S_{0}\lambda_t
\bigr)\tag{3}$$
The idea is that the initial loading of the LFSR is $(S_0, S_1, \ldots, S_{t-1})$,
and the weighted sum of the LFSR contents stated in $(3)$ is fed back
into the right end of the shift register as the LFSR contents shift one place
to the left. Thus, the new state of the LFSR is $(S_1, S_2,\ldots, S_{t-1}, S_t)$. In later clock cycles,
the LFSR will contain $(S_{i-t}, S_{i-t+1},\ldots, S_{i-1})$, the feedback
will compute $S_i$ as given in $(2)$ and so the new state of the LFSR
is $(S_{i-t+1}, S_{i-t+2},\ldots, S_{i-1}, S_i)$.  The output of the
LFSR is the symbol falling off the left end and is thus $S_0, S_1, \ldots, S_{n-1}$.

The dsp.SE reader will recognize that if we define polynomials
$$S(z) = S_0 +S_1z + \cdots + S_{n-1}z^{n-1}, ~~
\Lambda(z) = 1 + \lambda_1z + \cdots + \lambda_tz^t,$$
then the left side of $(1)$ is the coefficient of $z^i$ in the
product $S(z)\Lambda(z)$. Thus, the product $S(z)\Lambda(z)$
contains no terms of degree $t, t+1, \ldots, n-1$.

Turning to the problem at hand, if the given sequence can in fact,
generated by a LFSR of length $L$ (where $L$ is the length of the shortest
LFSR capable of generating $S(z)$), and if $n \geq 2L$, then
the Berlekamp-Massey algorithm will find the feedback coefficients
$\lambda_1, \lambda_2, \lambda_L$ of the unknown LFSR as soon
as it has examined the first $2L$ terms $S_0, S_1, \ldots, S_{2L-1}$
of the given sequence. It will then process the remaining terms
$S_{2L}, S_{2L+1}, \ldots, S_{n-1}$ of the sequence, and will discover
that the same LFSR that it has
already found will generate these remaining terms as well.

It is important to remember that the Berlekamp-Massey algorithm
will find the shortest LFSR that will generate
$(S_0, S_1, \ldots, S_{n-1})$, and this LFSR
might not be the same one
that was actually used to generate $(S_0, S_1, \ldots, S_{n-1})$.
Any sequence that can be generated via a LFSR with feedback polynomial
$\Lambda(z)$ can also be generated via a (longer) LFSR with feedback
polynomial $\Lambda(z)\Psi(z)$, and the Berlekamp-Massey algorithm
will find the shortest shift register that works.

What if $L$ is such that $2L > N$, then the Berlekamp-Massey
algorithm will find the shortest LFSR that will generate
$(S_0, S_1, \ldots, S_{n-1})$. The length of this LFSR
will generally not be $L$ and its feedback coefficients will in
general not be the same as those of the actual LFSR
that was used to generate the sequence. If at a later time,
the terms $S_{n}, S_{n+1}, \ldots, S_{2L-1}$ become known,
the algorithm will extend the LFSR and ultimately come up
with the right answer, but for now, it will simply find
the shortest LFSR that will generate
$(S_0, S_1, \ldots, S_{n-1})$.

In broad terms, the Kolmogorov-Chaitin theory of complexity
of a sequence
says that for almost all sequences of length $n$, the shortest
program that can print out the sequence has length $n+c$ where
$c$ is a constant. In other words, for most sequences, one can do
little better than simply store the sequence in memory and print it out: there
are no computational methods that will allow you to generate
the sequence via calculations. Thus, given an arbitrary sequence
of length $n$, the Berlekamp-Massey algorithm will typically
find an LFSR of length $n-1$ that stores the first $n-1$ symbols
and then calculates $S_{n-1}$ via $(2)$ with $t = i = n-1$.

The answer to the OP's question

  "...can the algorithm be used when $2L>N$ and $N$ is "reasonably" close to $2L$?"

is that the algorithm can be used, and it will find the
shortest LFSR
that will generate  $(S_0, S_1, \ldots, S_{n-1})$, but
this LFSR will typically not be of length $L$ and
the feedback polynomial will typically differ from
that of the LFSR of length $L$ that is known to
generate $(S_0, S_1, \ldots, S_{n-1})$.


Does EAX use the same keys for encryption and authentication? I am actually checking use of EAX AEAD mode, and following EAX spec review (scheme definition for my part), my question is: what about the derivation of the authentication and encryption keys? In the described scheme  the same input key $K$ appears used on all
   OMAC (authentication) & CTR functions. Did I miss something important
   as it would be surprising that the requirement of distinct
   authentication/encryption keys is not respected with EAX ?

I also have two other questions, but of less importance:

When comparing with GCM, I noted that C/AD length parameters are not
taken into account in MAC calculation. Does it have real importance
for security (message extension attack)?
Initial counter ICB for CTR function results from one OMAC operation;
so as ICB LSBits are not set to 0 value, it means to    handle
incrementation of a 128 bits word at each block cipher call by    CTR
function?

The same key is indeed used in EAX to key both the CTR mode and the underlying OMAC (which is actually used in 3 distinct phases: randomising the CTR nonce, authenticating the Additional Authenticated Data, and authenticating the Ciphertext). This is explicitly acknowledged in the security proof.

Where EAX differs from a naive reuse of the key is that it initialises each use of OMAC with a distinct parameter, and initialises the CTR mode cipher with one of the OMAC outputs, effectively randomising that as well. The security proof of this single key approach is (to quote the authors) "novel and involved" and "surprisingly complex", but seems to have stood up to peer review.

It's worth noting that in the EAX paper, 3 modes are actually defined:

EAX2 is a general composition method for combining a cipher and a MAC to produce an authenticated cipher using two keys Key1 != Key2.
EAX1 is a composition of EAX2 with one Key == Key1 == Key2
EAX is a composition of EAX1 with CTR and OMAC

The security proofs in the EAX paper are provided for EAX2 and EAX, but not EAX1 (the proof of EAX relies on the properties of OMAC, and so doesn't extend to general use of EAX1).

The lengths of the Ciphertext and AAD are not explicitly handled in EAX, which allows EAX to operate as an online mode (processing data as it arrives without buffering more than one block).
The authentication in EAX is simply processing the entire sequence of AAD and Ciphertext with OMAC, and the security proof for that (and any other secure MAC) naturally excludes any message extension attacks - any message extension resulting in the same MAC would be a forgery, and instantly invalidate the scheme as a secure MAC.

CTR mode has to handle incrementation of the nonce/counter value in any implementation - the starting value of the counter is arbitrary (and in the case of EAX pseudo-random). This isn't difficult (BouncyCastle for example does it in one line of code).


how hashing algorithm is shared in public key I am reading about public key working at following linkenter link description here

Here picture is provided

My question is how hashing algorithm is shared between sender and receiver?

First: This picture is wrong.  Signature is not encryption with the private key.  Encryption with the private key is a category error; it doesn't make sense.  This suggests to me that whatever source you are reading is likely to be full of confusing misinformation.

That said: The signer and verifier have to agree in advance what signature scheme to use, which entails a choice of hash function.

In brain-damaged protocols, the signature or metadata around it specifies which signature scheme to use (including the choice of hash function), and the verifier will happily use it.  This means that a forger can pick any weak signature scheme that the verifier supports—including completely nonsensical ones, like none, or the secret-key HMAC-SHA256 when the signer meant to use the public-key RSASSA-PSS—and persuade the verifier to use it, against the wishes of the signer.

In your system, in order to avoid leaving a trail of devastation and screaming cryptographers in your wake like JWT did, you should have the verifier store alongside the public key (not the potentially forged document!) whatever metadata you need to specify a particular signature scheme for that public key.  For example, in x.509 certificates, alongside the public key there is a field specifying what cryptosystem the public key is meant for.  Then there is no need for the signature to control which signature scheme the verifier uses: the verifier already knows for each public key which one to use.

As a simplification, you can just use a single signature scheme in your application, Ed25519, and never reuse keys in your application for any other purpose.  Then there's no need for any metadata.  If you ever need to replace the signature scheme, just replace the keys too.


AES MixColumns using L and E lookup tables I am trying to verify the multiplication by $\mathtt{02}$ in Galois Fields for MixColumns function using the L and E lookup tables. I could verify $\mathtt{D4}\cdot\mathtt{02}=\mathtt{B3}$ by manual calculation and using the lookup tables. However, I can't verify $\mathtt{87}\cdot\mathtt{02} = \mathtt{15}$ using the lookup table. Using the L table, $74 + 19 = 93$. Look up the E table for $93$ and it is $\mathtt{3D}$.
Where am i going wrong?

Link to lookup tables: Page 8 of this document.

The values in the tables are listed in hexadecimal; hence the Log table maps $\mathtt{87}$ to $\mathtt{0x74} = 116$.  Similarly, it maps $\mathtt{02}$ to $\mathtt{0x19} = 25$, and $(116 + 25) \bmod 255 = 141 = \mathtt{0x8D}$; looking up $\mathtt{8D}$ in the Exp table gives us... $\mathtt{15}$ (actually, $\mathtt{0x15}$).


DHE_RSA master secret computation? When using DHE_RSA, the prime $p$, the generator $g$ and the public keys $A$ and $B$ are transmitted in plain text. If I know the private key of the server $a$, I can calculate $k=B^a\ mod\ p$ to receive the pre master secret (correct me if I'm wrong). According to RFC 5246, this pre master secret is then combined with some random values sent in the server and client hello messages and hashed to receive the master secret.

Now, my question is how this calculation of the master secret is done in practice (which hash function is used, how are the parameters combined,...).

It's performed using the PRF, as indicated by the RFC specifying the TLS 1.2 specification you pointed to. The PRF is identified by the cipher suite - commonly as last part of the cipher suite string.

How the PRF works is specified by section 5 of the TLS 1.2 specification:

  In addition, a construction is required to do expansion of secrets
     into blocks of data for the purposes of key generation or validation.
     This pseudorandom function (PRF) takes as input a secret, a seed, and
     an identifying label and produces an output of arbitrary length.

And the specification then says:

 master_secret = PRF(pre_master_secret, "master secret",
                      ClientHello.random + ServerHello.random)
                      [0..47];

followed by:

key_block = PRF(SecurityParameters.master_secret,
                  "key expansion",
                  SecurityParameters.server_random +
                  SecurityParameters.client_random);

after which the output key_block is split into the session keys required.

So the entire spec relies on the PRF, which relies on the iterated P_hash, which relies on HMAC_hash which relies, finally, on a secure hash such as SHA-256. Otherwise it is just concatenation and splits of octet string (also known as byte arrays). I won't copy the algorithms here, they are well described in the TLS specification.

As it doesn't rely on any other cryptographic primitives the cipher suite string simply lists the hash function used as configuration parameter for the PRF, for instance SHA-1 in TLS_RSA_WITH_AES_128_CBC_SHA and of course SHA-256 in TLS_RSA_WITH_AES_128_CBC_SHA256, both from appendix C of the specification.

Note that the DH handling of TLS 1.2 is a bit strange in the fact that it uses the minimal size encoding of the DH result as pre_master_secret. Generally the output of DH Is considered static, and of the same size as the prime field (i.e. 1024 bit for 1024 bit DH). So you should not left-pad with zeros for TLS 1.2. This has been fixed in TLS 1.3 draft specification (to be precise after I mentioned it in the mailing list, in draft 13).

Note that the generation of keys using the PRF is generally known as (key based) key derivation. The PRF is therefore used as TLS-specific Key Based Key Derivation Function or KBKDF.


Diffusion in a block cipher? For a given block cipher, I would like to verify if any input word diffuses to all output words.

For example in Twine block cipher, they define diffusion as "every output word is dependent of every input word".

How can we check by the program? Is there any algorithm or program to test this property?

I couldn't write a computer program for that. Any help or reference would be appreciated.

In order to assert the diffusion of a block cipher you need to show that every bit of the output depends on every bits of the input. This can be done by hand when the block cipher is not too complex.

A simple case: AES

AES you can see that a difference in a word will be propagated into the full block after 2 rounds (look at the $\star$).

This proves the word diffusion, now you need to prove that the S-box is actually safe. In other word show that any bits in the input have an influence on any bits in the output of the S-box (testing for differentials cryptanalysis is one of the way to do it).

A more complex case: Twine

Twine uses a 16 branches  Feistel network with a round function. This round function uses multiple logical operations: $\lor, \land, \oplus$.

In order to show the bit dependency, we could take the code of the block cipher, and replace every of these 3 logical operators by $\lor$. We could also replace all the 4-bits S-box by a direct transposition to $15$ or $0x1111$ in binary.

Using a null input where only 1 bit is flipped (thus in the case of Twine, 64 test), and passing it through the modified, we verify that  all the output bits are set to 1.

Also note that the bitwise shift << >> and rotations <<< >>> are preserved.

This approaches guarantees that any bits in the output depends of every input bits.

However we modified the S-box, therefore it is left to prove is that these S-box also have a nice diffusion using differential cryptanalysis for example.

This approach is the same as the one presented in this analysis of MD5.


64 DES full example with all the stages I'm trying to write a code to perform encryption and decryption of 64-bit DES but I'm having a problem in verifying that my code is working correctly. My graduation project is about DES crypt-analysis so I'm trying to implement DES to generate the pairs used in the attack.

Can anyone give me an example on encryption of DES with all stages?

For instance, I would like to see the key schedule and the values of all 16 round keys generated by the input key.

Might I suggest the "DES cipher internals in Excel" page by Nayuki? Because everything's in Excel, all the internal values are openly displayed.


How should I read these three-dimensional (pseudo)random-generated numbers representations? Visiting this site: http://lcamtuf.coredump.cx/oldtcp/tcpseq.html#phase

I found graphical representations of random-generated sequence numbers, but I can't figure out how to interprete the plots.

Taking as example OpenBSD:

and the Windows NT4 SP3 distribution:

I can't understand why the ISN guessing attack feasibility is higher for the Windows NT4 SP3 one (attack feasibility: 97.00%) and lower for the "cube" of windows 2000 one.

I would expect to be the Windows NT4 the less easy to attack because in its distribution the points seems to be better distributed respect to the "cube" of Windows 2000 distribution.

Looking at the site I read that this a three-dimensional representation with these definitions for $x,y,z:$

$x[t] = seq[t]   - seq[t-1]\\
y[t] = seq[t-1] - seq[t-2]\\
z[t] = seq[t-2] - seq[t-3]$

Where $t$ seems to be the time at which we pick the sequence number

But, given this, I can not understand how points plotted are related: for example, what I should think about two near (respectively: far) points? are sequence numbers with low differences or high differences?

One of the key properties we want out of PRNGs is that they produce results that follow a desired probability distribution.  Nearly all of the time we want our PRNGs to produce data with uniform distribution—all of the possible output values should have equal probability.

So let's assume that we are given a seq sequence whose values are samples drawn from a uniform distribution.  We can now ask: what should be the distribution of the x, y and z sequences?  Well, since they're defined as sums of values drawn from a uniform distribution, this is the same sort of distribution we get from throwing a pair of dice and adding their results, where a 7 is six times more likely than a 2.  So the distribution we should ideally see in that page's data is:

A cube with a hard boundary (just like we can't roll a 1 or a 13 from the dice);
Centered around (0, 0, 0) (because the expected value of the subtractions is zero);
Denser toward the middle and sparser toward the boundary (just like throwing a seven is more likely than a two).

The Windows NT SP3 graph very obviously deviates from that pattern:

  I would expect to be the Windows NT4 the less easy to attack because in its distribution the points seems to be better distributed respect to the "cube" of Windows 2000 distribution.

What you should be thinking of is how closely does the distribution resemble the "ideal" one for the scenario in question.  This is the approach that I took above:

I picked uniform distribution as the ideal for sequence numbers;
And from that it follows that I must pick the "dice roll" distribution as the ideal for x, y and z.

Then, any significant deviation from the ideal distribution should be seen as a potential flaw.  Why?  Because non-ideal distribution means that some values are more likely than they ought to be, and thus that the attacker will succeed faster than they ought to by trying such values first.

  But, given this, I can not understand how points plotted are related: for example, what I should think about two near (respectively: far) points? are sequence numbers with low differences or high differences?

The magnitude of the distances between points isn't important.  What's important is whether those distances are predictable at a higher-than-chance success rate.  And this gets to the heart of the attacks they're analyzing here.  By looking at the distributions of the differences they are able to build models that predict the ISNs for various operating systems with better-than-chance success rates.

Finally, look at your definition of seq and notice that the differences in question are between the elements of consecutive quadruples of the ISN sequence.  If these differences are highly predictable, what it tells you is that you can easily guess the next sequence number just from knowing the previous ones, by guessing the next differences and adding them to the recently observed ISNs.


server side Javascript security It is accepted that the javascript library lacks the ability to create an adequate PRNG. My understanding that this was mainly due to the limits of a sandboxed browser enviroment that javascript resides in.

Is this correct? Can server side javascript generate provably secure cryptography due to system wide access?

I have developed an interest in node.js specifically.

As far as I know, there's no fundamental obstacle that would prevent you from implementing any crypto algorithm you want in JavaScript, whether on the server or the client side.
Compared to an optimized implementation written in C or assembly, JavaScript implementations of low level crypto primitives like block ciphers or PRNGs are likely to be slow and hard to secure against side channel attacks (although there are ways to do that, especially if you know the CPU and interpreter the code is going to run on), but they'll still work.

The big problem with doing crypto in JavaScript on the client side is that, unless you use a secure channel like HTTPS to deliver the code to the client, you have no guarantee that the code the client receives and runs is the same as the code you sent from the server.  And if you do use HTTPS, you might as well just use it to send the data securely to the server, without any need for doing client side JavaScript crypto.

(That said, there are some rare cases where doing crypto even in client side JavaScript might make sense.  For instance, in some cases, you might want to require the client to submit a proof of work before requesting an expensive operation from the server in order to guard against denial of service attacks.  Alternatively, some expensive crypto operations, such as key stretching, can be safely and usefully offloaded to the client entirely (although you should still hash the client-submitted key with a conventional hash function before using it).

However, in both cases, the slowness of JavaScript crypto implementations provides an unwelcome advantage for attackers, who would presumably not run the actual JavaScript but instead reimplement the algorithm in a faster language.  This is one use case where the proposed Web Crypto API might actually be useful, by providing access to fast native crypto primitives from JavaScript.)

In any case, the issues with secure code delivery don't apply to server side JavaScript, since there's no untrusted network over which the code would need to be sent.  However, the performance issues with doing low-level crypto operations in JavaScript are certainly still present, unless your server JavaScript interpreter provides some API to let your JavaScript code make use of fast native crypto primitives.


Building a pad for OTP on-the-fly with Diffie-Hellman Through repeated DH attempts, could Alice and Bob build a large random key for use as a one-time pad? My intuition is that this protocol would be as hard as breaking DH (discrete logarithm).

Through repeated DH attempts, could Alice and Bob build a large random key for use as a one-time pad?

No, since that is not how a one time pad works. You can use your idea to create cryptographic material to encrypt plaintext using XOR, what you are describing is an asymmetric stream cipher of some sorts.

A one time pad requires an "offline" exchange of key material. A one time pad when used properly is unbreakable, whereas a DH exchange can be broken or potentially maliciously interfered with. Using this idea may potentially expose a weakness in the PRNG used to generate the private keys, but that same problem is applicable to whatever is generating a true OTP. I this case however, the public key exchange may expose this weakness much earlier than an offline key exchange, as no ciphertext would be needed.

This idea may be significantly faster than an offline key exchange, but that depends on how much key material needs to be created. In your example, the shared secret would generally be passed through a hash function to distribute entropy more evenly over the bits, or possibly reduce the size of the shared secret so the entropy per bit is higher.


Zero knowledge proof protocol example? Alice is color blind.  She never knows if her gloves are matched.  Her
  brother Bob always   teases her saying her gloves are mismatched and
  she should go change them.  Alice wants to  know if Bob is telling the
  truth about her gloves.

  Assuming Alice only has 2 colors of gloves, how can she design a
  protocol that she can use  with her brother to determine if Bob is
  being truthful or just teasing her?

I would assume that Bob decides at the beginning whether to tease or be honest. If teasing, he chooses his response at random.

My intuition tells me this problem is similar to the coin toss over the phone problem... but I can't seem to create a scheme where Alice would know if he was telling the truth is she has no way of verifying?  Any help would be appreciated as I'm studying for finals!

This is a classical example.

Here is the proof system…

Bob gives two gloves to Alice so that she is holding one in each hand. Bob can see the gloves at this point, but Bob doesn't tell Alice which is which. Alice then puts both hands behind her back. Next, she either switches the gloves between her hands, or leaves them be, with probability $1/2$ each. Finally, she brings them out from behind her back. Bob now has to "guess" whether or not she switched the gloves.

By looking at their colors, Bob can of course say with certainty whether or not Alice switched them. On the other hand, if they were the same color and hence indistinguishable, there is no way Bob could guess correctly with probability higher than $1/2$.

If Bob and Alice repeat this "proof" $t$ times (with a large $t$), Alice should become convinced if the gloves are indeed differently colored; because if they would have the same color, the probability that Bob would have succeeded at identifying all the switch/non-switches is at most $(1/2)^{t}$.

(Furthermore, the proof is "zero-knowledge" because Alice never learns which gloves have what color; indeed, she gains no knowledge about how to distinguish the gloves… but the proof system helps her.)

In case anyone has problems understanding zero-knowledge proofs, I would like to point to “Zero-Knowledge Technique (PDF)” (PDF) which contains a colorblind example similar to mine, as well as a few more examples explaining ZKP, including the example by Jean-Jacques Quisquater which has been published in “How to Explain Zero-Knowledge Protocols to Your Children” (PDF). That should help…


Formula for the number of expected collisions Say we have a hash function that produces $n$ bit outputs. From the birthday problem that after around $\sqrt{2^n}$ different inputs to the has function, we can expect a collision.

Say instead that we have $m$ outputs. How many collisions can we expect in those $m$ outputs?

If there are $k$ inputs that all have the same output, we say there are $\binom{k}{2}$ collisions.

The expected number of collisions (assuming that the hash function can be modeled as a random function) is precisely $2^{-n}\binom{m}{2}$; that is, the expected number of pairs of values $x \ne y$ with $H(x) = H(y)$ (and so, to answer Ricky's question, $H(x) = H(y) = H(z)$ would count as three collisions).

The reasoning is the obvious one; there are $\binom{m}{2}$ separate pairs, and each pair has a probability $2^{-n}$ of colliding (and hence has an expected number of collisions of $2^{-n}$), and the expected sum of a set of probabilistic values is the sum of each individual value's expectation.  The probabilities are not independent (for example, if $H(x)=H(y)$ and $H(y)\ne H(z)$, we know that $H(x) \ne H(z)$); it turns out that the expected sum doesn't depend on independence.


Ring-LWE elliptic gaussian distribution I am currently trying to understand this Ring-LWE article: http://www.cims.nyu.edu/~regev/papers/ideal-lwe.pdf and I have a question.

Firstly, it is mentioned in the paper that we can view the elliptical Gaussian distributions $D_{\textbf{r}}$ (which are initially defined on $H$) as distributions on $K_{\mathbb{R}} =K \otimes_{\mathbb{Q}} \mathbb{R}$. Even though there isn't any explicit isomorphism mentioned there, I believe that $\varphi:K \otimes_{\mathbb{Q}} \mathbb{R} \to H$, $\varphi(x \otimes a) = a\sigma(x)$ makes sense in this context.

What I dont understand is the claim that the distribution $x \cdot D_{\textbf{r}}$ is equal to $D_{\textbf{t}}$, where $t_i =r_i \cdot |\sigma_i(x)| $, where $x \in K$. What I obtained is the following:
if $x\in K$ and $y\in H$, $y=\sum_{i=1}^n y_i h_i$ (distributed $y \sim D_{\textbf{r}}$), then

(EDITED formula)
$$xy= \sum_{i \in [s_1]} y_i \sigma_i(x)h_i + \sum_{i \in [s_2]}(y_{s_1+i}\cdot Re\sigma_{s_1+i}(x) - y_{s_1+s_2+i}\cdot Im \sigma_{s_1+1}(x)) h_{s_1+i}) +\sum_{i \in [s_2]}(y_{s_1+s_2+i} \cdot Re \sigma_{s_1+i}(x) + y_{s_1+i} \cdot Im \sigma_{s_1+i}(x))h_{s_1+s_2+i}$$
Basically I obtained the coefficients of $xy$ in base $\{h_1,h_2,\ldots,h_n\}$, and they dont seem to follow gaussian distributions with parameters $t_i = r_i \cdot |\sigma_i(x)|$ (except for the first $s_1$ of them)

Can anybody shed some light on this one ?

(I am one of the authors of the paper you're asking about.  The isomorphism $\varphi$ you wrote is the intended one.)

The key observation is that a Gaussian $D_r$ of parameter $r$ over $\mathbb{C}$ is "spherical," i.e., it is the sum of independent Gaussians (both of parameter $r$) for the real and imaginary components, and so is invariant under rotations of the complex plane.  Therefore, $x \cdot D_r$ equals $D_{|x| \cdot r}$ for any $x \in \mathbb{C}$.

The claim then follows by the fact that multiplication in $K$ corresponds to coordinate-wise multiplication in the real/complex components of $\sigma$.  That is, the distribution of $x \cdot D_{(r_1,\ldots,r_n)}$ for $x \in K$ is just $D_{(|\sigma_1(x)| \cdot r_1, \ldots, |\sigma_n(x)| \cdot r_n)}$.  (Note that the conjugate symmetry of the pairs of complex embeddings is preserved, as needed.)


Messages of different lengths and one-time computationally-secret I'm preparing myself to exam, but I have a lot of troubles with rigorous proofs.

  Let $\Pi=(Gen,Enc,Dec)$ be an efficient secret-key encryption scheme that is not fixed-length. That is, for any $n$ and any $k \leftarrow Gen(1^n)$ the encryption algorithm $Enc_k(\cdot)$ can encrypt arbitrary length messages $m \in \lbrace 0, 1 \rbrace^*$.

  Prove that $\Pi$ cannot satisfy definition of being one-time computationally-secret when the adversary $\mathcal{A}$ in $PrivK^{eav}_{\mathcal{A}}$ may output messages $m_0$ and $m_1$, that are NOT of the same length.

I just can (I think so) start this proof - if $Enc_k(\cdot)$ is some PPT algorithm, then there exists a polynomial $p(x) \in \mathbb{Z}[x]$ such that

$\forall n,k \leftarrow Gen(1^n), m \in \lbrace 0, 1 \rbrace^*: ||Enc_k(m)||<p(||k||+||m||)$.

Unfortunately I have no idea how to do the rest of the proof - by contradiction, or not? If you could help me with the rigorous proof, I'd be really grateful for your time.

P.S. Reminder (one-time computationally-secret).

  An (efficient secret-key) encryption scheme $(Gen,Enc,Dec)$ is one-time computationally-secret if for any PPT adversary $\mathcal{A}$ it holds that $Pr[PrivK^{eav}_{\mathcal{A}}(n)=1]-\frac{1}{2}$ is negligible function, where $PrivK^{eav}_{\mathcal{A}}(n)$ denotes the output of the following experiment:

  (a) The adversary $\mathcal{A}$ on input $1^n$ outputs a pair of messages $m_0,m_1$.

  (b) Let $k \leftarrow Gen(1^n)$ and let $b \in \lbrace 0,1 \rbrace$ be chosen uniformly at random. Then a ciphertext $c \leftarrow Enc_k(m_b)$ is computed and given to $\mathcal{A}$.

  (c) $\mathcal{A}$ on input $c$ outputs a bit $b'$.

  (d) The output of the experiment is $1$ if $b'=b$ and $0$ otherwise.

This is already explained well, at a conceptual level, at a different question: Why is a non fixed-length encryption scheme worse than a fixed-length one?

To turn it into a formal proof, write down an adversary $A$ that breaks the security of $\Pi$.  You may want to first work out the attack at a conceptual level to make sure you are clear on how to attack $\Pi$; then review the definition of what it means for an adversary to break $\Pi$; then turn your conceptual attack into a fully specified algorithm $A$, and check that it does indeed break $\Pi$.


Looking at hash output – is Base64 encoding in any way better than HEX encoding? I was wondering why most "normal/unsafe" crypto hashes like SHA-256, SHA-512, Whirlpool, RipeMD-160, MD5, etc. are HEX encoded.

But most "secure" crypto hashes (KDF' ) like bcrypt and scrypt are Base64 encoded. Why?

somewhere I heared that Base64 shortend the string for like 20%. Isn't that extremely bad for password hashed during iterations and makes them less collision resistent?

And if Base64 is really for some reason more secure, then why does Argon2 output HEX encoding?

The algorithms themselves just output binary (i.e. bytes) if you read their specifications. It's the implementation in API's and applications that output the hexadecimals and/or base64.

Sometimes there are also ad hoc standards / common practice that specifies a certain output format. This is for instance the case for the output of the bcrypt password hashing algorithm. In that case it's not just the hash that is displayed but also the type of algorithm, number of iterations and if course salt.

Base64 is more efficient than hex, while hex is easier for humans to digest. The value of the bytes as well as the amount of bytes are just easier to see in hex; the amount of stored bytes is for instance simply half of the displayed hex digits. However for textual formats or indeed larger hash values base64 may be chosen for its efficiency (~33% overhead for base64 vs 100% for hex).

The command line utilities md5sum, sha1sum and their successors have always kept to outputting hex; it's to be expected that hex is therefore more likely to be output by applications that want to remain compatible.

Note that I've changed the case of the terms "Base64" and "HEX" in this answer to lowercase to be compatible with RFC 4648: The Base16, Base32, and Base64 Data Encodings which tries to standardize the encodings. It only uses the uppercase variant in the title. "Hex" is an abbreviation, not an acronym, so all uppercase does not make sense.

Personally I prefer all uppercase for hexadecimals; people recognize the upper part of letters / digits more easily, so it makes sense to use it as default (and on all my old computers the characters were also in uppercase, so they are in most debuggers).


Risks hashing salt + 5 - 8 number pin with PBKDF2 I have been tasked with putting a simple sign in experience in place where the user types in their ID and a 5 to 8 numeric value as the password or PIN as it is called here.

I am using ASP .NET Core and using Identity Server 4 as the core implementation for issuing tokens. I have to implement the login page and know the requirements to make a secure page/cloud system.

From my research, Bcrypt is the defacto hashing mechanism to use to perform this task, but I have a couple of concerns:

That if/when as they say in the security industry the system is compromised, with such a short PIN, even if we use a large salt, it will be very easy to calculate all of the PINs as there is technically only a small number of outcomes compared to free text passwords.
There is not a verified implementation of Bcrypt in .NET - ASP.NET Core uses PBKDF2 and as it is part of the framework, so with that I think I gains credibility here.

My default answer in these situations is to use Auth0/Azure AD B2C or some other huge company who does this stuff day to day and enforce complex passwords but the requirement is very specific and cannot be fulfilled by the operators out there.

I have done a risk analysis around this and presented it to the business which they accept, but the niggling questions here are:

is there anything more modern than PBKDF2 and verified that I should be using?
Are my concerns valid that the the passwords will be easy to crack if the systems data stored are compromised?
What auditing mechanisms would you recommend in a system like this?

Yes, look for example here. Consider using Argon2 for instance.
Yes, your concerns are valid. Password derivation should be slow enough. But in practice users cannot accept if login takes  longer than 1 sec. So the password derivation should take not longer than 1 sec. If a PIN consists of 5 digits, it means 100 000 different PINs. If every one takes no longer than 1 sec, an attacker needs not more than 100 000 sec to brute force it with a single core of CPU, means ~28 hours. In case of 4 core CPU it will take ~7 hours. With 8 digit PINs it will take longer. Roughly it can be about 28000 hours for single core CPU = 7000 hours for 4 core CPU = 292 days for such CPU. Means, if you have 10 CPUs, it will take less than 1 month to break it. With more CPUs the brute forcing will take even less time.
The question about auditing is out of scope on this site. Better is to ask it at Information Security site. But no matter what auditing you will implement, if an attacker obtains database with password hashes, he will brute force it, retrieve plain passwords, and then apply them. When some user complains that something is wrong with his account, auditing might help to track the attacker. But it can be that even finding the attacker will not help to mitigate the damage caused.


Advantage of attacker in CPA secure IBE In CPA secure IBE systems, the advantage of attacker (A) is defined as  absolute value of

$$Pr[b=b^{'}]-\frac{1}{2}$$

Can someone please explain this to me in a few words? Where exactly does that absolute value come from? And how common is this advantage in the realms of cryptography; meaning: how often is this attacker advantage to be considered in general?

Sometimes, to make it easier to understand, the advantage is multiplied by a factor of 2: $Adv = 2|\Pr[b' = b] - 1/2|$.

Note that when the adversary has no advantage in breaking the protocol, the only thing s/he can do is guessing $b'$ at random.  In this case, $\Pr[b' = b] = 1/2$ and thus $Adv = 0$.

When the adversary always correctly finds the value of $b'$, we have $\Pr[b'=b] = 1$ and thus $Adv = 1$.

Similarly, when the adversary always incorrectly guesses the value of $b'$, we have $\Pr[b'=b] = 0$ and thus $Adv = 1$.  Note that such an adversary is as powerful that an adversary who always guesses the correct the value.  It suffices to flip the result to get the same answer.

To sum up, the advantage is a value between 0 and 1 (or 0 and 1/2 with your definition).  The higher the value is, the more powerful the adversary is.

In practice, typically, a cryptographic construction is said IND-CPA secure if $Adv < 2^{-128}$.


RSA: How do I decrypt this? Sorry if this is asked a lot, I just don't know if there's a specific word for it.

I'm at uni and have a codebreaking exam in a few days, I don't have to do well in it but I want to do as well as I can, but this is really making me struggle.

Here is my work so far, everything's going alright:

Obviously when I try to do the bottom part, any calculator I use says it's invalid or infinite, I understand it's a crazy big number, but I have no idea how to work it out otherwise.

If you want to do it with hand calculator, you can use exponentiation by squaring, and compute the remainder after each multiplication. (instead of first computing huge powers and only then taking the remainder)


Can AES use PKCS#5 padding From What is the difference between PKCS#5 padding and PKCS#7 padding, I understand that PKCS#5 is defined for 8 byte block sizes. Does this rule it out as a padding option for AES since AES has a 16byte block size. I have seen some conflicting usages and would like to get a definitive answer

PKCS5 padding is a narrowly defined subset of PKCS7 as per its specification.
PKCS7 padding is identical to PKCS5 when applied to an 8-byte block only.

The PKCS5 specification is actually defined only for DES, not 64-bit block ciphers in general.

However, PKCS5 by specification MUST created an invalid padding string when applied to a block size that is longer than 8 bytes, and where more than 8 bytes of padding are needed, since it explicitly defines the value 8 for the block size and divisor in bytes. If 9 bytes of padding are required, PKCS5 will create only 1 byte of padding with a value of 0x01.

That being said, I would suspect most in the wild implementations of PKCS5 padding actually use the block size of the cipher used rather than the predefined value, and it is certainly possible that application of padding will not cause an error. This is not hard to test.

So yes, it does rule out PKCS5 as a padding option for AES, or for any block cipher with a non 64-bit block (and technically for anything not DES or 3DES), but may sometimes work anyway.


What are the practical limitations of Asymmetric encryption vs Symmetric encryption? I hear it commonly said that the advantages of Symmetric encryption are speed and no limit to the amount of data that can be symmetrically encrypted.

I also hear it commonly said that the advantages of Asymmetric encryption are security.

But theoretically, if I want to symmetrically encrypt a 1TB file, my algorithm is just going to break the 1TB file into smaller chunks, encrypt them, and spit out the cipher text.

Why couldn't I do the same with Asymmetric encryption?  AKA,  what are the practical limitations of using Asymmetric encryption for bulk encryption?

The advantage of asymmetric encryption is not security, it is capability. Asymmetric crypto provides completely different capability that you can't get with symmetric crypto. With symmetric encryption, you have to establish a key a priori. With asymmetric crypto, you can establish a key on the fly (granted you have to have trust in the public key, that it belongs to the party you want to interact with). With asymmetric crypto you often have digital signatures, establishing authenticity of data.

You mention the primary advantage of symmetric crypto in your question, speed.

So, to your questions:

  Why couldn't I do the same with Asymmetric encryption?

You could. You would first have to define how you are going to encrypt large amounts of plaintext. Do you build a > 1TB modulus? Absolutely not. Do you establish some sort of mode of operation? Sure, but then you have to prove security.

You also will likely want integrity checks like you would get with authenticated encryption or HMAC. How do you do that?

  what are the practical limitations of using Asymmetric encryption for bulk encryption?

Speed and the lack of trusted, well studied standards.


Why algorithmic symmetry is important in hardware implementation? In AES, the encryption and decryption functions ordered in a symmetric way, I mean the same order of functions are used inside the round structure of both encryption and decryption (subbytes, shiftrows, mixcolumn, addroundkey) (see The Design of Rijndael List 3.8 page 49) but how does it actually make the algorithm better in hardware implementation?

Symmetry is something that is inherent in the design of SPN ciphers.  It doesn't explicitly make the layout of the cipher smaller, but it definitely helps.  You also see this in AES-NI where you can pipeline AES so each round is an instruction as you can just put latches on the boundaries.  For Feistel Ciphers, or Simon at least, I just run the ciphers as asynchronous circuits because they do not integrate as well on a per-round into a traditionally synchronous processors (even if they are much smaller in layout).

In hardware, symmetry is generally desired so that your wires stick on the same layers.  You have a stack of metal, and you generally run Metal 1 (M1) one direction and Metal 2 (M2) in the other direction. You just pick a direction for the data to "flow" On smaller processes with metal patterning, you find that you are forced in direction, also M1A and M1B need to go to M2 to make connections.

This "flow" is what helps AES implement nicer in hardware because of the nature of 8 in to 8 out bits of the S-Box and MixColumns.

The layout of an XOR in 14nm SOI looks like the following:

The two different colours of blue are the metal 1 lines for the tile (M1A is light blue, M1B is dark blue). I use this same layout for all of my cells, so I have the data flow from the top of the tile down.  I interrupt the M1A lines to go to M2A, and M2B (they are thicker because of M3 via rules in case I go M1->M2->M3)


Alternatives to Diffie Hellman and other Public Key Exchange schemes I've been researching public key exchange algorithms. I am not a cryptography expert but I have a couple of questions on the subject that I can't resolve on my own.

Strictly concerning public key exchange methods, do many of these ideas exist? Dozens? Hundreds? I'm trying to understand if many exist that accomplish the idea of private key building in a public "space". I am aware that each would have various strengths and weaknesses, etc. Though I've found a handful of these ideas (Diffie, RSA) it is not clear to me if they are "rare" in a mathematical sense.
Would commercial value exist in creating a new method? To this end, is it a problem being pursued in the world today? (Classical computing - I am aware quantum is an academic direction at this time)

I realize that second question is maybe opinion based, and so I would just really appreciate any thoughts on the subject.

Strictly concerning public key exchange methods, do many of these ideas exist? Dozens? Hundreds?

You have to define "exist" more precisely. If you mean widely known and/or standardized primitives, there are the obvious classic cryptosystems such as DH, RSA, ECDH, which would make dozens probably too high of a number to use.

If you mean "exist at all", including the broken ones (as well as the non-broken ones), unpublished ones* by amatuer researchers, and even minor variants of other algorithms, etc, then surely there are at least dozens. Hundreds would be surprising if we are limited to only primitives that facilitate key exchange.

You might consider some algorithms to be variations of others - this could easily influence your count by a large amount. ECDH and DH are an example. In that case, you'd be probably be interested in what different problems and assumptions are used in cryptosystems, and it would probably reduce your count back down to the order of a dozen or so at the most.

  Would commercial value exist in creating a new method?

Almost certainly not, at least in the direct and immediate sense. Cryptographic algorithm design is a poor business strategy, because you are competing with widely used, freely available, efficient, standardized algorithms. Unless you come up with something new that nobody else has but everyone wants, patenting your algorithm will probably just ensure that nobody uses it.

You could create specialized hardware for performing your algorithm very quickly or with very little power and sell or license that. But unless your algorithm is standardized and widely used, it is unlikely that it will receive much/any attention.

  To this end, is it a problem being pursued in the world today? (Classical computing - I am aware quantum is an academic direction at this time)

NIST's call for Post-Quantum algorithms actually just concluded. So research into it is indeed big at the moment, but if you are were hoping to design an algorithm and have it standardized, you probably just missed your chance.

For the curious, there were 59 KEM/PKE schemes submitted to NIST (according to the previous link).

*Disclaimer: This is my personal github, it just so happens to illustrate my point quite nicely


Lower Bound on the Probability an LWE Matrix is Primitive For positive integers $q, n, m>n$, how do we derive the lower bound $Pr[A\cdot \mathbb Z_q^m = \mathbb Z_q^n] \geq 1 - \frac{1}{q^{m-n}}$ for a uniformly random matrix $A \in \mathbb Z_q^{n \times m}$?

I know this probability is equivalent to the probability that each row has gcd 1 with q, $gcd(a_{i,1}, \dots, a_{i,m}, q) = 1$. Also, there is a lower bound on the totient function, $\varphi(q) \geq \sqrt q/\sqrt 2$, but this hasn't led me to a solution for the bound we want.

I think you're overthinking it.

Hint

The event in which $A\cdot \mathbb Z_q^m \neq \mathbb Z_q^n$ is the event in which the matrix $A$ has a rank defect, which is "contained" in the event in which (say) the first row is a linear combination of the other rows.
Now, what's the probability of the latter event?


"Safe" or Safest Method for Non-Hardened Key Derivation Functionality I'm currently working on the development of an unorthodox system in which, ideally, there would be one master key pair, with thousands of keys derived from it. There needs to be a way to prove that any one of those keys is derived from the master key. In this scenario, the private and the public keys of all of the derived keys can be considered common knowledge and can be used in that verification process. The public key in the master key pair may also be considered common knowledge. The only secret entity is the private key in the master key pair. I am aware that using non-hardened derivation, it is possible to accomplish this goal, yet that it contains many security risks, and the private key in the master key pair could be figured out (making non-hardened derivation as I've seen it, an unacceptable solution, unless you know of a way to make this process safe).

Is there any way to prove that derived keys could only have come from one master key pair, without exposing that master key pair's private key? Is there a safe way to do this with non-hardened key derivation? Is there a way to do this with zero knowledge proofs (they would have to be non-interactive)? Assume that it would not be feasible for the master to simply create and sign a document listing keys they've derived (new keys could be derived at any moment, and there could theoretically be too many keys derived to list within message size constraints). You may also assume that any algorithm that can accomplish this goal can be used (i.e. not necessarily just RSA).

This is for sure an abstract and vague question, so please guide me on what more information you need or how I can amend this question. Thanks.

There needs to be a way to prove that any one of those keys is derived from the master key. In this scenario, the private and the public keys of all of the derived keys can be considered common knowledge and can be used in that verification process.

The following seems to mach that requirement (as I understand it), and the additional one that private keys embed an identifier (that could be the Common Name or/and Certificate Serial Number of a certificate of the derived private key).

The master key is for a deterministic signature scheme with total message recovery with no place for a side-channel (that is: verification of a signature does not require the message, which is recovered as part of the signature verification; and it is impossible for anyone, including holding the master private key, to exhibit two different valid signatures for the same message).
Derived keys are for an (e.g. signature) scheme with the properties that:

a private key can be any signature per the master key scheme;
the public key is a public function of the private key;
it's impossible to turn a private key into a different private key yielding signatures that verify against the unmodified derived public key.

The master key signature scheme can be RSA-4096 per ISO/IEC 9796-2 mode 3, SHA-512 hash for signature and MGF1, trailer field option 1, non-alternative signature, which embeds any message up to 446-byte in a 512-byte signature.
We enforce that at least one bit is zero in the high-order 66 bits of the 4096-bit master key public modulus (though not the highest order bit), so that the signature codes an integer in range $[2,2^{4095}-2^{4029})$, making it suitable as private key for the scheme below.

The derived key signature scheme can be Schnorr signature (per Claus-Peter Schnorr, Efficient Signature Generation by Smart Cards, in Journal of cryptology, 1991) with SHA-512 hash (and missing details), in the 4096-bit MODP group of RFC 2526.

The 4096-bit MODP group has internal law the integer multiplication modulo prime $p=2^{4096}-2^{4032}+2^{64}\left(\lfloor2^{3966}\pi\rfloor+240904\right)-1$. It is generated by $\alpha=2$, hence is precisely the set of all $2^k\bmod p$ for integer $k$. It has order the (Sophie Germain) prime $q=(p-1)/2$. Private key $s$ is any integer in $[0,q)$, expressed as 512 bytes. Public key is $v=2^{q-s}\bmod p$, expressed as 512 bytes.

To generate a derived key pair, we sign an identifier with the master private key, yielding the derived private key; and from that compute the derived public key. The two are paired by a public relation ($v=2^{q-s}\bmod p$ in Schnoor signature) hence the derived public key can't be changed without changing the private key. Security properties of the master signature scheme protect against forged private keys. There can't be two derived keys with the same identifier, even if the master private key was misused.

  any way to prove that derived keys could only have come from one master key pair, without exposing that master key pair's private key?

To check a derived key pair, we verify its public key against its private key (which is easy with Schnorr signature), check that the alleged private key verifies as a signature against the master public key, and get the identifier in the process (which perhaps can be checked against an alleged public key certificate).


What is double-length derivation key? I trying to understand how can an IPEK created from a given KSN and BDK (Triple DES Edition). From this article-Creating an IPEK from a given KSN and BDK (Triple DES Edition):

  Derivation of Initial Key (IPEK) from Base Derivation Key (BDK) The initial PIN Entry Device key (the key initially loaded into the PIN Entry
  Device) is generated by the following process:

  Copy the entire key serial number, including the 21-bit encryption counter, right-justified into a 10-byte register. If the key serial
  number is less than 10 bytes, pad to the left with hex “FF” bytes.
  Set the 21 least-significant bits of this 10-byte register to zero.
  Take the eight most-significant bytes of this 10-byte register, and encrypt/decrypt/encrypt these eight bytes using the double-length
  derivation key.
  Use the ciphertext produced by Step 3 as the left half of the Initial Key.
  Take the 8 most-significant bytes from the 10-byte register of Step 2 and encrypt/decrypt/encrypt these 8 bytes using as the key the
  double-length derivation key XORed with hexadecimal C0C0 C0C0 0000
  0000 C0C0 C0C0 0000 0000.
  Use the ciphertext produced by Step 5 as the right half of the Initial Key.

What is double-length derivation key ? I can't find any useful information regarding this from internet.

What is double-length derivation key ?

My reading is that is the Base Derivation Key (BDK), used to derive (produce) an Initial PIN Entry device Key (IPEK). Both BDK and IPEK are 16-byte keys for 3DES; otherwise said for TDEA keying option 2 per the (obsolete) FIPS SP-800-67-Rev1 section 3.2, item 2.

The 16-byte BDK or IPEK is split into two 8-byte halves $K_1$ and $K_2$, and 8-byte $P$ is enciphered into $C=E_{K_1}(D_{K_2}(E_{K_1}(P)))$. That's the usual Encrypt-Decrypt-Encrypt of 3DES/TDEA, as explained in step 3.

Step 5 complements the high-order two bits of the four left/high order bytes of each of the 8-byte halves of BDK, to form a different BDK'. The same 8-byte value obtained in the first half of step 3 is enciphered per 3DES/TDEA using BDK (resp. BDK') to form the left/high order (resp. right/low order) half of IPEK.


How does AES introduce confusion and diffusion? I know that in AES the shift-rows and mix-columns operations introduce diffusion, but I don't understand how they create diffusion. Also, I know the add-round-key operation creates confusion, but I don't understand how it creates confusion by simply XORing the round key with the columns of the state matrix.

Put simply:

The add key layer ensures the encryption function is only computable by someone who knows the key

Adds some confusion because the key is (psuedo) random

The subBytes s-box layer creates confusion

each symbol is mapped to another symbol in a way that impedes common methods of cryptanalysis (high resistance to linear and differential cryptanalysis)

The shiftRows and mixColumns operations combine to provide full diffusion over the course of 2 rounds

The state is a 4x4 grid of 8-bit words
mixColumns operates vertically on each 4 word/32-bit column

One bits difference in any word in the input column will spread to multiple places in multiple words in the output column

shiftRows ensures that over the course of successive rounds different words are grouped up as inputs to the mixColumn function
There's a good answer that is slightly more specific here

For more information, consult the book on the design of Rijndael, or maybe try one of the handy diagrams or animations that exist.


What is the "Random Oracle Model" and why is it controversial? What is the "Random Oracle Model"?  Is it an "assumption" akin to the hardness of factoring and discrete log?  Or something else?

And why do some researchers have a strong distrust of this model?

A random oracle is described by the following model:

There is a black box. In the box lives a gnome, with a big book and some dice.
We can input some data into the box (an arbitrary sequence of bits).
Given some input that he did not see beforehand, the gnome uses his dice to generate a new output, uniformly and randomly, in some conventional space (the space of oracle outputs). The gnome also writes down the input and the newly generated output in his book.
If given an already seen input, the gnome uses his book to recover the output he returned the last time, and returns it again.

So a random oracle is like a kind of hash function, such that we know nothing about the output we could get for a given input message $m$, until we actually try $m$. This is a useful tool for security proofs because they allow to express the attack effort in terms of number of invocations to the oracle.

The problem with random oracles is that it turns out to be very difficult to build a really "random" oracle. First, there is no proof that a random oracle can really exist without using a gnome. Then, we can look at what we have as candidates: hash functions. A secure hash function is meant to be resilient to collisions, preimages and second preimages. These properties do not imply that the function is a random oracle.

Indeed, see SHA-256 (or SHA-512 if you wish). It suffers from something called the "length extension attack". This is an artefact from the Merkle–Damgård construction: to hash a message $m$, the message is first split into fixed-size blocks (64 bytes for SHA-256), the last block being padded with some bits which include the length of $m$, and some ones and zeros such that we end up with a full block. Each block is then processed over a running state, the hash output being the last block value.

So suppose that there is a message $m$, that I do not know, but I know the length of $m$ and its hash $h(m)$. With that information, I can rebuild the padding bits which were added (let's call them $\pi$). Then, I can envision the message $m'$:
$$ m' = m || \pi || x $$
for some value $x$ that I choose arbitrarily. I then know that the computation of $h(m')$ will begin by splitting $m || \pi$ into blocks and processing them, and after having processed the last bit of $\pi$, the current "running state" will be exactly $h(m)$. So, if I know $h(m)$, I can finish the computation of $h(m')$ by taking it from there, and I can do that without knowing $m$. In particular, I end up with $h(m')$ while not having presented $m'$ to the gnome.

This property proves that SHA-256 is not a random oracle. Yet, it does not endanger in any way the resistance of SHA-256 to collisions or preimages. Therefore, being a random oracle seems to be strictly harder than being a secure hash function.

It has actually been shown (by Canetti, Goldreich and Halevi) that random oracles cannot exist "in all generality" in the following sense: it is possible to build pathological signature and asymmetric encryption schemes, which are secure when they internally use a random oracle, but which are insecure whenever an actual computable function is used instead of the mythical gnome-in-the-box.

Summary: proofs in the random oracle model are fine, but are never complete enough to cover a practical implementation: we know that any function we will use in lieu of the random oracle will not be a random oracle; so security relies on the fervent hope that the parts where the actual function is not a random oracle do not impact security. This justifies a bit of mistrust. Still, a proof in the random oracle model is much better than no proof at all.