Turn a password into a key without using salt Assume I have a password with sufficient entropy but may not be uniformly distributed, how can I turn the password into a key that can be used for symmetric encryption?

I think there is surely such a method because when you type gpg -c it asks for a passphrase (more or less a password) not a key.

Ideally this method doesn't require a salt for ease of implementation, unless it's proven impossible.

For passwords with sufficient entropy you can use a KBKDF - a key based key derivation function - that allows a non-constant sized input and performs entropy extraction. The extraction of entropy into an intermediate form of a specific size is made explicit in HKDF by a function called HKDF-extract.

  HKDF follows the "extract-then-expand" paradigm, where the KDF
     logically consists of two modules.  The first stage takes the input
     keying material and "extracts" from it a fixed-length pseudorandom
     key K.  The second stage "expands" the key K into several additional
     pseudorandom keys (the output of the KDF).

  In many applications, the input keying material is not necessarily
     distributed uniformly, and the attacker may have some partial
     knowledge about it (for example, a Diffie-Hellman value computed by a
     key exchange protocol) or even partial control of it (as in some
     entropy-gathering applications).  Thus, the goal of the "extract"
     stage is to "concentrate" the possibly dispersed entropy of the input
     keying material into a short, but cryptographically strong,
     pseudorandom key.  In some applications, the input may already be a
     good pseudorandom key; in these cases, the "extract" stage is not
     necessary, and the "expand" part can be used alone.

Keys can then be derived from that intermediate state by HKDF-expand, which allows additional input parameters such as in the info field that may - for instance - include a label identifying the key to receive the output keying material.

Usually the extraction phase is implicit - not explicitly identified; this is for instance the case for other KDF's that rely on hash functions.

In others the extraction is not present; this is for instance the case for many KDF's that rely on block ciphers. Those start off with a symmetric key, which needs to conform to the requirements of symmetric keys that already presume "concentrated" entropy.

HKDF does not require a salt. It does take a salt as parameter but it may be empty. HKDF is significantly strengthened by a salt though, see chapter 3.1 for more information on when / how to apply a salt with HKDF.

The discussion about these principles for HKDF is applicable to many KDF's that may be equally secure within the protocols where they are used. The good thing of HKDF is that the principles are explicitly named and therefore - hopefully - well argued & applied.


Cocks IBE Scheme: why is -a a quadratic residue mod n? In the Cocks IBE scheme it is required for the hash function, that the Jacobi symbol of its output and the universally available moduls $n = p*q$ is $+1$, so:

$\Big(\frac{H(ID)}{n}\Big) = \Big(\frac{a}{n}\Big) = \Big(\frac{a}{p}\Big) * \Big(\frac{a}{q}\Big) = +1$

So, either both Jacobi symbols $\Big(\frac{a}{p}\Big)$ and $\Big(\frac{a}{q}\Big)$ are $+1$ or $-1$. In the frist case, $+a$ is a quadratic residue modulo $n$, because its the product of two numbers that are quadratic residue mod $n$. So far its clear to me. However, in the latter case, why is $-a$ a quadratic residue?

In Cocks paper [1] it says: The latter case arises because by construction $p$ and $q$ are both congruent to 3 mod 4, and so $\Big(\frac{-1}{p}\Big) = \Big(\frac{-1}{q}\Big) = -1$

If I try solve it for the case that $-a$ is a quadratic residue mod $n$, and that both $\Big(\frac{a}{p}\Big) = \Big(\frac{a}{q}\Big) = -1$,

I come to the following result:

$\Big(\frac{-a}{n}\Big) = \Big(\frac{-a}{p}\Big) * \Big(\frac{-a}{q}\Big) = \Big(\frac{a}{p}\Big) * \Big(\frac{-1}{p}\Big) * \Big(\frac{a}{q}\Big) * \Big(\frac{-1}{q}\Big)$

$ = \Big(\frac{a}{p}\Big) * (-1) * \Big(\frac{a}{q}\Big) * (-1) = \Big(\frac{a}{p}\Big) * \Big(\frac{a}{q}\Big) = (-1) * (-1) = +1$

However, in the last step both Jacobi symbols are $-1$, and thus $-a$ cannot be a quadratic residue mod $n$, because it is the product of two quadratic nonresidues?

I must have made a mistake somewhere, but I don't see it.

[1] Clifford Cocks: An Identity Based Encryption Scheme based on Quadratic Residues, 2001.

If $a$ is a nonresidue mod $p$, then since $-1$ is also a nonresidue mod $p$ by construction, $-a$ is a residue mod $p$. And likewise mod $q$, so $-a$ is a residue mod $pq$.


Why is the strength of an Elliptic Curve Cryptography (ECC) half the size of the prime field size? I've looked around and couldn't find a direct answer. As a general rule, I've read from various sources (here here, and here) that the strength of an elliptical curve key is half of the size of the prime field. I.e. for a 256-bit prime field (like a secp256r1 curve) the we have 128 bits of security and for a 384-bit prime field the symmetrical equivalent strength is 192 bits.

Why is this the case? As I understand it, an $n$-bit symmetric key has $2^n$ bits of security, and an ECC public key is some point $P$ such that $P=k \cdot G (\text{ mod }p)$ where $k$ is the private key and $p$ is the modulus prime field.

secp256r1 has a 256 bit prime field who's prime is a Mersenne prime. So what's going on? Do we use only half the field or...?

This is essentially because the best known generic algorithms for discrete logarithm, e.g., baby step giant step, have complexity $$O(\sqrt{G})=O(2^{n/2})$$
where $n$ is the number of bits to represent the elements of the elliptic curve group $G$.

If the eliptic curve group is carefully chosen, that is. So, avoid anomalous curves, for example.


AES-128 + HMAC-SHA-256 but HMAC truncated I implemented AES-128 in CBC mode + HMAC-SHA-256 but it seems to me that 256 bit HMAC is more than necessary.
Can I truncate the output of HMAC-SHA-256 to a desired bit length?
And what is the minimum required length of it to match the security level of AES-128?

Can I truncate the output of HMAC-SHA256 to a desired bit length?

Yes, in fact, it's quite common to do so...

  what is the minimum required length of it to match the security level of AES128?

Now, that's a hard question; I'll try to try to explain some of the reasons why it is subtle.

To break the privacy of an AES encrypted session, the hard part of the attack is performing a huge number of $X$ operations, where the huge number depends on the AES key size, and desired success probability (that is, the probability that the attack is actually successful); if we assume a 128 bit AES key, and a minimum acceptable success probability of $2^{-\delta}$, then the attacker will need to do at least $2^{128-\delta}$ $X$ operations.  To break the integrity of an HMAC protected session (ignoring brute force attacks on the HMAC key), the hard part of the attack is performing a huge number of $Y$ operations, where the huge number depeonds on the transmitted HMAC size, and desired success probability; if we truncate the HMAC tag to $N$ bits, this requires at least $2^{N-\delta}$ $Y$ operations.

What's so hard about that?  Well, the issue is that the cost of an $X$ operation and the cost of a $Y$ operation is not easily comparable; in most cases, a $Y$ operation is far costlier than an $X$; any analysis that ignores that is (IMHO) a gross oversimplification.

To break privacy, what we do is grab some ciphertext; the $X$ operation consists of selecting an AES key, and checking if that key works with the ciphertext (sometimes, it's a bit more complex than that, but that's the general idea).

To break integrity (again, ignoring brute force attacks on the HMAC key; we'll assume that key is at least 128 bits, so we can ignore that attack), what we do is format some ciphertext (which presumably decrypts to something the attacker would like inject), the $Y$ operation consists of selecting an HMAC tag value, sending the forged message and the HMAC tag value to the legitimate decryptor Bob, and seeing if Bob is fooled.

What's the difference between these two attacks?  In the AES attack, once we've received the ciphertext, the attacker can perform the $X$ operation (the trial decryptions) without any interaction with the systems under attack; our attacker can rent out a large cloud space, grab a large botnet, or throw a large FPGA/ASIC farm at the problem, and we have no idea.  In addition, this attack can be performed even when the session is over; the privacy concerns depend on how long the data will stay sensitive, and that's a property of the data, not the cryptography.

In contrast, in the HMAC attack, we need to get Bob (the legitimate receiver) involved for every single tag we come up with.  If Bob will refuse to check no more than $2^{20}$ tags per second (possibly because that's the limit of what his hardware can do), there's absolutely nothing an attacker can do to speed up the attack.  In fact, if Bob is reading the encrypted message from a storage device, well, he'll realize the storage device has been corrupted after a HMAC failure (which means that we get to do exactly one $Y$ operation.  In addition, even if Alice and Bob use using the HMAC to protect encryption communication, Bob might just notice that the last billion messages all had invalid tags, and so might be able to deduce he's under attack.  Thirdly, this attack can only be done while the session is up; once Alice and Bob have shut down the connection and are no longer communicating, we can no longer try to fool Bob.

Now, if we take the oversimplification that $X$ and $Y$ are approximately the same cost, then it's obvious from the above argument that 128 bit HMAC tags are quite sufficient (and we should use larger HMAC tags only if the larger tags are of essentially no cost).  However, by the above argument, HMAC tags can be safely truncated even more; exactly how far it would be safe would depend on the details of the system.


Public-key encryption with associated data In the symmetric-key world, we have authenticated encryption with associated data (AEAD).  I'm looking for something similar, but for public-key encryption: public-key encryption with associated data (PKEAD?).

Here's how it should work.  Given a message $m$ and a header $h$, let $E(m,h)$ denote the public-key encryption of $m$, bound to the data $h$.  Similarly, given a ciphertext $c$, let $D(c,h)$ denote decryption of $c$ under the corresponding private key, bound to $h$.  We want $D(E(m,h_0),h_1)$ to be $m$ if $h_0=h_1$, or $\bot$ (failure) if $h_0 \ne h_1$.  There is no requirement to provide confidentiality for $h$ (we assume it is public) and no need to include $h$ in the ciphertext (he assumption is that the header $h$ will be transmitted via some out-of-band means).  This binds the ciphertext $E(m,h)$ to $h$, so that decryption will succeed only if the sender and receiver have the same value of $h$ and the adversary hasn't tampered with $h$ in transit.

Also, I want the public-key encryption to be IND-CCA2 secure.

Are there any schemes designed for this task?

I can think of some trivial constructions, but I suspect they are not optimal.  One simple scheme is to let $E(m,h)$ be the public-key encryption of $m||H(h)$ under some standard public-key encryption scheme.  Then $D(c,h)$ decrypts $c$ to get some $m||d$, and returns $m$ if $H(h)=d$ or fails otherwise.  However, this causes message expansion (alternatively, it reduces the maximum length of the message $m$ that can be encrypted).  I suspect one can avoid any message expansion.  Has anyone designed schemes for this task?

There are no schemes that I'm aware of that are specifically designed for this task, i.e. where this was advertised as feature in a description I've come across.

The most standard solution I can provide is McBits (PDF). McBits is based on XSalsa20-Poly1305 and thereby can natively supports the associated data interface if enabled by the implementation. However (good) implementations of McBits are rare, although they shouldn't be too hard given a (standard) McEliece implementation.

What you can also do, is take your generic (IND-CCA2 secure) public key encryption scheme (e.g. RSA-OAEP), encrypt a symmetric key with it and use that key for the AEAD scheme of your choice (e.g. AES-GCM) to encrypt and authenticate bulk data and to authenticate header data.

The more distinguished solution is to just take the KEM of your choice (like the one used by ECIES, DHIES or RSA-KEM), use that to derive the key and then continue normally with your AEAD scheme of choice (e.g. AES-GCM). McBits basically is this with the KEM being standard McEliece encryption of a random vector.


Why does BitLocker not use RSA? If understand correctly from this post and the Wikipedia page for BitLocker and TPM, by default, BitLocker uses symmetric cryptography like AES. However, TPM is capable of performing RSA encryption.
Given that the RSA key is stored in the TPM, why does BitLocker not use asymmetric encryption (i.e., RSA)? By using such an encryption technique, we might be able to defend against the cold boot attack or sniffing on the LPC bus.

Asymmetric encryption is vastly inferior to symmetric encryption. That is, in all respects, except one -- being asymmetric. When that property is needed, there's no way around it, obviously.

Asymmetric encryption is much slower. It is much more susceptible to showing recognizable patterns of some kind given non-random input. You need much larger key sizes to provide an adequate level of protection, and the system is much more vulnerable in general with current and future technology (reasonably-sized quantum computers will basically mean instant death for RSA, but AES is pretty much "yeah, so what" in that respect).

That's the reason why asymmetric encryption is almost never used to encrypt bulk data.

Nothing prevents you from encrypting a terabyte of data with RSA using 2048 bit chunks, much like you encrypt a terabyte with AES in 128 bit chunks. Only just, it doesn't make sense to do that because it is several thousand times slower, and at the same time is much more insecure.


Can double-encrypting be easier to break then either algorithm on its own? As was pointed out in Martin Bonner's comment I cannot prove this, but it seems intuitively impossible.

An encryption function is supposed to obscure the plaintext to the point where no information can be obtained about it. If the underlying encryption algorithm can even be determined, that goal has not been achieved.

Is this correct? Can double-encrypting (with either the same or separate algorithms) weaken security?

Can double-encrypting (with either the same or separate algorithms) weaken security?

If you do not assume that the algorithms and keys are independent, then it certainly can.

The example of ROT13 from the other answer illustrates the point even if it is not real encryption. Similarly, a synchronous stream cipher applied twice with the same key will undo itself. Something like that could be possible with other kinds of ciphers, e.g. you could have block cipher such that $E_k = D_{k'}$ if you choose the keys wrong, or you could define AES' where the encrypt and decrypt directions are switched. A combination of these would be secure with independent keys but not necessarily otherwise.

If you assume keys are independent, the result can still be weaker compared to the stronger of the two algorithms. For example, assume you have CBC encryption that is vulnerable to a padding oracle attack. Even if you add a secure stream cipher on top, the padding oracle attack still exists. With some of those assumptions you can say that the combination is no weaker than the first cipher (pdf).


Computational trapdoor where the problem is tractable for both parties but easier for one Usually the sort of trapdoors which are talked about are designed such as to make the computation intractable for one party and tractable for the other.

But what if one party merely has a big advantage in computation over the other? Can you use it to create a construct in cryptography?

For example, suppose you have a way to construct a large number such that using it as an operand in multiplication is very cheap for you: O(kN) for a k you can somewhat control (by randomly trying many primes looking for such a quality and then multiplying them masking the quality). The best others can do seems to be O(N*logN*loglogN) nowadays.

How can you use this computational trapdoor? The multiplication is tractable for both parties but one has an advantage.

Is there a way with multiplication to amplify a linear advantage into an exponential or polynomial one?

Russell Impaglizzio wrote "A personal view of average case complexity" roughly 25 years ago. In this work, he describes "five worlds" that we could live in with regards to the $P\stackrel{?}{=} NP$ problem. In two of these worlds one can do cryptography, they are roughly summarized as:

Minicrypt: One-way functions exist
Cryptomania: Trapdoor one-way functions exist

To be clear, each of the five worlds describes a possibility of the resolution of the $P$ vs $NP$ problem (and various related problems). So if "we are in minicrypt but not cryptomania", it means that trapdoor one-way functions don't exist, but one-way functions do exist.

What about other cryptographic primitives? There has been a decent amount of effort to show that (roughly) "Minicrypt = private-key cryptography", and "Cryptomania = public-key cryptography". There's actually some really interesting recent work showing that there's more to the story than just this [1], but that's a separate topic.

So if we aren't in cryptomania, can we do public key encryption? Strictly speaking no (that's the point), but we can still hope for something akin to what you're describing --- while our protocols may not be impossible for a poly-time adversary to break, we can "have a computational gap" between honest parties and dishonest parties (although the gap is some polynomial). One of the initial public key schemes was actually of this form (Merkle's Puzzles). There has been some recent work revisiting this (seemingly motivated by "fine-grained complexity"), see Fine-grained Cryptography and Public-key Cryptography in the Fine-grained Setting.

[1] See Minicrypt primitives with algebraic structure and applications. Essentially all minicrypt primitives have been known to be equivalent for a few decades, but cryptomania primitives are not all known to be equivalent. There appears to be ways in which they aren't equivalent, meaning they break up into separate "continents" within the "world" of minicrypt.


Swap $x$ and $k$ in GGM construction I'm studying the Goldreich-Goldwasser-Micali construction from pseudo-random generators to pseudo-random functions. In this specific construction, assume $G:\{0,1\}^n\rightarrow \{0,1\}^{2n}$ is a PRG, mapping $x$ to $G(x)=(G_0(x),G_1(x))$. Then the PRF in this construction is given by
$$F_k(x)=G_{x_n}\circ\cdots\circ G_{x_1}(k),$$
with a random key $k$ in the same length as $x$. The proof is a hybrid argument, by replacing $G_{x_j}\circ\cdots\circ G_{x_1}(k)$ with a truly random function $\{0,1\}^j\rightarrow\{0,1\}^n$.

Now I wonder what if we swap the positions of $x$ and $k$ in this construction, that is to define
$$F'_k(x)=G_{k_n}\circ\cdots\circ G_{k_1}(x).$$
Intuitively one cannot use similar hybrid techniques like above to prove its pseudo-randomness. However I didn't figure out a counter example, as I wanted to keep some information of $x$ within $G(x)$, but the possiblility that this information is maintained after $n$-round of iterations is always negligible. For instance, if we keep the first bit of $G(x)$ being $x_1$, with only $2^{-n}$ probability we can still see the bit $x_1$ in $F_k'(x)$, when $k$ is random.

Are there any methods to prove or disprove the construction $F'_k(x)$ is pseudo-random? Thanks in advance.

$F'_k(x)$ is not necessarily pseudo-random.

Proof:
Changing one output does not affect PRGness, so if there is a PRG

that stretches by a factor of 2 then there is a PRG that stretches

by a factor of 2 and sends all-zero strings to all-zero strings.

For all $n$ and $k$ and $x$, if $G$ is such a PRG then $F'_k(x)$ is the string of $n$ zeros.

For all $n$, if $\: n\neq 0 \:$ then there are other strings with that length.

Therefore $F'_k(x)$ is not necessarily pseudo-random.

(Of course, this doesn't prove that your construction can't be pseudo-random.)


Why is SHA-3 robust against Length-Extension Attacks? If a length extension attack can occur because of $H(\text{K}\mathbin\|\text{Message})$, what changed in SHA-3 from SHA-2 that prevents this from occurring?

Everything was changed between SHA-2 and SHA-3.

In the specific case of the "length extension attack": the issue is that SHA-2 process data by splitting it into elementary blocks (64 or 128 bytes, depending on the SHA-2 variant), and produces for each block an output which has exactly the same size as the function output. Moreover, the output for a complete message is merely the current output after processing all blocks of the (padded) message. This means that anybody can take a hash output and "continue" processing of a longer message with additional blocks.

In SHA-3, a sponge construction is used. The crucial point is that, in a sponge, the internal state is much larger than the hash function output. Thus, you cannot simply "continue" processing of a message by using a hash output, because that output contains only a fraction of the internal state.

You can get the same kind of protection with a SHA-2 function by truncating the output. For instance, there is a (relatively new) member of the SHA-2 family called "SHA-512/256", which is SHA-512 (with a different conventional IV) with output truncated to 256 bits. This truncation makes it immune to the length extension attack.


With AES encryption and a known key and plaintext, can an attacker create a different key and plaintext resulting in the same ciphertext? In short: with AES encryption can an attacker create a new key2 and plaintext2 so that AESkey1(plaintext1) = AESkey2(plaintext2)
If so, can it be solved by just applying for instance a MAC like AES-GCM or an AES-CTR with a SHA256 HMAC?
Intended application:
The encryption of a file. Every client having the key can decrypt the file. The encrypted file is handled blindly by a server (without knowing the key) by its SHA256 hash.
When a new client is handed over a false key with the hosted file, he should be able to detect it is the wrong key. And not getting any other (noisy) binary from the same encrypted file as a result. Noting that an attacker delivering the false key has access to the original key, the ciphertext and thus also the plaintext.
(The option of identical files being encrypted with different keys should be there. So deterministic encryption is not my intention)
An other possible easy solution I thought of would be to store the hash of the secret key together with the encrypted file on the server and send it to the client to verify. But I actually prefer using a well known out-of-the-box solution, and not something I came up with. Is applying a MAC / HMAC enough to guarantee only one key results in the given ciphertext.
Hope my intention is clear, and someone knowledgeable can point me in the right direction.

For basic AES, it is easy to find two keys in this way. Take any $key1$ and $plaintext1$ and compute $c=AES_{key1}(plaintext1)$. Then, take any $key2$ and compute $plaintext2 = AES^{-1}_{key2}(c)$. It follows that $AES_{key1}(plaintext1) = AES_{key2}(plaintext2)$. Having said this, if AES is used in an authenticated encryption mode with a MAC, this may not necessarily be possible. I wish to stress that there is no guarantee that not, and such a thing would need to be proven. In particular, if you did the standard encrypt-then-MAC (with different keys), then this would be vulnerable in exactly the same way, since the "encryption" part is unchanged. Bottom line, this should be possible to achieve, but it's certainly not guaranteed, and often doesn't hold at all.


Why when I perform RSA 5 times do I get my original input back out? If I perform RSA on my input 5 times, I get the original input back out.
Why is it that often, iterating RSA encryption just a few times cycles yields back the original value, when the public modulus N is small?

I read the question as:

  Why is it that often, iterating RSA encryption just a few times cycles back to the original value, when the public modulus is $N$ is small?

With $N$ square-free and $\gcd(e,\varphi(n))=1$, textbook RSA encryption
$$\begin{align}E: [0,N)&\to[0,N)\\
x&\mapsto x^e\bmod N\end{align}$$
is a bijection, equivalently a permutation of the set $[0,N)$.

By the pigeonhole principle, cycling any permutation of a finite set will loop back to the starting point after a number of iterations bounded by the set size $N$. It is easy to show that for a random permutation and a random starting point, probability of cycling on or before $i$ steps is exactly $i/N$.

But if for example we take $e=37$ and $n=13333=67\cdot199$ then indeed we observe that starting from most $x$ we cycle after just $5$ iterations (and for some $x$, e.g. $x=937$, that's down to $1$). This calls for explanation.

Restricting to $N=p\,q$, define $E_p(x)=E(x)\bmod p=x^e\bmod p$, and $E_q(x)=E(x)\bmod q=x^e\bmod q$. By the Chinese Remainder Theorem, the cycle length of $E$ starting from $x$ is the Least Common Multiple of the cycle length of $E_p$ starting from $x\bmod p$, and the cycle length of $E_q$ starting from $x\bmod q$.

When cycling $E_p$ for $k$ iterations starting from $x$, we reach $\displaystyle x^{\left(e^k\bmod\left(p-1\right)\right)}\bmod p$ (by Fermat's little theorem). It follows that whatever the starting $x$, we always are back (though not necessarily first back) to the starting point after making a number of iterations equal to the order of $e$ in the multiplicative group $\Bbb Z_{p-1}^*$ (notice that $\gcd(e,\varphi(n)=1$ insures $\gcd(e,p-1)=1$ and thus that $e$ belongs to that group).

In our example $e=37$, $p=67$, $q=199$, and it happens that $e^5\bmod(p-1)=1$ and $e^5\bmod(q-1)=1$, hence both $E_p$ and $E_q$ cycle after $5$ steps (or just $1$, depending on $x$), and $E$ inherits that property.

But why are short cycle relatively common for moderate $N$?

Define the decomposition of $p-1$ (resp. $q-1$) into prime factors to be $p-1=\prod p_i^{\alpha_i}$ (resp. $q-1=\prod q_i^{\beta_i}$). The order of any element of $\Bbb Z_{p-1}^*$ divides the Least Common Multiple of the $(p_i-1)\,p_i^{\alpha_i-1}$. Thus when iterating $E$, we always are back (though not necessarily first back) to the starting point after making a number of steps equal to the Least Common Multiple $\ell(N)$ of the $(p_i-1)\,p_i^{\alpha_i-1}$ and $(q_i-1)\,q_i^{\beta_i-1}$. I'm still trying to track the name of this $\ell(N)=\operatorname{lcm}(\lambda(p-1),\lambda(q-1))$ (where $\lambda$ is the Carmichael function used for computing the lowest possible private exponent $d=e^{-1}\bmod\lambda(N)$ in RSA, but here applied to $p-1$ and $q-1$).

Even without a name, it can be computed and graphed.

The $p_i-1$ and $q_i-1$ are composite (or $1$), which increases the potential for common factors. Due to this effect, $\ell(N)$ often ends up with sizably less bits than $N$. For a particular $e$, some further factors of $\ell(N)$ may disappear. This explains the phenomenon.

In our example $p-1=66=2\cdot3\cdot11$, $q-1=198=2\cdot3^2\cdot11$, thus $\lambda(p-1)=2\cdot5$, $\lambda(q-1)=2\cdot3\cdot5$, hence $\ell(N)=2\cdot3\cdot5=30$, and for any $e$ the maximum cycle length must be a divisor of that. It happens that the choice of $e$ further reduces that maximum cycle length to $5$.

Being more rigorous is possible. But a convincing meta-argument that we need not worry for cycles in RSA encryption from a security perspective when $N$ is in the thousands bits, is that if we could, that would be a great way to factor $N$; but experience shows that's not.

More precisely: if we could find one $x$ and compute enough $x_{i+1}=E(x_i)$ starting from $x_0=x$ that we reach¹ $x_k=x$ for $k>1$, then computing $\gcd(N,x-x_i)$ would² have factored $N$ much before: when $i$ reached the point when $E_p$ or $E_q$ first cycled. That's a passable factoring algorithm, but³ it's less efficient than GNFS or ECM, and even Pollard's rho.

Reference: Ronald L. Rivest, Robert D. Silverman, Are ’Strong’ primes needed for RSA?.

¹ Thus deciphering $x$ by taking $x_{k-1}$. That would be a threat to RSA encryption: the so-called cycling attack.

² With overwhelming likelihood, since there's no reason³ $E_p$ and $E_q$ first cycle simultaneously.

³ Under heuristic grounds well verified in experimental factorization.


AES-256-ECB to encrypt VOIP audio-stream? I need to encrypt a live audio-stream that is being sent over the internet. The details are:

The stream contains spoken language (VOIP)
Only the raw stream is transmitted (no meta-data or container)
Latency needs to be low. Therefore, the stream is send via UDP
The Stream needs to be decryptable, even if a package goes missing (because of UDP).
I can't use TLS, because the SOC on the embedded hardware only supports TLS 1.0, which seems insecure.

For ease of implementation and because packages can get lost, I would like to use AES-256 in ECB-mode. I know that ECB can leak information and is prone to pattern detection. But is that still a concern with audio-data?

As an alternative, I could also use CTR-Mode and transmit the counter along with each package (unencrypted). Would that actually gain me anything?

I would be very scared about using ECB with audio (or anything really).  Note for example that attacks have been demonstrated on variable bitrate compressed encrypted audio:

  Despite the rapid adoption of Voice over IP (VoIP), its security implications are not yet fully understood. Since VoIP calls may traverse untrusted networks, packets should be encrypted to ensure confidentiality. However, we show that when the audio is encoded using variable bit rate codecs, the lengths of encrypted VoIP packets can be used to identify the phrases spoken within a call. Our results indicate that a passive observer can identify phrases from a standard speech corpus within encrypted calls with an average accuracy of 50%, and with accuracy greater than 90% for some phrases. Clearly, such an attack calls into question the efficacy of current VoIP encryption standards. In addition, we examine the impact of various features of the underlying audio on our performance and discuss methods for mitigation.

So right off the bat I have to worry that techniques similar to that paper could perhaps be adapted to ECB.  Note for example (section 2):

  Generally speaking, the codec takes as input the audio stream from the user, which is typically sampled at either 8000 or 16000 samples per second (Hz). At some fixed interval, the codec takes the $n$ most recent samples from the input, and compresses them into a packet for efficient transmission across the network.

So even if we used constant length packets, if each one is compressed separately in ECB mode, I would worry that it might interact poorly with the packetization described in this quote—would somebody with a good speech model and knowledge of the codec be able to use ECB ciphertext block frequencies to decode the speech?  Speech has a lot of phonemic, phonotactic and metrical redundancy and apparent limits on its information rate, after all, enough that compressed packet lengths are enough to recover 50-90% of the phonemic segmental stream.

One simple question that could serve as a starting point is this: could a cryptanalyst reliably identify which ECB blocks encode silence, or is the audio's noise floor high enough to defeat this?

In any case, I wouldn't go my own way on this topic—there seems to be a body of research on VoIP encryption, so I'd track that down and read it.


Is it possible to get my x,y coordinates from my "secret exponent"? ...or is that possible?

I am very new to cryptography! But, I think it's very interesting!! I have autism and numbers "are my thing" :)

I already understand a couple of things. For example I know you can get the $x/y$ or $x$ or $y$ from your public hexadecimal address, but can you get anything like that from the secret exponent? Is the secret exponent the non-hexadecimal representation of your private key or is it the secret exponent in hexadecimal? I know it's a random number, but are numbers always converted to hex in this situation? Because I can't imagine graphing a hex number! So, the $(x,y)$ coordinates are on the curve $y^2=x^3+7$, right?

How can you graph that? Like, is there a program that can generate a curve and then I can actually "see" where my $(x,y)$ coordinates are? I just got a free trial of matlab this morning, but I haven't figured out exactly how to replicate that curve on there. Basically, I'm just curious to know what point I am on that curve? How do I figure that out, and how can I draw it? I am a very visual person, so I would like anything that could help to be a gui version. I'm not very good with terminal commands...unless it's very specific.
Like: 1) type this exactly, press enter 2) type this exactly, press enter....etc...

Also, if anyone can recommend a program to help me learn some modular math, how to figure out inverses and multiplicatives of primes, and all that other fun stuff? Thank you! :)

Edit: It is possible I did not phrase this question correctly or put it in the right place. (is that what the -1 means?) Feel free to correct me or move this if need be, but do help please.

I'll answer your question in order of appearance and leave the ones out which are off-topic here.

  For example I know you can get the $x/y$ or $x$ or $y$ from your public
  hexadecimal address, but can you get anything like that from the
  secret exponent?

Not directly. You can use the secret exponent (a.k.a. private key) to calculate the public key (which likely is the same as the "hexadecimal address") and thereby recover these values.

  Is the secret exponent the non-hexadecimal representation of your
  private key or is it the secret exponent in hexadecimal?

The secret exponent is a number. How you represent it depends on the context. For exchange you may represent it Base64 encoded or hexadecimally encoded. For internal use, for the computations by the library, the secret exponents is usually represented using a basis that performs particularly well on the platform you're on, e.g. $2^{64}$ for 64-bit architectures and $2^{32}$ for 32-bit architectures.

  I know it's a random number, but are numbers always converted to hex
  in this situation?

See the previous answer.

  Because I can't imagine graphing a hex number!

I'm not sure what you mean here, but usually nobody ever plots crypto systems used in praxis, because the values and distributions wouldn't show you anything at all (by design) unless it's severely broken.

  So, the $(x,y)$ coordinates are on the curve $y^2=x^3+7$, right?

Yes, indeed. For a pair $(x,y)$ to be considered a point on the curve $E:y^2=x^3+7$, they need to fulfill said equation. Note however that the generic equation for elliptic curves in cryptographic use is $E:y^2\equiv x^3+ax+b\pmod p$.

  How can you graph that?

You can plot elliptic curves over the real numbers and they actually look quite nice, but it's very hard to do so for modular elliptic curves and they don't exhibit any nice visual properties. As for the "how" the plotting is done, in the real case standard methods are used and in the modular case one just tries all $x$ values and the corresponding $y$ values and enlists them in the coordinate space.

  Like, is there a program that can generate a curve and then I can
  actually "see" where my $(x,y)$ coordinates are?

I know for sure that there are programs that can do this nicely for the real case, but I'm not aware of any for the finite field / modular case. You have to ask elesewhere for a better answer on this question.

  Basically, I'm just curious to know what point I am on that curve?

Seeing the point for cryptographic applications is highly useless. You'll just calculate the point using the curve equation and then draw it onto the curve you've already drawn.


Single-algorithm authenticated encryption Are there any authenticated encryption methods that combine encryption and authentication, rather than useing a separate cipher and MAC?

Yes. If you are looking for AEAD ciphers wrapped around a single primitive, there are several in the CEASAR competition for authenticated encryption.

AEAD ciphers based on sponge constructions notably use only a single primitive, the F-function of the sponge permutation. These include NORX, Keyak, PRIMATEs-APE, and ICEPOLE, which are the 4 I find most interesting.

All of these use a central permutation, which generates a stream to encrypt the plaintext, accepts the plaintext to change the stream generation state, and finally generates the authentication tag.

Keyak also offers the ability to generate intermediate tags, so a ciphertext error can be caught before transmission is complete. NORX, ICEPOLE, and Keyak offer a parallel sponge mode to improve performance, and PRIMATEs-APE and ICEPOLE offer a secret message number to make them nonce misuse resistant under certain conditions. I believe Keyak has been modified to offer incremental addition of associated data, which PRIMATEs-APE also offers.

I have not looked at the permutation based ciphers, but they may also be built from a single primitive.

It is possible to build a block cipher mode to create a single primitive AEAD cipher, but it would have a performance deficit against purpose built ciphers. I built one over AES, and it is reasonably fast, almost as fast as OCB per block with longer startup and finalization. Making it purpose built around the AES round function makes it even faster than OCB with hardware acceleration, but as a mode it can be used with any 128-bit block cipher. My motivation was the complexity of generating the OCB offsets in 32-bit code.


Layman's explanation of encryption backdoors In the media, I sometimes read about "backdoors" in encryption algorithms. I'd like to understand what such a backdoor actually consists of. Is it:
a) a hidden weakness in the math formulas that can cause security to be broken by brute force in a reasonable amount of time rather than the universe's expected life span?
or b) a plain hole that makes it possible for a knowing person to extract information without any brute force attack at all; it's a way "straight in"!
I don't know if it's possible to answer this without going into complex math, but I hope the answer can be kept in layman's terms as much as possible.
Creating such a backdoor would involve the challenge of making it almost impossible to find. Moreover, if found, its creator could deny malicious intent and say it was just an honest mistake. Information about how this works and would play out in practice would be interesting as well!

There are two somewhat orthogonal concepts in backdooring encryption algorithms:

The backdoor can be explicit or implicit. An explicit backdoor is one that everybody knows it is there. An implicit backdoor strives at remaining undetected by the algorithm owners. Of course, when there is an explicit backdoor, people tend to avoid the algorithm altogether, so explicit backdoors may hope to work only in the presence of a legal framework that forces implementers to use the backdoored system.

An example of an explicit backdoor is the Clipper chip (which was ultimately abandoned). The backdoor is not really in the algorithm, more in the assembly of algorithms into a protocol, and technically it was an automatic key escrowing method. For an implicit backdoor, see the Dual EC DRBG as a famous example: it worked only as long as nobody was aware that it was backdoored.
The backdoor's security may be quantifiable, or not. In the case of Dual EC DRBG, the mechanism uses well-trodden mathematical paths: the NSA knew that exploiting the backdoor required knowledge of an internal secret key, based on discrete logarithm (on elliptic curves).

A non-quantifiable security is what happens when you try to push, for instance, a voluntarily flawed algorithm, or one for which you know of a cryptanalytic method that you did not publish. This is a very dangerous game for a spy agency, because you cannot really know whether third parties could find the flaw or not. Such backdooring tends to backfire in the long term.

Interestingly, the NSA tends not to use non-quantifiable backdoors. A good example is DES. At the time it was designed, the NSA believed that it could tackle an upfront 256 exhaustive search, and that nobody else (in particular the Soviets) had the technology and budget for that. The NSA also knew of a novel cryptanalytic method (differential cryptanalysis). So when the NSA intervened in the design of DES, it insisted on shortening the key from 64 to 56 bits (that's addition of a quantifiable backdoor, and it was rather obvious, so quasi-explicit), and also on strengthening the design against differential cryptanalysis. This is a good example about how NSA consciously refrained from a non-quantifiable backdoor. There is only one thing that spy agencies fear more than not being able to spy: it is the idea that other competing spy agencies may also spy.

So a real, good backdoor is one that uses maths to offer quantifiable security against unauthorized usage of the backdoor. It is extremely difficult to have quantifiable security without making the backdoor explicit. The "best in class" in that area is Dual EC DRBG, and even before the Snowden business, cryptographers were already finding it weird and strongly suspected foul play (see the analyses back in 2007, 6 years before Snowden).


Does Benford's law hold against encrypted data? If I can assume that the output of a block cipher like AES is a PRandom distribution, can I assume that Benford's law will hold if I partition that output into integer data?

No, Benford's law does not hold.

As a simple example, assume a block size of $8$ bits, so the values are uniformly distributed in the half-open interval $[0, 256)$. Benford's law predicts that the probability of a leading digit occurring is strictly decreasing for increasing digits. However, it's easy to see that values leading with any digit $d \geq 3$ is equally likely.

For $d=3$, the only choices are $x \in [30, 39]$ and $x = 3$, while for $d=4$ the choices are $x \in [40, 49]$ and $x = 4$, and so on for every $d \geq 3$. All of these have exactly $10 + 1 = 11$ choices that occur with equal probability. This contradicts Benford's law's prediction that the probability is strictly decreasing.

We do have a higher chance of $d=1$ and $d=2$, but this is strictly because of the choice of our base. If we chose a base $b$ such that $b^k = 256$ for some integer $k$, then every leading digit is equally likely.


Short length asymmetric encryption? I want to send out short messages to the world which listeners could verify to be send from me.

The way this is usually done is to encrypt the message with a private key where the readers decrypt it with my public key. My problem is that I need small messages, smaller than 64 bytes in base64, plain RSA won't work since the algorithm makes the encrypted message around 128 bytes.

Can someone suggest the name of an algorithm to me that may work?

Note that encrypting "the message with a private key where the readers decrypt it with my public key"

is usually insecure, although there are signatures with message recovery that are presumably secure.

The canonical short signature scheme is BLS.

The main alternative that I'm aware of is the random-oracle part of this paper,

although that scheme cannot safely sign a large number of messages.


Setting protocol parameters to achieve concrete security Background

One issue with modern security proofs is that they are usually asymptotic. In other words, such proofs are usually formulated as follows: For any polynomial-time adversary $\mathcal A$, we can select a large enough security parameter $n$, such that the probability that $\mathcal A$ breaks the system is a negligible function of $n$.

Unfortunately, concrete values for parameters of the protocol cannot be readily deduced from such asymptotic proofs. For instance, the size of RSA modulus for a secure signature scheme may not be obtained from an asymptotic proof of security for the given scheme.

This issue was first formalized by Bellare and Rogaway, in their famous paper "The exact security of digital signatures: How to sign with RSA and Rabin." They provided a new type of analyzing and proving the security of some scheme, which they termed exact security. Soon after, numerous papers considered this notion, and gave various results on the exact security of signature schemes.

Assumptions

This question considers "exact security" for identification protocols. Since we're going to give concrete parameters, we have to make some explicit assumptions:

The time-complexity of entities is limited to $2^{80}$ operations.
Entities can perform up to $2^{30}$ operations per second.
The best algorithm for factoring an integer is GNFS. Given this assumption, factoring a carefully chosen $1024$-bit integer requires about $2^{86}$ operations, which is infeasible according to assumption 1.
In the identification protocol, there is a $30$-second time-out. The adversary can take its time to perform any preprocessing, but when engaged in protocol execution, he must reply within $30$ seconds, or time-out occurs and he fails. (This is in contrast to signature schemes, where the adversary is not faced with such restriction.)
During the lifetime of the system, the adversary may engage in at most $10^8$ identification sessions. He is successful if he can impersonate in at least one session, and he fails otherwise. In other words, a successful adversary is one whose success probability is at least $10^{-8}$.

Protocol and Proof

The honest prover has the factorization of an integer $n$, and the verifier is going to verify this. Let $L = \Theta(1)$ and $m = \Theta(|n|)$.

The identification protocol is the $m$-time repetition of a $\Sigma$ protocol. The challenge of the $\Sigma$ protocol is chosen randomly from the set $\{0,\ldots,L-1\}$.

Now, we are given the following "tight" security proof (the details of how this proof is obtained is unimportant):

For any adversary $\mathcal A$ whose time-complexity is $T$, and who breaks the identification protocol with probability at least $\epsilon$, there exists another adversary $\mathcal B$, whose (expected) time-complexity is $\frac{TLm}{\epsilon} + \Theta(|n|^2)$, and can factor $n$ with probability 1.

Question

  How can we use these assumptions and facts, to suggest concrete values for $|n|$, $L$, and $m$, such that the system is both efficient and secure? (The efficiency condition is included because the choice of extremely large parameters will obviously make the system secure.)

Concrete units.
Nothing can be said in general until you replace $\Theta(|n|^2)$ by a concrete estimate for the actual computational costs, by filling in the constant factors with units like seconds, bits, and joules.  Obviously you should be a little conservative in cost estimates, although if there are multiple different attacks with different costs—e.g., for discrete logs, NFS cost scales with size of modulus while Pollard's $\rho$ cost scales with size of group order—you should try not to be too conservative with any one of them in order to avoid unbalanced costs to defend against unreasonably pessimistic models of attacks that cause you to make foolish compromises.

Cost metric.
You should take care of the actual cost model.  Time is not the only cost, and many attacks are parallelizable.  For example, although a sequential machine might take an expected $2^{n/2}$ operations to find a collision in an $n$-bit hash function using a gigantic table, it also costs $2^{n/2}$ space to store the table—but you can do better with with a $\rho$-type collision search in constant space, and with van Oorschot and Wiener's parallel collision search machine you can use a machine of size $2^{n/4}$ to get an answer in the time for $2^{n/4}$ sequential evaluations of the hash.

Largely the best metric seems to be the area*time cost: the two-dimensional size of the machine multiplied by the amount of time you have to run it, which is usually a good proxy for the cost in rials or joules.  In this metric, the van Oorschot–Wiener collision search still costs $2^{n/2}$.  Other metrics include RAM metric and NAND metric.  One often-ignored part of the cost is communication between large memories and the parallel computational machines.

Precomputation?
There is a foundational issue about quantifying human ignorance in the concrete, nonuniform setting.

We don't know messages $m \ne m'$ such that $\operatorname{SHA256}(m) = \operatorname{SHA256}(m')$, but we know such a message pair exists.  So there obviously exists a random algorithm $A()$ that finds SHA-256 collisions very efficiently—specifically, the trivial algorithm that returns $(m, m')$.  We just haven't found that algorithm yet.
Similarly, there almost certainly exists a string $s$ such that the first bit of $\operatorname{MD5}(s \mathbin\| F(0))$ is zero significantly more often when $F = \operatorname{AES}_k$ for a uniform random key $k$ than when $F$ is a uniform random function, which means there exists a high-advantage, low-cost distinguisher for AES—we just don't know what $s$ is, nor do we have any idea how to find it at reasonable cost.

These foundational issues are discussed by Bernstein and Lange in their nonuniform cracks in the concrete paper, which is worth reading if you're interested in the theory—there are more issues, and potential remedies, and compounded issues introduced by the remedies, than I can hope to address in a single crypto.se answer.

So, how do you decide what parameters to use?  It's easy as 1-2-3!

Solve a gigantic open problem in the foundations of cryptology of quantifying human ignorance and precomputation in the concrete nonuniform setting and rewrite the entire literature to address your solution.
Write down a concrete formula giving a cost estimate for the best attack on the system, based on attack costs on primitives and derived attack costs of reductions.
Choose the parameters optimizing your concrete costs, subject to a lower bound on the budget needed to break the parameters above what you assume the adversary has.

That is to say, find the best parameters for your budget that are beyond the reach of your adversary given an assumption about their budget.

Let's ignore space costs and communication costs and constant factors for the moment, and pretend the precomputation issue didn't exist.  If the adversary can break your protocol in time $T = 30\,\text{sec}$ with probability $\epsilon$, then they can factor $n$ in expected time $\frac{T L m}{\epsilon} + \tau |n|^2$, where $\tau$ is the constant to make the units work out.  What choices of $|n|$ (and $|p|$ and $|q|$) and $L$ optimize your costs, subject to the constraint that $|n|$ be out of reach for the NFS (or ECM, or Pollard's $\rho$, or whatever gives the best concrete factoring costs for $|n|$) to factor with a budget of $\frac{T L m}{\epsilon} + \tau |n|^2$?

For this to work, you need to be armed with:

an estimate of your costs, e.g. from https://bench.cr.yp.to or from your own measurements or from your own analysis
an estimate of NFS and ECM costs per key, which can be complicated

Of course, if you're not generating a fresh $n$ in each instance of the protocol, you also need to constrain the optimization so that $|n|$ is out of reach of the NFS/ECM with a budget of $2^{80}$ operations offline as you posited.

I'd give a concrete example but I'm too dizzy from reading about NFS costs and I need to sit still for a while.

Some caveats to beware of:

One type of attack cost is number of queries to an oracle.  This represents your application's maximum bandwidth; you might hazard a guess about limits on bandwidth of normal usage, but an adversary will saturate all remaining possible bandwidth to maximize the efficacy of an attack.
While you often care about the latency of a single operation, the adversary often cares instead about the bandwidth of many simultaneous attacks.
There are often batch advantages to attacks and opportunities for parallelism; brute force does not just mean trying every key sequentially.
Reduction theorems sometimes give wildly unreasonable bounds.  If there's a concrete attack actually attaining the bound, then this should worry you; if not, you are stuck in a limbo of wondering whether you really need a 100000-bit RSA modulus or you just didn't work hard enough to prove a better bound.


Is Mega.nz encryption vulnerable to brute force cracking by quantum computers? I am interested in Mega.nz cloud storage.
It is using end-to-end encryption.
It says that it uses AES-128 to encrypt files
And there are more details in their white paper
But I saw that quantum computers could be dangerous for AES-128:

Grover's algorithm allows brute-forcing an n-bit key in $\mathcal{O}(2^{n/2})$ time instead of the $\mathcal{O}(2^n)$ time required by classical computers. Therefore, an 128-bit AES key could be brute-forced in $O(2^{64})$ time by a sufficiently powerful quantum computer that can do Grover's algorithm with 128+ qubits for $2^{64}$ time.

So, my question is: could the encrypted files be decrypted by quantum computers?

Grover's algorithm on AES-128
If all of the problems of Grover's algorithm are solved then yes, otherwise no!

Grover's algorithm provides quadratic speed up so AES-128 has 64-bit security in the terms of searching complexity of Grover's method.

Grover's attack for AES-128 requires approximately $2^{64}$ successive AES evaluations. That is one has to set up the machine $2^{64}$ times, run successfully, and extract the result. This is not like a for loop on the classical machines.

The attack time is still quadratic and the required gates are not practical and it can be around $2^{86}$ for AES-128.

Graver algorithm can run in parallel, however, running $k$ machines will provide $\sqrt{k}$ speed up, and the above problem will still exist in each copy.

They are a company, if you are going to be their customer ask them to include the easiest mitigation AES-256 if you fear the future. The performance difference between AES-128 and AES-256 is just 40%, that is AES-256 is 40% slower. This is not a big deal in security. It is strange that they don't offer that since the industry sees the AES-256 as the gold standard.

A more realistic attack on AES-128
In MEGA file encryption, each node (file or folder) has its own encryption key. Although AES-128 is secure, with AES-128 the more users the MEGA has and the more file uploaded by the users will create an realistic attack on AES-128, the multi-target attack with parallel versions of Oechslin's rainbow tables.
Finding a key from $t$ targets's expected cost is $2^{128}/t$. Now assume that you have a billion targets. Then, you will be able to find the first encryption key much lower than 128-bit security. The cost would be below $2^{100}$ and the time would be below $2^{70}$. This can be achievable with supercomputers.
Therefore the MEGA must give the option to use AES-256 for their clients. In the end, the encryption is performed on the client-side, that is no cost for the MEGA servers at all.

A Review of Mega from their White Paper
Mega is simply

MEGA is a secure cloud storage and communication platform with user-controlled end-to-end encryption (E2EE). End-to-end encryption means that no intermediary - not even MEGA - has access to the user’s encryption keys and therefore the stored data. However, users have the option to share data (individual files or entire folders), plus the associated encryption keys, with others.

It enables browser-based access to end-to-end-encrypted
cloud storage.
End-to-end encryption
The files are encrypted on the client-side before uploading. If the user wants to share a file, then they share the encryption key of the file with the recipient’s public key. The recipient key can be verified in another channel as the Signal does, and any change will be notified.
Source code transparency
All security-related code work on the user side and Mega releases the source code so that third parties can verify the source code. This is a very important aspect
Privacy
They promise to only keep the user's e-mail and IP address for operational purposes. They promise to not keeping processing activities and the data, though they can see the activity. The files are still encrypted and not accessible to Mega.
Vulnerability management
They want to ensure security on an ongoing basis and they offer a prize for a previously unknown security-relevant bug or design flaw. This is an important aspect since it will attract more people to look at their designs and codes.
They also provide Data Redundancy and compliance with regulatory
requirements. The compliance is an interesting part since, at least now, Australia banned end-to-end encryption. Although the MEGA's service is governed by New Zealand law, it is unclear to me in the case of LAW change.


pbkdf2 password validation My question is related to PBKDF2. I am unsure how to validate user entered password with already existing hashes and salts.

I have heard of the so called "length-constant" comparison which basically ensures that every byte is being compared rather than a simple string comparison. And this is part where I am confused about. When deriving a key using for example "Hello" as password and "Hello2" as salt the output of PBKDF2 will always be the same. So why is there a slow equals (length-constant) comparison method?

What is the correct way of validating passwords in PBKDF2?

If the resulting hashes were the same, a non length-constant check would compare every byte of the resultant digest. This would take the most time to compare.

Lets say it takes 90.00ms to run the KDF, and 0.90ms to do a full length compare (not real numbers but good enough for the example)

If the password was "hello" instead of "Hello", it is probable that the digest will have a different first or 2nd byte, which means a comparison would determine they are different much faster than if they were the same. Instead of 90.90ms, it may take 90.10ms.

If the attacker is capable of measuring the cpu usage or cpu power draw, they may be able to measure the quantity of keystrokes, giving the attacker the length of the correct password. They may also be able to compare the time it takes between key presses to better determine what combination of key presses was entered. The attacker may be able to get much more information that that, maybe less, but every bit of information the attacker gets will help them attack the KDF and recover the password. Knowing that a specific combination is correct is a huge amount of information.

This is why constant time comparisons are so important, because it is extremely easy to put in bogus passwords and get a timeframe of how long it takes to compare incorrect results, so when the correct result is compared it will take longer, and be detected by whatever mechanism (software or hardware) is measuring them.


Why does curve25519 use a cofactor of 8? This cofactor (as I understand it) effectively discards valid points that satisfy the curve equation over the finite field.

Why would one wish to reduce the number of possible private keys, it seems to reduce security.

What is the reasoning behind using a cofactor of 8?

Curve25519 was chosen to have the Montgomery shape $y^2 = x^3 + A x^2 + x$ to support the fast single-coordinate Montgomery ladder for Diffie–Hellman: given $x(P)$ and $a$, it is cheap to compute $x([a]P)$, so there is no need to pass the $y$ coordinate and implementors are not tempted to use secret-dependent conditionals to compute scalar multiplication with the naive double-and-add algorithm—that is, the shape of Curve25519 was chosen to encourage implementors of the X25519 DH function to avoid timing side channels without sacrificing performance.

Every Montgomery curve has a point of order 2 (if the equation holds for $P = (x, y)$ then it holds for $(x, -y) = -P$ so $P + (-P) = \mathcal O$), so the cofactor is always greater than 1—and when the coordinate field is $\mathbb Z/p\mathbb Z$ for $p \equiv 1 \pmod 4$ as is the case for $2^{255} - 19$, the orders of the curve and its twist are 4 and 8 or vice versa.

Curve25519 was chosen to minimize the cofactors, and when taking all the other criteria into account, the best choice had cofactor 8 for the curve and cofactor 4 for the twist.  RFC 7748 gives a deterministic algorithm to search according to these criteria in Appendix A.  For comparison, the Curve448 coordinate field is modulo $p = 2^{448} - 2^{224} - 1$ with $p \equiv 3 \pmod 4$, so both the curve and its twist have cofactor 4.


Given infinite unencrypted and encrypted texts, can I find the algorithm? Given an infinite amount of both unencrypted and the corresponding encrypted text, would I be able to calculate the algorithm? I am relative new to cryptography and don't know if I would be able to find how the unencrypted text is encrypted... Is this possible? If so, what should I study?

summmary

In general, no.
An attacker who has lots of ciphertext+plaintext pairs may never be able to reverse-engineer an algorithm from them.
An attack may not even be able to distinguish which one of a large group of known encryption algorithms was used to generate those ciphertexts.

However, various weaknesses in some algorithms and protocols are known.
If such an algorithm was used, the attacker may find it relatively easy to rule out all but a few or perhaps only 1 of the known encryption algorithms.

details

Some people who build modern ciphers try to make their ciphers "indistinguishable from random".
Several modern ciphers (especially ones intended for use in steganography) are not currently known to be susceptible to such a distinguishing attack.

No matter how many ciphertext+plaintext pairs the attacker collects that were properly encrypted using a single one of those algorithms using a single long-term key,
there is no known practical way for that attacker to distinguish a new message encrypted using the same algorithm using the same long-term key from a freshly generated series of bits from a hardware random-number generator.
This implies that there is no known practical way for that attacker to discover which one of those algorithms was actually used.

Cryptanalysts have discovered distinguishing attacks for many vulnerable ciphers.
If an attacker collects enough ciphertext-plaintext pairs encrypted by such a vulnerable cipher, that attacker can rule out most other ciphers, narrowing down the possible algorithm to a few or perhaps only 1 known vulnerable encryption algorithm.

When an attacker has samples of both the plaintext (called a crib), and its encrypted version (ciphertext), the attacker can mount a known-plaintext attack.

The people who build modern ciphers try hard to make their ciphers immune to known-plaintext attacks.
Most modern ciphers are not currently known to be susceptible to known-plaintext attacks.

However, many historic ciphers (most famously, the Enigma cipher) can be partially or completely broken by a known-plaintext attack.

Many distinguishing attacks and known-plaintext attacks depend on the person doing the encryption using the same key for large numbers of messages.
Sometimes that number is so extremely large that these attacks are impractical.
Other times that number is large but not improactical, and cryptographers recommend periodically rekeying long before such attacks are practical (RFC4253, RFC4344, etc.).

In practice, many communication protocols transmit the specific encryption protocol used, transmitted in plaintext in the header before any ciphertext, at the beginning of every message.
An attacker only needs to look at that header to know which encryption algorithm was used.

If someone encrypts enough messages with the same key using a block cipher in electronic codebook mode,
and an attacker gets enough ciphertext-plaintext pairs,
then even without knowing which particular block cipher is used,
the attacker can decrypt any block in any new encrypted message whenever a block of plaintext in the new message happens to match a block of known plaintext.

In theory, if an attacker has an "infinite amount" of computing power,
that attacker try every possible encryption key in every known encryption algorithm and see if it "works".
Such a brute-force attack can in theory recover the key for almost all known encryption algorithms.
(The one-time pad and closely related ciphers are completely immune to a brute-force attack).
Fortunately for people who are not attackers, the amount of work required for such a brute-force attack usually makes them impractical.


Does the security of RSA come from just the carries in multiplication? Although it's hard for me to find a reference, it's my understanding that if you calculate $N = pq$ using $GF(2)$ polynomial multiplication rather than ordinary multiplication, it is easy to factor $N$ under this type of multiplication.
I might have the terminology wrong when I say "$GF(2)$ polynomial multiplication".  I mean carryless or "XOR" multiplication done in base 2.
Is this true, and if so, does it mean that the security of RSA comes entirely from the addition carries that happen during ordinary multiplication?

might have the terminology wrong when I say "GF(2) polynomial multiplication"

You are thinking of multiplication in the ring of binary polynomials, that is polynomials with coefficients in the Galois Field with 2 elements. That set is noted $GF(2)[x]$. It's addition reduces to XOR of the coefficients of equal weight. It's multiplication is called "carryless multiplication" in computing. It supports an analog to Euclidean division, and modular arithmetic.

It's my understanding that if you calculate $N=pq$ using (this) multiplication rather than ordinary multiplication, it is easy to factor $N$.

Yes. There are efficient algorithms for factoring binary polynomials into irreducible polynomials (which are analogs to primes in the ring of binary polynomials).

Does it mean that the security of RSA comes entirely from the addition carries that happen during ordinary multiplication?

True, RSA is not secure if we remove the carries (in the additions within it's multiplication by the schoolbook algorithm). I can't agree with "security .. comes entirely". Analogy: a chain is insecure if one removes it's last link, yet it's security does not come entirely from that link.


Are MAC algorithms and digital signatures secure from quantum computers? If not, why? I understand that asymmetric encryption is fundamentally deemed useless under Shor's Algorithm, and understand that symmetric encryption is somewhat quantum-resistant as long as the key-length is equal or above 192-bits.
MACs are symmetric cryptographic primitives, however, I have heard that they may be insecure due to the key exchange.

MACs don't involve any key exchange. The ability to share the key is assumed, just like with symmetric encryption. I'd tend to recommend a 256 bit key over a 192 bit key, because the effective key length is halved. 96 bits effective security might be breakable eventually, 128 bits effective security basically never will without discovery of flaws in the algorithm or implementation.

I understand that asymmetric encryption is fundamentally deemed useless under Shor's Algorithm,

This is incorrect. RSA and the usual ECC constructions (ECDSA, EdDSA, ECDH) are breakable for all practical key sizes. Other asymmetric constructions not based on integer factorization (RSA) or the discrete log problem(s) (ECC, ElGamal, traditional Diffie-Hellman) can be secure. EG Lattice-based cryptography (including but not limited to learning with errors, ring learning-with-errors, module learning-with-errors, and module learning-with-rounding), code-based cryptography, supersingular isogeny Diffie-Hellman are all asymmetric encryption thought to be resistant to attack by quantum computers. NIST is running a public contest to standardize some of these quantum-resistant asymmetric algorithms. It's currently in its third round.


How can I securely encrypt the same message multiple times? I want to encrypt the same message multiple times. I want to store the encrypted messages together. I've heard if you do this with RSA, an attacker could decrypt the message with the Chinese Remainder Theorem.

What encryption methods do not suffer from this vulnerability? Would RSA with some random bits added to the message suffice?

No, "RSA with some random bits added" does not suffice. There have been attacks against many of bad padding techniques for RSA. Instead a known secure mode of operation is required. The most well known secure mode is RSA-OAEP.

The earlier RSA with PKCS#1 v1.5 padding may also be secure, but it has a well known attack against it called the Bleichenbacher attack. More to the point, there is also a million messages attack which shows one example what kind of attacks is possible if you just "add some random bits" to a message.

Note that the security argument of RSA-OAEP was under serious scrutiny. This has weakened but not broken the security proof for RSA-OAEP, which had to be adapted to the new situation. Furthermore, implementation mistakes may allow attacks against RSA-OAEP.

This is why there are some proponents here for RSA-KEM. Here RSA simply encrypts a random number in the range $[0, N)$, which is then fed into a key derivation function or KDF, which in turn creates a secret key which can be used for symmetric encryption. This is a rather elegant scheme which is provable secure, just like OAEP.

Note that the security proof for RSA-OAEP and RSA-KEM assumes that the RSA trapdoor itself is secure. However, that's something that cannot be proven - we just assume it is secure because it withstood all attempts so far.


What cipher(s) can or should I use for attribute based encryption? What cipher(s) can or should I use for attribute based encryption? Can I use AES for that, or should I use some other, specific cipher(s)?

I am assuming that you are asking which encryption scheme is used to encrypt the actual data (file, stream data etc.) while using ABE. To encrypt the data, you can use any block cipher such as AES. Then, use ABE to encrypt block cipher key (AES key).


How to derive formulas for addition and multiplication in Jacobian coordinates Is there a way to derive the formulas for point addition and multiplication on elliptic curves in Jacobian format by yourself?  How could I have derived these formulas by myself?

I haven't worked through all the (boring) details but it should be fairly easy. Just start with the normal affine addition and doubling formulae but when it comes to the stage where you do any division, don't bother and just keep track of the numerator/denominator separately. The whole point of Jacobian and other projective representations is that you don't do any division until you HAVE to. The disadvantage is that one point has many different projective representations.

The $Z^2$ or $Z^3$ aspect is just shuffling multiplications around to make doubling slightly faster versus addition or vice-versa or to do with being able to add an affine point to a projective point more quickly. It tends not to matter too much. If you want faster calculations you should be choosing perhaps an Edwards curve representation and/or maths over an appropriately fast extension field.


Can I use the Sequence Number as the (implicit) IV in AES-GCM IPsec? The RFC https://tools.ietf.org/html/rfc4106#page-5 states that, under AES-GCM IPsec, each packet is expanded by 8 bytes for the IV and up to 16 bytes for the ICV.  Why? Since we already have a Sequence Number (4 or, in the case of ESN, 8 bytes), can't we just use that as an implicit IV? This saves 8 bytes per packet (which is sometimes negligible, but sometimes not), and doesn't seem to harm security at all - either way, we need to ensure that sequence numbers are unique.  If anything, it's easier to ensure that one field (ESN) is unique, more than two?

If I am correct, and you can just the ESN has the implicit IV, is doing so compliant with the standards?

Note: I recognize this assumes only one encryptor per SA.  For cases of multiple encryptors using the same key, each encryptor would need to prepend their unique id to it.

If I am correct, and you can just the ESN has the implicit IV, is doing so compliant with the standards?

No, it would not be compliant with the RFC. The RFC clearly states that there must be 8 bytes of IV payload immediately in front of the ciphertext (see section 3). Omitting those 8 bytes would not allow interoperability with standard implementations of ESP-GCM (and a large part of the reason the IETF does RFC's is to allow different implementations to interoperate).

Yes can, of course, copy the ESP sequence number into the 8 byte IV; that meets the requirement for uniqueness; however that obviously doesn't do the bandwidth saving you're looking for.

Alternatively, if you feel strongly enough about it, you could design a vendor-specific encryption method that does GCM (and derives the sequence number in the ESP header as payload); IKE does provide ways to do that.  However, you can't claim compliance to RFC4106...


argon2i hashes with GPU using JTR or any other tool please help! I have been working on an assignment to solve argon2i hashes but unfortunately. I am not able to use GPU with JTR i.e. no opencl mode for argon2. Thus the speed is very slow. Any suggestion how to proceed using GPU based attack?

I am not able to use GPU with JTR i.e. no opencl mode for argon2. Thus the speed is very slow. Any suggestion how to proceed using GPU based attack?

This is exactly one of the reasons that argon2 exists.

It was explicitly designed so that hardware other than a general purpose CPU provides only a minimal advantage, if any.

Proceeding with GPU based attacks is probably a waste of a GPU. One of the core features of argon2 is a large amount of memory usage, which GPUs are not exceptionally good at.

Options

Your best bet is to have a large number of normal computers with sufficient RAM, or investigate FPGAs. FPGAs may not be able to provide a worthwhile advantage due to the memory requirement, and they will not be so easy to work with (unless you are already skilled with an HDL).

Neither option will be cheap, and I assume that they are not practical in your situation.

Most likely, you are stuck testing one password guess at a time using your CPU. In such a case, the best that you can do is to use a good word list and hope that the password is weak. Either that, or find some alternative method of finding the password that doesn't involve cracking argon2 hashes.


Comparing different hashes to confirm they came from the same string Is there any safe hashing algorithm that returns a different hash each time (like bcrypt) but has the possibility to compare 2 different hashes and determine that they were hashed from the same password/string without knowing this password/string?

Here's a thought; we work in a pairing-friendly elliptic curve where the discrete log problem is hard, and we generate a 'hash' of a value $p$ [1] by selecting a random value $r$, and outputting the two points $(rG, rpG)$.

Then, given two such hashes $(rG, rpG)$ and $(r'G, r'p'G)$, we can check if they are hashes of the same password by computing the two pairing operations $e(rG, r'p'G)$ and $e(r'G, rpG)$.  If $p = p'$, then both values will be the same, namely the value $e(G, G)^{rr'p}$.

Reversing the hash, that is, given $(rG, rpG)$, recover $p$, is a discrete log problem, this is assumed to be hard.

And, given a long list of hash passwords $(rG, rpG), (r'G, r'p'G), (r''G, r''p''G), ...$, there doesn't appear to be any obvious way to compare all of then against an attacker chosen password with less than $O(n)$ pairing operations or point multiplications.

The attacker can test a single hash $(rG, rpG)$ against a test password $p'$ by checking if $p'(rG) = rpG$; however with any such primitive where there is a primitive to compare hashes, the attacker could perform this test by hashing the password $p'$ and using the comparison primitive to see if that hash matches the one under test, and so this is not a vulnerability.

[1] The value $p$ might be a conventional hash of the actual password; that detail isn't important for this idea.


Goofs that could creep in ECDSA signature verification? What are goofs that could creep in ECDSA signature verification, perhaps with focus on curves based on prime-order $\mathbb Z_p$, specifically P-256 aka secp256r1? Is it possible to construct test cases for these, and how (perhaps with distinction between various degrees of blackboxness)? How relevant is that in practice (risk of accepting an invalid/forged signature, or rejecting a valid one)?

I'm disregarding as off-topic the ASN.1 formatting checks, and the hashing; and consider that nothing is secret, hence side-channel leakage is a non-issue (the question would be much harder for ECDSA signature generation).

That leaves at least exceptional cases in modular reductions (be it modulo $p$ or modulo the curve's group order $n$); the possibility to hit the point at infinity/neutral element; validating inputs are on the curve, and other input checks.

Checks for $r$ and $s$

You should perform checking on $r$ and $s$ inside your signature verificatioin function. To be more specific you should check that $r$ and $s$ are integers in the interval $[1, n-1]$ as there are known attacks on related ElGamal signature schemes that do not have this check included. This could be a plausible attack on ECDSA if you do not check that $r \neq 0$ (or more generally, $r\not\equiv0 \pmod n$):

Suppose that $A$ is using an elliptic curve $y^2=x^3+ax+b$ over a field $\mathbb{F}_p$, where $b$ is a quadratic residue modulo $p$, and suppose that $A$ is using a base point $G = (0, \sqrt{b})$ of prime order $n$. This might be plausible as some entities might want to select a base point with $0$ $x$-coordinate in order to minimize the size of domain parameters. The adversary can now forge $A$'s signature on any message $m$ of its choice by computing $e=\mathrm{hash}(m)$. You can easily check that $(r=0, s=e)$ is a valid signature for any $m$.

Reduction mod $n$ after reduction mod $p$

During ECDSA signature verification you will have to compute $R=u_1G + u_2Q$. Your elliptic curve operations might be implemented in a way that the multiplication and / or addition will automatically perform a reduction$\mod p$ (order of the prime field). Note however, that you have to reduce the $x$-coordinate again, this time$\mod n$ (order of the generator). For me (and for the testvectors I had used), verification always worked without the reduction$\mod n$, which in my opinion, is the dangerous thing here. There might be curves / testvectors for which verification would fail without this last reduction step. I will implement some more curves (atm I had only used brainpool curves) and will post an update about this.


How would we design a fast circuit to solve LCS35? LCS35 is a time-lock puzzle, stated in Ronald L. Rivest's Description of the LCS35 Time Capsule Crypto-Puzzle [1] (April 1999). That instantiates a system in Ronald L. Rivest, Adi Shamir and David A. Wagner's Time-Lock puzzles and timed-release Crypto [2] (MIT technical report, 1996, revised March 1999).

Solving the puzzle boils down to computing $2^{(2^t)}\bmod n$ for $n$ a public 2046-bit RSA modulus of secret factorization, and $t\approx1.13\cdot2^{46}$. The reference method sequentially computes $w_i=2^{(2^i)}\bmod n$ for $i$ up to $t$, by iterating $w_{i+1}\gets w_i^2\bmod n$, starting from $w_0=2$, or perhaps $w_{10}=2^{1024}$.

How would we design a fast circuit for that purpose? And what speed (in equivalent modular squaring per second) could it achieve? I'm interested in

Mathematical techniques: e.g. would Montgomery arithmetic help?
Architectural tradeoffs: e.g. between circuit depth and size, both causing a slowdown.
Technology: I do not even know what technology is currently the state of the art when it comes to fast logic, much less what it could realistically achieve.

The design of LCS35 attempts to block attempts at massive parallelization, and mostly succeeds as far as we know. The question is about making the computation nevertheless.

The value of $t$ was chosen assuming 3000 squaremods/second in 1999, exponential grows to ×13 that per 2012, then again ×5 per 2034 (the challenge ends in 2033).

I propose to ignore:

Operating cost: it would be negligible compared to bitcoin mining, unless we find a way to parallelize, which would be a major breakthru.
Investment cost: it depends on too many factors, and evaluations are not falsifiable.
Computation errors, since we know how to deal with them:

Reference [1] suggests making the computation of $w'_i=2^{(2^i)}\bmod(c\,n)$ where $c$ is a moderate prime (50-bit). This allows a periodical check that $w'_i\bmod c\ =\ 2^{(2^i)\bmod (c'-1)}\bmod c$, backtracking if an error creeps, and getting $w_t\gets w'_t\bmod n$ in the end.
A variant is to compute both $w'_i=2^{(2^t)}\bmod(3n)$ and $w''_i=2^{(2^t)}\bmod(5n)$ on two independent engines (conveniently, both moduli are 2048-bit), and periodically check that $w'_i\bmod n=w''_i\bmod n$. That requires two independent implementations but little increase in the modulus size, hence (I guess) faster computation and smaller computing engines.

Attacks that essentially factor $n$, including using a Quantum Computer.
Alternatives to LCS35 for timed-release crypto, as asked in this other question.

Turns out the LCS35 problem was first solved on April 15, 2019 by Bernard Fabrot. It took 3.5 years of runtime on a single core of a standard modern CPU, using GMP.

Independently, the Cryptophage project solved LCS35 in less than 2 months, starting mid March 2019, using an FPGA-based system that performs modular squaring with extremely low latency.


RSA Cryptosytsem, choosing $e$ I am using the RSA crytposytem. I have $p$, $q$ and hence $n$ and $\phi$ however I don't understand how to get $e$ such that $gcd(e,\phi)=1$

Many thanks

You need to choose e such that it is co-prime relative to PHY(n). Since you do not want to get involved in factorization of PHY(n), the best way is to choose e randomly, and better let it be a non even prime. Common values are 2^16+1, 3, etc. Most of the primes you choose will have GCD(e,PHY(n))=1.


What is the Geometric Generalised T' Method? This page by Nicolas T. Courtois  mentions Geometric Generalised T' Method. It is described as

  an advanced geometric algorithm, never published, for finding extra linearly independent equations at a given degree, which would normally be found by Gröbner bases techniques, but at a higher degree(!) with much higher memory and with much higher complexity. So in practice, this algorithm has no competitors in producing such equations on current computers.

The other page of the same site mentions T' method (not geometric and not generalized) as one of the steps of the AES attack and it even says that it is described in several papers (but sadly without any link):

  In general, it is likely that in the future, the best attack on AES will be of the following form:
  1. Use the equations over GF(256).
  2. Apply one of the versions of XSL.
  3. Apply a final step. The so called T' method, described in several papers, may or may not be sufficient.

So, my questions are: What is the T' method? Where it is described? What could be its geometric generalization?

Will be grateful for any reference or clue.

T' method was introduced in the paper Cryptanalysis of Block Ciphers with Overdefined Systems of Equations by Nicolas Courtois and Josef Pieprzyk (see section 6.1 and Appendix E).

It is a part of XSL attack on block ciphers (such as Rijndael and Serpent).

During XSL attack cipher is represented as a system of multivariate quadratic polynomials and the goal of T' method is to derive more linearly independent equations form it.

Don Coppersmith criticized this attack but noted that

  The method has some merit, and is worth investigating, but it does not
  break Rijndael as it stands.


Hash collision using the leading 40-bits of SHA-1 I am trying to implement Floyd's cycle finding algorithm for finding a leading 40-bit hash collision in the SHA-1 algorithm. However, my code will not find a repetition even with 800,000,000 hashes. Can I get some help on this issue?

Here is my code for reference.

REMOVED

Note: I want to understand Floyd's cycle finding algorithm, can someone explain the theory and implementation?

EDIT: Finished Solution
Thanks everyone for the help, It now finds collisions in ~3,000,000 hashes!

#include "sha.h"
#include "cryptlib.h"
#include <cstdlib>
#include <iostream>
#include <string>
#include <iterator>
#include <algorithm>
#include <random>
#include <bitset>
#include <time.h>

#pragma comment(lib, "cryptlib.lib")

using namespace std;

CryptoPP::SHA1 SHA;

// takes the reference to a char array and fills it
// with random hex values
void randStr(byte(&src)[5]){
    const char *hex_digits = "0123456789abcdef";
    srand(time(NULL));
    for (int i = 0; i < 5; i++) {
        src[i] = hex_digits[(rand() % 16)];
    }
}

void hash_40(byte (&src)[5], byte (&hash)[5]){
    // Temp hash Storage
    byte k[CryptoPP::SHA1::DIGESTSIZE];
    // SHA Calculation
    SHA.CalculateDigest(k, src, 5);
    // Copy to hash destination
    for (int i = 0; i < 5; i++){
        hash[i] = k[i];
    }
}

// compares 2 strings to length len
// faster than C: strncmp with compiler
// optimizations and works as unsigned
bool cmp_hash(byte(&a)[5], byte(&b)[5], int len){
    for (int i = 0; i < len; ++i){
        if (a[i] != b[i]){
            return false;
        }
    }
    return true;
}

int main(){
    byte
        t[5],
        h[5],
        xT[5],
        xH[5];
    randStr(t);
    copy(begin(t), end(t), begin(h));
    hash_40(t, t);
    hash_40(h, h);
    hash_40(h, h);
    copy(begin(t), end(t), begin(xT));
    copy(begin(h), end(h), begin(xH));
    unsigned long ctr = 0;
    while (true){
        hash_40(t, t);
        hash_40(h, h);
        hash_40(h, h);
        ctr += 3;
        if (cmp_hash(t, h, 5)){
            break;
        }
        if (ctr % 10000 == 0){
            cout << ctr << "\r\n";
        }
        copy(begin(t), end(t), begin(xT));
        copy(begin(h), end(h), begin(xH));
    }

    cout << "\r\n" << xH << "\r\n" << xT << "\r\nHash to the same leading 40 bits\r\n";
    system("pause");
    return 0;
}

Ok, here's how it is supposed to work: we take the function (which maps a string of $n$ bits to a string of $n$ bits), and iterate it repeatedly.  After some amount of time, we'll run into a loop (that is, we'll evaluate to a value that we visited before, and there after, we'll repeatedly run through the loop).  And, we'll run the function iteration twice, with one of iterations running twice as fast as the other; what will happen eventually is that they'll both fall into the loop, and that the fast one will catch up with the slow one, and give us the collision (using somewhat more computation than other methods would, but using hardly any memory at all).

This is all well and good; the question is: how much computation do we expect.  Well, if the function acts like a random function (and SHA1 is believed to), we'll expect to hit a collision somewhere around $c2^{n/2}$ (for a value of $c$ not drastically larger than 1).

Ok, and so what's the value of $n$?  Well, you're feeding 160 bits into SHA, and using all 160 bits of SHA output in the next iteration, and so $n=160$ (and so this logic is unlikely to fall into a loop drastically earlier than $2^{80}$ iterations).

Now, during your comparison, you're comparing only 40 bits; however because it is unlikely you've fallen into a loop, you are effectively comparing random values; you might run into a collision, but with only probability $2^{-40}$ per comparison.  Hence, it's not at all surprising that you haven't found anything yet.

And, given all this, what is the correct fix?  Well, the obvious thing to do is to actually use $n=40$; that is, when you do your SHA1 computation, feed in only 40 bits (and not all 160).  That should fix your problem.


Relationship between AES GCM and AES CTR I have read that AES GCM uses AES CTR for encryption and GMAC for authentication.

If that is correct, what is the relationship between the IV used for AES GCM and the IV used for AES CTR?

TO put the question another way, can I encrypt using GCM and then decrypt using AES CTR (ignoring authentication) and if so, what's the relationship between the IV that I pass to GCM when encrypting and the IV that I pass to AES CTR when decrypting?

That's correct.

In most cases you can do what you are proposing. However be warned that by disregarding the authentication you clearly loose message authentication and bit flipping in AES-CTR encrypted stream is trivial.

You can do what you are proposing if the AES-GCM IV size is of 96 bits. AES-GCM supports also longer sizes for IVs and for those cases you would need GHASH to find the correct IV used by CTR. That having being said I believe 99% of implementation supports only 96 bit IV for AES-GCM (and rightfully so).

To obtain the CTR IV, just append the value 2 encoded as 32-bit big endian integer to the 96 bit GCM IV (equivalently adds in C notation "0x00,0x00,0x00,0x01").

Edited to change from 1 to 2 of the initial counter value. GCM acutally defines the starting counter as starting with 1, but increments it before the first encryption, thus resulting in a 2. Thanks to @TrickyDixon for pointing this out.


How complex must round constants be to resist slide attacks? A key schedule that generates round keys by XORing a round constant with the key is linear and can be vulnerable to related key attacks, but let's ignore that for now. Constants are necessary to avoid the slide attack. How complex do these constants need to be and how much must they differ?
For example, would a trivial key schedule composed of $r_i = k \oplus c_i$ to generate the $i^\text{th}$ round key $r_i$ using round constant $c_i$ and secret key $k$ be weak to any form of cryptanalysis if $c_i = i$?

It depends on the actual block cipher and is quite an open problem. For example, SCREAM, iSCREAM and Midori64 use such key schedule (i.e., its absense) with sparse round constants. They were broken with a practical attack on quite large weak key space [1]. Though, the linear layer has some special property.

I would add that its not the slide attack that matters, but symmetries/invariants and these things are not yet well understood.

[1] https://eprint.iacr.org/2016/732


Cryptanalysis of Marvin32 compared to SipHash So I am curious about the security analysis of Marvin32, the randomized hash algorithm used in .NET (to prevent hash-table DoS). I found the source code here: marvin32.h, marvin32.c.

At first glance, the construction looks really similar to that of SipHash, but:

Marvin32: 1 round per block and 2 finalization rounds
SipHash: 2 rounds per block and 4 finalization rounds
Marvin32: 64-bit key space (seed)
SipHash: 128-bit key space

Nevertheless, the construction seems so similar that it looks like MS was trying to build something like a PRF. The 64-bit key space is certainly too small for a general-purpose PRF, but assuming that 64-bit is enough, is this a secure PRF? Do you see anything else wrong with the construction (key expansion, hash)?

To me it looks like the rounds are too short for this to be a crypto-grade PRF (again, ignoring the key-space for a moment), but maybe it's enough to thwart the hash-table DoS assuming the key is changed from time to time using a CSPRNG?

It isn't a good cryptographical PRF (and, to be fair to the inventor, he never claimed it was).

Marvin32 starts with a secret state, and processing the message and the state to give a new state, and at the end, outputs the state.  However, it outputs the entire state, and the state update process is invertible (if you know the message); hence if you know the message and the output, you can reconstruct the original state (and with that, compute the output for any other arbitrary message).

Even if we ignore the state recovery attack, there are also issues with propagating deltas from the final message bits into the output; if we take a message and flip a bit in the final byte, it wouldn't appear that that change gets propagated to all the bits of the output with probability anywhere close to 0.5 (this effect is stronger if the message length isn't a multiple of 4); this raises questions whether it's a good statistical PRF.


Key Scheduling of International Data Encryption Algorithm (IDEA) How to perform the key scheduling in International Data Encryption Algorithm (IDEA),
I took a research but I can't understand how to perform it,

"further groups of eight keys are created by rotating the main key left 25 bits between each group of eight.", this is the part where I cannot understand the key scheduling of IDEA

Have a look at the corresponding paper.

The key is a 128-bit string $K$. The round keys for round $r=1,...,8$ are derived as follows:

take the version of $K$ cyclically rotated to the left $25\cdot r$ times;
split the string obtained into eight substrings and call them $Z_1^{(r)}$, ..., $Z_8^{(r)}$.

The keys $Z_7^{(r)}$ and $Z_8^{(r)}$ are never used. The subkeys $Z_1^{(9)}$, ..., $Z_4^{(9)}$ are used to mask the output.


Birthday Attack Probability of Collision in Introduction to Modern Cryptography I have some questions about the chapter of Birthday Attack in Introduction to Modern Cryptography.

  When $q=\Theta(2^{l/2})$ the probability of this collision is roughly $1/2$

What's the meaning of $\Theta(.)$ and $\Theta(2^{l/2})$, and why the probability of this collision is roughly 1/2 when the $q=\Theta(2^{l/2})$

Thanks in advance.

We say $f(n)=\theta(g(n))$ if
$$
cg(n)\leq f(n)\leq Cf(n),\quad 0<c\leq C<\infty
$$
as $n\rightarrow \infty.$

Apply the $\ell-$bit hash function to $k$ randomly chosen inputs. Let $n=2^{\ell}.$

The chance of two values picked being unique is $n- 1 \over n$ because when picking the second value you only have $n-1$ unique values left in the range. Repeating this argument,
the chance of picking $t$ unique values is:

$${n - 1 \over n} \times {n- 2 \over n} \times \cdots \times {n- (k- 1) \over n}.$$

This is exactly the same as the limit for the birthday paradox.

Now $1-x \leq e^{-x}$ and hence
$1-(v/n) \leq e^{-v/n}$ for $1\leq v\leq n,$ and thus the probability of no collisions is at most
$$e^{-{1 \over n}} \times e^{-{2 \over n}} \times \cdots \times e^{-{k - 1 \over n}} =\exp\left\{-{1 + 2 + \cdots + (k-1) \over n}\right\}$$
which equals
$$e^{-{k(k-1)/2 \over t}} = e^{-{k(k-1) \over 2n}} $$

The chance of a collision is 1 minus this quantity. Plugging in $k=\sqrt{n}=\sqrt{2^{\ell}}$ yields a value not too far from $1/2.$


Encrypted messaging web app design I’m implementing an encrypted messaging web app using JS. When composing a message, the user is provided with the public key of the recipients. A body field is also rendered for every recipient. After the user clicks submit, the original message is encrypted with the recipients’ public keys, which is then inserted into their respective body fields.

Since every user has their own body field (the ciphertext varies between users), a malicious user could write a different message for every recipient. How should I go about tackling this problem?

Include sender and receiver in the plaintext message (you need some kind of message format for that) and also sign the message (including sender / receiver) before encryption. That way an attacker cannot alter or swap the plaintext message. You may also need to assign the message a number of include some kind of timestamp to avoid replay attacks.

You could encrypt the message first using a message key and encrypt that key using the various public keys of the receivers. Note that the encryption scheme should not fall to plaintext / padding oracle attacks, as the signature should be over the plaintext, not the ciphertext.


How to improve entropy on a router running Linux kernel 2.6.x without TRNG or RTC? How could you improve entropy on a router running Linux kernel 2.6.x without TRNG or RTC ?

You don't need to continually feed entropy into the system for security, so long as the OS random number generator was strongly seeded once.

If you're unsure about the seeding history of the device, add some entropy. Take a photo of the sky with your mobile phone. Upload to your router and pipe it into /dev/random. That's all the entropy you'll ever need on that particular device.

Seriously, there is so much nonsense surrounding entropy gathering out there it's almost funny. The Linux manual page for /dev/random is the cause of much of this pseudoscience; it is simply wrong. The "entropy counters" provided by the kernel are ad-hoc estimates which are meaningless from a security perspective.

You can't "use up" or "lose" entropy on a modern OS. As long as your entropy is used only to seed a CSPRNG (which is true in even very old Linux), 256 bits of entropy is enough for every possible use case. If you don't believe that 256 bits is enough to generate a infinite stream of secure randomness, you'd better stop using AES in counter mode for encryption as well.


Prime Factorization in RSA always leads to the product of two primes? Lets prime factorize $30$:

$$30 = 3 \cdot 10 = 3 \cdot 2 \cdot 5$$

We see that the number $30$ is a product of $3$ primes. But in RSA, when factorizing huge numbers, we always seem to only get two primes. Why is this??

By construction, RSA moduli are the product of two large primes.