Security implications of the key padding in HMAC I just learned HMAC in class.
Keys are zero-padded in HMAC hashing function.
10 and 1 will be both transformed into the same final key (e.g. 1000).
Isn't that a problem?

Ordinarily, the keys for a MAC algorithm are assumed to have a fixed length.  (If they don't, e.g. if the "keys" are actually user-supplied passwords, then you should run them through a suitable KDF anyway.)  When HMAC is used that way, there is no problem, since the padding process cannot map two keys to the same output.

(If the input keys are longer than the hash input block length, HMAC specifies that they are to be hashed before padding.  In this case, two keys can end up getting hashed to the same value, but actually finding two such equivalent keys is as difficult as finding a collision for the hash function.  The hashing step does reduce the effective keyspace size of HMAC to the hash output length; that's only an issue insofar as it makes a brute force key recovery attack as easy as a single brute force MAC forgery.  But for normal applications of HMAC, the latter is already considered a break, and thus the hash output size should be chosen to make it infeasible.)

That said, precisely because of its flexibility and its strong security properties (PRF-ness), HMAC is not only used as a generic MAC, but also for other purposes such as, notably, as a component of password-based KDFs like PBKDF2.  In such uses, the key padding (and hashing) in HMAC could cause issues if one isn't careful:

For keys longer than the hash input block size, $k$ and $H(k)$ are equivalent HMAC keys.  This could be an issue e.g. in a carelessly designed application that used $H(k)$ as a key check value, and thereby revealed it to attackers.
Conceivably, a lazy application designer could be tempted to take advantage of HMAC's flexible key length and derive auxiliary keys from a master key simply by appending various suffixes to it.  In such a case, using two suffixes of different length (including, possibly, the empty suffix) that only differed by the longer one having one or more null bytes appended to it could potentially yield equivalent subkeys.
Similarly, when HMAC is used for password hashing (e.g. as part of PBKDF2), two passwords that only differ by appended null bytes would be equivalent.  Of course, people rarely use (or even allow) null bytes in passwords, and anyone who does is likely to run into bigger problems anyway (like the fact that many systems may store user input as a null-terminated string, effectively truncating it at the first null byte).  And even if someone did somehow end up using such an equivalent null-padded password, the security implications would be essentially the same as if they'd simply reused the original password.

In practice, all of these issues are easily avoidable simply by being aware of them and not doing silly things like using null bytes in passwords or in subkey suffixes.  The real problem with HMAC's key padding scheme is simply that it presents a subtle trap for careless cryptographers, and requires anyone analyzing HMAC-based schemes to be aware of its internal structure.  It would be nicer and simpler if we could just treat HMAC as an ideal black-box PRF, but alas, due to the possibility of equivalent keys, that's not quite the case.


Are SSL modes with forward secrecy vulnerable to the BEAST attack? From the original BEAST paper, it seems to me that you need the same session key when encrypting data, so you can check if the original plaintext block is the same as your chosen plaintext (which is impossible with different keys). However, in modes with PFS, the keys are different in each session, so doesn't this foil the BEAST attack as well?

I appear to be wrong somewhere, but I can't see where. Can someone enlighten me?

BEAST is not affected at all if the keys are derived with Perfect Forward Secrecy.  If you were to derive fresh keys quite frequently (that is, issue a Change Cipher Suite every couple of TCP segments), that would frustrate BEAST, however it wouldn't matter if the new ciphersuite used PFS or not.  In addition, there are cheaper ways to foil BEAST.

What PFS means for SSL is that, after we are done with the session keys, no one can rederive what they were, even if they have access to all the long term keys (e.g. the RSA private key, if that were involved).  The normal SSL ciphersuites do not provide this, as someone who has the recorded the negotiation and has the RSA private key can decrypt the premaster secret, and from there rederive all the keys.

However, with PFS, once we've derived the session keys, they are handled just like session keys from nonPFS ciphersuites; the keys are used to encrypt/decrypt traffic, and they aren't changed between TLS records (unless, of course, another Change Cipher Suite record is issued).

Hence, while this "no one can recover the session keys" property may be useful, it has nothing to do with BEAST.  BEAST does not attempt to rederive keys at all.  Instead, it tries to use the CBC-mode encryption as an Oracle (and then by injecting plaintexts that the attacker picks, confirms guesses on what earlier plaintext might have been).  It does care that the keys used to encrypt this latter data was the same as the keys used to encrypt the earlier plaintext; however it doesn't care how the joint keys were created.


Key Hierarchy and key Encryption If i have two 56-bit DES keys, and I use these two key to encrypt a 256-bit AES key. Like this $K_{AT}$ encrypts $K_{BT}$ and $K_{BT}$ encrypts $K$

What is the effective security of key $K$?

Is it $2 \times 56$ bits?

Can anyone help?

The security - assuming you can validate the correctness of $K$ - is 56 bits (not even counting any attacks on DES itself, assuming to test all keys). This is because you can brute force $K_{BT}$ without even looking at $K_{AT}$ in your particular scheme.

[EDIT] I'll explain: lets assume that the correctness of the AES key $K$ can be verified by looking at known plaintext / ciphertext pairs. Knowing $K_{BT}$ unlocks the key $K$, which can then be verified. Hence brute forcing $K_{BT}$ is enough to find the right $K$. And $K_{BT}$ has a security level of 56 bits. You can completely ignore $K_{AT}$, it doesn't offer any additional security at all. Minor note: this will cost you at least 5 decrypts (4 DES encrypts or decrypts for retrieving the AES key and one AES encrypt or decrypt to verify correctness).

2 key triple DES on the other hand would at least offer over 80 bit security. So this scheme is certainly not the best option available if you have 112 bits of entropy for your key.


Rationale for verification with cofactor $2^c$ in EdDSA? In EdDSA for more curves, it's described two options of signature verification

Verification, which checks $2^c\,S\,B\,=\,2^c\,R+2^c\,H(\underline R,\underline A,M)\,A$
Cofactorless verification, which checks $S\,B\,=\,R+H(\underline R,\underline A,M)\,A$

Cofactorless verification is more stringent: "any alleged signature that passes cofactorless verification will also pass verification", but "a signer using a secret key outside the normal signing procedure can create strings that pass verification without passing cofactorless verification".
So, what's the rationale for the first kind of verification, with cofactor $2^c$? If somewhat it's faster/simpler, why?

Update: after looking at this answer and it's references, I wonder if the only reason Verification¹ is defined is so that it holds the following
Proposition: If a set of signatures passed batch verification, then each signature passes Verification¹ with cryptographic certainty (including if signers are intentionally messing up or if adversaries modify signatures).
Is this proposition true? What's a proof? Why would not it hold if Verification was defined as Cofactorless verification?
Is there any other reason for Verification with cofactor? Like, a Fast Single-Signature Verification as in section 5 of Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang, High-Speed High-Security Signatures, in proceedings of CHES 2011)?

¹ Verification as defined above, that is with cofactor $2^c$.

It's flawed to imagine that "more stringent" is somehow stronger.  Actually ed25519-dalek's verify_strict method makes this mistake.
There are many plausible verification methods, which all define valid signature schemes based upon the same ed25519 keypairs.  You'll find them described in https://eprint.iacr.org/2020/1244 and https://hdevalence.ca/blog/2020-10-04-its-25519am
Almost none of those schemes agree perfectly with batched ed25519 signature verification however because batch verification randomly cancels out some cofactor tweaks.
If you employ ed25519 in a consensus protocol, like for accounts on a blockchain, then you'll want batched ed25519 verification that agrees perfectly with single ed25519 verification.  In such cases, you should use ZCash's ed25519 crate ed25519-zebra.  Afaik, all other ed25519 implementations exhibit variations between batched and single verification (as of march 2021).
I doubt TLS would adopt cofactor clearing verification, in part because cofactor-less verification runs slightly faster than cofactor clearing verification.  In fact, TLS could already batch verify ed25519 because one never has third parties check TLS handshakes in consensus protocols.  I suppose a CA could issue a certificate that worked only intermittently and only on some clients.


In RSA, why is it important to choose e so that it is coprime to φ(n)? When choosing the public exponent e, it is stressed that $e$ must be coprime to $\phi(n)$, i.e. $\gcd(\phi(n), e) = 1$.

I know that a common choice is to have $e = 3$ (which requires a good padding scheme) or $e=65537$, which is slower but safer.

I also know that for two primes $p,q$, we have $\phi(pq) = (p - 1) (q - 1)$

Now, let me give a (simple) example:

Say I choose $e = 3$, and two random primes $p = 5$ and $q = 13$.

I can now compute $\gcd(3, \phi(5 \cdot 13)) = 3$.

This reveals that $3$ and $\phi(n)$ are not coprime. I assume this could also happen for large values of $p$ and $q$, and likewise for another $e$. I therefore assume that the RSA algorithm must check that $\gcd(e, \phi(pq)) = 1$. But let's assume it doesn't.

How does RSA become vulnerable if $\gcd(e, \phi(pq)) \neq 1$?

It doesn't become vulnerable; instead, it becomes impossible to decrypt uniquely.

Let us take the example you give: $N=65$ and $e=3$.

Then, if we encrypt the plaintext $2$, we get $2^3 \bmod 65 = 8$.

However, if we encrypt the plaintext $57$, we get $57^3 \bmod 65 = 8$

Hence, if we get the ciphertext $8$, we have no way of determining whether that corresponds to the plaintext $2$ or $57$ (or $32$, for that matter); all three plaintexts would convert into that one ciphertext value.

Making sure $e$ and $\phi(N)$ are relatively prime ensures this doesn't happen.

BTW: when you generate an RSA key, common practice nowadays is to select $e$ first, and then when you select the primes $p$, $q$, you make sure that $p-1, q-1$ are relatively prime to $e$; this is equivalent to making sure that $e$ and $\phi(N)$ are relatively prime.


Storing Encrypted data in a mobile client We have a mobile client application which stores data in localstorage for offline use. The new GDPR requirements have to mandate us to encrypt the data we store in the client.

We used Stanford's sjlc.js package to encrypt the information using AES 128 before storing them in Local Storage. We did a brief performance test and it looks fine.

But the encrypted string is like below.

{"iv":"C8aBp2GjvPiZHCRtCPu+hg==","v":1,"iter":10000,"ks":128,"ts":64,"mode":"ccm","adata":"","cipher":"aes","salt":"duWxiMbE8TM=","ct":"cC4P/pMVozDpmnD/XzW2oif9GId8ZXCo7j/kP6QGlaT8C5pO09SBy6u6DneQz/AdeSQFtG9Ng05i0tASr8RcfNRYQGOFa17I7TI5xVSnd8L7322yihqxhsBbmBFSR0xesAEYmJcoIgPp1/MB+oXzm/pn0pzl0AfZNd8dTHrN+Wa9vcg107+2rVWY7K77BL1j7knRApU....................

We have to pass the whole string back to decrypt.

As you can see it contains the salt as well. Does that defeat the purpose?

I asked this same question in https://stackoverflow.com/questions/48275430/storing-encrypted-data-in-client. There was a suggestion to post it here.

Salt and IV are public data (just like the ciphertext) and don't reveal any data about the plaintext. They are necessary to decrypt. Therefore, they don't defeat the purpose.


Is the DES algorithm in OPENSSL random? Look at the hex dumps of encrypted1.bin and encrypted2.bin . They both have same password A which was used to encrypt sampletext

[achilles:~/Arena/crypto] $ openssl enc -e -des -in plaintext -out encrypted1.bin
enter des-cbc encryption password:
Verifying - enter des-cbc encryption password:

[achilles:~/Arena/crypto] $ openssl enc -e -des -in plaintext -out encrypted2.bin
enter des-cbc encryption password:
Verifying - enter des-cbc encryption password:

So both are encrypting the same text with the same password. Now when I hexdump them I get

[achilles:~/Arena/crypto] $ hd encrypted1.bin
    00000000  53 61 6c 74 65 64 5f 5f  50 cc a6 a8 6f 52 cf 53  |Salted__P...oR.S|
    00000010  c7 8e 71 ea 98 4b 2a 8c  a1 4d bd 0f d0 90 62 cb  |..q..K*..M....b.|
    00000020  b1 a0 7a ef b5 a8 c1 14                           |..z.....|
    00000028
    [achilles:~/Arena/crypto] $ hd encrypted2.bin
00000000  53 61 6c 74 65 64 5f 5f  0c c2 44 d0 19 bb a9 5e  |Salted__..D....^|
00000010  af 56 24 ce b3 b4 30 4f  61 1c f4 ba bd fc 1d a7  |.V$...0Oa.......|
00000020  b4 99 77 b9 1c 15 8a 42                           |..w....B|
00000028

How is this possible? How can the hexdump completely vary for the encryption of the same plain text with the same password and same algo (DES). And when encrypted1 and encrypted2 are decrypted they give me back the SAME plain text?

Using the -k option, you can specify a password. Passwords are not really encryption keys, so OpenSSL uses a key derivation process to turn the password into an encryption key. It turns out by default OpenSSL uses a salt in that derivation process (which is why you see Salted__ in the output, which is a magic to indicate that the next 8 bytes are the randomly generated salt). The ciphertext only starts from byte 16 onwards.

If the salt changes, the encryption key changes. If the encryption key changes, the ciphertext changes. By default OpenSSL generates a new random salt every execution. That is why you are seeing the changing ciphertext.

To turn this off you can add -nosalt. This is fine for testing purposes. As stated in the OpenSSL docs "This option SHOULD NOT be used except for test purposes or compatibility with ancient versions of OpenSSL and SSLeay". Otherwise your ciphertext is deterministic which can lead to cryptanalysis and a broken (i.e., insecure) system.

Alternatively -K lets you directly specify a key value in hexadecimals, skipping the (OpenSSL specific) password key derivation - and therefore the salt generation - entirely. You also need to specify the IV using -iv in that case. The IV should be random to achieve security in CBC mode if the key is reused, but the generation of the IV is left to the user.


2048-bit RSA Decryption If a message is encoded with 2048 bit RSA. The ciphertext is $M^e mod N$. In some cases, the message is short, $ M \approx 10^{20} $. With a high probability, $M$ can be written as $M = ab$ with $a, b \leq 4\sqrt{M}$.

Can you explain to me how I can find the initial message $M$ given $N, e,$ and the ciphertext using a computation with no more than $\approx$ $4*10^{20}$ total operations?

I heard that there was some relation between small a's and b's and being able to do a trick.

So if $M \approx 10^{20}$, and you have $4 * 10^{20}$ operations, why not just bruteforce it?

For more efficient solution, consider meet-in-the-middle technique. For all $1 \le a \le 4\sqrt{M} \approx 10^{20}$, make a hash table with values $a^e \mod{N}$. Then for all $1 \le b \le 4\sqrt{M} \approx 10^{20}$ check if $M^e/b^e \mod{N}$ is in the table.

Indeed, $M^e / b^e \equiv (ab)^e / b^e \equiv a^e \pmod{N}$ so it should be in the table (of course b must be invertible, otherwise it contains a factor of N and you can simply factorize N).

So total number of operations is $\approx 8\sqrt{M}$.


Keyed Hashing and verification Is there any standard algorithm where I can create a hash H(x,k) where x being the data and k being the private key. And verify on other end with H(x,l) where l being the public key?

How it can be achieved?

as SEJPM said you're looking for digital signature algorithms.
If you want names and standards, there's ECDSA based on elliptic curves and DSA based on the RSA philosophy.

https://en.wikipedia.org/wiki/Digital_signature

Good luck!


3DES over Galois Counter Mode (GCM) for authenticated encryption Is it possible to use DES or 3DES over Galois Counter Mode (GCM) to provide authenticated encryption?

I haven't seen any implementation yet.

According to Wikipedia,

  GCM is defined for block ciphers with a block size of 128 bits.

So no, you can't use GCM with 3DES or DES, because of the 64-bit block size. You could use something similar to GCM, but it wouldn't be GCM.


Can spatial filters be used to factor composite numbers? $Z=(N-XY)^2$ is a surface with absolute minima ($0s$) anywere $Y=N/X$.

I know this question is naiive, but shouldn't it be possible to apply a lossy compression filter to this function which preserves values only at discrete boundaries and then search for absolute minima?

If the answer is no, is there any online reference which describes the difficulties of this approach?

POSTSCRIPT

Some things crystalised in the discussion below, and need more space than can be added in the comments.

First, this question originates from the interaction of 3D rendering software and its interaction with the function $Z=(N-XY)^2$ (tested for small N only).  The interaction results in a surface denoted by $LC(x,y)$ below.

Now let $f(x)=N/x$, and $m(x)=\frac{df}{dx}=-N/x^2$, then the line normal to $f(x)$ at $\mathbf{x^\prime}$ is:

$$(y-f(\mathbf{x^\prime})) + (x-\mathbf{x^\prime})/m(\mathbf{x^\prime}) = 0$$

Expressing $y$ as a function of $x$:

$$y(x) = \frac{N^2-\mathbf{x^\prime}^4}{N\mathbf{x^\prime}} + x\frac{\mathbf{x^\prime}^2}{N} $$

Let the mouth of the valley below $\{\mathbf{x^\prime},f(\mathbf{x^\prime}),z\}$ be:

$$
r(\mathbf{x^\prime},z)=\sqrt{(x-\mathbf{x^\prime})^2+(y(x)-f(\mathbf{x^\prime}))^2} \,\,\, \text{where} \,\, LC(x,y(x))=z
$$

What is the likelihood of finding a suitable function $LC(x,y)$ such that $r(\mathbf{x^\prime},z)$ is maximum when $\mathbf{x^\prime}$ and $f(\mathbf{x^\prime})$ are integers?

Some things to note about $LC(x,y)$ and $r(\mathbf{x^\prime},z)$

$r(\mathbf{x^\prime},0) = 0$ iff $\{\mathbf{x^\prime},f(\mathbf{x^\prime}),0\}$ is rendered (i.e. sampled); otherwise $r(\mathbf{x^\prime},0)$ is undefined.
$r(\mathbf{x^\prime},z)$ is defined for $z>=z_{sat}$ where $z_{sat}$ is implementation dependent.
if $LC(x,y)$ is perfectly lossless, then $r(\mathbf{x^\prime},z)$ can be computed for all positive $\mathbf{x^\prime}$ and $z$ by solving the quadratic: $$\sqrt{z}-N+x\frac{N^2-\mathbf{x^\prime}^4}{N\mathbf{x^\prime}} + x^2\frac{\mathbf{x^\prime}^2}{N}=0$$

There are some good reasons why this hasn't been tried.

Firstly, it's not "discrete boundaries" but all points with integer coordinates $(x,y)$ on the hyperbola $xy=N$ which are candidates for factorization. The only information that matters is in those points, it doesn't matter if one uses your
$$
(N-xy)^2
$$
and look for zeroes, or if one uses
$$
(N/x)-\lfloor N/x\rfloor
$$
and looks for zeroes.

Secondly the function will be horribly noisy, and given our statistical knowledge about primes on the coarse scale, it is unlikely that it can be compressed much. The spatial filters can only use global, coarse information, otherwise they have to behave like functions that depend on brute force searching, in which case one might as well throw out the function, and the filter and the complications it represents, and work directly with discrete objects, i.e., integers, number fields, etc.

Finally, the state of the art factoring algorithms use a lot information from statistical as well as algebraic domains to optimize their execution complexity, but still have huge complexity, simply because $N$ is too large, and for the case we're interested in, $N=xy$ has ONLY one solution: This is when $x,y$ are two primes of roughly equal size.


Is HMAC-MD5 still secure for commitment or other common uses? MD5 collisions have been out for some time. In spite of this, HMAC-MD5 is still secure for authenticating data1. This illustrates a strength of the HMAC construction, it does not require that the hash function be (weakly) collision resistant.
Recently, Dan Kaminsky posted a simple method for finding HMAC-MD5 collisions. The steps of the attack are:

Given a hash function with a collision and a key either known or controlled by an attacker, it’s trivially possible to generate a HMAC collision.  The slightly less quick and dirty steps are:

Start with a file at least 64 bytes long
Generate a collision that can append to that file.
XOR the first 64 bytes of your file with 0x36’s.  Make that your HMAC key.
Concatenate the rest of your file with your colliding blocks.  Make those your HMAC messages.
HMAC(key, msg1+anything) will equal HMAC(key, msg2+anything)

HMAC has been suggested2 as a way to do cryptographic commitments.
Is HMAC-MD5 (or more in general, HMAC with a non-collision-resistant hash function) still a secure way to do commitments?
This is important because, for example, Python's HMAC library uses MD5 by default.
Bonus Question: Are there any other common uses of HMAC and are they still secure for HMAC-MD5?
1. Though not recommended for new applications.
2. If anyone knows of a more authoritative reference for using HMAC for commitment, please edit it in.

No, message commitment by disclosing its HMAC-MD5 with a key later revealed is no longer any secure, because of the ease with which MD5 collisions can now be found. There's however no compelling evidence that's insecure for messages constrained to belong in a small arbitrary set that no adversary can choose or influence. Still, whatever the constraints on the messages, the narrow 128-bit output width of HMAC-MD5 allows an attack with a relatively modest (and clearly feasible) $2^{65}$ evaluations of HMAC-MD5.

HMAC builds a PRF from a hash function $H$ with
Merkle-Damgård structure, message block width $w$ and output width $h$,
with $w\ge h$, as
$$\operatorname{HMAC}_H(K,m)=\begin{cases}
H\Big((K\oplus\text{opad})\mathbin\|H\big((K\oplus\text{ipad})\mathbin\|m\big)\Big) &\text{if $|K|\le w$}\\
\operatorname{HMAC}_H\big(H(K),m\big) &\text{if $|K|>w$}
\end{cases}$$
where $\text{opad}$ (resp. $\text{ipad}$) is the 0x5c5c5c… (resp. 0x363636…)
pattern with width $w$, and $\oplus$ is bitwise exclusive-OR with the
shortest operand right-padded using zero bits.

If the compression function used to build $H$ has suitable properties,
then for random unknown $K$ with $|K|\ge h$, the function $m\mapsto
\operatorname{HMAC}_H(K,m)$ is indistinguishable from random with
effort less than about $2^h$ evaluations of $H$. We have no compelling evidence that this does not hold for $H=\operatorname{MD5}$ (for which $h=128$, $w=512$). For more details see Mihir Bellare, New Proofs for NMAC and HMAC: Security without Collision Resistance, in Journal of Cryptology, 2015 (originally in proceedings of Crypto 2006).

When $H$ is MD5, or any $H$ that is not collision-resistant, the attack in the question renders insecure a commitment protocol where Alice

secretly chooses $m$ and $K$
computes and publishes $\operatorname{HMAC}_H(K,m)$ as a commitment of $m$
performs some action dependent on $m$ (like: offer a bet about the first bit of $m$)
later reveals $m$
reveals $K$, allowing a verifier to compute $\operatorname{HMAC}_H(K,m)$ on the $m$ Alice alleges, and compare against Alice's commitment.

Notice however that even with an ideal $H$, there's an attack with effort about $2^{h/2}$ evaluations of $H$, where Alice finds $m$ and $m'$ with $H\big((K\oplus\text{ipad})\mathbin\|m\big)=H\big((K\oplus\text{ipad})\mathbin\|m'\big)$; thus the mere output size of HMAC-MD5 limits its security level to a modest $2^{64}$ evaluations of MD5, in this protocol where $m$ is unconstrained.

On the other hand, I see no attack (much better than brute force on $K$) on the use of HMAC-MD5 (or HMAC with a non-collision-resistant $H$) in the variant of this protocol where Alice is constrained to choose $m$ in a small arbitrary set that no adversary can choose or influence, like $\{\text{“stone”},\text{“paper”},\text{“scissors”}\}$, as considered in the suggestion referenced in the question. Alice has so little choice on the messages that she must be clever in her choice of $K$, rather than $m$, in order to cause a collision. My intuition is that because $K$ enters twice in the computation of $\operatorname{HMAC}_H(K,m)$, with at least one execution of the compression function in-between (for heavily constrained $m$), finding a theoretical shortcut would be extremely hard, well beyond what the current cryptanalysis status of MD5 allows.


AES-GCM ciphertext that deciphers under two keys How can we exhibit an AES-GCM ciphertext, including IV and 128-bit authentication tag, and distinct keys $K_0$ and $K_1$, so that decryption succeeds for both keys?
What degree of control do we have on the respective plaintexts obtained by such decryption? Can that extend to the point that this nightmare (referring page) of the same encrypted and authenticated ciphertext decrypting to two meaningful but wildly different documents holds (for some standard document/archive format)?
Numerical example (or link to that) welcome!

Update: I'm told this is as described there by Yevgeniy Dodis, Paul Grubbs, Thomas Ristenpart and Joanne Woodage's Fast Message Franking: From Invisible Salamanders to Encryptment, in proceedings of Crypto 2018; but I'd like an independent answer focusing on the how (even if that's not detailed), and leaving out Associated Data if that's not essential.

How can we exhibit an [AES-GCM][1] ciphertext, including IV and 128-bit authentication tag, and distinct keys $K_0$ and $K_1$, so that decryption succeeds for both keys?

It's quite easy (if you grok linear algebra in $GF(2^{128})$
Here's what you do:

You arbitrarily select the keys $K_0$ and $K_1$,  the nonce and the ciphertext/AAD (except for one block, which can be anywhere, including in the AAD); we'll assume that the one block is at indes $i$ (where the last block of the ciphertext is index 2, the next to last is index 3, and so on - this rather odd convention is related to how GCM works internally).

We then compute the GCM authentication key $H_0 = AES_{K_0}(0)$ and $H_1 = AES_{K_1}(0)$
Then, the tag for the message with $K_0$ can be expressed as:
$$C_0 + M_i H_0^i$$
where $C_0$ is a function of $K_0$, the nonce and the selected message, AAD blocks, and $M_i$ is the value we'll place into ciphertext block $i$.  One easy way to compute it is to insert a 0 where $M_i$ would go, and compute the tag as normal.
Similarly, the tag for the message with $K_1$ is:
$$C_1 + M_i H_1^i$$
So, to find $M_i$ so that they have the same tag, we equate the two, resulting in:
$$M_i = (H_0^i + H_1^i)^{-1}(C_0 + C_1)$$
(Remember, we're in $GF(2^{128})$; addition and subtraction are the same operation, so we usually express it as addition; in a different field, this would be written as $(H_0^i - H_1^i)^{-1}(C_0 - C_1)$)
Put that into the ciphertext, include the appropriate tag (computable by the above formula), and there you go.
This approach can be extended to finding a message that'll decrypt with $k$ different keys (by using $k-1$ free blocks).

Can that extend to the point that this nightmare of the same encrypted and authenticated ciphertext decrypting to two meaningful but wildly different documents holds (for some standard document/archive format)?

Not quite; the attacker can pick the ciphertext so that it'll decrypt under one of the keys to a chosen message (except for that one block); however that gives him no control over the other decryption.
By making a reasonable assumption on AES, it would appear provable that the attacker cannot do significantly better (at least for 96 bit nonces).  GCM translates ciphertext to plaintext (assuming a valid decryption) by the operation $P_i = C_i \oplus AES_k( N(i) )$, where $N(i)$ is the nonce and the block index combined).  Hence, the xor of the two decrypted plaintexts will be, for that block $AES_{k_0}( N(i) ) \oplus AES_{k_1}( N(i))$, and that wouldn't be controllable.
Nonce sizes other than 96 bits would be harder to analyze (as $N(i)$ now becomes a function of the key); however there wouldn't be an obvious approach to break that either.


Clifford Cocks Interview: "Raising numbers to a power with the product as modulus" Disclaimer: I'm new to cryptography

Background: Clifford Cocks, the former GCHQ mathemetician and crytologist, gave an interview where he said:

  "My thinking was that you need something that is easy to do, and
  difficult to undo, so I thought of the product of two primes. It's
  essential that you have a one-way function which can only be inverted
  if you know the factors — and raising numbers to a power with the
  product as modulus is something you can unpick only if you know the
  factors."

Question: Does anyone have a very simple example of this?

My (probably wrong) attempt:

$2^2 \times 2^3 = 32$ whose factors are $1,2,4,8,16,32$
$x^{32} = y$
$y$ modulo ?

I'll give a brief and simple example of what is described in the quote, which is now known as RSA for which there are plenty of descriptions and tutorials for all levels of understanding as pointed out by yyyyyyy.

  ... so I thought of the product of two primes ...

So, for our example this will be $p=21$ and $q=23$ of which the product is $n=21\times 23=483$. Note that you'll find it easy to multiply the two numbers to find $483$, but will have a rather hard time to find the factors of $483$, only given a calculator or pen and paper, for real-world encryption the primes will be around $10^{300}$.

  ... raising numbers to a power with the product as modulus...

For our example let's pick the exponent $e=17$, which is also sometimes used in the real-world. As our example message, let's pick $m=131$. You'd now raise $m$ to the power $e$ modulo $n$ ($=m^e\bmod n$). In our example this would mean calculating $131^{17}=985398793384554108247251712700460611$ (using a calculator or a math program may be useful here). Next, you'd apply the modulo operation which is taking the remainder of division with remainder. In our example this would mean calculating $985398793384554108247251712700460611\bmod 483$ which is $395$ -- your result -- as $395 + 483 \times 2040163133301354261381473525259752=985398793384554108247251712700460611$.

That's it what he actually described in his quote, I'll add the decryption procedure below.

For decryption you must find an integer $d$ such that $(e\times d) \bmod{((p-1)\times(q-1))} = 1$ (also commonly notated as $ed\equiv 1\pmod{\varphi(n)}$). Normally you use the extended euclidean algorithm to find this value efficiently. In our example $d=233$, which you can use as the exponent to which you need to raise the ciphertext in order to retrieve the original message. So you'd calculate $c^d\bmod n=395^{233}\bmod n=131$ (don't bother calculating $395^{233}$, it's over 500 digits long) and get $131$ as expected.


Is WPA2(PKS) AES vulnerable to 4 way hand shake and brute force attack? I can easily crack a WPA TKIP using a dictionary/brute force method, provided that I collect the four way handshake. Is the same method possible on WPA2 AES? I cannot find any articles about '4 way handshake capture' and 'WPA2 AES cracking' together; but I was able to use aircrack-ng to crack my WPA2 AES wireless network.

Does WPA2 AES uses uses the same method as TKIP where using a 4 way handshake a temporary password is generated?

Yes. Both WPA-TKIP and WPA2-AES use the same 4-way handshake, and the same way of deriving the PTK from the PSK. AES does not affect this. To launch the brute-force attack on the PSK you only need to capture the 4-way handshake (including the nonces). This is also true for WPA2-AES-PSK.


Does a cryptosystem provide unconditional security if and only if it provides perfect secrecy? Is unconditional security and perfect secrecy one and the same thing, i.e a cryptosystem provides unconditional security if and only if it provides perfect secrecy ?

I've wondered about the above and seen that the one-time-pad provides unconditional security in terms of perfect secrecy. Does this hold in general ?

Yes, in context of encryption the two terms have the same meaning, i.e. even an unbounded adversary cannot succeed in breaking the secrecy of the scheme.

Note that there may be other primitives which also provide unconditional security with respect to some other notions, such as information theoretically secure message authentication codes with respect to unforgeability.


Key sizes for RSA over elliptic curves I know that it is possible to define RSA over elliptic curves just as DSA and Diffie-Hellman have been. I know that it doesn't offer much of a speed advantage, but does it at least reduce the size of the keys?

No, it would not reduce the size of the keys.  To break an ECRSA problem, you would factor the order; that factorization problem is not inherently different than any other factorization problem over the integers.  Hence, to make that problem intractable, you'd need to make it as large as traditional RSA.


What is the purpose of implementing cryptographic algorithms in a token? In particular, in PKCS #11. Not a lot of information on the web; I found this explanations. Ignoring the empty marketing talk like “heightened security” and “centralized and secure management”, I managed to extract the following benefits:

secrets do not leave the token,
tamper-resistant audit of the usage of secrets.

In practice, “secrets do not leave the token” is not benefitial. In order to use a secret, a user needs to upload that secret to a program with a user interface (UI). For example, a banking application. This program is not able to execute on a token since tokens have insufficient UI. Hence this program will execute on a UI device to which the token is attached.

Suppose that the UI device is breached.

If cryptographic algorithms are implemented in the token, the attacker can execute any operation that the user can as long as the token is attached.

If cryptographic algorithms are implemented in the UI device, the attacker posesses the user's secrets.

In practice, option 0 is as bad as option 1. For example, for a banking application, the attacker can sign a payment in either case.

Suppose that the UI device is not breached. Then we have equal security independently of where cryptographic algorithms are implemented.

Implementing cryptographic algorithms in the token has disadvantages:

AFAIK, PKCS #11 does not allow backups. If you store all your secrets in a token, it will be valuable not only to attackers, but to you too.
Restricted set of cryptographic algorithms. Only algorithms implemented in a token.
More complex hardware interface and API. [Update 2021-02-15. Here I am comparing to USB mass storage. If a token does not implement cryptographic algorithms, it is essentially an information storage device.]

Am I right?

In practice, “secrets do not leave the token” is not beneficial.

Ouch, I think I would rather like to know where my keys are. This is about the same as saying that you don't care if your house keys got copied or not.

For example, a banking application. This program is not able to execute on a token since tokens have insufficient UI. Hence this program will execute on a UI device to which the token is attached.

In PKCS#11 you can still have key specific PIN or passwords. This is especially important for transactions which is what you are referring to here.
Sometimes additional security measures such as counters are also present. If those are not depleted they can at least be used to check if the key was used unexpectedly. In software the attacker could just reset the counter at will. Cars also have odometer's that are deliberately hard to compromise.
That all said, yes, if an attacker has full access to the keys within the token over extended periods of time then the token is virtually useless.

If cryptographic algorithms are implemented in the token, the attacker can execute any operation that the user can as long as the token is attached.

Absolutely, and there is a balance between usability and security here, which is hard to maintain. E.g. you can setup a HSM in such a way that a person has to login into each session. Then again, you might have some trouble finding a human in the middle of the night that is able to do this upon a sudden restart of a server. This would be fine for personal tokens and smart cards.
Login procedures can also be protected by additional counter measures such as number of logins or delays between password verification checks.

If cryptographic algorithms are implemented in the UI device, the attacker posesses the user's secrets.

There are things like white box cryptography of course. And then there are certainly levels of access. Even in software you can have a secure system run at a different level than the user process. However, in that case you cannot easily protect against side channel attacks on processor usage. So this actually advocates for a hardware device such as a token.

AFAIK, PKCS #11 does not allow backups. If you store all your secrets in a token, it will be valuable not only to attackers, but to you too.

PKCS#11 is a generic token interface. However, most if not all HSM's have proprietary backup mechanisms and / or extensions of the PKCS#11 interface to deal with backups.
Other tokens such as smart cards basically require you to request a new smart card or token - which is fine for signature generation (authentication, non-repudiation). It is bit more tricky when it comes to decryption for obvious reasons.

Restricted set of cryptographic algorithms. Only algorithms implemented in a token.

Absolutely, and this can be a nuisance. And if you enable FIPS mode then only FIPS algorithms will be available. HSM's can receive (signed) updates though. And generally we don't use tokens for research, we tend to use them for standardized algorithms.
Some HSM's actually allow you to run restricted programs as well - although this may have interesting effects on certification of the hardware.

More complex hardware interface and API.

That's debatable. I think the PKCS#11 interface is well specified and it is about the only standardized, generic crypto API out there. It may not suite your language / runtime model perfectly, but the fact that you can use it from a myriad of languages and runtimes has a lot going for it. Many languages contain wrapper libraries around PKCS#11, which are then wrapped object oriented wrappers where required.


Difference between $F_2^n$ and $\Bbb F_2^n$ for a field I am confused between the notation $F_2^n$ and $\Bbb F_2^n$ for a field in regards to codes.

I thought that $F_2^n$ and $\Bbb F_2^n$ were both fields composed by codes of length n and entries in mod 2, but I now know that this cannot be true.
What is the difference between them?

For example, if code C is consists of all the codewords in $F_n^2$ that have even weight, to show that C is a linear code, do I use the fact that it is a subspace of $F_2^n$ or $\Bbb F_2^n$?

Thank you!

Some authors write $F_q$ for the finite field of order $q$.  Some authors write $\mathbb F_q$.  Some authors write $\mathbf F_q$.  Unless there's a typo, or unless your pet author is particularly confusing and as a personal peculiarity makes a nonstandard semantic distinction between them, which one you use is a matter of taste.  And as we all know—de gustibus non disputandum est: only with gusto can taste be argued.

What parts of the text you are reading are leading you to a state of confusion?  Maybe you can ask a question about those in particular.


HMAC-Ripemd-160 in TrueCrypt I'm wondering if it is still secure.

I know TrueCrypt closed its doors but I continue using it because the cryptoaudit didn't find any huge bugs or security issues in TrueCrypt.

But I have a bad feeling about Brute Force and Ripemd-160. I've read that it only uses 3000 Iterations. So I ask myself: How long would it take to Brute Force the password of the encrypted disk?

The use of RIPEMD-160 is not a cause for concern. It's the relatively small number of PBKDF2 iterations which is problematic. More than a decade ago, the minimum recommended number of iterations was 10,000. Nowadays, you should probably not be using less than 100,000, regardless of the hash function in use. However, even that is not ideal. If possible, you should be using a memory-hard KDF like Argon2. That limits the parallelism that an attacker can use against you with any given amount of resources.

Also, TrueCrypt used only 2000 iterations, not 3000, of RIPEMD-160 and 1000 for any other hash.


Does it make sense to have a 4000 bit long key? My question is about the key length of a asymetric algorithm. How is it possible to memorize or remember a key that is about 4000 bits long?

A 4000-bit RSA key is reasonable (more precisely, that would be the bit size of the public modulus; and 4096-bit would be more common). But it is not reasonable to memorize it (or, more precisely, that the owner try to memorize the corresponding private key); and that's practically never done.

One does not ask normal users to memorize or remember a key, or other information, with more than perhaps 50 bits worth of entropy (say as 8 characters among 77, or 2 phones numbers); even that is hard, and XKCD's method is probably more reasonable.

Long asymmetric private keys are usually

Stored encrypted by way of a symmetric algorithm using a stretched password/phrase as key, and stored on disk as a file; that's what PGP, GPG, and many other programs do.
Not stored, but rather re-generated at each use, from a passphrase combined with stretching seeding a CSPRNG used by the key generator; advantage is that the passphrase entirely replaces the private key in normal usage; but that makes safe passphrase change impossible; and requires a lot of stretching and a long passphrase to be secure.
Stored (and while we are at it used) inside a Smart Card protected by PIN with error counter (locking the card after 3 consecutive errors).


Why is elliptic curve cryptography not widely used, compared to RSA? I recently ran across elliptic curve crypto-systems:

An Introduction to the Theory of Elliptic Curves (Brown University)
Elliptic Curve Cryptography (Wikipedia)
Performance analysis of identity management in the Session Initiation Protocol (SIP) (IEEE)
Overview of Elliptic Curve Cryptosystems. (RSA.com)

It seemed to me to be great alternative to RSA as the de-facto cryptosystems to be used in banking and financial systems and in the public key infrastructure for certificates, but is not used! If someone can explain why this is not done, it would be very helpful. A comparison between traditional RSA and an elliptic curve cryptology would be helpful.

To begin with:

Advantage of RSA:

Well established.

Advantages of elliptic curve:

Shorter keys are as strong as long key for RSA (see the IEEE paper)
Low on CPU consumption.
Low on memory usage.

RSA was there first. That's actually enough for explaining its preeminence. RSA was first published in 1978 and the PKCS#1 standard (which explains exactly how RSA should be used, with unambiguous specification of which byte goes where) has been publicly and freely available since 1993. The idea of using elliptic curves for cryptography came to be in 1985, and relevant standards have existed since the late 1990s. Also, both RSA and elliptic curves have been covered by patents, but the RSA patents have expired in 2000, while some elliptic curve patents are still alive.

One perceived, historical advantage of RSA is that RSA is two algorithms, one for encryption and one for signatures, that could both use the same key and the same core implementation. But this is not a real advantage because it is usually a bad idea to use the same key for both encryption and signatures. Also, you can mathematically use the same private key for ECDH (key exchange) and for ECDSA (signatures), so that's really not an "advantage" of RSA over EC at all.

Another advantage of RSA is that its mathematics are somewhat simpler than those involved for elliptic curves, so many engineers feel that they "understand" RSA more than elliptic curves; again, a fallacious argument, since implementation of cryptographic algorithms is fraught with subtle details and best left to professionals -- and there is no need to understand the internal mathematics of a library to simply use it (we could make this argument semi-valid by pointing out that RSA relies on the hardness of factorization, which has been studied for 2500 years, whereas discrete logarithm on elliptic curves can only sport about 25 years of research).

The only scientifically established advantaged of RSA over elliptic curves cryptography is that public key operations (e.g. signature verification, as opposed to signature generation) are faster with RSA. But public-key operations are rarely a bottleneck, and we are talking about 8000 ECDSA verifications per second, vs 20000 RSA verifications per second.

An additional interoperability issue is that elliptic-curve operations can be made over curves of distinct types, and can be widely optimized if you stick to a specific curve known when the code was written. There is no security issue in using the same curve for many distinct people with distinct key pairs. But it means that most implementations will only support two or three specific curves. NIST has defined 15 standard curves. However, in practice, many implementations only support two of them, P-256 and P-384, because that's what is recommended by NSA (under the name "suite B")(a notorious example is NSS, the cryptography library used by the Firefox Web browser for SSL).

There are two ANSI standards for elliptic curves, X9.62 for signatures (partially redundant with FIPS 186-3, but much more detailed), and X9.63 for asymmetric encryption.

So there is a lot of political push for the adoption of elliptic curves in cryptography, by both academic researchers and institutional organizations. But inertia of the firmly entrenched RSA will take time to defeat. Also, the perceived mathematical complexity, and the potential legal risks related to patents, still hinder wide acceptance of elliptic curves.

(To your list, you can add "key generation time": generating a new key pair for ECDH or ECDSA is widely faster than generating a new RSA key pair.)


Which encryption algorithm is sensitive to an attacker having access to it? We are contemplating hiding a sensitive information from our business partner by encrypting it.
However, customers have access to both the sensitive and the encrypted information. Furthermore, they can influence the 'sensitive information' to their liking.
I am curious which security algorithms are sensitive to an attacker being able to encrypt whatever they choose to (and see the result). Also, is there a known guide (or a googleable name) of this property of crypto algorithms?

I am curious which security algorithms are sensitive to an attacker being able to encrypt whatever they choose to (and see the result).

No algorithm would be considered secure if they could be broken under that assumption.

Also, is there a known guide (or a googleable name) of this property of crypto algorithms?

There's a couple of different names (based on some fairly subtle distinctions); the most common is probably "IND-CPA", which stands for "indistinguishable from random against chosen plaintext attacks", that is, even if the attacker was allowed to submit large number of plaintexts of their choosing and get them encrypted, they still would be unable to obtain any information about the encryption method (it'd still look "random")


Keyless integrity checking with SHA-256 Currently a program is loading some files from an untrustworthy source (e.g. a CDN) which could have been tampered with. It has a known SHA-256 hash of the file stored locally, then it downloads the file from the CDN and compares the hash before loading the file into memory.

Because most of the SHA2 family suffers from length extension attacks (except for the truncated versions) this SHA-256 hash seems inadequate for integrity checking files coming from an untrustworthy source. A clever attacker could embed some extra data in the file being downloaded, the program would receive the file, calculate it to be the same SHA-256 hash, unwittingly execute that code and compromise the program.

The program's source code is publicly available, therefore embedding a secret key for HMAC is not an option and would be too slow anyway. SHA3 library code is not currently available either. However the SHA-384 hash is not vulnerable to the length extension attack. Would the next best option be to use SHA-384 for this integrity checking? It would also match up with NSA's recent recommendation to use at least SHA-384.

A length extension attack doesn't let you find a collision. It lets you predict the hash for an input with an unknown component in the prefix. If you have $h = H(x)$ for unknown (or partially unknown) $x$, you can generate $h_y = H(x \vert\vert y)$ for arbitrary $y$ (this is not strictly correct; I've ignored padding, but for the purposes of this discussion it's a minor detail). However, you still can't find $z$ such that $h = H(x \vert\vert z) = H(x)$ faster than brute force.


Why might SHA-384 throughput be lower than SHA-512 throughput in hashcat and more secure? I found a hashcat benchmark results in the internet: hashcat results:

SHA-384 is 17065.4 MH/s
SHA-512 is 17280.3 MH/s

Why does SHA-512 take less time? SHA-512 is longer and I thought it therefore needs more time and computation resources to compute the hash?

The only differences in calculations are the initial value and the output size. From NIST FIPS 180-4

The initial hash value, $H^{(0)}$, shall be set as specified in Sec. 5.3.4; and
The 384-bit message digest is obtained by truncating the final hash value  $H
^{(N)}$, to its left-most 384 bits:
$$H_0^{(N)} \mathbin\|H_1^{(N)} \mathbin\|H_2^{(N)} \mathbin\|H_3^{(N)} \mathbin\|H_4^{(N)} \mathbin\| H_5^{(N)}$$

When two source codes are compared inc_hash_sha384.cl and inc_hash_sha512.cl one can see that actually, SHA-384 does less job than SHA-512. It is not coded simply truncate the SHA-512 with different initial values. For the little speed difference, one explanation can be the vectorization that helps SHA-512 during the final calculations.
In the case of password protection, the tiny difference does not make much difference. In password hashing, actually, we use specially designed password mechanisms like PBKDF2 and Argon2 which was the winner of the password hashing competition.
In the security perspective, SHA384 has resistances to length extension attack but SHA512 doesn't have. SHA384 has 128-bit resistance against the length extension attacks since the attacker needs to guess the 128-bit to perform the attack. This is due to the truncation.
The different initial value provides domain separation. With domain separation  $$\operatorname{SHA384}(m) \neq \operatorname{SHA512}(m)|_{384}$$ where $|_{384}$ is the truncation.
In the case of pre-image, secondary pre-image, and collision resistance in generic attacks we have;
\begin{array}{|c|c|c|c|}\hline
& \text{pre-image resistance} & \text{2. pre-image resistance} & \text{collision resistance} \\\hline
\operatorname{SHA-384} & \mathcal{O}(2^{384}) & \mathcal{O}(2^{384}) & \mathcal{O}(2^{192}) \\\hline
\operatorname{SHA-512} & \mathcal{O}(2^{512}) & \mathcal{O}(2^{512}) & \mathcal{O}(2^{256}) \\\hline
\end{array}
The collision resistance is $\mathcal{O}(\sqrt{2^{n}}) = \mathcal{O}(2^{n/2}) $ due to the generic birthday attacks.
Therefore; SHA-512 is better in the case of pre-image, secondary pre-image, and collision resistance.  SHA-512's only weakness is that it is prone to length extension attacks.


Almost (epsilon) perfect secrecy - lower bound of keyspace size As a newcomer to cryptography, I'm working on Exercise 2.12 in the book, Introduction to Modern Cryptography.

Using the proof of the theorem that says if $E$ is a perfectly secret encryption scheme, then $\lvert K\rvert \geq \lvert M\rvert$),
I've shown that the lower bound for the size of the keyspace is as below:
$$\lvert K\rvert \geq (1-\epsilon)\lvert M\rvert$$

But here's the problem: I proved this under the condition that $$\lvert\Pr[M=m\mid C=c]-\Pr[M=m]\rvert\leq\epsilon$$

So I think I should show that this definition is equivalent to the condition given in the exercise.

My question is whether the two definitions are equivalent, and if so, how can I prove it?

Short answer: the two definitions are not equivalent.
Long answer:

The condition $|\Pr[M=m\mid C=c]-\Pr[M=m]|\leq\epsilon$ doesn't allow us to have less keys than messages. Encrypt an arbitrary message to get a ciphertext $c$, then use all keys to decrypt $c$. If $|K| \lt |M|$, there exists a message $m$ which can not be decrypted from $c$ using any key.
Then $|\Pr[M=m\mid C=c]-\Pr[M=m]| = \Pr[M=m]$ and since we can assign an arbitrary distribution to our message space, we can make $\Pr[M=m] > \epsilon$

The definition of $\epsilon$-perfect secrecy given in the book (the one you show in the image) does allow us to have fewer keys than messages. For example:
Suppose the message space $M$ contains all 4 English letter words, $|M|$ = $26^4$. Let's use a one-time-pad encryption scheme without the identity key, thus $|K|$ = $|M| - 1$.
Any adversary playing a game will choose two messages $m_0$, $m_1$. If our returned ciphertext $c=m_0$ the adversary knows for sure that the encrypted message is $m_1$. If our returned ciphertext $c=m_1$ the adversary knows for sure that the encrypted message is $m_0$. But if we return any other ciphertext, the one-time-pad scheme ensures that the best an adversary can do is to make a random guess. Therefore, the probability for an adversary to win a game is not greater than
$1 \cdot \Pr(c \in \{m_0, m_1\}) + \frac{1}{2} \cdot (1 - \Pr(c \in \{m_0, m_1\}))$ = $\frac{1}{2} + \Pr(c \in \{m_0, m_1\}) \cdot \frac{1}{2} = \frac{1}{2} + \frac{1}{2|K|}$
Thus, this scheme achieves $\epsilon$ perfect secrecy if $\epsilon \geq \frac{1}{2|M-1|}$

Let's find a lower bound for $\epsilon$. Suppose an adversary chooses $m_0$ and $m_1$ uniformly at random. Upon receiving a ciphertext $c$ it computes $M_c = \{ m | \exists k. enc_k(m) = c\}$ (it might be computationally infeasible to compute $M_c$, but we're not concerned about computational resources in this exercise).
Note that at least one of $m_0, m_1$ is in $M_c$. If some $m_i \not \in M_c$ the adversary knows for sure that the encrypted message is the other one. If both messages are in $M_c$, the adversary makes a random guess.
The probability of such adversary succeeding is
$\frac{1}{2} \cdot \Pr(m_0, m_1 \in M_c) + 1 \cdot (1-\Pr(m_0, m_1 \in M_c))$ = $ 1 - \Pr(m_o, m_1 \in M_c) \cdot \frac{1}{2}$
Let's estimate $\Pr(m_0, m_1 \in M_c)$ - the probability that both messages are in $M_c$. One message will certainly be in $M_c$ because we encrypted it to $c$, the other message is chosen uniformly at random from $M$, so the probability of both being in $M_c$ is $|M_c| / |M| \leq |K| / |M|$
Thus an adversary can win a game with a probability $p \geq 1 - |K| / |M| \cdot \frac{1}{2} = \frac{1}{2} + \frac{1}{2} \cdot (|M| - |K|) / |M|$. If we want $\epsilon$ secrecy we must have $\frac{1}{2} + \epsilon \geq p$ which implies that:
$|K| \geq |M| \cdot (1-2\epsilon)$
note that I have not shown this lower bound is attainable.


Showing a CBC-MAC is not preimage resistant with a proof So hypothetically I have a an arbitrary block cipher operating in CBC-MAC mode that makes use of a public and static $IV$ as well as a static key $K$.
I want to be able to that this won't be preimage resistant using a proof for an arbitrary single-block message $P$ that hashes to a given digest $T$. So far I've gotten as far as $$T = E(P \oplus IV, K)$$ $$D(T, K) = P \oplus IV$$ $$P = D(T, K) \oplus IV$$
I can't for the life of me figure out how to move from this to something that will show that the operation is not preimage resistant. As far as I understand if $K$ and $IV$ are fixed it should be computationally infeasible to find another $T_x$ such that $$D(T,K) \oplus IV = D(T_x, K) \oplus IV$$
Ideally I'd want to be able to extend this to show that for $P$ of any length I could find a $T_x$.

According to wikipedia's page on CBC-MAC:

If the block cipher used is secure (meaning that it is a pseudorandom permutation), then CBC-MAC is secure for fixed-length messages.[1] However, by itself, it is not secure for variable-length messages. Thus, any single key must only be used for messages of a fixed and known length.

Your case presents no such vulnerability, since you're hashing a fixed number of blocks ($1$, to be exact). If you were to compute the CBC-MAC of a variable-length message you could perform such a preimage attack.


How to encrypt and decrypt a transposition cipher? I encrypted the text hello there with a 3x4 table with the key 2 1 3. I fill in the text into the table row by row and got the ciphertext eohehltrl_ex(reading by column). So if I were to decrypt this ciphertext into the plaintext what should I do? I made a 3x4 table again and filled it in row by row (according to online tutorials). However, I couldn't get the same text anymore. Do I fill in the ciphertext into the table by columns? I did my homework on decrypting a transpostion cipher(I fill in the ciphertext into the table by rows and I got the answer); however when I tried encrypting and decrypting my own text I couldn't do it.

Does anyone know what I am doing wrong?

For Decryption Process, use the reverse of encryption process.
I think you are using a wrong table format. The table should be 4*3 instead of 3*4. Now, Write your encrypted text column by column(4 rows and 3 cols). It will be like this.

e h l

o l _

h t e

e r x

Now, Apply the decryption key of key 2 1 3. The decryption key will be the same.

2 1 3

| | |

2 1 3

Now, arrange the message in columns from above by making necessary transformations. The table will become,

h e l

l o _

t h e

r e x

Now, Read row by row. Your Message will be

hello there

Remember, For decryption, apply the same process for encryption in reverse order.
Hope that helps. :)


Best practices (if any) to add metadata to encrypted files I am encrypting files using AES/CBC/PKCSPadding, with 256 bits long keys. So far the first 16 bytes of each encrypted file are the IV.

I would like to store some more information regarding the algorithm used, key length, mode and padding at least.

This will be useful I think for two reasons:

a) I can scan the filesystem looking for my files and checking they are all encrypted (encryption is a new feature, so there are already a bunch of unencrypted files out there). This way I can create a background task that progressively encrypts all old files

b) Say someone breaks AES or there's a problem with CBC or something in 10 years or whatever. I could just upgrade the parameters of the encryption function and again scan the file system and upgrade the encryption of my files.

I was thinking for this something like:

byte[] header = "AES|256|CBC|PKCS5Padding|".getBytes(UTF_8);
byte[] iv = ...; // the result of cipher.getIV() after initializing the Cipher;

And then writing both the header + IV to the beginning of the file.

So my question is: Does adding such metadata to encrypted files create any security concerns for such files? Is this something that people normally do? If so, is the way I'm trying to do it (adding a fixed number of bytes) will be enough to accomplish this task?

This is pretty common. The method of encryption is public information, so it is safe to leave in the clear.

In your post you made no mention of authentication. This is something you absolutely must use, otherwise you have no way of knowing if your data has been modified and leaves you open to many attacks.

Consider using HMAC with SHA-256, or a block cipher mode with built-in authentication (e.g. GCM). Everything needs to be authenticated (any metadata, header, IV, ciphertext, etc).


Is there a way to sign a message so that any subset can be verified? I would like to know if there's a scheme that can allow something like the following:

Alice signs a message $M$ with signature $S$ and gives it to Bob and Mallory.
Bob can present any subset of $M$, along with $S$, to Victor, who can verify that the subset matches $M$.
If Mallory changes some bits of $M$, then sends a subset of the bits to Victor, Victor can know that the message has been tampered with. (Of course, Mallory should not be able to construct a valid signature that would allow her tampered-with bits to be verified).

For example, say

Alice's message $M$ is $100100$, and the signature is $101$.
Bob will send Victor $M[0]=1, M[4]=0, signature=101$, and Victor will verify that those bits match $M$.
Mallory will send Victor $M[0]=1, M[4]=1, signature=101$ (this is malicious, since $M[4]$ does not equal $1$ in $M$). Victor will notice this and refuse to verify.

Does a scheme like this exist?
I think that there are somewhat naive solutions (for example, perhaps the signature could consist of several sub-signatures: each bit and its index in $M$ are signed, and the results are concatenated), but I am hoping for something where the signature is short relative to the size of the message.

We can easily see that the signature must be at least as large as the message.  Otherwise, it would be impossible to verify any arbitrary single bit.  Signing  a message with n bits must necessarily must involve a signature that can validate n unrelated 1 bit message subsets.
However, if we assume Bob and Mallory are given copies of the message, there may be opportunities where computations are done over the entire message, but not transmitting the entire message.  This could help reduce the signature size.
You may be interested in Merkle Trees.  I don't know if they are exactly what you are looking for, but they provide some interesting approaches for proving things about contiguous subsets of messages.   In a worst case scenario, you would have to send Victor effectively the entire Merkle tree.  However, for revealing small fractions of the tree, you may be able to keep a large portion of the information out of the message.  You only have to reveal the sibling leaves for every bit you send, which would not reveal the whole message, while still authenticating it as a subset.
There are a few cryptocurrency algorithms out there which leverage this for micropayments.  Alice generates a list of coins, puts them in a Merkle tree, and then gets the top of the tree signed by Victor.  She then gives this signed top to Bob, who authenticates it with Victor (online or offline).  After this point, Alice can send Bob a coin simply by revealing it, and all of the sibling internal nodes required to prove it was part of her list of coins.  These algorithms, of course, strive to be efficient.  They expose the coins in order, so they only ever have to reveal contiguous subsets, not the arbitrary ones you might need.  This keeps the message traffic down to O(n log m) for n coins transferred out of m coins minted.
Another approach would be to carefully select the message that Alice constructs to have the properties you desire, rather than being an arbitrary message.  Zero Knowledge Proofs are full of clever situations where Bob has to demonstrate information about a message while carefully controlling how much information is transmitted.
One thing you should definitely watch out for is whether there is any issue with Eve computing the message from just S and the message traffic between Bob and Victor.  The content of the message could start getting leaked.  If you know the internal node over a group of n bytes, you can brute force those n bytes, recovering a part of the message that hadn't been revealed by Bob.  But if the goal is simply to provide subsets of a verified message to Victor, that may be acceptable.


Questions regarding static Diffie-Hellman (ephemeral-static) usage in TLS It looks to me that there 3 main variants of Diffie-Hellman in SSL/TLS.

Anonymous mode;
Static mode;
Ephemeral mode.

In case of static DH the server owns an X.509 certificate with a DH public key embedded in it and there’s a corresponding DH private key on the server.

Assume that the client is not using certificate authentication and trying to establish a connection with the server using a static DH cipher suite e.g. TLS_DH_RSA….  we would have  ephemeral-static DH variant (I would map that to client-server respectively).

And now my questions:

It is said that Alice and Bob publicly agree to use a modulus $p$ and base $g$.  As it turns out $p$ and $g$ are values in the certificate, so is it safe to say that $p$ and $g$ is  always dictated by the server? What if client certificate is used ?
Continuing if the server sends its public component (is that really the server’s public DH key) and uses its private component (is that really the server’s private DH key?)  what does the client do? Does it generate an ephemeral pub/private DH key pair on the fly  and sends / uses its public key and private key in the same way as the server?
Continuing on the last question, does such a setup not provide PFS because the server uses static values ? If I record a 100 of TLS conversation in such a scenario, would the private DH key from the server allow me to decrypt all of them?

Preliminarily, your question and this answer only apply to TLS versions through 1.2. TLS 1.3 no longer has any static Diffie-Hellman, and also no longer has ciphersuites that include/determine the key-exchange and authentication method(s) at all.

  It is said that Alice and Bob publicly agree to use a modulus p and base g. As it turns out p and g are values in the certificate, so is it safe to say that p and g is always dictated by the server?

Depending what you mean by 'dictated', maybe. The server and/or its operator(s) may have been subject to constraints. It is possible to choose DH parameters (p,g[,q]) which are insecure, either by mistake (e.g. a bug) or deliberately/maliciously, and it is very difficult to detect that insecurity (especially if deliberate) by looking at the parameters.
To prevent this authorities sometimes require(d) use of pre-vetted and often standardized parameters, such as the DH groups created for IKE (IPsec) in RFC2409 and RFC3526, some of which are also used for SSH, or the recently-standardized groups for TLS (including 1.3) in RFC7919, and some people choose to use them even when not required.

The CA (and if applicable RA) that issued the certificate could be among those that impose constraints. Certainly some CAs do require certain sizes of RSA and DSA keys, and (standardized) curves for EC algorithms, and I recall hearing of some that required specified parameters for DSA.
Since I have never heard of any (real) CA issuing any DH cert(s) at all, it is entirely speculative what policies such a hypothetical, imaginary CA would have.

It is true however that the parameters are at least communicated or confirmed by the server to the client in the server's certificate in its Certificate message.

  What if client certificate is used ?

You said 'Assume that the client is not using certificate authentication' so it's not. If you change that assumption it depends what kind of key the client has certified.

If the client like the server has a cert for a DH key then that key must use the same parameters as the server's; see e.g. RFC5246 7.4.6. In that case the DH is actually static-static not ephemeral-static, and the ClientKeyExchange message is effectively empty; see 7.4.7.2.

OTOH if the client has (and the server requests/permits) a signing cert then the client still generates, sends, and uses an ephemeral key in the same fashion as without a cert, but signs the partial handshake (including ClientKeyExchange) with CertVerify; see 7.4.8.

  Continuing if the server sends its public component (is that really the server’s public DH key) and uses its private component (is that really the server’s private DH key?) what does the client do? Does it generate an ephemeral pub/private DH key pair on the fly and sends / uses its public key and private key in the same way as the server?

A DH keypair and both of its halves (private and public) is always relative to a set of parameters. Whether you view the keypair and/or keys as including those parameters, or simply being linked to them, is kind of philosophical. For comparison, this Q was assigned number 71581 by crypto.SX. It certainly is wrong to just call it question 71581, because there are lots of other questions in other places, including other Stacks, with the number 71581. But we could say this is question 71581 on crypto.SX, or this is crypto.SX question 71581 -- is one of those more correct than the other, and if so, why?

However, as Maarten explained in some detail on your previous Q, the designers of X.509 certificates (which TLS uses) chose to nominally separate those values: the parameters (for DH, at least p,g) are stored one place in the SPKI data structure, and the public key relative to those parameters, which is the constrained integer (or equivalently integer residue class) conventionally notated y or Y, is stored in a different though nearly adjacent place. But both/all parts must be present to use the key.

Coming back to Earth, the client either generates an ephemeral keypair (for the same parameters) or uses its certified, static keypair (for the same parameters) as answered above. For a static keypair it sends the Y value by sending the cert (which duplicates the parameters); for an ephemeral keypair it sends the Y value in the ClientKeyExchange message (and does not need to send the parameters). In all cases both peers do the DH computation using their own X and the peer's Y, and then proceed with the rest of the TLS key deriviation process.

  Continuing on the last question, does such a setup not provide PFS because the server uses static values ? If I record a 100 of TLS conversation in such a scenario, would the private DH key from the server allow me to decrypt all of them?

Yes. If the server uses a static key for key agreement, compromising it allows decrypting prior sessions which used that key. That is one reason these key exchange methods were practically never used in the protocols where they existed, and have now been removed. As an example OpenSSL did not implement any static-DH for decades, from its creation (as SSLeay) in the 1990s until 1.0.2 in 2014, and then removed it (along with static-ECDH) when the state machine was redesigned in 1.1.0 in 2016; during much of that time I subscribed to their support maillist and never saw a single question, request or complaint about this lack.
For completeness, forward secrecy is also lost if the client uses a static key, but that can only occur if client-auth is used which it rarely is even with key exchanges which are used unlike static-(EC)DH.


What's is the simplest possible example of using cryptography to sign a message? I am interested in explaining to a total layman the basics of how a network can know that you are authorized without having to compromise your private key.

Using an example consisting of simple primes that anyone could understand, what is the best way to illustrate this?

It will be a bit of a journey to get to the answer for your question, but check out Khan Academy's crypto series: https://www.khanacademy.org/computing/computer-science/cryptography
They do a nice job of explaining how all the maths work with pretty small numbers. Even colors, which is an awesome analogy.


Detecting steganography by analysing non-significant data entropy? I am not thinking only steganography in images, I think it is also possible to encode data for example into the length of spaces of a clear html text.

I suspect, the steganography changes (elevates) the entropy of the non-significant part of the messages.

But:

How to detect in the general case, what is "non-significant"?
Sometimes the hidden content has also a low entropy, while "clean" content can have also high.

For (1): Afaik, it is impossible, the only possibility would be to use some application-level decoding and interpretation.

For (2): I think, there is (should be) some type of correlation between the entropy (complexity) of non-significant part and the significant part of the carrier content, too. Some type of uncommon deviation could be maybe detected.

Does such technique, algorithm already exist?

You cannot detect the use of steganography without taking into account the inherent variation in the protocol. Of course, you should be able to detect bad steganographic practices that operate outside the normal limits - you don't expect huge swaths of whitespace in HTML - but well applied steganography should be hard to detect by definition. So I agree with your evaluation of (1).

Entropy is not complexity. Pi may be considered complex if you try to estimate the value of subsequent digits (in whatever base) without using the common methods to calculate Pi. A common X.509 certificate is rather complex, but only the modulus (of the public key within the certificate) and signature may contain entropy.

Furthermore, I don't see how complexity of the significant part and non-significant part are necessarily related in any way. Take the certificate: you can easily re-encode it using XML encoding rules. Now generally a converter doesn't add any whitespace. However, a simple XHTML file may contain a lot of whitespace placed almost randomly between tags as it may be human generated.

As there doesn't necessarily seem to be a correlation, it would be impossible to create a generic algorithm that could detect steganography. Of course, heuristics can be used, but given that the amount of variation is unknown it advance, there must be either false positives, false negatives or both given any protocol that allows variation and any steganographic practice.

So I don't agree with your assessment of (2), and in my opinion, no generic algorithm should be possible to exist. Proof: take a protocol that randomly adds a space or tab character, ignored by the receiving party. Replace these by a CPA secure ciphertext, bit by bit. Now both the original data and space/tab encoded ciphertext should be completely random to an adversary.


Where can I find NIST SP800-38E's Test vectors? I am implementing XTS-AES mode in NIST SP800-38E, But I didn't find test vectors about it.

Who can help me?

Test vectors, as well as the requirements for validation testing, are currently available here:

https://csrc.nist.gov/Projects/cryptographic-algorithm-validation-program/CAVP-TESTING-BLOCK-CIPHER-MODES

By the way, this was literally the first result for a google search of "XTS-AES test vectors"


How can Bob validate Alice’s certiﬁcate? Suppose that Alice has a certiﬁcate CA1 << Alice >> issued by the certiﬁcation authority CA1, and Bob has a certiﬁcate CA2 << Bob >> issued by a diﬀerent certiﬁcation authority CA2.

It is known that CA1 possesses a certiﬁcate CA2 << CA1 >> issued by CA2. How can Bob validate Alice’s certiﬁcate CA1 << Alice >>?

I think CA2 is the root authority but I’m not sure how to proceed with this problem.

As CA2 << CA1 >> is a certificate it seems that CA2 is indeed a root certificate. This is not strictly necessary; CA2 just needs to be trusted by Bob.  CA2 << CA1 >> is then an intermediate CA certificate for cross certification.

To verify the certificate you need to verify the certificate chain. So the CA2 certificate is trusted, which verifies CA2 << CA1 >>, which finally verifies CA1 << Alice >>. This is performed by retrieving the public key within the parent certificate of the issuer and then use that to verify the signature of the child certificate of the subject. Besides verifying the signature over the "To Be Signed" part of the certificate you may also need to validate properties such as  validity period, key usage and so on.

Generally if there are two separate CA's that need to trust each other then the trust is established by issuing cross certificates: special intermediate certificates that establish the trust. These certificates may have additional properties that establish the type and level of trust. Here is an explanation of the trust relationships, unfortunately without the intermediate certificates being shown.

The cross certification certificate is placed next to the original certificate in the trust chain. So while you have C1, C1 << Alice >> as the original chain you would have another chain C2, C2 << C1 >> (replacing C1) and finally C1 << Alice >>.


Can any one explain why circuit privacy is needed on homomorphic encryption? I know some works have been done in the context of cirrcuit privacy on homomorphic encryption, where from an output ciphertext it does not allow
 someone to distinguish what function is computed.

I wonder the need of this functionality. If we use a cloud server to delegate some tasks over encrypted data, then the cloud can know what kinds of function is being evaluated (possibly from binary code or cpu behavior).

And, if some specific company delegates task to the cloud server. Then the server can infer what's going on and what types of data is being processed.

In this case, circuit privacy does not make sense for me.

When we say circuit privacy, we actually mean that the distribution over the result of the computation is the same (statistically close) to the distribution over an encryption of the result. This is needed because typically the party computing the circuit has its own private input and we need to protect this. However, if you are using FHE to just offload computation to a cloud in a private manner, then you not need circuit privacy. Rather, circuit privacy is needed when multiple parties with private inputs collaborate to compute an output.


How RSA-OAEP decrypt a Symmetric Key message? In an RSA-OAEP encrypted symmetric Key (AES for example) message. The message is then decrypted by the other party when R is a Random Number That other party doesn't know about. so How it can retrieve back the key when it's XORed with A Hash (hash1) That it doesn't know. I don't think that output of Hash2 helps with anything. Right?

OAEP is Optimal asymmetric encryption padding for RSA and developed by M. Bellare, P. Rogaway, in 1995 and standardized in PKCS#1 v2 and RFC 2437.

Optimal Asymmetric Encryption -- How to encrypt with RSA. Extended abstract in Advances in Cryptology

Your image hiding some internals of the OAEP. Here a better one;

The MFG is Mask Generation Function is expected to be a random oracle. The MFGs are similar to a cryptographic hash function except that while a standard hash function's output is a fixed size, the MGF supports output of a variable-length.
If OAEP is developed after the XOF (Extendable Output Functions) then the proof will be much easier.
Back to your question

How it can retrieve back the key when it's XORed with A Hash (hash1) That it doesn't know. I don't think that the output of Hash2 helps with anything. Right?

We can formalize above as;
\begin{align}
T &= lhash \mathbin\| PS \| \texttt{01} \mathbin\| Message\\
maskedDB &= MFG1(seed) \oplus T \\
maskedSeed &= MFG2(maskedDB) \oplus seed\\
\end{align}
In the PKCS#1 standard, the same MFG is used as the random oracles. I've made a distinction by numbering. $MFG1$ is taken the $seed$ as input.
Now, you got a message that is sent to you by RSA-OAEP. You get the $maskedSeed$ and $maskedDB$
The $seed$ can be calculated by
$$seed = maskedSeed \oplus maskedDB$$ and now we know the $seed$.
Now the $T$ can be computed by
$$ T = MFG1(seed) \oplus maskedDB $$
Now get the encoded $message$ block and check it.
$$T = lhash \mathbin\| PS \| \texttt{01} \mathbin\| Message$$


Examples of Weak Cryptography being exploited in the wild by cybercriminals? As a theorist, I often motivate the need for strong cryptography via simplistic methods, such as "If this did not exist, your online bank transactions would be vulnerable". This is of course true if "this did not exist" means that we are in Minicrypt (or some weaker "world"), but I also sometimes use this to motivate switching off of particular weak cryptographic primitives.
In this setting, it seems like social/legal conventions would mitigate the potential harm to the user --- for example, simple ways to attempt to leverage the total break of a cryptographic primitive (say transferring a ton of money into your personal bank account) would easily be undone through legal avenues.
In truth, I suspect that most of the hypotheticals that I can think of for how to nefariously exploit a broken cryptographic primitive in the wild would be easily reversed by law enforcement (perhaps I am just a bad cybercriminal though).
That, coupled with my perception that "most" cybercrime does not rely on breaking the "actual" cryptographic primitives that are used (and rather implementation errors/social engineering), makes me curious if cybercriminals have ever attacked underlying cryptographic primitives as part of their criminal enterprise.
I would be most interested in novel attacks / attacks against primitives that were thought to be strong beforehand, but as I suspect these do not exist I would also be interested in attacks against primitives that are known to be weak, provided they were against some notable company (where "notable" essentially means "something an average person may have heard of").
I want to exclude attacks by governments in this question, as these (especially via the NSA) tend to be fairly well-documented already, and seem to mostly sidestep the "law enforcement could/would undo the damage" argument.

I would also be interested in attacks against primitives that are known to be weak, provided they were against some notable company (where "notable" essentially means "something an average person may have heard of").

The first example that comes to mind in TJX's use of WEP 5 years after the break was announced; that lead to millions of credit cards being stolen.


Length of a Challenge in Challenge and Response Protocol Lets consider a challenge and response protocol with the following setup.
Two entities $A$ and $B$. $A$ is generating the challenge and $B$ is generating the response using a digital signature scheme. Lets suppose, that $A$ already has the certificate of $B$. So the procedure is as follows:

$B$ wants to access some service, that $A$ provides.
$A$ would like to know whether $B$ is authorized. Therefore, $A$ generates a challenge ch and sends it over to $B$.
$B$ is generating a response, by signing the ch with its private key and sending the signature over to $A$.
$A$ verifies the received response using the public key inside the available certificate.

This is just a common challenge and response procedure.
Question: How long shall the challenge be? If the challenge is to small, it repeats in a short amount of time. Are there any common methods that are "good-practice" in order to determine a suitable length?
Does this have anything to do with the security level of 128-bit that shall be satisfied in any case?

If your challenge is random bits, the security level is about $2^{bitlen}$, but since you are using it in challenge response you might want to avoid collisions as you said, especially if $O(2^{bitlen/2})$ storage is feasible, so you should set the length about twice required security level. But since you will likely be using pseudo-random numbers, your actual entropy won't be higher than its seed. For example, if the seed is just 64 bits, even if you produce 1K long sequence, we can expect collision in about four billion challenges since PRN generators produce a sequence deterministic to the seed which an attacker who is recording can replay using someone else's signature to complete authentication. But $k$ bit long seed from some source of entropy does not necessarily mean $k$ bits of entropy if the source of entropy used for seeding is not very good. And the PRNG must be cryptographically strong as well. In a nutshell, assuming cryptographically secure PRNG, you can expect repetition as you said in about half the actual bit entropy of the seed.


XTS-AES key management XTS-AES uses two keys $(k_1, k_2)$, which are obtained from a concatenated key $k$. Does this key $k$ remain same for the whole disk or changes per sector?

To answer the question we first need to take a quick look at how XTS encrypts data:

$$C=E_{k_1}(P\oplus(E_{k_2}(n)\otimes\alpha^i))\oplus(E_{k_2}(n)\otimes\alpha^i)$$

With $\oplus$ denoting bitwise XOR, $n$ denoting the sector index, $i$ denoting the block index within the sector. $\alpha$ is a polynomial in the $GF(2^{128})$ and is exponentiated appropriately and multiplied ($\otimes$) with the encrypted sector index.

As you can see you don't need to alter either the key $k_1$ or $k_2$ for each sector as the indices will introduce a unique whitening value for each block.


Can I encrypt data with multiple keys and decrypt with one? Can I encrypt data with multiple keys and decrypt with one? To be clear, I am not saying encrypt a file, decrypt it, then encrypt it again with a different key. I want to encrypt it, then encrypt it again, then again, maybe even again. I want to know whether I can use only one key to decrypt. The key can change though, it doesn't have to be the same key (in fact it shouldn't be).

I need a smart way to update the key to the new key, depending on how many times the data was encrypted. Also, the only way to get the new key is to have the old key... Is this possible? Is there an encryption algorithm that can be stacked multiple times and be decrypted by one key (and can I create that key)? Either this can already be done, or I am crazy--remember, I'm new to this...

Previously handled comments on StackOverflow:

  "What's the point of encrypting multiple times? Properly encrypted data is indistinguishable from random noise."

I'm not trying to make it more secure by doing this...

  "Do you want to perform E(k_n, msg) once with one of many possible keys then E(k_d,ciphertext) to get the ciphertext? Or do you want to perform E(k_1, E(k2, ... E(k_n,msg) ... ) ) as the encryption?

The latter, except I don't want to do encrypt with all keys all at once. I want E(k_1, msg) ... some time ... E(k_2, encrypted_msg) ... and so on, but I want to know if I can decrypt with one key after however many encryptions (and how to get that key).

  "Consider: 'I really want a smart way to update the key to the new key'."

Yes. And, of course, the encrypted file will change during the process.

Here is a candidate system, based on an ordinary message cipher $\mathcal E_\kappa(p)$ and $\mathcal D_\kappa(c)$ so that $\mathcal D_\kappa(\mathcal E_\kappa(p)) = p$ and $\mathcal E_\kappa(p)$ is indistinguishable from uniform random noise to anyone who doesn't know $\kappa$.

Let $k_i$ be the $i^\mathit{th}$ encryption key, let ${E^i}_{k_i}(x)$ be the $i^\mathit{th}$ encryption function, let $k$ be the decryption key, and let $D_k(x)$ be the decryption function.  We want to define $E^i$ and $D$ so that $$D_k({E^{n-1}}_{k_{n-1}}(\cdots({E^1}_{k_1}({E^0}_{k_0}(x)))\cdots) = x,$$ but otherwise we want all the intermediate ciphertexts, ${E^i}_{k_i}(\cdots({E^0}_{k_0}(x))\cdots)$, to be indistinguishable from uniform random noise to an adversary who does not know $k$ or the $k_i$.

To this end, define

\begin{align*}
  {E^0}_{k_0}(x) &= \mathcal E_{k_0}(x), \\
  {E^i}_{k_i}(x) &= x, &&\text{for $i > 0$.}
\end{align*}

Decryption is easy: the decryption key is simply $k_0$, and $D_k(x) = \mathcal D_k(x)$.

If this doesn't satisfy your needs, you will need to be more specific about what your needs are so that they meaningfully exclude this system.  ‘Meaningfully exclude’ implies that you have to give some reason related to your application why this won't work, rather than just say you don't like it and the $E^i$ functions have to actually do something.

In particular, it will be helpful for you to identify who changes the key and why.  Are you the sender and recipient, and are you changing your password because it got compromised and surgically removing all traces of the previous key derived from it and ciphertexts encrypted with it from all storage systems everywhere?  Are there multiple parties involved, like members of an organization who have split administrative functions to avoid unilateral power to doctor records?  What are you or they all trying to accomplish?  What is the adversary you hypothesize able to do to manipulate the resources they are trying to accomplish it with?  What do you want to make sure the adversary can't do?


Can the EdDSA signature scheme be customized with OpenSSL? EdDSA has currently two signature schemes: Ed25519 and Ed448.

Ed25519 is the EdDSA signature scheme using SHA-512 (SHA-2) and Curve25519

Ed448 is the EdDSA signature scheme using SHAKE256 (SHA-3) and Curve448

Is it possible to use EdDSA with a custom algorithm (signature scheme) for instance a different curve and a different hashing algorithm like SHA-1?
Is this not possible because of an RFC standard?
Are there any cryptographic reasons why OpenSSL does not provide EdDSA that use other curves?
Does this have to do with OpenSSL not having the feature implemented?

The first thing to clarify is the definition of “EdDSA”. EdDSA was introduced in Bernstein et al.'s High-speed high-security signatures in 2011. Various parameters it implicitly assumed were declared more generally in the 2015 paper Bernstein et al., EdDSA for more curves. This culminated in an RFC Edwards-Curve Digital Signature Algorithm (EdDSA), RFC 8032 from 2017.
All of them describe EdDSA abstractly and then instantiate it with a set of concrete parameters. Thus, Ed25519 and Ed448 are specific sets of parameters for EdDSA that form a concrete signature scheme that can be implemented.

Is it possible to use EdDSA with a custom algorithm (signature scheme) for instance a different curve and a different hashing algorithm like SHA-1?

Yes, this is possible, assuming you do not mean the specific instantiations in the first paper and RFC 8032.
In fact, the Monocypher cryptography library's crypto_sign() does exactly that, swapping out SHA-512 in favor of BLAKE2b.

Is this not possible because of an RFC standard?

As noted above, this is possible, but the result obviously wouldn't be able to be called “Ed25519” or “Ed448” because it'd be incompatible with those specific instantiations.

Does this mean that EdDSA is rigid by design?

It isn't, no. The 2015 paper even goes out of its way to add a bunch of.
EdDSA as specified in all of these documents is somewhat inflexible with regards to the underlying curve, however: It assumes that the cofactor $h=2^c$ has $c\in\{2,3\}$, which rules out prime-order Weierstrass curves for example. The required modifications to be able to not require $c$ with a prime-order curve are both trivial and obvious, but this specific set of permissible values for $c$ mandated by all specifications of EdDSA.

Does this have to do with OpenSSL not having the feature implemented?

No, nobody specifying EdDSA cared what OpenSSL does because that'd be putting the cart before the horse: OpenSSL can't implement EdDSA before it is specified.


Formula for bits of entropy per bit, when combining bits with XOR Assume that bits $A$ and $B$ each have .5 bits of entropy per bit.
The two-bit result of the concatenation $A‖B$ has 1 bit of entropy total, and it retains the entropy density of .5 bits of entropy per bit.
How many bits of entropy would the single-bit result of the exclusive-OR of $A$ and $B$, namely $A⊕B$, have per bit?
I'm guessing the formula is something like $\mathord{\mathrm{E}}(A⊕B)=1-(1 - \mathord{\mathrm{E}}(A))(1-\mathord{\mathrm{E}}(B))=.75$ bits of entropy per bit. Is this correct? If so,  is there a short proof of this equation that I can refer to?
Also, do I correctly interpret that you can only approach 1 bit of entropy per bit by XOR-ing bits of less dense entropies but never actually attain it?

Assume that bits $A$ and $B$ each have .5 bits of entropy per bit.

Fair enough (and I'll assume that we're talking about Shannon entropy)

The two-bit result of the concatenation $A‖B$ has 1 bit of entropy total, and it retains the entropy density of .5 bits of entropy per bit.

Not so fast.  The concatenation has between 0.5 and 1 bits of entropy.
The issue is that the bits may be correlated; if the bits are always exactly the same (or exactly the opposite), the concatenation will never have any more entropy than just one of the bits.  If the bits are independent (that is, are uncorrelated), then the concatenation will have 1 bit total.  If they are partially correlated, then the entropy will be somewhere between 0.5 and 1.
This is not a pedantic point; when computing the joint entropy of several events, one always needs to be aware of the possible correlations between these events.

How many bits of entropy would the single-bit result of the exclusive-OR of $A$ and $B$, namely $A \oplus B$, have per bit?

This is a somewhat more complicated situation; if we compute the probabilities involved with a source generating a single bit with 0.5 bits of entropy, well, that's the solution to $p \log_2(p) + (1-p) \log_2(1-p) = -0.5$, and those solutions are $p = 0.110028...$ or $p = 0.889972...$.  When we translate that into the possible entropies of the xor, that has a low of 0 (if the bits are perfectly correlated) to a maximum of 0.760269... (which happens if neither bit are in their low probability state at the same time); if they are uncorrelated, the entropy is 0.713537...
These values were computed by taking the above $p$ values, deriving the corresponding probabilities of the xor, and plugging them into the Shannon entropy formula.

I'm guessing the formula is something like $\mathord{\mathrm{E}}(A⊕B)=1-(1 - \mathord{\mathrm{E}}(A))(1-\mathord{\mathrm{E}}(B))=.75$ bits of entropy per bit. Is this correct?

No, it's not correct (even if we assume independence), at least if $E$ is the entropy function and not the expectation.  I'm not sure if there is a simple formula that gives you that; if $p$ is a solution to $p \log_2(p) + (1-p) \log_2(1-p) = -E(A)$, and $r$ is a solution to $r \log_2(r) + (1-r) \log_2(1-r) = -E(B)$, then the Shannon entropy formula applied to $A \oplus B$ would involve the term $\log_2( p \cdot r + (1-p) \cdot (1-r))$, and there's no immediately obvious way to simplify this term, or combine it with other terms.

Also, do I correctly interpret that you can only approach 1 bit of entropy per bit by XOR-ing bits of less dense entropies but never actually attain it?

Oddly enough, with the right amount of correlation, you can actually get 1 bit of entropy.  Consider the case where both sources generate a 1 with probability $0.25$ (and so have $0.811278...$ bits of entropy).  If they never both generate a 1 bit at the same time, then the probability that exactly one of then generate a 1 bit is $0.5$, and so the xor does yield an entropy of 1.
Of course, if the input bits are uncorrelated, then you are correct (unless one of the input bits already has an entropy of 1).


Are there any known weaknesses with ElGamal algorithm? I am working on a messaging system and plan to use ElGamal asymmetric encryption to protect the message contents during storage and transmission. (This would be in addition to TLS used during transmission.) What I want to know is if there are any inherent weaknesses in the ElGamal algorithm that I should be aware of or guidelines to the key bit size.

Assumptions:

Messages will be short, so performance is less of a concern.
Keys (and the associated user accounts) are disposable (short lived).
Message retention will be minimized (days, not weeks or months).
Messaging will be asynchronous as users are not expected to be online at the same time. (This is the main reason that I have ruled out the typical D-H key exchange to generate a shared, symmetric key.)
Private keys will never leave the client device.
Public keys will be stored in a database with the anonymous user account consisting of a username and hashed password.
Using libgcrpt.

A Diffie-Hellman exchange needs not be synchronous. In DH, each party has a private key (x) and a public key (gx mod p). If the sender knows the recipient's public key ga, then he can build his own key pair (b and gb), compute the shared secret (gab), and send both his public key (gb) and the encrypted message (symmetric key derived from gab) to the recipient. This works for asynchronous messages: the recipient needs not do anything at message sending time. This kind of processing is used in, for instance, S/MIME for encrypted emails, and it works.

The difference between DH and asymmetric encryption (like ElGamal or RSA) is only that in the case of DH, the sender does not get to choose the exact value of the shared secret, but that's fine as long as that secret is only used for symmetric encryption.

In fact, even if you use asymmetric encryption (ElGamal, RSA...), you still want to use it to encrypt a randomly generated symmetric key, and use that key with a symmetric encryption algorithm to process the actual data. Indeed, asymmetric encryption algorithms are quite limited in the size and format of what they could send.

That being said, ElGamal, as an asymmetric encryption algorithm, is fine as long as it is used properly. Notably, ElGamal is homomorphic (given the encryption of x and the encryption of y, one can from the outside compute the encryption of the product xy), which is a nice property in some cases, but can be bothersome in other conditions. A safe method to do ElGamal encryption is to, indeed, use it only to encrypt a random symmetric key, at which point there really is no advantage over a simple Diffie-Hellman.

"Proper usage" really means that you should not just slap together a few cryptographic algorithms; such an assembly is a delicate matter, and should be done only as part of a fully specified and analysed protocol. For instance, OpenPGP, which is implemented by GnuPG (an opensource library from which libgcrypt was derived). Indeed, OpenPGP supports ElGamal encryption, and does it "properly" (it uses ElGamal because that protocol was defined at a time when RSA was still patented, but ElGamal was not -- this no longer applies nowadays).

So that would be the "guidelines": follow OpenPGP; even better, save time and use the GnuPG implementation directly. Code which is easiest to design and implement is code which has already been designed and implemented by somebody else.