Decisional Diffie-Hellman assumption vs decisional bilinear Diffie-Hellman assumption For the Decisional Diffie-Hellman (DDH) assumption we know that:

Given $g^a$ and $g^b$ for uniformly and independently chosen $a,b \in Z_p$ the value of $g^{ab}$ looks like a random value in group $\mathbb{G}$.

For the Decisional Bilinear Diffie-Hellman (DBDH) assumption we know that:

In a group $\mathbb{G}_0$ of prime order $p$, let $a,b,c \in \mathbb{Z}_p$ be chosen at random and $g$ be a generator of $\mathbb{G}_0$. The adversary when given $(g,g^a,g^b,g^c)$ must be able to distinguish a valid tuple $e(g,g)^{abc} \in \mathbb{G}_T$ from a random element $R \in \mathbb{G}_T$.

I cannot clearly understand the difference between both. Can someone state the difference of each and when to consider each one. I know that DBDH is used when considering pairings but I am still confused about the difference of both.

I don't know if it can helps. But actually, you can win the DDH game if you are using pairings.

Suppose you are given $X = g^x$ and $Y = g^y$, you can apply $e(X,Y) = e(g,g)^{xy}$.

Given $Z$, your goal is to know if $(X,Y,Z)$ is a DDH triplet.

You can test, using useful properties of pairings, if $e(g,Z) = e(X,Y)$ and so you can distinguish from a random element.

So I think that's why we consider 3 numbers to distinguish.

You can also think about Key-exchange Diffie-Hellman and Joux "Tripartie DH" as described in this PDF.


How can I store confident data with OpenID? I want to make a system that needs to store some confident user information in a database. I intend on using OpenID for user authentication.

I would like encrypt the data in a way that it can only be decrypted when the user is logged in. What are the most common approaches to storing user's data securely in such a setup?

Let's have a look on how OpenID works.

Alice wants to log into Bob's website using Charles as her identity provider. (So, you are Bob in this scenario.)

Alice fills her OpenID alice.openid.example.org into Bob's web form.
Bob (or Bob's server, actually) transforms this into a canonical form https://alice.openid.example.org/, and fetches this resource to find out who is Alice's OpenID provider (https://charles.example.com/openID/)
Bob redirects Alice's browser to Charles' web site, Charles then somehow checks that it is really Alice who is currently logged in (maybe asking Alice for confirmation), and redirects Alice's browser again to Bob, sending also some information about Alice for Bob along the way.

The information which Bob gets is either signed using a MAC with some previously negotiated common secret (between Bob and Charles), or will be later checked by direct interaction between Bob and Charles.

There is nothing in here which can be used as a private/secret key for Alice's user data by Bob, so there is no way Bob can encrypt something in a way that can be only decrypted with Charles' help (i.e. Alice's OpenID).

(Also, as Alice can use OpenID delegation, Alice can change here OpenID provider without changing her OpenID, and you surely want to have her data being still decryptable.)


SHA256 IVs / NUMS numbers I've read that if the IVs for SHA256 were arbitrary and / or unknown (secret) than a backdoor to predict outputs would be possible.

How do the values chosen for the IVs / publishing the values prevent such a backdoor and if the values were arbitrary / secret, how would such a backdoor work?

I think it'd be more accurate if one says "if IV were chosen arbitrary and / or unknown, then backdoors might be possible".

From what I know, the SHA256 IVs are chosing from the fraction parts of well known irrational numbers (though I'm not sure it's sqrt(2) or pi or something else). This way, the only being(s) capable of crafting a backdoor, would be the supreme being(s) beyond our Universe.

Similarly, in RFC 3526, modulus is chosing using pi to avoid backdoors. As a side note, sadly, small modulus are vulnerable to mass pre-computation attacks.


Random Coin Flip using ElGamal and a Trusted Party An old exam question I am trying to figure out:

  Consider the following protocol for two parties to flip a fair coin.

  Trusted party T publishes her public key pk
  A chooses a random bit $b_A$, encrypts it under pk, and announces the
  ciphertext $c_A$ to B and T
  B does the same and announces a ciphertext $c_B$
  T decrypts $c_A$ and $c_B$, and announces the results.
   Both parties XOR the results to obtain the random value $b_A \oplus b_B$.

  (a) Argue that even if A is dishonest (but B is honest) the final
  value of the coin is uniformly distributed.

  (b) Assuming that T uses ElGamal (where bit $b$ is encoded as $g^b$ before encryption),
   show that a dishonest B can bias the coin to any value he likes.

I can figure out a, but I am having trouble with b.

ElGamal encryption works like this:

We work in a cyclic group $G$ of order $q$ (a prime integer), with $g$ being a generator. Here, we note the operation multiplicatively. For instance, we work with integers modulo $p$ (a big prime such that $q$ divides $p-1$) and $g$ is one of the $q$-th roots of $1$ modulo $p$.
Private key is $x$, an integer modulo $q$.
Public key is $y = g^x$ (i.e. $g^x \mod p$ if we use integers).

A chooses random bit $a$, and a random integer $k$ modulo $q$, and announces $c_A = (g^k, g^a·y^k)$ (encryption of $g^a$ with ElGamal). The second half of that encrypted message is equal to $g^{x·k+a}$. B sees these values.

To bias towards 0, B can simply send the exact same value ($c_B = c_A$). B does not know the value of the bit from A, but he knows that by sending the same value, he forces the final XOR to be a 0. To make the manipulation less obvious, B can choose a random integer $f$ modulo $q$ and send:
$$c_B = (g^k·g^f, (g^a·y^k)·y^f)$$ (i.e. values computed from those sent by A). If you expand these equations, you will see that $c_B = (g^{k'}, g^a·y^{k'})$ where $k' = k+f$. B knows neither $a$ or $k$, but he sends a valid ciphertext for the same value $a$, and with a uniformly chosen random $f$ this cannot even be detected. This is how B biases the coin to 0 with 100% success rate.

To bias towards 1, the construction is a bit more complex. B computes this:

$$ c_B = ((g^k)^{q-1}·g^f, (g^a·y^k)^{q-1}·y^f·g) $$

for a random $f$ modulo $q$. If you expand this equation, you will see that $c_B$ is a valid ElGamal encryption of $g^{a·(q-1)+1}$. Since $g$ has order $q$, $c_B$ is thus the encryption of $g^1$ if $a = 0$, and $g^0$ if $a = 1$. Thus, B always sends the bit opposite of the bit from A, guaranteeing a coin toss of 1. Furthermore, the random $f$ makes sure that the manipulation is not detectable.

Generally speaking, this exploits the homomorphic property of ElGamal: given the encryptions of $m$ and $m'$, one can compute a valid encryption for $m·m'$, without knowing $m$ or $m'$.


point addition for elliptical curves According to http://www.secg.org/sec1-v2.pdf#page=13 ,

  Rule to add two points with the same x-coordinates when the points are
  either distinct or have y-coordinate 0:

  (x, y) + (x, −y) = O for all (x, y) ∈ E(Fp)

  — i.e. the negative of the point (x, y) is −(x, y) = (x, −y).

The fact that it says "when the points are distinct" makes it sound like it applies when the x coordinates of both points match but the y coordinates do not.But if that's the case then it seems to me that that'd make the "or have y-coordinate 0" bit redundant? y is not equal to -y so it seems to me that that's redundant? I mean, I guess y is equal to -y over mod p but in ECC is it even worthwhile to handle the use case where x or y are greater than p?

And what about adding (x, 0) to itself? At that point do we do point doubling, since the points are the same or do we just return 0 because of the "or have y-coordinate 0" bit?

If y was 0 I guess you'd be doing $\frac{\mathbb{3x}_{1}^2 + a}{2y_1}$ or $\frac{\mathbb{3x}_{1}^2 + a}{0}$ so it seems like it might be good to avoid it all together by returning $\mathcal O$ but idk.

And plus, using that rationale then what is supposed to be done for when the two coordinates are different? At that point $\lambda$ is $\frac{y_2 - y_1}{x_2 - x_1}$ so what if both x coordinates match whilst the y coordinates didn't? At that point you'd have another division by zero error..

Addition of a point with itself is "just" the limit case of normal addition. Geometrically, point addition starts with a line that goes through the two points to add; point doubling uses the tangent to the curve on that point, which is what you expect to have when the two points are made very close to each other.

In that geometric interpretation, the tangent to the curve on a point $P = (x,0)$ is vertical, and thus won't intersect the curve anywhere else; or, more accurately (using projective geometry terminology), that vertical line meets the curve again only at infinity. The sum of $(x,0)$ with itself is thus the point at infinity. This also means that $(x,0)$ is its own opposite.

Now, in cryptography, we use curves in finite fields, which are discrete and don't look like curves. One interesting point to make is that a point $P = (x,0)$ is such that $2P = \mathcal{0}$, i.e. it is a point of order 2. Since an elliptic curve is a group, if there is a point of order 2, then the total curve order must be a multiple of 2. Many standard curves (e.g. the very widespread NIST curve P-256) have been chosen to have a prime order, hence odd; it follows that, for such curves, there is no point $(x,0)$, and the question of doubling such a point does not arise at all.


Why do we approximate R-1 rounds during linear or differential cryptanalysis? I am currently looking into differential and linear cryptanalysis. I am however unsure why do we only approximate only R-1 out of R rounds - is it because we already know the output or why ?

I have read "Linear and Differential Cryptanalysis" by Howard M. Heys, but I am not able to find it there, he only takes it for granted.

Thank you for your answers

is it because we already know the output or why ?

It's one of the strategies we use to turn a distinguisher (which a differential or linear characteristic) into a key recovery attack.

Here's how it goes; suppose we have a distinguisher that works over R-1 rounds, that is, given a number of plaintext/ciphertext pairs, it can tell us (with advantage over random guessing) whether or not those pairs there generated via the R-1 cipher (and an unknown key).

Then, we can then test guesses for the subkey on the last round on the full R round cipher.  We take our guess of the subkey (or a subset of that subkey, if our distinguisher doesn't rely on the entire ciphertext block), and then decrypt it through the round function to get the intermediate state after R-1 rounds.  Then, we can use our R-1 distinguisher to check whether the known plaintext and our guesses that the R-1 state are consistent with the R-1 cipher; if it is, then our guess for the subkey (or subset) is likely accurate.

If successful, this gives us some of the subkey bits; depending on how the key scheduling works, we may be able to deduce some key bits directly; alternatively, we may need to rely on other distinguishers (based on our knowledge of some of the subkey bits) to obtain others.

Obtainly, the details of how this works can vary significantly depending on the details of the cipher; this is just the general strategy.


Unconditionally Secure Authentication I'm trying to add the authentication for my One-Time Pad implementation.
I know that to provide Unconditionally Secure Authentication I need to use the One-Time MAC authentication.

But I don't understand why a solution as the following (that's a lot more easy to implement) doesn't provide the same security level :/

ciphertext = ((plaintext || H(plaintext)) XOR OTPKey)

With:
|| = concatenation
H = SHA-2
OTPKey is long enough to encrypt the plaintext and H(plaintext)

Mallory here can't brute force the ciphertext (because of the one-time pad), so he can't get the correct plaintext nor the digest...
Is this right? Can this provide unconditionally secure authentication?

EDIT 1
I know that in practice it's vulnerable to known-plaintext attacks so please, don't consider it in this particular case. I'm interested in Unconditional Security in the sense that both the plaintext and the digest can benefit of the Information-theoretic security provided by One-Time Pad.
I'm interested in passive attacks and not in active ones.
Assume that Mallory here knows only the ciphertext ;-)

EDIT 2
In other words: can I be sure that an attacker can't obtain the plaintext exploiting possible vulnerabilities introduced by the use of a hash function for the digest calculation?

Variant
How about this variant? Can I say that it provides Information-theoretic security for the plaintext AND it is vulnerable against active attacks with complexity of 2^256?
So in this case I can provide a certain level of security against known-plaintext attacks too (even if computational security).

ciphertext = (plaintext XOR OTPKey)
message = (ciphertext || H(ciphertext || K2))

With:
K2 = 32 bytes of random key, NOT correlated with OTPKey

Thank you to everyone :)

You need to prove that there does not exist a way of finding $x$ and $y$ so that $plaintext \oplus x$ and $H(plaintext) \oplus y = H(plaintext \oplus x)$. The problem is that the attacker is unlimited in time, so the above may actually be possible. (It suffices to prove that there exist messages for which this can be done.)

In addition, in order for this to be secure, it has to behave as a secure MAC, even known the plaintext. So, saying that you don't care about known-plaintext attacks doesn't make sense. I'll explain. Assume that the distribution over the plaintext is that with probability $0.7$ the plaintext is "attack today" and with probability $0.3$ it is "don't attack". Then, an attacker can assume that the message is "attack today" and modify it to "don't attack" (by XORing in "attack today XOR don't attack" to the first part, and XORing in "H(attack today) XOR H(don't attack)" in the second part. The result will be that with probability $0.7$ the message will be changed to "don't attack" and with probability $0.3$ an invalid message will be received. This should not be allowed under any reasonable definition of security.


DUKPT PIN decryption I have actually been able to carry out a DUKPT data decryption successfully, which was also been confirmed with the BP-Tools - Cryptographic Calculator.

After understanding the differences between the DUKPT PIN and DUKPT DATA from their respective Variant Constant "according to ANSI X9.24, Part 1 document the DUKPT section".

I already changed the index of my keys [Varaint Constant] tallying with the Variant Constant, for the PIN decryption which are 7 and 15 compared to that of the DUKPT DATA which are 5 and 13 which worked successfully.

What i would now want to understand is this, after checking through this git used for the DUKPT data decryption

What am i actually getting wrong in this process, or what am i yet to really understand.

Because, trying out the BP-tools DUKPT data decryption, it is really working out with the git provided above, but still having a slight issue to getting the DUKPT pin work out, while been compared with the BP-Tools Calculator.

The question is: Is there any other thing to take note of, apart from the Variant Constant when doing a DUKPT PIN decryption?

Had to use the BP-Tools to clarify the output I am getting so as to know the main difference between the DUKPT-PIN and the DUKPT-DATA.

For the DUKPT-PIN: The entered PEK value will be XOR-ed with the value of 00000000000000FF 00000000000000FF (see ANSI X9.24-2004 Appendix A, A.5, page 42) as part of the processing.

For the DUKPT-DATA: As part of the processing, if the data variant key = tdesEnc(key, key);is checked XORing it with  0000000000FF0000 0000000000FF0000

All i need to do was just to comment out the  key = tdesEnc(key, key); which serves the same function as that of the Data Variant which is not used in the process of carrying out DUKPT-PIN


When using DES, how large would the key space be if we only use letters as characters? Would it be safe? Or is it susceptible to brute force attacks or something else?

A DES key is 56 bits. If we assume letters are ASCII encoded and take 8 bits each this means a DES key of only letters would be 7 letters long. Given that there are 26 letters in the roman alphabet we would have $26^7 \approx 2^{33}$ possible keys, or if we allow uppercase and lowercase, $52^7 \approx 2^{40}$ possible keys. Both keyspaces can quickly be enumerated with modern hardware and can easily be brute forced.


Is there a standard prefix random padding scheme? Is there a standardized padding scheme which is prefix instead of postfix
and that uses random bytes except for the first byte which would be the
length of the padding?

I know of no standard like that and also doubt it exists.

It would have similar disadvantages as random padding at the end, which is no longer in use: subliminal channel, consumption of randomness which may be expensive. Additionally, it would require knowing the message length in advance, which is a practical limitation.


Windows certreq full response file I'm using the Windows certreq command line tool to submit a CSR for signing to a Windows Server CA.

certreq.exe -attrib "CertificateTemplate:WebServer" -submit webapp.csr webapp.cer webapp.p7b

It's working as expected I'm getting the Base64-encoded certificate webapp.cer and the certificate with the certificate chain webapp.p7b.
But the Microsoft documentation specifies that an extra parameter can be used named FullResponseFileOut which generates a Base64-encoded certificate file.

What is the purpose of this "Full Response File Out" and is there any way to display/decode it's content with OpenSSL or any tool?

The Full Response has additional information over and above the P7B file with information such as the CMC response and some chaining information.  I'd go as far as to say it's not really relevant in day-to-day use.

You can look at them all with certutil.exe and make your own mind up though - simply pipe the outputs to a text file and read at your leisure. If the extra parameter to your command above is webapp.ful the following will allow you to read all of the files with a text editor:

certutil webapp.cer > cer.txt
certutil webapp.p7b > p7b.txt
certutil webapp.ful > ful.txt


Period finding for Quantum Computers Shor's algorithm shows how a quantum computer (with sufficiently many qubits) can solve the factorization problem efficiently. Also the discrete logarithm problem can be solved efficiently with such a quantum computer.
Both boil down into finding the period of a certain function.
Can quantum computer find the period of any given function efficiently? Are there any requirements towards the function?
Closely related, the discussed post-quantum schemes (e.g. the ones submitted to NIST) do not provide a function whose period could be exploited to break the scheme?

Can quantum computer find the period of any given function efficiently? Are there any requirements towards the function?

Well, the function has to be periodic; that is, we have, for some $c > 0$, $f(x) = f(x+c)$, for all $x$ [1].
For both factoring and discrete log, we have such a function; and we know how finding the period of that function will give us the answer.
However, postquantum algorithms, we don't have such a way.  For code-based schemes, no periodicity is apparent.  For lattice-based schemes, there is (periodicity is inherent in the idea of a lattice), however we don't know how to convert finding such a periodicity into (say) an answer to the shortest vector problem.

[1]: Actually, I believe Shor's algorithm will work even if the above relation holds for most $x$; however for the functions of interest, true periodicity holds...


Has a collision ever been found for SHA-1/2/3 when truncated to 128 bits? I'm aware that MD5 is broken, and collisions have been found for it. I'm interested in other hashes (SHA-1, SHA-2, SHA-3) when truncated to the same digest size, i.e. 128 bits.

The time complexity of a collision attack is 2^(n/2) (the "birthday attack"). So in the case of a 128 bit hash, one would have to hash 2^64 inputs for a 50% probability of finding any two inputs hashing to the same value (though a collision might be found much earlier in practice).

The currently fastest single Bitcoin mining machine performs about 5 trillion double SHA-256 hashes per second, so assuming 10 trillion/sec for single ones, and assuming the inputs tested would not be larger than one block it would amount to:

2^64 / 10*10^12 / 31536000 = 5.85 years

To scan enough hashes to yield a 50% chance of a collision. Though at that point the machine would have to allocate at least 16 * 2^64 ~= 2.95+e20 bytes ~= 295 exabytes of memory for storing the previous hashes. With today's computing capabilities, this seems somewhat reachable (though not very trivial, and may be extremely expensive to handle the enormous memory/storage  requirements).

Has this already been tried/achieved? any references? (I'm interested mostly in attacks using brute-force search, but more sophisticated ones are also relevant).

I'm not aware of any case where somebody actually searched for such a collision.

However it would certainly be possible as the same workload ($2^{64}$) was already accomplished a few years ago (2002) by this project, having brute-forced RC5-64.

Now assume you'd use the full power of the bitcoin blockchain (300 Peta-Hashes / s = 600 Peta-Hashes /s for single hashing(19th may 2015)) you'd expect a (64-bit-)collision after 30.74 seconds ($=2^{64}/600*10^{15}$).

As noted correctly by poncho there are algorithms that help you overcome the massive amount of memory you calculated. Of particular interest would be a "memoryless" variation of Yuval's birthday attack(book page: 369, pdf page: 50 of the "Handbook of applied Cryptography").
This related question may be helpful.


How does the round function in this particular Feistel cipher work? I have this exercise that I found on the Internet. It is originally in French but it says:

  Exercise 3: (Feistel scheme). We consider a two-round Feistel cipher defined as follows:

  The length of the blocks is 8.
  The key $K = [k_1, ..., k_8]$ is of length 8. The two round keys are $K_1 = [k_1, ..., k_4]$ and $K_2 = [k_5, ..., k_8]$, where the $k_i$ are the bits of the key $K$.
  The function $V = f (U, U ')$ is defined by writing the bits $v_i$ of $V = [v_1, ..., v_4]$ as functions of $U = [u_1, u_2, u_3, u_4]$ and $U '= [u'_1, u'_2, u'_3, u'_4]$ as follows:

  $$\begin{aligned}
v_1 &= u_1 u'_4 ⊕ u_2 u'_3 ⊕ u_4 u'_3, \\
v_2 &= u_1 u'_2 ⊕ u_3 u'_1, \\
v_3 &= u_1 u'_4 ⊕ u_1 u'_3, \\
v_4 &= u_3 u'_3 ⊕ u_1 u'_1.
\end{aligned}$$

  Let the key be $$K = [1,0,1,1,0,0,1,0],$$ and let the message be $$M = [0,1,0,0,0,1,1,1].$$ Calculate the encryption of $M$ using the Feistel scheme above.
  Decrypt the message $C = [0,1,1,1,0,0,1,1]$ which was encrypted with the same key.

So my question is: I understood that $U$ is actually the right half of the plaintext and that $U'$ is actually $K_1$ in the first round and $K_2$ in the second. And I solved the exercise based on this understanding. But my teacher said that my understanding is wrong and that $U$ has to be the left half of the plaintext, while $U'$ is the right half of the plaintext. She means that the Feistel cipher is changed in this case. She added that her understanding is more logical and that mine could not even be considered as a possible one in this context. I think that if her understanding is logical and correct, mine is more so.

What do you think? I know this might seem like a trivial question but I really want to read other people's opinions and be convinced by the more logical understanding and explanation.

It seems to me that the exercise is missing some context (which is presumably to be found in the textbook it's taken from).  Specifically, it defines a function $$f: \{0,1\}^4 \times \{0,1\}^4 \to \{0,1\}^4,$$ but does not explicitly state what role this function is supposed to play in the Feistel encryption process.

That said, the usual way to define a Feistel encryption round (as given e.g. on Wikipedia) is $$\begin{aligned} L_{i+1} &= R_i, \\ R_{i+1} &= L_i \oplus F(R_i, K_i), \end{aligned}$$ where $L_i$ and $R_i$ are the left and right halves of the input block to encryption round $i$, $K_i$ is the $i$-th round subkey, and $F$ is some nonlinear function.

Presumably, the function $f$ defined in the exercise corresponds to the nonlinear round function that I've denoted by $F$ above.  Thus, presumably, one of its arguments is supposed to be the round subkey, while the other one is one of the input half-blocks, just like you say.  However, what's not obvious from the given definition is which argument is supposed to be the subkey, or whether the other argument is supposed to be the left or the right half-block (since either convention can be used, and they're essentially equivalent).

Anyway, if the exercise comes with an answer sheet, it should be easy enough to verify this just by doing the encryption is each of the possible ways and comparing the results with the expected answer.  Even with the small block size, getting the right answer just by change from the wrong encryption process should be pretty unlikely.


Which attacks can be avoided by the use of OFB instead of ECB? For a file encryption program, I was told to use Output Feedback mode (OFB) instead of ECB (Electronic code book) mode.

Which attacks can I avoid by this choice?

OFB is a mode of operation to ensure confidentiality of messages a) longer than the block size of the encryption algorithm, and b) that can be re-broadcast. The motivation for these kinds of modes it to avoid the weaknesses that come from using plain ECB mode.

To be precise, the typical attack on ECB mode involves analyzing the ciphertext and looking for repeated blocks. Repeated ciphertext blocks mean repeated plaintext blocks, and knowing about repeated plaintext can help the attacker analyze the captured ciphertext. (Meaning that ECB is not semantically secure.) In some cases, this is enough for the attacker to learn all, or almost all, of the plaintext. OFB mode prevents this from happening by using randomized encryption to ensure that repeated plaintext within the message does not cause repeated ciphertext.

OFB is resistant to ciphertext errors in that if the ciphertext has bits modified in error, only the bits of the plaintext that directly correspond to the ciphertext are modified.

Because it OFB mode works like a stream cipher, it has the typical weakness that allows known plaintext to be easily modified by an attacker. (Ie, if OFB mode produces a keystream $K$, then the ciphertext $C$ is defined as $C_i := P_i \oplus K_i$, so if $P_i$ is known to the attacker then so is $K_i$, so they can create a new ciphertext $C'_i := P'_i \oplus K_i$ where $P'_i := P_i \oplus X$ and $X$ is a value chosen to produce the desired modified plaintext $P'_i$.) But since message confidentiality (the goal of OFB) does not encompass message integrity, this is not necessarily a big deal.


Cryptography algorithms that take longer to solve on a GPU than a CPU I know that Graphics cards are faster at solving algorithms like SHA-256 because of the many builtin processors, but are there Algorithms that take actually longer on a Graphics card than on a modern consumer CPU (Amd/intel)?

This specific situation is a central part of the analysis of password hashing functions. Indeed, for hashing a password, we want a function which is:

slow in a tunable way;
such that the most cost-effective hardware for evaluating many instances of the function is the hardware that the expected defender will use, i.e. a "normal PC".

"Cost" here means actual money. For the attacker, it does not matter whether he will need 10, 100 or 1000 units of whatever hardware he'll use; only the total cost will be necessary. It can be argued that with modern hardware, in particular GPU, the majority of the budget for crunching passwords will be spent on electrical power, not on purchasing the hardware. Therefore, it makes sense to define the cost of the function with regards to the energy consumed by its computation, on both general-purpose CPU, and various GPU.

The bcrypt password hashing function appears to be indeed such a function, that is more expensive (energy-wise) to compute on a GPU than on a CPU. The bcrypt feature that makes it so is that it is organized around an internal 4 kB array of data which is continuously read and modified in a way which is not amenable to shortcuts, and at pseudorandom addresses. GPU are not well-equipped for that; if you try to implement bcrypt on a GPU, you will experience considerable contention for data access, and most of the GPU cores will be stalled at any time (and such a stalled core still consumes power).

The Password Hashing Competition was organized to define new functions that fulfill a larger goal, namely to not only be more CPU-friendly than GPU-friendly, but also to "hold the line" to some extent when facing attackers with FPGA or custom ASIC. The main tool used by most candidates was again RAM, but more of it; the underlying assumption is that modern PC (servers, desktop systems...) contain a thoroughly optimized memory bus that cannot be operated at a substantially lower cost by custom hardware. It is unclear how far that assumption holds.

One of the PHC candidates, called Makwa (which I designed), did not use RAM but modular arithmetics. This is not expected to fare well against FPGA and ASIC, but, for GPU, it appears to behave well: according to my analysis, costs on CPU and GPU appear to be roughly on par for a 2048-bit modulus, and larger moduli benefit the CPU more than the GPU.

To sum up, both bcrypt and Makwa seem to be valid answers to your question, and they do so through quite different means.


The existence of two-round zero-knowledge proofs Does there exist any (im)possibility results for two-round private-coin non-auxiliary input zero-knowledge proofs for languages outside BPP?

Under the following assumptions there does not even exist three-round private-coin zero-knowledge proofs for languages outside BPP. See here.

The theorem holds assuming:

Sub-exponentially secure one-way functions.
Sub-exponentially secure indistinguishability obfuscation for circuits.
Exponentially secure input-hiding obfuscation for multi-bit point functions


Are there asymmetric cryptographic algorithms that are not based on integer factorization and discrete logarithm? In the computer security class (in which cryptography is a big chapter) that I took, I remembered the professor said about current asymmetric cryptography algorithms are based on integer factorization (i.e. prime numbers) and discrete logarithm.

So my question is, are there any asymmetric cryptographic algorithms that are not based on these two mathematical fields? Is it that hard to come up with a strong algorithm without using prime numbers and logarithm?

Yes there are other hard problems you can base asymmetric cryptography on.

Lattices. The NTRU systems is based on the shortest vector problem in ideal lattices. Lattice-based cryptography is of much interest these days for two reasons: (1) unlike factorization and discrete logarithms, there isn't an efficient algorithm for breaking these problems on a (still theoretic but should happen within our lifetime) quantum computer; (2) you can use lattice-based systems to do arbitrary operations on data while it is still encrypted (not with NTRU though but other lattice-based systems).

Coding Theory. The McEliece system is based on decoding linear codes. It is a very old system but recently has seen renewed interest for the same post-quantum reasons as lattice-systems.

Misc. There are other more obscure (research-level) cryptosystems based on things like learning parity with noise, learning with error (related to SVP in lattices), subset sum problem (including a famous broken example), solving multivariate or diophantine equations, etc.

In response to your second question, is it that hard to find alternatives, the answer is it is reasonably hard. For most cryptographic primitives, you need to find examples of functions that are hard to invert, and for asymmetric encryption specifically, you are generally interested in functions that have a specific value that allow them to be inverted (but only if you know that value). See trapdoor functions. It is difficult to find new candidates for trapdoor functions and to establish they are suitably hard.


Why 3 round Feistel cipher are not common Luby and Rackoff showed that 3 rounds are sufficient to make the Feistel networks a pseudorandom permutation.

Question: why are 3 round Feistel Ciphers not common?

My thoughts about the round functions of Luby and Rackoff construction are

They are hard to find one
They are hard to analyze
They are complex to fit small devices.
3 rounds of Luby and Rackofd constructions are slower than 16 rounds non-Luby and Rackoff constructions. Assuming that they have the same security.

The main issue is that this only holds if you start with a PRF. Constructing a secure PRF is just as hard as constructing a secure strong PRP, so haven't gained much. In practice we typically start with constructing a PRP and then turn it in into a PRF, not the other way round.

Feistel based blockciphers use many rounds, because their round functions are individually weak but also faster than a PRF.

In addition we typically want a strong PRP, so you need at least four rounds, not three. Another limitation is that the block size must be big enough for the target security level (IIRC you need 2n-bit blocks for n-bit security while we often target a security level equal or higher than the block size (e.g. AES has 128-bit blocks and 128/192/256-bit keys with the security level matching the key size).

There is one area where Feistel constructions using a small number (two to four) strong round functions are popular: Large and variable width permutations. OAEP is based on a two round feistel structure. There is the EME mode for wide block encryption.


Are tags longer than 128 bit possible for AES-256-CCM and AES-256-GCM? I have an existing application that uses AES-256-CBC for encrypting data blocks, and HMAC-SHA-256 on the plaintext for eliminating duplicate data blocks.

For performance reasons, I would like to move to AES-256-CCM and using the resulting authentication tag instead of the SHA-256 .

However, this algorithm is designed to generate a 128 bit tag. This is more prone to hash collisions than HMAC-SHA-256. 128 bits doesn't seem to be sufficiently future proof to ensure collision safety for a system potentially storing enormous numbers of blocks.

Is there a way to extend the tags of AES-256-CCM or AES-256-GCM to have 256 bits strength?

Edit: What I'm try to accomplish is to encrypt a set of objects which are eventually stored in Amazon S3 in a content addressed way, that is, the key of the object should be a hash of the plaintext . People with access to my Amazon S3 bucket should not be able to be able to decrypt the data, nor should the scheme allow checking whether a specific known plaintext exists or not in the bucket. That is why the current scheme is HMAC-SHA256 on the plaintext to choose a key for the object, and then encrypting the object using AES-256-CBC with a unique and unpredictable IV.

AES-256-CBC and HMAC-SHA256 are rather slow, and thus I had the idea to use some form of fast authenticated encryption.

No, there is no black-box type way of increasing the security strength of the tags of CCM and GCM. Because in this case you would apply a deterministic function which couldn't bring you any increases in security as a collision on the input would still lead to a collision on the output.

For CCM there is also no non-black box type of way, at least if you want to stick to AES. This is because CCM uses CMAC internally which is close to CBC-MAC which is CBC adapted for authentication. The authentication tag for CMAC is the result of an AES encryption and AES is solely specified for 128-bit blocks (which is the size of the AES in- and output).

GCM is similar in that respect to CCM, in that the output of the polynomial hash function is actually XOR encrypted with the output of an AES block. However if you pick a longer polynomial for GCM (which will instantly break all implementations you may have) and if you maybe make some educated changes to how often the polynomial gets evaluated, you might get a stronger tag as the result. However this would most-likely be a GCM look-a-like, but would needs its own (difficult) security analysis and new implementations.

On a final note, the tags of CCM,  GCM and HMAC are MACs. MACs are not neccesarily designed to be good hashes (for a fixed key), because the threat model is different for them. They are designed so that you can't find a tag for a message for which you haven't seen a tag before. They are absolutely allowed to output two different tags for the same message or the same tag for two different messages (because an adversary could maybe have predicted a collision but not for which message pair).


Does ElGamal authentication exist? Are there any natural ways to transform ElGamal encryption system or ElGamal signature scheme into an authentication protocol?

You can turn any public-key encryption or signature system into an authentication protocol, and that includes both ElGamal encryption and the ElGamal signature scheme.

Protocols for this can be found in most textbooks. E.g. 10.3.3 in Handbook of Applied Cryptography.


When to use RSA and when ElGamal asymmetric encryption If i am not wrong in cryptography there are 2 basic cryptographic schemes for public key cryptography. RSA encryption whose security is based on the infeasibility of solving the factoring of big primes problem and the ElGamal encryption which is as secure as the discrete logarithmic problem. The question is whether or not there are specific circumstances where you must use ElGamal instead RSA and vice versa. What are the weak and the strong points of each?

To sum up is it harder under the same attacking model to solve the factoring problem or the discrete logarithmic problem?

Actually, for most applications where we want to use asymmetric encryption, we really want something a bit weaker: key agreement (also known as "key exchange"). When RSA or ElGamal is used for that, one party selects a random string, encrypts it with the public key of the other party, and the random string is used as a key for classical symmetric encryption. Therefore, we must add Diffie-Hellman to the list. You can imagine Diffie-Hellman as a kind of asymmetric encryption in which you do not get to choose the random value you are encrypting: less versatile than ElGamal, yet sufficiently powerful for most protocols where asymmetric encryption is used. SSL/TLS and S/MIME happily use RSA and Diffie-Hellman in practice. Diffie-Hellman, like ElGamal, relies (more or less) on the difficulty of breaking discrete logarithm, and is internally relatively similar to ElGamal.

Among differences between RSA, DH and ElGamal, one can find:

DH and ElGamal accept elliptic curve variants. They rely on hardness of discrete logarithm on elliptic curves, which is distinct from discrete logarithms modulo a big prime. Elliptic curve variants can use smaller fields, so while the mathematics are a bit more complex, performance is better.
RSA encryption (with the public key) is faster than the corresponding operation with ElGamal, or half of Diffie-Hellman. On the other hand, RSA decryption (with a private key) is a bit slower than ElGamal decryption or the other half of Diffie-Hellman (especially the elliptic curve variants).
An RSA-encrypted message is larger than an ElGamal-encrypted message or half a Diffie-Hellman, provided that elliptic curves are used for the latter.
Historically, RSA was patented in the US, while ElGamal was not -- which is why OpenPGP specified ElGamal usage, and GnuPG tends to favour it over RSA (the RSA patent expired a decade ago, so this is no longer an issue).
RSA is described by a clear standard, which is free (as in "free beer"), and says precisely where each byte should go. That's very good for implementers: it reduces the possible mishaps. On the other hand, the Diffie-Hellman standard (or that one for the elliptic curve variant) is not free, and, in my experience, less clear. There is no established standard at all for ElGamal, except the bits about it in OpenPGP, which do not deal with ElGamal "in general".

What protocol designers should do is to make some provisions for algorithm agility: the protocol should work with various algorithms, with fields indicating which algorithm is actually used. Algorithm agility helps quite a lot with dealing with future cryptanalytic advances, and with regulatory requirements.


Aggregation signature and verification I'm not even sure of the appropriate terminology to use to describe my problem so bear with me if the explanation is not exactly formal.

Imagine I have a simple digital calculator, with a screen and some buttons. I bring this calculator into a room full of people. I ask them each one by one to take the calculator and accumulate their age on the calculator, such that after everyone is done the calculator screen reads the combined age of everyone in the room.

The trick is that there is a lot of people in the room, and some of them are liars. I need to solve two problems relating to this:

I need to know if some user(s) has lied about their age
I need to know if some user(s) double counts their age

It's enough for me to recognise and throw away a bad result, not necessarily know who messed with the result.

We can assume that the calculator is rather large (ex. has a 256-digit display), but not arbitrarily large. This means that I can punch in a number that contains some identity information as well as my age, but I don't have enough digits to just have everyone's signature side by side.

Assume I've been given a value to verify.

There is a lot to this question, and I believe some concepts of multiparty computation can be useful in relation with this problem. There's one catch: lying is a very abstract concept, even with a simple and well defined concept as age.

So, for the sake of the argument, let's define some conditions:

Each participant introduces a valid age value (i.e. within a given range -maybe 0-99, as Maarten proposed).
Each participant provides only one input to the protocol.
The counting entity is reliable.

For certain encryption algorithms (e.g. Lifted ElGamal) it is possible to prove that an encrypted value falls within a range without disclosing the value. Then, each participant $p$ has to generate a set $(p, E(a_p), proof_{a_p})$. When the counting entity has all the sets, it can verify each value of $p$ is unique. Since Lifted ElGamal is also additively homomorphic, the sum of all the ages can be computed without decrypting the values.

DISCLAIMER 1: if the counting entity cannot be trusted, the scheme gets harder, but the general spirit of the communication is similar.

DISCLAIMER 2: this is strongly based on protocols for voting. The verification of identity, adding and the decryption processes can be performed by different entities within the counting authority to keep a higher level of privacy around the encrypted values.

As Maarten suggested, here are some links to the relevant content:

Homomorphic encryption : a property of cryptosystems that enable some operations on the ciphertexts without decrypting the values.
Sigma protocols : a generic approach to Zero Knowledge Honest Verifier Proofs (ZKHVP).
Zero Knowledge : a long lecture on zero knowledge techniques. Set Membership is covered around the slide 144.
Estonian voting process : an example of a critical application based on the principle of division of responsibility within the counting (voting) authority).


Noise bound in FHE over the integers I'm studying the paper Fully Homomorphic Encryption over the Integers by Marten van Dijk, Craig Gentry, Shai Halevi and Vinod Vaikuntanathan.

I have questions about the proof of Lemma A.1.

In page 6, the element of public key is in the form of $x=pq+r$
and the encryption is
$$ c← [m+2r+2\sum x_i]_{x_0} $$

But in the proof of Lemma A.1., the public key is $x=pq+2r$
and the encryption is
$$ c← [m+2r+\sum x_i]_{x_0} $$

This problem made me confused.
I tried to proof with first definition, but I encounter with another problem.
When I follow the same flow of the proof with first definition,
I reached that the noise term is $$(m+2r+k*r_0+ \sum 2r_i )$$
What I need to next is to get the upper bound of a $|m+2r+k\cdot r_0+ \sum 2r_i|$.
So I got
$$|m+2r+k*r_0+ \sum 2r_i| \leq m+2\cdot2^{\rho\prime} + \tau \cdot 2^{\rho}+\tau \cdot 2^{\rho} =m+2\cdot2^{\rho\prime} +2 \tau2^{\rho}$$

If the definition of permitted circuit in this thesis is correct, at least
$$m+2\cdot2^{\rho\prime} +2 \tau2^{\rho} \leq 2^{\rho \prime +2}$$
should be satisfied.

Can anybody help to get upper bound of noise?

Original question

I'm reading https://eprint.iacr.org/2009/616.pdf

I am reading the proof of Lemma A.1 which is in page 21.

In the page 22, the thesis tells that the noise is at most $(4\tau + 3)2^\rho < \tau2^{
\rho+3}$.

But I cannot follow the inequality.

Could you guys help me to understand the proof of Lemma A.1?

Just expand it out.  You get $4\tau \cdot 2^\rho + 3 \cdot 2^\rho$.  Then,

$\tau \cdot 4 \cdot 2^\rho = \tau \cdot 2^2 \cdot 2^\rho = \tau \cdot 2^{\rho + 2}$

and

$3\cdot 2^\rho < 4 \cdot 2^\rho = 2^{\rho+2}$.

Put it back together,

$\tau \cdot 2^{\rho + 2} + 2^{\rho + 2} < \tau (2^{\rho + 2}+2^{\rho + 2}) = \tau 2^{\rho+3}$


Can the fingerprint of a PGP key be combined with a phone number? Lets say I wanted to text a friend but I didn't want my carrier seeing my texts. I could just ask for a phone number, and have him/her text me a PGP public key. But, as everyone knows, the carrier can do a MITM attack easily. So what if we exchanged a different number, but kind of a combination of the 10-digit number and a PGP public key fingerprint using a pair function. Then I separate the phone number and the key, ask for a public key, and check the fingerprint.

Is it possible for me to do that while keeping that "number" down to about 15 base-36 or 64 characters? I want to keep the ID short so it can be easily typed on a phone. I am planning on using the 16 hex digit fingerprints. I've been trying for a solution but the best I can do for "FFFFFFFFFFFFFFFF" and 9999999999 is 19 characters of base-64 by concatenating the bits which is surprisingly shorter than using a pair function.

More information about Pairing Functions

Edit: Got a few comments about the exchange of the public keys.

The phone separates the fingerprint from the phone number using that ID number your friend gave you. Then the your phone sends a message to the phone number, which returns a public key. Since you gave your friend the key combined with the phone number, the phone is able to check the key against the fingerprint to see if the carrier attempted to do a little "trickery". Sorry if I didn't explain that well in the question.

Given a message space of $10^{10} \approx 2^{33.2}$ different phone numbers and $16^{16} = 2^{64}$ different fingerprints, you should expect to take no less than $\log_{64}(2^{33.2 + 64}) \approx 16.03$ base-64 characters, or $\log_{36}(2^{33.2 + 64}) \approx 18.61$ base-36 characters. Bit concatenation is fine in this case, assuming each fingerprint and phone number in the whole space is equally likely to occur.

However, what stops the carrier from still simply MitM'ing and swapping such an encoded pair of fingerprint and phone number with their own?


What prevents ProtonMail from sending me the wrong public keys? I've recently been looking at ProtonMail, an email service which provides transparent end to end encryption between users with PGP. In order for the encryption to be transparent, ProtonMail manages all of the public and private keys.

When sending an email from a ProtonMail account to another ProtonMail account, the ProtonMail server sends the destination's public key to the client. The client then encrypts the email using the given public key and sends the mail to the server to forward to the recipient, who can decrypt it with their private key.

Since ProtonMail's server only ever sees the encrypted email, and it doesn't have access to any cleartext private keys, it cannot read the email. According to ProtonMail, this means we don't need to trust the ProtonMail server to know it doesn't read the email (assuming it doesn't send malicious javascript with the client).

However, what, if anything, prevents ProtonMail's server from conducting a man in the middle attack by sending the wrong public key? If the server sends the public key corresponding to a private key they control, they could decrypt the email, then re-encrypt it with the correct public key, and send it to the intended recipient. In normal PGP the user must explicitly mark each public key as trusted, but no explicit trust is requested from the user of the ProtonMail client. So how does the ProtonMail client know to trust the public key sent by the server?

ProtonMail has a support page about this topic.

ProtonMail does not transparently solve this problem. By default, the client has no way to know if the server has provided the correct public key, it just implicitly trust keys sent by the server. Therefore, by default the client has no way to protect against man in the middle attacks from the ProtonMail server.

However There is an option to turn on manual trusting of keys, "Settings > Security > Address Verification (optional) > Prompt to trust keys". In this case, when encountering an unknown public key, the ProtonMail client will notify the user that the key is not trusted, and prompt them to "pin" the key. Keys must be pinned, per contact. Messages to contacts without pinned keys will be sent using keys from the ProtonMail server.

A pinned key is stored locally the client, and (presumably) encrypted and sent to the server, so it can be used from other devices when decrypted with the user's password. The client will always use the pinned key to encrypt messages for the corresponding address, and it will display an error if a message received from that address isn't signed with the correct key. It up to the user to verify that the key is correct, like in normal PGP.


How to make Fernet encryption produce the same ciphertext for the same data I am using a cryptography library for Python and it provides Fernet Module.

Now I have a plaintext to encrypt. It produces a ciphertext. Then I try to encrypt the same plaintext with the same key but the ciphertexts are different.

I need the ciphertext to be the same every time.
Do you know any way around this? Or maybe a different encryption technique?
Thanks in advance

It sounds like what you want is a deterministic authenticated cipher, or DAE, deterministic authenticated encryption, which has the property that an adversary can always tell when you have repeated messages, of course.

As far as I can tell, Fernet does not support any DAE.  Popular choices for DAE include SIV-type schemes like AES-SIV.  But you should have a good reason for using DAE first!  Most applications don't need it.


What is the most paranoid way to exchange messages? I'm looking for a way for Alice to send a message or a file to Bob in the most paranoid way possible (over the internet).

It can be asymmetric or symmetric. But According to some articles, AES 128bit, RSA, ECC are all broken or will be soon (with the new NSA Utah center).

I found PHPECC library on GitHub: https://github.com/mdanter/phpecc but I don't know how to generate private keys and change key length.

RSA is slow to get a decent security... AKA 2048-bit or more.

AES-256bit is fast and secure with a strong password... but I cannot figure how to communicate the password in the most paranoid way. (Again, please, not on a piece of paper :))

I've made a couple of schemas on a sheet, but I'm sure there's a better way than what I've imagine.

Any help or explanation, or good methods how to do that will be greatly appreciate.

EDIT:

OpenSSL Vulnerability: http://www.theregister.co.uk/2010/03/04/severe_openssl_vulnerability/

AES 128-bit: http://threatpost.ca/en_us/blogs/rsa-2010-experts-expect-several-ciphers-be-cracked-soon-030210

NSA is promoting ECC over RSA. And ECC 112-bit is broken:
http://www.nsa.gov/business/programs/elliptic_curve.shtml

http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

RSA is slow to get a decent security... AKA 2048-bit or more.

Well, if you want to be ultra-paranoid, then you'll have to accept some trade-offs.  Suffice to say, a one-time 2048-bit RSA key-exchange shouldn't eat up too much processing time.

Using SSL is the most reliable way to exchange information securely; it not only takes care of the key-exchange and message encryption, but also message authentication (ie, man-in-the-middle attacks).

I don't think you should be concerned about AES being 'broken', but if you really want to be ultra-paranoid, you might take a look at using Serpent - it was the runner-up to Rijndael (AES) in the AES contest, with many people considering it more secure, but slower.

  "Serpent was widely viewed as taking a more conservative approach to security than the other AES finalists, opting for a larger security margin: the designers deemed 16 rounds to be sufficient against known types of attack, but specified 32 rounds as insurance against future discoveries in cryptanalysis."


regarding nonce and secret key Consider the following challenge-response protocol for $A$ to convince $B$ that he is indeed $A$. Here we are assuming:

at the
start when the virtual circuit is being set up, $A$ has to convince $B$ that he is indeed $A$.
once a virtual circuit has been set up, the BG cannot alter messages in the middle.
$A$ and $B$ share a secret
value $S$.

$B$ sends $A$ a nonce $N$.

$A$ calculates $C$ to be the first 64 bits of $N$ XORed with the first 64 bits of $S$.

$A$
returns $C$ back to $B$.

$B$ checks whether $C$ = first 64 bits of $N$ XORed with the first 64 bits of $S$.

If it is, $B$ accepts
that $A$ is indeed $A$. is it good idea to use this kind of functionality?

Since N xor C reveals the first 64 bits of S, the secret cannot be reused. Also, a MITM attacker can observe the message sent from A to B then drop it. Then the protocol cannot restart with a new nonce. If you prefer a challenge-response protocol, maybe just use S to hash the nonce and send the result to the other party.


How to prove the security of block ciphers I see very often proofs of security for asymmetric crypto algorithms, for instance, using reductions to known hard problems, or game based proofs...

In the field of protocols (like authentication) it happens too, for instance proofs using formal models...

But what about the symmetric crypto? More specifically, the blockciphers?

For example, this paper (presenting the Piccolo blockcipher) has a section named Security Analysis on which the authors just argue why they think Piccolo is secure against some knowns attacks. This is actually the opposite of the "philosophy" of the provable secure crypto, that tries to analyse the security of a primitive without exhaustively trying the known attacks, because it may exist some attack that is not know by the academic community.

Thus,

Are the blockciphers usually proved to be secure?
If yes, how is it done? If not, how the security is measured?
Is the approach of security analysis used in the paper above common on blockciphers papers?
And since the answer to the first question seems to be no, is there any blockcipher whose security analysis was done following a "provable secure like" approach?

There is actually a field of study regarding provably secure block ciphers.  The seminal paper was "How to construct pseudorandom permutations from pseudorandom functions" (1988) by Luby and Rackoff.  Their paper used pseudorandom round functions in a Feistel construction, and proved that 4 rounds were sufficient to make the resulting block cipher a pseudorandom permutation against chosen plaintext and ciphertext attacks.  That paper spawned a cottage industry of similar papers based around the Feistel construction, or generalizations thereof.  In addition to academic papers and theoretical cipher constructions, this also inspired a few actual concrete block ciphers, such as the BEAR and LION ciphers by Anderson and Biham that Marcellus mentioned, and the Turtle block cipher, by Matt Blaze, for which the author claims that "recovery of its internal state given its inputs and outputs in NP-complete."

More recently, a similar wave of papers have developed regarding provably secure "key alternating" block ciphers, which are like AES in that the round function consists of the entire state being xored with a key, followed by an unkeyed permutation.  The seminal paper for this wave was
"A Construction of a Cipher From a Single Pseudorandom Permutation" (1991) by Even and Mansour, which focused on the security of a key alternating block cipher with a single round.  This was then expanded to iterated constructions with multiple rounds in "Tight Security Bounds for Key-Alternating Ciphers" (2013) by Chen and Steinberger, inspiring a similar cottage industry of related papers in recent years.

But the overwhelming majority of actual, concrete block ciphers are not provably secure in the sense of the above literature.  Instead, they accumulate confidence over time insofar as they continually resist cryptanalytical efforts.  As Biv described, they may also attempt to prove immunity to certain specific kinds of known attack; whereas the academic papers above purport to prove security against all attacks, known and unknown.


Ways to make white-box cryptography AES implementation more difficult to be broken Background: I want to use white-box cryptography to hide the keys stored in a client application.

I am looking for existing implementations of white-box cryptography, such as AES 128 or 256. But I found that almost all the existing implementations are breakable in some reasonable period of time. For example, see the CHES 2017 challenge and BGE attacks on the original Chow's scheme, etc. I haven't been able to find a mature/unbroken implementation so far.

My objective is to make WBC implementation very difficult to be broken. As we know,

1) WBC aims to protect cryptographic algorithms against key recovery

2) Code obfuscation aims to protect against the reverse engineering of a cryptographic algorithm.

Thus, I want to use a published WBC implementation (may be broken already), and then apply obfuscation on the code (e.g., C++).

Is the above way reasonable (if we cannot find a proper implementation)?
Please recommend any mature WBC implementations (not broken yet)
Any better ideas? (other than re-design & evaluate a new WBC algorithm)

Is the above way reasonable (if we cannot find a proper implementation)?

No, there are currently no such code-obfuscation algorithms that securely obfuscate code to a point where it's very hard to reverse engineer it.

  Please recommend any mature WBC implementations (not broken yet)

I'm not aware of any WBC implementations for AES.

Note, that a successful implementation of a WB-AES algorithm would mean that the "one-wayness" (very hard to invert) would turn this algorithm into a public-key-cryptosystem without a need for asymmetric cryptography (you would just publish the WBC-AES-implementation and the key wouldn't leak). So I'm pretty sure that there are no unbroken implementations.

It could be that there are some unbroken WBC implementations out there, but I don't think that they would remain unbroken for long if they would attract a lot of attention from the cryptographic community.

  Any other better idea? (other than re-design & evaluate a new WBC algorithm)

No. As Geoffroy Couteau and I commented, self-made code obfuscation is likely unsecure for many reasons, the main reason being that the security would rely on the fact that nobody ever would gain knowledge of your obfuscation algorithm.


AES in CTR mode, with a single key, and an IV derived from the plaintext We need a system to compare cipher-texts for equality, without (the checking system) having access to the plaintext.

We found a library that uses AES in CTR mode, with a single key, and an IV based on the SHA1 has of the plaintext.

This question is closely related to another question here on crypto.SE, but in our case the IV is derived by calculating a SHA1 has of the plaintext.

The plaintext in question are key value pairs, where the key is a short textual identifier and the value is a key. The total plaintext size is around 1k in bytes, and, additionally, but separately, SSH key files.

Would there by be any implications for the secrecy of the encrypted plaintext?

In the context, the IV is part of the ciphertext (as usual with AES in CTR mode). That part of the ciphertext leaks information about the plaintext including for one who does not know the AES key, which is bad in theory at least. This is because the (SHA-1) hash of the plaintext (or part of it) is the IV. In particular, an adversary can use a ciphertext to comfort a guess of the plaintext, by hashing the guess and checking if (the appropriate part of) that matches the IV.

One academic solution to the problem is a MAC of the plaintext, such as HMAC-SHA-256, with a secret key. This gives a short deterministic digest of the plaintext that does not leak any information about plaintext to adversaries not holding the key (beyond equality of two plaintexts, of course). That digest could be added as a prefix or suffix of the ciphertext obtained by AES-CTR or some other mode (authenticated encryption is a nice-to-have).

Using the same key for the encryption (authenticated or not) and the MAC is poor in theory, and could be disastrous with an AES-based MAC. However, with HMAC-SHA-256, the only foreseeable drawback would be that a key-recovery attack on HMAC (e.g. by some side-channel) would leak the encryption key; or vice versa.


Cost of upgrading to PQCrypto We already have recommendations on what PQCrypto to use:
PDF (page 11)

  Symmetric encryption Thoroughly analyzed, 256-bit keys:

  AES-256
  Salsa20 with a 256-bit key

  Symmetric authentication Information-theoretic MACs:

  GCM using a 96-bit nonce and a 128-bit authenticator
  Poly1305

  Public-key encryption McEliece with binary Goppa codes:

  length n = 6960, dimension k = 5413, t = 119 errors

  Public-key signatures Hash-based (minimal assumptions):

  XMSS with any of the parameters specified in CFRG draft
  SPHINCS-256

What would it cost to upgrade to those recommendations?

We assume that the recommendations will survive further scrutiny and that upgrading software is for free. In practice it will happen as part of a software upgrade that will happen anyway.

What is the additional:

Disk usage
RAM usage
CPU usage
Bandwidth usage

for a normal user and for a normal website?

Since users mostly visit the same websites as they did the day before I am thinking that the key exchange may not be so scary after all. If the SSL certificate is only downloaded every few months, then it will be very little extra bandwidth.

Using AES-256 or Salsa20, Poly1305 or GCM authentication should come at no to little additional cost if you are already using HTTPS. If your server is somewhat modern bandwidth cost is about 16 bytes per HTTPS data packet sent and a few hundred bytes (at most) of RAM and rather minimal performance overhead compared to the actual business logic running on the server. You shouldn't worry about this part.

The asymmetric part is the interesting one. As a server you'll have to generate 1 signature for TLS per handshake (so at most one per request) and SPHINCS-256 costs 43M cycles on Intel Kaby Lake CPUs which is about 20ms on a 2GHz CPU. Signatures are 41kB though which means the RAM overhead is probably about ~40kB per handshake and the bandwidth overhead is about the same. Now if you deliver 2MB of JavaScript anyways this will hurt less than if you're only using a very simple static website... I haven't found data on XMSS so won't comment on that.

As for McEliece, performance data suggests it needs about 2M cycles for decryption, which happens once during a TLS handshake, so about 1ms on a 2GHz CPU. However, the public key is 1.3MB which is usually transferred once per handshake. The actual ciphertext is only $n$ bits and so only a bit larger than a comparable RSA encryption. You may want to note though that modern TLS 1.3 doesn't support key transport (ie public-key encryption for key agreement) anymore.

So, in total we get an overhead of about 45M CPU cycles and about 1.4MB per TLS handshake which is about 23ms on a modern server CPU.


Need of Image Encryption Question is simple yet confusing, why there is the need for image encryption. How text encryption is different from image encryption if using same technique like AES, DES, Chaotic algorithm. If the only difference is at implementation it's more of engineering task than science. Can same encryption technique applied to both text and image, then why image encryption a separate part.

There is no need for those image encryption algorithms.

You can encrypt an image file, like any other sequence of bytes using standard encryption.
If you really want to encrypt the pixels themselves (not recommended), you can use standard length preserving encryption, such as a four round feistel network.

I've seen some image encryption papers, but they were badly written by people with little understanding of cryptography and not published in cryptography journals/conferences.


Can a MITM attack be applied to this construction? On reading the accepted answer to this question, I was wondering whether a Meet In The Middle attack could be applied to the suggested construction (below), and if not, then what is the effective key strength of combining two 256 bit ciphers in such a way? If I understand correctly, the Tahoe-Lafs 100 Year Cryptography project uses a similar construction.

  $C=P\oplus K^1\oplus K^2$, where $C$ is the ciphertext, $P$ is
  the plaintext and $K^1$ is the key stream of one cipher and
  $K^2$ is the key stream of the other cipher (courtesy of
  Maarten
  Bodewes).

Let $K^1,K^2$ be the key-streams generated by $k_1,k_2$.

Now define $E^1_{k_1}(m):=m\oplus K^1$ and $E^2_{k_2}(m):=m\oplus K^2$.

Note that $E^1_{k_1}(E^2_{k_2}(m))=m\oplus K^1\oplus K^2$.

You now have a straight double encryption and can apply the standard meet-in-the-middle attack now.

The implementation would use a known-plaintext pair $(m,c)$. You would now tabulate all $E^1_{k_1'}(m)=m\oplus K^{1'}$ and then try all $D^2_{k_2'}(c)=c\oplus K^{2'}$ and look for matches between $E^1_{k_1'}(m)$ and $D^2_{k_2'}(c)$.


CCM authenticity bound Can someone help me understanding the CCM authenticity bound by Phillip Rogaway?
i-e Success probability < $q_{\text{dec}}/2^\tau + \sigma/2^b$.

$\tau$ is tag length, where as $b$ is block length. $q_{\text{dec}}$ is the number of forgery attempts, I can not get whats "$\sigma$" is?

Also If i am not looking for forgery attempts but looking for the channel errors that cause invalid message to go through CBC MAC. Then for that case $q_{\text{dec}}=1$. Am I right?
And I am attempting to send 500MB of data? So what will be the number of un-authenticated messages that go through CBC MAC because of channel errors.

If you mean this paper by Rogaway, "Evaluation of Some Blockcipher Modes of Operation" (PDF, relevant page is 120) then it very clearly documents everything.

$q_{\text{dec}}$ is the total amount of decryption queries the adversary asks. If you only accept one decryption query before using different keys, this can be approximated by $1$.
$\sigma$ is the total number of block cipher calls the mode would make on the adversary's sequence of queries. So if all adversarial queries (encryption and decryption ones) together require 4 block cipher calls to process, then $\sigma=4$. For 500 MByte of Data (in the single query) this would imply $\sigma\approx 2^{26}$

Also note that the bound stated in the paper (note the additional square on the $\sigma$) is $$\leq \frac{q_{\text{dec}}}{2^\tau}+\frac{\sigma^2}{2^b}$$

Plugging in the above values yields an advantage of $\leq 1/2^\tau+2^{52}/2^b$ which bounds the success probability of any adversary. Now random noise usually isn't exactly a smart adversary so the probability of a (successful) forgery from random noise is even much lower.

So let's clarify on what a "block cipher call" actually is. Modes of operation like CCM are built on block-ciphers which get modelled as functions $C=E_K(P)$ for some plaintext $P$, some key $K$ and the corresponding ciphertext $C$ where $P$ and $C$ are the same, fixed size. One computation of $C$ from $K,P$ or of $P$ from $K,C$ is called one block cipher call (because in the implementation you call the block cipher function for this). Now for CCM mode, which I will skip describing here, you end up with about 2 block cipher calls per data block (one for privacy, one for authenticity), yielding the aforementioned $2^{26}\approx 2\cdot 500\cdot 10^6/16$.


Problem with calculating the correct value for $(p-1)*(q-1)$? I came to a problem when calculating some values for RSA encryption task.

So the data I have is this:

$e*d=81$

$C=5$

Now I have to calculate the original message($m$) and I have an issue because I can see what the solution for $m$ should be, but I get a different answer.

So far, I was able to figure out that $e=27$ and $d=3$.

Now I should calculate $m=(p-1)*(q-1)$ with the equation: $e*d \bmod m = 1$.

But the solution I have from this example says that $m=40 \rightarrow 4*10$ which gives us $p=5$ and $q=11$.

Now my question is why is $40$ correct and not $m=20 \rightarrow 2*10 \rightarrow p=3$ and $q=11$, which is what I got?

So, you're given the exponents (and the ciphertext), and are expected to recover the modulus?  That's certainly not the standard way of using RSA.

It turns out that the necessary and sufficient conditions on $p, q$ is that $p-1, q-1$ are factors of $ed-1$; hence we know that $p, q \in \{ 3, 5, 11, 17, 41 \}$ (as those are the primes that meet this criteria), and any such combination of distinct $p, q$ would work (we also know that $pq > c$, however all combinations meet this criteria); by work, I mean that $(m^e)^d \equiv m \bmod{pq}$ for all messages $m$.  Now, with some combinations, the $e, d$ combination might not be minimal; however nonminimal $e, d$ values do happen in practice.

As both $p, q = 5, 11$ and $p, q = 3, 11$ meet the above criteria, both lead to valid answers.  If the original question did not add any additional information, well, they did not specify the question sufficiently.


Is it safe to reuse an IV 100 times to a single key with AES CBC? I have a unique 6 digit number that I am generating a IV from. I am trying to make it as unique as possible. From my programming, I am able to get it down to only have 100 duplicate IVs per unique 6 digit number.
Now I have read that reusing IV's is a big no no because it leaks information.
My question now, assuming I am only using 1 key and if someone has gained access to my database of 1 billion records and has the encrypted string as well as the IVs. If each IV is only reused 100 times, would they be able decrypt the encrypted string based off only that information?
If so, how would they be able to?

Given sufficient resources - maybe.  If an attacker knows text that was encrypted and can associate that plaintext with an encrypted string then they can potentially work on figuring out what the other strings encrypted with the same IV are.  Can they simply derive the plaintext using some formula though?  No.  If you're encrypting textual data it's easier to determine than binary data.
You have another problem in that it's generally recommended to limit the total amount of data encrypted with a single key (no matter how many IVs get used).  In the book Cryptography Engineering Ferguson and Schneier recommend a limit of around 64 GB for CBC mode (assuming you're using AES).  So, if your billion records are more than 64 bytes each you'll start bumping into that.  This is a recommendation based on what they believe to be an acceptable risk of leaking data.  You could potentially encrypt 128 GB or 256 GB and be fine.  Or if you want the data to be safe for a number of years in the future without having to re-encrypt the data you might want to take it down to 8 GB or even 4 GB per key.  It just depends on the level of risk you're willing to take.


Cryptographic algorithms comparison, AES vs Camellia Which parameters should be used to compare AES vs Camellia? Their runtime ? The size of the encrypted data output?

Both AES and Camellia are block ciphers with a block size of 128 bits and three different key sizes: 128, 192 and 256 bits.

In both cases, when using a bigger key size, like 192 or 256, the cipher will do additional rounds. AES will do respectively 10, 12 and 14 rounds for 128 bits keys, 192 and 256, while Camellia do 18 rounds for 128 bits keys and 24 rounds for both 192 and 256 bits keys.

So far so good, all this information can be found on Wikipedia.
So, you want to compare both, but what kind of metrics do you want to use?
What are the key performance indicators you're valuating most? Is it the raw speed? Is it the security against differential power analysis? Is it the parallelization of the computation? Is it the number of line of code in an implementation? Is it the maximal code footprint? Is it the resistance against algebraic attacks?

I'll do the assumption that what you really want to do is comparing "implementations" of both ciphers, not the underlying algorithms (there certainly are papers doing so for both ciphers).

In order to compare implementations, you have two options:

Either you take reference implementations, without much optimization and compare then
or you take the "best" implementations out there and compare them.

As stated by Maarten in comments, AES being the most used block cipher nowadays, the currently best implementations all rely on the fact that there are hardware accelerators for them in almost all processors. However, it appears that Camellia can also be accelerated using some of the same tricks as AES [1]. I recommend you to take a look at this thesis, since the author is comparing different block ciphers, including both AES and Camellia, and tries to optimize their raw speed.
According to its results, Camellia is still 4 time slower than AES, even using the AES-NI tricks.

Now that last paragraph takes into account only the "raw speed" of the implementations, but an implementation can also be hardened against certain kind of attacks depending on the threat model scenario it tries to address. For instance, bit-sliced DES introduced by [2] is faster than standard DES (and is constant time), but there might be other hardening methods which are not necessarily improving the performance, like for instance the "infective countermeasures for RSA" against fault attacks, which add an overhead, or the "masking" used in RSA implementations meant to resist to DPA attacks.

In order to perform such comparisons between the "features" of the implementations, then you need to probably review the code and check what's being done. (Or have a list of the "features" the implementations sports.)

In the end you could also compare the usage of both ciphers, or the patents, or the amount of paper written about both, etc.

Notice that you can also look for existing benchmarks out there, if you what you care about is the speed, like for example the ones done by Crypto++, or the ones found in the above-mentioned thesis.

References

[1] Kivilinna, Jussi. "Block Ciphers: Fast Implementations on x86-64 Architecture." MSc diss., University of Oulu, 2013.
[2] Biham, Eli. "A fast new DES implementation in software." In FSE, vol. 1267, pp. 260-272. 1997.


Why is Bcrypt called a Key Derivation Function? I am trying to understand why is bcrypt called a Key Derivation Function?

I looked up the details of Ekfblowfish on Usenix article.

After reading it, I understood that:

The password is the encryption key. The length of the password can vary and so the length of the encryption key can vary (max is 56 bytes or 448 bits).
128 bit salt, it does not provide the details about how this salt is generated? It only says, that the 128 bit salt along with the variable length encryption key is used to modify the S Boxes and the P Array.
When it says, Key Schedule, it refers to both, S Boxes and P Arrays. The Key Schedule keeps changing using the bits of 128 bit salt and the encryption key.

Now, what key are we deriving here? It is not clear, why is bcrypt called a Key Derivation Function?

So, does it mean that at the end of Expensive Key Schedule, we have a unique value for S boxes and P array contents which are further used to encrypt "OrpheanBeholderScryDoubt" using ECB mode.

So, aren't we deriving the Key Schedule (S boxes + P Arrays) instead of the Encryption Key (which is the same as the password that was supplied as an argument in the starting)?

Which key has been derived using Eksblowfish?

It's called a key derivation function because that's what you'd typically use its output for — as a key for some other cryptographic algorithm.  (Of course, you can also use the output of Bcrypt for other purposes, e.g. storing it in a database as a password hash, but that's really a secondary use case.)

In general, key derivation functions (KDFs) serve a number of purposes:

Key separation: This is the most basic use case for KDFs. Basically, you have one key, but need several.  This might be e.g. because you're a server that needs to communicate with multiple clients using distinct keys for each, or simply because the algorithms you're using together (e.g. a cipher and a MAC) have only been proven secure under the assumption that they each have separate and independent keys.  You can solve this problem by using a KDF (with different salts) to derive multiple (quasi-)independent subkeys from your original key.
Key expansion: Related to the above, some algorithms may require rather long keys for practical reasons, even though the desired security level against brute force guessing could be met with a shorter key.  In such cases, you can use a KDF to effectively extend the length of your key.
Key whitening: Many encryption algorithms, such as block ciphers, require a key that consist of a fixed number of (effectively) random bytes.  If you have a key that is not in the required format (such as an arbitrary-length passphrase, or a Diffie-Hellman shared secret), you can use a KDF that accepts arbitrary input key material to hash it into a byte string of suitable size.
Key stretching: This is the specific use case for which Bcrypt (and other "password-based" KDFs like PBKDF2 or scrypt) are designed for.  Basically, say you have a user-entered passphrase that may have a relatively small amount of entropy (say, from 20 to 40 bits), in addition to all the other issues mentioned above (too short / too long, wrong format), and you want to use it to encrypt/decrypt some data (or to authenticate the user) while making it hard to break the encryption by guessing the passphrase by brute force.

The solution is to use a deliberately slow (and possibly memory-hungry) KDF, like Bcrypt, to derive an encryption key from the passphrase.  By making the derivation process deliberately take a very long time (say, a whole second, which might be a million times more than a simple non-stretching key derivation would take), you can slow down any brute force attacks by the same factor.  The reason it's called "key stretching" is, presumably, because you're taking a "short" (low-entropy) key and effectively making it as resistant to brute force attacks as a "longer" (higher-entropy) one.

Now, that's a whole bunch of jobs, and indeed one might argue against lumping all functions designed for some or all of these tasks under the single label "KDF", but that's how the established terminology works.  There is some justification for it, since systems that require the latter properties often also require the former.

Still, different KDFs do have different strengths; for example, Bcrypt is pretty good for key stretching, but somewhat awkwardly limited in other respects.  If I wanted a Bcrypt-based system that handled all of the points above, I might consider e.g. combining Bcrypt with HKDF (from RFC 5869), like this:

Use HKDF-Extract to whiten the input key material / passphrase, avoiding the input length limits of Bcrypt.
Feed the pseudorandom key generated by HKDF-Extract through Bcrypt to stretch it against brute force attacks.
Use the output of Bcrypt as the PRK for HKDF-Expand, to provide efficient key separation and expansion.


What does it mean for a random number generator to be cryptographically secure? I've never heard a good answer. I'd like to hear details about:

What are the criteria that make an RNG cryptographically secure?
Why must your RNG be cryptographically secure? I.e., what are the consequences if it is not?
Examples of secure and insecure RNG's
Would a non-pseudorandom generator be cryptographically secure? E.g. one based on radioactive decay of a particle.

What are the criteria that make an RNG cryptographically secure?

In short, a DRBG [deterministic random bit generator] is formally considered computationally secure if a computationally-limited attacker has no advantage in distinguishing it from a truly random source.

What does this mean? Given a DRBG F and a truly random oracle G, let A be a probabilistic "attacker" that accepts F or G and outputs 1 or 0 after making queries to the function it was given. We define the attacker's advantage Adv to be |Pr[A(F)=1] - Pr[A(G)=1]|. If Adv is non-negligibly more than zero, the DRBG is considered broken. In this definition, note that it doesn't matter what returning 1 or 0 "means", just that we care only if A has a different probability of returning one or the other when given F and G.

In English, if there exists a computable function that can reliably tell the difference between a black-box DRBG and a black-box truly random function, then we consider it a break of the DRBG.

  Why must your RNG be cryptographically secure? I.e., what are the consequences if it is not?

This is probably far too broad a scope for a question like this. In some cases it doesn't have to be. In some cases even a slight weakness can cause a near-total loss of confidentiality or authenticity. The implications of a weak RNG are completely dependent upon the system and context in which it is used.

  Examples of secure and insecure RNG's

There are multiple kinds of DRBGs, intended for different purposes.

Yarrow and, later, Fortuna are algorithms that accept as input entropy sources of unknown quality, mix them, and produce entropy streams with strong guarantees as output. They have self-healing properties that resist injection attacks; even if an attacker controls almost all of the inputs, after a finite amount of time, the outputs will become indistinguishable to the attacker.

This is an extremely useful property for system RNGs such as those used by operating system kernels and provided to userspace through /dev/urandom, getentropy(2), and CryptGenRandom() (note: these interfaces may or may not actually use Yarrow or Fortuna, they are just examples of the types of system RNGs those algorithms were designed for).

Stream ciphers like ChaCha20 or block ciphers in streaming modes like CTR are really just cryptographically-seeded DRBGs. These algorithms aren't designed or intended to defend against an attacker injecting predictable inputs as the aforementioned algorithms were, but they produce nearly-infinite streams of randomness at very high speed given only a small initial random key and IV. These streams can then be XORed against a plaintext to produce a cryptographically-strong ciphertext. Even better, these algorithms are typically seekable; given a key, IV, and long ciphertext, you can generally seek far into the ciphertext and decrypt individual bits without needing to compute the entire stream.

I won't list insecure DRBGs here. There are simply too many to list, and the general assumption should be that a DRBG is not secure unless demonstrated otherwise.

  Would a non-psuedorandom generator be cryptographically secure? E.g. one based on radioactive decay of a particle

Non-pseudorandom generators are the only generators that are even capable of being information-theoretically secure, which is a significantly stronger metric than computational security. With a computationally-secure DRBG, a small seed of n bits is expanded into a larger cryptographic stream; that larger stream still is only one selection of at most 2^n possible streams.

Quantum sources of randomness such as radioactive decay and thermal noise are by physical definition truly random.


RSA-896 solution costs $75,000

Actually, that was the cash prize that RSA offered for a factorization; this cash prize has been since withdrawn.

  But where did they get this number? Does anybody in the world know the factoring?

To quote RSA:

  The generation took place on a Compaq laptop PC with no network connection of any kind. The process proceeded as follows:

  First, 30,000 random bytes were generated using a ComScire QNG hardware random number generator, attached to the laptop's parallel port.

  The random bytes were used as the seed values for the B_GenerateKeyPair function, in version 4.0 of the RSA BSAFE library. The private portion of the generated keypair was discarded. The public portion was exported, in DER format to a disk file.

  The moduli were extracted from the DER files and converted to decimal for posting on the Web page.

  The laptop's hard drive was destroyed.

So, if they are to be believed (and people generally do), no one currently knows the factorizations (at least, of the values that have yet to be publicly factored).


Zerologon question - AES-CFB8 I was reading the zerologon whitepaper by secura named:

Unauthenticated domain controller compromise by subverting Netlogon
cryptography.

I'm trying to understand the zerologon attack. The issue is on the KDF function (AES-CF8) that uses a IV with all zeros, I tried to follow the AES implementation with the block mode chosen and my main question is, the secret used on AES encryption is the computer password hash or the server nonce?
My guess is that it's the server nonce else the output of the AES would always be equal. Also, if am I correct, this explains the reason that 256 tries should be needed, because we have 1 possibility in 256 options in one byte (first one). Is it correct?
Also, the document has a figure showing the output of the AES operation with only 8 bytes, however the document state

The basic AES block cipher operation takes an input of 16 bytes and
permutes it to an equally-sized output.

The protocol just transfer the last 8? Or transfer everything and he just did it to illustrate?

I guess you are referring to this whitepaper, so I will refer to it in my answer.
First, I think you misunderstood part of the protocol (illustrated in Figure 1): the KDF is not AES-CFB8. A KDF is a Key Derivation Function: in this particular case, it basically acts as a hash function, transforming the inputs into a random-like stream of bytes
We assume the client and server share a secret password (or a secret password hash to be more specific). At the beginning, the send each other a random challenge, and use both challenge and the shared secret to derive a session key, using the KDF. Since we assume the server to be honest, its challenge will be random, making the session key change every session (hence the 256 tries).
AES-CFB8 is only involved after, when they encrypt each other challenge with the session key (to show that they successfully derived the session key, proving they know the shared secret).
So both challenges (nonces) are fed to the KDF, along with the password, which give you a session key. Then AES-CFB8 is used to encrypt the challenge you received, with this sesson key.

Considering the 8 bytes long ciphertext, the whitepaper is right. Indeed, raw AES process 16 bytes blocks and output a 16 bytes block. However, CFB8 mode encrypts one byte at a time, by first encrypting the IV (16 bytes, in yellow) and XORing the last byte of the result (in green) with the first byte of plaintext (in blue), and start over shifting the block it encrypt from one byte (see Figure 2). Basically, you will perform a raw AES encryption of one block (so you have the 16 bytes input-output) but you discard 15 bytes of the output (yes, this is a slow way to encrypt).
This means CFB8 make it possible to process a plaintext of arbitrary size $\ell$, without padding anything, and to produce a ciphertext of $\ell$ bytes. Here, the challenges are 8 bytes long, hence the 8 bytes' output!


Abstracting primitives and modes of operation I am developing a symmetric crypto library and have reached a roadblock. Looking at block ciphers, it is quite obvious that all block ciphers are trivially abstractable as a simple primitive consisting of:

a key schedule
a permutation function (which takes as an input a key, possibly a "tweak" and a data input)

This makes all block ciphers easy to use in any mode of operation, and makes it easy to "swap out" various algorithms in favor of others without needing to rewrite extensive amounts of code - only the above components differ between algorithms.

I am having trouble observing the same level of abstraction with hash functions. They are described by their compression function (straightforward) but also seem to have a built-in mode of operation which, while often shared between various hash functions, is not meant to be changed, for instance nobody uses the MD5 compression function with a Davies-Meyer construction, it is always used with Merkle-Damgård because that is what MD5, as a whole, is.

And these modes of operation are not quite the same, for instance Merkle-Damgård applies some simple padding at the end of the message to hash and then divides the message into blocks and processes it like that, whereas the UBI construction uses an extra "configuration input" in its compression function which requires the message to be handled quite differently.

So my question is: is there a way to nicely abstract hash functions in a specific framework as elegantly as with block ciphers, without needing to specifically write every hash function in a different way, so as to achieve optimal code reuse?

The best compromise I could come with is categorizing different hash functions in groups depending on what mode of operation they use (such as MD5, SHA1, SHA2, RIPEMD, etc.. would all go into the Merkle-Damgård category, whereas Skein would go in the UBI category, and so on), which would have code related to message padding and handling being reused when necessary, but also increases code complexity slightly.

This is also an issue for HMAC constructions. There is a fully abstract HMAC construction which works with any hash function regardless of its internals, however newer hash functions are starting to provide their own specific HMAC designs (for instance, Skein and its HMAC configuration block) which are more efficient than the "standard" method.

It is not a good idea to try and find abstractions at places where there is no fundamental reason for them to exist. That there is some "accidental" structure in the way encryption or hash methods are build up does not say anything about future encryption or hash functions.

Besides, you may need to apply specific protections against e.g. side channel attacks. It would be a shame if your carefully build software design would be in the way of creating a more secure library.

Note that if there is no fundamental reason for specific abstractions, there may not be any advantage in creating them. E.g. you would not see too many advantages regarding code duplication.

Many algorithms have specific naming conventions and reference implementations. You should not want to shoehorn those into your design.


Can I use signature(hash(message)) instead of signature(message)? Background:

We use the TweetNaCl crypto library by Bernstein (tweetnacl.cr.yp.to) et al and we would like to stick to it. However, we have the need to sign large messages and the library does not explicitely support signing something that does not fit in a buffer of bytes. However, the 25 functions of TweetNaCl include the ability to hash (SHA-512) a message in pieces without the need to buffer for the whole message.

We consider:

So, we consider using s2 instead of s1 as defined below.

s1 = Ed25519Signature(message)
s2 = Ed25519Signature(Sha512(message))

The Ed25519Signature is computed with the TweetNaCl function:
"sm = crypto_sign(m,sk);"

Can we do this? Is s2 as secure as s1?

Edit 1: note that the "Ed25519Signature" function above is "crypto_sign" from TweetNaCl. It does hashing internally. So, the signature is computed by hashing already. The s2 approach hashes the message twice while the s1 approach does the hashing once.

Yes, this should be secure.

I am not familiar with TweetNaCl, so I cannot speak on the concrete implementation. However, the general construction of signing a hash of a message instead of the message should be secure. It is in fact a standard way to sign messages.

In general it should work for any secure signature scheme and cryptographic hash function. The intuition goes like this: assuming the signature scheme is secure, the only way to pass a signature on a message off as a signature of some different message is to find a new message with the same hash as the original message. Thus finding such a message would break 2nd preimage resistance of the hash function.


In RSA, what is $P[x \notin \mathbb{Z}_N^*]$ In the RSA problem, picking a message $x \in \mathbb{Z}_N \setminus \mathbb{Z}_N^*$ implies factorizing $N$. Since factorization with respect to the standard RSA generator is hard assuming the RSA problem is hard, it is likely that selecting $x \in \mathbb{Z}_N \setminus \mathbb{Z}_N^*$ is hard. Thus, one may ask the question:

  Given $x$ uniformly distributed over $\mathbb{Z}_N$ what is the probability that $x \notin \mathbb{Z}_N^*?$

with the hope that it is negligible. So I write:

$P[x \notin \mathbb{Z}_N^*] = 1 - \frac{\phi(N)}{N} = \frac{1}{p}+\frac{1}{q} - \frac{1}{pq}$

However, how does one prove this is negligible?

With fgrieu's idea:

If we consider the generator working on a security parameter of $n$ bits (meaning resistance to $\mathcal O(2^n)$ computational effort), then each of the prime $p$ and $q$ must be at least (about) $n$-bit, otherwise trial division would factor the public modulus. Then, $N=p\,q$ with $p$ and $q$ distinct primes at least $2^n$ implies $P[x \notin \mathbb{Z}_N^*]=1-\frac{(p-1)(q-1)}{p\,q}<\frac1p+\frac1q<\frac2{2^n}$, that is $\mathcal O(2^{-n})$ which is negligible.


Can you defeat AES-CTR's birthday boundary with a 2nd AES? This follows on from How do I produce a stream of secure random numbers from AES-Counter mode?

Consider then the generator:-

$$
 \operatorname{AES_{k1}}(n) \oplus  \operatorname{AES_{k2}}(n)
$$

where    $  k1 \ne k2  $, and  $n$ is the single counter variable. And we take care to ensure that there is no relationship between $k1$ and $k2$. If this  really does create a pseudo random function, will the  birthday boundary for AES-CTR output be overcome?

Yes. The number of $n$-bit blocks you can encrypt with this construction is proportional to $2^n$ instead of just $2^{n/2}$. So for AES this shouldn't be a problem because you can't process anything near $2^{128}$ blocks.

A secure stream cipher can be constructed from a PRF using something similar to AES-CTR.

AES is more accurately described as a PRP than a PRF, but this distinction is unimportant if the number of queries an attacker is allowed to make under a given key is much much less than $2^{64}$.

(See PRF switching lemma. If the number of queries the attacker can make is much less than $2^{n/2}$, then it is safe to substitute an $n$-bit PRP for a PRF. This is where AES-CTR's limit comes from.)

However it has been proven that the XOR of two PRPs is a secure PRF instead for up to $\mathcal{O}(2^n)$ queries. 1 2

Readers should note that this isn't the same as saying that you can use up to precisely $2^n$ blocks. For this reason, I strongly discourage using a block cipher algorithm with smaller blocks (like DES, Simon, or Speck) in this kind of construct. (Or any other mode, I suppose.)


what are multi-primes and how are they different from semiprimes? I came to know of semiprimes recently. The simplest explanation of semiprimes is you take any two prime numbers and you multiply them, say 3*11 = 33 in which case 33 would be a semiprime. The numbers may grow bigger but the idea is same.

Hypothetically (or maybe in reality as well), you could use a good large semiprime as your public key and one of the primes as the private key so encoding and decoding is simpler for the one who has access to the private key.

Now what is/are multi-primes? Are they multiple prime numbers which are multiplying with each other or some other thing ? As in the above scenario, if somebody encodes some data with result of multiplication of 3 or more primes. In this case, how would the above example work while decoding the data?

Looking forward to know and understand. I did use various search engines but didn't get any explanations for this.

Looking forward to know.

You got what a "semiprime" number is; it's a number which is the product of two primes.

When people talk about "multi-prime RSA", what they mean is something which is pretty much the standard RSA algorithm; however the modulus is the product of at least 3 prime numbers (as opposed to standard RSA, which has only 2 prime factors).

Why would anyone do this?  Well, for performance; using the CRT optimization, we can do the private operations (signature generation, public key decryption) somewhat faster than we can do with standard RSA.  And, it doesn't affect someone that has only the public key as well (they can't even tell if the key they've been given is standard RSA or multi-prime").

Why doesn't everyone do this?  Well, I'm not certain, but I can think of a few plausible reasons:

I believe this idea is patented.
If someone goes hog wild, and puts too many factors into the modulus, that will make the modulus easier to factor.  IIRC, having 3 or 4 factors is safe for common modulus sizes is safe; I know that having 10 is not.
Conservatism; we trust RSA as it was originally designed, we're not going to go to an unproven version for a modest performance gain.