Trouble understanding the correctness of this Zero-Knowledge proof of posession of a discrete log I came across the following protocol for a "Zero-Knowledge Proof of a Discrete Logarithm" in Bruce Schneier's Applied Cryptography (second edition) book. I simply cannot prove to myself that this algorithm is correct, and have been unable to find an explanation of the protocol online anywhere, only finding the original paper it appears Schneier got it from. (In the paper it is referred to as 'protocol 2,' and many of the variables are different, but it is indeed the same protocol.)

The protocol is as follows:

Peggy wants to prove to Victor that she knows an $x$ that satisfies:

$A^x \equiv (mod$ $p)$

where $p$ is a prime, and $x$ is a random number relatively prime to $p-1$. The numbers $A$, $B$, and $p$ are public, and $x$ is secret to Peggy. Here's how Peggy can prove she knows $x$ without revealing it.

Peggy generates $t$ random numbers, $r_1, r_2, ..., r_t$, where all $r_i$ are less than $p-1$.
Peggy computes $h_i=A^{r_i}$ $mod$ $p$, for all values of $i$, and sends them to Victor.
Peggy and Victor engage in a coin-flipping protocol to generate $t$ bits: $b_1, b_2, ..., b_t$.
For all $t$ bits, Peggy does one of the following:

a.) if $b_i = 0$, she sends Victor $r_i$.

b.) if $b_i = 1$, she sends Victor $s_i = (r_i-r_j)$ $mod$ $(p - 1)$, where $j$ is the lowest value for which $b_j=1$.
For all $t$ bits, Victor confirms one of the following:

a.) If $b_i=0$, that $A^{r_i} \equiv h_i (mod \space p)$

b.) If $b_i=1$, that $A^{s_i} \equiv h_i h_j^{-1} (mod \space p)$
Peggy sends Victor Z, where

$Z = (x - r_j) mod \space (p-1)$
Victor confirms that

$A^Z \equiv B h_j^{-1} \space (mod \space p)$

I was unable to prove this to myself, being very confused as to how the probability that Peggy can successfully cheat is indeed the claimed $2^{-T}$ where t is the number of trials performed.

Mainly, I fail to understand how Peggy could possibly be caught during steps 4 - 5. The paper linked above claims "This is because [Peggy] can never answer both possible cases to be sent in step 2." but in step two she either sends $r_i$, a value she literally already has and does not need to compute anything for, or $r_i - r_j \space (mod \space p-1)$, which at least needs some computation, but certainly nothing she couldn't easily perform.

I understand how sending Victor all $h_i$ commits Peggy to the $r$ values, but fail to understand how she uses those to prove knowledge of $x$. I feel as if I'm missing something obvious.

This is "Protocol 2" shown on page 207 of the paper (pdf) referenced.

Maybe I should start from "Protocol 1" that requires (I believe) $s_i = x e_i^{-1}$, not $xe_k^{-1}$.

With step 5, it was explained at Theorem 4, "Correctness" part (that is actually proving soundness property). It starts with a claim of Peggy unable to always produce an acceptable answer $s_i$ for both cases of $b_i$ at step 4. However, this answer does not depend on $x$ and only depends on $\{r_k\}$ chosen by Peggy herself at step 1.

My view is, a better (I believe) protocol was presented next year by (almost) the same team.
For practical purposes, Schnorr protocol would be my choice for this setup.
This paper remains the first to introduce a proof for DL setup/problem.


How to handle the GCD(V,P) != 1 case when doing point addition or point doubling in elliptic curve cryptography The equation for a finite field Elliptic Curve is of this form:

$$y^2 \equiv x^3 + a * x + b \pmod{P}$$

When we do common EC operations like point doubling or point addition we need to calculate the inverse of a number.

For example this is the formula to calculate the slope for the point addition.

$$(Y_1 - Y_2) * ( X_1 - X_2 )^{-1}$$

Now here is the thing. If the $\mathop{GCD}(X_1 - X_2 , P) \neq 1$ , then there is no solution for the inverse (Basic finite field math rule).

First I thought that this could never happen because P was a primary number, but then I discovered that in the cryptography libraries the GCD was tested and if it was not equal to 1 the resulting point would be a virtual point : the point at infinity.

So here Are my questions : Is $P$ a primary number for all the standard Curves Nist,Secp... and by the way if I just want to use this standard curves do I need to test the GCD?

Secondly, if P is not a primary number and if I decide to use this point at infinity "Technic" and I encounter a $\mathop{GCD} \neq 1$, will the public key resulting be a weaker one? (Knowing that the point at infinity has some tricky properties).

First of all, I would like to note that the statements you make up front are not universally true -- sometimes we use Elliptic Curves with different equations, and with a bit of cleverness, we can do a long series of point additions/doubles and compute a single multiplicative inverse at the end.  These cavaets don't really change the answers; they do indicate that what you're learning right now isn't everything there are to elliptic curves.

However, you have to start learning somewhere, and where you are isn't a bad place to start.

Now, to address your questions:

  Is $P$ a primary number for all the standard Curves Nist,Secp...

The answer is effectively "yes".  Now, here is why I say "effectively": there are some curves, called "even characteristic", where the number of values $x$ and $y$ can take on is $2^k$, for some integer $k$; however the multiplication operation is not "modulo $2^k$", and what I say below about inverses is still true.

  If the $GCD(X_1 - X_2, P) \neq 1$ then there is no solution for the inverse.  Can this actually happen?

Yes, it can, even though $P$ is prime.  $(X_1-X_2)^{-1}$ will always exist, no matter what $X_1-X_2$ is...., unless it happens to be 0.  That is, if $X_1-X_2=0$, or equivalently, if $X_1 = X_2$, then that inverse won't exist.

Can this happen in practice?  Well, yes, there are two different ways this can happen:

$Y_1 = Y_2$ as well; in that case, you're adding a point to itself.  In other words, you're doing a point doubling; with the standard Weierstrauss elliptic curve equations, there's a distinct algorithm to do that.
$Y_1 = -Y_2$; in that case, you're adding a point to its additive inverse; in that case, the result really will be "the point at infinity".

  I just want to use this standard curves do I need to test the GCD?

Well, you need to compare $X_1$ and $X_2$ to see if you fall into either of the above conditions.  If $X_1 \neq X_2$, then you'll always have $GCD = 1$.

And, if you're asking why the library you're looking at explicitly tests the GCD, well, I have no idea -- I didn't write that library.  However, one possibility is that they are using the Extended Euclidean Algorithm to compute the inverse -- that algorithm does the same logic that's used to compute the GCD (and keeping track of some extra information that is used to compute the inverse).

Finally,

  I decide to use this point at infinity and I encounter a GCD≠1, will the public key resulting be a weaker one?

Depends; if you're doing a long chain of point additions/doubles, and an intermediate point happens to be the point-at-infinity, that's not actually a problem -- that point works algebraically like any other point.

However, if the final point (that is, your "public key") is the point-at-infinity, well, that would be bad.


Looking for feedback on the cryptographic design of my open source project: Bloom I'm about to release the new version of my open source project: Bloom (encrypted Notes, Calendar, Contacts, Files…) which will feature end-to-end encryption.

I've published the cryptographic details online and I am looking for feedback by the community before launching it:

https://gitlab.com/bloom42/bloom/-/wikis/security

Any feedback is welcome.

One obvious note is that if someone (possibly someone posing as a server) overhears the client to server message (that is, the client's input to the crypto.verify.password_hash.argon2id function), then he knows enough to register as the client to a valid server.  He might not know the password; however he wouldn't need to.

If that is a problem, it would sound like you need some sort of authenticated key exchange (perhaps Opaque), which addresses this.  And, no, I don't happen to have an implementation of that handy...


In RSA encryption, does the value of e need to be random? I am a novice programmer and am just finishing up an RSA encryption program that I am writing for practice. Currently I have the program generate a relatively small random value for the public key e. When adding the finishing touches, I realized that there was no point for e to be random. Is this thinking correct?

Yes, this thinking is correct; there is no requirement that the public exponent $e$ to be random.  After all, it doesn't matter whether $e$ can be guessed by an attacker; we'll be including that value in the public key anyways.

Common practice is currently to use the fixed value $65537 =2^{16} +1$ for $e$.  Any odd value of $e > 1$ will work; however, smaller values of $e$ will tend to make the system brittle against errors in performing the RSA padding.


Any efficient text-based steganographic schemes? While there are sophisticated and efficient steganographic schemes with images as cover available, I am yet ignorant of the existence of any fairly efficient and secure schemes with texts as cover. This state of affairs is IMHO unsatisfying, since the communication channel may under circumstances only be able to transfer printable natural language texts, and that in rather small volume, due to constraints posed by the warden.

To be concrete on the efficiency issue, I would desire that the ratio of stego bits to covertext bits be no less than, say, 1/50. For references to existing schemes, if any, or else novel basic ideas that could lead to the development of such a scheme (if possible  user-friendly and not too hard to implement), I should be very grateful.

[Addendum 1, edited] I have in the meantime a scheme named WORDLISTTEXTSTEGANOGRAPHY that should achieve a not large but IMHO practically nonetheless useful efficiency in the range of [0.5, 1.0] bit per word of natural language texts, requiring though that the user does some amount of trial and error work under the guidance of the software. (Use e.g. of an appropriate codebook could highly compress the input stegobit sequence.) The latest Version 2.1 of it, running on Python V.3.6.1, is available at my new home page: http://mok-kong-shen.de. See update notes in it for the differences to the earlier versions. (I regret in particular that in the earlier versions a sentence is missing in the explanation of how to do the examples, with the very unfavourable consequence that new users may fail to do the examples.)

My understanding is that the three most popular approaches to "steganography using text as a cover" are:

1 Generate a completely new text by picking one word at a time from a dictionary, using the ciphertext bits to select which word.

Pick words in ways that, at first glance, look like real English sentences, using Markov chain algorithms.
Weihui Dai.
"Text Steganography System Using Markov Chain Source Model and DES Algorithm".
(2010).
H. Hernan Moraldo.
"An Approach for Text Steganography Based on Markov Chains".
(2012).
"Steganographic Markov Chains".
(2008).
Anna Lysyanskaya and Mira Meyerovich
"Provably Secure Steganography with Imperfect Sampling"
(2006). Etc.
For a given dictionary, picking words with uniform distribution gives you the most ciphertext bits per word,
but it's pretty obviously not real English text. Still, these schemes are very popular for sending raw bits over systems (like email, voice, etc.) designed for text: NATO phonetic alphabet, PGP word list, the S/KEY dictionary, the Diceware dictionary, etc.

2 Take some fixed text, and send exactly the same series of letters as in the original text, adding the ciphertext bits by modifying the presentation of that text in ways that we hope the warden doesn't notice.

Use two slightly different typefaces as in Bacon's cipher (1605).
Add space characters to the end of lines, where they are usually invisible, as in SNOW (1996?).
Vary the spacing between words; nudge the letters left-right (nonstandard kerning) or up-down.
Etc.

3 Take some fixed text, and slightly modify the words in ways that we hope the warden doesn't notice.

The receiver takes each word, looks it up in the agreed-on thesaurus; if the thesaurus shows 4 synonyms, the receiver decodes that word into 2 ciphertext bits. Nanhe, Kunjir, Sakdeo. “Improved Synonym Approach to Linguistic Steganography”. Shirali-Shahreza. "A New Synonym Text Steganography". Chang and Clark. "Practical Linguistic Steganography using Contextual Synonym Substitution and Vertex Colour Coding".
The receiver looks for certain "key words", ignoring all the other words.
The receiver decodes a few bits per sentence by noticing which of several ways (all with equivalent meaning) of arranging the words in that sentence were selected. Grothoff; Grothoff; Alkhutova; Stutsman; and Atallah. "Translation-Based Steganography" (2005). a
Etc.


Security proof, Sequence of games I hope someone can help me with the sequence of games security proof for protocols. Here are my questions:

What is the aim of each individual game? i.e. why can't we do this in one indistinguishable game ?

How can we link each game with the previous one? i.e. I am not understanding the difference lemma which states:

Lemma 1 (Difference Lemma). Let A, B, F be events defined in some probability distribution, and suppose that A ∧ ¬F ⇐⇒ B ∧ ¬F. Then |Pr[A] − Pr[B]| ≤ Pr[F].

The general strategy in sequence of games or game-hopping proofs is the following:
Starting with the original security game, change small details in the game in every hop until you get to a game where it is easy to prove security.
You do want small changes in the game hops such that you can prove indistinguishably between the games by security assumptions.
To answer your questions concretely:

The aim of each individual game is a small change from the previous game that can be proven indistinguishable from it.
We link these games by bounding the advantage of an adversary noticing the difference. If no P.P.T. distinguisher is able to decide whether it plays the first or the second game, we can include this bound in the overall security bound and consider the second game instead.

The lemma you stated is a formalization of this idea.


Threshold decryption in multi-key homomorphic encryption I have a problem understanding the security of threshold decryption in multi-key homomorphic encryption (MKHE) with so called "noise flooding". In particular I think that it is not secure, so probably I misunderstood something.

MKHE allows multiple clients to encrypt their inputs $x_i$ with their private keys, which is joined into a common ciphertext $C$. An arbitrary function $f$ can then be used on $C$ to produce an encryption $C_f$ of $f(x_1,\ldots, x_k)$. Finally (and most importantly for this question), each client creates a partial decryption of $C_f$, which is joined to obtain $f(x_1,\ldots, x_k)$.

I will explain how this is done in this paper based on BFV FHE scheme (RLWE), since I think it is maybe the most simple. There are other approaches with similar ideas like this first paper, this paper
,...

For simplicity I will consider just a simple operation of addition. Say we have three clients, each encrypting $x_i$ and at the end we want to get $f(x_1,x_2,x_3) = x_1 + x_2 + x_3$. The scheme is based on RLWE problem, so let $R$ be a ring and $D_{\sigma}$ a distribution for which RLWE problem is hard. Let $q$ be the modulus of $R$ and $t$ the modulus of plaintext. Define $\Delta = \lfloor q/t \rceil$.

Setup: Let $a \in R$ be a uniformly random element.

Key-gen: Each client samples a secret and noise $s_i, e_i$ with $D_{\sigma}$ and set $b_i = -as_i + e_i$. Then $(s_i, b_i)$ is his key.

Encrypt: Each client encrypts $x_i$ by sampling $r_i, e_i^1, e_i^2$ with $D_{\sigma}$ setting $(c_i^0, c_i^1) = (b_ir_i + e_i^1 + \Delta x_i, a_ir_i + e_i^2)$

Eval: Ciphertexts $(c_i^0, c_i^1)$ are evaluated into an encryption of $f(x_1,x_2,x_3)$ by defining:
$C_{f} = (c_0, c_1, c_2, c_3)$ where $c_0 = c_1^0 + c_2^0 + c_3^0$, $c_1 = c_1^1$, $c_2 = c_2^1$, $c_3 = c_3^1$.

PartDec: Each client samples so called "smudging noise" $e_i^{sm}$ and sends: $\mu_i = c_i^1s_i + e_i^{sm}$

MergeDec: Everyone can calculate $\mu = c_0 + \mu_1 + \mu_2 + \mu_3$ from which corresponds to $\Delta(x_1 + x_2 + x_3) + \text{noise}$ so the result can be extracted.

QUESTION: The reason for the security of the partial decryption is that the "smudging noise" should hide the secrets. But if I use the partial decryption $\mu_i$ of a client together with his partial ciphertext:
$$c_i^0 + \mu_i = (b_ir_i + e_i^1 + \Delta x_i) + (c_i^1s_i + e_i^{sm}) = ((-as_i + e_i)r_i + e_i^1 + \Delta x_i) + ((a_ir_i + e_i^2)s_i + e_i^{sm}) = e_ir_i + e_i^1 + e_i^2s_i + e_i^{sm} + \Delta x_i$$
But this means that one can get $x_i$ which is not ok. One can hide $x_i$ only if $e_i^{sm}$ would be big enough to hide it. But then also $\mu$ would be flooded with noise. What am I missing?

Everything you write looks correct. However, you may be expecting the distributed decryption protocol to have a security property that it does not (and was not intended to, and really cannot in your example) have.

Specifically, the Mukherjee-Wichs paper you linked defines security to say (roughly) that, given the evaluated ciphertext, its underlying plaintext, and the secret keys for all but one of the parties, we can statistically simulate that party’s partial decryption. This corresponds to all but one of the parties being semi-honest, and protecting the privacy of the remaining honest party’s input (as far as is possible).

In your example, the evaluation function just sums the three inputs. Because all but one of the parties is semi-honest, the adversary knows all their inputs. It is also entitled to the output sum of all the parties’ inputs. This means it can trivially compute the honest party’s input! So, there is actually no “security violation” arising from the fact that the decryption protocol implicitly reveals the honest party’s input, because that input is implicitly revealed by the function itself.

If you consider a different evaluation function that doesn’t implicitly reveal the honest party’s input, then I think you should see why the “smudging” noise works as intended.


Polynomial for secure communication Can we use a polynomial $P(x)$ to securely communicate ?

For example Alice & Bob agree on a degree of a polynomial. The value $x$ & the coeficients are generated from a seed using a hash function or any other PRG and change in each communication, the plaintext $m$ is hidden into $P(x)$. For example  $P(x) = ax^2+b(m)x+c$

alice sends the result of $P(x)$ to Bob, once received bob retreive $m$ from $P(x)$

can we provide a certain security level with the above method ?

If you're operating in some finite field, and the PRG used to generate the coefficients and $x$ is cryptographically secure (that is, it is infeasible to distinguish the output of the PRG from a truly random source of field elements), and you go back to the PRG for every single message, then it is secure as far as privacy is concerned (of course, you need to make sure that $bx$ is nonzero; otherwise, it might be a bit tricky for the decryptor to recover $m$).

As for integrity, well, if the attacker replaces a ciphertext $C$ with another $C'$, then that will decrypt to some message $m'$, where $m - m' = I(C - C')$ for some invertible element $I$ which is unknown to the attacker.  This is why you want to do the operation in a finite field (rather than a finite ring); in a field, $I$ can be any nonzero value, and so while the attacker can make the altered ciphertext decrypt to something else other than m, but he literally has no control beyond that.

On the other hand, the simpler polynomial $P(x) = mx + a$ has the same property; if $a$ and $m$ is generated via cryptographically secure source and you're operating in a finite field, then transmitting $mx+a$ also provides privacy, and prevents the attacker from making nonrandom changes to the decrypted ciphertext.

This garbling property (where any change in the ciphertext will make a random change in the plaintext) is the best we can do if the ciphertext must be the same size as the plaintext.  Generally, that is not considered good enough, and usually we include an authenticate operation which makes the ciphertext strictly larger than the plaintext, but also makes sure that any change in the ciphertext will cause the decryptor to reject the modified message (rather than emitting a random decryption).


RSA and the strong RSA assumptions The RSA assumption:

Given a randomly generated RSA modulus $n$, exponent $r$ and a random $z \in \mathbb{Z}_n^{*}$, find $y$ such that $y^r=z$.

The strong RSA assumption:

Given a randomly chosen RSA modulus $n$, and a random $z \in \mathbb{Z}_n^{*}$, find $r>1$ and $y \in \mathbb{Z}_n^{*}$ such that $y^r=z$.

In the strong RSA assumption usually they say that "$r$ may be chosen in a way dependent on $z$, while in the usual RSA assumption $r$ can be chosen in a way independent of $z$".

What is meant by in a way dependent on $z$? How can one achieve such dependancy? I'm very grateful if someone can explain this.

Even by substituting some values to $n$, $z$ etc. would be great and would help me to understand more.

Thanks a lot in advance.

What is meant by "$r$ may be chosen in a way dependent on $z$"?

An hypothetical algorithm $\mathcal A_2$ breaking the strong RSA assumption has input¹ $(n,z)$ with $n$ generated by the RSA key generation procedure, and outputs² $(r,y)$ such that $y^r\equiv z\pmod n$, with the only other constraint on $r$ that $r>1$. Contrast with an hypothetical algorithm $\mathcal A_1$ breaking the RSA assumption, which has input¹ $(n,r,z)$ with $(n,r)$ generated by the RSA key generation procedure, and outputs² $y$ such that $y^r\equiv z\pmod n$.

The distinction makes the problems different: an hypothetical algorithm $\mathcal A_2$ that builds $r$ as $r\gets n$ is of no obvious use to break RSA, since that choice of $r$ is never used by a standard RSA key generation procedure³. Same if $\mathcal A_2$ was generating $r$ as a function of $z$, e.g. $r\gets2\,\lfloor z/7\rfloor+3$, because that $r$ has vanishingly low probability to match the $r$ generated by an RSA key generation procedure.

In the other direction, we can turn an hypothetical algorithm of the $\mathcal A_1$ kind into one of the $\mathcal A_2$ kind, e.g. by repeatedly trying incremental odd $r\ge3$, submitting $(n,r,z)$ to $\mathcal A_1$ used as a subprogram, and if within some time limit it outputs an $y$, giving $(r,y)$ as output of our $\mathcal A_2$.

The strong RSA assumption (which is that there exists no algorithm² $\mathcal A_2$) is thus a no weaker assumption than the RSA assumption (which is that there exists no algorithm² $\mathcal A_1$). These different notions are soundly named!

¹ Making implicit the security parameter which can be taken as the bit size of $n$, and the random input for randomized algorithms.

² With non-vanishing probability of success within time polynomial w.r.t. the security parameter.

³ It is used by the C.C. Cocks cryptosystem, which predates RSA, and is believed just as secure.


Verification of signed message with encryption I have a question about the message that is being encrypted and signed. Say, two users called Tom and Mary, both have a pair of private key and public key. Tom sends a message through a system that will encrypt and sign the message. 2 kinds of message will be sent
1. encrypted message  and,
2. hash function of the message, public key of Tom and Mary,  secret Key (which is chosen by Tom)

I would like to ask after Mary got the message, she could recover the message by the public key of tom. but how could she recover the hash function so that she could make sure this 2 kinds of message are signed by Tom?

Thanks!

There is some confusion in your question, because a signature in a public key cryptosystem is (usually) not just a hash, but a hash of the message that is signed using the private key. E.g. in RSA it would be a hash value padded and raised to the private exponent.

There are two ways to have an authenticated encryption in a public key system: Should we sign-then-encrypt, or encrypt-then-sign? In encrypt-then-sign, the receiver can verify the signature just as if they had received a signed plaintext message. In sign-then-encrypt they would first have to decrypt the message, but then they have just a signed plaintext.

In either case the message hash can be calculated by anyone since it does not include keys. The keys only come into play when verifying that the signature was taken over the hash, and there the public key is enough.

For low level details of how it works in the case of RSA you can refer to PKCS #1.


Are the signcryption and the authenticated encryption same? The signcryption and the authenticated encryption are both the combine of encryption and authentication with three natural composition (i.e., EtS, StE, E&S). I am not sure that if they are the same cryptographic primitive.

If they are the same, why a cryptographic primitive has two different names?

If not, the only difference I personally found is that signcryption is a symmetric version and another is an asymmetric version. But I strongly believe that the difference I found is not true.

Your finding is correct. From your links;

In cryptography, signcryption is a public-key primitive that simultaneously performs the functions of both digital signature and encryption.
Authenticated encryption (AE) and authenticated encryption with associated data (AEAD) are forms of encryption which simultaneously assure the confidentiality and authenticity of data.

The signing in signcryption is performed with the private key operation. This can provide non-repudation since only the owner of the private key can sign.
The authentication in AE is performed with a shared key between parties. This cannot provide non-repudation since both parties have the key. We can say that the authenticity is mutual.


Very short signatures? (eg: 48bits?) Our application requires some 'mild' form of 'proof of origin' for the tokens we issue (~200 bytes), however, the value of each is trivial.
The requirement is to provide 'tamper resistance' rather than 'unforgeable', to not bloat the token size, and to use commonly available 'standard' libraries and tools.

In the token, we include a hash of the request we received, and I understand we can crop this down to the last n (e.g. 48) bits easily enough, and do the same with the token hash/digest before signing.

Is something similar possible with the signature, or do we need to just generate the smallest key and a tiny digest to get the output as small as possible?

I've been mucking about with openssl rsautl - is this as good as any other given our requirements as above?  The signatures are coming out at ~24 bytes, I'd like to reduce that a bit further if possible.

EDIT TO ADD

For us, the ability to forge a single signature within a few minutes is perfectly fine, sub-minute is getting problematic.  The ability to derive our private key, and subsequently bulk-produce counterfeit signatures with negligible time/energy cost is the primary risk.

With the advice of those below I've been looking at ECDSA and the secp112r1 OpenSSL built-in curve, assuming that is better than a 256bit RSA primary key.

Suppose you have an asymmetric algorithm that creates a 48-bit signature. Then an attacker can simply test possible 48-bit signatures and find one that verifies in $2^{47}$ tries on average. Even with a relatively slow asymmetric algorithm that would be feasible, especially if the attacker can test the same signature for multiple tokens. And that is only a brute force attack, asymmetric systems usually allow much faster attacks.

If you can establish a symmetric secret, even a short MAC is much better, because while the attacker still has a $2^{-48}$ probability of success with a random guess, they can no longer verify those guesses offline.


Why don't use random padding in RSA? Consider the following scenario:

Sender S sends a message to receiver R. He uses a hybrid encryption scheme with RSA as key-encapsulation algorithm and AES-256-CTR (4byte-counter) and SHA256-HMAC. These algorithms are specified and already known by the receiver → the receiver knows the encrypted key length:
32byte AES-key + 12byte AES-nonce + 64byte HMAC-key = 108byte

Why don't use RSA(SECURE_RANDOM(404) || key-block) as padding-scheme?

The length is already known by the receiver, so there is no reason to indicate it.
If the key-capsule is altered it will be detected because the decrypted keys will be wrong and the HMAC-verification will fail.
It shouldn't be susceptible against padding-oracle-attacks because the application cannot distinguish between correct decryption and defect padding (in contrast to PKCSv1.5 and OAEP after standard).

There probably is a very good reason not to do this, but I'm not seeing it.

It is an important feature to be able to see if encryption/decryption failed. Sure, padding oracles are a problem, but so is a protocol that doesn't perform intrinsic verification of the performed operation.

If you have a key agreement protocol then you need some kind of method of validating that the decryption of the symmetric key succeeded. Now you could do this by adding a separate authentication tag over some constant value calculated by the generated/decrypted key. That would however leak this information to an attacker. So you probably need to perform the MAC calculation over some challenge, which you would also need to include in the message. You could also create an additional key using the decrypted value as seed, and use that to verify the result, but again: additional operations are required and there is still an authentication tag to be sent. Note that MAC tags can also be vulnerable to (time based) oracle attacks.

What you really don't want is implicit verification, i.e. using the resulting keys and see if you get verification errors over the actual data. I'm using a protocol that does this and it makes for horrific implementation choices. In an update of the protocol explicit authentication with a third key (used to HMAC the handshake) is being utilized.

So currently there is intrinsic verification of the result, in your scheme there isn't. That said, your scheme is probably secure. RSA KEM is even more secure so if you like your scheme you should probably go for RSA KEM and send an authentication tag within the same message containing the encapsulated key.


Count the functions that have an entry with a specific structure Consider the function $f: \{0,1\}^n\rightarrow \{0,1\}^{2n}$
I want to count all the functions that have one entry where its first n bits are equal with the last n bits.
Assume we target entry number 10 and g is one of those functions that have the aforementioned property: $m=\{0,1\}^n;g(10)=m||m$
The total number of functions assuming $2^n$ rows where each row has $2n$ bits is $2^{{2^n}2n}$
I would say, if we want a specific entry of the function to have that structure we can first count the rest of the rows of the function which have: $(2^{n}-1)*2n$ bits and then since we want the first n bits to be equal with the last to the entry that we didn't take into account, we add another n bits, so total for each function: $(2^{n}-1)*2n+n$.
Total functions: $2^{(2^{n}-1)*2n+n}$
So the probability: $\frac{2^{(2^{n}-1)*2n+n}}{2^{2^n*2n}}=\frac{1}{2^n}$
Do i have it right? Is there an easier way to think about it? The result is to trivial to require that amount of effort.
Edit (added some more details):
One example (for $n=2$):
$F: \{0,1\}^2 \rightarrow \{0,1\}^{4}$
and I want to count all functions that have a specific entry, e.g 00, with a specific structure(first n bits equal with the last n bits). $F(00)=\{0000, 1010, 0101, 1111\}$ in this case

Entry 00| 0000
Entry 01| 0100
Entry 10| 0001
Entry 11| 0100

For example here $F(00)=0000$ and since $00=00$, this function should be counted

Entry 00| 0001
Entry 01| 0000
Entry 10| 0000
Entry 11| 0000

In this function since $F(00)=0001$ and $00\neq 01$, it should not be counted

If you want the function to have the property for one input, say $x$, which is fixed ahead of time, you just focus on that output vector
$$
f(x)=f(x_1,\ldots,x_n)=(z_1,\ldots,z_{2n})
$$
and the condition $z_i=z_{i+n}$ holds with probability

$$P(given ~row ~is ~good)=\frac{2^{n}}{2^{2n}}=2^{-n},$$
since in this case you don't care what is happening in the other rows.

If you want this property to hold only for your selected input, this happens with probability

$$P(given~ row ~is ~good) (1-P(given ~row ~is ~good))^{2^n-1}=2^{-n}[1-2^{-n}]^{2^{n}-1}$$
 which can be estimated for large $n$ from above and below by using
$$
1-k\varepsilon+\frac{k(k-1)}{2}<[1-\varepsilon]^k<1-k\varepsilon
$$
where $\varepsilon$ is small and positive.


Number of possible functions for a PRP In the Coursera crypto course, Dan Boneh states that if $F: K \times X \to Y$ is a PRF, if the size of the input space $X$ is $2^{128}$, and the size of the output space $Y$ is also $2^{128}$, then there are $(2^{128})^{(2^{128})}$ different functions that map the set $X$ to the set $Y$.

I guess that's because we can see this as a sampling with replacement : for each element in $X$ we pick a random element in $Y$, and replace the element in $Y$ before picking again. Once we're done, that make a random mapping from $X$ to $Y$, and so there are $(2^{128})^{(2^{128})}$ possible mappings.

What about PRPs? Because in a PRP the mapping functions must be invertible, can we see them as a sampling without replacement? And so, the number of possible functions from $X$ to $Y$ for a PRP should be $(2^{128})!$, is that right?

Yes, that's right. This is also why the key size can be much larger than the block size. The idea of a (well-distributed) key is that it pseudo-randomly chooses a function from X to Y.

So for instance AES can have a block size of 128 and a key size of 256 (and it has) because there are "only" $2^{256}$ keys while there are $2^{128}!$ possible functions / permutations. This is more explicitly explained here.


Define "cryptographer" I often encounter the phrase "I am not a cryptographer".  Is there a generally accepted definition for who is a cryptographer?  What qualifications would be expected?

For instance, should that person be expected to hold a relevant degree, or to have published $N$ papers?

Alternatively, would someone performing cryptanalysis or analysis of cryptographic protocols in a professional capacity be considered a "cryptographer", even without the academic background?

I had a similar conundrum myself when I accepted a position doing very crypto-specific engineering work in industry. They asked me what my title should be, and I didn't really know. I asked my undergrad advisor and he said, effectively, that someone who

builds cryptosystems, and
proves them secure in a precise way, using
modern proof techniques and security reductions

is a cryptographer. Cryptographers also publish attacks from time to time, but most people would call an attack-focused researcher a 'cryptanalyst'.

In my mind, the important difference between a cryptographer and someone who otherwise works in security is precision in definitions and arguments.

I should state, though, that this distinction is rarely useful in practice, because really good ideas can come from pretty much anywhere. Don't get hung up on terminology.


Hashing a message with a length that isn't a multiple of 8 bits NIST FIPS 180-4. “5.1. Padding the Message.”

  Suppose that the length of the message, $M$, is $l$ bits.

Is there any library that can receive a message of length (in bits) which is not a multiple of $2^3$?

Such libraries most certainly do exist; see here and here for two examples.

A hash implementation that can handle odd-sized bit strings is called "bit-oriented"; most implementations don't bother with it (just because the requirement just doesn't come up that often), however, a few do.


Modes of operation for Public Key Encryption schemes Symmetric key encryption schemes have well defined modes of operations for achieving deterministic (ECB) or Randomized (CBC, OFB, CTR ) etc. and other applications of the same. But are they defined for public key encryption schemes also ? i could not find on google.

Also are they applicable for PKE schemes ?

No, usually you are required to use hybrid cryptography.

ECB, CBC etc. are defined for block ciphers. Although you could possibly apply them to asymmetric cryptosystems, it would make little sense:

performing sequential asymmetric cryptography is not efficient, block ciphers are much more efficient
in general there will be a lot of overhead per block, e.g. due to per-block padding (where block ciphers don't have any overhead per block)
the block size is usually rather large

So in general a symmetric key is generated, which encrypts the plaintext, and then the symmetric (session or data) key is encrypted and send with the ciphertext.

Note that ECB is usually not secure. For asymmetric ciphers, the plaintext (or key) is normally wrapped with random padding before encryption. So ECB is not deterministic for most asymmetric encryption primitives for which such random padding is applied.


How do decryption algorithms determine whether your attempted passphrase is correct? Judging by the algorithm on the Blowfish Wikipedia article, there is no way for the process to fail with an error. How then does GnuPG know when to tell you your password is correct when decrypting a file, rather than proceeding to decrypt meaningless data?

An important property of a ciphertext is that it has to be indistinguishable from truly random data. This allows the encryption cipher to produce ciphertext that reveals no information about the plaintext (other than size) or the encryption key. In fact, this property even allows encryption algorithms to act as pseudorandom byte generators by simply making them generate a stream of random ciphertext.

In the case of stream ciphers, decryption is the result of XORing each ciphertext byte with its corresponding keystream byte in sequence. If the keystream byte corresponding to the ciphertext byte is correct, the result of the XOR will yield the original plaintext byte. Since ciphertext cannot be made to provide any information regarding the plaintext, it follows that it also cannot be made to reveal whether the XOR of a certain keystream byte yielded a correct plaintext for the byte or not. Otherwise, the cipher would be clearly broken and allow us to basically query it for information regarding the plaintext.

A similar principle applies to block ciphers such as Blowfish, except those ciphers operate on entire blocks of bytes instead of individual bytes, and also employ other operations such as substitution in tandem with XORs, organized in structures such as Feistel networks.

Therefore, when it's important to be able to inform the user whether a decryption operation has succeeded in yielding the expected data, cryptography engineers use Message Authentication Codes. Hash-based MACs allow a candidate plaintext to be compared against an authenticated hash value. If the check passes, then we know that it is the correct plaintext and are then able to notify the user that the decryption function was successful as intended.

Generally, if you want to verify the integrity of encrypted data as it goes through the wire to reach someone, you would generate a MAC for the ciphertext. But if you also want to verify that the decrypted plaintext is correct (as seems to be your case here,) then you would generate another MAC for the plaintext and send it along with the ciphertext.

While hash-based MACs are probably the preferred way to do this, they aren't the only way to verify successful decryption. For example, TrueCrypt will check the first four bytes of the volume header in order to see if decryption is successful. This approach is likely to be more error-prone than HMACs in most applications, however.

Finally, there are block cipher modes of operation (such as Galois Counter Mode) that grant block ciphers such as Blowfish or AES the ability to self-authenticate. This pretty much allows a ciphertext to verify its own integrity without the need for an external check. Depending on what you're trying to accomplish, you may want to investigate both HMACs and Galois Counter Mode and decide which offers the verification properties you're looking for.


how to use salt to sign a message and how is it effective? I've had an assignment to sign a file using hash and salt, so I read about salt and I got why it's important when it comes to password, but not to sign messages.

How do I sign something using salt? The only way I could think of is that I add the salt to the message then hash both and then send the hash along with the salt (encrypted of course)… but it makes no sense to me.
Even if what I said earlier is how it's done, it's not useful at all. How and why would I use salt to sign a message ?

There are a couple of reasons why a salted signature would be helpful. It really depends on the particular implementation of a system.

For example if your message is encrypted, then signing with a salt could give you a different signature for the same message each time. This can be very important depending on the situation.

If the salt was actually provided by the client, then it could be used to prevent man-in-the-middle replay attacks. But there may be better ways to achieve this.


Does chacha20-poly1305 require new key for every encryption process? As I know chacha20-poly1305 is stream cipher. Does that mean for every encryption process require a new key?

You do not require a new key. You use a different initialization vector (IV) for every message.

As long as you use a different pair of (key, nonce) for each message you retain the confidentiality and integrity of messages. The nonce is the initialization vector.


Using XOR to derive a data key for ECIES I have been thinking about a rather simple enhancement for (EC)IES / RSA-KEM. The scheme would allow you to encrypt data while the calculation of the session / data key can be performed afterwards or in parallel. It would also allow you to encrypt for multiple recipients.
Anyway, the scheme would simply be:

Generate a (random) symmetric key: $K_d$;
Encrypt data with key $K_d$ using a symmetric cipher, resulting in $C$;
Generate an ephemeral key pair with public key $\widetilde{P}$;
For each recipient enumerated by $i$:

Calculate a session key $K_i$ by performing key agreement with a static public key of the receiver (followed by a KDF);
Perform $A_i = K_i \oplus K_d$;
The messages consist of a quad $(i, A_i, \widetilde{P}, C)$ where the $i$ is just used to indicate the recipient.

To decrypt you would simply perform the key agreement again, followed by $K_d = K_i \oplus A_i$. For RSA-KEM the ephemeral key pair derivation is not required, and $\widetilde{P}$ is replaced by the result of the RSA-KEM operation with the public key of the receiver.
This seems to be a specific version of a simple Multi-Recipient Symmetric Encryption Scheme using Secret Sharing combined with (EC)IES or RSA-KEM. Obviously you'd have to store the $A_i$ values with the ciphertext, so that is a disadvantage compared with the normal ECIES approach.
Are there any particular problems with above approach? Are there more secure / flexible / efficient schemes to do the same?

As written, it makes an additional security assumption on the symmetric cipher; that the attacker can't flip bits in the key (and modify the ciphertext) to gain some advantage.  That is likely true for most ciphers we would use in practice, but is nevertheless an additional assumption.
This is not difficult to fix; we don't select a random symmetric key $K_d$, instead, we generate a random value $J$, and set $K_d = \text{Hash}(J)$.  Then, in step 4.2, we then instead set $A_i = K_i \oplus J$.


Inserting a backdoor into a cryptographic hash function I'm curious as to how a backdoor can be built into a hash function. What might it take the form of? What's probability of getting one that can be backdoored in a way that can actually undermine its security? Could this backdoor be asymmetric?

Here is a "backdoored" hash function:

Let $p = 2q + 1$ be a big prime of length $2048$ bits, such that $q$ is also prime. Let $a$ be an integer of order $q$ modulo $p$, i.e. $a \neq 1$ but $a^q = 1 \pmod p$; it can be shown that $a = 4$ is always a valid solution. Let $s$ be a (secret) integer between $1$ and $q-1$, and let $b = a^s \pmod p$.

Then define operation $\phi(x, y)$ such that input $x$ is a sequence of $2048$ bits, and $y$ is a sequence of $2042$ bits (not $2048$); the output is a $2048$-bit value:

Concatenate $x$ and $y$ and split it back into $u$ and $v$, such that $u$ and $v$ both have length $2045$ bits each: $$u || v = x || y$$
Interpret $u$ and $v$ as unsigned big integers, using some convention (e.g. big-endian). Note that both $u$ and $v$ are lower than $2^{2045}$.
Compute: $$z = a^u b^v \pmod p$$
$\phi(x, y)$ is the encoding of $z$ over exactly $2048$ bits (there again, using a fixed convention).

Note that $\phi(x, y) \neq 0$ for all $x$ and $y$.

Now that you have $\phi$, define a hash function $h$ as follows:

For input $m$, pad it with some "removable" padding sequence (e.g. a Merkle-Damgård compliant padding) so that the total length of $m$ is now a multiple of $2042$.
Split $m$ into $n$ blocks of $2042$ bits (denoted $m_1$, $m_2$, ... $m_n$).
Define $x_0 = 0$ (a sequence of $2048$ bits, all of value $0$).
For $i = 1$ to $n$, define: $x_i = \phi(x_{i-1}, m_i)$
Define the hash output $h(m)$ to be SHA-256($x_n$).

Let's see the security of this construction:

Preimages: for a given $t$, finding $m$ such that $h(m) = t$ implies, in particular, finding some $x_n$ such that SHA-256($x_n$) $= t$, so our function $h$ is at least as much preimage-resistant as SHA-256.
Second preimages: second preimages are a special case of collisions, so $h$ will resist second preimages at least as well as it resists collisions. Ideally we would want something better (i.e. resistance up to $2^{256}$ for second preimages, even though collisions can be found in effort $2^{128}$), but since collisions should be infeasible anyway, this is probably acceptable.
Collisions: suppose that $m \neq m'$ and $h(m) = h(m')$; $m$ yields a sequence of $n$ words $x_1$ to $x_n$, while $m'$ yields $x'_1$ to $x'_{n'}$. We suppose, without loss of generality, that $n' \geq n$. Then one of the following holds:

$x_n \neq x'_{n'}$ but SHA-256($x_n$) $=$ SHA-256($x'_{n'}$). We have found a collision on SHA-256.
There is an index $i$ such that $x_{i-1} \neq x'_{i-1}$ but $x_i = x'_i$. This means that we know integers of at most $2045$ bits $u$, $v$, $u'$ and $v'$ such that $(u, v) \neq (u', v')$, but $a^u b^v = a^{u'} b^{v'} \pmod p$. This implies that $a^{u-u'} = b^{v'-v} \pmod p$. Since $a$ and $b$ have order $q$ (greater than $2^{2046}$) and $u-u'$ and $v-v'$ cannot be both $0$, then $u-u'$ and $v'-v$ are invertible modulo $q$, and we can write $b = a^g \pmod p$ with $g = (u-u')/(v'-v) \pmod q$ (i.e. $g$ is the secret value $s$). We just solved discrete logarithm.
There is an index $j$ such that $n \lt j \leq n'$ and $x'_j = x_n$. By "rewinding" the steps this implies that either we find an instance of the previous situation ($a^u b^v = a^{u'} b^{v'}$ for $(u,v) \neq (u',v')$), or we have $x'_{j-n} = x_0$, which is not possible since $x_0 = 0$ and $x'_{j-n} = \phi(x'_{j-n-1}, m_{j-n}) \neq 0$.

Therefore, finding a collision on $h$ requires either finding a collision on SHA-256, or solving discrete logarithm modulo $p$. Since both are computationally infeasible (as far as we know), this function $h$ can be deemed "secure" as a hash function.

The backdoor is the knowledge of $s$. In all of the above, we used the $a$ and $b$ values "as is". The value of $s$ is not needed anywhere. However, if you know $s$, then you can compute collisions at will:

Generate two random blocks $m_1$ and $m'_1$. Compute the corresponding $x_1$ and $x'_1$.
Let $u$ be the first $2045$ bits of $x_1$, and $u'$ be the first $2045$ bits of $x'_1$.
Compute $k = (u-u')/s \pmod q$
If $k$ is less than $2^{2045}$, or greater than $q - 2^{2045}$, then you can find $v$ and $v'$ of $2045$ bits each, such that $v'-v = k \pmod q$, from which you can infer two blocks $m_2$ and $m'_2$ that match $(u,v)$ and $(u',v')$, respectively. You have your collision.
The condition on $k$ works with probability at least $1/2$. If you were unlucky, just try again with new random blocks $m_1$ and $m'_1$.

The above is thus a hash function with a backdoor. However, mind the fine print:

The backdoor is explicit. While the knowledge of $s$ is necessary to exploit the backdoor, everybody knows that it is there. Conversely, if you generate $a$ and $b$ as NUMS numbers (thus with $s$ convincingly unknown to everybody), then the hash function is "backdoorless" (but also useless).
When you exploit the backdoor, you produce two colliding messages $m$ and $m'$, from which anybody can recompute $s$. Thus, the backdoor is "one-shot".
The backdoor allows finding collisions, not preimages. A hash function designed to have a backdoor for preimages would need something else. Ideally you would use a one-way trapdoor permutation, but (to my knowledge) no such object is currently known, that would yield an output of suitable length (e.g. 256 bits).


OpenSSL encrypted text length OpenSSL block ciphers return length of the text as output of the encryption (envelope_seal()), and If I have to send the length over network, I append the length with the ciphertext as I can transmit only one field and envelope_open() needs the length of the ciphertext. Is there any other way that I can calculate the length of the ciphertext, which contains null terminated characters, on the receiving side?

Most binary network protocols are already bounded. So if you just send the ciphertext (or the IV and the ciphertext) then the length will be known by the transport mechanism. Otherwise the method of communicating the length is entirely up to your imagination as long as you can map it to a presentation that is acceptable to your transport protocol.

Null termination characters within ciphertext or tag are not an issue for binary connections; null termination characters are only an issue for C-style null terminated strings. You don't want to send binary data directly over a text-based connection; you need a form of encoding such as base 64 encoding if you want to do that. The output size of base 64 encoding is determined during decoding, although the base 64 input must of course be bounded as well.

Note that you need some form of integrity protection of the IV and ciphertext if you want to securely send/receive ciphertext. So you need an authenticated mode of encryption or an authentication tag created by a MAC.


Definition of indistinguishable schemes Let $\mathsf{Exp}_{A,\Pi}(\lambda)$ be some indistinguishability experiment that finally outputs 1 if A outputs $b'$ that satisfies $b' = b$, otherwise 0. Then the textbooks often define the security like this:

  If for all PPT adversary A, there exists a negligible function $\mathsf{negl}$ satisfies $\Pr[\mathsf{Exp}_{A,\Pi}(\lambda) = 1] \leq 1/2 + \mathsf{negl}(\lambda)$, then we say $\Pi$ is a indistinguishable scheme...

However, suppose there is an adversary A that wins the experiment in possibility 0.4, then we can construct another adversary A' that call A as an oracle, and output $b' = 1 - {b'_{A}}$ (where $b'_{A}$ is the output of A), then A' will win the experiment in possiblity 0.6.

So it seems that if $\Pi$ holds the indistinguishability, then there should not exist any adversary A that $\Pr[\mathsf{Exp}_{A,\Pi}(\lambda) = 1] < 1/2 + \mathsf{negl}(\lambda)$, for it also means an A' that $\Pr[\mathsf{Exp}_{A',\Pi}(\lambda) = 1] > 1/2 + \mathsf{negl}(\lambda)$.

Hence my question is, why we don't define the indistinguishability directly via the conditional $\Pr[\mathsf{Exp}_{A',\Pi}(\lambda) = 1] = 1/2 + \mathsf{negl}(\lambda)$?

Note that in the definition you gave, it says that in order for $\Pi$ to be an indistinguishable scheme, then the above inequality must hold for all PPT adversaries.

  So it seems that if $\Pi$ holds the indistinguishability, then there
  should not exist any adversary A that
  $\Pr[\mathsf{Exp}_{A,\Pi}(\lambda) = 1] < 1/2 + \mathsf{negl}(\lambda)$, for it also means an A' that
  $\Pr[\mathsf{Exp}_{A',\Pi}(\lambda) = 1] > 1/2 +\mathsf{negl}(\lambda)$.

If there is an adversary $A'$ such that $\Pr[\mathsf{Exp}_{A',\Pi}(\lambda) = 1] > 1/2 +\mathsf{negl}(\lambda)$, then $\Pi$ cannot be indistinguishable, by definition.

Another way to see it is that the only way $\Pi$ can be indistinguishable is that all adversaries $A$ have probability $1/2 + \epsilon$, at most, of guessing correctly, where $\epsilon \leq \mathsf{negl}(\lambda)$. Then, following your reasoning if you define an adversary $A'$ that simply outputs the opposite than $A$, its probability will be $1 - (1/2 + \epsilon) = 1/2 - \epsilon$, so the scheme is still indistinguishable.

  Hence my question is, why we don't define the indistinguishability
  directly via the conditional $\Pr[\mathsf{Exp}_{A',\Pi}(\lambda) = 1] = 1/2 + \mathsf{negl}(\lambda)$?

That definition would not be right, as the term $\mathsf{negl}(\lambda)$ is not actually a value, but an undetermined bounded function.

As mentioned in another answer, I personally don't like that definition either, although it is used in some places (see, for example, definition 7.2 in the Lecture Notes on Cryptography, by Goldwasser and Bellare). I also prefer definitions given in terms of the advantage of the adversaries, which is defined as $\mathsf{Adv}_{A,\Pi}(\lambda) = |\Pr[\mathsf{Exp}_{A,\Pi}(\lambda) = 1] - 1/2|$. In this case, the definition would be something similar to this:

  If for all PPT adversary A, there exists a negligible function $\mathsf{negl}$ that satisfies $ \mathsf{Adv}_{A,\Pi}(\lambda) \leq \mathsf{negl}(\lambda)$, then we say $\Pi$ is a indistinguishable scheme...


How can one encrypt with RSA (or ElGamal) without revealing whom the ciphertext is intended for? Imagine Alice wants to encrypt for Bob and post this encryption publicly, so that only Bob can decrypt but no one can other than Alice or Bob tell that the message was encrypted for Bob.

The naive approach leaks some information.  If Alice posts $y = x^e \bmod{n}$, then an observer can conclude that the recipient has a public key $n > y$, and can therefore eliminate many guesses as to whom the recipient is. Potentially this advantage can be amplified, depending on the higher-level protocol.

My thought was Alice can generate a random $r$ of size $2^{\textrm{L}}$, where $L$ is the largest allowable key size, and post $y + rn$.  Then, Bob can consider the residue mod $n$ when decrypting.

Similarly, in ElGamal, Alice can pick random $r_1$ and $r_2$, then post $\langle c_1 + r_1 p, c_2 + r_2 p \rangle$.

Do these constructions achieve their intended goals?

A use case for this is in PGP encryption.  Assuming Alice strips the key id from the outer packet, can she post a PGP encryption without leaking information about her intended recipient?

Your aim is to have a number $y' = y + rn$ that gives an uniform distribution over any valid key modulus $n'$, so that no keys can be ruled out. For that, you need $y'$ to be uniformly distributed modulo a larger number. How large is the question.

If you have uniform samples from $[0, 2^l-1]$, according to this (pdf, page 20 talking about key generation, but should apply here) they are uniform (enough) modulo $n < 2^k$ if $l = k + 64$. Hence, to have your $y'$ be uniform for keys up to $L$ bits you should draw $y'$ from $[0, 2^{L+64}-1]$.

Your approach gives even larger numbers ($2^{L+lg(n)} > 2^{L-lg(n)+64}$ with a realistic $n$), so that part's covered, but it may leak the minimum size of $n$, since if $r = 2^L$, no key with $n'<n$ could result in so high a number $y'$.

You should instead draw $r$ from $[0, 2^{L-lg(n)+64}-1]$, rounding the exponent so that $y'$ can reach $2^{L+64}-1$, then throw away those $r$ values that give you $y' > 2^{L+64}-1$.

(You could find a better upper bound for that random number generation, but generating uniform random numbers that aren't modulo a power of two is itself tricky. At worst you'll be throwing away half the $r$ values, so that should be easy enough.)


Best hash size for hash trees I want to know if having a 8-byte hash value is better than 16-byte hash value for use within hash trees.

My mind tells me that the shorter the hash value, the better. But doesn't a smaller hash value make it easier to invert? More strings would lead to the same hash value.

I guess this is very opinion-based, but I'd like to hear different reasoning for your answers.

The shorter the hash value the less effort for the attacker to brute force it. If the output is 16bytes then the attacker must spend $2^{128/2}$ "time" to find a collision. If it was 8bytes it would need $2^{64/2}$


Gap problem for Learning With Errors Informally, a "Gap problem" arises when solving the computational (or search) version using an oracle for the decisional version. This definition of Gap Problem was introduced by Okamoto and Pointcheval in this paper, originally related to Diffie-Hellman problems.

For example, the Gap Diffie-Hellman Problem (GDH) is to solve the Computational Diffie-Hellman (CDH) problem with the help of a Decisional Diffie-Hellman (DDH) Oracle (which answers whether a given triple is a Diffie-Hellman triple or not).

In the Learning With Errors (LWE) setting, is there any "gap" problem (or similar) that can be assumed to be hard? That is, which computational problem can be defined that is still hard when using an oracle for the Decision LWE? I know that there are some results (see papers from Regev and @chris-peikert) that prove the equivalence of the decision and search versions of the LWE problems. I guess that this means that a "strict" gap problem cannot be defined, since there is a reduction from the Decision LWE to the Search LWE, but maybe some other variant of LWE or related problem still applies.

I am not aware of any work that proposes a Gap problem related to LWE. The reason is probably that LWE is an average-case problem specifically designed for the use in crypto. However, there are the related worst-case problems, e.g. the shortest vector problem (SVP), that come with a Gap version. So, you might want to have a look at GapSVP and GapCVP.


How to reduce factorization into Independent Set Problem? Is it possible to reduce RSA (basically factorization) into a NP-Complete problem, concretely the ISP (Independent Set Problem)?

If so, which as far as I know is possible, how is it done?

I can't imagine how a problem like factorization could be interpreted as a binary symmetric matrix.

IF can be reduced to 3SAT. This was already addressed here before - https://cs.stackexchange.com/questions/11718/generating-3sat-circuit-for-integer-factorization-example

It should easy to convert that 3SAT to ISP - http://www.mi.fu-berlin.de/wiki/pub/ABI/ComputabilityComplexityWS11/Complexity2.pdf


risk of attacker decrypting RSA ciphertext without public or private key As I describe in my previous question I am trying to decide if it's worth it for me to use the Offline Private Key Protocol in creating some long term private archives, instead of just going with a simple symmetric encryption like AES-256. The answer to that question pointed out that using RSA to encrypt the symmetric encryption keys cannot make the solution any more secure. But since there are practical advantages I wanted to ask a further question:

When we say "RSA is broken" do we mean that a practical attack is discovered to retrieve the private key from the public, or do we mean that given a ciphertext and no knowledge of either the private or the public key the attacker can decrypt the data? I'm thinking that perhaps in my case the risk of the public key leaking from a trusted system that is doing the key-wrapped symmetric encryption is pretty small. And if by "broken" we mean the first alternative, and if we assume for a moment that the risk or the RSA public key leaks is zero (i.e. it's not public anymore) I am wondering if the more practical RSA+AES solution is for some reason actually less secure, rather than just equally secure, than the plain symmetric method.

Thank you!

When we say "RSA is broken" do we mean that a practical attack is discovered to retrieve the private key from the public, or do we mean that given a ciphertext and no knowledge of either the private or the public key the attacker can decrypt the data?

First off, we always assume the attacker has the public key. Someone saying "RSA is broken" could mean either. The first is a key recovery attack; the second is a message recovery attack. The second (finding $p$ from $c=p^e\bmod{n}$) is what is known as the RSA Problem. It just so happens that currently the fastest way to solve the RSA problem is to recover the private key (think factoring) and then recover the plaintext. It has never been shown that there doesn't exist a better way to find $p$ however (for more on this, see this question).


How AES-CTR is used in AES-GCM to generate cipherText and a authTag to authenticate the cipherText and authData? Let,

Inputs:

key = key used to encrypt the plaintext.
IV = initialization vector.
plainText = plaintext need to be encrypted.
authData = addition data need to be authenticated which is not encrypted.

Outputs:

cipherText = encrypted plain text.
authTag = Authentication tag required to verify authenticity of cipherText and authData

Then,

cipherText = aes-ctr(key, IV+1, plainText);
authTag = AES-CTR(key, IV, keyDependentPoint-H(key, (cipherText-aes-ctr + authdata)));

Note: IV+1 is used for generating cipherText and the first IV is saved for encrypting the generated hash at later point of time when cipherText is generated.

Ref: GCM-Galois Counter Mode with IV & Cipher

Ref: Galois/Counter Mode

am I doing any mistake?

This question is asked to ensure the above relation of AES-GCM with AES-CTR is correct and help others to understand AES-GCM in a simple and convincing way.

This question is derived from this question.

AES-GCM,or more generally GCM is a mode of operation for a symmetric block cipher. It stands for Galois/Counter Mode. It provides Authenticated Encryption, guaranteeing both confidentiality (data secrecy) and integrity (data authenticity).

Confidentiality is provided by the Counter Mode: roughly a counter is encrypted and the output is xored with the plaintext. If more than one block has to be encrypted, the counter is incremented.

To be secure, GCM requires that the counter is used only once (See here for details Nonce reuse vulnerability). It is usually generated as the concatenantion of a NONCE and an actual counter (e.g.: $NONCE || 0...0)$.

Please note that the standard GCM construction uses the encryption of the counter from 1 to do the actual encryption, while the encryption of the zero-counter is used in the AuthTag computation

From a confidentiality point of view they are the same. Indeed, AES-GCM is defined as AES-CTR + GMAC as authentication code.

The difference is that AES-CTR does not provide integrity protection and an AuthTag has to be added (could be HMAC, or CBC-MAC for example); on the other side the AES-GCM provides both protection (confidentiality and integrity).


Application of uni-directional proxy re-encryption? What kinds of applications is uni-directional proxy re-encryption applicable to?

I learned some applications that proxy re-encryption can be used, which are email and file sharing scenarios.

All of the scenarios that I am aware do make sense when we use bidirectional proxy re encryption.
When would uni-directional proxy re encryption can make sense?

In bidirectional proxy re-encryption, there's an efficient algorithm to transform a re-encryption key from Alice to Bob in a re-encryption key from Bob to Alice. For example, the BBS98 proxy re-encryption scheme has re-encryption keys of the form $rk_{A \to B} = \frac{b}{a}$, where $a$ and $b$ are the private keys of Alice and Bob, respectively; it is easy to see that this scheme is bidirectional, since the algorithm to transform $rk_{A \to B}$ into $rk_{B \to A}$ is simply the modular inversion:
$$rk_{B \to A} = (rk_{A \to B})^{-1} = (\frac{b}{a})^{-1} = \frac{a}{b}$$

Now, let's recall what's the main functionality of PRE: secure delegation of decryption rights from one user (Alice) to another (Bob). We usually think of unidirectional PRE schemes since in most cases the delegation is inherently unidirectional. For instance, in the typical email example, I can delegate decryption rights to my secretary while I'm on holidays so he can decrypt my emails. This, however, doesn't mean that my secretary wants me to be able to read encrypted emails directed to him. Similarly, in a file sharing scenario, I may share some encrypted documents with you, but you don't necessarily want to do the same with me.

Hence, bidirectional PRE schemes are only useful when there's a complete symmetry in the trust relationship between Alice and Bob. This may happen in some scenarios, but it's not common.


In PKI, with a hash-encrypted message (first hashed, then encrypted), how is the plaintext ever retrieved? Consider a normal PKI encryption flow - hash the plaintext, then encrypt the hash with the private key of the sender and then encrypt it with the public key of the recipient. All this is good - and I am good even with the decryption steps taken by the recipient.

I still don't understand how the recipient gets the plaintext from the hashed ciphertext. The recipient can easily 'decrypt the hashed plaintext'. But then what - all you are left with is a hashed plaintext. There is no way to un-hash it. How does the recipient retrieve the plain text message from the hashed message?

Signature generation is not encryption with the private key. Still, the basic flow of what you describe is correct for signature generation. However, the verification step is where everything derails.
As indicated in the comments, it is impossible to reverse a cryptographic hash. However, for signature verification, it is assumed that the verifying party knows the signed message M. The verifying party can then re-calculate the hash and use that as input for the rest of the verification procedure. So if the verifying party doesn't have the message M then you simply need to send it together with the signature.

See for instance step 2 in RSA signature verification specified for the PSS signature scheme:

Input:
      M      message to be verified, an octet string
      ...

and then later:

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

The verification procedure may indeed involve retrieving the original hash and perform comparison. However, other signature verification functions such as the verification function of ECDSA may simply require the re-calculated hash as input for the verification function. So in that case the original message hash isn't even retrieved from the signature.

There are schemes that perform message recovery. A few of those schemes are outlined in ISO/IEC 9796-2: Digital signature schemes giving message recovery. However, they are not often used anymore. In that case the message itself - or at least part of it - is included with the hash, the message is still not retrieved from the hash.

Remember that signatures do not provide message confidentiality. If you also want to keep your data secret then you should encrypt the data and signature over the data.


Calculating the number of rounds required for block cipher with known differential Suppose we have a 128-bit block cipher for which the best two-round differential holds with probability $p = 2^7$. Suppose as well that this differential is iterative and that the best differential attack will be formed when using this differential.

How many rounds would the block cipher need in order to be resistant to differential cryptanalysis?

I think that you typed the probability of two rounds incorrect and it should be $2^{-7}$. By assuming that, you should choose the numbers of rounds in a way that the number of (chosen plaintexts, chosen ciphertext), exceeds of the number of  (plaintext, ciphertext) that are available(for example with today's computational devices is bounded). As you told the probability for two rounds, if you choose 15 rounds, the number of (chosen plaintexts, chosen Ciphertexts) will be about $15 \times 7 = 105$, that we can use it as a bound for this. You should be considered that it is a theoretical bound and choosing the number of rounds based on 2 rounds estimation is somehow not precious.


ElGamal on elliptic curves attack model (CPA,CCA1,CCA2)? I can't find relevant literature discussing three attack models of the ECC-ElGamal algorithm (CPA, CCA1, CCA2)
ECC-ElGamal algorithm: ElGamal with elliptic curves
I only know that ElGamal belongs to CPA, but I can't determine which one (CPA, CCA1 or CCA2) belongs to in the case of ElGamal on ECC.
It would be better if there is a source of relevant literature!!! Thank you very much!!

In Tsiounis and Yung's proof of the IND-CPA semantic security of El Gamal, the only assumption made is that the decisional Diffie-Hellman problem is hard. The proof transfers easily to any group where the decisional Diffie-Hellman problem is hard, including we believe (non-pairing-friendly) elliptic curve groups.
Similarly all El Gamal instantiations are trivially CCA2 attackable (given a ciphertext $(rG,rA+M)$, request a decryption of (for example) $(2rG,2(rA+M))$ to recover $2M$ and hence $M$.
As far as I know the semantic security of any instance of IND-CPA secure El Gamal under CCA1 is an open problem.
On the pairing-friendly elliptic curve point, note that for such curves there is a means of checking whether a given El Gamal encryption is an encryption of a hypothetical message e.g. to check that $(P,Q)=(rG,rA+M)$ compute the pairing of $P$ and $A$ with the pairing of $G$ and $Q-M$. If the equality of the pairing holds, then so does the equality of the encryptions. This is because the decisional Diffie-Hellman problem is soluble in these groups.


Which is the correct duration of an AES execution? I  want to verify if my trigger gives me the correct duration of an AES-128 execution in a specific chip; I need only to have the duration of an AES block encrypt without any other functionality.

The frequency of the CPU is 128 MHZ, the frequency of the AES execution is 64 Mhz.

How can I calculate the duration of an execution of AES in order to verify with what I found with my oscilloscope?

The duration will depend on the chip and on the implementation.

In a good implementation, the duration of encryption is independent of the combination of the secret key and the message to encrypt (otherwise a so-called timing attack to gain knowledge on the key and/or the message is possible).

You need a model of the chip and its cache and the assembly code to do some real estimates (usually giving you a range of minimal and maximal cycles needed). For tight bounds there are commercial offers, e.g., by Absint. It is a feasible, but not a trivial task.


Is it safe to XOR-combine hashes by rotating them first? I have a small number of hashes.
I would like to combine them into a single hash.
XORing the hashes ignores their order, which is important.  Also, it could lead to a result of zero if there were an even number of identical items hashed.
Would rotating each hash (by a distance equal to the item's position) before XORing be secure?

First of all, if the order is not important then rotating a hash value depending on the order before using it would of course be counter-intuitive. Now the hash of a specific element is fully dependent on the order.

Generally I would not advice XOR-ing hashes.
Single rotation won't work especially if you combine multiple hashes - as you've indicated it would be easy to find a collision where two hashes cancel each other out. But you've already covered this.
XOR-ing would also make collisions easier to calculate, because the XOR of two hash values can also create a collision. Of course this won't change the order of finding a collision, but a XOR is still significantly faster than calculating a hash.
I could also imagine a scheme where you XOR (rotated) hashes that have a similar highest bit set. I think this could quickly create hashes that have the initial bits set to all zero. You could also XOR hashes that have a small Hamming distance. Either of these methods would create a set of hashes that have more than a normal amount of bits set to zero. It seems likely that these have less collision resistance than the initial hash. The fact that you can also use rotated hashes for this would make it even easier to create such attacks.

Instead you could think of sorting the hashes before you hash them (using a binary compare). That way you get a unique hash for a unique set where the order is ignored, even if it can contain identical elements. The disadvantage is that you cannot calculate a new hash value by adding a hash value after the final hash calculation is performed.


ED25519 Child Key Derivation Let's say I generate a keypair for a user with go's ed25519 package:

pub, private := ed25519.GenerateKey(nil)

And I want to generate additional child keys as signing identities for my user. Is it more secure to not use that public key created at initial generation and instead derive a new child private key as a signing identity? Or is creating another child key exactly as secure as using the public key created at generation?

A general common technique is used in PGP
"key rings" or "key chains". You generate a master public-key pair and distribute your master public key. Use this master private key to certify your other generated keys so that you can store your private key securely, probably off-line, and use the other keys for daily usage. With your master public key, the certificates of the other generated keys in the chain can be verified.


Is there a symmetric cipher that is explicitly designed to be slow? I am trying to find a symmetric cipher that is explicitly designed to be slow.  I realize that this is generally not desirable, but I'd like many cycles and lots of electronic action.  I could modify a cipher make a Fiestel network have a million rounds, but I'm trying to find something "provably slow" that is akin to a memory-hard function but without the memory.

The motivation for this is that I want a structured way to create test vectors for an asynchronous IC library that are "random-looking" but repeatable for simulation.  It's an easy way for me to keep track and cut up the problem on the cluster.  The reason that I don't want to use a hash function is architectural. I want to structure of a key schedule and data schedule with a dependency.

Has anyone ever come across a symmetric cipher design to be slow?

A memory hard PBKDF (or password hash, same thing, different name) without memory hardness is basically just a repetition of a hash or cipher.  In that case you might was well be the repeated application of a block cipher (with an alterated key if needed) or - indeed - increase the number of rounds.

The issue with increasing the number of rounds is that you also need to extend the key schedule. But since you're not trying to achieve more security, you could simply repeat previously calculated keys (if the key schedule itself cannot be easily extended).

Note that bcrypt is a password hash that uses a block cipher rather than a hash function. You could check if that suits your needs.


What is the current time limit of Keccak inversion? All sub-functions are referenced with respect to Keccak. It’s my understanding that the sub-function theta() would result in the largest resource allocation when attempting to invert Keccak. If this is incorrect please edit, comment, or answer. But for this reason I would argue it’s the most valuable sub-function to study if we are to determine the theoretical time limit of Keccak inversion. This question is asking specifically the estimated inversion time of theta^-1(o,n), when the inverting function is provided with some random output (o), and the number (n) of recursive iterations of theta(i,n) used to generate the output. Where theta(i,n) is initially seeded with what I will assume is some uniformly random 1600 bit input (i), and the number (n) of recursive iterations. See pseudo code provided.

def test_0(n):
    i=set_main_build(64,25)
    a_copy=list(i)
    for index in range(n):
        i=theta(i)
    o=list(i)
    return(o,'break',a_copy)

Now my serious curiosity is if someone can manage to execute theta^-1(o,n) where n > 10^6. But I fear finding theta^-1() in the wild is hard enough, but at last if someone has built a faster implementation I would most certainly like to see it. I'm trying to learn C, but even with the speed improvements over python I still think handling 5-bit pieces of information might prove to be be difficult in that language. If that is an incorrect statement please elaborate!

Use this script. Modify a single bit in ip (line 949-977)...then F5...it currently takes 2.1027 hours. I'll award the bounty to anyone silly enough to attempt this, and who posts their inversion.

But for this reason I would argue it’s the most valuable sub-function to study if we are to determine the theoretical time limit of Keccak inversion.

That is incorrect as you don't need a time limit to compute $\theta^{-1}$.

You are not using the correct representation. As follows are some intuitions of how to efficiently invert $\theta$.

I. Quick Reminder of $\theta$

II. Inverting the $\theta$-effect

Instead of seeing the parity  $\mathscr{P}$ of the state $S$ as $5 \times w$ bit-array. You can see it as  a $5w$-bit vector $W$. i.e. you have a unique mapping $\sigma$  between $x,z$ and $i^{th}$ the coordinate in that $5w$-bit vector $W$ : $i = x \times w + z$.
$$\varphi(\mathscr{P}) = W$$

The $\theta$-effect can be seen as the result of a matrix multiplication:
$$W' = W \cdot T$$
which gives us:
$$E = \varphi^{-1}\circ (\lambda x \mapsto x\cdot T) \circ \varphi$$
and the inverse:
$$E^{-1} = \varphi^{-1}\circ (\lambda x \mapsto x\cdot T^{-1}) \circ \varphi$$
Note: this assumes that $T^{-1}$ exists.

Proof:
\begin{array}{rl}
E^{-1} \circ E &= \varphi^{-1}\circ (\lambda x \mapsto x\cdot T^{-1}) \circ \varphi \circ \varphi^{-1}\circ (\lambda x \mapsto x\cdot T) \circ \varphi\\
 &= \varphi^{-1}\circ (\lambda x \mapsto x\cdot T^{-1}) \circ  (\lambda x \mapsto x\cdot T) \circ \varphi\\
 &= \varphi^{-1}\circ (\lambda x \mapsto x\cdot T \cdot T^{-1}) \circ \varphi\\
 &= \varphi^{-1}\circ (\lambda x \mapsto x) \circ \varphi\\
 &= \varphi^{-1}\circ \varphi\\
 &= id
\end{array}

As an example as follow is computed $T$ for $w = 4$:

i =  0 : 0 0 0 0   1 0 0 0   0 0 0 0   0 0 0 0   0 0 0 1
i =  1 : 0 0 0 0   0 1 0 0   0 0 0 0   0 0 0 0   1 0 0 0
i =  2 : 0 0 0 0   0 0 1 0   0 0 0 0   0 0 0 0   0 1 0 0
i =  3 : 0 0 0 0   0 0 0 1   0 0 0 0   0 0 0 0   0 0 1 0

i =  4 : 0 0 0 1   0 0 0 0   1 0 0 0   0 0 0 0   0 0 0 0
i =  5 : 1 0 0 0   0 0 0 0   0 1 0 0   0 0 0 0   0 0 0 0
i =  6 : 0 1 0 0   0 0 0 0   0 0 1 0   0 0 0 0   0 0 0 0
i =  7 : 0 0 1 0   0 0 0 0   0 0 0 1   0 0 0 0   0 0 0 0

i =  8 : 0 0 0 0   0 0 0 1   0 0 0 0   1 0 0 0   0 0 0 0
i =  9 : 0 0 0 0   1 0 0 0   0 0 0 0   0 1 0 0   0 0 0 0
i = 10 : 0 0 0 0   0 1 0 0   0 0 0 0   0 0 1 0   0 0 0 0
i = 11 : 0 0 0 0   0 0 1 0   0 0 0 0   0 0 0 1   0 0 0 0

i = 12 : 0 0 0 0   0 0 0 0   0 0 0 1   0 0 0 0   1 0 0 0
i = 13 : 0 0 0 0   0 0 0 0   1 0 0 0   0 0 0 0   0 1 0 0
i = 14 : 0 0 0 0   0 0 0 0   0 1 0 0   0 0 0 0   0 0 1 0
i = 15 : 0 0 0 0   0 0 0 0   0 0 1 0   0 0 0 0   0 0 0 1

i = 16 : 1 0 0 0   0 0 0 0   0 0 0 0   0 0 0 1   0 0 0 0
i = 17 : 0 1 0 0   0 0 0 0   0 0 0 0   1 0 0 0   0 0 0 0
i = 18 : 0 0 1 0   0 0 0 0   0 0 0 0   0 1 0 0   0 0 0 0
i = 19 : 0 0 0 1   0 0 0 0   0 0 0 0   0 0 1 0   0 0 0 0

If we take point at coordinates $(x = 0, z = 3)$ or $i = 0\times 4 + 3 = 3$ (thus the fourth column).

The $\theta$-effect gives us:

$(x-1, z) + (x+1,z+1) = (4,3) + (1,0)$ as we are with $w = 4$.

In other words we need:

$i = 4 \times 4 + 3 = 19$ and $i = 1 \times 4 + 0 = 4$.

You can check that these coordinates are set in the $4^{th}$ column.

Fun fact, $T$ is not invertible.

For $T$ to be invertible, the determinant should not be null. Using sage we notice that $det(T) = 0$, proving that $T$ is not invertible.

III. Going back to $\theta$

Sadly inverting the (non-invertible) $\theta$-effect does not gives us the inverse of $\theta$ as it is added back to the state. However we can notice multiple things.

   +---+       +---+
  /   /|      /   /|
 /   / +     /   / +
+---+ /     +---+ /
| S |/ ---> | S'|/
+---+       +---+
  |           ^
  v           |
  P  ------> E(P)

Notice that:

$\bigoplus_{y=0}^4 S[x,y,z] = \mathscr{P}$
$\bigoplus_{y=0}^4 S'[x,y,z] = \mathscr{P} + 5 \times E(\mathscr{P}) = P + E(\mathscr{P})$

In the same way as in [II], $P + E(\mathscr{P})$ can be seen as a matrix transformation (i.e. a multiplication by $(id + T)$).

Thus if we inverse this $(id + T)$ matrix, we will be able to find the initial parity $\mathscr{P}$ of the state, compute the $\theta$-effect and add it back to $S'$, canceling the itself ($\forall s, s \oplus \theta\text{-effect} \oplus \theta\text {-effect} = s$). And in such way, computing the inverse of $\theta$.

   +---+                              +---+
  /   /|                             /   /|
 /   / +                            /   / +
+---+ /        theta^-1            +---+ /
| S'|/ --------------------------> | S |/
+---+                              +---+
  |                                  ^
  v                                  |
P + E(P) ---------------> P ----- > E(P)
          *(id + T)^-1        *T

Going back to our $w= 4$ example we have:

id + T =
[1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
[0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0]
[0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0]
[0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0]
[1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0]
[0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0]
[0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1]
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0]
[0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1]

Which happens to be invertible:

(id+T)^-1=
[1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0]
[0 1 1 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1]
[1 0 1 1 0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1]
[1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0]
[0 1 1 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1]
[0 0 1 1 0 1 1 1 0 0 0 0 1 0 1 1 1 1 0 1]
[1 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1 1 1 1 0]
[1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1]
[1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 0 0 1 1 1]
[1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1 1]
[1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1]
[0 1 1 1 1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 0]
[0 1 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 0]
[1 0 1 1 1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0]
[1 1 0 1 1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0]
[1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 0 0]
[0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0 1 1 1 0]
[0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 0 1 1 1]
[0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1 1 0 1 1]
[0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 1]

Because of the associativity of the matrix group. You can just compute: $(id + T)^{-1} \cdot T$ giving you a slightly faster computation of the $\theta$-effect from $S'$ (as opposed to do the 2 matrix multiplications):

(id + T)^-1 * T =
[0 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0]
[0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1]
[1 0 0 1 0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1]
[1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0]
[0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1]
[0 0 1 1 0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 1]
[1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 1 1 1 0]
[1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 1]
[1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1]
[1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 0 1 1]
[1 1 1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1]
[0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 0]
[0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0]
[1 0 1 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0]
[1 1 0 1 1 1 1 0 1 0 0 1 1 0 0 1 0 0 0 0]
[1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0]
[0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0]
[0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 0 0 1 1]
[0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1 1 0 0 1]
[0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 0]


Is there a way to use a one-way hash function for both sides to "ratchet" an asymmetric keypair? Is there any way to derive a series of asymmetric keys, such as using a one-way hashing function, where both sides can predict the next in the sequence?
Detailed Scenario:
Imagine a chat application where two people, Alice and Bob, are sending messages -- each with the agreement to delete any messages received 7 days after they are sent.  And let's assume that some attacker is recording all of the encrypted communications between them.  The goal is to prevent an attacker who compromises a phone from getting more than 7 days of messages, either from the phone, or using any copy of a key on the phone.  Protecting against this requires both Alice and Bob to do two things:

Encrypt each message with a different key
Delete each message after 7 days
Also delete the key used to decrypt the message after 7 days

If they don't delete the key, then when the attacker compromises the phone, they can decrypt any previous messages from their historical record of the encrypted communications.
Partial Solution:
One way this could be done is for each side to publish a new asymmetric public key every day, with the promise that "any message encrypted to this public key (for me to decrypt with its corresponding private key) will be deleted, along with the private key used to decrypt it, on YYYY-MM-DD".  So, each side would receive the updated key every day, and encrypt messages to that public key (or more likely, use that public key to encrypt and deliver an ephemeral symmetric key used for all messages in that 24 hour range).  So long as both sides deleted their message after 7 days, and the recipient deleted their copy of the private key for that day (along with any ephemeral key), then forward secrecy would be maintained: compromising a device would only reveal at most 7 days of messages.
Problem:
The problem with that solution is it requires both sides to be in constant communication, in order to receive a daily key update from the other side.  If Alice were to go offline for, say, a month, then Bob wouldn't know which of Alice's public keys to encrypt a new message with.
Solution / Question:
Which brings me to my question:
Is there any way to derive a series of asymmetric keys, such as using a one-way hashing function, where both sides can predict the next in the sequence?
This is easy with a symmetric key: if you have the key for N=1 in the sequence, both sides can apply the same hash function, and generate the key for N=2 in the sequence.  I'm wondering if there is any equivalent for asymmetric keys, where:

Alice applies a one-way hash function to Alice's private key for N=1, to generate a private key for N=2
Bob applies a one-way hash function to Alice's public key for N=1, to generate a public key for N=2

If so, then both Alice and Bob could anticipate what key will be used for any future date by both "advancing" their side of the asymmetric keypair, even if they lose contact with the other side for extended periods of time.
Thanks!
PS: I'm aware there are other ways to solve this, such as by having each side publish a pool of "pre-keys" that are allocated out as necessary.  I'm specifically asking about if there's any way to directly ratchet both the public and private key.

Is there any way to derive a series of asymmetric keys, such as using a one-way hashing function, where both sides can predict the next in the sequence?

Here is one way, based on elliptic curves (or finite field based on discrete logs); one such public key encryption method is the Integrated Encyption Scheme.  Now, it does have the drawback that if the attacker learns a prior public key, he can then (with knowledge of the current private key), he can learn the prior private key.  However, this limitation may still be acceptable to you.
In such a scheme, there is a private key (which is an integer $p$ in the range $[0, q)$), and the public key is a point $P = p \cdot G$ (where $\cdot$ is point multiplication if you're using elliptic curves, and exponentiation, more commonly written as $G^p$ if you're using a finite field group).
To ratchet the key forward, the two sides would compute:

Private key: $p' = hash(P) \times p \bmod q$
Public key: $P' = hash(P) \cdot P$

(where $hash$ is a cryptographic hash function).
This works, in that the relationship between the new public key $P'$ and new private key $p'$ still holds; $p' \cdot G = hash(P) \times p \cdot G = hash(P) \cdot P = P'$.
In addition, it is ratcheting; given $p'$, you cannot recover $p$ without knowing the hash of $P$ (and we assumed that he doesn't know that)


CBC - a canonical mode, even though there are streaming modes Why is CBC considered the canonical mode when there are streaming modes available such as CFB and OFB? One thing that I can think of is that in CBC you can easliy do range-based decryption. All you have to do is load the previous block (whose size is explicit). How would you do it in CFB/OFB? In my previous question I was thinking that in streaming mode it just uses the cipher block versus a larger disk block.
Other things to note?

Diagrams to visualize this on wikipedia.

OFB and (to a lesser degree) CFB are malleable: an adversary knowing a selected portion of the plaintext and able to change the ciphertext can trivially change the alleged plaintext to something chosen, e.g. "no!" to "yes". CBC has a (small) degree of resistance to that.

OFB does not allow efficient decryption of an isolated segment of ciphertext (we need to know the IV, run the cipher for all previous blocks, and know or guess the position of the segment). CBC (and CFB) allow that (only the first block of the isolated segment is undecipherable).

CBC can be introduced as an improved version of ECB (the simplest mode), while CFB and OFB are a radical departure.

I conjecture this has conspired to make CBC popular.

Note: a previous version of this answer mixed OFB and CFB. That's fixed, thanks to Henrick Hellström.


Staying PCI compliant while upgrading encryption I am trying to migrate my encryption methods, currently I use RSA 1024 key size and hashing with SHA-1.

This configuration is going to be deprecated soon, but 2048 key size will have my system so slow and heavy transactions. Therefore, I am thinking about keeping RSA 1024 but hashing with SHA-256 (more secure and recomended by PCI).

Does anyone know if this configuration is PCI compilant? Would I have trouble getting certificates with it?

Supplementing RSA-1024 with SHA-256 instead of SHA-1 won't cut it from a PCI-DSS compliance standpoint: RSA-2048 is a minimum for a large class of uses according to PCI-DSS's definition of

  Strong Cryptography: Cryptography based on industry tested and accepted algorithms, along with key lengths that provide a minimum of 112-bits of effective key strength and proper key-management practices (..)
  At the time of publication, examples of industry-tested and accepted standards and algorithms include AES (128 bits and higher), TDES/TDEA (triple-length keys), RSA (2048 bits and higher), ECC (224 bits and higher), and DSA/D-H (2048/224 bits and higher). See the current version of NIST Special Publication 800-57 Part 1 for more guidance on cryptographic key strengths and algorithms.
  Note: The above examples are appropriate for persistent storage of cardholder data. The minimum cryptography requirements for transaction-based operations, as defined in PCI PIN and PTS, are more flexible as there are additional controls in place to reduce the level of exposure.
  It is recommended that all new implementations use a minimum of 128-bits of effective key strength.

Also, just switching from SHA-1 to SHA-256 arguably would not help against real attacks: as a general rule, a security chain can only be as strong as its weakest link; and in many usage patterns, second-preimage (rather than collision) is what matters, making RSA-1024 a weaker link than SHA-1 is.

Addition following comment: SHA-1's collision resistance is weaker than RSA-1024. But in most applications, a successful attack requires breaking the hash's second preimage resistance, and SHA-1 remains extremely strong against that. There are a few exceptions where breaking collision resistance matters, like attacking an hypothetical certification authority still issuing SHA-1 based certificates and using predictable certificate numbers; but notice that from the standpoint a PCI-DSS entity, using a strong hash does not help protect from this hypothetical attack; what matters is that acceptors of certificates reject certificates made with SHA-1 (or reject certificates issued by authorities that do not have a policy stating that when they issue certificates based on SHA-1, they use an unpredictable certificate number).


Is it feasible to break Diffie-Hellman key exchange when the implementation uses a poor-quality PRNG? I've come across an implementation of DH in Java that uses the Random class to generate the secret integer value $a$, as shown in in Wikipedia's description of the algorithm. As such, the seed of the RNG is only 32 bits and the output may be predictable.

By observing DH exchanges only, would it be possible to predict or compute the shared secret?

An attack would be trivial if the seed of the RNG was only 32 bits; just enumerate the seeds, and test which matches the intercepted messages. That's easy.

However the default Java Random class uses a 48-bit state and seed (which would still be attackable, though $2^{16}$ times less easily), and there are safe subclasses, thus use of Random does not imply an (insecure) 48-bit state, if the object really is a SecureRandom. See this Java 1.4.2 doc or this Java (1.)7.x one.

Update: While it seems the seed of the default Java Random class is 48-bit, its default seed indeed is 32-bit on some old Java platforms, and predictable to some degree on top of that; it is 48-bit on the latest Java platforms, and seems less predictable (though it could still be predictable/repeatable in a virtualized context).


Why does error propagation in CBC mode encryption affect two blocks? From Wikipedia:

Error propagation
It was common to discuss the "error propagation" properties as a selection criterion for a mode of operation. It might be observed, for example, that a one-block error in the transmitted ciphertext would result in a one-block error in the reconstructed plaintext for ECB mode encryption, while in CBC mode such an error would affect two blocks.

I read this similar post before. And I can understand that in CBC decryption, only two blocks are affected due to error propagation (error in 1 block).
But, for the same case in CBC encryption, why are still only two blocks affected? It looks like all the following blocks will be affected.

Encryption process in CBC mode is performed as
\begin{align}
C_1 &= Enc_k(P_1 \oplus IV)\\
C_i &= Enc_k(P_i \oplus C_{i-1}),\;\; 1 < i \leq nb,
\end{align}
where $nb$ is the number of blocks.

CBC is designed for chaining, therefore while encryption, if there is one block error at position $i$, it will affect the rest of ciphertext. This also can be seen from below if write the equation of encryption of $j$-th block.

$$C_j = Enc_k(P_j \oplus Enc_k(P_{j-1} \oplus \cdots Enc_k(P_1 \oplus IV)\cdots)).$$ If $i < j$  then the $j$-th plaintext block will be affected.

However, while decryption of the ciphertext, that is encryption of the plaintext that contains the errored block, you will get only one block with error, the errored plaintext block. Or simply, you will get what you encrypted if there is no error/corruption on the ciphertext blocks.

Note: if there is an error on one of the ciphertext blocks, it can affect one or two plaintext blocks depending on the index of the ciphertext block. One block if the last ciphertext block is corrupted, two blocks otherwise, see bit flipping attack to visiualize. The question is on the error on the plaintext.


what are DP and DQ in Encryption by RSA in c# I want to know about these tags in RSA Encryption by private Key. when I use this code:

using (var provider = new RSACryptoServiceProvider(keySize))
    {
        publicKey = provider.ToXmlString(false);
        privateKey = provider.ToXmlString(true);
    }

It create this xml:

<RSAKeyValue>
   <Modulus>…</Modulus>
   <Exponent>…</Exponent>
   <P>…</P>
   <Q>…</Q>
   <DP>…</DP>
   <DQ>…</DQ>
   <InverseQ>…</InverseQ>
   <D>…</D>
</RSAKeyValue>

I know that $p$ and $q$ are the primes number, but I dont know what are DP and DQ and why we need to InversQ and else...

is anyone explain these items for encryption?

DP is $d\bmod{p-1}$, similarly DQ is $d\bmod{q-1}$. InverseQ is $q^{-1}\bmod{p}$.

These are used in applying the Chinese Remainder Theorem to RSA decryption, which is an optimization technique.