Rainbow tables, where have I got it wrong? There seems to be some error in my understanding of the concept of rainbow tables, despite going through quite a bit of articles on it.

Let me show what I don't seem to agree with.

My plain text is 5-digit numeric input.
Hash function - MD5
Reducing func - Get the first 5 decimal digits from the cryptotext

Constructing a single chain

12345   827ccb0eea8a706c4c34a16891f84e7b
82708   71b8e22700e63c2a0c1bad6506549d3b
71822   03010f7d7933a011782c10faf91c4fca
03010   cae05e8533d17be83bce0f451d5c7dd7
05853   a6864772e19671240f491bc2c89a36e0

This gets me one entry in my Rainbow table

12345 -- a6864772e19671240f491bc2c89a36e0

Lets test this with a sample:

Test hash (nota bene: this is not a valid hash, just for consideration)

th = tb05be8531317be83bce0f451d5c7dd7

With the reducing function:

R(th) = 05853

Then on hashing gives us:

a6864772e19671240f491bc2c89a36e0

Now, though the end result matches, its doesn't resolve my hash into a valid plain text.

Would this not be the case for every hash generated through this process? The only true hash match would be the last plain text value which is hashed, and doesn't really relate to the initial plain text.

Note that for Rainbow tables you should use different reduction functions for each column.

Once you have a match on chain endpoint, you should get the start point of this chain and regenerate chain up to hash value you're looking for. This will give you the plaintext you're looking for.

To search for a matching chain, you guess the column $i$ where you think password is located and compute the chain from column $i$ to the end. In practice, $i$ is chosen to minimise attack runtime, i.e. $i=(N-1, N-2, ..., 0)$ ("walking" the chain backwards).

To check a particular column you re-compute remaining part of the chain by applying reduction and hash functions the same way you do during table generation (Note: remember that in Rainbow tables each column uses different reduction function, so to recompute chain you have to guess position in the chain). Once you have obtained a candidate endpoint, you check if it matches any of the endpoints from a table. If it doesn't, you take next $i$ and repeat the above process. If you've tried all columns with no luck, then password you're looking for is not covered by the table and the search have failed.

Once matching endpoint is found, you get corresponding starting point and recompute the chain up to column $i$. What you will get is the password you're looking for. Or maybe not because there might be collisions, in which case you go to a previous step and continue with next $i$.

In your particular simplified example (with identical reduction functions):

You start with $h=$`03010f7d7933a011782c10faf91c4fca`, compute $H(R(h))=H(05853)$=a6864772e19671240f491bc2c89a36e0
You locate a6864772e19671240f491bc2c89a36e0 in the table and get corresponding starting point – 12345.
You recompute the chain, starting with 12345, to get plaintext for the column where you've got a match, which will be 03010.


what is DHE_EXPORT cipher suite I need to know what is exactly DHE_EXPORT cipher suite and why it is still supported by some servers.
Is there any implementation or details about this weak crypto?

Export ciphers date back to the time when cryptography export was regulated by governments, most notably the US government (see this answer for a good overview of the history of export restrictions). Back then, exporting cryptography with more than 56 bit strength was forbidden. For the Diffie-Hellman Key Agreement scheme, 56 bit of security meant that they could only use 512 bit parameters (I'm going to assume that you know how Diffie-Hellman works. If not, see for example here).

All of the remaining details of the protocol are, as far as I am aware, identical to regular Diffie-Hellman. They are a relic from past times that continually crop up and cause trouble (like in the case of logjam, which is explained well in this answer and this article). There is absolutely no good reason to support them in this day and age, and if you find a server that still allows it, you should contact their admins and tell them to disable it.

(This is also a very good reason why we should not go back to intentionally weakening cryptography, as some people have proposed lately - we tried that once and it's still hurting us, over 20 years later.)


Why we cannot brute force Elliptic Curve private key? I am learning ECC, I am confused a bit how it works for now. To my understanding, G is the starting point, k is how many times you apply the dot operation. And Q is the public key, which is the final point after you apply k times dot operations, like this

Q = kG

And then Q is the public key, and k is the private key. We assume it's really hard to find k given Q and G are known. The thing I don't understand (or I misunderstood) is, if the creator of this pair of key, can calculate k times of G to get Q easily in a reasonable amount of time, why can't attacker do the same? I can start from 1 dot operation, then 2 dot operations .... and eventually, I will hit a point that's the same as Q, and because the creator already did this in a reasonable amount of time, so I guess I can do it too (as they need to do k times of operation for thing like Diffie–Hellman)? And if k is super huge, doesn't it take the creator to take a super long time to generate and use it for key exchange? But I don't think it will be that easy, otherwise, it will be useless, just not sure which part I missed.

The creator of the key pair can do it efficiently because he has to calculate $kG$ for only one value of $k$. The cost would be something like $\log(k)$ elliptic curve operations. It's very small.

What you propose is to compute $1G$, $2G$, until you reach $kG$. Since $k$ is a big number (something like $2^{256}$, it is very big), then you have to do $2^{256}$ times more operations than the creator. It is very big.


Finding if two points on elliptic curve are related On a given elliptic curve I have some points that are defined like this:
Where
$$A=a*G$$
$$B=b*G$$
$$C=(a+b)*G$$
$$D=d*G$$
$$E=(a+d)*G$$
So finally I have two equations like below:
$$A+B=C$$
$$A+D=E$$

Given the values $(C,E,A)$, is there any way I can prove that point $A$ is common in both the points $C$ and $E$?

Or can I also prove that point $A$ is part of the $C$ and $E$?

No you can't.

I'll make the argument over the integers, it directly transfers to ECC points.

Suppose you have two integers $c,e\in\mathbb Z$. You can now prove for every $a\in\mathbb Z$ that $c$ and $e$ have $a$ "in common".

For this you simply pick $b=c-a$ and $d=e-a$ and now you have the "proof" that both have $a$ in common. Note how no restrictions whatsoever have been placed on $a,c,e$ so it works with all triples.


Minimum difference collision metric Take a hash function $H$.

There will be pairs of messages of the same length $M,M'$ for which $M\ne M',H(M)=H(M')$.

Let $P(x)$ be a function counts the number of $1$s in $x$. $d=P(M\oplus M')$, or in words, $d$ is the number of bits where $M$ and $M'$ differ.

Let $T(H)$ be the minimum value of $d$ for $H$. This is the metric. It does not say anything about how hard it is to actually find these colliding messages, only that a certain minimum number of bits must change to produce a collision.

Is this metric actually useful? Is it okay for $T(H)$ to be small, as long as actually finding such a collision is infeasible, or does a small $T(H)$ imply $H$ is weak?

Are there bounds on $T(H)$ for any of the popular hash functions? (SHA2 family, SHA3 family, BLAKE2 and its variants)

Is it okay for $T(H)$ to be small, as long as actually finding such a collision is infeasible, or does a small $T(H)$ imply $H$ is weak?

If $H$ is a random function that takes large sized inputs, and produce a fixed sized output, then $T(H) = 1$ with exceedingly high probability.

Let us call then fixed size of the output of $H$ $n$ bits.

Then, for any pair of distinct messages $M, M'$, he have the probability of $H(M) = H(M')$ as $2^{-n}$ (as $H$ is assumed to be a random function).

Now, if we have $m > n$, and consider all possible $m$-bit pairs $M, M'$ that differ by one bit, we have $m2^{m-1}$ such pairs.

The probability that no such pair will collide is $(1 - 2^{-n})^{m2^{m-1}} \approx e^{-m 2^{m-n-1}}$, as $m2^{m-n-1}$ is large, this probability is tiny, and hence with high probability, there will be at least one collision that differs by a single bit.

As a collision must differ by at least one bit, we have $T(H) = 1$ (again, with high probability).

  Is this metric actually useful?

Doesn't appear to be; we don't have any way of computing $T(H)$ for any strong hash function, so it's not useful in a practical sense.  And, from a theoretical one, it's 1 for anything that acts like a random function, so I don't see any immediate use there.


Security implications of repeated hashing I have an hash function hash()

I can easily compute the hash of the string "hello" like this:

out = hash("hello");

What are the implications from a security point of view of hashing the same string as:

out = IV;
out = hash('h' + out);
out = hash('e' + out);
out = hash('l' + out);
out = hash('l' + out);
out = hash('o' + out);

I mean hashing single bytes one after another, concatenating the current byte with the previous hash (first hash could be all zeros or some IV).

I know I'll get a completely different hash. Apart from that, what are the security implications of such habit?

In terms of a hash scheme, the security of your construction can be proven secure in the same way that the Merkel-Damgard construction is. One subtlety is that you need to add a final invocation to "hash()" to make sure you don't suffer from a length extension attack as @codeinchaos mentioned.

With regard to the technique to store password, it is not recommended to have a constant IV but rather choose some random IV for every entry in your password table. This is for the reason that whenever someone breaks into your system then she could see immediately the entries that store the same password. This technique is called "salting".


Min Entropy Value for Health Test per NIST 800-90B for 32 bit Noise Source NIST 800-90B recommends Section 4.4.1 Repetition Count Test & Adaptive Proportion Test for health test on Noise sources.
In the equation to calculate the cut-off value C for Repetition Count Test, C = 1 + [-log_base_2 Alpha / H]; Alpha is 2^-20 but how is Min Entropy H being calculated ?

In the equation to calculate the cut-off value C for Adaptive Proportion Test, C= 1 +CRITBINOM(W, power(2,(-H)),1-Alpha); W = 1024, Alpha = 2^-20, How is the min Entropy H being Calculated ?

Clearly the installation of health tests must come after the development of the entropy source.  As part of that development, you'd need to assess the min.entropy of your new system under whatever sampling methodology you choose. And Min Entropy H comes out of that assessment. It is "the min-entropy of the samples from a (digitized) noise source or of the output  from  an  entropy  source;  the  min-entropy  assessment  for  a  noise  source or entropy source."

NIST suggests two tracks, either:-

Confirm IIDness via permutation testing, and take min entropy as log(Pmax[]).
Estimate it on the basis of a non-IID hypothesis using the methods of § 6.3 Estimators.

It's all detailed in §6 Estimating Min-Entropy. Track 2 is known to be unreliable as our measurements of entropy of non-IID sources are still inadequate. I recommend that the tightest bounds on measuring Min Entropy H will be achieved by  evolving your sampling methodology to obtain IID samples.


For a one-time pad, which MAC method is information-theoretically secure? In the the main post about MAC methods it mentions a few methods:

Authenticate And Encrypt: The sender computes a MAC of the plaintext, encrypts the plaintext, and then appends the MAC to the ciphertext.
Authenticate Then Encrypt: The sender computes a MAC of the plaintext, then encrypts both the plaintext and the MAC
Encrypt Then Authenticate: The sender encrypts the plaintext, then appends a MAC of the ciphertext.

I would like to know which of the last two methods (listed above) is better to provide integrity and authentication for a one-time pad message using HMAC. The method would need to be information-theoretically secure. I do not think it matters if the HMAC method wastes parts of the one-time pad to encrypt the MAC tag.

This paper which is linked in the post above Sadeq Dousti  mentions:

  On the positive side we show that the authenticate-then-encrypt method is secure if the encryption method in use is either CBC mode (with an underlying secure block cipher) or a stream cipher (that xor the data with a random or pseudorandom pad). Thus, while we show the generic security of SSL to be broken, the current practical implementations of the protocol that use the above modes of encryption are safe.

If HMAC was applied to a one-time pad message using the Authenticate then Encrypt method, would this be more secure than using Encrypt then Authenticate method?

My thoughts on this are that the Authenticate then Encrypt method is information-theoretically secure because the MAC tag is encrypted by the one-time pad as well. Are there any actual attacks against Authenticate then Encrypt when used with the one-time pad? The paper above claims it is still secure. Also when providing input into the HMAC function, the attacker is missing two key parts of the equation (the plaintext and the key) to be able to create a forgery. There could be any combination of message and any combination of key. It would be impossible for an attacker to determine the real message.

The general consensus in the post earlier seems to be that Encrypt then Authenticate is more secure method when using standard encryption methods. However this would leave the MAC tag unencrypted so it is not information-theoretically secure. The attacker is already provided with the ciphertext, so perhaps a computationally unbounded adversary could brute force key combinations using HMAC to find the pad/key which matches the MAC tag and available ciphertext, therefore eventually they would find a matching key and be able to decrypt the message.

Maybe one method to use the Encrypt then Authenticate method in an information-theoretically secure way would be to split the one-time pad into two parts. One part to encrypt the ciphertext message and the other to encrypt the MAC tag. First the message would be encrypted with the first part of the pad. Then the HMAC computed on the ciphertext using the full one-time pad as the key. Then the MAC tag would be encrypted with the second part of the pad and appended to/sent with the ciphertext. For verification it means you can verify the MAC faster by only decrypting the MAC tag first which is a simple xor operation. Maybe it provides just enough speed boost to fend off a Denial of Service attack?

Which is the better option to use? What alternatives are better for an information-theoretically secure MAC to be used with a one-time pad?
Is there any rule where the MAC tag output length should be related to the length of message or key which is input into the HMAC?

For example, if the message was 64 bytes in length, should the HMAC tag length be 1/4 of it (16 bytes/128 bit), 1/2 of it (32 bytes/256 bit), same length (64 bytes/512 bit) or something else? Given that the MAC tag will probably be encrypted with one-time pad anyway, is it possible to get away with a shorter tag length and still be information-theoretically secure?

First of all there does exist information theoretically secure message authentication codes suitable for use with a one time pad. An HMAC is not one of those information theoretically secure.

As far as I recall the first article presenting such a construction is the 1981 article by Wegman and Carter: New hash functions and their use in authentication and set equality

The construction build upon a specific class of universal hash functions. The MAC is constructed by computing a hash tree over the message, and finally applying a one time pad to the MAC tag.

Since we are not talking about a specific hash function but rather a class of hash functions, you will need key material to chose a hash function for each level in the tree. The key material needed at each level will be the same size as the final tag, the number of levels will be logarithmic in the maximum message size.

The key material used to chose hash functions for each level in the tree is reusable. The one time pad applied to the tag is of course not reusable. Quite conveniently the part of the key material which can be used only once is the smaller part, and doesn't grow with the message size.

If you combine this authentication scheme with a one time pad, the number of key bits consumed by the one time pad will be much larger than the number of key bits consumed by the authentication.

But this kind of authentication scheme can also be used in scenarios where you just need the authentication and not the confidentiality. For example the classical channel used in quantum key exchange need authentication but not confidentiality. So the two can supplement each other well as this construction provides the authentication needed for the quantum key exchange, and the quantum key exchange produce a stream of bit suitable for a one time pad, which can then be utilized by the authentication.

I have seen newer constructions than the one from the Wegman Carter article. All of them have build on the idea from the Wegman Carter article. They use the same hash tree plus one time pad construction, but they use other classes of hash functions. If each message will be several MB in size, I believe bucket hashing from a 1997 article by Rogaway is the fastest algorithm.

The question about whether to authenticate or encrypt first is a moot point if you are combining this kind of authentication with a one time pad, because the authentication itself by definition applies a one time pad to the tag.

Whether you apply a single one time pad or two one time pads to the tag doesn't change the security one bit. However if you do end up applying two one time pads, you will use twice as many key bits to achieve the same level of security. This would however only matter for small messages, because for large messages the key bits used for authentication is negligible compared to those used for the one time pad on the message.


How would you name and/or describe this algorithm? First up: this is not a decoding request or anything. This is about terminology.

Twice per year, we email another department to ask for a new licence file for their software. They are always slow to reply. The licence files are encrypted, but I noticed only a couple of characters change between revisions. My 'home-grown crypto' sense tingled. I surmised the characters that changed might correspond to the expiry date in the plaintext.

Ciphertext:

GO9ETBBE
GO9ETCBE
GO9WTBBE

Plaintext:

20150101
20150601
20160101

You can see it's not a substitution cipher. However a particular character at a particular position is always mapped the same way. For example, '1' at the third position is always mapped to '9'.

I amused myself by reverse engineering the rest of the algorithm (Python code):

letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 "
secrets = "C3H8NJ1AX5VRU 2F04KYDIS6PQMOG9TLB7EWZ"

def decrypt(ciphertext):
    plaintext = ""

    for i,x in enumerate(ciphertext):
        j = secrets.index(x)
        j -= i # offset moves backwards 1 each character
        j %= len(secrets)
        plaintext += letters[j]

    return plaintext

def encrypt(plaintext):
    ciphertext = ""

    for i,x in enumerate(plaintext):
        j = letters.index(x)
        j += i
        j %= len(secrets)
        ciphertext += secrets[j]

    return ciphertext

Anyway, my questions are:

Is there a name for the "a particular character at a particular position is always mapped the same way" assumption?
How would you describe the algorithm? Colloquially I'd call it a "substitution cipher with a rolling offset"

I don't think there is a name for this special kind of property, but it is a clear hint for polyalphabetic substitution ciphers.
It is a special kind of polyalphabetic substitution cipher. The first alphabet is a normal random key, while each successive alphabet is generated by a one-character right shift of the previous alphabet. As a result there are as many alphabets as there are characters in the plaintext (or cipher text) alphabet.


Purpose of key evolution? When generating and exchanging keys, what is the purpose of performing key evolution after public key exchange + authenticated encryption?

I believe that the purpose of performing key evolution after the public key exchange and authenticated encryption is to provide forward secrecy. While generating and exchanging keys there are two security objectives. First, partial send deniability, which is provided by the public key exchange and authenticated encryption. Second, the forward and backward secrecy, provided by the key evolution.


Are the metadata encrypted by PGP? I know that PGP provides an hybrid scheme of encryption which can ensure both the encryption of a message and the authentication, but how it stores the secondary data, such as the object, the sender, the receiver, time, etc. on the server? Are they encrypted or stored in plaintext?

The secondary data or metadata are stored in plaintext.

Should you receive an encrypted mail by pgp, you will notice that you have 2 files attached: noname.pgp and encrypted.asc. Thus the content of the message is hidden but not the metadata.

Why don't we also encrypt the metadata? Well how would we know who to give the mail to then? If you give your mailman a letter and don't tell him who the receiver is, how do you expect him to give it to the right person?

By the same principle, your receiver should be able to at least know what the message is about. Should you not want anyone to know, you could also leave the field blank.

Hence no, only the content is encrypted the meta data are still in clear text.


How to show Hash-Then-Encrypt is not AE-secure (E,D) is a CPA-secure cipher defined over (K,M,C).H: C → T is collision resistant hash functions.
E(k,m):=E(k,m), H(c)), D=(k,c1,c2):=D(k,c1) if H(c1)==C2 otherwise Reject.
ps:the question is from the book  <A Graduate Course in Applied Cryptography[Boneh]> exercise 9.2
can use cpa and cca to proof

first one is simple as ${H_1(m)}$ leaks the information about the message in the ciphertext. So it is not CPA secure.

second one , the scheme will be under CCA. as @SEJPM mentioned attacker can modify the c1 such that new ciphertext c2 will be the result of ${H_2(c1)=c2}$, so ciphertext integrity is not preserved, required in AE.


Efficient algorithm for remainder calculation over prime field for ECC implementation? I am working on 224-bit elliptic curve cryptography. In this 224-bit * 224-bit multiplication results 448-bit output. I am reducing 448-bit into prime field range( prime number $2^{224}-2^{96}+1$) using modulus operation. Can any tell me efficient modulus operation for remainder calculation? I am working on VHDL.

See section D.2.2 of FIPS 186-3. The modular reduction can be expressed as two additions and two subtractions of values which are assembled by concatenating selected 32-bit words of the 448-bit value which is to be reduced. Note that these additions and subtractions are modular, so you may have to mind some carries.


How does the time complexity of block cipher change with increase in key length? I am interested especially in the case when the keylength exceeds the length of the plaintext.

Intuitively, it should be harder to crack the key with an increase in key length even if it exceeds the plaintext length but does it actually hold true or there any caveats to this particular scenario?

Usually we want a block cipher to be resistant to an exhaustive search attack on the key, if the key space $\mathcal K$ is the set of all binary strings of length $n$ then for a particular $k$ the attacker would have to search against $2^n$ possible keys, so the key length is chosen to make the mentioned attack infeasible.

Even if the cipher is proved to be computationally secure there is another (sometimes underestimated) security issue related to the cipher block size.

When we encrypt a message of arbitrary length it gets broken in chunks and the cipher is used within a particular mode of operation (ECB, CBC, etc) and because of the birthday paradox if the block size is not large enough the cipher could be vulnerable to a birthday attack which shows that after $2^{m/2}$ message blocks, where $m$ is the block size, we already have a 50% probability of having a ciphertext block collision and therefore leaking information about the original plaintext blocks.

For example 3DES works with key of length 168, which makes theoretically the exhaustive search attack unfeasible$^*$, but it's designed to accept blocks of 64 bits which means that after we collect $2^{32}$ encrypted blocks ($\sim$32GB of data) we expect to have a collision with 50% probability.

$^*$there is a known attack that runs in time $2^{112}$ instead of $2^{168}$


Can neural cryptanalysis be applied to AES? In this Wikipedia article about Neural cryptography (section applications) it states:

  In 1995, Sebastien Dourlens applied neural networks to cryptanalyze DES by allowing the networks to learn how to invert the S-tables of the DES. The bias in DES studied through Differential Cryptanalysis by Adi Shamir is highlighted. The experiment shows about 50% of the key bits can be found, allowing the complete key to be found in a short time.

It could very well be that I misunderstood something, but I think that the same "attack" can't be used for AES, since the Inverse Rijndael S-box is public knowledge or am I wrong? Is AES designed this way to prevent an attack by inverting the S-box?

No. Neuro-Cryptanalysis fails on serious ciphers, including DES and AES.
Sebastien Dourlens's Neuro-differential cryptanalysis of DES (in sections 5.4.2 and 5.4.3 of his 1996 mémoire) learns an S-box. Applied to Unix crypt (section 5.4.4), it memorizes passwords/hash pairs (by a training requiring "from several days to several years") and then merely performs a quick retrieval; something a hash table does routinely and quickly! Neither is relevant to cryptanalysis.
Mohammed M. Alani's Neuro-Cryptanalysis of DES and Triple-DES (in proceedings of ICONIP 2012) claims cryptanalysis of DES or 3DES from 2048 or 4096 examples in an hour of Matlab on a standard PC; but there is no indication that it recovers the key or is  otherwise capable of predicting more input/output mappings than supplied in training (even though the later is a stated objective). My guess is that - at best - it performs similar plaintext/ciphertext memorization thru training.

Update: there recently has been noteworthy progress in the field of neuro cryptanalysys, with Aron Gohr's Improving Attacks on Round-Reduced Speck32/64 using Deep Learning, in proceedings of Crypto 2019. It's further analysed by Adrien Benamira, David Gerault, Thomas Peyrin and Quan Quan Tan in A Deeper Look at Machine Learning-Based Cryptanalysis (eprint, March 2021).


Hashing a password with the password? I was wondering if hashing a password with the password would be a good way of encrypting the password. So, the user must know his/her password to get the same result as the one in the database. Also, this would prevent decrypting of the password without the password... right?

I've read articles and other SO questions/answers on hashing passwords, but was wondering if this would actually work.

Short answer: Use bcrypt.

Long answer:

First, "hashing a password with the password" is an undefined statement. Regardless, you are well into "inventing your own crypto" territory. Assuming you mean something along the lines of SHA-256(password + password), this is a phenomenally bad password digesting scheme. Being unsalted, your approach is vulnerable to rainbow attacks. Not using key stretching, your approach is vulnerable to brute forcing with GPGPUs.

BCrypt is vulnerable to none of these. It uses cryptographically random salts, ensuring that duplicate passwords do not hash to the same value. And it requires a significant amount of work to be performed by an attacker in order to generate each hash, requiring tens to hundreds of thousands of times more computation per password attempt.

Edit: In the comments, it was clarified that the meaning was something along the lines of SHA-256(password + SHA-256(password)). This is susceptible to precisely the same attacks: identical passwords hash to identical values, which is a serious flaw. And again, hashing is fast. Fast enough to brute force a huge number of your passwords, if given your password database. Real key derivation functions significantly increase the cost of brute forcing past the point where it's no longer a practical attack vector.


Security analysis of Spritz? Recently, a new cipher called Spritz has been released by Ronald L. Rivest and Jacob Schuldt. It should be a "drop-in replacement" for RC4.

There are many differences to RC4, Spritz is "spongy" and also has a complete different way to handle the key setup. But still there are many similarities to RC4 in generating the key stream or the whole structure of the cipher it self.

There are many results against RC4, so Spritz should be an interesting topic for analysis.

I have looked at some attacks on RC4 and be curious if some of them can be applied to Spritz as well. Does anybody else has analysed Spritz so far? Or is it far too early for results against Spritz?

From the performance viewpoint Spritz is really slow (compared to other related ciphers e.g. Keccak or Salsa20, SHA-256). Why didn't they go for performance? Nobody will use it if its that slow.

I have looked at some attacks on RC4 and be curious if some of them can be applied to Spritz as well. Does anybody else has analysed Spritz so far? Or is it far too early for results against Spritz?

No third party analysis. Probably way too early. (Even the paper you linked is unpublished.) The answer may of course change any time.

  From the performance viewpoint Spritz is really slow (compared to other related ciphers e.g. Keccak or Salsa20, SHA-256). Why didn't they go for performance? Nobody will use it if its that slow.

They say in the paper that they were using "a simple and unoptimized implementation of Spritz". With the possible exception of Keccak, the implementations of those other algorithms may have seen years of optimization work.

Looking at the actual numbers, Spritz generates keystream at ~95 MB/s compared to 150+ for AES and 290+ for Salsa20 and RC4. So it's slower, but not by orders of magnitude. That sort of gap could realistically be closed with optimization work, if the implementation truly is poor. It also isn't necessarily that big a deal in many applications. Further, hardware performance might look completely different, although I don't see anything to suggest that it must.

The same question could be posed of AES: why are we using AES CTR if stream ciphers like Salsa20 have twice the performance? AES of course has the advantage of being an older design that has seen its share of cryptanalysis, but versatility may also play a role. As a block cipher, AES can be used for a variety of things, from MACs to disk encryption, whereas a stream cipher is basically only for encryption and requires a MAC to prevent malleability.

Similarly, due to being a sponge function, Spritz, like Keccak, could be seen as a more versatile primitive, offering not only encryption, but also a hash function and a MAC. This would allow you to rely on fewer moving parts, hopefully avoiding bugs and security weaknesses, possibly gaining back some performance too. Having a simple algorithm also helps.

However, the hash function performance of Spritz is more than an order of magnitude slower, so I'm not sure you'd really want to choose it over Keccak...


Non-deniability of data sent over TLS Andy is going to connect to a server Selma over TLS.  Later, Andy would like to be able to publish everything (the ciphertexts, the plaintexts, all his keys) and prove to a mediator what data he sent to Selma over TLS; or prove what data Selma sent to him over TLS.  Is there any way I can do this?

More specifically: We need some way that a third party could look at the information Andy published and convince themselves that he's not lying.  Selma is an existing, unmodified TLS server; it can't be modified.  Assume that Selma is trusted: i.e., the third party will be willing to trust that Selma isn't trying to fool them and isn't in collusion with Andy.  However, the third party doesn't trust Andy: they'll want a way to verify Andy is not lying about what data was sent/received over the TLS connection.  It's OK for Andy to use some clever/sneaky/weird combination of TLS options and features and random values/nonces, if that helps achieve this goal.  It's OK to use client certs.  Andy is willing to reveal his private key and all session keys when he publishes his data.

Is there a way to achieve these goals and enable Andy to prove what data was sent/received over the TLS connection with Selma?

I do know it might be possible for Andy to later prove that he did open a TLS connection with Selma (because the TLS protocol has Selma sign or decrypt something).  But that's not enough for my purposes; I want Andy to be able to demonstrate what data was sent over the TLS connection.  It's not enough to merely demonstrate that a TLS connection between Andy and Selma existed at one point in time.

My analysis: I can't see a way to achieve this goal.  It seems we'd need a way to make Selma sign something that depends upon the application data.  However, in the TLS protocol, what Selma signs seems to be independent of the application data.  The Finished message has a running hash of the contents of all of the handshake messages, but it doesn't seem to include any of the application data, and in any event it isn't signed.  I looked at multiple key exchanges and at features like session renegotiation and false start, but still couldn't find a way to do it.  I've seen Does a trace of SSL packets provide a proof of data authenticity?, which says the answer is no if Andy and Selma don't do anything strange.  Does the answer change if Andy has the freedom to abuse the protocol or send whatever he wants?

To rephrase: if the answer to my question is "it can't be done", that means that the data is fully deniable: regardless of what Andy does, Andy can always change his mind and later come up with a fake transcript and lie about what data was sent/received.  On the other hand, if the data isn't deniable in some circumstances, then that presumably must imply some kind of "yes" answer to my question.

There are only two messages from the client before TLS permits the server to send

Application Data; ClientHello and the other one, in that order.  Furthermore, the client does

not keep any secret randomness between ClientHello and that other message from the client.

Thus, the third party can use the following strategy in an attempt at breaking deniability:

Before the connection starts, the third party generates ClientHello, chooses a PRF key, and gives Andy that ClientHello and obfuscated code implementing [apply the PRF to the server's initial response, and use that output and randomness to generate the next client-to-server message].

Andy sends the ClientHello from the third party, applies the obfuscated code to Selma's response, sends that code's output to the server, gets authentincrypted Application Data from Selma,

and then sends both of the Selma-to-Andy messages to the third party.

Since the third party knows the PRF key, the third party can

verify-and-decrypt the alleged authentincrypted Application Data from Selma.

By this answer's first two sentences and the security of the to-be-obfuscated-code's PRF

and the fact that TLS's MACs are stateless, regardless of the Level #, just rewinding isn't

enough, so if the obfuscation was Virtual Black Box then, without Selma's cooperation,

Andy couldn't get the third party to accept any Application Data other than

that actually sent by Selma, even when Andy has oracle access to the third party.

Of course, Virtual Black Box obfuscation is impossible in general, but other than Level 4+ and the +s of higher levels implying a secure signature-with-message-recovery scheme for which TLS's symmetric part is the signing algorithm, I'm not aware of any arguments that there shouldn't be an obfuscation scheme that's good-enough at obfuscating the relevant things from this answer.

(On the other hand, I also have very little idea of what such obfuscation schemes might look like.)

Level 1:
If instead the obfuscated code took a ClientHello message as another input (rather than the third party giving Andy a specific ClientHello message) and used a perfectly invoker-randomizable PRF, then for all obfuscated-programs which it's possible for an honest third-party to generate

(but otherwise chosen by the server), the server would have exactly zero ability to distinguish Andy's first two messages (with the latter generated via the obfuscated-program) from a normal client's first two messages.  (weakPRP-based constructions of invoker-randomizable PRFs

result in the perfect invoker-randomizability property holding unconditionally.)

Level 2:
Level-1 code could be extended to authentencrypt Application Data from the client and

decrypt authentincrypted Application Data from the server.  In this case, under the same

assumption on the obfuscated-code, the only way for the server to distinguish Andy

from normal clients will be sending invalid allegedly-authentincrypted Application Data.

Level 3:
Level-2 code could be extended to [come close-enough to verifying the

authentincrypted Application Data from the server] that, under the same assumption

on the obfuscated code, it will be hard or [information-theoretically impossible]

for the server to distinguish Andy from a normal client.

Level 4:
Level-3 code could be modified to verify the authentincrypted Application Data from the server

in the same way as a normal client, so that under the same assumption on the obfuscated code,

the server will have zero ability to distinguish Andy from a normal client.

The + of a Level:
There could be [a specific simply-efficient obfuscation scheme achieving the Level] for

which it is infeasible for Andy to have a non-negligible chance of fooling the third party.

(rather than [the scheme just being fast-enough to break deniablility]

or [there just not being an efficient way to reliably simulate])

Level 5:
Level-4 code could be modified to output [signatures from a standard signature scheme] on structs encoding [the relevant parts of the protocol's first three messages] and [the plaintext Application transcript].  In that case, the third party would only be needed to securely generate

the signature verification key and obfuscated code, rather than also to check Andy's claims.

Level 6:
There might even be canonical "obfuscated code" that breaks deniability at Level 5,

in which case there wouldn't even need to be a designated third party

- Everyone could check without needing to trust anyone.


Can you explain partial private key extract algorithm in certificateless Public key cryptography? Related to the algorithms of certificate-less Signature approach of Al-Riyami and Paterson…

Why is there a need for a "partial private key extract algorithm"?
Why should it be needed when calculating "user's private keys by user"?
Is "partial private key extract algorithm" further used in other algorithms?

I still got the impression that you did not really have read my answer to a related question.

But still, I try to briefly answer your questions here. First of all, private key extraction essentially means private key generation. Extraction, because the partial private key ($D_A$) is generated with repsect to an identity string $ID_A$ uniquely identifying the user $A$ (and thus it may be viewed as extracting the private key from the string).

  Why is there a need for a "partial private key extract algorithm"?

Because the certificateless-approach is in the middle between traditional public key crypto (key pairs are generated by the users themselves) and identity based cryptography (private keys are generated for the users by a trusted authority - this is necessary, since public keys are identity strings and otherwise everybody could generate private keys for any public key - and this would be quite bad).

Consequently, in public key crypto, public keys need to be certified by another party and in identity based crypto they do not need to be certified, since a user has to prove the identity to the trusted authority before the private key is generated.

In certificateless cryptography a part of the user private key is generated by a trusted authority (partial private key extraction) and the other part is computed by the user locally.

  Why should it be needed when calculating "user's private keys by user"?

It is needed since users do not compute their entire private keys on their own. Then, they would need to certify their respective public keys (who will certify that they are indeed who they are pretending to be in certificateless crypto?). So a partial private key is issued to users after identity verification by the trusted authority. The remainder of their private key is chosen on their own and used to compute the public key (without requiring to certify it).

  Is "partial private key extract algorithm" further used in other algorithms?

No, this is only used for key generation (of the partial private keys of users).

Summary:

It is important to understand that in certificateless encryption, a message is encrypted with respect to the user's identity ($ID_A$ - which is used for by the trusted authority to generate the partial private key) and the public key $P_A$ (this one does not need to be certified). The ciphertext can then be decrypted using the knowledge of the partial private key $D_A$ and the second part of the private key $x_A$ only known to the user.

Someone that encrypts a message with respect to $ID_A$ and $P_A$ can be sure that only the owner of the private key corresponidng to $ID_A$ can decrypt (this is the only user who will get issued the partial private key after identity verification at the trusted authority) and without the requirement that $P_A$ needs to be authentic (thats the idea).

Sorry, if there are many repetitions in the answer, but I tried to make the essential poits as clear as possible ;)


Is there a way to optimize a linear scan while preserving anonymity? I've been wrestling with a problem, and I was hoping if someone else had a bright idea.

Here's the problem: I have two sides, Alice and Bob.  Alice has a single high entropy string $A$, and Bob has a number of high entropy strings $B_i$, one of which may be $A$.  What we would like to do is have Alice send a single randomized message $F(A, r)$ to Bob so that:

Bob can determine in sublinear time which $B_i$ is equal to $A$ (or if none is)
Someone listening into two such exchanges (and who doesn't know either string) cannot determine if the two exchanges had the same string or not.

It's easy with only one of those constraints; it's easy to do if we let Bob take linear time (by having Alice send $r, Hash(A || r)$ to Bob, and have Bob compute each $Hash(B_i || r)$ value and look for a match.  And, it's easy to do if we don't care if someone listening in can check if two exchanges have the same string (just have Alice send $A$ in the clear).

I've tried to think of ways for Alice to include a hint that would allow Bob to skip over sections of his list; however every way I thought of would allow an attacker some advantage in determining whether two different exchanges had the same string.

And, in case you're wondering:

We can't assume that Alice and Bob had any preexisting shared secrets (other than the joint value of $A$ and some $B_i$).
We can't have Bob send a message to Alice first (which, again, would make it easy; Bob would send his public encryption key).  This limitation is because this exchange piggybacks on an existing protocol, and we can't add messages to that.

So, any bright ideas???

Your problem has a contradiction: since there is no agreement between two parties anything that Bob should learn about $A$ is also possible to learn for a third party. So, there should be a kind of trapdoor for Bob to be able to learn something about $A$ which is not possible to learn without knowing that trapdoor.

Your problem can be defined as a kind of secure set intersection protocol. One of the most significant works on the set intersection and the usage of it for pattern matching is done by Carmit Hazay and Yehuda Lindell.

However, in their work Alice is the one going to learn the result, not Bob. However you can use the idea of using a key as a trapdoor and by using an OT protocol have alice to learn $PRF(A,k)$ and send it to Bob whom is able to locally generate $PRF(B_i,k)$ and find the result.


How long would it take all of the supercomputers or cloud computing on Earth to bruteforce a significantly long password? I was arguing with a colleague who thinks that SHA256 (password + 64 character static salt) is "insecure." My argument is that nothing in cryptography is "secure," it's all a sliding scale, and the amount of time it would take to bruteforce such a combination would be so long (I'm thinking over 30 years) that for all intents and purposes it is "secure." His argument is that because SHA256 hashes are so quick to generate, you can crack something like this using all of the computers on Earth quite easily, and as such, it's "insecure."
I agree that using something like Bcrypt is "more secure," but I wouldn't consider the above "insecure" because of the difficulty in cracking such a thing.  If we factor in Moore's law, which argument is correct? And how about if we change that 64-character salt to a
128-character salt?
I feel like this is an argument about semantics, but it annoys me that someone can have such a black-and-white perspective that "this is insecure (SHA256 pass + insanely long salt), but this is secure (Bcrypt)". I understand that something like Bcrypt is obviously preferred and "more secure," and I could see the argument that the other approach is "less secure," but to say one is "secure" and the other is "insecure" is to me a fallacy.

A salt is supposed to be publicly available, for instance it needs to be stored in a DB next to the password hash. In that case the time it takes to recover the password is just a brute force or dictionary for the password. If the salt is static then rainbow tables may be used as well for any attack. Now if the password has an entropy of 256 bits then this is obviously not a problem. Actual passwords however only have about 42 bits of entropy on average, and this is why bcrypt is often needed to provide some additional security.
It is of course also possible to use a 256 bit pepper, which is a salt value that is kept secret. In that case "cracking" the hash will require both the password and the pepper. We cannot do that even with quantum computers because the energy requirements would be too high (cracking > 128 bit security against classical computers or > 256 bit against quantum computers is completely infeasible and forever will be).


In which order are the round keys used during AES decryption? In the Add Round Key step in AES decryption, which part of the expanded key will I XOR first to the result of the SubBytes step?

Is it the 10th round key?
For example, is this the right order?

addRoundKey(subBytes,roundKey10);
addRoundKey(subBytes,roundKey09);
addRoundKey(subBytes,roundKey08);
addRoundKey(subBytes,roundKey07);
addRoundKey(subBytes,roundKey06);
addRoundKey(subBytes,roundKey05);
addRoundKey(subBytes,roundKey04);
addRoundKey(subBytes,roundKey03);
addRoundKey(subBytes,roundKey02);
addRoundKey(subBytes,roundKey01);
addRoundKey(subBytes,secret key);

Here "secret key" is my secret key that I used in encryption.

In the expansion of my secret key in decryption, is it the same procedure like in encryption?

If you want to undo the encryption, you'll have to undo the whole sequence of the encryption procedure - i.e. undo each encryption step, in the inverse order.

Encryption has these steps (here for AES-128, the number of rounds differs for other Rijndael versions):

AddRoundKey(State, ExpandedKey[0]

SubBytes(State);
ShiftRows(State);
MixColumns(State);
AddRoundKey(State, ExpandedKey[1]);

SubBytes(State);
ShiftRows(State);
MixColumns(State);
AddRoundKey(State, ExpandedKey[2]);

...

SubBytes(State);
ShiftRows(State);
MixColumns(State);
AddRoundKey(State, ExpandedKey[9]);

SubBytes(State);
ShiftRows(State);
AddRoundKey(State, ExpandedKey[10]);

So, for decryption, you'll have go through this list from bottom to top, undoing each step by applying its inverse transformation.
Luckily, the inverse of AddRoundKey is just AddRoundKey with the same round key, so we get something like this:

AddRoundKey(State, ExpandedKey[10]);
InvShiftRows(State);
InvSubBytes(State);

AddRoundKey(State, ExpandedKey[9]);
InvMixColumns(State);
InvShiftRows(State);
InvSubBytes(State);

...

AddRoundKey(State, ExpandedKey[2]);
InvMixColumns(State);
InvShiftRows(State);
InvSubBytes(State);

AddRoundKey(State, ExpandedKey[1]);
InvMixColumns(State);
InvShiftRows(State);
InvSubBytes(State);

AddRoundKey(State, ExpandedKey[0]);

(Yes, ExpandedKey[0] is the original encryption/decryption key for AES-128.)

So, to answer your question: Round key 9 is the first which gets XORed with the subbytes result, but before that (at the very start of decryption), round key 10 gets XORed with the ciphertext.

As we have to use the same subkeys for encryption and decryption, you'll have to do the same (or equivalent) key schedule, too.

Note that in addition to this straight-forward (or actually straight-backward) decryption, there is an alternative (equivalent) one which uses a different ordering of the operations, and a mixed version of the sub keys (i.e. a changed key schedule).

But I recommend you to stick to this one here, as it is easier to understand. (No, actually I recommend not to implement AES yourself, but use an existing implementation.)


difference between the math of RSA problem and DH problem I'm trying to understand why the RSA problem is not related to the Discrete Log problem, and how breaking the Discrete Log problem does not directly compromise RSA.

I will explain my reasoning of why it seems to me that they are the same in hope that someone will find the flaw in my reasoning and correct me.

If you don't take into account how you generate the public and private keys and just assume they exist, we could minimize the RSA problem to just modular exponentiation in this way:

$M$: Plain text
$C$: cipher text
$E$: some number
$D$: some other number
This is easy (encrypt): $M^E \bmod N = {?}$
This is hard (decrypt): ${?}^E \bmod N = C$

Now, according to this khan academy video, ${?}^E \bmod N = C$ is equivalent to $C^{D} \bmod N = {?}$ for some unknown $D$, this will act as our private key.

Now my question is: If I can identify if I have decrypted $M$, by some file header for example. isn't finding $D$ for $C^{D} \bmod N = M$ the Discrete Log problem? Given this khan academy video about the discrete log problem, it would appear it is.

If you could take discrete logarithms modulo a composite number of unknown factorization, you could recover the decryption exponent.

Compute $c = m^e \bmod N$ for some $m < N$. We know that $c^d \equiv m \bmod N$.

You have $m, c, N$, and knowledge that $c^d \equiv m \bmod N$. Recovery of $d$ is the discrete logarithm problem.

The factorization of $N$ being unknown will probably work against you when attempting to compute the discrete logarithm. Depending on the hypothetical algorithm that you employ to compute discrete logarithms, knowledge of the factors of $N$ may be required, which implies that you still have to factor $N$ to compute the discrete log, which means breaking RSA would still be as hard as factoring.

Diffie-Hellman usually works with a prime modulus, so the factors of the modulus (which are just $1, P$) are public information.


Bitcoin Private Key Question If Bitcoin can be forked, and the same address can exist on both blockchains, what stops the re-generation of a privatekey on one blockchain that would also work on the other?

For that matter, what stops someone from forking the technology, starting from the genesis block, and using a program to endlessly create addresses > Search those addresses on the Bitcoin blockchain > if the address on the Bitcoin blockchain contains funds > use the newly generated privatekey to access the funds on the bitcoin blockchain?

A Bitcoin address is computed as follows, according to the Bitcoin wiki:

A private key is a 256-bit integer $k$ below 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141, the order of the group $E(\mathbb F_p)$ of $\mathbb F_p$-rational points on the curve secp256k1, $E/\mathbb F_p: y^2 = x^3 + 7$ where $p$ is the prime $2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1$.
A public key is the standard encoding $\underline P$ of a point $P = [k]B$ on secp256k1, the scalar multiplication by $k$ of the standard base point $B \in E(\mathbb F_p)$.
An address is the ‘base58’ encoding of the string $\text{‘1’} \mathbin\Vert h \mathbin\Vert c$, where $h = \operatorname{RIPEMD160}(\operatorname{SHA256}(\underline P))$ and $c$ is the first four bytes of $\operatorname{SHA256}(\operatorname{SHA256}(\text{‘1’} \mathbin\Vert h))$.

If you could find $\underline P$ given $h$, you would be given top billing in a top-tier cryptology journal.  This is because it would tear down the widely held conjecture that both RIPEMD160 and SHA256 are preimage-resistant.

If you could find $k$ given $P$, you would also be given top billing in a top-tier cryptology journal.  This is because it would tear down the widely held conjecture that discrete logarithms are hard to compute in well-understood elliptic curves like secp256k1.

You would alternatively be able to make money from exploitation of much more lucrative markets than your own private blockchain or cryptology journals.  But there are lots of very very smart people in cryptology who aren't doing that, and it's not just because they're all paragons of morality.


PIN-based authentication with Diffie-Hellman modular arithmetic Given $\text{server}_\text{pub}= ((2^\text{largerandom}\bmod P) \cdot (2^{\operatorname{intvalueof}(“XXXX”)} \bmod P)^\text{pin})\bmod P$
We know the $\text{server}_\text{pub}$ and we know that $\text{pin} \in [0,9999]$.
What we want to find out is the pin. You could write it as $( (2^x \bmod P) \cdot Z ) \bmod P = \text{server}_\text{pub}$
$Z$ is one of 10K values.
I think somehow since $\text{pin} \in [0,9999]$ we should be able to brute force the value but I am unable to come up with the math to do so.
$(2^\text{largerandom} \bmod P) = (\text{server}_\text{pub}\cdot(2^{\operatorname{intvalueof}(“XXXX”)^{-\text{pin}}} \bmod P)) % prime$
So the question is: how can use the fact that $\text{pin} \in [0,9999]$ to determine the value  $(2^\text{largerandom} \bmod P)$. Where $\text{largerandom}\in [1, P-1]$ and $P$ is a large RFC-based prime.

I think somehow since $pin \in [0,9999]$ we should be able to brute force the value but I am unable to come up with the math to do so.

Unless the random number generator is broken, there is no way to recover pin; this would remain true even if we were able to compute discrete logs mod $P$ (which we can't).
The issue is that the public key is generated as:
$$server\_pub = 2^{R + N \cdot pin} \bmod P$$
(where $R$ is largerandom, and N is the publicly known intvalueof("server") value)
Even if we were able to compute the discrete log, that would give us $R + N \cdot pin \bmod (P-1)/2$ [1]; however for any potential value of $pin$, there is a value of $R$ that gives us the value consistent with the observed server_pub; because $R$ is assumed to be (almost) uniformly distributed over $[0, (P-1)/2)$ [2], that observed public value gives us no information about the value of pin.
Our inability to compute discrete logs does not change the above reasoning.

[1]: why $\bmod (P-1)/2$?  That's the size of the group that $2$ generates modulo this prime
[2]: in your code, $R$ is generated uniformly randomly in the code over $[1, P-1]$; that does mean that the possible value $R \equiv 0 \bmod (P-1)/2$ is less than any other value of $R$.  This would, at extremely rare occasions, allow us to deduce that a specific pin value is somewhat less likely to be the correct value - however, this is so rare (probability of us being able to deduce that is approximately $1000/ P \approx 3 \cdot 10^{-613}$) that we can ignore that.


Zero-Knowledgeness of Fiat-Shamir heuristic I have read about the Fiat-Shamir heuristic for making an interactive proof of knowledge into a non-interactive proof of knowledge. If I apply this to zero-knowledge proof of knowledge, it seems to me that I would destroy the simulator and therefore the zero-knowledgeness.

Does the Fiat-Shamir heuristic destroy zero-knowledgeness?
If it does, it it possible to circumvent this?

Link to Fiat-Shamir heuristic.

In the random-oracle model, it has been shown that the Fiat-Shamir transform preserves the soundness and zero-knowledge of certain families of zero-knowledge (proof of knowledge) protocols (e.g., Sigma protocols) -- see [§5 in BR93,PS00,FKMV12]. Instantiating the random oracle with a concrete hash function is a much harder prospect, but there have been some recent works in this direction as well --- for example, the recent construction of NIZK from LWE relies on such an instantiation of the Fiat-Shamir transform [PS19].

P.S. Zero-knowledge is usually easy to show -- it is arguing soundness that usually causes problems in the non-interactive setting.

[BR93]: Bellare and Rogaway: Random Oracles are Practical: A Paradigm for Designing Efficient Protocols
[FKMV12]: Faust et al. On the Non-malleability of the Fiat-Shamir Transform
[PS00]: Pointcheval and Stern: Security Arguments for Digital Signatures and Blind Signatures
[PS19]: Peikert and Sheihan Non-Interactive Zero Knowledge for NP from (Plain) LWE.


Why Abstract Algebra in Cryptography? I come from an engineering background, but not from computer science or anything to do with pure math. I studied applied math in college--never abstract algebra, number theory, or discrete math, formally. I have been a programmer most of my career.
Having developed a keen interest in cryptography, I learned number theory and abstract algebra on my own, and I get the role of number theory:  in factoring prime numbers and the discrete logarithm problem for PKI. These are both hard problems.
However, why discrete log over a group? What is the significance of a group here? Why do we need a group?
Why use abstract algebra?  I know AES uses Galois fields. I understand how, but I cannot figure out why.
I mean, why use finite field arithmetic?
Why should the arithmetic be done in a group? Why an Abelian group? Why a polynomial? Why are the closure, inverses, and identities necessary to AES?
Likewise, what other advantages do groups, rings, and fields have for cryptography? How exactly are the characteristics of finite fields indispensable for AES and cryptography in general? Why couldn't this be achieved without finite fields? Likewise, for other uses of abstract algebra in cryptography...

Abstract algebra basically comprises Groups, Rings, Fields, Vector Spaces, Modules, and many other algebraic structures. It is not only useful in Cryptography but in Channel Coding, in the branch of Chemistry and Physics too.
It is a tool like Groups where you can do arithmetic and algebraic operation under a closed set. One can compare two algebraic structures and find similarities between them and use these properties further.

Now your question about AES and Galois Field. if you do arithmetic operation on the matrix of AES, say multiplying two bytes $\texttt{0xEF}$ and $\texttt{0xDC}$, without finite field your many arithmetic operations go beyond 1 byte of length. Finite field make sure that it will remain within the closed set by reducing to modulo.

for example; if you take the finite field created by the prime number 11 ($\mathbf{Z}^*_{11}$) the set only contains $\{1,2,\ldots,10\}$ elements. All operations are done within this set.  Then only you can substitute bytes find inverses when you decrypt AES encrypted ciphertext.
if you don't use them, strictly speaking without irreducible polynomial (like in AES it is $x^8+x^4+x^3+x+1$) or prime number, where it makes sure that all length of all operations ends up in byte and hence easy to find their unique inverses while decryption.


AES 5 and 6 round SQUARE Attack SQUARE attack on AES128 requires a single delta set for 4-round variant, or I assume single delta set is enough since keyspace is reduced to few keys which can be easily brute-forced. However, as we increase round number to 5, we need 5 delta sets approximately, as proposed by AES proposal. And further, for 6-round variant, we need about 10 delta sets. Is there a mathematical relation between the number of rounds and required delta sets, or is this pure heuristic? If there are any underlying mathematical relations, I couldn't spotted.
I am not able to execute a 5-round attack, since I'm following up the attack mentioned at the proposal, which requires a search on $ 2^{40}$ bits, and I'm not sure about the size of the resulting keyspace after using only one delta set. I mean, if we use a single delta set, is brute force still infeasible so that we want to use multiple delta sets, or is there any other reason?
Answers appreciated.
Thanks

Found an answer here:

For each group of 256 plaintexts, this filter rejects 255/256 of all
wrong key guesses. As we guess a total of nine key bytes, we will need
10 or so groups of 256 encryptions to find the key.


Attacks against RC4 when index $i$ is unknown RC4 uses two 8-bit indices. One, $j$, is key-dependent and secret, and the other, $i$, increments by one for each byte output. The $i$ index is typically considered to be public, but what if the RC4 keystream starts at an unknown position, putting $i$ anywhere in the range of $0$ to $255$ with equal probability? I can think of a few inefficient and naïve techniques, but what would be the most efficient technique to discover $i$?

The most efficient way I can think of (not that it's all that practical) is to take a very long section of the keystream (think a Gigabyte+), and check it against the known RC4 digraph statistics; some of these biases (actually, most of them) depend on the value of i, and so the value of i that is correct will show up as more strongly biased than incorrect values.

The practical downside is that it requires a lot of keystream; on the other hand, it is computationally efficient (and works even if the RC4 key is large)


ECC - Point Addition/Point Multiplication So I have a very beginner-esque knowledge of ECDSA and I'm trying to write something in python to take a private key and output the public key (Basically from what I understand just trying to do the point multiplication k number of times on the basepoint) to get a better understanding.

My two main resources are the wikipedia page
and this tutorial.

While trying to program point addition, I couldn't work out how to calculate the lambda on wikipedia under point addition (Which as I understand as the "slope"). What happens if you get numbers that don't divide nicely into each other in the fraction?

One example I found in the certicom tutorial (my second resource) is with the curve $(a = 0, b = 6$ over $\mathbb F_{23})$ doing a point doubling on $P=(7,2)$. It gives $\lambda = 147/4  \mod 23$, which it then simplifies to $\lambda = (9 * 6) \mod 23$ . What happens to turn $147 / 4$ into $9 * 6$?

The arithmetic done during a point addition is done using the addition and multiplication operations in the field; when you are using a prime field, that is equivalent to doing addition and multiplication modulo the prime (23 in this case).

Now, because we're doing the arithmetic modulo 23, we get to notice that $147 \equiv 9 \bmod 23$, and so those refer to the same field element; that is, in any field equation, we can replace one with the other without changing anything, or in other words $147 / 4 = 9 / 4$

Now, what does division mean in this case?  Well, what $a / b = c$ means is that $a = b \times c$ (and since this is done within the field, this actually means $a = b \times c \bmod 23$).  What we do is define the multiplication inverse $b^{-1}$ defined by $b \times b^{-1} = 1$, and so we have $a / b = a \times b^{-1}$.  And, in this case, we have $4^{-1} = 6$ (because $4 \times 6 \equiv 1 \bmod 23$).

Combing these two, we get $147 / 4 = 9 \times 4^{-1} = 9 \times 6$

Now, the obvious question that you will ask is "how do we find multiplicative inverses"?  After all, when dealing we numbers between 1 and 22, it's easy enough to find it via brute force, however how do we find these when we're dealing with modulii hundreds of bits in length?

The answer to that is the extended Euclidean Method; that gives an efficient way to find such inverses.

Now, I'll leave you with one last point; the references you give might give you some background as to why the point addition operation makes sense, however there are a bunch of optimizations they don't discuss (because they get in the way of explaining the basics).  On reference (that doesn't talk about the why, but considerably more about the what) is this IETF RFC; the "projective coordinate" method of representing points turns out to be considerably more efficient than more naive methods.


Ed25519 with R replaced by H(RAM)? Ed25519 signatures consist of $(R, s)$, where $s = r + H(RAM)a$ $mod$ $l$, and $R = rB$. This differs from the Schnorr signature where instead of $R$, the signature contains the hash $h=H(RAM)$. According to the Elligator paper (page 5) "one can reconstruct $(h, s)$ from $(R, s)$ and vice versa".

I see that $(R, s) => (h, s)$ is trivial, but how would one derive $(R, s)$ from $(h, s)$?

Or more generally, how would the verification equation look like with $(h, s)$ as the signature?

(Motivation: I'd like to use $(h, s)$ as the signature to get indistinguishability from random numbers without needing the Elligator 2 map. Probably means no bulk verification, but that's not needed for what I'm thinking about.)

Unless I am missing something, I believe that you can simply compute $R = s*B - h*A$ using point subtraction.


Frequency of letters change by the length of the texts? In terms of the frequency of letters, how is it possible to have different frequent letters when the length of the text I'm analyzing is shorter?

At the moment, I'm comparing the frequencies of a long text and a subtext from that text. To my surprise, the most frequent letters changed. In the long one it was the letter e followed by the letter t, however in the small text it was t followed by e. Also, when I checked the frequency of different types of texts (e.g news articles), the frequency of letters also changed as well as the most frequent one.

The bottom line is, how can that be possible? It makes no sense to me.

Letter frequency checks how often a letter appears in your text.  Depending on your text, the frequency of letters will change.  If your text is short and has the name "Alex" in it a lot, it will make the frequency of the letter X much higher than average.  Generally when discussing the expected letter frequency, people refer to the average letter frequency that appears in the english language (http://en.wikipedia.org/wiki/Letter_frequency).  Though for specific texts the fequency might not be close to the average, and with shorter texts the frequency might be dramatically different, overall the frequency of a long passage should be close to the average.


Multilinear Extension Polynomial: Compute the coefficients of the expanded polynomial Let $\textbf{a}=\left[10, 32, 57, 81\right]$ and $x=\{0, 1, 2, 3\}$.
Then multilinear extension of vector $\textbf{a}$ is the polynomial, $f_\textbf{a}(x_2, x_1) = 10(1-x_2)(1-x_1) + 32(1-x_2)x_1 + 57x_2(1-x_1) + 81x_2x_1$, where
$x_2$ and $x_1$ is the second and first bit of $x$ respectively.
Thus,
$$ x = 0, f_\textbf{a}(0, 0) = \textbf{a}[0] = 10$$
$$ x = 1, f_\textbf{a}(0, 1) = \textbf{a}[1] = 32$$
$$ x = 2, f_\textbf{a}(1, 0) = \textbf{a}[2] = 57$$
$$ x = 3, f_\textbf{a}(1, 1) = \textbf{a}[3] = 81$$
Expanding the polynomial:
\begin{align}
    f_\textbf{a}(x_2, x_1) &= 10(1-x_2)(1-x_1) + 32(1-x_2)x_1 + 57x_2(1-x_1) + 81x_2x_1 \\
     &=  2 x_2 x_1 + 22 x_1 + 47 x_2 + 10
\end{align}
Is there an algorithm to directly compute the coefficients of the expanded polynomial $f_\textbf{a} = 2 x_2 x_1 + 22 x_1 + 47 x_2 + 10$ without naively expanding the polynomial from $10(1-x_2)(1-x_1) + 32(1-x_2)x_1 + 57x_2(1-x_1) + 81x_2x_1$?

This can be done in $O(n2^n)$, where $n$ is the number of variables (naive expansion would take $O(2^{2n})$ in the worst case).
This is a standard technique called "sum over subsets/supersets/submasks/supermasks". A usual example is the ANF computation, which does it in $GF(2)$ so it uses the XOR operation. Here it is basically the same but since we work with integers, we have to care about the sign now.
The idea is to apply recursively the matrix
$$
M=\begin{pmatrix}
1 & 0\\
-1 & 1\\
\end{pmatrix}
$$
which corresponds to applying the matrix $M^{\otimes n}$ to the input.
To illustrate the idea a bit further, see what happens when we apply the transformation for one bit (variable), say $x_1$. We have
$$
f_a = 10(1-x_2)(1-x_1) + 32(1-x_2)x_1 + 57x_2(1-x_1) + 81x_2x_1.
$$
What $M$ tells us to do, is to consider coefficients for terms containing $(1-x_1)$, and subtract those from coefficients of terms which are the same except that $(1-x_1)$ is replaced by $x_1$. For the example above, it tells to subtract 10 from 32, and 57 from 81. It is easy to see that this action corresponds to expanding the term $(1-x_1)$. By repeating this procedure for all variables, we obtain the desired result.
Here is python code.
def ext(a):
    if len(a) == 1:
        return (a[0],)
    n = len(a)
    h = n // 2
    l = ext(a[:h])
    r = ext(a[h:])
    return l + tuple(vr - vl for vl, vr in zip(l, r))

a = [10, 32, 57, 81]
b = ext(a)
print(b)  # (10, 22, 47, 2)

To clarify the notation.

in the input array $a$, $a_i$ is the coefficient of the product of: $x_j$ if $j$-th bit of $i$ in the binary representation is 1 or $1-x_j$ otherwise;
in the output array $b$, $b_i$ is the coefficient of the product of $x_j$  if $j$-th bit of $i$ in the binary representation is 1 or $1$ otherwise.

Bits are counted starting from the most significant bit. E.g. for $n=3$, $i=3$ in the input corresponds to $(1-x_1)x_2x_3$, and $i=3$ in the output corresponds to $x_2x_3$.


Why is it good to split a CTR-mode counter into nonce and counter? When discussing the CTR mode of block ciphers, Wikipedia says the following:

  Simply adding or XORing the nonce and counter into a single value
  would completely break the security under a chosen-plaintext attack.

I don't understand the difference between the split nonce/counter design and simply using a random value and incrementing.  Why is using nonce +/⊕ counter insecure whereas nonce || counter is secure?

I don't see the difference between a split nonce/counter and nonce +/⊕ counter.  At first glance, isn't split nonce/counter mode the same as concatenating a bunch of 0 bits to the nonce and using nonce +/⊕ counter mode?

(By "+/⊕", I mean either addition or XOR, since it doesn't seem to matter which is used for this purpose.)

Suppose you do CTR mode as:

  $E(k,nonce+1) \oplus m_1$, $E(k,nonce+2) \oplus m_2$, $E(k,nonce+3) \oplus m_3$, etc.

The wikipedia page is talking about a non-random nonce, with a specific example of a packet counter. So suppose $nonce$ is a packet counter and in each packet you encrypt several blocks. You might end up with the following:

In packet #$p$:

  $E(k,p+1) \oplus m_1$, $E(k,p+2) \oplus m_2$, $E(k,p+3) \oplus m_3$, etc.

In packet # $p+1$:

  $E(k,(p+1)+1) \oplus m'_1$, $E(k,(p+1)+2) \oplus m'_2$, $E(k,(p+2)+1) \oplus m'_3$, etc.

The nonces are unique, but CPA security is broken. You have used $E(k,p+2)$ as a mask twice, and are leaking the value of $m_2 \oplus m'_1$.


easy hash algorithm to use without computer I am searching for a simple hash algorithm(s) which can be used to calculate relatively secure hash without using of any computer. Some requirements:

use only simple arithmetics operations (+ - / *, maybe mod and abs)
base of 10 (letters can be substituted with groups of 2 digits), not binary
short time of calculations (limited number of operations per hash and limited number of digits per number)
simple calculation (normal person should be capable of memorize it)
if whole calculation could be done in memory, it would be a plus but it is not necessary
only short messages will be hashed (maximum 50 - 100 characters, about 35 on average)
relatively secure (of course no modern computers will be used to reverse / find a conflict)

Edit:

there is similiar question here:
 Is there a simple hash function that one can compute without a computer?, but all responses seems to be too complicated to fit in my requirements

There has been a similar question. The accepted answer there refers to Manuel Blum's HCMU hash function.

Check out Manuel Blum's human computable hash function. He calls it HCMU for Human Computable Machine Unbreakable.
He claims you have to spend an hour memorizing the technique and then you can apply the has function in about 20 seconds without even using pencil and paper.

I have found an implemention of this function here, in just over 60 lines of Python code. Unfortunately I cannot find any paper on it on the go and the link in that other question is broken.


How can I combine Quorum and Zero Knowledge Range Proofs I have 20 years of experience at java JEE coding, and 10 years in devops as well,
but no experience with blockchains, or the Go language.

I want to setup a cluster of Quorum blockchain nodes, including the features
provided in ING bank's zkproofs project. I want to be able to complete transactions where a Prover and Verifier can interact. The Github project provides zero knowledge range proofs
and zero knowledge set membership.

I don't think I'll have much problem bringing up Quorum, but the documentation in the github project https://github.com/ing-bank/zkproofs is limited! How can I come to understand how to put the zkrp code with the Quorum nodes, to realize an integrated system? Any tutorials that would help out there somewhere?

Now there are a lot of interesting variants of Zero Knowledge Proofs with and without trusted setups. The traditional ZK SNARKS had a requirement for a trusted setup and demanded larger proof size and prover time and verifier times. However in the recent times Bullet Proofs have reduced the proof size significantly. ZK STARK is a recent Zero Knowledge Proof technique that has introduced transparent Zero Knowledge Proofs. Please find reference to two Zero Knowledge Proof based Toolsets implemented on JPMorgan Quorum protocol in the recent times.

ZSL on QUORUM

Anonymous ZETHER


How does OpenSSL know if a decryption failed? I have a file full of garbage, random data, and I encrypt it with AES256:

openssl -in myfile -out encfile -aes256 -pass pass:abc123

If I try to decrypt it with the wrong password, it says:

bad decrypt
140546891773584:error:06065064:digital envelope routines:EVP_DecryptFinal_ex:bad decrypt:evp_enc.c:516:

But, if I try to decrypt it with the correct password, it doesn't return any errors, meaning it was successful.

How does it know that it was successful?

This code is very near the lines the error mentions for evp_enc.c (there may be some differences between different versions of OpenSSL):

 527                 n=ctx->final[b-1];
 528                 if (n == 0 || n > (int)b)
 529                         {
 530                         EVPerr(EVP_F_EVP_DECRYPTFINAL_EX,EVP_R_BAD_DECRYPT);
 531                         return(0);
 532                         }
 533                 for (i=0; i<n; i++)
 534                         {
 535                         if (ctx->final[--b] != n)
 536                                 {
 537                                 EVPerr(EVP_F_EVP_DECRYPTFINAL_EX,EVP_R_BAD_DECRYPT);
 538                                 return(0);
 539                                 }
 540                         }

This is an implementation of PKCS#7 unpadding (b is the block size, retrieved from the "context").

There is no mention of MAC verification or authentication tag inside this code, so we can safely assume this is only called for ECB/CBC decryption (if you don't provide a mode of operation, OpenSSL defaults to CBC with PKCS#7 padding).

This also means that there is no certainty at all that the decryption was correct if you do not receive an error. For instance, you may get "lucky" and create a valid padding even though the wrong ciphertext was decrypted (or, with the wrong IV or key). And if the ciphertext two blocks before was changed then the error won't be caught either because CBC has limited error propagation.

In other words, if you need integrity / authenticity then you need an authentication tag, for instance using an authenticated mode such as AES-GCM.


Full diffusion or Partial diffusion between s-box applications? In regards to maximizing active s-boxes: is it advantageous to apply the non-linear layer after complete diffusion of the state, rather after then partial diffusion?

Using AES as an example, with the well known mixColumns and shiftRows combination: What if this linear diffusion layer were applied twice in succession between s-box applications, instead of just once?

Doing the math for the regular AES with 2 rounds is simple:
\begin{align}
    1 + 4 &= 5\\
    4 + 16 &= 20 \\
    5 + 20 &= 25\\
\end{align}

The first number in each row is the number of different s-boxes at the input of the round.
The second is the number of differences at the output of the round.
The third is the sum of the two.
The first row represents round 1
The second row represents round 2
Finally, the two rounds are summed to give the total minimum number of active s-boxes.

So to simulate a double application of the linear diffusion layer, I tried substituting 16 for 4, but was unsure of how to proceed:
\begin{align}
    1 + 16 &= 17\\
    16 + 256 &= 272\\
    17 + 272 &= 289\\
\end{align}

or should it be:

\begin{align}
    1 + 16 &= 17\\
    16 + 32 &= 48\\
    17 + 48 &= 65\\
\end{align}

Or something else entirely? How many active s-boxes over the course of two rounds would such a variant of AES have?

Put succinctly, I guess I really want to know: Is there an cryptanalytic advantage to diffusing the entire state before applying the s-box layer? Or is it better to apply s-boxes more frequently, with "just enough" diffusion between them?

If the linear diffusion layer were applied twice without applying the s-boxes between them, it is possible there might be an iterative differential characteristic with only four active s-boxes per modified 'round' (i.e. instead of a provable minimum of 25 active s-boxes over 4 rounds there could be as few as 16 active s-boxes over 4 'rounds').

Consider for example a state where all four bytes in a single row are active.  After SubBytes, all four bytes are still active.  After ShiftRows, all four bytes in that same row are still active.  Then after MixColumns all sixteen bytes in the state are active.  Applying ShiftRows again doesn't change the fact that all sixteen bytes are active.  But applying MixColumns again might (assuming the bytes differences are just right) result in a single row of active bytes.  If that row is the same row as the one we started with, and if the resulting differences of the active bytes are the same as the differences we started with, then that is an iterative characteristic that only activates 4 s-boxes in each 'round'.

If you want complete diffusion in a single round while still retaining provable minimum numbers of active s-boxes, you should use a 16 x 16 MDS matrix with a branch number of 17, such as this one.  But even with such a beast, you can only prove a minimum number of 34 active s-boxes over 4 rounds.


Prove that a function is not PRF? Let $G$ $PRG$ and $G'(s)$ equal to the first $n$-bits of $G(s)$, where $|s| = n$. Show that $F_k(x) = G'(k) ⊕ x$ is not a $PRF$.

My attempt:
Lets assume a $k$ and 2 messages $x_1$ and $x_2$. So, for $x_1$ I have $F_k(x_1) = G'(k) ⊕ x_1$, for $x_2$ we have $F_k(x_2) = G'(k) ⊕ x_2$. If the attacker does $F_k(x_1) ⊕ F_k(x_2)$ he gets $x_1 ⊕ x_2$. And then he can simply $XOR$ that by $x_1$ or $x_2$ and then get the message from that.

I have no idea if this is the correct way to prove this. Can you give my any hint if this is the correct way to show that a function is not $PRF$, maybe I have to do a proof by contradiction ?

EDIT:

I also know that a $PRG$ must not be predictable, if it is then that's not good, so for the function $F$ to use $G'$ as the $PRG$ which is always the first $n$-bits of $G$ it's not good because it violates the pseudorandomness property. I don't know if this is correct or helpful at all.

For something to be a PRF, it must be impossible for a probabilistic polynomial time algorithm to distinguish it from a random function. The distinguisher you note in your attempt is correct, as a random function would not have that property (xor two calls with the same key but different x values and you get the xor of the two x values).

As a side note, these notes are very good when it comes to PRFs. Especially 3.3 and 3.4.


AES 256 Encryption - Is it really easy to decrypt if you have the key? So this might sound like a crazy question but bear with me for a minute. I can't find any info on the internet and so am here, although this might have been a good place to start.

I've recently developed an encryption engine using the .net's AES managed classes. I use a 256 bit key generated by the Rfc2898DeriveBytes function. The key is generated from a pass phrase that is at least 40 characters long. The IV is also generated from this pass phrase. The encryption class uses a CypherMode of CBC and a padding mode of PKCS7. There is a static salt that is 8 bytes long.

The key is stored in a separate database to the data and is itself encrypted using a certificate based on the database master key.

So, my question is: is it really easy to decrypt the data if the attacker has the key? I'm not talking about the Chinese government (or even GHCQ given recent headlines), I'm talking about an attacker who steals both databases.

What would be the steps they have to follow and/or how can I stop them on their path? The reason I ask this is that I want to know how feasible it is. Is it something that can be done in minutes or does it fall into the bracket of being infeasible? Do they have to calculate all of the parameters used when encrypting?

I assume you follow Kerckhoffs' principle so the attacker knows the padding scheme and derivation function so the answer is yes, it only takes a few seconds to decrypt and anyone can do it.

If he doesn't know these things, he can find them by trial and error (assuming he can get his hands on a valid ciphertext).

The IV can be sent in the clear so making it depend on the key reveals some information on the key. It should also be unique for each session so I'm a bit worried about it. It should be OK if the KDF you're using is non-deterministic, which implies it uses its own IV so the problem remains. See this question for more on IVs.

Edit based on comments:
The cracking procedure is the following:
$a$ is the number of all modern ciphers. Let's set this to 100. $m$ is the number of modes per cipher, set it to 6. $k=100$ is the number of key derivation functions, $p=100$ are the padding schemes. The values are arbitrary. So we have $(p*k*m*a*c)/n = 6*10^6$ which equals to approx. 69 days with $c=1$ second and $n=1$ processor.

Your adversary will solve the problem in $69/2=34.5$ days. Not as practical but definitely feasible, especially if you throw extra processors at it. This solution is completly brute-force, it makes no attempt at distinguishing and pre-eliminating ciphers.

Since non-indistinguishability is a business requirement (really?) you could just get away with using ECB instead of any other mode.


Any downside to encrypting original signed message with the private key? Is there any downside to encrypting the original message for signing purposes. I understand this does not provide actual protection, and any one with the public key (any one in the world if the public key is made completely public), however, it would seem if the public keys were kept restricted to TLS tunnels and required password access, this would seem to be a small layer of protection. The upside is small, but is there any downside?

There are actually a few downsides which mostly depend on the size of the original message.

So recall that for signing purposes, the hash (or message digest) is used to sign the document. Thus assuming that the message is large we can face several possible issues:

1. Efficiency: Recall that signature schemes use asymmetric encryption which is much slower than symmetric encryption. So if you were to sign the entire message it could take some time. (Hash or message digest is relatively small in size and thus fast to sign)

2. Integrity: Given the message is too large (for the signature space) the message may be required to be split into separate blocks (separate messages). Now each message created must now be signed differently and the order of the message blocks may need to be preserved which is an additional overhead.

3. Compatibility: Some signature schemes such as RSA can not operate on Bit strings so it adds extra difficulty re-configuring the message or changing the signature scheme.

Of course, if the message is small, it can get away with the first two issues with small overheads, but it's probably better to use a key-sharing encryption scheme with signatures rather than have to go through all this overhead.

Let me know if that raises any other questions, Cheers!


Using multiple permutations to strengthen the security of a cipher In one book it says

  a set of permutations with the composition operation is a group. This
  implies that using two permutations one after another cannot
  strengthen the security of a cipher, because we can always find a
  permutation that can do the same job because of the closure property.

If I try to understand the bold part, is below explanation correct?

Assume you have a set of all permutations of "abc", that is:
Your set is: "abc" ,"acb", "bca", "bac", "cab, "cba".
Let's take "abc".

Permute it once and get say: "cba" (Let's say permuting once means you encrypt it).

Now let's assume you want to strengthen above permutation by permuting it once again (encrypt it once more), e.g. now you permute "cba" and arrive at "bac".
In theory one could have arrived at "bac" from "abc" in a single permutation too (in a single encryption), thus additional permutation didn't really make much sense from this point of view. Because it says basically what you can do in two permutations you can effectively also do in a single permutation.

At component level, such as Sboxes, you are essentially correct. This is why an (unkeyed, fixed) SBox is never composed with another SBox, without some kind of other mechanism, such as key bit addition, or a permutation of bits between adjacent SBoxes [as suggested by @Paul Uszak].

Note that above, I interpret the word "permutation" as a fixed, unkeyed map. When keys are mixed in, and we view the full cipher globally things change drastically. In this case, the permutation which is the composition of two (or three for triple DES) permutations is extremely difficult to determine since

the search space is so large
there are no shortcuts, the permutations are not presented in lookup table form, plus random keys are involved so we now have essentially random permutations.


A confusion about HMQV? As the full version of HMQV is very long, I will give a graph  of it below

\begin{array}{@{}l@{}c@{}l@{}}
\hat{A} && \hat{B} \\
(a,A=g^a)&&(b,B=g^b) \\
 x\in_R[1,q-1],\quad X=g^x  \\
& \xrightarrow{\textstyle \hat{A},\hat{B},X} \\
%&& verify \; X \in G^* \\
&& y\in_R [1,q-1],\quad Y=g^y \\
& \xleftarrow {\textstyle \hat{B},\hat{A},Y} \\
&& d=\bar{H}(X,\hat{B}), \quad e=\bar{H}(Y,\hat{A}) \\
&& s_B=y+eb,\quad \sigma_B=(XA^d)^{s_B} \\
&& K=H(\sigma_B) \\
%verify \; Y \in G^*\\
d=\bar{H}(X,\hat{B}), \quad e=\bar{H}(Y,\hat{A}) \\
s_A=x+da,\quad \sigma_A=(YB^e)^{s_A} \\
 K=H(\sigma_A) \\
\end{array}

$a$ and $A=g^a$ are static private key and public key of party $\hat{A}$ ($\hat{A}$ denote the identity of a user ) respectively ,and the same with  $\hat{B}$ .

HMQV appears in 2005, while the eCK model appears in 2007. After that , nobody try to prove the security of HMQV under eCK model, although,intuitively it's secure under eCK. So, I wonder that why  nobody give a proof of it ?  Could someone give a sketch of proving HMQV under eCK model?

In this paper it is shown that the security model under which HMQV was designed (CK-HMQV) and the eCK model are incomparable based on their security prerequisites, adversary model, and application domain. Essentially, there are known protocols which are secure in the eCK model but insecure in the CK-HMQV and other protocols which are secure in the CK-HMQV but insecure in the eCK model.

Specifically, for the HMQV model the author states:

  The HMQV protocol is insecure in eCK because the adversary can trivially reveal the session key in the two-initiators scenario, as in the proof of Theorem 3. The insecurity is based on a mismatch between the equivalence type of matching sessions and the equivalence type of derived keys.

The definitions of equivalence for session and keys can be found for Definition 3 and 4. The equivalences $\approx_A$, $\approx_B$, $\approx_C$ and $\approx_D$ for sessions basically define conditions that need to be satisfied for sessions to be equivalent and the key
equivalence means that sessions which are equivalent with respect to $\approx$ yield the same derived keys.

Theorem 3 states that: Role-symmetric protocols with key type $\approx_A$ or $\approx_B$ are insecure in eCK.

Where a protocol is said to be role-symmetric, when the messages of each role (sender, receiver) are identical up to their order (which holds for the HMQV protocol).

Now, HMQV is role-symmetric and the key equivalence type is $\approx_A$ and the matching sessions equivalence type used in the proof is $\approx_A$ (see Table 2). Unfortunately,
this means that HMQV cannot be secure in the eCK security model.

Consequently, the HMQV protocol as it is can not shown to be secure in the eCK model, although it may intuitively seem to be the case (but security models for AKE are quite complicated and
there can be very tricky issues which are not that obvious).

Observe that as stated by the author in Section 2.5 that eCK-matching is equal to CKHMQV-matching $\wedge$ $s_{role}\neq s'_{role}$.

This basically says that for matching sessions $s$ and $s'$ which are equivalent, i.e., lead to the same derived key, it must not be the case that they can be obtained when conducted
in the same role (sender or receiver) in the security game. Thats what is stated in the cited part above. This indicates that one way to modify HMQV to provide eCK security is to break the role symmetry and/or include session identifiers into the messages (but I am no expert in AKE and this my intuition :)


Clarification on Key exchange approaches in TLS/SSL When RSA is used for key exchange in SSL, the client basically encrypts some random data using the server's public key and and sends it to the server. This data is then used to compute the shared key which is used for symmetric encryption.

When Diffie-Helman (DH) is used on the other hand, -- are the DH public values exchanged unecnrypted? I ask this because while the client can use the server's public key to encrypt DH values to be sent to the client, the server has no such key to encrypt data being sent to the client (since typically the client has no public keys of its own).

are the DH public values exchanged unencrypted?

Yes, that are.  After all, they are "public values"; there's no weakness in exposing them in the clear.

Now, we do have to be careful that they aren't modified in transit (if they can be, then someone can perform a Man-in-the-Middle attack).  We do that by having the server sign its key share (using the private key of its certificate).


How to verify CA certificate from Yubico with openssl? I'm going to verify the CA certificate from Yubico. I copied the whole certificate from

-----BEGIN CERTIFICATE----- to  -----END CERTIFICATE----- in a file with the ending .pem. Then I wanted to verify this with openssl verify test.pem in the command line (test.pem is my file with the certificate). I got

test.pem: CN = Yubico U2F Root CA Serial 457200631
error 18 at 0 depth lookup:self signed certificate
OK

I'm very new to openssl and openSUSE, so I don't know how I can solve this problem. My aim is to verify a certificate against this CA file. But first I want to get this error off.

Well, they say they use gpg to sign the file (yubico-utf-ca-certs.txt) and the signature is in the linked file. So

gpg --verify yubico-u2f-ca-certs.txt.sig yubico-u2f-ca-certs.txt

gpg: Signature made Tue Sep  2 11:18:24 2014 CEST using RSA key ID 32F8119D
gpg: requesting key 32F8119D from hkp server keys.gnupg.net
gpg: key 54265E8C: public key "Simon Josefsson <simon@josefsson.org>" imported
gpg: 3 marginal(s) needed, 1 complete(s) needed, PGP trust model
gpg: depth: 0  valid:   1  signed:   0  trust: 0-, 0q, 0n, 0m, 0f, 1u
gpg: next trustdb check due at 2019-08-28
gpg: Total number processed: 1
gpg:               imported: 1  (RSA: 1)
gpg: Good signature from "Simon Josefsson <simon@josefsson.org>"
gpg:                 aka "Simon Josefsson <simon@yubico.com>"
gpg: WARNING: This key is not certified with a trusted signature!
gpg:          There is no indication that the signature belongs to the owner.
Primary key fingerprint: 9AA9 BDB1 1BB1 B99A 2128  5A33 0664 A769 5426 5E8C
     Subkey fingerprint: 9941 5CE1 905D 0E55 A9F8  8026 860B 7FBB 32F8 119D

Ok. This shows that the file in question was signed (validly) by someone at Yubico, so it seems.

The cert itself (some_cert.pem) is self-signed so openssl has to be told to trust it: "verify" checks the chain of certificates but here the chain ends right away: the cert signs itself. In this case you want to check the signature (but this says nothing about the origin of the cert, anyone can make a self-signed cert with Yubico in the name!), so we can do

openssl verify -trusted some_cert.pem -check_ss_sig some_cert.pem

Which indeed says OK (it says to check the last (here only) link, the self-signed one, and to explicitly trust the signer; normally there is a directory of trusted certs that openssl knows about or needs to be told about in a command line argument.).

To inspect the cert (that you now trust the origin of, due to it being signed by gpg etc.) and checked the signature of, e.g. do

openssl x509 -in some_cert.pem -noout -text

which outputs all the fields including the serial, which was also in the signed text file. So now you see that all is consistent in itself. But you have to  believe the gpg key (from a key server) and the fact that the file is hosted on the site etc. The gpg key is untrusted according to my gpg install...

Hope this helps.


Better security than SHA1 for signature? An application that I maintain uses Sparkle Update to update itself. I expect attacks from high level attackers (China, USA's NSA, etc.) and have some questions about how secure the cryptography Sparkle uses actually is. Specific examples of good practices would be much appreciated.

Creating public/private signing keys.

Sparkle uses the following to create public/private signing keys:

openssl dsaparam 2048 < /dev/urandom > dsaparam.pem
openssl gendsa dsaparam.pem -out dsa_priv.pem
openssl dsa -in dsa_priv.pem -pubout -out dsa_pub.pem

1.1 Is using "/dev/urandom" a good idea on OS X?

1.2 Are there any other problems here? (I will probably generate a 4096-bit or larger key instead of the 2048-bit one.)

Signing the application

Sparkle protects from forged updates by signing the updates. It uses the following to generate a signature:

openssl dgst    -sha1 -binary < in-file | openssl dgst -dss1 -sign private-key-file

Would changing it to

openssl dgst  -sha256 -binary < in-file | openssl dgst -dss1 -sign private-key-file

(and changing the signature verification to verify the signature on a SHA256 hash, of course)

be enough to avoid the weakness in SHA1?

Or is there also a problem with "openssl dgst -dss1"?

Thanks in advance.

Is using /dev/urandom a good idea on OS X?

Yes. /dev/urandom is the preferred way to get random values on all modern unixes. Arguments that /dev/random are more secure is a complete myth.

  Are there any other problems here? (I will probably generate a 4096-bit or larger key instead of the 2048-bit one.)

2048 bits is considered secure and likely will be until ~2030. 4096 bits is overkill — the next logical step is 3072 bits, which is roughly equivalent to a 128-bit symmetric key.

  Would changing it to [SHA-256] be enough to avoid the weakness in SHA1?

Probably. But SHA-1 collisions are only just now starting to become computationally feasible. It's worth trying to get upstream to migrate onto a more resistant hash function.