Chinese Remainder Theorem and RSA Wikipedia has a nice section regarding the speedup of the RSA decryption using the Chinese Remainder Theorem here. I need to understand the implementation of a similar speedup for the encryption algorithm of a more complex homomorphic encryption scheme (DGK) and, for some reason, I'm unable to get my head around the way the Chinese Remainder Theorem is used to achieve this. I don't have a lot of background on modular arithmetic and I would really appreciate it if someone could explain this in more detail.

Edit: Following @mikeazo's comment, I just want to understand the way CRT is applied to speed up the RSA encryption.

Well, the idea behind the CRT optimization is that if we know the factorization of the modulus $N$ (which we may if we have the private key), then we can split up the message $M$ into two halves (one modulo $p$, and one modulo $q$), compute each modulo separately, and then recombine them.  That is, we compute:

$m_1 = (M^d \bmod N) \bmod p = ((M \bmod p)^{d \bmod p-1}) \bmod p$

$m_2 = (M^d \bmod N) \bmod q = ((M \bmod q)^{d \bmod q-1}) \bmod q$

(Note that the exponents are reduced modulo $p-1$ and $q-1$; we can do this because $p$ and $q$ are prime (and Fermat's little theorem); this is the source of a good portion of the speedup).

Then, we recombine them; that is, we find a number $m$ such that:

$m \equiv (M^d \bmod N) \mod p$

$m \equiv (M^d \bmod N) \mod q$

Because of the Chinese Remainder Theorem (and because $p$ and $q$ are relatively prime), we can immediately deduce that:

$m \equiv (M^d \bmod N) \mod pq$

which is exactly what we were trying to compute.

Now, the questions in your comments appear to be asking about the details of this recombination step.

Now, it is actually fairly easy to see the correctness of the algorithm.  To make the last step work, we need to show that we have come up with a value $m$ such that:

$0 \le m < pq$

$m \equiv m_1 \mod p$

$m \equiv m_2 \mod q$

As for the the first criteria $0 \le m < pq$, well, that's straight-forward; we know that $0 \le m_2 \le q-1$, and $0 \le h \le p-1$, and so the smallest that $m$ can be is $0 + (0 * q) = 0$, and the largest it can be is $q - 1 + ((p-1)*q) = pq - 1$

As for the third criteria, that's also straight-forward; $(m_2 + (h * q)) \bmod q = m_2 \bmod q + (h*q) \bmod q = m_2 \bmod q$

The second one is a little tricker: $(m_2 + (h * q)) \bmod p = (m_2 + q * q_{inv} * ( m_1 - m_2) \bmod p) \bmod p = (m_2 + q * q_{inv} * (m_1 - m_2)) \bmod p$

Now, $q_\mathit{inv}$ is defined to be the number that, when multiplied by $q$ modulo $p$, results in 1 (that is, $q * q_\mathit{inv} \equiv 1 \mod p$).  Now, because the above equation is, in fact, computed modulo $p$, we can replace $q * q_\mathit{inv}$ with 1, which gives us:

$m \bmod p = (m_2 + 1 * (m_1 - m_2)) \bmod p = m_1 \bmod p$

QED


What is the correct use of RSA I study cryptography as a hobby and I made a high school work (essay-like) about cryptography. When I was defending my work in front of a committee, one of the teachers confronted me about my suggestion of RSA usage.

I claimed that the public key can be freely available on a website for everyone to download it (and I've seen people do it that way). His argument was that what if someone was listening to my communication and as well was able to hack my website and change my public key to a different one. That way, he could decrypt at least one message encrypted with this key (before I would realise that I myself can't decrypt it).

Is it a correct argument or is it just my fault that I had my website hacked? I think that the latter is the right answer.

RSA and other public-key protocols assume that the keys are securely delivered. To quote "Introduction to Modern Cryptography" by Lindell and Katz:

  Call the receiver Alice and the sender Bob. [...] We emphasize that the channel between Alice and Bob may be public, but is assumed to be authenticated, meaning that the adversary cannot modify the public key sent by Alice to Bob (and, in particular, cannot replace it with its own key). [...] An [...] approach is for Alice to generate her keys (pk, sk) in advance, independently of any particular sender. (In fact, at the time of key generation Alice need not even be aware that Bob wants to talk to her, or even that Bob exists.) Alice can widely disseminate her public key pk by, say, publishing it on her webpage, putting it on her business cars, or placing it in a public directory.

(Bold emphasis mine)

So, having said that, you're right that the system assumes the keys will be communicated in an authenticated manner. But also the committee member is right in that hacking the website would constitute a valid attack. When you define your threat model, it should be clear if an undetected hack of the website is within it and appropriate measures be taken. For example, if it is considered a reasonable threat, then the keys can be communicated by business cards handed in person or through a web-of-trust, among many key distribution mechanisms.


Difference b/w Hash function & Keyed Hash function? And HMAC with Matyas-Meyer-Oseas hash function I am looking for hash functions. In this process i came across hash & keyed hash functions(HAMC). In which it uses some has function to generate MAC.

And also Matyas-Meyer-Oseas hash function, which is of block cipher hash function.

I would like to know the difference between HMAC, and hash functions?

And about Matyas-Meyer-Oseas hash function, how hash will be calculated?

At least where can i find proper solution for this?

Intuitively a MAC is essentially the symmetric cryptography variant of a signature. To calculate a MAC a secret key which is shared between sender and receiver is used. This means that somebody who does not have the key cannot calculate the MAC.

A hash function on the other hand can be computed by anybody, uses no secrets and is simply used to get a shorter representation of data. For example, if somebody wants to sign an e-mail they usually hash it first and then sign the hash.

The Matyas–Meyer–Oseas construction is a way to construct a one-way compression function from a block cipher. This can then be used in the construction of a hash function, for example, using the Merkle–Damgård construction.

In particular, this means that the Matyas–Meyer–Oseas construction doesn't actually specify a complete hash function in an implementable way.


Compute maximum PRF advantage Hello all, I'm new to crypto,  I'm not sure if my thought process is correct ? any assistance will be helpful.

How useful is the partial info that A gets from (a), (b), and (c) ; in (c) A can determine Fn. How useful is this partial info in distinguishing F from a Rand Func

I understand that the advantage is the P ( Real) - P ( Rand). and in the first instance where the key is 000, each query that A makes returns the same output as the input. So the adversary will guess that they are in the real world since input and output matches

So does that mean the advantage is: 1 - (2^-3) ??

So does that mean the advantage is: $1 - (2^{-3})$ ??

That would be the advantage if the attacker knew apriori that the key was 000; however in this model, the attacker knows that the key is one of the eight listed values, but doesn't know which one (and each of the eight possibilities are equiprobable).

So, if the attacker doesn't know what the key is, what strategy of inputs can the attacker use to get the optimal advantage?  Hint: if the attacker is restricted to a single query, what's the probability distribution of the output of the block cipher; how does that compare to the probability distribution of a truly random output?


Why don't most encryption algorithms use perfect secrecy? Isn't it possible to make algorithms that are both computationally complex and have many possible answers if you try to crack them without knowing the password?
Why aren't many popular algorithms like AES like this?

Why don't most encryption algorithms use perfect secrecy?

Perfect secrecy can only achievable if the $\text{key size} \geq  \text{message size}$ and the key is never re-used.
It is not suitable for modern usage, where a lot of messages are sent/received and that is impractical since one has to send the key beforehand in a secure channel and this is not encryption. You must trust the carrier or you have to carry the keys yourself. Instead, we go the other way, use shorter keys with good analyzes algorithms. Exchange the key with DHKE protocol ( where mostly elliptic curve version is used), and use AES-GCM, AES-GCM-SIV, or ChaCha20-Poly1305.
Reuse of the key has catastrophic results that confidentiality is broken. What will you do when the keystream is depleted? Would you wait for the new key, or you would re-use some part of the keystream? Both have critical results. You will not communicate when needed or OTP will fail, see Crib-Dragging. Instead, one can use DHKE to create a new key, even for every encryption, and even can achieve forward secrecy.

Isn't it possible to make algorithms that are both computationally complex and have many possible answers if you try to crack them without knowing the password?

The encryption should be easily computed so that the legal party doesn't use so much power to encrypt. This doesn't mean that it is breakable since the adversary can compute with lots of resources. If the algorithm, block or stream cipher, use correctly given key then, then one can adjust the key size so that brute force out of reach of anybody, even for the quantum computers.
The encryption can be randomized and indeed in modern cryptography, we prefer this, forget the otherwise, it is insecure. See semantic security and indistinguishability. For example, we prefer at least Ind-CPA security. CBC and CTR mode can achieve this, however, ECB cannot. Actually we want more, the standard of IND-CCA2/NM-CCA2- ciphertext indistinguishability and non-malleability under adaptive chosen-ciphertext attack. The examples are AES-GCM, AES-CCM, and ChaCha20 which are an Authenticated Encryption with Associated Data (AEAD) and provides Confidentiality, Integrity and Authentication.
The decryption must be unique since there is no way for the receiver to determine the correct message among the possible answers.
The password is not the correct term. We use the encryption key or in a short key when it is clear in the context. The password is only applicable if the key is generated by using a Password Based Key Derivation Function like PBKDF2 or Argon2id.

Why aren't many popular algorithms like AES like this?

Mostly answered, AES is a fast and secure keyed permutation. Yes, for each key, AES chooses a permutation from all possible permutations. We expect that it chooses this in a way that its selection is indistinguishable.

There are also Q/A and answer here that talks about achieving perfect secrecy with AES with some very nice answers;

Can one claim that AES is a perfect cipher?
Can one claim that AES has perfect secrecy for a key size and message size of 128 bits?
Key length and message length in AES and perfect secrecy if plaintext length <= key length


Amateur question: Constant two way cryptography First of all, I would like to tell you guys that I'm a complete noob at cryptography in general, so please pardon any dumb stuff I may say.
Well, I have used a lot of cryptography libraries in a couple projects I have done in the past. They usually work like this:

Input: secure = cryptography('sensitive data', 'password, salt, key, whatever');
Output: U2FsdGVkX1/+sKF6K1TD2/wdHJRwhuwuYez4yESJxuI= ( or something like this)

Question is, when I run the exact same piece of code, the output is always different:

input: secure = cryptography('sensitive data', 'password, salt, key, whatever');
Output: U2FsdGVkX1+TkUfkTukfsEuSBMree9vg2I/ixgOZE1A= (different output from the first time)

Being completely ignorant about cryptography, I don't know why do they change like this every time I run the exact same piece of code again and again.
So, I would like to know, why do they behave like this? And, is there any cryptographic algorithm that always returns the same output when the sensitive string and the key are equal no matter how many times I run the code? Thank you very much.

Two reasons why cryptographic algorithm often behaves as you observe (non-deterministically):

When the objective is to encipher some secret, it is necessary for security in many scenario. Otherwise, an observation post sending its report which usually is "Nothing in sight anywhere" would always send the same cryptogram in this situation, allowing to discriminate this usual case from "Elbonian vessels by south".
Things get worse with public-key encryption: if the encryption was deterministic, it would be possible to check a guess of the message; thus knowing that the message is the name of someone in class, someone with the class roll could break the encryption.
In some other applications, some randomness is necessary for security, or strengthens it, because it makes internal values unknown or unpredictable to an adversary. An example is signature: many signature schemes (including DSA, ECDSA, and to a lesser degree RSASSA-PSS), rely on a random value drawn by the signer (that must imperatively remain secret in [EC]DSA), and influence the result.

Deterministic encryption can be done, but as stated above that tends to be a defect (in particular it prevents from meeting the standard academic goal of CPA security), thus this is uncommon.

I looks like what you are looking for is deterministic password-based encryption with salt. This could be done as follows:

turn password and salt into an AES key using a Password-Based Key Derivation function like PBFDF2, Bcrypt, or Scrypt (these are deterministic)
encipher the result using AES in CBC mode with the IV implicit and set to zero, and some standard byte padding.
move the last 16 bytes of the ciphertext in the front, and again encipher the result using AES in CBC mode with the IV implicit and set to zero (no byte padding is needed this time).

For decryption:

turn password and salt into an AES key as in encryption
decipher the ciphertext using AES in CBC mode with the IV implicit and set to zero, and move the first 16 bytes of the deciphered plaintext to the end
decipher the ciphertext using AES in CBC mode with the IV implicit and set to zero, and undo the byte padding.

The double encryption gives some level of insurance that plaintext with the same beginning won't be recognizable as such from the ciphertext.


RSA blind signatures in practice Hi I have a problem with moving my blind signature implementation from educational (textbook RSA) to more practical (padded RSA) side.

David Chaums paper gives a following figure:

$r$ - blinding factor

$e$, $d$ - public & private exponent

$Blinded\ message = Message \cdot r^{e}$

$Signature\ of\ a\ Blinded\ message = Blinded\ message^{d} = (Message \cdot r^{e})^{d} = Message^{d} \cdot r^{ed} = Message^{d} \cdot r\ (\bmod\ N)$

now to unblind a blinded message we should remove the blinding factor:

$Unblinded\ signature = Signature\ of\ a\ Blinded\ message \cdot r^{-1} = Message^{d} \cdot r\ \cdot r^{-1} = Message^{d}\ (\bmod\ N)$

It is clear that real-world RSA implementation shouldn't use plain textbook for encryption or signature purposes as it is vulnerable to a range of attacks. To overcome these attacks a textbook must be armoured with "padding", prior encryption or signature operation.

Now, as far as I understood (in simple English): a "padding" process "changes" the plain text prior encryption to make it more durable to known attacks.

Mathematically speaking, the whole process would look like:

$Signature\ of\ a\ Blinded\ message = pad(Message \cdot r^{e})^{d} (\bmod N)$

In other words "padding" destroys blind signature, because there is no such "$unpad$" function that would satisfy the following equation:

$unpad(pad(Message \cdot r^{e})^{d})\ (\bmod N) = (Message \cdot r^{e})^{d}$

So this means blind signatures can not be used with padding.

Question Am I correct that using blind signatures in practice, one should never use a public/private key pair for both encryption and blind signature purposes together, and to actually use a blind signature that person is obligated operate on a plain textbook making the whole process vulnerable to a range of attacks?

EDIT

As far as I understood the whole process, there are two sides A - Applicant, B - Bank. For example Applicant creates a token that represents 10\$ with serial number AH43S, then Applicant blinds the token with random R so that the Bank is not able to discover token's serial number. Then applicant sends blinded token to Bank, and asks it to sign with 10\$ key. Now Bank needs to pad a blinded version of token, to prevent any attacks on it's key, and after the blinded token is padded there is no way to unblind it...

The padding is applied on the bank side(side that signs the message), am I correct? And if so, it would break blinding factor presented by the side that asked to sign a token...

The answer is correct, you don't need to unpad the message.
When/if you verify the signature, simply check that $(\text{signature})^e == \text{pad}(\text{message})$

Regarding the padding scheme, you can just use a full domain hash.

Here's how you implement a full domain hash:
$$ \mathrm{cycles} = \frac{\text{(RSA key length)}}{\text{(SHA digest length)} \times 8} + 1$$
(e.g., RSA key length = 1024bits and SHA digest length = 20bytes)
$$ \mathrm{FDH}(M) = \mathrm{SHA1}(M || 0) \mathbin\Vert \mathrm{SHA1}(M || 1) \mathbin\Vert \ldots \mathbin\Vert \mathrm{SHA1}(M || \mathrm{cycles}-1)$$

where $||$ denotes concatenation


Where did the SHAKEs come from in SHA3? Where did SHAKE128 and SHAKE256 originate from?

I am trying to find them in the original Keccak documentation but can't find them.

Is it some special mode of Keccak referenced in the documentation? Or something invented by NIST and added to the SHA3 standard?

Any public cryptanalysis done on them?

Where did SHAKE128 and SHAKE256 originate from?

They follow from the general properties of the sponge construction. A sponge function can generate an arbitrary length of output. The submission of Keccak to the SHA-3 competition proposed a single "XOF" (extendable-output function) with a user defined length, which would have been essentially SHAKE-288. NIST seems to have decided on two instead, with more "normal" security levels.

  Any public cryptanalysis done on them?

Anything on the generic Keccak function may also apply to them. I don't know of any cryptanalysis specifically on the XOFs, beyond what was done by the authors themselves in the submissions and the site I linked above. However, a comment (pdf) to the draft standard complains that the usage of XOFs (i.e. SHAKEs) is not defined well enough and that their security claim is not very rigorously stated.


Which cryptography technique does not increase the size of the plain data? I want to encrypt some data(text/voice/video) but it is essential that the size of the cipher data remains the same as the plain data.

Which techniques can I use, and how secure are these techniques as compared to the ones which increase the size of the data?

The standard answer to this question is format-preserving encryption (FPE). FPE is a class of techniques that allow you to encrypt data while preserving some of its format (which can include its length).

In terms of security, most FPE schemes are deterministic, which means they do not achieve the standard IND-CPA notion of security. However, for high-entropy message distributions this is probably not an issue (ymmv). If your ciphertext can't be even one bit longer than the input plaintext, you don't have space to include a random IV or tweak, so randomization is out of the question unless you get tricky with your protocol.

FPE schemes usually do achieve a security notion called "strong indistinguishability from a random permutation", or SPRP.

For an example of FPE being used in a network protocol, see this paper on network protocol obfuscation.


Why would my certificate's signature algorithm differ from its keys' signature algorithms? I have a signing certificate that I'm loading into an X509Certificate2 object in Visual Studio. I can't get my head around why the certificate itself has one signature algorithm, while the same certificate's public and private keys have a different signature algorithm.

Specifically:

x509Certificate.SignatureAlgorithm.FriendlyName = "sha256RSA"
x509Certificate.PrivateKey.SignatureAlgorithm = "http://www.w3.org/2000/09/xmldsig#rsa-sha1"

Does it matter that the former is SHA-256 and the latter is SHA-1?

I can't get my head around why the certificate itself has one signature algorithm, but the same certificate's public and private keys have a different signature algorithm.

A certificate is a document signed by an issuer (the certificate authority or "CA"), that contains a public key used to verify signatures by a subject (the "owner" of the certificate so to speak).  The issuer and subject's choices of signing algorithm are independent.  What's going on here is that the certificate contains a signing key with one algorithm, and the issuer signed it with a different algorithm.  A very silly analogy:

Issuer is a notary
Subject is notary's client
Keys are pens
Algorithms are ink colors
Notary and client can use pens with different ink colors

The x509Certificate.SignatureAlgorithm field in your question seems to correspond to section 4.1.1.2 ("signatureAlgorithm") of RFC 5280:

  The signatureAlgorithm field contains the identifier for the cryptographic algorithm used by the CA to sign this certificate.

The key word there is "CA"—the issuer of the certificate.

Certificates in the proper sense of the term don't include private keys, so the x509Certificate.PrivateKey property that you describe must be related to the software library that you're using.  The certificate proper however, under tbsCertificate.subjectPublicKeyInfo, contains SubjectPublicKeyInfo records that specify algorithms used by the subject keys, as explained in section 4.1.2.7 ("Subject Public Key Info"):

  This field is used to carry the public key and identify the algorithm with which the key is used (e.g., RSA, DSA, or Diffie-Hellman).  The algorithm is identified using the AlgorithmIdentifier structure specified in Section 4.1.1.2.

And this, again, is independent of the other field, because one is for the issuer and the other is for the subject.

  Does it matter that the former is sha256 and the latter are sha1?

It's not a problem that the algorithms are different, but it is one to have SHA-1 in the latter, since SHA-1 should no longer be used for public-key signatures.


Finding the IV values of SHA-256 given all message blocks Given all message blocks $w[i],i \in 0:63$ and assume that $n<128$ (arbitrary) bits $x_1,x_2,...,x_n$ of the IV values are unknown (e.g., $h_7$ bits are unknown) while other IV values coincide with those in the SHA-256 algorithm. Let $h_{i}^{j}$ denotes $i$-th hash of $j$-th round that is $$(h_{0}^{0},h_{1}^{0},...,h_{7}^{0})\overbrace{\mapsto}^{SHA256}(h_{0}^{1},h_{1}^{1},...,h_{7}^{1})\overbrace{\mapsto}^{SHA256} ...\overbrace{\mapsto}^{SHA256}(h_{0}^{64},h_{1}^{64},...,h_{7}^{64}),$$ and $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ depends on $n$ unknown IV bits. Now let us take $n$ (arbitrary) bits $y_1,y_2,...,y_n$ of $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ and assign values to them.

Question: Is there a possibility to find $x_1,x_2,...,x_n$ giving the assigned values of $y_1,y_2,...,y_n$ faster than exhaustive search?

Remark. One can notice that for the fixed $w$ the function

$\operatorname{SHA256}_{w}^{-64}(h_{0}^{64},h_{1}^{64},...,h_{7}^{64}) = (h_{0}^{0},h_{1}^{0},...,h_{7}^{0})$ can be constructed analytically, so if all the bits of $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ are known, it is easy to obtain IV values. However, if only $n<128$ bits are assigned it is needed to find $2^{256-n}$ preimages in the worst case.

With the question as asked, no, there it is not possible to recover the missing part of $h_0^0,h_1^0,\ldots,h_7^0$ faster than brute force search.
The question states:

$\operatorname{SHA256}_{w}^{-64}(h_0^{64},h_1^{64},\ldots,h_7^{64})=(h_0^0,h_1^0,\ldots,h_7^0)$ can be constructed analytically

Most probably, this not even a function, because the true SHA-256 compression function $\operatorname{SHA256}_{w}$, hereafter $F$, is most probably not a bijection, hence $F^{-1}$ not a function, due to the construction of $F$ as
$$\begin{align}F: \{0,1\}^{256}&\longmapsto\{0,1\}^{256}\\
h'\quad&\longrightarrow\;F(h)\;\underset{\text{def}}=\;G(h)\boxplus h\end{align}$$
where

$h$ denotes vector $h_0,h_1,\ldots h_7$ assimilated to a 256-bit bitsring from $\{0,1\}^{256}$
$G$ is a bijection, fully determined by the 512-bit padded message block (taken from $w$) at this compression step, and the specification of SHA-256. $G$ is essentially a 64-rounds block cipher with known sub-keys. A useful mental model of $G$ is an arbitrary bijection of the set $\{0,1\}^{256}$.
$\boxplus$ is addition modulo $2^{32}$ of 32-bit words, a regular group operation of the set $\{0,1\}^{256}$.

Knowing $h'=G(x)\boxplus h$, we know no method to find unknown $h$ better than brute force search, and there's demonstrably no better one under the simple model of $G$ as an oracle implementing an arbitrary bijection.
If we additionally know part of $h$ [e.g. $h_7$ as in the question for the first compression step, or even $h_1,h_2\ldots,h_{7}$ ], the best that it does is simplify slightly the combinatorial problem we face, but again the best known method to solve it is essentially brute force, and demonstrably so under the random oracle model.
Therefore, even if the question was asked for a single compression step and the full output known, there's no known method to solve it more efficiently than searching the unknown input bits, with cost $\mathcal O(2^n)$. More compression steps make the situation even more hopeless.

This late comment introduces a radical variant with the compression function simplified to $F=G$. Now $F^{−1}$ is a function, easily computed by inverting each of the 64 rounds in $G$ in reverse order.
Wikipedia's compression main loop pseudocode:
for i from 0 to 63
    S1 := (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
    ch := (e and f) xor ((not e) and g)
    temp1 := h + S1 + ch + k[i] + w[i]
    S0 := (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
    maj := (a and b) xor (a and c) xor (b and c)
    temp2 := S0 + maj
    h := g        g := f        f := e
    e := d + temp1
    d := c        c := b        b := a
    a := temp1 + temp2

can be inverted as:
for i from 63 downto 0
    S1 := (f rightrotate 6) xor (f rightrotate 11) xor (f rightrotate 25)
    ch := (f and g) xor ((not f) and h)
    S0 := (b rightrotate 2) xor (b rightrotate 13) xor (b rightrotate 22)
    maj := (b and c) xor (b and d) xor (c and d)
    temp2 := S0 + maj
    temp1 := a - temp2
    a := b        b := c        c := d
    d := e - temp1
    e := f        f := g        g := h
    h := temp1 - S1 - ch - k[i] - w[i]

Note: when going backward, S1, ch, S0, maj and temp2 are computed from different variables using otherwise the same formulas as forward; and temp1 (resp. d and h) are computed by reversing with basic algebra the formulas used to forward-compute a (resp. e and temp1).
If we knew the whole output $h^{64}$, we could efficiently walk back from it to $h^0$ with 64 evaluations of the $F^{−1}$ functions determined by the 64 known fragments of $w$, as efficiently as hashing forward. The partial knowledge of the IV would be of little help.
But in the question we only know $n$ out of 256 bits of $h^{64}$. The best attack is educated brute force as suggested in the question, with a cost of $\mathcal O(2^{\min(n,256-n)})$. This is obtained by searching unknown input bits for small $n$, and unknown output bits for large $n$. Argument: the whole chain of (modified) compression functions forms a bijection, and in the random oracle model for that the best attack is such brute force.


Difficulty of collision vs preimage vs second-preimage attacks It seems at first glance that brute-forcing a collision would be exactly as difficult for all of them. They all (I would expect) work like this: select a hash value, and then try messages to get an equal hash.

The difference between them is just how that first hash is selected:

Collision: random message.
Preimage: the supplied hash.
Second-preimage: the hash of the supplied message.

So why are they different in difficulty? (~$2^{n}$ vs ~$2^{n/2}$) Yes. Obviously I'm wrong about some point (probably that collision resistance has some shortcut). I'm asking what is my error.

EDIT

It seems that the simple answer to my question is that collision resistance is weaker because every hash one is testing can be paired with every hash tested up to that point, and not only with one specific hash.

If this is not correct - please correct me. If it is, however:

In practice, somewhere around $2^{40}$ (-Terabyte) - the IO time for storing and testing would probably be greater than hashing a message (which can be in excess of $10^{8}$ hashes/s). and over $2^{60}$ would probably be practically impossible. So the difficulty levels are more theoretical than practical for high values such as in the case of SHA-256. Is this correct?

For a $n$-bit ideal hash:

Finding a collision is expected to require a little above $2^{n/2}$ hashes, in short because after having computed $m$ hashes, there are $m(m-1)/2$ opportunities of collisions. For details, see Birthday problem for cryptographic hashing, 101.
Finding a preimage (first or second) is expected to require about $2^n$ hashes, in short because the best known method is to try until hitting the hash thought, and each try has odds $2^{-n}$ to succeed.

The naive algorithm to find collisions with about $2^{n/2}$ hashes requires to store the previous hashes and search among these, thus requires in the order of $2^{n/2}n$ bits of memory, which is totally impractical for cryptographic hashes. However, with better methods, memory becomes essentially a non-issue.

The simplest such method is Floyd's cycle finding, which uses negligible memory, at the expense of like tripling the expected number of hashes. Better methods exist that achieve a lower increase of the expected number of hashes, or/and allow a near arbitrary number of independent search engines to cooperate with modest data exchange. The reference article is Paul C. van Oorschot, Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology (1999).


Parallel file encryption and authentication for large files For a cloud storage upload client I want to encrypt files during upload, so that they cannot be read by the cloud service provider or anyone who gains access to the account. I would like to use some standard format, instead of rolling my own crypto, but I couldn't find anything that does what I want.

The main problem is that I want to split large files and upload them in parallel to maximize bandwidth. If uploading of a part fails, I might have to go back and upload the same part again. Therefore, I need an encryption scheme which allows encrypting only some parts within a file. Also, a full authentication pass before uploading should be avoided.

After a lot of reading in the past two days I came up with the following scheme:
Split the file into fixed sized (few KB) blocks. Calculate the SHA-1 hash of each individual block and append it to the plaintext. Encrypt the plaintext and the following hash using AES in CBC mode with a random IV for every block. This is similar to what RFC 4880 specifies for symmetric encryption, just with blocks. This provides authentication for every individual block. To protect the file as a whole, an additional last block with a concatenation of all block hashes is processed using the same technique.

From the RFC 4880 document it's already clear that this only provides modest security against modifications. So I'm thinking about further improvements. The use of a simple hash function could be replaced with a HMAC. From this document it's clear, that authenticate-then-encrypt is not generically secure. However, for CBC mode this doesn't apply, so I would like to keep authenticate-then-encrypt, since it allows easy checking of the encryption key, without decrypting the whole file. I'm also not very happy about, the last block which repeats all the previous hashes. Maybe a HMAC off all previous hashes would suffice? I hope someone can shed some light on the practical security of this technique.

I also stumbled across GCM, which seems exactly what I want. However, I understand that there is a limit of ~68GB, which can be encrypted for a given IV/key pair. Is it safe to approach this limit, or should one stay far below? Also, I didn't find any good Python library which actually allows parallel encryption using GCM.

To answer your ideas of:

"I use hash-then-encrypt" with CBC + SHA-1
"I use MAC-then-encrypt" with CBC + HMAC
"I won't use GCM because of unclear usage guidance"

First, hash-then-encrypt is a really bad idea. You really should avoid it if possible. Details are explained in this related question on Crypto.SE.

Second, MAC-then-encrypt is a concept you also should avoid. Not only do generic compositional security proofs don't generally hold, but it also allows for padding oracle attacks in some circumstances, so encrypt-then-MAC is better and there's no significant advantage to use authenticate-then-encrypt over the more generically secue encrypt-then-authenticate. Also see our canonical question on this subject.

Third : GCM. You indeed only should encrypt than less than 60GiB of data under a given key-nonce pair. However, you could assign (ascending) nonces to your data chunks (of a few kBs each) and authenticated encrypt them each using a different nonce. This way you stay way below the 60GB limit and you generate your nonces deterministically (using counter incrementation) which will also quite reliably protect you against nonce re-use based on nonce collisions. Upon retrieval of the data you could just check then whether all chunks are valid and whether a chunk is missing (because there's a gap in the nonces) and maybe you'd want to encode the number of chunks into each chunk to allow proper verification.


What is a good way to handle longer strings using FPE? While experimenting with this FPE based on FE1

http://botan.randombit.net/manual/fpe.html

(well actually a port of it in C#)  I found when the string length gets too long (number of characters N) basically it's designed to throw an exception

So the byte array for the modulus is limited to this value

    // Normally FPE is for SSNs, CC#s, etc, nothing too big
    private const int MAX_N_BYTES = 128 / 8;

And this is where we check the length of the byte array

    /// <summary>
    /// A simple round function based on HMAC(SHA-256)
    /// </summary>
    private class FPE_Encryptor
    {
        private System.Security.Cryptography.HMACSHA256 mac;

        private byte[] mac_n_t;

        internal FPE_Encryptor(byte[] key,
                         BigInteger n,
                         byte[] tweak)
        {
            mac = new System.Security.Cryptography.HMACSHA256(key);

            mac.Initialize();

            byte[] n_bin = n.encode();

            if (n_bin.Length > MAX_N_BYTES)
                throw new Exception("N is too large for FPE encryption");

            var ms = new MemoryStream();

            ms.update_be(n_bin.Length);
            ms.update(n_bin);

            ms.update_be(tweak.Length);
            ms.update(tweak);

            mac_n_t = mac.ComputeHash(ms.ToArray());
        }

        internal BigInteger F(int round_no, BigInteger R)
        {
            byte[] r_bin = R.encode();
            var ms = new MemoryStream();
            ms.update(mac_n_t);
            ms.update_be(round_no);

            ms.update_be(r_bin.Length);
            ms.update(r_bin);

            byte[] X = mac.ComputeHash(ms.ToArray()).Reverse().ToArray();
            var X_ = new byte[X.Length + 1];
            X.CopyTo(X_, 0);
            X_[X.Length] = 0; // guarantee a positive interpretation
            BigInteger ret = new BigInteger(X_);
            return ret;
        }
    }

However say I want to encode a long string like this "Asddasdasdasdasdasdasdasd"

I'm in Base 52 so my modulus is very large 7944811378381908491977011631194721432371200

Which after converting to byte array using

    internal static byte[] encode(this BigInteger n)
    {
        if (n.IsZero) return new byte[0];
        else return n.ToByteArray().Reverse().SkipWhile(h => h == 0).ToArray();
    }

gives a length of 18, bigger that the maximum 16.

Does anyone have suggestion how to deal with the larger number of characters in the plaintext you want to encrypt?  I was thinking to chop it up into fragments and encrypt the pieces if the string gets longer than a maximum value.  Would this be acceptable?

FE1 has no inherent maximum length; that limit is imposed by the implementation.  The first obvious suggestion would be to use an alternate implementation without that limitation.

Now, lets assume that's not a viable option; that you have to use this particular FE1 implementation.

Now, the problem with chopping up the plaintext into fragments and encrypting those separately is that if someone modifies just one of those encrypted fragments, they'll modify part of the decrypted plaintext, but not all.

I'll suggest a way around that, using the "tweak" that FE1 also provides.  This "tweak" value is another input into the FE1 algorithm that modifies how it encrypts data; it is not assumed to be secret, but not be presented to both the encryption and the decryption.  What it is intended to do is bind the ciphertext to a particular context (so that the ciphertext cannot be used in any other context).

The idea is to split up the plaintext, and encrypt each one separately; however we use the rest of the message as a tweak.  For example, if we split up the plaintext into three sections $P_1, P_2, P_3$, we generate the ciphertext as:

$$C_1 = FE1_k( P_1, 0 || P_2 || P_3 )$$
$$C_2 = FE1_k( P_2, 1 || C_1 || P_3 )$$
$$C_3 = FE1_k( P_3, 2 || C_1 || C_2 )$$

(where $FE1_k(A, B)$ means "the $FE1$ encryption of $A$, using key $k$, with tweak $B$).

In general, ciphertext $C_i$ is defined as $C_i = FE1_k( P_i, i || C_1 || C_2 || ... || C_{i-1} || P_{i+1} || P_{i+2} || ... || P_n )$

To decrypt, you just do things in the opposite order:

$$P_3 = FE1^{-1}_k( C_3, 2 || C_1 || C_2 )$$
$$P_2 = FE1^{-1}_k( C_2, 1 || C_1 || P_3 )$$
$$P_1 = FE1^{-1}_k( C_1, 0 || P_2 || P_3 )$$

By binding each ciphertext block to both the previous and subsequent blocks, you prevent anyone from modifying part of the message without affecting everything.  This does assume that your FE1 implementation allows long tweaks.


In RSA, rationale for prime $p$ with $p-1$ having prime factor $u$ with $u-1$ having large prime factor? In the 1978 RSA paper, it is recommended, among other things, to choose primes $p$ such that $(p-1)$ has a large prime factor $u$. This was motivated by Pollard's p-1 algorithm. Further, the authors state:

  Additional security is provided by ensuring that $(u−1)$ also has a large prime factor.

What was the motivation for that?

This issue, and its history, was discussed at length in Silverman and Rivest. The relevant passage here is in Section 6, which I quote:

  In 1977 Simmons and Norris [53] discussed the following "cycling" or
  "superencryption" attack on the RSA cryptosystem: given a ciphertext
  C, consider decrypting it by repeatedly encrypting it with the same
  public key used to produce it in the first place, until the message
  appears. Thus, one looks for a fixed point of the transformation of
  the plaintext under modular exponentiation. Since the encryption
  operation effects a permutation of $\mathbb{Z}_n =  \{0,1,\ldots,n-1\}$, the message can eventually be obtained in this
  manner. Rivest [46] responds to their concern by (a) showing that the
  odds of success are minuscule if the n is the product of two
  $p^{--}$-strong primes, and (b) arguing that this attack is really a
  factoring algorithm in disguise, and should be compared with other
  factoring attacks.


How do Käsper and Schwabe's Bitsliced AES Mixcolumns work? The only way I see it possible to do the matrix-multiplication in the MixColumns operation of AES is by shifting the bits in the multiplied number, and then reduce with the polynomial if needed.

This can be done in constant time for a bitsliced implementation as shown below in C-like pseudo-code (the example is for multiplication by $3$ in $GF(2^8)$):

vector bit[8] = "bits from a bitsliced byte";
vector new_bit[8];

//First multiply with 2 in GF(2^8) with polynomial x^8+x^4+x^3+x+1:
new_bit[0] = {0} ^ bit[7];
new_bit[1] = bit[0] ^ bit[7];
new_bit[2] = bit[1];
new_bit[3] = bit[2] ^ bit[7];
new_bit[4] = bit[3] ^ bit[7];
new_bit[5] = bit[4];
new_bit[6] = bit[5];
new_bit[7] = bit[6];

//XOR M2 with original bits to get the result for multiplying with 3
for (int bit = 0; bit < 8; bit++){
 new_bit[i] = new_bit[i] ^ bit[i];
}

However, this does not seem to be the way that Käsper and Schwabe do it in their bit-sliced AES MixColumns operation. Instead they are doing rotates. I have read their paper and looked at the layout of their bit-sliced state, but I'm unable to understand, how they arrive at those equations. If someone understands it, could they perhaps help a poor soul out there to understand it too? Just sending me in the direction for a paper that explains it more in depth would mean the world to me as well!

I'm currently trying to implement a bit-sliced mix columns implementation for a cipher other than AES (I'm trying to bit-slice the primates cipher: http://primates.ae/wp-content/uploads/primatesv1.02.pdf), and have currently made the "simple" MixColumns that I described. I'm curious in whether it can be done better, after having seen that they do it differently in their AES implementation. There's not the same symmetry in this MixColumns matrice, so I doubt a bit that it is possible.

EDIT: Here is a link to their AES implementation paper: https://www.iacr.org/workshops/ches/ches2009/presentations/01_Session_1/CHES2009_ekasper.pdf

Slide #8 in the presentation you linked to describes the way Käsper and Schwabe pack the bits of the AES data blocks into CPU registers.

According to the slide, what they're doing is processing eight 128-bit AES blocks in parallel, using eight 128-bit XMM registers to store them.  They're not doing basic "naïve bitslicing", which would involve using 128 $n$-bit registers to process $n$ different 128-bit AES blocks in parallel, but rather exploiting the structure of AES to effectively do "byte-level bitslicing".

Conceptually, each AES block consists of a 4×4 matrix of 8-bit bytes, for a total of 4 × 4 × 8 = 128 bits.  The standard packing order of these bits in AES input / output looks like this:

| Block 0:
|-------------------------------+-------------------------------+
|           Column 0            |           Column 1            |
|-------+-------+-------+-------|-------+-------+-------+-------|
| Row 0 | Row 1 | Row 2 | Row 3 | Row 0 | Row 1 | Row 2 | Row 3 | ...
|-------|-------|-------|-------|-------|-------|-------|-------|
| bits  | bits  | bits  | bits  | bits  | bits  | bits  | bits  |
| 0 - 7 | 0 - 7 | 0 - 7 | 0 - 7 | 0 - 7 | 0 - 7 | 0 - 7 | 0 - 7 |

That is, the bits of each input / output byte are stored consecutively, and the bytes within each block are sorted first by column and then by row.

Note that, even though standard non-bitsliced AES only processes one block of data at a time, I've included a block number at the top row of the diagram.  This becomes relevant when comparing this standard packing order with the internal order used by Käsper and Schwabe, since their bitsliced AES implementation processes 8 blocks at the same time.

Specifically, whereas the canonical AES bit packing order illustrated above can be compactly summarized as "block > column > row > bit", the internal packing order used by Käsper and Schwabe is "bit > row > column > block":

| Register 0 (stores bit 0 of each byte):
|-------------------------------+-------------------------------+
|             Row 0             |             Row 1             |
|-------+-------+-------+-------|-------+-------+-------+-------|
| Col 0 | Col 1 | Col 2 | Col 3 | Col 0 | Col 1 | Col 2 | Col 3 | ...
|-------|-------|-------|-------|-------|-------|-------|-------|
| block | block | block | block | block | block | block | block |
| 0 - 7 | 0 - 7 | 0 - 7 | 0 - 7 | 0 - 7 | 0 - 7 | 0 - 7 | 0 - 7 |

Since they're processing 8 independent input blocks at a time, the bits from different input blocks never influence each other.  In particular, this implies that, using the "reversed" representation above, the bits in each byte never influence each other, and so the entire AES encryption can be implemented using only byte shuffling and bitwise logic operations at byte (or larger) granularity.

Specifically, looking at slide #11 of the presentation, Käsper and Schwabe note that, in their AES implementation:

ShiftRows is reduced to byte shuffling, for which the Intel SSSE3 instruction set they're using has a dedicated instruction (pshufb); and
MixColumns can be implemented using a combination of byte shuffling and XOR.

I have not actually looked at Käsper and Schwabe's AES implementation code (and, in any case, I suck at reading Intel assembly code), but a basic naïve implementation of AES MixColumns using their bit packing would look something like this pseudo-C code:

// rotate each 32-bit block of state by 8 bits
void rotateColumns (uint128_t state[8]) {
    for (int i = 0; i < 8; i++) {
        uint128_t temp = state[i];
        state[i] = ((temp & 0x00FFFFFF00FFFFFF00FFFFFF00FFFFFF) << 8)
                 | ((temp & 0xFF000000FF000000FF000000FF000000) >> 24);
    }
}

// multiply each AES byte (spread across the 8 state registers)
// by 0x02 = x modulo the AES polynomial x^8 + x^4 + x^3 + x + 1
void doubleBytes (uint128_t state[8]) {
    uint128_t temp = state[7];
    for (int i = 0; i < 7; i++) state[i+1] = state[i];
    state[0] = temp;
    state[1] ^= temp;
    state[3] ^= temp;
    state[4] ^= temp;
}

void bitslicedMixColumns (uint128_t state[8]) {
    uint128_t oldstate[8];
    for (int i = 0; i < 8; i++) oldstate[i] = state[i];
    rotateColumns(oldstate);
    for (int i = 0; i < 8; i++) state[i] ^= oldstate[i];
    doubleBytes(state);
    for (int i = 0; i < 8; i++) state[i] ^= oldstate[i];
    rotateColumns(oldstate);
    for (int i = 0; i < 8; i++) state[i] ^= oldstate[i];
    rotateColumns(oldstate);
    for (int i = 0; i < 8; i++) state[i] ^= oldstate[i];
}

A less naïve implementation would of course inline the helper functions, unroll the loops, use registers instead of arrays, and replace the klugy byte rotation in rotateColumns e.g. with a pshufb instruction and the trivial shift loop in doubleBytes with register renaming.


Understanding the q-SDH Problem (on elliptic curves) I have some troubles in understanding the q-SDH problem. The discrete logarithm problem states the following.

Given a point P of order on an elliptic curve and a point Q on the same curve. It is hard to find a such that $0 \leq a \leq p-1 $ and $Q = aP$.

The q-SDH problem states the following:

Let $g_1$ be a generator of the elliptic curve. Given $\beta \in \mathbb{Z}_q^*$ and q+1 tuple $(g_1, \beta g_1, \beta^2g_1, ..., \beta^qg_1)$ it is hard to find the SDH tuple $(x, \frac{1}{\beta+x}g_1 ) $

I do not understand why we have to find $\frac{1}{\beta+x}g_1$. Why is this hard? What is the underlying problem? Is the discrete log problem somewhere hidden? Why do we need x?

The goal of the problem as you've described it is to find any $x$ along with $\frac{1}{\beta + x} g_1$.

There's no real reason it's in the denominator. That's just the definition of the problem. If you believe the assumption that this problem is hard, then you believe that finding those values (where $x, \beta$ are in the denominator) is hard to compute.

As for why it's hard: we don't know that it's hard, it's just an assumption (as one comment pointed out, it's definitely not harder than the discrete log problem).


Does gpg's symmetric encryption keep information about the filename? If I encrypt a file with gpg -c file.zip, and change the filename. Is there any way I can restore the filename as I used as a password. or the name encrypted to?

Yes, gpg -c file.zip does encode the input file name in the encrypted packet.
The gpg man page documents a few relevant options:

--set-filename string
Use string as the name of file which is stored in messages.

This  overrides the default, which is to use the actual filename of the file being encrypted.

--use-embedded-filename
Try to create a file with a name as embedded in the data. This can be a dangerous option as it allows to overwrite files.

This defaults to no.


How to understand "homomorphically decrypting" in bootstrapping? I come across the following explanation of bootstrapping in this tutorial:

  Once the “noise” in a ciphertext grows too large it is no longer able to be decrypted properly. Bootstrapping solves this problem. It does so by homomorphically decrypting the ciphertext, performing a single computation on it, and then recrypting under a different public key.

What is the meaning of homomorphically decrypting? Does it mean decrypt to the plaintext first then recrypt again?

Does it mean decrypt to the plaintext first then recrypt again?

No. It doesn't. It just mean to run a "homomorphic version" of the decryption function. Since homomorphic evaluation just use homomorphic operations and these operations always return ciphertexts, the result of homomorphic decryption is also a ciphertext. And since the decryption removes the noise, this new ciphertext is fresh.

Think of evaluating homomorphically as a function, which we will call $Eval$.

So, homomorphically evaluating any function $f$ on arguments $m_0$, $m_1$, ..., $m_\ell$ means to execute $Eval(pk, f, [m_0]_{pk}, [m_1]_{pk}, ..., [m_\ell]_{pk})$, which returns $[f(m_0, m_1, ..., m_\ell)]_{pk}$.

(Here I'm using $[m]_{pk}$ to denote the encryption of $m$ under the public key $pk$).

That is, $Eval$ returns an encryption of the function evaluated in the arguments, given the function, encryptions of those arguments, and the public key used to encrypt them.

Now, let's say you have a pair of keys $sk$ and $pk$ and you want to refresh a ciphertext $c = [m]_{pk}$. Then, you have to homomorphically decrypt $c$. To do so, replace $f$ by $Dec$. Also, the arguments of $Dec$ are $sk$ and $c$, so, you should use $[sk]_{pk_1}$ and $[c]_{pk_1}$, for some public key $pk_1$. Then, we get:

$\begin{align}
Eval(pk_1, Dec, [sk]_{pk_1}, [c]_{pk_1}) &= [Dec(sk, c)]_{pk_1}\\
                                       &= [m]_{pk_1}\\
\end{align}$

that is, a fresh encryption of $m$ under the public key $pk_1$.

Note that this $pk_1$ may be a new public key, and in this case we will need a new secret key $sk_1$ to decrypt $[m]_{pk_1}$, or it can be equal to the original public key $pk$, and in this case we are supposing circular security...


Understanding the signature and hashing algorithms in TLS connection debug output I have an application using TLSv1.2 for communication. I use the option -Djavax.net.debug=all

Cipher Suites: [TLS_DHE_DSS_WITH_AES_128_CBC_SHA]
Compression Methods:  { 0 }
Extension signature_algorithms, signature_algorithms: SHA512withECDSA,SHA512withRSA, SHA384withECDSA, SHA384withRSA, SHA1withECDSA, SHA1withRSA, SHA1withDSA, MD5withRSA
Extension renegotiation_info, renegotiated_connection: <empty>
***
[read] MD5 and SHA1 hashes:  len = 74

I do not quite understand this output.

The client sends the cipher suites it wants to use, and the signature algorithms extensions correspond to that cipher suite?
I also do not understand the [read] MD5 and SHA1 hashes:  len = 74 why is the length of the message equal to 74 ?

Although you don't say so, this appears to be a server-side log; your 'application' is accepting a connection from something else which is the client.

Yes, the client sends the list of ciphersuites it supports and is willing to use in ClientHello; this is usually more than one (often 10 to 20 and sometimes over 50) but it can be one as in your example. However offering only suite(s) using DHE-DSS requires the server to have a DSS (aka DSA) certificate, which is rare on the public Internet, although it may be more common in intranets (especially in the US government). See rfc 5246 section 7.4.1.2 which is not materially changed in this area from earlier versions. Each ciphersuite that uses certificate authentication (not anonymous or pure PSK,SRP,Kerberos) defines the type of publickey in the server (EE) certificate, and thus the 'raw' signature algorithm (except for plain-RSA which doesn't sign at all) but not the associated hash.

In TLS1.2 only, the client MAY include the signature_algorithms extension indicating what types of signatures it supports verifying. If used, this constrains both the signature done by the server on ServerKeyExchange if ephemeral (and DHE-DSS is), and the signatures on the certificates in the server's chain (except the root/anchor if present, since verify it is meaningless). If not used in TLS1.2, the server assumes the signature type implied by the ciphersuite, and SHA1; see section 7.1.4.1.
Also if used, the rare static (EC)DH ciphersuites which formerly constrained the second (CA) certificate key type no longer do so; see section 7.4.2.

Earlier versions of TLS did not have signature_algorithms; the server's signature on ServerKX always used a nonstandard combination of SHA1+MD5 for RSA and SHA1 for DSA and ECDSA, and the certificate signatures were not specifically constrained but prior to 2015 in practice almost always used SHA1 or MD5. MD5 is now considered broken for certificate signatures and prohibited by nearly all reliers (browsers and clients). The standard for DSA, FIPS 186, did not even allow it to use any hash other than SHA1 until 2009, and it took some time after that for most implementations to follow suit.

For completeness, if client authentication is used in TLS 1.2, the client signature in CertVerify if ephemeral, and certificate signatures, are constrained by a similar field supported_signature_algorithms (required, not extension) in CertificateRequest, and also by the certificate (and key) chosen which is constrained by the certificate_types field; see section 7.4.4. In earlier versions only certificate_types was present, and the CertVerify signature used the default hashes like ServerKX while the certificate signatures in practice used SHA1 or MD5.

All versions of TLS (back to 1.0) also allow the client to send a supported_curves extension identifying which elliptic curves it supports. If present and an ECDH[E] ciphersuite is negotiated (which can only occur if the client offers it/them) the server must use an ECDH key (point) on a curve on that list; if present and ECDHE-ECDSA keyexchange is negotiated it must use a certificate for (and thus sign ServerKX with) a key on a curve in that list; if present and any ECDSA-signed certificate(s) are used they must use curve(s) on that list. In practice the supported_curves list is often the two formerly-NSA-SuiteB curves, P256 and P384, sometimes extended to add P521.

Aren't you glad you asked :-?


The 9 lives of Bleichenbacher's CAT, it puts another scratch again Bleichenbacher demonstrated a padding oracle attack against RSA implementations that follow the PKCS #1 v1.5. Through the years, there are various mitigation techniques developed as OAEP and limiting the number of query execution over a period of time. OAEP has been proven secure in the random oracle model.

In November 2018, Ronen et. al demonstrated in The 9 Lives of Bleichenbacher’s CAT: New Cache ATtacks on TLS Implementations that Bleichenbacher is still applicable.

How does the new attack work at top level?
Which TLS implementations are affected?
How one can mitigate from the attack?

How does the new attack work at top level?

In short

They used BEAST-like Man in the Browser attack by using Cache-like attacks to perform a downgrade attack against any TLS connection to a vulnerable server. With this, they showed the feasibility of using  Cache-like attacks.

More detailed

Even over the years, numerous mitigation techniques are deployed against the padding oracle attacks, they showed that some implementations are still vulnerable to various microarchitectural side channels. They target PKCS #1 v1.5 implementations that leak information via microarchitectural side channels.

Their attacker requires 3 capabilities:

Side channel capability: attacker must be able to execute code on the victim machine to mount microarchitectural side channel attack. They used Flush+Reload attack.
Privileged Network Position Capability: The attacker must be in the man-in-the middle position so that padding oracle attack with the private key can be exploited. The attacker downgrades the communication to TLS 1.2 RSA key exchange with Jager et. al.'s attack and used BEAST method.
Decryption Capability: The attacker needs an ability to start decryption of ciphertext chosen by him on the target system. They utilized Bleichenbacher and Manger’s Attack attack.

A concrete scenario of the attack:

A physical device shared between a TLS server and the attacker's virtual machine. This requires a determined adversary.
Second and third can be achieved by the controlling a node between the server and client

Note: Manger’s Attack that requires $\log_2(N)$ perfect Oracle queries. Bleichenbacher's attack requires millions of Oracle calls but can tolerate false negatives. They mounted an improved Manger’s Attack's attack with only 6144 queries due to an error.

Although the timeout of the browser limits the attack, they were able to parallelize the attack by using TLS servers that share the same public key certificate.

  Which TLS implementations are affected?

They tested the following implementations:

OpenSSL
Amazon s2n
MbedTLS
Apple CoreTLS
Mozilla NSS
WolfSSL
GnuTLS
BearSSL
BoringSSL

All, except the BearSSL and BoringSSL are affected by their attack.

  How one can mitigate from the attack?

Keep the system up-to-date: don't support different versions.
The backward compatibility is the main issue of this attack. TLS 1.3 security doesn't help you if your server can be downgraded to an earlier version.
Deprecate the RSA key-exchange.
Certificate Separation: Don't use the same key for signing and RSA-key exchange.
Constant-Time Code and Safe API as in BearSLL and BoringSSL API.
Using Large RSA Keys. The attack requires $\approx \log N$ oracle calls. Use larger keys $>2048$-bits to make the attack less practical.
Reduce the TLS Handshake Timeouts in order to make MitM attack harder.
Use BearSSL or BoringSSL

Note: The 30-second timeout in Firefox can be extended see Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice. by Adrian et. al.

Note 2: There is a related question in SecuirtySO about effected cipher suites.


Can I use a key twice if the message is longer than the key in one-time pad? I have a key for a one-time pad. Its length is 512, and I have a message to encrypt whose length is 600. Can I reuse the first 88 chars of the key to encrypt the end of the message?

The key is still random, so it should be still secure, right? If it isn't secure, why not?

Re-using the key of a one time pad in a cycle makes your cipher a Vigenère cipher - it is no longer a one time pad.

This scheme is weak for lots of reasons. The easiest example is with known plaintext.   Let's pretend your scheme is used to encrypt packet data.  Chances are, the first 20 bytes are known or easy to guess packet header bytes so we have:

$
\text{KnownBytes} \oplus k_{1-20} \mathbin\Vert \text{Something} \oplus k_{21-512} \mathbin\Vert \text{Bytes1} \oplus k_{1-20} \mathbin\Vert \text{Bytes2} \oplus k_{21-88}
$

where $k$ is the key

Given this, we can recover the value $\text{Bytes1}$ simply by $\text{KnownBytes} \oplus k_{1-20} \oplus \text{Bytes1} \oplus k_{1-20} = \text{KnownBytes} \oplus \text{Bytes1}$.  Since you know $\text{KnownBytes}$ you can then compute $\text{Bytes1}$.

It gets worse. You've also reused key bytes 21 through 88.  Just because the attacker doesn't know the value of $\text{Bytes2}$ or the first few bytes of $\text{Something}$ doesn't make it secure.  The two ciphertexts can be xored to remove the key and yield the xor of the underlying plaintext.


Most Compact Secure Post-Quantum Signatures and Public Keys? Which post-quantum public key and signature system includes the most compact reusable keypairs?  E.g. a private key which produces practically unlimited signatures without losing the security provided initially like RSA as opposed to something like hash-based Merkle tree driven signatures with a limited number of uses?

First of all, you have to say bye to the assumption that you get something like RSA or even ECDSA. Sizes for post-quantum candidates are larger than for classical schemes. Period. There exist schemes with small public keys or signatures but never both. The point is that you can often shift information around between public key and signature but the sum remains the same or gets even worse.

Generally, you got three areas that you can pick from: Hash-based, lattice-based, or multi-variate signatures. Code-based and isogeny-based do not really have practical proposals, yet. Each of these areas has its advantages and disadvantages.

Hash-based gives you the most reliable security guarantees, small public keys and moderate size signatures. For small, fast signatures you require to maintain a state (XMSS / LM-HSS), for stateless schemes (SPHINCS, SPHINCS+, Gravity-SPHINCS) signatures get to the order of 10th of kilobytes.

Lattice-based crypto currently provides you with the best sizes. If the current parameters turn out to be secure you can get away with 2.5 kilobyte signatures and 1.5 kilobyte public keys (Dilithium). However, the cryptanalysis of lattice problems is still on the move. It would not be totally surprising if someone finds an algorithm that is an order of magnitude faster than current attacks (this does not mean that the schemes would be broken but that parameters would have to be adjusted).

Finally, for MQ or multivariate signatures you got two choices: You can go with schemes like UOV or Rainbow (careful: patents) which offer extremely  short signatures but somewhat large public keys (I do not know exact numbers  as all I found are numbers for classical attacks and 80bit security...). If you further add cyclic structure to the keys, public key sizes go down. However, these constructions are heuristic and we only know that they were not yet broken with known attacks. Especially, their security is not only linked to the MQ-problem but also to far less understood problems like IP and MinRank. Alternatively, you can go with something like MQDSS which has a security reduction from MQ. However, then you are at slightly larger sizes than SPHINCS.


Can I use the cipher text ouput of only one DES rotation as plaintext to check validity? I have made a python code for one DES rotation. Can I use the resulting cipher text as a plain text for the same rotation with the same key? I think the answer is no, I can't do so. But I need to be sure, an explanation will be very helpful.

Yes, you can, but it's insecure. DES has a different key schedule for each round to avoid linearity and meet-in-the-middle attacks. Also you reduce the strenght of your cipher since not all encryption round embed the whole key. Be aware that you need to swap left part and right part of your data material after each round otherwise it's going to be terribly insecure.


AES GCM symmetric encryption of data at rest in c#, ciphertext much longer than plaintext I've written encryption/decryption routines using AES GCM. Code can be found here.

I recently realized that the cipher text is longer than I believe it should be. It should add the tag and IV onto the encrypted plaintext, but the result is still longer than it should be.

Here is the portion of the code doing the encrypting

    using (MemoryStream ms = new MemoryStream())
            {
                using (IAuthenticatedCryptoTransform encryptor = aes.CreateAuthenticatedEncryptor())
                {
                    using (CryptoStream cs = new CryptoStream(ms, encryptor, CryptoStreamMode.Write))

                    {
                        // Write through and retrieve encrypted data.
                        cs.Write(message, 0, message.Length);
                        cs.FlushFinalBlock();
                        byte[] cipherText = ms.ToArray();

                        // Retrieve tag and create array to hold encrypted data.
                        byte[] authenticationTag = encryptor.GetTag();
                        byte[] encrypted = new byte[cipherText.Length + aes.IV.Length + authenticationTag.Length];

                        // Set needed data in byte array.
                        aes.IV.CopyTo(encrypted, 0);
                        authenticationTag.CopyTo(encrypted, IV_LENGTH);
                        cipherText.CopyTo(encrypted, IV_LENGTH + TAG_LENGTH);

                        // Store encrypted value in base 64.
                        return Convert.ToBase64String(encrypted);
                     }
                 }
             }

Here are two examples of the encryption:

plaintext: example

ciphertext: XtmTBIqKxKdYKWH2zXRUp8jN6etGNUiTyffAFZYV3KB2WVU=

plaintext: much longer example, blah blah blah blah blah

ciphertext: H17hnG4CSmZQ0UeEcY6wirtjW1il+dw7JHqXwWm908Tvb8/+q0E1HerN0chbuUbhL0jLOs8HIpp7ypQQ/ LTacnWW22CyiwAuiA==

The IV is 12 bytes. And I believe the authentication tag is 16 bytes. Why is the cipher text coming out so much longer than expected and how should I fix this issue?
Thank you.

If you go through the math, it appears that exactly the expected amount of ciphertext expansion is happening.  Here's what's happening:

The GCM takes the plaintext as a byte string of size N, and generates a ciphertext which is a byte string of size N+28, where 12 of the 28 is the nonce, and the other 16 is the authentication tag.
Then, that octet string undergoes a base-64 encoding, which converts 3 bytes into 4 printable characters; this gives an average ciphertext expansion of a factor of 4/3.

In the first case, you had a plaintext of 7 bytes; after encryption, that gives you a ciphertext of 35 bytes; the base-64 encoding of these 35 bytes would be expected to be 47 bytes long, which is exactly what you see.

In the second case, you had a plaintext of 46 bytes (assuming there's a trailing space to the string you gave); after encryption, that gives you a ciphertext of 74 bytes; the base-64 encoding is then 99 bytes, which is exactly what you see.

Now, you ask how you should fix this issue.  Well, the transform is working as designed; what is the issue?  If the issue was that you were concerned that something wasn't working properly, well, everything appears to be correct.  If the issue was that the ciphertext was too long for your application, well, you'd need to consider how to trim it.  Here are some easy ways:

Do you really need the output to be printable?  Well, I see you put the 'database' tag on the question; are you encrypting a database field?  If so, can the database store arbitrary bytes, or is it restricted only to printable strings?  If it can store arbitrary bytes, then you can get rid of a good part of the overhead simply by not base-64 encoding the text.  If you do, well, if you're desperate, there are some more aggressive encoding methods (which use more characters in their outputs); going to one of those would save you some small amount.


Question about using BN_rand() I am working on a project and I'm noticing a peculiar behavior that I was hoping someone could tell me if it is correct or not.

I have a program that is trying to generate some random numbers using BN_rand().  Snippet of code follows:

BIGNUM *test = NULL;
unsigned char buffer[2048];
int fd = open("/dev/urandom", O_RDWR);
read(fd, buffer, 2048);
close(fd);

test = BN_new();
if (RAND_status() != 1)
    goto error3;

RAND_seed(buffer, 2048);

if (!BN_rand(test,2048,0,1))
    goto error3;

do_bn_print_name(stdout, "test", test);

Every time I run this program though, it gives me the same random number.  I was expecting the number to be changing after every run.  Am I doing this right or is this expected behavior?

Thanks for any assistance!

I couldn't reproduce the issue since you used some custom functions, but this works for me:

#include <openssl/bn.h>
#include <openssl/rand.h>
#include <stdio.h>

int main(void) {
    BIGNUM *test = NULL;
    unsigned char buffer[2048];
    FILE* fd = fopen("/dev/urandom", "r");
    fread(buffer, 1, 2048, fd);
    fclose(fd);

    test = BN_new();
    if (RAND_status() != 1)
        printf("Not enough entropy\n");

    RAND_seed(buffer, 2048);

    if (!BN_rand(test,2048,0,1))
        printf("Not enough entropy\n");

    printf("%s", BN_bn2dec(test));
    return 0;
}


Is secure remote snap possible? Scenario:

We have a central server $S$.
We have a number of peripheral servers $P_i$
We have some individuals $U_j$
A given individual may be "known" to one or more peripheral servers. Each peripheral server generates unique IDs for the individuals it knows and stores a map $f_i: U_j \to \textrm{ID}$ and the corresponding inverse $f_i^{-1}$
A peripheral server may share its IDs but may never share the identities of the individuals it knows.
The peripheral servers can communicate securely with $S$.
The peripheral servers regularly transmit to $S$ a map from IDs to some data.

Problem:

$S$ wants to determine whether $P_1$'s ID $a$ corresponds to the same individual $u$ as $P_2$'s ID $b$ without ever knowing the value of $u$. If so, it will merge the data from the different peripheral servers. (Details of the merge method are out of scope). Is this possible?

In essence this is "mental snap", or perhaps zero-knowledge set intersection.

Rejected approach:

The domain of individuals is too small to simply send hashes to $S$ and compare the hashes: this would allow identifying the individuals by brute force.

Yup, should be possible.  Look at multiparty secure computation protocols.

In particular, you might want to look at secure protocols for private set intersection.  $P_1$ and $P_2$ can use such a protocol to find the individuals that are in the intersection of a set known to $P_1$ and a set known to $P_2$.  Then, they can let $S$ know whether there is any intersection and what the correspondence between IDs is

Specifically: $P_1$ has a set of individuals ($f_1^{-1}(a)$), and $P_2$ has another set ($f_2^{-1}(b)$); now a private set intersection protocol lets us check whether these sets have any elements in common, without revealing anything else about the sets.  In such a protocol, the set of individuals never leaves $P_1$ or $P_2$, but we still have a way to learn whether $P_1$'s set $P_1$ has any overlap with $P_2$'s set.  The details are, well, detailed, but if you are interested, look up any reference on private set intersection.

This approach scales beyond pairwise comparison of individual IDs; if the server has a set of IDs on $P_1$ and a set of IDs on $P_2$, you can use this approach to find whether there is any overlap between these sets and if so, what the correspondence is between the IDs.


Security level of DSA when $q$ is a 224 bit prime? What is the security level of DSA algorithm when $q$ is a 224 bit prime?
Is it always a simple rule that the security level is the bit length of $q$ divided by two ?

What is the security level of DSA algorithm when q is a 224 bit prime?

About 112-bit, at most. More precisely, there's an attack recovering the private key from the public key, by solving a Discrete Logarithm Problem, costing roughly $2^{113}$ modular multiplications, and little else: the attack can be efficiently distributed and requires little memory. See Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999.

Is it always a simple rule that the security level is the bit length of $q$ divided by two ?

No. That rule applies unless there's another weakness:

The public prime $p$ is too small (or of a special form facilitating attack). As a rule of thumb, size (and requirement to not be too close to an exact power) are comparable to that of $n$ in RSA for the desired security level, in order to resist index calculus and GNFS variants. That would make about 2048-bit a minimum. See KeyLength.com for more precise advice on size.
The random generator used for signing has an exploitable weakness.
The private key leaks, e.g. by power analysis or timing attack.


Constants Differ in SHA1 implementation I am trying to understand why the constants differ in this SHA1 implementation:

https://code.google.com/p/crypto-js/source/browse/tags/3.1.2/src/sha1.js

this._hash = new WordArray.init([
    0x67452301, 0xefcdab89,
    0x98badcfe, 0x10325476,
    0xc3d2e1f0
]);

https://code.google.com/p/google-authenticator/source/browse/libpam/totp.html

V = 0x67452301,
W = 0x88888888,
Y = 271733878,
X = Y ^ W,
Z = 0xC3D2E1F0;

You'll notice the constants in [1] and [2] are different. Is this the result of an optimization, or is there another reason why those constants are different?

They are actually the same, because you missed W^=V in the second link. When you work out the XORs, you arrive at the same constants.


What key exchange protocols give Forward-Secrecy resisting future progress? I (wrongly) understood what I've been told as meaning DHE in TLS, PFS in IPSec do not provide Forward-Secrecy; and I'm told that common forward-secure key exchange protocols are restricted to establishment of an Asymmetric key, or are otherwise vulnerable when the security of some security assumption of an asymmetric cryptosystem collapses.

I ask which (preferably well-studied) key exchange protocols (if any, which I have now come to doubt) provide the following enhanced form of Forward Secrecy, for exchange of a wide ephemeral symmetric key, by mean of some asymmetric private/public key pairs; in the sense of insuring that an intercept made at a date when the assumption(s) of hardness underlying the asymmetric protocol(s) used holds, can't help recovering the ephemeral symmetric key established, even after said assumption(s) of hardness no longer holds.

Note: I now realize that collapse of assumption of hardness of all asymmetric cryptosystems is a stronger assumption than compromise of the long term private asymmetric keys, which is the standard assumption in forward-secrecy.

To make key exchange protocols (providing perfect forward-secrecy) robust against quantum computers they need to rely on assumptions that are not susceptible to quantum attacks (post-quantum crypto) like hash based, lattice based or multivariate-quadratic-equations based.

Clearly, quantum key distribution is a candidate for key exchange with all the associated problems.

pqcrypto.org provides a quite updated reference to post-quantum research. It looks like the key exchange issue and in particular perfect forward-secrecy has not really seen much research so far.

At least the paper Smooth projective hashing and password-based authenticated key exchange from lattices provides a construction of an password-based authenticated key exchange for the post-quantum world.

Subsequently, I comment on the below cited part of the question and I only speak of protocols where we use hardness assumptions which do not longer hold in the advent of a quantum computer below.

  ...insuring that an intercept made at a date when the assumption of hardness underlying the asymmetric protocol holds, can't help recovering the ephemeral symmetric key established even after said assumption of hardness no longer holds.

We speak here of key-exchange/key-agreement protocols which allow to parties to compute a common secret over some
public channel where this common ephemeral secret may then be used to compute some common symmetric session key.

Perfect forward-secrecy in the key-exchange context typically means that both parties have some long term-key and on every session they
run some key-agreement to compute a common session key, but the compromise of long-term keys does not compromise the
secrecy of any past sessions.

In order to compute a session key there happens a key-agreement protocol (typically, the long term-keys will
be used to sign the respective ephemeral information of the key-agreement sent by the respective party), where the ephemeral information exchanged to compute the common
key do not deterministically depend on the long-term keys if perfect forward secrecy is provided. Anyways, there always
simply happens a key-agreement irrespective of the perfect
forward-secrecy feature or not.

So if the security of the key-agreement is based on some hardness assumptions $P_1,\ldots,P_n$, it does not make a difference if you consider
key-agreement protocols that provide perfect forward-secrecy or not. If the $P_i$'s do no longer hold, e.g., if we
have a fancy quantum computer, then the transcript of any key-agreement will allow you to recover the respective session key.

Perfect forward-secrecy is concerned with compromise of the long-term secrets (such as private keys for static DH keys), but not
with breaking the hardness assumptions when given the transcript of a key-agreement (clearly, because the key-agreement
only makes sense if the hardness assumption holds).


RSA: Is it possible to recover the plaintext given that we have the ciphertext and the public key? The $N$ and ciphertext are huge number that is more than 600 digits long.

I'm trying to find the prime factors of $N$ in order to get $p$ and $q$. Using $p$ and $q$ I can get $\phi(n)$. And using $\phi(n)$ and the public key I would be able to calculate the private key.

So, my question is if it is possible to recover the plaintext given that we have ciphertext and the public key?

If so, is it computationally feasible?

It might be feasible, or not.

If "digits" had been binary digits or bits, the answer would have been yes. Anything about 600-bit can be factored by GNFS. The public record is for a 768-bit RSA modulus, factored in 2009. 600-bit is within reach of CADO-NFS and Msieve. That's even packaged into factoring as a service for semi-deep-pocketed script kiddies.

It could be that $N$ was poorly chosen and can be factored much more easily than by GNFS. Since the generation algorithm is unspecified, we can't tell. Poor RSA key generators have happened (see e.g. SmartFacts, ROCA, and predictable SSH hosts keys on way too many platforms).

It could also be that the encryption system used is plaintext RSA, where the ciphertext is $C=M^e\bmod N$ with $M$ the plaintext. This contrasts secure RSA, where $M$ is obtained from plaintext and randomness using a padding scheme such as OAEP. If $M$ is the plaintext (or a known deterministic function of the plaintext), some attacks much easier than factoring the modulus might be possible:

if $M$ is in a known small set (names on the class roll, 16-digit credit-card number), it is possible to enumerate possible $M$, perform encryption, and check against the ciphertext.
if $M=U\cdot V$ with $U<2^u$, $V<2^v$, $u\le v$ (which is likely when $M\ll2^{u+v}$ ) then there's a Meet-in-the-Midle attack with cost $O(2^v)$ time and $O(2^u)$ memory.
if $M<\sqrt[e]N$ we have the $e^\text{th}$ root attack (which can be extended to slightly larger $M$).


ECDSA signing process I am trying to learn how ECDSA works. I do not have a background in maths, but have been following a guide which has built me up from finite fields, elliptic curves.
I am unable to figure out how a signature is generated , a description of it is here.

To state what i understand.

e = private key
G = generator point
P = Public key
k = Ephemeral key

The public key is a point on the curve computed as

  e.G = P

The signing algorithm starts by taking a random target R

  kG = R

The guide straight up represents R as follows (where u/v are chosen by user):

  uG + vP = kG

I sort of fail to understand how or why this relation holds true. It seems to be starting with a random point on the curve uG and it adds a scalar multiple of the public key (which could be further expressed v.e.G)

Pick a coordinate field $\mathbb F_p$, such as $p = 2^{256} - 2^{32} - 977$.  Pick an elliptic curve over $\mathbb F_p$ of the form $y^2 = x^3 + a x + b$, such as $a = 0$ and $b = 7$.  (This is the curve secp256k1 used in Bitcoin.)  Pick a standard base point $G$ of prime order $\ell$, so that $\ell$ is the smallest positive integer such that $$[\ell]G = \underbrace{G + \cdots + G}_{\text{$\ell$ times}} = \mathcal O.$$  Here $\mathcal O$ is the ‘point at infinity’, or the identity of the group.

An ECDSA public key is a point $P$ on the curve with coordinates $(x(P), y(P))$.  An ECDSA signature on a message $m$ under $P$, is a pair $(r, s)$ of integers with $1 < r, s < \ell$ such that the verification equation $$r \equiv f\bigr([H(m) \, s^{-1}]G + [r s^{-1}]A\bigr) \pmod \ell$$ holds, where $f(A) = x(A) \bmod \ell$ is a kind of arbitrary function mapping the $x$ coordinate field $\mathbb F_p$ to the scalar ring $\mathbb Z/\ell\mathbb Z$ (which is a rather weird thing to do, but such is life).

The signer knows the secret scalar $e$ such that $P = [e]G$, in terms of which this equation is $$r = f\bigl([H(m)\,s^{-1}]G + [r s^{-1} e]G\bigr) = f\bigl([H(m) \, s^{-1} + r s^{-1} e]G\bigr),$$ which means the signer can choose a per-signature secret $k$ uniformly at random, derive $r = f([k]G)$, and then solve the scalar equation $$k \equiv H(m)\,s^{-1} + r s^{-1} e \pmod \ell$$ for $s$, by computing $$s := [H(m) \, k^{-1} + r k^{-1} e] \bmod \ell.$$


What PRG expansion factors are safe? I'm trying to better understand the "cost" of randomness usage/generation in practice. I understand that generally, some (small) amount of "true" randomness is generated, and then a CSPRNG is applied to expand this out to a larger amount of pseudo-randomness.

I'm curious as to precisely how these "small" and "large" amounts are related in practice.
If I want $k$ pseudo-random bits, that an adversary can't distinguish from random with less than $2^{\lambda}$ time, how many truly random bits do I need to seed my PRG with?

I understand this may depend on the particular CSPRNG I use. If it does, how does one find out this conversion factor for a particular CSPRNG.

In practical terms, you can take 32 bytes, and safely expand them into up to $2^{128}\cdot64$ bytes using ChaCha, which is more bytes than you can actually expand anything into even if you could enlist the help of all the queen's horses and all the queen's men even if they weren't busy putting Humpty together again.

Some practical PRGs are more limited.  For example, by the birthday paradox, the distinguishing advantage against AES-256 grows with $q^2\!/2^{128}$ where $q$ is the number of blocks of output, so it falls apart around $2^{64}$ blocks and you should really limit yourself to well below that many, say $2^{32}$ under a single key in order to keep the distinguishing advantage below $1/2^{64}$.  This is because AES is a permutation, and a permutation of 128-bit strings at that; in contrast, ChaCha is a function into 512-bit strings.


Perfect Secrecy -> One Time Semantic Security -> Secure PRG I think I have some sense of what Perfect Security means, and even Semantic Security, but I am struggling with randomness, so I'm going to ask a question about CSPRG's (Cryptographically Secure PRG's) by going through the first two.

The basic idea that leads to the notion of Perfect Security, as I understand it, is that given a ciphertext $c$, and a message $m$, there are a certain number of keys that might turn $m$ into $c$.  If someone shows me $c,$ and tells me that keys are chosen uniformly in some space, then a message $m$ that has many keys that will encrypt it into $c$ is far more likely to be the original than a message $m'$ that has few keys that will turn it into $c$.  In this way, some probabilistic information might be leaked about the nature of the original message.  Perfect secrecy rules out this leak by saying that given a $c$, the number of keys must always be the same regardless of $m$.

One time "Semantic Security" codifies this as a game.  I give you $m$ and $m'$, you give me $c$, and I try to guess whether it's more likely that you encrypted $m$ or $m'$.  If lots of keys would change $m$ into $c$, but only few would change it into $m'$, then I have an advantage in my guess of which one you encrypted.

So now let's suppose we have a function $G$ that takes a seed and gives me a key, and I want to use this as a stream cypher, calculating $c = G(s) \oplus m$.  Let's play the semantic security game with $m$, $m'$.  Once given $c$, the attacker now knows that the key was either $m \oplus c$ or $m' \oplus c$.  So the question the attacker will ask himself is:

Are there more seeds $s$, such that $G(s) = m \oplus c$?  Or, $G(s) = m' \oplus c$?

If they can answer this question, then they might be able to get an advantage.  The question I want to answer now is: what characteristics does $G$ have to have so that the attacker can not get an advantage?

Well, suppose it was $m$ that was encrypted, but the attacker doesn't yet know this.  Then:

$$s = G^{-1}(m \oplus c)$$

At the same time, the attacker is going to be inspecting $G^{-1}(m' \oplus c)$ to see if it's possible that this could be a seed.  Since the key space is the message space is the ciphertext space, and all are much larger than the seed space, $m' \oplus c$ is going to range over things that are not mapped to by $G$.  So there are choices of $m'$, even a lot of choices, for which $G^{-1}(m' \oplus c) = \emptyset$.  Therefore, we can not hope to find, as we did in the case of perfect security, that the number of seeds is invariant as we change the message.

The only other option I can see is that we must hope that there is no effective means of inverting the function $G$.  If there is, then we're lost, as the attacker has an effective way of finding out whether they have a seed or not; and for a lot of choices of $m'$ s/he won't.  That will give the attacker a very large advantage.

So, my question is how we relate this requirement for the lack of an effective inverse, into the usual definition of a Cryptographically Secure PRG? And indeed, what is the definition of a CSPRG?  Dan Boneh describes it as a kind of "computational indistiguishability" of two measures (the uniform measure on the key space and the push forward of the uniform measure on the seed space).  And he claims that by Yao it's equivalent to a notion of "unpredictability".  Could someone hash these three different things together for me?  Finally, in this question, D.W. mentions an "asymptotic" (and not very good) definition of a PRG vs. a "concrete security" definition.  Could he, or someone, clarify what these are?

And also, does anyone have the reference to Yao?

First, on the difference between perfect security and semantic security. Both definitions concern confidentiality, so let us first define what confidentiality means.

Note first that an adversary as some a priori knowledge of the message. We can capture that by e.g. having the adversary choose two messages and then flipping a fair coin to decide which one to encrypt.

Next, note that the adversary wants to learn something from the ciphertext, his a posteriori knowledge of the message. We capture that by having the adversary guess which message was encrypted.

If the adversary cannot guess correctly which message was encrypted with probability significantly different from $1/2$, then we have confidentiality.

That was the definition of confidentiality.

(More complex definitions are possible using a probability space and a function from the message space to 0 and 1, but we ignore that since it isn't important for the present discussion.)

Perfect security is about confidentiality against arbitrary adversaries. Now we can prove many theorems about perfect security, and one of them talks about the number of keys taking a given message to a given ciphertext (as you describe).

Semantic security is about confidentiality against computationally bounded adversaries. Unlike for perfect security, there aren't so many theorems we can prove about semantic security, which means that we know less about what is required to achieve semantic security.

So the difference between perfect and semantic security is just about which adversaries we consider, nothing else. The two notions are often presented in a superficially different way, however, making it look like they are different in other respects.

Regarding computationally bounded adversaries. The traditional approach (based on computational complexity theory) is to speak about families of cryptosystems with increasing key lengths, and let the adversary's effort be bounded by some polynomial in the key length. The concrete security approach says that we have a concrete cryptosystem with a fixed key length, and let the adversary's effort be bounded by a fixed number of computational steps (probably relative to some fixed universal Turing machine or something, there are some foundational problems here).

Second, on pseudo-random generators. A pseudo-random generator is a function that "expands" a short string into a long string. As above, we define first a security goal similar to confidentiality, and then we can consider different adversaries against that goal.

A short string is sampled and expanded into a long string. A second long string is sampled. The adversary gets either the first or the second long string, decided by a fair coin flip.

If the adversary cannot guess correctly which of the two strings he got with probability significantly different from $1/2$, then we have security.

(This is equivalent to Boneh's notion of indistinguishable probability distributions.)

Perfect security considers arbitrary adversaries. Using the arguments you outline in your question, it is fairly easy to show that perfect security for a pseudo-random generator is impossible.

Computational security considers computationally bounded adversaries. Obviously, here there's no proof of impossibility. Instead, we have good reason to believe that this is possible to achieve for useful values of "computationally bounded".

Since perfect security is impossible, there's no point in going on about "computational" all the time, so we usually ignore it and talk about "secure pseudo-random generators". Since pseudo-random generators are used in many fields of science, we often add "cryptographically" in front to say clearly that we are talking about cryptography here, and not (say) statistics.

A pseudo-random generator is a function $G$ from the set of short strings to the set of long strings. If you can invert the function (or find preimages if it is not injective), then the generator is obviously not secure, as you observe.

Third, on unpredictability. It is clear that if I sample a long string and show you a prefix, then you cannot say anything about the remainder of the string, specifically not about the next symbol.

Suppose that if you are given a prefix of a pseudo-random generator's output, you can predict the next symbol of the output. In the setting described above, where you either get the generator's output or a random string, you can recognize the output of the pseudo-random generator.

Here's how you recognize the output: You get a long string. Momentarily, you forget all but a prefix of the string and pretend that it is a prefix of something output by the generator (which it may be). Now you use your ability to predict the next symbol. Then you remember the entire long string, specifically the next symbol. If you predicted it correctly, then probably the long string was output by the generator. If your prediction was incorrect, then probably the long string was random.

Since you can recognize the generator's output, the generator is not secure. It follows that if you have a secure generator, it is unpredictable. Which is nice.

(The other direction is more complicated. Basically, the idea is that if given a prefix, you cannot say anything about what the next symbol will be, then you cannot distinguish the generator's output from the generator's output with the final symbol randomized. But you cannot distinguish the latter from the generator's output with the final two symbols randomized. Etc. Since indistinguishability is transitive, it follows that you cannot distinguish the generator's output from random strings.)


How obvious is it to decrypt numerics encrypted with a reused one time pad? For instance say you encrypt text using the one time pad and you end up with some scrambled text that appears illegible.  If you reused the key for multiple times for enough text, someone could potentially crack the message using something like crib-dragging. The hacker tries and tries until eventually comes up with a message that has meaning and is no longer scrambled.

However say you use the one time pad technique to encrypt numeric values like dates, time, or just some numbers within a range like say numbers from 00000 - 10000  AND reuse the same key over and over.

For example in the case of dates like a month you would create a key that consists of a random number between 1 and 12, so that when you add the key value to actual month value and mod by 12 (and add 1) you end with a real month value different from the initial.  Then you use the same method (different range of values) with the days, or years, always ensuring you end up with a real date value in the end.

First is it even possible for someone to recognize that the result was encrypted? The values all appear to be legitimate, real, non-scrambled values, just as the originals were (only displaced in time)

If for some reason they figured out that the numeric values were encrypted, would they even be able to decrypt them to their original values?  How would they know that their efforts are resulting in the correct original value?

Yes, the same weaknesses apply. Text on computers is a bunch of numbers; a OTP encrypts a sequence of numbers modulo 2.


Does Hinek and Lam's Paper prove that Common Modulus Attacks is possible with non-coprime public exponents? We know that Common Modulus Attacks work with coprime public exponents $(e',s)$ such that $${e_1}s+{e_2}t=\gcd(e_1,e_2)=1$$
I am reading Hinek and Lam's Paper: Common Modulus Attacks on Small Private Exponent RSA and Some Fast Variants (in Practice). Got confused, it seems they proved that Common Modulus Attacks would work with non-coprime public exponents, with the condition of "Small Private Exponent RSA".
Is my understanding correct? Is there some example for this?

The first common modulus attack is described by G. J. Simmons

1983 A ‘weak’ privacy protocol using the RSA crypto algorithm

and if there is a common modulus and the public exponents are relatively prime (i.e. $\gcd(e_1,e_2)=1$) then recovering the message is easy ( no factoring).
As pointed in section 5 of your linked article;

Howgrave-Graham and Seifert’s small private exponent attack on common modulus RSA [1] improves upon Guo’s attack in several ways. In particular, the attack can be mounted with only two instances of RSA (although it gets stronger with more), the problems associated with relatively prime quantities are not a concern and, most importantly, the attack (even with only two instances) is much stronger.

So your understanding is correct.


Latin dance family in block cipher Is it secure to use Salsa20/ChaCha as the key schedule for a 512-bit block cipher using a public permutation in Even-Mansour construction?

If you define one round of your Even-Mansour cipher as: $$c \leftarrow P(\operatorname{Salsa20}(k, f(\text{nonce}, \text{round})) + m)$$

Where $P$ is your public fixed permutation, $f$ is some function that ensures the combination of nonce and round number don't lead to repeating nonces, and $\operatorname{Salsa20}$ is the Salsa20 stream cipher.

And assume that:

Salsa20 is a secure stream cipher
The Even-Mansour cipher uses one round
The permutation is the identity permutation

Then the proposed Even-Mansour cipher is secure. To see this, simply drop the permutation and round counter altogether and get $$c \leftarrow \operatorname{Salsa20}(k, nonce) + m$$

If $\operatorname{Salsa20}$ is assumed to be secure, then the above is secure.

The latter two assumptions of a single round with the identity permutation are the worst case scenario. More rounds and an alternative permutation should not make the design weaker.

However

This also demonstrates that there is little benefit to using more than one round and an additional permutation.

Note also that with more than one round, the $f$ function needs to be designed to ensure that the combination of nonce and round counter never leads to the generation of repeated key streams. It is conceivable that failure to do so could lead to an Even-Mansour cipher that is trivially broken despite Salsa20 being secure, e.g. a 2 round variant where rounds 1 and 2 result in the same key stream being generated, leaving the plaintext message unaltered.

If Salsa20 is secure, then there is no real benefit from embedding it inside of another encryption algorithm. The extra complexity could lead to something that is broken, despite Salsa20 being secure.