Can the original data be extracted from an RSA private key signed message I'm working on a system that the main objective is to verify the message was written by the right person, but it would also be desirable if the message can't be understood by anyone sniffing it.

It runs on Java/Android using RSA/ECB/PKCS1Padding (so it's not textbook RSA, but a real implementation) and the data is guaranteed not bigger than the RSA 2048 bits.

The public key on this case is not really public, it is sent to the server over standard SSL/HTTPs with certificate pinning and kept there.

The desired message is later sent over an insecure channel signed with the private key and the server can verifies the sender.

The question: can someone that sniffed the message over that insecure channel recreate (within reasonable time frame) the original message?

edit:

Adding here to give a more complete explanation to Martin Boner.

I'm mostly a Android developer with general notion of cryptography, that's why I'm making sure to ask questions that might be dumb for some, but it's better be sure I'm not messing up important things.

For that reason, I'm not sure the direct answer to Martin, so I'll just show the code. It's Android/Kotlin code, but it's standard Java APIs:

private const val TRANSFORMATION = "RSA/ECB/PKCS1Padding"

internal fun rsaEncrypt(data: String, keyPair: KeyPair): String {
    val cipher = Cipher.getInstance(TRANSFORMATION)
    cipher.init(Cipher.ENCRYPT_MODE, keyPair.private)
    val bytes = cipher.doFinal(data.toByteArray(Charsets.UTF_8))
    return Base64.encodeToString(bytes, 0)
}

So this returned String is what's being sent. I manually tested that val bytes when converter back to string is unreadable
and I have the inverse operation (below) that runs on my tests that I know the original data can be reconstructed with the public key.

internal fun rsaDecrypt(data: String, keyPair: KeyPair): String {
    val cipher = Cipher.getInstance(TRANSFORMATION)
    cipher.init(Cipher.DECRYPT_MODE, keyPair.public)
    val bytes = Base64.decode(data, 0)
    val decrypted = cipher.doFinal(bytes)
    return String(decrypted, Charsets.UTF_8)
}

How the other end exactly is doing, I don't know because that was up for the Ruby developers, but it's perfectly reasonable to assume it's very similar to the above.

With this edit in mind, I'll add a secondary question:

(original question) Can someone that sniffed the message over that insecure channel recreate (within reasonable time frame) the original message?
(Bonus) Is there any other security concern/issue here? For example, could someone after sniffing a few messages over the insecure channel, be able to regenerate or fake the private key and pretend be the proper user?

Whenever you see the letters ECB, you should run away screaming.  This is a telltale sign that something has gone terribly, horribly wrong.  The code fragment you quoted implements what we sometimes call ‘textbook RSA’, which is a polite way to discreetly announce to the cocktail partygoers that you are desperately in need of a professional cryptographer.

This is not your fault: whoever designed the Java API that requires you to specify ECB in a string and which you will use to ‘encrypt with the private key and decrypt with the public key’ (which is a contradiction in terms that makes cryptographers twitch involuntarily, sometimes leading to a cocktail dribbling down your face and shirt) did not have the decency to ask for a professional opinion—which is what you are more or less doing now!—before they inflicted a monumentally wrong confusion of ideas into an API set in stone.

Let's back up a moment.  What do you and your peer have in common, and what security do you want?

If you share a secret already, and you want to exchange unforgeable and possibly secret messages, what you want is a symmetric-key authenticator like HMAC-SHA256, or a symmetric-key authenticated cipher like AES-GCM or NaCl crypto_secretbox_xsalsa20poly1305.  But you mentioned public keys, so maybe you and your peer don't share a secret yet—maybe all you have is your respective public keys, which are known to be correct but are not secret.
If you share a public telephone book with public keys, and you want to exchange unforgeable and possibly secret messages, what you want is public-key key agreement like X25519, which is a way for you to use your private key and your peer's public key in the telephone book to compute a secret, which can also be computed by your peer using their private key and your public key in the telephone book so that you and your peer have a shared secret; or you want public-key authenticated encryption, like NaCl crypto_box_curve25519xsalsa20poly1305, which works by stringing together public-key key agreement (X25519) and symmetric-key authenticated encryption (crypto_secretbox_xsalsa20poly1305).
If your peer has a public telephone book where you are named, and you want to send a message to your peer that your peer can show to a third party and convince the third party it came from you, then what you want is public-key signatures like Ed25519.

You could also use an RSA-based signature scheme like PKCS#1 v2.1 RSASSA-PSS, but unless you have a specific technical reason motivating the use of RSA, you are better off using the smaller faster safer Ed25519, unless the cost of verification is your principal bottleneck.
If you have a public telephone book where your peer is named, and you want to send a message to your peer anonymously so that only your peer can read it but not necessarily verify it came to you, then what you want is public-key anonymous encryption like NaCl crypto_box_curve25519xsalsa20poly1305 with an ephemeral public key.

You could also use an RSA-based encryption scheme like PKCS#1 v2.1 RSAES-OAEP, strung together with an authenticated cipher like AES-GCM, but unless you have a specific technical reason motivating the use of RSA, you are better off using the smaller faster safer NaCl crypto_box_curve25519xsalsa20poly1305 with ephemeral keys, unless the cost of encrypting messages is your principal bottleneck.

But OK, let's suppose you are using some RSA signature scheme.

Any serious RSA-based signature scheme involves hashing the message.  The simplest one, RSA-FDH, uses a hash function $H$ that hashes messages into all or nearly all of the set $\{0, 1, 2, \dots, n - 1\}$; a signature under public key $n$ on a message $m$ is an integer $s$ such that $s^3 \equiv H(m) \pmod n$.  From the signature $s$, even if you don't have the message $m$, you can recover $H(m)$ simply by computing $s^3 \bmod n$, but if $H$ is a good hash function this doesn't help to recover $m$.

With RSASSA-PSS, the equation is more like $s^3 \equiv 2^t r + H(r \mathbin\| H(m)) \equiv n$, where $H$ is a smaller hash function like SHA-256.  Again, you can recover $H(r \mathbin\| H(m))$ this way, but not $m$.

There are some ‘message-recovery’ variants of RSA signature schemes, in which some part of the message $m$ is embedded in $s$ alongside $H(m)$, but they are not widely used and you would probably know if you were using one.

All that said: Usually what you do is send a signed message, i.e. a message alongside its signature; otherwise, how does the recipient act on the message, or even find what message the signature corresponds to?  And if you do that, there is nothing a priori that prevents anyone but the intended recipient from reading the message—after all, in a signature, only the sender's keys are involved.

You can combine public-key signature and public-key encryption, but this is usually a bad idea for two reasons:

A secure composition is hard to get right; OpenPGP and S/MIME got it wrong.
Public-key signature also usually guarantees that third parties can verify messages, which is usually not what you want for private conversations.

So, you are most likely better off using NaCl crypto_box_curve25519xsalsa20poly1305, which does it all in one: combines you private key, your peer's public key, a 192-bit message number, and a message, and returns a ciphertext that your peer and only your peer can check for forgery and decrypt.


Origin of the SHA-224 initial hash value? At the start of each of the SHA-0 through -2 algorithms, the initial state is set to certain constants.  I'm curious where the initialization values in SHA-224 are from.

MD5's initial values are simple increasing and decreasing patterns of hex digits.
SHA-0's and SHA-1's values are the same as MD5's with one additional value that is also a simple hex digit pattern.
SHA-256's values are the fractional bits of the square roots of primes $2$~$19$.
SHA-384's values are the fractional bits of the square roots of primes $23$~$53$.
SHA-512's values are SHA-256's values expanded out to 64 bits.

But what are SHA-224's initialization constants from?  They're the only one in the SHA family that I can't find the source of.  They're also not simply the square root of primes $23$~$53$ like you might expect.

The SHA-224 initial values are the second 32 bits of the fractional parts of the square roots of the 9th through 16th primes (namely, 23 through 53), or in other words, $\lfloor 2^{64} \sqrt{p} \rfloor \bmod 2^{32}$, for $p = 23, 29, 31, 37, 41, 43, 51, 53$

For example, the hex expansion of $\lfloor 2^{64} \sqrt{23} \rfloor = 4cbbb9d5dc1059ed8_{16}$, and so the initial value for $a$ is the last 8 hex digits,  namely $c1059ed8_{16}$

Similarly, the hex expansion of $\lfloor 2^{64} \sqrt{29} \rfloor = 5629a292a367cd507_{16}$, and so the initial value for $b$ is $367cd507_{16}$

Note that the SHA-224 initial values are the lower 32 bits of the SHA-384 initial values (!).


Under what conditions did a Bletchley bombe stop? I am trying to understand the conditions necessary for one of the Bletchley Park bombes to stop. Let me give an example.

I have been experimenting with Enigma machine and bombe simulators to try to understand better how the bombe works.

Using a standard three rotor Enigma machine set up as follows:

Rotors IV-I-III,
starting with QLH
rings set to AAA
with plugs EL GK US XZ WI NV FD BY MC PQ

The following plaintext WETTERVORHERSAGE becomes the following cryptotext RRHKJKNJXEUWNFOT (see enigma simulator) .

Using this as a crib, the menu that this produces has three loops (REHTK, EHT, RETK) and a click (loop of the two letters WR), which is pretty good as a crib as this means that the bombe then returns far fewer false stops.

When I plug this crib into the following bombe simulator (where all rings are set to A) I get a collection of about twenty stops, one of which is the correct one.

So my question: what is the condition that stops a bombe that is satisfied with respect to the crib menu?

My understanding is that the back of the bombe is set up to simulate the menu and then the bombe is switched on, stopping through a short circuit when, well, when what?

I tried to use the first false stop that the bombe simulator gave me to understand: 231-YAL. So in particular, my question can be applied to this situation. What is it about this set-up that would stop the bombe with the given crib-menu?

What I did notice in this configuration is that the click is correct with respect to the letters M and T (indicating that there should be plugs WM and RT) BUT the remainder of the loops do not match.

After a year I have managed to find a suitable solution to the problem. My understanding is based on the following picture that I created, based on a simplified version that I found online (at present I cannot find the reference, if I do I will edit it in).

It is supposed to be a bombe and can be understood in two parts.

The top contains 26 columns, one per letter of the alphabet. Each column is made of 26 connections one from each letter to each other. That what gives the triangular effect.
The bottom half are what would be the bombe connections depending on the menu derived from the crib. Each block that we can see spans and connects two columns are based on the crib and the corresponding position of the rotors.

The idea is that in the real bombe all these lines are wires and a current is introduced arbitrarily somewhere. Then the current flows through the diagram making lines 'live' and others not.
A live connection between two letters means that either there is a Steckerverbindung between them else they are not Steckered together. Although this sounds like a tautology, we do need to consider the picture as a whole. For example: if at the A column only the F connection is live, then it means that it is consistent that A and F are Steckered together; if at the A column more both F and G are live, then it means that A is not Steckered with either F or G; if at the A column all connections are live, then this means we have a definite contradiction, and that means the bombe position is false - and in such a case the bombe, I assume, would have just continued.
We can test the information above with such a diagram as above. The following diagrams are all close ups of the diagram above (the top right part of the bottom half):

The bombe is in the correct position and the current is sent into a correct connection, as in the picture below. Here the current is sent to the X connection in the R column. I indicated in red the live current. It flows through the diagram and as can be seen. Eventually we see that the L wire of the T column s live, as is the E wire of the V column. Nothing else in this block becomes live. So it is consistent that we have the three Steckerverbinugen RX, TL and VE.
The bombe is in the correct position and the current is sent into a false connection. Again we can use the picture above but now we concentrate on the blue. Here I assumed the current was sent in at the A wire of the T column. In this case eventually every wire is live except the correct wires as given above (at least in the given part of the picture). When I say eventually, this means that one has to follow in and out of all the connections, and up through the top part of the diagram when necessary. Hence when the bombe is in a correct position and viewing the diagram as a graph, we would have (ideally) two connected components: the correct component (where there is at most one live wire per column) and the false component (where we would have at least one non-live wire pre column). I say ideally since there would be at least one extra component of information that is unobtainable from the rest (i.e. letters that are not part of the steckers we can find and don't appear in the crib).
If the bombe is in a false position, then it shouldn't matter we the current is sent in. I did this in the following diagram, which is the same as the original but all rotors have been shifted by one position. Here the current enters at the L wire of the T column. In this case, eventually, everything becomes live, which gives the contradiction.

We also learn from this set up the importance of the loops in the crib. This enables a lot of feedback, which is particularly important when the current is sent into the false wire.
Hence to answer my original question: when did the bombe stop? It seems that it should not stop when one column is completely live. And therefore perhaps it stopped when there was at least one non-live wire per column. If your crib had no loops, and therefore no feedback, then this condition would be easily satisfied, and there would be far too many bombe stops to deal with.
Edit after 4 years: I found in the book The Hut Six Story from Gordon Welchman first published in 1982 (although my copy seems to be first published in 1997) Appendix I p241 it says: Thus, in order to detect a "drop", the bombe needs to look for one of only two situations: a case in which current does not get back to any test register terminal other than A, or one in which there is some terminal other than A to which current does not get back.


How to judge a determinant equals non-zero in cryptography? In the paper [1,p5], the authors construct a matrix to find out $n$ solutions of a equation set as follows:

where $c_i$ is generated by the adversary, $c$ is picked by the simulator. Note that $c^i$ means different forgeries instead of exponent.

My question is, they find out $n$ solutions iff the determinant equals non-zero, but they don't prove why the determinant equals non-zero. There is no need to prove it?

(I'm not true this is a crypto problem or not, it seems more like a math problem?)

[1] Liu, J. K., Au, M. H., Susilo, W., & Zhou, J. (2014). Linkable ring signature with unconditional anonymity. IEEE Transactions on Knowledge and Data Engineering, 26(1), 157–165. https://doi.org/10.1109/TKDE.2013.17

For linear system $Ax = \beta$ with a vector on $n$ unknowns $x$, $A$ is the Vandermonde matrix, produced with powers of $c_i$. For such a matrix, determinant is a product of $(c_i - c_j)$, and so is non-zero for different $c_j$ in the set of field elements.


What is the difference between these two TLS suites? I am comparing the security information of two different HTTPS connections in the Google Chrome (v63.0.3239.132) security tab in developer tools. The information for each of the two connections is given below:

The first states ECDHE_ECDSA with X25519 as the key exchange.  The second just states plainly that X25519 is the key exchange.  This seems odd to me because X25519 is the curve, correct?  Are these two key exchanges the same and they are just worded differently (for some reason)?  Is this because of the use of QUIC?
The first site is an API, the second is google.co.nz.

What are the differences, if any?

There is no difference. It’s just the way the devs described it; which actually makes sense because X25519 implies ECDH is used.

Also, X25519 is not the curve… it’s the function (to be used with Curve25519).

Quoting RFC 7748, Elliptic Curves for Security, January 2016, Page 7:

  The "X25519" and "X448" functions perform scalar multiplication on  the Montgomery form of the above curves.  (This is used when implementing Diffie-Hellman.)

So, to recap: The curves are named Curve25519 and Curve448, while the according functions are called X25519 and X448. And since X25519 implies ECDH, one might regard the additional mentioning of ECDH or ECDHE_ECDSA to be superfluous.


How were codes in WW1 reciphered (to enhance security levels) without them turning meaningless? In WW1, the Germans made their communications secret by encoding their messages. This meant that the message's sender would have a codebook with all possible words and phrases he might use listed in alphabetical order. Those were attached to a random number. He would then write down the numbers corresponding to his message. The receiver would have the same book, just reversed. He would have all numbers listed from the smallest to the biggest, and he would be able to decode the message by finding the corresponding word/phrase for each number.
So far, so good. Now, I keep reading about how Germans would add a layer of enciphering to enhance security. I just do not get how this wouldn't be paradoxical with the concept of the codebook. I have two different outcome suggestions, and they both fall short:

Suppose the sender wanted to send the word "hi." He would then encipher this and get, let's say, "xt." He would then look at his codebook and find no number corresponding to "xt."

Suppose the sender wanted to send the word "hi." He would then find the corresponding number for "hi." He would then decipher that number and get a different number. The receiver would then look up the number and find either a non-existing number or a wrong word.
Here are two examples in the literature of the history of cryptography that state how an extra layer was added:

Page 66 in The History of Code Breaking:
"The Zimmermann Telegram was superenciphered (encoded again by using the German Diplomatic Code Book, Code No. 13040)."
Under "VB codebook" in the Wiki page about Room 40:
"Re-ciphering of the code was accomplished using a key made up of a codeword transmitted as part of the message and its date written in German. These were written down in order and then the letters in this key were each numbered according to their order of appearance in the alphabet. This now produced a set of numbered columns in an apparently random order. The coded message would be written out below these boxes starting top left and continuing down the page once a row was filled. The final message was produced by taking the column numbered '1' and reading off its contents downward, then adding on the second column's digits, and so on."

The concept is called superencipherment or multiple encryption, and works as follows:

The original message M is enciphered using the code book, resulting in an enciphered message C1.
C1 is then treated as the plaintext, and enciphered using another method, resulting in a new ciphertext C2.
C2 is then sent to the receiver
The receiver uses the decryption algorithm for the second method on C2, obtaining C1.
The receiver then uses the code book to decrypt C1 and get the message M.

Creating an example:
Suppose I want to send the message "Small supplies of fruit expected. Buy as much as you can."
For my code book, I will use the A B C Universal Commercial Electric Telegraphic Code, 4th Edition.

Step 1: On page 128, we have the phrase "Small supplies of fruit expected.", with the corresponding code number 06375.  Moving to page 45, we find "Buy as much as you can." with the code number 02221. So in this example, C1 is "06375 02221".

Step 2: For the second level of encryption, I will add 13348 to each code number (ignoring any carry or borrow beyond 5 digits).  So to encrypt C1, we calculate 06375+13348=19723 and 02221+13348=15569, resulting in C2 as "19723 15569".

Step 3: The message C2 ("19723 15569") is sent to the receiver.

Step 4: The receiver decrypts C2 by subtracting 13348 from each code number.  So the receiver would calculate 19723-13348=06375 and 15569-13348=02221. This results in the message C1 equal to "06375 02221".

Step 5: The receiver then uses the code book to decrypt "06375 02221". Since I am using a one-part code here, again go to pages 128 and 45 to get the original message "Small supplies of fruit expected. Buy as much as you can."

As long as you maintain the sequence "Encrypt using A, Encrypt using B, send, Decrypt using B, Decrypt using A", the exact encryption steps can be replaced as long as the sender and receiver agree on the algorithms and keys.


Simple reversible algorithms that satisfies SAC What are some simple algorithms that …

operate on a block of fixed size (or can be easily made to do so), i.e. the input block has a fixed size, e.g. 256 bit, and the output is a block of the same size
are reversible (can't be a hash function)
satisfy the strict avalanche criterion (SAC)

I'm not interested in any other cryptographic properties. It doesn't have to be a secure cipher.

I use the word simple in a very general sense. I'm interested in anything that most engineers would call simple, easy to implement in software and/or hardware, although there is likely a correlation to well-defined measures like computational complexity.

I have considered AES or a hash function like SHA-256, which I believe exhibit a strong avalanche effect (not sure if they satisfy SAC), but a hash function is not reversible and AES seems unnecessarily complicated if you do not require the algorithm to be a secure cipher. I thought there must be something simpler. I could, of course, be mistaken.

One simple approach would be, if your input/output size is $n$ bits, is to select a representation of $GF(2^n)$, and a random nonzero value $v$, and have your function be $F(u) = u \times v$ (where $\times$ is multiplication within $GF(2^n)$)

It operates on blocks of fixed size
It is reversible (by multiplying by the value $v^{-1}$)
It satisfies the SAC in this sense: for input bit $i$, and any output bit $j$, flipping bit $i$ of the input will flip bit $j$ of the output for almost exactly half, that is, $2^{n-1}/(2^n-1) \approx 1/2 + 2^{-(n+1)}$

Now, it doesn't satisfy the SAC for a fixed value $v$; for a fixed value, flipping bit $i$ will flip bit $j$ either always or never; so, it might not be the answer you're looking for (on the other hand, it may)


Security of stream cipher with a priori knowledge of message I am generating a ciphertext by XORing the message bits with key stream bits of a stream cipher. But, if I know a priori that message bits contain a predefined number of 0's (say 60%) at unknown positions, then how to analyze the security of such system both mathematically and empirically.

Can we analyze using hypothesis testing (given two messages m1 and m2 with the same distribution and analyze whether ciphertext leaks any information about messages) or using entropy bounds?

Can we analyze using hypothesis testing (given two messages m1 and m2 with the same distribution and analyze whether ciphertext leaks any information about messages) or using entropy bounds?

If the output of the key stream generator is indistinguishable from a random stream and uncorrelated to the plaintext, then no, you cannot.

Consider the case where we know almost all of the paintext, that is, we have an encrypted message $e = m \oplus s$ (where $m$ is the plaintext, and $s$ is the keystream output), and we know apriori that either $m = m_1$ or $m = m_2$ (but we don't know which).

We can compute $e \oplus m_1$ and $e \oplus m_2$, one of which will be $s$ and the other will be $s \oplus m_1 \oplus m_2$

However, if we assume that $s$ is random and uncorrelated, then both $s$ and $s \oplus m_1 \oplus m_2$ will be random; we have no way of deciding which is which.  Any hypothesis testing on $s = e \oplus m_1$ will give the same expected result as on $s = e \oplus m_2$


Is RDSEED a true RNG? Is Intel's RDSEED a true random number generator?

Yes, RDSEED is a true random number generator.

From Wikipedia:

  The entropy source for the RDSEED instruction runs asynchronously on a self-timed circuit and uses thermal noise within the silicon to output a random stream of bits at the rate of 3 GHz [...].

RDSEED is however used as a seed for (software implemented) PRNGs of arbitrary width.


Is signing a plaintext sufficient? If I have N bytes of plaintext, does signing it with my private key prove (to holders of my public key) that I have signed that exact plaintext messages?

i.e. could an attacker use the plaintext and signature to generate another plaintext which would also verify?

Or do I need to hash the plaintext to provide message integrity?

A signature algorithm should - in general - be thought to contain the hashing method as parameter. Take for instance RSA / PSS. RSA / PSS includes the  EMSA-PSS-ENCODE operation. Here the hash function to use is an option to the algorith.

Step 2 is:

  Let mHash = Hash(M), an octet string of length hLen.

where M is the message to be signed.

"Or do I need to hash the plaintext to provide message integrity?" is therefore a question that is non-sensical for most signature definitions. RSA has deprecated modes that directly sign a message (with message recovery) but those are generally not used. ECDSA is also defined for use with a hash function and EC crypto cannot easily "encrypt the message" with the private key for signature generation.

As you have found out, Signature dsa = Signature.getInstance("SHA256withECDSA"); uses SHA-256 as an option to ECDSA. The hashing will then be performed internally.

Sometimes hash value or intermediate hash value is used as input for signature generation. This can be useful when the device that performs the private key generation is limited in hashing bandwith. E.g. for a smart card you may not want to send all the data to the smart card - sending just the hash is much more efficient.


Which attacks are possible against raw/textbook RSA? The PKCS#1 standard defines multiple padding schemes for signature generation/verification (EMSA-PSS and EMSA-PKCS1-v1_5),  and encryption/decryption (EME-OAEP and the less safe EME-PKCS1-v1_5).

Which attacks are possible on signature generation/verification and encryption/decryption if no padding mechanisms are applied, i.e. if raw RSA is used over the plaintext or hash?

This describes some attacks against textbook RSA (also known as raw RSA), where the public function $x\mapsto y=x^e\bmod N$ or private function $y\mapsto x=y^d\bmod N$ are applied directly to the integer $m$ representing the message. Per standard assumption, the public key $(N,e)$ is known.
Encryption / Decryption
Per standard assumption, ciphertext $c\gets m^e\bmod N$ is known.

Determinism in textbook RSA allows an attacker - given a ciphertext - to search for the corresponding plaintext.
Determinism also leads to traffic analysis. It is possible to distinguish if the same encrypted message is sent, and when the message changes. This could reveal information. For example, if an attacker sees $E(\text{stay put})$, $E(\text{stay put})$, $E(\text{stay put})$, $E(\text{stay put})$, and finally $E(\text{attack})$, an attacker will know something has changed.
$e$th root attack: For short messages $m$ and low $e$ (e.g. $e=3$), it may happen that $m^e<n$ so that the ciphertext $c=m^e$, and then it is possible to implement the decryption function as $e$-th root extraction. This attack has extensions to $\log_2(m)$ somewhat above $\log_2(n)/e$.
Broadcast Attack: When the same message is sent encrypted to at least $e$ different correspondents, it can (with high likelihood) be recovered without knowing any private key.
Meet in the middle attack; this is an improvement of 1 above that allows searching plaintext faster than brute force; if the message is assumed to be writable as $m=a\cdot b$ with $\max(a,b)\le u$ and $\min(a,b)\le v$, the effort is $\mathcal O(u)$ with memory $\mathcal O(v)$ for constant $N$.
Leak of Jacobi: if $c=m^e\bmod N$, then $\big({c\over N}\big)=\big({m\over N}\big)$. In other words, the Jacobi symbol of plaintext $m$ relatively to $N$ leaks from the ciphertext $c$. This can be a problem in some (rather hairy) protocols built on top of RSA, or/and for some constructions of message $m$; for example $m=4r^2+b$ with $r$ a 500-bit random secret, $b$ a single-bit secret, and 1024-bit $N$: when it is observed that $\big({c\over N}\big)=-1$, it is known with certainty that $b=1$.

Signature Generation / Verification
Per standard assumption, verification of signature $s$ computes $s^e\bmod N$ and either checks that against $m$, or checks that's a sensible $m$.

Eve can pick a random $s$, compute $m=s^e\bmod N$, and pretend $s$ is the signature for $m$. With a little trial an error, she can choose some of $m$, e.g. make it print as OK if it's displayed as a C string, with an expected $2^{24}$ attempts.
An attacker can combine signatures to create a new signature. For example - given a signature of $2$ (i.e., $2^d\bmod{N}$) - it is possible to create a signature for $4$ ($2^d\cdot 2^d\equiv 4^d\bmod{N}$).
Say Alice implements a signing service using her RSA private key. In particular, anyone can send Alice a message, she checks the message contents to make sure there isn't anything too bad in it. If the message isn't bad, she signs it. Let $m_b$ be a bad message. Eve can send $km_b$ for some constant $k$ to Alice. Since $km_b$ isn't bad, Alice will sign it. Giving Eve $(km_b)^d\bmod{N}$. Eve can also get a valid signature for $k$ from Alice since it isn't bad $k^d\bmod{N}$. Using those two, Eve can now get a valid signature for $m_b$, something that Alice would have never signed before, by multiplying the inverse of the second signature.
Eve knows the signature of some messages; e.g. the signature of $0$ is $0$, the signature of $1$ is $1$, the signature of $n-1$ is $n-1$, the signature of $k^e\bmod N$ is $k$ for $0\le k<N$. This could be a nuisance by itself, or could help attacks 1 and 2.

More attacks are described in Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem (in Notices of the AMS, 1999; or this other version with a few more references).


Decrypting a small Message using RSA with a Private Key If I have a private key of (43, 341). What would be the steps I need to take to decrypt a small message using RSA? I have looked online and everything seems very confusing. Any tips or advice would be helpful.

I have gotten this far:

p=31  q=11
p*q=341
O(n)=(31-1)(11-1)=300
e=7
(43*e)%300=1  e=7
public key (e,n) (7,341)
Private Key (d,n)(43,341)
encryption of m=2   c=2^7%341=128
decryption of c=128 m=128^3%341=2

What would be the next step to decrypt a message?

In step 9, you decrypted the ciphertext, 128, to the original message, 2. That's it. You're done with the toy example of naive RSA encryption/decryption.

Using RSA in real life, you would apply padding, such as OAEP (also known as PKCS#1v2), to your message before raising it to the e power modulo n.

If the plaintext you're trying to encrypt is quite short, say less than half as long as the RSA modulus, you might agree with the recipient to apply RSA directly to the message.

Normally the plaintext isn't that short. What you do is encrypt and MAC the plaintext with a symmetric cipher and MAC algorithm that you agree on with the recipient, using a randomly selected key for the symmetric cipher and a randomly selected key for the MAC. Then you use RSA with a 'message' consisting of the key to the symmetric cipher and the MAC key. You send your recipient all of (A) the RSA ciphertext, (B) the ciphertext from the symmetric cipher, and (C) the MAC. The recipient decrypts the RSA ciphertext (A), unpads it and obtains the keys for the symmetric cipher and the MAC. With those in hand, verifies the MAC (C) of the ciphertext (B) and finally decrypts the symmetric ciphertext (B) to obtain the plaintext.


Proving impossibility for a stronger primitive I have a primitive $A$ which is impossible to prove under some hardness assumption in a black-box way. Now, if another primitive $B$ is stronger than $A$ - in other words $B$ implies $A$ - will it imply that $B$ is also impossible to prove under the same hardness assumption in a black-box way?

This seems like a logic question: $B$ implies $A$, therefore not $A$ implies not $B$

Proving $B$ would prove $A$, so if it is impossible to prove $A$ it must be impossible to prove $B$ in the same setup.

Alternatively lets assume $B$ is proven, since $B$ implies $A$, $A$ is proven. Yet $A$ is unproveable: a contradiction.


Adapting LWE Trapdoors for Ring-LWE In the paper Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller by Micciancio and Peikert, they present the following theorem about the existence of trapdoor for LWE.

Theorem 5.1: There is an algorithm $\mathsf{GenTrap}(1^n,1^m,q)$ that, given any $n\geq 1, q\geq 2$ and $m=\mathcal{O}(n\log q)$, outputs a matrix $\mathbf{A}\in\mathbb{Z}^{n\times m}_q$ and a trapdoor $\mathbf{R}$ such that:

$\mathbf{A}$ is indistinguishable from a uniformly chosen matrix; and
there is an algorithm $\mathsf{Invert}$ that, given $\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}$ (with $\mathbf{s}\in\mathbb{Z}^{n}_q$, $\mathbf{e}\in\mathbb{Z}^m$ and $||\mathbf{e}||<q/\mathcal{O}(\sqrt{n\log q})$) and a trapdoor $\mathbf{R}$, outputs $\mathbf{s}$ and $\mathbf{e}.$

They mention that the results in the paper can be straightforwardly adapted to the ring setting (Ring-LWE), however, they don't give details on that. What would be an equivalent result to this one in the ring setting?

Instead of plain matrix, a matrix similar this (but bigger):

+a -h -g -f -e -d -c -b
+b +a -h -g -f -e -d -c
+c +b +a -h -g -f -e -d
+d +c +b +a -h -g -f -e
+e +d +c +b +a -h -g -f
+f +e +d +c +b +a -h -g
+g +f +e +d +c +b +a -h
+h +g +f +e +d +c +b +a

which one can deduce it's equivalant in addition and multiplication to a polynomial reduced by $X^8+1$. And here, the polynomial is the "Ring".

And instead of plain matrix of $n$ x $m$, we use a $1$ x $2$ matrix of polynomials.

Note: the arithmetical difference between matrix-represented polynomial rings and plain matrices, is that the former is commutative in multiplication, while the latter is not.


privacy enhancing techniques on image data To give some context:

I am looking for a suite of techniques and tools that can theoretically enable me to conduct analysis such as classification on image datasets in a manner in which a naive observer cannot derive "much" information from an image e.g. if the image is of a person/object then the naive observer cannot tell who/what is in the image.

Naively adding noise doesn't seem to protect the content of an image, since a human observer can easily see past the noise.

I'm not aware that a machine learning task can be performed on encrypted images effectively and on naive inspection it shouldn't be possible while still maintaining cryptographic properties.

Is there any work out there on such techniques that maintain privacy of an image while still allowing it to be used for analysis?

Is what I'm after a fool's errand?

I think what you are looking for is "Perceptual Hashing".

What I understand from your question is that you need a way for programmatically identifying images even when they have been manipulated beyond human recognition.

Their is a Microsoft project called PhotoDNA. I believe the have a cloud API.

You may also want to look at this Python example


Is it safe to use shared secret as a symmetric key in one way communication? I have a one way communication from one device to another, which needs to be secure and there cannot be any feedback in the other direction. Now both sides happen to have ECC P-256 key pairs and they know public keys of each other. So, I thought it would be natural to use the shared secret which is already 256bit - suitable for AES256, in which sender can encrypt the message and receiver can decrypt it.

Note: By shared secret I mean the usual $x$ coordinate of multiplying public key of $A$ and private key of $B$, or public key of $B$ and private key of $A$ - which are the same. I am not referring to calculated secret that is based on some random value generated each session, that would require I believe two way communication, which is not possible in this settings.

Now I am wondering if this by itself is sufficient, maybe I am overthinking this but I see two issues:

Such derived key is not uniformly distributed
If the symmetric key gets compromised, it requires that at least one side changes its key pair, as opposed to having a key different for every session, so only data for one session would be compromised.

I thought about generating some pseudorandom sequence of bytes on the sender's side, adding it to the shared secret, then hashing it altogether and use the result as a symmetric key - using SHA-256 would again give exact size of key for AES256 (this should also address the issue 1.). Then the random sequence of bytes would be part of the message, so receiver could do the same.

Now is this secure? Is there better way to do this, within the one way communication constraint? Or maybe this all is unnecessary and just using the shared secret directly is enough?

The linked questions (duplicates) are talking about shared secret, but I don't see how they address the one way communication problem I have here. There is no issue in calculating the shared secret, and also it is no issue of how random is the shared key, it is more about whether keeping the symmetric key the same (based on shared secret) for every session, or whether to apply some additional processing to ensure it is different each session, and if so, how to do it safely.

Consider a device A and a device B. Let me paraphrase what I believed you just said.

Communication happens only from A to B. We have public keys $PK_A$, $PK_B$, and the private keys $PrK_A$, $PrK_B$.

Devices A and B apply the Diffie-Hellman key exchange protocol to obtain a shared secret, $SS$. You say that it is logical to use $SS$ as a key for AES symmetric cryptography. It is sensible that the shared secret obtained from the DH protocol is used to derive symmetric keys from.

You say that the shared secrets derived from DH are not uniformly distributed. This is indeed the case. Hashing the obtained shared secret will solve this, as any different shared secret will produce a vastly different digest. $K_{AB} = H(SS)$

Let $r$ denote a random number. You propose $H(SS|r)$ (appending pseudorandom numbers, then hashing it) but this is will not result in a differently distributed digest space than omitting the $r$. You'll have to communicate $r$ to $B$ as well so there is no security gain but only a costs increase.

You also said that in the case of $K_{AB}$ being compromised, at least one of the devices must change its key pair. To my understanding this is not true. A new Diffie-Hellman key exchange can take place with different domain parameters, since the private keys of A and B are not compromised in this scenario.


Why are RSA key sizes almost always a power of two? I know that other bit sizes are possible, e.g. this HTTPS server seems to have a 9000 bit key https://www.ssllabs.com/ssltest/analyze.html?d=qqq.gg, but it's very rare that one sees a key not of size 1024, 2048, 4096, etc. bits in common usage - what is the reason for this? Is it just customary, or is there a cryptographic advantage?

In RSA, the bit size $n$ of the public modulus $N$ is often of the form $n=c\cdot2^k$ with $c$ a small odd integer. $c=1$ ($n=512$, $1024$, $2048$, $4096$.. bit) is most common, but $c=3$ ($n=768$, $1536$, $3072$.. bit) and $c=5$ ($n=1280$..) are common. One reason for this is simply to limit the number of possibilities, and similar progressions are found everywhere in cryptography, and often in computers where binary rules (e.g. size of RAM).

The difficulty of factoring (thus, as far as we know, the security of RSA in the absence of side-channel and padding attacks) grows smoothly with $n$. But the difficulty of computing the RSA public and private functions grows largely stepwise as $n$ increases (more on why in the next paragraph). The values of $n$ just below a step is thus more attractive than the value just above a step: they are about as secure, but the later is more difficult/slow in actual use. And, not coincidentally, the common RSA modulus sizes are just below such steps.

One major factor creating a step is when one more word/storage unit becomes required to store a number. When the storage unit is $b$-bit, there is such step every $b$ bits for the RSA public function $x\mapsto x^e\bmod N$; and a step every $r\cdot b$ bits for the RSA private function $x\mapsto x^d\bmod N$, with $r=1$ for the naïve implementation, and $r$ equal to the number of factors of $N$ when using the CRT with factors of equal bit size (most usually $r=2$, but I have heard of plans up to $r=8$). On any modern general-purpose CPU suitable for RSA, $b$ is a power of two and at the very least $2^5$, creating a strong incentive that $n$ is at least a multiple of $2^6$ ($r=2$ is common, and the only reasonable choice for $n$ below about a thousand).Note: $n=1984=31\cdot2^6$ is not unseen in the field of Smart Cards, because the next multiple of $2^6$ would break the equivalent of a sound barrier in a common transport protocol, ISO/IEC 7816-3 T=0. For a list of common RSA modulus size in this field, search LENGTH_RSA_1984.

As an aside, it is significantly simpler to code quotient estimation in Euclidian division (something much used in RSA) when the number of bits of the divisor is known in advance. This creates an incentive to reduce the number of possible bit sizes for the modulus. The two simplest cases are when the number of bits is a multiple of $b$, and one more than a multiple of $b$; the former won.


How fast would a polynomial time factoring algorithm compute? I know factoring is the chief means of breaking RSA keys. I know an algorithm that runs in polynomial time would be able to break an RSA key pair "quickly". But how quickly is "quickly"? Note, I'm not talking about any quantum computing at all here.

I know an algorithm that runs in polynomial time would be able to break an RSA key pair "quickly". But how quickly is "quickly"?

No way to say, it might be microseconds, and it might be large multiplies of the age of the universe.

When we say that an algorithm runs in polynomial time, we're not saying anything about how fast the algorithm runs given any particular input.  Instead, what we're saying that, as we give the algorithm increasingly large inputs, the time it takes doesn't increase that quickly.

How polynomial time is generally expressed is that there are values $c, e$ such that, given a problem of size $N$ (and in the factorization case, $N$ would be the number of bits in the RSA key), the algorithm takes time less than $cN^e$.  Now, there are no limits on how big $c$ and $e$ might be, and so this doesn't give any limits on how much time a specific instance might take.

On the other hand, for all known factorization algorithms, this is not true -- no matter how large values we select for $c$ and $e$, we can find problem sizes $N$ large enough that the algorithm takes more than $cN^e$ time; hence saying that an algorithm is "polytime" does say something -- it just doesn't say what you're hoping it did.


Encryption and decryption using multiple different keys I want to encrypt files, wich can be decrypted and encrypted by multiple different keys. Is there any algorithm which can accomplish this?

Example (Each user has a different key):

User 1 encrypts a file with his key
User 2 decrypts the file, adds information and encrypts it with his key
User 3 decrypts the file with his key

It seems that the similar problem was discussed here. The general approach was to encrypt the file with a random key and then encrypt copies of this key with users' keys.

However, if you'd like really different keys, check @ddddavidee's answer.


Is Googles Envelope Encryption the same as Hybrid Encryption? Google is advertising the use of Envelope Encryption in their products with their KMS. By the description, it sounds very much like Hybrid Encryption. But since I could not find any reference to Hybrid Encryption, I wonder if there might be a difference in the idea behind it.

Source: https://cloud.google.com/kms/docs/envelope-encryption

Hybrid encryption refers to an implementation of a public-key encryption interface by the composition of a public-key primitive to encapsulate a symmetric key that's used with a symmetric algorithm to encrypt the actual messages.  The motivation is that public-key primitives don't perform nearly as well as symmetric ones, so this hybrid encryption optimizes performance by minimizing the use of the former.

In the sense that the Google cloud (and AWS) use the term envelope encryption, there's a difference both in the mechanics and the motivation:

Envelope encryption doesn't require the use of public key cryptography; normally instead it uses symmetric Key Encryption Keys (KEKs, also often labeled "master keys") to encrypt also symmetric Data Encryption Keys (DEKs).
The motivation is not performance like it is with hybrid encryption, but rather key management. Google and AWS promote envelope encryption in connection with their Key Management System services (KMS) that generate and managed master keys internally, and are designed not to allow export of said keys, but rather to require clients to submit messages to the service for decryption/encryption. The intended use of this is that the KMS manages your KEKs, and the clients ask it to encrypt and decrypt DEKs with it. And the point of this is to avoid an architecture where you deploy a copy of the same symmetric master key to lots of hosts in your network, increasing the risk that this key will be exposed by a compromise of one of the servers.

So there is a similarity in that short-term symmetric data keys are getting encapsulated with some sort of long-term key, but what sort of long-term key is assumed is different, and the goal of the constructions isn't the same.


Hardware AES: can we have a decryption implementation only? I'm wondering if implementing only the AES decryption can reduce the hardware cost? And does anybody have some examples of the cost (speed, size) of hardware AES implementation?

In practice, AES encryption mostly use CTR mode or some authenticated encryption, and in these the block cipher itself is only used for encryption. There is thus often no need to implement AES decryption in hardware.

We can always remove features from hardware circuitry. Implementing only the AES encryption sizably reduce the hardware cost (compared to also implementing decryption), but implementing only decryption saves much less (especially for cost-optimized rather than speed-optimized designs), because:

Decryption requires (as does encryption) forward-computing the round keys, and (specific to decryption) either storing them or walking backward. Therefore the relatively large saving possible for round keys computation by omitting said storage or capability to walk backward has no equivalent when omitting encryption.
The S-box used for encryption and the (inverse) one used for decryption are different, and there's sizable saving possible by omitting the decryption one. However the two are not needed simultaneously; it is feasible to share some gates between the two; and even in speed-optimized implementations where that's not done, it might still be possible to reduce to almost nothing the power consumption (and associated costs) of the inactive S-Box.
The MixColumns step for decryption is significantly more complex than the one for encryption, and it is feasible to share a lot of gates between the two, so that omitting encryption capability won't necessarily save much there.


Calculate a base point on the twist of secp192k1 with maximal order I want to calculate a base point on the twist of secp192k1 with maximal order.
'secp192k1': _ECData(
    p=2**192 - 2**32 - 2**12 - 2**8 - 2**7 - 2**6 - 2**3 - 1,
    a=0, b=3,
    Gx=0xDB4FF10EC057E9AE26B07D0280B7F4341DA5D1B1EAE06C7D,
   Gy=0x9B2F2F6D9C5628A7844163D015BE86344082AA88D95E2F9D,

 n=0xFFFFFFFFFFFFFFFFFFFFFFFE26F2FC170F69466A74DEFD8D

Let $\beta$ a non-square element in $\mathbf{F}_p$, then the elliptic curve defined by $\beta y^2 = x^3 + 3$ is a quadratic twist of secp192k1 whose equation is $y^2 = x^3 + 3$.
It means that if $x_0^3 + 3$ is a square, there exists $y_0 \in \mathbf{F}_p$ that is a square root of $x_0^3 + 3$, so $(x_0, y_0)$ belongs to secp192k1, and on the other hand if $x_0^3 + 3$ is not a square, there exists $y_0$ such that $\beta y_0^2 = x_0^3 + 3$, so $(x_0, y_0)$ lies on the quadratic twist instead. Here, we can take $\beta = -1$ since it is not a square in the finite field $\mathbf{F}_p$.
There is a relation between the cardinality (number of points) with the quadratic twist. The cardinality of secp192k1 is a prime number $n$, that can be rewritten as
$$
n = p + 1 - t,
$$
where the value $t$ is called the trace of Frobenius. Then it is easy to compute the cardinality $n'$ of the quadratic twist:
$$
\begin{align}
n' & = p + 1 + t, \\
& = 3 \cdot 373 \cdot 56383 \cdot 619124299 \cdot 160695254510139039862526647837522958722153.
\end{align}
$$
Write $n'= h\cdot q$ where $q$ is the largest prime in the decomposition. The goal is to find a point of order $q$ on the twist. Let's use SageMath for the computation, but unfortunately it does not handle elliptic curves with an equation of the form $-y^2 = x^3 + 3$. That's not a problem, a simple change of variable will do the trick: let $x'=-x$, and the equation becomes $-y^2 = -x'^3 + 3$, and by multiplying each side by $-1$ we get $y^2 = x'^3 - 3$.
We can make some check that all is good:
p = 2**192 - 2**32 - 2**12 - 2**8 - 2**7 - 2**6 - 2**3 - 1
E = EllipticCurve(GF(p), [0, 3])
n = E.cardinality()
print(n.is_prime())
t = p + 1 - n
Et = EllipticCurve(GF(p), [0, -3])
nn = Et.cardinality()
print(nn == p + 1 + t)
print(Et.is_quadratic_twist(E))

The last command returns a nonzero value if the two curves are indeed a quadratic twist of each other.
To find a point whose order is the largest prime $q$, we can run something similar as in this post.

Generate a random point on the twist;
Compute $Q = [h]P$;
If $Q \neq \mathcal{O}$, then $Q$ is a point of order $q$.

h = 39062147507228523
q = 160695254510139039862526647837522958722153
while True:
    P = Et.random_element()
    Q = h*P
    if Q != Et(0):
        break
print(Q)
print(Q.order() == q)


How to know which key was used for an AES encryption? I am starting a project where several categories of sensitive data have to be accessed within a table. Based on his role, a user can see clear text columns (not encrypted), accessible columns (decrypted for his role), and can't see the content of other columns (encrypted).
This implements segregation of duty (for example) :

Database administrator can only see clear text columns
Person A can only see person's details to validate data
Person B can only see revenue details to build statistics

Role management rules dictate which role uses which key, and keys are highly protected. But after a few years of people moving and roles adapting, how can I make sure the system still knows which key was used when?
I can imagine two solutions:

Build a solid log of keys usage
The key signature hash is present in the cryptogram

Even though I don't think one can guess the key from the hash, I'm afraid this would introduce a weakness...
How would you proceed?

I agree with your solution. Log that stores info about who and when is active with a particular role. You could use ID or name, but password hash seems ideal, to see when user changed the password, to not to show him his old data that he will try to decode with a new password. SHA3 is considered secure. If user makes a password and then sends SHA3(password) - there is no way for you to get the password out without brute force.
Could use SHA3(company name + password) to avoid easy guessing of known password hashes from the table. If someone gets the table, makes pre-calculated table with values like sha(12345) and scans the whole database, he is likely to find some matches.
Could also use SHA3(username + password), to avoid search for dublicates if the whole database is leaked or to show that even you cant search for dublicates. In addition to the previous bonus.
Could go further and use SHA3(your own secret + SHA3(username + password) to protect from all sides, leaked database and your own actions against the users. That is, user sends SHA3(username+password), but on your server you make SHA3(your secret+what user has sent you), and only that becomes public and is written in the database. One more way to make it better is a long generation time on the user side, like 100 or 100k steps of SHA3. But this is questionable for weak devices. Reason for this is mainly to prevent you to quickly crack users passwords with a dictionary, since you know how their response is calculated and what is there. One step further is to use algorithms that are hard to speed up on asics or GPU. https://en.m.wikipedia.org/wiki/Argon2
TLDR: use SHA3(your secret + 1000 chained steps of SHA3(username+password)), OR SHA3(your secret + argon2(SHA3(username + password)). Check if mobile device can handle it under 1 second.


Is Encrypt+HMAC stronger than AEAD? There are a few posts that I've come across that seem to imply that using regular encryption and a MAC might be better than using the newer AEAD (ie: AES/GCM) modes.

https://www.daemonology.net/blog/2009-06-24-encrypt-then-mac.html

https://blog.cryptographyengineering.com/2011/12/matt-green-smackdown-watch-are-aead.html

My questions are thus:

Is an AEAD more likely to fail (being subject to chosen plaintext attacks, versus HMAC protecting the encrypted part more securely), and if so, does it fail in a more catastrophic way?

Assuming that you have securely generated both the HMAC and encryption keys, is Encrypt+HMAC therefore more secure?

This is something I tend to disagree somewhat with Colin Percival on.

You should use Encrypt-then-HMAC if and only if you can get it right. The biggest pitfall is using a short-circuiting string comparison versus a constant-time string comparison. Given the former, people can use timing attacks to forge valid HMACs for arbitrary ciphertexts. With an encryption mode like CBC, this could be used to read the contents of encrypted messages. Other pitfalls include accidentally implementing Encrypt-and-MAC or MAC-then-encrypt, which have historically had vulnerabilities related to their construction.

On the other hand, EAX and GCM modes provide this feature transparently. There are some concerns about potential side-channel attacks against dedicated AEAD modes, and there is also the conceptual issue of potentially passing unauthenticated packets to your decryption algorithm. You, of course, have to get details like unique IVs correct, but you also have this requirement for Encrypt-then-MAC.

That said, potential flaws in EAX and GCM implementations can be fixed for many people at once with patches to the relevant libraries. Flaws where non-cryptographers naïvely compare HMACs are epidemic, and even high-profile projects like Google's KeyCzar have made this simple mistake. If you absolutely know what you're doing, Encrypt-then-HMAC is a provably secure construct. If you don't know what you're doing, something like EAX or GCM may be found to have weaknesses, but they are assuredly better than implementing something yourself.

Edit: I may have made Encrypt-then-HMAC sound easier than it actually is. One other major pitfall of Encrypt-then-HMAC is not HMACing enough information, or not HMACing the information correctly. The HMAC must include the ciphertext, the additional authentication data, and the initialization vector. It probably must also (perhaps someone else can confirm or deny this) include a descriptor to identify the encryption algorithm used. To pass these fields into the HMAC, you must use a format that unambiguously delineates fields. The easiest way to do this is to prepend a 4-byte big-endian length before any variable-length field (usually just authentication data and ciphertext), but doing this for all fields is probably a good idea. If you don't HMAC all this information, an attacker can modify any of the data not included. If you don't HMAC them unambiguously, an attacker can manipulate message boundaries, which could allow him to conduct an exploit.

Edit 2: Another detail of Encrypt-then-HMAC I've forgotten. Hopefully you can see how hard this is to get right. Ideally, you should never reuse the same key across security contexts. I'm unaware of any attacks that would result from using your encryption key as the key for the HMAC, but best practice is to use a different key for encryption and authentication. One simple approach (assuming a 256-bit encryption algorithm and 256-bit HMAC) is to use a "virtual" 512-bit key. Use the first half for encryption and the last half for authentication. Another approach is to use a 256-bit key, but pass it through HKDF with a 512-bit output; use this as before: split it into two parts, use one for encryption and one for authentication.

Edit 3: I asked a highly relevant question on the security StackExchange a few months ago. Thomas Pornin's detailed answer may be helpful.


Sextic twist optimization of BN pairing - cubic root extraction required? I found the following paper really interesting:

http://www.researchgate.net/publication/220378229_A_family_of_implementation-friendly_BN_elliptic_curves/file/79e4150b3a773beecd.pdf

It allows construction of a subset of BN curves where it easy to find the sextic twist. For instance, one knows through the contruction that the sextic twist will be the D-type which means one doesn't have to count points on the elliptic curves to check their order. Also, it gives explicit parameters for the generators of the involved subgroups.

Anyway there's one thing I'm wondering which the paper doesn't go into. Having determined the sextic twist and its generator, how do I map points on the twist back to the "real" curve over $p^{12}$? Other papers specify an isomorphism like:

$(x,y) \to (i^{1/3} x, i^{1/2} y$)

for the D-type (where $i$ plays the role of the epsilon in the paper mentioned). But how do I find the cube-root of $i$? It has to be found when $i$ is interpreted as an element of the finite field of size $p^{12}$ (probably represented using tower polynomials which the paper also describes? I have no problems understanding how to do ordinary arithmetic in this field but I don't know how to do cubic root extraction.

Also, I'm wondering if I'm completely off track because one of the benefits on the construction mentioned in the paper should be that one doesn't have to do cubic root extraction!

You need to recall how the extension is built. $\mathbb{F}_{p^{12}}$ is built on top of $\mathbb{F}_{p^2}$ using the reduction polynomial $f(x) = x^6 - \xi$, where $\xi \in \mathbb{F}_{p^2}$ is a non-square and non-cube (using the notation from the paper). In other words, this is the set of polynomials with coefficients in $\mathbb{F}_{p^2}$, modulo $f(x)$.

Since we're working modulo $f(x)$, then $f(x) = 0$ which means that you can write $x = \sqrt[6]{\xi}$. However, this does not mean that you actually carry out the sextic root (it does not exist in $\mathbb{F}_{p^2}$), but you can "define" the sextic root of $\xi$ as $x$ (which is an element of $\mathbb{F}_{p^{12}}$: $x = 0x^5 + 0x^4 + 0x^3 + 0x^2 + 1x^1 + 0$). This process is called "adjoining roots": here is a good explanation. (A good analogue is with how you build the complex numbers by "defining" $i$ as the square root of $-1$, which does not exist in the reals).

In your question, $i = \xi$. This means that $i^{1/2} = (i^{1/6})^3 = x^3$ and $i^{1/3} = (i^{1/6})^2 = x^2$. They are just $\mathbb{F}_{p^{12}}$ elements with one coefficient $1$ and the others are zero and are trivially "computed"; you don't need to carry out any square or cube root.

There are some other issues since the sextic extension is often built as a quadratic extension over a cubic extension, but the reasoning is the same.


Step by step conceptual implementation of AUTHENTICATED Diffie-Hellman? I'm already doing classic DH with pre-shared key in my setup, and it prevents people knowing the same password from eavesdropping on others' traffic. But it doesn't cover situations where a third party authenticates to the server, then masquerades as the server to an incoming client, performing an authentication and then forwarding the traffic to and from the server transparently to both parties, all the while it is able to read and modify it at will.

Wikipedia contains half an explanation in its DH article about how the authenticated/public key flavor goes, but it's confusing to follow step by step. From what I managed to understand, the private key is g^a%p=PUBKEY then for each one-way encrypted message, g^b=ENCRYPTED_SECRET is computed, and sent to the PUBKEY holder.

I do not understand however, what the PUBKEY holder is supposed to do with ENCRYPTED_SECRET upon receipt in order to retrieve b, if b is indeed what is supposed to even be retrieved. Nor what the formula for this should be, what I exponentiate to what etc.

A step by step would help. Thank you.

Both parties are pub-key holders, so let's call them A and B having their private keys $a$ and $b$.

DH conceptually goes (this is something you already may know):

A: computes $g_a = g^a \pmod p$ and sends it to B
B: computes $g_b = g^b \pmod p$ and sends it to A
A: computes key $K = g_b^a \pmod p = g^{ab} \pmod p$
B: computes key $K = g_a^b \pmod p = g^{ab} \pmod p$

and now there are several authentication schemes to validate they're really speaking to each other. You may check the X.1035 or SPKE, there are the complete step-by-step recommendations.

Basically I found 2 methods:

A and B send each other hash of the salt, their public keys, shared password and the computed secret key
DH parameters ($p$ or $g$) depend from the shared password


RSA proof regarding m % n I have a question regarding the proof that RSA works
I understand that $m^{(ed \bmod z)} \bmod n = m \bmod n$ , but I don't understand why $m \bmod n = m$
(This question assumes m is the message, $z=(p-1)(q-1)$, $d$ is such that $(ed \bmod z) = 1$, and $e$ is such that $e$ is relatively prime with $z$)

All is solved in the comments, but I thought this would be a good opportunity to tell a real story. I was once called urgently by a company that I consulted for due to a bug discovered by their QA department. When they encrypted and decrypted with plain RSA, they would sometimes not get the same input back. The problem was simple, they were using RSA1024 at the time (many years ago) and would take random 1024-bit strings as input. But as good QA people, they also tested the "edge cases", so they would encrypt the string of all zeroes and the string of all ones. Needless to say, the string of all ones would not decrypt correctly. This is exactly the case that $m \geq n$ and so "decryption" indeed doesn't work. It's a nice story and just goes to show that even QAing crypto requires some math understanding!


Is RSASSA-PKCS1-v1_5 a good signature scheme for new systems? Is RSASSA-PKCS1-v1_5 a good signature scheme to recommend that people use in new systems?  Is it believed to be secure and represent the state-of-the-art in RSA-based signatures?

I understand that RSA-PSS is a newer signature scheme, also standardized in PKCS #1.  I found a memo from RSA recommending that people transition to RSA-PSS.  Is that right?  Would it be better to recommend that people use RSA-PSS, instead of RSA-PKCS1-v1_5?  If you were going to recommend a single RSA-based signature scheme, which would you recommend that new systems use?

Practical relevance: for instance, at the moment the current draft of the WebCryptoAPI recommends supporting RSASSA-PKCS1-v1_5 (but not RSA-PSS).

PSS is harder to implement because it uses randomness -- randomness is hard on many embedded systems like smart cards.

The most proclaimed advantage of PSS is that it has a "security proof" with, apparently, a rather tight reduction (see this page for some references). Security proofs are not an easy subject; the proof for OAEP (the encryption padding which is like the "sister protocol" to PSS) was found out to be wrong by Shoup and then repaired again by Fujisaki, Okamoto, Pointcheval and Stern, albeit with some casualties on the tightness front. I do not know how much all of this extends to PSS, but it shows that security proofs, however cool they may be, also need the "peer scrutiny" on which cryptographic security is traditionally built.

On the other hand, v1.5 signatures have been exposed "in the wild" for twice as long as PSS, and remain unbroken. In my opinion, this is very good and I quite trust that kind of security.

On a practical point of view, using a signature algorithm implies using a key storage device which knows that algorithm (smart card, HSM, software implementation...). The choice is not necessarily up to the application which requests the signature.


Does having a hash of a password jeopardize the security of plaintext that was encrypted with that password? A malicious actor wants to decrypt ciphertext that was encrypted with a password. He also possesses the hash (bcrypt/PBKDF2) of that password. Does he have any significant practical advantage in decrypting that ciphertext as compared to just having the encrypted ciphertext (with no hash)?

I believe that the clear advantage would come from the ability of being able to do a dictionary attack, since the guessed passwords could be deterministically checked against the hash. However, I could not find or come up with any other advantage. How does this change the situation if the password used is stronger (making dictionary attacks less dangerous)?

Does having a hash of a password jeopardize the security of plaintext that was encrypted with that password?

As usual in password-based cryptography, we'll consider that the password was chosen from a relatively small set, small enough that password enumeration by an adversary can generate passwords including the one of a target user with fair probability, but large enough that additionally computing the (purposely slow) password hash for each password enumerated is too costly for the attacker.

Three cases must be distinguished.

If the password hash is directly the key of an encryption algorithm, having that password hash is having the encryption algorithm's key, and the security is compromised.
If the password (rather than its hash) is directly the key of a fast encryption algorithm, then the security is jeopardized by that, not by the disclosure of the password hash. Problem is, an adversary can enumerate passwords and test each to find the right key, under the standard assumption of availability of a suitable plaintext/ciphertext pair, or just ciphertext if plaintext is redundant.
If the password is processed thru a purposely slow password-to-key derivation function, either different from the one used for the password hash, or the same parametrized for independent results given the same password, then the encryption system is not compromised by the disclosure of the password hash, under the "large enough" hypothesis in preamble, which implies in practice that the password hash is quite slow, and [passwords are imposed to users, or [users are motivated to not have their password guessed, and neither lazy nor stupid]].

(There could in theory be something intermediary between 1 and 3, where the password hash gives a little usable info about the key; but that's unlikely. The closest is that, in a nightmare scenario, the only difference between the password hash and the key is more iterations for the later, and somewhat re-hashing the password hash gives the cipher's key; but neither PBKDF2, nor anything I have studied, has such weakness).

In conclusion:

Try hard to not let the password hashes leak: password hashing should be a second line of defense.
Make the results of the password-to-key derivation function and password-to-password-hash function independent (in the sense that one can't be efficiently found from the other). One way that works for most purposely-slow key-or-password derivation functions is to use a different salt, or different prefixes to the same salt (empty being a valid prefix).
Especially if you must use password-based encryption, take the password-to-key derivation seriously: use a memory-hard construction such as Argon2 or scrypt, and parametrize generously.

Addition per comment:

  Are there techniques to use password based encryption but at the same time, have confidence in 128 bit security ?

The best we have combines

Sensitizing users to the choice of good passwords, perhaps starting with calling these "passphrase" instead. That simple and unobtrusive thing has gone miles in PGP.
Using Argon2 or other well-thought memory-hard iterated hash to transform password into key, before using it for standard encryption. Merely using a hash requiring sizable memory makes attack using GPUs, FPGAs and ASICs decimal orders of magnitude less attractive than they are to well-funded attackers targeting users of a plain iterated hash like PBKDF2. Password cracking is commonly assisted by GPUs, sometime by FPGAs. I have no hard evidence for ASICs, but technology and greedy mentality in cryptocurrencies are perfect fit.

See this for an exploratory idea: in addition to the above, with a lot of ifs, a memory-hard all-or-nothing transformation of plaintext to ciphertext could force the adversary to decipher the whole file (or a sizable part of the start) in order to test a password. This could be useful to a degree for files of large but still common size.

Regarding the memory-hard iterated hashes: there are iteration, memory, and parallelism parameters to choose.

When we double the iterations (e.g. increase the user-perceived delay from 4 to 8 seconds),

Attackers are hit by a double of energy cost, and of time at constant investment.
Legitimate users also are hit by a sizable increase in energy cost/battery drain, beyond the delay. Thus that adds next to 1 bit of cryptanalytic resistance, but is a pain.

When we double the memory (e.g. from 4 to 8 GiB), and that whole memory can be put to use within the delay, and a number of plausible assumptions hold, then

Attackers using specialized hardware are hit by a double of the time at constant RAM cost, and a RAM cost increase at constant time to a possibly lesser but still sizable degree.
Legitimate users gain some sizable fraction of a bit of key, quite painlessly until they hit the limits of available memory.

When we double the number of CPUs used, which is possible to small (but increasing) degree, this has a chance of decreasing the user delay to some degree, and shouldn't harm much more than making the machine less responsive for other tacks, and noisier/hotter. Thus that can allow raising the iteration count, see 1. Also, for small delay, that may allow to increase the amount of memory actually used, see 2.

I wish I could rationally tell how better it is to use Argon2d vs directly using (a very fast hash of) the password in AES-128. But can't. Using hypothesis so wild that I won't state them, I get anywhere from +20 to +50 bits. One thing is sure: that can't stretch anywhere near to true 128-bit-ness most passwords chosen by a large sample of computer users.

  Is it time to move on to ECIES ?

It does not solve that issue. Any good public-key encryption scheme solves the problem of confidentiality in key distribution, but not the problem of integrity in key distribution. And go figure how to use public-key to authenticate a human to a machine.


Is the one-time-pad a secure system according to modern definitions? Occasionally I hear people say that one-time pads are "useless" or even "broken".

  "modern cryptography knows more security definitions, under some of
  which the one-time pad is completely broken."
  -- How do we know a cryptographic primitive won't fail suddenly?

...

  One time pad: why is it useless in practice?

...

  "we don’t need (and shouldn’t want) to use one-time pads"

...

  "The one-time pad is not a semantically secure encryption
  algorithm."

...

  "One-time pads may be theoretically secure, but they are not secure in
  a practical sense."
  -- Bruce Schneier

What specifically are these "modern ... security definitions", and how exactly is the one-time pad completely broken?

Modern security has moved beyond looking just at passive attacks (in which the attacker is just a passive eavesdropper seeking to learn what was said); attackers are generally considered to be able and willing to pull off active attacks of various types (in which the attacker can modify or forge messages to achieve some goal). One-time pads are extremely vulnerable to modification; if an attacker knows that a message says "Pay Robert \$100,000", they can trivially change it to "Pay Joseph \$999,999". They share this property with all stream ciphers; if your ciphertext is the plaintext XOR a keystream, then an attacker who knows $P_1$ and $C_1$ can easily compute $C_2=C_1\oplus (P_1\oplus P_2)$, which decrypts to $P_2$. Working around that requires some way to verify message authenticity, which a one-time pad doesn't do (and doesn't try to do). This is provided by message authentication codes (MACs), or by a cryptosystem that combines authentication and encryption (like AES-GCM).

Also, many security properties literally do not apply to OTPs, because the properties are along the lines of "given the ability to encrypt multiple messages with the key, do X."

Uselessness is broader: even if you just need confidentiality, OTPs have serious issues for usability. That's because a OTP key has to be as long as the message and transmitted in secret; cryptography is most useful when you just need to transmit a little information secretly to encrypt a lot of stuff. An OTP is only as secure as the key exchange, so to be useful the keys have to be exchanged without relying on cryptography for security (else you're not getting perfect security). There are a few cases where they work well (like distributing in person to someone who's about to go on a mission and will need to send stuff back to you over an insecure channel), but they're rare.


ISAKMP 'master key' PFS (phase I) vs Ipsec session key PFS (Phase II) A question for the crypto-experts to help out a somewhat confused guy: why does PFS (perfect forward secrecy) also exist in phase II as well as in phase I?

Rationale:
 In phase I ISAKMP, the result of main mode is following keying material:

SKEYID_d = prf(SKEYID, g^xy | CKY-I | CKY-R | 0)

SKEYID_a = prf(SKEYID, SKEYID_d | g^xy | CKY-I | CKY-R | 1)

SKEYID_e = prf(SKEYID, SKEYID_a | g^xy | CKY-I | CKY-R | 2)

SKEYID_d is used in phase II to come up with a session key.
g^xy is the DH (Diffie-Hellman) shared secret.

So there is already PFS in phase I by design. Each time someone establishes a new IPsec VPN tunnel, a new DH shared secret g^xy will be used to compute SKEYID_d, right? Hence, the session key in phase II will also be unique. This is PFS right there?

So if we also do DH in phase II we have double PFS? What is the point?

So there is already PFS in phase I by design. Each time someone establishes a new IPsec VPN tunnel, a new DH shared secret g^xy will be used to compute SKEYID_d, right? Hence, the session key in phase II will also be unique. This is PFS right there?

No, you do not recompute a fresh SKEYID_d for every Quick Mode; instead, a value for SKEYID_d is assigned when the IKE Security Association is created (just like all the other SKEYID values), and is thereafter constant for the duration of the SA.

Hence, that wouldn't meet the definition of Perfect Forward Secrecy; the idea behind it is if the adversary captures the device (and learns everything it knows), he would not learn any previous keys (of course, he would learn any current keys).

In this case, the adversary would learn the value SKEYID_d; the IPsec keys are derived in IKEv1 from prf(SKEYID_d, [ g(qm)^xy | ] protocol | SPI | Ni_b | Nr_b).  If the attacker captures the device (and so learns the SKEYID_e value, and so is able to decrypt the IKE traffic), he learns the values of protocol, SPI, Ni_b and Nr_b (as they are all sent through the encrypted session).

So, if the PFS option is not used, the attacker can learn the IPsec keying material, and read all the traffic.  If the PFS option is (properly) used, then the attacker cannot learn g(qm)^xy, and so does not get the keying material.

I made these comments in the context of IKEv1; similar reasoning applies to IKEv2 (the current version of IKE)


Relationship between source and output entropy True Random Number Generator (TRNG) use external physical phenomena to generate true randomness. I have a TRNG which uses two sources (oscillators) and gives an output of 256 bits. The entropy of TRNG output is 256 bits. The entropy of bit string with N distinct possible combinations is given by log2(N) bits (reference is given below). TRNG claims to have entropy of 1 bit for each input source i.e. totally unpredictable. Is there any relationship between TRNG’s source entropy and output entropy ?

http://csrc.nist.gov/publications/drafts/800-90/draft-sp800-90b.pdf

Any help/reply is appreciated please.

Thanks & Regards,

Qualified no.  There is no relationship between source entropy and the output entropy from a TRNG other than you can't output more entropy than you put in.  The actual source entropy rate can vary vastly.  Clearly the TRNG output entropy has to be 100%, 1 bit /bit or however you measure it.  Otherwise it wouldn't be a TRNG with a statistically flat output.

I like to talk in percentages, with 100% being absolute true randomness.  A physical source can produce entropy at any rate from 0 - 100%.  I can't imagine a physical source that can naturally produce 100% though. I have built two generators that produce entropy at the rates of 85% and 1.9%.  An experimental third outputs at a very very approximate 0.1%.

It's all to do with what happens to the source entropy once you've digitised it.  I think of entropy extraction as a distillation process akin to whiskey production.  The distillation process is a euphemism for lossy compression of the source entropy.  This might be a (non) cryptographic hash, matrix multiplication or just some simple bit folding.  Most TRNG devices use custom extraction techniques anyway.

If you start with 85% mash, you only need to refine /compress the mash /entropy by 17% to get 100% pure stuff.  Similarly the compression /refinement needs to be 52 fold for the 1.9% mash.  So 52 fold compression would result in a 100% rate of entropy.  But then consider that you might continue compression /refinement, so in the end you've compressed the 1.9% source entropy 100 fold.  Or 200 fold.  You still get 100% output entropy and the numbers are exactly just as random.  This is why there is no particular relationship between the source entropy and the output of a TRNG.


What happens if a SHA-256 input is too long (longer than 512 bits)? What I understand is: When we parse a message into 512 bit message blocks. Then we extend the first message block to 64 entry array and start with the compression function.

What happens if the message is longer than 512 bits? As a result, we would receive several message blocks, but where are these fed into the function.

If the input message is longer than 512 bits, the input is chopped in “chunks” (read: pieces) with fitting length (512 bits) and those are successively fed to the hash compression function.

See, in layman’s terms, SHA-256 processes things like this:

init SHA-256
while there are input chunks,
update hash compression function with the next input chunk (pad to 512 bits if needed)
finalize SHA-256 and return the result (which is the hash output)

As mentioned in “2”, when SHA-256 reaches a chunk which is less than 512 bits, it is padded accordingly… so that all input chunks fed to the hash compression function are exactly 512 bits long. For details on the padding itself, see “How is input message for SHA-2 padded?” and “SHA256: Padding a 512 bits length message”.

A note aside: The maximum message size which can handled by SHA-256 is $2^{64}-1$ bits, which means SHA-256’s compression function can handle up to $\lceil(2^{64}+64)/512\rceil$ of 512-bit input  chunks. In the (unlikely) case when you try to feed more input than the maximum, the hash function should refuse output (read: fail with error).


Elliptic curves in Edwards form (or Edwards curve) and addition formulas In recent studies on elliptic curve cryptography, Edwards curves are remarkable examples on this field. Studies show that this kind of elliptic curves provide faster computation compared to Weierstrass form.

The following equation is called an Edward Curve
$$x^2 + y^2 = 1 + d\cdot x^2\cdot y^2$$
or $$x^2 + y^2 = c^2 \cdot (1+d\cdot x^2y^2)$$

If $(x_1, y_1)$ and $(x_2, y_2)$ are points on an Edwards curve, then new point calculated by addition formula would be still on the curve as illustrated below.

$$(x_1, y_1) + (x_2, y_2) = (x_3, y_3)$$
where:

$$\begin{align}
x_3 &= \frac{(x_1\cdot y_2+x_2\cdot y_1)}{(1+d\cdot x_1\cdot x_2\cdot y_1\cdot y_2)}\\
y_3 &=  \frac{(y_1\cdot y_2-x_1\cdot x_2)}{(1-d\cdot x_1\cdot x_2\cdot y_1\cdot y_2)}\\
\end{align}$$

Proofs of addition formulas for conventional Weierstrass form exist. However, I cannot find any proof for Edwards curve addition formulas. Where do they come from?

I think this is a good question, but not one with an easy answer. Let me give it a go anyway.

First of all, let's focus on the classic Weierstrass case. The points on an elliptic curve $E$ in this shape form a group. We can do this by the standard way (in most cases): draw a line between two points $P$ and $Q$, intersect at a unique third point, and invert across the $x$-axis. The resulting point $R$ is defined to be $P+Q$. Many standard texts indeed provide proofs that the points with this operation form a group.

Now, as you may have noticed, this way of defining the group depends very much on the way we represent the elliptic curve. That is, it assumes that we write $E$ as the set of solutions to $y^2=x^3+ax+b$. Can we also define the group law without making this assumption? The answer is yes.

How to do this, is quite complicated. Think of an elliptic curve $E$ as a very abstract object, not even assuming how to represent its points. It can be shown, that there exist some group attached to $E$, which is the degree-0 group of something called the Picard group. We denote it by $\operatorname{Pic}^0(E)$. Even more, it can be shown that there is a bijection between the points of $E$ and elements of $\operatorname{Pic}^0(E)$. Because $\operatorname{Pic}^0(E)$ is a group, so are the points on $E$.

So, we know that the points on $E$ form a group. How do we compute it? Well, it depends on how we represent points on $E$. If we choose to write points as $(x,y)$, where $y^2=x^3+ax+b$, then it is the classical way. If we choose to write points on $E$ as $(u,v)$ where $u^2+v^2=1+du^2v^2$, then it is done in the way you described.

TLDR How do we prove that your $x_3$ and $y_3$ are correct? As above, we need to prove that they correspond to a point on $E$ such that it corresponds exactly to the group law defined by $\operatorname{Pic}^0(E)$. For this specific case, your best bet is the original paper or the cryptographic application paper. In particular I would look at section 3 of the latter paper.


Does $i^n=j^n$ for $i, j \in GF(2^q)$ and $i \neq j$ for some $n<2^q-1$ Let $i, j \in GF(2^q)$ and $i \neq j$ and $i,j\neq0$.

Is that possible that $i^n=j^n$ for some $n$ such that $0 < n < 2^q-1$?

I am looking for a proof if the answer is no, or for a method to find $n$ if the answer is yes.

Actually, the answer is "such an $n$ exists iff neither $i, j$ are 0".

We have $x^{2^q-1} = 1$ for $x \ne 0$ (because multiplication in $GF(2^q)$ over the nonzero elements forms a group of order $2^q-1$), hence if $i, j \ne 0$, $n=2^q-1$ is one answer (if not necessarily the minimal one).

If we add the simple observation that if one of $i, j$ is 0, then $i^n = j^n$ cannot happen; this gives us the full answer for all possible values $i, j$.

If you want to extend the question to find the minimal $n$, then you can do this if you know the factorization of $2^q-1$.  That's because if $i^n = j^n$, then $n$ must be a divisor of $2^q-1$; hence you can just search through the divisors of $2^q-1$.

If $2^q−1$ is a Mersenne prime, then no such $0 < n < 2^q-1$ will exist, no matter what $i,j$ are. However, if it is composite, then such $i,j$ will exist (and, in fact, you can find such an $i,j$ pair for every nontrivial divisor $n$ of $2^q−1$). If $g$ is a generator, then two such values are $g^{a\cdot(2^q−1)/n}$, $g^{b\cdot(2^q−1)/n}$ for $0\le a,b<n$


Private Information Retrieval with no server computations Is there any way to perform Private Information Retrieval when no computations can be executed on the server-side?

I would like to perform the computations on the client, and without having to download the whole database.

Not when it comes to PIR. However, depending on your use case, have you considered using Oblivious RAM?
From Mayberry et al. (2013):

There are traditionally two ways to hide a user’s access pattern (given only a single server/cloud): Oblivious RAM (ORAM) and Private Information Retrieval (PIR). The traditional approach taken by ORAM is to arrange the data in such a way that the user never touches the same piece twice, without an intermediate “shuffle” which erases the correlation between block locations. [...]
Private Information Retrieval, in contrast with ORAM, hides the target of each individual query, independent of all previous queries. This can be accomplished by using a homomorphic encryption which the server uses to operate over the entire database, selecting out the block of data that the user has requested. The user generates encrypted requests and sends them to the server. Since PIR does not try to hide a sequence of accesses, but each access individually, the amortized cost is equal to the worst-case cost. Unfortunately, the requirement that the server computes over the entire database for each query is often impractical, especially for large databases.

So, for ORAM you generally have a single client, which holds some client storage. Of course it is possible to have multiple clients, but then they have to download/re-upload the client state before and after transferring blocks. One construction is Recursive Path ORAM, which for storing $N$ blocks has $O(\log N) \cdot \omega(1)$ blocks of client storage and $O(\log N)$ blocks of bandwidth, where we assume blocks are “moderately sized”, i.e. of size $\Omega(\log^2 N)$.


What are the differences between these AES ciphers? aes128-ctr
aes192-ctr
aes256-ctr
aes128-gcm@openssh.com
aes256-gcm@openssh.com

Mac Sierra recently deprecated blowfish, but I don't understand use-case differences of other ciphers. This is for testing a remote web project with X11Forwarding. I'm also curious about the last option,

chacha20-poly1305@openssh.com

CTR mode aims at confidentiality only; GCM additionally aims at integrity (catching attempts to forge or modify a message by one not holding the key, nor having some form of access to a device holding it).

The numbers 128, 192 and 256 are the key size in bits. 128 bits of key is secure enough for most purposes; 192 (or more) is enough for all purposes, except when there is a regulatory requirement for even more. AES192 (resp. AES256) is slower than AES128 by roughly 20% (resp. 40%).

Chacha20-Poly1305 is functionally comparable to AES128-GCM (giving confidentiality and integrity), but is easier to implement securely and efficiently, especially without AES support in hardware.


Block cipher encryption of decryption with the same key With block chipers can I assume that

Enc(k,Dec(k,m))=m

Meaning if I decrypt something with a key k and then encrypt the result with the same key k, do I get what I originally had? Using the same BC scheme of course.

I can't right? It's possible that it has some random parts, no?

If by $\operatorname{Enc}$ and $\operatorname{Dec}$ you mean the application of the block cipher primitive to a single block, then yes, it is assumed to be deterministic. (Since the size of input and output block is the same, and we want to be able to decrypt again, there is no way to be nondeterministic.)

(Note that in "normal" encryption/decryption usage, you'll have not the block cipher primitive, but a block cipher with a mode of operation, and together the encryption is usually are not determined by just the key, as it is also using an initialization vector.)

When you are thinking about block ciphers in compression functions for hashes, you are usually taking the block cipher primitive, so your determinism is given.

For collision resistance of a hash function, you don't need to show that there are no collisions (this is impossible, if the input size is larger than the output size), just that it is "hard" to calculate them. (Or if you want to show that a function is not resistant, show that you somehow can calculate a collision.)

Your idea of creating a collision is good – you just have to show on how it applies to the way a message is encoded and then passed to the compression function (i.e. the block cipher) to find two colliding messages. (This depends on your concrete candidate hash function.)

This is also the reason that we don't use a "pure" block cipher in real live compression functions, but add some feedback of either the "key" or the "plaintext" or both into the output.


Would SHA-256(SHA-256(x)) produce collisions? Was reviewing some Bitcoin public-key hash literature and the use of RIPEMD-160 and the SHA-256 as below:

 RIPEMD160(SHA256(ECDSA_publicKey))

The Proof-of-work on the other hand uses SHA256 two times (instead of RIPEMD-160).

There is some notes on why RIPEMD160 was chosen (here).

Considering the 256-bit output space of SHA256, what would happen (theoritically) if one were to use SHA256 on a SHA256 output? For example:

SHA256(SHA256(x))

Would this be a bijective mapping? or Surjective mapping?

Can such mapping be used, in any way, to break the SHA-256?

Since SHA-256 is supposed to be a one-to-one function, there is no way the SHA256(SHA256(x)) could be injective function (since the input space and output space are both 256-bits). But if it is not injective, then SHA-256 cannot be one-to-one function for longer message (>256-bit input). How is this contradiction being worked out in the algorithm?

First of all, note that, SHA-256 operates on a minimum of 512-bit messages. The message is always padded to be a multiple of 512-bit ( see padding below). For double SHA256(SHA256(m)), after the first hash, the result is padded to 512-bit.

padding: The SHA-256 message format |L|1|0..0|message size in 64 bits|. L is the original message bits to be hashed, it is followed by 1, and many zeros except the last 64-bit so that the padded message is multiple of 512-bit, minimally. The last 64-bit is the message size. The maximal message that can fit into one 512-bit hash block is 447-bit.

So, if $x = \operatorname{SHA256}(m) $ the it will be padded as

| x 256-bit| 1 | 0000's 191-bit | 64-bit size of x) |

for the next SHA-256 calculation.

Now, the input-out space will be exactly 256-bit. In this case, we don't know it is one-to-one or not. The space is huge for calculations. If it is one-to-one then it will be a permutation, too. There are $2^{256}!$ permutations and there are $(2^{256})^{(2^{256})}$ functions. It will be amazing if it is a permutation. For simplicity, take 5-bit as an example, there are 32! permutations ~112-bit and there are $32^{32}$ functions ~161-bit. If we consider that the restricted SHA-256 is a randomly selected function then the probability of being permutation is around $\frac{1}{2^{50}}$. See a glimpse from WolframAlpha in a logarithmic scale.

  Since SHA-256 is supposed to be a one-to-one function

SHA-256 is not a one-to-one function. It is a one-way function i.e. you cannot revert it. Since the minimum input size 512-bit and the output size is always 256-bit, there is no way to be one-to-one.

  Would this be a bijective mapping? or Surjective mapping?

It would be surjective mapping.

  But if it is not injective, then SHA-256 cannot be one-to-one function for longer message (>256-bit input).

It is not one-to-one.

  Would SHA-256(SHA-256(x)) produce collisions?

If we consider that you are talking about hashing bitcoin public keys, it has 33 bytes compressed and 65 bytes uncompressed public keys.

If the key is uncompressed, it has 520-bit therefore by the pigeonhole principle there will be collisions.

If the key is compressed, it has 264-bit again therefore by the pigeonhole principle there will be collisions, the output is 256-bit.

Note that SHA-256(SHA-256(x)) will be still collision-resistant.

  Can such mapping be used, in any way, to break the SHA-256?

See this question Weaknesses” in SHA-256d? for the nice answer of FGrieu.