What is the use of REAL random number generators in cryptography? I understand the use of pseudo-random number generators. I am not getting mixed up between these and "real" random number generators.

However, I don't understand for what a real random number generator is used.
If it is not deterministic, how can it be used in an algorithm?

For some types of algorithms (or protocols) we only need non-guessable (by the attacker) bits/numbers, not reproducible non-guessable ones (like from a deterministic PRNG).

In this cases, "real" random numbers are in theory (i.e. from an information-theoretic point of view, not a cryptographic one) better, since they can't be guessed (or even influenced) by an attacker, even if she could break our PRNG.

Some cases that I can now think of, where we don't need deterministic random numbers:

key generation (both symmetric and asymmetric)
initialization vectors for block cipher modes of operation (these are usually sent with the message, so the same plaintext will not result in recognizable ciphertext for the next message)
random padding in asymmetric encryption (for example OAEP)
salts for password storage (these are stored with the hash)
challenges in zero knowledge proofs (sent to the partner)
random values used in digital signatures (the k in DSA)
one time pads (OTP)  (Here, for the security proof, we actually need "real" random numbers.)
chaffing and winnowing

In practice, pseudo-random bits are cheaper and just as secure for real-world attackers (e.g. with resources limited by our earth mass and universe lifetime), as long as the PRNG is not broken and has enough entropy input to start with.

(If the attacker can control the seemingly random input to the "true random" generator, this would be even worse than a good PRNG.)

Often for these uses we use a combination of a cryptographically secure (deterministic) PRNG and an entropy pool, which gets filled (and re-filled) by random bits gathered by the OS. This would be a non-deterministic PRNG.


Lenstra's ECM Algorithm - field requirement In Lenstra's ECM algorithm, $\#E(\mathbb{F}_{p})$ is required to have small prime factors. Why is this so?

I understand that the p-1 method is efficient for factoring N with small factors. The ECM algorithm replaces the $\mathbb{Z}/p\mathbb{Z}$ group with points on an elliptic curve, both groups having finite cardinality. Why isn't there a restraint on the former?

In Lenstra's ECM algorithm, $\#E(\mathbb{F}_{p})$ is required to have small prime factors. Why is this so?

Actually, it is not required to have small prime factors; it does work better (that is, succeeds quicker) if it happens to have small factors.  To explain it fuller, we'll look at ECM and the p-1 method, which brings up your comment:

  I understand that the p-1 method is efficient for factoring N with small factors.

Actually, what it is good at is factoring N that happens to have a prime factor p where $p-1$ is smooth; that is, consists only of small factors.

The p-1 and the ECM method both work this way: we take our composite number $n = pq$ (where, in general, can have more than two prime factors), and set secret values $p - \epsilon_1$, $q - \epsilon_2$.  Then, we keep on guessing prime factors of $p - \epsilon_1$, $q - \epsilon_2$; if we guess all of the prime factors of one of them, then we immediately get the factorization (and other than time, there's no penalty for making incorrect guesses).

That's what they have in common; now, here's the difference between p-1 and ECM.  With the p-1 method, we always have $\epsilon_1 = \epsilon_2 = 1$ (and that's what having $p-1$ smooth is important; we'll guess small factors, and so $p-1$ works when all the factors are small).  Now, with ECM, $\epsilon_1, \epsilon_2$ are small (compared to the magnitude of $p, q$), but can vary to a large extent (depending on the curve).

And, that's the advantage of ECM: the p-1 method is entirely dependent on something beyond the algorithms control.  If both p-1 and q-1 contains a large (unguessable) factor, it's out of luck, and there's nothing the algorithm can do about it.  With ECM, we can try lots of different curves (with different $\epsilon_1, \epsilon_2$ values), and we might get lucky with one.


How could consumer level OTP + QKD over the internet ever be practical? Please note, I am in no way questioning the future usefulness of quantum key distribution (QKD) in certain applications. I have no doubt it will prove useful for large banks, and in certain military research applications.

However, I cannot ever see it becoming common at the consumer level, or even enterprise level, even if the cost of sensitive quantum hardware decreases drastically.

http://users.telenet.be/d.rijmenants/en/onetimepad.htm

  One-time pad encryption nevertheless has a bright future. It is in fact the only crypto algorithm that has any future. Once that computational power and codebreaking technology has surpassed the capabilities of cryptologists and the limitations of mathematics to make strong encryption, there will no longer be any crypto algorithm that survives the evolution of cryptology, unless it meets the standards of information-theoretical perfect security.

The above article claims that all other encryption algorithms will be made obsolete by computing advances, and therefore, we must at some point move to a combination of One Time Pad (OTP) and QKD. I find this claim to be dubious, but as a non-cryptography expert, I am trying to keep an open mind.

Although this article is mostly about OTP, QKD would need to be used along side OTP to be of much practical value for all but a few select applications.

My doubts stem from QKD not seeming compatible with the principals and implementation of the world wide web. The WWW requires decentralized routing; that is to say, the electrons you receive, will never be the actual electrons I sent you, and that is okay, as long their frequency pattern matches.

To my knowledge, there is no way to duplicate a photon's properties without collapsing its wave function; perhaps this assumption is incorrect?  That means, my server would have to find a way to redirect the same photon to its intended target, which seems error prone and unpractical.

Even if we can find a way to duplicate a photon (or electron) without collapsing its wave function in an efficient manner, how do I now transmit that wave function over wifi, which is how most people use the internet?

Am I misunderstanding something here that would allow widespread QKD and OTP to become practical for a large distributed consumer network? Or is the conclusion this article came to questionable as I suspected?

There are many questions here; I am not answering the question in the title, but rather addressing the final questions in the body.

  One-time pad encryption nevertheless has a bright future. It is in fact the only crypto algorithm that has any future. Once that computational power and codebreaking technology has surpassed the capabilities of cryptologists and the limitations of mathematics to make strong encryption, there will no longer be any crypto algorithm that survives the evolution of cryptology, unless it meets the standards of information-theoretical perfect security. Just as classical pencil-and-paper ciphers were rendered useless with the advent of the computer, so will current computer based crypto algorithms become victim to the evolution of technology, and that moment might creep on us much faster than we expect. Only one-time pad encryption, the only information theoretically secure encryption, will survive that evolution.

The linked article describes OTPs at great length. It goes on to quickly make casual claims about how doomed all other cryptographic algorithms are, without providing any kind of citation or real argument for why this will be the case. There is no reference to even a weak argument such as "but maybe P=NP". They make vague references to increasing computational power and improved cryptanalytic techniques, so I guess that is what we will have to cover.

Computational Power

This demonstrates a lack of understanding of how the cost of cracking a key actually scales. Claiming that advances in computational power alone will ever threaten the security of, for example, AES-256, is evidence in support of this. No amount of computing power will ever brute force an AES-256 key. It is not a possibility even from a theoretical point of view, let alone a practical one.

Additional misunderstandings are present in the paragraph immediately preceding that one:

  Another disadvantage is that one-time encryption doesn't provide message authentication and integrity.

Ok good, this is true and at least the author recognizes this much.

  Of course, you know that the sender is authentic, because he has the appropriate key and only he can produce a decipherable ciphertext ...

This is silly. Anyone can simply craft any set of bits they want and submit it as a "ciphertext", and the receiving party has no way of verifying that the message actually came from anyone in particular (indeed, they could not accurately tell the difference between a ciphertext intended for them and a pile of random bits)

Continuing further into that same paragraph, we see the author advocate MAC-then-encrypt (edit: Actually, it's arguably not even MAC-then-encrypt as the hash is not even keyed), which runs contrary to standard best practices

  A solution is to use a hash algorithm on the plaintext and send the hash output value, encrypted along with the message, to the recipient (a hash value is a unique fixed-length value, derived from a message). Only the person who has the proper one-time pad is able to correctly encrypt the message and corresponding hash. An adversary cannot predict the effect of his manipulations on the plaintext, nor on the hash value. Upon reception, the message is deciphered and its content checked by comparing the received hash value with a hash that is created from the received message. Unfortunately, a computer is required to calculate the hash value, making this method of authentication impossible for a purely manual encryption.

Interestingly enough, regular old hash functions appear to be good enough for our information-theoretic security lover, despite the fact that information-theoretically secure MACs exist.

But what about cryptanalysis?

Cryptanalytic attacks may exist that can recover a key in less time then brute force. This does not imply that:

The space requirements of such attacks is practical
The time requirements of such attacks is practical (> 2 ** 100 == impractical)
The conditions required for the attack to function may not be realistic

For example/before anyone comments with "But related key attacks on AES-256!", consider the context and costs of that attack:

  There is a key owner; the key is KA
  and the attackers tries to guess it.
  The key owner can somehow be persuaded to compute three other keys KB
  , KC and KD, from KA, using a specific derivation algorithm (KB is equal to KA XORed with a constant that the attacker chooses; KC and KD
  use a more complex but equally deterministic derivation algorithm).
  Then, the attacker can make the key owner encrypt and decrypt arbitrary blocks -- that the attacker chooses -- with the keys KA
  , KB, KC and KD.
  The key owner will accept to process up to $2^{99.5}$ blocks (that's 16-byte blocks, hence a grand total of about 14 thousands of billions of billions of gigabytes).
  Finally, the attacker has access to some storage space of about one million of billions of gigabytes.

Did you see the part where the adversary can encrypt and decrypt 14 thousands of billions of billions of gigabytes under four different keys of their choosing? What exactly is your cipher protecting, in this scenario? Why does the adversary even need your key if they have access to a decryption oracle? Is this really a reasonable and practical scenario to be in? Would you really base your decision on which algorithm to use based off of an attack with these kind of requirements?

The point is that just using "the bottom line" where the author(s) consolidate all of their attack into a single measurement of time as the only gauge for security is too narrow of a perspective. Is an algorithm that is broken in time 2 ** 115 really less secure then an algorithm that requires time 2 ** 128 to break? Obviously in theory the correct answer to the question is "yes", but in practice both such attacks would take too long to execute and hence both would offer equivalent security as neither attack would ever be performed (we will ignore the argument that the hypothetical attacks could be improved).

  Am I misunderstanding something here that would allow widespread QKD and OTP to become practical for a large distributed consumer network? Or is the conclusion this article came to questionable as I suspected?

There are reasons to believe that the conclusion of the article is questionable. The author of the article basically claims that widespread QKD+OTP is needed, but does not appear to offer any constructive advice as to how to build such a future, nor any supporting evidence for why all of the rest of cryptography is apparently doomed.

Amidst all of the praise of the OTP, they completely neglect to mention how the algorithms that are used in practice (i.e. AES/ChaCha) succeed at providing security to the entire world on a regular basis, while the OTP in all of it's theoretically perfect glory has been broken in practice on multiple occasions.

The OTP and quantum cryptography are basically the opposite of practical cryptography. The more complicated the communication system is, the more vulnerable it will be to attack.

Adversaries will not target the strongest parts of the equation; Supposing you really did utilize QKD and OTP to secure your messages, they will simply wait for you to receive the messages then extract the information from you personally.

Either that or they will target/exploit some aspect of the implementation, because there is a difference between a theoretically secure algorithm and a secure implementation of that algorithm.


Why are protocols often proven secure under the random oracle model instead of a hash assumption? Is this true that whenever you design a protocol using a hash function, you must prove its security under the random oracle?

I mean, is it possible to devise a protocol $P$ using a function $H$, and then prove a theorem saying that $P$ is secure in a model $M$ given that $H$ is a collision-resistant function? What I most often see is some thing like: given a random oracle $H$, $P$ is secure in the model $M$.

Is this because it's more difficult or even impossible to prove security without the random oracles?

A random oracle is an idealization of a hash function $H$: if hash functions were perfect they would be random oracles. This is why it is always easier to consider a hash function a random oracle when one proves something about a larger scheme. Those are "proofs in the random oracle model". [1]

That being said it is still possible to prove things using different, weaker, assumptions about the hash function or even the compression function in the case of a MD hash function (collision resistance for example). Those are "proofs in the standard model"

Is it possible to go from one to the other? Not always since there are separations: there exists schemes that can be proven secure in the RO model that will become insecure as soon as you instanciate the RO by a real world hash function. [2]

Is it the end of the world? Not really, since we also have strong results that use the notion of Indifferentiability from RO: simply put, if your hash function is indifferentiable from a RO then you can replace your RO by your hash function and the scheme will remain secure. [3]

There are (as always) subtleties and what I've just said is not always true but this is good enough to make us feel more comfortable with our assumptions. [4]

Is this RO-indifferentiability just theoretical crypto stuff? No! I haven't checked for all of them but I know that Skein and Keccak 2 of the SHA-3 finalist come with proofs regarding that very property. I believe all of the finalist do. [5] [6]

[1] Random Oracle
[2] Impossibility result
[3] Indifferentiability framework
[4] Indifferentiability revisited
[5] Skein Proofs
[6] Sponge Proofs (keccak)

If you want you can start by reading the following:

http://en.wikipedia.org/wiki/Standard_model_%28cryptography%29
http://en.wikipedia.org/wiki/Random_oracle
http://blog.cryptographyengineering.com/2011/09/what-is-random-oracle-model-and-why.html


Possible ECC backdoor and its impact on Internet traffic In a recent article, Bruce Schneier suggested that he prefers classic discrete log crypto over ECC because "I no longer trust the constants. I believe the NSA has manipulated them through their relationships with industry."

Can someone elaborate on a case study what the above phrase would mean in the real world? Could a backdoored ECC allow the passive sniffing of HTTPS traffic that uses ECC for the ephemeral key?
Can someone explain the logic behind this fear?

If the NSA has chosen the elliptic curve parameters (the "constants") in a way that makes the elliptic curve cryptographically weak, then cryptography using that curve might be, well, insecure and breakable by the NSA.  For instance, it is known that there exist various classes of elliptic curves where the discrete log problem is easy (or not very hard).  If the NSA knows of an additional class of weak curves, and if they were able to influence the choice of parameters, it is plausible they could have chosen the parameters to make the curve weak.  Given that the NSA apparently spends $250 million per year on research, it is not implausible that they might know of classes of weak curves that are not known to the public community.

No one currently knows of a concrete, fully-worked-out way they could have done that with the NIST curves (for instance), but at the same time, no one knows of any proof or argument why this would be impossible.

In this scenario, if the curve is sufficiently weak, then it would let them mount passive attacks: by eavesdropping on traffic that is protected with ECC using those curves, they could break the ECC crypto and decrypt the traffic.  Hypothetically.  Yes, in this scenario, it could let them passively sniff HTTPS traffic that is using an ECC-based ciphersuite.  This is all terribly speculative, but you asked how it could happen, at least in principle.


Database sharing in Private Information Retrieval (PIR) Private information retrieval (PIR) protocols assume multiple parties have copies of a search database. How practical is this in real world?
(In more details the 'practical' term is: Will Google be ready to allow other independent search tools copy its database for such PIR? If Google allows, then I assume that there should be no loss in its business)

Information theoretic PIR protocols that have communication complexity less than the size of the database require multiple, non-cooperating servers [1]. In a computational setting, this is not required. So if you do not want to have to share your database with multiple servers, you should probably use a computational PIR protocol.

1. https://en.wikipedia.org/wiki/Private_information_retrieval#Advances_in_information_theoretic_PIR


AES key expansion: 256bit key In AES algorithm, in the key schedule,
Why does the expansion of a 256 bit key need an extra application of the S-box, unlike the expansion of 128 bit and 192 bit keys ?

(The obvious answer would be "because it is more secure" ... but why ? And if it is more secure, why don't use it on 128 and 192 ?)

It has to do with the alignment between the size of cipher the key and the size of a round key. Since a 256-bit key is twice the size of a round key, the nonlinearity of the key schedule would be aligned to every other block, and that is bad.

Here is an example of the round keys generated by the key schedule for a key (hex bytes) of value 0000000000000000000000000000000000000000000000000000000000000001:

00  00000000 00000000 00000000 00000000
01  00000000 00000000 00000000 01000000
02  637c6362 637c6362 637c6362 637c6362
03  fb10fbaa fb10fbaa fb10fbaa fa10fbaa
04  cf51a96f ac2dca0d cf51a96f ac2dca0d
05  6ac88f7d 91d874d7 6ac88f7d 90d874d7
06  c131c8f9 6d1c02f4 a24dab9b 0e606196
07  c11860ed 50c0143a 3a089b47 aad0ef90
08  a19db82e cc81bada 6ecc1141 60ac70d7
09  118931e3 414925d9 7b41be9e d191510e
10  0aa339ef c6228335 a8ee9274 c842e2a3
11  f9a5a9e9 b8ec8c30 c3ad32ae 123c63a0
12  ea6ad234 2c485101 84a6c375 4ce421d6
13  d0cc541f 6820d82f ab8dea81 b9b18921
14  173c1ad3 3b744bd2 bfd288a7 f336a971

And here is what happens when you take out the extra SubBytes:

00  00000000 00000000 00000000 00000000
01  00000000 00000000 00000000 01000000
02  637c6362 637c6362 637c6362 637c6362
03  637c6362 637c6362 637c6362 627c6362
04  c9d6739b aaaa10f9 c9d6739b aaaa10f9
05  c9d6739b aaaa10f9 c9d6739b abaa10f9
06  50b4df55 fa1ecfac 33c8bc37 9962acce
07  50b4df55 fa1ecfac 33c8bc37 9862acce
08  dbf275cc 21ecba60 12240657 8b46aa99
09  dbf275cc 21ecba60 12240657 8a46aa99
10  358c2f70 14609510 06449347 8d0239de
11  56f04c12 771cf672 6538f025 ef7e5abc
12  5053dcee 443349fe 4277dab9 cf75e367
13  9985af75 ee995907 8ba1a922 64dff39e
14  5b1042a3 1f230b5d 5d54d1e4 92213283

It can be seen as far as round 9 the round keys are still extremely linear, and because the sbox application is performed every other round key, 3 of the 4 subkeys for the round keys are identical to a neighboring round key up to the 9th round, and the 4th only differs by a 4 bit maximum.


Why should symmetric block cyphers be efficient? If I remember well, AES (then named Rijndael) won the competition because it was slightly faster to implement as one of its competitors, Serpent, which erred on the side of caution, using 32 rounds as where most probably, 16 rounds would have been sufficient.  In a way, the competition was rewarding "highest security per clock cycle" (way of speaking).  That was almost 2 decades ago, when computers were still much slower than today, so clock cycles were still expensive, and too heavy cryptographic burdens might make it hard to use on home computers.
However, today the problems of encryption are rather the large amounts of brute force that one can apply.  This is why one uses "inefficient" key derivation functions, to slow down brute force.

My question is: why doesn't this apply to block cyphers ?  Wouldn't it be a good idea to have "inefficient" and slow block cyphers ?  Wouldn't something like Serpent, but even with say, 4096 rounds, be preferable over an efficient algorithm like AES, so that it takes much more time to use in a brute force attack ?

Slowing block ciphers by increasing the number of rounds is an idea that does not catch because

Compared to 15 years ago, the volume of data routinely enciphered by a computer has grown much more than the frequency of its CPU (even multiplied by number of cores and IPC improvements). Hence speed of ciphers is more important than it ever was. Correspondingly, we see AES implemented in hardware (giving a huge speedup) or faster ciphers (like Chacha) increasingly used.
Increasing the number of rounds would only give the equivalent of a few bits more key in term of resistance to brute force; so if we want more resistance to brute force, we just use a wider key, and avoid a huge performance drop. For illustration: 4096 rounds instead of the regular 32 in Serpent makes brute force about 128 times harder, that's the equivalent of 7 extra bits of key (since 128 is 27); these few bits are negligible when AES candidates came in 128, 192 and 256-bit key size variants (going from 128 to 192 bits is an extra 64 bits, that is about 16 million million million times harder by brute force).

There are applications for slow cryptography: in particular password-based encryption, where a password is used as key of a cipher. In that application, we need something slow to mitigate the risk of brute force password search. But using a block cipher with many rounds would be very misguided, because for legitimate use one needs to make all the rounds for each block encrypted, when the attacker only needs to make all the rounds for the first block during most of the attack. Instead, what works best is making many rounds in an initial transformation from password to key (key streching), then using a regular (fast) cipher.

Rant: Sadly, many programs implement that poorly. For example, 7zip's AES encryption uses a fixed 1000 iterations of hashing (line 27 of WzAes.cpp there), leaving it needlessly vulnerable to brute force password search. Even GPG 1.x comes out of the box with insufficient settings for passphrase-to-key transformation as used to protect private keys at rest, and the following arcane settings beefing it up to the max are not entirely satisfying:

s2k-mode 3               # iterated hashing (that's the default)
s2k-count 65011712       # maximum supported number of iterations
s2k-digest-algo SHA512   # one of the slowest/widest hash supported
s2k-cipher-algo AES256   # no incentive to use a narrower key


MD5 Hash outputs not produced Are there any hash outputs not produced by the MD5 hash function? I need to use it as a placeholder for an empty hash while comparing two hashes.

Not provably. Maybe, since it's not a permutation, but you couldn't verify it practically.

Just use all-zeroes: it's easily recognizable as a null value, and thanks to pre-image resistance, no-one knows what hashes to that.


AES: Why is it a good practice to use only the first 16 bytes of a hash for encryption? I'd like to encrypt Text with AES/CTR and a password defined by the user in java. I already checked the internet (and stackoverflow) for answers. The most used version is to hash the user password with sha1 and take only the first 16 bytes.

But I don't think this can be a good practice.

sha1 is weak
taking only the first 16 bytes makes the hash also weak
and rise the chance for a collision (even with sha-256)

Is this really the best practice? Why? How can I do things better?

Some links to the articles I mentioned:

https://stackoverflow.com/questions/3451670/java-aes-and-using-my-own-key
https://howtodoinjava.com/security/java-aes-encryption-example/
https://blog.axxg.de/java-aes-verschluesselung-mit-beispiel/

Why is it a good practice to use only the first 16 bytes of a hash for encryption?

As you noted, it isn't.

But, the problem is not with the "16 bytes" part of the statement, or the concern for collisions. The problem is with the "hash" part.

16 bytes

As stated in one of the links you shared, AES only uses key sizes of 128, 192, and 256 bits (or 16, 24, and 32 bytes, respectively). So the key must be one of these sizes, because AES simply does not support other key sizes.

Trying to use a larger key could have a variety of possible outcomes depending on what the implementation chooses to do. It might raise an exception, or continue silently while only using the first N bits of the supplied key.

Hashing a password to use as an encryption key

Using a hash function such as MD5, SHA1, SHA2, SHA3, blake2, etc, would all be bad practice. The first two are obvious: MD5 and SHA1 are known to be weak in general.

But even using a strong cryptographic hash like SHA3 or blake2 would also be bad, because they were not designed to solve the problem of deriving a key from a password. Use of a cryptographic hash function is involved in this process, but it is not the entirety of it.

Good practice would be to use a dedicated key derivation function such as Argon2 that was designed to solve this problem. If your library doesn't support Argon2 but supports scrypt, bcrypt or PBKDF2, any of these three is also a reasonable choice.

Why/How

A normal hash function is designed to be fast and require little space.

A hash function designed for use on passwords is quite the opposite: it is a slow function that requires lots of memory access, in an attempt to try and optimize the function towards what a consumer CPU is good at, and minimize the potential for optimization with special hardware. Specialized hardware is usable by an attacker, but a legitimate user is limited to a commodity CPU; The goal is to try and use a function that cannot take advantage of special hardware to the extent possible.

Details about the hows and whys of password hashing are listed in this paper and quoted below (with minor modifications, e.g. removing citations and modified formatting):

  Cryptographic  Security: The  scheme  should be  cryptographically secure and  as  such possess the  following  properties:

  1) Preimage  resistance
  2) Second preimage resistance
  3) collision resistance.

  In addition it should avoid other cryptographic weaknesses such as those present in (some)Merkle-Damgård constructions(e.g. length extension attacks, partial message collisions, etc)

  Defense against lookup table /TMTOAttacks:

  The  scheme  should aim to make TMTO attacks that allow for precomputed lookup table generation, such as Rainbow Tables, infeasible

  Defense  against CPU-optimized 'crackers':

  The  scheme  should  be ‘CPU-hard’, that is, it should require significant amounts of CPU processing in a  manner that cannot be optimized away through either software or hardware. As such, cracking-optimized  (multi-core)  CPU  software  implementations (eg. written in assembly, testing  multiple input  sets  in parallel) should offer  only  minimal  speed-up  improvements  compared  to  those  intended  for validation (“slower for attackers, faster for defenders”).

  Defense against hardware-optimized 'crackers':

  The scheme  should be 'memory-hard', that is, it should significant amounts  of  RAM  capacity  in  a manner  that  cannot  be  optimized  away  through  eg. TMTO attacks. As such cracking-optimized ASIC, FPGA and GPU implementations should offer only minimal speed up improvements (eg. in terms of time-area product) compared  to  those  intended  for  validation. As  noted  by  Aumasson one of  the  main  scheme  design  challenges  is  ensuring  minimized  efficiency  on GPUs,  FPGAs  and  ASICs  (in  order  to  minimize  benefits  of  cracking-optimized  implementations)  and  maximized  efficiency  on  general-purpose CPUs (in order to maintain regular use efficiency).

  Defense  against  side-channel  attacks:

  Depending  on  the  use-case  (eg. for key derivation or authentication to a device seeking to protect against modification  by  the  device owner)  side-channel  attacks  might  be  a  relevant  avenue  of  attack.  Password  hashing  schemes  should  aim  to  offer  side-channel resilience. With regards to password hashing  scheme  security  we  will  focus on  security  versus  the cache-timing type  of  side-channel  attacks  given the existence of such attacks against the commonly used scrypt scheme. The  second category of side-channel  attacks  we  will take  into consideration are so-called Garbage Collector Attacks (GCAs). GCAs have been discussed in  literature as an instance of a 'memory leak' attack relevant to password hashing scheme security. GCAs consist of a scenario where an attacker has access to a target machine's internal memory either after termination of the hashing scheme or at some point where the password itself is still present in memory (the so-called WeakGCA variant)...


Is there only one formula for the statistical difference between a pair of distribution ensembles? Statistical closeness implies computational indistinguishability was recently posed.  It revolves around a numeric value $\Delta(n)$ of the statistical difference between a pair of distribution ensembles, as:-

$$ \Delta(n) = 1/2 \sum_{\alpha}|\mathbb{P}[X_n = \alpha] - \mathbb{P}[Y_n = \alpha]| $$

But statistical distances can also be measured via other techniques such as Pearson's chi-squared test, Kolmogorov-Smirnov & Anderson–Darling tests and Kullback–Leibler. There are many other exotic tests as well.  My four examples are non parametric tests too that produce a numeric test statistic. And they are also used in many aspects of cryptography.

Is the $\Delta(n)$ formula specific to cryptography, and if so, why?

What we call "statistical distance" in cryptography is called total variation distance by statisticians. So it certainly exists outside of cryptography.

I can't speak to its applications within statistics. But it certainly is the most natural metric for cryptography because it has an equivalent formulation in terms of distinguishing two source distributions given a sample, which is how we state many security properties. Restricting the distinguisher to be polynomial-time leads to natural and useful generalizations.


Is it safe to salt a MAC? Say that I define a scheme where the salt is public and is MAC-ed with the message:

$k = KDF(password, salt)$
$tag = MAC_k(salt || message)$

Is it safe to salt the MAC this way? Assume that the salt is public and can be modified by an attacker.

Safe, yes, but it doesn't really give you anything.  The only use for a salt is to mitigate precomputation attacks against a password.  Since it is public, it gives you no extra MAC security.  By the property of the MAC, no adversary can forge one without knowing the key, and by the security of your KDF (which includes the salt) no one should be able to get the key.  So, it is pretty much pointless.


Basic Encryption and Decryption related question I recently started studying cryptography and got interested in the subject. But I got this doubt when I was studying the encryption scheme. Even though we encrypt our message and change it into ciphertext, this ciphertext is still available to the attacker. So, what if the attacker modifies this ciphertext and sends it to the receiver? Then the receiver cannot decrypt the message right..?

For a block cipher

A block cipher is a PRP, a Pseudo Random Permutation. That is: given a key it generates a permutation of all possible plaintext blocks to all possible ciphertext blocks. So there is a bijection between each plaintext block and each ciphertext block, i.e. each possible plaintext block is assigned its own ciphertext block. So there is a 1:1 relation between the plaintext block and the ciphertext block given a specific key.

This doesn't of course happen in practice, this is just a mathematical description. Instead each plaintext block that is inserted into the block cipher gets transformed into a single ciphertext given a specific key. Without the key you cannot reverse this process (unless the cipher is broken). It is of course also impossible to retrieve the key from the plaintext and ciphertext. Decryption performs the reverse operation.

Now what happens if we change a bit in one of the ciphertexts? Well, you get another ciphertext, which in turn maps to a different plaintext. This plaintext can be any of the remaining $2^{128}$ plaintext. As all possible 128 bit plaintext are possible you get one block of random garbage. The cipher just reverses the mapping without checking that you get the wrong plaintext block!

Now this explains what happens with a block cipher. How the change is otherwise handled depends on the mode of operation that the block cipher is used for (ECB, CBC, CFB, CTR etc). If you introduce errors in the ciphertext you would have to look at the error propagation property of the mode of operation.

If the block cipher is CBC and padding is applied then an attacker may have enough information to perform a padding oracle attack. This means that the attacker can use the unpadding performed by the receiver to quickly and completely find all the plaintext from the message without breaking the block cipher. So in this case introducing a modification of the ciphertext may give the attacker enough power to find out all information about the message - full loss of confidentiality!

For stream ciphers

For stream ciphers (that generate a key stream) the situation is significantly easier. With a stream cipher (or OTP) changing a single bit in the ciphertext simply changes the bit at the same location in the plaintext.

Preventing modifications

Modification by an attacker can of course not be prevented by any algorithm. What is possible though is to add an authentication tag to the ciphertext. An authentication tag is usually computed using a Message Authentication Code or MAC. By verifying the MAC against the plaintext or ciphertext the receiver can detect if the integrity of the message is still intact.

Many new protocols, including TLS 1.3, use so called authenticated ciphers. Authenticated ciphers always create an authentication tag internally. So it should always be possible to verify that the ciphertext is not changed in transit.


What are the odds of collisions for a hash function with 256-bit output? There are some related questions on the net but I did not understand their solutions.

I am reading in a textbook about methods of finding a collision. It states  to consider a collision for a hash function with a 256-bit output size and writes if we pick random inputs and compute the hash values, that we'll find a collision with high probability and if we choose just $2^{130}$ + 1 inputs, it turns out that there is a 99.8% chance at least two inputs will collide. It also says we can find a collision by looking at roughly the square root of the number of possible output results.

Questions:

What is the formula used to calculate that if we choose $2^{130}$ + 1 input at least 2 inputs will collide with a 99.8% probability?

From my research it looks like this is related to the "birthday attack" problem, where you calculate first the probability that the hash inputs DO NOT collide and subtract this off from 1. Whenever I tried to plug and chug using the formulas I found online I wasn't getting the results the book stated.

Edit: I tried using the formula P(A) = 1 - $\frac{k!}{(k-n)!k^{n}}$ and obtained
99.99...%. I do not know how the authors obtained the percentage 99.8%. Can someone please state the explicit equation used, so I can see how the book gets the 99.8% probability of collisions with $2^{130}$ + 1  randomly chosen inputs? Where does the +1 come from?
How is the square root function related to this? If I take square root of 256, I get 16. What does this mean in the context of collisions?
The size of the output is 256 bits. Does this mean the total number of possible outputs is $2^{256}$?
Does the pigeonhole principle apply to this? You are taking an infinite amount of inputs and mapping them to a finite amount of outputs.

Birthday problem for cryptographic hashing, 101.

Let $p_n$ be the probability of collision for a number $n$ of random distinct inputs hashed to $k$ possible values (that is, probability that at least two hashes are identical), on the assumption that the hash is perfect. That $p_n$ is also the minimum probability of collision with no hypothesis on the hash.

Obviously, $p_0=p_1=0$ (until there are at least two hashes, no collision is possible); and $p_j=1$ if $j>k\;$ (by the pigeonhole principle, with more than $k$ pigeons for $k$ holes, at least one pigeon needs to share a hole with another).

Let $q_j=1-p_j\;$ be the probability of no collision for $j$ hashes, with $q_0=1$. When we add another hash after there was no collision among the previous $j$ hashes, the new hash has probability $\frac j k$ of matching one of the $j$ previous hashes (creating the first collision), and probability $1-\frac j k$ of not creating a collision. Hence the recurrence: $q_{j+1}=q_j\,\bigl(1-\frac j k\bigr)$. It comes the exact:
$$p_n=1-q_n\quad\text{with}\quad q_n=\;\prod_{j=0}^{n-1}{\Bigl(1-\frac j k\Bigr)}\;=\;{\frac{k!}{(k-n)!\;k^n}}$$

That is also $\displaystyle q_n\,=\,P(k,n)/k^n\,=\,C(k,n)\,n!/k^n\,=\,{k\choose n}\,\frac{n!}{k^n}$, where $P(k,n)$ is the number of permutations of $n$ things among $k$, and $C(k,n)={k\choose n}$ is the number of combinations of $n$ things among $k$ (beware that $k$ and $n$ are reversed in this answer compared to the linked references).

This is fine for low $k$ and $n$, but impractical for large values. With $n\ll k\,$, applying that for small $\epsilon>0$ it holds that $\log(1-\epsilon)\lessapprox-\epsilon\;$, we get
$$\log(q_n)\;=\;\sum_{j=0}^{n-1}{\log\Bigl(1-\frac j k\Bigr)}\;\lessapprox\;-\frac 1 k\sum_{j=0}^{n-1}j\;=\;{-\,\frac{n\,(n-1)}{2k}}$$

In summary we have exactly
$$
\begin{align*}
p_n=1-q_n&=1-\frac{k!}{(k-n)!\;k^n}&&=1-P(k,n)/k^n\\\\
&=1-{k\choose n}\,\frac{n!}{k^n}&&=1-C(k,n)\,n!/k^n
\end{align*}$$
and as fair approximations when the above is inconvenient
$$p_n=1-q_n\quad\text{with}\quad
\begin{align}
&q_n\lessapprox e^{-n\,(n-1)/(2k)}&\text{(assuming $n\ll k$)}\\
&q_n\approx e^{-n^2/(2k)}&\text{(additionally assuming large $n$)}
\end{align}$$

From this we can derive that for large $k$ as used in cryptography, or a $b$-bit hash (where $k=2^b)$, probability and odds of collision for $n$ random messages are approximately
$$
\def\alignedcolumn#1#2#3#4#5{\phantom{#1}\llap{#3}\mathrel{#4}\rlap{#5}\phantom{#2}}%
% Specify the widest expressions on the left-hand and right-hand sides.
\def\ncolumn{\alignedcolumn{1.177\sqrt k}{2^{b/2+0.236\ldots}}}%
\def\pncolumn{\alignedcolumn{1-e^{-1/2}}{00.0\%}}%
\def\oddscolumn{\alignedcolumn{}{11/17}}%
\begin{array}{c|c|c}
n&\text{$p_n$ of collision}&\text{odds of collision}\\
\hline
\ncolumn{\sqrt k}={2^{b/2}}&\pncolumn{1-e^{-1/2}}\approx{39.3\%}&\oddscolumn{}\approx{11/17}\\
\ncolumn{1.177\sqrt k}\approx{2^{b/2+0.236\ldots}}&\pncolumn{1/2}={50\%}&\oddscolumn{}{\phantom{=}}{\hphantom{1}1/1}\\
\ncolumn{1.414\sqrt k}\approx{2^{(b+1)/2}}&\pncolumn{1-e^{-1}}\approx{63.2\%}&\oddscolumn{}\approx{12/7}\\
\ncolumn{2\sqrt k}={2^{b/2+1}}&\pncolumn{1-e^{-2}}\approx{86.5\%}&\oddscolumn{}\approx{19/3}
\end{array}
$$

The applied cryptographer is often interested in very low probability of collision $p_n$, as occurring for $n\ll\sqrt k$. The above approximation remains mathematically valid and usable for $q_j$, but can give inaccurate results for $p_j=1-q_j$ because the difference is orders of magnitude smaller than either term in the subtraction. We need another method.

Observe there's a collision when the $i$th hash equals the $j$th hash, for any pair $(i,j)$ with $1\le i<j\le n\;$; and for each of such $n(n-1)/2$ pairs, there is probability $1/k$ of a collision. Probabilities for such $n(n-1)/2$ events are not quite independent, but for low overall probability of collision this remains a valid approximation, as well as approximating very low probability that any of multiple events occurs to the sum of the probabilities of each event. We get these approximations
$$\begin{align*}p_n&\lessapprox{\frac{n\;(n-1)}{2k}}&\text{(assuming $n\ll\sqrt k$)}\\
&\lessapprox{\frac{n^2}{2k}}&\text{(additionally assuming large $n$)}\end{align*}$$

For example, with $n=2^{100}$ distinct random inputs (hypothetically) hashed to $b=256$ bits with a perfect (or even passable) hash, probability of collision is about $2^{2\cdot100-1-256}=2^{-57}$ (less than 8 chances in a million million millions, which can safely be discounted).

In the question, we have a hash with $b=256$-bit, that can thus take $k=2^b=2^{256}$ output values, and $n=2^{130}+1\;$. Here $k$ is large, $n\ll k$ and $n\not\ll\sqrt k$, therefore the appropriate formulas are

$$p_n=1-q_n\quad\text{with}\quad q_n\approx e^{-n^2/(2k)}\quad\text{(assuming large $k$ and $n\ll k$)}$$

The $+1$ term in $n=2^{130}+1$ is negligible, and we get $-n^2/(2k)\approx-\left(2^{130}\right)^2/\left(2\cdot2^{256}\right)=-2^{2\cdot130-1-256}=-2^3=-8\;$, giving $q_n\approx e^{-8}\approx0.034\%$ and $p_n\approx99.966\%\;$.

Notes: $n\approx2^{130}$ is so large that it is practically impossible to carry that number of operations, much less hashes. The question's body, and the present answer, thus does not contain anything that could help practically towards finding collisions for a hash function with a 256-bit output size (as in the question's original title).
The approximations 99.8% and 99.99% in the question are incorrect in their last digit, whatever the rounding convention.


Are all stream-ciphers IND-CPA? A stream cipher usually generates a stream of pseudo-random bits which get XORed with the plaintext to form the ciphertext. The stream is generated using a given IV / nonce and a secret key. CTR-mode for block ciphers is usually described as turning a block cipher into a stream cipher.

It is now widely known that the CTR-mode of operation provides IND-CPA security. Katz proves this in his book.

Does this result imply that all stream ciphers are IND-CPA?

No.

There is a difference between the type of a cipher and the construction of a cipher. If a cipher is of a specific type for which there are known IND-CPA secure constructions then that doesn't mean that an entirely different construction is secure. There are known attacks on stream ciphers, including "modern" stream ciphers such as RC4.

A stream cipher must be used correctly for the encryption scheme to be IND-CPA secure.

If the generated key stream is secure then the XOR of the plaintext with the key stream will of course also be secure (up to the specified limits of the stream cipher anyway).


What is Attribute Based Encryption? Can someone explain what attribute based encryption is?

I was searching for a book or something that can help me in this regard but so far I have found none. Google also returns practically nothing aside from the papers.

I try to provide a brief intro.

ABE

Attribute-based encryption (ABE) is a relatively recent approach that reconsiders the concept of public-key cryptography. In traditional public-key cryptography, a message is encrypted for a specific receiver using the receiver’s public-key. Identity-based cryptography and in particular identity-based encryption (IBE) changed the traditional understanding of public-key cryptography by allowing the public-key to be an arbitrary string, e.g., the email address of the receiver. ABE goes one step further and defines the identity not atomic but as a set of attributes, e.g., roles, and messages can be encrypted with respect to subsets of attributes (key-policy ABE - KP-ABE) or policies defined over a set of attributes (ciphertext-policy ABE - CP-ABE). The key issue is, that  someone should only be able to decrypt a ciphertext if the person holds a key for "matching attributes" (more below) where user keys are always issued by some trusted party.

Ciphertext-Policy ABE

In ciphertext-policy attribute-based encryption (CP-ABE) a user’s private-key is associated with a set of attributes and a ciphertext specifies an access policy over a defined universe of attributes within the system. A user will be ale to decrypt a ciphertext, if and only if his attributes satisfy the policy of the respective ciphertext. Policies may be defined over attributes using conjunctions, disjunctions and $(k,n)$-threshold gates, i.e., $k$ out of $n$ attributes have to be present (there may also be non-monotone access policies with additional negations and meanwhile there are also constructions for policies defined as arbitrary circuits). For instance, let us assume that the universe of attributes is defined to be $\{A,B,C,D\}$ and user 1 receives a key to attributes $\{A,B\}$ and user 2 to attribute $\{D\}$. If a ciphertext is encrypted with respect to the policy $(A \wedge C) \vee D$, then user 2 will be able to decrypt, while user 1 will not be able to decrypt.

CP-ABE thus allows to realize implicit authorization, i.e., authorization is included into the encrypted data and only people who satisfy the associated policy can decrypt data. Another nice features is, that users can obtain their private keys after data has been encrypted with respect to policies. So data can be encrypted without knowledge of the actual set of users that will be able to decrypt, but only specifying the policy which allows to decrypt. Any future users that will be given a key with respect to attributes such that the policy can be satisfied will then be able to decrypt the data.

Key-Policy ABE

KP-ABE is the dual to CP-ABE in the sense that an access policy is encoded into the users secret key, e.g., $(A \wedge C) \vee D$, and a ciphertext is computed with respect to a set of attributes, e.g., $\{A,B\}$. In this example the user would not be able to decrypt the ciphertext but would for instance be able to decrypt a ciphertext with respect to $\{A,C\}$.

An important property which has to be achieved by both, CP- and KP-ABE is called collusion resistance. This basically means that it should not be possible for distinct users to "pool" their secret keys such that they could together decrypt a ciphertext that neither of them could decrypt on their own (which is achieved by independently randomizing users' secret keys).

Beyond ABE

ABE is just one type of the more general concept of functional encryption (FE) covering IBE, ABE and many other concepts such as inner product or hidden vector encryption (yielding e.g., searchable encryption) etc. It is a very active and young field of research and has many interesting applications (in particular in the field of cloud computing).


Dancing confusion with Daniel J. Bernstein's stream ciphers I know of Salsa20 which won the ESTREAM competition. This is dated of 25 Dec 2007.

There is also the ChaCha20 stream cipher (cr.yp.to/chacha.html). This claims to increase the amount of diffusion per round. This is dated 28 Jan 2008.

Then there is another variant called XSalsa20 which has a 192 bit nonce instead of 64 bits. This is dated 4 Feb 2011. I'm not sure if it contains the diffusion per round improvements from ChaCha20 though.

Question is, which variant of these is the most secure to use? I do not care about speed. It would be really nice if cryptographers would just number their cipher versions/improvements as 1.0, 1.1, 1.2 so people know which is the latest algorithm easily.

On one hand, a 192 bit nonce with XSalsa20 sounds more secure than a 64 bit one. Maybe someone can explain the advantage of that? Would there be an advantage in using a 256 bit nonce which would keep it consistent with the key size? On the other hand, the better diffusion per round of ChaCha20 sounds like a good thing to have as well compared to the original Salsa20. Could a combination of the improvements in XSalsa20 and ChaCha20 be made?

XSalsa20 uses the same cryptographic core as Salsa20 and comes with a security proof that it's secure if Salsa20 is secure. It doesn't use the core of ChaCha and thus has worse diffusion.

The way XSalsa20 works is that it hashes its 256 bit key and the first 128 bits of the nonce using HSalsa down to a 256 bit key and then uses that key together with the remaining 64 bits of the nonce in Salsa20. You can find the details in the paper Extending the Salsa20 nonce.

The problem with nonces is that you must be sure that you never reuse one. With a 64 bit nonce a counter works well, but a counter is stateful. If you want a stateless nonce, the usual approach is to generate a random one, and assume that collisions are sufficiently unlikely to happen. Assuming uniqueness with a random 128 bit value is pretty safe, but with a random 64 bit value collisions become likely even with a moderate number of messages. So you can't use random 64 bit nonces. But if you have a 192 bit nonce, you can randomize it.

Thus the increased nonce size isn't a security improvement, but a feature that allows random nonces.

In principle it's possible to use the same nonce extension technique with ChaCha, but Bernstein didn't publish a specification. In my answer to Can I use the ChaCha core as a 256-bit to 256-bit one-way function? I describe how to construct HChaCha from ChaCha, in the same way HSalsa20 was built from Salsa20. Combining HChaCha and ChaCha into XChaCha is straightforward.


Is message integrity possible without confidentiality? Are there any mainstream protocols? I understand that many schemes that provide data integrity involve a hash-then-encrypt approach. I was wondering if data integrity is achievable without confidentiality? Are there any mainstream protocols for this?

Hash-then-encrypt is not a scheme that is used a lot. It may not be necessarily secure in all situations.

Instead message authentication codes (MAC) are used. These produce what is called an authentication tag (symbol: $t$); a fixed size, keyed hash over the processed data. Obviously, as a keyed hash it requires a key as input, preferably one specific for the MAC.

MAC can be split into hashes that are based on block ciphers or hashes. An example of a MAC is AES-CMAC; it is based on AES in CBC mode but it doesn't encrypt the plaintext (the intermediate ciphertext is not kept). It makes sense to use a block cipher based MAC if the block cipher - usually AES - can be used with hardware acceleration.

HMAC - which simply stands for Hash-based MAC - can be used with MD5, SHA-1 and SHA-2 as underlaying hash construct. As SHA-3 is already protected against length extension attacks it can be used with a more elegant approach called KMAC.

Nowadays authenticated ciphers such as AES-GMAC are becoming popular. Authenticated ciphers are usually AEAD ciphers: ciphers providing Authenticated Encryption with Associated Data. The associated data (AD) or additional authenticated data (AAD) within these schemes is also integrity protected and not encrypted.

This way you can decide yourself what data you want to keep confidential. If you want you can put everything in the AD, so you would not have any ciphertext, only plaintext and the authentication tag.

Usually you only need to provide a single key which can be used for both confidentiality and authenticity, simplifying key management somewhat.

Notes:

You may require additional constructs such as a message counter or session keys for each sending entity to create a secure protocol; just having a MAC or authenticated cipher may not be enough.
Most cryptographers agree that encrypt-then-MAC is more secure than MAC-then-encrypt in most situations, so please keep that in mind if you do need to keep part of the data confidential.
When in doubt: use HMAC; it's the most common MAC, it has aged really well and provides lots of security. HMAC-SHA-256 - HMAC with SHA-256 as underlying hash algorithm (configuration parameter) is a good, secure, generally available algorithm. If you think a 32 byte tag is a bit too large you can just the 16 leftmost bytes instead.


How does Scrypt use Salsa? Bcrypt uses Blowfish to encrypt a derived key from the passphrase, and Blowfish is a cryptographic algorithm, but here it is said  that:

  Note that
     Salsa20/8 Core is not a cryptographic hash function since it is not
     collision-resistant.

so how this is useful in Scrypt?

Salsa20/8 is used not to enhance cryptographic strength, but to make random-ordered requests to the RAM (and to slower FPGA/ASIC implementation of scrypt). The scrypt uses PBKDF2-HMAC-SHA-256 (PBKDF2 of HMAC-SHA256) to provide such strength.

There is simple variant of scrypt, with parameters p=1 (Parallelization parameter), N=16384, r=8, taken from linked draft and simplified for p=1:

Algorithm scrypt

Input:
        P       Passphrase, an octet string.
        S       Salt, an octet string.
        N       CPU/Memory cost parameter, must be larger than 1,
                a power of 2 and less than 2^(128 * r / 8).
        r       Block size parameter.
        p       Parallelization parameter, a positive integer
                less than or equal to ((2^32-1) * hLen) / MFLen
                where hLen is 32 and MFlen is 128 * r.
        dkLen   Intended output length in octets of the derived
                key; a positive integer less than or equal to
                (2^32 - 1) * hLen where hLen is 32.

Output:
        DK      Derived key, of length dkLen octets.

Steps:

 1. B[0] = PBKDF2-HMAC-SHA256 (P, S, 1, 128 * r)

 2. B[0] = scryptROMix (r, B[0], N)

 3. DK = PBKDF2-HMAC-SHA256 (P, B[0], 1, dkLen)

We can see that there are two PBKDF2 with HMAC SHA256, one before ROMix and one after. They will provide collision resistance for the scrypt.

And here is the scryptROMix, which uses N-sized array, every element of which is equal to scryptBlockMix of previous element (step 2). Salsa is used inside scryptBlockMix and in scryptROMix it defines both transformations of X and the order of read accesses to V array:

Algorithm scryptROMix

Input:
        r       Block size parameter.
        B       Input octet vector of length 128 * r octets.
        N       CPU/Memory cost parameter, must be larger than 1,
                a power of 2 and less than 2^(128 * r / 8).

Output:
        B'      Output octet vector of length 128 * r octets.

Steps:

 1. X = B

 2. for i = 0 to N - 1 do
      V[i] = X
      X = scryptBlockMix (X)
    end for

 3. for i = 0 to N - 1 do
      j = Integerify (X) mod N
             where Integerify (B[0] ... B[2 * r - 1]) is defined
             as the result of interpreting B[2 * r - 1] as a
             little-endian integer.
      T = X xor V[j]
      X = scryptBlockMix (T)
    end for

 4. B' = X


Solving the discrete logarithm problem for a weak group I was reading an answer about an attack on a weak group for the discrete logarithm problem and wanted to formalize and verify that the attack was correct. That is, that it was guaranteed to always find $x$ (and quickly) given $g$, $h$, and $p$ for $h \equiv g^x \pmod p$. Please read the answer here. In the process I think I found a mistake on the author's part, but figured out how to quickly solve the problem anyway. A number of other questions came up in the process that I'll ask below.

I'll start by proving the first assumption of the attack. How do we know $\forall i: \exists x_i: g^{x_i} \equiv h \pmod {a_i}$?

We know $a_i | p$. Let $b_i = p / a_i$. We also know $g^{x} = py + h$ for some $y \in \mathbb N$. This implies $g^{x} = a_i \cdot b_i \cdot y + h$, so $g^x \equiv a_i \cdot b_i \cdot y + h\equiv h \pmod {a_i}$. Thus, $x$ satisfies $x_i$ in the equation above, so $\forall i$ there is at least one solution and $x \equiv x_i \pmod {a_i}$.

How do we most efficiently compute the $x_i$?

It seems like according to these records listed on Wikipedia that a number field sieve algorithm will be the fastest since these are fields of form $(\mathbb Z / p \mathbb Z)^\times$, $p$ prime, and that's what the records are for. On the other hand, it must be faster, even for the best implementation of this algorithm to simply do trial multiplication until $p$ is at least so large.

How do we know that $\exists x': \forall i: x' \equiv x_i \pmod {\phi(a_i)}$?

Now, the author suggests using the Chinese Remainder Theorem (CRT), but because the $\phi(a_i)$ are not pairwise coprime (in particular, $2$ is a divisor for each $\phi(a_i)$), this doesn't follow. This really threw me off because for a while I was trying to prove that such an $x'$ existed, and was trying to understand how the group order of each cyclic subgroup was relevant to finding $x$.

If you think can explain where the author may have been going, please let me know.

What we're actually looking for is a $x'$ such that $x' \equiv x_i \pmod {a_i}$ holds $\forall i$. By the CRT we know that such a $x'$ exists, and is unique (up its residue modulo $p$). Thus we know $x' \equiv x \pmod p$.

Now we just need to efficiently compute $x'$.

How do we efficiently compute $x$ that satisfies the $x \equiv x_i \pmod {a_i}$ equivalences?

Again, reading from Wikipedia it lists solving the equivalences for the first two moduli using the extended Euclidean algorithm and Bézout's identity, followed by extending the solution to all equations as the fastest way to solve this. Will any optimized algorithm, in general or in particular, such as a number field sieve or the Pollard rho method work faster than the two steps listed above? That is when the group is "weak" (or when it is "weak" in this particular way being a composite of many small primes) is there such an algorithm that will always work faster and implicitly take advantages of the weaknesses?

Am I missing any important ideas? Is there a more illuminating way to explain anything I did above?

The question is about making wonky DH parameters for which discrete logarithm is super-easy to solve. Thus, somebody suggests the following:

Let the modulus $p$ be the product of all small primes from $3$ to some value such that $p$ is adequately large. In this case, we consider the product of all primes from $3$ to $1471$; there are $232$ such primes, and their product is a $2046$-bit integer.

We now have a $y = g^x \bmod p$, for known values $y$ and $g$, and unknown $x$. The task at hand is to find $x$, or at least one value $x$ that matches the equation. There may be several (this is the common case; the algorithm below will usually find a much smaller solution than the original $x$). Crucially, we assume that there is a solution, i.e. that $y$ was obtained by choosing a (random) value $x$ and then computing the modular exponentiation.

Let's called $p_i$ the small primes. Let's define:
\begin{eqnarray}
  g_i &=& g \bmod p_i \\
  y_i &=& y \bmod p_i \\
\end{eqnarray}

The Chinese Remainder Theorem basically tells us that whatever happens modulo $p$ also happens modulo each of the small primes $p_i$, and back; said otherwise, if we can find a $x$ such that $g_i^x = y_i \bmod p_i$ for all $232$ values of $i$, then $x$ is a solution. Note that it is about using the same value $x$ modulo each prime $p_i$.

We now consider each small equation $g_i^x = y_i \bmod p_i$. There are two sub-cases:

$g_i = 0 \bmod p_i$. In that case, $y_i$ must be 0 \bmod $p_i$ (otherwise there would be no solution, and by definition we assume there is at least one); and any value $x$ works here.
$g_i$ is invertible modulo $p_i$ and has a definite multiplicative order $n_i$ which is a divisor of $\phi(p_i) = p_i - 1$. There again, since we assumed the existence of a solution, $y_i$ must be part of the group generated by $g_i$ modulo $p_i$. There is then exactly one value $x_i$ modulo $n_i$ that matches the equation. Since $p_i$ is small (our largest small prime $p_i$), the value $x_i$ can be obtained with the dumbest of brute force, i.e. trying values $0$, $1$, $2$... until $g_i^{x_i} = y_i \bmod p$ is satisfied.

Thus, we end up with a number of values $x_i$. We know that $x = x_i \bmod n_i$ (for all $i$ that match sub-case 2). By the magic of the CRT, this works both ways: if we find a value $x$ such that $x = x_i \bmod n_i$, then it will be a solution to $g^x = y \bmod p$.

Now, each $n_i$ is itself a product of small primes, which can easily be found (the largest $n_i$ is not greater than $1470$ since $n_i$ divides $\phi(p_i) = p_i - 1$). In general, we can write:
$$ n_i = \prod p_j^{a_{i,j}} $$
i.e. $n_i$ is a product of powers of small prime powers.

Let's look at these small primes. For each $p_j$, there will be one of the $n_i$ which maximizes $a_{i,j}$. In other words, we define:
$$ b_j = \max\{ a_{i,j} \} $$
We can then extract some information from the corresponding equation, i.e. we can define $d_j = x_i \bmod p_j^{b_j}$ for the value $x_i$ such that $n_i$ is a multiple of $p_j^{b_j}$ (there may be multiple matching $n_i$, but, by the assumption that there is a solution, they must all agree).

We now have a bunch of prime powers $p_j^{b_j}$, for distinct small primes $p_j$, and equations $x = d_j \bmod p_j^{b_j}$. Since we took care to maximize the $b_j$, the equations are sufficient: any $x$ that matches all of them will be a solution to the original DL problem. And since all the $p_j^{b_j}$ are prime to each other, the CRT applies without any further issue.

The tricky part in this description is that we have two distinct domains in which we use the CRT: one is modulo the small primes $p_i$, the other is in the exponents, which work modulo each order $n_i$. Note that the $n_i$ are not necessarily prime to each other, which is why we have to factorize them all and find the largest prime powers.

Less talk, more code! I wrote a C# implementation of the algorithm above. Main file is EasyDL.cs, that follows the steps above. It uses a generic big-integer implementation that I wrote previously, ZInt.cs. This is easily compiled on a Linux machine with Mono (install package mono-devel on a Ubuntu system):

mono-csc EasyDL.cs ZInt.cs

This produces EasyDL.exe, which can be executed with Mono:

mono EasyDL.exe

On a Windows machine, use the command-line compiler csc.exe, which is typically in C:\Windows\Microsoft.NET\Framework64\v4.0.30319\ (assuming a Windows 8+ machine in 64-bit mode; the code should work also with older .NET versions such as 3.5).

When executed, the program:

rebuilds the modulus $p$ as a product of small primes;
generates random $g$ and $x$, and computes $y = g^x \bmod p$;
applies the algorithm above to recompute a solution $s$ such that $y = g^s \bmod p$.

Values are printed out in hexadecimal.


DES hardware implementation of substitution lookup table [ ReWorked ] I'm a crypto enthusiastic and student of cryptography.
I'm developing a project with other students titled "A hardware implementation of a DES cryptography for educational purposes", our idea was to make a simple version of DES encryption in a piece of hardware to help students that are learning cryptography understand better how this complex encryption method is implemented in hardware.

First, we started the system with an input of 8 bits to simplify the complexity and save space. Them, we created all the parts of DES cryptosystem (Initial Permutation, Feistel, XOR, Final Permutation).

Here is a image of our main system:

One of the important parts of the system is the Feistel Function. The Feistel part were divided in 4 parts, Expansion, Mixing, Substitution, Permutation.
Each of these parts are implemented as following:

The expansion CI just take the bits and duplicate them putting the new bit in the adjacent output, this CI receive 4 bits of the right part of the input and outputs 8 bits. Mixing just take the first bit of the output of expansion and XOR with the first bit of the key(8 bits) and so on... the output is 8 bits.
Now we have the most important part and the part that I personally think we're missing something.
The Substitution in witch is the S-Box, this CI has an 8 bits input and these 8 bits are divided in two parts(because we developed only 4 bits S-Boxes) these parts enter the S-Box and the S-Box output is of 2 bits, when you see the S-boxes of DES, all of them uses a lookup table, we've the idea of using the Karnaught map for implementing this table.

Our table :

And here is where we stopped, because we implemented all of this and had fail results like this:

The S-Box works like a lookup table on software but the system does not work, is there any specific way that these look up tables are created ? We couldn't see any pattern in the outputs of the table, do you guys have any material to help us ? I feel like this is the last thing to work on.

Thank you for reading it all. Please leave a comment! :)
Thank you again!

A simple way to think of the S-boxes of DES when it comes to a hardware implementation is: 8 independent ROM ICs, each with 6 address input lines and 4 data out lines. In an educational physical implementation with retro standard ICs, two such ROMs fit a 4 kiB EPROM (a 2732). Some actual software implementations of DES do group S-boxes two by two in order to reduce the number of table lookups.

Another way is: 8 times, 4 independent boolean functions of the same 6 input bits; for a total of 32 independent boolean functions of 6 input bits out of 48 input bits (which themselves come from the key, with a wiring dependent on the round and if we are enciphering or deciphering). It is well known how to build any boolean function of 6 input bits (e.g. using Karnaugh maps), hence in principle build these 32 boolean functions. However Karnaugh maps do not yield efficient/compact circuits in the case of DES S-boxes.

There is little exploitable regularity in the DES S-box functions. The most striking one is that each line of numbers of the spec of the S-box values (FIPS 46-3 appendix 1) is a permutation of $\{0\dots15\}$.
It follows that we can model each of the 32 boolean functions by: 4 functions of 4 input bits (coding columns on that spec) set for precisely 8 out of 16 combination of these 4 inputs, followed by selection of the appropriate of the 4 results of these 4 functions according to 2 other input bits (coding line in the S-box).
This translates into a trivial systematic construction of the functions using NAND gates with at most 8 inputs, of depth 3 (including input inverters) plus the final 1-out-of-4 multiplexer stage.
Using this structure, it is very easy to fit two S-boxes in a generic PAL with 12 inputs plus internal feedback and 10 outputs, at least 8 of which having at least 8 input terms. The once-popular PALCE22V10 is ample.

The problem of minimizing the complexity of these 32 functions, including considering that they are evaluated together and some work can be shared among the 4 functions belonging to the same S-box, has been extensively studied; for example by Matthew Kwan: Reducing the Gate Count of Bitslice DES, 2000, eprint 2000/051; however he is focusing on 2-input gates and considers XOR of unity cost, which is fine for software, but hardware has different constraints.


Should I use ECB or CBC encryption mode for my block cipher? Can someone tell me which mode out of ECB and CBC is better, and how to decide which mode to use? Are there any other modes which are better?

The really simple explanation for the difference between the two is this:

ECB (electronic code book) is basically raw cipher. For each block of input, you encrypt the block and get some output. The problem with this transform is that any resident properties of the plaintext might well show up in the ciphertext – possibly not as clearly – that's what blocks and key schedules are supposed to protect againt, but analyzing the patterns you may be able to deduce properties that you otherwise thought were hidden.
CBC mode is short for cipher block chaining. You have an initialization vector which you XOR the first block of plaintext against. You then encrypt that block of plaintext. The next block of plaintext is xor'd against the last encrypted block before you encrypt this block.

(Public domain image from Wikimedia Commons.)

The advantages of CBC over ECB are many – with ECB, assuming many things, you could manage a partial decryption and easily fill in the blanks, for example if extracting data from an encrypted hard disk. With CBC, if you are missing a few blocks in the sequence encryption becomes impossible. However, there is one downside to CBC – ECB naturally supports operation in parallel since each block can be encrypted independently of the next. However, with CBC this is harder, since you have to wait on each block. (You can still parallelize decryption, though.)

CBC itself can also be considered vulnerable in certain situations, specifically the use of predictable IVs and unauthenticated decryption can allow you to guess plaintexts as explained in this answer and in more detail here.

The IV problem is resolved by using unpredictable (cryptographically random) IVs. The authentication problem is traditionally resolved using message authentication codes - however, implementation of these is not perfect. Dedicated modes have been invented which tackle the issue of authentication too, for example EAX and Galois Counter Mode.

Other modes exist to deal with specific scenarios, e.g.:

Counter Mode uses the fact that a block cipher's output in ECB mode should be indistinguishable from random, and XOR's the result of encrypting a counter+iv combination as a stream cipher.
XTS is a mode of operation used in disk encryption.

The key point to take away is that each mode has a number of merits and implementation concerns and these must be weighed up carefully (and correctly implemented). And, where possible, avoid ECB.

Expanded explanation for how resident properties propagate into ciphertext with ECB

When writing this answer, I tried to not post a picture of the typical ECB-encrypted linux penguin, but I've been asked to expand on "resident properties in the plaintext" so what follows will be the same idea, just in text form. If you don't need it, feel free to skip.

Firstly, let's use a format I know something about - the mp3 frame. Like most plaintext this is far from "indistinguishable from random" - indeed for example, the MP3 frame header begins with 11 bits set to 1.

There are two important properties of block ciphers:

On a block level, operations are deterministic. If I encrypt "Cryptography Stack Exchange" and this fits in a single block, I expect to get the same output for given parameters every time. This sounds like a crazy critera (of course we need this) but it's worth highlighting.
On a block level, the output is indistinguishable from random - more formally there's no advantage for an attacker over using a random permutation, at least in a way that is realistically computable. My terminology might be a bit off because I am self taught, but I believe if the advantage is non-zero you've got a bias and this makes the cipher a candidate for linear cryptanalysis.

These statements apply considering only a single block; however obviously in the real world we want more than that - we want to encrypt multiple blocks.

Suppose we live in an imaginary world where people think block ciphers with a block size of one byte are a good idea. Now let's imagine this is otherwise a totally fine block cipher. Now imagine you have some MP3s of Justin Bieber music and you'd very much like the NSA not to find out about this. So you take your block cipher and you encrypt your MP3.

Now, one of those blocks, making some assumptions about file alignment, is going to be 0xFF - that's 8 of your 11 ones from the frame header in the MP3. These are always there at the beginning of each frame. Now our cipher is indistinguishable from random so we get perfectly random ciphertext, say 0x1c. But it is also deterministic and we're using ECB, so every frame header that was 0xFF becomes 0x1c.

All of a sudden we're giving away information to our attacker - specifically they can deduce where the frame headers are if they suspect this to be an MP3. Cryptanalysis is sometimes about guessing correctly and a correct guess in this case will give them an idea of exactly how long the audio samples are and allow them to identify the format.

Moreover, every other ciphertext block 0x1c is now decodable too. That's not information we intended to give away, but we did.

This problem is common particularly when you consider much of what we encrypt has a rigid data format. You have to make some assumptions about alignment on the blocks, but the larger the data the more this problem becomes apparent.

This is what I mean by residual plaintext properties becoming evident in the ciphertext. These are the structure inherent to and wanted in the plaintext that inadvertedly become exposed to the attacker.

The original purpose of CBC mode was as a form of identifying corrupt messages and the security of CBC for this purpose is treated in this paper. I can't find the original realization of this idea in terms of papers, but you might be able to find it. Certainly most books on block ciphers that I have read mention it and other issues.


Best method of converting a private key string into a 12 word mnemonic? Is there a method of converting a Bitcoin private key into a 12 word mnemonic seed out of a 1000-2000 word dictionary? I couldn't think of a good way of solving this.

BIP 39 describes the implementation of a mnemonic code or mnemonic sentence -- a group of easy to remember words -- for the generation of deterministic wallets.

Bitcoin private key is not stored in this way, rather seed to prng which generated the private and public key pair is converted into mnemonic so that its easy for human to type or remember.

A list of 2048 words, which is indexed from 0-2047(11 bit information) is used. 132 bit value (128 bit seed + 4 bit checksum) is divided into 12 chunks of 11 bits each, then each 11 bit is used to select a word from dictionary.

for more details see BIP39


Is there value in performing signature during key exchange? I looked around the net, however I couldn't see anything authoritative on this.

If one is using something like libsodium to perform key exchange (using x25519), is there value in using Ed25519/signature, to sign the public keys being exchanged for use in the key agreement scheme (assuming the ed25519 keys are correctly tied to an entities identity)?

Or is this over-engineering?

I have static keyPairs tied to user identity in my app, and see some value in signature despite the extra effort to sign public keys being exchanged during symmetric key agreement.

As for the first question: as long as you create a signature over some or all data that is required and unique in the key establishment protocol then you should get entity authentication for that session. If you sign entire messages then you may be able to avoid some attacks on the message format itself. Some protocols deliberately include the public key into that calculation, others don't. Including the public key is not strictly required of course, you can also sign over a nonce used in the protocol or even over the shared secret (although I would seriously frown on the latter, as you don't want to use the key material for anything other than what it should be used for).

I'd also make sure that the established secret is correct by validating the generated secret (derive a MAC key and use that to create a MAC over some or all data unique to the session); you don't want to be relying on the messages themselves (implicit authentication) to verify the data and shared secret, use explicit authentication instead. It might be a good idea to start hashing the messages immediately and perform the signing / MAC'-ing over the calculated hash for maximum efficiency.

Yes, you can achieve forward secrecy with libsodium, if - as always - you make sure you destroy the keys as soon as they are not needed anymore. Just performing ephemeral-static DH - using whatever scheme - doesn't cut it, as you must make sure that the key material is not available anymore. Fortunately, Daniel is known for trying to make his protocol implementations in such a way that key destruction is easy.


What is the encoding protocol for passphrase protected RSA private keys? What is the protocol used to encode an RSA key protected with a passphrase?

If I generate an RSA key with

ssh-keygen -t rsa -b 4096

and do:

head ~/.ssh/id_rsa

I get:

-----BEGIN RSA PRIVATE KEY-----
Proc-Type: 4,ENCRYPTED
DEK-Info: AES-128-CBC,83F1F6710FBD0610A70A04F5ABDE4114

<base64 data>

What encoding protocol does this use?

For RSA private keys not protected by a passphrase, they are encoded in Base64 ASN.1 and the structure is documented here: https://tools.ietf.org/html/rfc8017#appendix-A.1.2

This file format, which is used by OpenSSH below 7.8 by default for RSA, is actually defined and implemented by OpenSSL, which documents it fairly tersely on the man page for a group of library routines including PEM_write_RSAPrivateKey near the bottom at the heading "PEM ENCRYPTION FORMAT". Quoting for convenience and because of many Stack-ers' linkophobia:

The line beginning with Proc-Type contains the version and the protection on the encapsulated data. The line beginning DEK-Info contains two comma separated values: the encryption algorithm name as used by EVP_get_cipherbyname() and an initialization vector used by the cipher encoded as a set of hexadecimal digits. After those two lines is the base64-encoded encrypted data.
The encryption key is derived using EVP_BytesToKey(). The cipher's initialization vector is passed to EVP_BytesToKey() as the salt parameter. Internally, PKCS5_SALT_LEN bytes of the salt are used (regardless of the size of the initialization vector). The user's password is passed to EVP_BytesToKey() using the data and datal parameters. Finally, the library uses an iteration count of 1 for EVP_BytesToKey().
The key derived by EVP_BytesToKey() along with the original initialization vector is then used to decrypt the encrypted data. The iv produced by EVP_BytesToKey() is not utilized or needed, and NULL should be passed to the function.

EVP_BytesToKey itself is documented on its own man page and covered in numerous Stack questions or answers including one of my longer ones (which is actually about commandline enc but the EVP_BytesToKey part applies additionally to 'legacy-PEM' encryption).
The decrypted plaintext is the same as the unencrypted form, PKCS1 (rfc8017 et pred).
The ursine answer to this Q over in security also covers this and related formats in some detail.
For clarity note there are many other file formats for RSA keys, even within OpenSSL and OpenSSH much less other software; this is a scheme for some passphrase-protected RSA private keys but not the scheme for all such keys.


What are the safe ways to derive HMAC key using block cipher? Suppose we have a state of block cipher initialized with some key unknown to us, that is, we have the state after running key schedule, but we have no access to actual key or subkeys, all we can do is encrypt and decrypt data with this state. How to safely derive an HMAC key from it that we can use to authenticate data encrypted with the same state?

If we use CTR mode to encrypt data, it's probably safe to use the first $n$ bytes of keystream as HMAC key, and then use the other $n + i$ bytes for the actual encryption (at least, that's what NaCl do to derive Poly1305 key from XSalsa20 stream).

What is the best way to do this if we use CBC mode to encrypt data?

Well, if you are using CBC mode in the recommended way (always using an unpredictable IV), then it turns out to be easy.

With CBC mode, the value that is presented to the encryptor is always a plaintext block exclusive-or'ed with an IV or a previous ciphertext block.  If plaintext blocks are uncorrelated with both the IV and the previous ciphertext block (and the latter just means we didn't deliberately pick plaintext blocks depending on what the previous ciphertext block looked like), that means that what is presented to the block cipher are effectively random values, with no specific value being any more probable than any other.

So, if we need a bit of additional keying data, what we can do is pick an arbitrary block value $B$ (perhaps the all-zero block), encrypt that using the block cipher in ECB mode, and use that $Encrypt_{key}(B)$ value as the HMAC key.  The attacker will gain information on that value only if the CBC mode cipher also happens to present that exact value $B$ while encrypting some text, that is, $B = Plaintext_0 \oplus IV$ or $B = Plaintext_n \oplus Ciphertext_{n-1}$.  However, by the above argument, the values on the right hand side are effectively random, and so if we have a $b$-bit block cipher and are encrypting no more than $2^{b/2}$ blocks (going past that is not recommended because of the birthday bound; you'll be leaking plaintext blocks at that point), then the probability of that happening will be less than $2^{-b/2}$; if $b=128$, this is usually considered sufficiently small.

If you are ultraparanoid about that slight possibility, what you could do is select two blocks $B$ and $B'$ (for example, the all-zeros block and the all-ones block), and use the value $Encrypt_{key}(B) \oplus Encrypt_{key}(B')$.  The attacker will know that your HMAC key is not the all-zeros value; other than that, he will gain information on the value only if both $B$ and $B'$ happen to crop up during the CBC operation; that would be bounded by $2^{-b}$

The above analysis rather assumed that you need only one block of information for your HMAC key; if you happen to need multiple, it is easy to extend this analysis to $Encrypt_{key}(B_0), Encrypt_{key}(B_1), ... , Encrypt_{key}(B_n)$ for preselected distinct values $B_0, B_1, ..., B_n$


No of keys used in Triple DES Algorithm I am studying Triple DES.

I have got two basic questions. One, why are we following a sequence like encrypt(decrypt(encrypt)); what is the problem using a sequence encrypt(encrypt(encrypt))?

Second, why are we not using a single long key (say 168 independent key bits) in lieu of three individual 56 bits keys?

Thanks.

The first question is already answered here.

For the second question, a single key $k \in \left\{0,1\right\}^{168}$ can be trivially converted back and forth from three keys $k_1, k_2, k_3 \in \left\{0,1\right\}^{56}$ – there is no semantic difference between the two. DES itself operates only on 56-bit keys, and triple-DES requires three independent DES operations. Software that implements triple-DES can trivially be written to either accept a single 168-bit key or three 56-bit keys.


Distributed generation of random numbers I have a network of $N \gg 1$ nodes. Some relatively low fraction $p$ (e.g., $p \simeq 0.01$) of them is under the control of a malicious attacker. Nodes can talk to each others and verify each other's identity (i.e., when a node communicates with another one it can verify the other's identity and membership to the network).
Now, I need my nodes to agree on a random number. It should be the same random number for all the nodes, and it should indeed be random. In other words, the malicious attacker shouldn't be able to steer the distributed random number generation to produce a number of its choice, unless $p$ is larger than some reasonably large amount (e.g. $0.1$).
Is there any way to do so with $O(N \log(N))$ communication complexity? For example, a trivial way of doing this with $O(N^2)$ communication complexity is that each node generates a random number, hashes it with a secure hash and communicates it to all the other nodes. When all the commitments are exchanged, everyone sends out its own random number, and all the numbers are XOR-ed or modulo-summed or so. But this is expensive in terms of communication, and definitely not scalable.
What I need this for
I am developing a peer to peer storage network, where a potentially very large set of nodes contribute to storing each other's data. I am working under the assumption that only that fraction $p$ of the nodes is malicious and willing, e.g., to corrupt or make unavailable some data. Now, I am using a redundancy protocol where a group of, e.g., 36 nodes store each other's data using an erasure code that allows up to 12 nodes to be wiped before the data is lost. This is nicely reliable, as long as the attacker has no way to infiltrate more than $12$ nodes in any specific group. Since $p$ is small, if I have a way of organizing the nodes into groups at random, the probability of any group having more than $12$ malicious nodes is vanishingly small.
This is why I need globally verifiable random numbers: I need all my nodes to be certain that the groups they have been organized into are really random.

The commit-then-reveal approach above is not secure as it allows an attacker to bias the output by forcing the protocol to restart. For an overview on generation of distributed unbiasable randomness, checkout our research paper: https://eprint.iacr.org/2016/1067.pdf

A Golang prototype of RandHound, one of the protocols proposed in the above article, is available in the DEDIS cothority project of EPFL: https://github.com/dedis/cothority/tree/master/randhound


Dropbox Password security Dropbox have recently published How Dropbox securely stores your passwords

Is this really more secure than using bcrypt with a complexity of 11 or 12 ?

The password "chain" is secure as its weakest part, so is there any point adding the extra 2 parts in ?

I understand that the Global "pepper" means that a DB dump protects the hashes until that pepper is found, and then each hash is still salted per user, but how much would that slow down people reversing the passwords in the event of a DB leak over simply bcrypting them ?

Is this really more secure than using bcrypt with a complexity of 11
  or 12 ?

It depends. Obviously if you consider everything on their servers compromised this isn't more secure than using a higher workload for the password hashing scheme (PHS). If you assume they can guard their pepper better than their password database then the passwords are irrecoverable from the dump.

  The password "chain" is secure as its weakest part, so is there any
  point adding the extra 2 parts in ?

A chain isn't really the correct analogy here. Assume an attacker can brute-force infinitely many bcrypt hashes but can't get the pepper. There's no way such an attacker could recover the passwords because he can't obtain the hashes required to brute-force them.

A better analogy would be an onion. You can't get to the core (the password) without going through all the layers (pepper, bcrypt, SHA-512).

  I understand that the Global "pepper" means that a DB dump protects
  the hashes until that pepper is found, and then each hash is still
  salted per user, but how much would that slow down people reversing
  the passwords in the event of a DB leak over simply bcrypting them ?

The pepper is a 256-bit AES key. If an attacker doesn't get hands on this one there's no way they can recover the hashes and thus potentially the passwords. However as soon as you have exfiltrated the key, the additional AES encryption has just about 0 influence on the run-time required for brute-forcing a key. So you win in case you can protect the key and you lose nothing if you can't do that.


What is a Non-Interactive Zero Knowledge Proof? I understand the concept of a Zero Knowledge Proof thanks to the easy to understand analogy of Alibaba's cave. However, this seems to require interaction between the verifier and the other party.

I have not found an explanation of non-interactive zero knowledge proofs (NIZK). The wikipedia article is way too complex for someone without advanced training to understand.

https://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof

Can someone explain the concept of non-interactive zero-knowledge in a simple way?

A non-interactive ZK proof is when you play with yourself. Or, more accurately, with an impartial version of yourself.

In a normal ZK proof, the prover first issues a bunch of commitments, then the verifier issues challenges that the prover complies with; this proves anything only as long as the verifier is assumed to issue challenges normally without any prior understanding with the prover.

In a non-interactive ZK proof, the verifier is replaced by a hash function (or something similar) which is computed over the whole set of commitments: the hash function result is the challenge. If the hash function is really a random oracle then the prover cannot guess its output before trying it, i.e. before having produced his commitments, and that's where the security comes from.


Hash function that allows to decide if A > B if you only have hash(A) and hash(B)? Is it possible to construct a hash function with the following property?

If you have hash(A) and hash(B) with A and B being integers, you can tell if A is greater than B -- without however knowing the actual values of A and B.

Even better: If you have hash(A) and hash(B) with A and B being ordered sets of strings, you can tell which elements of A overlap with B (e.g. those at position 1 and 3 in the ordered set) -- without however knowing the actual contents of A and B.

For hash function $h : \{0,1\}^* \rightarrow \{0,1\}^k$, this is not possible. This is because there are more possible inputs than outputs (pigeon hole principle). And this means that for some $A < B$ we have $h(A) = h(B)$. Thus there will be no way to tell the order of $A$ and $B$.

Addition:  To address some of the comments; note that this answer only talks about hash functions defined as functions where the domain is the set of all bit strings and the codomain a set of bit strings of some fixed length $k$. It also assumes that inputs $A$ and $B$ are interpreted as integers (as specified in the question).

The argument only uses that such a hash function must have collisions. We can in fact generalize the argument to any hash function with collisions (i.e., also functions with different domain and codomains). Note that the argument only assumes the existence of collisions and thus holds even if the hash function is collision resistant.

The argument says that for such hash functions there will be some pairs of inputs, those defining a hash function collision, where the order cannot be decided from the hash alone. What happens on other inputs pairs the argument does not directly say anything about.

It is true however, as some comments point out, that if we define hash functions to include functions completely without collisions, then the argument does not hold for all hash functions. However, for functions where my argument does not apply we can use the argument of fgrieu, to show that a hash function with the desired properties can at least not be pre-image resistant.


What is the use of a nonce in public-key encryption if it's meant to be shared? I'm using PHP. The guys over at paragonie have made encryption easy for the PHP eco-system.

Now, on my computer, Alice, when I encrypt a message using Alice's private key and Bob's public key, I am also given a nonce. Its use? I don't know. I just trust the guys that it's needed and safe.

Thing is, this got me thinking - a nonce, in my book is a protection against forgery, but here I am giving it away. Clearly, if you go to this article: https://paragonie.com/book/pecl-libsodium/read/05-publickey-crypto.md and check the //Bob's computer part, you can see that Bob also needs that nonce Alice generated.

So, what am I missing here?

Thing is, this got me thinking - a nonce, in my book is a protection against forgery, but here I am giving it away.

The primary purpose of nonces is not protection against forgery, but rather, to ensure that encrypting the same plaintext many times with the same key does not produce the same ciphertext (which risks the possibility that an eavesdropper might learn something from frequency analysis).  For a very simplistic example, imagine encrypting the plaintexts YES and NO over and over and they always encrypted to XUW and EG.

There are protocols that secondarily exploit nonces in some fashion to avoid replay or reordering attacks (a kind of forgery). For example, when encrypting a large volume of data, one strategy is to break it into smaller sequential chunks and encrypt each one separately with the same key but a nonce that encodes:

The chunk number
A flag indicating for each chunk whether it's the last one

...so that when you decrypt the file, you verify as you go that no chunks have been reordered and that it hasn't been truncated.  But that's an optional thing an application may (wisely) choose to use chunks for, not a basic requisite like the ciphertext diversification.

I must say that I find the documentation that you link rather confusing in its treatment of nonces, because:

For ciphers popular today (and used by the Libsodium C library this PHP package is seemingly based on), encrypting two textually different plaintexts with the same key and nonce can result in a catastrophic security loss;
The linked page don't seem to sufficiently warn of the danger inherent to nonce reuse;
It also doesn't explicitly specify over what scope the library expects nonces to be unique.

Compare what the Paragonie docs say:

  Each message sent requires a nonce (a unique large number represented as a binary string that should only be used once).

...with its counterpart in the documentation of Libsodium library:

  The nonce doesn't have to be confidential, but it should be used with just one invocation of crypto_box_easy() for a particular pair of public and secret keys.

  One easy way to generate a nonce is to use randombytes_buf(), considering the size of the nonces the risk of any random collisions is negligible. For some applications, if you wish to use nonces to detect missing messages or to ignore replayed messages, it is also acceptable to use a simple incrementing counter as a nonce. A better alternative is to use the crypto_secretstream() API.

  When doing so you must ensure that the same value can never be re-used (for example you may have multiple threads or even hosts generating messages using the same key pairs).

Much, much better, and the recommendation to use random nonces is safe, but the alternative suggested of using a simple incrementing counter is a bit scary, it's much too easy to implement that wrong e.g. across multiple executions of the same program.  They suggest the use of their newer crypto_secretstream() API instead, but that uses shared-key encryption, not public key, leaving the user the highly non-obvious task of figuring out how to wire those together.

Caveat emptor. Cryptography is a minefield.


Merkle–Damgård padded block concatenated outside the compression function hash? I learned that the output of hash function from Merkle Damgard is

H(x) = ZB+1 = h(ZB || L) = h(ZB - 1 || XB || L) where XB = block of padded x and L = XB+1

and it is proven that H(x) is collision resistant.
However, what if I tweak the H(x) by extracting L from the compression function h(x) s.t

H(x) = h(ZB - 1 || XB) || L

I feel like this makes H(x) to be not collision resistant, but I don't know how to design an attack for this hash function. Can someone give me an idea (perhaps hint) to design such attack?

NOTE: Before anyone screams at me about anything, I want to say YES this is a practice question from a cryptography textbook. That is why I asked for a HINT not an answer. Thanks :)

Why don't you look at it the other way; suppose you could find a collision with your modified H(x) = h(ZB - 1 || XB) || L; could you use that collision to find a collision in the original H?