Cardinality of the group of units in a cyclotomic ring? In the NTRU key generation, one samples a polynomial from $K = (\mathbb Z/q\mathbb Z)[X]/(X^n+1)$ and tests if it is invertible. What are the chances of this to happen? In other words:

Let $q$ be a prime and $n>4$ be a power of $2$. What is the cardinality of $K^*$?

The $n$th cyclotomic polynomial $\Phi_n\in\mathbb Z[x]$ is irreducible in $\mathbb F_q[x]$ if and only if $q$ is a generator of $(\mathbb Z/n)^\times$ (proof).
Hence, unfortunately, the polynomial $x^n+1$ is never irreducible modulo $q$ if $n>4$ is a power of two: The group $(\mathbb Z/n)^\times$ is not cyclic in that case. Thus it may indeed happen that the polynomial chosen in NTRU is not invertible.

Since I am not aware of any exact results, we shall derive a generic lower bound for the cardinality of $(\mathbb F_q[x]/(x^n+1))^\times$.
(By "generic", I mean that the following is not specific to cyclotomic polynomials. I suspect one can obtain much better bounds by using cyclotomic theory.)

I will assume $q\geq3$. Then the polynomial $x^n+1$ is square-free over $\mathbb F_q$ since $\gcd(x^n+1,nx^{n-1})=1$.
Decompose $x^n+1$ into (therefore distinct) irreducible factors $g_i\in\mathbb F_q[x]$ of degrees $e_i:=\deg g_i$.
By the Chinese remainder theorem, we have an isomorphism
$$
    \varphi\colon\quad
    \mathbb F_q[x]/(x^n+1)
    \;\cong\;
    \prod_{i=1}^r\underbrace{\mathbb F_q[x]/g_i}_{\cong\ \mathbb F_{q^{e_i}}}
    \text.
$$
Composing this isomorphism with projections to the direct factors $\mathbb F_q[x]/g_i$ yields ring homomorphisms
$$
    \pi_i\colon\quad
    \mathbb F_q[x]/(x^n+1) \;\to\; \mathbb F_{q^{e_i}}
$$
with the property that an element of $\mathbb F_q[x]/(x^n+1)$ is invertible if and only if its image under each $\pi_i$ is invertible, i.e., non-zero. Hence the probability that an element $f\in\mathbb F_q[x]/(x^n+1)$ chosen uniformly at random is a unit is
$$
    \Pr[\text{unit}] \;=\; \prod_{i=1}^r (1-1/q^{e_i})
    \text.
$$
How bad can this become? In the worst case, we have $r=n$ and all $e_i=1$, hence
$$
    \Pr[\text{unit}] \;\geq\; (1-1/q)^n
    \text.
$$

When considering small $q$ and large $n$, this bound becomes quite low quickly, but keep in mind that it is a worst-case estimate. In practice, it seems that the $e_i$ are typically much greater than $1$.

Moreover, in the NTRU scenario, $q$ is quite big: The parameters recommended, depending on the source, are roughly $q\approx 2000$ and $n\approx 1000$, yielding
$$
    \Pr[\text{unit}] \;\geq\; \frac12
    \text,
$$
so one can easily find a unit within a few tries with very large probability.


Schnorr protocol: how does malicious verifier win? My question is about the challenge space size in Schnorr protocol. To be precise, I feel I've read all the Internet (twice) and I still don't understand why is it bad to allow challenge space to be large (say, why one shouldn't let $\text{Challenge} \in \mathbb{Z}_q$)

I'm interested only in situation of honest prover $P$ and malicious verifier $\tilde{V}$.

To settle the notation, recall that (one round of) Schnorr protocol has the following form:

Prover generates random $r \in \mathbb{Z}_q$, calculates $\text{Commit}=g^r \pmod p$, then sends $\text{Commit}$ to verifier.
Verifier generates $m$ random bits and forms the number $\text{Challenge}$ from them (thus $\text{Challenge}$ is the random number ranging from $0$ to $2^{m} - 1$), then sends $\text{Challenge}$ to prover.
Prover calculates $\text{Response} = r+s \cdot \text{Challenge} \pmod q$, then sends $\text{Response}$ to verifier.
Verifier checks that $g^{\text{Response}} = \text{Commit} \cdot y^{\text{Challenge}} \pmod p$

where $y = g^s \pmod p$ and $s$ is the prover's secret.

The simulator for this protocol is as follows.

The algorithm generates random $\text{Response} \in \mathbb{Z}_p$.
The algorithm asks verifier for the number $\text{Challenge}$ and receives it.
The algorithm sets $\text{Commit} = g^{\text{Response}} \cdot y^{-\text{Challenge}} \pmod p$
The algorithm appends $(\text{Commit}, \text{Challenge}, \text{Response})$ to the transcript.

The standard answer to my question is: if $\text{Challenge}$ is pseudorandom -- namely, depends on $\text{Commit}$, say, is equal to $\text{hash} (\text{Commit} || M)$ -- this simulator protocol cannot work, since at step 2 it requires the knowledge of parameter generated at step 3. There are no other simulators known for this protocol, so in the case of malicious verifier there's just no simulator. And since any ZK-protocol has simulator, the conclusion follows that malicious verifier case is not ZK.

Question 1. However, I still don't get how exactly can malicious verifier extract some information. Okay, there's no known simulator for malicious verifier case -- well, how does it help him?

Question 2. What about the challenge space size? Mao, Wenbo in their "Modern Cryptography" state that, thus, because of this simulator argument, $\text{Challenge}$ space size should NOT be large (don't get the logic again) ($\text{Challenge} \in \mathbb{Z}_q$ is prohibited)  and state that the best choice is $\text{Challenge} \in [0, \log_2 p)$ (or, equivalently, $m = \log_2 \log_2 p$). Why such an odd and strange value?

This all seems to be explained in the book (warning: large) you mention, all I mention here is taken from there.

This is the last sentence before $\S18.3.2$:

  Enlarging challenge size not only improves performance (a positive result), in $\S18.3.2$ we will further see that this also has a negative consequence. Be careful, size matters!

This last sentence is of critical importance, but we will focus on the first one for now. Moving to $\S18.3.2$, we find the last sentence before $\S18.3.2.1$:

  However, there is a subtlety for the problem. Let us examine it now.

This is followed by about 2 pages of explanation to your question, which indeed they agree to have subtleties. Although you have read all the internet twice (kudos), your answer suggests you may have missed this.

It seems that setting

  $${\tt Challenge}={\tt prf}(M||{\tt Commit})={\tt prf}(M||g^{\tt Response}y^{\tt
> Challenge}\bmod{p})$$

leads to two options:

  The equation was constructed by Alice using her private input, and hence Alice discloses the fact that she has been in interaction with,
  and fooled by, $\tilde{Bob}$, or
  $\tilde{Bob}$ has successfully broken the pseudo-random function ${\tt prf}$ of the large output space $\mathbb{Z}_q$, because he has
  constructed equation $${\tt Challenge}={\tt prf}(\cdots y^{\tt Challenge}).$$ This is a well-known hard problem because ${\tt prf}$
  is assumed to be one-way.

  Given that $\tilde{Bob}$ is assumed to be polynomially bounded, the
  third party will of course believe that (i) is the case.

The information revealed is thus the fact that the prover has been interacting with the malicious verifier. Luckily, the authors mention that

  A small consolidation for Alice is that the information disclosure caused by $\tilde{Bob}$ is not a too disastrous one (though this assertion has to be based on applications really). [...] the proof transcript still does not disclose to $\tilde{Bob}$ or a third party any information about Alice's private input $a$.


Questions regarding random values in Schnorr authentication In Chapter 21.3 of Schneier, Applied Cryptography I read the following about the Schnorr Authentication Protocol:

To generate a key pair, first choose two primes, $p$ and $q$, such that $q$ is a prime factor of $p - 1$. Then, choose an $a$ not equal to $1$, such that $a^q \equiv 1 \pmod{p}$. Then choose a random number less than $q$. This is the private key $s$. Then calculate $v = a^{-s} \mod p$. This is the public key.
Authentication Protocol
(1) Peggy picks a random number, $r$, less than $q$, and computes $x = a^r \mod p$.
(2) Peggy sends $x$ to Victor.
(3) Victor sends Peggy a random number, $e$, between $0$ and $2^t - 1$. (I’ll discuss $t$ in a moment.)
(4) Peggy computes $y = (r + se) \mod q$ and sends $y$ to Victor.
(5) Victor verifies that $x = a^yv^e \mod p$.
The security is based on the parameter $t$. The difficulty of breaking the algorithm is about $2t$. Schnorr recommended that $p$ be about $512$ bits, $q$ be about $140$ bits, and $t$ be $72$.

I have two questions regarding this:

Why can $r$ not also be $q$? This would make the commitment $x=1$, but what would be the problem with that?
Why is the challenge $t$ not allowed to be as large as $q$? It would not break anything, would it? I even found this lecture on Youtube where the lecturer lets the challenge (there denomiated $c$) be $c \in \mathbb{Z}_q$. Does limiting the size of $t$ make the procedure more efficient? If so, how?

Your first question: $r$ is taken from the group $Z_q$ ranging from 0 to $q-1$, and $q\equiv 0 \bmod q$, i.e. $q$ is the same as 0 in this group. Thus if you allow $q$ to be chosen, then $r$ is not uniform: you get 0 with a probability $2/(q+1)$ and all other elements in $Z_q$ with a probability $1/(q+1)$. Not really a big deal since the difference in probability is anyway negligible, but it is enough to annoy cryptographers.

Your second question: it really depends on what kind of zero-knowledge property you want. If you want zero-knowledge (without restriction), you have to have a small $t$; if you just want honest verifier zero-knowledge, then you can choose $c$ from $Z_q$. The reason is that when you use $c$ from $Z_q$, you will run into big trouble when trying to prove zero-knowledge because there is not a way to construct a simulator to handle such a big $c$. The usual simulating strategy is to let the simulator guess $c$ randomly until it is the one chosen by the verifier, which does not work when the probability of guessing correctly is negligible (if $t$ is small then the probability is high). But if the verifier is honest, you don't need to simulate it, so it is fine.


Three-party protocol for multiplication with output privacy Suppose this simple protocol with three parties: $X$ (with secret input $x$), $Y$ (with secret input $y$), and $Z$ (no input). Suppose that we are operating with elements from a finite field.

The goal is that after the execution of the protocol, $Z$ knows $x\cdot y$ but not $x$ nor $y$, and $X$ and $Y$ does not learn anything. This can be considered similar to output privacy in secure multiparty computation. It is clear why we need output privacy: if $X$ learns $x\cdot y$, he can compute $y$ (and viceversa).

An initial approach could be based in using blinding factors. $X$ gives $b\cdot x$ to $Y$ and $b$ to $Z$, for a randomly sampled $b$; next, $Y$ gives $(b\cdot x)\cdot y$ to $Z$; and finally, $Z$ removes $b$ to obtain $x\cdot y$. This solution assumes that all parties are honest.

Any other ideas or references on how to come up with better solutions? I'm sure that similar problems should have been already tackled by the SMC community.

First, I'll assume that parties' inputs come from a multiplicative group. If they're in a ring and you also want multiplication by zero, then things get harder. In that case, the protocol you describe is not secure even in the semi-honest case.

The protocol you describe is already secure in the malicious case.  $X$ gives random $b$ to $Z$ and $bx$ to $Y$. $Y$ gives $(bx)y$ to $Z$, who computes $b^{-1}(bxy)$.

If $X$ is corrupt, he sends some $b$ to $Z$ and $c$ to $Y$. This achieves the same effect on the honest parties as running honestly with input $b^{-1} c$ in the ideal world, so it's simulatable / not an attack.
If $Y$ is corrupt, she gets $c = bx$ from $X$ and gives $d$ to $Z$. The message $c$ from $X$ is distributed uniformly, so this message is simulatable without knowing $X$'s input. Furthermore, $Y$'s behavior achieves the same effect on the honest parties as running honestly with input $d c^{-1}$, so it is simulatable / not an attack.
If $Z$ is corrupt, there's nothing he can do, since all he does is receive messages.
If $Z$ is corrupt and colludes with one of $\{X,Y\}$, then in the ideal world they can deduce the honest party's input in its entirety. So there is nothing to hide.
If $X$ and $Y$ collude, then $X$ sends $b$ to $Z$ and $Y$ sends $d$ to $Z$. This achieves the same effect on the honest party as them running honestly with inputs $1$ and $b^{-1} d$.


Can I secure my key by XORing it with a hashed password? I'd like to build a simple password-protected symmetric key system.  The key-creation process in my system operates as follows:

The system creates a 256-bit key purely at random.
The user chooses a password, which is hashed using SHA-256.
The system stores the value key XOR SHA(password), which we call the "pseudo-key".

The pseudo-key is stored permanently by the system or user, whereas the actual key and password hash are never stored. When the user wants to produce his key for encryption or decryption, he can recreate the actual key from pseudokey XOR SHA(password). The password hash and actual key are always destroyed immediately after use.

Aside from an adversary obtaining the pseudo-key and brute-forcing the password, are there any obvious theoretical problems with this system?
Is it notably inferior to other extant password-based key systems?
Is the system I'm describing (or any system that password-protects a symmetric key) already present in some cryptographic library?

You are using a Vernam-encryption (simple XOR), as for the one-time pad.

The general principle for Vernam is that it is perfectly secure as long as you never reuse the same key for more than one message, and gets utterly broken as soon as it is reused even once (this is the "two-time pad"). The key here is the hashed password, the message the key.

If one of your encrypted keys is leaked, all others encrypted with the same password are immediately broken, too (since you can get the password hash, which is the actual key). You normally don't want this property in an encryption system, even if it is only used for data which is of random nature and of only temporary use.

Instead, do one of the following things:

Use a real encryption (like a block cipher) with the hashed password as key and the stored key as input.
Use some (random) salt in the hash function, so that each use of the password gives another hash. Store the salt with the XOR-ed key.
Use a key derivation function to derive the actual key from salt and password. Do only store the salt, not the key in any form.

The OpenPGP message format uses some of these, I think.


Can Shannon's entropy be used to determine if a file is encrypted? If we have to determine a file is encrypted or not, can we use Shannon's entropy algorithm on the file?

As discussed here, the entropy (in bits per byte) being closer to 0 is considered as more orderly and being closer to 8 is considered more random.

Intuitively this might be generating false positives a lot. Can any one explain if this approach is appropriate to determine given a random file is encrypted or not?

You are likely going to have both false positives and false negatives if you try to use Shannon entropy for this.

Many compressed files would have close to 8 bits of entropy per byte, resulting in false positives.
Any encrypted file that has some non-binary encoding (like a file containing an ASCII-armored PGP message, or just a low entropy header) could have a lower entropy, resulting in false negatives.
If Format Preserving Encryption is used , this might result in false negatives too

It may work as a heuristic, but you should not rely on the results being correct.


Solve System of Equations including XOR and Modular Addition A Dummy cipher is shown in figure below. Plaintext is 16 bits ($X_1$ and $X_2$ are 8 bit each). Ciphertext is computed after two rounds using two round keys $K_1$ and $K_2$. Can the round keys $K_1$ and $K_2$ be found by solving the system of equations, which involves XOR and Modular Addition?

$\boxplus $ = addition modulo $2^8$

$\oplus$ = XOR

$X_1$, $X_2$, $Y_1$, $Y_2$ are 8-bit. $i=1,2$.

I am confused on how to solve such system of equation which involves XOR and modular addition. How many PT-CT pairs are required to solve such system of equations? How many linear, non-linear/quadratic terms will there be in the system of equations?

Ok, this would appear to be homework, so I won't give the full answer; I'll get you started.

First thing to do (with this attack approach) is to write out the full equations of the system, as in:

$$T_0 = P_0 \oplus K_0$$

$$T_1 = P_1 \boxplus T_0$$

$$T_2 = T_0 \oplus T_1$$

$$T_3 = T_2 \oplus K_1$$

$$C_1 = T_3 \boxplus T_1$$

$$C_0 = T_3 \oplus C_1$$

where you know $P_0, P_1$ (the plaintext), $C_0, C_1$ (the ciphertext), and you don't know $K_0, K_1$ (the keys) or $T_0, T_1, T_2, T_3$ (the internal states of the cipher at various points).  And, we'll assume that we have a single plaintext/ciphertext pair (that will turn out to be sufficient against this cipher).

Where to do go from here?  Well, the first obvious step is to notice the last relation $C_0 = T_3 \oplus C_1$; we know $C_0, C_1$, and so we can deduce the value $T_3 = C_0 \oplus C_1$.  Then, we notice the relation $C_1 = T_3 \boxplus T_1$, we know $C_1$ and $T_3$, and so we can deduce the value $T_1 = C_1 \boxminus T_3 = C_1 \boxminus (C_0 \oplus C_1)$.  Where do we go next?

Now, this approach takes apart this two round cipher quite nicely; however it doesn't scale very well; adding a third round to this toy cipher will break the relations this depends on.  On the other hand, I suppose it might be a start in learning how to think about how to attack a cipher, although you will need to find other ways to attack less trivial ciphers. fgrieu's suggestion about looking at the lower-order bits first is a more general approach that'll work in cases where this won't.


Symmetric encryption algorithms with large IVs and authentication? Most modern symmetric ciphers require a nonce/IV.  If the nonce is reused, security is lost.

If the nonce is large enough, it can be generated securely by using a CSPRNG.  This avoids needing to keep state between encryptions.  I am looking for algorithms that

have a large IV — specifically, one large enough that using a CSPRNG
to generate a fresh IV each time is secure.
provide authentication.
have easy-to-use, well-regarded, portable open-source implementations that
are resistant to timing attacks.

The reason for these requirements is that I am looking for an implementation that is (relatively) hard to misuse and works just about anywhere — and that is written by an expert cryptographer.

I have some ideas (such as encrypting a randomly-generated 512 bit IV with a single round of ChaCha20 – and then transmitting it) but I am not a cryptographer so I don't trust them.

Let's look at your requirements:

  have a large IV — specifically, one large enough that using a CSPRNG to generate a fresh IV each time is secure.

Generally, IVs/nonces longer than 96 bits are thought to be okay for random generation. If it is at least 128 bits you can safely use it as long as you can a 128-bit block cipher like AES, because before you run into random nonce collisions you already have random block collisions.

Shorter nonces, such as the 64-bit nonce in Salsa20 and ChaCha cannot be used as freely, since you would expect a collision after a few billion ($10^9$) messages and after just millions with non-negligible probability.

  provide authentication.

Unless you want to compose your own authenticated encryption using a cipher and a MAC, this basically leaves you with one option that is in common use: AES-GCM. ChaCha20Poly1305 is also in common use (TLS), but has a short 64-bit nonce. XSalsa20Poly1305, which CodesInChaos mentions, is also an option, but basically only used in NaCl/libsodium as far as I know.

The X in XSalsa20 is important. That algorithm has a 192-bit nonce. That long nonce allows you to e.g. use a 128-bit random value and a 64-bit timestamp, making collisions unlikely even in the case of a deficient RNG.

  have easy-to-use, well-regarded, portable open-source implementations that are resistant to timing attacks.

This is a bit off topic here, but again, AES-GCM and XSalsa20Poly1305 both have open source implementations. E.g. libsodium has implementations of both.

  I have some ideas (such as encrypting a randomly-generated 512 bit IV with a single round of ChaCha20 – and then transmitting it) but I am not a cryptographer so I don't trust them.

This does not seem to accomplish anything. IVs do not need to be secret and ChaCha20 itself requires a (short) nonce.


Proof of work for standard computers I'm interested in a proof-of-work system that works well on standard computers without using the GPU.

Properties the system should have:

Seed based proof-of-work.
There is no distinguished challenger who can solve the problem efficiently. A typical seed is a 256 bit hash of a public key.
Minimize the advantage an attacker gains from specialized hardware.
The legitimate worker has a standard desktop or notebook. He's willing to commit about 1GB of memory and his CPU to calculate the proof. The time he spends is a few minutes to a few hours, depending what grade the proof should have.
The attacker can use specialized hardware including GPU, FPGA and ASIC. The amount of money he spends for hardware and electricity to calculate the proof should be maximal.
Efficient verification
Verifying the proof should be cheap. For example taking 1ms and 1MB of memory.
Small proof
A 16 byte proof would be ideal, but a few kilobytes would be OK too.
Predictable duration
For many proof systems each attempt is independent, making it hard to predict when you succeed. Success peaking around the average time would be nice. This is just a nice-to-have feature, and I'd be content with a system that only satisfies 1 to 4.

Systems I know, but that don't satisfy my requirements:

Hash prefixes for standard hash functions such as SHA-2. This fulfills 1, 3 and 4, but utterly fails 2. Specialized hardware is much more efficient than the target hardware.
Hash prefixes for scrypt. This fulfills 1, 2 and 4. But it fails 3, because verification requires just as much memory as working, and verification time is a bit long too.

I believe it is possible to create a system that fulfills the four main requirements. My idea is solving a problem which in principle can be solved with little memory, but the chance of success is small, and thus the amount of work is very large, in that case. But if you are willing to commit significant amounts of RAM, you can run a different algorithm, that solves the problem efficiently.

$\quad$ chosen-prefix partial collisions for scrypt

This does somewhat better at #3 than your second option because

working requires storing previously obtained scrypt outputs.

(I think it would be better to require a at most a given Hamming distance between the outputs rather

than equality of a specific set of bits of the output. $\:$ The first of those would require storing the

entirety of the outputs, while the second would only require storing the relevant bits of the output.)


Rounds in cryptography I need to make it clear I  know nothing about crypto so in that context I'm hoping to clear up some confusion:

As I understand it a "round" in a cipher is one encryption operation and a cipher like AES has multiple rounds. Did I get this right?

I've seen descriptions of attacks against a cipher say something like it "broke 4 out 8 rounds". In this case, if the plaintext wasn't recovered than how is it determined that any number of rounds were broken?

Thanks

Most encryption algorithm use a specific number of the same (or similar) group of operations. As example, AES consists of 4 different operations: SubBytes, ShiftRows, MixColumns and AddRoundKey. AES-128 (AES with a key of 128 bits) uses all this operations 10 times in 10 rounds. Well, not exactly. The last round doesn't have the MixColumns step. It would add nothing to the security which is why it's omitted.

If an attack has "broken 4 out of 8 rounds" it means that the same algorithm was broken if it would use only 4 instead of the normal 8 rounds. Using only 4 rounds instead of 10 in AES-128 is broken, even without special prequesits. Breaking a few rounds of a cipher is normal, because the secure properties of an algorithm have to slowly establish through the rounds. If 9 out of 10 rounds would be broken, that would be much more alarming. We can assume that the last round will be broken soon enough.

Now we have to mention one important thing: If an algorithm is broken it doesn't mean that someone can decrypt every message encrypted with this algorithm without the key. Nearly every attack on modern algorithms is not about this. There are different kinds of attacks: As example, a known-plaintext attack needs a special amount of plaintexts and corresponding ciphertexts to gain the key. Numbers of $2^{40} = 1\,099\,511\,627\,776$ are low, despite being something like 128 terabyte of encrypted data. A break with this small amount would be considered devastating for AES. For one special attack on AES-256 we still need ca. $2^{100}$ operations - too much in practice, despite being "broken" in the academic sense.


Does XOR'ing a random number with its inverse reduce its security if the result is a palindrome? [And four related questions/examples below:]

2) If a random 256-bit number is XOR'ed with its reverse (i.e. the big-endian version XOR'ed with the little-endian version), does this reduce the security properties in terms of bits, if the result is a palindrome, as there are only ${2^{128}}$ such palindromes in the range of  ${2^{256}}$?

3) Can an adversary efficiently brute-force search just the palindromes in that range?

Example:  an L-bit random N ${\oplus}$ reverse(N) = palindromic string L-bits long.

Example using a random 256-bit binary string:

N=1000001110111000001110001111100111001000111111111111010110111001011010110110010110011001100010110110101101001000001110111111111111001110101001110001101101110101010101110011000111000010101011001010100000110110111000010101101000100111001010110110011011010110

Reverse(N)=0110101101100110110101001110010001011010100001110110110000010101001101010100001110001100111010101010111011011000111001010111001111111111110111000001001011010110110100011001100110100110110101101001110110101111111111110001001110011111000111000001110111000001

N ${\oplus}$ Reverse(N) = 1110100011011110111011000001110110010010011110001001100110101100010111100010011000010101011000011100010110010000110111101000110000110001011110110000100110100011100001101010100001100100011110100011010110011001000111100100100110111000001101110111101100010111

4) Are there any advantages in using a longer key with reduced security than a smaller key with the same security (i.e. could there be an advantage having a 256-bit key with 128-bits of security, compared to having a 128-bit key with a 128-bits of security?)

5) In addition, could there be benefits such as only having to retain half of the palindrome, in order to reconstruct the other half, in terms of compression/notation while avoiding information loss despite any reduced security?

Example using above palindrome where only the leading 128-bits are retained:
 11101000110111101110110000011101100100100111100010011001101011000101111000100110000101010110000111000101100100001101111010001100 and where reconstruction of the original 256-bit palindrome is achieved by concatenating the reverse of the 128bits to the right-end of the retained 128 bits as follows: 11101000110111101110110000011101100100100111100010011001101011000101111000100110000101010110000111000101100100001101111010001100||00110001011110110000100110100011100001101010100001100100011110100011010110011001000111100100100110111000001101110111101100010111

The xor of two random strings is a random string, so you're basically generating a 128-bit random string from a 256-bit random string.

Yes, it reduces security compared to a pure 256-bit random string.
Yes. As you pointed out, there are only $2^{128}$ possible strings.
Yes. The attacker can generate all $2^{128}$ strings and trivially concatenate them with their reflection in each step.
No, both have 128-bit security against brute force attacks.
No, as mentioned there is no security gain in using palindromes, which implies that there is no advantage at all in use palindromes. For example, a 256-bit palindrome can be stored "compressed" in 128 bits, but it still provides only 128 bits of security. You could simply use a normal 128-bit key instead, which fits in the same size, has the same security, and is a lot simpler.


"Memory-Hard" vs. "Memory-Bound" Functions? One of the approaches in order to prevent Sybil or DoS attacks is CPU-bound PoW. However, because of the influence of Moore’s law, the memory-based approaches are suggested.
As actually there are two different terms: (1) memory-hard functions and (2) memory-bound functions;
Does it mean that we have two different memory-based techniques?
And if yes, What is the difference between these two terms?

The Wikipedia definitions are clear;

memory-bound functions;

Memory bound refers to a situation in which the time to complete a given computational problem is decided primarily by the amount of memory required to hold data.

This is proposed for using against spams, first CPU-bound then memory bound. This algorithms requires to access memory in an unpredictable way so that caches are ineffective. This discourage the spammers.

memory-hard functions

In cryptography, a memory hard function (MHF) is a function that costs significant amount of memory to evaluate. It is different from memory bound functions, the latter incurs cost by slowing down computation through memory latency. MHFs find their use as a form of proof-of-work.

This is against the massive parallelization of hashing etc. For example the bitcoin miners create farms for SHA2d calculations since SHA2 is not memory hard.
There are two variants

Data Dependent
Data independent

For example Argon2 has both mode and even combined. Argon2i for data independent and Argon2d for data dependent. In the combined mode Argon2id.


Why would you ever need Key exchange algorithms, when you can use public key encryption? Key exchange algorithms make it possible to establish a shared secret key.

But isn't a shared secret always just as powerful as each party creating a public/private key pair and sending each other their public key, and using that for exchanging data?

I always read this is not secure because of the risk that the private key might leak. However the shared key might also leak.

Why the need for key exchange algorithms?

Why the need for key exchange algorithms?

Most of the time in practice you will probably use a secret key with a symmetric cryptosystem because of efficiency reasons. Especially if you have a large amount of data to send, doing a single key agreement via Diffie-Hellman and then using the resultant key with a symmetric cryptosystem will be take significantly less time than actually packaging the data up and sending it one chunk at a time via RSA. Performing a key exchange and then using the key for a symmetric cryptosystem is referred to as a hybrid cryptosystem.

Less time implies fewer CPU cycles

Fewer CPU cycles implies lower power consumption

Public Key Encryption implies ciphertext expansion

This results in slower transfer speeds for data in transit on a network
This results in more space consumed for data at rest on a storage medium

Key agreement algorithms such as Diffie-Hellman are sometimes simpler to implement than public key encryption schemes such as RSA.

When to use Public Key Encryption

Many PKE schemes offer homomorphic encryption. If you want homomorphic encryption, you probably can't opt for the hybrid cryptosystem and will need to package your message into the PKE ciphertext.

If you are operating in a constrained environment, depending on the nature of the constraints and environment it can possibly be better to simply use PKE directly instead of a hybrid cryptosystem. Such constraints might include:

Code size constraints
Data size/bandwidth constraints
Latency constraints
Compatibility constraints

What is most efficient will depend on the exact nature of the environment, constraints, and algorithms in question.


Hash and sign via trapdoors for lattices Both the papers GPV'08 and MP'11 present trapdoors for lattices that allow to recover $s\in\mathbb{Z}_q^n$ and the error vector $e\in\mathbb{Z}_q^m$ when given $y=As+e$, for $A\in\mathbb{Z}_q^{m\times n}$.

Also, they claim that their constructions allow to construct signatures via the "hash and sign" paradigm. That is, given a random oracle $h:\{0,1\}^*\to \mathbb{Z}^m_q$, to sign a message $M$, the signer computes $$\mathsf{Sign}(\mathsf{td},M)=\mathsf{Invert}(h(M))=(s,e)$$ such that $As+e=h(M)$, where $\mathsf{td}$ is the trapdoor for $A$ and $\mathsf{Invert}$ is the inversion algorithm.

My questions are:

Does this means that there are a non-negligible number of words in $\mathbb{Z}_q^m$ that are decodable?
If so, every word in $\mathbb{Z}_q^m$ is decodable or we need to use a similar technique as in CFS'01, the McEliece based signature, where we need to try to decode $h(M,i)$ (for $i=0,1,2...$) several times, before getting a signature?

No: the parameter $m$ and the size $B$ of the coefficients of $(s,e)$ would not be the same in both scenarios. In the first (LWE decryption) the matrix $A$ is high and narrow, which makes the function `strongly injective', and decoding is possible. Most images do not have preimages, i.e., only a small fraction of $y$ are decodable, those corresponding to proper encryption. For (SIS) signature the matrix is wide and short, so that most images have many preimages. The term decodable should not be applied here nevertheless, since, well, the preimage is not unique.
No. There is no need to try several times, though care must be taken to avoid `learning attacks' such as this one. This is the role of Gaussian sampling.


Implementation of a decryption mixnet, and problems with the size of the key I've been studying decryption mixnets, in the context of e-voting and stealth networks. Let's describe it in a very simplified way. The concept is pretty simple. A message M is forwarded through several servers, A,B,C. The user encrypts the message with the public key of C, then encrypts that output with B's key, and then encrypts it with A's key. Each server removes a layer, and the last server knows the plaintext.
My two questions are...
How is it possible to implement this in software? I'm using Python, and every single library uses padding. After two or three layers of encription, the output is so, so large. For security purposes,  asymmetric encryption needs a random padding. But I think that this case needs just one layer of random padding, at the beginning (C layer), instead of adding PKCS in every layer. Is there a library implementing mixnets, or a low-level module that allows you to encrypt with RSA or ECC without padding?
And, what about the lengths? Public-key encryption has a length limitation for the plaintext, depending on the size of the key. How does this apply to mixnets? Is the only solution to this problem a hybrid scheme, encrypting a symmetric key?

With RSA and ECC you generally don't encrypt the actual message. When signing, you sign a hash of the message; and when encrypting you encrypt a symmetric-key that can be used to decrypt the message. The message itself is encrypted using either a block cipher, or a stream cipher, depending on what was chosen in the design. As such, with a block cipher, once the message is padded once it's already as long as it's gonna get, and with a stream cipher no padding is needed at all.
Also, it should be noted that ECC-based public-key algorithms operate a lot more like a block cipher than RSA does. With RSA you would need padding at every layer, but with ECC you only need to pad once.


Would adding daily changing nulls in front of their messages have made the Engima harder to crack? The British decrypted the German enigma because they knew that they would repeat the message key twice at the start of every message.

Of course, technology to encrypt enigma without the repetition using cribs was developed later but only after it was cracked before.

The encryption key for the Enigma messages changed daily but what if the Germans also specified an amount of nulls before the message begins.
Then they wouldn't just have changed plugboard settings and rotor settings every day but would have also put X amount of gibberish in front of every message.

Would this have made the Engima significantly harder to crack?

No, padding would make the message much easier to crack.  This is a great example of why cryptography is left to the professionals (I am not a professional cryptographer, I'm not even a very good amateur one).  Amateurs tend to just make things worse.

First problem is the Enigma had no way to produce a "null".  It was only capable of producing letters.

The nearest equivalent of your scheme would be to pick a letter to use as padding (for example, A) and then add that at the start of the message.  Yes, it makes it a bit harder to find the KEYKEY repetition, but not much. You just need to slide your window of six characters over a bit and cryptographers were already doing such sliding window analysis to find other cribs.

But because it's always the same letter at the start of the message it gives the cryptographer a very reliable crib.

(For this answer I'm ignoring the plugboard and rings, there were other techniques to work those out).

Let's say the Germans always put at least two padding letters before the key.  And let's be generous and say they choose a different padding letter every day.  Now the cryptographer knows at least the first 2 letters are going to be the same letter, and there's a very good chance the next letters are also the same.  This provides the cryptographer with a very small set of possible texts to work through.  Since they're right at the start of the message, they can reveal the rotor settings.

Now any setting can quickly be eliminated if decryption does not result in a message which starts with at least two identical letters.

It doesn't even do a very good job at masking the key, since it's still known that the repeated key will start somewhere in the first N characters (where N is the maximum amount of padding the Germans use).  It adds, at most, N - 1 more possibilities.

A A K E Y K E Y

A A A K E Y K E Y

A A A A K E Y K E Y

...and so on...

This is not worth the cryptography gold that is the padding.

  The British decrypted the German enigma because they knew that they would repeat the message key twice at the start of every message.

While this was the first and most important crib, and it was found by the Poles, different branches of the German government and armed forces had different procedures for using the Enigma which changed over the war. This flaw did not last long. For example, by 1937 the German Naval Enigma had already rectified this flaw but was cracked anyway.

Key repetition was just one of many the Poles and British had available to them.  "Pinches" (stealing code books) were one, but the most reliable was the methodical Germans themselves.

The cryptographers knew, for example, that certain operators would always end a message with H E I L H I T L E R, or begin a weather report with the same phrasing, or that somewhere in the message would appear the name of their unit, or location, or any number of other likely texts.

The operators also provided their own cribs.  The person encrypting the message had to come up with a key.  Humans are very bad at producing randomness.  A radio operator, possibly in the field, possibly tired, hungry, cold, has to come up with dozens of unique keys every day.  They're going to get sloppy.  The cryptographers could use this to guess what the key is likely to be, or eliminate unlikely keys (for example, it's not going to be AAA).

Furthermore, they could identify individual radio operators by how they transmitted their Morse Code, known as a "fist".  Certain operators would have certain ways of picking their keys, or certain ways of writing their messages to provide cribs, and the cryptographers could use this to their advantage.

The Enigma machine had other mathematical flaws which were exploited.  Rather than going into them here, I recommend Numberphile's excellent videos on the subject.

158,962,555,217,826,360,000 (part one)
The Flaw In The Enigma Machine (part two)
Extra Enigma Footage

In addition Simon Singh's book on code breaking, "The Code Book".


AES MixColumn Polynomial Transformation I just read about the AES MixColumn step, which can be calculated as:
$$b(x)=c(x)a(x) \pmod{X^4 +1}$$
$a(x)$ is the column to encode and $c(x)=3x^3+x^2+x+2$
My question is: how did they calculate $c(x)$?

Each column of 4x4 byte array S is regarded as column vector over the Rijndael field F.
It is then updated by multiplying the column vector by a specified 4x4 matrix over F.
Thus muxColumns modifies the state array by hte matrix multiplication (0<=j<=3),
Hence, in your example you are encoding ${S_{(3,3)}}$ which is last row of Matrix and represented as polynomial ${3x^3+x^2+x+2}$


Inconsistent terminology for ciphers and algorithms I've been baffled by all the different kinds of names which are given to cryptographic algorithms.

There are block ciphers and stream ciphers (AES and RC4).

There is symmetric and asymmetric encryption (AES and RSA).

I get that block ciphers and stream ciphers are symmetric encryption, but Wikipedia makes things more difficult because it states it's the other way around:

  By type of key used ciphers are divided into:

  symmetric key algorithms (Private-key cryptography), where the same
  key is used for encryption and decryption, and asymmetric key
  algorithms (Public-key cryptography), where two different keys are
  used for encryption and decryption.

then it goes on to say:

  Ciphers can be distinguished into two types by the type of input data:

  block ciphers, which encrypt block of data of fixed size, and stream
  ciphers, which encrypt continuous streams of data

However, RSA is not a cipher because it is not a block cipher nor a stream cipher, is it?

So am I missing something, or is there indeed a gap in this terminology?

It sounds like you're basically asking for a definition of the word "cipher".  I agree that it's somewhat fuzzy and complicated — that's mainly because "cipher", on its own, is not a precisely defined technical term in modern cryptography, but a descriptive word whose meaning, like that of most other English words, has evolved gradually over time.

So, let's start from the beginning.

The word "cipher", as any good dictionary can tell you, originally comes from the Arabic word ṣifr (صفر), meaning "empty" or "nothing", and also the numeral zero.  As the Arabic numerals (notable, compared to the older Roman numerals, for their inclusion of a symbol for zero) were introduced to Europe, this word was adopted into Medieval Latin as cifra, whose meaning broadened to cover any of the Arabic number signs, or even any other strange sign or symbol.  (These senses are still retained e.g. in the French word chiffre, whose meanings include "numeric digit", "figure" and "cipher".)

It's not fully clear how the word used for Arabic digits came to be also applied to any kind of secret or obscured writing system, but given that the new number system was only adopted gradually, and long remained, in the public view, a strange and incomprehensible notation only used by a few learned men and secretive merchants (who, being also generally interested in confidentially recording and discussing matters financial and political, were also early adopters of cryptography), it is perhaps not surprising.

In any case, by the 19th and early 20th centuries, during the peak days of the "classical cryptography" era, before the introduction of computers and modern cryptographic theory, methods of transmitting encrypted messages had come to be generally divided into two broad categories: "codes", which replaced words or entire phrases with specific agreed-upon symbols (often distributed in "code books"), and "ciphers", which were based on replacing and/or rearranging individual letters in a message.
While codes were generally regarded as more secure (since a good code offered fewer opportunities for a cryptanalyst to find patterns in the message), ciphers had the definite advantage of being able to encrypt any messages, even ones that the compiler of the code book had not anticipated.

The ciphers used in the classical era were, in turn, grouped into several distinct types, such as:

substitution ciphers, which worked by transliterating the message into a secret alphabet; and
transposition ciphers, which instead used the normal alphabet, but shuffled the letters of the message into a seemingly random order according to some prearranged pattern.

Of course, an advanced cipher might combine both of these types, and there were even systems, like the French Great Cipher, which combined elements of ciphers and codes.  Also, while the simplest substitution ciphers used just a single fixed secret alphabet, more advanced schemes — like Bellaso's chiffre indéchiffrable, commonly misattributed to Blaise de Vigenère, or the later rotor machine ciphers of the 20th century — used a different alphabet for each letter of the message, making them considerably harder to break.

The electromechnical rotor machine ciphers, such as the famous German WWII Enigma machine, were the state of the art for much of the early and mid-1900s, during the transition period from classical to modern cryptography.  They (like the older polyalphabetic substitution ciphers of Bellaso, Vigenère and others) may be seen as early examples of stream ciphers, although the term "stream cipher" did not really enter the common vocabulary before the 1970s:

Graph of the relative frequencies of the terms "stream cipher", "block cipher", "substitution cipher" and "transposition cipher" between the years 1900 and 2000, generated using Google Ngram Viewer.

What happened in the 1970s was the invention of a new kind of cryptographic tool — the block cipher, developed in its modern form by Horst Feistel at IBM, who designed the Lucifer cipher that eventually became DES.  (Of course, the idea was not entirely without precedent: the Hill cipher, from 1929, had also operated on blocks of characters, as did the various earlier polygraphic substitution ciphers, and of course much of the general theory had been introduced by Claude Shannon in 1949.  Still, in many ways, Lucifer and DES did represent a strong and radical departure from earlier traditions in civilian cryptography.)

The thing about block ciphers is that, unlike stream ciphers (a term which, in its broadest sense, covers pretty much every practical encryption system capable of encrypting arbitrarily long messages), a block cipher is not really very useful on its own: it's great if you just happen to need to encrypt blocks of, say, 64 or 128 bits into other blocks of the same length, but how often is that the case?

To make a block cipher practically useful, you will need to combined it with some kind of a higher-level scheme (often called a mode of operation) to turn it into a more general-purpose encryption scheme (which will, usually, be some kind of a stream cipher, in the broad sense).
Thus, a block cipher is perhaps better regarded as a useful tool for building ciphers (and other cryptographic schemes), rather than as a general-purpose cipher in itself.

So why apply the name "cipher" to them at all, then?  Well, for one thing, that's the name the folks at IBM and NBS (now NIST) chose to use back in the 1970s, and the rest of the world simply followed their lead.  From a historical perspective, it's also a fairly understandable decision: in cryptographical parlance of the day, a "cipher" was something used to encrypt data, and that's certainly what DES did, if in a somewhat unconventional manner.  Thus, it made perfect sense at the time to call it a "cipher", but specifically a "block cipher", to differentiate it from other types of ciphers used at the time.

However, the end result of all this is that, today, we have two different kinds of "ciphers" used in modern cryptography: stream ciphers, which are used to encrypt (streams of) data, and block ciphers, which are (mostly) used to build other kinds of cryptographic algorithms (including stream ciphers).

What about asymmetric encryption schemes like RSA, then?

Well, they're certainly ciphers in the broad sense of "something used to encrypt data", and indeed several authors do use terms like "public-key cipher"or "asymmetric cipher".

On the other hand, if block ciphers are somewhat restricted in their direct applications, public-key algorithms like RSA are even more so.  For one thing, a block cipher can encrypt any string of 64 or 128 bits; RSA can encrypt a number between 0 and the recipient's RSA modulus (minus one).  This may not seem like much of the difference (since it's easy enough to map bitstrings to numbers and back), but do consider the fact that this means that the space directly encryptable messages is different for each RSA key.

Also, "textbook RSA" is only secure if the messages are unpredictable, more or less uniformly distributed between 0 and the modulus, and if the same message is never encrypted with multiple RSA keys.  If the messages belong to a small subset of the full range, an attacker can easily decrypt them by a brute force attack; if they're too small compared to the modulus, or if the same message is encrypted with too many keys, they may be able to break the encryption much more easily than by brute force.

Also, even if those problems are fixed by appropriate padding (effectively adding enough (pseudo)random bits to the messages to make them unique, unpredictable and long enough), RSA (like most asymmetric encryption schemes) is still poorly suited for directly encrypting long messages.  Thus, the standard way of using RSA is a part of a hybrid encryption scheme, where the data is first encrypted using a symmetric encryption scheme (i.e. a stream cipher, broadly speaking) with a random key, and that random key is then encrypted with RSA.

All these issues make some cryptographers (including myself, to some extent) reluctant to call RSA a "cipher", in the same sense as the term is applied to modern stream ciphers and earlier classical substitution / transposition ciphers.  In these people's minds, a "cipher" is something you could use to encrypt a normal plaintext message (and not just a random number in some interval) directly, whereas RSA would be better described as just an "algorithm" (in its "textbook" form, which is not really secure on its own) or a "cryptosystem" (with all the additional trappings needed to turn it into a secure and usable encryption scheme).

(Ps. It's worth noting that there's quite a bit of variation between different public-key encryption schemes, in terms of what they can encrypt directly.  For example, traditional ElGamal encryption is pretty flexible, and can safely encrypt any number less than the (fixed) order of the group, which may be, and usually is, shared by all recipients.  Conversely, for most elliptic curve based systems, even just efficiently and unambiguously encoding an arbitrary message as an encryptable curve point is a non-trivial exercise.)


Is obfuscation considered a cryptographic primitive? The general definition of obfuscation is the process of obscuring a message (not necessarily source code). There is a "rigorous" method for obfuscation (indistinguishability obfuscation, extractability obfuscation) and a less rigorous one (spaghetti code, antipatterns, seldom used languages behaviours, ...). But is obfuscation a type of cryptographic primitive?

I don't think this can be answered with facts or definitions - so this answer is just my opinion:

If you have a specific obfuscation with some cryptographic security property in mind, e.g. IO, and use it to build something else: Then yes, it is. If you just use it as a general term to describe something possibly non-cryptographic (code obfuscation, etc.), then it isn't.

Generally, I think the word obfuscation alone is underspecified. So the first counter-question probably should be: What do you mean? At least in the context of cryptography, definitions matter a lot. And if in doubt: Assume the 'wrong' meaning and say "No, it isn't".


Text encryption algorithms that can be used and are secure what text encryption algorithms are being used nowadays that are secure? Obviously I am not interested in DES or 3-DES that google shows me and which can break...

Generally we first encode the text to binary and then do the encryption. Then we can decrypt and decode to text again. If that suits your need then you can use any secure cipher. The conversion of a textual message to binary is called character encoding. UTF-8 is probably the most used encoding as it supports all Unicode characters & code points, keeps text relatively small and it is compatible with US ASCII. So there is generally no need for specialized text encryption algorithms.

If the ciphertext also needs to be text then you can perform an additional binary to text encoding. Before decryption you need to decode the encoding-specific text to binary again. Base 64 is probably the most used, as it is relatively efficient (6 bits per character) and ASCII (and thus UTF-8) compatible.


SCP03 - Does it always to depend on pre-provisioned static keys? I am trying to understand Secure Channel Protocol 03 from specified by Global Platform and have seen a few implementations. From the standard:

  Session keys are generated to ensure that a different set of keys is used for each Secure Channel Session. The session keys are derived from the static Secure Channel keys.

"
From what i have understood, there is a set of keys known to both parties (host and the card) refered as " static Secure Channel keys". So any new session is encrypted with a new set of keys that are freshly derived from the static keys but those keys are always derived from the same static keys.

Isn't this a security vulnerability ? I mean wouldn't doing asymmetric channel encryption like Diffie-Hellman for every session and continuing  with symmetric encryption there on be a lot better ?

I am relatively new to the field and might be missing something fundamental or this might be an affordable risk compared to the overhead and implementation complexity. Any clarification is appriciated.

A few words on SCP03

As you said, SCP03 is based on the shared knowledge of some symmetric keys (refereed as static keys). This can be seen as a weakness more than a vulnerability since deriving multiple keys from common materials does not break the security guarantees offered by the protocol.

For each sessions, new keys are derived based on:

The shared static keys,
Some constants defining the length and usage of the key,
The session random challenges, one challenge generated by each peers. Each of the challenge is 8 or 16 bytes long (depending on the mode chosen by the Off-Card Entity), avoiding key collision.

In case of pseudo-random challenge generation (i.e not random), a 3-bytes counter is held on the card and involved in the generation process (only card-side). One counter is bind to a key set (i.e. a static shared keys collection), and the counter is is set to 0 whenever the key set is updated.

At each challenge generation, the counter is incremented and one. Once it take the maximum value, the card will refuse to generate a new challenge, making it impossible to complete a SCP03 session. This means that the session key set can only be used in a limited number of sessions, hence it can only be used to generate a finite number ($2^{24}$) of session key sets.

As a side note, the card send the counter to the Off-Card Entity as part of its response to the INITIALIZE UPDATE APDU, but it is not involved in the Off-Card entity side of the generation.

Asymmetric based SCP

Relying on public key cryptography, with a Diffie-Hellman-like scheme would be a better choice since it would namely:

Make key management more straightforward (no sharing)
Ensure forward secrecy

Due to the constraint of such an asymmetric scheme (PKI, large key storage, heavy computational cost), symmetric cryptography has been favored in a first time (SCP01, SCP02, SCP03). For long, RSA have not been available at all on smart cards.
As for today, the trend is slowly changing: GlobalPlatform has issued SCP10 (see the card specification, Appendix F) and SCP11 (see Amendement F) relying on RSA and ECC respectively. They both allow authentication and key exchange, before continuing with symmetric cryptography to communicate.

Smart card industry is a very slow-paced world when it comes to upgrade since deployed hardware can't be upgraded (usually). To give you an idea, SCP03 took almost 8 years to be implemented and deployed, despite its similarities to the widely deployed SCP02, and you can still find a lot of SCP02 in the wild, even so it is  has been shown to be vulnerable to some attacks.

Some say that SCP10 will be skipped altogether, and the SCP11 will be used instead, but RSA is more widely supported.
That being said, I couldn't manage to find any SCP10 or SCP11 open source implementation.


How many NVidia 3090 would you need to brute force a 1024 key in one day? How many NVidia 3090 would you need to brute force a 1024 key in one day?

Brute force means running $2^{1024}$ operations. NVidia 3090 has $10496 \approx 2^{14}$ cores, each running at 1.70GHz which is approximately $2^{30}$ operations per second. Making the ridiculous assumption that a single clock cycle suffices for verifying a key, this comes to $2^{44}$ operations per second.
Before going to $2^{1024}$, let's consider 128-bit keys for AES. This would take $2^{84}$ seconds which is about $6 \times 10^{17}$ years. So, if I take a server farm of 1 trillion (about $2^{40}$) NVidia 3090 devices, then it would take "only" $2^{44}$ seconds, which is about 550,000 years. Of course, it would be much longer since you can't verify a single AES key guess in 1 clock cycle.
Let's now look at the entire power of the bitcoin network. This is estimated to run at about 150 million Terahash per second, which is about $2^{67}$ operations per second. That is absolutely huge! However, it means that it would take $2^{61}$ seconds which is 70 billion years. Just to reiterate - it would take 70 billion years for the entire bitcoin network to brute force a 128-bit key. (Of course, that network is computing SHA256 hashes and not AES computations, but you get the idea.)
Forget about 1024-bit keys and brute forcing. 128 is already too high for that.


Signal vs Telegram in terms of protocols? Some time ago, the question was asked in chat, why MTProto (Telegram's protocol) is supposedly worse than Axolotl (Signal's protocol) as both protocols have been the inventions of their respective companies, thereby "rolling their own crypto", which by agreement is bad.

At this point, stating that the protocol is "worse" was my action and shall not influence answers.

To get a more complete answer to this widely interesting question I'm hereby asking for a canonical answer that compares MTProto with Axolotl and uses well-defined and well-accepted cryptographic knowledge and standards.
A responder may (but does not have to) put a conclusion promoting one protocol over the other.

An answer may include, but doesn't have to or is limited to the following points:

Broken security ("On the CCA (in)security of MTProto" by Jakobsen and Orlandi).
Highly non-standard modes (e.g. IGE).
Highly discouraged modes (e.g. MAC-and-Encrypt)

Alright, I'll bite.

First, let me propose bounding the discussion to just the core of the protocol.

In particular, let's not get hung up on:

Social engineering attacks
How broadly the end-to-end encryption is applied (i.e. are all conversations in the app encrypted?)
The backgrounds of the inventors and reasoning for inventing the protocol
Metadata leakage (i.e. who is talking to whom, which is pretty much the same between the two protocols)

There's a surprising amount of vitriol floating around the internet on those points, NONE of which is germane to the discussion at hand.

MTProto

EDIT: the following is specific to MTProto 1.0.  MTProto 2.0 has since been released, in late 2017.  Some of the potential problems discussed below have been fixed (ex. they migrated from sha1 -> sha256), while others have not seen updates (ex. MTProto 2.0 still uses IGV).  I encourage people to read the new spec (the url is the same; the content has been updated).  I would also encourage any sufficiently-motivated, enterprising individual to write a new answer that takes into account updates to the protocols. :)

Let's quickly review the basics of MTProto 1.0:

(Full specification for those interested: spec v1 )

The protocol starts with a standard Diffie-Hellman key exchange.  Users can compare a hash of the generated key, exposed as either an image and hex code, for the two parties to exchange over an existing secure channel (preferably, in person).  There was a theoretical vulnerability where the original image wasn't large enough (and hence the key-exchange could be man-in-the-middled by someone with sufficient resources), but that's reportedly been fixed by increasing the size of the images / hex printout.  The session key ("auth_key") is derived from this original key (see the spec for particulars).

The meat of the specification hinges on the message envelope.  Briefly, it takes the payload, prepends a salt and session ID, hashes that (SHA-1), and uses that as the "msg key" (MAC).  This also gets mixed with the auth_key (SHA-1 based KDF) to produce a per-message encryption key (256 bit) and initialization vector (256 bit).  The salt, session ID, payload, and 0-15 bytes of arbitrary padding are then encrypted with AES in IGE mode.  Finally, the auth_key_id, "msg key" (MAC) and encrypted data are concatenated to produce the final message.

Whew.  Actually, the diagram from the spec makes much more sense.

MTProto makes what many cryptographers would consider odd choices.  You pointed out several in your question.

A hash algorithm that's reaching the tail-end of its life (SHA1)
An old attempt at authenticated encryption (IGE), of which the authentication part has long-since been broken, but which MTProto doesn't actually use to provide authentication.
A discouraged mode (MAC-then-encrypt)
Vulnerability to a chosen-ciphertext attack  (which may not have been a choice as such).
A non-standard padding algorithm (which is to say, "append whatever bytes catch your fancy")

Those are the sorts of decisions that give cryptographers the willies - and rightfully so.  They've all been broken in various ways.

However - I'll point out that, just like choosing good primitives doesn't necessarily guarantee a secure protocol, choosing bad primitives doesn't necessarily guarantee an insecure protocol.  Anecdotally, bad primitives have probably lead to insecure protocols more often than good primitives have lead to secure protocols, but that's beside the point.  Bad primitives can still be secure as long as you side-step the parts of them that are broken.

Let's examine that:

Would a break in SHA1 lead to a break in MTProto? (it would probably allow an attacker to forge a single chat message per collision; but we're not quite there yet as of 2016)
Does the known problem with IGE lead to a break in MTProto? (no; they're not depending on the authentication)
Is MAC-then-encrypt used improperly in MTProto? (no)
Does the IND-CCA attack invalidate the security guarantees of MTProto? (the authors admit not, at least tentatively)
Does the padding algorithm make MTProto susceptible to any attacks? (technically yes, since it's used in the IND-CCA attack, but again, it doesn't lead to known plaintext-recovery attacks)

Then why do those choices give cryptographers the willies?  First because of experience: even if two choices are not problems on the surface, they can sometimes interact in non-intuitive ways to result in real problems.  In a sense, problematic choices are anecdotally multiplicative in complexity and probability of breakage.  (By analogy, that's an inherent property of high-dimensional design spaces.)  Also, cryptographers have to think about lots of unknowns: are nation-state attackers using unpublished vulnerabilities in any of those underlying algorithms?  Those are particularly concerning since, again, they can interact badly with other design decisions.

Axolotl / Signal Protocol

The Signal Protocol (formerly known as Axolotl) is, to some degree, an orange to MTProto's apple.  It solves different problems, and is concerned with slightly different security model.

For example, Signal is primarily concerned with key derivation and updates/ratcheting (the Axolotl Ratchet, now called the Double Ratchet Algorithm; DRA for short), while MTProto is primarily concerned with the message envelope format, assuming that key exchange has already taken place via fairly generic Diffie-Hellman.

The goal of the Double Ratchet algorithm is to minimize the impact of compromised keys.  This article explains how it works better than I ever could, but the gist is this:

DRA takes the best properties of DH ratcheting (used in OTR - the "Off The Record" IM protocol) and symmetric key ratcheting (used in SCIMP, the Silent Circle Instant Messaging Protocol).

Breaking that down:

SCIMP uses a (one-way) KDF to derive a new key after every message is sent, and the previous key is promptly forgotten.  This way, if the key is ever compromised, it can only be used to decrypt future messages, not past messages.
OTR renegotiates DH keys for every round-trip of messages between parties, and thus self-heals compromised keys after a round-trip has taken place.  This limits the exposure window, but the window can extend into the past in this case, unlike with SCIMP.

DRA on the other hand, regenerates per-message keys like SCIMP, but also renegotiates the DH keys for every round-trip.

The envelope used in the Signal Protocol is unremarkable (in a good way), when compared with MTProto:

Encrypt-then-MAC (using HMAC-SHA256)
AES in CTR mode, PKCS5 padding (>= version 3, at least)

No red flags there.

A formal analysis showed that the Signal Protocol (then called TextSecure) is vulnerable to an Unknown Key-Share attack, whereby B can trick A into sending message M to C, such that A believes it has actually sent M to B.  The paper suggests a way to mitigate that attack, but I wasn't able to find any information as to whether that change has actually been applied.

Conclusion

In the envelope, Signal uses a simple Authenticated-Encryption (AE) system, whereas MTProto uses a custom wrapper that, through a series of odd choices, doesn't qualify as AE or IND-CCA.  Although there are no known plaintext-recovery attacks in MTProto (yet), those properties could well lead to theoretical (or practical) attacks.

For key derivation, Signal has a good story to tell: compromising the current key will only compromise a set of future messages (possibly zero; until the next message from the other party arrives).  However, in MTProto, compromising the authorization key (which is the closest equivalent key) allows all past and future messages to be compromised.

Personally, I (as a developer) wouldn't use MTProto except if I needed interoperability with Telegram.  The folks behind the Signal Protocol (Open Whisper Systems) have fairly universally been praised for the security of their protocol, which makes it an obvious choice.


Is encryption with the Web Cryptography API resistant against side channel attacks? If I want to encrypt some payload with AES-GCM, with the Web Cryptography API, how resistant would this be against side channel attacks?

The safe academic thing is to assume that no, something using the Web Cryptoraphy API can not be assumed resistant to side-channel attacks.

The Web Cryptography API is, as the acronym states, an Application Programming Interface. What it does is platform-dependent. For example, in a browser environment, the code that implements that API is browser-dependent (including version), and what it interfaces to can be OS-dependent (including version). User-settings may matter, compilation options of the native code often do. Plus, the feasibility of side channel attacks turns out to be CPU-dependent, microcode-of-the-CPU-dependent, setting-of-the-BIOS-or-virtualization-environment-if-any-dependent...

However, the worst is not certain! Actual feasibility of side channel attacks is extremely attacker-capabilities-dependent, and quite often it is pointless to assume that the attacker has a foot in the client machine (for in this case the attacker has options beyond side-channel attacks). And once there is the constraint to be platform-independent, perhaps the Web Cryptoraphy API is the best thing to use: rolling one's own side-channel-resistant implementation in JS is bound to be much less efficient than a native implementation, hard to the point of being next to infeasible, potentially ruined by the execution environment, and rightly recommended against by every expert.


"Reduced to" vs "deduced from" Assume it's proven: "Security of protocol $\Pi$ can be deduced from hardness of problem $P$".

Is it correct to state: "Security of protocol $\Pi$ can be reduced to (hardness of) problem $P$" ?

My question is about accepted VOCABULARY in the field of cryptography with provable security.

This is a simplified version of this question, where the first of the above assertions is (I assume, rigorously) established by exhibiting an algorithm that would solve problem $P$ from an algorithm that would break protocol $\Pi$. I read two interesting answers (which I thus upvoted) concluding for one that that reduced "cannot (technically)" be used in this way but remains understandable in the context, for the other that it's "appropriate".

For a non-native speaker like me, that's far from trivial.

I think you are right (in the other question): “security of protocol $P$ reduces to assumption $X$” is incorrect (or at best too sloppy) language, and has too much potential for confusion. This is both because the intended “direction” of the reduction is not completely clear (does breaking $P$ imply breaking $X$, or the other way around?), and a reduction is supposed to be from one computational problem to another (but “security of $P$” is not a problem).

Saying “security of $P$ is based on assumption $X$” is fine, and is more naturally phrased than “breaking $X$ reduces to breaking $P$.” Though it is perhaps not entirely explicit that there is a formal reduction, because a few authors might say this even without a reduction. (But I think they would be wrong to do so.)

All this is somewhat a matter of opinion, relating to prescriptivism versus descriptivism in language. The descriptivist argument is that words and phrases take on meanings when enough people say they do, so “security reduces to” is fine. But for precise technical and mathematical language, especially where the intended meaning could be one of two completely different things, I would lean toward prescriptivism, and “reduction”/“reduces to” already have established meanings that were inherited deliberately from complexity theory.


Modular exponentiation with Chinese Remainder Theorem I'm learning modular exponentiation with Chinese remainder theorem.

I found a great answer from below
How can I use eulers totient and the chinese remainder theorem for modular exponentiation?

But I can't understand the last step of construction from $C_p$ and $C_q$ very well. Can someone explain it to me? Moreover, if I make $N = 55 = 11 \times 5$ instead of $5 \times 11$, that last step fails to give correct answer.

The last step:
$$M^e \bmod{pq}= C_q+q((C_p−C_q) \bmod p)$$

First, you got the last line wrong, it's
$$M^e \bmod{pq} = C_q+q(q^{−1}(C_p−C_q) \bmod p)$$

The basic idea of the CRT is that if $a$ and $b$ are relatively prime, working modulo $ab$ is the same as working modulo $a$ and modulo $b$ separately. In the case of modular exponentiation, exponentiating an element modulo $a$ and then modulo $b$ is much cheaper than modulo $ab$, because you can work with smaller exponents.

About that last step, it's standard CRT computation, you have
$$\left\{\begin{array}{l}
M^e \equiv C_p \pmod p \\
M^e \equiv C_q \pmod q
\end{array}\right.$$

The second line gives $M^e = C_q+kq$. Plugging that into the first gives $C_q+kq \equiv C_p \pmod p$, so $kq \equiv C_p-C_q \pmod p$. Since $p$ and $q$ are relatively prime we can take $q^{-1} \bmod p$, so $k \equiv q^{-1}(C_p-C_q) \pmod{p}$, so $k = q^{-1}(C_p-C_q) + k'p$. Plugging that into $M^e = C_q+kq$ gives the desired expression.


Can I use 128 bits of entropy and a KDF to make a 256-bit ECC key? Since ECC over P-256 provides only 128 bits of security, I'd like to cut corners and generate a private key using HKDF to generate 32 bytes of key material from an input secret that's only 16 bytes long, on the theory that it's no harder to brute-force the KDF than it is to break the key using Pollard-rho.

This seems like a bad idea, but I can't prove it!

This is 100% safe, assuming your 128 bits of entropy is generated properly, and assuming your attacker is only trying to attack one key.

If you did use, say, 17 bytes (136 bits) of entropy for your KDF, then the attacker would simply choose to break the ECC using Pollard Rho, instead of breaking the KDF using brute-force, and in this case they would still not need to do any more than $ 2^{128} $ work. (This is the weakest-point principle in action). This means that using more than 128 bits of entropy to generate a 256-bit ECC key is useless, unless your attacker is trying to break multiple keys.

In that case, using 256 bits of entropy to generate the ECC key would be completely justified, since it prevents certain batch attacks. Daniel J. Bernstein has a great blog post about batch attacks.


Key Handling in Multi Platform Applications I'm working on a mobile application with which a signed in user can send encrypted data to a serverside backend. Also, the user may log in to some website on his laptop and view his encrypted data then decrypted.
My plan is to use AES for encryption but I can not figure out a good solution how to handle the AES key. As a user's password is often not >= 128 bit strong, I don't won't to use the user's password for encryption. Also, generating a key and storing it somewhere in a remote database is a bad idea in my opinion as the key would be accessible for any intruder.
So, is there a best practice to handle such situations?

This answer will orientate around "Method to Protect Passwords in Databases for Web Applications" by Contini, you really should read this paper and follow it with the here proposed modifications.

Your objective is to secure an AES key on the server end, because it needs to be available regardless of devices and the only ressources you can use are usernames and (bad) passwords.
The obvious strategy is to encrypt this key and only temporarily decrypt it when needed using the password. For this you derive a key from the password using a password-based key derivation function (PBKDF) and encrypt the key afterwards with AES-GCM, which will tell you whether the decryption is valid and the user is authorized as a bonus.
In regards to this, the paper will tell you to hash the password hash one more time on the server end. You replace this with the AES-GCM decryption of the key. Additionally you should use Argon2, scrypt, bcrypt or PBKDF (in order of preference) for the client-side password hashing.

So far for the modifications, now for a quick TL;DR of how the scheme roughly works:

Ask the server for access, include the username and the server (domain?) name
Receive the username, website and server-side secret dependent salt (even for usernames that don't exist in the database)
Do the password hashing and send the result to the server
Try to decrypt the AES key using the password hash
Grant or deny access based on whether the user exists and whether the hash was correct


Why not encrypt salt? Assuming I had to distribute salt+ciphertext together over an insecure channel, isn't it better to store the salt encrypted?

By encrypted I mean with a block cipher and with key and IV derived from the same passphrase used to encrypt the original text.

I've been told that leaving salt unencrypted is the way to go. Why? Why not encrypt? Isn't it always better?

No, it is not better. To send the salt encrypted, one would need a key and IV (another salt) to encrypt it. This adds unnecessary complexity as the security of the ciphertext does not depend on the salt being kept private. So, encrypting the salt adds negligible security yet adds a fair amount of complexity. Keeping things as simple as possible is often a good rule of thumb.


How do disk encryption programs solve the "IV problem"? I was reading a paper on the "elephant diffuser" used in BitLocker and it got me wondering how other systems (e.g. TrueCrypt before it shutdown) solved the problem the elephant diffuser was meant to solve; namely that there isn't enough space on a disk block to store an IV.  Where is the IV stored in other systems or do they have alternative solutions?

The problem is not to store an IV but to store an authentication tag.

I don't know about any other products that solve this problem in a way similar to BitLocker. LUKS uses XTS by default, and TrueCrypt supported LRW and XTS, among other modes. Neither of these two modes provide any diffusion. Information about various modes for disk encryption is available here.


Which PRNG security requirements do I need for key generation Do I need to worry about "predictability" an an allegedly secure CSPRNG if I am just using it to generate key material from time to time?

Suppose that for some odd reason, I am less trustful today than I was last week of SecRandomCopyBytes() in OS X and iOS and of CryptGenRandom() in Windows. If I am using this for occasional key generation instead of for the basis of a stream, can I get away with just de-biasing them?

What we're doing…

I have an application which occasionally needs to create AES keys, HMAC keys, and IVs for CBC mode.  Most of the AES/HMAC key pairs are used for single records, and so a new set of keys need to be generated when a new record is created. When the database is first created a set of very high value master keys are created.

Extra measures for the very high value keys…

Currently, for the master key pairs, we already don't fully trust the operating system provided RNG, and so we actually request 256-bytes of data from that RNG and then hash that down to 512 bits using SHA512.  (The first 256 bits are used as an AES key and the second 256 bits are for an HMAC key.)

The intent here is that if there is some unknown (to us) bias in OSs CSPRNG, then grabbing more of those bytes than we need and then hashing them down should wash away any bias that could be hidden in those. (Larger bias, we hope, would have already been detected.)

For all of the other keys, we just the OSs CSPRNG directly.

How many keys, how fast…

Under normal usage, two 32 byte keys will be generated at nearly the same time (AES and HMAC keys, along with a 16 byte IV and a 16 byte item identifier), when a single item is added to the database. But on data import or conversion a few thousand items may be created within a second.

And restating my question in light of the application…

Given the way that I'm using the outputs of that RNGs, do I need to take additional measures (such as XORing against an additional and independent RNG)? Or should I only be worrying about bias in the RNGs?

A second question is whether the de-biasing measure I've described makes sense.

Update: What passes for my threat model (tin-foil hat mode)

I am acknowledging the non-neglible possibility that 'CryptGenRandom()' and 'SecGetRandomBytes()' may have been "adjusted" by the NSA to be weaker in a way only known to the NSA. Certainly some of the users of our application may well consider that "non-neglible" (I no longer put much stock in my own intuitions about what they NSA would or wouldn't do given an opportunity.)

But I also assume that any such adjustment would have to be very subtle. And I imagine that such subtle mischief would have to be.

Biasing the output (e.g., making each 16 bytes actually be a hash of only 8 random bytes) of the CSPRNGs, or
Making their output easier to predict from other output (e.g., not reseeding as often as claimed and using a weakened PRNG internally)

Note, I am not considering a targeted attack against my application or an individual user of it. Just a generically tampered with CSPRNG to potentially weaken all crypto that has come to depend on those CSPRNGs.

Given my use of the CSPRNG (low volume, typically for an individual key at a time), I am asking whether I can ignore the second (prediction) kind of sabotage.

Update 2:

After doing a bit more homework, I see that my two distinct security properties actually follow from one property, and so my question isn't fully coherent, although I believe that it can be made coherent by defining bias as predictability based on zero prior output.

The accepted answer of "use a KDF" seems correct. The scheme we do use is a KDF, but one of our own devising. I'll be looking at better reviewed, developed KDFs. Note that I'm not looking for a password based KDF. I'm looking for entirely random keys that are not derived from user input.

Your idea is not bad, but not a magic bullet. Any serious vulnerability at the root CSPRNG as you describe is fatal for the system facing any serious attacker.

A serious vulnerability being that the attacker can at will force values or predict (partially) values generated in a particular timeframe.

A serious attacker is an attacker knowing your protocols and schemes - if you're worried about things like this and follow Kerckhoff's principle then you should assume you are indeed facing a serious attacker.

However, I doubt that things like CryptGenRandom face a serious vulnerability as described above. This does however not mean it's immune to things like related key attacks and biases. This is where your idea could potentially help.

If you're slightly distrustful of the underlying RNG and need high volumes, hash it and most potential biases/attacks should disappear.

If you don't require large volumes of seeding data, get a lot of output from the RNG and use a KDF to limit key space attacks.

If you want any kind of security that's worth it's salt get a hardware random number generator.


Using Microsoft SIDH library for messages signing SIDH library looks good but lacks documentation and samples.
The only signature-related code was found at http://github.com/yhyoo93/isogenysignature/blob/master/tests/kex_tests.c appeared not able to sign/verify message (just measure abstract performance of some partial calculations).

Thus it's not clear how to mix arbitrary message to SIDH signature and then verify the signaure corresponds to initial message?

SIDH is a key exchange algorithm, not a digital signature algorithm. The way SIDH works is each side generates a private, random value along with a corresponding public value. The public values are exchanged, and from this, a shared secret can be mutually calculated. No signing is involved.

If you need a post-quantum signature algorithm, you would want to look at something like SPHINCS. You can also use a classical, non-PQ signing algorithm if your threat model allows it.


what is the block in crypto Sorry for the newbie question, I'm new to cryptography and I have difficulty in understanding what the block is. For example for DES algorithm the block size is 64 bits and the key is equal to 2 to the power of 56.
Can someone explain this to me ? Maybe like I'm 5?

A "block" is the amount of bits your block cipher operates on (There are other kinds of ciphers, see below.)

Think of a Caesar cipher, it replaces letters in words. For example with key 13 it replaces as follows:

A -> N

and

HELLO ALICE -> URYYB NYVPR

Note that the same letter will always be replaced by the same letter. So it operates on one letter at a time.

A block cipher operates not on individual bits 0/1 but on blocks of them so if your block size was four your cipher might do the following replacement:

0100 -> 1110

(Of course what exactly is replaced with what depends on the key.)

Essentially, a block cipher behaves like a permutation of the blocks. Which permutation exactly, is determined by the key. So it is a bijective map $\{0,1\}^{blocksize} \rightarrow \{0,1\}^{blocksize}$.

It is not strictly required for a cipher to have a block size. A stream cipher for example operates on individual bits.

Note, that since a block cipher is a permutation it will replace the same input-block with the same output-block just like the Caesar cipher always replaces the same input-letter with the same output-letter. Because this makes for bad cryptography block ciphers are used in different modes of operation.


Subgroups generators with respect to group generators of composite order If I have a group $\mathcal{G}$ of order $N=npq$ and subgroups $\mathcal{G_n,G_p,G_q}$ of order $n$, $p$, $g$ respectively and if $g$ is a generator of $\mathcal{G}$ why then $g^{nq}$ is a generator of $\mathcal{G_p}$, $g^{np}$ is a generator of $\mathcal{G_q}$ and $g^{pq}$ is a generator of $\mathcal{G_n}$ ? I am trying to understand a research paper

If $\mathcal{G}$ is of order $N$ (who doesn't look like a prime number btw) and $g$ is a generator of $\mathcal{G}$ then $g$ has order N. Since $(g^{nq})^p=1$ and $\forall 1\le k <p, (g^{nq})^k\neq 1$ (g has order $N$ and $knq<N$) then $g^{nq}$ generates a subgroup of $\mathcal{G}$ of order $p$ and there's only one such subgroup : $\mathcal{G_p}$.
The reasoning is the same for the rest.
Hope it's clear and correct


Finding public exponent e I'm trying to create an algorithm to find the public exponent e given a plain (non-CRT) private key that doesn't include the public exponent, i.e. I've only got $n$ and $d$.

A question has already been asked how easy it would be to find the public key given a private key. The answer was that it was likely to be easier, but none of the answers specify a good algorithm for RSA.

What would be the most efficient algorithm for finding the public exponent for RSA given the private key?

The fastest way to solve your problem instance is as outlined in the above comments.

First choose yourself a random message $m$ with $1<m<n-1$. Now compute $c\equiv m^d \pmod n$.

Try if any of the following equations holds, if an equation does hold you've found the public exponent $e$.
$m \equiv c^3 \pmod n$
$m \equiv c^{17} \pmod n$
$m \equiv c^{65537} \pmod n$

If none of the above equations held you have two choices, based on the effort you're willing to spend and the probability that $e$ is rather small.

If you suspect $e<\frac{1}{3}N^{\frac{1}{4}}$, then you should use Wiener's attack on small decryption exponent RSA with the lost public exponent taking the role of the decryption exponent to find. Wikipedia explains the basics and Wiener's original attack.
As Maarten points out in the comments below this attack is very fast and consumes moderate amounts of memory.

If you think / know that $e<2^{40}$ and/or you're not willing to implement Wiener's attack you can use the following approach, as you can always come back to Wiener's attack in case you think that you've tried long enough.
The brute-force approach would work as follows ($i=3$, optimized using fgrieu's comment):

Set $c_m \gets (c * c) \bmod n$,
Check if $c \equiv m \pmod n$ or $c_m \equiv m \pmod n$, if the first holds, output 1, if the second holds, output 2.
Set $c_3 \gets (c * c_m) \bmod n$
Check if $c_{i}\equiv m \pmod n$ holds. If yes, output $i$
Set $c_{i+2}\gets (c_i*c_m) \bmod n$, goto step 3

If you can not apply Wiener's attack and you consider brute-force "way too inefficient" there are still two methods left:

Use your favorite factorization algorithm to factor $n$ and deduce $e$ from $(d,p,q)$
Use your favorite discrete logarithm algorithm to solve $c^e \equiv m \pmod n$ for $e$.


Is there a theoretical maximum useful keysize given the block-size? Consider a block-cipher $F$ with a $N$-bit block-size and a $M$-bit key-size. That is, if  $k$ is a $M$-bit key, $p$ is a $N$-bit block of plain-text and $c$ is a $N$-bit block of cipher-text, then:
$$
F\left(k,p\right) = c
$$

Each plain-text block of $N$ bits must have a 1-to-1 correspondence with a cipher-text block of $N$ bits.

My question is: is there a theoretical maximum number of distinct keys such that in the set of such keys, there are no two keys $k_1$ and $k_2$ for which $F\left( k_1, p \right) = F\left( k_2,p\right)$ for all values of $p$?

For instance, if all we could do was a bit-permutation and an exclusive-OR with masks derived from the key, then  $M \le N + \lfloor\log_2 N!\rfloor$ could be such a maximum. But given for instance the 'MixColumns' and 'SubBytes' steps in AES, many more distinct keys would be possible. But is there a theoretical upper limit?

If you are asking about a truly theoretical limit for a theoretical block cipher (as opposed to a practically usable one, like AES), you could calculate the number of possible keys like this:

A block cipher, together with a key $k$ ($|k|$ = $M$), describes one of many possible random permutations: For every plaintext block, there is exactly one ciphertext block. The number of possible blocks is simply $2^M$, where $M$ is the length of a block in bits.

The number of permutations of $n$ different objects is $n!$, so for our (very unpractical) block cipher, there can be at most $2^M!$ keys. Many of those will be unusable in practice (for some, plaintext and ciphertext will differ for only a single block), but they all satisfy your condition that they differ in at least one plaintext-ciphertext-pair from all other permutations.

Now, specifying one of all possible permutations without any optimization would take an insane number of bits to transfer (the number of plaintext-ciphertext-pairs in the permutation, times the number of permutations: $2^M\cdot2^M!$

To be able to actually transmit the key with fewer bits than any conceivable message, we limit our keyspace to mere $N$ bits, or $2^N$ possible permutations.

If you insert the actual numbers, we get $2^{256}$ possible keys for AES-256, which seems like a lot (and for practical purposes, it is), but the theoretical limit for 128-bit blocks is much, much higher: $2^{128}\cdot2^{128}!$.

Update:
Avijit has pointed out in the comments that there is an easy optimization which allows enumerating all possible permutations with "only" $\lceil log_2 2^M!\rceil$ bits (which allows for $2^M!$ keys). This is a lot more compact, but still much larger than any practical key size.


Does a "commutative" asymmetric system exist? Completely crypto noob here.

I'm looking for a cryptosystem made of a func f + key1 + key2 such that they satisfy:

g(f(msg, key1),key2)=msg
g(f(msg, key2),key1)=msg
key1 != key2

Does such a cryptosystem exist?

Ideally I'd like f and g, to be the same function, but I'm ok if they are different.

It is ok if it's not Fort Knox secure, I want it to play with my nephews but I don't mind going hardcore :)

RSA with random exponents would fulfill your key-swapping requirement. I.e. RSA where you generate one exponent randomly and then compute the other from it normally, with neither exponent made public. The operation to encrypt and decrypt is the same (modular exponentiation).

The security of this scheme, or some uses of it is considered in the (currently unanswered) question: Could this "symmetric RSA" scheme provide key compromise resistant communications?

Since you say you do not need it to be extremely secure, it should fit your bill regardless.


How long does it take to extract a key from a FIPS-140 Level 2 device? How long does it take to extract a key from a FIPS-140 Level 2 device?
What records are there of successful extraction?
How much did the first extraction from a given device cost?
How much would a subsequent extraction cost?

Dr. Google is usually very helpful on questions like this but he isn't helping me here.
Any ideas?

FIPS 140-2 Security Level 2 does not require any form of security measure to prevent extraction of secrets. It simply requires tamper evidence, that is, it should be possible to notice that such attack took place by looking (for instance) at some seal on the device or at a log file.

To answer your question, extracting a secret may therefore take 0 seconds and 0 dollars.

Only Security Levels 3 states that the cryptographic module must respond to attacks, even though the requirements are not phrased in terms of attack cost, but rather of guidelines the module must follow. For instance, it says that the circuitry should be covered in hard epoxy, but not exactly how, so a manufacturer could also choose a substance a hairdryer can easily melt.

A good source of material to look at is Ross Anderson's group at the University of Cambridge, and more in particular the work of Mike Bond.


Is the following crypto compatible so that I can use the same keys for both products (Wireguard & Libsodium)? I am wondering if it is possible to use the public/private keys of two WireGuard peers also in another communication channel using libsodium?

According to the WireGuard Protocol documentation and the WireGuard paper, they are using:

  Curve25519 for ECDH
  ChaCha20 for symmetric encryption, authenticated with Poly1305, using
  RFC7539's AEAD construction

On the other hand, libsodium (which also supports a ChaCha20Poly1305 variant of the same construction) says:

  Sealed boxes leverage the crypto_box construction (X25519,
  XSalsa20-Poly1305)

Importantly, both are using DJB's Curve25519 but I am not sure if their keys are compatible, e.g. if they are using Weierstrass' or Edwards' notation. Can I use the WireGuard keys inside of libsodium, too? Do the two use compatible crypto?

WireGuard uses keys that are on the Montgomery curve, not the Edwards curve. It's the standard X25519 or Curve25519 commonly used for ECDH.

In libsodium, crypto_box_keypair calls crypto_box_curve25519xsalsa20poly1305_keypair which calls randombytes_buf(sk, 32), return crypto_scalarmult_curve25519_base(pk, sk). In WireGuard, wg genkey calls get_random_bytes(sk, 32) and wg pubkey calls curve25519_generate_public(pk, sk). It turns out that crypto_scalarmult_curve25519_base(pk, sk) and curve25519_generate_public(pk, sk) are essentially the same thing.

So this means in theory those keys would be "compatible".

However, you should not do this under any circumstances.

Cryptographic protocols make various assumptions on how keys are used. The WireGuard Protocol is formally verified, which means within the WireGuard handshake, it's been verified that none of the constructions will lead to any catastrophic situations. However, there's no guarantee that re-using these same keys within other random constructions that you might cook up won't interact badly and will retain the same guarantees of the WireGuard Protocol. So, if you reuse WireGuard private keys in your own protocol, you do so at your own risk. That's the kind of thing you only do if you really, really know what you're doing and are certain that there won't be any bad interactions.

(Perhaps a more productive way forward would be to describe what you actually want to do with WireGuard key identities and your libsodium-based protocol. Then maybe folks can help you find a safe way of accomplishing this. What's the overall end goal of your project?)