How is CipherCloud doing homomorphic encryption? Much of the literature and latest papers suggest that homomorphic encryption is still not practical yet.

How is CipherCloud able to achieve this? Does anyone have an idea? Their website does not provide much information about how their system works.

I could not find any evidence pointing towards homomorphic encryption. What I could find were different combinations of deterministic and format-preserving encryption. There is probably also a variant that preserves order, but I couldn't find any material depicting it.

This post is based on material published on the CipherCloud website at CipherCloud Cloud Security Learning Center - Featured Content. CipherCloud notes that the actual product has additional encryption features that offer stronger security and don't suffer from the listed weaknesses (see CipherCloud response section).

Material 1: A screenshot from their whitepaper Best Practices in Securing Your
Customer Data in Salesforce,
Force.com, and Chatter on page 10:

[image removed due to DMCA request]

Description: This screenshot depicts contact details (name, address, phone, etc.) in three columns.

The first column shows the policy which determines how different fields should be encrypted. For most fields this is "AES Crypto Encryption", for some fields such as phone numbers it's a specialized form of encryption, such as "Telephone Number Encryption".
The second column shows the plaintext ("As seen by authorized users")
The third column the ciphertext ("As seen by Unauthorized Users")

Analysis: When a field consists of several parts(say firstname and lastname) they split it into those parts and encrypt them individually.

Some important fields, such as "annual revenue" aren't encrypted at all, probably because they need to do use it in calculations.

The encryption for names and addresses preserved the length of the individual words and the position of spaces. There are special tags between words that seem to mark encrypted parts and separate tokens.

Preserving length strongly hints at deterministic encryption, as does support for search. In theory, it'd be possible to use difference nonces for different records, but I consider that unlikely since it'd be hard to keep a search index in such a case.

Material 2: Feature list from the same whitepaper (page 11):

  Encryption Options: AES-256, Function Preserving Encryption,
  Length Restricting Encryption, etc. Ability
  to select on a field-by-field basis

Analysis: Same length encryption was already observed in Material 1. Presumably preserved functions search and ordering. Probably it's possible to choose which functions to preserve on a per-field basis. Material 3 will demonstrate a form of encryption that allows search, but does not appear to preserve ordering.

Material 3: CipherCloud Connect AnyApp Demo Video around 2:30 and 3:00:

[screenshot omitted due to DMCA request]

Description: This shows a typical message board that is part of the yammer web-application. There are two open windows showing the same thread. One shows the encrypted messages (as the yammer.com server sees it), the other the plaintext form as it is seen when accessed through CipherCloud. The message bodies are encrypted, the usernames and post times are not. The encrypted messages are a mix of Asian and ASCII characters.

Analysis:

There is a clear correspondence between plaintext words and ciphertext token. Each token starts with zqx1, ends with 0j1xqz and corresponds to one word. Punctuation marks are not encrypted at all.

Words that occur multiple times in the plaintext (for example meet, to, want) appear as identical tokens in the ciphertext.

The words new and will are even more interesting. They occur both in lowercase and uppercase form. The encrypted form of New might look like zqx1賓翡祀徠鈞祁記勤机琦芸稶70j1xqz1 and the encrypted form of new like zqx1賓翡祀徠鈞祁記勤机[linebreak]20j1xqz2.

So I assume the first part of the token encodes the word in a case insensitive form and the second part supplies the casing information. Sid made the same observation in his post. This form of encryption allows the case insensitive search they demoed in the video, where a search for apac turned up a message containing APAC since the beginning of the word is the same, regardless of case. This certainly looks like a 1:1 mapping between lower case words and the first part of the token.

The first part of the token seems to have a constant size of 9 Asian Characters. Given a large number of such characters, that would be enough to encode 128 bits or one AES block. So one possible implementation would use AES in ECB or CBC mode with constant IV encrypting a single block. But this paragraph is pure speculation that can't be proven from the limited observations we made.

An inherent weakness in such a scheme is that it doesn't offer semantic security.  If the same word gets encrypted in different places, an attacker can see that the same word was used in both places. If he can figure out one of them, he automatically knew the other too.

The attacker could also employ some kind of word-level frequency analysis on tokens. Once part of the ciphertext has been recovered, the known words serve as a context for further guesses. Once a certain knowledge threshold has been exceeded this should allow recovery of most words. So it's essentially to prevent an attacker from learning any (ciphertext, plaintext) pairs, even for harmless messages. Quoting public material or storing drafts which later will be published is also quite dangerous.

A similar non-deterministic scheme

The above scheme is essentially a word-level substitution cipher. Classical substitution ciphers usually use a single letter (or a small fixed amount of letters) as a substitution unit. Modern block ciphers such as AES trivially allow using whole words as a substitution unit which was a bit difficult to do without a computer.

Those early substitution ciphers had similar weaknesses to the above scheme (1:1 mapping between letters, deterministic encryption, and frequency analysis). Of course with short/letter units these weaknesses where much more pronounced than with long/word units.

One technique used to reduce the impact of these weaknesses is having multiple possible substitutions for each plaintext unit and randomly choosing one during encryption. This technique is called Homophonic substitution. This technique can obviously be applied to word-level substitution ciphers as well.

When a word has n possible ciphertexts, one could still do searches by triggering n separate searches over the encrypted data and merging the results. This would turn above 1:1 mapping into a 1:n mapping, make the encryption non-deterministic and, depending on the chosen probability distribution, frequency analysis might be less effective as well. Of course, such a combined search would leak some information to the server about which ciphertext units might correspond to the same plaintext unit.

There is no evidence that CipherCloud uses a homophonic word substitution cipher. I only mentioned this scheme because it's the simplest change to the above scheme that doesn't contradict the claims in their DMCA notice. Ciphercloud claims not to suffer from the above weaknesses, thanks to "patent pending mechanisms". I certainly hope that their mechanisms are better than simply switching to a homophonic word substitution cipher.

CipherCloud's claims in their DMCA notice:

As a counterpoint to this analysis here are some claims made in their DMCA notice:

  Such false, misleading and defaming statements include the following sample:

  (2) "If the same string gets encrypted in different places, an attacker can see that the same string was used in both places." [statement from an old version of this post]
      * Again, CipherCloud's product is NOT deterministic.

  (4) "As CodesInChaos suggested in an earlier answer, this makes the solution extremely vulnerable to frequency-analysis attacks." [from AdrenaLion's post]
      * The referenced scheme does NOT represent CipherCloud functionality. In fact, CipherCloud has patent-pending mechanisms to defeat frequency-analysis attacks.

  (7) "Basically they end up with a 1:1 mapping of lower case words." [Sid's post, referring to the message board discussed in this post]
      * The statement is patently false. Sid implies that what was perceived from a public demo is CiperCloud's product offering. [emphasis mine] CipherCloud does not incorporate 1:1 mapping.

(10 sample statements were included in the DMCA notice, I picked those most relevant to this post. I inserted notes linking quoted statements to their original posts)

Conclusion

The observed encryption has significant weaknesses, most of them inherent to a scheme that wants to encrypt data while enabling the original application to perform operations such as search and sorting on the encrypted data without changing that application. There might be some advanced techniques (homomorphic encryption and the likes) that avoid these weaknesses, but at least the software demoed in the video does not use them.

The only way I see to reconcile the statements in their DMCA notice with the observed encryption properties is that the actual CipherCloud product is significantly different (and better) than what is shown in their promotional material.

If they don't want to be judged based on the information they published about their product, perhaps they should update their material to match their actual product more closely.

CipherCloud response

CipherCloud post a response on their blog: Responding to the Myths about CipherCloud’s Encryption Technology

Pretty little concrete information, but here some relevant parts:

  I wanted to provide some clarity to the question of whether CipherCloud uses homomorphic encryption.  The answer is NO.  Homomorphic encryption is far from ready for practical usage due to performance and lack of capabilities.

  The cited CipherCloud product demo in the board threads was focused on highlighting our reverse-proxy concept for cloud information protection to organizations using cloud applications. Some of the fundamental security features made available  (e.g. full-field encryption, randomization through IVs, etc.) were disabled because we were not comfortable sharing such IP on the internet while our patents are still pending.

1 The actual Asian characters were different from the one in my post, but the general form was the same.
2 The linebreak is an artifact of the browser displaying the text. It might have hidden some characters.


Is it possible to find what is the random generated key if I know the plaintext and ciphertext? Is it possible to find what is the key with only plaintext and ciphertext?

For example,

My plaintext is: hi

My ciphertext is: 0x1db5

If you don't specify the stream cipher in question, then no.

If you do specify the stream cipher in question, and it meets some of the most modest security goals of a stream cipher, then no.


Performance of Counter mode (CTR) with Ciphertext Errors In the "Introduction to Cryptography: With Coding Theory" by Trappe and Washington, in the chapter about Counter mode (CTR) the authors say that:

  "As a result, its performance is identical to OFB's when errors
  are introduced in the ciphertext."

What does this mean ? The authors don't explain it

What it means is that neither CTR nor OFB detects errors in a message, and that an adversary can flip arbitrary bits of their choice in the plaintext very easily—by flipping the corresponding bits of ciphertext.  This is because both CTR and OFB essentially work by using the block cipher as a stream cipher to pseudorandomly generate a one-time pad to xor with the plaintext.

This implies that an adversary can easily change one message like ‘Attack at dawn!’ to another message like ‘Attack at dusk!’ and the recipient of the message will be none the wiser.  Worse, an adversary can change a message like ‘Put the secret message in locker 42!’ to ‘Put the secret message in locker 41!’, and then by acting on the message your confidentiality goes out the window.  This is not merely theoretical; this actually happened in a major real-world protocol, OpenPGP, in EFAIL, because OpenPGP was badly designed.

To avoid this, you should generally use an authenticated cipher like AES-GCM or NaCl crypto_secretbox_xsalsa20poly1305.  An authenticated cipher detect any errors, whether random errors or malicious forgery attempts, with high probability.

You should also forget that ‘block cipher modes of operation’ exist at all—just focus on the complete construction AES-GCM.  The fact that there's a block cipher somewhere in there is not important to anyone except a cryptographer designing a system.  What matters is the security contract which tells you what your obligations are for using AES-GCM and what security you get in exchange.


Does the multiplicative property apply to modern, non-text book RSA? I'm aware of the multiplicative property of the textbook RSA and how it can be used to get a signature from a CA without having the CA directly signing it.

My question is - can this apply to the real world in modern implementations of RSA?

More specifically - assume I have this CA that will sign every CSR (Certificate Signature Request) I give it except a specific one, a "forbidden" one.

Theoretically, I would like to have this CA sign 2 (or more) "valid" CSRs and "multiply" their signatures to generate the desired "forbidden" signature (that one CSR the CA refused to sign)

Could this work?

can this apply to the real world in modern implementations of RSA?

No!

RSA is a trapdoor function and the RSA public encryption/decryption and RSA signatures are derived from them. Contrary to some people, RSA decryption is not a signature.

RSA must never be used without proper padding. It is very dangerous and example attacks can be seen from the paper Twenty Years of Attacks on the RSA Cryptosystem by Dan Boneh.

Apart from the multiplicative property, some of the attacks are;

Common Modulus attack where a group shares the same modulus in which any other user can find the others private key.
Blinding is signature forging where the forger asks a blinded, suspicious, message to sign and then convert this into a valid signature.
Low private exponent ( Wiener's attack) where the private exponent is chosen small to reduce the signature time. The attack can recover the d
Hastad's Broadcast Attack where the sender sends the same message to may. The attack recovers the message.
Bleichenbacher's Attack on PKCS 1 uses the invalid ciphertext error returned from the target and the attacker turns the target into a decryption oracle.

For encryption use

Optimal asymmetric encryption padding (OAEP), or
PKCS#1 v1.5 padding

for security comparison of these two encryption padding see this answer from Cryptograpgy.SE.
For signatures use Probabilistic signature scheme (PSS)

This question What is RSA OAEP & RSA PSS in simple terms gives a simple explanation for both.


RSA: Most significant key bit always 1? Is it possible to say that the most significant bit of an RSA private exponent is always 1? Wouldn't that weaken the key strength by exactly that one bit?

I refer to the paper "Timing Attack: What can be achieved by a powerful adversary?", p. 2, footnote 2.

No, in the end the private exponent $d$ is just a number within $0..N$ where $N$ is the modulus. It depends on $N$ what the chance is that the first bit is one, but in more likely to be valued $0$ than $1$ (given that it is well distributed, you would expect it to be $0$ around $\frac23$ of the time). If you generate enough private keys you'll even see private exponents that start with a few leading bytes that are completely zero'ed out (!). That's not a problem cryptographically speaking, it just shows that the entire key space is utilized.

So the private exponent $d$ doesn't always start with a $1$ when you consider the most significant bit of the modulus. The fact that the modulus is strictly less than $2^{keylength}$ does matter ever so slightly though. But as RSA requires exponential sized keys to achieve a certain security level, that should not worry you overly much (1 partial bit out of 1024 for the absolute minimum key size is completely negligible). Even if the private exponent would always have a 1 at the most significant position then the same logic applies; it would not have any significant impact on security.

I'm assuming a calculation with a preset/precalculated RSA public exponent, which is most often used in practice. If PKCS#1 conformant calculations are used then the most significant bit of $d$ is always $0$.

As I'm not that good in statistics, my computer has calculated that the first bit is probably 0 about 69 percent of the time and the first byte is zero 0.54 percent of the time, slightly higher than you would probably expect. And yes, I did generate 21171 keys starting with at least two zero bytes.


Verilog simulation & synthesis of Diffie-Hellman key exchange Is there any freely available verilog implementaion of Diffie-Hellman key exchange?

I couldn't find anything using google. So, assuming its not there I started implementing on my own.
The code is hosted at https://github.com/nulpoet/verilog_diffiehellman.
Behavioral simulation in xilinx works.
However it cannot synthesize the remainder(%) operator.

So, I does anybody know how to design a module for remainder operation in verilog that computes the remainder in a single clock cycle?
Any links to literature discussing the algorithm would suffice.

Solution to any of the above two question would solve my problem.
Thanks in advance!

Look on opencores within the vhdl section.

There are some older dos-era vhdl programs on simtel that have parsed-out statements so it might be more trouble than it is worth, but at least you could look under the hood of each function, grab what you need, run a lint checker etc, then perform verification.


Frequency tables for HTML page source Are there online resources with an ASCII character frequency table for HTML?

There's tons of them for english, but I can't seem to find one for page source. I know that this is something that's likely to vary from site to site, but surely there's rule-of-thumb good-enough-usually tables where < is ranked higher than z?


Perfect Forward Secrecy in TLS I read that TLS does PFS using Diffie Hellman. However, DH can be used even without certificates - so how is DHE-RSA better than plain DHE?

Is DHE a insecure algorithm, that DHE-RSA is needed?

No, DHE is secure and allows to share a common secret between two parties over an insecure channel. But you cannot know, if the one you share the secret with is the one you want (DHE is vulnerable to man in the middle attacks). So DHE-RSA uses DHE to share a common secret and signs the communication with RSA to make sure, that both persons communicate with the right other person.

So in short: DHE does not provide authenticity. DHE-RSA does.


Difference between RSA-617 and RSA-2048 according to wikipedia:

RSA-617 has 617 decimal digits (2,048 bits).
RSA-2048 has 617 decimal digits (2,048 bits).

What is the main difference between them?

They are both the same size, however they were created at different times during the factoring challenge, which is why one uses the bit size and the other uses the decimal size. They are created from different primes and are not directly related to eachother other than the fact they are both from the chllenge.

The first series of numbers in the challenge used the decimal size, of which 617 was the largest. Later they switched to the bit size, of which 2048 was the largest, and 576 was the smallest.

The decimal size numbers were last used in the challenge in 1997, and in 2001 the new set of challenge numbers with bit sizes were released.


Are there any papers explaining how to port textbook RSA to realworld RSA? Are there any papers, books, or link where it explains how the plain vanilla "textbook RSA" is actually implemented in practice with all the padding and stuff?

Basically, I would like to know the intricacies of implementing an algorithm into production level code…

Vanilla textbook RSA does not include "padding and stuff", the term "textbook RSA" generally refers to simply encoding a plaintext message as an integer and raising it to an exponent. Implementing this is pretty easy, just follow the steps outlined on Wikipedia. You can easily translate those steps into some given programming language.

Based on the rest of your statement, it sounds like you want to implement a real-world encryption/signing scheme using RSA, but not some higher protocol that uses it. If so, I would suggest looking at PKCS #1 v2. It's an authoritative specification for several such RSA padding schemes. (RSA-OAEP is probably the most recommended padding scheme for encryption if that's what you want.)


CSIDH: Why do we need ideals in the form of $\langle \ell, \pi \pm 1 \rangle$ in order to apply Vélu's formulas when computing the action? I am trying to understand the action of the CSIDH protocol.

Let $E_0:y^2=x^3+ax^2+bx$ be a Montgomery elliptic curve over $\mathbb{F}_p$ for some prime $p$. If we take $\mathcal{O}$ as $End_{\mathbb{F}_p}(E_0)$, then $Cl(\mathcal{O})$ acts on $\mathcal{E}\ell\ell(\mathcal{O})$ as follows:

Let $I\in Cl(\mathcal{O})$ an ideal. We define $H_I=\lbrace P\in E_0 \vert \alpha(P)=\mathcal{O} \text{ for all $\alpha \in I$} \rbrace$. The action is defined as below:

$I*E_0=E'$, where $E'$ is the unique curve such that there exists a unique separable isogeny
$$\phi:E_0\longrightarrow E'$$
With $\ker(\phi)=H_I$. In other words, the kernel of $\phi$ is the intersection of all $\ker(\alpha)$ where $\alpha \in I$.

In order to compute the $\phi$ and $E'$, papers on CSIDH make use of Velu's formulas. So far, I have found the following theorem which applies to Montgomery curves:

Let $K$ be a field with char($K$)$\neq$ $2$. Let $a\in K$ such that $a^2\neq 4$ and consider the Montgomery curve $E/K: y^2=x^3+ax^2+x$. Let $G\subset E(\bar{K})$ be a finit subgroup with $(0,0)\not \in G$ and let $\phi$ be a separable isogeny such that $\ker(\phi)=G$. Then, there is a curve $E'/K:y^2=x^3+Ax^2+x$ such that, up to composition with isomorphisms,
\begin{align*}
\phi: E &\longrightarrow E' \\
(x,y) &\mapsto (f(x),c_0yf'(x))
\end{align*}

where
$$f(x)=x{ \prod_{T\in G\setminus \lbrace \mathcal{O}_E \rbrace}^{} \frac{xx_T-1}{x-x_T}}$$
Furthermore, if we let
$$\pi=\prod_{T\in G\setminus \lbrace \mathcal{O}_E \rbrace}^{} x_T, \quad \quad \sigma=\sum_{T\in G\setminus \lbrace \mathcal{O}_E \rbrace}^{} \left( x_T-\frac{1}{x_T} \right)$$

Then, we have $A=\pi(a-3\sigma)$ and $c_o^2=\pi$.

So far so good, we have a way of computing isogenies between Montgomery elliptic curves. What I do not understand is the following. In several papers and slides, they explain that we have to take ideals $I\in \mathcal{O}$ with the form  $\langle \ell, \pi \pm 1 \rangle$, where $\ell$ is a prime. Analizing said ideals, we see the following:
$$H_I=\lbrace P \in E/\mathbb{F}_p \text{ } \vert \text{ } [\ell](P)=\mathcal{O},\pi (P)=P\rbrace$$

Since $\pi(P)=P$, it means that $P\in \mathbb{F}_p$. So it turns out that $H_I$ is just the $\ell$-torsion points defined over $\mathbb{F}_p$. The main claim is that we have to take $I$ in such a way because in doing so, we have a Vélu-friendly computation. This is what I fail to see. Why having rational points makes the Vélu computation easier?

In the theorem stated above, the hypothesis requires us that $G\subset E(\bar{K})$. But taking our ideal as $I=\langle[\ell]\rangle$ instead of $I=\langle [\ell], \pi \pm 1 \rangle$ also gives us a $H_I\subset E(\bar{K})$, which would be $G$ in the theorem notation, and so the theorem holds. Why is it then that having $H_I$ composed of rational points $P\in E(\mathbb{F}_p)$ makes the computation Vélu-friendly?

You are right that Vélu's formulas also work for any extension field, but then they require arithmetic in that field.
Doing computations in $\mathbb F_p$ is simply much more efficient than in extension fields.

Generally, for a "random" ideal of prime norm $\ell$, you can only expect the corresponding points to be defined over $\mathbb F_{p^k}$ for some $k\in\mathcal O(\ell)$, hence if CSIDH didn't have those rational points, one would have to compute in extension fields of degrees of a few hundred.

(In fact, the earlier variants¹ of CSIDH were, among other techniques, using subgroups that are not necessarily rational, because it seems hard to find an ordinary curve with many "good" subgroups. The core observation in CSIDH is that switching to supersingular curves makes this trivial, simply by picking the prime $p$ of a special form!)

¹ Couveignes, Rostovtsev–Stolbunov, De Feo–Kieffer–Smith


What is straight line black box reduction? I understand the notion of black box reduction. But what is straight line black box reduction?

A straight-line black-box reduction is one that interacts with the adversary in a black-box manner (read: is given oracle access to the adversary) and "cannot rewind" the adversary.

So, assuming (as an example) that the protocol has the corrupted party receiving $5$ messages, then the straight-line black-box reduction can/will give the adversary the messages $m_1,m_2,m_3,m_4,m_5$. In that order; and in that order only.

Simpler said: a straight-line black-box reduction interacts with the adversary the same way it interacts with a regular party.


With sufficient randomness, is XOR an acceptable mechanism for encrypting? I have heard criticism of various cryptosystems saying that "at their heart, they were just XOR."

Is this just ignorance, or is there something inherently wrong with XOR based ciphers?

It's important to make the distinction between ciphers which use XOR
internally as a component operation (which is nearly all of them),
and 'ciphers' which just XOR the plaintext with a secret. If the key
is the same length as the plaintext, then it's a one time pad, so in
some sense, yes, with "sufficient randomness" you can safely encrypt with XOR.
The problem with this is that it only applies if the key is
exactly as long as the plaintext, and is perfectly uniform random.
If it's not, then you've basically created a Vigenere
cipher, which
can be trivially broken. It's interesting, and unfortunate, how
the 'provable security' of the OTP fools people into thinking
they can just take a little shortcut or two and still get
something safe.

Typically, people who implement simple XOR ciphers compound their
mistake by using hard-coded keys, in which case a single known
plaintext/ciphertext pair is sufficient to decrypt anything.
That's probably mostly because if you were some kind of prebuild
crypto toolkit, it would be easier to just use AES along with your
RSA key management, etc, versus using a decent key distribution
scheme and then using XOR with your safely shared keys.


XOR cipher with fixed key and known relation among plaintexts I have three messages, each known to be XOR-encoded, with the same key used for each message of this XOR cipher.

Encoded message 1: $e_1\,=\,00100111010$
Encoded message 2: $e_2\,=\,01001110110$
Encoded message 3: $e_3\,=\,11010110101$

I also have an extra information: I know that the decoded contents of $e_1\oplus e_2$ is equal to the decoded contents of $e_3$.
How would one go about solving this problem, in order to get the key and decode the contents of the message?

I'm somewhat new at this, so there might be a better way to solve this, but this is how I solved it. If I understand right, the extra parameter given is written as:
$$\mathtt{}({e}_{1} \oplus k) \oplus ({e}_{2} \oplus k) = e_{3} \oplus k$$
(that is, the decoded contents of e1 xor'd with the decoded contents of e2 is equal to the decoded contents of e3)
The brackets only provide readability, and so the equation is the same without them. This means that we have $$\mathtt{}{e}_{1} \oplus k \oplus {e}_{2} \oplus k = e_{3} \oplus k$$
There are 2 "$\mathtt{}\oplus k$"'s on the left hand side here, so they can be removed to get the following:
$$\mathtt{}{e}_{1}\oplus {e}_{2} = e_{3} \oplus k$$
The right hand side can also be replaced with $\mathtt{}m_{3}$ to denote decrypted $\mathtt{}e_{3}$:
$$\mathtt{}{e}_{1}\oplus {e}_{2} = m_{3}$$
$\mathtt{}e_{1}$ and $\mathtt{}e_{2}$ are given, and by xoring them we can get:
$$\mathtt{}{m}_{3} = 1101001100$$
and we also know that:
$$\mathtt{}{m}_{3} = {e}_{3} \oplus {k}$$
Now we have both $\mathtt{}m_{3}$ and $\mathtt{}e_{3}$, and we can now solve for $\mathtt{}k$:

xor both sides by $\mathtt{}e_{3}$
$$\mathtt{}{m}_{3} \oplus {e}_{3} = {e}_{3} \oplus {e}_{3} \oplus {k}$$
remove $\mathtt{}e_{3} \oplus e_{3}$ from right hand side:
$$\mathtt{}{m}_{3} \oplus {e}_{3} = {k}$$
substitute in $\mathtt{}m_{3}$ and $\mathtt{}e_{3}$'s values:
$$\mathtt{}1101001100 \oplus 11010110101 = {k}$$
giving...:
$$\mathtt{}k = 10111111001$$

You can now decode all 3 encrypted messages:
$$\mathtt{}m_{1} = 10011000011$$
$$\mathtt{}m_{2} = 11110001111$$
$$\mathtt{}m_{3} = 01101001100$$
Hope that helps.


Elliptic curve cryptography attack vector I would expect a complicated answer for what seems like a simple question about Elliptic curve cryptography. I've read several entries here such as "Elliptic curve cryptography related key attacks" and afterwards I am still left wondering what the primary attack vector would be and also what can be done by an implementer to shore-up a weakness.

Is hashing of keys the main weakness or is it in the PRNG? At the end of the day I want to do what I can to prevent "anyone" from reading what Alice or Bob have communicated.

To summarize, what is the weak point in the algorithm and what can be done to minimize the effectiveness of an attack?

If you use elliptic curve cryptography properly, with a suitable choice of parameters, there is no known weak point.  (More precisely: The cryptography is unlikely to be the weakest link in your system.)

The trick is to use the cryptography properly.  That's why people generally recommend that you use some existing well-vetted solution, like TLS 1.2 or similar, rather than implementing your own.

If you want to know what is the primary, most likely risk that will cause the security of your communications to be compromised, it is probably things like (1) insecure endpoints, (2) human error/mistakes, (3) compromise of one of the people/entities who are party to the communication, (4) traffic analysis, etc.  In other words: system-level issues, not the elliptic curve crypto algorithms.  One could write an entire book on what could be done about that, and people have; see the information security literature.


Entropy after shuffling result of /dev/urandom first of all: Im pretty paranoid.
I am creating a seed on my linux server using the following command:

cat /dev/urandom |tr -dc A-Z9|head -c${1:-81}

Since I don´t have any local linux systems, I connect to my external server via SSH.

Now, I got this (probally unjustified) fear, that my seed, although being transferred via SSH, might be compromised. So I considered shuffling the seed on my local computer. For example taking parts of it (5-10 digits) and pasting them at a differnt location.

I guess that this might decrease the security/entropy of the seed. My questions is: how much? Should I either trust that my seed has been transmitted safely or shuffle it around a bit?

Of course I know the easiest solution would be using a local Linux system to generate it. But let´s talk about the other solutions.

I can understand paranoia.  They're probably recording everything I type.

There's good paranoia of the sort that gets the adrenaline pumping, sharpens the reflexes and gives you the energy to turn that sabre tooth tiger into dinner and moccasins.  Unfortunately, I think that you might be suffering from the bad type of paranoia.  This has led you to think irrationally (sorry).

Let's assume that your urandom seed is generated magically and is cryptographicly safe, and uniformly distributed.  It's about as good as its going to get without a true random number generator.  You then transmit it and the bad people read it.  Is this your compromised? So security = 0.

You then start manipulating it by slice and dice.  This is a speculative calculation, but I would suggest that the only security you add is the decision where to chop the seed.  So if you chopped and swapped a 32 byte (256 bit) seed  at some random place, you add log2(32) bits of entropy.  That's 5 bits. Perhaps you add another 5 if you chop and swap again.  Ultimately though, you can only generate an absolute maximum of 32! byte permutations /combinations.  It will be less in reality as some bytes might be equal (and I can't do the maths). That's a maximum of 118 bits, which is less than  half of your original entropy. And you have to realise that a human is very poor at thinking of random things in his head.  The 5 bits might actually only be 4 or even less. (Have scientific studies been done of human generated entropy?)

You can see where bad paranoia can take you?  Taking of other solutions, urandom isn't magic.  It's a CSPRNG (SHA1 or ChaCha) which you either have on your client computer, or can implement using one of the many kosher algorithms. You might even have access to a Windows version of /dev/urandom if that's your bent.

In summary, it all falls apart when you believe THEY read your SSH traffic.


How does changing input size affect The Goldreich-Goldwasser-Micali Construction? If we want to construct a PRF that is length preserving, it is easy to show with hybrid proof that the resulting construction is a PRF.

But what happens when we have longer input. Supose that the key and output length are $n$ and the input size is $2n$.

I have been imagining what could happen to the binary tree. I feel like since input is double the size it will go double the depth. But in this case I cant tell if the resulting construction is a PRF.

Any hint would be helpful!

The input size and the key size need not have any specific relation. The security analysis of GGM goes through as long as the key size is equal to the seed size of a secure length-doubling pseudorandom generator, independently of the input size, which can be an arbitrary polynomial in the security parameter.

Since the depth of the GGM tree is exactly the input length, if you double the input length, you indeed double the depth of the tree. The security analysis remains identical: the only difference is the number of hybrids in the proof, but changing the number of hybrids by any polynomial amount does not harm security, since the adversary has negligible advantage in distinguishing any two hybrids.


Trial division + Miller-Rabin complexity I was reading a paper that shows time complexity of Trial division + Miller-rabin test for creating prime number.

T = N(T_rnd + T_td + T_mr)

T_rnd denotes time for making rnd number, T_td denotes time for trial division, and T_mr denotes time for Miller-rabin test.

N denotes the number of r(n-bit random number) that algorithm make until r is a prime number. Which is nln2/2.

I can't calculate how nln2/2 comes out.

Anyone can help me to understand this?

and sry for my bad English.

Well, the probability that a random number circa $N$ happens to be prime is approximately $1 / \log_e N$ (for $e=2.718281828...$), this is also known as $1 / \ln N$.

Now, if $n$ is the number of bits of the number we're searching for, that is, we are generating random numbers circa $2^n$, then this probability is approximately $1 / \ln 2^n = 1 / (n \ln 2)$.  Hence, if we try random $n$ bit numbers, we would expect to need to try about the inverse of this number, namely $n \ln 2$, before we stumble onto a prime.  Now, obviously, we might get lucky early, or we might happen to need to do several times this number before we find a prime - this is just an average.

Now, one thing that you don't mention that they do is, when they select a random number, they set the lsbit.  This means that we'll never select an even number (which are hardly ever prime), effectively doubling the probability that a guess happens to give us a prime.  This doubling of the probability halves the number of expected trials, hence giving us an expected $n \ln 2 / 2$ trials.

Now, one thing about the equation you listed; it includes the term $N T_{mr}$.  This may be accurate if, independent of whether the trial division finds a factor or not, you perform the Miller-Rabin test anyways.  However, it is more likely that, if the trial division shows that the number is composite, you don't perform the Miller-Rabin test, but instead try again with another random number.  This implies that you perform fewer Miller-Rabin tests than the number of random numbers you picked (and how much fewer would depend on how thorough you are with your trial division; checking the factors 3, 5, 7 will be less effective (but cheaper) than checking all potential prime factors less than, say, a million).


NIZK proof for cipher randomisation Is it possible to contract NIZK proof that a cipher was randomised?

Suppose Alice creates a cipher $c = \text{Enc}(m,r)$ and ZK proof that $c$ was formed correctly (for example, $\text{Enc}$ could be the lifted ElGamal encryption function). Bob wants to randomise $c$ and construct $c' = c\cdot \text{Enc}(0,r')$. How can Bob prove that $c'$ was indeed computed correctly?

Thank you!

There is a very simple way using proofs of discrete logarithms equality and ElGamal encryption. Let me first recall the following sigma proof of equality of to discret logarithms:

Let $G$ be a prime order group, and let $(a,b,c,d)\in G^4$ be such that there exists $x$ such that $a^x=c$ and $b^x=d$. Let a prover that knows $x$ and that want to prove to a verifier that $\log_a(c) = \log_b(d)$

The prover chooses $r$ and computes $A=a^r$ and $B=b^r$, then he sends $(A,B)$ to the verifier.
The verifier chooses a random $e$ and sends it to the prover. In order to turn it into a non-interactive proof, $e$ can be generated from the hash $H(a||b||c||d||A||B)$ in the random oracle model.
The prover returns $z= r + xe$ to the verifier.
The verifier checks that $a^z=Ac^e$ and $b^z=Bd^e$.

Well, we then show how to use this proof to prove that some ciphertext $c'$ is the randomization of $c$.

We denote by $g$ the generator of a prime order group $G$, by ${\sf pk} \in G$ the public key, and by $m\in G$ the plaintext message.

We parse $c$ as $(c_1,c_2)=(g^r,{\sf pk}^r m)$.

To randomize $c$, Bob chooses $s$ at random and computes $c'=(c'_1,c'_2)=(c_1 g^s , c_2 {\sf pk} ^s) = (g^{r+s},{\sf pk}^{r+s} m)$.

To prove that $c'$ is the randomization of $c$, he proves that $\log_g(\frac{c'_1}{c_1}) = \log_{\sf pk}(\frac{c'_2}{c_2})$ using the secret $s$.

Note that this works because $\frac{c'_1}{c_1}=g^s$ and $\frac{c'_2}{c_2}={\sf pk}^s$ have the same discrete logarithm $s$ iff the ciphertext is correctly randomized.


Should data encrypted in a database have a MAC? I need to store sensitive data in a particular column in my database (Postgres). I'm hosting with AWS, so I'm planning on using KMS to use envelope encryption. For example:

To encrypt a secret:

Generate a 256-bit plaintext data key.
Generate a 256-bit random IV.
Encrypt the secret with AES-256-CBC using the plaintext data key, and the IV.
Using KMS, encrypt the data key.
Throw away the plaintext data key.
Encode the IV, the ciphertext secret, and the ciphertext data key in the column.

To decrypt a payload from the column:

Decode the IV, ciphertext secret, and the ciphertext data key from the column.
Using KMS, decrypt the ciphertext data key.
Decrypt the ciphertext secret with AES-256-CBC using the plaintext data key, and the IV.

With this in place, should I encrypt-then-MAC the message? I found this answer about using a MAC with a HSM, but I'm not sure if it still applies in the case of data stored in a database:

For checking data integrity, isn't this already covered by our database?
For checking authenticity, we are the only ones who consume the ciphertext. For example, we do not exchange the ciphertext with a client where it could be modified.

Is applying a MAC to the encrypted data unnecessary overhead?

Ideally yes, encrypted data in a database should be authenticated as well, along with the context in which the encrypted data appears as associated data—some subset of plaintext values like (not exhaustive):

A database instance identifier;
The database, schema, table and column names in which the encrypted data is stored;
The column names and values of unencrypted columns in the same row as the encrypted value.

The reason is that this protects against a privileged user—say, a malicious DBA—from cutting and pasting values around to change the interpretation that a client application will give to the data.  E.g., Eve the malicious DBA could take encrypted credit card numbers in the database and swap them in order to cause the system to charge the wrong person for things.

If you don't authenticate the values, or even if you just authenticate them minimally, with no associated data, you expose yourself to such attacks.  This is also true if you use too little associated data—for example, if you just use the row primary key as associated data, a malicious DBA might still be able to carry out the same attack by swapping everything else other than the ciphertext and primary key.

There are big downsides here, however, which is that the more thoroughly you authenticate the ciphertexts and their contexts, the harder you make it for honest users to work with the database unless you hand them the master key as well—which is of course very undesirable.  For example:

Suppose you include all the unencrypted columns in the same row as associated data for the ciphertext's authentication tag.  Well, now any non-identity update to the row's plaintext columns will cause the decryption to fail unless it also decrypts, reencrypts and authenticates the encrypted columns anew.  For insert-only databases this might not be a big deal, but if your application is heavy on updating existing rows then it can easily be a deal-breaker.
A very common operation in relational database management is to create custom views (logical or physical) that present a subset of the data from one or many tables to some user or application.  If some such views present them with encrypted data that they may want to decrypt, using associated data with the authentication can make things harder or impossible:

If table names are used as associated data, the decryptors must keep track of which column in the view came from which base table in order to decrypt it.  This defeats the data abstraction that views are supposed to afford their users.
If the views available to some user or application allow them to see a ciphertext column but not all of the columns that provide its associated data, the user won't be able to reliably decrypt the ciphertext.

So these are very serious obstacles that make extensive use of associated data a tricky proposition for databases.


Homomorphic Encryption vs. Garbled circuits I'm currently trying to understand all the differences between homomorphic encryption and garbeled circuits. As I understood the use of homomorphic encryption hides either the data or the computation from the computational party, but what about the circuit? Is only the data hidden with homomorphic encryption?

There has been work on using garbled circuits while also hiding the function. This can be done via implementing a universal circuit inside the garbled circuit. However, the standard garbled circuit does reveal the topology of the circuit. Also, when considering malicious security, the most efficient method is cut-and-choose, and this reveals the actual circuit. When you need to hide the function, then you need to take care of this explicitly (e.g., via a universal circuit, as mentioned). Here is one paper by Mohassel and Sadeghian that considers this question.

Beyond this, there are many differences between FHE and secure computation. In general, FHE is one way of getting secure computation, but it can also be used in other settings where secure computation is not applicable (e.g., when you cannot have interaction). However, FHE is not yet efficient enough for most tasks, and garbled circuits is much much faster. Having said this, in some cases, it suffices to use somewhat FHE (which works for low-depth circuits), and this can be very fast.


What are the known weaknesses in AES and is it being considered for upgrade or replacement? I was at a conference earlier this week sponsored by a library about data archiving. The conference was not about cryptography. One of the speakers said that the Advanced Encryption Standard (AES) was going to be 20 years old next year (Rijndael was first published in 1998) and that it was getting near the end of its life.

I'm familiar with cryptography, and I've been troubled by this statement ever since, because I didn't think that AES was in any danger. The algorithm has sufficient key lengths, even to resist quantum computer attacks, and there are no algorithmic flaws that have been discovered.  Recall that DES was showing its age in the mid 1990s, but that was because it's key length was unreasonably short, not for any other reason.

Are there current reasons to consider upgrading or replacing AES?

The two main weaknesses where AES shows its age are the 128bit blocksize and the fact that AES 192 and 256 have far less security margin than the pure key size would suggest (some reasons for that here).

Besides that the concept of a block cipher with modes begins to be regarded as risky (authentication, padding, nonces) and more higher level primitives should be used in APIs (newer approaches like NaCl secretbox).

So from a crypto community standpoint it shows its age but is still time proofen and not broken. Especially since alternatives enjoy less general acceptance (especially if compliance voodoo is required).

I would argue long term archives cannot escape the voodoo argument for now, so they do rely on AES (at least in western geographies).

I think a successor will provide more than 128bit block size (or state), start with large key sizes and support efficient authenticated methods and maybe some support for parallelisation. It will hopefully define a approved family of modes/parameters in favor of free composition of primitives.


Can we use a Cryptographic hash function to generate infinite random numbers? I have seen that there are PRNG that can generate a specific number of random-numbers. The Mersenne Twister as an example, can generate 2**19937 (if I'm not wrong) but... can we use a cryptographic hash function to generate infinite random numbers setting any seed to it?
So I can set text for the seed and do it like this:

seed set to "myseed"
counter set to 0
first random number generated = first 64 bits of "myseed0" hashed with sha512
secound number = first 64 bits of "myseed1" hashed with sha512

Or we can save the other 448 bits left and use them later. The main idea, is 100% secure to generate PRN's from a hash function? why don't we do it?

This construction gives you cryptographic-quality pseudorandom output, but it isn't as secure as it can be for a random generator.

With commonly used hash functions $H$ (such as any of the SHA2 and SHA3 family), as far as we know, the bits of $H(\textrm{seed}, n)$ are unpredictable if you only know $n$ and $H(\textrm{seed}, m_i)$ for any number of values $m_i \ne n$, but you don't know $\textrm{seed}$. This makes $D(n) = H(\textrm{seed}, n)$ a good key derivation function: its output is essentially indistinguishable from random.

A good random generator must have the property that a bit in the output is not predictable even if the adversary knows all the other bits of the output, but not the seed. The construction $H(\textrm{seed}, \textrm{counter})$ has this property. But a good random generator also has an additional property: backtracking resistance. Backtracking resistance means that if the adversary compromises the hash state at some point, then they can't recover past outputs. (Of course the adversary will know every future output, at least until the random generator is reseeded.) Your construction does not have this property since the original seed remains a part of the hash state.

A good random generator has a “ratcheting” step, which makes it impossible to recover the previous state from the current state when generating some output. It's easy to build ratcheting with a hash function: you basically just run the hash function on the hash state. Take a hash function with an $n$-bit output. Start with an $n$-bit secret seed; that's the original state of the random generator. To generate up to $n$ pseudorandom bits, calculate $H(0 || \textrm{state})$ and output that; also calculate $H(1 || \textrm{state})$ and use this as the next internal state. In pseudocode:

state = seed
while True:
    output(hash('0' + state))
    state = hash('1' + state)

Hash_DRBG specified in NIST SP 800-90A is a popular pseudorandom generator construction based on this principle.


Does Coron and May's paper for deterministically reducing finding  to factoring  work with $\lambda(n)$? Samuel Neves in his reply mentioned a method by Coron and May's 2004 paper for deterministically reduce finding  to factoring .
As you all know, we are using $\lambda(n)$ everywhere now for RSA. So question is, does this work for $d$ generated with $\lambda(n)$? The paper seems referring to $\varphi(n)$ only. If it does work, what is the proof?
Also, anybody knows some reference implementation of Coron and May's method in Python or other language?
If it does not, is there any probabilistic method/algorithm to factor $n$ if $e,d$ are known and $ed = k\lambda(n) + 1$ ?

As mentioned in the other answer, the probabilistic method always works, and I've described both of these methods before.
We'll deal exclusively with $p, q$ of approximately the same size here. Suppose $l = \gcd(p-1, q-1)$, the ratio between $\phi(n) = (p-1)(q-1)$ and $\lambda(n) = \mathrm{lcm}(p-1, q-1)$. As usual, let $n = pq$, $e$ be the public exponent, $d = e^{-1} \bmod \phi(n)$, and $d' = e^{-1} \bmod \lambda(n)$.
The original Coron-May reduction observes that $f(x) = n - x$ has a "small" root $p+q-1$ modulo $\phi(n)$, a "large" divisor of $ed - 1$. More specifically, as long as there's a $\beta \in [0, 1)$ such that $p+q-1 \le (ed - 1)^{\beta^2}$ and $\phi(n) \ge (ed - 1)^{\beta}$, the method works in polynomial time. Because $\phi(n) \approx n$, this effectively translates into the requirement $ed \le n^2$.
Without any changes to the method, replacing $\phi(n)$ by $\lambda(n)$ means that $f(x) = n - x$ has a small root $p+q-1$ modulo a large factor of $ed' - 1$. Because of the common factor $l$, $d'$ may be much smaller than $d$, and in particular the size is no longer neatly related to $n$, so as to achieve a bound like $ed' \le n^2$. However, the method still works under the more elaborate constraint that there be a $\beta$ such that $p+q \le (ed' - 1)^{\beta^2}$ and $\lambda(n) \ge (ed' - 1)^{\beta}$.
For typical $e = 65537$, we still have $\lambda(n) = (ed'-1)^{\beta}$ for a $\beta$ very close to $1$. As long as $2p < (ed' - 1)^{\beta^2}$, the reduction still works.
Here's a worked example using Sagemath, where $\phi(n) \approx 2^{130}\lambda(n)$.
sage: p = 30010719099306564150822479775631261956587370647517629976046542673406882291177
sage: q = 91932507744510266739810220416155764940049951037172916877150162469889273507869
sage: n = p * q
sage: l = gcd(p-1, q-1)
sage: l
1361129467683753853853498429727072846028
sage: e = 65537
sage: d = inverse_mod(e, lcm(p-1,q-1))
sage: P.<x> = Zmod(d*e-1)[]
sage: f = x - n
sage: beta = d.log(d*e).n()
sage: beta
0.959304860280816
sage: assert(p+q < (d*e-1)^(beta^2))
sage: f.small_roots(X=2^257, beta=beta, epsilon=0.05)
[121943226843816830890632700191787026896637321684690546853196705143296155799045]
sage: p+q-1
121943226843816830890632700191787026896637321684690546853196705143296155799045

With a larger $e$, it still works. Say, $e \approx 2^{180}$:
sage: e = next_prime(2^180)
sage: d = inverse_mod(e, lcm(p-1,q-1))
sage: P.<x> = Zmod(d*e-1)[]
sage: f = x - n
sage: beta = d.log(d*e).n()
sage: beta
0.677720040398063
sage: f.small_roots(X=2^257, beta=beta, epsilon=0.01)
[121943226843816830890632700191787026896637321684690546853196705143296155799045]

Here we are already pushing the limit, since $(ed' - 1)^{0.6777^2} \approx 2^{256.53}$. Going much higher with $e$ will fail. The original method with $\phi(n)$ would allow $e$ to go up to $\approx 2^{512}$ in this example.


X.509 ECDSA signature field in DER format includes '00' between bit string and sequence of r and s I created a X.509 certificate with ECDSAwithSHA256(OID=1.2.840.10045.4.3.2) by openssl.
ECC parameter is secp256r1.

Following is the signatureAlgorithm and signatureValue.

30 0A 06 08 2A 86 48 CE 3D 04 03 02 // signatureAlgorithm field
03 49 // the starts of signatureValue indicating bitstring length of 0x49 bytes.
00 // what is this?
30 46 // the sequence of r and s as specified in RFC3279
02 21 00 98 21 1C AE A4 03 EA 1C 3A 9F 4B 9A AB 94 2E 89 97 67 F1 51 76 F8 00 A8 3B 72 57 1D 95 FA C6 B8 // this is r
02 21 00 A9 79 69 AC 04 A0 8C 2E 40 7C EF 81 B4 E2 1B DE 58 BB E4 EB 3D 4A 0D 7E 2D 80 EB FA 89 B5 B6 E8 // this is s

I don't get what '00' does here.

Is it related with following statements in the X.690 specification?

  8.6.2.3 If the bitstring is empty, there shall be no subsequent octets, and the initial octet shall be zero.

No, the 00 simply indicates how many least significant bits are not used in the last octet of the BIT STRING.

As the bit string contains an octet string (consisting of the sequence of two integers) it will always be zero, as all the bits in the BIT STRING are used. This is defined for the BER/DER encoding of BIT STRING itself.

As for why the signature is not specified as an OCTET STRING itself, well, beats me, as most signatures are defines as OCTET STRING anyway, even if they are not constructed such as RSA signatures.


Why do we get the following equation in case of a One Time Pad? If m: message, M: message space, k: key, K: keyspace, c: cipher, C: cipher space and $E_k$: encryption function, such that
$E_k(m) = c,\ m,m^* \in M,\ k\in K,\ c\in C.$

My first question is, is the following equation correct for One Time Pad encryption?

$$P[E_k(m) = c] = \frac{ \sum_{m_ i\in M} \sum_{k_ i\in K} P[E_ {k_ i}(m_ i) = c] } {|M|.|K|} $$

And, my second question is, why do we get that?

I'm not fully sure if the equation is correct, as I think $P[E_{k_i}(m_i)=c_i]=1$, as the encryption always produces a cipher text (which is what you formulated I think, as there's no definition of $c_i$).

If you change the $c_i$ to $c$ however you'd calculate the average probability that any message-key-pair encrypts to $c$.

I didn't take part in such a course yet, but this looks right as for the OTP the probability that a certain message encrypts to a certain ciphertext under a certain key is basically the same as the probability that any message using any key encrypts to this specific ciphertext. So this would mean that you can't derive any relations between ciphertext and plaintext because any plaintext-key pair could match your ciphertext. This sounds pretty much like perfect secrecy and hence like an OTP.

I hope this helps you.


Secret Key Exchange and FIPS or Industry Standard Compliance I am trying to collect several information regarding Security Industry Standards and the FIPS compliance to meet the security standards for our future development system.

In this case, we have two systems connected each other point to point through switch. We are interested in encrypting the data to run IO's across these two systems. Planning to encrypt data with AES-128, but struct on the best Industry standard compliance algorithsm to exchange the Symmetric Key. We are not connected here to Internet to exchange keys through 3rd Party or any other Certificate Authority.

Could someone please suggest the best possible way to generate and exchange keys in this scenario and also meet the industrial standard ?

Thanks a lot in advance...

Suppose you are a device manufacturer. Suppose further you know to which companies you are selling your devices. Suppose further that all that really matters for the device-to-device communication is a) that they are legitimate devices made by you and b) that they are operated by a specific company. Now if your customers trust you (which they kinda have to given that you sell them devices), these devices can be made to communicate securely.

I'll make the assumption that the static private keys are non-extractable because if you can extract one, you can impersonate this device. This can be achieved using TPMs, HSMs or other security-chip based key-stores.

The idea here is that you pre-provision all devices you ship and you essentially act as the CA in this ecosystem.

The setup is really quite simple:

Manufactur the device right up to the point where you would normally ship it (that is all hardware and software is complete)
Generate an asymmetric signature key-pair on the device. Also generate a CSR on the device, given that you create the CSRs in a trusted environment, you can include the designed customer in it.
Transport this CSR to your internal CA and issue the requested certificate. Given that the CSR is from a trusted environment, you can "blindly" copy the owner information into the certificate.
Transport and install the certificate into the secure-chip's keystore. Also install the certificate / public key of your internal CA into your platform's root CA store (and make sure it's the only root CA) on the device. Make sure that your preferred SSL/TLS library actually uses this key-store.

This is the whole setup, which needs to be executed per-device.

Now for the connection establishment which is really standard.

Suppose Device A wants to securely talk to Device B. Suppose further both devices are listening for incoming connections.
Now A ("the client") initiates a TLS handshake with B ("the server").
You run a standard TLS-connection between the two devices with the following caveats:

You make sure only secure parameters and cipher suites are used.
You only accept B's certificate if it passes standard certificate validation and your custom company-based validation and it is issued by your root CA.
B needs to request client-authentication during the handshake. B needs to only accept A's certificate if standard validation succeeds and it passes the custom company-based validation and it is issued by your root CA.

And that's it. Your devices now have a secure connection and they know (and only that!), that their communication partner was manufactured by you and that their communication partner is a device that was sold to the given (other?) company.

The use of the device-manufacturer CA is industry-standard, as well as the use of TLS here. For high confidence you may want to your customers to use their own CA, their own sub-CA (and filtering for that one then if requested) and you want to apply standard CA security practices to your device-authentication CA.


Single-block hash construction based on a block cipher with two fixed keys Let k1, k2 be two arbitrary fixed keys (nothing-up-my-sleeve values like "foo" and "bar") and E_k1 and E_k2 be the corresponding encryption functions of a block cipher. x is a single input value (same value is fed to both E_k1 and E_k2).
Define a hash as follows:
H(x) = E_k1(x) xor E_k2(x)
This hash is meant to be used exclusively for proof-of-work purposes. The input size is assumed to exactly match the block size. There is no significant issue with the risk non-trivial collisions. The construction was intentionally designed to include only encryption operations, not key-scheduling (for optimization reasons). This makes it different than common constructions like Davies–Meyer, Matyas–Meyer–Oseas or Miyaguchi–Preneel.
Wikipedia says:

Black, Cochran and Shrimpton have shown that it is impossible to construct a one-way compression function that makes only one call to a block cipher with a fixed key.

This one uses two fixed keys, so it leaves the option it is good enough.
The underlying cipher is intended to be AES-128 or AES-256.
The question is: do you know of papers that have tried to analyze this type of construction? Can you give some of your own insights?
Edit: The intention was to define a hash. I misunderstood the idea of "compression function". I have changed the title now.

This construction is well-known as XORP = "XOR of independent permutations". In your case the permutations are obtained by invoking a block cipher $E$ with different keys.
If $E$ is an ideal cipher, and $k_1, k_2$ are distinct (fixed, public) keys, then $E_{k_1}(\cdot)$ and $E_{k_2}(\cdot)$ are independent, ideal permutations. Ideal permutation means that everyone has oracle access to these permutations as well as their inverses.
The right question to ask here is:

If $\pi_1$ and $\pi_2$ are independent ideal permutations, is $\textsf{XORP}(x) = \pi_1(x) \oplus \pi_2(x)$ indifferentiable from a random oracle?

"Indifferentiable" means that $\textsf{XORP}$ looks like a random oracle, even to a distinguisher who has access to the underlying $\pi_1, \pi_2$ (and their inverses), which is the case here.
The answer to the question is yes, XORP is indifferentiable from a random oracle. See:

Srimanta Bhattacharya, Mridul Nandi: Full Indifferentiable Security of the Xor of Two or More Random Permutations Using the $\chi^2$ Method (Eurocrypt 2018)

Notably, XORP is secure beyond the birthday bound. If the permutations are on $n$-bit strings, then an adversary who makes $q$ oracle queries can distinguish XORP from a random oracle with probability at most $q/2^n$, instead of $q^2/2^n$.
In summary: $x \mapsto \textsf{AES}_{k_1}(x) \oplus \textsf{AES}_{k_2}(x)$ is a very strong one-way function, under the assumption that AES is an ideal cipher.
Aside: if $k_1$ and $k_2$ are independently random and private, then the question is whether $x \mapsto \textsf{PRP}_{k_1}(x) \oplus \textsf{PRP}_{k_2}(x)$ a pseudorandom function. This is much simpler since the distinguisher does not get direct access to the individual PRPs. Of course the answer here is also yes.


How can I create a fixed length output in my hash function? I've been recently looking into the creation (and theory) of hash functions, however I just can't figure out how to turn a message into something of a fixed length.

At the moment, my theory of a hash function is like so:

Take in the message (e.g. "secret")
Split it into different 'blocks' (e.g. "sec" + "ret")
Mix them up, and interact different blocks depending on what block type
they are (perhaps block type would be determined by mathematical calculations
on the character values, and then certain blocks would interact with other
blocks to merge in a weird way to create another block).

This creates a message which cannot be undone (since at the end, you don't know what the block types are - and even if you do, you don't know how they interacted to get to those blocks) - however it is not of a fixed length.

What would I do to create a fixed length digest?

Basically, typical hash functions produce a fixed-length output by the following method:

They expand the input to some multiple of their block size by adding padding.
They compress the first two blocks into a single block using a mixing function and repeat until only one block is left.
The use a fixed finalizing function to turn that last block into their output.

As a simple example, consider a rather trivial and insecure hash function for decimal numbers that produces a one decimal digit output. It could work like this:

Add a 9 onto the end of the input. Then add zeroes until the number of digits is even.
If there are more than two digits, replace the first four digits with the two-digit sum of those four digits. Repeat until only two digits remain.
Sum the final two digits to get the output.

This will produce a single decimal digit of output for any decimal input.

For example, take 123.

Add a 9 on the end - 1239. The number of digits are even, so no zeroes appended.
We replace the first four digits with their sum, 15. There are two digits, we're done.
We sum the 1 and 5 to get 6. Our output is 6.

While this function is simple and insecure (because its mixing function is so bad and its block size so small) it illustrates how hash functions produce a fixed-sized output from a variable-sized input.


Plaintext block chaining, bad idea why? Ahead of the question, little warning. Question is not about what are the better options. Question is why it is bad idea?

Ok, suppose we have plaintext $p$, which divided into blocks: $p_1,p_2,p_3,...,p_n$

CBC (cipher block chaining) can be then defined as $c_1=E_k(p_1 \oplus IV)$,$c_2=E_k(p_2 \oplus c_1)$,$c_{i+1}=E_k(p_{i+1}\oplus c_i)$

Ok. What would be bad about this version $c_{i+1}=E_k(p_{i+1}\oplus p_i)$?

($E_k$ is some encryption function)

Patterns aren't hidden. Assume you've got a pair of plaintext blocks $p_1, p_2$ then the encryption of $p_2$ will always be the same: $c_2=E_k(p_1 \oplus p_2)$ as it only depends on the plaintext. So you haven't basically solved the basic problem of ECB (patterns remain) but rather moved it (to the more rare case) that two blocks repeat.
Plaintext isn't random. In most cases an attacker can predict plaintext. As you basically use plaintext as IV for each block you make the scheme vulnerable to attacks like BEAST, where attackers use predictable IVs to gain information about target connections. See this related question.

Corrected my speed concerns. Encryption and decryption can be parallelized, speed should be comparable with CTR.


Turning data into seemingly random noise I am currently working on a python script that does image steganography, altering the least significant bit on each channel of the image. Now imagine encrypting a file with a bunch of null bytes, or if you want a more realistic scenario, text that has a lot of repeating sequences in it (whole words / characters); Analysing the LSB of every channel of every pixel of this image, will reveal certain patterns and the hidden message can be decrypted easily.

The ultimate goal would be to turn the data given in bits into something that looks like random noise, but can be decoded easily with the given key.

What is a (fast) way to achieve this ?

One idea I came up with after googling for a while is the following:
Generate a random bit sequence, the same length as the data you want to hide, that is based on a specific seed/key. It can be generated again as often as you want supplying the same seed. Now xor the generated bit sequence with the data provided and use this hopefully random looking binary data as the basis for the pixel modifications.

Is this (more or less) secure from a cryptographic standpoint provided the evil decoder doesn't know the algorithm ?

What you described is to use a so-called "stram cipher".

Stream ciphers output a random sequence of bytes for the same Key/IV pair.

The usual usage of stream ciphers is to XOR the data with the stream to obtain the encrypted data. You may want to follow the same approach by replacing the LSBs by the bits that were output by the encryption procedure (Data XOR Stream). The data is confidential then and can not be deciphered.

If you use some well-known algorithm like ChaCha, Salsa20 or AES-CTR you don't even have to hide the algorithm, you can tell your adversaries that you use this algorithm and they still can't read the enciphered data. You only need to keep the Key and the IV secret. Note: Using stream ciphers will hide any patterns that might be in the plaintext.

But you're not done here.
An attacker can't read the information but he can still alter it. So he can tamper with the data you encrypted and using some nice bit-flips he can alter the transmitted data in a malicous way (like changing numbers). So you wan't to use some sort of authentication mechanism (Message-Authentication-Code = MAC).

The best approach is to use AES-GCM or ChaCha-Poly1305 to get both: Confidentiality and Integrity. These modes will generate tags (usually 128 bits) which you'd store at the end of the data and you'll be able to verify that the data hasn't been tampered.


Key at start or end of HMAC In the book Information Security Principles and Practice, the author explains why HMAC should be used for integrity with a symmetric key with the message, to prevent a MiTM to replace both the message and its MAC.

He explains why it is not secure to prepend the key to the message, with notation h(K, M). I don't understand how the attack works. Here's the paragraph:

  Suppose  we  choose  to  compute  an  HMAC  as  h(K,M).        Most
  cryptographic  hashes  hash  the  message  in blocks—for  MD5, SHA-1,
  and  Tiger,  the  block  size  is  512 bits.   As a result,  if M  =
  {B1,  B2),  where  each  Bi  is  512 bits, then  h(M)  =  F(F(A, B1),
  B2) = F(h(B1), B2)                        (5.2)
  for  some  function  F,   where  A  is  a  fixed  initial  constant.
  For  example,  in  the  Tiger  hash,  the  function   F  consists  of
  the  outer  rounds  illustrated  in  Figure  5.2,   with  each  Bi
  corresponding  to  a  512-bit  block  of  input  and   A
  corresponding  to  the  192-bit  initial  value   (a,b,c).

  If  Trudy  chooses  M'   so that  M' =
  (M, X),     Trudy  might  be  able to use  equation (5.2)  to  find
  h(K, M') from h(K, M)  without knowing  K since, for  K,  M,  and  X
  of the  appropriate  size,   h(K,  M')  =  h(K,  M, X) = F(h(K, M),X),
  where  the  function  F  is  known.

The last paragraph is the attack.

I don't understand, how does the attack work? How can Trudy find h(K, M') from h(K, M) without knowing K?

This is a basic length extension attack. For hash functions like SHA-1 and SHA-2 the final state of hashing $h(K \| M)$ block by block is the output. If you hash $h(K \| M \| X)$ then you simply continue hashing from the given state (i.e. the last output).

In practice though the final block must contain a valid padding and length, which is added to $K \| M$. So basically you can create a valid hash for $K \| M \| P \| LE \| X$ where $P$ is the padding and $LE$ is the length encoding. You cannot just create any message that starts with $M$.


BLS to Schnorr signature conversion? Imagine a situation where a prover can only sign with BLS signature signing algorithm, a verifier can only verify with Schnorr signature verification algorithm. Is it possible to convert a BLS signature to a Schnorr signature, so that a verifier who can only verify Schnorr signatures can verify derived signature given public key and message?

You can't convert the signature output from one algorithm to another, especially not ones relying on random oracles.


What is meant by a 'tag' with regards to transmitting a MAC? What is meant by a 'tag' with regards to transmitting a MAC?

Are there multiple meanings within cryptography?

Update - take this for example:

$Bob \to Alice \Rightarrow m\ ||\ h(m, ``secretTag")$

A tag or authentication tag is something that is attached to (tagged along with) a message. It provides integrity and authenticity to the message.

Tags are also calculated for authenticated ciphers (AEAD ciphers, such as GCM). They can in that case be calculated by an internal MAC algorithm, but this does not have to be the case.

The size of an authentication tag can usually be configured. The size must be predetermined before use however (or an attacker can simply try and crack a shorter authentication tag). Usually the size is between 64 and 128 bits (128 bits being the block size of e.g. AES), although hash based tags may be larger than that.

A tag is usually placed at the end of the ciphertext. It can however in principle be communicated or placed separate from the ciphertext.

I'm not aware of any other meaning of the word "tag" or "authentication tag" within cryptography.


Stream slicing operation in block cipher and side-channel attack My symmetric block cipher works kind of like a stream cipher, but it works on $128$-bit blocks. It generates a $128$-bit block in every round. And at the end of the round, I have to slice it into two blocks and add them together. I mean after each round we take first $a$ bits and second $b$ bits of $128$-bit block and then compute $b+a$. $a$ is equal to $0$ to $127$, it is computed from the key schedule and should be indistinguishable from random. But such slicing can be attacked by the side-channel attack. Attacker can find $a_{0}$, $a_{1}$, $a_{2}$ and so on for every round.
But my cipher works like a stream cipher. That means it computes bit by bit in steps and then combines them into a block. Normally I'm making $128$-bit block with this, for $i$ in the range $0-127$:
$ct=0$
$ct=ct+bitv$
$bitv$ is a bit value $0$ or $1$ and it comes from cipher function. We are just making some binary string/block here. My idea is to not slicing block in the end but first compute first $a$ bits like a string for $i$ in the range $0-a$, where $a$ is some indistinguishable from a random number from the key schedule:

$a=a+btiv$

and then compute the rest of the string for $i$ in range $a+1-127$ as:

$ct = ct + bitv + a$

Anyway, we still have to make for example two loops "for". First for $i$ in range $0-a$ and second in range $a+1-127$ inside the round. Is it possible to attack it by the side-channel attack? Can the attacker detect when the first loop will end and the second will start and then find $a$?

The key schedule should be considered secret. Your side channel reveals the key schedule. Even if your key schedule is indistinguishable from random an attacker can usually still derive the key. Since your key schedule is the same as your encryption algorithm it would be inherently vulnerable to the same attacks as your encryption. Even if it isn't, your key schedule probably still isn't a secure hashing algorithm and therefore the original key can even be obtained.
Most (all) modes of operation are broken even if only the key schedule is revealed but not the key. Some are (slightly) less broken than others.
Side-channels are enabled by any data-dependent memory accesses. Even if the total number of memory accesses is constant, this cannot be assumed to provide security. If I perform some computation on bits $1,...,a$ and I perform another (possibly the same) computation on bits $a+1,...,128$ I've just performed a different pattern of memory accesses, and revealed the value of $a$ (which is nearly impossible to fix in implementation). Nevermind the fact that for loops require an if statement to tell when to break (the compiler adds it implicitly). That means that you've allowed cache-timing, branch-prediction, and branch-timing attacks.
On the impact of various side-channels

Cache-timing is fixable in hardware that doesn't cache memory. Memory caching exists in all major architectures, and can't really by bypassed or disabled.
Branch-prediction (also known as speculative execution) only exists in hardware that tries to predict branching. This behavior exists in all major architectures, and can't be bypassed.
Branch-timing attacks, however, are hardware-agnostic and will affect every system identically... For this reason these are among the worst of all side-channels.

All side-channel attacks, even if hardware-dependent, are considered crippling to a secure cryptographic implementation.


Lamport-Diffie + Security Proof I am studying Lamport-Diffie signature scheme. In the lecture present the algorithm  $A'$ for attempting to invert the one way function $f$, where $f$ is used to compute the public key. My question is Why to use this algorithm $A'$ to prove the Theorem 1?, Why I cann't use other any algorithm (for example Grover, or Brute Force)?

Well, $f$ is assumed to be a one-way function. That means, there cannot exist an efficient algorithm for finding preimages under $f$. The algorithm $A'$ is what we call a reduction.

We are trying to show that an efficient algorithm for attacking the signature scheme does not exist. To do that, we assume the contrary, i.e. we assume an efficient algorithm $A$ exists that successfully forges a signature. We then use this algorithm $A$ as blackbox (i.e. we do not assume anything about it beyond the fact that it works) to construct a second algorithm $A'$.
This algorithm can efficiently compute preimages under $f$, if $A$ works as specified. Because we assumed that $f$ is one-way, this a contradiction, as no such algorithm can exist if $f$ is one-way.

Now, because the existence of $A$ implies existence of $A'$, but $A'$ cannot exist, we can conclude that $A$ cannot exist either. This proves that no efficient adversary against the one-time signature scheme exists and the scheme is, therefore, secure.

Some algorithm for inverting $f$ that does not use the adversary against the signature scheme (besides not being efficient) would not allow you to conclude anything about the security of the scheme.


AES Implementation for Image Encryption I've been delving into cryptography for fun and trying to implement a visualization for AES using image encryption. So far, represented each pixel's RGB values as hexadecimal numbers, then split it into an array of 16 character strings. I know that AES is a block cipher, so I have to split them into 16 character strings, but how am I supposed to handle when the string becomes less than 16 characters? I've heard that I should just pad it and add more characters to fit it into 16 characters, but I'm not sure if that's correct, since the padded characters won't be represented in the final image, and be able to be decrypted.

CAUTIONARY NOTE: Beware that the vast majority of countless articles that discuss "image encryption" using computers (rather than using essentially optical means) are junk science. I don't know any article with "image encryption" and "AES" in the title (as the question does) that's worth studying (I welcome a link in comment if I missed one).
Encrypting digitized images (rather than other kinds of digital data) using AES requires no special crypto or preprocessing. As for other kinds of digital data, compression (if used) must be applied before encryption, and decompression after decryption; and then one should examine the consequences of the fact that crypto does not hide the length of what's encrypted.

There's no good reason that the plaintext (what's encrypted) go thru hexadecimal (a system of representation where 4 bits are encoded into a character): this would typically double the size compared to using the raw bytes. Hexadecimal is a way for eyes to see raw bytes, or express the ciphertext (result of encryption) as text (even though there are better encodings for that), but it should not be part of how the plaintext is transformed for encryption.
Learn about AES-CTR (or AES-OFB, even though it's not nearly as common), which let you encrypt data without bothering forming 16-byte blocks (these two modes avoid the need for padding; on the other hand that would be necessary for ECB, a mode of operation notorious for being bad, especially for highly redundant plaintext including uncompressed images).
Then learn about authenticated encryption, which is the modern way to protect data confidentiality and integrity using a symmetric key. Examples of that include AES-GCM(-SIV).


How to crack SHA256 only letters I recently created a program that hashes a password using SHA256 and potentially using salt. How can I crack that if I know that the password only contains lowercase letters?

Let us ignore all kinds of encoding or protocol details. We are looking for some string such that $yourprogram(string)=h$, where $h$ is a specific hash value. You will try to crack that password, rather than SHA-256.

Let us assume that all the possible messages you have are the 26 lowercase letters of English alphabet. That means that, for every letter in your password, you would multiply by 26 the amount of possible passwords. For instance, there are $26^{10}$ passwords of 10 letters. Then, if you try to brute force (try every possible solution until you hit the jackpot), it would be enough to use a longer password to prevent your attack. Sure: it would be longer than a password with a longer character set (uppercase, numbers, special characters), but it could be somehow manageable.

The problem is that humans are very bad at producing and remembering randomness. The fact that we are discussing this issue occurs mostly because "hquekl" is, despite being meaningless (to me, at least), easier to remember and communicate than "a{çè_". Which means that most passwords are likely to be "words". A word, in this sense, is a broad term, since it is just a string that we can remember. It can be an English word (password), a Spanish word (clave), a pattern (qweqweqwe), an English word backwards (drowssap) or a phrase (iloveyou). Some languages have a name for the word "dictionary" that can be roughly translated as "wordbook". As an attacker, this is the goal: collect the sets of words that compose the most likely passwords and create a list. Now, as an attacker, using a dictionary makes your job easier.

If you do not use salt, your scheme will be victim of determinism. Let us say that (for a very innocent hash algorithm) $hash(password)=5$. You do not know the value of $password$, but you steal a list of password hashes and see several entries of $5$. Not only that increases the likelihood of $password$ being in a dictionary: that means that several users have the same password. Furthermore, you can check a rainbow table: a gigantic list of precomputed hashes. Maybe someone already found out a value of $password$ that hashes to $5$, and even the dictionary attack will be unnecessary.

If you use salt, keep in mind that the value of salt is intended to be considered public, but has to be long enough. You can always make it difficult to the attacker, by asking increasing long passwords and blacklisting passwords that can be found in a dictionary. But you will make it even more difficult for your legitimate users.


How to produce large list of BigInteger prime numbers (RSA) in fast and efficient way Hello fellow experts here, in order to use RSA to encrypt and decrypt in a controlled environment, we will actually need to have a list of prime numbers to do so instead of using library generated RSA keys to encrypt and decrypt.

My current approach here is to actually skip all the even numbers and increment the BigInteger by 2 through looping to select and filter out the possible prime numbers. However this process is really performance taxing (by using BouncyCastle), I was wondering if there was really any faster and efficient method to generate an infinite amount of BigInteger prime numbers that can be used for RSA?

We will actually need to have a list of prime numbers

That's dangerous, since that list must be kept secret, and primes that have been used removed to avoid reuse. There's almost always a better way, like generating the primes on demand. But let's ignore that.

  My current approach here is to actually skip all the even numbers and increment the BigInteger by 2 through looping to select and filter out the possible prime numbers

If two large primes $p$ and $q$ thus obtained are used to form RSA moduli $N=p\,q$ , then that modulus $N$ will be factorable in a millisecond: compute $u=\left\lceil\sqrt N\,\right\rceil$, $v=\sqrt{u^2-N}$ (which critically will be a small integer), the factors are $u-v$ and $u+v$. That's a special case of Fermat's factorization method. This works because the two primes will be overly close¹, and illustrates a more general fact: we must generate two primes forming an RSA moduli in a way such that they bear no relationship known to an attacker².

Also, in most applications, we want that revealing the factorization of a number of $N_i$ does not help factoring any other $N_j$. For this reason, it's simplest/common/best to generate the primes independently. It remains important to generate them fast.

There are several ways to generate primes in a reasonable time. A simple one improves on the method above by avoiding not only the multiples of two, but the multiples of more small primes, so that fewer candidates will be tested before a prime is found. For example, when generating a prime with $b$ bits, we would expect to test about $b\ln(2)/2$ odd integers (that's $\approx355$ for $b=1024$), per the Prime Number Theorem. But if we manage to avoid those with no divisor among the first $127$ primes (that is, the primes to $709$), we improve this by a pleasant factor of $\displaystyle\prod_{3\le s\le709\\\,s\text{ prime}}\frac s{s-1}\ \approx5.9$.

The most usual methods towards that are

First testing a candidate odd prime $r$ with $\gcd(r,m)=1$, where $m$ is the product of a number of small odd primes; e.g. first up to $23$, or $29$ such that $m=3234846615$ barely fits 32-bit. In one swift test, that reduces the number of prime candidates by a factor of $\approx3.17$. But if the method to test primes already does something equivalent or better, this added filtering will actually harm!
Sieving, essentially building a sieve of Eratosthenes localized to an interval sieved. It's effective, and often practiced. But it's a tad difficult to code and optimize³; and the basic algorithm exhibits detectable bias⁴.

There are other techniques which generate provable primes, and I'm told they are competitive from a performance standpoint. See e.g. FIPS 186-4 B.3.2 for one.

I now describe an alternative to sieving, that also avoids testing candidates $r$ with a small prime factor $s$ (though to an appreciably lower bound than possible with sieving, as noted by poncho), without an explicit sieve array, and (discounting precomputations) with less work on modular reduction of a large value modulo a small prime $s$, which sometime gives a speed advantage.

In a nutshell, we'll use the Chinese Remainder Theorem to generate candidate primes $r$ with $r\bmod e$ drawn in $[2,e)$ and $r\bmod s$ drawn in $[1,s_i)$ for other small primes $s_i$.

Inputs:

We want to generate random primes in $r\in[r_\min,r_\max)$ for use as RSA modulus. We restrict to $2^{(2^6)}\le r_\min<1.01\,r_\min\le r_\max\le2^{(2^{20})}$. For $b$-bit primes intended for $2\,b$-bit RSA moduli with two factors, the customary interval is $\left[\left\lceil 2^{b-1/2}\right\rceil,2^b\right)$, which insures that the product of any two primes generated will be $2\,b$-bit.
We want to use some public exponent $e$, and thus need $\gcd(r-1,e)=1$. We restrict to $e$ an odd prime. Popular choices for $e$ are the five known Fermat primes, and 37.

One-time precomputations:

$m\gets2\,e$.
$r\gets\left\lfloor(r_\max-r_\min)/(2^{40}\,m)\right\rfloor$.
$i=0$.
$s\gets 3$.
While $s<r$ (it's possible to abort earlier, e.g. when $s$ or $i$ is above some bound):

if $s\ne e$:

$s_i\gets s$ (these are primes saved for later use).
$c_i\gets(-m)^{-1}\bmod s$ (these are CRT coefficients for later use).
$m\gets m\,s$.
$r\gets\left\lfloor r/s\right\rfloor$.
$i\gets i+1$.
$s\gets$ the prime following $s$.

Slightly restrict the search interval for $r$ to $[k_\min\,m,k_\max\,m)\,\subset\,[r_\min,r_\max)$ with $k_\max-k_\min$ a prime $t\ne e$, as:

$k_\max\gets\left\lfloor r_\max/m\right\rfloor$.
$t\gets\left\lfloor(k_\max\,m-r_\min)/m\right\rfloor$.
if $t$ is even: $t\gets t-1$.
while $t$ is not prime or $t=e$:

$t\gets t-2$.
$k_\max\gets k_\max-1$ (optional, keeps the interval centered on $[r_\min,r_\max)$ ).

$k_\min\gets k_\max-t$.

For each prime $r$ to generate:

Pick a uniformly random secret $v$ in $[0,e-2)$.
$r\gets ((v+1)\bmod 2)\,e+v+2$; this leaves $r$ odd with $(r\bmod e)\in[2,e)$.
$m\gets2\,e$ ; it now holds $r\in[0,m)$.
For $j$ from $0$ to $i-1$:

Pick a uniformly random secret $v$ in $[0,s_j-1)$.
$r\gets r+m\,((r+v+1)\,c_j\bmod s_j)$ ;
this leaves $r\bmod m$ unchanged and $(r\bmod s_j)\in[1,s_j)$.
$m\gets m\,s_j$ ; it now holds $r\in[0,m)$.

Pick a uniformly random secret $v$ in $[0,t)$, determining the first $r$ tested.
$r\gets r+(k_\min+v)\,m$.
Pick a uniformly random secret $v$ in $[0,t-1)$, determining how $r$ is stepped.
$v\gets v+1$.
$r_0=v\,m$ (increment for $r$)
$r_1=(t-v)\,m$ (decrement for $r$)
$r_2=(k_\max-v)\,m$ (threshold for an increment of $r$).
Repeat⁵:

If $2^{(r-1)/2}\bmod r$ is $1$ or $r-1$ (that is, $r$ pass the Euler test to base $2$):

Test if $r$ is prime⁶, using e.g. a small number of strong pseudoprime⁷ tests to random base, and if so:

Output $r$ and stop.

If $r<r_2$: $r\gets r+r_0$; else: $r\gets r-r_1$.

Caution: It is critical to use an unpredictable randomness source, and that all quantities manipulated remain secret.

¹ The primes will be close if they have been chosen incrementally.

² Other kinds of harmful relations between primes could be: they are generated by testing integers of the form $2\,k\,a+b$ for public $a$ and random secret $b$. That could extend to random secret $a$, if there are several $N_i$.

³ Competing computational bottlenecks are the final primality test (the more small primes are sieved, the less such tests there are), and computing the offset in the sieve (which requires computing the remainder of a large value modulo each of the small primes).

⁴ If we select the smallest prime in the sieved region, it will have a gap with the previous prime larger than expected for a random prime. Selecting a uniformly random prime in the sieved region mostly fixes that, but still the selected prime will tend to have less neighboring primes than expected for a random prime. These biases are detectable when examining the primes generated, but are not a security concern in RSA.

⁵ With $(r\bmod e)\in[2,e)$, $(r\bmod2)=1$, and $(r\bmod s_j)\in[1,s_j)$ for $0\le j<i$. The product of these distinct coprime moduli is $m$. Prime candidate $r\in[k_\min\,m,k_\max\,m)$ changes by multiples of $m$, among $t$ possible candidates. $t>2^{39.9}$, which makes it beyond reasonable doubt that there's a prime among the candidates, given the upper bound for $r_\max$. The order in which we scan them is random and secret among $>2^{39.9}$ possibilities, conjecturally defeating statistical tests of non uniformity.

⁶ This is very likely, to the point of making the contrary hard to test.

⁷ In an RSA context, it is considered acceptable to restrict to primes $r\equiv3\pmod 4$. This simplifies the strong pseudoprime test to an Euler test (or otherwise said, makes the straightforward Euler test more robust). This can be obtained by $r\gets ((1-v)\,e\bmod4)\,e+v+2$ rather than $r\gets ((v+1)\bmod 2)\,e+v+2$, and $m\gets4\,e$ rather than $m\gets2\,e$ (the later occurs in two steps).


Does Curve25519 only provide 112 bit security? In a recent mail on the IETF CFRG mailing list it was claimed that:

  The (currently missing) security considerations (or somewhere) should describe why Curve25519 is ok when used in contexts where we'd
  otherwise ask for 128 bit strength, (basically because it's close
  enough), and also why the 224 bit level is considered a good choice.
  There was a lot of debate on the list about that, and I've seen the
  issue come up elsewhere so this text will avoid re-litigating that and
  should be worthwhile even if it takes a little time to agree.

I read this such that Curve25519 only provides security on the 224-bit level i.e. 112 bit security.
But when I look up Curve25519 on Wikipedia I get to see in the very first line that

  Curve25519 is an elliptic curve offering 128 bits of security

Wikipedia itself references to Bernsteins original paper "Curve25519: new Diffie-Hellman speed records" which indeed confirms Wikipedia as follows:

  Every known attack is more expensive than performing a brute-force
  search on a typical 128-bit secret key cipher.

So my question is:
Does Curve25519 indeed provide significantly less security than 128-bit?

Some claim that Curve25519 has 112 bit security, others that it has 128 bit security; which is it?

Well, actually, neither - it's actually somewhere in the middle.

For a curve without known weaknesses (and Curve25519 doesn't have known weaknesses), then if the curve order has a large prime factor around $2^{2k}$, then the best known attacks against it take $O(2^k)$ time (where the O-notation conceals a constant which is a bit larger than 1, but is constant for the various types of curves), and so by convention, we say that such a curve as "k-bits of strength".

Now, for Curve25519, the curve order has a prime factor circa $2^{252}$; by the above standard metric, this yields a security of 126 bits.  This is slightly less than the 128 bit security that the curve P256 claims; however it is significantly more than the 112 bit security that was claimed on the IETF mailing list.

Is the difference between 126 and 128 bit security significant?  In my opinion, no; a work effort of 128 bits ought to be sufficiently large that a factor of 4 decrease in the attacker's time still should make this infeasible.

In addition:

  Every known attack is more expensive than performing a brute-force
  search on a typical 128-bit secret key cipher.

Makes a very good point; against an elliptic curve, the fundamental operation that is perfomed during the attack is an elliptic curve point addition; this is significantly more expensive than (say) testing an AES key.  And, I believe this remains true even if you factor in a 4-times speedup on the elliptic curve side.


Probability of SHA256 Collisions for Certain Amount of Hashed Values I wonder if you can help me figure out that question:

Is there a known probability function f: N -> [0,1], that computes the probability of a sha256 collision for a certain amount of values to be hashed? The values might fulfill some simplicity characteristics to reduce the complexity of the problem e.g. all of them are of equal difference to each other with a constant difference t or whatever is needed to somehow reduce it to manageable complexity.

In other words: How likely is it to have sha256 hash collisions in a "simple" set of n values?

Yeah, I'ld like to hear your thoughts about that :) Thanks for all helpful comments / answers in advance!

EDIT
Background is: I wonder if it is possible to decide when the change to a 'higher' hash function (like changing from sha256 to sha512) makes sense - not only by having an eye on experiments but by theory.

The wikipedia page for the Birthday problem gives the details, including the exact formula.

As an approximation you can use:

$$p \approx 1-\exp(-\frac{\tfrac{1}{2}n(n-1)}{2^{256}})
\approx 1-\exp\left(-\frac{n^2}{2 \cdot 2^{256}}\right)
\approx 1-\exp\left(-\tfrac{1}{2} \left(\frac{n}{2^{128}}\right)^2\right)$$

If $n \ll 2^{256/2}$ and thus $p \ll 1$ you can use the approximation $\exp(x) \approx 1+x$ and obtain:

$$p \approx \tfrac{1}{2} \left(\frac{n}{2^{128}}\right)^2$$

This means that the probability is negligible as long as you have significantly less that $2^{128}$ values. (For an idea of "how significantly" less, refer to the table on the Wikipedia page, "Desired probability of random collision".) That's the case for any realistic amount of data, so an unbroken 256 bit hash is good enough and there is no need to upgrade to 512 bits.