Questions about future and session key generation in DUKPT process As I understand this process is done in the client device for generating a unique key per transaction:

inject generated IPEK to client device;
generate set of future keys (actually 21 future keys) using IPEK+KSN and delete the IPEK;
generate session key using transaction key + KSN;
use this session key per transaction and for next transaction use increment KSN and use next future key.

My questions:

Why we need session key? While future key itself is a unique key and if we encrypt each transaction by a future key, actually we used a unique key per transaction.
Why we generate only 21 future key? Then after 21 transaction we need new future key and because of deleting IPEK, then we need to inject a new IPEK to device and as I know, from security point of view this is not good idea to transmit device master key in short cycle like every 21 transaction. Why do we not use a bigger cycle like thousands?
How we transmit new IPEK to device after 21 transaction? there are no description about this? Does IPEK encrypted with any other key and then send to device or it sent plain?
EDIT:

session key is coming from here :

  The swiper usually encrypts these tracks using one of its generated
  future keys (called the "Session Key") along with its current KSN.

Assume this situation:

IPEK is injected to device and 21 future keys are generated
first future key + KSN is used to encrypt 1th transaction and KSN was increased
do this until using 21th future key for 21th transaction.
know for 22th transaction do we used 1th future key + increased KSN or new future keys are used ? If first state then does this means 1th encryption key and 22th encryption key are only differs in KSN ?

EDIT2:
dave_thompson_085 describe sequence of generation and using of future keys(thank about it ),the only section which is still unclear to me is detail of generating future keys.I mean assume we want to generate 21 future keys in initial steps,of course we derive this keys from IPEK by 3DES?but do we use IPEK as message and KSN as key for all 21 step future key generation?and after that e.g. for 3th transaction ,when we want to generate and store key in FK21 do we use 3DES encryption with IPEK and KSN for generating FK21?

I don't know where you're seeing session keys. DUKPT is designed to do transactions, not sessions, hence the name. If some application is using them for sessions that is probably a bad idea. (added for edit) Okay, that website is amazing: I think every sentence of the text has an error or ambiguity, yet the code is correct -- at least for the simpler 'host' algorithm; it doesn't implement the device-side future-key algorithm. DUKPT is not intended to and should not be used for session keys.

For the device-side algorithm, the 21 so-called Future Keys are used in a hierarchical fashion controlled by a 21-bit counter (which is the low bits of the KSN) to derive a sequence of keys; they are not directly used as the key sequence. Because high Hamming weights are skipped, the key sequence for a device (starting from an Initial KSN and corresponding Initial Device or TRSM Key, Device or TRSM Injection Key, or various other names) is $2^{20}-1$ or 1048575 keys -- slightly over a million.

(expanded in detail since I can't seem to convey that the 21 future key registers are not 'used up' by 21 transactions; revised to more accurate 'derive' instead of 'generate')

AN EXAMPLE OF THE FUTURE-KEY ALGORITHM

In either host or device (future-key) mode the Initial Key (two 64-bit halves) for a device is created by twokey-3DES encrypting the high 8 bytes of the device's IKSN with the BDK for the left, and with the BDK with each half XORed with C0C0C0C0_00000000 hex for the right.

At device injection this Initial Key is used to derive the keys for each KSN whose counter value is a power of two, and store them in the future-key registers: the key for IKSN+$2^0$=IKSN+1 in FK21, for IKSN+$2^1$=IKSN+2 in FK20, for IKSN+$2^2$=IKSN+4 in FK19 and so on to IKSN+$2^{20}$=IKSN+1048576 in FK1. Since all keys derived by a device are for KSNs beginning with the device's IKSN, I will omit that part from now on and just say the counter value.

For transaction 1, the device (TRSM) finds the lowest 'on' bit in the counter which is $2^0$=1 and uses the key in the corresponding FK register (FK21) which was set above to contain the key for counter 1. Actually the key is first modified to a 'variant' key with two octets complemented depending on the type of crypto done in the transaction. After use FK21 is logically erased.

For transaction 2, the lowest 'on' bit is $2^1$=2 so it uses FK20 similarly and erases it, but first uses it to derive the key for counter 3 and store that in FK21.

For transaction 3, the lowest 'on' bit is $2^0$=1 so it uses FK21 similarly which now contains the key for counter 3 as set above, and erases it.

For transaction 4, the lowest 'on' bit is $2^2=4$ so it uses FK19 which contains the key for counter 4, and erases it but first derives the keys for counter 4+2^1=6 in FK20 and 4+2^0=5 in FK21.

For transaction 5, the lowest 'on' bit is $2^0=1$ so it uses FK21 which contains the key for counter 5 as above, and erases it.

For transaction 6, the lowest 'on' bit is $2^1=2$ so it uses FK20 which contains the key for counter 6 as above, and erases it after generating the key for counter 7 in FK21.

For transaction 7, the lowest 'on' bit is $2^0=1$ so it uses FK21 which contains the key for counter 7 as above, and erases it.

Txn 8 bit $2^3$ uses key 8 from FK18 and derives key 12 in FK19, 10 in FK20 and 9 in FK21.

Txn 9 bit $2^0$ uses key 9 from FK21.

Txn 10 bit $2^1$ uses key 10 from FK20 and derives key 11 in FK21.

Txn 11 bit $2^0$ uses key 11 from FK21.

Txn 12 bit $2^2$ uses key 12 from FK19 and derives key 14 in FK20 and 13 in FK21.

Txn 13 bit $2^0$ uses key 13 from FK21.

Txn 14 bit $2^1$ uses key 14 from FK20 and derives key 15 in FK21.

Txn 15 bit $2^0$ uses key 15 from FK21.

Txn 16 bit $2^4$ uses key 16 from FK17 and derives key 24 in FK18, 20 in FK19, 18 in FK20, 17 in FK21.

Txn 17 bit $2^0$ uses key 17 from FK21.

Txn 18 bit $2^1$ uses key 18 from FK20 and derives key 19 in FK21.

Txn 19 bit $2^0$ uses key 19 from FK21.

Txn 20 bit $2^2$ uses key 20 from FK19 and derives key 22 in FK20 and 19 in FK21.

Txn 21 bit $2^0$ uses key 21 from FK21.

Txn 22 bit $2^1$ uses key 22 from FK20 and derives key 23 in FK21.

Txn 23 bit $2^0$ uses key 23 from FK21.

Txn 24 bit $2^3$ uses key 24 from FK18 and derives key 28 in FK19, 26 in FK20, 25 in FK21.

Txn 25 bit $2^0$ uses key 25 from FK21.

Txn 26 bit $2^1$ uses key 26 from FK20 and derives key 27 in FK21.

Txn 27 bit $2^0$ uses key 27 from FK21.

Txn 28 bit $2^2$ uses key 28 from FK19 and derives key 30 in FK20 and 29 in FK21.

Txn 29 bit $2^0$ uses key 29 from FK21.

Txn 30 bit $2^1$ uses key 30 from FK20 and derives key 31 in FK21.

Txn 31 bit $2^0$ uses key 31 from FK21.

We have now generated 31 transaction keys and have not come anywhere near 'using up' the future key registers -- in fact we've only used five of them, not even touching FK1-16 at all.

If you continue this process for a long time you will see it derives a key for every 21-bit binary value other than zero, of which there are 2097151; but DUKPT prescribes that counter values with more than 10 bits set are skipped, so only 1048575 of these values, and their corresponding keys, are used -- and as I said in the summary above, that's the number of keys and transactions for one DUKPT device, without rekeying.

The original intent was that a device, or (much more likely in the technology of the 1980s and 1990s) the secure module within a device, would be replaced after this cycle. In recent years as DUKPT has been applied to higher-volume but lower-value and lower-security applications, there is more desire for rekeying. See What is transaction capacity of a POS using 3DES DUKPT? for some (differing) perspectives on this.

(further expanded for completeness although this part is correct at the link)

Each derivation step occurs between the key for one KSN and a subsequent KSN which has exactly one bit set that was cleared before, i.e. adds a power of two. For the (trusted) host algorithm, all these steps are performed in a loop, from the highest-order bit set in the desired counter to the lowest-order; for the future-key algorithm they are spread out in time with each bit effectively done at the beginning of the range of counter values which have that bit set, as laid out above; either way the cumulative result for each key actually used is the same.

Each one-bit derivation step uses two single-DES encryptions (but not triple-DES) and is expressed by the standard in a rather complicated form that boils down to:

Input: curkey = key for 'before' KSN, with Left and Right halves accessible separately;
ksn = low 8 bytes of updated KSN (with new bit added) corresponding to new key

Temporary: modkey = curkey with each half XORed with C0C0C0C0_00000000

Output: newkey = key for updated KSN, similarly with Left and Right halves

newkeyR = DES_encrypt(key=curkeyL, data= ksn XOR curkeyR) XOR curkeyR

newkeyL = DES_encrypt(key=modkeyL, data= ksn XOR modkeyR) XOR modkeyR

The website you linked expresses this more concisely in pseudocode as

GenerateKey(key, ksn) { # where ksn is already updated by the caller, and the return is used to update key
    return EncryptRegister(key ^ KeyMask, ksn) << 64
         | EncryptRegister(key, ksn)
}
EncryptRegister(key, reg) {
    return (key & FFFFFFFFFFFFFFFF) ^ DesEncrypt((key & FFFFFFFFFFFFFFFF0000000000000000) >> 64,
                                                  key & FFFFFFFFFFFFFFFF ^ reg)
}

The main benefit of the future-key algorithm is that if a device is compromised, the data currently in the FK registers cannot be used to construct any previous keys for the same device, or any keys at all for another device. Thus assuming the compromise is detected and all new keys from this device are blacklisted, the compromise results in no loss of security. DUKPT was originally intended for use in bank ATMs and it was expected (correctly) that some ATMs would be stolen or attacked because, as Willie Sutton famously observed, that's where the money is. The simpler host-side algorithm is capable of creating the key for every txn for every device on demand, but was assumed to be implemented only in a well protected environment, typically a dual-locked vault inside a fortified data center with reinforced walls, fences, and round-the-clock armed guards. And possibly, though an ABA committee would never say so, sharks with frickin lasers :}


The sign of the correlation in linear approximation ${\text{Let }}g:{\{ 0,1\} ^n} \to {\{ 0,1\} ^n}$ be a round function of an $n$-bit iterated block cipher and let $K \in {\{ 0,1\} ^n}$ be a fixed round-key, and denote ${g_K}(x) = g(x \oplus K).$ Show that $${\text{cor}}(u \cdot x,v \cdot {g_K}(x)) = {( - 1)^{u \cdot K}}{\text{cor}}(u \cdot x,v \cdot g(x))$$

Since $c(f,g)=\sum_x (-1)^{f(x)\oplus g(x)}$, we can write  $$c(u\cdot x, v \cdot g(x\oplus K))=\sum_x (-1)^{u\cdot x \oplus g(x\oplus K)}$$ where the sum ranges over all binary strings of length $n$ which is a vector space over the binary field. Now let $y=x\oplus K$ and note that as $x$ ranges over this vector space so does $y$. Therefore we can rewrite the same correlation as
$$c(u\cdot x, v \cdot g(x\oplus K))=\sum_y (-1)^{u\cdot (K \oplus y) \oplus g(y)}=(-1)^{u\cdot K}\sum_y (-1)^{u\cdot  y \oplus g(y)}.$$
The last sum is just $c(u\cdot x, v \cdot g(x))$ thus giving the claimed result.

This is also related to a shift property of the Walsh Hadamard transform which is after all a Fourier transform.


Text cipher option that can decrypt the same ciphertext to two DIFFERENT and DESIRED outputs given DIFFERENT keys (and/or alphabet) I have a pen pal that I discuss with. In our latest discussion it was proposed to write a short message that is ciphered and have the other one find what it is, given some clues.
I would like to ask if its possible to have the same ciphertext that when decrypted with key "his_name" gives a result and if decrypted with key "my_name" gives a different result, but, obviously, I suppose that both results must be constricted to the same number of letters.
I am not versed into computer ciphers or AES or RSA or other mathematical difficulties, so I'd like to ask if there is a possibility to have something that does not involve having to own a piece of software to do hundreds of computations in order to find the cipher.
I was thinking that I can have the same ciphertext that, when used with two different ciphers, offers two distinct messages. If this can be possible, is there a way for me to get the 2nd cipher working after getting a ciphertext from using the 1ts cipher? Like, I use simple caesarian shift and get a ciphertext. Then I have this ciphertext to also be decrypted to whatever text I want to have by juggling with some property of the 2nd cipher?
I was also thinking that I can have two different alphabets for the same ciphertext, as this can be a property of the 2nd cipher. But how can I find the alphabet order for the second message to match deciphering from the ciphertext that resulted from the first message (that can have the normal alphabet)?
I have checked the questions linked below:

Create a ciphertext that decrypt to different plaintexts with different keys in RSA

Ciphertext to different plaintext

Is it possible to get different plaintexts from a single ciphertext using different keys?

From what I understood:

there is such a notion that if I have (text A) and (key A) and the resulting (ciphertext A) and I also have (text B) and (key B) and the resulting (ciphertext B), I can do some operation with [(ciphertext A) and (ciphertext B)] to get (ciphertext C) that, when used with (key A) it'll give me (text A) and when used with (key B) it'll give me (text B)
there is something like a deterministic symmetric encryption that I may use to get a hash for the cipher and then use two different ciphers on the hash, but I may have misunderstood some things here
there might be an option that requires to have a bigger 2x ciphertext that can have its 1st half decoded with the first key and remaining padding, and the 2nd half decoded with the second key and remaining padding

Example:
Key 1 : Adam
Message 1: you are very good you discovered this aaaa
Alphabet 1: ABCDE.....XYZ

Key 2 : Dave
Message 2: this is a secret message harder to find aaa
Alphabet 2: GREPTL......YHX

-> results only 1 ciphertext
Ciphertext: gdeowxiwetzmckdslfproewlqasdcmbrtrw

The "a" at the end of messages is just to have padding up to 35 characters.

For the above example, the other user will only know the resulting ciphertext, the cipher method and the alphabets that were used. So they only have to guess the key to decipher.
Is there such a thing possibile, and relatively trivial to find - for short messages?

I've been thinking about this for a while and I can only think of one possible solution.
If you want to share two different messages with the same cypher text then you might be able to use a "one-time pad" with multiple decryption possibilities, or rather multiple one-time pads for the same text.
So if I were to have the following cypher text
GTEROSDFEE
Each one-time pad takes individual letters in the cypher text and assigns an other letter;
Thus, with the same cypher text, with one one-time pad I would get
HELLOTHERE
(pad: G->H, T->E, E->L, R->L, O->O etc.)
And with an other one-time pad I would get
GOODBYEYOU
(pad: G->G, T->O, E->O, R->D, O->B etc.)
This can be practical for short messages that do not use too many characters, as to decrypt you must know the unique decryption for each individual column of characters of text.


Why has the RSA factoring challenge been withdrawn? Wikipedia states that RSA challenge has been withdrawn.

Does it mean that an efficient factoring algorithm is "just around the corner"?

or are there some other reasons?

If the challenge was still open people would have even more confidence in RSA.

RSA themselves (the company) say this in their RSA Factoring Challenge FAQ:

Why is the RSA Factoring Challenge no longer active?
Various cryptographic challenges — including the RSA Factoring Challenge — served in the early days of commercial cryptography to measure the state of progress in practical cryptanalysis and reward researchers for the new knowledge they have brought to the community. Now that the industry has a considerably more advanced understanding of the cryptanalytic strength of common symmetric-key and public-key algorithms, these challenges are no longer active. The records, however, are presented here for reference by interested cryptographers.

This, of course, does not really answer the question. Although there have been many optimizations, and computers have quite grown in both CPU power and RAM size, the best known algorithms for factorization have not qualitatively changed since the late 1980s, when the General Number Field Sieve was discovered. Even with GNFS, today's computers, and the fine brains of the authors of the RSA-768 factorization, a 1024-bit RSA modulus still seems out of reach. The money at stake was sizeable for an individual, but not that much for a company such as RSA (there was a 100k\$ prize on RSA-1024, 150k\$ for RSA-1536 and 200k\$ for RSA-2048; RSA Security appears to have a yearly revenue of more than 700 millions of dollars).
My guess is that they withdrew the challenges for a mixture of the two following reasons:

When a RSA challenge is broken, it makes bad press, and the press is worse if there is a prize, because it may serve as an highlight on the event (which is otherwise extremely technical).

An open challenge with a prize implies some kind of provisioning, which is bound to upset someone in the accounting department.

So, at some point, RSA Security decided that the inconvenience of maintaining the challenges exceeded the inconvenience of withdrawing (which your question incarnates: a suspicion of potential weaknesses).
One might notice that the withdrawal happened at about the same time than the bulk of the sieving work for RSA-768 began -- I do not have the exact timing, but it is conceivable that the withdrawal decision had been pending for awhile, and was triggered by rumours of the RSA-768 factorization effort.


Why does bit padding work in practice in a message authentication code? I understand that bit padding (add a 1, then 0's as needed) is a secure way to pad a message, preventing an unpadded message producing the same tag as a message that has been padded.

What I don't understand is how this works in practice. Surely a message exists that has a '1' bit followed by several trailing 0's. How does the system for a MAC distinguish between a regular message that naturally has a 1 and trailing 0's, and a padded message?

Bit padding is a padding that is always applied. So every possible message still has a canonical representation.

It is even possible to remove the padding always by removing all trailing zeros and the rightmost bit with value one.

For MAC calculation the unpadding is of course not used, but it shows that every message is still unique, even after the padding has been applied.

So if you have one message and you pad to a multiple of 8 bits (to make the example readable):

0000      -> pad -> 0000 1000

and a message that is identical to that padded message:

0000 1000 -> pad -> 0000 1000 1000 0000

as you can see the messages are still distinct after padding.


zero knowledge proof of encryption Is there a way to prove that a ciphertext $c$ was encrypted under a given public key, $Pk$, without revealing the plain text message $m$?

For most classical encryption schemes from the literature, what you want will in fact be trivial, as it is common that every possible ciphertext is a valid encryption of at least some message $m$ with respect to the public key. This is not implied by the standard security properties (and does not hold, for example, with respect to IND-CCA secure encryption schemes), but it holds for many IND-CPA secure encryption schemes.

Take for example ElGamal over a group $\mathbb{G}$, with public key $(g,h)$ ans secret key $s$ such that $h = g^s$. Then any pair $(c_1,c_2)$ correspond to a valid encryption of some message $m$: set $r$ to be the value such that $c_1 = g^r$ (it exists since $g$ is a generator of $\mathbb{G}$), and set $m$ to be $c_2/h^r$. Then, you obviously have $(c_1,c_2) = (g^r, h^rm)$.

The bottom-line is: if you want such a zero-knowledge proof, you should specify which encryption scheme you want it for - for some classical schemes, no proof is needed.


Is my high school cryptography/steganography science fair project practical? I'm a 12th grade student interested in a science project in cryptography and steganography for my school's science fair. I chose this path of computer science partly because my coding skills are weak (even though I've taken computer classes for 3 years) and partly because I wanted a more math-oriented field. After doing my research, I found that for my science project, I wanted to test how to implement both cryptography and steganography techniques to maximize data security in a message. My plan to execute this is skewered by the fact that my topic is very advanced and usually requires years of complex math. So far, this has been my plan:

Q: which cryptographic algorithm and which steganography technique put together will result in the most efficient, secure data?

I will be testing 3 cryptographic algorithms: DES, AES, and RSA
I will be testing 3 steganography techniques: Adding bits to a file, and Least Significant Bit (LSB), and RGB color encryption

The purpose is to see which two combination of methods offer the most security, and at the moment there are 3x3=9 combinations of tactics I can test to see which is strongest.

So far example, using the crypto library in Java, I would be able to implement one of the cryptographic algorithms into my code for encryption. Then, using a steganography software tool, I would then hide the file using one of the steganography techniques. I was thinking the security of the combined techniques could be measured by the encryption time (the higher it is, the less efficient and secure), but my main concerns are:

Is this a practical project? Can this be executed like a true science fair project
and
In what way other than encryption time should I measure the 'effectiveness' of the two techniques?

I have to start collecting data very soon, and I feel as though I'm underestimating how complex this experiment is. But I would really like feedback!

which cryptographic algorithm and which steganography technique put together will result in the most efficient, secure data?

AES and DES are already a combination of separate algorithms involving multiple steps each.  They are already "put together".

Steganography won't add additional security because of Kerckhoffs’ principles.

  In what way other than encryption time should I measure the 'effectiveness' of the two techniques?

Computation time is not a good indicator of security. If AES and DES are used together, the security will be equal to AES' security by itself.  This is because DES' seed can be guessed faster than brute force - it has been broken.

  Is this a practical project? Can this be executed like a true science fair project

It is not a practical project because neither AES nor DES can be broken using any machine you own, therefore output (no matter how much you massage or analyse it) will always appear as random bits.  This means there will be no way to measure the security provided by combining methods.


How is El Gamal different from Diffie Hellman Key Exchange I am Reading RSA and Public-Key Cryptography by Mollin and I can't make out how El Gamal is different from Diffie Hellman Key Exchange. Any thoughts?

The difference is purely conceptual. That is, when Diffie-Hellman published their paper, they equated between public-key encryption and trapdoor functions. Thus, they did not think that they had constructed a public-key encryption scheme, and this invention came only a year later with RSA. In fact, Diffie and Hellman even explicitly talk about publishing one part of the key...

The contribution of ElGamal was to formalize this as an encryption scheme, and free us of the conceptual block that public-key encryption requires a trapdoor function. By the way, conceptual contributions are very important, so this does not belittle it in any way. In addition, note that El Gamal was very clear about this in his paper. A quote from the paper:
"Section II shows a way to implement the public key distribution scheme introduced by Diffie and Hellman to encrypt and decrypt messages."


Why is a CSR signed and which key is used for signing? I know that a CSR includes a public key from which a signed certificate shall be generated.

But why is the CSR istself signed and which key is typically used?
For signing I need a private key, so the user of the CSR's signature must have the associated public key. But what key/pair is taken?

[Why] is the CSR istself signed?

The CSR is signed to ensure consistency of the data in it in a similar way to how root certificates are also self-signed. Additionally signing the CSR proves ownership of the private key corresponding to the public key in the CSR.

  [Which] key is typically used?

The private key which is associated with the public key embedded in your CSR.


How can I calculate non-linearity of an s-box element wise? First i transform the s-box into row matrix like if i have 4×4 s-box having 16 elements into 1×16 row matix then substitute the binary values in column . multiply the matrix by mobius trasformation matrix then tell me how to trasform the s-box which is in binary form into decimal form? Also how i calculate the non linearity of certain element of that s-box.

I'm not sure if I fully understand your question.

"tell me how to trasform the s-box which is in binary form into decimal form?": Changing numbers between binary and hexadecimal (or decimal, if you would really want to) is not different for numbers that are used with S-boxes compared to any other numbers.
"Also how i calculate the non linearity of certain element of that s-box.":  As far as I am aware, nonlinearity is defined for functions from $\mathbb{F}_2^n$ to $\mathbb{F}_2^m$. In the context of S-boxes, we typically consider the nonlinearity of a full S-box, and not of a single element.

Having said that, let $S : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^m$ be our S-box. Then the nonlinearity $\mathcal{N}$ of $S$ is usually defined in terms of the linearity $\mathcal{L}$ of $S$,  which is usually defined in terms of the $bias$ $\mathcal{E}$ of Boolean functions. Here is the full definition, where $S_b$ considers Boolean component functions of $S$ and $\varphi_a$ does $x \mapsto ax$:
$\mathcal{N}(S) = 2^{n-1} - \frac{1}{2}\mathcal{L}(S) = 2^{n-1} - \frac{1}{2} \max_{a,b \in \mathbb{F}_2^{m*}} \left|\mathcal{E}(S_b + \varphi_a)\right|$.
In this answer, I elaborated on how to compute this bias $\mathcal{E}(S_b + \varphi_a)$ to compute the values in the linear approximation table of $S$, including a fully worked out example. I'll try to avoid repeating that here.
Once all values in the linear approximation table are computed, the largest absolute number (ignoring the trivial case of $a=b=0$) is called the linearity. Using the definition, it is then straightforward to calculate the nonlinearity.


Proof of non-membership on a Merkle tree? Assume a user $U$ and a server $S$. $U$ uploads its data and wants later to perform an authenticity check. It also sends a Merkle tree to the server. Let’s say we would like $U$ to ask for a specific element in the tree. $S$ then returns the leaf node and the path to the root that would allow $U$ to verify. This acts as a proof of completeness.

In the case an element is not part of the Merkle tree, how the server can prove the non-membership proof?

If you are not worried about revealing information, then you can commit to the set of data items in one Merkle tree, and to the frontier of that set in another Merkle tree. A frontier is the set of ancestors to all values that are not in the tree (note that this is about the same size as the size of the set itself). Then, in order to prove that a value is inside the set you work with the first tree, and in order to prove that it is not you work with the second tree.

However, I strongly recommend that you read this paper on Zero-Knowledge Sets by Micali, Rabin and Kilian. First, the notion of a frontier mentioned above is defined. Second, they provide a formal definition and analysis. Third, they achieve something much stronger which is that nothing but the fact that the element is in or is not in the set is revealed (not even the size of the set). There was some follow up work on zero-knowledge sets as well, but you can find them easily by Googling.


Why is double encryption that's equivalent to single encryption no better than single encryption? In the "Introduction to Cryptography: With Coding Theory" by Trappe and Washington, in the chapter about DES algorithm the authors say that:

  "if a cryptosystem is such that double encryption is equivalent to a single encryption, then there is no additional security obtained by double encryption"

Why is this?

This is simply saying that if a cryptosystem has a functional composition that is
$$ h_{k}(x) = f_{k_1}(g_{k_2}(x)) $$
then you can find a key for single encryption that works as the double encryption.
For example: consider the permutation cipher where a permutation is a key. The permutations are forming a group, named permutation group, under the composition. Therefore, double encryption in permutation cipher is just another permutation, i.e. another key. Therefore you will not get a benefit.
To see this, let simplify the alphabet into 5 letters and let $P$ and $Q$ be two keys for a 5 letter permutation cipher:
$$P = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\2 & 4 & 1 & 3 & 5 \end{pmatrix} \text{ and } Q = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 5 & 4 & 3 & 2 & 1 \end{pmatrix}$$ The compositon of the two keys is
$$R =QP = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\4 & 2 & 5 & 3 & 1 \end{pmatrix}$$ and this is another permutation $R$, i.e. $R$ is a key that works as a single key.
Now turn back to DES:
Campbell and Wiener in 1992 showed that DES is not a group (paywalled) (and paywall-free). They showed that that the size of the
subgroup generated by the set of DES permutations is greater than $10^{2499}$. Therefore this value is far greater than potential attacks on DES which would exploit a small subgroup. As a result, DES has no such weakness. Actually, we will be surprised that a well-designed block cipher will be forming a group.
If there is such property that is the DES forms a subgroup of the permutation group then there exists a known-plaintext attack on DES that requires, on average $2^{28}$ steps showed by Judy H. Moore and Simmons (paywalled).
Also, forming a group will reduce the Triple-DES or more generally the multiple encryptions into single encryption.

The academical works on DES closure

1982 - D. Coppersmith, “In Defense of DES”, personal communication‡ Don Coppersmith was first to ask this. And he developed a method to show that lower bound on the size of the subgroup generated by the DES permutation is to be greater than the number of DES permutations, providing conclusive proof that set of DES permutations is not closed.
1988 - Burton S. KaliskiJr.Ronald L. RivestAlan T. Sherman, Is the Data Encryption Standard a group? (Results of cycling experiments on DES) (pay-walled), and pay-wall free.
They introduce a novel cycling closure tests which gave evidence that the
set of DES permutations is not closed. However, they assumed that DES pseudo-random function on their experiments. Therefore the claims are difficult to prove.
1989 - Jean-Jacques Quisquater, Jean-Paul Delescaille How easy is collision search. New results and applications to DES (pay-walled)
1989 Jean-Jacques Quisquater, Jean-Paul Delescaille How easy is collision search? Application to DES (pay-walled)
1992 - Campbell and Wiener DES is not a group (paywalled) (and paywall-free). In their conclusive work, they used a similar technique of Quisquater and Delescaille's work.

‡ This work claimed to be
described briefly in a posting to sci.crypt on Usenet News, 1992 May 18. This needs a link!


Private Information Retrieval with a pre-prepared database Informally, Private Information Retrieval (PIR) is a protocol between a user $U$ and a Server $S$, that meets the following conditions:

$U$ obtains enough information about a database hosted by $S$, to decide which record $i$ in the database to request from $S$.
$U$ initiates the PIR protocol with $S$ and retrieves all information from record $i$, without $S$ learning this was the record $U$ requested.

The trivial PIR protocol consists in $U$ requesting the entire database from $S$, replicating it locally, and performing all queries locally. The purpose of the more elaborate PIR protocols is consequently to reduce the amount of data that has to be transferred between $U$ and $S$, without $U$ loosing this privacy.

However, from what I understand, all existing PIR protocols still require $U$ and $S$ to transfer data with a quantity that is a function of the size of the entire database, rather than a function of the size of the individual records. (If not for any other reasons, because $U$ has to obtain enough information about the database in advance, to be able to pick $i$.)

I would like to know if it would be possible to reduce the quantity of the data transmitted, by introducing a third party $TP$ and changing the game (exactly) as follows:

$TP$ obtains the long term public key of $U$. This is the only information exchanged directly between $TP$ and $U$ throughout the entire protocol
$TP$ decides what information $U$ is to retrieve, prepares it using the long term public key of $U$, and posts it to the database of $S$
$U$ requests the record posted by $TP$ by sending her long term public key to $S$. $S$ responds and $U$ decodes the response using her long term private key. $S$ doesn't learn which record was requested by $U$.

The trivial protocol that meets these conditions, would be if $TP$ performs a conventional public key encryption of the record, $U$ requests the entire database, attempt to decrypt each record in order, and picks the one that decrypts correctly.

Granted, such a protocol would, in some respects, be significantly different from PIR, so perhaps there already exists a better term for it that I am not familiar with.

Efficiency of PIR largely depends whether you have a single-server or a multi-server PIR (replicate the database $n>1$ times).

Multi-server PIR seems more attractive (Ian Goldberg does a lot of research into this direction, e.g., this paper is the basis for most multi-server PIR approaches). Considering the database to be organized in a $r\times s$ matrix the client communication function of $r$ and the number of servers and the servers communication a function of $s$.

This is a recent paper on boosting the  efficiency when receiving multiple blocks in one query PIR in multi-server PIR.

What you mention (as far as I understand it) is a single-server solution and typically called hardware-assisted PIR (you may look here) and seems to be a practical alternative to multi-server PIR. Here, loosely speaking, you have a trusted component to which you send encrypted queries, this trusted party scans the entire database (typically co-located at the server for performance in form of some hardware secrutiy module) and then sends you back the encrypted query-result.


Symetric key encryption is not Authentication? Is there any way to show CCA-secure symmetric-key encryption does not have to be an authenticated encryption?

I know you can create a setup that isn't authentication, but how will you go about it?

Consider a CCA2 secure secret key encryption scheme $\mathcal{E}$ with an exponentially large randomness space. Turn this into an encryption scheme $\mathcal{E'}$ where we extend the randomness space of $\mathcal{E}$ with one more element. Let's think of it as $0$ (we can get there by rearranging the randomness space). For randomness $0$ the encryption in $\mathcal{E'}$ becomes the identity for every element.

Now, I claim $\mathcal{E'}$ is still CCA secure as the probability that for the challenge query randomness 0 is chosen is negligible. However, $\mathcal{E'}$ is not a secure MAC as everybody knows a valid tag for any message.


IEEE P1619/XTS, inconsistent reference implementation and test vectors I'm testing IEEE's P1619, which is XTS mode. IEEE documents from 2007 provided both test vectors and a reference implementation. Documents from 2008 only provided the reference implementation. Here is the 2007 document with both.

The reference implementation stayed the same from 2007 and 2008. The problem is, the reference implementation does not arrive at the test vector result. I've got it tracked down to the handling of the 64-bit S parameter in XTS_EncryptSector. The test vectors call out, for example, S=0x9a78563412; but I believe it should be S=0x123456789a, which allows the reference implementation to arrive at the test vector result.

I believe one of three things is wrong but I am not sure which one:

The S parameter is incorrect and should be byte-reversed
XTS_EncryptSector, which parses S into the tweak, is incorrect
The test vector result is incorrect

Based on Section 5, p. 4, I believe the test vector or S parameter is incorrect because of this sentence, which seems to apply to the S parameter:

  When encrypting tweak value using AES, the tweak is first converted into a little-endian 4 byte array. For example, tweak value 123456789A16 corresponds to byte array 9a16,7816,5616,3416,1216.

For anyone who wishes to try the code, see test2.cxx on GitHub. It is a copy/paste of the algorithm "C.2 Encryption of a data unit with a size that is not a multiple of 16 bytes" with OpenSSL providing AES code.

My question is, where does the problem lie?

Here's the relevant code for the handling of S:

void XTS_EncryptSector
(
    const AES_Key k2,               // key used for tweaking
    const AES_Key k1,               // key used for "ECB" encryption
    u64b  S,                        // sector number (64 bits)
    uint  N,                        // sector size, in bytes
    const u08b *pt,                 //  plaintext sector  input data
    u08b *ct                        // ciphertext sector output data
)
{
    ...

    for (j=0;j<AES_BLK_BYTES;j++)
    {                               // convert sector number to tweak plaintext
        T[j] = (u08b) (S & 0xFF);
        S    = S >> 8;              // also note that T[] is padded with zeroes
    }
    ...
}

It takes a value like S=0x9a78563412, and converts it into a tweak 12 34 56 78 9a 00 00 00 00 00 00 00 00 00 00 00 00.

From §5.1 ‘Data units and tweaks’, p. 4:

  Each data unit is assigned a tweak value which is a non-negative integer. The tweak values are assigned consecutively, starting from an arbitrary non-negative integer.  When encrypting tweak value using AES, the tweak is first converted into a little-endian byte array.  For example, tweak value 123456789A16 corresponds to byte array 9a16, 7816, 5616, 3416, 1216.

The test vectors appear to be written as byte arrays, not as integers (which in English are written big-endian), so where it says

  Data unit sequence number 9a78563412

on p. 23, that presumably means the integer 0x123456789a, i.e. 78187493530 in decimal.


Which HMAC scheme more secure? Which HMAC scheme is more secure? Or are they of the same level of security?
Scheme One

Compute a HMAC on the data to encrypt (cleartext/plaintext)

Encrypt the data with AES_CTR_256, and append above HMAC to end of ciphertext

Scheme Two

Compute a HMAC on the data to encrypt (cleartext/plaintext)

Encrypt the data with AES_CTR_256, and append above HMAC to end of ciphertext

Compute another HMAC on the ciphertext_HMAC combo and append it; ciphertext_HMAC_HMAC

And also, would using the same HMAC key be secure for scheme two?

The first scheme is similar to what's called Encrypt-and-MAC. It is not ideal, but it is not fatally broken, and it is still used by the SSH protocol securely. You need to include a counter or other unique value in the data being MACed to maintain IND-CPA security (i.e. identical plaintexts don't have identical MACs).

The second scheme you present doesn't really make sense. I can't see what benefit it would provide. Generally, you would want to use Encrypt-then-MAC, or EtM, a scheme where the plaintext is encrypted, the MAC is computed over the ciphertext and appended directly to it. EtM is a better scheme because it gives away no information about the plaintext, even if the MAC is broken. It also gives you the benefit of allowing you to discard a forged message without needing to decrypt it first, to prevent some attacks.

See also Should we MAC-then-encrypt or encrypt-then-MAC?

On a side-note, you should use AEAD instead. For AES, that means selecting an authenticated mode like GCM, which is both fast and secure. Although HMAC can be used safely, AEAD is usually better.


Reason for 3 rounds ChaCha in ChaCha20Poly1305@openssh OpenSSH uses a slightly different ChaCha20Poly1305 AEAD construct then the one proposed by A. Langley and others for TLS.

The TLS version

The openSSH version (and here)

The openSSH version uses two 256bit keys.
First key is used for deriving the Poly1305 MAC key and for encrypting the actual payload
The second key is used to encrypt the AAD (the 4 byte packet length in the openSSH case)
This construct result in at least 3 rounds of ChaCha20 for small messages (<=64 bytes).
The first ChaCha20 round for deriving the 256bit Poly1305 key spits out 64bytes where the last 32bytes are unused.
The second ChaCha20 round encrypts the AAD data (a 4 byte packet length)
The third (and more) ChaCha20 round(s) encrypts the actual packet payload.

For small messages, this seems to generate an unnecessary overhead of up to 33% computation time (in case message payload is less then 64 bytes).

The question

Why not use the unused 32bytes from the Poly1305 key derivation ChaCha20 round in order to encrypt the packet length (or say the AAD data up to 32 bytes)?
Is it cryptographically required to use a 2nd ChaCha20 context with a 2nd key to encrypt the packet length (the AAD data),... or in other words, is it more secure to use a 2nd key (that very likely comes from the same single shared secret as the first key) rather then use a single key and encrypt the AAD data from the same ChaCha20 round that derived the Poly1305 key?

The point of having two ChaCha instances is to make sure that one cannot be used to attack the other. From the draft RFC:

  Two separate cipher instances are used here so as to keep the packet
     lengths confidential but not create an oracle for the packet payload
     cipher by decrypting and using the packet length prior to checking
     the MAC.

Using the unused part of the first block from the same cipher instance as used for the rest of the construction would not seem to allow any kind of attack in this case, because that would always be the same part of the keystream, which is never used for anything else. I guess the proof of independence is easier with two cipher instances, but I suspect it is more about simplicity and extensibility.

By having a separate instance, you can easily decrypt the packet length separately using normal cipher interfaces, without adding any offsets. And by treating the encrypted packet length as additional data for the MAC, you get to use the normal process of verifying the MAC, without needing to decrypt it.

This way is also more extensible if there is a need for more than 32 bytes of additional data. It seems from the author's blog post there are some plans to extend this protection of packet lengths. Maybe that will require more additional data to be outside the main packet to allow earlier processing:

  We're not done yet though - an attacker may still observe the encrypted packets on the network to try to ascertain their length, and right now they are likely to be successful. I hope to add some features to frustrate this sort of traffic analysis some time next year.

I.e. to answer your question explicitly, no, I do not think it is more secure to have a second cipher instead of using the unused 32 bytes. It seems there may just be other practical reasons to do that.


Why are the mixcolumns in AES in a fixed order? Can the order be changed? Almost the same question as my “Why are the shiftrows in AES in a fixed order? Can the order be changed?” but this time it’s about the AES MixColumns.

Why are the mixcols fixed? Can we keep adequate security by changing the order? If not 'any' order, what about some other arrangements? Or is this arrangement the only one suitable?

What do you mean by "order"? Each column is "mixed" independently using the same operation. If you are talking about the MixColumns matrix, of course you can change it, but

the operation defined by the matrix must be bijective;
the matrix should have low linear and differential branching numbers (optimal in case of the AES MixColumns).


Vulnerabilities if encrypting the same data with 2 different keys Let's say that Alice and Bob complete a key exchange and then Alice uses that key k1 to encrypt a 256-bit key kaes1 and sends it to Bob. From there, Alice and Bob exchange a lot of messages back and forth, using AES-256 to symmetrically encrypt the data with the key kaes1.

Then, Charlie comes along and wants to participate, so Alice and Charlie complete a key exchange and Alice then uses that key k2 to encrypt the same original kaes1 and sends it over to Charlie. From there, Alice and Bob and Charlie now exchange a bunch of messages symmetrically encrypted with AES-256.

Eve has been listening in this whole time, and she has all the data, but none of the keys. Does Eve gain an advantage if she knows that kaes1 was the payload for 2 different messages encrypted with 2 different keys k1 and k2?

You basically ask the following question: Is there a weakness anywhere if I encrypt the same message independently with 2 different keys?  To answer this, please consider the following:

The cipher text coming from a perfect encryption algorithm is indistinguishable from random data.
Practical encryption algorithms have some flaws, leading to ciphertexts that are not truely random.
Any hint in the encryption process (including implementation flaw, input data processing, ciphertext output etc) that would provide some statistical bias away from a "chaotic" process flow may help an attacker.
It is well established that using the same key to encrypt different messages may provide some hints regarding the encryption process. Looking from a "system" perspective, this is due to a strong bias in the input variables - the encryption key has no random differential value any more.
In your case, different keys but same message also have an input factor with no random differential value, namely the plaintext. So yes, this may provide some cryptanalysis hints to Eve.
The practical question would be - how strong is this hint? should I be concerned? well, if your are a researcher, then you can write a paper on this and present it in some conference. But if you are talking about real security in the field, I would say that this is still secure: AES 256 is well known cipher, and the attacks based on (4) above may reduce its strengh from 256 bit to several notches below that (and only if you encrypt insane amount of messages with the same key), but still it stays resistant (read: infeasible) now and in the foreseeable future to any breakage due to these input biases - especially when you talk about a fairly limited number of key sharing in your application.


What is the difference between "wrapping" a key and encrypting? I wanted to implement a way to generate an RSA public/private key pair and protect the private key with a password.

Looking into the Web crypto api, I thought the wrapKey/unwrapKey pair was the way to go. But then I got confused, and the documentation is not really helping because it seems to assume you know everything about cryptography.

What I'm really stumped on is, why do we need a wrapKey/unwrapKey in the first place? Can't you generate a symmetric key and encrypt the RSA private key with the symmetric key, and later decrypt it with the same symmetric key?

I get nausea every time I look at the WebCrypto API documentation, so if all you get is confusion, consider yourself lucky.

From what I can tell by reading the W3C Web Cryptography API recommendation of 2017, in particular the §19 Algorithm Overview table, the only difference is that the AES-KW algorithm of RFC 3394 supports wrapKey/unwrapKey but not encrypt/decrypt.

The intent appears to be that you use wrapKey/unwrapKey when you know the plaintext is itself a short uniform random octet string, but encrypt/decrypt if it has any other structure to its distribution; then if you attempt to use encrypt/decrypt with AES-KW, the API will noisily fail because you might be trying to use it with structured data, which AES-KW is unfit to conceal.

For all other documented encryption schemes, public-key or secret-key, wrapKey/unwrapKey just defers to encrypt/decrypt.  So there's no idea of KEM at all, which simultaneously generates a key and encapsulates it for you.  One can hope that they will introduce a KEM API in the next version of the specification, since with NIST PQCRYPTO it appears the world is finally, nearly two decades after Shoup introduced the concept, converging on it as the basic way to do public-key encryption.


How to encode a message to MD5? I have faced a problem to understand MD5 algorithm.My question is weather the original input message is converted to binary value in MD5 before using the input message as parameter in four Feistel permutations FF,GG,HH and KK?

In order to understand my question here is an example.
If the original input message is 'amrasobaiatel' my question is that weather the message is converted to binary value such as '00010000000000' before padding and appending the 64-representation of the length of the input message?

If the answer of my question is 'yes' then my another question is that how can we convert the original input message into binary value?

MD5, like most cryptographical algorithms, takes inputs which are strings of bytes (actually, bits, however we rarely need to hash an arbitrary bitstring).  So, yes, to hash a string with MD5, you need to convert that string into a series of bytes somehow.

As for how you do that, well, for a string like 'amrasobalatel', the most common transform is to take the ASCII encoding of that string; however there's no reason you couldn't use UTF-16 or EBCDIC...


Byzantine Agreement: Why does OM need f+1 rounds in a synchronous setting? To get Byzantine Fault Tolerance in a synchronous model you can use an Oral Message Algorithm. For n > 3f+1 it gets an Byzantine agreement in f+1 rounds. Why f+1?

I will use $m$, not $f$  according the original paper.  It gets an Byzantine agreement in $m+1$ rounds.

The paper the byzantine generals problem       says:

  THEOREM 1. For any m, Algorithm OM (m ) satisfies conditions IC1 and IC2
  if there are more than 3m generals and at most m traitors.

Since it is a recursive algorithm,
from  $OM(0)$ to $OM(m)$, so it is $m+1$ rounds.


Encrypting a TCP connection between two unknown nodes I'm writing an application for controlling computers from a client.

I'd very much like it if the connection is secure and only authenticated clients are allowed access.

The workflow will be something like this:

A client use decides to add the server
The server allows the client

Alternative 1; On the server screen a X digit code is displayed that the client has to enter.
Alternative 2; The server presents a dialog which the server user has to accept.

The client and server exchanges keys to remember each other.

I understand that this initial communication won't be 100% secure unless the user manually verifies it, what's important is that future communications are secure.

What are good ways to make this as secure as possible?
None of the data sent is ATM sensitive so as a worst case only authentication is required.

If possible I would like to use HTTP(S) as the protocol.

What you are looking for is how to implement an SSL/TLS layer on top of your TCP connection. Try to use the OpenSSL library, it's the most popular implementation.


Proof of correct construction of a private key in distributed cryptography In an exponential ElGamal encryption scheme where the key generation is done in a distributed way among $n$ trustees we have that each trustee $i$ (where $1 \leq i \leq n$):

Selects a private key share $x_i \in \mathbb{Z}_q^{\star}$.
Computes a public key share $h_i = g^{x_i} \mbox{ mod } p$, where $g$ is the generator of the group.

Then, the public key of the cryptosystem is computed as $h=h_1 \cdot \ldots \cdot h_n \mbox{ mod } p$, while the secret key of the cryptosystem can be considered to be $x=\sum_{i=1}^n x_i$. Clearly, with this setting all shares $x_i$ of the secret key will be needed in order to decrypt any ciphertext, and thus no individual trustee is able to decrypt ciphertexts on his own.

Among some other things not relevant to my question, we usually have that every trustee $i$ is asked to prove that $h_i$ was correctly constructed (that is, $x_i= \log_g h_i$). This is usually proved by means of a Schnorr proof of knowledge.
The goal of asking the trustee to prove such thing is, as I've read in the literature, to prevent the trustee from constructing his public key share $h_i$ as a function of the public key of the other trustees.

My question is: what would be the dangers of doing so? That is, what could a trustee gain by constructing $h_i$ as a function of the public key of the other trustees, if he still doesn't know the private key which would allow him to decrypt ciphertexts on his own?

Here's what can happen if you don't do this verification:

Suppose Alice, Bob and company generate their public key shares honestly, $h_2, h_3, ..., h_n$

Now, Snidely Whiplash (who is also a trustee) is the last to contribute his share, he selects a private key $x_{evil}$ and computes $h_{evil} = g^{x_{evil}}$.  However, instead of sharing $h_{evil}$ as his share, he computes $h_1 = h_{evil} \cdot ( h_2 \cdot h_3 \cdot ... \cdot h_n)^{-1}$, and provides $h_1$ as his share.

Then, when we compute the public key, we get $h = h_{evil} \cdot ( h_2 \cdot h_3 \cdot ... \cdot h_n)^{-1} \cdot h_2 \cdot h_3 \cdot ... \cdot h_n = h_{evil}$

Hence, Snidely is able to decrypt any message encrypted with this public key, without the help from anyone else.

Asking Snidely (and everyone else) to prove that they know the discrete log of their share prevents this, because Snidely does not know the value of $log_g h_1$


Does a masked look-up table prevent cache timing attacks? When applying the boolean masking countermeasure to a cipher which uses an S-box $S$, a way to handle this nonlinear operation is to recompute a new S-box $S'$ such that $S'(x \oplus r_{in}) = S(x) \oplus r_{out}$ (see, e.g., this paper).

On the other hand, for processors using cache techniques, look-up tables have been proven vulnerable against timing attacks (see this paper). Therefore, it is recommended to use regular implementations (e.g., bitsliced implementations).

My first impression is that the masking technique described above also acts as a countermeasure against the timing attack introduced by Bernstein (as the look-up table accesses do no longer directly depend on the internal state, but also on a random mask $r_{in}$). However some works study bitsliced masked implementations to prevent timing and power side-channel attacks (see, e.g., this paper).

So my question is, does a masked look-up table as described above (assuming $r_{in}$ and $r_{out}$ are renewed at each execution) also prevent from cache timing attacks? Are there any published papers on the link between this countermeasure and timing side-channels?

After going through this, you can use bit slicing to mask power and timing of data.  This is because it does not leak any information if you interrupt that calculation that is useful to reconstruct and identify the type of calculation.  Having said that, it's very slow and you wouldn't want to do it.  I'm going to just use my cache description from a previous side-channel attack question.

The general idea behind cache timing attacks is that you can create a memory collision in the tag table of the cache so that you can know which index is being reloaded.  This attack works very well against a lookup table, which is how everyone would probably calculate this in software, which is a pre-calculated array.

Can you calculate this bit-wise in software to get around these attacks?  Absolutely, but it will be very slow to execute.  I did this type of implementation for the AES S-Box because I was trying to support simulation for my semiconductor implementation and I wrote it an BASH. It was terrible, but it gave me an easy way to extract strobes (For this same purpose, I have a complete AES implementation in BASH and it's not pleasant.  It takes about 1 second to compute a single block with AES256).

There's a paper by Satoshi et al that I used for the mathematics, which gives
$$\left(n_1x+n_0\right)^{-1}=n_1\left(n_1^2\lambda+ n_0\left(n_1+n_0\right)\right)^{-1}x
+\left(n_0x+n_1\right)\left(n_1^2\lambda+n_0\left(n_1+n_0\right)\right)^{-1},$$
which becomes the following circuit:

You would have to make a bit-slice implementation for each of those blocks in the figure.  And having done that, i'm going to guess that in a C implementation it's going to be 100x slower at a minimum than just using a lookup table, but I do not believe that you will leak any useful data because there's no way to identify from cache misses or power the values that you are calculating.

If you have a "masked" value, it must not be logically masked, but functionally masked.  The means that branch-index returns must not be used for values, and everything must be explicitly calculated. Therefore a XOR mask alone is insufficient to hide the data.


Does AES have any fixed-points? Is there any pair of 128-bit strings M and K such that AES$_K$(M) = M?

If yes, how do I go about (efficiently) finding such a pair?

Short version: It is quite likely that a large proportion of the keys have fixed points, but I don't have any idea on how to find them.
Long version: A stochastic argument
There are $2^{128}!$ permuations of 128-bit blocks, and of these, $!2^{128}$ (this is the subfactorial) are fixpoint-free. It is known that
$\lim_{N\to\infty}\frac{!N}{N!} = \frac 1e \approx 0.3679$ (and this limit is approached quite quickly), i.e. slightly more than one third of all permutations are fixpoint-free.
AES-128 selects $2^{128}$ from these $2^{128}!$ permutations. Assuming this selection behaves like a random one, about 63% of all keys have at least one fixed point.
(This argument is valid for any block cipher with sufficiently large blocks, nothing AES-specific here.)
But ...
Of course, AES (and any block cipher usable in practice) is not a random selection of permutations – for example, all permutations selected by AES are even (AES is composed of operations which each leave some bits unchanged, these are even, and compositions of even permutations are even), thus the available space is halved.
There might be some similar property which makes fixpoint-less permutations less or more likely than a random selection, or even make each key (or no key) have fixed points (both the number of fixed-point-free and non-fixed-point-free permutations are much much larger than the number of available AES keys). I don't know anything here (and as Thomas points out, knowing more might indicate a weakness in AES).
Also, this heuristic gives no way of finding these fixed points (other than brute force).


is DES Faster Than AES on software I conducted a software based experiment for encrypting difference size of images using AES and DES. However unexpectedly DES encryption speed was higher than AES. is it possible that DES is faster than AES?. I also search the literature but could not come up with clear conclusion on this matter. Thanks

Yes, it is possible that AES is slower than DES. There is no limit to the slowness of un-optimized software!

Some factors that I have witnessed slowing a software AES implementation:

not using tables for computation of the S-box(es) (an extreme example is the implementation there, when compiled with BACK_TO_TABLES undefined; another possibility is using a formula intended for hardware or bitslicing, perhaps in order to remove timing variations).
using hexadecimal ASCII (or binary) strings for everything, perhaps with the excuse that there is no built-in 128-bit type;
using an interpreted language (one without built-in XOR will insure particularly poor performance)
leaving debug code that dumps every intermediary result, even if that's effectively to /dev/null or equivalent;
to a moderate degree, recomputing subkeys at each invocation when the mode of operation allows to factor that out;
to a small degree, using 256-bit keys (it is hard to lose more than a factor of two with this one).

This is also applicable to DES to a large degree.

I should have mentioned that for decently and comparably optimized implementations, AES is typically faster than TDES and often than DES, and illustrated that with throughput; but that other answer does it nicely.


SHA1 collision event probability after n iterations There are String1 and String2 - some variables-strings.
The probability of collision for different String1 and String2 is

P{SHA1(`String1`) == SHA1(`String2`)} = p

What's the probability of

P{SHA1(SHA1(`String1`))} == P{SHA1(SHA1(`String2`))} //two times
P{SHA1(...(SHA1(`String1`)))} == P{SHA1(...(SHA1(`String2`)))} //10^9 times

Assuming the inputs and outputs are random, you would expect:

$$\begin{align}
P[\operatorname{SHA1}(s_1) \not= \operatorname{SHA1}(s_2)] &= 1 - 2^{-160} \\
P[\operatorname{SHA1}^2(s_1) \not= \operatorname{SHA1}^2(s_2)] &= (1 - 2^{-160})^2 \\
... \\
P[\operatorname{SHA1}^n(s_1) \not= \operatorname{SHA1}^n(s_2)] &= (1 - 2^{-160})^n \approx 1 - n/2^{160}, \\
\end{align}$$

where $\operatorname{SHA1}^2 = \operatorname{SHA1} \circ \operatorname{SHA1}$, etc.

Thus, $P[\operatorname{SHA1}^{10^9}(s_1) = \operatorname{SHA1}^{10^9}(s_2)] \approx 10^9 / 2^{160} \approx 2^{-130}$.

That's for a single pair $s_1 \not= s_2$. If you are looking for collisions, you would expect a collision with $\operatorname{SHA1}^{10^9}$ after something like $2^{130/2} = 2^{65}$ strings.

This approximation only holds while $n$ is small enough, and breaks down when it gets close to $2^{80}$ and cycles start to become an issue. However, for $10^9$ it should do all right.

However, there are (theoretical) attacks to find collisions in SHA1 faster, so for non-random inputs the probabilities could be higher.


What libraries do people use to implement and evaluate cryptography protocols? I want to implement this credential system: “Anonymous Credentials Light” (PDF). The implementation would involve some zero-knowledge proof and some exponentiation.

For some basic group computations like $g^x$, do people usually just come up with their own implementation or is there some famous library that provides such basic operations? If, what would be some of the possible libraries or implementations I could (or should) start with?

You can use any library you like, as long as it is has been tested for the specific algorithm. In other words, if $G^x$ is implemented in a specific library you must make sure that there are unit tests and if it is used in a verified algorithm.

There are some hints you can take from the library to see if it was programmed well:

the code should point to the implemented standard;
the code should use identifiers that can be mapped to the algorithms specified in the standard it implements.

There are some more general security requirements as well of course:

the code should keep to an apparent programming style;
the code should be accompanied with the test vectors;
the code should provide unit tests for (implementation specific) edge cases (maximum integer values etc.);
the code should provide unit tests for the complementary functions;
etc. etc.

As for the unit tests of the (complementary) functions: this is not often the case, I've seen horrible failures here, including those made by myself) but also e.g. the DH implementation of Bouncy Castle and the CCM code of SJCL. In some sense you could share heartbleed under this as well.

OK, so back to the question: it depends rather a lot about the size of $G$ to find out which $G^x$ is most efficient. The choice of library would probably depend on that. Runtimes may already include these kind of algorithms as well, but they may not always be the most efficient choice for certain parameters.

I'd recommend reference implementations if not for the fact that they are often horribly programmed. Mathematicians and cryptographers are just as likely to succeed in software development as anybody else. Quite often they do not keep to the requirements above, often for the sake of brevity.

Finally, you probably should chose a library that fits your programming environment of choice. The library should be quite extensive and the functions well defined; single purpose libraries should not be used unless they have been made for your specific problem domain.


OpenPGP Public-Key Encrypted Session Key Packet Key ID generation Im probably just not reading something again, but:

RFC 4880 says that a OpenPGP Public-Key Encrypted Session Key Packet (tag 1) is made up of

- A one-octet number giving the version number of the packet type.
The currently defined value for packet version is 3.
- An eight-octet number that gives the Key ID of the public key to
which the session key is encrypted. If the session key is
encrypted to a subkey, then the Key ID of this subkey is used
here instead of the Key ID of the primary key.
- A one-octet number giving the public-key algorithm used.
- A string of octets that is the encrypted session key. This
string takes up the remainder of the packet, and its contents are
dependent on the public-key algorithm used.

i encrypted (using a working pgp program) a string of 0123456789abcdef using a key whose KeyID is 30522545CF77DD86, but the pgp message packet that resulted had a KeyID of F940C4301A67779D in its tag 1 data. it is certainly not the KeyID from the public key i used.

what do i need to do to get that keyid? what am i not seeing?

key used to encrypt data:

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: BCPG v1.39

mQGiBE5B0h8RBAD533Z5bK1IpBx02QyQL0QoJE4uFRIMGDiwXuwmZzVl+R7Vlurd
GRLsCCbE6vOOh7XQVZGzLEBy9WNzZ9m+EbCfSVAYkjS6FhLws6hG6irrnS+b3JBf
gFJ8vNGF9Z7bhx+7y7NBk0IMyWkGnUkcnav73t5FQUI2faEBN4c/yAGJZwCgjcB7
3akWk9XVWvTCsiMXxpyvkukEALXsvB6cOoFEtQq9cQHjP63fBlvD94dhhMiM0cH6
hW9JotxdK+cxFGG9ZIWgoN2PWbMJka/H4W5EL6tS+YiNAR7I1Ozkt6X16GjnQUzZ
MlSpleK+KiKVN2anRaPEoOIinHrE3ZXd6QlJ/4+OJn4IVWmSEaJpFf4QNgvEu4rh
xinyBAD2RNzREOA+wpnFZ4lDt9NZXmXdxQME/l0J9XcvWhpGsxA/MATQKImy7N49
7GT/M38F+TrpBobag1O3buE99fOLyws4Tbc+sZMdHxoiGZDAIRNQS2rv475E6ktj
7vd5CYvOkA6+8sX1+hPcNlkHtHB1OFkJRsYp6k0zkyC9adjBM7QTYWJjIDxtYWtj
bUBhYWEuY29tPohGBBMRAgAGBQJOQdIfAAoJEDBSJUXPd92GRSQAoItbtbToOg7a
/hcg2sA/aBEQNwuxAKCGR69vmSoCWoBP5waPk0UsjM3BSbjMBE5B0h8QAgCUlP7A
lfO4XuKGVCs4NvyBpd0KA0m0wjndOHRNSIz44x24vLfTO0GrueWjPMqRRLHO8zLJ
S/BXO/BHo6ypjN87Af0VPV1hcq20MEW2iujh3hBwthNwBWhtKdPXOndJGZaB7lsh
LJuWv9z6WyDNXj/SBEiV1gnPm0ELeg8Syhy5pCjMAf9QHehP2eCFqfEwTAnaOlA6
CU+rYHKPZaI9NUwCA7qD2d93/l08/+ZtFvejZW1RWrJ8qfLDRtlPgRzigoF/CXbR
iEYEGBECAAYFAk5B0h8ACgkQMFIlRc933YZRrACfUnWTjHHN+QsEEoJrwRvFmvzj
bR4An24pTpeeN+I6R59O/sdmYsAhjULX
=sStS
-----END PGP PUBLIC KEY BLOCK-----

encrypted data: 0123456789abdef

-----BEGIN PGP MESSAGE-----
Version: BCPG v1.39

hI4D+UDEMBpnd50QAf9bWG97E9FfnSKB/WpVcBtLJqk5f/Ih9YZTUDULDZpSE0TP
ObJnCs91okOv6/BtDRDZ84ChF5pOZezb5+aL3TW5AfwK3gJ7nPTlmZOm5Kf7qOfB
n307xpn0qRw395y1mfOm10TsMpaCkbSvwjhqPi8hRMM17y29OsqGLstZdeAaNTGt
0mwB7EiZti4jOUF3/SCNnn2vA9hVc6o6c0l0h5vQOF0L+eL1Pmhg8RcFT4kHRnI/
A+Ad4hsbOxD1vvzZHx2iETkt1JmNTHmOOY5Cw/n+sFlU9JzZpzAtqwUjjnyN8NjQ
6NbpwL6gebTJCVTNW2c=
=kI32
-----END PGP MESSAGE-----

An OpenPGP "key" is actually a structure that may contain many public keys. Typically, it contains two, a signing key and an encryption key. The signing key is considered the top-level key, as it issues signatures claiming ownership of all the subordinate keys, be they encryption or signing keys.

The key ID of the whole structure as you'd see it in a program is the key ID of the top-level signing key. The keyID if the ESK packet is the key ID of the encryption key. That's why they're different.

Put your whole key into the dump program at http://www.pgpdump.net/ and you'll get the whole thing dumped out for you.


Quantum security risk to present encryption Quantum computers will seal the fate of conventional encryption techniques. Of these, the hardest hit will be the RSA algorithm used by 99 percent of all applications the encryption standard for any secure transfer and storage of communication data or software updates. What are some solutions to the inevitable?

Quantum computers will seal the fate of conventional encryption techniques

This is only somewhat true in regards to asymmetric cryptosystems. Algorithms such as AES256 and XSalsa20 will remain secure even in the face of full scale quantum computation.

  the hardest hit will be the RSA algorithm used by 99 percent of all applications the encryption standard for any secure transfer and storage of communication data or software updates.

Both RSA and discrete-logarithm based systems such as Diffie-Hellman (including the Elliptic Curve variants) are vulnerable to Shor's algorithm, and both are widely used. RSA is used more for signatures than for key exchange. RSA is far from a single point of failure and being the only mainstream public-key cryptosystem.

  What are some solutions to the inevitable?

It is arguable that Quantum Computing of scale that will impact cryptography is "inevitable". There are non-trivial engineering barriers that have to be overcome.

Solutions

NIST is currently hosting a contest of sorts to find and standardize quantum-resistant asymmetric calgorithms.

Candidate schemes include:

Hash-based signatures
Code based cryptography
Lattice based cryptography
Supersingular Isogeny Diffie-Hellman
Multivariate cryptography


What are the approaches to private computations? I'm talking about the ability to safely run a virtual machine on a physical device that is not trusted. It is necessary that the owner can not access the data that the virtual machine operates on. I am interested in what theoretical or practical implementations exist without special hardware.

I know about homomorphic computations (this in theory fully satisfies my question), but for now it's incredibly slow. It will take many years before the protocols of homomorphic calculations just approach application in practice.

I also read about Intel SGX, which implements enclaves. The RAM stores only encrypted data, which is decrypted at the input to the processor and is again encrypted at the output. The disadvantage of Intel SGX is that you need special hardware. How could you do something like this without a special hardware? How can we store a key for decrypting data from RAM so that the owner of this physical device can not recognize this key?

If the VM actually has anything that needs protection, running the VM on untrusted hosts is not secure (period). There is nothing that will change that.

Going to homomorphic encryptions etc. implies that even the VM doesn't know any secrets, only the source of the data (outside of VM and host) does. In this case, having a VM or not isn't even relevant.
There are of course still problems with the authenticity of the results etc. - just encrypting is never enough.

Using Intel SGX from within VMs relies on the support/cooperation of the VM software - meaning, it might be useful for separating VMs fom each other, but it can not help VMS against their malicious host.
Given that VMs are, well, virtualized, any hardware support is useless in your scenario. If the host and the virtualization software can't be trusted, your VM is not secure.


Question about second preimage resistance of hash function combiner Let $\Pi=(Gen_1,H_1)$ and $\Pi=(Gen_2,H_2)$ be two hash functions. Define $(Gen, H)$ so that $Gen$ runs $Gen_1$ and $Gen_2$ obtaining $s_1$ and $s_2$ respectively. Then let $H^{s_1,s_2}(x)=H^{s_1}(x)\|H^{s_2}(x)$, is it second pre-image resistant if at least one of $H^{s_1}$ and $H^{s_2}$ is second pre-image resistant?

I have found the paper Multicollisions in iterated functions, application to cascaded constructions.by Antoine Joux and it showed that the hash function $H^{s_1,s_2}(x)$ is not secure. But does this approach work for every hash function?

The answer you are looking for is that a pre-image/2nd pre-image attack on two combined hash functions is at least as difficult as an attack on the stronger of the two hash functions.

Take a look at Joux's paper on multi-collisions. There is a section on pre-image attacks for concatenated outputs. (I suggest reading the entire thing. It's one of those rare short, to the point, easy to read papers.)

The attack described in the paper has complexity of:

$n_g2^{{n_f}/2} + 2^{n_f} + 2^{n_g}$

For two hash functions of length $n_f$ bits and $n_g$ bits where $n_f \leq n_g$


Attacks on schemes based on elliptic curves when the transmitted points are not on the curve Some elliptic curve schemes require to send a curve point during the normal execution of the protocol. For example, ElGamal encryption and ElGamal signature require this. On the other hand, ECDSA does not.

Can an attacker determine some private information when curve points are sent to unsuspecting users which don't lie on the curve?

If either ElGamal encryption or ElGamal signature are vulnerable, is there an obvious property that can be checked to see if another protocol is vulnerable?

Let's assume that the curve parameters are pre-shared and the system is set up.

In this state we have well known attack that is called invalid-curve attack.

Let $E:y^2=x^3+ax+b$ and $E':y^2=x^3+ax+b'$ be two elliptic curves with reduced Weierstrass form. $E'$ is called an invalid curve relative to $E$.

Since formulae for adding and doubling points on $E$ does not involve coefficient $b$ thus addition law for $E$ and $E'$ is same. In this attack, we can send several low order points and find the private key using the chinese remainder theorem.

For more detail you can see "Guide to Elliptic Curve Cryptography" page 182.


Can we use the authentication tag as Nonce / IV for the next message? Let's assume we're in some scenario requiring transfer of large amounts of data. This means we can only use AES-GCM chunk-for-chunk as its maximal size is restricted to a few GiBs. This means we have to define a new nonce (a counter?) for each new chunk.

However each chunk needs to have its authentication tag appended to verify decryption. So I had the idea to use this available ressource for the next decryption to completely avoid those counters.
A bonus of this is that re-ordering attacks are completely impossible as the nonce is authenticated as AD for GCM and hence the previous tag will be used for the next tag, "chaining" the chunks together.

Note: One can also replace the word "chunk" by message and apply the same principle to something like TLS.
Note further: The "0"th authentication tag is a random value prepended to the chunk.

So my question:
Is it actually safe to use the authentication tag of the last message as the nonce for the next one in AES-GCM mode?

For me it looks like it should be safe as the first chunk is standard GCM and every following one is indirectly based on the exact same nonce.

If needed: The first nonce is assumed to be of size 16 bytes and every tag is also assumed to be of size 16 bytes.

What was the inspiration for this question?
An AE scheme (AERO) that actually verifies based on nonces and state. In this case we don't even need state (except for the bytes we just had available i.e. the latest tag). And this would also reduce the possibility of errors based on wrong nonce states (incremented the counter in the wrong way).

The authentication tag in GCM is generated by XORing a block cipher output with the Galois field hash (and truncating it for shorter lengths). It is thus assumed to look PRF. So it is effectively just a random nonce that should not collide until a birthday bound of $2^{t/2}$.

With a tag length of 96 or more bits, it should be secure. Shorter random IV lengths are prohibited in SP 800-38D. However, that standard also limits you to using the key no more than $2^{32}$ times, when using a random IV.

(Even though the nonce is "controllable" by an attacker with a chosen plaintext attack, that does not allow generating a collision except randomly. Otherwise it would lead to a forgery attack.)

I would still prefer a counter.

  For me it looks like it should be safe as the first chunk is standard GCM and every following one is indirectly based on the exact same nonce.

Note that this dependence means two things:

You need the tag from the previous chunk to decrypt the next one, so parallelization is slightly more difficult. (E.g. both processors would need to read the same memory location.)
If some chunk does not authenticate, you cannot trust that it's the only one that has changed. An attacker who changed chunk $i$ could also remove any number of chunks after it without that fact being visible. (With counters you can detect a localized change and still authenticate the rest as being in the correct place.)


Semi static ElGamal vulnerability when the secret is not truely random Assume Alice wants to communicate with Bob. Bob provides his public parameters $(g,n,y)$ with $y=g^x$ where $x$ is his secret key

Now Alice wants to send $m$ to Bob. She generates a random $r$ and computes $u = g^r$ and $c=my^r$ and sends back to Bob $(u,c)$.

You intercept $(g,n,y)$ and $(u,c)$ and you also know what $m$ is.

As far as I know, it is still not possible to recover $r$ from this.

But what happens if Alice sends a second message $(u',c')$ with $u' = g^{r'} = g^{f(r)}$, in other words $r'$ can be easily computed from $r$.

Can you recover $m'$ and/or even $r$ ?

The answer obviously depends on what $f$ is. However, we can say a few general things.

If $f$ is a "simple" linear function (e.g. $f(r) = kr$ for most constant $k$), you can recover $m'$ easily. You cannot recover $r$ or $r'$.

If $f$ is a more complex function that is bijective or nearly bijective (say SHA-256), then you probably cannot recover $m'$. You cannot recover $r$ or $r'$.

If $f$ is a sufficiently many-to-one function and its inverse image is sufficiently simple (say $f(r) = r \bmod{2^i}$ for a suitable $i$), you may be able to recover $r$ and $r'$.


How does GHASH used in GCM behave as a universal hashing function? As per my understanding, a Universal Hash Function isn't a cryptographic hash function & it's output isn't uniformly distributed. However, this is still secure because it's actually a family of functions & one or more of the random inputs to the function decides which function is actually picked from the family of functions & this is what makes it secure.
However, these are the Parameters to GHASH
$GHASH(H, A, C)$ where
$H = E(K, 0^w)$
$K$ is the encryption key & it's fixed, so a new one isn't picked every time, which means $H$ is also fixed.
$A$ is the Additional Authenticated Data
$C$ is the Ciphertext
So how exactly is this a universal hashing function - what is the family & how exactly are we randomly choosing from the family?

Indeed $H=E_k(0)$ is used to choose from the family. This is not a problem, and here is some intuition on why.
The output of the hash function is not leaked in clear, it is "hidden" by xoring with $E_k(iv,ctr=0)$ which is different per each encrypted message (in contrast to $H=E_k(0)$). Otherwise it would be indeed trivial to recover H as the UHF is linear.
Intuitively, the property used is that UHF should be hard to blindly predict the difference for any two inputs without knowing the key, even with multiple attempts, but without revealing the UHF value on each attempt.
Note that the "difference" matters here because in forgery attempts you are allowed to reuse the nonce, so guessing the right difference would suffice for a break. For example, given $$(iv,m,t),~~ t=E_k(iv,ctr=0)\oplus GHASH(m))$$ and guessing the difference $\Delta = GHASH(m)\oplus GHASH(m')$ would allow to forge
$$
(iv,m',t'),~~ t'=t\oplus \Delta=E_k(iv,ctr=0)\oplus GHASH(m').
$$


Key exchange using ECDH vs ECIES? I'm a beginner to ECC crypto programming. Can anyone explain to me the difference between using ECDH for shared key exchange and the use of ECIES by encrypting a shared key with the public key of the receiver?

I feel that ECIES could also provide me with secure key exchange as long as the private key is kept secret.

That's a bit of a strange question. ECDH is a key agreement protool. ECC does not have a direct form of encryption as RSA has. ECIES is basically ECDH used to derive a symmetric key, which is then used to encrypt the plaintext. You can see it as a delayed form of key agreement.
So your question is if ECIES can be used to encrypt session keys. That would come down to performing ECDH to derive a data key, and then using that data key to encrypt a session key. Yes, it is probably secure, but directly deriving a session key using ECDH is a lot easier. Using ECIES is only useful if - for some reason or other - authenticated DH key establishment cannot be integrated into a protocol.
For more information about using ECIES & ECDH for authentication, please see this other question.


Parallel Rho Hash Collisions I've been having a hard time placing DJB's analysis of Oorschot & Wiener parallel rho collision search into context.  There is plenty of discussion about the birthday bound and quantum computers in relation to hash functions, but these speedups are much more dramatic.

How does this attack alter the runtime analysis for brute forcing hash collisions?  Is it only a linear speedup, but how big are hashes going to balloon to?

How does this attack alter the runtime analysis for brute forcing hash collisions?

Absolutely nothing whatsoever.

The traditional brute force analysis counts the total number of hash computations required, and nothing else.  In this model, the best we can do is hash $O(2^{n/2})$ distinct messages, and then scan them all, and see if there are two messages that hash to a common value.

If the hash function acts like a random function, we can't do any better; however if we look at actually implementing this attack, we notice that this attack also requires $O(2^{n/2})$ space, and that's actually a bigger problem than the computation required.

What rho (and parallel rho) collision attacks do is increase the number of hash computations required by a constant factor (nothing huge, but greater than 1); and also drastically reduce the amount of memory involved.

If we're actually looking to do a brute force collision (say, of a 100 bit hash function), a rho collision attack would be much more feasible than anything requiring you to store $2^{50}$ or so hashes.  However, if you're just thinking about how much processing power it would take, the traditional birthday attack scores better.

And, because a standard birthday attack against a 256 bit hash function would require $O(2^{128})$ hash evaluations, which we believe is infeasible, a rho attack would require even more (and hence, also be infeasible).

If you're worried about the parallel side of it, well, the possibility of parallel computation is already baked into the analysis; it is commonly believed that $O(2^{128})$ (or more) hash evaluations is infeasible, even if someone had vast (but realistic) quantities of parallel processors.

BTW: DJB's point wasn't that parallel rho attacks are actually a threat against SHA-256 or SHA3-256; he is trying to show that attack is better than a quantum computer running Grover's algorithm to search for collisions (and so if those hash functions are safe against a parallel rho attack, they are certainly safe against a quantum attack).


For uniterated SHA-256 of salted password, should the password precede the salt? This is a follow-up to this question (thanks to answers from @fgrieu and @kelalaka
) about the format of a salt when hashing a salted password.

I realize this is pretty much academic, as the proposed uniterated SHA-256 of a salted password is already acknowledged to be much less secure than trusted password storage algorithms (scrypt, Argon2, PBKDF2, etc.). And, this may be a very obvious point, but I haven't found anything mentioning it (quite the opposite).

Nevertheless, considering the use of this (ill-advised, but currently available) approach, when concatenating salt & password, if the salt precedes the password, wouldn't that allow an attacker to optimize away the salt when doing a dictionary or brute force attack, and speed up the results?

Here's my thought:  A SHA-256 hash is a left-to-right processing of the source data. While processing the data, the SHA-256 code could be modified to take a snapshot of the intermediate algorithmic values (variables) as the salt is being processed, but just before the first password character is read. This would be done once to collect the values. Then a further modification of the SHA-256 code, which allowed the hash for each try to begin with the intermediate values previously stored. This would allow only the characters of the test passwords to be processed on each try, eliminating the overhead of processing the (presumably 256-bit) salt, but still providing the correct SHA-256 result.

Again, assuming no iterations, and no nested hashing, wouldn't it be better for the password to precede the salt, so that the attacker had to process the salt data to obtain the correct SHA-256 value for every try?

We are considering two hypothetical password hashes

$(S_i,P_i)\mapsto H_i=\operatorname{SHA-256}(S_i\mathbin\|P_i)$
$(S_i,P_i)\mapsto H_i=\operatorname{SHA-256}(P_i\mathbin\|S_i)$

As pointed in the question, both are un-iterated, thus very weak under the attack model where the salt $S_i$ and hashes $H_i$ leak, and the adversary is after $P_i$ (for a particular $i$, or worse for one of any $i$).

An important thing is what we put in the salt $S_i$: that should include both a fixed string $F$ dependent on the instantiation (e.g the name of the server), and a user-unique string (e.g. userid, login, email, random) $U_i$. The term $U_i$ helps because with $U_i$ adversaries can not attack multiple logins simultaneously, they must perform a hash for each password tested for each login. The term $F$ prevents amortizing attack work across multiple servers, and makes the hash slower, thus more secure.

The least feeble option is probably $H_i=\operatorname{SHA-256}(P_i\mathbin\|U_i\mathbin\|F)$, with $F$ as large as possible. The password should be first for the reason in the question: that blocks optimizations where some of the hash's internal operations is reused across multiple $P_i$. For the same reason, $U_i$ should be second.

But when $P_i\mathbin\|U_i\mathbin\|F$ is short (less than 64 bytes), the order is nearly immaterial, because that fits in the same first padded block of message of SHA-256, thus an attacker can not precompute any full compression in SHA-256, at worse some of very few rounds among 64.

Thus if for some strange reason (like a device operated on small battery and very little RAM) one can't go for an iterated password hash and must use plain SHA-256, then put the constant part $F$ of the salt last, and make it as long as practical; and rather put the password before the salt.

As an aside, if a long $F$ is obtained by repeating a shorter string (which allows arbitrary long $F$ with only little RAM), it should have an odd length, in order to reduce the potential for optimization of the message expansion of SHA-256.

P.S. per comment: While the $U_i$ part of the salt must be in the database, $F$ needs not, at least in each entry, especially if it is long. I have been assuming that $F$ is public, not "pepper" (that is, semi-secret). If there is some pepper $K$ (that is, a tentatively secret key, by opposition to salt that is assumed fully public), it should be early in the hashed data, in contact with $P_i$ or otherwise in the first 64 bytes; and backed up other than in the database in case the whole thing needs to be restored on a different machine.


What is the projective space? In Elliptic Curve Cryptography, using the projective space is often mentioned to accelerate the computations and to represent the point at infinity.
But What is the Projective space exactly ? How can we represent the curve in such space ?

Let us consider this beautiful elliptic curve:

She is defined in a plane ($\mathbb{R}^2$).
1. From a plane to a projective space
For an affine plane $\mathbb{A}^2 = \{(x,y): x,y \in \mathbb{K}\}$, we can define its projective space as follow:
$$ \mathbb{P}^2 = \{(x:y:z): x,y,z \in \mathbb{K}\}\backslash(0:0:0) \sim $$
Where $\sim$ is the equivalence relation such that:
$$\sim : (a:b:c) \sim (a':b':c') \iff \exists \lambda. (a,b,c) = (\lambda a', \lambda b', \lambda c')$$

In other words, all the points on the same line going though the origin $(0:0:0)$ are equivalent with respect to $\sim$.

It may seem complicated so let us use some figures.
Here we have a projective space.

Each points on the same green line (passing through the origin) are equivalent due to the $\sim$ relation. Each points on the same orange line (passing through the origin) are equivalent due to the $\sim$ relation.
We can divide this space into 2 sets. The points with $z=0$ (in orange) and the points with $z \neq 0$ (in green).
Let us have a look at the green set. If we consider the lines (or equivalent points), one can remark that they all intersect the plane $\{z=1\}$ (See diagram below). Thus all the points in the green area have an equivalent into the  plane $\{z=1\}$.

The only points that does not satisfy this property are those which equivalence line is parallel to the plane $\{z=1\}$. In other words, the points where $z=0$.
Let us have a look at those points. Using the same principle as with the green space, one can see that each line going through the origin cut the line $\{z=0, y=1\}$. Therefore with one exception, all the points in the orange plane have an equivalent on the line $\{z=0, y=1\}$.

Note that the exception are the points parallel to the line $\{z=0, y=1\}$, in other word, the $x$ axis. Because they form a line, they are all equivalent with respect to $\sim$ therefore, they are all equivalent to $(1:0:0)$.

In the end, all the points in the projective space $\mathbb{P}^2$ have an equivalent in the plane $\{z = 1\}$ or on the line $\{y = 1, z = 0\}$ or to $(1:0:0)$.

2. Going back to the curve
In the projective space, the equation of the elliptic curve is:
$$y^2\ z = x^3 + a\ x\ z^2 + b\ z^3$$
(The degree of each term of the polynomial must be 3: $deg(y^2\ z) = deg(y^2) + deg(z) = 3$ etc.)
We can now represent the points of the elliptic curve in this space. Due to the equivalence relation of this projective space, we can just display those on the different subdivisions (plane $\{z = 1\}$, line $\{y = 1, z = 0\}$ and $(1:0:0)$).
for $(1:0:0)$ (point)
$(1:0:0)$ is not part of the curve as $y^2\ z = 0$ and $x^3 + a\ x\ z^2 + b\ z^3 = 1$
for $z = 1$ (plane)
This is the simplest form, by replacing $z$ by its value in the equation we get: $y^2 = x^3 + a\ x+b$. Therefore the representation of the elliptic curve will be the same as the one above but projected on the plane $\{z = 1\}$.
for $z = 0$
$$z = 0 \implies y^2\ z = 0 \implies x^3 + a\ x\ z^2 + b = x^3 = 0 \implies x = 0$$
The points that satisfy this equations are the one of the form $(0:\lambda:0)$.
Or $(0:\lambda:0) \sim (0:1:0)$ This is the missing point that can not be represented using the plane representation: the point at infinity $P_\infty$.
Thus, we can finally represent our elliptic curve in its projective space as bellow.

Remarks
As a quick reminder, here is what a curve really looks like in a finite field: not as smooth as one would expect...

$$y^2 = x^3 - 2 x + 1 \text{ over } \mathbb{Z}_{89}$$