Ciphers providing Deniable encryption? I stumbled on the concept of Deniable encryption on Wikipedia, with the following scenario:

  Deniable encryption allows the sender of an encrypted message to deny
  sending that message. This requires a trusted third party. A possible
  scenario works like this:

  Bob suspects his wife Alice is engaged in adultery. That being the case, Alice wants to communicate with her secret lover Carl. She
  creates two keys, one intended to be kept secret, the other intended
  to be sacrificed. She passes the secret key (or both) to Carl.
  Alice constructs an innocuous message M1 for Carl (intended to be revealed to Bob in case of discovery) and an incriminating love letter
  M2 to Carl. She constructs a cipher-text C out of both messages M1, M2
  and emails it to Carl.
  Carl uses his key to decrypt M2 (and possibly M1, in order to read the fake message, too).
  Bob finds out about the email to Carl, becomes suspicious and forces Alice to decrypt the message.
  Alice uses the sacrificial key and reveals the innocuous message M1 to Bob. Since Bob does not know about the other key, he might
  assume there is no message M2.

I would like to have examples of ciphers providing this property. The Wikipedia page only gives softwares like filesystems.

Here's a relatively complete list of the papers on deniable encryption (plus papers containing a lower bound against some type of deniable encryption):

Deniable Encryption by Canetti/Dwork/Naor/Ostrovsky [CRYPTO 1997]
Separating Random Oracle Proofs from Complexity Theoretic Proofs: The Non-committing Encryption Case by Nielsen [CRYPTO 2002]
Lower and Upper Bounds for Deniable Public-Key Encryption by Bendlin/Nielsen/Nordholt/Orlandi [ASIACRYPT 2011]
Bi-Deniable Public-Key Encryption by O'Neill/Peikert/Waters [CRYPTO 2011]
On the (Black-Box) Impossibility of Sender-Deniable Public Key Encryption by Dachman-Soled [PKC 2014]
How to Use Indistinguishability Obfuscation: Deniable Encryption, and More by Sahai/Waters [STOC 2014]
Deniable Functional Encryption by De Caro/Iovino/O'Neill [PKC 2016]
Deniable Attribute Based Encryption for Branching Programs from LWE by Apon/Fan/Liu [TCC 2016-B]


Crack cryptographic hash functions using Toffoli gates? Might it be possible that reversible combinatorial circuits (or some emulating software) are going to be used to get the input of the white box?

I mean if I have constructed a proper reversible circuit then (in theory) I can obtain the input of whatever output I get. Am I missing the point?

Here is the relevant WP link for those interested: http://en.wikipedia.org/wiki/Toffoli_gate

Such a reversible circuit would have many additional output lanes. Since there are too many different values those can have(exponential in the number of extra lanes) you can't guess a complete output of such a circuit. Without a complete output of the circuit you can't reverse it. So your approach doesn't work.

If you could construct a reversible circuit with few additional output lanes, that'd break a hash-function. But there is no simple way construct such a circuit given a normal circuit.

  The Toffoli gate is universal; this means that for any boolean function f(x1, x2, ..., xm), there is a circuit consisting of Toffoli gates which takes x1, x2, ..., xm and some extra bits set to 0 or 1 and outputs x1, x2, ..., xm, f(x1, x2, ..., xm), and some extra bits (called garbage). Essentially, this means that one can use Toffoli gates to build systems that will perform any desired boolean function computation in a reversible manner.

Quoted from Wikipedia: Toffoli gate


Feige–Fiat–Shamir identification scheme: Question about a part of the ZK protocol My question (at the bottom) is in regards to the part of the protocol where the Verifier challenges the Prover by sending a bit b where b = 0 or b = 1.

Example for context

One Time Setup

p = 3
q = 5
n = 15
privKey = 8 (co-prime to n)
pubKey = privKey^2 mod n ⇒ 64 mod 15 = 4

  At this point, the verifier knows:
  n = 15
  pubKey = 4

Protocol: The following is repeated t times

Prover selects a random number < n
randNum = 11
Prover computes x as follows and sends x to Verifier
x = randNum^2 mod n ⇒ 121 mod 15 = 1
Verifier chooses a bit, b = 0 or b = 1, and sends it to Prover as a challenge
Prover computes (privKey^b • randNum) mod n as a response

  By choosing a bit b = 0 or b = 1 the Verifier chooses to see either:
  Case 1
  b = 0: randNum mod n ⇒ 11 mod 15 = 11 (if randNum is < n, verifier will receive randNum)
  OR Case 2
  b = 1:(randNum • privKey) mod n ⇒ 88 mod 15 = 13

Case 1: b = 0
As a response from Prover, Verifier receives: 11
Verifier computes:

11^2 mod 15 = (x • pubKey^b) mod n
11^2 mod 15 = (1 • 4^0) mod 15
121 mod 15  = 1 mod 15
1 = 1 //passes the test

Case 2: b = 1
As a response from Prover, Verifier receives: 13
Verifier computes:

13^2 mod 15 = (x • pubKey^b) mod n
13^2 mod 15 = (1 • 4^1) mod 15
169 mod 15 = 4 mod 15
4 = 4 //passes the test

My Question

In Case 1, the Verifier is actually checking that:

randNum^2 mod n = (randNum^2 mod n) mod n

which is essentially randNum = randNum

I don't understand why this part of the protocol is necessary. It seems that all the Prover has proved here is that they've picked a randNum. Anyone who doesn't know the privKey will always be able to do this.

I understand that there is only a 50% chance in any given round that this case will be chosen and that a false Prover (one who does not know privKey) will inevitably fail, but it seems that Case 2, where b = 1, is sufficient for the Verifier to be convinced that the Prover knows the privKey whilst gaining zero knowledge about the privKey and that no false Prover could pass this test.

Why is Case 1 a necessary part of the protocol? I must be missing something.

I hope that's clear, Thanks!

If $b$ was always the same value, you could convince the Verifier that you have the private key even though you actually don't!

Case $b = 1$:

Instead of sending $x = {\text{randNum}}^2 \bmod n$, the false Prover can send $x = {\text{randNum}}^2 / \text{pubKey} \bmod n$.

Assuming the Verifier sends $b = 1$, the false Prover can then send $\text{randNum} \bmod n$.

When the Verifier verifies the response, they check if ${\text{randNum}}^2 == (({\text{randNum}}^2)/\text{pubKey} \bmod n) \times \text{pubKey} \bmod n)$, which simplifies to ${\text{randNum}}^2 == {\text{randNum}}^2 \bmod n$, and that's obviously true. So even though the false Prover doesn't actually have the private key, the verification succeeded. But here's the catch: If $b$ turns out to be $0$ instead, they'd have to send $\sqrt{x} \bmod n$ in the final step. This is computationally infeasible.

As you observed, if the false Prover sends $x = {\text{randNum}}^2$ and $b$ turns out to be $0$, they can pass the verification. But if $b = 1$, the false Prover can't pass the final step, as they don't know $\text{privKey}$.

In summary, the false Prover has to commit to $b$ either being $0$ or $1$ before sending $x$. Each guess has a 50/50 probability of being correct. So after $t$ rounds, the chance of the Prover actually being a false Prover is $(1/2)^t$


Generating bilinear pairing parameters - running time of finding member of p-torsion group Update: Question completely rephrased.

I want to create the parameters for a bilinear pairing (the Tate pairing in this case).

In case you're interested I'm following this thesis, specifically the type $F$ curves (page 61) which has embedding degree $k = 12$. But it's probably not necessary to refer to the thesis to answer this question, since my question is likely elementary.

Using the method I've so far generated a finite field of size q where q is prime, an elliptic curve over $F_q, E(F_q)$, a prime of size $p$ so that $p | (q^{12} - 1)$ and a point $P$ on $E(F_q)$ of order $p$. Now the last step is to generate a point $Q$ which must also have order $p$ over the curve $E(F_{q^k})$ which must not be on $E(F_q)$. I've searched around and found the following suggested algorithm (where n is the number of points on $E(F_{q^k})$):

1) Generate a random point $R$ on $E(F_{q^k})$

2) Calculate $Z :=(n/p) R$

3) If $Z != O$, return $Z$ - otherwise, go to 1.

I.e. keep generating random points, scaling them by $(n/p)$ and repeating this until one gets a point different from the point-in-infinity, in which case the result should be a point of order $p$.

My question is - what is the running time of this algorithm? I.e. what is the per-iteration probability of getting $Z != O$ in step 3? I've tried to let it run but it doesn't find any points, it just keeps getting $O$ in step 2. Now, since calculation over $E(F_{q^k})$ are quite slow, I've only tried a few hundred iterations.

In this case $p$ and $q$ are primes of size 256 bits and $k = 12$. This means that $n$ is of the order of $2^{3072}$ (since n is the number of points on $E(F_{q^k})$). The p-torsion group has size $p^2$ meaning that such points are extremely rare and would be impossible to find by "random checking". But in this case, the algorithm doesn't operate by just generating a random point and checking if $p R$ is O. Rather, it generates a random point and multiplies by $(n/p)$. So it could be this increases the probability of finding a point.

But still, it seems to take forever! So it would be nice to know what the expected number of iterations is. Thanks!

In your step 2 replace $p$ by $p^2$. That should do it.

But you should really be looking for points Q on the sextic twist. See the original Barreto-Naehrig paper.


What is the difference between a permutation and a shuffle (transposition cipher) A non-cryptographic definition of a permutation is "2a: the act or process of changing the lineal order of an ordered set of objects. 2b: an ordered arrangement of a set of objects
The Wikipedia article on Random permutation states that "A good example of a random permutation is the shuffling of a deck of cards: this is ideally a random permutation of the 52 cards."
An ideal block cipher is a pseudorandom permutation.
Shuffling a deck of identical cards would result in output indistinguishable from the input. Applying an ideal block cipher to an all-zero (or all-one) plaintext block would yield a random ciphertext block, not the same all-zero (or all-one) input block!
What's an easy-to-understand difference between a shuffle (equivalently a transposition cipher) and a permutation in the sense meant by cryptographers?

A shuffle (or transposition function) re-arranges elements of the input. A permutation re-arranges the entire output domain.
For example, compare the following transposition function and pseudorandom permutation:
The transposition takes in a 4-digit number, and re-arranges the digits. 1234 might become 4213, but never 1692.
A pseudorandom permutation has a shuffled list of all possible 4-digit numbers, and an unshuffled list of all possible 4-digit numbers. It looks up the input number in the unshuffled list, finds the corresponding number in the shuffled list, and outputs that. 1234 might become 1692.


Is there an economic way to check if an eliptic curve point in jacobian coordiate is the same as a compressed point On an elliptic curve such as $y^2 = x^3 + b$, we define $a$ compressed point $P = (x, y)$ by it's coordinate $x$ and the parity of the $y$ coordinate. $y$ can be computed using $y = \pm\sqrt{x^3 + b}$ and choosing the right value of $y$ using the parity information.

We also define a point in Jacobian coordinate such as $P = (a, b, z)$ with $x = a / z^2$ and $y = b / z^3$ .

I would like to know if there is a known way to check if 2 points in these two set of coordinates are the same point that is cheap. Computing if the $x$ coordinates are the same is easy by checking if $x * z^2 = a$ .

To check if the $y$ coordinate are the same, the best I can come up with is to compute $y = a * z^{-3}$ and check if it has the same parity as the compressed point. However, it requires an expensive computation of the multiplicative inverse of $z$ to get $z^{-1}$. This seems rather overkill as it compute way more information than required. Only one bit is needed.

I was wondering if there is a known way to check if thee 2 points are the same that do not involve expensive computations such as the finding multiplicative inverse or a quadratic residue to decompress the point.

Computing the $z^{-1}$ is very cheap. We can do this by Euclidean algorithm, and in logarithmic time. But you can set $z=1$ in projective coordination. This make computations easy($O(1)$ since $z^{-1}=1$), and with this representation you can see the equality of points evidently.

  Note that, instead of computing $y=b*z^{-3}$ you can check  $y*z^3=b$. In this state, you don't need to finding multiplicative inverse.

Also in powerful programs such as MAGMA, $z$ is equal to $1$, by default.


What does "birational equivalence" mean in a cryptographic context? In a recent question on using the same curve for signing and ECDH it was noted for the Ed25519 curve and Curve25519:

  Nitpick: the curves are birationally equivalent, not isomorphic.

Now this term shows up quite often in cryptography, especially when one is concerned with the differences and transformations between various curve representations. So my question:

For a "cryptographer" who has never heard of "varieties" or "functional fields" what does "birational equivalence" state for the relation between two groups / rings / fields?

I have searched around a bit but usually most explanations use this advanced algebraic terminology and I'd just like to have a "simple" explanation / intuition for the day-to-day algebra in cryptography.

I feel that as it was my comment, I am obliged to answer this :-).

First of all, birational equivalence is really a geometric notion. As far as I know, there is no analogue for groups, rings or fields and therefore the cryptographic relevance is limited. It becomes relevant when speaking of geometric objects: for example, elliptic curves.

Given these geometric objects, we want to define what it means to be "the same". The usual terminology is that given two curves $E_1$ and $E_2$, they are "the same" when they are isomorphic. There is another way to equate objects, and that is by saying that they are "almost the same". This is what a birational equivalence does: two curves $E_1$ and $E_2$ are birationally equivalent when there is a map $\phi:E_1\rightarrow E_2$ between them which is defined at every point of $E_1$ except a small set of exceptions and there is an inverse map $\phi^{-1}:E_2\rightarrow E_1$ which is defined at every point of $E_2$ except a small set of exceptions. This definition is very close to that of an isomorphism, except for the fact that we allow some exceptions.

To make this more concrete, you could think of an isomorphism as a tuple of polynomials:

$$\psi:E_1\rightarrow E_2,\quad (x,y)\mapsto (f(x,y),g(x,y)),$$
where $f,g$ are polynomials in $x,y$. The inverse is also defined in terms of polynomials.

A birational map can be thought of as a tuple of fractions of polynomials, say

$$\phi:E_1\rightarrow E_2,\quad (x,y)\mapsto \left(\frac{f_1(x,y)}{f_2(x,y)},\frac{g_1(x,y)}{g_2(x,y)}\right).$$

This is defined at all points $(x,y)$ except for the ones where $f_2(x,y)=0$ or $g_2(x,y)=0$. The inverse is also a fraction of polynomials, and can therefore be undefined at certain points.

Now let's make this even more concrete, and follow the Ed25519 paper. The Curve25519 curve is defined by $$E_1:v^2=u^3+486662u^2+u.$$
It is birationally equivalent to the Edwards curve given by
$$E_2:x^2+y^2=1+\frac{121665}{121666}x^2y^2.$$
The birational equivalence is given by the map $\phi:E_1\rightarrow E_2$ defined by
$$\phi(u,v)=\left(\frac{\sqrt{486664}u}{v},\frac{u-1}{u+1}\right).$$
Notice that it is undefined for $v=0$ or $u=-1$, and therefore is not an isomorphism. The inverse map is defined by
$$\phi^{-1}(x,y)=\left(\frac{1+y}{1-y},\frac{\sqrt{486664}u}{x}\right).$$
Again, it is undefined for $y=1$ or $x=0$.

Finally, consider the twisted Edwards curve
$$E_3:-x^2+y^2=1-\frac{121665}{121666}x^2y^2.$$
There is a map $\psi:E_2\rightarrow E_3$ defined by $\psi(x,y)=\left(ix,y\right)$, assuming that $i$ is a square root of $-1$. This is clearly defined everywhere, and is an isomorphism.


Practical multivariate quadratic FHE – how does it compare to other FHEs? Came across this startup claiming practical FHE and then their blog post going into some additional details on it.

It was my understanding that practical FHE is still years/decades off. They said back in September 2015 that they would publish the details of their FHE cipher which they call “KFHE”, but it appears that the details still have not been released (as of June 2016). They have released the source code for their KFHE implementation, however. From it, it appears they are using multivariate quadratic FHE.

What is multivariate quadratic FHE and what is unique about this FHE compared to previous attempts? How does this hardness assumption compare to others that have been previously used in building FHE?

I've spoken to the CEO a couple times. They've contracted some prominent French cryptographers to vet their cryptosystem, but no security analysis or whitepaper has been released.

Their KFHE scheme is different than previous schemes because it uses a different hardness assumption that leads to better performance and smaller keys. Previous FHE schemes used hardness assumptions based on ideal lattices, but their scheme uses a different assumption based on the hardness of solving a system of quadratic equations in many variables. Whether their construction truly is a practical general-purpose FHE scheme is not clear, since perf numbers for general circuits are not available (as far as I know).

Schemes based on solving systems of multivariate quadratic equations have some nice properties, including the aforementioned performance benefits as well as conjectured resistance to quantum attacks, but have proven extremely difficult to get right. Many schemes based on these assumptions have been severely broken. However, there exist cryptosystems from this family that are widely believed to be secure.

The homomorphic properties of their scheme are used to build a kind of multi-user searchable encryption in their main product, Kodex. A user allows other users to search on their documents by homomorphically sharing document search keys. I don't know all the details, but my guess is this specific 'share' operation can be done efficiently because they avoid evaluating a circuit and just do stuff directly.

As with all shiny new things in cryptography, caution is called for. Editorializing a bit, I see little reason to believe this is snake oil. [Indeed, if they were only looking for a rubber stamp from Faugere and Perret it seems like something would have been made public already.] However, perfectly honest and forthright people have built many, many broken cryptosystems, so I recommend taking any claims with a moderately-sized grain of salt until given reason to do otherwise.


Is AES in CBC mode secure if a known and/or fixed IV is used? I have a need to encrypt credentials for a third-party app used by a secured internal app. Over on ITSec.SE, I was helpfully shown a scheme to encrypt the third-party credentials based on a hash of the credentials for the internal app.

I picked AES as the encryption algorithm, but the problem is that the password-based scheme doesn't produce a "secret" IV. So, the IV must at least be known to an attacker (stored alongside the encrypted data). A hash value used for password verification could work, or I could just generate a pseudorandom byte array and drop it in the DB as a new column. I was further considering, for simplicity, to use a constant IV.

What adverse effect will either of these choices have on the security of the encryption? Does AES depend, as many block ciphers do, on an unpredictable IV? Does it matter if the IV is stored as unencrypted plaintext?

Do not use a fixed IV. It can have seriously negative consequences. This is especially true for CBC mode.

That said, a random 128-bit IV stored in plaintext is typically what you want. The IV can be known to an attacker without breaking security.


what motivated the design decisions of RFC 8291 ("Message Encryption for Web Push")? Related question here.
I'm reading RFC 8291, which describes a protocol to protect web push messages sent between an application server and a user agent (typically a mobile browser or other mobile application), using an untrusted "push service" (think APNS or FCM) as an intermediary. The constraints appear to be as follows:

The user agent and the application server are assumed to have an out-of-band secure channel for initial setup (typically a direct TLS connection)
After initial setup, the application server needs to be able to asynchronously send messages to the user agent, achieving confidentiality and integrity

The RFC takes what seems to be a fairly complex route to solving this problem, using three different primitives: elliptic-curve Diffie-Hellman, HKDF, and AES-GCM:

During the initial handshake, the user agent generates a long-lived ECDH keypair and symmetric secret, then sends them to the application server over the secure channel
To send a message, the application server:

Generates an ad-hoc ECDH keypair and carries out ECDH with the user agent's public key, deriving a shared secret
Combines this ad-hoc shared secret with the long-lived symmetric secret using HKDF, deriving a key
AEADs the message with AES-GCM and sends it to the push service, which relays it to the user agent

As I understand it, ECDH is used for confidentiality and the symmetric secret is used for integrity (it authenticates the server to the client). One might think that ECDH is also used to achieve forward secrecy. But technically, this protocol is not forward-secret, since there is a long-term key (the private half of the user agent's ECDH keypair) that can be used to decrypt any message.
My question is: how does this protocol improve on transmitting a single symmetric key over the secure channel, then sending messages protected by a single AEAD (XChaCha20-Poly1305 seems especially attractive for this use case)? Is it because the user agent's private key is thought to be harder to attack than a symmetric shared secret (e.g., because individual client devices are harder to attack, or because it can be stored in a secure coprocessor)?

Although it is not forward secure against client-side compromise (i.e. disclosure of the user agent's long term private key), it is forward secure against server-side compromise (i.e. disclosure of all information available to the server).
Thus, for example, if ownership of the application server is transferred from one company to another and the user's trust relationship with the new company is not as strong as the old company, the user still has assurance that their old messages are not compromised.
Bidirectional forward security would seem to be preferable, but the the offline encryption implications of push messaging make this a constraint that is hard to achieve.


Knowing you can combine 2 signatures, Is it possible to remove part of the signature? Since my last post I've been more interested into RSA cryptography, but I'm questioning one thing.

Lets say we are using standard textbook RSA with no padding and with the standard signature generation in lets say the Microsoft crypto API and you got the part you want to remove by itself is it possible to remove that from another signature with the same thing on the beginning or end?

As soon as you are working using standard textbook RSA without padding (or hashing), you can fully exploit the malleability of the RSA cipher.

So, let's say you have a message $m$ which is equal to $a\cdot b$, for $a,b$ two values you know. If you can get the signer to sign both $a$ and $b$, you can compute the value of the signature of $m$, thanks to that malleability:
$$m^d = (a\cdot b)^d = a^db^d \mod N$$

Now regarding the possibility to "cancel out a factor" thanks to this malleability, it is partly possible and is actually used in the so-called "blind RSA signatures". (Read it, it explains all the maths.)
However it requires to be able to get the signer to sign a specially crafted message.


Protocol for Sharing Blinding Factor with RSA What is the protocol for choosing blinding factor when RSA is applied with key blinding?

(Related question: How would you find the Blinding factor R in RSA blind signature algorithm?)

Since blinding factor R should be randomly chosen, who has control
over how R is chosen - the client (public key user), or the server
(private key user)? If the client has control over the choice, the
client can defult to the same value of R every time & thus defeat
the purpose of choosing a random R.
Given that R must be a shared value for every encrypt/decrypt
operation (sort of an IV like parameter for symmetric ciphers),
which protocols supported the     transmission of a blinding factor?

First of all, you need to understand what's the point of key blinding in the first place.

First of all, you have a server (who has a private key, and who is willing to decrypt messages), and you have a client (who has a value who he wants decrypted, but is unwilling to tell the server what that value is).  The client might not want to tell the server what the value is to preserve anonymity (e.g. Chaum's ecoin idea, which uses a similar idea with signatures), or perhaps because he is afraid that the server might leak that info (e.g. through a side-channel).

So, what the client does is pick a random value $R$ (and keeps it to himself); the encrypted message $C$, and computes $R^e \cdot C \bmod N$ (where $e, N$ are from the server's public key); we then asks the server to do an RSA decryption of that.

Then, the server computes $(R^e \cdot C)^d \bmod N = R \cdot C^d \bmod N $ ($d$ is server's private key), and sends that back to the client.

Then, the client computes $R^{-1} \bmod N$, and then $R^{-1} \cdot (R \cdot C^d) = C^d$, which is the decrypted (padded) message $P$.

Because we allow $R$ to be any value (relatively prime to $N$), then $R^e \cdot C$ can also be any value, and so the server gets no information about what he's decrypting.

With that background in mind, let us go through your questions:

  Who has control over how $R$ is chosen?

As you can see from the above example, the client does.

  If it's the client, what's preventing him from picking the same value of $R$ every time.

Absolutely nothing.  There's also nothing preventing him from publishing the value $P$ in the Times, if he were so minded.  $R$ is there to protect the client's data; if he doesn't do things correctly, it's his own data that suffers.

  Given that R must be a shared value for every encrypt/decrypt operation

Actually, if you go through the above, $R$ is used only during the decrypt operation (or the signature operation); the original encryptor (the guy who created $C = P^e$ in the first place) need not know it (or even if RSA blinding was being used).  The client needs to use the same $R$ to compute both $R^e \cdot C$ and $R^{-1} \cdot (R \cdot C^d)$, however that's both in the decryption process, and the client never needs to give $R$ to anyone else (in fact, that would rather mess up what $R$ is trying to do)


Keyless Signature Infrastructures as a secure Post-Quantum Scheme I came across a company that relies on hashing, similar to block chain technology.  They explicitly stated in their white paper that hash based cryptographic schemes are inherently post-quantum schemes.

Counter to this, is an article co-authored by Schneier (linked in blog post) that lends support to the idea of Grover's algorithm enabling cryptanalysis of "Keyless Signature Infrastructure" (KSI).  Is the position that KSI is inherently a PQC scheme tenable simply because no conventional device is known to have broken it?

It seems like this argument is sleight of hand, given it does not rely on a security reduction of an NP-Hard problem which as I understand is essential to any PQC scheme.  Is their use of a modified blockchain method actually post-quantum secure?

I would just like to know on what basis they can say it is PQC without any NP problem reduction.

I believe that the point you're making is assuming that a Quantum Computer could solve any problem in NP that's not actually NP-complete quickly (or, at least, in polynomial time).  That's not known to be true; Quantum Computers would be able to solve some problems (such as factorization) in polynomial time, if $P \ne NP$, there's a whole range of problems in NP that's neither P nor NP-complete.


Guaranteed decryption time schedule Suppose you want to store information in, say, safe container for  a certain time, after which you want information to be accessible.

Let's assume simple idea and fill details by yourself. Take some space of strings (for example 10 characters in size, containing capital and ordinary letters) and encrypt a container with randomly generated password that is never stored - for example by asking other person to type the password without revealing it, or by closing your eyes and enter random characters).

Then start breaking by brute force. It doesn't guarantee perfect timing, but in the average You may estimate how long it would take to break the password and open stored content. By clever manipulation of string's space [ed: of the password] you may probably scale it from seconds to epochs.

You may assume some cascade/ hierarchy system: simple random input ( say: 3 chars of low dimensional space) is used as a seed for cascade of the systems you have to break. As breaking password from 3 char space is deterministic in fraction of seconds, such cascade may give you a loosely speaking, a way of measuring a time range of second with not so big error. So cascade of such cryptography systems may work as a clock, implemented on non safe scheduling system.

Questions:

Are there known any protocols or algorithms with precisely narrowed time estimate above?
Is it possible to design such brute force breaking scheme it guarantee that it will be successful after t_min but before t_max?

For given system working on isolated ( this one) problem it provides a method of measuring time without use of values from internal clock ( which is controlled by user, hackers etc). Using such multiple systems of cascades method we may in probabilistic way guarantee that box is open not earlier than certain amount of processor cycles is used. That's the goal of such idea.

Processor cycle count measurement by brute force breaking scheme :)

Are there known any protocols or algorithms with precisely narrowed time estimate above?

Of course not, because it would depend on the details of the system performing the brute forcing / dictionary attacks. Your comment: "Processor cycle count measurement by brute force breaking scheme" basically contains the answer.

  Is it possible to design such brute force breaking scheme it guarantee that it will be successful after t_min but before t_max?

Same answer of course, but you can certainly create a protocol which requires a certain proof-of-work. And that's precisely what the current block chain technology is all about. But proof-of-work relates to the amount of work performed, not the amount of time that it took.

You could of course also use a trusted third party to release information - such as a key - at a certain time. Not all protocols allow for such a third party to exist though.


Secret Sharing between $x$ parties So for an unknown number of parties $x$, I make $x-1$ random $n$-bit strings represented by {$r_1, r_2,...,r_{x-1}$}. Where  $s$ is the complete string split up between $x$ parties (yes?).

I then send each party one of the fragments $s_i$, so party 1 would get $s_1$, party 2 would get $s_2$ etc. all the way through to $s_{x-1}$. Along with these fragments. I then send $r_1⊕...⊕r_{x-1}⊕s$ to party $x$.

The message $s$ can then be reconstructed by XORing all the fragments together. Any singular $x-1$ party should not have enough information to reconstruct a message. But then what happens if there are only two parties? if $x=2$, then the message $s$ would be divided between $x-1=1$, which means that that singular party would acquire the entire $n$-bit string on their own, or am I over looking something that prevents this so that any $x-1$ party does infact not have enough information to reconstruct the message, even if it was only 1-bit ($n=1$) in length?

What about if 3 parties share two keys $a,b$? Assuming their fragments are $f_j$ for $a$ and $g_j$ for $b$ (that is these are $r_j$ fragments, and party 1 has $g_1$ and $f_1$, party 2 has  $g_2$ and $f_2$ etc), could they manage to derive the secret if each party makes $z_j=f_j⊕g_j$, using the $z_j$ values of each?

So for an unknown number of parties $x$, I make $x-1$ random $n$-bit strings represented by {$r_1, r_2,...,r_{x-1}$}. Where  $s$ is the complete string split up between $x$ parties (yes?).

  I then send each party one of the fragments $s_i$, so party 1 would get $s_1$, party 2 would get $s_2$ etc. all the way through to $s_{x-1}$. Along with these fragments. I then send $r_1⊕...⊕r_{x-1}⊕s$ to party $x$.

That is not how it is typically done.  One issue is that two parties (say, party 1 and party $x$) get partial information of the shared secret, that is, the part that was masked by $r_1$.

Instead, what we do is make $x-1$ random strings (each as long as the secret $s$).  Then, we send party 1 the string $r_1$ (not $s_1$), party 2 would get $r_2$, etc.  And then send $r_1 \oplus r_2 \oplus ... \oplus r_{x-1} \oplus s$ to party $x$.

This can be seen to yield no information about $s$ to any $x-1$ parties, and still makes $s$ recoverable to someone with all $x$ shares.

Studying this version of the protocol may answer your questions.


ANSI X9.31: the purpose of the date/time vector in the PRNG? What is the exact purpose of the date/time vector $dt$ in the ANSI X9.31 PRNG?

$$ I := E_K(dt) $$
 $$ R := E_K(I \oplus V_{old}) $$
 $$ V_{new} := E_K(R \oplus I) $$

Specifically, the document seems to imply that the seed $V_*$ and key $K$ must be kept secret, but makes no claims on the secrecy of the $dt$ vector, only that it should be increased on each iteration. Can it be known by an adversary? Are there any implications if it is known to an adversary?

From ANSI X9.31:1988, Appendix A.2.4 (Generating Pseudo Random Numbers Using the DEA):

"Let DT be a date/time vector which is updated on each iteration."

The purpose of $dt$ is to supply a value that is different each time the algorithm is seeded, so as to generates a different sequence, even if $V_*$ (the initial value of $V_{old}$) is a fixed secret.

The algorithm seems to be secure even if $dt$ is known, and predictable, e.g. a 64-bit counter starting from 0; at least, that's the design goal. However it must not be possible to return $dt$ to an earlier value. In other words, $dt$ needs to be a "number used once", sometime called nonce.

Beware that an adversary could set the clock, hence $dt$. In the absence of a specific mechanism, that might allow her to re-generate a previous sequence!

It is probably best if the adversary can not choose $dt$ (and that makes it much easier to insure that $dt$ is unique).


Attack on security model for RSA-FDH I recently read in Cryptography textbooks and online videos that compared to Textbook RSA which is insecure against Chosen
Plaintext Attacks (CPA) and Chosen Ciphertext Attacks (CCA), RSA-FDH is Existentially Unforgeable Under Chosen Message Attacks
(EUF-CMA) if the hash fuction is uniformly random.

However, to my surprise, on online Cryptography forums and some Cryptographers say that the security model behind RSA-FDH, so EUF-CMA
can be broken if one can find collisions in the hash function itself. The thing is, I have not been able to find such examples or even
understand how this is even possible. I read in a lecture slide online that if we ask signatures $σ_1$, $σ_2$ for $m_1,m_2 \in \mathbb{Z}_n^*$ and
output $(m^*, σ^*) := (m_1 \cdot m_2 \mod{(N)},\ σ_1 \cdot  σ_2 \mod{(N)})$. But then I still don't know how it practically applies to RSA-FDH IF the hash function has collisions.

This is
a) no attack on the security model, but an attack in the security model of EUF-CMA, and
b) a generic attack on any signature scheme that signs the hash of a message instead of the message itself (as done in RSA-FDH).

The idea is that if you can find a collision for the used hash function $H$, i.e., two messages $m_1, m_2$ such that $H(m_1) = H(m_2)$, then they have the same signature: $\sigma = \textrm{sign}(sk,m_1) = \textrm{sign}(sk,m_2)$.
To see this consider RSA-FDH as example: The signature on $m_1$ is $\textrm{sign}(sk,m_1) = (H(m_1))^d \mod N$ for private exponent $d$ and modulo $N$. The signature on $m_2$ is $\textrm{sign}(sk,m_2) = (H(m_2))^d \mod N = (H(m_1))^d \mod N = \textrm{sign}(sk,m_1),$ where the mid equality follows from $m_1,m_2$ being a collision.

In the EUF-CMA setting you are allowed to ask for signatures on arbitrary messages and have to come up with a signature on a new message. So given collision $m_1,m_2$, you ask for a signature $\sigma$ on $m_1$ and then output the pair $(m_2, \sigma)$ as forgery.


Can I prove that a message is part of a set of known messages without disclosing the message? If Alice sends an encrypted message to Bob, how can Bob prove to Charlie that the message he received from Alice is part of a set of predefined messages, without disclosing the encryption key or the message itself.

Let's say we use El Gammal encryption scheme and let's say the predefined messages are M = {1,2}. Bob's pair of keys are x and y = gx.

Alice encrypts message m $\in$ M and sends the tuple (c,e), where c = gr, e = yr * m and r = random.

How can Bob prove that the decryption of (c,e) $\in$ M, without revealing the value of m ? Maybe some sort of zero-knowledge proof ?

Yes, this can be done. For your simple example, what you want amounts to an "OR proof", a proofs that shows that one of two statements is true. Let $(c, c')$ be your ciphertext; to show that it encrypts either 1 or 2, you just have to prove that "$(g,h,c,c')$ is a DDH tuple OR $(g,hc,c'/2)$ is a DDH tuple".

Proving that a tuple $(g,h,g',h')$ is a DDH tuple is the classical "proof of same discrete logarithm in different bases" (you prove that $\log_g(g') = \log_h(h')$) (see e.g. this answer). To perform an OR proof, the idea is simply to perform two proofs for the two statements in the clause in parallel, but sending a challenge that binds only the prover to, say, the sum of the challenges. This gives him the freedom to choose one of the challenges before the execution of the protocol, and therefore to forge the corresponding proof, but not both; therefore, the prover will be able to forge at most one proof, and the verifier cannot know which one. See for example this article.

This generalizes to OR with arbitrarily many clauses, and so to "sets of messages" of arbitrary size, but the size of this proof is linear in the size of the set of messages. I know that if you use the additive ElGamal instead (a ciphertext is of the form $(g^r, h^rg^m)$), there are way more efficient methods: this article, for example, provides a zero knowledge proof of membership of an (additive) Elgamal plaintext to a known set of size $n$ in communication $O(\log n)$. The same holds for other cryptosystems with additive properties; for the standard ElGamal scheme, there might also be efficient proofs (in fact, there are necessarily such proofs, as we have ZK arguments for any statement in communication polylog, but the constants involved in these generic construction would be highly impractical here), but I do not know much about this specific case.


Why is it that researchers prefer finding secure software solutions over secure hardware solutions? My understanding is crypto researchers tend to prefer solving a problem in software without the need for secure hardware.  Why is this? What is the big problem with using secure hardware if the hardware components are cheap and can be easily made?

I think this question is setting up a false dichotomy.

It's not that a researcher has an opinion as to whether they prefer software or hardware implementations. The choice of implementation depends on the requirements of the specific cryptosystem you're building.

For example, if you're designing a system to encrypt voice traffic on a mobile phone network, then clearly that's going to favour hardware based solutions.

Alternatively, if you're building an open-source program that handles file-encryption, this is going to strongly favour a software based solution.

Some requirements drive hybrid solutions. Two factor authentication systems such as Yubikey or RSA's Securid use a blend of hardware and software.

It's worth pointing out that all software requires hardware at some level. At what point does the software solution become a hybrid solution?

These days, the lines are becoming more blurred. Modern processors now contain hardware RNGs and instructions that implement the core operations in AES.

So even applications that appear on the surface to be composed entirely of software could utilise these instructions if they were available.

To summarise, I think the distinction between drawn in the question is false and that all cryptography uses a blend of hardware and software. The precise blend is controlled by the requirements of the system. Over time, more of the crypto is finding its way in to hardware due to better standardisation.


stream cipher and block one, which one is faster to encrypt/decrypt? As the title says, I would like to know which one is faster.  I read in some book it indicates the stream is faster since it encrypts one bit at a time; the others show block is faster since it is using "block".

Thanks

It depends on what you're trying to do.

In general, block ciphers are more versatile: anything you can do with a stream cipher can also be done with a block cipher in a suitable mode of operation.  So if there was no other advantage to "pure" stream ciphers (i.e. ones that are not based on block ciphers), everybody would just be using block ciphers.

The main advantages of pure stream ciphers over block ciphers are usually 1) raw speed, and 2) code / circuit size.  The versatility of block ciphers tends to come with some overhead cost, and if you're targeting a very low-end device, you can often squeeze some extra speed out and/or save some memory by only using a purpose-built stream cipher.

(Of course, that only really works if all you need is a stream cipher.  In the past few decades people have gradually woken up to the fact that in many — if not most — cases it's not enough to just hide the data by encrypting it, but you also need to protect it against tampering.  Block ciphers can do that, when used in a suitable mode, but most traditional stream ciphers can't.  So either you need to implement an extra integrity protection layer on top of the stream cipher encryption, or use an "authenticated stream cipher" that has it built in.  Either way, that adds extra complexity.)

So, at least in some situations, stream ciphers can be faster than block ciphers — and, in fact, that's their main selling point.

That said, there are also several situations where block ciphers can beat stream ciphers in speed:

Many modern high-end CPUs provide hardware acceleration for the AES block cipher.  If you're using such a CPU, using that is almost certainly going to be faster than any encryption you could implement purely in software.

(Of course, a similarly hardware-accelerated stream cipher might be even faster yet, and would likely require less space on the CPU chip, but it wouldn't be useful for nearly as many purposes as a block cipher like AES is.  So if you're only going to add extra hardware for one crypto primitive to your general purpose CPU, it might as well be a block cipher.)
Stream ciphers typically generate a sequential keystream, always starting from the beginning of the stream.  So even if you only need to decrypt, say, the last kilobyte of a multi-megabyte message, you still need to generate all those megabytes of keystream first.

There are various ways to work around that, such as splitting long messages into smaller chunks and encrypting those separately.  But many block cipher operating modes offer something even better: the ability to decrypt any block (of, say, 16 bytes for AES) of the ciphertext independently of the others.  If you need fast random access to small pieces of the encrypted data (e.g. to query an encrypted database), a block-cipher-based encryption scheme is probably the way to go.
The same features of many block cipher modes that allow random access also allow decryption (and in some cases also encryption) to be done in parallel by as many processor cores as you happen to have available.  Stream ciphers tend to be limited by their sequential nature to a single core per keystream.  Again, on modern multicore processors, that can make block ciphers significantly faster even without hardware acceleration.

Ps. For more information, you might also want to take a look at this earlier answer I wrote about the differences between block ciphers and stream ciphers, as well as the answers and wiki pages linked from it.


Should I bother implementing DH + AES, or leave it to a library like Crypto++ I'm making a C++ back end for an application that'll heavily rely on AES-256 and DH. Should I trust third party libraries, or spend (lots of) time to learn about cryptographic implementation and write my own? Is there any reliable authority that can audit the security of a library (like Crypto++ in this case)? I hope this question doesn't come off as opinion based, but it's quite hard to find reputable data on this. I have no idea where to even start.

TL;DR: What's worse: risking vulnerabilities in a third party library, or risking novice mistakes in a custom implementation?

Rather risk vulnerabilities of third party library than implement your own.
If you feel novice on this field, only implement cryptography yourself as an learning exercise.

Why:

Mistakes, lack of know-how and maintenance.

It is very easy to make novice mistakes in custom implementation of
cryptography. Even battle scarred veterans of the field do mistakes
now and then. The amount of software quality assurance (including
testing, reviews, ...) needed to ensure quality of cryptographic
library is very significant.
When vulnerabilities are found third party cryptographic libraries are (often) updated. The user of the software may be able to update the library to newer version and (assuming API compatibility) fix the issue. If cryptographic functionality is built inside the program, all vulnerabilities always require fixes to the program itself.
Cryptographic libraries have to protect them against attacks almost no other software needs to (like timing attacks, and pretty recently, sound). New attacks are found now and then.
Even when no new attacks are not found, the cryptographic practices develop (towards safer). For instance, NIST considers 1024 bit RSA modulus fairly safe to use now, but in 1.1.2014, the minimum NIST accepts will be 2048 bit. Similarly, other parties "upgrade" minimum key length requirements from time to time.


CVE-2014-1295 (Apple's Secure Transport and Triple Handshake Attack) Apple is releasing some updates today. They have not published the bulletins yet, but they are available here: https://gist.github.com/FredericJacobs/11189734.

In the writeup for CVE-2014-1295:

Security - Secure Transport
...

Impact: An attacker with a privileged network position may capture
data or change the operations performed in sessions protected by SSL

Description: In a 'triple handshake' attack, it was possible for an
attacker to establish two connections which had the same encryption
keys and handshake, insert the attacker's data in one connection, and
renegotiate so that the connections may be forwarded to each other.
To prevent attacks based on this scenario, Secure Transport was
changed so that, by default, a renegotiation must present the same
server certificate as was presented in the original connection.

How is it possible to run two instances of a protocol and get the same parameters? Wouldn't nonces specifically neutralize this attack?

(And sorry about the crummy tagging).

The attacker acts as a man-in-the-middle and can forward the clients nonce to the server and the servers nonce to the client. As a result both parties establish a connection with the attacker using the same nonces.

Because of a weakness in the TLS protocol, the two connections can have the same key, and this key is known to the attacker.

After resumption TLS 'forgets' that the connections were established with the attacker, and did not prevent renegotiation, e.g. using client authentication, between two honest participants. This is corrected by the patch that requires a renegotiation to present the same server certificate as was presented in the original connection.


How to verify a shared secret using only AES? I have two devices that need to verify that they both are in possesion of the same secret key. One of the devices is a very limited embedded device that only has AES128 available, no SHA or other hash variants.

My idea is a basic two-way challenge-response scheme:

Device 1 generates 8 bytes of random data (C1), and sends it to Device 2
Device 2 generates 8 bytes of random data (C2), and calculates R1 == AES(key, C1 || C2)
Device 2 sends R1 and C2 to Device 1
Device 1 calculates AES(key, C1 || C2) and verifies that this matches R1
Device 1 calculates R2 == AES(key, R1)
Device 1 sends R2 to Device 2
Device 2 calculates AES(key, R1) and verifies that this matches R2

Or put another way:

D1->D2: C1
D2->D1: C2, AES(key, C1 || C2)
D1->D2: AES(key, AES(key, C1 || C2))

My thinking is that this is a form of CBC-MAC, where each device offers a random challenge to the other that prevents replay attacks. Since it's just one block of data being processed, the CBC-MAC weaknesses aren't a problem.

Is this a sensible way of verifying the shared secret, or should I be doing something different?

Why over-complicate it like that,

D1 and D2 generates random 64-bit P (half the block size of AES)
they send it to each other
both generate AES(key,P_own||P_other) and again send to each other (note that these are different for each)
then both can verify that what they received is equal to AES(key,P_other||P_own)

Upside here is that it is a fully symmetric protocol.


Does there exist a CSPRNG that does not require generating prime numbers, but also does not depend on any other cryptographic primitives? The following excerpt is taken from the “Cryptographically secure pseudorandom number generator” article on Wikipedia:

  CSPRNG designs are divided into three classes:

  those based on cryptographic primitives such as ciphers and cryptographic hashes,
  those based upon mathematical problems thought to be hard, and
  special-purpose designs.

  The last often introduces additional entropy when available and, strictly speaking, are not "pure" pseudorandom number generators, as their output is not completely determined by their initial state.

I am interested in the question: does there exist a cryptographically secure pseudorandom bits generator that satisfies all of the three following requirements?

It belongs to class 2 according to the classification described above. Assuming that CSPRNG uses multiple iterations of some function $F$ to generate the output of the desired length, this requirement implies that the description of $F$ does not mention different versions of the function that are explicitly constructed for different word sizes. Examples of algorithms that satisfy this requirement: Blum Blum Shub, Blum–Micali algorithm;
It does not require generating prime numbers (or testing primality of any number);
If the algorithm uses any precomputed values, then there should be an open algorithm that demonstrates how these values are generated (with the detailed explanation of why it is required to use these values and why other values might impact the desired properties of the output).

Yes, at least for a definition of "based on a particular mathematical problem" allowing the problem to be breaking the generator!

Restricting to constructions that can be efficiently implemented, one of the simplest conjecturally Cryptographically Secure Pseudo Random Number Generator in the literature is the Alternating Step Generator, proposed by Christoph G. Günther: Alternating step generators controlled by de Bruijn sequences, in proceedings of Eurocrypt 1987. Its best known cryptanalysys is by Shahram Khazaei, Simon Fischer, and Willi Meier: Reduced Complexity Attacks on the Alternating Step Generator, in proceedings of SAC 2007

The ASG consists of three Linear Feeedback Shift Registers, which have a well known reduction to arithmetic in $GF(2^k)$. To produce a bit:

advance LFSR2
according to it's low-order bit, advance LFSR0 or LFSR1
output the XOR of the low order bits of LFSR0 and LFSR1

To choose the (public) LFSR parameters, select the desired security parameter $n$. Then pick three binary primitive polynomials of degree $n_0$, $n_1$, $n_2$ with $\alpha\,n<n_0<n_1<n_2$ so that $2^{n_0}-1$, $2^{n_1}-1$, $2^{n_2}-1$ are pairwise coprime. The best known attacks are for $\alpha=\frac32$, but $\alpha=2$ is more reasonable.
Note: in the initial exposition, LFSR2 is modified to generate a de Bruijn sequence, that is the output sequence has an extra zero inserted after $n_2−1$ consecutive zeroes. But this detail makes no cryptanalytic difference, since that point in the sequence is reached with negligible probability for $n_2$ large enough to thwarts attacks guessing the state of a single LFSR.

Per comment: Checking if two integers are pairwise coprime does not require "testing primality of any number". It can be done with Euclid's algorithm (or others that efficiently compute the Greatest Common Divisor), and checking that the GCD is 1. Also, parameter choice is performed just once, then we can have multiple instances of the generator using these parameters and different keys.

Example, with the help of the compact table of primitive binary trinomials compiled by Jörg Arndt (and a caveat: I have no clear-cut argument that using trinomials leaves the ASG secure): $n=192$, $n_0=385$, $n_1=386$, $n_2=393$ and

LFSR0: $x^{385}+x^{142}+1$
LFSR1: $x^{386}+x^{83}+1$
LFSR2: $x^{393}+x^{91}+1$
$n_0$ and $n_1$ are minimal given the choice $n=192$ and $\alpha=2$. $n_2\in\{387, 388, 389, 392\}$ was not used due to absence of trinomials. $n_2=390$ was not used because $\gcd(2^{386}-1,2^{390}-1)=3\ne1$. $n_2=391$ was not used so that the center terms (otherwise minimal) are farther than 64-bit from each side (in hope to ease constant-time software implementation).

The key is the initial state of the three LFSRs (with say the high-order bit of each LFSR set to the complement of the XOR of the others in order to ensure non degenerate states). This is an inconveniently long key, of $n_0+n_1+n_2-3>3\,\alpha\,n$ bits, and the security conjecture is for uniformly random independent key bits.

Some formal definitions of a CSPRNG (and practical robustness) require it's key to be of size equal to the security parameter. If that's wanted, coming up with a safe initialization procedure starting from a key of $n$ bits is non-trivial: we need some auxiliary CSPRNG to expand from $n$ to $n_0+n_1+n_2-3$ bits (from 192 to 1159 in the above example).


Attack on envelop mac As I am reading the Paper: MDx-MAC and building fast MACs from hash
functions

I am having trouble understanding the Attack on the Envelope Method (4.3). In particular, I am not sure what chaining variables are referring to and what Prerequisites have to be met in order to execute the attack.

Maybe a more detailed/ rephrased explanation could help me to understand the gist of the attack.

The MAC under attack is built from a hash $h$ (assumed to process a hashed message by splitting it in blocks processed only once, as most hashes do), with a key split into $K_1$ and $K_2$ of equal size. It computes the MAC of a message $x$ as $$\operatorname{MAC}_{K_1\mathbin\|K_2}(x)=h(K_1\mathbin\|x\mathbin\|K_2)$$

The attack in the paper recovers $K_1$ and $K_2$ from an oracle accepting to compute the MAC, in 3 steps

We make online queries to the oracle until we find $x$ and $x'$ with the same MAC, and such that this occurs due to a hash state collision before $K_2$ is hashed. The later condition is testable by a few extra queries to the oracle. It is chosen $x=x_1\mathbin\|x_2$ with a hash block frontier between $x_1$ and $x_2$, with $x_1$ large enough to find a collision, and $x_2$ used to test for a hash collision before the frontier, per the criteria that if $h(K_1\mathbin\|x_1\mathbin\|x_2\mathbin\|K_2)=h(K_1\mathbin\|x_1'\mathbin\|x_2\mathbin\|K_2)$ for a few distinct values of $x_2$, then most likely there was a hash state collision before the frontier.
We find $K_1$ by offline exhaustive search, with the selection criteria that $h(K_1\mathbin\|x)=h(K_1\mathbin\|x')$ (changing $x_2$ and/or using a second collision similar to that in 1 to weed out false positives).
We find $K_2$ by offline exhaustive search, with the selection criteria of computing the correct MAC for a few examples kept from step 1.

For a hash with $s$ bits of internal state at block boundaries and a key of $k$ bits, step 1 costs $\mathcal O(2^{s/2})$ oracle queries, and steps 2/3 costs $\mathcal O(2^{k/2})$ hash computations. Truncating the MAC width to a fraction of $s$ increases the attack cost, but does not change these asymptotics.

The attack is practical if $s=64$, $k=128$, and it can be made $2^{32}$ oracle queries.


Possible to check if $a \in \mathrm{QR}_n$? It is possible to check $a \in \mathrm{QR}_p \text{ iff } a^{(p-1)/2} \equiv 1\ (\bmod\ p)$ if $p$ is a prime.

$n$ is a large RSA modulus. Is it also possible to check if $a \in \mathrm{QR}_n$ if the factorization of $n$ is unknown?

It is possible to check $a \in \mathrm{QR}_p \text{ iff } a^{(p-1)/2} \equiv 1\ (\bmod\ p)$ if $p$ is a prime.

Yes, you have already written down the check, which is known as Euler's criterion.

  $n$ is a large RSA modulus. Is it also possible to check if $a \in \mathrm{QR}_n$ if the factorization of $n$ is unknown?

You can use the Jacobi symbol if the factorization is unknown to find out if $a\in \mathrm{QNR}_n$, i.e., if the Jacobi symbol is $-1$.

But if the Jacobi symbol yields $+1$, then you can either have a quadratic residue or a pseudosquare, i.e., a quadratic non-residue yielding Jacobi symbol $+1$.

Distinguishing pseudosquares from quadratic residues modulo an RSA modulus if the factorization is unknown is known as the quadratic residuosity problem which is believed to be a hard problem and is the basis for some cryptographic constructions such as the Goldwasser-Micali encryption scheme.

For generic algorithms this problem can be shown to be equivalent to factoring.


Recovery of private key in AES-CBC from two ciphertexts with different IV, but identical plantext I have a system that encrypts messages for a given user using key K using AES-CBC in response in an external stimulus.  Each message has a randomly generated IV.  The user never decodes these messages, they are used as opaque token.

Under certain circumstances it is possible Mallory can observe the system and infer that two messages (M1, M2) have identical plaintext (P).  My concern is given two messages that are known to have identical plaintext and same key, is it possible to recover the K?

E: AES-128-CBC

IV: randomly generated IV one block size.

IV1 + E(K, P, IV1) => M1

IV2 + E(K, P, IV2) => M2

If it possible to recover K, what mitigations could I put in place?  For example would a nonce within the plaintext help, i.e.:

IVx + E(K, (Nx + P), IVx) => Mx

How would I calculate the size of nonce determine computational difficulty for recovery (within P there is a CRC32 to determine tampering)?

To give a short answer, if an attacker knows ($P$, $IV_1$, $M_1$) and ($P$, $IV_2$, $M_2$) such as :

$M_1 = E_K(P, IV_1)$

and

$M_2 = E_K(P, IV_2)$

where $E_K$ is the AES-CBC encryption function with the key $K$ then he doesn't learn anything about $K$ because AES is resistant to known plaintext attacks. As long as the $IV$ is randomly chosen, encrypting the same message with the same key $K$ do not reduce the security of AES-CBC.

Here is a longer answer : Why is AES resistant to known-plaintext attacks?


Why is an RSA public key BITWRAP-ed in ASN.1 DER encoding? While playing around with creating an RSA public key, and decoding it using a home brew ASN.1 decoder, I ran into the fact that the public key is BITWRAP-ed. BITWRAP seems to be an OpenSSL modifier, and I wonder why it is needed, what the rationale is?
This page describes what BITWRAP is but not why it is needed.
Why can't $n$ and $e$ be encoded in a regular non-BITWRAP-ed ASN.1 sequence?
Below example shows the BITWRAP modifier in an ASN1 definition (copied from OpenSSL docs):
asn1=SEQUENCE:pubkeyinfo

# BITWRAP here
[pubkeyinfo]
algorithm=SEQUENCE:rsa_alg
pubkey=BITWRAP,SEQUENCE:rsapubkey

[rsa_alg]
algorithm=OID:rsaEncryption
parameter=NULL

[rsapubkey]
n=INTEGER:0xBB6FE79432CC6EA2D8F970675A5A87BFBE1AFF0BE63E879F2AFFB93644\
D4D2C6D000430DEC66ABF47829E74B8C5108623A1C0EE8BE217B3AD8D36D5EB4FCA1D9
e=INTEGER:0x010001

That is a Subject Public Key Info structure defined by the X.509 standard:
   SubjectPublicKeyInfo  ::=  SEQUENCE  {
        algorithm            AlgorithmIdentifier,
        subjectPublicKey     BIT STRING  }

The reason it's BITWRAP-ed is that the structure of the wrapped public key depends on the algorithm. It could be a RSA public key as you described, but it could be an elliptic curve or DSA public key too. Without wrapping, the ASN.1 parser would need to be aware of the algorithm it has just parsed to know how to parse the subjectPublicKey, which is cumbersome. With wrapping, it just parses the whole structure and subjectPublicKey can be interpreted later.
(The big question for me it's why it uses a BIT STRING instead of a OCTET STRING...)


Are factorization algorithms parallelizable? I was reading about the Blum-Blum-Shub random number generator, and its security depends on the hardness of factoring very large numbers (like many things in crypto do).

I'm just wondering, if I have 10 computers, can I break Blum-Blum-Shub 10 times faster? Or is it impossible to factor numbers more quickly using parallel computation?

Summary: to a considerable degree, more computers speed up factorization of a given integer; but the expected time decreases significantly slower than the inverse of the number of computers used: we are in the area of sub-linear speedup.

Some high-performance (but not the best) factorization algorithms, in particular ECM, enjoy near-linear speedup with the number of computers used; in practice, only the initial distribution of parameters and the announcement of success by the lucky computer requires communication between computers. Failure of one computer is not a serious problem, its work can be ignored, or redone.

Problem is, the best algorithm we know for integer factorization is GNFS, which is asymptotically faster than ECM for factoring $N=p\cdot q$ with two factors $p$ and $q$ of about equal size, as often used in RSA (and in the theoretical setup in which BBS is typically discussed); the crossover, though dependent on many things, is perhaps $N$ of 300 bits give or take a factor of 2. So what's really needed to attack that mainstream variant of RSA is efficiently running GNFS on multiple computers.

Simplifying greatly, GNFS has two main bottlenecks:

The relation collection step (also known as sieving step), which is efficiently run on ordinary computers sending the relations they found by ordinary broadband network (internet) for the next step; not much of a parallelization problem here.
The matrix step, which can and is routinely distributed between multiple CPUs, but requires massive communication between these (ideally, high-speed shared memory, which is not achieved beyond a few CPUs or cores even on enterprise-grade servers, where 8 heavily interconnected CPUs each with 18 cores each with 2 threads is the current high-end, see SEJPM's comment), and very expensive in high-performance computers which implement the highest level of interconnection between many nodes using specialized technology (such as infiniband).

However, there are parameters in GNFS that allow a trade-of between making more work in the relation collection step, against manipulating considerably less data in the matrix step (again simplifying: only the best relations are sent for use in the matrix step, others are discarded). The issue is complex, well beyond my full grasp, but I'll give two meta-arguments that parallelization helps a lot:

In the record Factorization of a 768-bit RSA modulus (collective, in proceedings of Crypto 2010), "In total 64 334 489 730 relations were collected, each requiring about 150 bytes" "for an average of about four relations every three seconds" "scaled to a 2.2 GHz Opteron core with 2 GB RAM"; that's about 500 000 core⋅day of said core. For the hard part of the matrix step, "doing the entire first and third stage would have taken 98 days on 48 nodes (576 cores) of the 56-node EPFL cluster" of "3.0GHz Pentium-D processors on a Gb Ethernet"; that's 60 000 core⋅day of pragmatically-coupled (rather than coupled-to-the-max) CPUs; even if cores do not quite compare, significantly more work was done on relation collection than in the matrix step. I conclude that the matrix step was not the limiting bottleneck by any metric other than capital investment (and the expensive cluster was not purpose-built, and was only used for months versus years for the computers collecting relations).
Arjen K. Lenstra, Adi Shamir, Jim Tomlinson, Eran Tromer's Analysis of Bernstein's Factorization Circuit (in proceedings of Asiacrypt 2002) conclude that with a custom hardware "device that costs a few thousand dollars" proposed by Daniel J. Bernstein to perform the matrix step efficiently, "from a practical standpoint, the security of RSA relies exclusively on the hardness of the relation collection step of (GNFS)".


Can AES be considered as Perfectly Secure? I am studying about the AES encryption standard, and as I know from the theory there is no known weaknesses today about this block-cipher.

I would like to find out or at least to understand what "classification" of secureness is AES.

As I know there are several classifications:

Perfectly secure. Which is not able to break and an example is the One-Time-Pad.
Provably secure that is we can proof that the complexity of the algorithm is closed to a known theoretical assumption like the NP-hard.
Practically secure when an encryption algorithm is tested for long time and there is no sucesful attack so far.

With this in mind I will say that the AES is provably secure because as I know (correct me if I am wrong) the AES is able to crack but to test all the possible keys will take trillion (?) years to achieve that so that my answer.

So I am wrong?

AES is not provably secure, for the simple reason that there is no security proof for it. We suspect that AES is secure in practice, but there is no proof of that.


Retrieve value of private key after encryption with the public key Is there a way to find an RSA private key after it is encrypted with the corresponding public key? Does there exist an algorithm to recover the private key in this special case?

If an appropriate padding mechanism is used then you cannot directly encrypt the private key with the public key as the input size would be too large. If hybrid encryption is used (RSA + AES) then the answer is no.

You could possibly raise (modulo $n$) the private exponent to the power of the public exponent. So then you would need to retrieve $d$ from $d ^ e \mod n$. I don't see how you could retrieve $d$ from that, even if you take into account how $d$ and $n$ are calculated.

Note that you could not do this if you would require the CRT parameters instead of the private exponent $d$.


How fast does a pseudorandom number generator have to be in order to be competitive? Let $\{x_n\}_{n}$ be the pseudorandom sequence produced by a cryptographically secure pseudorandom number generator $G$. What is the cost of computing a term in the sequence for a competitive pseudorandom number generator (PRNG)?

Let me clarify: among the cryptographically secure PRNG, I would like to know which one has the lowest computational cost.

On modern CPUs, a fast Cryptographically Secure Pseudo-Random Number Generator runs sizably faster than one cycle per byte. We are talking >40Gbit/s. See numbers there. Top contenders are AES-CTR assisted by special instructions, and ARX ciphers like ChaCha.

When using dedicated hardware, the true limit is moving around the generated random bits. We can arbitrarily parallelize CSPRNGs, and we have many efficient designs. For example, Trivium is reported at >120Gbit/s/mm2 using 250nm metal CMOS technology, and state of the art today is about 10nm technology, which is faster and some hundreds time denser.

Update per comment: All modern CSPRNGs require $O(n)$ bit operations to produce $n$ bits, and we want a more precise estimate. ChaCha with $r$ rounds (see source) produces $16$ words each 32-bit with computational cost dominated by $16(r+1)$ 32-bit additions and $16r$ 32-bit XORs. Using NAND gates, a ripple-carry adder is 9 gates, XOR is 4 gates, thus the cost is $13r+9$ NAND bit operations per bit produced. For ChaCha8 (which is hoped to have at least 128-bit security), the cost is $\approx113n$ NAND bit operations to produce $n$ bits (with no consideration for circuit depth).

Update on the security of ChaCha8 per this other comment: I'm reasonably confident that ChaCha8 is at least 128-bit safe, but reluctant to state much more because

ChaCha is an evolution of Salsa20, with the same number of 32-bit additions and XORs, and a faster diffusion. While that could make it safer, I'm using that as safety margin.
In the abstract of the Salsa paper, Daniel J. Bernstein recommends the 20-round version for typical applications, and presents 12 and 8-round variants as reduced-round versions recommended for applications where speed is more important than confidence.
Salsa20 was proposed for eSTREAM, in the category asking for fast software ciphers with 128-bit security. While DJB presents Salsa20/20, Salsa20/12 and Salsa20/8 as 256-bit ciphers (which they are as far as key size goes), I'm not reading him as claiming 256-bit security, especially for the reduced-round versions.
There is a known attack with complexity $\approx2^{249}$ against Salsa20/8, thus definitely it does not have security matching its key size. Again, ChaCha8 differs only by its diffusion pattern.
There is a known attack with complexity $\approx2^{153}$ against Salsa20/7, and as the saying goes: attacks only get better; they never get worse.


TLS-conformant ciphertexts and SSLv2-conformant ciphertexts for Blechenbacher attack for DROWN attack This is regarding the published paper on the DROWN attack (https://drownattack.com/drown-attack-original-report.pdf)

It was mentioned in the paper that for TLS, RSA PKCS#1 v1.5 is used to encapsulate the 48-byte premaster secret exchanged during the handshake. Does means that  a random padding string PS is prepended to the 48-byte premaster secret to this formatted massage

([00] || [02] || PS || [00] || pms)

before the actual RSA encryption is done?

If yes, I have 2 questions

(1st question)
How does the decryption oracle in the SSLv2 server differentiate between TLS-conformant ciphertexts and SSLv2-conformant ciphertexts, since the padded TLS plaintext also contains ([00]||[02]) as the 1st 2 bytes?

(2nd question) Why is it that one has to transform a RSA PKCS#1 v1.5 TLS conformant ciphertext to RSA PKCS#1 v1.5 SSLv2 conformant ciphertext before being fed to the Blechenbacher oracle?

Thanks in advance!

(background) It wasv mentioned in the paper that for TLS, RSA PKCS#1 v1.5 is used to encapsulate the 48-byte premaster secret exchanged during the handshake. Does means that a random padding string PS is prepended to the 48-byte premaster secret to this formatted massage
  ([00] || [02] || PS || [00] || pms)
  before the actual RSA encryption is done?

Yes, with the correction that PS is random nonzero. (I'm sensitive to this because I once had to interop-test with a system that didn't correctly exclude zero from PKCS1-type2 padding, resulting in several percent of cryptograms causing spurious test failures.)

  (1st question) How does the decryption oracle in the SSLv2 server differentiate between TLS-conformant ciphertexts and SSLv2-conformant ciphertexts, since the padded TLS plaintext also contains ([00]||[02]) as the 1st 2 bytes?

As described in 2.2, for SSLv2 the PKCS1-encrypted value is $mk_{secret}$ whose size depends on the ciphersuite selected.

As described in 3.2, the SSLv2 oracle (server) checks "$m$ starts with
0x00 02 followed by non-null padding bytes, a delimiter
byte 0x00, and a master_key $mk_{secret}$ of correct byte
length $k$" where k depends on the ciphersuite; examples given are 5 to 24.

48 is not equal to the k value for the selected SSLv2 ciphersuite, or indeed any of them.

3.3 confirms this: "But since no SSLv2 cipher suites have
48-byte key strengths, this means that a valid TLS ciphertext
is invalid to our oracle O." The rest of 3.3 explains the (clever) process used to find a mathematically-related and SSLv2-conformant ciphertext.

  (2nd question) Why is it that one has to transform a RSA PKCS#1 v1.5 TLS conformant ciphertext to RSA PKCS#1 v1.5 SSLv2 conformant ciphertext before being fed to the Blechenbacher oracle?

Because the SSLv2 oracle only gives a distinguishable response for an SSLv2-conformant ciphertext. For all TLS-valid ciphertexts it gives a randomized response from which no information can be extracted -- but the entire purpose of an oracle is to leak information.


Dimension of secret key vector tensor with itself? In the algorithm FHE.KeyGen on page 18 of BGV, the dimension of the secret key $\textbf{s}_j$ is $n_j+1$. Why would the dimension of the long secret key $\textbf{s}_j' \leftarrow \textbf{s}_j \otimes \textbf{s}_j$ be $\binom{n_j+1}{2}?$ Wouldn't it be $(n_j+1)^2?$

Maybe it is because the ring is commutative, so the products $s_j[\ell]s_j[k]$ and $s_j[k]s_j[\ell]$ are equal, and therefore, it is not necessary to store all the $(n_j + 1)^2$ elements.

But even so, in this case, it would be needed to store $\frac{(n_j + 2)(n_j + 1)}{2}$ elements, which is equal to $\binom{n_j+2}{2}$ instead of $\binom{n_j+1}{2}$...


For any hash value, is there an infinite number of inputs that hash to it? Bruce Schneier writes (back in 2005) in a post on cryptanalysis of SHA-1:

  SHA-1 produces a 160-bit hash. That is, every message hashes down
      to a 160-bit number. Given that there are an infinite number of
      messages that hash to each possible value, there are an infinite
      number of possible collisions.

How do we know that there is an infinite number of messages that hash to each possible value?
Is this known to be true for other hash algorithms than SHA-1?

As rightly pointed by Henrick Hellström and Otus, FIPS 186-4 defines SHA-1 with a maximum message length of $2^{64}-1$ bits, hence it is certain that no 160-bit value is the hash of an infinite number of messages. In the following, unless otherwise stated, I assume that we modify the definition of SHA-1 to allow for an infinite number of messages, by removing the length limitation and taking the message length modulo $2^{64}$.

It is not known, in the mathematical sense of that, that there is an infinite number of messages that hash to each possible value; that's both if we define possible value as one of the $2^{160}$ bitstrings of size 160 bits; or even if we define it as one of the (conceivably less than) $2^{160}$ bitstrings such that there exists a message that hashes to that value.

However, we expect that each of the $2^{160}$ bitstrings is the result of hashing an infinite number of messages.

Given the structure of SHA-1 (a Merkle-Damgård hash), this would follow from the plausible conjecture that modifying two consecutive message blocks except for the last 72 bits (of padding and length) is enough to reach any desired value. Or more precisely: that for any $I$ and $K$ of 160 bits, and any suffix $S$ of 72 bits, there exists $A$ of 512 bits and $B$ of 440 bits, such that $\mathcal F(\mathcal F(I,A),B\|S)=K$, where $\mathcal F$ is the compression function of SHA-1 (with first argument the 160-bit hash state, and second argument the 512-bit block input). This conjecture allows to explicitly construct $2^{160n}$ messages of $1024n+952$ bits hashing to any value $K$ (for $n=0$ we set $I$ to the initialization constants of SHA-1, and $S$ to $\text{0x80}$ followed by the length $952$ over 64 bits; we proceed by induction, postfixing previous messages with the former $S$, and setting the new $S$ to $\text{0x80}$ followed by $(1024n+952)\bmod2^{128}$ over 64 bits).

That conjecture seems extremely plausible is we model $\mathcal F$ as a random function of its inputs; or if we model the cipher that it uses internally as an ideal cipher, followed by addition modulo $2^{32}$ of each of the 5 words of input and output (an even better model of what SHA-1 is). The argument goes like: it is likely that for any 160-bit intermediary $J$ we can find $B$ allowing to reach any $K$ as $\mathcal F(J,B\|L)$, for we have $2^{440}$ choices of $B$ and only $2^{160}$ values of $K$ to cover, with the square of the later number much larger than the former. Even if there was some exceptions because $\mathcal F$ or its internal cipher is too regular, we have a large (arguably full or next to full) choice of $J$ by varying $A$, and that will help fully covering the possible $K$. Note: I fell more confident about this argument with belt and suspenders than I would be with a single round of $\mathcal F$.

Back to the actual definition of SHA-1 with limited input length, the above plausible conjecture would imply that more than $2^{(2^{61})}$ messages hash to any given value. That's practically infinite for all but a mathematician.


Multi signature encryption (multiple people can decrypt) I understand that multi sig transactions exist so that X of N need to sign to release a transaction. If only 1 of N is required I guess any of the recipients can spend.
This made me wonder, is it possible to encrypt something, so that any one of a set of people can decrypt the data?
I suppose the data could be in the exponent or something, but also possibly going beyond bitcoin, would it be possible to do this with multiple Mb worth of data (stored off chain in this case)? I guess it would require some sort of script that means conditions have to be met to decrypt the data.

Sure. First of all, to encrypt a large amount of data you just require a single secret key. So now we've reduced the problem to a single small key instead of a large swath of data. Let's call this key the data key.
Now the easiest way of encrypting for multiple parties is for each party to send you their specific public key. Then you encrypt the data key with each public key and include the results with the ciphertext. This will increase your ciphertext of course, but you should be able to limit to N times the size of the encrypted data key.
There are also schemes such as Shamir's secret sharing where you can do M out of N encryption / decryption.


What is the purpose of the middle-man actor in chaffing and winnowing? Chaffing and winnowing is presented as a form of confidentiality without using encryption. This is beneficial for countries where encryption is regulated.

Below is a diagram from Wikipedia showing Alice sending "1001" to Bob.

My question is what is the purpose of Charles in this picture? Why can't Alice just chaff the data herself before sending it directly to Bob?

Additionally, if this assumes that traditional encryption methods aren't available, how are Alice and Charles talking over a secure channel?

Ron Rivest proposed this technique as a way of dealing with export restrictions as well as giving some protection to the parties communicating. It was roughly at the time of the Clipper chip debate. It is not encryption but gives confidentiality.

Pre shared symmetric keys is assumed to exist between Alice and Bob so the MAC tags can be checked at the destination to verify what's chaff.

Charles adds chaff independently so that confidentiality is achieved but Law Enforcement can't obtain "keys" from Alice or Bob to break the confidentiality.

Note that the keys supply authentication (NOT confidentiality) as is the normal purpose for the MAC.

Read more at Rivest's homepage


why does TTLV encoding in KMIP require padding? I study the KMIP in OASIS standard, I need some help.
Integers, Enumerations, and Intervals in KMIP length shall be padded with four bytes. the reason for padding in kmip is need to match the right size??

The padding in KMIP is present only when data is converted to TTLV format, which is a binary representation of KMIP data. TTLV padding exists to "provide optimal alignment for both 32-bit and 64-bit processors" according to the kmip specification. It's generally easier for a CPU to load memory when it's aligned to certain byte widths, especially when the CPU is doing work in parallel.

see section 9 in the kmip 1.0 spec:
https://docs.oasis-open.org/kmip/spec/v1.0/os/kmip-spec-1.0-os.html#_Toc262581260

wikipedia describes how "there can be substantial performance advantages from using aligned data" on x86 cpus:
https://en.wikipedia.org/wiki/Data_structure_alignment


Why is time-lapse cryptography not popular? Time-Lapse Cryptography has been introduced by Michael Rabin and Christopher Thorpe in the paper “Time-Lapse Cryptography”, but it does not seems to be popular. It is a really good paper with an great theoretic background and the authors themselves mention to release an implementation of it “in a few months” (stated in 2006). Yet surprisingly, I couldn't find any reference of it on Google.

Does any one know the reason behind this? Have the authors abandoned this idea?

I suspect the main (only?) reason is that nobody's set up the necessary distributed key generation infrastructure.  That's not as easy to do as you might think, since, for the scheme to be practical and credible, the key generation network needs to meet a bunch of challenging requirements:

It needs to be composed of multiple unrelated parties located in separate regions, so that no plausible adversary can compromise a majority of the network (or more than the threshold number of nodes, if lower).  It would also be desirable for most of the parties to be considered generally trustworthy to begin with, but the whole point of the distributed key generation network is to avoid relying on this.
The hardware and software used by the nodes should be as secure and well reviewed as possible, to avoid it being compromised.  Yet, on the other hand, it would be desirable for the nodes to use many independent implementations of the protocol, so that a vulnerability in any single implementation cannot be used to compromise a majority of the network.  These requirements are, alas, even more difficult to realize together than they are separately.
The parties need to be committed to maintaining their nodes: if too many of the nodes participating in the original public key generation cease operating, the private key can never be reconstructed.  It's possible to mitigate this issue somewhat if new nodes enter the network, both by having existing nodes generate new shares for new nodes and by having closing nodes pass on their shares to others.  However, both of these mechanisms also increase the risk of early compromise, so they need to be considered carefully.

The first and second requirements are challenging enough, but not impossible to meet: both the Tor and Bitcoin networks demonstrate that.  However, I suspect that it's the last one that's the killer: all successful distributed crypto networks that I know of contain a large number of ephemeral nodes.  For time-lapse cryptography, most of the nodes need to stick around for however long you want the secrets to be kept.

Another, related problem with Rabin and Thorpe's proposal is that it doesn't really offer any obvious incentive for anyone to commit to maintaining a node.  Contrast that with e.g. Bitcoin, which provides direct financial incentives for keeping the network running, and Tor, which strongly encourages anyone using the network to also participate in it as a relay.

Both of these networks also deliberately keep the barrier of entry very low, something which I wouldn't see as practical with time-lapse cryptography for the reasons described above: if somebody's going to join the network, you want to be reasonably sure that they're going to stick around, and that they're not just the next one in a string of a million sockpuppets created by an attacker.


Using ECDSA to sign a ECDiffieHellman-derived key Assuming that Alice and Bob know the hash of each other's public key, take this method:

Use ECDiffieHellman with temporary private keys each time to generate a per-session shared symmetric key
Create an AES connection secured with the shared key (unique IVs for each message, verified with HMAC)
Send their public keys along with their signatures of that particular session key over the encrypted connection to authenticate each other (by verifying that the public key matches the stored hash, and that the signature was signed by the public key).

Is this a safe way to create a secure and authenticated session? Are there any better ways that do not require pre-existing knowledge of the private key (or trust in a centralised certificate authority). I know that you should always try to use standard libraries, but I am interested in understanding more about cryptography - this will not be used in any critical software.

Thanks very much for your help.

Sure, first you set up a 1:1 communication and then you establish trust in it. This is kinda like TLS 1.3 where encryption starts as soon as possible. Of course, anything up to the authentication of the entity and handshake can be generated by an adversary, so it is slightly dangerous in that sense.

And in general, you would try and authenticate as many handshake parameters as possible, rather than just the ongoing channel. Basically you try and tend to achieve confidentiality and authentication over as much data as possible. You could do that by hashing all the communication messages and then signing that separate hash, for instance.

As for the trust in the public keys: yeah, sure. This is almost identical to certificate pinning after all, where a certificate is trusted explicitly rather than just a public key. The advantage of using a certificate is of course that you can use a certificate chain later and that a certificate contains more information than just a public key (validity period, identification information, CRL and whatnot). So generally if you want to use a public key, why not create a self signed certificate for it and pin that instead.

The described scheme can certainly be part of a secure protocol. If the protocol is actually secure depends on a lot of other factors. And such details matter even for the specific scheme mentioned (parameter validation, side channel resistance, avoidance of replay attacks and mirror or reflection attacks), and so on. Creating a secure transport protocol is one of the most daunting tasks, especially for a beginner.


How to use the hardcoded server's public key to register a client application? I'm designing the security for a smartphone app that can be used to make car reservations.

Clients have to register them with their driver's licence through the application and can then book a car.

Is it a good practice to hardcode the server's public key in the application and then encipher a secret using this public key?

I'm seeing an Eve-in-the-middle attack and authentication as a security issue. How can this be solved? Or how can this process be done securely?

Can you please describe your functional requirements in more detail, i.e. what are  you trying to solve? That will ensure that you get most appropriate advice.

What do you care to achieve?

server to authenticate the client making the reservation?
a way for the client to send its driver license in a confidential manner?
client to authenticate the server before it sends its driver license?
ability to revoke and renew a compromised server key?
other?

Having a well defined number of functional requirements will let you laser-focus on determining what crypto primitives you should consider for meeting those functional requirements.

Encrypting the driver's license data with the server's RSA public key, in theory gives you confidentiality of the driver's license data since only the server private key may decrypt the driver license. In practice, the robustness of the confidentiality is a function of quality of your source of randomness, length of the RSA key, what padding is used, server-side protection of the private key, malleability of the client app since someone can hack your client app and replace the public key with their own public key, etc. In other words, take extra care with your implementation.


Attacks on Aes (128-192-256) I have a direct question
Is there any practical attacks on the AES cryptosystem (128-192-256 keys)

There are practical side-channel attacks against implementations of AES, but there are not any practical cryptanalytic attacks against the abstract algorithm.

The best cryptanalytic attack against the complete cipher in a reasonable attack model is probably the biclique attack, which only knocks a few bits off the key. The related key attacks against AES have attack models which are unreasonable when using AES as a block cipher to preserve confidentiality, and so are less/non applicable even though the bottom line of the computational cost of the attack is more pronounced.

For more information, you might investigate the following question/answers: How is encryption broken today? While that question/answer(s) is not specific towards AES, most if not all of the information is relevant.


Is semantic security important in a hybrid cryptosystem? RSA doesn't provide semantic security when used unmodified, and neither does the commonly used PKCS#1 v.1.5 padding scheme for encryption.

Is this a problem for hybrid cryptosystems at all?

My suspicion is that it isn't, since the plaintext message of the RSA encryption should be a random string used as an encryption key for the symmetric cipher used to encrypt the actual message, which would make the advantage an attacker could gain by the lack of semantic security pretty neglegible.

I guess that it's still a bad idea to rely on the randomness of the ciphertext in that way, but then again, as far as I understand, more secure padding schemes like OAEP also need a random input to guarantee semantic security, so by encrypting messages without a good entropy source seems to be equally bad in both cases.

To sum up my question:

Is semantic security necessary if the plaintext is guaranteed to be random for all messages encrypted by an asymmetric encryption scheme?
When the plaintext turn out to be not as random as expected (e.g. due to a broken RNG), is that worse than the RNG input for a semantically secure padding scheme being predictable?

Additionally, if it is, can anybody explain why PKCS#1 v.1.5 is still commonly used? As far as I know, GnuPG uses it exclusively for RSA encryption, and TLS does so as well for its RSA key exchange in many of its cipher suites.

Not a complete answer, but since you mentioned "unmodified RSA" I feel it's relevant.

Something stronger than vanilla RSA is necessary, even if it isn't semantic security.

Example: What if you have a public key exponent of 3 and the symmetric key being encrypted is 16 bytes long? Using raw RSA, $m^e$ would be about $128 \times 3 = 384$ bits long and thus smaller than any modern public key modulus would be. Being smaller than the modulus would prevent the calculation from taking advantage of the RSA Assumption, which is the premise of RSA's security. Since $m^e$ is easy to factor simply over the integers all security would be lost. (And this mistake would be somewhat obvious to the attacker because the vast majority of the high bits would all be 0.)


I am trying to implement TLS v1.1 {3,1} but get alert 70 on hellomessage to goolge I am trying to implement TLS on top of the winsock api's from windows. I am using port 443 and have created a socket. I have sent this message

in decimal.

22 3 1 0      112 1 0 0
108 3 1 48    227 142 116 0
1 4 9 1       25 4 17 0
17 4 25 16    9 4 1 0
1 4 9 16      25 4 17 0
17 14 25 16   0 0 68 192
10 192 20 0   136 0 135 0
57 0 56 192   15 192 5 0
132 0 53 192  7 192 9 192
17 192 19 0   69 0 68 0
51 0 50 192   12 192 14 192
2 192 4 0     65 0 4 0
5 0 47 192    8 192 18 0
22 0 19 192   13 192 3 254
255 0 10 10

The response is

21
3
1
0
2
2
70

This is the char* or string I am passing to winsock as the message, so that would imply this is my ciphertext simply with the null stream or block cipher which is the identity map of the plaintext fragment and with no MAC. As is the record state on the initial client hello message, the first step in the handshake. Perhaps I am getting the length wrong,

If the CipherSuite is TLS_NULL_WITH_NULL_NULL,
   encryption consists of the identity operation (i.e., the data is not
   encrypted, and the MAC size is zero, implying that no MAC is used).
   TLSCiphertext.length is TLSCompressed.length plus
   CipherSpec.hash_size.

I can not find the definition of CipherSpec.hash_size in the request for comments on TLS 1.1?

Also I have tried different versions to no prev ale. Perhaps someone can look through my encoding  below and see if there is a problem? Other then an encoding issue I can only suspect that google.com does not take TLS on port 443 but instead an http upgrade to TLS on port 80? https://tools.ietf.org/html/rfc2817

I was able to realize that the above message is malformed(with help of wireshark). You will notice there are 33 random bytes instead of the 32 as prescribed by record layer protocol. It was an error on my part with the char * holding them. Zero was first char so should go up to 31, mine went to 32. Doh.

Now most servers respond with server hello and certificates.


RSA and its Limitations How and why do we face a problem when encrypting values of 0 and 1 using the RSA cryptography Algorithm?
Is there any way to solve it?

RSA encryption is based on modular exponentiation, where the plaintext $m$ is transformed into a ciphertext $c$ by the operation $c = m^e \pmod n$. For any moderately large value of $e$ (normally 65537), this works OK.

However, the numbers 0 and 1 are unaffected by this operation, because $0^e = 0$ and $1^e = 1$ for any encryption key $e$ and any modulus $n$. Thus in "textbook" RSA, if $m$ is equal to 0 or 1, then $c$ is equal to $m$ and the encryption has no effect.

In practice, this isn't a problem because in the real world, padding is used to ensure that there is no possibility of $m$ being equal to 0 or 1. Padding can also provide other benefits such as semantic security.