Why do cryptographic hashing and symmetric encryption use different functions? Something about encryption and hashing has always bothered me.

Given a cryptographically secure hash function $H$, I can produce an arbitrarily long key from any seed $s$ by recursively applying $H$ to the seed $(s, H(s), H(H(s)), ...)$.
Then I can XOR the resulting array with any plaintext $x$ to produce my ciphertext.

Similarly, given an encryption function $E$, I can produce a hash of any input $x$ by simply encrypting each block of $x$ with itself, and then XORing the results together.

So why, then, do we use different functions for hashing and crypto (say, SHA-256 vs. AES)?
If one of them is secure, shouldn't it work for the other purpose too?

You are correct: The 'workhorses' or primitives of cryptography, hash functions and block ciphers, can be used in such a way that they accomplish each others tasks:  A hash function can be used to generate a key stream just as a stream cipher or block cipher in CTR mode (see e.g. Salsa20).  And a block cipher can be transformed into a hash function (e.g. a Davies–Meyer compression function inside the Merkle–Damgård construction).

So why use different functions?  Well, hash functions are not as versatile as block ciphers for the purpose of encryption - you can't do CBC mode with a hash function, for example.  And block ciphers are generally not as well suited to the task of hashing as a purpose built compression function - they tend to have smaller blocks and relatively slow key schedules (or key schedules which are not secure when the attacker can control all the inputs).  For efficiency's sake, it is easier to design a really strong and fast block cipher and a separate really strong and fast hash function than it is to design a single function which is really strong and fast in both capacities.

P.S. The hash function constructed from a block cipher you describe in your question is not cryptographically secure - you can find a collision merely by re-ordering the blocks of the message.


Composition of weak one way function is not a strong one way function Given $f(x)$, a weak one-way permutation, how to prove that $f^T(x)$ is not a strong one-way function? Here $f^T$ denotes
$T$ times self composition of $f$ and $T$ is a polynomial in input length.

Obviously, composing $T$-times a weak OWP can give a strong OWF: simply consider the case where $f$ is already a strong OWP (hence in particular a weak OWP). Now, what you want is to show that it is not necessarily the case; i.e., you want a function $f$ which is a weak OWP, but such that $f^T$ is not a strong OWF (i.e., an example where security does not "amplify through composition").

I'll give you such a candidate; I let you prove that it satisfies what you want, that is a quite simple exercise. Let $g: I \mapsto I$ be an arbitrary (strong or weak) OWP, and let $J$ be some arbitrary set such that $|J| = |I|$, and $I$ is disjoint from $J$. Consider the following function $f$:

$f:I \cup J \mapsto I \cup J$ is defined as follows: $f(x) = g(x)$ if $x \in I$, and $f(x) = x$ if $x\in J$.

Claim: $f$ is a permutation (that's quite obvious), and also a weak-OWP (you should be able to check that easily). Yet, $f^T$ is still a weak-OWP, but not a strong OWF. Can you see why?

(if you're stuck in the analysis, just ask for more hints in the comment section)


Is the encryption of a hash a good MAC? At university we were told that it is a bad idea to implement a MAC by simply concatenating a key with the data to sign and to run it through a hash function (e.g. $s = \mathrm{hash}(k||\mathrm{data})$ or $s = \mathrm{hash}(\mathrm{data}||k)$). The next ideas that were presented then were HMAC and CBC-MAC which are a lot more complex (but standardized).

Now I'm wondering what the security of the following "idea" would be (I'm sure that there a good reasons why it is not used as it is more simple than HMAC or CBC-MAC):

Compute the hash value $h = \mathrm{hash}(\mathrm{data})$.
Compute the ciphertext $c = \mathrm{enc}_k(h) = \mathrm{enc}_k(\mathrm{hash}(\mathrm{data}))$.
Set signature $s = c$.

Where $\mathrm{hash}$ is an arbitrary hash function and $\mathrm{enc}$ an arbitrary, symmetric block cipher using a key $k$.

I was not able to find any statements about such schemes, maybe I searched in the wrong place. However, it would be nice if you could help me with that question.

No, in general, this is not secure, unless you make additional assumptions on the encryption method beyond the standard assumption of privacy.

To simplify things a bit, the assumption of privacy means that given a ciphertext $C$, the attacker has no information about what the plaintext might be.  However, in your case, we don't really care if the attacker can figure out what the plaintext of the encryption function; we also give him the data, and he can compute $hash(data)$ himself, should he care to.

What we are concerned with is (again, to simplify a bit) that an attacker, given a message M and a valid tag for that message, cannot come up with another message, and a valid tag for that message.  Translating that into your proposal, if the attacker was given $M$, and $E(Hash(M))$, can he pick another message $M'$, and come up with $E(Hash(M'))$?

Well, for a lot of encryption methods, he can.  For example, if we consider a block cipher in counter mode, well, if you flip a bit in the ciphertext, the corresponding bit in the plaintext also flips.  What that means that if the attacker computes $E(Hash(M)) \oplus Hash(M) \oplus Hash(M')$, well, that turns out to be precisely $E(Hash(M'))$, and so the attacker has won.

The additional property that we need to assume for the encryption method is nonmalleability; that is, given $M$ and the corresponding encryption $E(M)$, the attacker cannot modify the encryption so that it decrypts to any other specific message.

Of the standard encryption modes, well, ECB actually is nonmalleable, if (and this is a big if) the hash fits entirely within a single block output.  Given that 128 bit hashes are vulnerable to collisions (and a hash collision would be another way of producing a forgery), this means using a nonstandard block cipher (for example, Rijndael with a 256 bit block size).

Authenticated encryption modes are also nonmalleable.  However, this may be considered cheating; authenticated encryption modes work by effectively using a MAC internally; if the point of the exercise is to create a crypto primitive from other crypto primitives, well, this didn't do it.


If $E_{k_1}(p_1) = c_1$, what is the probability that there exists key $k_2$ such that $E_{k_2}(p_1) = c_1$? Let $k_1$ be a 56 bit DES key that performs $E_{k_1}(p_1) = c_1$. What is the probability that there exists another key $k_2$ such that $E_{k_2}(p_1) = c_1$?

DES is a block cipher with $b=64$-bit block width, and $w=56$-bit key width (ignoring key parity bits). An ideal model of a block cipher is that each key defines an independent, random-like permutation of the blocks. Under that model, if $E_{k_1}(p_1)=c_1$, then

For each key $k\ne k_1$ there is independent probability $u_1=2^{-b}=2^{-64}$ that $E_k(p_1)=c_1$
Hence for each key $k\ne k_1$ there is independent probability $v_1=1-u_1=1-2^{-b}=1-2^{-64}$ that $E_k(p_1)\ne c_1$
There are $n=2^b-1=2^{56}-1$ keys $k\ne k_1$, hence the probability $v$ that for each of these keys $E_k(p_1)\ne c_1$ is: $v={v_1}^n={(1-u_1)}^n=(1-2^{-64})^{(2^{56}-1)}$
Hence the desired probability $u$ that there exist any key $k\ne k_1$ such that $E_k(p_1)=c_1$ is: $u=1-v=1-{(1-u_1)}^n=1-(1-2^{-b})^{(2^w-1)}=1-(1-2^{-64})^{(2^{56}-1)}$
For integer $n>0$ and real $\epsilon$, it holds that $(1-\epsilon)^n=1-n\,\epsilon+O((n\,\epsilon)^2)$
Therefore, for $m\gg1$ and $m\,|\epsilon|\ll1$, it holds that $1-(1-\epsilon)^{(m-1)}\approx m\,\epsilon$
Applying the approximation in (6) to the expression in (4), with $\epsilon=u_1=2^{-b}=2^{-64}$ and $m=2^w=2^{56}$, it comes
$$u\approx2^{w-b}=2^{-8}\approx0.39\%$$

Note per Ilmari Karonen's comment: the approximations made after step (4) fail when the key width $w$ approaches or exceeds the block size $b$, as would be the case for 3DES ($b=64$ and $w\in\{112,168\}$) or AES ($b=128$ and $w\in\{128,192,256\}$). We then want a better approximation. We can use ${v_1}^n=\exp(n\log(v_1))$ and $\log(1-\epsilon)=-\epsilon+O(\epsilon^2)$, giving at step (7) $u\approx1-\exp(-2^{w-b})$, valid for $b\ge20$ and $w\ge20$. That's mathematically more accurate, but numerical accuracy requires extended precision when $b-w$ is positive and sizable, which is dangerously close to hold for $b-w=8$ in the question.

Note: Our model of DES is imperfect, in particular when we consider many plaintexts $p$ : DES has additional properties that our model misses. In particular the complementation property $E_\overline k(\overline p)=\overline{E_k(p)}$; that the permutation of blocks for any particular key is even; existence of weak keys. More generally, DES is a particular block cipher (a Feistel cipher within a few cryptographically neutral bit permutations). But given that in the context there is as single plaintext $p_1$ considered, and that DES is a fair cipher (except for its last-century key and block size), it is reasonable to believe that our model is good enough for an excellent approximation of $u$ for random choice of $k_1$ and $c_1$.

Note: with DES a fixed cipher, we can no longer talk of the desired probability $u$ when the whole of both $k_1$ and $c_1$ is fixed. I conjecture that the approximation still holds when $c_1$ and all but say 16 bits of $k_1$ is fixed, but wonder what happens when $k_1$ is fixed to some particular values (like all-zero, which is a weak key).


Can a Vigenère cipher be solved if the alphabet is modified (custom)? Let's say I have about a statistically good sample of characters of text that appear to be uniformly distributed, but the composition of the text is [A-Z], [a-z], [0-9], +, and / — constituting basically a base64 alphabet. To me, the more or less uniform distribution of the text suggests at least a polyalphabetic cipher, and possible a Vigenère.

As far as I've been able to find, there doesn't exist any Vigenère cipher program to decipher a base64 alphabet. As an amateur coder, I can see why, but firstly the biggest obstacle to creating the code is that the + and / and separated from the rest of the characters in the ASCII lookup table, so a rotation algorithm is not straightforward, like it is for just caps.

Would it be possible to create a custom code/algorithm to code and decode base64 text using the Vigenère method?

The barrier to coding it would be the order to place the alphabet— should it be lowercase, UPPERCASE, numbers, symbols— mapped in that order, or does it matter?

Does the ordering of the alphabet matter to using a Vigenère? Can the keyword be altered to decode the cipher text in a shuffled alphabet?

See, I actually have a lot of text that I suspect is base64 Vigenère, and I also have the key— but I just don't have an algorithm to decode it.

I should probably add that the amount of characters is in the thousands, so it would not be practical to decode it by hand.

Basically, yes you can. To jump from alphabet to numbers without forgetting the + and / you can store the ASCII values in an array of 64 values.

Considering the order, it doesn't really matter as long as the cipher program and the decipher program use the same alphabet in the same order. You could use the ASCII order (symbol, numbers, uppercase, lowercase) or more probably the base64 order (uppercase,lowercase,number,symbol).

The list of the ascii values:

[43, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122]


Security analysis of Rijndael (AES) I was studying the Rijndael Block Cipher for an assignment. I am looking for a (layman-ish) explanation as to why the cipher is secure. Googling did not seem to be give any good explanations. The paper linked itself is a bit too high level for me to understand.
Could anyone explain the security or give a reference to where one could read about it?

Rijndael follows (like all decent cryptographic algorithms, to my knowledge) the principles of confusion and diffusion, formulated by Claude Shannon. Confusion means the ciphertext depends on the plaintext and the key in a highly nonlinear way, i.e. the function that calculates a specific output bit from the input (plaintext, key) is not a polynomial of low degree in the finite field $\text{GF}(2)$. Diffusion means that every bit of the input affects every bit of the output. Also, the computations that create confusion and diffusions are intertwined so that every information bit is fed into a confusion-creating operation and then spreads over the whole block multiple times, at least 4 or 5 times during the encryption.


How to implement 1-out-of-n OT from 1-out-of-2 OT? How can I implement a 1-out-of-$n$ oblivious transfer protocol from 1-out-of-2 OT protocol which is resistant against passive corruption? Assume we can access 1-out-of-2 OT $n$ times.

Approach 1

The simplest way of doing this is for the receiver, with choice $j \in \{1,\dots,n\}$, to input $1$ in the $j$-th 1-out-of-2 OT and $0$ elsewhere. The sender, with input $(x_1, \dots, x_n)$, inputs $(0,x_i)$ in the $i$-th OT.

Approach 2

An alternative protocol (that just came out of a discussion with a colleague, and seems to be actively secure) is for the sender to sample $n$ random strings $r_1,\dots,r_n$. Now run $n$ 1-out-of-2 OTs where the sender inputs:

$$
\begin{aligned}
(r_1, \,& x_1) \\
(r_2, \,& r_1 \oplus x_2) \\
(r_3, \,& r_1 \oplus r_2 \oplus x_3) \\
&\vdots \\
(r_n, \,& r_1 \oplus r_2 \oplus r_3 \oplus \dots \oplus r_{n-1} \oplus x_n) \\
\end{aligned}
$$

Now, it should be easy to see how the receiver gets the right choice. The advantage here is that a cheating receiver cannot easily learn any other choices, as each $x_i$ is masked by a fresh random value.

(Caveat: I've only thought very briefly about this and am not 100% sure about its active security)

Approach 3 (using $\log n$ OTs)

Naor and Pinkas gave a protocol using just $\log_2 n$ 1-out-of-2 OTs on $k$-bit strings (for security parameter $k$).
The sender inputs $\log{n}$ random pairs of strings to the 1-out-of-2 OTs, and the receiver inputs their choice represented as $\log n$ bits.

Now for each $i \in \{1,\dots,n\}$, let $b_1^i b_2^i \cdots b_{\log n}^i$ denote the bits of $i$. The $i$-th sender's string is defined as

$$x_i = H(s^1_{b_1^i}\|\cdots\|s^{\log n}_{b_{\log n^i}})$$

where $s^j_0,s^j_1$ are the random strings used in the $j$-th 1-out-of-2 OT.
This gets a 1-out-of-$n$ OT on random strings, which can be easily converted to chosen strings by sending the XOR.

(Note that the Naor-Pinkas protocol used a PRF, but if $H$ is modelled as a random oracle then this works too)


A key-generator outputs an encrypted string that only changes the second half - what weaknesses could that expose? The company I work for provides a software solution. The software is licensed and I have access to the license generator.

We have a company culture of challenging our perceived security but I am a very basic cryptanalyst. I would like to ask for some leads to see if I can prove our license generator needs to be fixed.

Example (not real licenses):

License #1: abc111
License #2: abc222

Real licenses are about 600 chars and look very much like an ssh-rsa public key.
(I can't explain it, they just look like one! If I could show you a real one, I am sure you would agree there is something in common)

The reason what you called "real licenses" look like ssh-rsa keys is probably just the encoding format for some of them. ssh-rsa keys are base64 encoded, and that might be the only reason. The decode content can really differ based on the license checking algorithm.

You'd probably be better off disclosing your license verification algorithm, and letting people comment on its security/strength which will enable you to improve it in case any issues are found. The fact that the licenses start with the same prefix, on its own, doesn't indicate much about the security of your license verification.
You should also be clear about the assumptions you're making about a potential cracker, and what can they do. That would help assess whether the licensing scheme is secure under those assumptions.


What is the difference between a sealed box and a normal box in libsodium? I'm trying to learn libsodium to better my crypto knowledge. One nagging question I have is what is the difference between libsodium's sealed box and their normal box? Not in terms of technicalities as the docs do distinguish this well; but in terms of practical use cases.

Per the docs:

  Sealed boxes are designed to anonymously send messages to a recipient given its public key.

  Only the recipient can decrypt these messages, using its private key. While the recipient can verify the integrity of the message, it cannot verify the identity of the sender.

  A message is encrypted using an ephemeral key pair, whose secret part is destroyed right after the encryption process.

  Without knowing the secret key used for a given message, the sender cannot decrypt its own message later. And without additional data, a message cannot be correlated with the identity of its sender.

Sadly this doesn't address the use case when this is needed. For example Say Alice generates a keypair and gives Charlie the untrusted 3rd party the public key for storage. Bob asks Charlie for the public key and sends Alice a message using said public key. From my limited understanding of this this should be secure and prevent Charlie from knowing the message. Is this not your basic end-to-end-trust-no-one system in the same vein as PGP?

If this system were to be implemented with an ephemeral key exchange as suggested by the sealed box concept would that not just add more overhead to an already secure system?

Perhaps I'm misunderstanding and perhaps my intended use case is different which is why I'll explain my mental model to better give context. (Also note I think the signal protocol uses ephemeral pre-keys and I also don't understand why in that context).

Alice runs an app on her phone which generates a unique keypair (unique in that it regenerates a new one every time the app opens) and then registers a unique address along with her public key with Charlie the back end server. The app then presents Alice with a URL that contains her unique address and a nonce. She shares this link with Bob who also opens the app providing it with the address and nonce. Bob's app generates a unique keypair then asks Charlie for Alice's public key (based on the address). Bob's app then encrypts Bob's public key along with the nonce and sends it to Alice (via Charlie). Alice's app verifies the nonce and then uses the provided Bob's public key and is now able to send him messages back.

AFAICT the above is a very basic key exchange through a third party in the same way we handle PGP key sharing on a key-server with the distinct difference in that once the session is over (app closed) the keys are no longer valid (secret keys erased) and a new session would be completely new identities and keypairs.

Is this even remotely related to the use of sealed boxes or have I only proved that I am sleep deprived and know nothing about crypto?

The premise of boxes is that Alice and Bob know each other and write to each other.  Alice can use a box to send a message to Bob.  On receipt of the box, Bob knows (a) it came from Alice, and (b) nobody else could have read or tampered with it.

The premise of sealed boxes is that Bob has an anonymous dropbox.  Alice can use a sealed box to send a message to Bob.  On receipt of the box, Bob knows nobody but the sender could have read or tampered with it.  But he knows nothing about who the sender was—it could have been Alice, or Charlie, or Dominique.

The nonce is only required to be distinct for each message Alice sends to Bob, and vice versa.  For example, Alice might count the number of messages she has sent so far, and use that number as a nonce.  If the nonce is large enough, say ≥192, as it is in crypto_box_curve25519xsalsa20poly1305 (but not crypto_box_nistp256aes256gcm where it is 96), it can safely be chosen uniformly at random for each message and affixed to the ciphertext.  The nonce need not be secret.

Neither boxes nor sealed boxes enables a third party to verify the authenticity of a message.  For that, you need digital signatures.

If Bob's private key is ever compromised, whether for boxes or for sealed boxes, or if Alice's private key for boxes is ever compromised, then any message Alice has sent to Bob can be decrypted.  To avoid this, protocols like Signal (a) regularly generate new keys and promptly erase the old keys for things like boxes,* and (b) use long-term key pairs only for digital signatures to assert what the user's current box public key is, so that compromising the long-term private keys doesn't enable retroactive decryption.

* A protocol that prescribes when to promptly erase keys is sometimes said to have ‘forward secrecy’, a term I prefer to avoid because in its glibness it obscures when the keys can be erased—which obscurity may serve to conceal lurking vulnerabilities like TLS session resumption even in sessions that use ‘forward secrecy’ cipher suites with ephemeral Diffie–Hellman key agreement.


AES key schedule. Does it use a KDF to generate the round keys? So for each round in AES a different key is used, and as I saw the keys are created form a master key.

My question is how these round keys are generated.

Are they created via a Key Derivation Function as the session keys, or its something else ?

No, it uses a specific type of algorithm called a key schedule. Unlike a KDF, it is not designed to be slow (in the case of a password-based KDF) or to be irreversible. The requirements of a key schedule are quite simple. Whereas a KDF might need to expand a key into a number of keys such that knowledge of any one key does not reveal knowledge of the master key or any other derived keys, that is not always true for a key schedule. If you have any round key for 128-bit AES, you can derive all other round keys.


Ring-LWE in other fields Can someone please tell me why in R-LWE we always make use of Cyclotomic fields, and specially those with degree equals to a power of $2$?
Can we use another fields without losing in hardness of the problem?
What about Quadratic fields for example?
Thank you!

We don’t always use power-of-two cyclotomics for RLWE. Many cryptosystems use other cyclotomics, or subfields thereof, or even other fields altogether. For example, many FHE schemes use non-two-power cyclotomics for “packing” and SIMD operations on plaintexts.
However, it is simplest to properly define and use RLWE over two-power cyclotomics, in large part because one can easily avoid using the “codifferent” (fractional) ideal $R^\vee$. (Other associated operations, like the NTT/CRT algorithm, are simpler in the two-power case as well.) So, this is probably why people tend to stick with two-power cyclotomics for RLWE.
The use of fields other than two-power cyclotomics can be justified by theory. The original LPR’10 paper proved the hardness of search-RLWE over any number field (not just cyclotomics), based on the conjectured quantum hardness of worst-case approximate-SVP on ideal lattices in that same number field. It also proved the hardness of decision-RLWE, assuming the hardness of search, for any cyclotomic number field (whether two-power or not); it turns out that this proof also works just as well for arbitrary Galois number fields, e.g., multiquadratics. Later, Peikert—Regev—Stephens-Davidowitz’17 directly proved the hardness of decision-RLWE over any number field (whether Galois or not), based on the same assumption as in the first sentence of this paragraph.
As for whether we can use quadratic fields, all of the above applies equally well for them, but the dimension is so small that worst-case SVP is easy—even on arbitrary lattices, not just ideal lattices. Similarly, RLWE over a quadratic field is trivially easy (except possibly if one used an enormous modulus, but this is not typical).


Why does RSA need p and q to be prime numbers? Despite having read What makes RSA secure by using prime numbers?, I seek clarification because I am still struggling to really grasp the underlying concepts of RSA.
Specifically,  why can't we choose a non-prime $p$ and $q$?
I do understand the key concept: multiplying two integers, even two very large integers is relatively simple. However, factoring a large integer is extremely difficult, even for a computer using known factoring algorithms.
If this is correct, then the original question posed by the OP in this thread continues to befuddle me.
This section from Henrick's answer in this post contains the relevant information:

It also means that if you were to select $p$, $q$ just as odd integers, you
would make it harder for yourself to find $\phi(n)$, while at the same time
decreasing the relative size of the second-largest prime factor, and
thereby making it easier for everyone else to factor n. In fact, it
would be as hard for you to factor n as it would be for everyone else,
so you would completely lose the trapdoor component of your scheme
(if not making it completely infeasible to find a pair $e$, $d$).

But I do not understand why we make it harder for ourselves to find $\phi(n)$. I BELIEVE that it has to do with the fact that for any prime, $n$, all integers up to $n-1$ are relatively prime. If the integer is not prime, then we actually need to find which integers up to n are actually relatively prime.
I understand how we are decreasing the relative size of the 2nd largest prime. For example: $10403$ has prime factors of $[101,103]$ while $11000$ has prime factors of $[2, 2, 2, 5, 5, 5, 11]$.
So, if I understand things correctly, choosing a non-prime $p$ and a non-prime $q$ would theoretically work, but the issue is that we would be creating a more insecure encryption scheme since:

the product of non-prime $p$ and non-prime $q$ are more easily factored (2nd largest prime is smaller than if $p$ and $q$ were prime);
finding $\phi(n)$ becomes more difficult for the key generator step, which decreases efficiency with the aforementioned decrease in security

Sorry if this is completely obvious, but I am a newbie in higher math and programming. I really want to understand this as deeply as I can.

However, factoring a large integer is extremely difficult, even for a computer using known factoring algorithms.

Not categorically. Factoring a large integer is trivial if it is only composed of small factors.

A fairly naive algorithm for factoring N is the following:

while N > 1:
  for p in increasing_primes:
    while p divides N:
      N = N / p
      factors.add(p)

With this algorithm, $340$ $282$ $366$ $920$ $938$ $463$ $463$ $374$ $607$ $431$ $768$ $211$ $456$ can be factored in exactly $128$ iterations of the innermost while. (The number, of course, is $2^{128}$)

The more prime factors a composite number has, the smaller those factors have to be. For example, $919 \cdot 677 = 622$ $163$. With the naive algorithm, this takes $157 + 1 = 158$ iterations to factor. A number of roughly the same size comprised of three factors, $73 \cdot 89 \cdot 97 = 630$ $209$, only takes $25 + 2 = 27$ iterations to factor.

Similarly, a 1000-digit number composed of two roughly equally-sized factors will take about $10^{497}$ iterations to factor. A 1000-digit number composed of 100 roughly equally-sized factors will take about $434$ $294$ $481 + 99 \approx 10^{9}$ iterations. And a 1000-digit number composed of 1000 roughly equally-sized factors will take about $4 + 999 \approx 10^{3}$ iterations.

So, to make factoring as difficult as possible, you want the prime factors to be as large as possible, which means you want N to have the fewest factors possible. With $p$ and $q$ prime, $N$ has two factors. With $p$ and $q$ composite, $N$ has at least four factors, possibly more.

Note that this is far from a complete answer on why (we think) RSA is secure, but I hope it gives a more intuitive / example-based idea of why $p$ and $q$ should be primes.

Note also that $p$ and $q$ should be similar in magnitude. If one is much larger than the other, factorization becomes easier. For example, if $p = 43$, the naive algorithm would only take $14$ iterations.

(After reading the comments (thanks Taemyr and Daz C), I corrected some mistakes in the answer. The main point is unaffected.)


Diffie-Hellman Primitives in SP800-56A I wonder if someone can give an explain about the different between two Diffie-Hellman Primitives defined in SP800-56A, CH5.7.1

5.7.1.1 Finite Field Cryptography Diffie-Hellman (FFC DH) Primitive
5.7.1.2 Elliptic Curve Cryptography Cofactor Diffie-Hellman (ECC CDH) Primitive

Actually the first one is named as (FFC DH) and its looked very similar to RSA way.
And for the 2nd one , though it is based on ECC, but is also on a Finite Field.

A group if a set of elements and some operation that satisfy some requirements. This operation is usually called "addition" or "multiplication", depending on the group, even though it may not be actually the classic addition or multiplication. The integers $0 < x < p$ for some prime $p$ form a group under the modular multiplication operation (multiply the integers, then compute the remainder of the division by $p$). This group can be denoted by $\mathbb{Z}_p^*$.

A field is a set of elements with two operations that satisfy some requirements; you can think about it as consisting of two groups (one for each operation). The integers $0 <= x < p$ for some prime $p$ form a field under modular addition and multiplication. This field can be denoted by $\mathbb{F}_p$.

That is the field that is used by FFC DH. However, note that DH only requires a group, and not a field. FFC DH uses the multiplicative group of the finite field, i.e. $\mathbb{Z}_p^*$; the addition operation is never used.

An elliptic curve is a set of $(x, y)$ coordinates ("points") that satisfy some equation. In cryptography, these coordinates are elements of a finite field, e.g. $\mathbb{F}_p$. The curve also forms a group under the "point addition" operation, which takes two pair of points and return a third point also on the curve. Note that a curve forms a group, and uses an underlying field, but it's not a field itself.

(A curve has a "point multiplication" operation, but that's not a group operation between points, it's simply repeated addition, like exponentiation in $\mathbb{F}_p$ is just repeated multiplication).


Why HAIFA and sponge constructions are not prone to length extension attacks? I was writing in a document about the flaws of the MD construction which pushed cryptographers to create different and more robust constructions. However, I don't know why HAIFA and Sponge constructions don't suffer from this attack.

Sponge Construction
In sponge construction, the block size $b$ has two parts, $r$ is the rate and it is the written part and $c$ capacity is the untouched part by the input/output, $b= c+r$

The output is taken from $r$ in the squeezing stage. Therefore not all of the $b$ is the output. This prevents the length extension attack like in the truncations of SHA2, which are standardized after Keccak.
The idea is: when someone wants to extend a message $abc$ into $abcde$ they should be able to continue the hash output where it is left, the hash value. $h=H(IV,\text{"abc"})$ then using the $h$ as the IV for the $H' = H(h,\text{"df"})$ then the length extension is possible (here we did not consider the padding and not a big issue, either). Originally the length extension attack worked on MAC with $H(\text{secret}\mathbin\|\text{message})$ construction. Although the output will be different, the attacker can inject this with the new MAC tag, without the knowledge of the key, and the server will accept it. So. it works even the attacker cannot have the secret and the message. It doesn't work with HMAC, which is designed to be secure against this. On the other hand, KMAC based on SHA3 has much simpler design since SHA3's immunity.
The sponge constructions' two-stage design, that is absorbing and squeezing together with the $c$ prevents the length extension attack with a calculatable countermeasure.
Below is the capacity against the length extension attack of SHA-3.
\begin{array}{|c|c|c|c|c|}\hline
\operatorname{SHA3}\text{ variant}\  & \text{output size} & \text{internal block size} & \text{rate } r& \text{Capacity against LEA} \\ \hline
\operatorname{SHA3-224} & 224 & 1600 & 1152 & 448= 1600-1152\\ \hline
\operatorname{SHA3-256} & 256 & 1600 & 1088 & 512 = 1600-1088 \\ \hline
\operatorname{SHA3-384} & 384 & 1600 & 832 & 768 =1600-832\\ \hline
\operatorname{SHA3-512} & 512 & 1600 & 576 & 1024 = 1600-576\\ \hline
\end{array} LEA stands for Length Extension Attack.
HAIFA construction
The HAIFA construction is not mentioned about countermeasure about length extension, however, it can be designed/modified simply using a different salt in the last block as in BLAKE2 Is Blake2b vulnerable to length extension attacks?, like using $true$ for the last block and using $false$ for any other block. The HAIFA construction is simple as;
$$C:\{0,1\}^{m_c} \times \{0,1\}^n \times \{0,1\}^b \times \{0,1\}^s  \to \{0,1\}^{m_c}$$ or
$$h_i = C(h_{i-1}, M_i, \#bits, salt)$$ $\#bits$ is the number of bits hashed, $h_0 = IV$, and $salt$ is the usual salt value.


What is the exact purpose of length padding in Merkle–Damgård hash functions? Is a length padding technique in a hash function used to avoid length extension attacks ?

Hash functions are defined to work on an arbitrary integer number of blocks. The minimal quantity of data that can be processed by an hash function is a single block.

So, if the message size is not an integer multiple of the block size one has to pad it to the right size.

One needs also to make the message + padding have one and one only interpretation, otherwise it would be simple to create collisions. Therefore adding the padding lenght gives an unique way to interprete the message+padding couple.

As example: let's imagine that one pads addings just zeros to achieve the right lenght. Therefore message $m$ and message $m||0$ have the same hash image.


Finding the first few digits of p and q Is there a way to find out the first few digits of the factors of the RSA numbers (RSA-1024 or RSA-2048)?

I do not want to get all the digits but only first 4-5 digits. My question is thus more precisely:

Is there a known, efficient, classical algorithm, that given a composite number, outputs the 4-5 most significant decimal digits of one of the prime factors of this number?

I do not think this is a practical possibility. In order to get the 4-5 most significant bits, the bits of lower significance must be known. This is due to the manner in which numbers are multiplied. The most significant bits of the product do not depend solely on the most significant bits of the factors. Bits of lower significance may have an effect too due to the propagation of carry bits up the product as partial products are summed. Even with some look-ahead optimizations the bits of lower significance would still need to be known. The best I could see would be a probabilistic scheme in which k>5 bits would would be attempted to be solved and the result would be probabilistically correct with some chance as a function of k.


Group Dependent Language The text below has been taken from the below paper Groth-Sahai Paper. The relevant part is highlighted in red.

What does this group-dependent language mean in this context? From the definition of a language we know that it means a set of strings. In this case, what are all the strings forming the language?

You may be aware of the fact that zero-knowledge proofs for any language in $NP$ can be constructed if you have a zero-knowlege proof for any $NP$-complete language. Then you can reduce your original language to the $NP$-complete one in polynomial time and you are done (more precisely you reduce the instance and the corresponding witness). As the $NP$-complete language you could use 3-coloring or circuit satisfiability for instance. Although in theory such an approach is feasible, it is not practical for cryptographic protocols.

Group dependent language here means relations of elements and exponents in bilinear groups that can be expressed using all the equations illustrated in Figure 1 of the paper you linked to. Although this language is a more restricted language than "any language in $NP$", it is expressive enough for many interesting tasks that show up in cryptographic protocols to prove statements about ciphertexts, commitments and (structure-preserving) signatures for instance. The benefit is that it is practically efficient.


What cryptanalysis is possible against two independent keystreams XORed against plaintext? If a wise person was unsure about which commercial cryptography standards are truly secure from the fascist powers that be, it would seem the obvious option for companies and individuals is to now use two independent algorithms to encrypt. To be clear I am not talking about a cascade cipher in CBC mode e.g. $Encryption_2$($Encryption_1$($plaintext$)), where an attacker can unravel one layer of encryption at a time because they have direct access to the resulting ciphertext from each algorithm.

I am talking about using two unique keys and two block cipher algorithms in Counter Mode (or stream cipher algorithms) to generate two unique keystreams, then XORing (⊕) them together with the plaintext. For example:

$Key_1$ = 256 bit random key
$Key_2$ = different 256 bit random key
$IV$ = 128 bit random initialization vector for AES
$Nonce$ = 192 bit random nonce for XSalsa20
$Keystream_1$ = $AES$$_C$$_T$$_R$$(Key_1, IV, Counter)$
$Keystream_2$ = $XSalsa20(Key_2, Nonce, Counter)$
Ciphertext = $Keystream_1$ ⊕ $Keystream_2$ ⊕ $Plaintext$
Decryption = $Keystream_1$ ⊕ $Keystream_2$ ⊕ $Plaintext$
Data sent over wire = $IV$ | $Nonce$ | $Ciphertext$

The key exchange, MAC and transport protocol are out of scope for the question, I want to focus on the encryption part.

It would appear that an attacker's methods of cryptanalysis for each individual algorithm would not work as they do not have access to the plain ciphertext of either algorithm because the keystreams from each algorithm are XORed together.
Known plaintext cryptanalysis would not work either. For example the first 5 bytes are hello, and they have a resulting ciphertext of xAi3z. With a single keystream they could get those 5 bytes of the keystream which would be the plaintext ⊕ the ciphertext. Then over the course of multiple ciphertexts/known plaintexts there might be a weakness to deduce the original key which generated the keystream. However with two independent keystreams, a cryptanalyst can't know which combination of bits make up the combined keystream. For example: they know plaintext bit 0 and ciphertext bit 1, but do not know whether the keystream bits were definitively a 1 or a 0 bit, nor which bit came from which keystream.

Advantages:

Protection from non-public flaws or weaknesses in either encryption algorithm.
Cryptanalysis is almost impossible?
Decryption requires breaking both algorithms.
Brute force required to find two random keys instead of one ($2^{256} + 2^{256}$) or $2^{128} + 2^{128}$ (on a quantum computer).

Minor disadvantages:

Generating and exchanging two keys instead of one.
Slightly more network traffic required to send an extra IV or nonce with each transmission.
Slower encryption and decryption.

My questions:

Assuming both algorithms are implemented properly, the random number generators produce truly random data and there is an attacker in a privileged network position intercepting multiple ciphertexts, how or what kind of cryptanalysis could the attacker perform against this scheme to break the confidentiality of messages?
Is there a faster method than brute force to find the two encryption keys or break the confidentiality of messages?

Asmuth and Blakley provided a proof that, assuming the keys for each cryptosystem are chosen independently, breaking their composite cryptosystem is at least as hard as breaking the hardest part of either. [1]  Building on their work, cascade ciphers have been shown to in fact be harder to break than the hardest part of either.

Admittedly, what you're talking about sits in an awkward place between cryptographic exponentials and cascade ciphers.  A cryptographic exponential (of two ciphers) is defined as:  $$M\oplus R\oplus R'\>\|\>E(R)\>\|\>E'(R')$$ where R and R' are truly random bitstrings.

I can't give much of anything concrete other than that.  Hope this answers your question.

C. Asmuth, G. Blakley.  "An efficient algorithm for constructing a cryptosystem which is harder to break than two other cryptosystems"


What's the difference between RSA and Diffie-Hellman? I've been reading on a lot of websites that same thing: RSA is for communication using the public and private key for both the server and client, where Diffie-Hellman is just for exchanging the same secret key that will then be used for both encryption and decryption, but they both depend on the same MATHS, e.g: that question on quoraThen I was confused when I also read that RSA shares a master and pre-master key, as well, like in this question:SO, the question here is, does RSA use the public and private key to encrypt the whole conversation, or is it used just to encrypt a key then the encryption depends on that symmetric key? And if it was used to encrpyt the key and it was the same MATH as Diffie-Hellman, so what is the difference anyways??

Diffie-Hellman Key Exchange

Problem: We have a symmetric encryption scheme and want to communicate. We don't want anybody else to have the key, so we can't say it out loud (or over a wire).

Solution/Mechanics:

We each pick a number, usually large, and keep it a secret, even from each other. I'll pick $x$, and you'll pick $y$.
We agree on two more numbers, both prime, which anybody can know. We'll call them $g$ and $n$.
I'll calculate $g^x\bmod n$ and tell you my answer. You'll calculate $g^y\bmod n$ and tell me your answer.
Our shared key is $g^{xy}\bmod n = (g^y\bmod n)^x\bmod n = (g^x\bmod n)^y\bmod n$.

RSA Asymmetric Encryption

Problem: I want anybody to be able to encrypt a message, but I'm the only one who can decrypt it. I don't want to share decryption keys with anybody.

Solution/Mechanics:

I choose two large primes, $p$ and $q$.
I calculate $n$ such that $pq = n$.
I calculate $t$ such that $(p-1)(q-1) = t$.
I choose an integer $e$ that is both less than $t$ and coprime with $t$.
I find $d$ such that $d$ is the multiplicative inverse of $e$ modulo $t$.
I release $(e, n)$ as my public key, and retain $(d, n)$ as my private key.
When you communicate with me, you treat your message as a large number $m$. The ciphertext $c$ is given by $c = m^e\bmod n$, and decrypted by $m = c^d\bmod n$.


How can one show that an ElGamal-like signature verification scheme is valid? For an ElGamal-like signature scheme, I am given two things:

The signing function,
the verification function.

How can I show that the verification function is valid?

Example 1:

Signing: $s := x^{-1}(m - k·r) \pmod {p - 1}$

Verification: $g^m = (g^x)^s · r^r \pmod p$

NOTES:

$g$ is the generator over the set $\mathbb Z^*_p$.

$x$ is the secret value, $g^x$ the public one.

$r := g^k \pmod p$

Your scheme is not the "true" ElGamal signature scheme: you swapped $x$ and $k$. I assume that $m$ is the hash of the message to sign, not the message itself.

Your scheme is sound, which means that the verification algorithm will return "ok" for a signature which has been generated as you suggest. To see that, remember Fermat's Little Theorem which says that for a prime $p$ and every integer $a$ (not multiple of $p$), we have $a^{p-1} = 1 \pmod p$. This means that when dealing with exponents, we can compute them modulo $p-1$.

So, when looking at your verification equation:

\begin{eqnarray*}
    (g^x)^s r^r &=& (g^x)^{x^{-1}(m - kr)} (g^k)^r \cr
                &=& g^{m - kr} g^{kr} \cr
                &=& g^m
\end{eqnarray*}

Soundness means that the algorithm works as intended, not that it is secure. This specific variant of ElGamal has been proposed in 1990 by Agnew, Mullin and Vanstone (the article is called "Improved Digital Signature Scheme based on Discrete Exponentiation"; I could not find a freely downloadable version). It has then been studied in a more general framework, called Meta-ElGamal Signature Schemes. As far as I know, it is still believed secure, but uninspiring (thus understudied), because, like most ElGamal variants, it leads to rather large signatures. DSA is preferred.


Add a pepper to a hash: as a string or a buffer, and should I calculate a hash of a peppered plain text? I'm using a bcryptjs to generate a computationally slow hash function for storing passwords:

BCRYPT.hash(plainTextPassword, HASH_ROUNDS_NUM);

Now I want to add a pepper before a hash is calculated:

BCRYPT.hash(pepperedPassword, HASH_ROUNDS_NUM);

where pepperedPassword = plainTextPassword + PEPPER;

Questions:

Should I represent a PEPPER as a string or as a buffer?
To calculate a pepperedPassword I can either just concatenate two values:

pepperedPassword = concate(plainTextPassword, PEPPER);

or concatenate them and then calculate a fast hash of it (in addition to  bcrypt):

const concatPassPepp = concate(plainTextPassword, PEPPER);

const hashedConcatPassPepp  = crypto.createHash("SHA3-512").update(concatPassPepp, "utf8").digest("base64");

Is it a useful idea to calculate a fast hash of password-pepper concatenation before sending it to bcrypt? Which scenario should I prefer?

Both questions are asked from security and performance point of view.

To calculate a pepperedPassword I can either just concatenate two values:

Bcrypt limits the password. This means that if the password is too long (longer than 56 bytes), it will simply be truncated. If you just attach the pepper to the password, there is a high risk that this will happen. Then the pepper's security gain could even be lost without being noticed.

Use HMAC or even a hash function to combine a password and a pepper.

  Should I represent a PEPPER as a string or as a buffer?

That's up to you, but if you use HMAC or a hash function, it's obvious not to use a string.


key length considerations Learning about cryptosystems and basic cryptology and I have a sort of vague understanding of key sizes/key space and think I may have done something wrong in my calculations, can someone please explain how to properly calculate key space/length I would greatly appreciate it, thanks!

Assume a password consisting of 8 letters, where each letter is encoded by the
ASCII scheme (7 bits per character, i.e., 128 possible characters). What is the
size of the key space which can be constructed by such passwords?
128!
What is the corresponding key length in bits?
56 bits
Assume that most users use only the 26 lowercase letters from the alphabet instead
of the full 7 bits of the ASCII-encoding. What is the corresponding key length in bits in
this case?
28 bits
At least how many characters are required for a password in order to generate a
key length of 128 bits in case of letters consisting of
a.  7-bit characters?
19 char
b. 26 lowercase letters from the alphabet?
32 char

As there is some minimal attempt in solving I will answer at least in part.

No 128! would be the number of permutations. But that is not what we are doing, we 128 is already the number of possibilities to combine 7 bits $2^7$ if you have 8 of these then you get: $128^8$ or alternatively bitwise $2^{56}$

yes

no, 26 letters. need $\log_2(26)$ bits or just over 4.7 bits per letter. Assuming compact representation and after rounding it 8 independent letters need 38 bits.

I'll leave something for you still.


What was the key length of the Enigma? When I type in any plaintext to an Enigma machine (Enigma machine emulator) the substitution does not seem to follow any pattern. In other words, there is no cycle in the use of enciphering alphabets (defined as the number of switches done when turning a plaintext letter to a ciphertext letter - which can vary from 0 to 26).

But since the key is the alignment of the rotors, there must be a finite key length even though it probably is longer than any plaintext ever would be. I imagine if you keep writing long enough, the rotors will eventually align in a way they already were. If I'm right - how long is the key?

And if the key is much longer than any plaintext, wouldn't that mean the Enimga is a one-time pad? From what I can read, the OTP is defined as an algorithm with a key longer than the plaintext. Is this wrong?

Enigma works with the idea of one time pad, it's a machine that automates key generation. In the one time pad, we have to generate a random key with the same length as plaintext but in Engima we make few setups, and the machine creates a that random key.
Here is the enigma procedure

A day key has the form

Plugboard setting: A/L–P/R–T/D–B/W–K/F–O/Y
Scrambler arrangement: 2-3-1
Scrambler starting position: Q-C-W

Sender and receiver set up the machine the same way for each message
Use of message key: a new scrambler starting
position, e.g., PGH

first, encrypt and send the message key, then set the
machine to the new position and encrypt the message
initially, the message key is encrypted twice


Zero Knowledge Proofs: to establish a public key cryptography encryption I am very interested to know in the general sense how two parties who know each other are able to continue a conversation IF and ONLY IF they both earn the same salary. For example, we have a person X who earns 75000USD, but they only want to continue speaking to person Y IF and ONLY IF person Y also earns 75000USD. They do not really know how much person Y earns but much rather they get a bit of some sort similar to a signature where b=0 if personXSalary != personYSalary and b=1 if personXSalary == personYSalary. Only if b=1, then does person X know the actual salary of person Y

My question is, how would one instantiate such a public key encryption scheme to ensure this? I was thinking of something along the lines of Zero Proof Knowledge but then MACs also was another thought

By using SPAKE2, we can achieve this as Poncho said in comments.

Let $s_a$ be the salary of Alice
Let $s_b$ be the salary of Bob
Let we have Ed25519 curve with the base point G.

Exchange part;

Alice  pics a random scalar $x$ and calculates $X = x\cdot G$ and $T = s_1\cdot M+X$, where $M$ is another point on ECC and sends the value $T$ and $M$ to Bob (pake message).
Bob pics a random scalar $y$ and calculates $Y= y\cdot G$ and $S = s_2\cdot N + Y $, where $N$ is another point on ECC and sends the value $S$ and $N$ to Alice.

Key calculation part:

$Key_{Alice} = x ( S - s_a \cdot N) = x ( s_b N + Y - s_a N ) = x(s_b - s_a)+xyG $
$Key_{Bob} = y ( S - s_b \cdot M) = x ( s_a M + X - s_b M ) = x(s_a - s_b)+xyG $

if $s_a = s_b$ then we will have a cancelation to $xyG$ on both sides. Now, two sides can assume that they have a key agreement, without knowing the equality. They can encrypt pre-agreed plaintexts and sent each other, after this, they can conclude that their salaries are the same if the decryptions are successful, they conclude otherwise if not successful.

After the conclusion of success, one can convert the result into a bit $b$ by;

if p1 == Dec(xyG,c1)
   return 1
else
   return 0


How do single use passwords work for an encrypted message LastPass encrypts its data before sending it to their servers. The key for the data is generated using a combination of the master password and username.

How then can a one-time password be used to decrypt this data? The data on the server has been encrypted with the master password and username. Does this mean that LastPass stores a new version of encrypted data for every (single-use) password?

As hunter notes, the only people who can really say what LastPass actually does are those who work there.  However, as long as we only consider what they can and should do...

They don't really need to store a separate copy of your data for each one-time password.  Instead, all they need to store for each password is an encrypted copy of the key used to actually encrypt the data.

So, when you log in using a one-time password, the password is (presumably) passed through PBKDF2 to derive a "key-encryption key", which is then used to decrypt the actual key needed to decrypt the data.


How Elliptic-Curve affects the Server Key Exchange parameters In Finite Field DHE, the server sends the following parameters in the server key exchange message:
$p$: prime
$g$: group
$g^b$: the server's public DH key

In DHE_RSA (non anonymous DHE), the server signs the parameters. The full parameters according to the specs are:

  ServerKeyExchnage($p$, $g$, $g^b$, sign(hash($\mathit{server\_nonce}$,
  $\mathit{client\_nonce}$,$p$,$g$,$g^b$))

The client sends it ClientKeyExchange which contains the client's public DH key:

  ClientKeyExchange($g^a$)

ECDHE uses Elliptic-Curve and this entails different methods in selecting the key parameters.

1) In terms of TLS message, if the key exchange is Elliptic-Curve not Finit-Field, precisely how this affects the parameters and messages above? What does it changes in terms of the exact parameters the client and server send?

2) In terms of key parameters, does Elliptic-Curve changes the method used by both parties to compute the pre-master-secret? In Finit-Field, the client's pre-master-secret is computed by:

$pms = g^{ab}$

The same for the server:

$pms = g^{ab}$

Since EC does not use $g$, is the pre-master-secret still computed by multiplying the other peer's public ECDHE parametrs in its private ECDHE parameter? I.e:

$pre\_master\_secret_{Server} = ECDHE\_pk _{Client} \times ECDHE\_sk _{Server}$

Generally a pre-selected set of parameters are used: a named curve such as brainpoolP256r1. Here the parameters have been pre-selected. It is computationally inefficient to choose the EC domain parameters on the fly, and preferably the other party should be able to make sure that the parameters are generated securely. So the $p$ and $g$ used for Finite Field DH are commonly replaced by a single identifier (e.g. in text or an OID, depending on the implementation) that represent the domain parameters.

The the curve parameters can also be communicated using the actual values. For a curve over a prime field the parameters are:

the prime field $p$;
the coefficients $A$ and $B$;
the base point $G$ consisting of coordinates $x$ and $y$;
the prime order $q$;
the cofactor $h$, commonly set to 1.

sometimes a seed - to generate the parameters - is communicated as well.

The base point G here takes the same role as the $g$ in Diffie-Hellman over a finite field. Instead of repeating the answer, you can find a complete description here.

In general ECDH is described using point multiplication instead of exponentiation.

Lets describe it using:

$P$ for the public key (so $P_A$ is the public key of $A$)
$S$ for the private key (so $S_A$ is the private key of $A$ called $a$ in the question)
$X$ is the shared secret as we're running out of variable names
${}\times{}$ is point multiplication

Calculation of the public key:

FFDH: $P_A = g^{S_A}$
ECDH: $P_A = S_A \times G$

And the key agreement itself:

FFDH: $X_B = P_A^{S_B} \to X_B = (g^{S_A})^{S_B} \to X_B = g^{S_AS_B}$
ECDH: $X_B = S_B \times P_A \to X_B = S_B \times (S_A \times G) \to X_B = S_A \times S_B \times G$

and for both you can see that they rely on the commutative properties of modular exponentiation and point multiplication. It is easy to see that $X_A = X_B$ using both methods.

It is simply possible to write $g^a$ and say that the normal exponentiation function is representing multiplication in a cyclic group. So in that case $g^a$ would be seen as $g \times a$ for Elliptic curves. $g$ is however generally written in uppercase as $G$ (not to be confused with cyclic group $G$) because it is a point, not just a single number.

Although EC operations are often described using multiplication and (point) addition it is important to keep reminding yourself in which model you're operating. There are a lot of ways and a lot of ways to map variables in ECC, making a hard to understand field even more difficult to grasp.

In the end your CPU will still have to perform modular exponentiation to implement point multiplication. The modular exponentiation is however over smaller numbers, making it more efficient.


Do I need a salt for Scrypt if the data is client-side? I have a web app, in which I am encrypting user data client side. Each client has their own password, which is used to derive an encryption key (via Scrypt) for encrypting their data. Since the data is client side and a hacker has full access to the (encrypted) data, would it be necessary to use a salt for Scrypt? The reason why we use a salt for KDFs is to reduce rainbow tables affecting web servers. Since there is no web server in play here, and the attacker can attack however they like, then a salt would provide no additional benefit, am I correct?

Can you guarantee that the users are going to use high-strength passwords like dicewire? What if they are using simple passwords? Are they going to sue you when they are hacked and their data exposed? Lots of questions?
Consider that all of your users are hacked due to a bug in your application, then the attackers can execute a batch attack, too. Using salts can prevent this batch attack.
Using salt is the countermeasure to the rainbow tables where applicable. Therefore you limit them to single searching. In this case, two vectors remain

How good are the users' passwords?
How much can the password hashing algorithm slow the attacker?

The answer to the first question has a human side. You can test the quality of passwords up to some point and reject if lower. Teach your users to use the dicewire. Not hard to learn, see XKCD 936
The second question has a better answer as the Argon2id is the best choice. You can parametrize;

Number of iterations $t$, affecting the time cost.
Size of memory used $m$, affecting the memory cost.
Number of threads $h$, affecting the degree of parallelism.

This parameter must be tuned according to your target systems.
Therefore you can limit the attackers to use Massive GPU/ASIC parallel search mostly single case and with the timing, you can cripple their effort.
The recommendation is to use the salt, it is not hard to generate one by using /dev/urandom or similar methods.
And remember that the entropy and output cannot exceed the entropy of the input. Make sure that users have high-strength passwords.


Von Neumann Extractor - Which bit is retained? Which bit is retained in the Von Neumann debiasing algorithm?  00 and 11 are discarded and 10, 01 are retained but is the first or the second bit retained or does it matter?

In other words:

first: 10 -> 1 , 01 -> 0

second: 10 -> 0 , 01 -> 1

Original Paper (appears to be first but could be interpreted either way):

https://dornsifecms.usc.edu/assets/sites/520/docs/VonNeumann-ams12p36-38.pdf

Examples (first digit accept):

https://en.wikipedia.org/wiki/Hardware_random_number_generator#Software_whitening

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

http://pit-claudel.fr/clement/blog/generating-uniformly-random-data-from-skewed-input-biased-coins-loaded-dice-skew-correction-and-the-von-neumann-extractor/#more-410

https://people.seas.harvard.edu/~salil/pseudorandomness/extractors.pdf

Examples (second digit accept):

https://www.researchgate.net/publication/38359648_Iterating_Von_Neumann's_Procedure_for_Extracting_Random_Bits

https://www.esat.kuleuven.be/cosic/publications/article-2628.pdf

Examples of the second are present in papers regarding an Iterated Von Neumann algorithm.

It doesn't matter at all, since both $01$ and $10$ have the same probability $p(1-p).$


SSL 2.0 Finished Message Reference to SSL 2.0 specs. from: Mozilla - SSL 2.0
Can I conclude that SSL 2.0 Finish messages does not provide AMC for all the messages sent/received by both parties (as in TLS 1.2)? Due to lack of SSL 2.0 official detailed documentation, I am unable to confirm this.

2.2.1 Assuming no session-identifier

client-hello         C -> S: challenge, cipher_specs
server-hello         S -> C: connection-id,server_certificate,cipher_specs
client-master-key    C -> S: {master_key}server_public_key
client-finish        C -> S: {connection-id}client_write_key
server-verify        S -> C: {challenge}server_write_key
server-finish        S -> C: {new_session_id}server_write_key

Yes, SSL2 did not MAC the handshake. See (recentish and more available) rfc6176

  SSL 2.0 Deficiencies

  SSL version 2.0 [SSL2] deficiencies include the following:

  ...

  o  Handshake messages are not protected.  This permits a man-in-the-
    middle to trick the client into picking a weaker cipher suite than
    it would normally choose.


Verifying the integrity of ciphertext using the cleartext hash? I want to be able to verify the integrity of a ciphertext by providing the cleartext hash, for this to work it would need to:

$$hash(crypt(cleartext)) = f(hash(cleartext))$$

Where $f$ is an arbitrary function mapping the cleartext hash to the ciphertext hash.

Is there such a pair?

Update: I'm trying to prove the integrity to the receiver while delaying the key exchange until I'm ready to commit (send him the decryption details). The hash that proves the integrity comes from another source entirely.

There really isn't such a function $f$; encryption algorithms attempt to generate what looks like random bitstrings (at least, it looks that way to anyone who doesn't know the key), and because the plaintexts and the ciphertexts look unrelated, their hashes are also going to look unrelated.

On the other hand, what is the problem you're trying to solve?  When you say 'verify the integrity of a ciphertext', who is doing the verification?

Are you trying to allow the decryptor to verify that the message he got was the message that the encryptor sent without someone modifying it in the middle?  If that's the case, the standard way of addressing it is with a Message Authentication Code
Are you attempting to allow the encryptor to verify that the encryption process proceeded properly?  About the only ways to do that are to either run the encryption process again (with the same IV) and compare, or attempt to decrypt the ciphertext and compare.
Are you trying to allow someone in the middle (without the keys) to verify that a specific ciphertext happens to be a specific plaintext?  Well, that would be an unusual requirement; I don't have any bright ideas on that one.


Pseudorandom generator designs When designing pseudorandom generators what should one consider? Here is an example pseudorandom generator $F^t : \{0,1\}^n \rightarrow \{0,1\}^{4n}$. I have no idea what it means, so what does it kindly mean? It is one proposal written in a book for the truly random compression function $t : \{0,1\}^{2n} \rightarrow \{0,1\}^n$

Like how would I design one for truly random compression function such as $t : \{0,1\}^{2n} \rightarrow \{0,1\}^n$?

It just defines a function that expands the input size with the output size four times, where the output depends on configuration value $t$ as well. The hash function compresses the input to an output that is half the size (which is not common, usually a hash function outputs a constant size hash).

Here ^ is not a power function. It simply shows how many elements there are sequentially taken from the input set $\{0, 1\}$ - properly formatted it reads $\{0, 1\}^{4 \cdot n}$. So the $x$ in $\{0, 1\}^x$ simply defines an input or output consisting of $x$ bits - with value $0$ or $1$ of course.


Can we estimate the amount of entropy required to generate an RSA key? Of say 4096 bits as is a default GPG master key.

I can manage the first one or so almost immediately on Ubuntu.  It then  runs out of entropy when generating several more RSA keys, and I'm   forced by GPG into mouse wiggling and keyboard smashing.  More entropy is clearly required in those cases than available from /dev/random.

Is there some measure of the total amount of entropy bits needed to make a single 4096 bit RSA key?

Close but not quite is Detecting the amount of entropy used for random number generation. Nor How to generate 1024-bit RSA key as that only calculates the bits in the final key pair. Some sort of combination is probably required to take into account primacy testing.

Is there some measure of the total amount of entropy bits needed to make a single 4096 bit RSA key?

Well, there are two relevant attacks against RSA:

The attacker uses NFS to factor the modulus
The attacker scans through the possible entropy inputs that possibly generated the public key, and for each such input, generates the corresponding RSA public key, and see if that's the one he's looking for.

The first attack is estimated to take circa $O(2^{160})$ time; while the second attack will take circa $O(2^k)$ time if we use $k$ bits of entropy, hence if we use $k=160$ bits of entropy, the second attack is no easier for the attacker than the first (which doesn't depend on how much entropy we collect).  Note that this rather crude analysis ignores some significant constant factors (the algorithm to turn an entropy sample into an RSA public key isn't cheap); however for this question, it should be good enough.

In addition, if we use our 160 bits of entropy to seed a good CSPRNG, and use the CSPRNG output to generate the actual bits used by the prime searching algorithm, that means that there is no easier entropy-based attack.

So, 160 bits are sufficient, and significantly fewer entropy bits will cut into the security of the RSA key.

Now, that's what is possible; I don't know the algorithm that GPG uses to search for RSA public keys - they may use significantly more.


How is NIST's Key Wrap (using AES GCM) different than normal AES GCM Authenticated encryption? From what I could gather, it seems like that NIST's key wrap (publication) provides similar security like AES-GCM Authenticated encryption. If this is true, why did we need a separate specification for key wrap in the first place ?

You can find some info in section B.2. "Comparison of Functionality with Other Authentication Methods" in NIST SP 800-38F, where it said:

  2) Many authenticated encryption algorithms ... provide an efficient means of authenticating associated data that is not confidential ...

  3) Digital signatures on ciphertexts or MACs on ciphertext can be verified without decrypting the ciphertext. ...

So obviously, NIST KWs don't allow authentication without decryption or associated header data.

But apart from NIST, you may also be interested in the paper Deterministic Authenticated-Encryption, where it gave a treatment on what does it mean to be a "key-wrapping" mode. To summarize, we can look at the following quote from the introduction section:

  We call the goal deterministic authenticated-encryption (DAE) ... In a DAE scheme, encryption deterministically turns a key, a header, and a message into a ciphertext.

Where as traditional AEAD as treated semi-conanically in RFC5116: An Interface and Algorithms for Authenticated Encryption, a nonce/IV needed to be provided so as to provide so called "semantic security".

As to

  Q: why did we need a separate specification for key wrap in the first place?

Determinism decreases the likelihood that misuse of the schemes happens, as could with non-deterministic schemes running on top of broken RNGs or compromised state.


using Post-quantum asymmetric ciphers instead of RSA We can't trust RSA to encrypt our Emails so what is best post-quantum cryptography system as alternative for RSA which provide good security and don't be breakable? because McEliece cryptosystem looks break with 2^60.55 bit operations..

My impression is that there is no production ready post quantum scheme ATM.

NTRU seems to be decent (complete spec,  reasonable parameter-sizes and performance), but I think it's patented. No idea about the licensing terms.

But whatever scheme you choose, don't use it instead of a conventional scheme(RSA, DH, ECDH) but in addition to a conventional scheme. If you use a good construction, your protocol will be as secure as the stronger of the schemes.


Advanced Encryption Standard Algorithm Secret Key just a follow up question with this question..

How does the key schedule of Rijndael looks for keysizes other than 128 bit?

A 256-bit key can still encrypt a block of plaintext in 128 bit?

but in this tutorial, to encrypt 128-bit plaintext, It need 128-bit of secret key also..

can someone provide me a clear explanation about using of 192, 256 bit key to encrypt a 128-bit block of plaintext?

The only thing that I can understand is that If you will encrypt a 128-bit of plaintext, it need to use 128 bit of secret key, to encrypt a 192 bit of plaintext, it need to use 192 bit of secret key, to encrypt a 256 bit of plaintext, it need to use 256 of secret key.. that is the only thing that I know based on my research..

One very important thing you are missing is the idea behind AddRoundKey and the Key Schedule.

Each round, there is a new round-key. The round key is derived from the main key. So, say you have a 128-bit block (AES) and a 256-bit key. The internal state is 128-bits and the round key is 128-bits. The specification states that for this configuration, there will be 14 rounds. Since the round-key changes for each round, it is easy to see that all 256-bits of the main key will be used over the 14 rounds.

To see exactly how all 256-bits of the main key are used, you'll have to dive into the details of the key schedule.


Converting Ed25519 public key to a Curve25519 public key I understand that:

$$x_{montgomery} = \frac{1 + y_{edwards}}{1 - y_{edwards}}$$

Using the libsodium ed25519 implementation, I have tried to write the following:

void keypair_2(unsigned char *pk, unsigned char *sk)
{
    ge_p3 A;
    int i;

    sk[0] &= 248;
    sk[31] &= 63;
    sk[31] |= 64;

    ge_scalarmult_base(&A,sk); // generate ed25519 public from sk.

    fe one;
    fe u, v, vinv;
    fe montx;
    fe_1(one);
    fe_sub(v, one, A.Y); //v = 1-y
    fe_add(u, A.Y, one); //u = y+1
    fe_invert(vinv, v); //vinv = v^(-1) = (1-y)^(-1)
    fe_mul(montx, u, vinv); //montx = u/v = (y+1)/(1-y)
    fe_tobytes(pk, montx);
}

And I have compared this against the curve25519 implementation, but I am getting differing results.

I am unsure as to my error.

ge_scalarmult_base returns GroupElementP3 which doesn't have (x, y) as members. It has X, Y, Z from which you can compute x = X / Z and y = Y / Z.

So you have two choices:

Compress the point with ge_tobytes:

byte[32] Abytes;
fe y;

ge_scalarmult_base(&A,sk);

ge_tobytes(Abytes, &A);
fe_frombytes(&y, Abytes);

// your code here using `y` instead of `A.Y`

The downside of this technique is that it costs two field inversions. So I'd only use it if the input is a compressed point.
Modify the formula to work with X, Y, Z coordinates:

$$x_{mont} = \frac{1+y_{ed}}{1-y_{ed}} = \frac{1+\frac{Y}{Z}}{1-\frac{Y}{Z}} = \frac{Z+Y}{Z-Y}$$

fe_sub(v, A.Z, A.Y); //v = Z - Y
fe_add(u, A.Y, A.Z); //u = Z + Y

This solution is preferable if you just computed the point without having reduced yet. Typically directly after a scalar multiplication.


Any known cases of lucky collisions resulting in security breaches? This isn't a deep technical question, but I feel like this is a good place to ask. Modern cryptography generally rely on statistical chances of collisions according to current computing powers. Are there any known cases where someone was lucky and cryptography was broken?

Also, would it be an interesting thing to do to gather as many keys as possible and try to break them all. Would it increase the chances of breaking some of them? I could see organizations like the NSA do something like this.

There have been similar "security breaches" where someone did indeed gather a lot of public RSA keys and successfully factored some of them using Euclid's algorithm.

I believe the weakness was that a lot of implementations didn't use "random enough" RSA key generators (by using a cryptographically secure random number generator) and this resulted in some common factors of said public keys.

Here's the paper with more information if you're interested.


ECC private key generation collision I am generating ECC private keys. however I noticed that since ECC private key is just a BigInteger. e.g. spec256k1 says private key is anywhere between [0~2^256-1].

my question is, if everyone is using Random(32) to generate a 32bytes private key, there is not likely but still possible situation that 2 people could generate the same private key. therefore also same public key.

so if this happens on blockchain like Bitcoin or Etheruem, does that mean those 2 people are in theory sharing the same account? or wallet address?

maybe I am missing some details here. Please guide me.

Edit:

thanks for everyone's answer here.

the reason why I was asking this is because first I wonder if there is any protection against collision in the system. however, if there is, and you are told you had a collision, that basically means you figured out someone else's private key...

second reason is, I was considering generating a long(64bits) and then cast into BigInteger(32bytes) to be the private key. however, that will have a much higher collision chance due to the fact that I will only have a private key space of 2^64.

Assume that there are $2^{50}$ keys out there. Then calculating one of these keys by chance is $2^{50} \over 2^{255}$ for each calculation or a chance of one in $2^{205}$. Now say that you generate $2^{64}$ keys then you'd still only have a chance of one out of $2^{91}$ of hitting the right key.

Note that making sure that you hit a key would however require $2^{50}$ tests, and knowledge of $2^{50}$ operations by the public key of course. To test a single key the situation is significantly worse, the chance of finding it after
$2^{64}$ tries is only one out of $2^{191}$.

Chances of hitting the right key increase somewhat if you make sure you make sure that you don't generate the same key again. For instance you could start at a specific value and then simply test each following value. But that won't increase your chances by much and the calculation is too hairy to do here.

This is always what cryptography relies on: that you cannot just guess the private key. There is no cryptosystem to protect against that. And there doesn't need to be because the chance of generating a matching private key is negligible.

And think about it, I could guess the value of a coin as well. There is no protection against that either.

Note that a chance of one in $2^{91}$ is one in 2475880078570760549798248448 or one in 2 octillion 475 septillion 880 sextillion 78 quintillion 570 quadrillion 760 trillion 549 billion 798 million 248 thousand 448 (using the short scale).


Are there any algorithms for which generating any zero-knowledge proofs is not practical? It is related to my earlier question:

Can zkSNARK or other zero-knowledge proofs be used to proof message authenticity without revealing private key?

Are there any algorithms for which generating zero-knowledge proof is so computationally complicated that they cannot be generated in any practical time, by mainstream devices (PCs, smartphones)?

I am interested mostly in encryption algorithms, but any examples would be great.

The following is a fairly "boring" example, but likely works (I'll point out the specific assumption I'm making later). If you also feel its boring, it might help you refine your question so that the answer is more interesting.

Say you have some encryption scheme with security parameter $n$ (We may as well think of $n$-bit RSA, any example works). Say that encryption takes $T_E = O(f(n))$ time for some function $f(n)$.
Now consider some ZK proof of the statement you're interested in. Say that it takes $T_P = O(g(n))$ time to prove the statement, where the complexity depends on the security parameter chosen for encryption.

I'm going to assume that encryption is easier than proof generation, or formally $f(n) = o(g(n))$.
This seems fairly natural, but I'm not familiar enough with the particulars to know if it holds for all pairs of encryption schemes/proofs (although if it doesn't, one gets proofs 'for free' asymptotically for a particular encryption scheme, which seems odd).

We can then consider introducing another parameter $k$ (which is small compared to $n$), and look at the encryption scheme/proof system with security parameter $kn$.
I claim that the following two things should hold:

If $k$ is small enough, encryption with security parameter $kn$ will still be feasible on the devices you're imagining
As $f(n) = o(g(n))$, asymptotically proof generation will become infeasible before encryption does (as the complexity of proof generation grows "strictly faster").

So if we take $k$ large enough, we expect both encryption and proof generation to become infeasible. But as the asymptotic complexity of the two differ, we expect proof generation to grow infeasible first, so there should be some "intermediate values" of $k$ such that one can still encrypt, but cannot generate proofs.


Explanation of protocol secure under random oracle but insecure with any hash fuction It is known that there is a protocol that is secure in the random oracle model, but where any real hash function makes the protocol insecure.  The proof is constructive, but I could not understand the protocol in question.

Could someone explain the protocol in language that is easier for a programmer to understand?

I believe the "simple" examples are of the form

adversary can send honest party arbitrarily-long messages

messages sent by honest parties in that context all start with 0

when an honest party receives a message in that context that

starts with 1, if the rest of that message encodes a circuit then:

The honest party evaluates that circuit and the oracle at a secret value.

If the outputs are equal then the honest party does something obviously insecure.

.

This paper shows that even Fiat-Shamir can fail.


Publicly exposed hash of private key Would exposing a cryptographic hash function's digest (e.g. SHA-3) of RSA private key data compromise the key? If so, what are the possible (cryptanalysis-) vectors for attacking the key if an attacker had knowledge of this hash?

This does not compromise the private key as long as the hash function is preimage resistant, i.e. given $H(M)$ it is hard to find $M$ (or any  $M'$ giving the same $H(M)$). SHA-3 is assumed to be preimage resistant.


Design properties of the Rijndael finite field? So we've already had a question on replacing the Rijndael S-Box. My question is - can we use a different finite field other than the one given by $x^8 + x^4 + x^3 + x + 1$ in $GF(2^8)$. In other words, would any irreducible polynomial over this field do the trick or are the special considerations and properties of that particular reducing polynomial?

If a more general discussion on appropriate fields for cryptographic operations, such as those used in ECC, is necessary, then I'd be happy to hear it. What I'm trying to get to is an understanding of whether there are any important properties in terms of the "randomness" of the operation - for example, are there weak fields to operate over? For example, $x^8 + x^3 + x + 1$ ought to also be irreducible - so would it be suitable? I ask partly because of the Galois/Counter Mode issue with short tags which lead me to think not all fields might hold equal strength. Right? Wrong? Inconsequential?

For security of ECC, the choice of the irreducible polynomial is unimportant, because all finite fields with the same cardinal are isomorphic to each other (and the isomorphisms are easy to compute); this is why we can say "the finite field $GF(2^{163})$" even though there are many irreducible polynomials of degree $163$ over $GF(2)$. So the algebraic structure of an elliptic curve is not impacted by the actual field choice (of course, the curve is described with an equation $Y^2+XY=X^3+aX^2+b$ for two given constants $a$ and $b$, and those constants are represented with a given choice for the field; but using another field and applying the isomorphism on $a$ and $b$ yields another curve with the same structure). In practice, we use polynomials which promote implementation efficiency, i.e. polynomials with very low Hamming weight ($3$ if possible, $5$ otherwise), and where the non-zero coefficients are of the smallest possible degree (to make post-multiplication modular reduction easier).

For the Rijndael S-Box, things are not as simple. In the original Rijndael specification, there are some explanations on the design rationale, which were not copied into the final FIPS 197 standard. The S-Box is treated page 26; the use of an inverse in $GF(2^8)$ comes from a 1994 article by Nyberg, as providing good defense against differential cryptanalysis. To this inverse, Daemen and Rijmen added the so-called "affine mapping" which is meant to mask the algebraic structure of the said multiplicative inverse. All details are not given, so presumably they tried many polynomials (there are 30 irreducible polynomials of degree 8 over $GF(2)$, 16 of which being primitive) and many possible affine mappings, "measured" resistance to differential and linear cryptanalysis, and kept the best candidate.

Daemen and Rijmen published a book on the design of Rijndael (I have not read it).


How to construct a next bit predictor from a distinguisher I read the claim, without proof, that it is possible to construct a next bit predictor for any PRNG given an oracle distinguisher for that PRNG and vice versa. How do I prove that?

A distinguisher takes a bitstring and tells you if it was generated by the PRNG or not.
A next bit predictor takes a bitstring and tells you what the PRNG would output next.

My own idea for distinguisher to predictor is as follows: Let s be the bitstring generated so far by the PRNG. I will ask the distinguisher if s||1 or s||0 (s appended a 0 or 1) is a string generated by the PRNG. I will then take the one where the distinguisher says its coming from the PRNG.

My idea for predictor to distinguisher is: Take s without the last bit and predict the next bit for this. If it matches s came from the PRNG.

If the distinguisher/predictor is only right with some probability, the first case gets an unusable case where the distinguisher outputs the same thing for s||0 and s||1, but that won't always happen. The second case stays the same.

Can I prove the above claim in that way, i.e. is what I am saying correct?
Google doesn't really help here.

Your idea for constructing a distinguisher from a predictor is fine, assuming you know that the predictor predicts the last bit.  The more general statement is: if you can predict any bit of the output, say the $i$th bit, given the first $i-1$ bits, then you can also build a distinguisher.  A similar idea to what you showed also works to prove this statement.

For constructing a predictor, your idea doesn't work; we have to work a bit more.  The problem is you don't know which bit is predictable; it could be any of the bits.  Here's how we handle that.  We prove that if none of the bits is predictable, then there can be no distinguisher.  You prove this using a hybrid argument (do you know what that is?).  Then, take the contrapositive, and you get the result you wanted.


NACL with public key encryption and authentication As suggested in this answer i can use nacl for public key encryption with:

ephemeral_pk ‖ box( m, recipient_pk, ephemeral_sk,
           nonce=blake2b(ephemeral_pk ‖ recipient_pk))

But if i want also the sender to verify that it is him. Would the practice to use HMAC with preshared key or using a box as nonce be safe?

Something like:

ephemeral_pk ‖ box( m, recipient_pk, ephemeral_sk,
           nonce=HMAC(ephemeral_pk ‖ recipient_pk, hmac_key))

or like:

ephemeral_pk ‖ box( m, recipient_pk, ephemeral_sk,
           nonce=box(ephermal_pk ‖ recipient_pk,
           nonce=blake2b(ephemeral_pk ‖ recipient_pk),recipient_pk, sender_sk))

I was looking into the tweetnacl implementation. And there it appeared to me that the nonce length is 24 bytes. So i would have to truncate the nonces created with HMAC or box. Would this impact the overall security in an negative way?
The third possibility would be to sign the secret with sender_sign_sk and provide sender_sign_pk to the recipient.
From my trials i got the speed of the hmac solution to be on par with the normal hashing solution. The box solution is about 1.5 times slower and the solution with additional signing is about 3 times slower.

If I understand properly, you want to use ephemeral keys, and verify the identity of the sender.

A HMAC would not be enough to verify the identity of the sender, because the recipient is able to compute a valid authentication tag as well.

Signing the message before encrypting it solves this. Note that in that case, the message can simply be a random session key. So, for most applications, the cost is pretty low: signing is only required once, during key exchange. If this is acceptable for your application, this is probably the easiest route to go.

Otherwise, the Noise framework can be used to build secure key exchange protocols, according to what each participant knows about its peer. I would highly recommend using these patterns instead of inventing your own.

Do both the client and the server know about each other's public keys? The Noise KK pattern is likely to be the one you are interested in. Or if you have a single client, NNpsk0 is faster as it requires a single DH operation.


Does a Finite Field of 36 elements exist? I'm having a little trouble understanding the finite fields theory, so I'm sorry if my question would seem a little stupid.

I wanted to know if a finite field of 36 elements could exist.
Basically, I thought of the field $\mathbb{F}_{37}$, which has 37 elements. But does for example the invertibles of $\mathbb{F}_{37}$ form a field of 36 elements or not? Since all elements are invertible and we have 36 invertibles in $\mathbb{F}_{37}$.

Finite fields only exist for an order $q$ if $q$ is prime or a power of a prime (http://mathworld.wolfram.com/FiniteField.html). Since 36 is neither a prime itself, nor it is a power of a prime ($36 = 2^3 * 3^2$), there is no finite field with 36 elements.


How to identify RSASSA-PSS from rsaEncryption OID? Following the RFC 8446 it states that:

  RSASSA-PSS RSAE algorithms:  Indicates a signature algorithm using
        RSASSA-PSS [RFC8017] with mask generation function 1.  The digest
        used in the mask generation function and the digest being signed
        are both the corresponding hash algorithm as defined in [SHS].
        The length of the Salt MUST be equal to the length of the output
        of the digest algorithm.  If the public key is carried in an X.509
        certificate, it MUST use the rsaEncryption OID [RFC5280].

And from RFC 4055 it's stated that:

  The rsaEncryption object identifier continues to identify the subject
     public key when the RSA private key owner does not wish to limit the
     use of the public key exclusively to either RSASSA-PSS or RSAES-OAEP.
     In this case, the rsaEncryption object identifier MUST be used in the
     algorithm field within the subject public key information, and the
     parameters field MUST contain NULL.

It got me confused when trying to verify certificate signature, how can I know which algorithm was used if the OID is rsaEncryption and furthermore with what hash? (PSS or not)

Because the params field is NULL, and there's only the OID info, so from where can I derive the relevant information such as signature and hash algorithm with it?

There are two different identifiers in a certificate, the algorithm of the public key for the certificate and the algorithm of the signature from the issuer.  The two don't have to even be the same algorithm family (e.g. RSA CA certs can sign ECDSA certs, and vice versa).

In the following certificate parse structure the algorithm identifiers starting at offset 24 and 529 (certificate.tbsCertificate.signature and certificate.signatureAlgorithm) identify that the issuing authority signed the certificate with RSA PKCS#1 with SHA-1 (id-sha1WithRSAEncryption).

The algorithm identifier at offset 371 (certificate.tbsCertificate.subjectPublicKeyInfo.algorithm) identifies that the public key contained within this certificate is an RSA key (id-rsaEncryption).

If the issuing authority had signed the certificate using RSASSA-PSS then the certificate.signatureAlgorithm and certificate.tbcCertificate.signature values would have the RSA-PSS object identifier (1.2.840.113549.1.1.10) and their parameters would convey the PSS data.

$ openssl asn1parse -in rsa384.cer -i
    0:d=0  hl=4 l= 591 cons: SEQUENCE
    4:d=1  hl=4 l= 521 cons:  SEQUENCE
    8:d=2  hl=2 l=   3 cons:   cont [ 0 ]
   10:d=3  hl=2 l=   1 prim:    INTEGER           :02
   13:d=2  hl=2 l=   9 prim:   INTEGER           :C42D621149D3EE63
   24:d=2  hl=2 l=  13 cons:   SEQUENCE
   26:d=3  hl=2 l=   9 prim:    OBJECT            :sha1WithRSAEncryption
   37:d=3  hl=2 l=   0 prim:    NULL
   39:d=2  hl=3 l= 146 cons:   SEQUENCE
   42:d=3  hl=2 l=  11 cons:    SET
   44:d=4  hl=2 l=   9 cons:     SEQUENCE
   46:d=5  hl=2 l=   3 prim:      OBJECT            :countryName
   51:d=5  hl=2 l=   2 prim:      PRINTABLESTRING   :US
   55:d=3  hl=2 l=  19 cons:    SET
   57:d=4  hl=2 l=  17 cons:     SEQUENCE
   59:d=5  hl=2 l=   3 prim:      OBJECT            :stateOrProvinceName
   64:d=5  hl=2 l=  10 prim:      UTF8STRING        :Washington
   76:d=3  hl=2 l=  16 cons:    SET
   78:d=4  hl=2 l=  14 cons:     SEQUENCE
   80:d=5  hl=2 l=   3 prim:      OBJECT            :localityName
   85:d=5  hl=2 l=   7 prim:      UTF8STRING        :Redmond
   94:d=3  hl=2 l=  24 cons:    SET
   96:d=4  hl=2 l=  22 cons:     SEQUENCE
   98:d=5  hl=2 l=   3 prim:      OBJECT            :organizationName
  103:d=5  hl=2 l=  15 prim:      UTF8STRING        :Microsoft Corp.
  120:d=3  hl=2 l=  32 cons:    SET
  122:d=4  hl=2 l=  30 cons:     SEQUENCE
  124:d=5  hl=2 l=   3 prim:      OBJECT            :organizationalUnitName
  129:d=5  hl=2 l=  23 prim:      UTF8STRING        :.NET Framework (CoreFx)
  154:d=3  hl=2 l=  32 cons:    SET
  156:d=4  hl=2 l=  30 cons:     SEQUENCE
  158:d=5  hl=2 l=   3 prim:      OBJECT            :commonName
  163:d=5  hl=2 l=  23 prim:      UTF8STRING        :RSA 384-bit Certificate
  188:d=2  hl=2 l=  30 cons:   SEQUENCE
  190:d=3  hl=2 l=  13 prim:    UTCTIME           :160302165904Z
  205:d=3  hl=2 l=  13 prim:    UTCTIME           :160401165904Z
  220:d=2  hl=3 l= 146 cons:   SEQUENCE
  223:d=3  hl=2 l=  11 cons:    SET
  225:d=4  hl=2 l=   9 cons:     SEQUENCE
  227:d=5  hl=2 l=   3 prim:      OBJECT            :countryName
  232:d=5  hl=2 l=   2 prim:      PRINTABLESTRING   :US
  236:d=3  hl=2 l=  19 cons:    SET
  238:d=4  hl=2 l=  17 cons:     SEQUENCE
  240:d=5  hl=2 l=   3 prim:      OBJECT            :stateOrProvinceName
  245:d=5  hl=2 l=  10 prim:      UTF8STRING        :Washington
  257:d=3  hl=2 l=  16 cons:    SET
  259:d=4  hl=2 l=  14 cons:     SEQUENCE
  261:d=5  hl=2 l=   3 prim:      OBJECT            :localityName
  266:d=5  hl=2 l=   7 prim:      UTF8STRING        :Redmond
  275:d=3  hl=2 l=  24 cons:    SET
  277:d=4  hl=2 l=  22 cons:     SEQUENCE
  279:d=5  hl=2 l=   3 prim:      OBJECT            :organizationName
  284:d=5  hl=2 l=  15 prim:      UTF8STRING        :Microsoft Corp.
  301:d=3  hl=2 l=  32 cons:    SET
  303:d=4  hl=2 l=  30 cons:     SEQUENCE
  305:d=5  hl=2 l=   3 prim:      OBJECT            :organizationalUnitName
  310:d=5  hl=2 l=  23 prim:      UTF8STRING        :.NET Framework (CoreFx)
  335:d=3  hl=2 l=  32 cons:    SET
  337:d=4  hl=2 l=  30 cons:     SEQUENCE
  339:d=5  hl=2 l=   3 prim:      OBJECT            :commonName
  344:d=5  hl=2 l=  23 prim:      UTF8STRING        :RSA 384-bit Certificate
  369:d=2  hl=2 l=  76 cons:   SEQUENCE
  371:d=3  hl=2 l=  13 cons:    SEQUENCE
  373:d=4  hl=2 l=   9 prim:     OBJECT            :rsaEncryption
  384:d=4  hl=2 l=   0 prim:     NULL
  386:d=3  hl=2 l=  59 prim:    BIT STRING
  447:d=2  hl=2 l=  80 cons:   cont [ 3 ]
  449:d=3  hl=2 l=  78 cons:    SEQUENCE
  451:d=4  hl=2 l=  29 cons:     SEQUENCE
  453:d=5  hl=2 l=   3 prim:      OBJECT            :X509v3 Subject Key Identifier
  458:d=5  hl=2 l=  22 prim:      OCTET STRING      [HEX DUMP]:0414E451B61668BCEA124E09FE0A9E36B13865957515
  482:d=4  hl=2 l=  31 cons:     SEQUENCE
  484:d=5  hl=2 l=   3 prim:      OBJECT            :X509v3 Authority Key Identifier
  489:d=5  hl=2 l=  24 prim:      OCTET STRING      [HEX DUMP]:30168014E451B61668BCEA124E09FE0A9E36B13865957515
  515:d=4  hl=2 l=  12 cons:     SEQUENCE
  517:d=5  hl=2 l=   3 prim:      OBJECT            :X509v3 Basic Constraints
  522:d=5  hl=2 l=   5 prim:      OCTET STRING      [HEX DUMP]:30030101FF
  529:d=1  hl=2 l=  13 cons:  SEQUENCE
  531:d=2  hl=2 l=   9 prim:   OBJECT            :sha1WithRSAEncryption
  542:d=2  hl=2 l=   0 prim:   NULL
  544:d=1  hl=2 l=  49 prim:  BIT STRING


Can we map SHA-256 output bits to fixed-length input bits? If I have a set of $N$-byte input values to be hashed using SHA-256, then what are the mapping functions for each of the 256 bits of the output?

It seems to me that hashes are one-way partially because we don't know the input size, but if we did know the size to be $N$, then I expect to find a generalized mapping functions for each of the 256 output bits as functions of the $N$ input bits.

To be clear, I am not trying to find an input for a given output - I am happy for a mapping to still be a 1-way function.  Say, for 1000 bits of input, each output bit may be a function of all 1000 bits, or perhaps fewer, or perhaps with extra variables (S-box etc): ox = f(i0, i1,...1N, s0, s1,...) for the Xth output bit as a function of up to $N$ input bits and other variables.

In theory, should this be possible? If not, why not? If yes, what are some tips to learning all 256 mapping functions from the algorithm?

No this is not possible.

Basically SHA-2 consists of many rounds where the input is confused using irreversible functions. Each time such an irreversible function is called another variable is introduced. Furthermore these functions are not operating on a single input/output bit (of course) - they are dependent on all the input bits due to the inherent transposition.

So the reverse function will consist of many many variables, that cannot be simplified to a function without one. Any SAT solver will happily break its teeth on it. And that's why you cannot just create a generalized mapping function.

For attacks usually a reduced number of rounds are used, trying to expand them to the full hash later. And if your input $N$ is small enough then you could simply use brute force or an attack using a rainbow table... but that's about it.


Triple DES with 2 keys Suppose triple DES is performed by choosing two keys $K_1$ and $K_2$ and computing $C = T (T (T (L, K_1), K_2), K_2)$. How to attack this modified version with a meet-in-the-middle attack, in which the attacker knows at least one $(L,C)$ pair?

This illustrates the importance of getting the key order right with 3DES two-key keying option. With the correct order of $k_1$, $k_2$, $k_1$ you get something that should be impossible to attack with current resources, while with the incorrect order in the question it is feasible to attack.

The outer two encryption layers can be joined into a single cipher, which we may call DES2. That is a 64-bit block cipher with a 56-bit key, just like DES. It is approximately twice as expensive to compute.

The question then becomes the simple case of applying the meet-in-the-middle attack to double encryption. The inner cipher is DES, the outer DES2. The fastest option is to build the table for the inner encryption encryption in $2^{56}$ DES calls, since you then only need to compute the outer cipher $2^{55}$ times on average (i.e. $2^{56}$ DES calls).

You need memory for a $2^{56}$ item table, unless you apply a time-memory tradeoff. It would be expensive but on the verge of doable even with this brute force approach. You may also be able to get away with a factor of 2 or so fewer calls by making use of related keys. Other improvements are likely possible.