Why does P1363 require RW signature with $0 ≤ s < n/2$? I'm using an older copy of P1363 Public Key Cryptography was used below. It may (or may not) reflect the current state of affairs.

P1363 has the following requirement in section 8.2.8 IFSP-RW, p. 45:

  Output: The signature, which is an integer $s$ such that $0 ≤ s < n/2$

8.2.5 IFVP-RSA1 (p. 43) does not have the same requirement; but 8.2.6 IFSP-RSA2 (p. 44) does have the requirement.

Bernstein does not appear to discuss the requirement in RSA signatures and Rabin–Williams signatures: the state of the art.

What's the purpose of the restricted range on the signature? What threat does the requirement address?

That practice of replacing the result of $y=x^d\bmod N$ (or $y=x^e\bmod N$) by $\hat y=\min(y,N-y)$ is also in ISO/IEC 9796-2:2010 (paywalled) and ancestors; I first met that in [INCITS/ANSI]/ISO/IEC 9796:1991, also given in the Handbook of Applied Cryptography, see in particular note 11.36. ISO/IEC 9796 was a broken and now withdrawn signature scheme with message recovery based on RSA or RW, very different from ISO/IEC 9796-2.

With $e=2$ (or more generally even), $\;y^e\bmod N\;=\;(N-y)^e\bmod N$. Thus in a RW signature application, signatures $y$ and $N-y$ are equivalent. One rationale of using $\hat y$ is to choose a canonical signature among $y$ and $N-y$. This allows the verifier to check that the signature is less than $N/2$, which prevents an adversary from turning a signature $y$ into a different but equally acceptable signature $N-y$ (some definition of signature security consider that a break).

With odd $e$ (RSA), there is no such security rationale. However we can still use $\hat y$ rather than $y$, if the low-order bit of $x$ is set to 0 by the padding scheme: if $\hat x=\hat y^e\bmod N$ turn out to be odd, the verifier uses $x=N-\hat x$ instead.

Whatever $e$, the maximum bit size of $\hat y$ is one less than the maximum bit size of $y$ (for arbitrary $x$). That size reduction, however small in proportion, allows:

Direct re-encryption of $\hat y$ under textbook RSA using a different $N'$ of the same size as $N$, including when $N'<N$, which can happen when encryption and signature keys have modulus specified only by their common bit size (and is bound to happen for one of the two parties in some protocols between peers each using a single key for both encryption and signature, as in the European Digital Tachograph).
Use of $N$ with $8k+1$ bits with convenient signatures of $k$ bytes; such $N$ have been extensively used in early public-key systems; as illustration, the example given in ISO/IEC 9791:1991, appendix B.1.1, has as 513-bit $N$.Incidentally, the leftmost 129 bits are all-zero except the leftmost one, which simplifies quotient estimation, perhaps at the price of somewhat easier factorization in particular with NFS, but that was not known at the time.


Secret sharing scheme WITHOUT Shamir Secrete Sharing I am planning to use the following XOR scheme to divide a secret into only 2 shares (I do not want to use Shamir Secret Sharing for different reasons that are beyond the scope of this post).

Here's an example of the XOR scheme I have in mind.

SECRET (128 bits)  =  0 1 0 1 0 0 1 0 0 0 0 1  (…)  0 0 1 1 0

SHARE 1 =  TRUNC128 (SHA512 (SECRET))

     =  0 0 0 0 1 1 1 0 0 0 1 1  (…)  1 1 0 0 1

SHARE 2 =  SECRET ^ SHARE1

     =  0 1 0 1 0 0 1 0 0 0 0 1  (…)  0 0 1 1 0

     ^  0 0 0 0 1 1 1 0 0 0 1 1  (…)  1 1 0 0 1

    =  0 1 0 1 1 1 0 0 0 0 1 0  1 1 1 1 1

SECRET   =  SHARE1 ^ SHARE 2

   =  0 0 0 0 1 1 1 0 0 0 1 1  (…)  1 1 0 0 1

    ^  0 1 0 1 1 1 0 0 0 0 1 0  (…)  1 1 1 1 1

   =  0 1 0 1 0 0 1 0 0 0 0 1  (…)  0 0 1 1 0

I have a few questions about that XOR scheme as I am building a case for using it.

1) How resistant would such a scheme be to common attack vectors (brute force...)?

2) Are there any ways to evaluate what it (or how much it) would take to break that scheme?

3) Is that scheme already used in "notably safe applications"? If that is the case, which ones?

XOR secret sharing used directly is unconditionally secure, if the randomly generated first share $S_1$ is a uniformly distributed vector in $\{0,1\}^{128}$. Let the secret be $X \in \{0,1\}^{128}$ and the shares be $S_2=X+S_1,$ and $S_1,$ where $+$ denotes bitwise XOR.

For a third party to learn the secret, they need to brute force $O(2^{128})$ guesses in the worst case.

Now you've "hidden" the secret $X$ by your $S_1'=TRUNC_{128}(SHA_{512}(X)).$

As stated in the comments I was wrong, thebirthday paradox does not directly apply.

An attacker brute forcing the share $S_2’=X+X_1$ at the same complexity will not learn your secret but its hash, so you’ve gained something.

However in the absence of side information, the original XOR scheme is as secure, unless the guesses for the secret can be tested by using it, say, as a password to unlock some system. In that use case, your modification is an improvement since it prevents this way of testing if the guess is correct.


How to calculate the time it'll take to crack RSA or DH? Sometimes the easiest way to describe security of a type of cryptography is to say that "the time it takes to solve for an x-bit key would be y years". How would one go about doing such a calculation for RSA, DH, and ElGamal. In other words, given x, how to solve for y?

There is an asymptotic formula for the General Number Field Sieve for factoring big integers. This is the most efficient known algorithm for breaking RSA keys which are longer than 400 bits or so (since the current world record is 768 bits, a 400-bit RSA key is quite weak). For discrete logarithm (to break DH), the best known algorithm is also known as "number field sieve" and it is much similar to the one for factorization. In particular, it has the same asymptotic complexity.

However, asymptotic formulas do not capture all the information you want:

An asymptotic formula describes the behaviour of the function which gives the computation time depending on the size of the input, for large enough inputs. It says that "when the input size grows toward infinity, the complexity grows in a way similar to this formula". But that's still an approximation and nothing guarantees that an actual RSA key you are trying to break is large enough for the asymptotic formula to be reasonably accurate. For instance, Multi-Polynomial Quadratic Sieve is asymptotically slower than GNFS; but it is in practice faster than GNFS for 300-bit integers. This means that 300-bit integers are not large enough for asymptotic formulas to accurately rate factorization algorithms against each other.
Even when the formula is accurate, it has an implicit multiplicative constant in front (which you can name "number of operations per second" if you wish). So the formula must be calibrated with an actual experiment. Speaking of which, even though GNFS for factorization and NFS for discrete logarithm share the same asymptotic behaviour, they do not have the same "constant" so, in practice, a 600-bit DH key seems to be substantially harder to break than a 600-bit RSA key (indeed, the current world record for discrete logarithm is "only" 530 bits).
Time complexity formulas talk only about operations, but do not describe space requirements. In GNFS for large numbers, the storage space can become tremendous, especially for the last part of the algorithm (the "linear algebra") which is a conceptually simple operation (Gauss reduction) on a matrix of humungous size; in practice, that step is constrained by the RAM size and speed, and also how fast you can move the data around in a cluster. CPU is not the bottleneck, and the time complexity formula talks only about the CPU.
The whole process is not streamlined. There are several steps in the algorithm (polynomial selection, sieving, linear algebra) and although there is good opensource code for that, it still requires some thinking by smart people at some crucial moments. To beat the world record in factorization, you need horsepower but also computer scientists who know the ins and outs of GNFS, and there are maybe a hundred of those worldwide.

So the practical way of estimating the breaking time for a RSA or DH key is to extrapolate from the published integer factorization records and discrete logarithm records.

There has been quite a lot of work on such "extrapolation", in particular in the search for "equivalences" between symmetric and asymmetric key lengths (as in: "a 1024-bit RSA key is roughly as robust as a 160-bit hash function"). See this site for a comprehensive summary of the resulting recommendations emitted by various organizations (with online calculators and many pointers). Given the points I evoke above, it is not surprising that the published recommendations do not really match each other...

The synthetic advice which is often given in 2011 is: "use 2048-bit RSA/DH/DSA keys, and you will be fine for a looong time."


DES Bruteforce attack and false positive keys I have read that a bruteforce attack (regardless on which block cipher is used) can lead to a false positive if key space is greater than blocks space.
It is pretty clear to me that is due the pigeons hole principle (if I have more keys than available blocks, sooner or later I will use two different keys for the same mapping).

My question is, how can DES exhibit such behavior if the key space is about $2^{56}$ and block space is $2^{64}$.

What I am expecting from those premises is that given a plaintext and all possible keys, not all possible ciphertexts will be addressed.

My question is, how can DES exhibit such behaviour if the key space is about $2^{56}$ and block space is $2^{64}$

Let us assume that the attacker has a single plaintext/ciphertext pair, that is, two eight byte values $P, C$ with $C = \text{DES}_k(P)$, where $k$ is the correct unknown key.

Then, let us consider the values $\text{DES}_{k'}(P)$; there $k'$ ranges over the $2^{56}-1$ possible incorrect keys.  If we model DES with the incorrect key as a random permutation, then what we get is a list of $2^{56}-1$ random 8 byte values, each one of which has a $2^{-64}$ probability of just happening to be $C$.

Hence, the expected number of times the value $C$ appears on that list is $(2^{56}-1)2^{-64} \approx 2^{-8}$ (and the probability that the value $C$ appears at least once on the list is a tad smaller).

Hence, there does indeed exist a nontrivial probability that a brute force search would find two keys; the correct key $k$, and another key $k'$ that just happens to map $P$ to $C$.

Of course, in practice, we never really get only one plaintext block and one ciphertext block; we generally get additional ciphertext blocks that, at the very least, attempt to decrypt, and see if they make sense; that'll allow us to distinguish the correct key from any incorrect ones.


How to multiply a matrix of bits with another? For example, assume I have two 4x4 matrices of bits:

1 1 1 1       1 1 1 0

0 0 0 0       0 1 1 1

1 0 0 1       1 0 1 1

0 1 1 1       1 0 1 0

I want to apply matrix multiplication for the modified IDEA (International Data Encryption Algorithm). How does one multiply a matrix of bits with another matrix of bits?

Multiplication of bits matrices works just like multiplication of number matrices, except the rule of addition is modified to: $1+1\mapsto 0$.

Let $U$ (resp. $V$) be a square matrix of $n\times n$ elements noted $u_{l,c}$ (resp. $v_{l,c}$) with $1\le l\le n$ and $1\le c\le n$. The product $U\cdot V$ is a square matrix $W$ of $n\times n$ elements noted $w_{l,c}$, with
$w_{l,c}=\sum_{j=1}^n u_{l,j}\cdot v_{j,c}$

In the problem at hand, $n=4$. To compute the bit at (say) the third line and first column in the result, we'll use the above formula with $l=3$ and $c=1$, giving $w_{3,1}=\sum_{j=1}^4 u_{3,j}\cdot v_{j,1}$, that is $w_{3,1}=(u_{3,1}\cdot v_{1,1})+(u_{3,2}\cdot v_{2,1})+(u_{3,3}\cdot v_{3,1})+(u_{3,4}\cdot v_{4,1})$. The third line of the left matrix gives $u_{3,1}=1$, $u_{3,2}=0$, $u_{3,3}=0$, $u_{3,4}=1$. The first column of the right matrix gives $v_{1,1}=1$, $v_{2,1}=0$, $v_{3,1}=1$, $v_{4,1}=1$. Thus $w_{3,1}=(1\cdot1)+(0\cdot0)+(0\cdot1)+(1\cdot1)$. That simplifies to $w_{3,1}=1+0+0+1$, then $w_{3,1}=0$.


Brute forcing an elliptic curve encrypted key I've been reading about ECC, and what I've established so far (correct me if I'm wrong) is that:

pubKey = privKey * G

where G is some special point on the secp256k1 curve.

Doesn't this mean we could attempt to brute force a private key by using:

privKey = pubKey/G

for all potential values of G.

I know it would require some unfeasible amount of attempts, but what if by chance that one of the first few attempts happened to have the correct value?

Doesn't this mean we could attempt to brute force a private key by using:
  $$\mathit{privKey} = \mathit{pubKey}/G$$
  for all potential values of $G$?

There seems to be a misunderstanding here: $\mathit{pubKey}$ and $G$ are fixed and publicly known, so there's nothing left to brute-force. The operation of "dividing" $\mathit{pubKey}$ by $G$ is (to the best of current public knowledge) computationally infeasible; this is the elliptic-curve discrete logarithm problem (ECDLP).
However, of course, one can brute-force by trying all possible values of $\mathit{privKey}$ and checking whether $\mathit{privKey}\cdot G=\mathit{pubKey}$ holds.

  what if by chance that one of the first few attempts happened to have the correct value?

This is very much related to this recent question. The bottom line is: Yes, that could happen, but the probability is so incredibly low it is never going to occur in practice. (And in any case, if we're worried about someone just guessing our secret keys by pure luck, there's nothing anyone could do against it anyway.)


Ways to make a "doomsday" cryptocurrency which becomes untradable As a social experiment (not a money-making scheme), I'm interested in developing a crazy cryptocurrency which, by its very design, will become worthless and untradable after a certain point. Ideally, this would be a fixed date like "January 1st 2020," but it could also be after a predictable event occurs, such as after one million trades have been made, or once a super expensive computation completes. I, the designer of the currency, should not have any ability to prevent this "doomsday," postpone it, or even cause it to happen early. Lastly, my users should not have the ability to defy the doomsday by creating their own fork of the code.

The current idea I'm running with is to have there be a "super-key," which works as a universal private key and allows you to break into anyone's account. Since the accounts would cease to be secure, the currency would be worthless. I would generate this key, then encrypt it in such a way that it would take years (but not decades!) to crack, then release it publicly. The superkey could a third party, but this is less fun because it goes against the basic idea of cryptocurrencies. I also do not know if I would be able to guarantee that I myself don't own the super-key in its unencrypted form.

I'm wondering if anyone has any suggestions on how to implement this.

I would generate this key, then encrypt it in such a way that it would take years (but not decades!) to crack, then release it publicly.

Yes, you are in effect putting the master key in a time capsule. The problems of time capsules in general apply: the release time will not be exact and a breakthrough in e.g. CPU design could hasten it. If no one's trying, it may never be broken.

  I also do not know if I would be able to guarantee that I myself don't own the super-key in its unencrypted form.

A simple way would be a nothing up my sleeve number. For example, generate a "random" public key using e.g. the digits of $\pi$ in an obvious way. Have all the relevant information be encrypted using this public key. Then brute forcing the private key will reveal it all. The size of the key will determine the difficulty of breaking it.

The problem is how to make sure the users really encrypt data for that key, instead of pushing some dummy data into the block chain. There is no way to prove a given value makes sense when decrypted, if you don't know the private key.

One option would be to instead of going after accounts, tie the proof of work function to this key pair. E.g. instead of looking for values that hash to a certain kind of value, look for signatures that verify to a given number number of bits. For the owner of the private key that would be trivial, allowing easy 51% control and maybe even flooding the market with coins if you made the difficulty calculations slow enough to adjust.


The Probability to Detect or Identify an Unknown Ciphertext Let $\it C$ be a ciphertext such that we have no information about the type of symmetric encryption algorithm used to generate $\it C$.
Let $\bf S$ be the source bank of most block and stream ciphers such as AES,DES,RC4 and so on. Let $s \in {\bf S}$.
Question:
Is there an algorithm, software, or method (especially based on deep learning or machine learning) that receives $\it C$  and $s$ as input and the output is the probability that  $\it C$ is encrypted by $s$?
Thanks for any help such as paper or thesis.

Is there an algorithm [...] that receives $\it C$  and $s$ as input and the output is the probability that  $\it C$ is encrypted by $s$?

No. Not unless the system $s$ in question is horribly broken.
The reason is simple: Most modern symmetric encryption schemes are built from primitives which are designed to heuristically achieve one of three security models: PRG, PRF or PRP.1
The fundamental property all three of these models have in common is the fact that when given a random input (in the appropriate input slot) then the output will be indistinguishable from a random string.
If you can break this security property for any of these primitives while knowing which you target this is usually worth a peer-reviewed academic paper. Example for Gimli.
Now the output of all non-horribly-broken schemes is indistinguishable from random which means they're also indistinguishable from each other and thus you can't deduce to which a ciphertext belongs. Except of course for horribly broken schemes where you can more clear say whether or not a ciphertext belongs to a scheme. Of course you wouldn't want to actually use any of those schemes but rather use them as examples of how not to design heuristically secure primitives.
Note that the above definitions still leave some wiggle-room as outlined in this Q&A. However this would mostly be length-based (e.g. a direct AES ciphertext is always 16 byte) or based on oracle access to the encryption scheme. Depending on the concrete setup in question this may or may not be applicable (e.g. if outputs are always truncated to 8 byte).

1: For encryption schemes the relevant security property is called IND\$-CPA but these three are the building blocks from which IND\$-CPA security is usually proven.


How to evaluate chi squared result? I've been recently working on a (supposedly) TRNG. I'm still at the beginning of the project, so it is certainly not cryptographically secure yet, for now I'm just playing around.  In fact, I've already discussed the project and the chi square results here in question: Random number generator issue.

At this early stage I'm using ent to see if there is any gross issue, later I'll move to a more accurate test suite.

One of the ent measured parameters draw my attention: the chi-squared. After doing some research I've understood that this value basically says how much, in a set of values, their frequencies match with the theoretical expected frequency.
$$\chi^2=\sum_{i=1}^n\frac{(o_i-e_i)^2}{e_i}$$
where $o_i$ is the actual frequency and $e_i$ is the theoretical frequency.

And that's fine, but how do I understand which would be my optimal value?  For my particular case (values ranging from 0 to 255, uniform distribution) I'm using 254.3 as a reference "optimal value" from ent's manual. (I could be wrong on this, ent manual explicitly states only that for true randomness i should expect my percentage value to be between 10 and 90%, which is centered to 50%, which gives a value of 254.3)

Let's say everything is perfect, I'd have $o_i$ which is equal to  $e_i$, so the difference would be 0 for every $i$, they should add up to 0 and my optimal chi-squared would be 0.

But according to ent my optimal chi-squared is the above mentioned 254.3.

How I should calculate my optimal chi-squared for a different distribution (e.g. the normal distribution) or for a different range of values (e.g. 0 to 65535) ?

Testing the frequency of bytes produced by an ideal (uniform) random generator per question's method with $1200$ samples or more gives a $\chi^2$ that varies typically by few dozens around the average, $255$. It should be below $254.334$ for 50% of experiments, and the most likely values those closest to $253$.

For a good uniform random sequence of bytes, and "enough" samples, the distribution of $\chi^2$ computed as in the question has a well-studied distribution: the $\chi^2$ distribution with $2^8-1=255$ degrees of freedom, with this Probability Density Function:

The mean is $255$ (that's what you obtain by averaging the $\chi^2$ of many experiments). The median is $\approx254.334$ (the $\chi^2$ is less than this for 50% of experiments). The mode is $253$ (that's the most likely value, maximizing the PDF).

The standard deviation is $\sigma=\sqrt{510}\approx22.58$. Because the PDF is close to a normal, the 68–95–99.7 rule applies: that gives the probability (in percent) to be one, two and three $\sigma$ from the mean. Again that's with "enough" samples. A rule of thumb tells that about $5$ samples per expected value (thus like $1200$ samples) starts to be enough when reasoning at up to $2\sigma$. More sample usually help (I wish I knew how to more rigorously choose the minimum number of samples).

The Cumulative Density Function $\displaystyle\operatorname{CDF}(x)=\int_0^x\operatorname{PDF}(u)\ du$ is:

That tells the expected proportion of experiments (for a uniform random sequence) where the computed $\chi^2$ is less than a certain value.

We have a 0.05% chance that the $\chi^2$ is less than $187.171$, and 0.05% chance that it is above $335.917$. Thus in only about one experiment out of 1000 will the $\chi^2$ will be out of that range, for a truly uniform random sequence, and "enough" samples.

In particular, a generator that consistently gives low $\chi^2$ is not random!

When we generalize to different tests with a random variable taking one out of $n\ge2$ different outcomes with expected frequencies $e_i$ and $\displaystyle1=\sum e_i$, and the number of samples is at least about $5/\min(e_i)$ (enough for a minimum of $5$ expected samples for each value), then the distribution of $\chi^2$ is the $\chi^2$ distribution with $k=n-1$ degree(s) of liberty.

The shape of the Probability Density Function vary with $k$.

The mean is $k$, the median is about $k(1-2/9k)^3$, the mode is $\max(0, k-2)$.The variance is $\sigma=\sqrt{2k}$, but for low $k$ computations or tables (rather than estimations based on $\sigma$ and a normal approximation) are necessary.

The shape of the Cumulative Density Function vary with $k$:


Implementation and Testing of SRP-6a I have been wracking my brain trying to develop a functioning implementation of SRP-6a in Python to use with a 3rd-party API that claims to use SRP-6a with $N=$ 2048-bit prime and generator of $2$.  Unfortunately it has proven quite difficult to find two implementations that "match" to themselves.

For example, Stanford’s “SRP Protocol Design” page indicates that $K=H(S)$ (and I'm assuming that $H$ is SHA1 even though some implementations are using SHA256), but RFC2945 (original RFC for SRP) indicates $K$ is an Interleave-SHA1.  So which is it?

Second, the proof that the user generates ($M$) is stated, "one possible way" is $M=H(H(N) \oplus H(g), H(I), s, A, B, K)$ whereas some implementations have $M=H(A,B,S)$?
Which is it?

Finally, if I look at the original RFC2945 I see pretty much what is written in SRP Protocol Design, with the exception that $k=H(N,g)$ in 6a and for example in the design URL $B=(kv + g^b) % N$ (I guess, its never clear where to apply modulo $N$ if its just left out and written as "All arithmetic is done modulo N) where as in RFC2945 B is simply $(v+g^b) % N$.

Finally, are there test vectors other than $N$=1024-bit, $g=2$ , I can recreate the vector that exists even though nothing every shows the expected calculation for $K$ or $M$.

Apologies for first post to this site as sounding needy, but I've been trying to wrap my mind around this and work with a blackbox application that I simply fail the proof every time even after checking and doublechecking my code. :-(

SRP protocol is quite abstract so to provide matching implementation for version 6a you need to know following:

N, g - group parameters
H - hash function, there can be different hash functions used for different values
how is private key x calculated
how is shared session key K calculated
how are evidence messages (M1, M2) calculated

In addition you need to know what is internal representation of numbers (byte order, padding) and what is the format of messages being exchanged between client and server.

Without that knowledge all you can do is reverse enginner (even without disassembling binary ie. you could deduce what might be hash function based on size of M1) or try your luck with different configurations. For example (based on RFC 5054 and SRP-6a summary):

byte order: big endian
encoding: UTF-8 (for username and password)
N = 2048 bit prime from appendix A
g = 2
H = SHA1
x = H(s | H(I | ':' | P))
k = H(N | PAD(g))
u = H(PAD(N) | PAD(B))
K = H(S)
M1 = H(H(N) xor H(g), H(I), s, A, B, K)
M2 = H(A, M1, K)

As for the test vectors I haven't found others then those at RFC 5054 and on Stanford SRP demo page.


HMAC SHA256 - fixed vs dynamic key - security and collision impacts Assume we should apply an hmac sha256 on different messages made of incremental numbers (Ex. 1 to 1 billion).
Does it make sense in terms of security to apply a different fixed key for each message?
message 1 key X1
message 2 key X2
...
message n key Xn
Will applying a key for each message impact the collision rate?
If yes, will it increase or decrease the collision possibility?
The aim is to generate unique deterministic tokens starting from sequential values as source domain.

No, it is not useful to change the key between invocations of HMAC.
That would not change the expected probability of collision, which remains about $n(n-1)/2^{257}$ for $n$ values under a model of HMAC-SHA-256 as a PRF. For $n=2^{40}$ (over a million million, the UK bilion), that's less than $2^{-177}$, the probability of 177 consecutive tails with a fair coin, that is negligible in practice.
That probability can be brought to zero using encryption of a counter with a block cipher.


How much would an unexpected hash collision undermine the security of a hash function? Say some random person manages to, by sheer luck, find 2 messages with the same hash. There is no systematic way of creating more such pairs of messages that produce collisions.

How much would this one pair of collision producing messages affect the security of the hash function?

In many cases the collision might be exploitable to create many other collisions.  In almost all common constructions you could use the collision to build a collision of messages with arbitrary suffix.
Building a useable collision for most attacks like colliding pdfs requires something about the prefix.
But even without a known attack on the relevant prefix I would be worried a different exploitation scenario exists.
Also I would be very worried about such "luck" which may suggest either:
a. The chance of collision is much higher than it seems
b. There is an efficient way of generating collisions it's simply not public.

Furthermore the structure of the collision may give important cryptographic insights.

So for a random collision I don't know of an exploitable attack. I worry there is such, I worry the collision could be extended, the crypo is weaker than it seems and may have already been broken. I would migrate away.


Would it be possible to negotiate a key of 128 or 256 bits strength using Merkle puzzles? One can be fascinated by the simplicity of the schemes created by Ralf Merkle; like the Merkle tree or his key negociation protocol over an insecure channel.

Wikipedia has some material on "Merkle puzzles"
(wikipedia_page)
and his seminal paper can be found online
(article_pdf).

But, could this venerable construction be put to use in order
to reach nowadays security strength requirements (i.e. a key
of at least 128 bits strength, or even 256 bits for the real paranoids out there).

Thanks!

The complexity required for the attacker to break the scheme is at maximum quadratic in the security parameter $n$. It is not enough for a secure cryptographic protocol where you want exponential complexity to break the scheme.

Say $n$ is the difficulty of solving the puzzles and $m$ is the number of puzzles. Alice needs to solve one puzzle in time $O(n)$ but Bob will need to look in his puzzles to find the correct key. He needs roughly $O(m)$ time. The scheme has then $O(n+m)$ time complexity.

For breaking the scheme, Eve can brute force all the puzzles, she then needs $O(nm)$ time complexity. If you want to have this complexity be around $2^{128}$ you need to send an incredible amount of puzzles and/or puzzles too hard.


How does the Flame malware take advantage of MD5 collision? It's said that malware Flame used an MD5 collision to get "a counterfeit copy of the certificate".

We know that MD5 is broken on collision attack, but not broken on pre-image attack, thus the only way to get a fake cert is to generate the fake cert when applying for a legitimate cert.

My questions are :

Isn't it too dangerous for the virus maker to do this? (We can check who applied for the legitimate cert and catch him.)
If he can apply for a legitimate cert, why bother making a couterfeit cert? Why don't use the legitimate cert to sign anything he like?

I think you missed reading a part of that Wikipedia article:

  … Flame was signed with a fraudulent certificate purportedly from the Microsoft Enforced Licensing Intermediate PCA certificate authority.  The malware authors identified a Microsoft Terminal Server Licensing Service certificate that inadvertently was enabled for code signing and that still used the weak MD5 hashing algorithm, then produced a counterfeit copy of the certificate that they used to sign some components of the malware to make them appear to have originated from Microsoft.…

(emphasis mine)

In simpler words this means that the malware author(s) didn’t need to apply for a certificate himself/herself/themselves. Instead, the malware author(s) used a genuine Microsoft certificate he/she/they found and created a fake certificate based on that. That way, it seems as if Microsoft itself has signed some files – which Microsoft (of course) didn’t.

So, your …

  thus the only way to get a fake cert is to generate the fake cert when applying for a legitimate cert.

… is partly correct, but it’s only one side of the coin. The other way to get a fake certificate is to find a legitimate but weak and exploitable certificate from someone else – like one from Microsoft in this case.

Having said that, let’s answer your two questions:

  Isn't it too dangerous for the malware author(s) to do this? (We can check who applied for the legitimate cert and catch him)

No, since the fake certificate was based on a Microsoft certificate the malware author(s) got his/her/their hands on. That way, the fake certificate points to Microsoft (just like the genuine certificate it was based on), not the identity of any malware author(s).

  If he can apply for a legitimate cert, why bother making a couterfeit cert? Why don't use the legitimate cert to sign anything he like?

Not being Microsoft, the malware author(s) would hardly have had a chance to apply for a legit Microsoft certificate… and a certificate on his/her/their own name(s) would indeed have been pretty useless for his/her/their intended purposes as that would have added his/her/their name(s) to the equation.

Applying for his/her/their own legitimate certificate would have been a pretty stupid move while having the option to impersonate a trusted company like Microsoft. Remember the fact that the malware author(s) had access to a genuine Microsoft certificate with code signing enabled. (see first quote of my answer)

All in all you could say the malware author(s) found "a pot full of gold at the end of some rainbow" (read: a weak and exploitable Microsoft certificate with code signing enabled) and used what he/she/they found to his/her/their fullest malicious advantage.

Microsoft dropped a ball, and the malware author(s) picked it up. It was that simple for them. After Microsoft became aware of the situation, they handled the situation accordingly.

Quoting "Microsoft releases Security Advisory 2718704" dated June 3, 2012:

  We are taking several steps to remove this risk:

  First, today we released a Security Advisory outlining steps our customers can take to block software signed by these unauthorized certificates.
  Second, we released an update that automatically takes this step for our customers.
  Third, the Terminal Server Licensing Service no longer issues certificates that allow code to be signed.

  These actions will help ensure that any malware components that might have been produced by attackers using this method no longer have the ability to appear as if they were produced by Microsoft.

(emphasis mine)

But how did they do it?

Quoting an article from “nakedsecurity” – Sophos‘ blog:

  …

  In the Flame case, the attackers took a legitimate Microsoft certificate using MD5 for its hash and RSA-2048 for its public-key encryption. They then generated a similar-but-different certificate with the same MD5 hash. This means that the RSA-2048 signature from Microsoft’s genuine certificate could be grafted into their forged certificate to make it appear valid.

  …

Obviously, the above quote doesn’t really provide any real details.

In fact, explaining all the details would be a bit too broad to post as an answer here, but if you really want to dive deeper into an analysis of the Flame MD5 case, check the PDF: “Analyzing the MD5 collision in Flame”. Those 40 pages/slides walk you through details with screenshots etc.

Long story short: For Flame, a chosen-prefix collision attack against MD5 has been used. Its malware author(s) used a new variation of a chosen-prefix collision attack to spoof code signing of its components by a Microsoft root certificate that still used the compromised MD5 algorithm.


Concatenation of multiple shorter hashes vs a single long hash I permanently need to hash lots of data quickly, but the result only needs to be collision resistant.

Is there any negative side-effect of using multiple (say 2) algorithms providing a shorter digest (e.g. RIPE-MD-128 and Tiger128) versus using an algorithm providing a digest of the added length (e.g. SHA256).

I want to explicitly highlight that I only need high performance and collision resistance. Other properties (avalanching, etc.) are irrelevant, I do not even care if it is possible to go back from digest to input. So I do not even need to really use "cryptographic" hashing algorithms (CRC32 is perfectly fine here I guess).

More specifically my idea is to use multiple REALLY FAST algorithms (clhash performing at over 4 gigabyte per second on my testsetup, xxhash performing at over 6GB/s, ...) and simply concatenate them to improve collision resistance:
$$
Digest(Input) = XXH64(input)\ |\ CLhash(input)\ |\ CRC32(input)\ |\ Farsh(input)
$$

This results in a digest with $64+64+32+32=192$ bits length, but is faster than an algorithms providing a digest with 192 bits. The important question for me is: is the collision resistance comparable to an algorithm providing 192 bits?

I benchmarked a lot of different hashing algorithms and the fastest performing hash, that is also reviewed and provides a long digest (which can be an indicator of better collision resistance), is Blake2b performing slightly above 1500 megabytes per second and provides a 512 bit digest. A combination of different algorithms would be even faster, and for my use case performance is key.

TL;DR: We don't know how secure your construction is with regards to collision resistance. We do however know that it isn't a cryptographically secure hash.

  I permanently need to hash lots of data quickly, but the result only needs to be collision resistant ... So I do not even need to really use "cryptographic" hashing algorithms (CRC32 is perfectly fine here I guess).

If you require collision resistance you generally require a hash with large output. CRC32 would certainly not be fine. You would normally use a cryptographic hash to achieve this; you definitely need a large output size of the hash (i.e. 160 bits or over).

  Is there any negative side-effect of using multiple (say 2) algorithms providing a shorter digest (e.g. RIPE-MD-128 and Tiger128) versus using an algorithm providing a digest of the added length (e.g. SHA256).

Well, yes, it won't provide as much security. How much less may be tricky to calculate though. MD5 and SHA-1 concatenation was used by SSL for a while. However, a paper by Antoine Joux: Multicollisions in Iterated Hash Functions has shown that these constructions aren't very secure when it comes to finding collisions. If the input cannot be manipulated then the chance of a collision happening should still be high though (i.e. finding collisions implies an active attack).

  More specifically my idea is to use multiple REALLY FAST algorithms (clhash performing at over 4 gigabyte per second on my testsetup, xxhash performing at over 6GB/s, ...) and simply concatenate them to improve collision resistance.

You don't use any cryptographically secure algorithms, so the result is unlikely to be secure as well. At the very least it is probably impossible to prove security as the algorithms may be mathematically linked somehow.

With regards to collision resistance: it is likely that it will provide about 192 / 2 = 96 bits of resistance in case active attacks are not considered. It would be very hard to provide that it does because the algorithms may be somehow related.

It could be equally hard to find a way of showing that it does not provide 96 bits of resistance as proving that the algorithms are related may be hard as well.

A method of speeding up hash calculations is to use a Merkle- or hash tree. This will enable parallel processing to calculate the hash values.


How much processing power should you assume an attacker has? The answer to this question says that you should assume an attacker can do one billion operations per second: Key Size for Symmetric Homomorphic Encryption Over the Integers

Is that a single attacker with a simple desktop computer, or is that someone with a bot net or super computer?

I'd say it depends of value of the assets. If you need to protect data worth let's say $10m, you can assume someone could throw at least money up to that value to get it. Converting money into computational power with AWS or Azure is pretty trivial today, and it can be done by virtually anyone.

And of course state-level parties might be interested in your data for whatever reason they like (for example NSA, interested even in your private photos - see Can They See My Dick?), and they might throw computational power of much higher value that traditional cyber-criminal could justify in given case.

So in short: always assume adversary might have supercomputer or powerful botnet.


What is a white-box implementation of a cryptographic algorithm? What is a white-box implementation?

Does a white-box implementation have specific properties?

This article is a nice introduction to the concept of white-box cryptography. It can be viewed as the devious cousin of code obfuscation.

In simpler words: usually, security of a cryptographic algorithm is studied in the "black-box" model: e.g., for symmetric encryption, the attacker is given access to a "device" which runs the encryption algorithm with a given key, and can submit plaintexts and ciphertexts, the goal of the attacker being to be able to decrypt a given block without submitting that exact block as ciphertext. In the "grey-box" model, the attacker also has access to some partial side-channel information; this is where power analysis fits. In the "white-box" model, the attacker has full access to the internal state. The white-box model is meant for: "the algorithm runs as software on the attacker's own computer".

White-box cryptography is less ambitious, and correspondingly a bit less impossible, than the Holy Grail of video game vendors, namely preventing any kind of reverse engineering; WBC aims at protecting "just" cryptographic keys. WBC studies techniques by which a white-box implementation could be made, and also what security characteristics could be achieved assuming that a white-box implementation exists.

Brecht Wyseur wrote a PhD thesis on white-box cryptography (there is also a downloadable presentation). See also this site (from B. Wyseur).


Dividing elements in $R_q$ by $z$ in Grag-Gentry-Halevi (GGH) Graded Encoding Scheme I'm trying to understand the GGH graded encoding scheme, but something there leaves me very confused and I can not figure out how to explain it:

Let $R := \mathbb{Z}[X]/(X^n+1)$, where $n$ is a power of $2$ (hence $X^n+1$ is irreducible in $\mathbb{Z}[X]$); $q := 2^a$ for a large enough $a$;
$R_q := R/qR$, i.e. $R_q = \mathbb{Z}_q[X]/(X^n+1)$.

In the scheme, we choose $z$ uniformly at random in $R_q$. Then the scheme uses this $z$ to divide other elements in $R_q$, like $[c/z]_q$. But is it correct? I believe $R_q$ is not field (it is not even integral domain) and so not every element there has it's multiplicative inverse.

Or maybe I misunderstood the notation?

Thank you for any advice.

I believe $R_q$ is not field

Yes, it is not a field in general. $R_q$ is a field if, and only if, $q$ is a prime and $X^n+1$ is irreducible over $\mathbb{Z}_q[X]$.

However, you are not forced to pick $q$ as a power of two. As section 4.2 of the original paper explains, the only restriction over $q$ is

$$q \ge 2^{8\kappa \lambda}n^{o(\kappa)}$$

In particular, you can let $q$ to be prime (as it is supposed to be in Lemma 5).

And even if you don't select $q$ as a prime, you just have to check that $z$ has an inverse in $R_q$ and that the order of $z^{-1}$ is bigger than $\kappa$. If this is the case, then you are fine, if not, then sample another $z$.


Possible to split a secret to generate a re-encryption key (PRE)? I am wondering, if it is possible to split a secret (s.th. like shamir's secret sharing) which can be used to generate a re-encryption key in proxy re-encryption and only serve the splitted portions for the sake of generating a re-encryption key which can only be used for a specific public key?

So something like:

sec = secret to decrypt message
sec1 = portion of sec
sec2 = portion of sec

pkr = public key of receiver of the message
pkm = public key of bad actor who wants to re-encrypt for him
sec1_pkr = getKey(sec1, pkr)
sec2_pkr = getKey(sec2, pkr)

reKeyPkr = getReKey(sec1_pkr, sec2_pkr, [secn_pkr...], pkr) = re-encryption key for receiver pkr
reKeyPkm != getReKey(sec1_pkr, sec2_pkr, [secn_pkr...], pkm) = re-encryption key for receiver pkm
...

Something similar to what you ask, although not exactly, is the PRE scheme called Umbral. It has a reference implementation called pyUmbral. (Disclaimer: I'm the author of Umbral).

Umbral is a threshold PRE scheme, which means that re-encryption is divided among several proxies and at least certain threshold of them has to cooperate. With Umbral, the delegator can generate M-out-of-N re-encryption keys, in a way similar to Shamir's Secret Sharing.

I think you probably can reuse some of the techniques used in Umbral to split the delegator's private key and generate re-encryption key shares from the shares of this private key, rather than Umbral's approach which consists in generating directly re-encryption key shares. Anyway, both approaches should be very similar from the perspective of the application of Shamir's Secret Sharing.

I also think these techniques can be easily adapted to pairing-based PRE schemes, such as AFGH and others.


What is this "finite field cryptography"? See RFC 5931 § 2.2.1 which talks about "finite field cryptography" as opposed to elliptic curve cryptography and it looks like it is describing the Diffie-Hellman protocol. But Diffie-Hellman is not a done over a finite field, so is this some different class of algorithm?

"Finite field cryptography" is fancy language for group-based cryptography done over the integers modulo a prime (instantiating a field) to distinguish this more "classic" approach from the new fancier elliptic curve cryptography.

Example:
Finite Field Diffie-Hellman: Diffie-Hellman done in $\mathbb F_p$.


The correct use of the term "TLS session" TLS consists of sub-protocols including the handshake where the key-exchange is and the record protocol. If I want to use a statement like:

  both parties negotiate a ciphersuite that defines the algorithms that
  will be used in the session

Is this a correct statement? Can I use the term session in a context that includes the key-exchange? The term session gives me the impression that it is after the key-exchange has been done. However, I use it in my statement because I am not sure if the ciphersuite defines anything beyond the key-exchange?

Need more clarifications please.

Yes, that looks like a correct usage of the word session.

Of course the session keys are only valid for the record layer. But the session keys are tied to the session, not the other way around. And usually the TLS session is of course tied to a TCP/IP session, but that doesn't need to be the case.


How to generate unique (random) numbers that can be traced back to a unique source number? I need to generate unique (random) numbers that I can trace back to a unique source number.

For example:

source number A can generate numbers A1, A1, A3 .... Am
source number B can generate numbers B1, B2, B3 .... Bm
...
source number N can generate numbers N1, N2, N3 .... Nm

All the source numbers A, B, .. N and generated numbers Ai, Bi, Ni should be unique and mutually exclusive.

Now for any generated number Ai, I should be able to compute unambiguously the source number A (and the same goes for Bi, Ci, ... Ni).

Can anybody help with the algorithm for this?

Use case: a user types a numeric code generated by this algorithm. The server should be able to identify this user, from the code alone. For others it should not be possible to identify the user, nor generate subsequent codes for that user.

The numbers $n$ (coding source) and $m$ (coding index for a given source) can be combined into a single  bitstring; e.g. with  $0\le m<2^u$ and $0\le n<2^v$, as a bitstring of $\lceil u+v\rceil$ bits. Then, converting that single bitstring into a unique random-like number can be done by encryption with a secure block cipher with block width $w\ge u+v$ bits and a fixed secret key (prefixing input with $w-\lceil u+v\rceil$ zero bits in order to reach the width $w$ of the block cipher). The random-like number will be an integer corresponding to the ciphertext bitstring, thus in range $[0\dots2^w-1]$.

Distinct pairs $(n,m)$ inputs allways lead to distinct output, because a block cipher is a permutation of its block space. Decryption (requiring the key) allows recovering the original bitstring from the random-like number, and from that $n$ and $m$. If one checks that what's deciphered could have been obtained from a valid $(n,m)$ (including $w-\lceil u+v\rceil$ zero leading bits), residual odds that a random bitstring is acceptable are $2^{u+v-w}$.

Using AES ($w=128$, regardless of key width) and $u=v=40$ ($n$ and $m$ up to about a trillion), these residual odds are $2^{-48}$. Problem is, the random-like number is up $2^{128}$ (about $39$ decimal digits). The classic 3DES ($w=64$) or the relatively unproven Speck ($w\in\{32,48,64,96,128\}$) are alternatives.

If you want a shorter unique random-like number (with as a counterpart higher residual odds that a random bitstring will be acceptable), or more choices for $w$, use format-preserving encryption; we have a number of questions about that.


Is it feasible to build a stream cipher from a cryptographic hash function? A few years ago I devised a symmetric-key system that worked like so:

H()   = some hashing function
h     = the number of bits in the result of H()
key   = bits to be used as a key
^     = the XOR operation
+     = concatenation
len() = the length function (in bits)

max = ceiling(len(cipertext) / h)
pad = pad_0 + ... + pad_max
pad_0 = H(key) ^ H(plaintext)
pad_n = H(pad_(n-1))
cipherpart_n = plaintext_n ^ pad_n
ciphertext = H(plaintext) + cipherpart_0  + ... cipherpart_max

Basically, it builds up a "pad" based on the hash of the message and hash of the key and XORs the message against it.

I am not actually an expert, so I was wondering why an approach like this isn't very common.

With the corrected system (which actually uses the key), I see these weaknesses:

If the attacker can guess some plaintext_n, he can derive pad_n from ciphertext_n and from this all the following pad_i - which means that he can read the rest of the message.
The ciphertext starts with a H(plaintext), which means that an attacker which can guess the plaintext has a means to verify this guess. To avoid this, the plaintext should at least be randomly padded. (But then you could simply use these random bytes as the initialization vector instead of the hash of the plaintext).
The entropy of your actual key stream (the pad) is reduced to h bits, even if the key itself had bigger entropy. This might be better if you input the key again to the hash function for creating the higher-order pad_n.
As already said by Jack, the need to hash the plaintext before you can start to encrypt it means that you need two passes over the plaintext, which means that the encrypting algorithm is not an online-algorithm (the decryption is).

Other than this, your algorithm is similar to the Output feedback mode of operation for Block ciphers, with the initialization vector derived from the message, and without new key input for the following steps.

Here is a variant which would not have these weaknesses (and hopefully no others):

initvec = random
pad_0 = H(key + initvec)
pad_n = H(key + pad_(n-1))

ciphertext = initvec + cipherpart_0 + ... + cipherpart_max

(The rest as in your example.)

This does not do integrity-protection ... for this you would append some keyed MAC at the end (so it can be an online algorithm).

Then we have actually the OFB mode of a strange "encryption only" block cipher derived from the hash function. The only problem would be that it would be quite slower than a normal block cipher, as Jack already mentioned.

Disclaimer:

Note that while this construction is secure in the random-oracle model (see this blog entry for a proof of a similar construction, using a counter instead of previous hash), the proof uses properties which are not implied by the collision-resistance and preimage-resistance properties of a hash function (which is what hash functions are constructed for).

So while this might work, it does not have to work with real-world hash functions.


Challenge / Response to Prevent Replay Attack - Using nonce as challenge I am implementing a radio protocol and trying to prevent replay attacks. It is an embedded system so storing nonce values is not an option, as each node in the system may talk to each other.

My plan is to implement a challenge response system to authenticate both ends of the communication. Instead of separately generating a unique value for the challenge, my intention is to use the nonce as the challenge and then encrypt the nonce using ChaCha20 and the pre-shared key for the challenge response.

Is it safe to encrypt the previous nonce? This will not be a random unpredictable value, but it will be unique and it wont be the same nonce that is used to encrypt the current packet. The attacker will know both the plain text and the encrypted form (is they know the protocol), but this only helps for a brute force attack, I believe?

The packets are authenticated with poly1305 using the same key.

In general symmetric ciphers are not vulnerable to attacks with known plaintext. So in general it is perfectly possible to encrypt the previous nonce.

With multiple nodes it would be a good idea to include the identity of the sender / receiver in the challenge or at least in the poly 1305 based authentication. Otherwise an attacker may trick a node into authenticating a different node than intended.


Extended Canetti-Krawczyk - Clean Session Definition In the extended Canetti-Krawczyk (eCK) model [1] the adversary $\mathcal{M}$ is allowed to make a sequence of queries, eventually performs a $Test(sid)$ query, receives a value $C$ and at some point later has to guess whether $C$ was the session key or a random value. In order for $\mathcal{M}$ to win the experiment, they have to both guess the challenge correctly and the test session has to be clean. The latter means none of the following conditions may be true:

$\mathcal{A}$ or $\mathcal{B}$ is an adversary-controlled party. This means in particular that $\mathcal{M}$ chooses or reveals both the long-term and ephemeral secret keys for the party and performs all communications and computations on behalf of the party.
$\mathcal{M}$ reveals the session key of $sid$ or $sid^*$ (if the latter exists).
Session $sid^*$ exists and $\mathcal{M}$ reveals either both $sk_\mathcal{A}$ and $esk_\mathcal{A}$, or both $sk_\mathcal{B}$ and
$esk_\mathcal{B}$
Session $sid^*$ doesn't exist and $\mathcal{M}$ reveals either $sk_\mathcal{B}$ or both $sk_\mathcal{A}$ and $esk_\mathcal{A}$

The first condition appears to state, that the adversary $\mathcal{M}$ would not be allowed to perform a man-in-the-middle attack on the test session between $\mathcal{A}$ and $\mathcal{B}$.
As far as I can tell, the original CK model didn't make such a restriction and intuitively I don't see why the adversary would be forbidden to impersonate the parties to each other. It would demonstrate that the adversary is able to break the authentication of the AKE protocol and as such it wouldn't be secure.
Am I misunderstanding the definition or is this actually forbidden in the model? If a MITM is allowed, then please point out the particular aspect of the model definition that allows this.
[1] LaMacchia, Brian, Kristin Lauter, and Anton Mityagin. "Stronger security of authenticated key exchange." International conference on provable security. Springer, Berlin, Heidelberg, 2007.

The first condition appears to state, that the adversary $\mathcal M$ would not be allowed to perform a man-in-the-middle attack on the test session between $\mathcal A$ and $\mathcal B$.

This is not correct. The eCK model does allow MitM attacks.
For some more background on formal AKE models see this question. To quickly recap, in an AKE model (including the eCK model) the adversary is assumed to control the entire network and can re-route, change, and drop message as it sees fit. In particular, this means that the adversary can do MitM attacks almost by definition. Then, to measure the adversary's ability to break the protocol, the adversary is given a Test session (a running instance of the protocol at some party, say $\mathcal A$) for which it is asked to distinguish its real session key from a random key. If the adversary can't do this, then we say that the protocol is secure. Notice in particular that the adversary can pick a Test session for which the adversary itself created all the messages it sent to the Test session (thus modelling a MitM attack). This is also true for the eCK model.
However, AKE models (including eCK) usually go beyond just MitM attacks, and also allow the adversary to obtain many of the secret values in the system too. This can include session keys derived by sessions other than the Test session itself, long-term keys held by the parties, and also the full internal randomness used by the sessions (the eCK model allows all three of these). However, once we start allowing the adversary these additional powers, certain unavoidable attacks start to become possible. It is this that the quote you refer to is about. In particular

$\mathcal A$ or $\mathcal B$ is an adversary-controlled party. This means in particular that $\mathcal B$ chooses or reveals both the long-term and ephemeral secret keys for the party and performs all communications and computations on behalf of the party.

deals with the following attack. Suppose the adversary picks the Test session to be at party $\mathcal B$ (communicating with a session at party $\mathcal A$). Now, using the powers granted to it in the eCK model, the adversary obtains the long-term key of party $\mathcal A$ as well as all the internal randomness used by the the running instance at $\mathcal A$. At this point the adversary has all the secret values that the honest session at $\mathcal A$ would use when communicating with $\mathcal B$, hence it can trivially impersonate $\mathcal A$ towards $\mathcal B$ allowing it to compute the same session key as the Test session (at $\mathcal B$). Thus it can trivially break the protocol. However, note that this attack is unavoidable given the powers the adversary is given. Thus, to make the eCK model meaningful, these trivial attacks need to be disallowed, and this what the restriction above does.
In summary, the eCK model allows MitM attacks, but since it also allows the adversary additional powers (such as obtaining certain secret values in the system), it must also impose some constraints on the adversary in order to account for the possibility of trivial attacks made possible by these powers.


The relationship between a private and public key? It's known that the relationship between public and private key allows data encrypted by the public key to be decrypted only by the corresponding private key.

As I understand it, this means that normally there is a relation between them (regarding obtain one from the other).

But I found this:

  It is almost impossible to obtain the private key from the public key.

My question is how a private key can decrypt data encrypted with a public key, without it being possible to obtain the private key from the public key, since there has to be a relationship between them for decryption to work?

We'll assume RSA rather than elliptic curve, just because it's simpler.

A key consists of a modulus and an exponent. Both the public and private key use the same modulus, what differs is the exponent. To encrypt (or decrypt) you take your message, raise it to the power of the exponent, divide the modulus, and the remainder is your encrypted (or decrypted) answer.

How to generate your key

You start with two random prime numbers ("p" and "q"), if you have a 2048-bit key, then P and Q are both 1024 bits long. You multiply them together; that's your "modulus" -- the unique part of your public key. The other part of your public key (the "exponent") doesn't need to be unique, but it should be prime; most people just use 65537 because it's safe enough, and it makes your implementation fast.

Now let's figure out the corresponding private key. All you need to do is find the modulo multiplicative inverse of your public exponent with respect to (p-1) times (q-1). The math is simple, but not important here; it's just a simple calculation. That result you get, that's your private exponent; that's the "secret" part about your private key. You're done with P and Q now, throw 'em away.

So encrypt/decrypt a value: raise the value to either your public exponent or private exponent, divide by your modulus (same modulus for both keys) and the remainder is your answer.

Now let's try to attack it

I have the public key (which consists of the number 65537 as well as the modulus (P * Q) and what I'm trying to figure out is the number derived from (P-1) * (Q-1). If I knew what P and Q were, that would be dead-simple. But I don't. Instead, I know what P * Q is.

This is why people say that breaking RSA just boils down to factoring large numbers. Because if I could factor P * Q into P and Q, then I could re-derive the private key.

How are the keys related

The link between the two is this multiplicative inverse thing; it's like how 2 is linked to 1/2 and 13 is linked to 1/13. One can undo the other. Except that the relationship only exists in this finite field defined by the modulus. This is that wrap-around math world which is a lot like dealing with time on a clock -- where 10 plus 3 is 1 instead of 13 (because the clock only goes up to 12).

So to calculate that inverse relationship directly from the public key, you'd end up having to try to compute it over and over, with 1 trip around the clock, two trips, three, and so on until you got an answer that works. This turns out taking more time than the factoring challenge, so everybody just sticks to factoring.

This post contains mild technical inaccuracies mostly for brevity and simplicity. Feel free to leave a comment if you're the type of person who likes to argue on the Internet for fake points, but you will likely be summarily ignored.


Why is Serpent faster than AES in this benchmark? I have a laptop without the AES-NI CPU instructions but with SSE4.1.

I'm using Linux and tried the (in-memory) cryptsetup benchmark to get the rough tendency which returned:

#  Algorithm | Key |  Encryption |  Decryption
     aes-cbc   128b   101,4 MiB/s   159,6 MiB/s
 serpent-cbc   128b    52,7 MiB/s   203,4 MiB/s
 twofish-cbc   128b   126,4 MiB/s   176,1 MiB/s
     aes-cbc   256b   107,8 MiB/s   120,4 MiB/s
 serpent-cbc   256b    52,9 MiB/s   203,3 MiB/s
 twofish-cbc   256b   135,2 MiB/s   177,0 MiB/s
     aes-xts   256b   160,6 MiB/s   160,2 MiB/s
 serpent-xts   256b   181,2 MiB/s   188,6 MiB/s
 twofish-xts   256b   164,4 MiB/s   166,2 MiB/s
     aes-xts   512b   121,4 MiB/s   121,0 MiB/s
 serpent-xts   512b   181,4 MiB/s   188,6 MiB/s
 twofish-xts   512b   164,7 MiB/s   165,4 MiB/s

I'm very surprised:

AES has fewer rounds than Serpent so AES should be faster.
AES usage is much higher than Serpent so one could expect the Linux AES crypto module to be much more optimized than Serpent's.
There is no speed decrease with bigger key size in Serpent while there is in AES.
The tests I made 1 year ago on the same computer gave the same speed for AES but all Serpent entries were averaging at 50 MiB/s.
To my knowledge, there has been no huge enhancement of Serpent kernel module in the past year.

Would you trust this "benchmark"? If not, how would you explain the great results for Serpent?

AES has fewer rounds than Serpent so AES should be faster.

The number of rounds by itself is meaningless. Some ciphers have a few complex rounds and others have many simple rounds. See my answer to Why does SHA-1 have 80 rounds? for a related explanation.

  There is no speed decrease with bigger key size in Serpent while there is in AES.

The performance is determined by the number of rounds, and not directly influenced by the key-size.

The AES designers decided that 14 rounds are required for a 256 bit security level and 10 rounds for a 128 bit security level. So AES-256 is about 1.4 times as expensive as AES-128. If you add overhead the relative difference becomes a bit smaller.

The Serpent designers decided to use 32 rounds for all key sizes, so performance is the same for larger keys.

  How would you explain the great results for Serpent?

When operating on a single block Serpent is more expensive than AES. This was one of the reasons why Rijndael was chosen over Serpent to become AES.

When operating on multiple blocks in parallel, Serpent profits from an implementation technique called bit-slicing. So Serpent is faster in modes that allow parallelization.

CBC encryption is sequential (You need the previous block of ciphertext to start encrypting a block), so Serpent is slow here. CBC decryption supports parallelism, since you already know the previous ciphertext block at the start, so Serpent is fast here.

XTS always allows parallelism since the encryption/decryption of different blocks is independent. So Serpent is fast in XTS mode.

It's also possible to implement AES using bit-slicing, but it doesn't profit as much as Serpent since it's possible to use lookup tables to produce an implementation of AES that's fast even for a single block. Some people prefer bit-sliced AES implementations since they avoid timing attacks associated with lookup tables.


how is the rsa $publickey(n ,e)$ transformed into a textfile allowing its public distribtution? wikipedia says about the keys itself:

  The public key consists of the modulus n and the public (or
  encryption) exponent e. The private key consists of the modulus n and
  the private (or decryption) exponent d, which must be kept secret.

I know, that public keys look like that in the wild:

  -----BEGIN RSA PUBLIC KEY-----
  MIIBCgKCAQEA+xGZ/wcz9ugFpP07Nspo6U17l0YhFiFpxxU4pTk3Lifz9R3zsIsu
  ERwta7+fWIfxOo208ett/jhskiVodSEt3QBGh4XBipyWopKwZ93HHaDVZAALi/2A
  +xTBtWdEo7XGUujKDvC2/aZKukfjpOiUI8AhLAfjmlcD/UZ1QPh0mHsglRNCmpCw mwSXA9VNmhz+PiB+Dml4WWnKW/VHo2ujTXxq7+efMU4H2fny3Se3KYOsFPFGZ1TN
  QSYlFuShWrHPtiLmUdPoP6CV2mML1tk+l7DIIqXrQhLUKDACeM5roMx0kLhUWB8P
  +0uj1CNlNN4JRZlC7xFfqiMbFRU9Z4N6YwIDAQAB

  -----END RSA PUBLIC KEY-----

or sth like:

   Subject Public Key Info:
       Public Key Algorithm: rsaEncryption
       RSA Public Key: (1024 bit)
           Modulus (1024 bit):
               00:b4:31:98:0a:c4:bc:62:c1:88:aa:dc:b0:c8:bb:
               33:35:19:d5:0c:64:b9:3d:41:b2:96:fc:f3:31:e1:
               66:36:d0:8e:56:12:44:ba:75:eb:e8:1c:9c:5b:66:
               70:33:52:14:c9:ec:4f:91:51:70:39:de:53:85:17:
               16:94:6e:ee:f4:d5:6f:d5:ca:b3:47:5e:1b:0c:7b:
               c5:cc:2b:6b:c1:90:c3:16:31:0d:bf:7a:c7:47:77:
               8f:a0:21:c7:4c:d0:16:65:00:c1:0f:d7:b8:80:e3:
               d2:75:6b:c1:ea:9e:5c:5c:ea:7d:c1:a1:10:bc:b8:
               e8:35:1c:9e:27:52:7e:41:8f

=> My question is, how are those numbers $n$ and $e$ transformed to a keyfile like above?

EDIT: Additionally, i was specifically wondering how the numbers are calculated into a keyfile. I mean, if I had a single really big number, i can imagine the number is easily converted into one of your encoding. But the public key is a combination of $n$ and $e$, and i don't know which combination.

There are two concepts that are relevant for your question: Base64 encoding and ASN.1 DER encoding.

So, to deal with the most immediate concern, take n and e as the representation of the RSA values stored in a byte array.

Base 64

Given that cryptographic algorithms usually deal with purely binary data (keys, ciphertexts, random values), their representation can lead to communication issues. The most evident: you can't send the key as a string (e.g. via email) because it can be misinterpreted and even reformatted. What is just a random byte of a key could be an EOL character, and parsing can be jeopardized.

Base64 aims to solve all that family of issues by encoding the data using only 64 printable characters. I will not detail here the encoding rules, but, at a cost of roughly 30% of communication overhead, you get rid of encoding issues dependent on the platform. A base 64 string will have only letters, numbers and the symbols "+", "/" and "=".

ASN.1 DER

The Distinguished Encoded Rules define the encoding of certain data types with the format TLV: Type Length Value. Some of the types can be classical (BOOLEAN, INTEGER), some can be understandable (BIT STRING, OCTET STRING, UTF8String, UTCTIme), some are rather specific (OBJECT IDENTIFIER, SEQUENCE, SET) and some are constructions that build over existing data types to build upon.

Unless you're very interested in the details of how it works, I would suggest to avoid the details about the encoding of each data type and use a parser instead. The encoding rules are a bit dark and contribute little to nothing to the understanding of what's built on top. You can, however, Base64-decode the public key you posted and pass the result to a tool like dumpasn1 to see how nested the structure can get.

What you're seeing

Given all the background, I can finally reply to your question. The first key you got is a PEM encoding: a ASN.1 DER structure subsequently Base-64. I have seen the structure below as an equivalent and functional text representation of the same data, but I can't seem to find the right name for that encoding.

UPDATE: It seems I published an incomplete version of my answer. Particularly, I did not include the link to the RFC 3280, which contains the definition of the DER encoding of a RSA public key (page 15). Thanks to @dave_thompson_085 for bringing it up and the useful additional links:

RFC 3280 (page 15)
PEM
RFC 3447 (Appendix A)
Wikipedia ASN.1 entry
Wikipedia BER encoding entry


Does it matter whether the KDF salt is integrity protected? I am writing a simple application, mainly as a fun challenge, but also to hopefully someday use as my password manager.

I'm using pynacl's SecretBox, which provides an extremely simple API to encrypt and MAC (presumably encrypt-then-mac, although the docs are a bit sparse on these details) data. In my application, the user is prompted for a password, which is then run through pynacl's KDF module to generate the key for the SecretBox.

Obviously, it's important to supply the KDF with a randomized salt, and if I want the file to be usable, I have to store that salt. At the moment, I am storing the salt in the first 32 (set by the pynacl constant SCRYPT_SALTBYTES); to read the file the application reads the first 32, stores that in a variable as the salt, and then reads the rest and passes that on to the SecretBox.

As a result, my salt has no integrity protection at all. The downside of the simplicity of the SecretBox API (literally a constructor, and encrypt and decrypt methods) is that there's no obvious way to sneak this extra bit of data into the MAC, and I'd rather avoid implementing my own encrypt-then-MAC scheme if possible as I'm not a crypto expert (A big part of why I chose this API is because of how idiot-resistant it appears).

Are there any concerns with allowing an attacker to modify the password salt in this context?

No, integrity protecting the salt is probably not required.

For confidentiality this is pretty obvious because changing the salt only throws away information for the attacker.
Concerning integrity things are a bit more complicated.
Suppose, these files are stored on a central server where an attacker can manipulate them and suppose that some client will automatically retry downloading the file if decryption failed or something like that.
Can an attacker learn anything about your password from knowing about decryption failures or the like for different salts?

You could construct KDFs where this is possible but for any decent KDF (it just needs domain separation) it won't be. If you have domain separation changing the salt will never influence your password in a useful way and this makes incremental testing impossible.


How to apply encryption on sensitive data exchange? I have the following scenario to which I have to apply cryptography to protect sensitive data:

An embedded Linux computer box will be creating and accepting file packages with contents that should not be accessible to anyone outside a restricted group of persons. These packages will be sent to and retrieved from the box via http or USB drives.

A software tool will exist that can create and extract the packages. This tool will only be accessible to the restricted group.
Another tool will exist that can create packages but not extract them. This will be freely distributed.

These statements also apply:

The files can be easily obtained by any potential attacker.
The box can fall in the attacker's hands at any time but we assume that they will not gain root access to it.
There will be many boxes around and a file created by either of the tools or any box should be accessible by any other box.
The boxes are distributed and are no longer accessible to the restricted group of persons (i.e. to change keys, pass phrases, etc.).

The question is what cryptographic solution can we apply to this scenario using standard algorithms and tools/libraries, and how do we protect the key(s) from a leak from the restricted group of persons (we can assume a sub-group of them is 100% trustworthy).
It would be possible setting up a server in a restricted network that could handle the decryption for the tool for the restricted group of persons.

This is the answer I can come up with after more investigation and comments above:

All boxes have a shared public/private key pair with the private key protected with a passphrase.
The software tool will have the same public key but not the private key.
The software tool also has a symmetrical key.
There is a server in a secure network that has the shared public/private keys. The server also has the symmetrical key.
When someone with the right to decrypt wants to decrypt a file using the tool they will connect to the secure network via VPN and the tool will send a request for the file to be decrypted. The request is encrypted with the symmetrical key. The server decrypts the request and then the file and re-encrypts just with the symmetrical key.
The symmetrical key can be changed every so often.
Instead of the symmetrical key we could use a second public/private key pair.


Deriving 256-bit key from PBKDF2-SHA1 I am working in .NET and their PBKDF2 only uses SHA-1.  I am using it to, given a user-supplied password and random salt, generate a 256-bit AES key.  The plaintext is encrypted with the AES key and the ciphertext and salt are then stored.  SHA-1 has a 160 bit output size.  So if I specify 100000 iterations to PBKDF2 it will actually run 200000 iterations.  Let's say an attacker did a dictionary attack on the password (running each password and the known salt through the key derivation and trying to decrypt the data with the derived key). Would he also need to run 200000 iterations, or is there a shortcut he could use that would only require 100000 iterations?

The OWASP states:

  Using PBKDF2 for password storage, one should never output more bits than the base hash function's size. With PBKDF2-SHA1 this is 160 bits or 20 bytes. Output more bits doesn't make the hash more secure, but it costs the defender a lot more time while not costing the attacker. An attacker will just compare the first hash function sized output saving them the time to generate the reset of the PBKDF2 output.

But since I am not storing passwords, is the above not concern for me?

Of course it would be nice if .NET supported PBKDF2-SHA-512, but as far as I know that is not yet the case.

Note: If I understand correctly, my 256-bit AES key only offers 160 bits of security (due to 160-bit output length of SHA-1), but that seems not too problematic considering a dictionary attack on the password would likely be much more appealing to attackers than a brute force attack on the key.

I think it's OK in this instance: an attacker cannot check the first half of the hash (160 bits) because he cannot use AES-256 yet; the key is incomplete. So he needs to run the second half too. He needs the full key to check the decryption.

The OWASP guide refers to the case where the output of the PBKDF2 function is stored directly as the hash-check in a database. In that case the first 160 bit check is already enough to discard almost all invalid passwords. In the rare case the 160 first bits match, you can do the second half to confirm, and that's no extra work, really.


Why we use a fixed inverse Multiplication Matrix in AES I just want to  know that in AES we use following multiplication matrix for encryption.

2 3 1 1
1 2 3 1
1 1 2 3
3 1 1 2

and for decryption it use's following matrix.

0E 0B 0D 09
09 0E 0B 0D
0D 09 0E 0B
0B 0D 09 0E

So my question is that can i change these matrices? and what is the process of doing that.

The matrices are inverse of each other. Specifically, we work in a vector space of dimension $4$ over the finite field $\mathbb{F}_{256}$. That finite field (also often denoted by "GF(28)", with "GF" meaning "Galois field") is the one defined in section 4 of the AES standard. From there, matrix inversion is classic algebra.

Now, about the process... These matrices have been defined in the following way:

The AES designers thought real hard to make matrices that ensure good security properties, in particular proper behaviour with regards to differential cryptanalysis, while at the same time trying to achieve good performance for a large variety of implementation strategies, notably hardware circuits. Not all matrices are equivalent to each other in terms of security, by far.
Since it is actually nigh impossible to guarantee that you did not goof up with the security analysis, the only known method to get some decent security is to show your creations to hundreds of other cryptographers and have them mull over it for a few years. In the case of AES, this was organized as the AES competition.

Therefore, if you want to set out and "change the matrices", then, rationally, you would have to follow the same process:

Think real hard about the properties you want to achieve, and find matrix values that fulfill them.
Somehow induce hundreds of other cryptographers to themselves think real hard over your creation.
Wait for a few years.
If none of these cryptographers has found anything bad in your new matrix values, then rejoice! Process is done.

Understanding the maths behind finite fields and matrix multiplication are merely the first step of a very long journey.


Decrypt all RSA ciphertexts if you can break 1% of them I was given a cryptography question during an interview the other day.

Imagine you are given an efficient algorithm which for a given RSA public key (n,e) is able to decrypt 1% of the messages encrypted with that key.

1% means that the algorithm will deterministically decrypt 1% of all possible ciphertexts on the first call, and will never decrypt the other 99% of all possible ciphertexts with any number of invocations.

Figure out an algorithm that uses this one and can decrypt any message. Any ideas?

The attacker wants to find $m = c^d$ but doesn't know $d$, but they can find $m'=(c')^d$ for a significant fraction of random $c^\prime$s. Assume that $\mathrm{GCD}(c, n)=1$.

The attacker chooses a random $r$ with $\mathrm{GCD}(r, n)=1$ and computes a new ciphertext $c^\prime$:

$c^\prime = c \cdot r^e$

This ciphertext is uniformly distributed among all ciphertexts with $\mathrm{GCD}(c^\prime, n)=1$. So the attacker has a 1% chance that they can compute the corresponding message $m^\prime$. If it doesn't work, the attacker simply chooses a new $r$.

Relate $m'$ to existing variables:

$m^\prime = (c^\prime)^d  = c^d \cdot r^{e \cdot d} = c^d \cdot r = m \cdot r$

Solve for $m$:

$m = m' \cdot r^{-1}$

$r^{-1}$ can be efficiently computed using the extended Euclidean algorithm. This means that an attacker who can break a significant fraction of messages can break all of them.

We assumed that GCD(c, n)=1. If it's not, that GCD is a factor of $n$. In the two-prime RSA case this is a complete break. In multi-prime RSA divide out that factor and you're back to the GCD(c, n)=1 case.


What is the verification algorithm for verifying RSA signatures? I am not able to find much information how how to verify RSA signatures.

I have three values.

Message = "Launch a missile."

public key:

e = 010001 (this hex value equals to decimal 65537)
n = AE1CD4DC432798D933779FBD46C6E1247F0CF1233595113AA51B450F18116115

I want to verify if the signature below is the correct signature.

S = 643D6F34902D9C7EC90CB0B2BCA36C47FA37165C0005CAB026C0542CBDB6802F

The only formula I was able to find is

$S^e = \operatorname{Pad}(\operatorname{Hash}(M))\pmod N$

Is this the correct verification algorithm? If so, I am unclear about the Pad() and Hash() functions.  How can I calculate the hash and pad functions?

I finally found an answer to this.  A simple formula to verify the signature is: $M = S^e \pmod N$.

If I take the numbers in my original post and plug them into that formula, I get $M = 4C61756E63682061206D697373696C652E$.

Then, if I use the python command below to convert the hex string back to ASCII, print("4C61756E63682061206D697373696C652E".decode("hex"))

I get "Launch a missile", which is the same as the original message.  This means I can verify the signature was correct.


Recommended minimum entropy for online passwords in 2018 Assume a simple case, that an attacker knows the password creation scheme, and that we're not dealing with state actors, nor with sites which keep passwords in plain text. We're trying to defend against offline brute force attacks on a compromised database of password hashes. And we want the vast majority of our passwords to resist an attack over ten years.

From anecdotal evidence it seems like even sites that should know better keep passwords hashed only once. (And others in plaintext, but there's nothing to do about those.)

So it seems like the answer will depend on the following:

Are single-iteration-hash databases really common? If not, what
method is the least secure and most common? (Including iteration
counts, hash types, etc.)
And how long does it take to crack these methods. (Including common
hash cracking hardware, do these databases become public and are then
cracked by the best hardware out there (think ASICs),...)
How much time do attackers spend on a password before giving up on
it (Assuming unique salts)?
More parameters?

Just saying that we'll never have enough information for an informed decision is not enough. We need some idea. We all use passwords, and not everyone uses password managers. (I'm not saying it's not a good idea. It's just a fact.)

(I initially asked this on security.stackexchange, thinking that that would be more appropriate, but got no answer there. In fact, at first I got comments questioning the basics of password storage etc. (Which were later edited out by the mods.) So I'm asking this here instead, hoping that the crowd here will have already asked itself that question.)

If the password is salted, pick a password uniformly at random from ${\geq}2^{128}$ possibilities.

Example: A sequence of ten words from a 7776-word diceware list.
Example: A sequence of twenty graphic US-ASCII characters.

If the password is unsalted, pick a password uniformly at random from ${\geq}2^{256}$ possibilities.

Example: A sequence of twenty words from a 7776-word diceware list.
Example: A sequence of forty graphic US-ASCII characters.

If you do this, the cost of evaluating a password hash—be it MD5, PBKDF2-HMAC-SHA256, scrypt, or argon2id—is immaterial: an adversary must perform an expected ${>}2^{127}$ bit operations to try enough guesses to find your needle among the haystack of possibilities.  Nobody can afford that, and it's not likely all of humanity could in the foreseeable future afford that.

Details. Suppose every one of $t$ users draws their passwords uniformly at random from $n$ possibilities.

If the passwords are salted, the expected cost of an attack to find at least one of the $t$ passwords is $O(n)$ trial evaluations of the password hash.  If the passwords are unsalted, the expected cost of an attack to find at least one of the $t$ passwords is $O(n/t)$ trial evaluations of the password hash.

The expected time may be faster if the attacker spends money to power $p$ computers in parallel: if salted, $O(n/p)$; if unsalted, $O(n/(pt))$.  But powering sixty computers for a minute is not cheaper—whether accounted in joules, rubles, or bitcoins—than powering one computer for an hour.

There are always fewer than $2^{128}$ users, so as long as $n \geq 2^{128}$, the advice above guarantees that the adversary's expected cost is always at least $2^{127}$ evaluations of the password hash.

Using a password hash like argon2id raises the cost of evaluating the password hash versus a hash function like SHA-256 not designed for hashing passwords.  It is important for engineers designing systems that handle passwords to take responsibility for raising the attacker's costs using the resources available to legitimate users, and to use a password hash.  But from the user's perspective, the advice above makes it immaterial what password hash the engineer choose, whether argon2id or MD5—the cost of an attack is insurmountable for humanity.


How much time will it take to brute force a password I am building a client-side app that will encrypt data, using password-based key generation, into the database. Can someone verify my calculations to figure out what is the right number of iterations I should use to dissuade a potential hacker?

We'll assume that the password is at least eight characters long with a mix of numbers and upper, lower, and special characters. So that makes $72$ possibilities per character
Thus total passwords to brute force $= 72^8 \approx 722$ trillion
If I want it to take 100 years to try all possibilities using 10 computers, then per second my settings should be able to produce 22,900 passwords
Now what I am unable to figure out is, how many iterations would it take to limit a GPU such as 8x Nvidia GTX 1080 to be able to generate 22,900 passwords?

We can assume HMAC-SHA-1 or HMAC-SHA-256.

There is a basic problem with your idea, which makes the entire calculation and the result pretty much meaningless. Your actual question is:

Can someone verify my calculations to figure out what is the right number of iterations I should use to dissuade a potential hacker.

Let's keep that in mind for now. You want security.

We'll assume that the password is at least eight characters long with a mix of numbers and upper, lower, and special characters. So that makes 72 possibilities per character
Thus total passwords to brute force = 72^8 = 722 trillion

It is approximately $722$ trillion, that is not equal to $72^8$ but an approximation. Other than that, this is fine (although I find $10^{12}$ more intuitive than trillion).

If I want it to take 100 years to try all possibilities using 10 computers, then per second my settings should be able to produce 22,900 passwords
Now what I am unable to figure out is, how many iterations would it take to limit a GPU such as 8x Nvidia GTX 1080 to be able to generate 22,900 passwords?

We can assume HmacSHA1 or HmacSHA256

Okay, these all belong together and can't be answered alone. Your math in 3. is fine, the question in 4. can be answered with basic arithmetic and a benchmark of the system, and the statement about the used algorithm is needed to answer number 4 at all.
I think it would be much clearer to go this way:

Find a benchmark or generate one yourself. For your specific setup I found this source. It only lists SHA1 and SHA256, but for a rough approximation it's fine to consider two hashes euqal to one HMAC ($0.5$ times the number of hashes per second). For SHA-256 it's around $23\cdot 10^9$ hashes per second and SHA-1 almost exactly three times this number.
Calculate how long it takes for your setup ($10$ systems) to test all combinations ($72^8$ - but actually this is a lower bound, not the exact number).  For example for HMAC-SHA256 this would be: $\frac{72^8}{0.5 \cdot 23 \cdot 10^9} \approx 62800$ seconds for one system, and thus $\approx 6280$ seconds for 10 systems.
If you want to achieve "security for a 100 years", calculate the number of requires iterations as $6280 x = 3153600000$, where the righthand side is the number of seconds in 100 years. The result is approximately $5 \cdot 10^8$.

To put this number into context: You can't run these $500$ million hashes in parallel. According to this list SHA256 can process around $223 \cdot 1024^2$ Byte per second, with blocksize $512$ bit that's around $3.65$ million SHA256 operations per second. So as a very rough estimate we get $\approx 137$ seconds for $500$ million iterations.

Now let's go back to the original question:

Can someone verify my calculations to figure out what is the right number of iterations I should use to dissuade a potential hacker.

Unfortunately, you completely disregarded that passwords are not uniformly distributed - and you are asking about a hacker: a person who can adapt  and choose which values to test first - it is not just a brute force algorithm.
Passwords are usually not drawn from all possible passwords with equal probability, but they are usually chosen by a person instead. The hacker knows this - and he can use it to his advantage. This can be used e.g. in a so-called dictionary attack - and if we talk about passwords we have to keep this in mind.
An alternative point of view is: Passwords actually have much less entropy than a truly random (uniformly and independently drawn) string of the same length with the same set of symbols.
So while your idea is not entirely wrong, it does not have any meaning regarding the security of the password - unless you can make sure that the passwords actually are not chosen by a person but generated with the full entropy.

Instead of trying to make up your own password hashing scheme and calculations like this one, I would suggest checking out existing solutions. There are key-derivation functions for passwords, e.g. Argon2 won the Password Hashing Competition (from 2013 to 2015). Another popular function is scrypt, and previously PBKDF2 (I wouldn't recommend using this today, but it was very popular at some point). All of them offer various parameters you can adjust to your needs, including more than just number of iterations. The modern ones allow you to adjust the memory requirement to evaluate the function, which is an entirely different countermeasure to the full search than just increasing the number of iterations.


Is DL difficult under the group of Unimodular matrices? Is discrete logarithm assumed to be computationally hard in a non-abelian group as the  subgroup of the general linear group under matrix multiplication formed by the unimodular matrices? The two assumed unimodular matrices have the form $$A=\begin{bmatrix}
    X       & 1  \\
    1       & 0
\end{bmatrix},B=\begin{bmatrix}
    X       & X+1  \\
    1       & 1
\end{bmatrix}$$, for a irreducible polynomial P_n of degree $n$.
Elements belong to a quotient field $\mathbb{F}_{2^n}=\mathbb{F}_2[X]/P_n$

You will need to solve discrete log(s) over the field itself at some point to solve the matrix equation. Now, discrete logs over $F_{2^n}$, as opposed to $F_p$ ($p$ prime) are much easier as shown in the work by Joux, but no full proof yet.

However see, e.g.,here where the abstract states
"A new index calculus algorithm with complexity L(1/4+o(1)) in very small characteristic" is presented.

The L-notation is clarified in wikipedia, but the notation above essentially means that the complexity is essentially $\exp{[ c_n (\log n)^{1/4} (\log\log n)^{3/4}}]$ so closer to polynomial than exponential and the coefficient $c_n$ goes to zero as $n$ goes to infinity.


Modes of Triple DES - When to use each? I'm studying for CISSP certification & am using Shon Harris Exam Guide. It states that there are 4 modes that Triple-DES can be used in:

DES-EEE3
DES-EDE3
DES-EEE2
DES-EDE2

I understand these modes. I also understand that EEE2 & EDE2 would be faster than EEE3 & EDE3. My questions:

What is the use-case for EEE vs EDE? Does this have something to do with the hardware that is used?
Does it matter which DES mode is used?

Thanks in advance!

Triple DES has been standardized by NIST as DES-EDE. So the EEE versions are usually not present in cryptographic libraries. Using them is not advisable for this reasoning alone. Hardware will not have support for EEE and DDD operations. fgrieu already pointed out the answer by Poncho for theoretical reasons why NIST chose DES-EDE but that's ancient history; everybody just uses DES-EDE where DES is still used.

Two key triple DES is not faster than three key triple DES. There are 3 iterations of DES per block. The number of operations is identical.

Two-key 3DES only provides a security of about 80 bits (for a key size of 112 without parity or 128 bits including parity), while three-key triple DES is still at 112 bits (for 168/192 bits key size). For generic legacy applications NIST currently advises three-key 3DES (that is, DES-EDE, see above). Two-key 3DES has been deprecated, it does not offer enough security for most purposes.

Neither of these modes should however still be used. Three-key triple DES is not broken, but it has weak keys, offers too little security for the key size used, has a small block size (problematic with counter mode and modes providing authentication) and provides lackluster performance.

You should use AES or a modern stream cipher instead. AES is a faster, 128 bit block cipher with key sizes of 128, 192 and 256 bits that provide approximately the security provided by the full key size. AES has authenticated modes such as GCM and EAX that also provide integrity and authenticity on top of the confidentiality that may be achieved if the right mode / implementation is used.

TL;DR: Use three-key triple DES (DES-EDE) only for legacy applications. You are better off rewriting the application to use AES, especially if the applications still use two-key triple DES.


Why don't parameters generated by dhparams conform to `(2^p) mod (p-1)/2 == 1`? I've used openssl dhparams to generate 512-bit DH parameters for a test. The resulting file is:

-----BEGIN DH PARAMETERS-----
MEYCQQDgkQsR2SuYabxysYaxk2oB2Us+YKNbEBQCdhBzMZ/5fb1s80PBDsch5gRD
A5TLoOG/XOc9hr6MXhNu2A6/WzZ7AgEC
-----END DH PARAMETERS-----
Vs-MacBook:LRS v$ openssl asn1parse -in dh512.pem
    0:d=0  hl=2 l=  70 cons: SEQUENCE
    2:d=1  hl=2 l=  65 prim: INTEGER           :E0910B11D92B9869BC72B186B1936A01D94B3E60A35B101402761073319FF97DBD6CF343C10EC721E604430394CBA0E1BF5CE73D86BE8C5E136ED80EBF5B367B
   69:d=1  hl=2 l=   1 prim: INTEGER           :02

Yet, if we take those numbers, and compute (2 ^ prime) % ((prime-1)/2),

the result is not 1, which I thought should be the case.  Why?

OpenSSL prefers groups where $g$ (in this case, $2$) is a generator, that is $2^x \bmod p$ can take on $p-1$ distinct values (depending on $x$).  Because of this, $2^{(p-1)/2}$ can't be 1, as if it were, $2^x$ could take on, at most, $(p-1)/2$ values.

In the $g=2$ case, and where $p$ is a "safe prime" (that is, $(p-1)/2$ is also prime), then there's a simple rule; if $p \equiv 3 \bmod 8$, then $2$ will generate the entire group (and so $2^{(p-1)/2} \not\equiv 1$); if $p \equiv 7 \bmod 8$, then $2$ will generate only half the possible elements (and so $2 ^{(p-1)/2} \equiv 1$.  A quick examination of the last hex digit of $p$ (B) gives us $p \equiv 3 \bmod 8$.

The obvious question would be "what does this matter for security"?  Well, this observation allows the attacker to deduce the lsbit of each side's DH private exponent; however it doesn't do anything other than that.  Some (including me) would question why it's necessary to reveal anything at all about the private exponent; the OpenSSL people thought that minor leakage was acceptable.

Now, if you're proposing to use the group for something other than DH, this may matter to you; however it's hard to complain that a tool doesn't work for a use it was never designed for.  On the other hand, if you need a $g$ which generates the subgroup of size $(p-1)/2$, there's always $g=4$


Can I use the ChaCha core as a 256-bit to 256-bit one-way function? I'm looking to implement Lamport signatures as a little fun project, and I need a fast one way function that maps $\{0,1\}^{256} \rightarrow \{0,1\}^{256}$.

I was wondering whether I could safely use the ChaCha core for that, by setting the input as the key, the nonce and counter to 0 and truncating the output to 256 bits?

If there are other secure, fast one-way functions I'd love to hear about them.

ChaCha builds on a 512 bit permutation and then applies a feed-forward by xoring the input into the output. Without truncation, that feed forward is essential for one-way-ness.

We're going to build a one-way function that maps a 32 byte value x to another 32 byte value y.

Using truncated ChaCha including the feed-forward

Put the x into the 32 key part of the input, put the normal constant into the 16 constant part and put something public (e.g. a constant or perhaps some kind of tweak) into the 16 byte nonce/offset part. Compute ChaCha including the feed-forward. Take whichever 32 bytes of output you like as y.

Computing x given y implies being able to recover the ChaCha key from the key-stream.  So this is a secure one way function if ChaCha is a secure stream cipher.

Using truncated ChaCha without the feed-forward

Since you truncate the output to half the permutation size the feed-forward isn't strictly necessary for one-way-ness.

In practice it doesn't matter which 32 bytes of output you choose, but if you want a security reduction to ChaCha it does.

The idea behind the proof is that the attacker knows 32 bytes of the input: the nonce and the constant. So they can undo that part of the feed-forward. This means that if you choose only the part of the output that's xor-ed with the nonce/constant but not the part of the input that's xor-ed with the key, you can omit the xor while retaining a security proof that this is as strong as ChaCha itself.

This construction mirrors the construction of HSalsa, so you could call it HChaCha. One important issue here is that Salsa puts the key into different words than ChaCha, so you need to take different words from the output in HChaCha.

=> take words 0, 1, 2, 3, 12, 13, 14, 15 as output.

My recommendation is to use HChaCha instead of ChaCha. Same security, better performance.

One interesting modification is to use a different nonce for each call, functioning as a tweak. It probably doesn't gain you much, but shouldn't hurt either.