ISO 9797-1 MAC Algorithm 3 and Doc 9303-11 I am trying to write a python script to access the IC in an eMRTD as per ICAO Doc 9303. Everything is going swimmingly until I come to the part where I need to calculate a MAC using ISO 9797-1 Algorithm 3 (padding mode 2).

In Appendix D-3, the MAC of E.IFD 72C29C2371CC9BDB65B779B8E8D37B29ECC154AA56A8799FAE2F498F76ED92F2 using K.MAC of 7962D9ECE03D1ACD4C76089DCE131543 is meant to return 5F1448EEA8AD90A7.

However, when I calculate the MAC, it returns AAE3F35132ED3465. This is the return when I run through the steps step-by-step using pyDes (ECB mode and manually xoring as appropriate) and when I use the code as written here.

I am clearly missing something - would love any help!

I need to calculate a MAC using ISO 9797-1 Algorithm 3 (padding mode 2)

and the context makes references to 3DES (as confirmed by the 8-byte width of the result without mention of truncation, and the fact that all bytes of the test key 7962D9ECE03D1ACD4C76089DCE131543 have odd parity).

ISO/IEC 9797-1:2011 (revising the 1999 edition) specifies MAC algorithms based on an iterated block cipher with CBC chaining, along the general structure of CBC-MAC. With Algorithm 3, the structure is:

The standard has a Padding Method 2 (not "padding mode 2") where a single 1 bit is appended to the input, then just enough 0 bits (possibly none) to reach a multiple of the block width. Since the input is 32-byte, there are four 8-byte blocks and a last padding block mx of 8000000000000000.

We get F97B82EC7727D582 after the fourth encryption, then 797B82EC7727D582 after XOR of the padding block, then 5F1448EEA8AD90A7as the result.

Caution: there is an attack on this MAC Algorithm 3 recovering the key with the order of $2^{32}$ MAC queries of short messages to find a collision, followed by in the order of $2^{57}$ offline DES operations to recover K1, then K2.


Given a secret - how does one generate a reproducible private key from it? Let's say I have a secret "hitheremynameisbob"... I'd like to use this to encrypt/sign things. Is this possible or is it always expected to generate random secrets?

Yes, generating private keys from passphrases / passwords is possible.1

However, I strongly advise against basing your public key exclusively on your password and not proper (pseudo)randomness.

If you publish your public key, everybody will be able to brute-force your password which will allow for passive decryption (encryption keys), identity theft (signature keys) or impersonation (signature keys / password re-use).

So let's get into the technicalities.

What ever the methods say here. Always pre-process the password with the strongest password-based key deriviation function you can find (eg Argon2, you may have to turn the salt off for this).
If your preferred library has a plug-in architecture for the RNGs, you can just replace the RNG with a contruction which is deterministic in your password input. AES-CTR would be a good example here.
If not, your best bet is to restrict yourself to discrete-logarithm-based cryptography where the private key literally is just an integer, which you can get trivially from the transformed password. From there you use static group parameters and generate the public key on-the-fly as usual.

1: Bitmessage for example allows you to do that


Has a Two Key TDES encryption ever been successfully attacked? Is there any known instance of a Two Key TDES ever being successfully attacked (in real life), when the key is used to encrypt less than $2^{20}$ words?

If we talk about key search attacks (rather than key compromise or/and side-channel attacks), the answer must be no, for the best known method is impractical.

On the other hand there has been numerous successful key-recovery attacks against devices using TDES, including on some that try hard to avoid it. One example here, another there.


Does Rabin function lose its one-way property if squaring mod a prime? I am looking into various one way functions and I stumbled upon a Rabin function, which is squaring modulo an RSA modulus $N=pq$, where $p,q$ are prime: $R_N(x) = x^2 \mod N$.
Would it lose the one-way property if $N$ is prime and not a product of two primes?
UPD: Also, is Rabin function still one-way if factorization of $N=pq$ is known?

Would [$f_N(x)=x^2\bmod N$] lose the one-way property if $N$ is prime and not a product of two primes?

Yes, thanks to the Tonelli-Shanks algorithm (special cases here).

[Is] Rabin function still one-way if factorization of $N=pq$ is known?

No, because the main ("only") information advantage the private key holder has in the Rabin cryptosystem over the public key holder is the factorization of $N$. If the one-wayness was preserved even under known factorization the system wouldn't allow decryption in its normal form.
The way to see how factorizing allows square roots in this scenario is to remember that the chinese remainder theorem establishes a ring isomorphism between $\mathbb Z_N$ and $\mathbb Z_p \times \mathbb Z_q$ ... and as established above we know how to compute square roots in $\mathbb Z_p$.


Speck with signed math I find myself implementing Speck in an industrial controller that only does signed math.

What cryptographic ramifications would there be if the Speck algorithm was implemented using signed math?

There are a number of things to watch due to signed arithmetic:

If the hardware was not using 2's complement arithmetic (representing range $[-2^{k-1},2^{k-1})$ on a $k$-bit word, with negative integer $x$ represented as $x+2^k$ is in binary), then it would be difficult to use the full word width $k$. It would then likely be a better idea to keep everything non-negative and less than $2^{k-2}$.
That is easy for Speck-$n$ (where $n$ is the block width) when $k\ge n/2-2$. E.g. for Speck-32, $k\ge18$ allows to compute $(x+y)\bmod 2^{16}$, as required, using (x+y)&0xFFFF, without depending on the representation of negative numbers.
Or, another option is using multiple-word arithmetic. That's what a compiler does on an 8-bit CPU to implement wider arithmetic types, and how large integers are usually implemented in asymmetric cryptography. It reduces speed and increases code size by a factor like 3 when going from one to two native words, thus is best avoided.
Fortunately, 2's complement arithmetic is common. That would make Speck-$n$ with $k=n/2$ feasible without multiple-word arithmetic, baring the next issue.
Some industrial controllers detect overflow (e.g. when $2^{k-2}+2^{k-2}$ is attempted). When using words to their full width, overflow will occur often, and its detection should be disabled. An alternative is to avoid overflow by keeping everything non-negative and less than $2^{k-2}$ as above.
Speck requires rotation by constants, often implemented with a combination of left and right shift followed by bitwise OR, e.g. For Speck-32 (x>>13)|(x<<3). Right shift by $b$ positions on signed variables sometime replicates the sign bit $b$ times rather than introduce $b$ zero bits. That would require extra masking, e.g. ((x>>13)&7)|(x<<3). With $k>16$ make that ((x>>13)&7)|((x&7)<<3) when needing to avoid negatives and overflow.

To watch also, but not directly related to signed arithmetic:

Speck is a block cipher, thus needs an operating mode to become a cipher, and for more than a single use a True Random Number Generator to generate its IV (or at least persistent storage for a counter), before it can be used to encrypt arbitrary data.
Most of the time, when encryption is thought, integrity/proof of origin is functionally needed also (sometime, only). That's authenticated encryption, and while it can be implemented with a block cipher, there are a few catches.
Industrial controllers need to be reliable, not fast. Speed might be an issue, especially if multiple-word arithmetic has to be used due to signed arithmetic.
For security, the implementation should have execution time independent of data if an adversary can time execution (which should be the default assumption), and a number of things (like overflow detection, and more) could introduce timing dependencies.
Industrial controllers are usually not designed to keep secret the data they manipulate; I've met one (emulating relay logic) that blinked a led according to the state of its (one-bit wide) data register! And there could be much more subtle side-channels.


RSA Optimal Asymmetric Encryption Padding Beginner I'm new to the OAEP scheme.
I learn it from the Wikipedia page. Link
The page does not explain a proper setup for of the system.
So I'm not sure if the output of the padding scheme which contains two components X and Y (X||Y) is going to be the input of the RSA encryption? Or is there something that I'm missing?
Many thanks.

Yes, (Optimal) "Asymmetric Encryption Padding" means padding for asymmetric encryption which in practice means RSA encryption. The padded block is then RSA-encrypted, and on decryption the RSA-decrypted block is unpadded.

The drawing and description in Wikipedia is based on the original Bellare and Rogaway paper (link '1' from Wikipedia). The scheme actually used is specified in PKCS#1 and differs in a few details that don't affect security, but do matter for interoperation if that's your goal, or just exact understanding, and also uses somewhat different (but equivalent) notation.

The exact process is laid out in detail in PKCS#1 v2.0, republished conveniently as RFC2437 (linked from wikipedia), or the updated v2.1 republished as RFC3447 (linked on the IETF website), or the even newer v2.2 (only on the former RSA-labs site which is now EMC and every time I look they've reorganized it so just google). See 7.1.1 for pad-encrypt and 7.1.2 for decrypt-unpad.


Why do you need padding block at the end of Merkle damgard if the input is multiple of block length? Why do you need padding block at the end of Merkle Damgard if the input is multiple of block length? I learned that it was not collision resistant if a dummy block is not added to the end but I want to understand why this is the case.

Let's say MD outputs Zb instead of H(Zb||L). What is the reasoning for why this particular construction isn't collision resistant?

Let's say we have a message $m$ whose length is not a multiple of the block length, and that our hashing scheme pads it to a multiple of the block length by appending the padding $p_m$ to it.  That is to say, $$\textsf{Pad}(m) = m \,\|\, p_m,$$ where the length of $m \,\|\, p_m$ is a multiple of the block size.

Now, if messages whose length was a multiple of the block size were not padded at all, consider what would happen if one deliberately tried to hash the modified message $m' = m \,\|\, p_m$.  Since the length of $m'$, by construction, is a multiple of the block size, we'd have $$\textsf{Pad}(m') = m \,\|\, p_m = \textsf{Pad}(m).$$

And since the final hash value is calculated from the padded message, this would mean that $m$ and $m'$ would have the same hash value.


How measurement error works in PRNG operation? Suppose, I have PRNG with seed key length of $|K_s|$ and output sequence length of $2^{|K_s|}$, so the complexity of the PRNG is of the order of $2^{|K_s|}$. Now, if there is any measurement error in the output of the PRNG, how this measurement error works in the overall complexity of the PRNG?

Unless the measurement error is huge (e.g. you read every bit correctly with probability $p = 0.5$), it doesn't add significantly to the work required to find the key.

To give a concrete example, let us consider a measurement error where we read each bit correctly with probability $p = 0.75$ (and for simplicity, let us assume that the errors are independent of each other, and whether the correct bit was a 0 or a 1).

Then, what the attacker can do is cycle through every possible key, and generate the first 1000 bits of the PRNG with that key, and check if at least 600 of those bits agree with the first 1000 bits of the noisy sample he was given.  With extremely high probability, the correct key will generate a sample with that many bits set, and no incorrect key will.

This procedure still takes $O(2^{|K_s|})$ time, and so all you've done is increase the time required by a constant factor.


Decrypting a vigenere cipher with a reused one-time pad I understand that when a plaintext is encrypted with a key of the same length, it is referred to as a one-time pad. Now when this key is reused to encrypt another plaintext, there is potential for decryption of the original ciphertexts.

Following on from the question asked here, Taking advantage of one-time pad key reuse?, the ciphertexts there were retrieved via a Vernam cipher:-

$ciphertext = plaintext \oplus key$

which gave rise to the following relationship between the two:-

$ciphertext_1 \oplus ciphertext_2 = plaintext_1 \oplus plaintext_2$

If instead of a Vernam cipher the encryption is carried out via a Vigenere cipher, where I have two plaintexts and a key, all three of which are the same length - is it possible to draw any relationships like the one above, from the resulting ciphertexts, when I do not know what the plaintexts and key were?

The crib-drag attack applies with a different operator.

p1 = AtextencryptedByFirstPassword
p  = HelloHelloHelloHelloHelloHell
c1 = hxpihlrncmwxpopfjtcgatldgdsco

p2 = ASecondEncryptedTextBySecondPassword
p  = HelloHelloHelloHelloHelloHelloHelloH
c2 = hwpncuhpyqycaeskxpihicdpqvroaozwhzfk

When you $c_1 - c_2 \bmod 26$ you will have the same problem as many-time-pad. This subtraction will remove the key.

 c1[i] - c2[i] = p1[i] - p2[i]

But this time instead of $\oplus$ we will have plus modulo 26.

 c1 - c2 = azafvjqcwecflqdfowgbijsmkszmm


How to construct a strong Fiat-Shamir in zero-knowledge proof? I'm new to zero-knowledge proof. Recently, I'm implementing a non-interactive zero-knowledge proof using the Schnorr scheme. I understand the non-interactive zero-knowledge proof needs random oracle for a prover to generate a proof along with a hash. Others suggested that I need to use Strong Fiat-Shamir to generate the hash.
Could you please give me some points about how to use and implement the strong Fiat-Shamir?  What should be included in this Hash?

Quick remarks:

the Fiat-Shamir transform is implemented with a standard hash function (e.g. SHA-256 or SHA-3). Random oracles do not exist in the real world: it is only in the security analysis that the real hash function is modeled as a random oracle to get heuristic guarantees about its real-world security.
In most $\Sigma$-protocols (Schnorr included), the prover first generate a commitment (in Schnorr, this is something like $g^r$). Fiat-Shamir is then used to generate the verifier challenge non interactively by hashing something the prover has. Strong and weak Fiat-Shamir usually refer to the following alternatives: either the prover hashes only the commitment (e.g. $g^r$, this is the weak Fiat-Shamir - avoid it) or she hashes both the commitment and the statement (e.g. $(g^r || g^x)$ if you use Schnorr to prove knowledge of the discrete logarithm of $g^x$, this is the strong Fiat-Shamir - use it).

As for why these differences matters: in some scenarios (typically, when the prover can choose the statement adaptively in the larger context where the zero-knowledge proof is used), the weak Fiat-Shamir transform is provably insecure. This is discussed for example in this paper.


Graphically representing points on Elliptic Curve over finite field I have taken elliptic curve $E\colon y^2=x^3-4x+20$, defined over $\mathbb{F}_{29}$.
The number of points on the curve, $\left|E(\mathbb{F}_{29})\right|=37$.

I took base point $P=(1,5)$, and got following results:

I want the results graphically to know the behaviour of the curve.

Is there any tool for this to show results graphically by giving input as curve points?

None of the above answers see the mistake in the question. The point $P=(1,5)$ is not on the curve $E\colon y^2=x^3-4x+20$ over $\mathbb{F}_{29}$. To see this, place $x=1$ and $y=5$ into the curve equation.
\begin{align}
5^2&=1^3-4+20\\
25& = 1-4+20\\
25& \neq 15\\
\end{align}
Therefore $P = (1,5)$ is not on the curve. But it is on the curve $E'\colon y^2=x^3\color{red}{+}4x+20$ over $\mathbb{F}_{29}$.
Now, let us continue to the second equation as $E \colon y^2=x^3\color{red}{+}4x+20$
The curve $E$ has 37 points; the below lists them in projective coordinates;
$[(0 : 1 : 0), (0 : 7 : 1), (0 : 22 : 1), \color{red}{P =(1 : 5 : 1)}, (1 : 24 : 1), (2 : 6 : 1), (2 : 23 : 1), (3 : 1 : 1), (3 : 28 : 1), (4 : 10 : 1), (4 : 19 : 1), (5 : 7 : 1), (5 : 22 : 1), (6 : 12 : 1), (6 : 17 : 1), (8 : 10 : 1), (8 : 19 : 1), (10 : 4 : 1), (10 : 25 : 1), (13 : 6 : 1), (13 : 23 : 1), (14 : 6 : 1), (14 : 23 : 1), (15 : 2 : 1), (15 : 27 : 1), (16 : 2 : 1), (16 : 27 : 1), (17 : 10 : 1), (17 : 19 : 1), (19 : 13 : 1), (19 : 16 : 1), (20 : 3 : 1), (20 : 26 : 1), (24 : 7 : 1), (24 : 22 : 1), (27 : 2 : 1), (27 : 27 : 1)]$
Visualizing a curve is easy when the curve is defined over the Rational Field.

Where all the arithmetic-geometric relation work almost flawlessly; that is $$P+Q-R$$ is on the same line;
When we turn in to finite field case, we have a discrete plot;

The blue line is drawn to show the symmetry since if $(x,y)$ satisfies a point therefore $(x,-y)$ ( in the plot $ = (x,29-y)$) also satisfies the equation.
Now we can see the point addition with $P=(1,5), Q=(5,7)$ and $R = P+Q = (16,2)$ is drawn on the figure.

The proof of the connection of this figure with the ECC point addition is performed by Fgrieu for this question : Must a line hitting two points on the elliptic curve over a finite field hit another point by continuation?
As we can see from these figures, the point of infinity is missing here. Consider the summation of $R$ and $-R$, there it should be $\mathcal{O}$ on the vertical line! nope!.
Another visualization is the Torus shape. Any rectangle image can be map into a torus shape.

This is a vector image with Asymptote and the points that cannot be seen directly are set to be opaque. This is calculated by ray-tracing. The $R$ and $-R$ on the background. This 3D can be best viewed within HTML. A snapshot from the bottom;

The HMTL is interactive, you can zoom and rotate in 3D, you can download it from Github and view it locally.


DES Crack simulation I wish to simulate an implementation of a DES Cracker using verilog. But every paper I read give only abstract hints but no concrete steps or how really to go about it. How is it usually done? For example for DES encryption there exists a sequence of steps with ordered connection of known blocks.

A DES cracker just tries out keys until a matching key is found.

So, with Verilog, you design a circuit which includes:

a counter, which enumerates possible keys in a fixed order;
a DES encryption engine, which, given a plaintext block and a key, computes the corresponding ciphertext block;
a comparison engine, which compares the ciphertext block obtained from the DES engine with the expected ciphertext block, and raises a flag if a match is found.

The outer system (say, the PC which controls the experiment) just has to measure the exact time at which the flag is raised, to infer the counter value at that time -- depending on the precision of the measure, this will narrow down the set of possible keys down to a few millions at most, and the PC can finish the work in a fraction of a second.

Of course, there are $2^{56}$ possible DES keys, which is a quite huge number. A complete DES cracking engine will include many copies of the DES encryption and ciphertext comparison engines, each engine exploring a given fraction of the set of possible keys (to some extent, counters may be shared).

If you read French, my PhD thesis contains a description of a DES-cracking engine with FPGA.


What is the difference between a 'cipher' and a 'mode of operation'? What is the difference between the term cipher (a name like RIJNDAEL) and mode of operation (like ECB)?

Aren't these both terms for the encryption/decryption technique?

A mode of operation is an explicit method by which we use a block cipher (eg AES) to do more than just encrypt one block of data. For example, it may allow us to encrypt multiple blocks of data (eg ECB,CBC etc), provide us with some authenticated encryption (eg GCM) or a method for encrypting disc storage (eg XTS).

Rijndael,DES etc are block ciphers. That means they provide a method for encrypting a fixed amount of data (in the case of AES, they encrypt blocks on 128 bits).

In practice, the amount of data you want to encrypt is often much larger than the block size. So, we either need to create more and more block ciphers of almost every size, or we come up with a way of using our block cipher to encrypt larger amounts of data.  This method is called a mode of operation.

To use the most simple case as an example, consider AES in ECB mode. ECB mode tells us that we need split our plaintext string into sections of 128 bits (possibly after some padding scheme). Then, each section is encrypted using AES, and the resultant encryptions are then concatenated to form our output ciphertext.
AES simply performs encryptions of the plaintext blocks we give it, whereas ECB allows us to encrypt arbitrarily large amounts of data.

For descriptions of many different modes of operation and a discussion of their merits/weaknesses, you might be interested in this paper by Rogaway, and section 2.3 provides his formalisation of a mode of operation.


Replacement for XOR in CBC? In CBC mode, the XOR operation is used to combine the previous encrypted block with the current plaintext, to be used as the block to encrypt. Apart from other known disadvantages inherent to the mode itself, usage of XOR creates a collision vulnerability, where if there's a collision in the output, and the plaintext block can be known or guessed, then another plaintext block can be exposed, as noted in this answer: https://crypto.stackexchange.com/a/14325

This is due to the fact that from $E_k(P_i\oplus C_{i-1}) = E_k(P_j\oplus C_{j-1})$, it is immediately obvious that $P_i\oplus C_{i-1} = P_j\oplus C_{j-1}$, and due to the properties of XOR, we have that $P_j = P_i\oplus(C_{i-1}\oplus C_{j-1})$, therefore by XORing the ciphertexts that precede the collision and the guessed/known block, we can obtain the other plaintext block.

Of course, many other operations have that same problem (modular addition or subtraction, for example). Is there any other operation or function that can replace XOR, to make CBC mode not be vulnerable to this flaw?

Edit: To make the question clearer, I'd like to know of a reversible operation/function $\circ$ that takes $P_i$ and $C_{i-1}$ as input, and for which it's computationally infeasible to find $x$ such that $P_i\circ C_{i-1} = x\circ C_{j-1}$ when $P_i$, $C_{i-1}$ and $C_{j-1}$ are known. I guess that some cipher function $F_k(p)$ for which $k$ and $p$ are both the same width where $k = C_{i-1} || secret$ and $p = P_i$ would fit that purpose, but are there other simpler choices?

And while I'm here, is CTR mode safe against this kind of flaw?

Without completely restructuring how CBC mode works, that would not appear to be possible.

Your generalized CBC mode encryption would be defined as:

$$C_i = Enc_k( P_i \circ C_{i-1} )$$

for some operator $\circ$ (which need not be commutative, or even associative).

What this means is that, during decryption, we have:

$$Dec_k(C_i) = P_i \circ C_{i-1}$$

To make decryption, that is, the recovery of $P_i$ feasible, we must have an easy way, given $A, B$, to find the solution $x$ for $A = x \circ B$.

In the problem you're asking to be infeasble, that is, $P_i\circ C_{i-1} = x\circ C_{j-1}$, if we set $A = P_i\circ C_{i-1}$ and $B = C_{j-1}$, we see that must also be an easy problem (otherwise decryption would be difficult)


Is there a name for this 'enhanced' caeser shift and if so, is it trivial to break? This cipher shifts the letter that it will shift to, after each shift...

I used to play with this when I was a kid. I was thinking about it recently and realized that it wasn't as simple as I thought. Here's the description:

  The second number makes the code much harder to break. It changes the number of letters above the letter to be replaced by a different amount each time. For example "a" will be subsituted by "b" (one place higher), "b" by "d" (two places higher), "c" by "f" (three places higher) and so on. Try changing the second code number in the code maker and see how much more difficult trying to break the code will be.

Source: http://web.archive.org/web/20120818085711/http://www.puzzlepixies.com/activites/activites/make-secret-codes.html

Is there a name for this type of shift?

So if I understand correctly, the following describes your cipher:

Take letters A-Z to be numbers 0-25.
Let Mi represent letter i of the message
Let Ci represent letter i of the ciphertext
Let n be the ceasar shift number
Let m be the skip number
Let the key be described as the tuple (n,m)
Then, Ci = (Mi + n + m*i) modulo 26

The system is a type of polyalphabetic cipher. The Trithemus cipher is the same as your system, but it always used a key of (0,1). Your system is also equivalent to a Vigenere cipher that uses a key that is the full alphabet, but rotated a skip number of letters.

I can't find any reference to historical use of this system, so very likely there is no standard name for this type of cipher.

This cipher is still easy to break, because there are strict limits on the numbers you can choose for the shift and skip.

The shift can only be from 0 to 25, because any higher numbers work the same as a number from 0 to 25.
The skip can also only be from 0 to 25, for exactly the same reason.
This means the total set of keys is 26*26 = 676

It's not hard to brute force 676 keys with a computer, but you usually don't have to. If you try all 26 skips, then you can figure out which skip is correct by doing a frequency analysis of the letters. The letter distribution that looks closest to the letter distribution of English is probably your skip. Then you just have to guess the shift based on the same frequency analysis you just did.


Securing content and login with "same" password I'm writing a client application that wants to store some secret information with a storage service. The client has to authenticate the user with the service and the service should not be able to decode the information that it stores for the user. Authentication against the service has to be based on username - password combination (I also can't use local storage to store encryption keys on the client).

I want to minimize the information the user has to memorize (willing to sacrifice some security but not too much for this). Ideally just username plus 1 password. Is there a well understood cryptographic scheme that allows me to do that?

If not how well would the following work (from a security perspective):

Client app asks user for username (U) and password (P) .
Using cryptographic hash H(), the client registers the user with the user name U and password H(P).
Client then encrypts the secret that is to be stored using some password based encryption (e.g. PBKDF2) using P.
Client then authenticates with the service using U and H(P) and uploads the secret information encrypted with P.

The thinking being that the server will only ever see H(P) and thus not be able to decrypt the secret (which requires knowledge of P) and also H(P) being a reasonable password for the service.

If you want to keep the crypto simple and mostly on the server side (which may be a good choice e.g. if you're developing a web service), you could use the following scheme:

To log in, the client sends the password $P$ to the server in clear, preferably over a secure channel (e.g. HTTPS).
The server derives a "master key" $K_0$ from $P$ using a key-stretching KDF (e.g. PBKDF2 or scrypt) and a salt $S$ stored in the database.  The length of $K_0$ should ideally match the natural output length of the KDF (e.g. 256 bits for scrypt or PBKDF2-HMAC-SHA256), and should be at least 128 bits.
The server uses a fast KDF (such as HKDF; note that extraction part of HKDF can be safely skipped, since $K_0$ is already a PRK suitable for direct expansion) to derive a verification key (i.e. a "password hash") $V$ of, say, 128 bits, which is compared against the corresponding value in the database to tell if the password is correct.  If it is, the server can use the same KDF to also derive additional key material, such as any number of file encryption keys $K_i$, from $K_0$.  After all necessary keys are derived, $K_0$ can and should be discarded.

Where desired and practical, the computationally intensive part of deriving $K_0$ from $P$ may equally well be performed on the client side.  However, $K_0$ should still be transmitted to the server over a secure channel, since under such a protocol it is still effectively a "password-equivalent authenticator".

Under this scheme, the server only stores $S$ and $V$ (and, of course, the encrypted files and any associated material such as IVs), which are not sufficient to recover $K_0$ or any of the file encryption keys.  A brute force attack on $P$ should be impractical due to the slow KDF used to derive $K_0$ from it; a similar attack on $K_0$ itself is infeasible due to the size of the keyspace.

The major and obvious weakness of this scheme, of course, is that a malicious or compromised server can still obtain $K_0$, and thus also any file encryption keys, when the user logs in.  Thus, while the user is safe from server compromises as long as they don't actively use the service, they do need to trust that the server is not currently compromised at the moment when they log in.

As long as the actual file encryption is done on the server, the weakness described above is unavoidable.  If this is not required, the obvious alternative is to perform the file encryption entirely on the client side (for which essentially the same key derivation process as described above may be used, just all done on the client) and in full control of the client (i.e. no running server-supplied crypto code on the client), and simply treating the server as a dumb file storage device.  The user can then be securely authenticated to the server using an augmented PAKE protocol such as SRP, possibly (but not necessarily) using the same password as for deriving the encryption keys.

Edit: ps. Even if the server can't be made to support SRP or some other augmented PAKE protocol (e.g. if the server runs some pre-existing software that you can't modify), a custom client could still securely store encrypted files on it by deriving both the file encryption keys and the server "password" (e.g. a 128-bit key, ASCII85 encoded for interoperability) from the user's actual password using a KDF as described above.  No matter how insecure the server may be, a compromise of the derived password will, at worst, allow an attacker to log into the server as the user, but it won't compromise the user's actual password or file encryption keys.

One difficulty here is that, without help from the server, there may not be any convenient place to store a salt for PBKDF2 / scrypt.  One way to work around that issue could be to derive the salt e.g. from the username and the server name; this is not ideal, but it's good enough for most purposes, especially if you also use a random per-file salt (stored as part of the encrypted file) when deriving each file encryption key from the master key.

In fact, even if you do store the salt on the server, it may still be a good idea to append the username and server name to it, since it can protect against some theoretical attacks (where a compromised server lies about the salt to find out if two users have the same password) as well as, more practically, against poorly implemented salt generation.


choices for k in binary finite field modular reduction algorithm In the Guide to Elliptic Curve Cryptography there's this algorithm:

My question is...  what is $k$? Is it just some random value we pick? If so are some numbers better than others?

$W$ is the size of the words we are operating on, and hence $u_k(z)$ is a precomputed polynomial for each bit of a word (note $0 \le k \le W-1$), defined as $z^kr(z)$. So if we have 32 bit words we have 32 precomputed polynomials, indexed by $k$.

Then, in the actual algorithm, at each step we compute $k$ as $(i - m) - Wj$, and use that value $k$ to select one of our precomputed polynomials, which we add to $C\{j\}$. So $k$ is not randomly selected, it is deterministically computed at each step of the algorithm and then used to select a precomputed polynomial.

As an example, if we are at a step where $i = 128, j = 2, m = 64, W = 32$ we would compute $k = (128 - 64) - 32  * 2 = 0$. So we would add $u_0(z) = z^0r(z) = r(z)$ to $C\{j\}$.


Third-party security issues with Shamir's secret sharing scheme In Shamir's secret sharing scheme, we are trusting a third party who generates the secret polynomial.

How can we ensure security here when we are involving a third party?

We simply have to trust this party because this scheme requires a trusted dealer (a party that distributes the shares to the secret to the participants - this can be you or some other party - but if its you you should trust yourself).

We can use verifiable secret sharing, that allows the parties to check whether the shares they have obtained are consistent, i.e. to verify if the dealer behaves honest (but the dealer still knows the secret and thus this is only a partial reduction of trust).

If we do not want to have a trusted dealer who sets up the shares at all, we have to switch to dealer-free secret sharing schemes. See for instance, here.


Which Cryptographic Standard ensures cryptographic agility and good adapotion Which Cryptographic Message Standards are recommended to ensure cryptographic agility in the future and good adapotion trough different programming languages (.NET and Go)?
(PublicKey with authenticated symetric encryption)
I doesn't want handle to cryptographic primitives myself, but rather I want to handle facade which protects more or less from small mistakes.
I found these different Standards, in which my experience varies:

PKCS #7 (Old standard, suitable for the future?)
NaCl crypto_box (Fixed primitives and limited message size)
JSON Web Encryption (JWE) (JWS is very well established, but not JWE)
XML Encryption Syntax and Processing Version 1.1 (Large overhead trough use of XML)

Are some worth mentioning missing? Which would be recommend for a future proof application?
Update
Application: is local installed and sends encrypted data over HTTPS with TLS Auth. to a service in the cloud, but data will be encrypted locally on-prem and not in cloud. One message is around 5kb-2MB and around 100-2.000 messeages per day. Crypt primitives should be fast, around ~50ms.
Constraints: Must be compatible with BSI TR-02102 and should be compatible with BSI recommendations (written in German) for the migration to post-quantum cryptography.

All but NaCl allow you to specify algorithms, but none of them would allow you to specify an algorithm that is part of the Post Quantum Cryptography initiatives yet (which, although unmentioned in the question, would be a very good reason to have crypto-agility).
For classic cryptography and a relatively high resistance against quantum computers, all those allow for RSA key encapsulation (including RSA-OAEP) and 256 bit AES as primitives. So using an RSA key pair of, say 4096 bits, will allow you to have a pretty good resistance against anything but a full featured quantum computer with more than 8192 logical qubits.
Otherwise I'd make sure that I would use a standard that is practical for you, that has a mature, well maintained library and is checked for e.g. side channel attacks. That's also something that's a good property of CMS; it may be old, but there is little wrong with maturity when it comes to choosing a library.


S-DES Binary converted to ASCII? I have been working with the following SDES Encryption templates and got the following as my ciphertext. I believe the ciphertext is correct because when I decrypted it I got my original plaintext.

If someone could inform me if the "encoded binary value is the ciphertext, and how do you convert this back to ASCII using the binary - ASCII table below?

Based on my results, I now have to answer the following questions, which I have answered in bold.

Plaintext binary value of e: 01100101

THE SUBKEYS WERE GENERATED USING THE KEY: 0101010110

Key 1:10011001

Key 2: 01101010

Encoded Binary Value: 11000001 (Is this regarded as the ciphertext?)

Finally convert, the encoded binary value back to ASCII: ? (Could someone please explain how this is done?)

Encoded Binary Value: 11000001 (Is this regarded as the ciphertext?)

Yes. Or at least it is considered a block of ciphertext, as in, the output of a block cipher. A block cipher in itself is not a CPA secure cipher, as identical input messages (plaintext) will lead to identical output.

  Finally convert, the encoded binary value back to ASCII: ? (Could someone please explain how this is done?)

You look up 0110 on the top row listing the high order bits, and then lookup 0101 in the low order bits, so you'll find the lower case e again. Of course most computer languages have functions such as CHR$ to do this for you.


Question of proving the opening of Pedersen Commitment Given an opening $(m, r)$ of a Pedersen commitment $c = g^m h^r$, where $g, h$ are the generators of a group $G$ with prime order $q$ (public), a PPT prover wants to prove to a verifier the opening of $c$ in zero-knowledge. Let us see the following procedure. Here we note that the DLP in $G$ is hard.

Prover randomly pick $s, t < q$, computes $y = g^s h^t$.
The verifier checks whether $y \in G$. If it is, the verifier sends a random challenge $e$ to the prover.
The prover sends to the verifier $z_1 = s + em \bmod q$, $z_2 = t + er \bmod q$.
The verifier accepts if $g^{z_1} h^{z_2} = y c^e$.

It seems that this argument works for our requirements. It is complete and special honest-verifier zero-knowledge.

But for the soundness, if a malicious prover provides $z_1' \ne z_1$, $z_2' \ne z_2$, such that $g^{z_1'}h^{z_2'} = yc^e$, it seems that such a prover can cheat in the procedure above. I know that a PPT prover cannot do this except for a negligible probability. But how can we formally prove this fact? Is it possible to provide a formal reduction that, if a malicious prover can cheat in this way, using this malicious prover we can provide two openings of a Pedersen commitment? If we can't, how can we show the soundness of this procedure? In a formal proof, do we need to always provide a reduction?

With this zero knowledge proof, the prover attempts to prove that he knows an opening of the commitment.

The obvious way to approach this is to show that, if the prover is able to complete the protocol for two different challenges, he is able to construct an opening of the commitment (and hence he actually knows what he is attempting to prove knowledge of).

How we show this is straight-forward:

Suppose the prover knows a value $y$ for which he can correctly answer two distinct challenge values $e, e'$.  That is, if given the challenge $e$, he can answer with $z_1, z_2$ such that $g^{z_1}h^{z_2} = yc^e$, and if given the challenge $e'$, he can answer with $z'_1, z'_2$ such that $g^{z'_1}h^{z'_2} = yc^{e'}$
Then, given these values, the prover then knows:

$$g^{(z_1-z'_1)(e - e')^{-1}}h^{(z_2-z'_2)(e - e')^{-1}} = c$$

That is, with valid answers to those two challenges, he can deduce an opening of the commitment.

Hence, someone who doesn't know a valid opening to the commitment can provide a valid answer at most one challenge to any $y$ value.


How to find the right additive polynomial in inverse affine transformation in AES Addition polynomial affine transformation rijndael is (x^7 + x^6 + x^2 + x)

The affine transformation represented in A(x)

A(x) = (x^7 + x^6 + x^2 + x) + a(x)(x^7 + x^6 + x^5 + x^4 + 1)mod x^8 + 1

Inverse of the multiplication can be found easily is (01001010) (x^6 + x^3 + x^1), so how to get the addition polynomial inverse affine transformation ?
it should be (01010000) (x^6 + x^4)

The inverse affine transformation represented in B(x)

B(x) = (x^6 + x^4) + a(x)(x^6 + x^3 + x^1)mod x^8 + 1

The Affine Transformation for AES Sbox is given by

Let M b the 8x8 binary matrix and C be the affine additive constant then

B = M x A xor C --------------- (1)

The straight forward reverse to this transformation is

A = M-1 * ( B xor C ) --------------- (2)

Where as the inverse of Affine Transformation is given as

Let D be the additive constant used in above inverse affine transformation then

A = ( M-1 x B ) xor D --------------- (3)

Place value of B from (1) in (3)

A = ( ( M-1 x (M x A xor C ) ) xor D

A = ( ( M-1 x M x A) xor ( M-1 x C ) ) xor D

Multiplying M with M-1 will be Identity, thus

A = A xor (M-1 x C) xor D

this implies

D = M-1 x C

and thats how the additive constant in inverse affine transformation have been calculated.

in fact it is


Practical differences between circuits and turing machines for cryptography In formal cryptography, we model algorithms (mostly our adversaries) as (Probabilistic) Turing Machines or as boolean circuits. In our lecture on formal cryptography, we learned that circuits are more powerful than turing machines, in the sense that every polynomial-time (probabilistic) turing machine can be represented by a polynomial-size circuit, but not every circuit can be represented as a polynomial-time turing machine.

As circuits are more powerful, it would intuitively make sense to use them instead of turing machines when modeling algorithms, as proving our system secure against a PPT turing machine does technically not imply security against polynomial-size circuits. However, since people are still using turing machines, I assume that this distinction is mostly irrelevant in practice.

Are there any practical differences between circuits and turing machines for cryptographic research (i.e. are there systems that are secure against PPT turing machines, but not polynomial-size circuits?) or does it exclusively come down to personal preference / convenience which one you use for your proofs?

Remark: I considered posting this to the computer science stack exchange, but decided against it as it is directly related to cryptography. If you disagree, feel free to migrate.

Just looking for a Turing machine vs circuit is a bit misleading. The important distinction is uniform (complexity class BPP) vs non-uniform (complexity class P/poly) adversaries. You can characterize P/poly in terms of circuit families, but also in terms of Turing machines with arbitrary "advice strings." In fact, the latter is the more traditional complexity-theoretic way to define P/poly. So just the fact that a definition mentions Turing machines doesn't mean it only applies for uniform adversaries.

If the authors are being careful, then their definitions will explicitly consider a TM adversary to take some advice string as input, and security must hold for all such inputs. Hence, security holds for P/poly adversaries. Even when the authors are not so careful with the definition, the results almost always carry over for non-uniform adversaries as well.

In general, I think it's safest to just assume non-uniform adversaries unless the paper explicitly says otherwise.

Of course, there are times when the distinction is important, and I can mention one way it might manifest itself. We generally have an asymmetry between wanting the "good guys" to be described by uniform algorithms, while protecting against "bad guys" who are non-uniform algorithms. Occasionally this becomes a problem when you want to convert an attack into a construction. For example, you can have a result like "an attack against scheme $X$ implies an improved construction for task $Y$." In these cases you often have to relax one of the definitions to bring them into alignment. For example, either:

"a [uniform] attack against scheme $X$ implies an improved construction for task $Y$."
"an attack against scheme $X$ implies an improved [non-uniform] construction for task $Y$."

Some examples:

Completeness for Symmetric Two-Party Functionalities - Revisited by Lindell, Omri, Zarosim: They show that certain protocols have some round at which Alice can distinguish some information about Bob's input. Then this distinguishing strategy can be used to construct an oblivious transfer protocol. But to incorporate this distinguishing strategy into another protocol, the strategy must be uniform, and the paper has to use a uniform definition of distinguishability. Alternatively, you could allow protocol constructions to be non-uniform.
In my own paper Universal Composability from Essentially Any Trusted Setup, I define a 2-player game between Alice & Bob. If Alice has a winning strategy in this game, then I create a protocol of one kind. If Bob has a winning strategy, then I create a protocol of a different kind. But in both cases I need the "winning" party's strategy to be uniform (they are the person whose strategy gets incorporated into a protocol), while the "losing" party's strategy can be non-uniform (the losing party corresponds to the adversary in the protocol I construct). So the result leaves a gap (what if non-uniform strategies can always beat uniform strategies)? As above, you could close the gap by allowing protocol constructions to be non-uniform.


Why is TLS susceptible to protocol downgrade attacks? A recent blog post from Ivan Ristić (expert extraordinaire on all things SSL) says:

  all major browsers are susceptible to protocol downgrade attacks; an active MITM can simulate failure conditions and force all browsers to back off from attempting to negotiate TLS 1.2, making them fall back all the way down to SSL 3. At that point, the predictable IV design is again a problem. Until the protocol downgrade weakness is fixed, newer protocols are going to be useful only against passive attackers, but not against the active ones.

Why is this?  Why is TLS vulnerable to this?

I know that SSL 3 included special mitigations to prevent protocol downgrade attacks where a man-in-the-middle downgraded two SSL3-capable endpoints so they end up using SSL 2.  This protection in SSL 3 was critical, because SSL 2 had some major problems, and if you could downgrade both endpoints to SSL 2, nasty attacks would have become possible.  Happily, the SSL 3 designers anticipated this risk in advance and made sure to introduce a special mechanism in the protocol to prevent "downgrade-to-SSL2" attacks.

So how is it that TLS ended up without any mitigation to prevent downgrade from TLS 1.2 to TLS 1.0 or even to SSL 3.0?  Is there some reason why it is non-trivial to add downgrade protection?  Did the TLS standard committee just overlook this one?  Or, was it considered a low priority?  Is there a straightforward way for future versions of TLS to address this issue?

Short answer: Because the browser developers have long thought interoperability to be more important than security and standard compliance.

Slightly longer answer: Some SSL/TLS server implementations do not negotiate the protocol version correctly, but terminate the connection with a fatal alert if the client attempts to negotiate a protocol version that the server doesn't support. This might happen at either of three steps in the handshake protocol:

When the server parses the client hello (which should contain the highest protocol version supported by the client). A correctly implemented server should store the client version value, even if it is not supported by the server.
When parsing a client key exchange message containing a RSA encrypted pre master secret (which should contain the highest protocol version supported by the client as the first two octets). This version field should be compared to the client version value above, and not to the negotiated version.
When verifying the client finished message (which should be a hash of all handshake messages, including the client hello which contains the highest protocol version supported by the client).

Now, if the server for some reason doesn't process these steps in accordance with the TLS 1.0, 1.1 or 1.2 standards, but one way or another e.g. requires the highest protocol version supported by the client to have a specific value, or to be no greater than the highest protocol version supported by the server, the client has two choices: Either fail the connection with an error message that is displayed to the user, or attempt to connect again with the highest protocol version disabled.

The exploit is possible if the client uses the second alternative (which e.g. Chrome does, but not IE 10). Even if the authentic server actually supports TLS 1.1 or TLS 1.2 and the authentic server actually does handle the client version value correctly, the MITM might exploit that the client doesn't know which server handles the client correctly or not, and inject alerts in both directions to get the client to reconnect using a lower version.

Edit: For completeness, I should add that I concur with @Thomas in his answer that this should largely be a non-issue, simply because:

Trivially, even under a MITM attack that exploits this behavior, neither the client nor the server will be able to negotiate a protocol version they don't enable, and
Neither the client nor the server should enable protocol versions that don't provide adequate security.

The underlying problem is not really that some clients negotiate the protocol version in a way that is not strictly supported by the standard, in order to be able to connect to servers that might or might not negotiate the protocol version in a way not strictly supported by the standard.

Rather, the problem might occur in situations where Carol might connect to multiple servers, but TLS 1.2 is only required for the connection to Sue, for all other servers SSL 3.0 is sufficient. Conversely, Sue might accept connections from multiple clients, but it is only the connection from Carol that requires TLS 1.2. Ideally, Carol and Sue should be able to rely on the protocol negotiation to ensure that TLS 1.2 automatically gets negotiated (and in such case they might, or might not, be vulnerable to the exploit), but correct implementations should really check that the TLS connection meets the minimum security requirements after it has been negotiated.


Prevent MITM attack while encrypting data by using ElGamal ECC? I am using ElGamal ECC to encrypt my plain text data. I want to ensure that my data is safe from a Man-In-The-Middle attack. What methodology I can adopt to achieve this goal?

How can we prevent a Man-In-The-Middle attack while encrypting data by using ElGamal ECC?

DrLecter is right.

It all boils down to making sure to use the right public key. In fact this is the same for any public key cryptosystem be it RSA elGamal or ECC variants thereof.

A MAC or whatever other construction local to your system won't do the job. The MAC e.g. can only make sure the last "editor" of the message knew the symmetric key the message is enciphered with, which a man in the middle obviously always does.

You can only achieve some protection by

trusting a CA who signed the key or
trusting a PGP style "web of trust" or
by meeting your communication partner in person and exchange keys face to face.

A somewhat weaker protection independent of an external organization might be achieved by:

Using a second independent and well protected channel to transfer the public key. E.g. use the phone if you trust your mobile...
Posting a video where you read your public key aloud.
(This helps with people who know you well in person and is hard to fake - I do that with my Academic Signature ECC-key here: http://www.fh-wedel.de/~an/crypto/key_read_anders.ogv . It might be awkward with elGamal or RSA keys which need to be very long nowadays.
There are also cryptographic concepts of deterministically deriving a public key from an e-mail address or a name string. This concept is called "Identity Based Encryption" (IBE). You can find it explained in wikipedia. IBE, however, IMHO just transfers the problem and doesn't solve it.


Attack on stream cipher I am trying to decrypt a message, which was encrypted using a stream cipher and 8 bit LFSR.

First two letters of plain text are given: K and A.

To find $X_n$ I used following formula:

$$X_n = M_n \oplus Y_n$$

I found $X_1 = 81$ and $X_2 = 65$.

Assuming the next step would be to find $C_1,C_2,\dots,C_n$ then how can I find them?

Assuming as you specified that $X_1$ is $81$ and $X_2$ is $65$.
$X_1 || \ldots || X_n$ is your key stream in bits.

So you need to convert 81 and 65 into bits.

$81 = \texttt{01010001}$
$65 = \texttt{01100101}$

Thus your key stream is : $\texttt{01010001 01100101}$

You are attacking a 8 bit LFSR and we will assume Galois mode (because it is easier in this case).

The diagram of such LFSR is:

+-------------+-----------+-----------+-----------+------------+-----------+-----------+------------+
|             |           |           |           |            |           |           |            |
|            *a          *b          *c          *d           *e          *f          *g            |
|             |           |           |           |            |           |           |            |
|    +-----+  |  +-----+  |  +-----+  |  +-----+  |  +-----+   |  +-----+  |  +-----+  |  +-----+   |
|    |     |  |  |     |  |  |     |  |  |     |  |  |     |   |  |     |  |  |     |  |  |     |   |
+--->+  x0 +---->|  x1 +---->|  x2 +---->|  x3 +---->|  x4 +----->   x5 +---->|  x6 +---->|  x7 +-------> ...
     |     |     |     |     |     |     |     |     |     |      |     |     |     |     |     |
     +-----+     +-----+     +-----+     +-----+     +-----+      +-----+     +-----+     +-----+

where a b c d e f g are constants set to 0 or 1 to determine whether a bit influence the next result.

You must notice that the output is actually decided 8 rounds before being seen.

Thus you can see the LFSR as following parallel formulas:

$out \leftarrow x_7$
$x_7 \leftarrow x_6$
$x_6 \leftarrow x_5$
$x_5 \leftarrow x_4$
$x_4 \leftarrow x_3$
$x_3 \leftarrow x_2$
$x_2 \leftarrow x_1$
$x_1 \leftarrow x_0$
$x_0 \leftarrow f(x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7)$

where
$$f(x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7) = \\
(x_0 \land a) \oplus
(x_1 \land b) \oplus
(x_2 \land c) \oplus
(x_3 \land d) \oplus
(x_4 \land e) \oplus
(x_5 \land f) \oplus
(x_6 \land g) \oplus x_7$$

From this you can deduce:

$f(1,0,0,0,1,0,1,0) = 0$ and the LFSR returned $0$
$f(0,1,0,0,0,1,0,1) = 1$ and the LFSR returned $1$
$f(1,0,1,0,0,0,1,0) = 1$ and the LFSR returned $0$
$\ldots$
and finally:
$f(0,1,0,0,1,1,0,1) = 1$ and the LFSR returned $1$

Notice that the first column is the second part of the stream : $\texttt{011}\ldots \texttt{1}$ and the second column (LFSR returned) is your first part of the stream: $\texttt{010}\ldots \texttt{1}$

Intermediates steps not provided as it is your homework.

Thus this gives you 8 equations to solve with 7 variables ($a,b,c,d,e,f,g$).

Equations not provided (nor solved) as it is your homework.

From this you have will have recovered the complete state and will know the formula to compute the next outputs bit, giving you full prediction on the stream to attack $C_1, \ldots, C_n$.


Why can't different messages result in the same ciphertext when encrypted with RSA? In the encryption step of the RSA encryption to get the cypher text $C$

$C \equiv M^e \pmod n$

I am struggling to understand how we know that there only exists one $M$ that maps to a certain $C$?

Does there not exist an $M$ and an $N$ such that $M^e \equiv N^e \pmod n$? How do we know this?

The property that you are talking about is the injectivity. I think this link will maybe help you.


Why can't I reverse a hash to a possible input? I'm going to provide “proof” why a hash function can be reversed, and I hope you can tell my why I'm wrong

So, a hash function can be implemented as a series of logic gates. All logic gates can be implemented using only NOT and OR gates. (I'm fairly sure about both of these, but please correct me if I'm wrong.)

Therefore, a hash function can be implemented as a series of NOT and OR gates.

A NOT gate can be easily reversed by going through another NOT gate.

An OR gate cannot be reversed, since it fundamentally losses information. However, a possible input can be derived from any given output.

Therefore, I should be able to construct a possible input given an output from a set of logic gates, including from a hash function.

What have I gotten wrong here?

It is correct that any hash function used in cryptography, restricted to fixed (or bounded) input size, can be implemented as a finite number of NOT and OR gates. What's more: the gates can be given an index such that the input of any gate consists of either an input of the hash function, or an output of a gate with lower index; this insures the construction of gates is a function, rather than depending on some internal state. And the number of gates is manageable (perhaps in the order of $n=10^{5\pm1}$ OR gates for the SHA familly and single-block message).

This does give a constructive way to find an input corresponding to a given output, as outlined in the question: try every possible inputs for a gate with an output that's a given output, or has been hypothesized in an earlier step. For NOT, there's only one possible input (the complement of the output). If the output of OR is 0, its inputs are 00. If the output of OR is 1, there are 3 possibilities for its inputs: 01, 10, 11. When a new hypothesis conflicts with an earlier hypothesis (which occurs since inputs of different gates can be connected to the same output), eliminate the new hypothesis. If all new hypothesis for a gate's input(s) are eliminated, eliminate the old hypothesis. When all the circuit is covered, and if there's a possible input, any hypothesis not eliminated gives a possible message input.

That works. But critically: new hypothesis are dependent on earlier ones, thus when we meet an OR gate with a 1 output, it multiplies by 3 our number of hypothesis to keep track of (in a breadth-first approach) or explore later in case of failure (in a depth-first approach). If we examine the maximum number of hypothesis to be examined as a function of the number $n$ of OR gates, it grows as $\mathcal O(c^n)$ for some constant $c$ that can be significantly above 1. Using that a XOR can be built with 3 OR gates (and some NOTs), we have an argument that $c\ge\sqrt[3]2\approx1.26$ for some large portion of some possible circuits (adding a XOR gate on an unknown input transforms it into 2 unknown inputs).

Thus the argument in the question proves that a hash can be reversed with enough effort, but it gives no lower bound for the corresponding effort; and the best bound we know to derive is exponential w.r.t. the gate complexity. It turns out that for hash constructions used in cryptography (e.g. SHA-1 with 160-bit output and 176-bit input), the cost of this method is much higher that trying all possible hash inputs (e.g. $2^{176}$).


The index of coincidence is significantly higher for

The correct keylength
All its multiples

Even if that is not the correct key, you will have a behavior like that. Assuming you have a high index at length $7$, then by the nature of the algorithm you will have a high index at $14, 21, 28, \dots$, regardless if that is the correct key or not.

So the best stragety would be, just to start with the lowest value and if it doesn't work out move to the next outlier (which is most likely your first value doubled). Things like calculatin the GCD of all the outliers, etc. is not wrong but unnecessary, if you can just iterate through and have a really high chance of success on your first (or first few) tries.

One more thing: This kind of analysis is only faulty for short texts (with being impossible to break if the keylength is as long as the message, and the key is chosen uniformly random and only used once), and for longer texts the law of large numbers (in particular, see the variance of the central limit theorem ) will cause all the other values to be really, really close to what you would exepct from a uniform distribution over the alphabet.


Can a service that can only sign text, be used for encryption/decryption? This is somewhat a theoretical question, but I am also interested in whether this is possible in practice.

Assume, that there is a service that possesses a private RSA key, and can sign any data with that key, after the key is unlocked with a password. Something similar to the ssh agent. Once unlocked, you can talk to this service through a protocol, but don't have access to the (unlocked) private key in any way. You hand over the data to sign to the service, and it returns the signature. And you also have the corresponding public key.

Now, the question is, can this service be used for encryption and decryption? I am thinking of something like this for encryption:

You unlock the service with a password.
You have plaintext you want to encrypt.
You generate a random blob of data.
You ask the service to sign this data. You verify the signature using the public key.
You treat the signature (or some hash of it) as a key for symmetric encryption/decryption, e.g. as an AES key.
You encrypt the plaintext with this key, and get a secret.
You store

the secret, and
the random data you used to create the signature.

When you want to decrypt a secret:

You unlock the service with a password.
You take the stored random data.
You ask the service to sign it with its private key. You verify the signature using the public key.
You treat the signature (or some hash of it) as an AES key.
You decrypt the secret with the AES key.

I admit, that I don't know much about cryptography, but to me, this seems like a good (=secure) algorithm for solving the problem, at least in theory. Am I missing something? Is this already known/used somewhere in practice?

The signature algorithm would need to be deterministic. Only PKCS#1 v1.5 based RSA signatures are deterministic; most other modern (and popular) algorithms use random input for the signature. If the signature is random then your encryption and decryption key will be different and the protocol will fail.

The random blob of data isn't kept secret (if you could keep it secret between the two parties you would not need the signing service). Anybody can access the blob. So anybody with access to the service will be able to generate the signature used to derive the secret key.

So (after the edit) the scheme could be used to generate a symmetric key. But beware that whenever the private key changes or whenever the private key is used for a different, non-deterministic scheme it will fail. If the signature is deterministic you could however generate a static shared secret and use that for further communications.

It's kind of obvious, but remind your self that the owner of the private key service will also be able to generate the secret key. You might as well randomly generate a secret and put it somewhere in the service. Then you would not be dependent on the private key being available (using keys for different services is severely frowned upon when it comes to key management).


modular exponentiation as a one-way-hash As far as I can tell most one-way hashes apply some iterated encryption algorithm to the input data.

What would be the issues with a one-way hash based on some fixed large prime $p$ and a generator $g$ with $h(x) = g^x \bmod p$? Is it just that the methods used for modern hashes are even harder than the discrete logarithm?

It's a fine one-way function, based (as you noted) on the computational difficulty of the discrete logarithm problem. As far as its relation with modern-day cryptographic hash functions, however, it lacks two quite important properties.

Here's an okay definition: a function $H$ is called a cryptographic hash function if it possesses the following three properties:

Preimage resistance: Given $H(x)$, it's hard to find $x$
Second preimage resistance: Given $m_1$, it's hard to find another $m_2$ such that $H(m_1) = H(m_2)$
Collision resistance: It's hard to find any two distinct messages $m_1$, $m_2$ such that $H(m_1) = H(m_2)$.

Note that a general one-way function possesses only property 1. Unfortunately, your $h(x) = g^x \bmod p$ fails property 2. Suppose you had a fixed message $m$ that the adversary knows. Notice that

$$h(m + p - 1) \equiv g^{m + p-1} \equiv g^m \cdot g^{p-1} \equiv g^m \pmod{p}$$

by Fermat's little theorem. By extension, you find that $h(m + k(p-1))$ collides with $h(m)$ for any $k \in \mathbb{Z}^{+}$. So, you can in fact efficiently find infinitely many collisions with any $m_1$, which is relatively exciting, I suppose. And since $h(x)$ doesn't have property 2, it can't possibly have property 3. On the other hand, SHA2 and SHA3 (as two example candidates of modern-day hash functions) are strongly suspected to satisfy even property 3.

Also, even if we wanted a one-way function, modular exponentiation is dreadfully slow. Even with the repeated-squaring method, it's still painful. Some researchers at Intel did a benchmark with a modular exponentiation implementation and found that their implementation took nearly 450,000 cycles (!) for a 512-bit modular exponentiation. On the other hand, the Crypto++ Benchmarks report a figure of 17.7 cycles per byte for SHA-512. Now, I do admit that these were ran on different processors, but the difference is pretty spectacular.

So, in sum, there are essentially two reasons we use hash functions like SHA2: (1) they offer two extra properties, both of which are quite essential for many purposes and (2) modular exponentation is so very painfully slow. I'm sure there are more to be found, but I think these two are the most compelling.


Non malleable Encryption scheme I know that one time pad is malleable. Can you give me an example of an encryption scheme which is non-malleable?

IMHO the best option to mitigate the maleability is using the authenticated encryption. So every scheme that includes the authentication tag should not be malleable (when done properly). Examples - the GCM mode, CCM, etc..


Why random number used in RSA padding but not in AES? I noticed that people use a random number in the RSA-OAEP padding scheme to avoid deterministic encryption. But in pkcs#7 people just use the padding size rather than some random bits. Doesn't it make AES deterministic?

They are different concepts and have different approaches. AES like any block cipher is a primitive and the encryption is performed by using the block cipher mode of operation. Like ECB,CBC,CTR,GCM,EAX...
The pkcs#7 padding or any other padding that is used to fill the last block to the block size with ambiguous remove, not designed for randomization. Even one can design a randomized padding mechanism it can affect at most 2 blocks without wasting the other blocks. Therefore not a good randomization point. Indeed, the CTR and OFB don't use padding at all.
The randomization ( probabilistic encryption) is achieved by using IV/nonce.
Since the insecure ECB doesn't use an IV, it doesn't have Indistinguishability under chosen CPA attack (Ind-CPA). This is the minimum requirement for modern Cryptography, but not enough. The other modes have IND-CPA.
Like other Authenticated Encryption modes, AES-GCM can have IND-CCA2. And we prefer the Authenticated Encryption ( with Associated Data (AEAD)) to use. The common modes are AES-GCM, ChaCha20-Poly1305, EAX, and CCM. TLS 1.3 standard has the AES-GCM, AES-CCM, and ChaCha20-Poly1305 AEAD cipher modes.
And note that Authenticated Encryption is a stronger notion, AEAD > IND-CCA.
One should note that IV/nonce is necessary but not sufficient for security. For example, the CBC IV must be more than a nonce, it must be unpredictable. For the CTR mode, the (key,IV) pair must never be reused ( similar to GCM mode since it uses CTR mode inside). There is a mode against the nonce misuse:
SIV (Synthetic Initialization Vector) mode, it called a nonce-misuse resistant authenticated-encryption.


An attack an encrypted classified data in a theoretical situation Lets say for some reason you carry AES-256-XTS encrypted data with using Whirlpool as the KDF. The data is in a 100 MB encrypted container format.

You get caught on the airport by the police. The data is so important to the country that it is the #1 priority of the intelligence service to crack it. However, no social engineering can be applied by the party that takes you in custody.

The computer on which the encryption was done has been overwritten using DoD-5220.22-M. The other party has infinite money and electricity and the best data center available.

How would they attack the file ? Would it be possible in reasonable time (less than 2 years?). If they use some kind of special attack, how would it work?

Well, given that (for whatever reason) they cannot try to overcome you with either rubber hoses or large bags of money, the next best options they would have are:

A brute force search on the password (you didn't state this, but I assume that the encrypted data is protected by a password which is the only unknown input to the KDF); if we're talking about a major TLA who is willing to throw all their resources at it, I'd expect them to be able to check all (circa) 12 character passwords (and many longer ones that don't look like line noise).
Do a black bag job on your home/work, and see if they can recover the plaintext (or a clue for the password)

Now, XTS does have weaknesses (if you update a disk block and modify only some of the 16 byte AES blocks, the attacker can see which blocks you updated); that weakness wouldn't apply here.  None of the other components are amenable to cryptanalysis.


Has there been any cryptanalysis of RC4-52? Several websites ( such as Is there a secure cryptosystem that can be performed mentally? ) briefly mention RC4-52 as a modification of standard RC4.

RC4-52 has only with 52 instead of 256 elements in the state array, so encryption or decryption (or both) can more easily be executed manually (literally "by hand") with a standard deck of playing cards, far away from any computer.
Some people seem to think that, unlike classical ciphers, RC4-52 is difficult to decrypt even using computer assistance.

Has anyone done any cryptanalysis on RC4-52?
Where can I find such cryptanalysis?
A published thesis or magazine article would be nice, but I'd be happy with a well-written blog post.

Well, I have unaware of any specific analysis of RC4-52.  The closest thing I can think of is Cryptanalysis of RC4-like ciphers, which is an early paper which explores RC4.  Of particular interest would be section 5 (Tracking analysis), along with Table 4; that explores the obvious way to attack RC4-52.  Now, I suspect that it could be improved modestly (say, by attempting to search for a Fortuitous State, see section 5), however I suspect that won't gain you all that much unless you have huge amounts of keystream available).


Do you really need a KDF when you have a PRF? My understanding is that a KDF is like a PRF, except that it has a preliminary step that "extract" entropy. It is thus needed when the entropy is non-uniform (for example the output of ECDH is modulo a number that is not a power of 2, and is thus non-uniform if represented as a bit-string).

Yet, I am not sure there are modern symmetric algorithms that require the secret to be uniformly distributed. Sure their security might be defined with a uniform key, but using a KDF feels a bit like a cheat since there is no new entropy added, and it's not slow either. Am I missing something?

Do you really need a KDF when you have a PRF?

Maybe.

The security contract of a PRF requires that the key be a uniform random bit string.  If you have a DH secret or a diceware phrase, then what you have is not uniform random as a bit string, and so your contractual obligations are not satisfied and the PRF may give no security.  You need something a little stronger to hash a DH secret or diceware pass phrase into a uniform random bit string, which is what the ‘extract’ step does.

Here's an example.  Let $F_k$ be a PRF and let $H$ be a random oracle.  Define $$F'_{x,y}(s) := F_{H(u)}(s), \quad u = (y^2 - x^3 - 7) \bmod p,$$ where $p = 2^{256} - 2^{32} - 977$.  $F'$ is also a PRF, because when $(x, y)$ is uniformly distributed among 512-bit strings, the probability of collisions in $u$ is small.  But if $(x, y)$ is the outcome of a DH key agreement on secp256k1, then $y^2 \equiv x^3 + 7 \pmod p$ so $u$ is always zero and hence $F'_{x,y}(s) = F_{H(0)}(s)$ for all $x$ and $y$—that is, the DH key agreement doesn't affect the output at all, so the system gives no security whatsoever!

If what you have is a uniform random bit string as a master key already, and you just need to derive subkeys from it with distinct labels, then a PRF is all you need, and the ‘expand’ step is, in fact, a PRF.  If you look closely at HKDF, for example, you will see that $$\operatorname{HKDF-Expand}_k(L) = \operatorname{HMAC-}\!H_k(L \mathbin\| \mathtt{0x01}),$$ if the desired output size matches the output size of $H$; if more bytes are requested, just repeatedly call $\operatorname{HMAC-}\!H$ with consecutive counters and the previous chunk prepended to $L$, and concatenate the outputs.  You could, of course, substitute for $\operatorname{HMAC-}\!H$ your favorite PRF like keyed BLAKE2b, KMAC128, KangarooTwelve, Kravatte, prefix-keyed Gimli-Hash, or ChaCha $\circ$ Poly1305, and while it wouldn't be HKDF it would be just as good for deriving subkeys.

  My understanding is that a KDF is like a PRF, except that it has a preliminary step that "extract" entropy. It is thus needed when the entropy is non-uniform (for example the output of ECDH is modulo a number that is not a power of 2, and is thus non-uniform if represented as a bit-string).

Correct: The purpose of collecting the concepts of extract-with-salt and expand-with-label into a single term KDF is that often the two steps are close by—you have a DH secret, or a master diceware phrase, which is not uniform in bit strings but which has high entropy, and you want to derive many secret keys from it for different labeled purposes.

  Yet, I am not sure there are modern symmetric algorithms that require the secret to be uniformly distributed. Sure their security might be defined with a uniform key, but using a KDF feels a bit like a cheat since there is no new entropy added, and it's not slow either. Am I missing something?

The security contract for many cryptographic primitives requires the input to be uniform random.  Violate the contract, and the security may evaporate.  Obviously you can choose the input by a pseudorandom function under a uniform random key—if that broke the composition, merely using the composition would then serve as a distinguisher for the pseudorandom function.  But it's not a priori clear whether highly structured keys like the bit encodings of points on particular curves might be exploitable in downstream cryptosystems.  Maybe you'll be bitten by a bad interaction like in the contrived secp256k1 example above; maybe you won't be.  Using HKDF-Extract, or otherwise hashing the input, renders these concerns moot so you don't even have to think about them.


AES-256 with random key generation instead of hash In order to use AES256 encryption, we will need a 256 bit key, and 128 bit iv. We will need some kind of salt and hashing function to convert a password to the desired key.

However, let's assume the password is automatically generated for every file anyway. This means that we can theoretically skip the salt and hash (e.g. pbkdf2), and just generate a random 256 bit key and 128 bit iv. Is there any security implication which might be generated from this?

We know that you can't invert the AES encryption to determine it's key at present.  So you're fine there, as long as you are able to generate all 256 bits in the uniformly distributed way.  Any decent random number generator will be able to do this as long as it can be seeded correctly.  If there is some mathematical relationship between the files (you derive from) and the key, you'll need to make sure that the file entropy fits into the random number generators state space.  This can be a little tricky sometimes, and there are examples like the seeding mechanism of RC4 that's quite poor and can lead to /induce weak states.  This then has a detrimental effect on the generator's output.  Similarly, correctly seeding a large state generator like the Mersenne Twister is difficult. This is all however an implementation issue.

One security issue lies with the IV.  This is stored in plain form.  In order to maintain security, the IV must be generated from a cryptographically secure generator.  Otherwise it might be quite simple to determine an insecure generator's state and thereby predict all IVs. Since you need a CSRNG for the IV, you might as well use the same generator for the 256 bit key.  The same issue of correct seeding still remains however.

The other issue is if you transmit the same file repeatedly.  The purpose of the IV is to make sure that the cipher text is unique per transmission, even if the plain text is the same.  If the IV /key pair are directly (and only) related to the encrypted file contents, the cipher text will always be identical.  This may not be an issue for disk storage, but can be for copying /transmission as it leaks some information.

My sense would be to have some form of salt anyway.  Without it, the system feels very predictable as all the information is there in hard coded form.  Something that only you know would improve the security.


Derivation of many (Key, IV) pairs from random 128 nonces and one secret 512 master key The ext4 encryption system encrypt files with aes-256-xts. Each file uses two unique keys which are derived from a 512 bit master key and a per-file 128 bit nonce randomly generated when the file is created (see the design doc).

In order to derive two 256 bit keys for each file, the 512 bit master key is encrypted with AES-128-ECB using the 128 nonce as a key.

One disadvantage noted in the design doc is that if the file keys are leaked then the attacker can retrieve the master key by decrypting the file keys with the nonce.

My question is : why not use a one-way KDF to derive the per-file keys instead ? I would have derived the keys using something like :

  key1||key2 = hmac_sha512(master_key, nonce)

Is there any downsides with this approach ?

Do we get to assume that the master key is uniformly selected?  The goal of a KDF, as the HKDF paper defines it, is this:

  Its goal is to take a source of initial keying material, usually containing some good amount of randomness, but not distributed uniformly or for which an attacker has some partial knowledge, and derive from it one or more cryptographically strong secret keys. We associate the notion of “cryptographically strong” keys with that of pseudorandom keys, namely, indistinguishable by feasible computation from a random uniform string of the same length.

If the master key is selected uniformly at random, then the full HKDF extract-and-expand paradigm is not needed; all we need is the expand phase, which can be realized by a PRF with an uniform key.

Given the PRF security of HMAC-SHA512 your use of it looks appropriate then, but possibly overkill because:

HMAC supports variable input lengths, but this application has fixed input and output sizes;
The application is already using AES, so bringing in HMAC requires an extra primitive.

So perhaps simpler would be to just:

Use a shorter, 256-bit master key directly as the AES key;
Given a file's random nonce, derive the file key as fk = fk[1] || fk[2] || fk[3] || fk[4], where:

fk[0] = random_nonce;
fk[i] = AESENC(master_key, fk[i-1]).

This is equivalent to encrypting all-zero plaintexts in OFB or CBC mode with random IVs, so attacks against this approach should reduce to attacks against those modes.  So for example if some file keys are leaked as you suggest, that's a known-plaintext attack scenario.

As a real-life example, the current AES-GCM-SIV draft (draft-irtf-cfrg-gcmsiv-02) uses a variant of this to derive its encryption and authentication subkeys (section 4):

if len(key-generating-key) == 16 {
  record-authentication-key = AES128(key = key-generating-key, input = nonce)
  record-encryption-key = AES128(key = key-generating-key,
                                 input = record-authentication-key)
} else if len(key-generating-key) == 32 {
  record-authentication-key = AES256(key = key-generating-key, input = nonce)
  second-half = AES256(key = key-generating-key, input = record-authentication-key)
  first-half = AES256(key = key-generating-key, input = second-half)
  record-encryption-key = concatenate(first-half, second-half)
}


What is the difference between OTR and Signal protocols? The Signal Protocol is a relatively new secure messaging protocol that was recently implemented in Signal, WhatsApp, and several other messenging apps.  According to Wikipedia, the Signal protocol is an evolution of the OTR protocol (https://otr.cypherpunks.ca/otr-wpes.pdf).

One of the major new features of Signal is that it allows for asynchronous messaging (i.e. both participants need not be online at the same time).

What are the other important differences between these protocols? Are there any instances in which OTR would be better suited than Signal?

Check out the blog post by Whisper Systems regarding the triple ratchet of OTR verses the double ratchet of Signal. Also, a prior article about synchronous versus asynchronous messaging is worth the read. Both of those should answer all of your questions.


Single string producing two different hash results with SHA-256 Is it possible that a single string produces two different hash results after going through the same SHA-256 hash function? The code I'm working on right now is doing this, and I assumed this should not be possible. Any help?

No.  This doesn't make sense.  SHA-256 is a mathematical function on bit strings.  As such, it doesn't give different answers at different times of day or under different phases of the moon.  It gives different answers only for different inputs.


Encrypt and decrypt data accessible by multiple users within a team I'm currently working on web services which allows to send and retrieve data.

The data belong to a team.
A team is composed of users.

Each authenticated user can send and retrieve data to/from their team.

I need to add encryption to this with the following requirements:

Data are encrypted on the server and the server doesn't store (might handle, but not store) any key
Each user has a different key or password to decrypt the data
Each user encrypts the data before sending it (data must of course be "decryptable" by other team users)

After searching for hours, I came to this solution, however I would like to have some comments whether this seems to be good or not, and if I could improve it.

Each user, at creation time, receives a RSA public and a private key, the keys are generated by the server, the public key is stored in the database, the private key is immediately sent back to the user via SSL secured connection and removed from server memory.
When the first user is added to a new team, the server generates a 64bits key (for AES). The user public key is used to encrypt the AES key.
The encrypted AES key is stored in the database (user/team pair).
When a user receives/sends some data, he first has to get the encrypted AES key from the server. The user uses his private key to decrypt the AES key.
For "send" action, he uses the AES key to encrypt the data.
For "receive" action, he uses the AES key to decrypt the data.
When a user needs to be added to a team, the existing team member will use the new user public key to encrypt the AES key then send the new user info to the server (user info + encrypted AES key for the new user/team pair)

Two things I don't like:

If a user needs to be removed from a team, he still could have saved the AES key.
This is not a major problem has he won't be authenticated anymore and therefore won't have access to the encrypted data anymore.
AES requires an IV, which should be different for each encrypted piece of data, so I would need to store an IV for each piece of data.

Do you think of any better solution ?

Thank you

One potential risk is your AES key length. Using a key length of 64 bits or less is not advisable as it can be relatively easy to brute force these days. Recommend that you use at least 128 bits.

As for your problem when a user is removed, you may like to try something similar to PGP. Each time you commit a file to the server, you encrypt it with a randomly generated symmetric key and encrypt the key with the public keys of all other legitimate users. In this way, a removed user would no longer be able to access newer files.

But I dunno if that will be secure enough, its two cents worth.


Simple application of verifiable random function? I have been reading a little bit about verifiable random functions (e.g.). In the literature, these are described as "pseudo-random functions that provide a non-interactively verifiable proof for the correctness of their output". I'm having a little trouble seeing a clean example of a 'killer application' for such a primitive. Can anyone describe one here?

I guess I'm having trouble seeing the usefulness of such a proof of correctness for a pseudorandom function. What does it give you that a normal PRF can't?

Sharon Goldberg's research group at Boston University has a web site on VRFs with research references and applications, including key transparency in CONIKS, authenticated enumeration-resistant denial of existence in DNSSEC with NSEC5, and the Byzantine agreement protocol Algorand.

Here's a quick history of how negative answers work in DNS and DNSSEC.  The things to watch out for are:

Forgery of A records, so a MITM can direct legitimate users to evil hosts.
Forgery of negative answers, so a MITM can cheaply deny service to legitimate users without getting out the wirecutters and digging a trench by their house.
Consequences of breaking into a live nameserver but not an operator's airgapped laptop.
Zone enumeration: what is the computational and network cost of enumerating all names in a zone?

The DNS can be used for many purposes, and you might want to prevent someone from enumerating all hosts on your network, or all users' if each user gets a unique hostname for their mailbox, or what-have-you.  (Debating the merits of zone enumeration or its prevention is left as an exercise for a pyromaniac on an IETF mailing list.)

Unauthenticated version (NXDOMAIN):

  CLIENT: Can you give me the A record for stackexchange.com?

  MITM: stackexchange.com does not exist.

  CLIENT: Thanks!

  SERVER: stackexchange.com is at 1.2.3.4.

  CLIENT: What?  I already had an answer which I acted on.  Go away!

There's no way for the client to distinguish an answer by the legitimate nameserver from an answer by a malicious MITM—positive or negative.

This fails to thwart forgery of positive (1) and negative (2) answers, and if an attacker breaks into a live nameserver (3) then the legitimate operator can't recover until the longest TTL period after they regain control of the live nameserver or delegation.  But zone enumeration (4) costs one network query per guess.

Hypothetical online signed version:

  CLIENT: Can you give me the A record for example.com?

  MITM: example.com is CNAME for malicious.badguys which is at 4.3.2.1.

  CLIENT: What?  That doesn't have a valid signature.  Go away!

  SERVER: example.com does not exist.  Signed, --Server.

  CLIENT: Thanks.  Can you give me the A record for example1.com?

  SERVER: example1.com does not exist.  Signed, --Server

  ...

  CLIENT: Thanks.  Can you give me the A record for example11237.com?

  SERVER: I'm tired and I'm out of CPU to answer legitimate queries because signing takes too much effort.

  ATTACKER: I broke into the live server because it was running an unpatched version of BIND 8 and now I can forge records with wild abandon!  Haha!

  OPERATOR: Damnit!  I knew we should have chosen a protocol with an offline signing key.

The computational cost of signing every negative query seemed prohibitive at the time DNSSEC design began.  The world has since changed, so that doesn't matter as much now.

This thwarts forgery of positive (1) and negative (2) answers, though if an attacker breaks into a live nameserver (3), which necessarily has a signing key, then it's much the same as the unauthenticated story. Zone enumeration (4) still costs one network query per guess.

Can we do signing offline instead?

Offline signed version (NSEC):

  CLIENT: Can you give me the A record for example.com?

  SERVER: There are no domains between exampla.com and examplo.com.  Signed, --Server

  CLIENT: Can you give me the A record for examplo1.com?

  SERVER: There are no domains between examplo.com and exemption.com.  Signed, --Server

  CLIENT: Can you give me the A record for exemption1.com?

  SERVER: There are no domains between exemption.com and exuberate.com.  Signed, --Server

  ...

  CLIENT: Aha!  I have enumerated all the domains in the com zone!

This still thwarts forgery of positive (1) and negative (2) answers (as will all subsequent methods), and the signing key can be offline so the worst an attacker can do by breaking into the live nameserver (3) is deny service.  But now zone enumeration (4) is amazingly cheap: it costs one network query per name in the zone, and negligible computation.

With the original NXDOMAIN system, the client must test each guess with a query to the server.  With NSEC, the client can quickly skip large ranges of the space of names because the server says which ranges to skip.

Offline hashed signed version (NSEC3):

Here $H$ is a public hash function, such as SHA-256 iterated 1000 times.

  CLIENT: Can you give me the A record for example.com?

  SERVER: There are no domains with hashes between H(foo.com) and H(bar.com).  Signed, --Server

  CLIENT (after some work to find bar.com from H(bar.com)): Can you give me the A record for ejemplo.com?

  SERVER: There are no domains with hashes between H(fnord.com) and H(fjord.com).  Signed, --Server

  ...

  CLIENT: Aha!  I have enumerated all the domains in the com zone!

Live nameservers still need not have signing keys.  Zone enumeration costs more computation per guess now, but it still costs only one network query per name in the zone.  Since the space of domain name labels is relatively sparse, it is not hard to guess them; there's even a prepackaged tool to automate the process called nsec3walker.

This is the point at which standard DNSSEC as of today stopped.  CloudFlare took a middle ground between online signing and NSEC3 called ‘NSEC3 white lies’, eating the server's computational cost of signing each negative answer afresh and the cost of live nameserver compromise by storing the signing key online and answering ‘there are no domains with hashes between SHA256(query.com) and SHA256(query.com) + 1’.  (NSEC3 white lies is what motivated CloudFlare to push for the deployment of elliptic-curve cryptography in DNSSEC, since its signing performance beats the pants off RSA's at the same security level.)

But there's another option with VRFs:

Offline VRF'd signed version (NSEC5):

Here H is a secret hash function, namely a VRF, with a corresponding public key that can verify proofs of the output of H.

  CLIENT: Can you give me the A record for example.com?

  SERVER: There are no domains with hashes between H(bar.com) and H(foo.com).  Signed, --Server (NSEC5)

  SERVER: P.S.  ‘H(example.com)’ is H(example.com), and here's a proof of the fact.  (NSEC5PROOF)

  CLIENT: Blast!  I'm thwarted.

Forgery is prevented as usual.  The cost of zone enumeration is back to one network query per guess, because the client cannot evaluate H(guess.com) to try a guess.  And if an attacker compromises a live nameserver, although there is secret key material for evaluating H(query.com) when a client asks for a nonexistent query.com, that's useful only for evaluating the NSEC5PROOF postscript.  The signing key for the NSEC5 record denying the existence of any domains between H(bar.com) and H(foo.com) can remain offline.


Why "encipher" instead of "encrypt" and "decipher" instead of "decrypt"? According to a book I am reading, Applied Cryptography by Bruce Schneier, the ISO 7498-2 standard uses the terms “encipher” instead of "encrypt" and “decipher” instead of "decrypt" because some cultures find the terms “encrypt” and “decrypt” offensive, as they refer to dead bodies.
I am curious to know which cultures exactly the author is talking about as I can not find information about the topic online.
Moreover, when you search for ISO 7489-2 on Google, the first link you get is this one: https://www.iso.org/standard/14256.html, a downloadable document but its not for free, you have to pay and I don't know why the standard is for sale.
Is there concrete evidence that in cryptography the standard words to use are "encipher" and "decipher" and that we do not use "encrypt" or "decrypt" because they are offensive words?

I've seen encipher, encrypt, and encode for encryption. Encode is the worst since we have text encoding. The below definitions from Google dictionary that uses  Oxford Languages.

encipher: convert (a message or piece of text) into a coded form; encrypt.
Merriam Webster gives the date of the first usage of encipher as 1577.

encrypt: convert (information or data) into a cipher or code, especially to prevent unauthorized access.
Encrypt formed from English en + Greek kruptos is originally from the USA around 1950s.
Merriam Webster gives the date of the first usage of encrypt as 1944.

The above chart doesn't compare the actual values, Google's ngram can handle this

Encode: convert into a coded form. ( Please don't use this for encryption)

Is there concrete evidence that in cryptography the standard words to use are "encipher" and "decipher" and that we do not use "encrypt" or "decrypt" because they are offensive words?

I've searched and I couldn't find, however, if you consider usage statistics, the encipher should be increasing over time instead of decreasing. The academicians visit various countries around the world and meeting in the conferences, and if it is an offensive word in some language we have already heard about that a lot from them. For example, take Eve, although it is an abbreviation for an eavesdropper, it is used for a bad actor can be considered an offensive usage since the religious Adam and Eve but still in use. I know some people don't use Eve anymore.
Personally, I read a lot of text using encipher, however, that usage is decreasing. And I've seen some texts that use encoding for encryption, I hope that will fade away.
And the Google fight Encipher vs Encrypt : Encipher 1 : Encrypt 200

Is there concrete evidence that in cryptography the standard words to use are "encipher" and "decipher" and that we do not use "encrypt" or "decrypt" because they are offensive words?

Actually, I have seen the reverse of this. There is a website named word safety ( Warning no https) show some -not exact- potential unwanted meaning for the word encipher in Russian, I would not list here.


XOR instead of Multiplication in ElGamal encryption In the ElGamal encryption scheme, the message $m$ is multiplied with the secret $g^{xy}$ Wikipedia. I don't understand the advantage of it. Why we can't just XOR our message with the shared secret? As far as I know, multiplication is costlier than the XOR operation. Also, both the schemes will be CPA secure but not CCA secure, in that case, we have to add a MAC anyway. Can anyone please explain this to me?

One small question, from the DDH assumption we know $g^{xy}$ is random.

Actually, that's not true.  What the DDH assumption says is that we cannot distinguish $g^{xy}$ from $g^z$; however it does not say that we can't distinguish either from a random string.

Indeed, we can; if the order of $g$ has no small factors, then $g$ must be a quadratic residue (that is, there must exist a value $h$ with $h^2 = g$; this is easily tested); and hence $g^{xy}$ must also be a quadratic residue.  However, a random string is not a quadratic residue with probability 0.5, hence that serves as a distinguisher.

And, if $g$ is not a quadratic residue, then neither the DDH assumption nor indistinguishability from random hold, assuming the attacker can see $g^x$ and $g^y$; that's because $g^{xy}$ is a quadratic residue iff at least one of $g^x$, $g^y$ is a quadratic residue (hence the attacker can compute whether $g^{xy}$ is, even though he doesn't know the value).

This is why Yehuda is telling you to hash $g^{xy}$ first; $g^{xy}$ is distinguishable from a random string (although not necessarily due to a bias in any of the individual bits), $\text{hash}(g^{xy})$ is not.