Proof that a particular algorithm has been used I’m looking for the existence (or the proof of non-existance) of a method to prove (with arbitrary certainty) that a particular output is the result of a particular algorithm applied on a particular input.
$$ f(x) = y $$
How can I prove the above equation holds by knowing all of its constituents but without actually applying the function?
This would be akin to a zero knowledge proof but could be easily used in blockchains to embed AI algorithms.
Given some constraints on the inputs (correlated) or the algorithms (linear) do you know of any such method?

I’m looking for the existence (or the proof of non-existance) of a
method to prove (with arbitrary certainty) that a particular output is
the result of a particular algorithm applied on a particular input.

If by "a particular algorithm" you mean "any algorithm whatsoever", then definitely no such method exists, because before you could establish if an algorithm gave a particular output for a particular input, you'd first have to establish whether the algorithm even halts on that particular input, and the halting problem is well-known to be undecidable. Note that even removing the restriction on not actually running the algorithm wouldn't let you escape from this.
If by "a particular algorithm" you mean "a specific algorithm that I'm thinking of right now" then in general, as was discussed in the comments, if you have a single input and a single output, an infinite number of different algorithms which produce that specific output from that specific input can be constructed, so it's impossible to distinguish between them solely by inspecting those two values.
If, on the other hand, you just want to test whether a given algorithm would have given a particular output for a given input, regardless of whether some different function might also have given the same output, then there are at least some relevant cases where it's not - or shouldn't be - possible. For example, any block cipher should output ciphertext that doesn't leak any usable information about either the key or the plaintext. Even if you have the key and the plaintext, if you can tell a given ciphertext would be produced by them without actually running the encryption (or decryption) function then that function is broken.
In general, if you have all the inputs, all the outputs, and full knowledge of the algorithm, then it's not clear what "zero knowledge proof" would mean here, since you evidently possess all the knowledge you'd need to run the algorithm yourself. There is the concept of a certificate value which can be a proof of an expensive algorithm - for example, you can prove you solved a given discrete logarithm by simply supplying the right exponent, so anybody can easily verify it without going to the trouble of solving it themselves - but this is completely dependent on the algorithm in question.


Why the LM-OTS signature is so long? I refer to the LM-OTS specification in RFC8554.
It seems that
after having hashed all the chains, including the checksum’s ones, the signature is essentially the concatenation of the hash results.
Apparently one can make the signature much shorter, by hashing the above again.
Boneh and Shoup define Winternitz signatures in this way. Why the RFC doesn't?

Apparently one can make the signature much shorter, by hashing the above again. Boneh and Shoup define Winternitz signatures in this way

No, Bohen and Shoup do not; their Winternitz signature is a concatination of the hashes.  This can be seen as the output of their $S(sk, m)$ algorithm on page 591 of version 0.5 of their book - the signature they generate is $(\sigma_1, ..., \sigma_n)$, that is, the concatination of the intermediate hashes $\sigma_1, ..., \sigma_n$
If you do generate a signature which is the hash of the intermediate hashes, it is not clear how the verification process is supposed to work.  The procedure that Boneh and Shoup propose (which is what LM-OTS does) starts with the intermediate hashes $\sigma_1, ..., \sigma_n$, and follow the hash chains upwards to the tops of the Winternitz chains $y_1, ..., y_n$.  It is not clear how one can rederive $y_1, ..., y_n$ given only $H(\sigma_1, ..., \sigma_n)$
Now, the public key they use is, in fact, the hash of all the tops of the chains $H( y_1, ..., y_n)$, and hence the public key is short.  LM-OTS also follows this.


If RSA is only used to encrypt symmetric keys which are random, what's wrong with textbook RSA? IND-CPA is used to protect against frequency analysis AFAICT. But if RSA is only used to encrypt symmetric keys (AFAICT) then what's wrong with using only textbook RSA because random keys are very unlikely to repeat?

This is a common mistake, so I'd like to give an in-depth answer. Basically, what you are proposing is to rely on the ONE-WAYNESS of RSA as a ONE-WAY FUNCTION, rather than relying on its CPA or CCA security as an encryption scheme. The advantage of using RSA as a one-way function is that no padding etc is needed.

Now, the first important thing to note is that the RSA assumption states that RSA is hard to invert when given a random element in the ring. So, if you choose a random value $x$ between $0$ and $N-1$ and then compute $x^e \bmod N$, then according to the RSA assumption it will be hard to find $x$. However, this doesn't mean that it's hard to find some of $x$ (and knowing some of the key is disastrous), and it also doesn't mean that it's hard to invert RSA when $x$ is not a random element between $0$ and $N-1$. For example, what happens if $x$ is a random 128-bit string (converted to a big number)?

The good news is that we actually do have a (partial) answer for this. First, consider the case of $e=3$. In this (quite common) case, if $N$ is 2048 bits long then for any string $x$ of length at most 682 bits, it is trivial to invert and find $x$ when given $y=x^e \bmod N$. This is due to the fact that when $e=3$, the length of $x^e$ is 3 times the length of $x$. If the length of $x$ is less than 682 bits then the length of $x^e$ is less than 2048, and so $x^e \bmod N$ equals $x^e$ over the integers (this is because no modular reduction ever takes place). Note that finding a cube root over the integers is easy (just do a "binary search" over the possibilities). I stress that the conclusion from this is not to use a larger $e$; the conclusion is not to do plain RSA.

However, since people are often not yet convinced by this, there is another attack that works for any $e$, including large values. In this attack, when the input $x$ is of length 128 bits, it is possible to find $x$ in about $2^{64}$ time, given $x^e \bmod N$. In general, it is possible to invert RSA in time that is square-root of the string length of the input. So, this is not secure. Now, you may want to say: OK, so I'll use a 256-bit key! However, note that instead of having 256-bit security you'll have 128-bit security. More importantly, this attack that takes square-root time is an indication that this is a really bad idea. So, don't do it! (References for the attack: the basic attack on plain RSA appears in this paper by Dan Boneh et al. (Why Textbook ElGamal and RSA are Insecure), and removing the space requirement in that paper can be achieved using the technique in this paper by Oorschot and Wiener (Parallel Collision Search with Cryptanalytic Applications.)

This leads to another possibility which is to choose a random $x$ between $0$ and $N-1$ and to compute $x^e \bmod N$. Then, using a hash function $H$, derive a key $k=H(x)$ to use for symmetric encryption. In the random oracle model (with $H$ being a random oracle) this is actually secure, and will even be CCA-secure if the symmetric scheme is CCA secure (this is actually a CCA-secure KEM/DEM scheme; see the next paragraph for more on this). However, without a random oracle we have no idea how to prove this secure.

In general, we know that in order to get a CPA-secure hybrid encryption scheme, we need both the asymmetric and symmetric scheme to be CPA secure; likewise for CCA security. However, there are more efficient ways of working, which is the KEM/DEM paradigm. This is more relaxed than hybrid encryption, since the asymmetric part defines a random key for the symmetric encryption, but it's not necessarily in the hands of the encryptor to determine what the key will be. I will leave you to look up the KEM/DEM paradigm if you are not familiar with it.


How to find 64 collisions for a hash value? The first block $M_0$ is one of 64 possible values, whereas the next six blocks $M_1...M_6$ are chosen randomly. The idea is to publish the SHA-1 hash of $M_0...M_6$, wait for the value of $M_0$ to be announced, and then release the original message $M_0...M_6$ - so as to prove that we can predict $M_0$ beforehand.

But now we want to fake our prediction: that is, publish a certain hash $H$, and then once $M_0$ is revealed, we publish $M_0...M_6$ such that $M_0$ is correct and it hashes to $H$.

I'm not sure if my attack should leverage properties that are specific to SHA-1: it seems unlikely that it should. But I'm lost as to how I can choose 64 different sets of 6 random blocks that hash to the same value (when concatenated with one of $M_0$'s 64 values).

Edit: I forgot to mention that the algorithm used can be probabilistic, and it should work with at least $50\%$ probability.

As far as I understand, you are trying to find $M_1...M_6$ so that $H(M_0||M_1||...||M_6) = h$ for any of 64 preset values of $M_0$. This implies a collision attack on $H$, which in the case of SHA-1 has not yet been accomplished in practice (though it is probably close).

Specifically, you would need a chosen prefix collision. We have such attacks for MD5 (see e.g. the links from this answer), assuming you have enough freedom in the size/choice of $M_i$. However, there is still a ways to go before it could be accomplished for SHA-1.


Is there a way to use bcrypt with passwords longer than 72 bytes securely? From my understanding BCrypt truncates the password to 72 bytes. If a password is longer than 72 bytes, what is a way to store that password using bcrypt securely without compromising it? Or is this incorrect and we should just let bcrypt truncate it?

The reason why I ask is that I've seen some implementations where they SHA-256 the password first then enter it into BCrypt (e.g. PassLib bcrypt_sha256). However the SHA-256 output is a 32 byte digest. If the original password before the SHA-256 was longer than 32 bytes doesn't hashing it with SHA-256 compromise bcrypt by shortening it to 32 bytes?

If that is the case with SHA-256 would SHA-512 be a more secure option with 64 bytes?

I've seen in some places like Wikipedia and SE Cryptography where they say 56 bytes is the max password byte length. What password byte length is optimal for bcrypt passwords if it isn't 72 bytes?

If that is the case, then with passwords less than the optimal byte length is it better to hash them to a longer byte length?

Introduction

BCrypt is a password-based KDF (far from state-of-the-art, but better than PBKDF2, because BCrypt requires sizable RAM, which greatly increases the cost of hardware-accelerated password search).

Bcrypt is based on the block cipher Blowfish, with the initial processing of the password reminiscent of Blowfish's key preprocessing. Bruce Schneier's Description of a new variable-length key, 64-bit block cipher (Blowfish) (in the proceedings of the first FSE conference, held Dec. 1993) defines that Blowfish's key is of 4 to 56 bytes (32 to 448 bits), with this rationale for the maximum:

  The 448 limit on the key size ensures that the every bit of every subkey depends on every bit of the key. (Note that every bit of $P_{15}$, $P_{16}$, $P_{17}$, and $P_{18}$ does not affect every bit of the ciphertext, and that any S-box entry only has a $.06$ probability of affecting any single ciphertext block.)

Using more than 56 bytes of key for Blowfish is against its definition and design rationale: key bytes beyond the 72nd have no effect whatsoever, and the few before may have somewhat less diffusion (though not nearly as badly as the above quote suggests). Some Blowfish implementations nevertheless accept keys with any positive number of bytes.

Bcrypt, as defined in Niels Provos and David Mazières's A Future-Adaptable Password Scheme (in proceedings of Usenix 1999) accepts a key of 1 to 72 bytes; even with the lowest cost parameter, all key bytes have ample time to reach full diffusion. Bytes beyond the 72nd (if any) have no effect whatsoever. The mapping of password to key is "defined" by:

  take user-chosen passwords as keys

and implementations are known to vary wildly. ASCII only? Some 8-bit codepage extension? Replacement of gremlins with 0x3F bytes? Little-endian or Big-endian UTF16 or UTF32? UTF8, with or without BOM? Length byte, zero-termination? Your guess!

What should be done if the password can be more than 72 bytes?

If there was a formal requirement that it is impossible to exhibit equivalent passwords, or that every character in a password is significant, or with UTF32-encoded passwords (thus only 18 characters), it would be bad to just truncate a password/passphrase to 72 bytes.

The option of replacing Bcrypt's mapping of password to key by a cryptographically secure hash is excellent, if all the characters in the password make it to the input of the hash, and all the bytes in the hash's output make it to the key (I can imagine an implementation where bytes beyond the leftmost 0x00 in the hash, if any, are just ignored; that would be extremely bad, for one in 256 passwords could be replaced by any password with the first byte of its hash equal to 0x00).

The hash should be computationally collision-resistant to a degree significantly better than the strength of the requirement that it is impossible to exhibit equivalent passwords (thus with output of $h$ bits with $h$ significantly above $2k$ if aiming at $k$-bit security level, and unbroken from a collision-resistance standpoint; no MD5, or even SHA-1 from a theoretical standpoint). The strength of all other properties (minimum expected cost for password search by brute force, first and second preimage resistance, resistance to length-extension, and more generally computational indistinguishibility from a random oracle) demonstrably follow from Bcrypt's security.

If there is an entropy of $e$ bits in the input password, and for a hash of $h$ bits indistinguishible from a random oracle, it is expected that there are about $\max(e,h)$ bits of entropy in the key fed to Bcrypt, nearly exactly when $e\ll h$ or $e\gg h$, and within less than about $0.83$ bits in the worst case $e=h$ (see this).

SHA-256 (32 bytes) is thus perfectly fine in practice for any password/passphrase that a human types in (or even more so, memorizes); SHA-512 (64 bytes) can't harm. Ample entropy remains if there was enough in the first place.


RSA: Derive modulus from known ciphertexts encoded with same keypairs I have two ciphertexts

$c_1 = m_1^e \bmod n$

$c_2 = m_2^e \bmod n$

I know $c_1, c_2, m_1, m_2$ and $e$. Is there a way to derive n from this? I first thought Franklin Reiter but I'd need an $n$ for that which is precisely what I am missing. What other approaches are there?

Here is the hint you requested:

We know that we have $m_1^e - c_1 = k_1n$ for some integer $k_1$
We know that we have $m_2^e - c_2 = k_2n$ for some integer $k_2$

So, given that we know the values $k_1n$ and $k_2n$, how can we recover the common $n$ value?  Hint: look at the $\gcd$ function...


AES - CCM, why not use CMAC inside instead of CBC-MAC? I was reading up on AES-CMAC when I learned that this basically is an improved and more robust version of CBC-MAC, with the ability to safely have variable-length messages.

Difference between CBC-MAC and CMAC

The AES-CCM uses AES in counter-mode, and thus turns AES it into a stream cipher. It therefore needs message authentication at the end to ensure message integrity as far as I have understood. Here it uses CBC-MAC. But if CMAC is more robust, why not just use this one?

I am working with Bluetooth Low Energy, and this algorithm is the backbone in the encryption of LE Secure Connections.

Grateful for any clarification.

AES - CCM, why not use CMAC inside instead of CBC-MAC?

So in their original suggestion of the mode for 802.11i (for WPA2) the only reason given by Whiting, Housley and Fergueson is:

  A combination of counter mode  encryption  and  CBC-MAC authentication is proposed here. These modes have been used and studied for a long  time,  with  well-understood  cryptographic  properties,  and  no  known  patent  encumbrances.  They  provide  for  good security and performance, whether implemented in hardware or software.

So they probably were mostly looking for a mode that satisfied their specific needs at the time (no patents, reasonably fast and cheap, with security proof) and so they came up with this relatively simple construction.

Furthermore, "CMAC" is actually OMAC1 (first definition (PDF) from 2003) which is based upon OMAC(2) (from december 2002) which is based upon XCBC (from 2000, PDF) which is based upon CBC-MAC.
So as the CCM specification is from January 2002, it obviously couldn't make use of OMAC / CMAC. Furthermore XCBC was known at the time, but had the problem of requiring 3 keys which would have bumped the key size for CCM from 128 bit for AES-128 to at least 384 bit, probably an undesirable result.

  But if CMAC is more robust, why not just use this one?

So I looked through the specification and CMAC actually isn't more robust. CBC-MAC by itself is a prefix-free PRF (and thereby a MAC). So if you don't allow sequences of message blocks to be prefixes of each other you get a secure MAC.

The way this weakness is overcome in CCM is that the length of the message is encoded into the first input block to CBC-MAC so no two messages of different length can be prefixes to each other because the initial block will always differ.
The way CMAC overcomes this is by XORing a constant secret into the last input block, so that an adversary doesn't actually know the complete input to CMAC and thereby can't find any prefixes without guessing the secret key-dependent constant.

So as you can see, security-wise both CCM's CBC-MAC and CMAC are rather equivalent in their properties. The only downside is that with CCM you need to know the message length in advance which sometimes is inconvenient.

Bonus: I actually think the prepending of the message length is unncessary for CCM. This is because CCM already needs a nonce-respecting adversary for security (or else the CTR component breaks horribly), so it's guaranteed that the first block is different for each CBC-MAC invocation and thereby no two inputs can be prefixes of each other.

Also note that the more popular GCM breaks at least as badly as this CCM variant since it leaks the secret authentication key in that case...


Luby-Rackoff theorem confusion The Luby-Rackoff theorem states that if a round function is a secure pseudorandom function (PRF)
then 3 rounds are sufficient to make the block cipher a pseudorandom permutation (PRP).

PRPs are invertible whereas PRFs are not. How come 3 rounds of a PRF
will make an invertible block cipher out of a non-invertible function?

The proof is loosely as below.

Lets assume a one round Feistel network, where $2n$ bits are divided into $n$ bits each $L_0, R_0$

The encryption is defined as

$L_{1} = R_{0}, \\ R_{1} = L_0 \oplus f(R_0) $

where f is any random function (PRF) and $\oplus$ is XOR operation

Now the cipher text is $L_{2} = R_{1}, R_{2} = L_1 $

Decryption is same as encryption circuit as defined above.

The input to decryption is $L_2, R_2$.

So decryption is defined as below

$ L_{3} = R_{2} \\ R_{3} = L_{2} \oplus f(R_2) $

Where the plain text should be considered $R_3, L_3$

Now lets substitute from
$ L_{3} = L_{1}, \\ R_{3} = R_{1} \oplus f(L_1) $

Now lets substitute further to get the plain text is $R_3, L_3$ which is $L_0, R_0$ as shown below
$ L_{3} = R_{0}, \\
 R_{3} = L_0 \oplus f(R_0) \oplus f(R_{0}) ,\\
 R_{3} = L_0 $

So it does not really matter if $f(R_0)$ is reversible or not. And the same holds good for any number of rounds.

There is also an intuitive explanation here


Using the Unix epoch as nonce Since a nonce must be unique and that time only goes forward, is it safe to use the Unix epoch as nonce ?

My use case is be AES w/ GCM which recommends a nonce length of 12B. Current Unix time can be represented using 4B, so that leaves the upper 8B free for future timestamps (plenty of space).

One possible security implication is the forgery of NTP replies, which would cause the client to use a Unix timestamp in the past (i.e. breaks the stream cipher). Secure channels should prevent this from happening, but a bad operator could always force bad NTP replies.

Using a Unix Timestamp as the sole source for the nonce would make me nervous.

In addition to forged NTP replies (and legitimate operators deliberately resetting the clock for some reason, and I'm not sure whether leap seconds would pose a risk), you also would need to worry about "what if I send two messages within the same second"

On the other hand, you have 12 bytes to play with; if you use four of the bytes to hold the Unix timestamp, and use another four as a counter (which you increment every time you send a message), and the other four as something else, that'd be a system which would be more resilient against nonce repeats.


Brute force attack on DES + property of DES In a brute force attack on DES, it seems to me that one plaintext-ciphertext pair suffices to launch the attack. (I.e. suppose we are given a message $x$ and a ciphertext $c$ such that $DES_k ( x ) = c$, where the $56$-bit key $k$ is unknown. Then going through all $2^{56}$ keys will eventually give the result.) I am, however, unsure about this, as in Katz/Lindell's book Introduction to Modern Cryptography on page 179 (line -9) they seem to suggest that "these attacks require a large number of input/output pairs...". This sentence thus confuses me, as to me it seems that one pair suffices.
Related to the first point, is the following statement true?

Statement. For all messages $x$ and all keys $k_1, k_2$, if $DES_{k_1} ( x ) = DES_{k_2} (x)$ then $k_1 = k_2$.

I'm not sure if it holds. Have been thinking about it for a while.
In Katz/Lindell they say that an exhaustive key search happens "in time $2^{56}$". I do not completely understand this statement. I do understand that there are $2^{56}$ keys in total. So, in the worse case scenario, it will take $2^{56}-1$ "steps" (i.e. DES-applications). So if they speak about "time", do they always mean worse-case scenario-time?

However, the expected value (of the needed "time") seems to me to be $2^{56} / 2 = 2^{55}$. Is this correct?

You are right that a brute force attack on DES requires a single plaintext/ciphertext pair; another plaintext/ciphertext pair is useful to confirm the result once found (and rule out a false positive).

No, $DES_{k_1}(x) = DES_{k_2}(x)$ does not imply $k_1=k_2$; the same holds with high probability for any ideal cipher with the same parameters as DES, modeled as a key-dependent family of random permutation (explicitly finding a counterexample requires significant work, but still much less work than a brute-force key search: that's essentially a collision search, memory or/and cycle-finding can help; in fact that is an interesting hands-on computer project).

DES key search with a single plaintext/ciphertext using a black-box DES implementation requires $2^{56}$ invocations at worse (we discount the "optimization" of concluding after $2^{56}-1$ keys did not match that the single remaining one must be right, which is unrealistic, and saves only $2^{-56}$ of the effort with odds $2^{-56}$). That is "in time $2^{56}$" (the default assumption is a sequential attacker). There will be $2^{55}$ invocations on average (the expected time/effort). Chance/risk (depending on point of view by attacker/user) that the key is found after only $2^t$ tests is $2^{t-56}$ for $t\le56$ using sequential key search, or $t\ll56$ using random key search.

Notice that if one has two pairs $(x,E_k(x))$ and $(\overline x,E_k(\overline x))$, the DES complementation property gives $E_k(\overline x)=\overline{E_\overline k(x)}$ and allows to half the work, for we can test $k$ and $\overline k$ in a single operation. Also notice that in a computer program (rather than a black box) we can change the keys in a manner such that a little of the work with earlier keys is reusable, saving some time; and more generally test $t$ keys with appreciably less work than what's required for $t$ encryptions with arbitrary different keys.

The DESCHALL project and EFF DES Cracker have been historical demonstrations that the DES key space of $2^{56}$ was too small even for civilian application in 1998.


What would currently make the strongest https connection? when you look at the encryption websites use you will see that there is alot of diversity, some use 256 bit keys some do not, some use DHE-RSA some ECDHE some use sha 256 some sha1, but my question is, what would currently make the strongest https connection in terms of asymmetric  symmetric and hashing algorithms used.(I do understand that there might not really be an overall "strongest" one and that some schemes a better in different situations)

The cipher suite with the best theoretical security for TLS (v1.2) right now is clearly:

TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA384 with P-521
as the associated curve for the certificate and the key-exchange.
The arguments are simple:

ECDHE and ECDSA with P-521 both provide 256-bit security against forgery / key recovery attacks
AES-256 is the strongest possible AES instance you can get
CBC is the most resilient mode to IV-reuse (you only learn whether two messages share a common prefix)
SHA-384 implies use of HMAC-SHA-384 as the MAC which has a much higher "bit-length-protection" against forgeries than, say GCM

The arguments against it are clear as well:

The support situation is probably horrible, because P-521 isn't exactly the most wide-spread supported curve as is probably the ECDSA-CBC-SHA2 combination
This suite is prone to many (side-channel / padding oracle) attacks on CBC and authenticate-then-encrypt from the past

Note well: Because of these attacks I strongly recommend against using any CBC based cipher suite.

The cipher suite with the best practical security (and somewhat decent support) for TLS (v1.2) right now is clearly:

TLS_ECDHE_ECDSA_WITH_AES_256_GCM_SHA384 with P-384
Downgrade to TLS_ECDHE_WITH_AES_128_GCM_SHA256 with P-256 / P-384 for more supported systems (such as Firefox)

ECDHE and ECDSA with P-384 both provide 192-bit security against forgery / key recovery attacks, which is on the edge of "physically infeasible" and will likely remain unbroken until the rise of quantum computers, the support is really good here, because P-384 is part of NSA's Suite B and many people implemented it because of that
AES-256 is the strongest possible AES instance you can get
GCM is the mode which has seen the least amount of attacks, as predicable IVs are a non-issue and padding doesn't need to take place and authentication is built-in
GCM "only" provides 128-bit forgery security, but this is (a worthy / the) trade-off for a much better side-channel resistance


Let $ALG_2$ be an algorithm that solves the RSA problem, can it solve the generalized Diffie-Hellman problem? Let $ALG_2$ be an algorithm that solves the RSA problem for all $e\in \mathbb{Z}_n^*$ i.e given $e,m^e,n$ then $ALG_2(e,m^e,n)=m$. Is it possible to use this algorithm to solve the generalized Diffie-Hellman problem?

By generalized Diffie-Hellman I mean that we choose $n=pq$ where $p,q$ are both primes (found something else online so wasn't sure if everyone will understand).

So at start, I thought it can but couldn't prove that. So I just thought maybe it can't because what it actually does is get 2 numbers- $e$ and $m^e$- and calculate root $e$ of $m^e$ i.e $m$. But at Diffie-Hellman we don't know anything about the ratios between $r_a,r_b$ or even $g^{r_a},g^{r_b}$ and all we know is $g,g^{r_a},g^{r_b},n$. The only thing I can think of is find $r_a$ and $r_b$ by guessing numbers and using $g$ but it doesn't use $ALG_2$.

Anyone got any ideas?

Suppose you had an algorithm $\operatorname{DL}(n, g, h)$ that, with probability $p$, successfully yields $x$ such that $h \equiv g^x \pmod n$.

Then you could define $\operatorname{FACTOR}(n)$ as follows:

Pick $g$ and $h$ uniformly at random.
Compute $x = \operatorname{DL}(n, g^2, h^2)$.

If successful, $h^2 \equiv (g^2)^x \equiv (g^x)^2 \pmod n$; hence $$n \mid (g^x)^2 - h^2 = (g^x + h) (g^x - h).$$

Fail if $g^x \equiv \pm h \pmod n$.

If not, then each of $p$ or $q$ must divide $g^x \pm h$ but not both.

Compute $\gcd(g^x \pm h, n)$.

This succeeds with about probability $p/2$—every quadratic residue $h^2$ has exactly four square roots modulo $n$, so there's only a 1/2 chance that $g^x$ is $\pm h$—and a handful of arithmetic.

Nobody has found a way to factor $n$ given an oracle to solve the RSA problem modulo $n$, so this suggests you're not likely to find a way to implement $\operatorname{DL}(n, g, h)$ in terms of your $\operatorname{ALG_2}(e, c, n)$ RSA oracle.  If you did, the editors of many reputable cryptography journals and conferences would like to hear from you!

This reduction breaks down if your DL algorithm works only for quadratic nonresidues.  On the other hand, if you it worked only for quadratic nonresidues, then you could probably use that to (somewhat inefficiently) solve the quadratic residuosity problem, and that might be publicationworthy in reputable cryptography journals; as far as I know nobody has found a reduction of RSA to QR or vice versa.


Reason(s) for using a KDF for encryption keys Assuming I already have a 256-key (32 char password) for AES encryption, comprised of random alpha-numeric characters and punctuation (95 possible ascii chars), generated by a decent PRNG, is there any reason to use a KDF to convert this into another key of the same length?  Is a derivative hash in some way stronger?

Obviously if a password was shorter than the intended key-length, or if the password was predictable (ie, memorizable), I can see how a KDF would be useful. But given the above circumstances, I reason that a KDF (like BCrypt of PBKDF2) would actually reduce the character-range of the key (to 64 chars in bcrypt, and 16 chars in PBKDF2), effectively increasing the chance of a brute-force attack (however unlikely).  Any insights?

The point of a KDF is to take a low-entropy input and significantly increase the amount of computational power (and thus time or cost) it requires to brute-force, hopefully to a level on-par with a truly random value.

If you're already using a 256-bit value generated from a CSPRNG, there is no need to use a KDF.

In fact, using a KDF can only reduce the security of your keys. If there are any collisions in your hash function for 256-bit inputs, the number of possible KDF-generated keys will be fewer than the number of inputs, and you have a smaller possible keyspace. On the other hand, it can't possibly increase security, because if you're using a KDF to expensively turn 256-bit keys into different 256-bit keys, attackers have no need to go through the KDF. They can just enumerate the 256-bit keyspace in the first place.


Why do digital signatures use a hash algorithm instead of a checksum? Based on my knowledge, all digital signature algorithms use a hash function to sign a message, and then encrypt the hash result. So why do these algorithms not use a checksum instead of a hash algorithm? By the end, both are going to encrypted, correct?
A checksum is faster than a hash algorithm.

A digital signature can only sign a relatively small amount of information, which is why the digest is signed instead of the original message. Because of this limitation, the digest must be a faithful representation of the complete message. A cryptographically-secure hash is require to resist collision attacks, second preimage attacks, and preimage attacks, all of which can invalidate the guarantees that people expect from a digital signature. In other words, if one signature is valid for two distinct messages, the signature is useless. A cryptographically-secure hash prevents this.

Also note that digital signatures are not simply encrypted digests. This is a simplified explanation which is common, but technically incorrect. This answer describes signatures for RSA.


Encrypt-then-MAC Confidentiality, Integrity and Authenticity Does Encrypt-then-MAC provide equal confidentiality, integrity and authenticity as other constructs such as EAX?
If yes, how do I go about using it?

My current understanding is:

E = encrypt(plaintext)
H = hash(E)
output(H || E)

Is that correct?

Encrypt-then-MAC has been standardized in ISO/IEC 19772:2009 hence it is safe to assume all the properties that you mentioned.

To the best of my knowledge, the best way to perform EtM is:

E = ENCRYPT(PLAINTEXT)

  I am assuming that you are using a block cipher such as AES and
  appending the encryption IV or nonce to the start of E unless of course you are using ECB.

M = HMAC(E)

  HMAC also takes a key which must be different from your encryption
  key. There are of course other MACs, but I recommend HMAC since it removes the complexity of MAC IVs.

OUTPUT E, M


Use R-CTR (randomized counter mode) to compute MAC I've read that in conjunction with CBC-MAC, R-CTR (randomized counter mode) can be used to compute a MAC, but why wouldn't you just use a block cipher in R-CTR on its own to compute a MAC?

I'll assume that R-CTR is CTR with a random IV or nonce.

Counter mode cannot be used to compute a MAC for the simple reason that the ciphertext of any part of the plaintext does not depend on any other part of the plaintext.

With CBC the ciphertext over the previous block is used as input (vector) for the next block encryption; it is XOR-ed with the next block of plaintext before it is encrypted. This means that the last block of ciphertext depends on all previous blocks. This makes it possible to create MACs such as CBC-MAC and the more secure CMAC out of CBC mode encryption.

Counter mode first creates a key stream which is then directly XOR'ed with the plaintext to produce the ciphertext. This means that each and every bit of plaintext is encrypted completely independently of any other bit of plaintext. So in the end you're just as far as you were before.

I cannot explain how you could combine CBC-MAC and R-CTR to create a MAC without seeing the definition of this scheme. In principle you'd just need CBC-MAC or course, even if that requires that the length can be determined in advance.


Reciprocal block ciphers I'm interested in the property of involution in block ciphers and how one would go about constructing one. Creating a cipher where $E_K(E_K(M))=M$ for any $M$ and $K$ isn't an obvious task and the use of round keys makes it seem like this is an impossible task without undermining the security of the thing. What is my best approach for constructing a reciprocal block cipher? How do Anubis and Khazad do it?

Anubis (128-bit block) and Khazad (64-bit block) work by using involutional components in sequence. The complete ciphers are not fully involutional, as the key schedules and round constants prevent that from occurring. Decryption requires a different key schedule, but all other operations remain the same. They are SP-network ciphers, which are generally not involutional.

Feistel ciphers also use the same core components for encrypt and decrypt, but work differently, in that they generally do not use components that are involutions. As orlp pointed out, changing the key schedule can make a Feistel cipher into a full involution.

The advantage to involutional components is code reuse; you have a single encrypt/decrypt operation, and most parts of the key scheduling algorithms. It may also be easier to analyze the algorithm. The disadvantage is the components may be suboptimal, which means it usually will require more rounds to provide the same level of non-linearity and diffusion when compared to say, the AES candidates.

For the diffusion component (P) of the cipher, a Cauchy matrix is the go-to operation, since it provides a high branch diffusion, is an involution, and is simple to implement in reference and table-lookup designs. Large matrices can be implemented to provide full diffusion in a single round, but are slow outside of a table-lookup implementation. Khazad uses a large 8x8 matrix operating on the whole 64-bit block, whereas Anubis uses a 4x4 matrix like AES multiple times.

Here is the 8x8 MDS diffusion matrix for Khazad:

\begin{bmatrix}
01_x~~ 03_x~~ 04_x~~ 05_x~~ 06_x~~ 08_x~~ 0B_x~~ 07_x \\
03_x~~ 01_x~~ 05_x~~ 04_x~~ 08_x~~ 06_x~~ 07_x~~ 0B_x \\
04_x~~ 05_x~~ 01_x~~ 03_x~~ 0B_x~~ 07_x~~ 06_x~~ 08_x \\
05_x~~ 04_x~~ 03_x~~ 01_x~~ 07_x~~ 0B_x~~ 08_x~~ 06_x \\
06_x~~ 08_x~~ 0B_x~~ 07_x~~ 01_x~~ 03_x~~ 04_x~~ 05_x \\
08_x~~ 06_x~~ 07_x~~ 0B_x~~ 03_x~~ 01_x~~ 05_x~~ 04_x \\
0B_x~~ 07_x~~ 06_x~~ 08_x~~ 04_x~~ 05_x~~ 01_x~~ 03_x \\
07_x~~ 0B_x~~ 08_x~~ 06_x~~ 05_x~~ 04_x~~ 03_x~~ 01_x \\
 \end{bmatrix}

As you can, see, all 4x4 diagonal corners of the matrix are same, all 2x2 diagonal corners of those matrices are the same, and all 1x1 diagonal corners of those matrices are the same. That is the property that makes the Cauchy matrix an involution. The matrix can be built at runtime from a single row and a recursive algorithm.

For the substitution component (S) of the cipher, using an involutional s-box is not optimal. Even the best involutional s-boxes have inferior properties when compared to modern block ciphers. Anubis and Khazad use the same s-box, here is a comparison to some of its primary properties against the AES s-box:

                          AES       Anubis/Khazad
Nonlinearity:             112       96             higher is better
Differential Uniformity:  4         8              lower is better
Autocorrelation:          32        104            lower is better
Sum of Squares Indicator: 133120    270208         lower is better

AVAL Relative Error:      3.52%     11.72%         lower is better
Bit Independence Rel Err: 13.4%     27.6%          lower is better
SAC Relative Error:       12.5%     34.4%          lower is better
Distance to SAC:          432       620            lower is better

These suboptimal s-box properties are the main reason that Anubis requires more rounds than AES for the same key size, as their diffusion component is essentially the same. The s-box has an iterative period of 2, with every element paired to another.

If you wish to create a cipher that is a full involution, your best bet is a Feistel structure. You can use involutional components but that is not a requirement. If your goal is code reuse and simplicity of description, look at the design principles of Anubis.

You can also use a stream cipher mode such as CTR on any block cipher, as XOR is its own inverse.


AES CBC: how shall i get to know with AES CBC method, the received Cipher Text is padded or not Algorithm: AES - CBC mode with PKCS7 padding

KeyValue:

10a58869d74be5a374cf867cfb473859

IV:

00000000000000000000000000000000

Plaintext:

00000000000000000000000000000000

Expected ciphertext:

6d251e6944b051e04eaa6fb4dbf78465

Three steps are used to compute the CBC Encrypt as mentioned below:

CBC_Start(Key,IV)
CBC_Update(Plaintext, plaintext length, Ciphertext, Ciphertextlength)
CBC_Finish(Ciphertext, Ciphertextlength)

Ciphertext is obtained when the update is finished, but when finish is completed, the ciphertext obtained is different from what is expected.

Why is this happening?

Your expected ciphertext is correct if you work with no padding. With PKCS padding the result is
6D251E6944B051E04EAA6FB4DBF78465881572C3A96A612C111055707BD7614E


What is the time complexity of the RC6 encryption? I am confused to analyze time complexity of rc6 encryption. Please help me

The time complexity of encryption, decryption and brute forcing a block cipher key are all O(1). This is a fixed problem with no apparent n. If you want to encrypt many blocks using some sane mode (cbc,cfb,ctr,...) the complexity would obviously be O(n).
Cryptographers often misuse assymptotic complexity annotations and write stuff like O(2^128) which is silly as it is still O(1).


CRS vs SRS in zk-SNARK Are Common Reference String (CRS) and Structured Reference String (SRS) is the same in preprocessing phase of zk-SNARK? Is there any difference between them?

There has been variants of definition in the literature, but I would say the zkproof.org's effort to standardize these terminology is a good reference. See page 82 here

I recall there's some discussions on Twitter between Benedikt Bunz, Vanishree Rao and others here


Malicious party security model: When one party is corrupted at a time Consider we have three parties,namely client $A$, client $B$ and a server. Client $B$ and the server can be malicious, but we do not allow the adversary to simultaneously corrupt the server and  client $B$ (similar to [1]).
The scenario is that both clients outsource their private data to the server. Then they ask the server to do computation and send back the result and a proof of computation correctness to client B.  I have designed a protocol that satisfy the above properties but the malicious server may send an incomplete result. This can be detected by client B but after that if client $B$ proceeds it can learn client $A$'s data (and this is not desirable).

Question: Based on the above security model, is client $B$ allowed to take further action to figure out the other client's data, after it detects the server's malicious behavior?

Edit: TBN: The outsourced data is not leaked to the malicious server.

[1]. http://research.microsoft.com/pubs/194141/sapsi2.pdf

$A$ has outsourced it's private data to the server, right? In that case $A$'s private data has already been leaked to the adversary when the server was corrupted. So there is no added leakage in $B$ also learning this data. In fact since only one of $B$ and the server can be corrupted (assuming static corruptions) we can conclude that $B$ is honest, and there is really no problem.


Are hashes only used to confirm data integrity when used for distributed ledgers? I have a couple questions related to hashing and data. Please let me know if the questions I have are too broad for this site, or if clarification is needed.

I have read a lot about hashing as it relates to distributed ledger technology (DLT) like blockchains and directed acyclic graphs (DAG), but I am I am wondering if hashing is only to confirm that the data being hashed was unaltered, so I have some questions:

Can hashes be used in other ways? For example, can a hash be used as an address to locate data?
Since a hash is only one way I am guessing someone cannot obtain the original data before hashing, which means a hash is only a confirmation that data is unaltered?
If data in the past is altered, the current hash encompassing previous data will change, but where is the original hash to compare it to that lets a user know that a hash has changed? I am guessing the correct hash is held by a majority of people in the DLT?

Can hashes be used in other ways? For example, can a hash be used as an address to locate data?

Hashes of many kinds figure prominently almost everywhere in cryptography: stream ciphers, key derivation, message authentication, public-key signatures, public-key encryption, noninteractive zero-knowledge proofs, etc.  They are indeed sometimes used as an address for data in content-addressed storage systems like Tahoe-LAFS.

  Since a hash is only one way I am guessing someone cannot obtain the original data before hashing, which means a hash is only a confirmation that data is unaltered?

If a hash function $H$ is second-preimage-resistant, and you know $h = H(m)$, then it is hard for an adversary to retroactively find $m' \ne m$ such that $h = H(m')$ even if they know $m$.
If a hash function $H$ is collision-resistant, then it is hard for an adversary to actively find $m' \ne m$ such that $H(m') = H(m)$, which would enable them to hand you a benign message $m$ for you to review, and later substitute a malicious message $m'$ for it without anyone being any the wiser because the hash didn't change.

  If data in the past is altered, the current hash encompassing previous data will change, but where is the original hash to compare it to that lets a user know that a hash has changed? I am guessing the correct hash is held by a majority of people in the DLT?

This depends on the details of the protocol.  Nothing can be said in general.  But usually in a complex data structure like a Merkle tree or a blockchain (which is a kind of pathologically unbalanced Merkle tree), the current hash is calculated over some data together with the previous hash.


Why Merkle Tree doesn't suffer Birthday attack? I am trying to understand why Merkle Tree doesn't suffer the birthday attack?

Can you help me?

The birthday attack, birthday paradox or - probably most accurately - birthday problem does occur for Merkle-trees. This is both the case for the output of the hash algorithms used for the nodes, the in between hash values in the tree as well as the final hash value.

What's probably confusing you here is that the birthday attack isn't really a practical attack against secure hash functions unless the output size is not large enough. In other words, it is the output size of the hash values that protect against the birthday problem becoming a practical issue.


Order of g in Paillier Scheme I'm trying to understand the Paillier Scheme but there's something I can't understand in the  keyGen algorithm:

  Ensure $n$ divides the order of $g$ by checking the existence of the following modular multiplicative inverse: $$\mu = (L(g^\lambda \bmod  n^2))^{-1} \bmod n.$$

I'm trying hard to find the relation between $n$ divides the order of $g$ and $\gcd(n, L(g^\lambda \bmod n^2))=1$ but I can't find it. I hope that somebody can help me understand it.

You can find the folowing information in the book Katz, Lindell "Introduction to modern cryptography".

  PROPOSITION 13.6 Let $N=p q$ , where $p, q$ are distinct odd primes of
  equal length. Then:

  $\operatorname{gcd}(N, \phi(N))=1.$
  For any integer $a \geq 0,$ we have $(1+N)^{a}=(1+a N) \bmod N^{2}.$

  As a consequence, the order of $(1+N)$ in $\mathbb{Z}_{N^{2}}^{*}$ is $N .$ That is, $(1+N)^{N}=1 \bmod N^{2}$ and $(1+N)^{a} \neq 1 \bmod N^{2}$ for any $1 \leq a<N .$

  $\mathbb{Z}_{N} \times \mathbb{Z}_{N}^{*}$ is isomorphic to $\mathbb{Z}_{N^{2}}^{*},$ with isomorphism $f : \mathbb{Z}_{N} \times \mathbb{Z}_{N}^{*} \rightarrow \mathbb{Z}_{N^{2}}^{*}$
  given by
  $$
f(a, b)=\left[(1+N)^{a} \cdot b^{N} \bmod N^{2}\right]
$$

It means that $n$ divides the order of $g=f(a,b)$ iff $L(g^\lambda \bmod n^2)=a\cdot \phi(N)\in \mathbb{Z}_{N}^{*}.
$


Pen and Paper Authentication What is the best way to prove that you wrote the encrypted message on a piece of paper? As most of us know, many conspirators have died because of false message implants, Mary Queen of Scots, for example.

You have asked about the authentication of a hand-written message, but let's also include an integrity check as a desired service.

Let's say that your message was encrypted with a one-time pad. The following methods of early modern cryptography will not do:

  (1)  Russian
  copulation  (which is designed to further conceal names, headers, salutations, etc.)

  (2)  Variable-length padding

  (3) Using a reasonably-sized tabula recta

For example:

Plaintext (your message):        DONOT  NEGOT IATE
Truly random key:                JQOXF  RMSUA PWBI
                                -------------------
Ciphertext:                      MEBLY  EQYIT XWUM

Variable padding added:

KIPXQ NECEM EBLYE QYITX WUMRZ NUDOA DIEHL ARAIT EMONG ESEBO SLAVO

But this is no solution.  People used to simply take it for granted that the message was authenticated because their pre-shared symmetric key worked to decrypt it.

Option A

However, one could take advantage of having pre-shared secrets, especially with the OTP because this must have already been done anyway.  First, determine the size limit of the ciphertexts that will be sent. For example--choose thirty-one characters-- and draw a box, say 31 columns wide and 34 rows deep.  Write the plaintext across the top in the first row.  Yes, this is going to be a short message, but notice that this system might be amenable to using code. Next, under each character of the plaintext, write the predetermined 31-character authenticator for that character.  For example:

DONOT NEGOT IATE  (__truly random, pre-established, one-time, filler__)

DONO...
FTID...
GWOZ...
NRFG...
RIUW...
QESD...
JFLK...
GUEE...
MUNF...
ARAI...
TEMO...
NGES...
EBOS...
LAVO...
WAZY...
QLYX...
etc.
etc.

To clarify, this means that each character in the plaintext will have a thirty-one character authenticator, and these will always be different (which recalls homophonic substitution and your reference to Mary Queen of Scots).

It is crucial that all of these values be generated in a "truly random" manner.

There will be a table similar to this:

If 1st character is "A" =  KFGEIOGZUZDOITSEHAJNWNSYFEBMAXY
If 1st character is "B" =  BREHYEMKIDHFDDJBDIHTDZGDOODYHWV
(etc.)
If 2nd character is "A" =  VRDABALALAJEOQZFURJVLPQWVMVAECZ
(etc.)

So, each character in the ciphertext will correspond to one of the 26 possible authenticators, and this is going to end up being a little booklet of truly random values.

The last two rows will be a truly random authenticator which will match the indicator tag.  The indicator tag will appear above the message, and will mainly be used for convenience--to indicate message sequence and which key to use.

For example (which is not to be encrypted):

AVRAL OBESE XIANG POLAR GRIME TIARA HANOI THUGZ

It will, of course, correspond with the shared secret authenticator in the last two rows of the message.  Both will be non-sequential.  The shared secret authenticator will only be used once. As you can see, the pre-established size of the message is very important.

Again, the authenticator will be 62 characters long and take up the last two rows of the message.

For example:

ATSOHKIFZPYTSWTEHKANNAVASUUXWO
IMDYSDFFLHTGEISOUBZFWQBXRQOKSI

Now, pass your intended one-time pad key over the whole thing.

Note:  for this option we could expand the alphabet for added strength. Everything is going to depend on the strength of the key, and a long key it will be.

Option B

Using Poly1305 by hand might be a solution, but that is going to take some work. You are also going to have to devise a method for adding that information to your message.  Poly1305 has a 32-bit preshared key that cannot be reused. Good advice, coming from forest and, graciously, from Ross J. Anderson himself, says use a Carter-Wegman universal hash function.

Option C

Construct a one-time MAC according to these instructions.


Why does NIST SP 800 `KDF in Counter Mode' specification require a PRF rather than a PRP? This is the NIST SP 800 KDF in Counter Mode specification.

Where $K_I$ is the input key, $[i]_2$ is the counter value, Label and Context are fixed-length strings and $[L]_2$ is the output size, the input to the PRF for each block $i\in n$ is as follows

$$K(i) := \operatorname{PRF} (K_I, [i]_2 \mathbin\Vert \mathit{Label} \mathbin\Vert \mathrm{0x00} \mathbin\Vert \mathit{Context} \mathbin\Vert [L]_2)$$

I'm trying to understand why

  this Recommendation approves the use of either the keyed-hash Message Authentication Code (HMAC) specified in [8] or the cipher-based Message Authentication Code (CMAC) specified in [7] as the pseudorandom function.

Why not just use a straightforward PRP like AES here? Provided the fixed input data is of the correct width, I don't see why the complexity of using i.e. a CMAC PRF is being added to the construction.

Moreover, looking at the NIST CMAC specification and adapting it for one-block fixed-length inputs it seems the only difference would be XORing a second key with the input to the PRP.

The basic goal—not really explicated by the standard—of these KDF constructions is to turn an unstructured-input short-output PRF $f$ into a structured-input long-output PRF $\operatorname{KDF-}\!f$, whose PRF-advantage has some standard reduction to the PRF-advantage of $f$.

If the label, context, counter, etc., are all short enough, you could instantiate it with a PRP instead of a PRF for $f$, and you would incur the standard PRP-for-PRF cost on security bounds.  It is likely that with CMAC, you don't pay that cost—though I haven't done the analysis to be sure.


The difference between MACs vs. HMACs vs. PRFs I have some confusion regarding the difference between MACs and HMACs and PRFs and when to use which term.

If the function is computed using a hash and secret key like the following, is this a HMAC or MAC?

MD5(master_secret + pad2 + MD5(handshake_messages + Sender + master_secret + pad1));

If I have a tag for verifying data, computed using a PRF in the form:
PRF(master_secret, finished_label, Hash(handshake_messages))

Again, my question, is this HMAC or MAC or none, just a PRF?

The above functions are what is used in the Finished messages for SSL 3.0 and TLS 1.2 respectively. The literature use MAC generally. I am not sure if this is the correct term used to refer to them.

Can I refer to HMAC and PRF by MAC?

A PRF or pseudorandom function family is a family of functions $F_k\colon \{0,1\}^n \to \{0,1\}^m$ such that if $k$ is uniformly distributed, then $F_k$ appears to be uniformly distributed among all functions $G\colon \{0,1\}^n \to \{0,1\}^m$.  A PRF $F_k$ is secure if an adversary who does not know the key $k$ can't distinguish $F_k$ from a uniform random choice of function $G\colon \{0,1\}^n \to \{0,1\}^m$ with more than negligible probability of success beyond flipping a coin—the adversary's only strategy is to correctly guess the key $k$ which is usually drawn uniformly from a space of usually $2^{128}$ or $2^{256}$ possibilities, which no adversary will ever stumble upon by chance.

The existence of PRFs remains a conjecture, related to P = NP; at best we conjecture that function families are PRFs, and sometimes find counterexamples to the conjectures.  Some PRFs have long or variable-length inputs, e.g. keyed BLAKE2b; some PRFs have short inputs, e.g. ChaCha or the compression function inside MD5.

A MAC or message authentication code is a family of functions $M_k\colon \{0,1\}^* \to \{0,1\}^T$ with which one can construct and verify a $T$-bit tag $t = M_k(m)$ on a message $m$ with a secret key $k$.  A MAC is secure if an adversary, upon seeing some number of past (possibly adaptively) chosen messages and tags $(m_i, t_i)$ with $t_i = M_k(m_i)$, can't forge a tag $t' = M_k(m')$ for a message $m'$ not previously seen with better than negligible probability.

Many MACs are one-time authenticators, meaning the secret key can be used for only one message, such as Poly1305 and GHASH (of AES-GCM).  One-time authenticators are useful because they can be extremely fast and can come with an unconditional information-theoretic security proof of forgery probabilities, and it is easy to use a PRF with a nonce to create a new OTA key for each message.

A long-input PRF $F_k$ can also serve as a MAC, because an adversary having seen $\{F_k(m_i)\}_i$ can't even distinguish that from $\{G(m_i)\}_i$ for a uniform random choice of $G$, so the best strategy the adversary has is to pick some $k'$ uniformly at random, try forging $t' = M_{k'}(m')$ for some message $m'$, and hope that $k = k'$, whose success probability is bounded by the probability that $M_{k'}(m')$ happens to coincide with $M_k(m')$ or that $k = k'$, which are both negligible.

$\newcommand{\concat}{\mathop{\Vert}}$HMAC is a specific construction of a long-input PRF out of a short-input PRF chained in a Merkle-Damgård construction $H$, such as MD5 or SHA-256.  Naively using the function $$F_k\colon m \mapsto H(k \concat m)$$ for uniform random key $k$ does not give a PRF when $H$ is either MD5, SHA-1, SHA-256, or SHA-512, because even if I don't know $k$, knowing $F_k(m)$ enables me to easily compute $F_k(m \concat p \concat m')$ for some padding $p$ and an arbitrary suffix $m'$.  This is called a length extension attack.  HMAC works around this for an MD hash function $H$ by using $$F_k\colon m \mapsto H\bigl((\mathrm{opad} \oplus k) \concat H\bigl((\mathrm{ipad} \oplus k) \concat m\bigr)\bigr),$$ where $\mathrm{opad}$ and $\mathrm{ipad}$ are constant strings defined in the standard.

(The full details are finicky, e.g. if $k$ is not exactly the length of one block of the short-input PRF underlying $H$.  You can also use HMAC on non-MD functions such as SHA-3, but the usual reference for an HMAC security reduction relies on MD.  The security reduction story for HMAC is complicated, and there has been some more recent work on it; however, the strategy for modern designs like SHA-3 and BLAKE2 is to just make prefix-keyed $F_k\colon m \mapsto H(k \concat m)$ work as a PRF without the contortions of HMAC, and to define a standard domain-separated keyed PRF variant of the function.)

Since for certain fixed hash functions $H$, HMAC-$H$ is conjectured to be a PRF, and since a PRF always makes a MAC, you can use HMAC-$H$ to make a (rather slow) MAC.

Is your construction an HMAC for some fixed hash function $H$?  No.

Is your construction a PRF?  No: if an adversary can control $\mathrm{handshake\_messages}$, then they can almost certainly find a collision in $$\operatorname{MD5}(\mathrm{handshake\_messages} \concat \mathrm{Sender} \concat \mathrm{master\_secret} \concat \mathrm{pad}_1),$$ which would enable them to distinguish $F_k$ (your construction) from a uniform random $G\colon \{0,1\}^\ell \to \{0,1\}^T$ without knowing $k$ ($\mathrm{master\_secret}$) by simply evaluating it on the colliding messages and seeing whether it's the same, which for the overwhelming majority of functions $G$ will not be the case.

Is your construction a MAC?  Again, no, because if the adversary can find a colliding pair of handshake message sets, then they can ask you to make a tag on one of them, and then they can use the same tag to produce a forgery on the other one.

Does this mean you can immediately attack a system in practice that works this way?  Maybe, maybe not.  What it means is that the crypto is not engineered out of reliable well-understood parts that could give confidence in the security of the whole system.  Thus to understand the security of the whole system you cannot simply (a) assess the security of the parts, and (b) assess the security of how they are wired; you must assess the whole thing as a giant unit ball of hair.  And most cryptographers and auditors don't want to bother doing that because it's a lot more work than well-done crypto engineering.


On splitting vs factoring On page 89 Remark 3.5 in the Handbook of Applied Cryptography the following is written:

  A non-trivial factorization of $n$ is a factorization of the
  form $n = ab$ where $1 < a < n$ and $1 < b < n$; $a$ and $b$ are said to be non-trivial factors
  of $n$. Here a and b are not necessarily prime. To solve the integer factorization problem, it
  suffices to study algorithms that split $n$, that is, find a non-trivial factorization $n = ab$. Once
  found, the factors $a$ and $b$ can be tested for primality. The algorithm for splitting integers can
  then be recursively applied to $a$ and/or $b$, if either is found to be composite. In this manner,
  the prime factorization of $n$ can be obtained.

I think that this argumentation is flawed. At the time the book was written there were no efficient primality tests available (or at least none are given in the book, but to my knowledge the first of these test was the AKS algorithm back in 2002), so the statement

  Once found, the factors $a$ and $b$ can be tested for primality.

does not make sense to me, as a primality test can not be done efficiently in the context of this book. Am I getting something wrong?

EDIT:

I am aware that probabilistic primality test like Solovay-Strassen or Miller-Rabin were already around at the time, they are also covered in the book. But I do not see why the existence of Miller-Rabin should be an argument that a primality test can be done efficiently, since said tests have an error bound when returning "n is prime". And by the definition of polynomial reduction (again taken from the book on page 88:

  Definition Let $A$ and $B$ be two computational problems. $A$ is said to polytime reduce to $B$, written $A \le_P B$, if there is an algorithm that solves $A$ which uses, as a subroutine, a hypothetical algorithm for solving $B$, and which runs in polynomial time if the algorithm for $B$ does.

If I understand this definition correctly we can not use Miller Rabin as a primality test in the argument $\text{factoring} \le_p \text{splitting}$ above, since then we can not be certain that the factors we found are indeed primes. (If I am not mistaken an algorithm is said to solve a problem if it can give 100% accurate answers.)

I hope it is clear what I mean, if not please let me know and I will reformulate my question.

Miller-Rabin has been known since at least 1980 (according to Wikipedia). Even though it's probabilistic, it's good enough. For example, openssl uses it$^\textrm{1}$. Chapter 4 of the handbook talks about various primality tests, which may gave you a better understanding of the authors' thoughts.

$^\textrm{1}$See the source code for bn_prime.c


How does the size of the prime affect Elliptic Curve Bit Security? I am using the MIRACL Library to implement an Elliptic Curve Diffie Hellman based Key Exchange according to ECDH-Scheme-Wikipedia.

Referring to the Miracl Docs they suggest a few curves.
Each curve is with respect to a prime p which is n bits in length Miracl Docs EC suggestions.
How does the n bit length of the prime e.g. from the ssc-192 suggestions refer to the provided bit-security?

Elliptic curve security relies on the hardness of discrete logarithm on that curve. (Well, that's a simplification, but this will do for this answer.) When the curve contains N points, it takes an effort of roughly sqrt(N) "elementary operations" to break discrete logarithm.

A prime p of "k bits" means that p is less than 2k, but greater than 2k-1. The number of points on a curve defined over the field of integers modulo p will be close to p (that's Hasse's theorem). Thus, if the prime p has length k bits, the breaking effort will be on the order of the square root of 2k operations, i.e. about 2k/2. It is usually considered that the current, absolute barrier on that which is technologically feasible is between 280 and 2100, so a safe curve would need a prime size of at least 160 to 200 bits. The "ssc-192" curve falls in that domain, so it could be deemed "probably secure".

Cryptographers are fashion victims, and thus always want powers of 2; thus, they will usually ask for "128-bit security" which then translates to a 256-bit prime p.

See this site for a lot of pointers to information on the concept of key strength.


In a very simplistic and step by step example, how do I get the 'w' values for SHA256? I've been to https://docs.google.com/spreadsheets/d/1mOTrqckdetCoRxY5QkVcyQ7Z0gcYIH-Dc0tu7t9f7tw/edit#gid=1194752368, http://www.righto.com/2014/09/mining-bitcoin-with-pencil-and-paper.html, and https://en.wikipedia.org/wiki/SHA-2#Pseudocode (the pseudocode is for sha256)

The use of those links, not withstanding, I cannot create the 'W' values beyond the first 16 values.  Everything I read is complex beyond my understanding.

In a very simplistic and step by step example, how do I get the 'w' values for SHA256?

In SHA-256, $W$ is a vector of 64 values $W_i$ each 32-bit, collectively forming an expanded form of the input to a compression step. Said input is a 512-bit sub-block of the message to be hashed par SHA-256 after that message was padded. The $W_i$ depend only on said input.

$W_0$ to $W_{15}$ are said input, formatted as 32-bit words. $W_{16}$ to $W_{63}$ are computed from these by applying for $i$ from 16 to 63 the recurrence defined by FIPS 180-4 section 6.2.2 as (within a reordering of terms):
$$W_i\gets W_{i-16}\;\tilde+\;\sigma_0(W_{i-15})\;\tilde+\;W_{i-7}\;\tilde+\;\sigma_1(W_{i-2})$$
where $\;\tilde+\;$ is addition with truncation of the result to 32-bit.

In the above expression, $\sigma_0$ and $\sigma_1$ are 32-bit functions of a 32-bit argument defined by FIPS 180-4 section 4.1.2 as:
$$\begin{align}
\sigma_0(x)&\gets(x\ggg\,\,\,7)\oplus(x\ggg18)\oplus(x\gg\,\,\,3)\\
\sigma_1(x)&\gets(x\ggg17)\oplus(x\ggg19)\oplus(x\gg10)
\end{align}$$
where $\oplus$ is bitwise-XOR, $\ggg$ is right-rotation of a 32-bit word (also known as right-rotate-no-carry or right-circular-shift), $\gg$ is right-shift of a 32-bit word (also known as right-logical-shift).

For example, to compute $W_{16}$, we

apply the function $\sigma_0$ to $W_1$ (right-rotating that value by 7 and 18 bits, right-shifting it by 3 bits, then combining the resulting three 32-bit values by XOR);
apply the function $\sigma_1$ to $W_{14}$ (right-rotating that value by 17 and 19 bits, right-shifting it by 10 bits, then combining the resulting three 32-bit values by XOR);
add $W_0$, $W_9$, and the two above results, truncating the result to 32-bit.

Note: the reason for using shift rather than rotate for one of the terms of $\sigma_0$ and $\sigma_1$ is discussed here.

Note: often (including in almost any careful hardware implementation) it is kept only the chronologically last obtained 16 values of $W$, evolving as the compression rounds are performed per the transformation:
$$W_i\gets W_i\;\tilde+\;\sigma_0(W_{(i+1\bmod16)})\;\tilde+\;W_{(i+9\bmod16)}\;\tilde+\;\sigma_1(W_{(i+14\bmod16)})$$


Do I have to have a different salt for each password? Should I use a different salt for each password?

In my system, there are no user names, only passwords.  When a user logins in, he types in one or more passwords and the server compares the results of the password(s) hashed many times (PBKDF2) for authentication.  Each password might unlock some subset of functions.

As I see it, salt has two purposes:

Decrease the feasability of using (rainbow) tables: The salt makes rainbow tables with just ascii characters useless and the cost of making rainbow tables for all possible salts is greater than that of brute-forcing the password.
Unique salts per password mean that users selecting the same password won't have identical authentication results.

In my situation, using a salt per-password makes authentication an O(n*n) problem, time that could be spent on adding rounds to the hash.  With a single salt, (1) is accomplished and (2) doesn't matter because there are no user names.

So, can I use just a single salt?

"In my system, there are no user names, only passwords."

This is the real problem.  Using the same value for both identification and authorization is usually a bad idea, for several reasons:

Two accounts cannot have the same password.
An on-line attacker needs only a single query to determine if any password in the system matches their guess; thus, they can attack all accounts in your system simultaneously with no more effort than attacking a just single account would take.
Since you cannot use per-account salts, an off-line attacker has the same advantage: they can hash each guessed password and then quickly match it against the table of valid hashes.

About the only time when using a single combined identifier/authenticator may be valid is when this identifier is randomly generated and known to have very high entropy (say, 128 bits or more).  With that much entropy, even the odds of guessing just one identifier out of millions of valid ones are acceptably low.  However, such long random tokens are generally impractical for humans to enter or memorize, so they're usually only practical in low-level automated protocols, e.g. as session identifiers.

You also write that:

  "When a user logins in, he types in one or more passwords [...]. Each password might unlock some subset of functions."

So it seems that, instead of the passwords being associated with user accounts, they're associated with some kind of roles.  That's a pretty interesting design, but I won't argue about its merits as such, compared to more traditional user account schemes; presumably you have some reason for designing your system like this.

However, what you could do is give names (or at least some kind of identifiers) to the roles, and have the users enter both the name as well as the password for each role they want to use.  That way, you can use the name to look up the relevant authentication record — which can then include a per-role salt — in the database.

In any case, naming your roles sounds like a good idea for other reasons too: surely there are times when you'd like to be able to refer to a particular role without divulging its password?


When is each key used when encrypting an email using OpenPGP? When you send an email using PGP to encrypt emails, is the recipients public key used to encrypt the email, or is your private key used? Are they both used?

At what points do each of the four keys from the two key pairs get used?

Let Alice have a key pair (PubKeyA, PrivKeyA), where the first is public, the second private,
and similarly for Bob (PubKeyB, PrivKeyB). Alice and Bob know each other's public keys in a reliable way (from a key server, or because they received them in person etc.)
If we use RSA keys, e.g., then they could use just one pair, so I'll assume this first.

When Alice sends Bob a signed message (signing is optional in PGP, but good practice), the following happens, simplified:

Alice generates a key K for some symmetric cipher algorithm, say AES (i.e. the program does, using a good random number generator, etc.)
Alice encrypts the message M using K, to get AES-Enc(M,K).
Alice encrypts K using PubkeyB, to get RSA-Enc(K, PubKeyB).
The 2 parts RSA-Enc(K, PubKeyB) and AES-Enc(M) are combined in an unambiguous way (so they can be split later) into an encrypted message M' = Enc(M, K, PubKeyB).
Alice uses her PrivKeyA to cryptographically sign M' (which mostly means hashing M' and "encrypting" the result with that private key, in the case of RSA), which gives us Sign(M',PrivKeyA)
Enc(M, K, PubKeyB) and Sign(M',PrivKeyA) are combined in an unambiguous way into the message that Alice sends.

Note that we need a secure mode of operation to AES to encrypt M using K, a secure way to encrypt the key K using PubKeyB (using a secure padding scheme, like OAEP), a secure hash function and way to sign (also using a padding scheme) and a good file format to unambiguously pack all the data in. Read up on the standards involving them...

Bob does the following (simplified) when he receives the message:

Split the message into M' = Enc(M, K, PubKeyB) and Sign(M', PrivKeyA).
Check, using PubKeyA, that Sign(M', PrivKeyA) is a valid signature for M'. Stop if that fails. If it succeeds Bob is confident that M' is intact and indeed sent by Alice.
Then split M' into RSA-Enc(K, PubKeyB) and AES-Enc(M).
Using his PrivKeyB, decrypt K from RSA-Enc(K, PubKeyB) and PrivKeyB.
Using K, decrypt M from AES-Enc(M) and K.

Now Bob has M too, and is confident it is the actual message Alice wanted to send, and was not tempered with in transit.

Like I said, the devil is in the details, but this is the essence of it.

Now, in practice, PGP creates 2 pairs per user, an encryption pair and a signing pair. Also the programs sends key-identifiers with the message to indicate which ones are used (in general, a user could have more public keys etc.)


What is the key strength reduction encrypting only 160 bits of data using RSA1024 for signatures? I am attempting to determine the strength of an incorrectly implemented 1024 bit RSA signature scheme. The weakness in the implementation is that the padding data lacks random numbers. As a result, for every message signed, only 160 bits of data are changed (cryptographic hash).

How does one determine the resulting reduction of strength in the scheme, and how many signed messages would be necessary to make a 1024 bit private key a mathematically feasible operation to recover?

Well, there are no necessary 'reduction in strength', for two reasons:

You ask about how many signatures you'd need to recover the private key.  Well, even with unrestricted Oracle access to the private operation, there's no known way to recover the private key (or equivalently, factor the modulus) that's more efficient than just ignoring the Oracle and attacking the modulus directly.  Hence, giving the attacker access to a limited number of signatures cannot help him recover the private key.
What the attacker might be able to do with some padding methods is deduce the value of other signature operations; this would be generating a forgery without the private key.  Now, there are certainly known padding methods (such as a naive 'zero fill' method) that are prone to this.  On the other hand, there are deterministic padding methods (such as the PKCS #1.5 RSASSA-PKCS1-v1_5 method) for which there is no known method of generating forgeries easier than finding collisions in the hash function.

So, if the system is using, say, the above PKCS method, there is no known weakness, even if the attacker has access to huge numbers of signatures.


Why can't hashes be reversed with toffoli gates? This is a follow up question to this question: Crack cryptographic hash functions using Toffoli gates?.

Suppose there is a hash function $$H(x)=y,$$ where $x$ is the input of the function and $y$ is the hash of $x$. Now, suppose we have made an emulating software that emulates $H(x)$ using Toffoli gates. This new function can be denoted by $$T(x)=(y,z),$$ where $z$ is the garbage. Now toffoli gates are reversible, so we can make a function $$T^{-1}(y,z)=x.$$ Now the problem is that we do not know $z$, because it was lost during the calculation of $H(x)$.

Now we can choose any random (but valid) garbage $z'$ and calculate $$T^{-1}(y,z')=x'.$$ Now by definition of $T^{-1}$, we have $T(x')=(y,z')$; and so $$H(x')=y.$$ So we have found a collision (if not the original value).

I know very less about cryptography, and I know something must be wrong in the above but I cannot find out what is wrong. So, please tell me what is wrong. I do not have the neccesary information and software to test this procedure.

Example

This is a very simple example. More complicated examples can be difficult to calculate by hand.

Suppose $x\in(0,1)$ and $H(x)=x\land1$. Now we will try to reverse the output $H(x)=0$. Now let's denote the toffoli gate by $G(x,y,z)$. The function $H(x)=x\land 1$ can be converted into $$T(x)=(y,z) \rightarrow G(x,1,0)=(y,z_1,z_2).$$ Reverse of this is $$T^{-1}(y,z)=(x) \rightarrow G^{-1}(y,z_1,z_2)=(x,1,0).$$ We have $y=1$. Let's choose $z'=(1,0)$. Now calculate $$T^{-1}(1,(1,0))=1 \Leftarrow G^{-1}(1,1,0) = (1,1,1).$$ So, we have $H(1)=1$. This is the answer! (Because $1\land1=1$)

The question errs precisely at the point when it writes: $$\text{and so }H(x')=y.$$

Problem is: that holds for $x'$ matching some garbage $z'$, including $z'=z$, and perhaps other garbage $z'$, but we do not know which garbage (or $z$ unless we know $x$), and I see no reason that it holds for $x'$ obtained from any garbage $z'$ except for trivial $H$; and in the question $z'$ is random.

The only constructive process (as opposed to search) that I can think of to exhibit garbage $z'$ such that $H(x')=y$ is clause resolution or some improvement of that, well known to be exponential, as well as its sequential alternative.

Or otherwise said, my understanding of Toffoli-gate equivalent circuits (still limited, but improved in the process of making the present answer) is that they really are of the form $T(x,z)\mapsto(y,z)$ where it is easy to deduce $z$ from $x$ such that $H(x)=y$ holds, but not to deduce $z$ from $y$ such that $H(x)=y$ holds. Or, if we insist on the $T(x)\mapsto(y,z)$ notation, that is use $z$ built from inputs taken from $x$, we need $x$ to exhibit $z$.


There is Alice and there is Bob. But what is the name of the malicious user? I know it is a kinda funny and maybe even naive question but its still security related, so I decided to ask.
Bob and Alice are widely used names indicating the two end-users/parties for web protocols. But in security there is also a third entity, the malicious user. I read a blog post naming that entity "Maria". I giggled and wondered:
Is "Maria" actually a well-established name for the malicious user, in the security industry?

That's a funny question, I think it depends on the kind of attack you're performing.
For example, when you're trying to eavesdrop a communication, it's usually "Eve" who's doing it.
For more generic attacks, "Mallory" (Coming from "malice") is the most common choice.
As Stephen Ullrich pointed out in his comment, here's a list of all the commonly used characters: https://en.wikipedia.org/wiki/Alice_and_Bob


what is the current actual budget - as of 2015 - needed to build a DES breaker machine? EFF - Electronic Frontier Foundation - built a DES cracker for a budget of 250K$ in July 1998. I assume that as of 2015 - the cost of such a DES breaker would be less, are there any estimations about how it would cost? Re-using their 1998 design.

Re-using their design might be no good idea - there are cheaper designs for sure. This new DES cracker would just need to try every possible key - like the one of the EFF already did.

DES was a big standard for encryption, so some people did build such machines, right? Of course did they: COPACOBANA is able to break DES in under 9 days and costs under 10,000 US $ - That was 2006. You could even run a few of them parallel and crack algorithms like DES even faster - or you just use RIVYERA and crack DES in 1 day. You can use more than one machine of them, too.

More informations about the DES cracker and the mechanic behind it can be found in this document.

I'm pretty sure there are even better methods as of 2015.


What is a man-in-the-middle attack (for instance in Diffie-Hellman)? I'm new to cryptography and I just started learning about the Diffie-Hellman key agreement. I read that this system is vulnerable to a man-in-the-middle attack when used alone. What kind of attack is this?

in diffie-hellman key exchange algorithm vulnerability's is good defined by RSA lab :

"The Diffie-Hellman key exchange is vulnerable to a man-in-the-middle attack. In this attack, an opponent Carol intercepts Alice's public value and sends her own public value to Bob. When Bob transmits his public value, Carol substitutes it with her own and sends it to Alice. Carol and Alice thus agree on one shared key and Carol and Bob agree on another shared key. After this exchange, Carol simply decrypts any messages sent out by Alice or Bob, and then reads and possibly modifies them before re-encrypting with the appropriate key and transmitting them to the other party. This vulnerability is present because Diffie-Hellman key exchange does not authenticate the participants. Possible solutions include the use of digital signatures and other protocol variants."

and some simple example of mitm attack :

Alice "Hi Bob, it's Alice. Give me your key." →     Mallory     Bob
Alice     Mallory "Hi Bob, it's Alice. Give me your key." →     Bob
Alice     Mallory     ← [Bob's key] Bob
Alice     ← [Mallory's key] Mallory     Bob
Alice "Meet me at the bus stop!" [encrypted with Mallory's key] →     Mallory     Bob
Alice     Mallory "Meet me in the windowless van on 22nd Ave!" [encrypted with Bob's key] →     Bob


Understanding ChaCha20-Poly1305 AEAD In the AEAD scheme described in https://tools.ietf.org/html/rfc7539#section-2.8.1, the aad and cyphertext are padded to be a multiple of 16 bytes in length. Why is this necessary? Does it provide any advantage over simply not padding the data?

It is the authentication - which uses Poly-1305 that needs the padding; the padding does not expand the ciphertext. The Poly-1305 operates on blocks of 128 bits. The padding is applied so that Poly-1305 can always process full blocks of input. Afterwards the the padding is discarded - it is not kept with the ciphertext.

During verification the padding is reapplied, otherwise the calculated authentication tag would not be identical with the one that was kept with / is part of the ciphertext.

In the case of Poly1305 it seems that the additional authenticated data (AAD or just AD) is padded separately, instead of concatenating the two and padding the combination of the two. This makes it possible to calculate the AAD component independently of the ciphertext component of the authentication tag, as DannyNiu's answer indicates.

Note that in practice a single block input buffer will be used within the implementation of the Poly-1305 function. Implementations will pad the buffer instead of the actual input. Discarding consists of clearing the buffer - if it is cleared at all, it can also ignore the data in it.


Derivation of birthday paradox probability I am trying to come up with an explanation of the probability of birthday collision.

$P$(no collision among t people) = $(1− \frac{1}{365}) · (1-\frac{2}{365}) ··· (1-\frac{t-1}{365})$

  For one person, the probability of no collision is 1, which is trivial
  since a single birthday cannot collide with anyone else’s. For the
  second person, the probability of no collision is 364 over 365, since
  there is only one day, the birthday of the first person, to collide
  with:

  $P$(no collision among 2 people) = $(1− \frac{1}{365})$

  If a third person joins the party, he or she can collide with both of
  the people already there, hence:

  $P$(no collision among 2 people) = $(1− \frac{1}{365})·(1−\frac{2}{365})$

While it is clear how we get the probability of collision for 2 people, it is not intuitive to me that how we get the probability of collision between 3 people. I'd expect the probability would be $(1−\frac{2}{365})$. For example, when you roll the dice, the probability of $6$ is $\frac{1}{6}$, and the probability for 5 or 6 is $\frac{2}{6}$. It is not $\frac{1}{6}$·$\frac{2}{6}$ which seems to be the case in birthday collisions.

I'd appreciate an answer with an intuitive explanation.

The probability becomes more intuitive when one pictures the $t$ persons entering one by one in the room.

Before the first person enters, there's no collision/coincidence of birth-date, thus probability of no collision is $P_0=1$.

When the first person enters, there can't be a collision/coincidence of birthdate, probability of no collision is $P_1=1$.

When the second person enters, there is one chance in $365$ that his/her birthday is the same as the first person's birthdate, thus the probability of no collision is $P_2=1-\frac1{365}$.

When the third person enters, either
- there was a collision at the previous stage, and then the probability of no collision is $0$;
- or there was no collision at the previous stage, thus there was $2$ persons with different birth-dates in the room, and the probability that the third person has one of their birth-dates is $2$ in $365$, thus the probability of no collision is $1-\frac2{365}$.
The total probability of no collision after the third person enters is obtained by adding these two probabilities weighted by the probability conditioning them. We thus have $P_3=(1-P_2)\,0+P_2\,\bigl(1-\frac2{365}\bigr)$, thus $P_3=\bigl(1-\frac1{365}\bigr)\bigl(1-\frac2{365}\bigr)$

The same reasoning gives $P_{i+1}=(1-P_i)\,0+P_i\bigl(1-\frac i{365}\bigr)$, that is $P_{i+1}=P_i\bigl(1-\frac i{365}\bigr)$.

From which it comes $P_t=\displaystyle\prod_{i=0}^{t-1}\,\Bigl(1-\frac i{365}\Bigr)$.

For derivation of formulas used in a cryptographic context where the numbers are huge, see my Birthday problem for cryptographic hashing, 101.
Note: $P$, $t$, and $365$ here are $q$, $n$ and $k$ there.


Is there an increased risk of nonce reuse when using GCM with a nonce more than 96 bits? GCM is designed to use a 96-bit nonce, which can be generated either randomly or deterministically. If you use a nonce that isn't 96 bits then it is padded and hashed with GHASH to create a pseudorandom nonce (and block counter) instead. For example, suppose that you generated uniformly random 128-bit nonces, these would be hashed with GHASH and converted into a 96-bit nonce and 32-bit random block counter. Given that GHASH is not collision resistant, is this significantly more likely to result in nonce reuse than generating a random 96-bit nonce directly?

If you insist on random nonces, 128 bit random nonces are safer than 96 bit random nonces (but not as good as 96 bit counter-based nonces - I presume that is infeasible in your scenario).

The 128 bit random nonce is transformed (via GHash) into what is effectively a 96 bit nonce and a 32 bit counter; in the 96 bit case, the 96 bit nonce is used directly, and we use a fixed 32 bit counter value value $1$.  If this (96, 32) bit value is $(X, Y)$, then an encryption of an $N$ block message uses the values $(X, Y)$ through $(X, Y+N+1)$ (and the addition is done modulo $2^{32}$)

Now, GCM runs into trouble if either a used range contains the value $(0, 0)$ (which can't happen with 96 bit nonces), or two separate encryptions (with their nonces) use a value in common.

As for the first possible case (using a value $(0, 0)$ somewhere in the range), that happens with probability $2^{-128}(N+2)$ for an $N$ block message - obviously, 96 bit nonces are better there.

As for the second possible case (using two ranges that interest), 128 bit nonces are clearly better.  After all, for two ranges to interest, they must share the same $X$ component; for 96 bit nonces, that is sufficient; for 128 bit nonces, the $Y$ components also need to intersect, and unless $N$ is near the maximum, that has a probability less than 1.

If we model the prohibition on the $(0, 0)$ value as a single message that just happens to use that single value, then that falls in line with the 'no two messages can use intersecting ranges'.  Then, it is easy to see that encrypting $M$ messages with 128 bit random nonces must be at least as secure as encryption $M+1$ messages with 96 bit random nonces, and actually, because of the observation that two 128 bit nonces that happen to map to the same 96 bit space will generally not intersect, it is actually considerably better.

In addition, you claimed that GHASH was not collision resistant, and Woodstock claimed that GHASH output was likely not uniform.  Actually, if $H \ne 0$, then with 128 bit inputs, GHASH is a permutation, hence it is collision resistant, and the output is uniform.


What is the sponge construction in simple terms? I suggested to my client to use SHA3 instead of SHA2. I know that SHA3 is based on Keccak algorithm which won the NIST's competition.
I want to explain the structure of sponge functions in very simple terms; does anybody have a simple explanation of cryptographic sponges?

I find that the following image from Wikipedia, though perhaps a bit too technical for your purposes, is still helpful with a little explanation:

Essentially, a function $f$ is used repeatedly in two phases, absorbing and squeezing.
In the absorbing phase, small chunks of the input data are mixed into the beginning of the buffer using XORs (using the variables from the image: $r \oplus P_i$). This updated buffer value is then passed through $f$ and the process continues.  With each step a small amount of input date (the bit-length of $r$) is "absorbed" into the buffer using $f$ to semi-randomize the entire buffer.
In the squeezing phase, the same process is repeated but instead of XOR-ing the first $r$ bits with data, they are extracted as the next $r$ bits of the output.
tl;dr: The input is mixed into a buffer in small chucks in between phases where a buffer is randomized, then the buffer is randomized repeatedly while small chucks of it are taken as output.
For more detailed information, see this webpage and this paper by the Keccak team.

It feels worth calling out that your purposes for recommending SHA-3 over SHA-2 may be more important.  Does their application of SHA-2 suffer from the possibility of length-extension attacks?  Are there other benefits of SHA-3 that you could benefit from?  As mentioned here the situation isn't really "move to SHA-3 because it's a better version of SHA-2."
It's possible you're already aware of this, but your client may not be.  As such, a simple description of how it works may not really be all they need, even if that's all they're asking for.


How do I encrypt a bunch of messages by different authors, shared with that group of people? I'm still getting my head around public/private key cryptography, and I can't quite work out how to ask the right question to get an answer for this problem, but here goes!

Alice, Bob, Carol, and Dave are all in a secret society which writes exquisite corpse stories.
First Alice writes a line into a file; then she sends this file to Bob, Carol and Dave. Each of them might write a line too, and share it with the group again.
Nobody outside the secret society should be able to read their story, but each of them should be able to read the whole story.
After a while, Alice invites Edgar into the secret society. He can now read all the previous lines in the story, and add his own.

How would I make this scenario happen? Does each person have their own key? Is there a single key pair representing the society as a whole? Is there any reading I could do or terms I could search which would help me understand this scenario?

There are many ways to solve that problem. I would like to tell you my first ideas:

Create a protocol, so that everyone shares the same key. With this key everyone can decrypt the file, write stuff, and the encrypt it again. It is a symmetric approach, but you public key infrastructure may be good to share the key (e.g. Diffie Hellman key exchange. This can also be used for groups). This idea is similar to group chats of messengers. Therefore you could inform yourself, how known messenger apps solve it.

If we assume that they communicate circular ( A -> B -> C -> D -> A -> etc. ) you could only use public key crypto: Just give everyone a public key to decrypt and a private key to encrypt. A writes the file, decrypts it with the public key of B and sends it B. B can encrypt it, write stuff, etc.

What can be a problem is the point that Edgar also wants to know the previous messages. In idea 2. it's simple: Just add him to the circle. For idea 1 it's a bit more complex. When you add Edgar you want to create a new symmetric key. Therefore someone in the remaining network can decrypt the file first, then produce the new key and afterwards share the encrypted file (with new key) again.
Anyway: There are a lot of methods to solve your problem and for most applications performance is very important. Therefore in practice you want to choose the solution which is fastest, cheapest and still provides security.
I hope I way able to help you!


What exactly is the contents of the LDAP userSMIMECertificate attribute? I'm trying to setup an LDAP with user certificates. I have already learned that certificates can be stored in either the userCertificate attribute in DER format, or in userSMIMECertificate in PKCS#7 format, the latter having the advantage of being able to contain the full certificate chain, plus the S/MIME algorithms supported and/or preferred by the client.

However, I'm struggling with what variation of the PKCS#7 format has to be used. I can export certificates as p7b file which - as I understand it - is just a certificate bundle containing multiple certificates, but no further information.

The userSMIMECertificate obviously expects a (signed?) CMS message with no (or at least a negligible) message text. Is this the p7m format created by email clients? But that seems to be encrypted? How can I create the required userSMIMECertificate format?

tl;dr
The userSMIMECertificate attribute must hold a signed S/MIME message.
To create the contents for userSMIMECertificate, sign an email message with an empty message body, then remove all mail headers except for those describing the signature attachment.
The result should look similar to this (signature only):
Content-Disposition: attachment;
    filename=smime.p7s
Content-Type: application/pkcs7-signature;
    name=smime.p7s
Content-Transfer-Encoding: base64

MIAGCSqGSIb3DQEHAqCAMIACAQExCzAJBgUrDgMCGgUAMIAGCSqGSIb3DQEHAQAAoIIEQTCCBD0w
ggMloAMCAQICAQIwDQYJKoZIhvcNAQELBQAwgbYxGjAYBgNVBAMMEXNhdmlnbmFubyBDRVJULWky
MSUwIwYDVQQKDBxzYXZpZ25hbm8gc29mdHdhcmUgc29sdXRpb25zMR4wHAYDVQQLDBVDZXJ0aWZp
[...and so on...]
wtIEojI4gYW+wg/50/viPjxisPIPm3dEJbM+CN5gnySH9HwAAAAAAAA=

or like this (multipart message):
MIME-Version: 1.0
Content-Type: multipart/signed;
    protocol="application/x-pkcs7-signature";
    micalg=SHA1;
    boundary="----=_NextPart_000_003C_01D7312D.9474A240"

This is a multipart message in MIME format.

------=_NextPart_000_003C_01D7312D.9474A240
Content-Type: text/plain;
    charset="us-ascii"
Content-Transfer-Encoding: 7bit

This contents part may be empty or not and will be ignored.

------=_NextPart_000_003C_01D7312D.9474A240
Content-Disposition: attachment;
    filename=smime.p7s
Content-Type: application/pkcs7-signature;
    name=smime.p7s
Content-Transfer-Encoding: base64

MIAGCSqGSIb3DQEHAqCAMIACAQExDzANBglghkgBZQMEAgEFADCABgkqhkiG9w0BBwEAAKCCCDUw
ggQDMIIC66ADAgECAgRK+N2BMA0GCSqGSIb3DQEBCwUAMIHAMSMwIQYDVQQDDBpzYXZpZ25hbm8g
[...]
E3toHxuZzFrZMnMobwmt1nbAwNodpSsAAAAAAAA=

------=_NextPart_000_003C_01D7312D.9474A240--

This format can be created manually by signing an empty message using an email client, then saving that email in text format and removing the unwanted headers in an editor.
To create this format with openssl, use:
openssl smime -sign -in empty.txt -text -out userSMIMEcertificate.txt -signer mycert.pem -certfile intermediatecerts.pem

where mycert.pem is the signer's private certificate including its key and intermediatecerts.pem are any additional certificates that should be included. Add -inkey mykey.pem if the key is separate rather than included in the private certificate.
Note that, in order to sign the message, the certificate owner's private key is required.

Background Details
Format
The userSMIMECertificate is designed to hold a signed message that is signed using the user's email certificate. Additionally, it can and it should also contain the other certificates needed for chaining and verifying the user certificate. It's also designed to provide details about the encryption algorithms which are supported and preferred by the email client.
The userSMIMECertificate LDAP attribute is defined in RFC 2798: Definition of the inetOrgPerson LDAP Object Class as

A PKCS#7 [RFC2315] SignedData, where the content that is signed is
ignored by consumers of userSMIMECertificate values.

The format is based on RFC 2315: PKCS #7: Cryptographic Message Syntax. I find this RFC hard to understand, but fortunately, there is another document RFC 4134: Examples of S/MIME Messages that exhibits an example in chapter 4.9 S/MIME application/pkcs7-mime Signed Message.
As we can see there, it is an S/MIME signed email as created by any email client when sending a signed (but not encrypted) email.
According to this, it's not even necessary to remove any headers, but I recommend it for improved compatibility.
Purpose
In a quote from an original discussion with the creators of the userSMIMECertificate LDAP attribute, one of the authors explains:

Now we come to the question of why we felt we needed a new directory attribute for S/MIME certificates. I was told by our directory engineers that the existing userCertificate attribute was defined as a single raw certificate. That leaves no place to store the other certificates needed for chaining, and no place to store the algorithm capabilities. We had an existing package available to us that could contain both the certificates and the capabilities. That package is an S/MIME signed message.
The format of the userSMIMECertificate attribute is an S/MIME signed message with a zero length body. It contains the user's entire certificate chain and the signed attribute that describes their algorithm capabilities.

There is also a draft about the format to publish the data in userSMIMECertificate that provides some insight, but it has expired in 2001, and there doesn't seem to be successor to it.
Practical Notes
Weak Support
Most email clients seem not to understand a userSMIMECertificate that holds a PKCS#7 signed message. They do understand DER encoded certificates in this attribute. I'm planning to create a compatibility table but haven't yet.
Removed Headers
My above recommendation to remove all headers so only the signature is left is made because I have otherwise experienced problems with some clients, but I don't remember which. The actual definition does not require such modifications.
Algorithm Capabilities
One of the ideas for userSMIMECertificate was that the PKCS#7 data can include the owner's encryption capabilities (i.e. which ciphers they support). That way the encrypting client can select the best encryption cipher supported by both the sender and recipient of the email.
However, in extensive testing I've learned that in practice, only some (older) email clients provide such capabilities. My guess is that this feature has become obsolete by the fact that nowadays users are not confined to using only one email client all the time. Therefore, including one client's capabilities would be useless at best and might even lead to problems with the other client(s).