Shuffling alphabet cipher Disclaimer: this is actually a coding challenge therefore I am expressly not looking for complete solutions.

The way the cipher works is as follows:

Start with ABCDEFGHIJKLMNOPQRSTUVWXYZ and a keyword KEYWORD. We construct our first alphabet by shuffling the above around each letter of the keyword in turn. I.e.:

First letter K, alphabet becomes LMNOPQRSTUVWXYZKABCDEFGHIJ

Second letter E, alphabet becomes FGHIJELMNOPQRSTUVWXYZKABCD

etc. etc. until we get the initial cipher alphabet: YFGHIJELMNRPQDSTUVOXWZKABC

In order to encrypt we then use this alphabet and for each letter in the plain text perform the same shuffling operation as in the inception stage around the plaintext letter (so if the first letter of the plaintext is F you would get J as the first ciphertext letter and your new alphabet would be GHIJELMNRPQDSTUVOXWZKABCFY

How would I go about solving this? I'm thinking known plaintext attack since I most likely know the beginning of the plaintext and also know that there are only a finite amount of possible words in the solution.

Further research led me to an obscure cipher Chaoscipher which goes in that direction.

Edit: longer example (also uses keyword as keyword):

doyouthinkthereisanotherwaytosolvethiscipher

becomes

HFUTLNAQYWHBWBEBTIEXWSZFGZQPINTQGHKDSVVVPXNM

Second edit: python code to test it

class ScrabbleCipher:
    def __init__(self, keyword):
        self.alpha = string.ascii_uppercase
        self.keyword = keyword.upper()
        self.initialAlpha()

    def initialAlpha(self):
        for i in self.keyword:
            self.shuffle(i)
        self.initial = self.alpha

    def shuffle(self, letter):
        try:
            tg = self.alpha.index(letter)
        except Exception as e:
            print letter
        self.alpha = self.alpha[tg+1:] + letter + self.alpha[:tg]

    def encrypt(self, plaintext):
        self.alpha = self.initial
        plaintext = plaintext.upper()
        ciphertext = ''
        for i in plaintext:
            pos = string.ascii_uppercase.index(i)
            ciphertext += self.alpha[pos]
            self.shuffle(i)
        return ciphertext

    def decrypt(self, ciphertext):
        ciphertext = self.sani(ciphertext)
        self.alpha = self.initial
        plaintext = ''
        for i in ciphertext:
            pos = self.alpha.index(i)
            corLet = string.ascii_uppercase[pos]
            plaintext += corLet
            self.shuffle(corLet)
        return plaintext

So, I found a way to do it but it's neither elegant nor a general solution. It relies on the (heavy) assumption that the initial chosen keyword is English and a second assumption that the resulting cipher text is also English. It then becomes a relatively crude bruteforcing exercise:

1) Choose an English word

2) Create a cipher instantiated by that word

3) Decrypt the ciphertext using that cipher

4) Check whether the decrypted plaintext contains English words

Using a relatively large wordlist (400k), it took around 30-40 seconds to break, the keyword itself was 9 chars long. As such, the solution would be completely unpractical if the keyword is random (which incidentally is the second part of this challenge and as such I will update this answer if I solve that one too).


Looking for CPRNG implementatoin I'm looking for commonly used and proven CPRNG implementation in C. What to use? ChaCha20 like in Linux Kernel?
Does anybody know other implementations?
PS: I don't want to implement by itself because it requires high accuracy and later must be verified by security experts to make sure all works correctly. Also I plan to use it on embedded device which OS doesn't have random system calls

commonly used and proven CPRNG implementation in C

An alternative would be knocking off Microsoft's CryptGenRandom.  That's the old CSPRNG build into the WinNT family of OSes.  Essentially it's SHA1(RC4) and has FIPS certification so should be okay for you.  There's enough detail in On the (in)security of the random number generators of Linux and Windows and Cryptanalysis of the Windows Random Number Generator for you to be able to reconstruct it. SHA1 and RC4 details are everywhere. Do not be alarmed at the bias issues with RC4.  Those occur natively before the hash function is applied.

You will note a valid forward security attack on CryptGenRandom. It only requires $ 2^{32} $ work effort which is quite low and therefore serious.
 However that requires knowledge of the internal state. Whether an attacker can know the internal state of anything is a huge can of worms, and only you can decide if this is a likely scenario.

Whopping great caveat: You need entropy to initialise (and perhaps reseed) your RNG. To be honest this is the hardest part.  Generating cryptographically secure numbers is easy if you just use a library implementation of a CSPRNG. Similarly, a bit of ChaCha is easy, but you still require an initial seeded state.  Seeding is the problem. Since we don't know your electronic environment, my advice can't be specific at this time. Have a look through the two links, try to identify any similarities (particularly related to the state)  and come back with any further questions.


openssl_get_cipher_methods: which one to choose? When calling openssl_get_cipher_methods we get several cipher methods.

I noticed that some of these method have same prefix like AES-256-(CBC|CFB|CFB1) or IDEA-(CBC|CFB).

My question is which one to choose: which is the most safe and secure for encrypting a string or large file? What process should I follow to encrypt data correctly?

IDEA is a block cipher with a 128 bit key size and a 64 bit block size. AES-256 is a more modern block cipher with a key size of 256 bits and a block size of 128 bits. For large files AES certainly has the advantage.

As for the modes of operation: CBC, CFB and CFB1 are all non-authenticated modes of operation. CFB1 is an older format that is mainly useful for its error propagation properties. That's not often considered an important factor anymore. So lets focus on CBC and CFB. CFB is probably the more secure choice. It's a streaming mode of operation which doesn't require a randomized IV (just a unique IV). Because it is a streaming mode it also doesn't require a padding mode.

So AES-CFB is probably the best of the choices above. It certainly can be secure when correctly used within a protocol. But in the end the cipher and mode of operation cannot protect a broken security system. So how safe depends on the details of your protocol.


Why not the one-time pad with pseudo-number generator I am very new to cryptography (so be kind), but I have a question that may seem silly.

If the one-time pad is the perfect cipher and impossible to crack, why would the following algorithm not be one of the strongest:

To encrypt:

generate a random bit array using a pseudo number generator with the key as the seed
The generated bit array is the size of the data
use a simple XOR to encrypt using the generated bit array

To decrypt:

pseudo-random number generator will generate the same bit array with the same seed (the key)
generate bit array the same size of the encrypted data
run XOR on encrypted data using bit array that's generated

This is very simplified, but you can imagine how for larger encryption you could break down the data into blocks, and in order to ensure that the block bit arrays are random a new seed for each can be derived from the key. So, if $f(k)$ is the pseudo random number generator, and b is the block number, you can encrypt each block with $f(k+b)$. ($k$ is key)

Instead of using a pseudo-random number generator, you could use some hash algorithm to generate the pad.

Ceteris paribus (assuming you can use equivalently strong keys) would this not be a very strong cipher method? Perhaps it may be strong and heavy on memory since the pad needs to be the size of the data. So during encryption and decryption you need to generate a pad that's equivalent to the size of the data.

Is there a flaw in this algorithm, or would something like this not be practical and much slower than current standards?

It's a good question. As pg1989 said, this is the basis behind stream ciphers, which are very fast in practice.

I thought I'd quickly expand upon your statement that "the one-time pad is the perfect cipher and impossible to crack." This is true, in a sense, but it's worth pointing out that sometimes an attacker wants to do something simpler than "cracking" the encryption scheme in order to recover all plaintexts.

For instance, an attacker may just want to change the message so that the honest recipient decrypts something else. As a simple example, suppose that the attacker knew for sure that the message was either "yes" or "no!" and just wants to change the message to the other value. Note that:

This is simple to do for messages encrypted using a one-time pad. The linked Wikipedia page describes why this is true, but it's probably more fun to figure it out for yourself.
The attacker can do this without learning the plaintext. Hence, the original claim of a one-time pad being uncrackable is still true.

There are some other issues with a one-time pad construction too, such as the fact that usually some state will be required to make sure that you don't re-use the seed during the next encryption. Hence, while your question is definitely not silly, and stream ciphers are very useful in certain circumstances, they also have their limits.


Are Barreto-Naehrig Curves suitable for pairing-based cryptography? If Barreto-Naehrig Curves are suitable for pairing-based cryptography, can I use the library available at Optimal ATE Pairing?

You can, with the right parameter sizes (384-bit prime instead of the older 256-bit).

Pairings can be attacked in two fronts: the elliptic curve or the extension finite field. The security of the pairing will be the the one that is easiest to break.

Previously, a BN curve using an elliptic curve over a 256-bit prime provided 128 bits of security; it was the "perfect" case since the elliptic curve provided 128 bits and the extension field also provided 128 bits.

After Extended Tower Number Field Sieve:
A New Complexity for the Medium Prime Case, things changed in the extension field case, and it's hard to give a concrete estimate since the paper handles asymptotics and we'd need to have concrete implementations to have more accuracy. But the paper estimates that the prime size must be doubled (i.e. from 256 bits to 512 for 128 bits of security). Aurore Guillevic estimates that it should be changed to 448 or 512 bits. However, further analysis in Challenges with Assessing the Impact of NFS Advances on the
Security of Pairing-based Cryptography, indicate that 384 bits should be enough.

So, if you use $p$ with 384 bits, you should be fine, but the performance won't be very good. In this case, the elliptic curve provides 192 bits of security while the extension field provides 128 bits, and we're stuck with the smaller value.

As an example, Zcash chooses the BLS12 pairing for the 128-bit security level since, due its structure, it is a 256-bit group (instead of a 384-bit group in BN) which makes some things faster. The underlying prime is the same size, though (384 bits).


Cryptographic algorithm for knowing who has more money? I recall reading about this but forgot what it’s called.

Suppose two people want to know who is richer but don’t want to reveal their net worth to the other. How can they securely exchange info to determine who’s number is larger?

You are looking for Yao's Millionaire Problem:

Yao's Millionaires' problem is a secure multi-party computation problem which was introduced in 1982 by Andrew Yao, a prominent computer scientist and computational theorist. The problem discusses two millionaires, Alice and Bob, who are interested in knowing which of them is richer without revealing their actual wealth.
This problem is analogous to a more general problem where there are two numbers ${\displaystyle a}$ and ${\displaystyle b}$ and the goal is to solve the inequality ${\displaystyle a\geq b}$ without revealing the actual values of ${\displaystyle a}$ and ${\displaystyle b}$.


What's wrong with NIST SP 800-90B? NIST SP 800-90B offers various tests for estimating entropy.  They also offer an implementation of these tests.  With their program called ea_iid, estimating entropy is very easy.
$ ea_iid random.dat
Calculating baseline statistics...
H_original: 7.884314
H_bitstring: 0.998545
min(H_original, 8 X H_bitstring): 7.884314

** Passed chi square tests

** Passed length of longest repeated substring test

Beginning initial tests...
Beginning permutation tests... these may take some time
** Passed IID permutation tests

So the min-entropy estimation for the source that produced random.dat is 7.88 bits of information per byte.
However, this page calls it USELESS. I'm unable to reproduce the claims made this page --- none of my NIST SP 800-90B programs show even similar output as those displayed by this page.  The output above is an example.  Am I running a totally different version of the programs?

As the author of that page I feel that some clarification is necessary:-

Am I running a totally different version of the programs?

Yes. You're running the IID test. You need to run ea_non_iid.  What you've run assumes that the data sample is IID within a p=0.01 certainty.  It then calculates the min. entropy of the dataset using the maximum probability ($H_\infty$). That's easy.
ea_non_iid attempts to measure $H_\infty$ of correlated data.  That's hard.
The reason 90B is pretty useless (and never used) is that code assumes uniformly distributed data.  Well to be honest, no one really knows what the authors were thinking. [Insert appropriate conspiracy theory, but I draw your attention to Federal Information Security Modernization Act (FISMA) of 2014, 44 U.S.C. § 3551 et seq., which is referenced on page 3 of 90B].
Other than a few laboratory binary entropy sources, most generate some form of non uniform distribution.  You can get really weird ones depending on how the source is sampled and packed into bytes. That site has examples, and this is another one from a current project's source:-

The site also says to not trust anything on that site.  Do your own research and have a look at:-
John Kelsey, Kerry A. McKay and Meltem Sönmez Turan, Predictive Models for Min-Entropy Estimation, and Joseph D. Hart, Yuta Terashima, Atsushi Uchida, Gerald B. Baumgartner, Thomas E. Murphy and Rajarshi Roy, Recommendations and illustrations for the evaluation of photonic random number generators.
This is an extract:-

You can see that in some cases $H_\infty$ is underestimated sixfold.  Their various predictors are not very good. From experience and research I trust the LZ78Y compression predictor the most, but still.  This is consistent with my own testing as shown.
John Kelsey is one of the 90B authors and so he criticises himself!


AES process candidates implementations and usages There were fifteen candidates in the AES selection and I suppose that Rijndael wasn't the single good algorithm. I know that Camellia is an evolution of E2 candidate and can be used as symetric cryptographic routines in TLS. Which others ex-candidates have today a "serious" implementation and a real usage ?

Well, not all of the AES-candidates have been considered good. In fact one of them even got broken at the presentation (within 20min!).

I'll list any (non-author) occurence of algoriths I'm aware of. Note: This list doesn't claim to be complete and may be extended by other people.

Now for a list of algorithms, for which I know there're an option

SAFER, well it's predecessor, SAFER-K and SAFER-SK are available at least in the Crypto++ library
CAST-256, available in the Crypto++ library
MARS, finalist, available in the Crypto++ library, because of the finalist status it may be an option in other programs
RC6, finalist, available in the Crypto++ library, available in Jetico's encryption tool, may be an option in other places as well as it's simpler than MARS and also has finalist status, according to wikipedia it was used pre-AES by the NSA. Furthermore usage of this algorithm can be costly as RSA Labratories seem to hold patents on it, as RC6 didn't win the AES-competition.
Serpent, finalist, 2nd place of the AES process, back then it was believed to be the most secure available candidate, adopted in Crypto++ and available in Jetico's tools and in TrueCrypt and it's derivatives (e.g. CipherShed and VeraCrypt).
Twofish, finalist, 3rd place of the AES process, back then it was approximiately as fast as Rijndael but it was believed to be more secure, adopted in Crypto++, TrueCrypt, by Jetico and in KeePass (1.x, 2.x as plug-in), and is part of the OpenPGP standard.


If PGP and GPG both follow the OpenPGP standard, are they 100% compatible in all use cases? If someone gives me their PGP key, can I use it with GPG, and vice versa, all the time (100% interchangeable)? Or are there times when they are not compatible, when only PGP can be used with a PGP key, and only GPG used with a GPG key?

"If PGP and GPG both follow the OpenPGP standard, are they 100% compatible in all use cases?"

No, they are not 100% compatible in all use cases, because — depending on the PGP version — there are known interoperability problems.

The GNUPG FAQ answers this question quite well:

  Is GnuPG compatible with PGP?

  In general, yes. GnuPG and newer PGP releases should be implementing the OpenPGP standard. But there are some interoperability problems. See question How can I encrypt a message with GnuPG so that PGP is able to decrypt it? for details.

For your convenience, I'll also quote that linked Q&A:

  How can I encrypt a message with GnuPG so that PGP is able to decrypt it?

  It depends on the PGP version.

  PGP 2.x

  You can't do that because PGP 2.x normally uses IDEA which is not supported by GnuPG as it is patented (see How do I include support for RSA and IDEA?), but if you have a modified version of PGP you can try this:

$ gpg --rfc1991 --cipher-algo 3des ...

  Please don't pipe the data to encrypt to gpg but provide it using a filename; otherwise, PGP 2 will not be able to handle it.

  As for conventional encryption, you can't do this for PGP 2.
  PGP 5.x and higher

  You need to provide two additional options:

--compress-algo 1 --cipher-algo cast5

  You may also use "3des" instead of "cast5", and "blowfish" does not work with all versions of PGP 5. You may also want to put:

compress-algo 1

  into your ~/.gnupg/options file — this does not affect normal GnuPG operation.

  This applies to conventional encryption as well.

I think that pretty much answers your question.


ECDSA Private Key from SSS I have all of the Shamir's secret shares required to Lagrange-interpolate f(0), which represents an ECDSA private key. The field of this object is secp256k1, which has associated prime number p=115792089237316195423570985008687907853269984665640564039457584007908834671663.

The Lagrange interpolation produces a negative f(0), but because curves over secp256k1 can have exactly 0 or exactly 2 y-coordinates at any x, I'm assuming I can use the absolute value of f(0).

My other understanding is that since we're working over the finite field Zp, S = f(0) (mod p). Where I'm held up is how to turn this 77-byte number (S) into the ECDSA private key.

I've tried reconstructing a wallet using S in hexadecimal as the private key, as well as the sha256 of S, but I don't believe either of those methods are correct.

Are my previous assumptions correct, and if so, how should I go from S to the ECDSA private key?

In ECDSA one randomly selects the private key $d_A$ from interval $[1,n-1]$, where the $n$ is the order of the Elliptic curve with $n-1$ non-trivial points, and with the point at infinity, $\mathcal O$ as the trivial point.

$n = \texttt{FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141}$ that is 64 bytes, or as an integer

$n = 115792089237316195423570985008687907852837564279074904382605163141518161494337$

one should prefer $S = \operatorname{Hash}(f(0)) \pmod n$ so that all the information mixed before the modulus. Actually, one can still use the original number, however, if the number is bigger than the order, it generates unnecessary bigger calculations, when this step is performed

$$s=k^{-1}(z+rd_{A})\,{\bmod {\,}}n$$

Note that the $p$ is used to represent the elements of the curve and an easy observation is that it limits the number of points of any curve $\leq p^2$. The Hasse theorem gives a tighter relation;

$$|n-(p+1)|\leq 2{\sqrt  {p}}$$


Montgomery Powering Ladder and Side Channel Attacks: Is it practically (im-)possible to analyze where intermediate values are stored? The Montgomery Powering Ladder performs an exponentiation with the operations square and multiply (called double and add in the case of elliptic curves). To my knowledge the order and kind of operations involved are independent from the exponent, which prevents side channel attacks if the exponent is a secret key.

But of course the computation does depend on the exponent: Each bit of the exponent decides where intermediate results are stored. More concretely, the exponent is processed bit by bit and in each step, two intermediate values, say R and S, are updated. If the exponent bit is zero then one of the values, say R, is overwritten with the product of R and S and S is squared. If * denotes the underlying group operation then this can be written as

R <- R*S
S <- S*S

If the exponent bit is one then it is the other way round:

S <- R*S
R <- R*R

So if one could determine which value is squared then this would reveal the respective exponent bit. I guess that this is not possible in practice since otherwise there would have been exploits.

Could someone explain to me why this is difficult in practice? I am an absolute beginner in embedded devices, microcontrollers etc. I am particularly interested in the case where the Montgomery powering is done on an embedded device (not a particular one).

Each bit of the exponent decides where intermediate results are stored.

Not necessarily.

One approach is to use a primitive known as a (constant access) conditional swap.  This primitive takes the values R and S, and swaps them if the bit in the exponent is 1, and leaves them alone if they are 0.  Naturally, this is done with constant accesses (even if the bit is 0, you still read and write R and S) and constant time; it's pretty straight-forward to implement (and is considerably quicker than the Bignum operations the rest of the algorithm uses)

With this primitive, the pseudocode looks like:

CSWAP R, S
R <- R*S
S <- S*S
CSWAP R, S

If the exponent bit is 0, we can ignore the CSWAP's, and this is exactly the Montgomery Ladder 'bit 0' logic.

If the exponent bit is 1, then we effectively do this logic:

R' = S, S' = R   /* First CSWAP */
R' <- R'*S'
S' <- S'*S'
R = S', S = R'   /* Second CSWAP */

Renaming variables, this simplifies to:

S <- S*R
R <- R*R

Which is the 'bit 1' Montgomery logic (as * is commutative).

Hence, we've implemented both sides of the ladder with constant memory accesses.

If we write out the full ladder, we'll see that there are adjacent CSWAPs based on different bits of the exponent; it's obvious how those could be combined to further simplify things.


RSA-OAEP: How does it work? I was looking at this image about OAEP:

..and was wondering what was happening here.

We have a data block DB which consists of:

lHash: What is this and where does this come from?
PS: A string of zeros, but how much zeros?
M: clearly our message.

We have a seed which , is some random number. We put this seed into a MGF, a Mask Generating Function, and XOR the outcome with the MB. This is our maskedDB. Correct?
We put the  maskedDB to the MGF again and XOR it with the seed. This is our maskedSeed.
For the final EM (encrypted message) we prepend some zeros. What do we do with EM then?

1a lHash: What is this and where does this come from?

That's in PKCS#1 v2.1: RSAES-OAEP-ENCRYPT ((n, e), M, L):

  2a. If the label L is not provided, let L be the empty string. Let
           lHash = Hash(L), an octet string of length hLen (see the note
           below).

1b) PS: A string of zeros, but how much zeros?

Similarly for this question, lets look at the actual standard:

  2b. Generate an octet string PS consisting of k - mLen - 2hLen - 2
           zero octets.  The length of PS may be zero.

2) We have a seed which , is some random number. We put this seed into a MGF, a Mask Generating Function, and XOR the outcome with the MB. This is our maskedDB. Correct?

Well, yes, but you XOR with DB, not with MB (whatever that is). It's in steps 2c..2f of the linked section of PKCS#1.

3) We put the maskedDB to the MGF again and XOR it with the seed. This is our maskedSeed.

4) For the final EM (encrypted message) we prepend some zeros. What do we do with EM then?

You continue with steps 3a..c and of course step 4 of the standard, which basically means:

3a) creating an integer from the octet string you've just constructed
3b) modular exponentiation with the public exponent and modulus of the public key (also known as raw or textbook RSA)
3c) creating an octet string from the result again

And 4, output the result (well...duh).


Why can ECC key sizes be smaller than RSA keys for similar security? I understand how ECC is based on the discrete log problem and RSA on integer factorization. I've read several references that show how a solution to either of these problems can typically be adapted to solve the other - for example, one reference claims:

  The asymptotic running time of the best discrete logarithm algorithm
  is approximately the same as that of the best general-purpose
  factoring algorithm. Therefore, it requires about as much effort to
  solve the discrete logarithm problem modulo a 512-bit prime as it does
  to factor a 512-bit RSA modulus.

Now, I suspect that this isn't true, but I'd like to get a feel for why it isn't true.

For instance, as I understand it, the generalized number field sieve can be applied both to solve integer factorization and to solve discrete log. Why is it that it gives such an extreme speed up in integer factorization compared to brute-force, and less so in improving discrete log?

If the asymptotic running times for both applications are approximately the same, then I'm completely confused. I suspect that I'm comparing the wrong parameters, but how is it that ECC key-sizes can be so much smaller that in RSA?

Actually, the problem is that the above quote uses the term "discrete log" in a way that's different from what you're thinking of.

When someone uses the term "discrete log", they can mean two things:

A discrete log in the group $Z^*_p$; that is, given $p$, $g$ and $g^x \bmod p$, recover $x$
A discrete log in some other group; that is, given a group $G$, a generator $g$ and the value $g^x$, recover $x$.

Of course, the precise meaning is given by context.

In this specific case, the quote refers to the first meaning of discrete log; a log over a multiplicative group modulo a prime (and for such a group, there exist subexponential ways of solving it).

However, when we're dealing with the security of an EC group, we don't care about discrete logs modulo $Z^*_p$; instead, we care about the discrete log within the EC group (that is, the second meaning).  These EC groups (or, at least, the ones based on curves that we actually use) do not have these fast methods of solving it; in particular, the number field sieve algorithm does not appear to apply.

And, because the DLOG problem in an EC group is much harder, we can use a smaller EC curve safely.


Is there an encryption algorithm with a key that can only be used to decrypt? I was wondering if there were any encryption algorithms that kinda worked like RSA in the sense that there are two keys, however, one of the keys only decrypts (meaning you can't encrypt with it) and the other key that only encrypts. Is this possible?

There's two fundamental difficulties with what you're asking for.

First, in the usual definition of public-key encryption, the public key is assumed to be, well, public.  That is, everybody is assumed to know it, and thus to be able to encrypt messages.

If you don't want everybody to be able to encrypt, then you're no longer doing public-key crypto in the usual sense, and you need to start paying attention to things like exactly who should be allowed to know the (not so) public half of the key pair and how the halves of the key pair should be distributed.

Second, in general, whoever first creates the key pair must, at least temporarily, possess the information necessary the construct both keys.  If they want, they can save that information and use it to both encrypt and decrypt any messages.

In standard public-key crypto this is not an issue, since it's usually assumed that the keys are generated by the private key holder, who is supposed to know both keys anyway.  But if the private key holder is not supposed to know the "public" key, then we need to either:

trust the private key holder to forget the public key (and any other information that could be used to reconstruct it) after generating it,
entrust the key pair generation to some trusted third party (who, if they're not as trustworthy as we think they are, could then eavesdrop on or tamper with any communications encrypted with the keys), or
somehow generate the key pair using some kind of distributed multi-party computation scheme that doesn't allow any party to learn any parts of the keys they shouldn't know (which is far from a trivial task, if it's even possible).

All that said, if we handwave all those issues away (e.g. by assuming a trusted third party that handles key generation and distribution), plain old RSA can be used like this.  In fact, I asked a question about using RSA in a very similar manner a while ago.

All we need to do is somehow ensure that:

only those who should be able to encrypt messages know the encryption exponent $e$,
only those who should be able to decrypt messages know the decryption exponent $d$, and
nobody (except maybe the 100% trustworthy key generator) knows the factors $p$ and $q$ of the modulus $n = pq$, or anything else (such as $\lambda(n) = \operatorname{lcm}(p-1,q-1)$) that could be used to reconstruct one exponent from the other.

(The modulus $n$ itself can still be public knowledge.)

Of course, this implies that we cannot use a fixed encryption exponent like $e = 65{,}537$, like most ordinary RSA implementations do, but must instead pick $e$ at random from the set of distinct possible encryption exponents (i.e. positive integers less than and coprime to $\lambda(n)$).

We can do this by repeatedly picking a random odd number $1 < e < \lambda(n)$ until we find one that satisfies $\gcd(e, \lambda(n)) = 1$, and compute $d = e^{-1} \pmod{\lambda(n)}$.  Or, equivalently, we can pick $d$ randomly in the same way, and compute $e = d^{-1} \pmod{\lambda(n)}$.  Modular inversion is a bijection, so picking $e$ uniformly at random from the entire set of invertible congruence classes ensures that $d$ is also uniformly distributed, and vice versa.

In fact, the latter scheme is essentially* what Rivest, Shamir and Adleman used in the original RSA paper.  Using a small, fixed $e$ is a later optimization introduced after it was realized that $e$, being public, doesn't actually need to be random.

The tricky part, of course, is that whoever generates the key pair will still end up knowing both $e$ and $d$, and — if they're not supposed to retain the ability to both encrypt and decrypt — must be trusted to securely forget at least one of these exponents, as well as any other values (including $p$, $q$ and $\lambda(n)$) that would allow them to reconstruct those exponents later.

*) The original RSA paper uses $\phi(n) = (p-1)(q-1)$ instead of $\lambda(n)$ when computing the modular inverse.  This has no real effect on security, it just sometimes produces larger exponents than necessary and allows multiple equivalent key pairs.  The original RSA paper also does not specify an actual range to pick $d$ from, but only that it should be "a large, random integer".


Adi Shamir's secret database of all primes I was going through these presentation slides (PDF) on  Crypto 2013.

It summarizes the paper, Factoring RSA keys from certiﬁed smart cards: Coppersmith in the wild.

In the last slide, it was mentioned that one possible future work to be done is to use the “Adi Shamir's secret database of all primes” to attempt breaking RSA-1024. I tried to Google for “Adi Shamir's secret database of all primes”, but I can't find anything. Does anyone have any idea about this "database"?

Adi Shamir's secret database of all primes is to cryptography venues what the Dahu is to French summer camps. For why, see the answers to this related question.

The three other future work items in the quoted presentation are in the same vein (Breaking RSA-1024 with Fermat factoring; Breaking RSA-1024 using $1024 = 2*2*2*2*2*2*2*2*2*2$; Breaking RSA-1024 using Intel's new RDRAND_NSAKEY instruction).

Note: serious work and some further progress did occur after Cypto 2013; see these updated slides of Asiacrypt 2013, also linked from DJB's smartfacts page.


Security proofs for CBC mode I'm looking for different approaches to proofs for the security of CBC mode encryption. What are the best sources of information about this subject?

Here's a nice paper I came across a while ago: Wooding, Mark (2008), "New proofs for old modes", Cryptology ePrint Archive, report 2008/121:

  "Abstract: We study the standard block cipher modes of operation: CBC, CFB, and OFB and analyse their security. We don't look at ECB other than briefly to note its insecurity, and we have no new results on counter mode. Our results improve over those previously published in that (a) our bounds are better, (b) our proofs are shorter and easier, (c) the proofs correct errors we discovered in previous work, or some combination of these. We provide a new security notion for symmetric encryption which turns out to be rather useful when analysing block cipher modes. Finally, we pay attention to different methods for selecting initialization vectors for the block cipher modes, and prove security for a number of different selection policies. In particular, we introduce the concept of a `generalized counter', and prove that generalized counters suffice for security in (full-width) CFB and OFB modes and that generalized counters encrypted using the block cipher (with the same key) suffice for all three modes. "


How to handle modular arithmetic with regard to two's-complement negative numbers? The reason for asking, is that this occurs in real life with CRT calculation of RSA decryption/signing. In CRT RSA, there's the need to calculate subtraction, and it's known negative numbers could occur, especially with multi-prime cases.
While RSA would eventually phase out when moderately-sized quantum computers are available, before QCs can reach that scale, scaling RSA parameters (especially towards using more primes) may be more feasible than rushing to adopt post-quantum schemes in the short term, therefore, it's still a bit relevant.
While it's easy to to do modular arithmetic in variable-time, it seems very difficult do it in constant-time and with limited space for holding working variables.
Q1: Is there a way to implement efficient constant-time modular arithmetic for signed two's-comlement integers in constant time?
Additional Q2 for refuting the use of such implementation: Is there alternative methods for computing CRT RSA decryption/signing that uses no more (or even less) number of working variables? (these "working variables" are big integers).

This answer answers Q1, as there may be merit other than just for calculating CRT RSA (e.g. the extended Euclidean algorithm).

Let's build it step-by-step.
First let's assume you've implemented the % operator for unsigned modular arithmetic in constant time, when you encounter a negative number x, we have the following:
x === -(-x)
Introducing the modulus p, and we have:
x (mod p) === p - (-x) (mod p)
Hence, the algorithm for negative numbers (in pseudo-code, not constant-time yet):
imod(x):
    x = -x
    x = x % p
    if x > 0: x = p - x
    return x

Now, we want to generalize it to apply to also positive numbers, here's the full code in C (constant-time this time):
uint32_t imod(uint32_t x, uint32_t p)
{
    uint32_t neg = -(x >> 31);
    uint32_t z;

    // conditionally negate x.
    x ^= neg;
    x += neg & 1;
    x = x % p;

    // test for 0.
    z = x;

    // Per suggestion by @fgrieu
    // The following code fragment involves:
    // 2 shifts, 4 bit-ops, and 2 additive ops.
    z |= z >> 16;
    z &= 0xffffU;
    z = -(1 ^ ((z ^ (z - 1)) >> 31));

    // In comparison, the following requires:
    // 5 shifts, 6 bit-ops, and 1 additive ops.
    /* z |= z >> 16;
     * z |= z >> 8;
     * z |= z >> 4;
     * z |= z >> 2;
     * z |= z >> 1;
     * z = -(z & 1);
     */

    neg &= z;

    // conditionally compute p - x.
    x = ((~neg & x) | (neg & p)) - (neg & x);
    return x;
}


Does anyone still use BAN or GNY logic in practice? I want to implement a simple protocol, and I'd like to verify it through BAN or GNY logic.  I would assume that if these logics are still used that there would be some programs available that would automate this.  In fact I found one paper on how to automate GNY logic, and another mentioning a tool called SPEAR that automates BAN and GNY logic, but in no case could I actually find these tools.

All of these references are pretty old, and it looks like these logics are only used academically.  Are there any examples of more modern or practical use of these, and are there any tools that are available for automating them?

I don't think they are even used academically anymore, possibly because of soundness problems and limited expressivity. I would not recommend this approach.


Help Finding D from Dq and Dp Let
$$d_p = d~\mathrm{mod}~(p−1)$$
and
$$d_q = d~\mathrm{mod}~(q−1).$$

Given $d_p$, $d_q$, $p$ and $q$, how can I reconstruct $d$?

If you happen to know also $e$ then you can use the formula

$$d = d_p + d_q - e\cdot d_p\cdot d_q \quad\bmod (p-1)\cdot(q-1).$$

Instead of modulo $\varphi(p\cdot q) = (p-1)\cdot(q-1)$ you can also calculate the result modulo the least common multiple of $p-1$ and $q-1$.

PS: I do not understand the downvote(s) for the question. When generating an RSA key one usually first finds $p, q, d_p, d_q$ (and maybe $p^{-1}\bmod q)$ given $e$. If one uses the private key on an embedded device that is susceptible to fault attacks like the Bellcore attack, one might prefer to refrain from using the CRT despite the performance advantages.


Using AES-CTR to generate AES subkeys from a master key and nonce Suppose I would like to encrypt some data using AES-GCM because it has hardware support on my processor and it is secure.

Unfortunately, I don't like the 96-bit nonce size, because I want to randomly generate the nonce each time (to avoid having to keep state).

So instead of it, I use my 256-bit master key to encrypt 32 null bytes with AES in CTR mode with a 127-bit nonce, and use the resulting keystream as the AES-GCM key.

I have now a $96 + 127 = 223$ bit nonce, which is plenty long enough to generate afresh each time.

I presume that this is secure since a block cipher in CTR mode can be used as a CSPRNG (as here).

Am I correct?

If I understand correctly:

You have a 256-bit master key $K0$
Generate a random 128-bit value $N0$ and set the last bit to 0
Generate a 256-bit keystream $K1$ using $E_{K0}(N0)$ || $E_{K0}(N0 \oplus 1)$
Generate a random 96-bit value $N1$
Using $K1$ as the key, and $N1$ as the nonce, encrypt your message with AES256-GCM, and authenticate $N0$ as associated data
Include $N0$ with the ciphertext

As you suggested, this should give a 127-bit effective nonce size for generation of the key $K1$, plus a 96-bit nonce size for the actual nonce, resulting in 16 byte ciphertext expansion, and minimal extra computation, but now with a $2^{-111.5}$ probability of a key/nonce pair reuse.

Because there are only $2^{127}$ possible keys, you may want to consider additional ciphertext expansion, and instead generate a 256-bit nonce $N0$, encrypting the whole thing with ECB or CBC to get $K1$.

Be aware, security proofs may include keeping the nonce $N0$ (effective state) of the PRNG secret, and here you are providing it as part of the ciphertext. I would do it like this:

You have a 256-bit master key $K0$
Generate a random 256-bit value $N0$
Generate 256-bit key $K1$ by hashing $N0$ with something like SHA-384
Generate a random 96-bit value $N1$ (optional)
Generate $S$ = $E_{K0}(N0)$
Using $K1$ as the key, and $N1$ as the nonce, encrypt your message with AES256-GCM, and authenticate $S$ as associated data
Include $S$ with the ciphertext

Encryption only requires a single hash iteration beyond the initial scheme, in addition to the ciphertext expansion from $S$. Decryption of the message requires decryption of $S$ followed by hashing to recover $K1$. In this scenario a GCM nonce $N1$ is not required to be generated, since you are using a new 256-bit key with each message you can use a fixed nonce. You could also get $N1$ from the unused remainder of the hash output. The GCM key is also protected by encrypting the state of the PRNG, which is now a random input to a hash function.

It is probably not insecure to do it your way, I just do not feel good about exposing $N0$ directly. If the system RNG has some problem, exposure of $N0$ (or even $N1$) could give an attacker information they could use against you in some way. Dual-EC is a good example.


Surprisingly, very basic algorithms which the children learn at the basic schools are used. For instance:

http://www.wikihow.com/Do-Long-Multiplication

You can find a similar algorithm for sum, sub and division. Try to ask google for: "division on paper"

The "power of" is little tricky. In cryptography you don't really need the "real power of". Instead you need:

(a ^ b) mod c

It is easy to compute a^(power of 2) mod c

a * a mod c= a^2 mod c
(a^2)^2 mod c= a^4 mod c
(a^4)^2 mod c= a^8 mod c
...
(a^512)^2 mod c= a^1024  mod c

And if you need a^5

(a^5) = a^2 * a^2 * a

thanks to "mod c" you keep the numbers no higher than c.

For example:

c = 10

2^2 = 4
2^4 mod 10 = (4^2) mod 10 = 16 mod 10 = 6
2^8 mod 10 = ((4^2)^2) mod 10 = (6^2) mod 10 = 36 mod 10 = 6
2^16 mod 10 = (6^2) mod 10 =....

etc..

There are many tricks how to make the calculation faster. For example, Montgomery multiplication algorithm is often used for that. But even without those tricks the implementation would be fast enough. I would estimate RSA instead of 0.2s would take 5s or so.


How can public key not reverse encryption if the algorithm is known? I've been reading about WhatsApp getting "end-to-end" encryption, and when reading about it, I've notice something.

If I want to send a message from cell $A$ to cell $B$, since there's a public key, I will pass my message through this "algorithm" and send to the cell $B$.

My question is, knowing the public key doesn't automatically gives you power to reverse engineer the message sent? How is that possible that knowing the algorithm that created a code and the code itself doesn't get you the original information?

I will give you the simplified answer.

The public key encryption does not prevent adversery from computing private key from public key. It just makes it very very very hard. The algorithms use math that allows simple private->public calculation, but public->private has no good mathematical "shortcuts". It would take adversery more time to calculate this, then for him to walk in front of every home on Earth, and beat every occupant inside with a rubber hose while asking about content of Your message.


Post-quantum authenticated key exchange with forward secrecy Are there any post-quantum, forward-secure, hybrid, optionally authenticated key exchange protocols?  Specifically, I am looking for one that can be deployed in a hybrid with X25519 + EdDSA.

Key exchange and authentication are typically done by separate algorithms. However, there are post-quantum key exchange algorithms that also provide forward secrecy. For example:

SIDH - Supersingular Isogeny Diffie-Hellman is very similar to regular DH. The main difference is that the security is related to the problem of finding the isogeny mapping between two supersingular elliptic curves with the same number of points.1
NewHope - This algorithm is based off of ring-learning-with-errors (R-LWE). The security relies on the approximate shortest vector problem (α-SVP). This is the idea that finding a vector shorter than α times the shortest vector is difficult, even for quantum computers.

Both of these algorithms can be combined with traditional key exchange to form a hybrid that is secure against both quantum computers and cryptanalysis of the relatively newer post-quantum algorithms. Google for example has experimented with their CECPQ1 key exchange algorithm, which combines NewHope and x25519. The Tor Project is also working on a hybrid algorithm using the same primitives, though implemented differently (using NTor rather than TLS).

Neither of these schemes provide post-quantum cryptographic signatures. The reason for this is simply that a signature does not need to provide security for nearly as long as key exchange. Key exchange must be secure against an adversary who can store the handshake and encrypted message and decrypt it at a later time when technology is sufficiently advanced. Signatures on the other hand only require that they cannot be broken right now. If your adversary is an attacker who is storing encrypted connections to break in the future, there is no need to switch to PQ signature schemes. It's only if your adversary is an active attacker with a quantum computer at this very moment that you need to worry about more secure authentication.


Length Extension attacks in SHA1 and MD5? From my understanding on the internet about length-extension attack, I have understood that hash(secret_key|known_data) can be exploited to produce hash(secret_key|known_data|appended_data) even without knowing the exact value of the secret_key by just knowing the length of the key. I tried implementing this using hashpumpy python module and this did not match.

import os
import sys
import hashpumpy

secret_key="secretkey"
known_data="data"
appended_data="append"

hash_1="9885f8af04289135df259e34bd22d17fe45ea81e" # hash of secret_key+known_data
hash_2="e9163e43652a921df34f76e635d32f6aad1286b8" # hash of secret_key+known_data+appended_data

new_hash,msg=hashpumpy.hashpump(hash_1,'data','append',len(secret_key))
print(new_hash,msg)

Output:

  475bdd96a25e7717842072c5be2944076ba31143
  b'data\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00happend'

But the hash I want to calculate is of secretdataappend

You forget one little step of how Merkle–Damgård construction works; the padding, here SHA-1 padding:

  append the bit $\texttt{1}$ to the message e.g. by adding $\texttt{0x80}$ if message length is a multiple of 8 bits.

  append $0 \leq k < 512$ bits $\texttt{0}$, such that the resulting message length in bits is congruent to $$−64 \equiv 448 \pmod{512}$$

  append ml, the original message length, as a 64-bit big-endian integer.
     Thus, the total length is a multiple of 512 bits.

Therefore the real input is

$$\text{SHA-1}(\text{secret_key}\mathbin\|\text{known_data}\mathbin\|pad1)$$

because the attackers only get the hashed value. And, you need

$$\text{SHA-1}(\text{secret_key}\mathbin\|\text{known_data}\mathbin\| \text{pad1}\mathbin\|
 \text{appended_data} \mathbin\| \text{pad2})$$

for extension attack. This works similarly for any hash function that uses the same padding mechanism.

The attackers can access the hash of a padded message and they can extend it in this way. This is due to the artifact of Merkle–Damgård construction. SHA-3 is safe from this attack by design and later the new SHA2 modes SHA512/256 and SHA512/384 and other truncated versions of SHA2 also have resistance to length extension attack.

SHA-1 or MD5 is not considered secure. Use modern Hash functions like SHA3 or Blake2 with good output sizes to prevent the generic collision attacks like at least 256-bit.


elliptic curve infinity point implementation returns exception I am trying to implement an elliptic curve discret logarithm problem, but I have got a problem due to the representation of the infinity point. I tried this code :

first define what is an infinity point

    public Point infinity() {
        BigInteger xInfinity = new BigDecimal(Double.POSITIVE_INFINITY).toBigInteger();
        BigInteger yInfinity = new BigDecimal(Double.POSITIVE_INFINITY).toBigInteger();

        return new Point(xInfinity, yInfinity, this.E);
    }

then to test if a given point is an infinity point to return the same point when adding to it

public boolean isInfinity() {
    if (this.x == new BigDecimal(Double.POSITIVE_INFINITY).toBigInteger()
            || this.y == new BigDecimal(Double.POSITIVE_INFINITY).toBigInteger()) {
        return true;
    }
    return false;
}

but I still get an exception even if i try to calculate with simple points

  java.lang.NumberFormatException: Infinite or NaN

Thanks to help me solving this.

So to understand why the code doesn't work, we need a bit of background on IEEE 754 floating point representation of which BigDecimal is essentially an arbitrary precision extension. Most notably it defines special values to indicate a computation yielded "infinity" (which is the Double.POSITIVE_INFINITY you are using) and for computations that yielded an invalid result (such as log(0) or 1/0), this is called "NotANumber" (NaN). So what BigDecimal does, is that it is essentially a double with higher precision, but using similar values for these special cases.

Now BigInteger on the other hand, is an extension of the usual int to arbitrary precision, taking up as many bits as needed to represent the number at hand. As it is an extension of int, this also means that it doesn't support special values such as "infinity" or "NaN", but rather only actually representable integers.

When you do new BigDecimal(Double.POSITIVE_INFINITY).toBigInteger(), you create a new BigDecimal with the special "infinity" value / flag and try to convert this to an "ordinary" integer. But as you can't represent infinity with an integer, as this would need an infinite amount of storage, an exception is thrown instead.

Now, how can you fix this? Well, this is actually a non-trivial question and depends on what you want to do with the points. If you want to do elliptic curve cryptography using affine coordinates (which is terribly inefficient), then the usual approach is to give your Point a flag which essentially indicates "infinity" and test for the flag when you implement doubling and addition. When you use a more modern curve which has a complete addition law (that is it works for all points), then there are specific, concrete coordinates defined for the point at infinity. Of course the best solution would be to use projective coordinates, which can represent the point at infinity perfectly easy using a Z coordinate of 0.


Which block ciphers are considered staples for constructing hash functions? I've been looking all over the internet for an answer, and I must not know how to search because I've been really surprised that I haven't been able to find one. I'd also love to know what makes a block cipher a good candidate for being the basis of a hash function.
Thanks!

Block ciphers used in hash functions built per the Merkle-Damgård structure with a Davies-Meyer compression function (e.g. MD5, SHA-1, and SHA-2) have special requirements:

They must have a wide block (data input and output): as wide as the hash, thus twice the security (in bits) if collision-resistance is a consideration. For 128-bit security, we thus need a block cipher with a 256-bit block. This disqualifies all three variants of AES, and many earlier block ciphers.
They must be immune to related-key attacks, which normally are of secondary concern in block ciphers. This disqualifies DES when viewed as a 64-bit key block cipher (and makes it clumsy when viewed as a 56-bit block cipher), and TEA (Microsoft used it anyway in the original Xbox, and got pwned).
For best efficiency, they need a wide key input (at least twice the block size is typical), and high key agility (low computational effort to change the key). This disqualifies some block ciphers.

The block ciphers used thus tend to be built for the specific use, and designated as the block cipher of their associated hash. An example is SHACAL.


RSA - source and image - all are possible? Given a key $e = 3$ (the public exponent for RSA) and a group of numbers, say $Z_n^*$ (the multiplicative group of $n = pq$, where $p$ and $q$ are primes as requested by RSA).

I can find the decryption key: $d = e^{-1}$

Is it correct to say than any member $a$ in $Z_n^*$ has a source such that: $source = a ^ d$?

Edit: suppose we have gcd(3,phi(n)) = 1 as requested by RSA

If you're asking whether the power map $x\mapsto x^a \pmod n$ is injective, it suffices to take $a$ with $1 < a < \phi(n)$ and $\gcd(a,\phi(n)) = 1$.

Edit:  I couldn't complete the answer earlier. As mentioned in the comments $gcd(a,n)$ is enough, but for computational efficiency one might as well take $a \pmod n$ as the exponent. In the RSA setup, $n$ is square free thus the function is bijective.

To see this, note that after all $e,d$ have similar roles and if one of them, say $e$, satisfies $\gcd(e,n)=1,$ then there is an integer $f$ such that $ed+fn=1$ (by the fact that they are inverses) thus demonstrating $gcd(d,n)=1.$)


What are fixed points and length extension attack in hash functions? I was recently reading about hash functions, and I came across fixed points (one or more fixed points, interested in both) and length extensions, but I didn't exactly understand how these work. If someone can explain them or point me to a reference, I would be glad.

If $H(x) = x$, $x$ is a fixed point. If for a value the output of the function is the same as the input, it is called a fixed point.

A length extension attack is unrelated to the concept of fixed points. There is a good question about understanding length extension attacks here.


Can string lookups be vulnerable to timing attacks like array lookups are? Per “Can non-assembly crypto libraries truly be secure against timing attacks?”, array lookups are vulnerable to timing attacks. Like, if you do cresult[map[i]] and map is an array and cresult, is a string then map is vulnerable to timing attacks because it's an array but is cresult?

Yes, string algorithms can be vulnerable to timing attacks.

A very common example is string comparison. The best performing way to implement it in general is to compare two strings one character (or memory word) at a time and return inequality as soon as they don't match. However, this kind of a routine is vulnerable to timing attacks that can find the (approximate) length of the common prefix. Using such a string comparison routine to compare passwords or hashes has lead to attacks (an early 1970s example, a random 2009 example).

Similarly, when you are using a multibyte encoding, simply looking up a character in a string can allow timing to reveal details about the string before then.


How should ECDSA handle the null hash? In ECDSA, assume your public key is $Q=(x,y)$, then when performing the verification of any message leading to a null hash value (that is $H(M)=0$), the signature $(r,s)=(x,x)$ would always lead to a valid verification for that message, no matter what your public key is.

This is the case since upon verification you compute:

$e = \textrm{H}(m) =0$.
Let $z$ be the $L_n$ leftmost bits of $e$, so it's zero.
$w = s^{-1}=x^{-1}\bmod\,n$ by my choice of $s$.
$u_1 = zw\equiv 0\bmod\,n$ and $u_2 = rw=xw \equiv 1\bmod\,n$.
the curve point $$(x_1, y_1) = u_1 \times G + u_2 \times Q= 0 \times G + 1 \times Q=Q$$
The signature is valid if $r \equiv x_1 \pmod{n}$, invalid otherwise, but this is the case by choice of $r$.

I'm perfectly aware that the probability of finding a message $M$ hashing into $0$ is extremely low, let alone a useful message... But without going as far as considering some big companies with tons of computation power, the zero value might somehow happen for example because of targeted faults in the memory of the device or through some other means... Whatsoever it seems me to be an important value since it creates such a special case.

Yet, according to my reading of Sec1v2 and other standards concerning ECDSA, none consider this specific edge case.

I have done some tests with a few libraries, and at least OpenSSL, Go, and Crypto++ are completely falling for it. Only mbedTLS seems to reject it, and does so with an error "MBEDTLS_ERR_ECP_INVALID_KEY".

I know this does not imply much in term of practical security, but I believe this should still be considered in the frame of the so-called defense in depth, knowing such a special case exists.

Regarding signature generation, having $H(M)=0$ also has the consequence of rendering $s$ only dependent on $k^{-1}rd$, but this does not imply anything in term of key recovery as long as $k$ is a secret.

So, what should one do about this?
Should a library explicitly reject such a special case upon verification? If so, shall it reject the 0 value or signatures where $r=s$? In the later case, it would mean that signatures generated correctly with a null hash would still be verified correctly.

More generally, do you see any other implication of such a case? To which extent is a null hash something to be worried about for ECDSA?

This is true.

A conciser statement is: If an adversary can find a message $m$ for which $H(m) = 0$, then the adversary can forge the signature $(r, s)$ on $m$, where $r = x([k] Q)$ for some arbitrary ‘nonce’ $k$ (e.g., 1), and $s \equiv r k^{-1} \pmod n$, because $$x\bigl([H(m)\,s^{-1}] G + [r s^{-1}] Q\bigr) \equiv x\bigl([rr^{-1}k] Q\bigr) \equiv x([k] Q) \equiv r \pmod n,$$ satisfying the verification equation.

The obvious solution is to pick a hash function for which an adversary has no hope of finding preimages of 0, of which the streets of cryptography are littered with examples.  Here's one: SHA-256.

Suppose an adversary can cause a signer to accidentally compute 0 for $H(m)$ via some fault attack and learns a ‘signature’ $(r, s)$ on a hypothetical message $m_0$ with $H(m_0) = 0$.  Now what, supposing the adversary knows no such message $m_0$?  From this the adversary learns a uniform random curve point's $x$ coordinate $r = x([k] G)$, and a uniform random scalar $s \equiv r k^{-1} d \pmod n$, where $d$ is the signer's secret scalar and $k$ is the signer's secret nonce.

These are not independent, but they are related by a discrete log: if the adversary can compute $d$ from $(r, s)$, then the adversary can also compute $k$, the discrete log of $R = \pm x^{-1}(r)$ from the base point $G$.  And if the adversary can compute discrete logs, they might as well just compute $d$ offline from $Q = [d] G$ without bothering to apply a fault attack in the first place.

In other words, this does not really seem worse than a fault attack revealing an unintended signature on any other message with a nonzero hash.  And the signer can always thwart fault attacks by verifying the signatures it computes before revealing them.


How to decipher an ADFGVX cipher? I got introduced to the ADFGVX cipher, and it seems very tedious to decipher such ciphertexts. If I do not have access to the key square and the keyword, and I am just given the ciphertext and a string of numbers, how do you decipher it? The columnar transposition is another thing that makes it even more difficult to break. (I am assuming that ADFGVX comes with a columnar transposition). I am planning on making a code that can break it. A complete brute force seems possible, just too tiresome.

As you must know, ADFGVX is a German cipher from World War I. It was broken by the French (Painvin) during that war, but not without a major effort, and only on certain days.

It uses fractionation and a Polybius square, followed by a columnar transposition based on a keyword.

In Milton F. Friedman's Military Cryptanalysis, Part IV, pp. 103-149, he goes into detail about how to break this cipher.

There is also a useful paper from 1984, Konheim, A. G. (n.d.). Cryptanalysis of Adfgvx Encipherment Systems. Lecture Notes in Computer Science, 339–341. doi:10.1007/3-540-39568-7_26 (an extended abstract)

Konheim presents a four-step cryptanalytic technique to break ADFGVX.

Determine which column vectors are adjacent in the array.
Determine the relative order of the pairs of column vectors.
Recover the substitution.
Recover the transposition order of the columns in the array.

One thing that could be looked at first is this: perhaps the Polybius square is not a mixed alphabet after all, but alphabetical.


Families of public/private keys in elliptic curve cryptography I'm looking for a related key scheme for elliptic curve cryptography. The basic idea would be that there would be a master public key and a master private key. From the master public key, you could generate a series of public keys. From the master private key, you could generate the corresponding series of private keys.

Ideally, without the master public key, even given a number of public keys in the series, it would be impractical to determine any other public keys in the series or the master public key.

I've been told that it's possible, and have just the following description of how it would be implemented:

  S = Random number
  RootPrivateKey = Random number
  RootPublicKey = RootPrivateKey*point

  Master Private Key = RootPrivateKey, S
  Master Public Key = RootPublicKey, S

  PrivateKey(n) = RootPrivateKey + Hash(n|S)
  PublicKey(n) = RootPublicKey + Hash(n|S)*point

I understand the first five lines. But I am, unsure about the implementation details in the last two lines. Is the + supposed to be addition? If so, is it modular? In the public key, is + adding the two EC points? If anyone knows of any example code, ideally using OpenSSL, that would be the most helpful.

The typical use case for this kind of thing is creating deterministic wallets for crypto-currencies like Bitcoin.

I would assume that all the operations are to be done in the elliptic curve group (viewed as a module over $\mathbb Z/k\mathbb Z$, where $k$ is the order of the group), so that addition is the group operation and multiplication is elliptic curve point multiplication.

That is to say, assume we have an elliptic curve $E$, equipped with the point addition operator $+$ so that $(E,+)$ is a group.  We can define a scalar multiplication operation on $E$ simply as $$n \cdot P = \underbrace{P+P+\dotsb+P}_{n \text{ times}},$$ where $n$ is an integer and $P$ is a point in $E$.
Let $G$ be a point in $E$ which generates a cyclic subgroup of $E$ of order $k$: that is, $k \cdot G = 0_E$ (and $0 < j < k \implies j \cdot G \ne 0_E$), where $0_E$ is the group identity of $(E,+)$.  All these are public parameters shared by all users of the group.

In ordinary ECDSA, we would choose a random private key $x \in \mathbb Z/k\mathbb Z$ (that is, a random integer such that $0 \le x < k$) and compute the public key $Q = x \cdot G$.

However, if we also had a function $H$ mapping integers to (pseudo)random values in $\mathbb Z/k\mathbb Z$, we could define a sequence of private keys and corresponding public keys as $$x_i = x + H(i)$$ $$Q_i = x_i \cdot G = Q + H(i) \cdot G$$ where the $+$ on  the first line stands for ordinary addition (modulo $k$) and the $+$ on the second line is elliptic curve point addition.  (A consequence of the way we defined scalar multiplication above is that addition distributes over it: $(a + b) \cdot P = a \cdot P + b \cdot P$.)

There are various ways in which we could define $H$.  For example, we could use a hash function as in your example, possibly with a salt $S$, or we could perhaps pick a block cipher $B$ and a random key $K$, and let $H(i) = E_K(i)$.  In fact, assuming that $H$ and $Q$ are indeed truly public, I'm not even sure that there's any reason not to just use $H(i)=i$.  (Indeed, I can't even prove off the top of my head that this scheme is secure for any $H$.)  But the salted hash certainly seems as good as any other choice for $H$.

Edit: I just noticed that you wrote:

  "Ideally, without the master public key, even given a number of public keys in the series, it would be impractical to determine any other public keys in the series or the master public key."

I'm not sure if you wanted that to be impractical with or without knowledge of $H$ and of the indices $i$ corresponding to the known public keys $Q_i$.

If with, we have a problem: anyone who knows $H$, $i$ and $Q_i$ can calculate $Q = Q_i + (k-H(i)) \cdot G$.

If $i$ and/or $H$ can be treated as secret, things get trickier.  Obviously, $H(i)=i$ is a bad choice in this case, since anyone who knows $Q_i$ could then calculate $Q_{i+j} = Q_i+j \cdot G$ for any $j$, but using a hash or a block cipher for $H$ would eliminate that simple weakness.

Also, regardless of $H$, someone who knows $Q_i$ and $Q_j$ can calculate $Q_i - Q_j = (H(i)-H(j)) \cdot G$; but I'm not sure what, if any, good that would do them, assuming that $H(i) - H(j)$ is not likely to equal $H(k)$ for any valid index $k$.

Anyway, it would be helpful to know just what parties are supposed to be involved in this scheme and what they're supposed to know.  In my original answer, I'd been implicitly assuming that the public keys were, well, public and known to everybody.  If that's not supposed to be the case, that could complicate things a lot.


SHA-256 support for SecretKeyFactory in Java 6 and 7? According to the following linked Java documentation, the relevant option for SecretKeyFactory algorithm (ignoring deprecated options involving MD5 or DES etc.) running in JRE 6 and JRE 7 is: PBKDF2WithHmacSHA1

With the advent of SHAttered, does Oracle have any plan to support later SHA versions for SecretKeyFactory? What are the alternatives?

With the advent of SHAttered, does Oracle have any plan to support
  later SHA versions for SecretKeyFactory?

First, they don't need to. We are talking about PBKDF with HMAC-SHA1 here, which is a password-based key derivation function.You don't need collision resistance (which is the only property SHAttered broke) for password hashing, in fact it is trivial to find two passwords that hash to the same value with PBKDF2. What you really want from a password hash is one-way-ness / pre-image resistance (ie you can't recover the input from the output) other than using generic attacks.

Second, as of JRE8 you can use any pseudo-random function (PRF) the API knows instead of HMAC-SHA1 already and in fact HMAC-SHA256 is given as  an example in the documentation.

  What are the alternatives?

You don't use PBKDF2 from the standard library but rather use a binding to a more advanced password-based key derivation function such as Argon2, which has at least bindings for Java.


Block Cipher CTR mode when offset is not known by receiver When an encrypted message is received, it can be easily decrypted if the offset (=counter) of the received message is known (and also the required private key of course). This allows for random access on decryption. What if the receiver somehow forgot to keep track of the counter. Can the receiver still recreate the original plaintext? Or is it required that every received encrypted text is asigned a resp. counter value upon arrival? Or is this counter passed in some way such that the receiver does not have to keep track of it, e.g. as an additional parameter.

A scenario I was thinking of is that when the receiver missed the first N blocks. He/she would then not know the current counter resulting in not being able to decrypt.

Most protocols are like TLS, where you can't start in the middle. In most protocols, the counter is implicit, the receiver needs to count blocks from the beginning, if the receiver doesn't know the current value they can't decrypt.

The reason this is not a problem with live streaming video on the internet is that in modern video livestream, the video is cut into little 5 second chunks encoded in multiple resolutions for clients with different effective bandwidth, and the client uses TLS download of each 5 second chunk of the video, switching to smaller or bigger version depending on how long it took to download the previous 5 seconds of video. See HTTP Live Streaming.

Most protocols do not support "tune-in in the middle of broadcast, already have shared symmetric key, start decrypting in middle of stream".

If you are developing something like encrypted broadcast with shared key, you need your protocol to insert "resync" metadata every few seconds (maybe every second) for the benefit of clients tuning-in just now [1]. Maybe the resync provides only markers, and the "handshake" protocol the joining client uses to receive the shared symmetric key will also give the client the counter value for the next marker.

1 - Video codecs also need to do that if the video is not cut into separate 5 second video files (see "Periodic Intra Refresh" in x264).


AES CBC mode or AES CTR mode recommended? What are the benefits and disadvantages of CBC vs. CTR mode? Which one is more secure?

I wrote a rather lengthy answer on another site a few days ago. Bottom-line is that CTR appears to be the "safest" choice, but that does not mean safe. The block cipher mode is only part of the overall protocol. Every mode has its quirks and requires some extra systems in order to use it properly; but in the case of CTR, the design of these extra systems is somewhat easier. For instance, when compared to OFB, there is no risk of a "short cycle" with CTR.

This is why actually usable modes like EAX and GCM internally use CTR.


Is it generally okay to substitute “like for like”? Is it generally okay to substitute “like for like” in cryptographic protocols?

For example, many lattice protocols use SHAKE and SHA3 for various purposes.  However, both of those are relatively slow in software.

If I substitute Blake2X and Blake2b for these respectively, will the resulting (incompatible) protocol still be secure?  Similarly, if a protocol calls for an AEAD, and specifies AES-GCM, can I substitute ChaCha20-Poly1305 instead and still get a secure protocol?

Broadly speaking, the answer is yes IF the protocol was designed to be modular and not depend on any particular properties of the underlying algorithms.

If the protocol has a proof of security that abstracts the underlying primitives (i.e. if the theorem statement contains a phrase like "Let $blah$ be an AEAD scheme" and the proof contains a reduction to the AEAD security of $blah$) that proof should still more or less hold. If there is no proof of security you have two options: (a) write one and make sure the reduction goes through or (b) just make an educated guess. I recommend (a).

Some details, in particular exact security bounds, may change slightly when different primitives are used. For example, AES-GCM has a relatively low authenticity bound compared to something like AES-CTR-HMAC-SHA256. This really only matters if you're planning on encrypting huge numbers of very large messages with the same key, but it's worth checking nonetheless.

Standard caveats about side-channels and things like that apply, obviously.

EDIT: Just saw your question asks about hash functions too. Hash functions are sometimes trickier to reason about, especially if the random oracle model is involved. If the protocol is just reducing to the collision-resistance of the hash function, swapping one good hash function for another is probably fine. However, if the hash function is being used to instantiate a random oracle, you need to make sure the hash function you want to swap in is indifferentiable from a random oracle. So, for example, it's not ok in general to use SHA256 in place of SHA3, because the former is not indifferentiable from a random oracle.


How is a re-encryption done with elGamal? For example, the "Mental poker" protocol asks for Bob to encrypt each card with his key, shuffle them, and then pass them to Alice.  Alice then encrypts each card with HER key, shuffles them, and then hands them back.  Bob removes his original key and .....

Looking at homomorphic cryptosystems, elGamal seems to work well, but the result of any encryption gives TWO numbers:

$a = G^k \mod P\\
b = y^k \ DATA \mod P$

This makes me ask: How is a re-encryption done with elGamal?

First, I can't find a copy of the RSA mental poker report, so I cannot say for sure what kind of "commutative encryption" they wanted to use, but one type is the Pohlig-Hellman cipher, where you encrypt a group element $x$ using a key $k$ by computing $x^k$. To decrypt $y$ using the key $k$, you compute $y^{k^{-1}}$, where the inverse is computed modulo the group order.

In this case, what is meant is to use it like in Shamir's three-pass protocol. Alice encrypts using $k_A$. Bob encrypts using $k_B$. Alice decrypts using $k_A$. Bob decrypts using $k_B$.

Second, ElGamal is a public key cryptosystem, so encrypting a ciphertext doesn't immediately make sense. However, as it turns out, it is possible to do something similar with ElGamal.

So Alice has a public key $y = g^a$ and Bob has a public key $z = g^b$.

Alice has encrypted a message $m$ as $(x,w)$ with $x = g^k$ and $w = y^k m$.
Bob reencrypts $(x,w)$ as $(x', w')$ with $x' = x g^u$, $w' = w y^u (x')^b$.
Alice "redecrypts" $(x',w')$ as $(x'',w'')$ with $x'' = x' g^v$, $w'' = w' z^v (x')^{-a}$.
Bob decrypts $(x'',w'')$ as $w'' (x'')^{-b}$.

Note that

$x' = g^{k+u}$ and $w' = y^{k+u} \; m \; z^{k+u};$ and
$x'' = g^{k+u+v}$ and $w'' = y^{k+u} \; m \; z^{k+u+v} y^{-k-u} = m z^{k+u+v}$

so $w'' (x'')^{-b} = m$. Here, $(x,w)$ is an encryption of $m$ under $y$, $(x',w')$ is an encryption of $m$ under $yz$ and $(x'',w'')$ is an encryption of $m$ under $z$.

I suspect that these encryptions may be sufficiently independent to be useful in this context, but there is some proving to be done.


Security difference(s) between Shamir's Secret Sharing Scheme and Blakley's Secret Sharing Scheme? We know that Blakley's scheme is less space-efficient than Shamir's and that they both work based on pretty different aspects (Shamir = polynomial-based; Blakley = hyperplane-based).
Looking at how both work, my gut feeling tells me Shamir’s scheme seems to be more robust than Blakley’s because – for example – if an insider can gain any more knowledge about the secret than an outsider can, then Blakley's system no longer has information theoretic security.

But gut feelings rarely tend to represent actual facts and I might be missing something in relation to Shamir’s scheme, which is why I’m asking:  Are there any practical security differences between Shamir's Secret Sharing Scheme and Blakley's Secret Sharing Scheme? Am I correct to think that Shamir’s scheme is more robust than Blakley’s?

It would be nice (but optional) if you could add one or more relevant references to your answer.

They are both perfectly (information theoretical) secure, as you mentioned, Shamir's Secret Sharing Scheme is more space efficient.
When Blakley's scheme is optimized by using finite fields, it eventually turns into Shamir's Secret Sharing Scheme.
They are equal from a security perspective.


Why does AES have exactly 10 rounds for a 128-bit key, 12 for 192 bits and 14 for a 256-bit key size? I was reading about the AES algorithm to be used in one of our projects and found that the exact number of rounds is fixed in AES for specific key sizes:

$$
\begin{array}{|c|c|}
\hline
  \begin{array}{c} \textbf{Key Size} \\ \left(\text{bits}\right) \end{array}
 &\begin{array}{c} \textbf{Rounds}   \\ \left(\text{number}\right) \end{array} \\ \hline
128 & 10 \\ \hline
192 & 12 \\ \hline
256 & 14 \\ \hline
\end{array}
$$

Why these specific numbers of rounds only?

Why these specific number of rounds only?
Because AES is a standard; AES is an acronym for "Advanced Encryption Standard".
The standard specifies these specific number of rounds to ensure that different implementations are interoperable.
Why not more or less?
The reason these specific numbers of rounds were chosen was a choice of the designers. They did a lot of math to determine that these were the sweet spot between sufficient security and optimal performance.
Less might be insecure, and more might be slower with no benefit.
To quote the above book (from Section 3.5 The Number of Rounds):

For Rijndael versions with a longer key, the number of rounds was raised by one for every additional 32 bits in the cipher key. This was done for the following reasons:

One of the main objectives is the absence of shortcut attacks, i.e. attacks that are more efficient than an exhaustive key search. Since the workload of an exhaustive key search grows with the key length, shortcut attacks can afford to be less efficient for longer keys.

(Partially) known-key and related-key attacks exploit the knowledge of cipher key bits or the ability to apply different cipher keys. If the cipher key grows, the range of possibilities available to the cryptanalyst increases.


RSASSA-PSS-SIGN modBits size In RFC 8017 modBits is the length in bits of the RSA modulus n
I am using 2048 RSA key
modBits = 2048?
modBits = 2048 % n?
lets say n = 10 decimal = 1010 binary
then modBits = 4?
in my 2048 RSA key DER file n uses 257 bytes
then modBits = 257 *8 ?
which modBits = ... is true?

$\text{modBits}$ is the length of RSA modulus $n$ for example if you have 17 as RSA modulus than it has $\texttt{10001}$ as base two representation and has $\text{modBits} = 5$
If you generate a modulus $n$ which is 2048-bit than the $\text{modBits} = 2048$. Keep in mind that, we say a number $n$ is 2048-bit when it is between $2^{2047} \leq n \leq 2^{2048}-1$

  lets say n = 10 decimal = 1010 binary
  then modBits = 4?

Yes 4.

  in my 2048 RSA key PEM file n uses 257 bytes
  then modBits = 257 *8 ?

The leading 00 is coming from ASN.1 encoding of integers. Therefore you have 256-byte key.

  which one is the value of modBits?

8*256


Why shouldn't cryptocurrency hash algorythms, resist side channel attack? 2015's Argon2 publication suggests that cryptocurrency hashing like password hashing on backend servers should not be subject to side-channel attack:

Argon2d is optimized for settings where the adversary does not get
regular access to system memory or CPU, i.e. he can not run
side-channel attacks based on the timing information, nor can he
recover the password much faster using garbage collection [17]. These
settings are more typical for backend servers and cryptocurrency
minings.

Why ?

It is generally assumed that cryptocurrency mining is an "offline" process, that is you take one input from outside, and then after a long while you report back with a result. In particular, it is assumed that an adversary does not see when exactly one search starts and when it ends nor do they see how many tries it took you exactly. This makes timing-based side-channels extremely hard - most likely impossible - to execute, even if you leak "a lot" in terms of traditional timing side channels. Furthermore the input to the hash function - which is what you'd want to recover - is only secret right up until you make your outside communication announcing said input - at which point a more sophisticated recovery of it would be pointless...


Is there an accepted way to cryptographically enforce tracked changes on a document? I'm working on a document-editor project, and I would like to add a feature to lock tracked changes, similar to Microsoft Office.  The goal is to allow one user to lock tracked changes with a password, which would allow other users to only edit the document with tracked changes.  Any edit to the document that is not tracked would be detectable.
The solution I've come up with so far is to split the binary file into two sections: the original state of the file when tracked changes was turned on, and a list of the changes made since then.  A checksum of the original file would be included and encrypted by the password provided.  This would prevent other users from editing the block and producing a new checksum.
However, I believe that this would constitute a vulnerability because it would expose the password to a brute-force attack.
Is there any commonly accepted way to approach this problem, or any documentation on how other software (i.e. MS Office) solves this problem?
Thanks

A checksum of the original file would be included and encrypted by the password provided. This would prevent other users from editing the block and producing a new checksum.

This is a failed attempt to achieve integrity, with a secret password. A Message Authentication Code does that, with a secret key (see e.g. HMAC). One issue with the question's encrypted checksum is that for most document formats, it's easy to make two apparently identical documents with the same checksum. And even if we fix that by using a hash instead of a checksum, an encrypted hash is still not necessarily a proper MAC. That's because encryption is intended to provide confidentiality, not integrity. And for some common encryption systems (including the widely used and recognized AES-CTR), it's possible to alter the cryptogram obtained by encrypting a checksum/hash to match a different checksum/hash.

I believe that this would constitute a vulnerability because it would expose the password to a brute-force attack.

Yes, but there is a standard mitigation to this: using a purposely slow and salted Password-Based Key Derivation Function, such as Argon2 or scrypt, in order to generate the key of the MAC from the password (note: while PBKDF2 and it's ancestors are Password-Based Key Derivation Functions, they are obsolete, and do not seriously deter brute-force password search by powerful adversaries).
With the combination of a Password-Based Key Derivation Function and a MAC, there remains a devastating issue: the password or the key is needed to check the MAC, and that allows to forge a new MAC for a different text.
This issue is solved by using (public-key) digital signature instead of a MAC. Each user generates a public and a matching private key. The private key is necessary to make a signature, the public key allows to check it, and with that the integrity of the document, and which private key produced the signature. That could be extended to revisions (e.g. what's signed is the document as it stood when the user made the last revision. Multiple signatures of multiple states of the document can coexist, be stored in the document, and checked quickly enough).
A remaining problem is to distribute the public keys in a way ensuring their integrity and unique association to a user. One method is thru public key certificates.
Another remaining problem is storing the private keys in a manner ensuring confidentiality. That's usually done with encryption, and generating the encryption key with a Password-Based Key Derivation Function. That's standard with PGP/GPG private keyrings, and private keys matching public key certificates.

I would like to add a feature to lock tracked changes.
Is there any commonly accepted way to approach this problem?

Not much if you ask a cryptographer, beside

The aforementioned use of digital signature with a trusted public repository of public keys, or public key certificates.
Keeping the document on a trusted server keeping track of changes thru cryptographic authentication of users and user-originated changes, and defining the document as what's on this server; or a copy of that signed by the server.

And then the first option does not really prevents untracked changes, only bogus attribution of a change to a user that didn't originate it (assuming it's required that any change is signed). And in both options there remains the very real possibility that a user's computer is compromised, and changes to the document attributed to a user have been made contrary to the will of the user.
From a cryptographic standpoint, if one can read data using an untrusted computer, one can copy and alter it. The best crypto allows is detect that. This would be different if one assumed people can't modify what a program does. But that's not something crypto knows how to achieve on a standard, open computer.
Another option might be a blockchain. I don't really understand what that is or does (I recently asked), but can tell it does not qualify as widely accepted.


Definition of textbook RSA What is the definition of textbook or "raw" RSA?

What are some of the properties of textbook RSA?

How does it differ from other schemes based on RSA?

Textbook RSA:

Choose two large primes $p$ and $q$.
Let $n=p\cdot q$. Choose $e$ such that $gcd(e,\varphi(n))=1$ (where $\varphi(n)=(p-1)\cdot (q-1)$). Find $d$ such that $e\cdot d\equiv 1\bmod{\varphi(n)}$. In other words, $d$ is the modular inverse of $e$, ($d\equiv e^{-1}\bmod{\varphi(n)}$).

$(e, n)$ is the public key, $(d, n)$ the private one.

To encrypt a message $m$, compute $c\equiv m^e\mod n$.
To decrypt a ciphertext $c$, compute $m \equiv c^d\mod n$.

Signing and verifying messages is also defined (omitted for brevity).

Some (Undesirable) Properties of Textbook RSA:

It is malleable. I.e., if you give me a ciphertext $c$ which encrypts $m$, I can compute $c'\equiv c\cdot 2^e\mod n$. When the owner of the private key decrypts $c'$, she will get $2m\mod n$. In other words, I can make predictable changes to ciphertexts.
It is deterministic, and thus not semantically secure. I.e., I can distinguish between the encryptions of $0$ and $1$ (simply by encrypting both values myself and comparing the ciphertexts).

Differences with Deployed RSA:

Padding
Chinese Remainder Theorem is sometimes used in deployed systems for more efficient decryption.
$e$ is often statically set to $65537 = 2^{16} + 1$ for encryption speed (since there are only two set bits in that number).
Side-channel attack mitigations can be put in place for deployed systems too.

In no way is my list comprehensive, but hopefully this helps.


Turning a 64 bit block cipher into a 128 bit block cipher There are quite a few block cipher modes of operation that require 128 bits. There are also modes of operation where a higher block size than 128, e.g. a block size of 256 bit would even be practical.

Is there a generic method of combining two blocks together in such a way that two 64 bit blocks can be seen as one 128 block? Is there an efficient method that could be used for CTR mode of operation (the underlying primitive for most popular AEAD ciphers)?

There are two well-known Encryption modes, that can construct a $mn$-bit tweakable blockciphers from a $n$-bit blockcipher ($n=64$ for DES) with $1\le m\le n$.

The older one is CMC, being not parallelizable.
It was superseeded by Encrypt-Mix-Encrypt (EME), which is parallelizable.
The basic idea of the two algorithms is to encrypt each block of input data once, then perform a nonlinear transformation on the resulting bits and feed those into the second round of blockcipher calls. This is neccessary as otherwise attacks on the schemes would be possible. For the stong linking of the two input and  output blocks, double encryption can't be avoided.

As EME requires $2m+1$ blockcipher calls, in your case $m=2$, $5$ calls to DES are neccessary for each block of data.

As DES is slow compared to AES, using AES for 128-bit modes and Threefish for larger modes is preferrable.

Besides the performance issues with EME ($>2$ times the work) there also seem to be patent issues with EME.


Why is CBC with predictable IV considered insecure against chosen-plaintext attack? I just learned that using CBC encryption with an IV which is predictable is not secure.

From what I understand, using certain plain texts, and then guessing the IV that it uses, the attacker can verify if the IV he guessed was right. How does this qualify as an attack?

The CBC IV attack does more than that.

If I guess the plaintext corresponding to any ciphertext block I've seen before, and can predict a future IV, I can verify my guess by submitting a suitable message to be encrypted with that IV.  Obviously, that could be bad if, say, I knew the plaintext to be either "yes" or "no", and only needed to find out which one it is.

More concretely, the BEAST attack for example allows the recovery of cookies sent by a web browser over HTTPS.  The way it works is (more or less) that you first convince the browser to send an HTTPS request where a block boundary falls just after the first unknown byte in the cookie (e.g. by adjusting the length of the requested URL) and intercept the ciphertext.

So now you have a ciphertext block that you know corresponds to, say, the string Cookie: secret=X, where X is an unknown byte.  Now you use the CBC IV attack to test all possible values of X and find the right one.  Then you repeat the process with a URL that's one byte shorter, so that you get a ciphertext block corresponding to ookie: secret=XY, where you now know X but don't yet know Y.  Then just keep repeating the process until you've recovered the entire cookie, byte by byte.

See this answer to a related question for more details.


Show that $\text{FACTORING} \le_P \text{SQROOT}$ I tried to prove that $\text{FACTORING} \le_P \text{SQROOT}$ in a general setting, so $n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}$.

  THEOREM:Let $n$ be a composite number and let $x$ and $y$ be integers such that $x^2 \equiv y^2 \pmod n$ and $x \not \equiv \pm y \pmod n$ holds. Then $\gcd(x+y, n)$ and $\gcd(x-y, n)$ are non-trivial divisors of $n$.

My attempt:

  $\text{FACTORING} \le_P \text{SQROOT}$: Suppose we have an algorithm $\mathcal{A}$ that solves $\text{SQROOT}$. We show that we can then factor $n$ with prime factorisation $n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}$. Select a random $x \in Z/nZ$ with $\gcd(x,n) = 1$. Compute $a = x^2 \pmod n$ and use $\mathcal{A}$ to find a square root $y$ of $a$ modulo $n$. If $y \equiv \pm x \pmod n$ choose another $x$ and repeat this process until a $y$ with $y \not \equiv \pm x \pmod n$ is found. Since there are $2^k$ distinct square roots of $a$ modulo $n$ the chance that said procedure needs to be repeated is $\frac{1}{2^{k-1}}$. So by the theorem above we can find two non-trivial divisors of $n$ in expected polynomial time. Repeating this procedure for the thus found factors of $n$ we can find the prime factorisation of $n$ in expected polynomial time.

I am a bit unsure about the whole "expected polynomial time" thing. I have only heard informal definitions of it until now. Could you please have a look at my proof?

EDIT: I initially accepted the answer of Meir Maor below, but there was a gap in it as I just realised:

  $k=2$ is the worst case. But this implies only that $n=p_1^{\alpha_1}p_2^{\alpha_2}$, not $n=p_1 p_2$. So we still have to find some non-trivial divisors of the thus found factors of $n$ to get $p_1$ and $p_2$. I would like to keep the rigour of Meir Maor's answer, but I do not know how to determine the runtime of this procedure. Could you help me?

Your proof is essentially correct.
You may improve rigor by either calculating exactly or giving a bound on it's expected runtime.

If we take the simple case(which is also the worst case) where k=2 we get a probability of 1/2 to get a different root.

It should be noted that since our root x was uniformly random over Z/nZ it is also uniformly random over the roots of a. And therefor the probability of success at each attempt is 1/2 regardless of how our SQROOT algorithm chooses which root to provide.

If the probability is 1/2 per iteration the expected number of iterations is 2. This can be as 1/2+1/4+1/8... With probability 1/2 it takes 1 iteration with probability 1/4 it takes exactly 2 (fail, success) with probability 1/8 it takes exactly 3 (fail,fail, success) etc.

For k>2 the probability of success only increases and the expected invocation count is lower.

Therefor the expected runtime is 2 invocations of SQROOT + O(log(n)).
The additional element is for the gcd and random selection part (or even receiving input and giving output).


Diffie-Hellman: choosing wrong generator "g" parameter and its implications of practical attacks In traditional DH one chooses two shared parameters: a large prime $p$ and base $g$, which is primitive root $\bmod p$. Suppose that the generation algorithm is broken and $g$ generates only a subgroup (the group with fewer elements than the number of coprimes to $p$), what could be the possible attack? what's the complexity ? are there any real-world examples of attacking wrong DH parameters (implementation)?

As far as we know, Diffie-Hellman is secure as long as the subgroup generated by g is impervious to discrete logarithm. When working modulo a prime p, this is achieved when the following are met:

p is large enough (at least 1024 bits, go to 2048 bits for a bigger safety margin) and is not a "special form" prime (a randomly generated prime will be fine with overwhelming probability).
the subgroup generated by g has an order t which is such that there is at least one prime factor q of t which is "big enough", i.e. more than 2k bits, when k is the "security level" (e.g. to have at least 80-bit security, q should be at least 160 bits).

Note that it is in no way necessary that g generates all non-zero integers modulo p. It is fine if it generates a strict subgroup, as long as that subgroup cannot be split into several subgroups, each being very small. This is the essence of the necessity of at least one medium-sized prime q in the factorization of the subgroup order t.

The order of g, called t above, is a divisor of p-1. With overwhelming probability, a randomly generated g will imply an order which will not be much smaller than p. Indeed, there is only one chance in a billion to hit a g which implies an order t smaller than p by more than 30 bits (because 230 is about one billion). It is preposterous to imagine that a random g, modulo a 1024-bit prime p, will imply a subgroup order smaller than 900 bits.

The biggest prime factor of a random integer of n bits will have length, on average, about 0.3*n. It is extremely improbable that the biggest prime factor will be much shorter than that.

Bottom-line is that a purely random prime p (of at least 1024 bits) and a purely random g modulo p will be fine. To get bad DH parameters, you have to do it on purpose.

However, some people are arguing for ensuring that p and g are fine with "stronger" arguments than the probabilistic properties explained above (mathematically, these probabilities are extremely strong, but convincing people is not only about mathematics, but also about psychology). First, p will be generated as a "nothing up my sleeve" number with a completely open and fully described pseudo-random generator. See appendix A of FIPS 186-4 for an illustration (this is for DSA, but it may apply to DH as well). Then there are two ways for g:

The smaller prime q could be generated first; then p is produced randomly as p = qr + 1 for random r of the right size, until a prime p is reached. Then a random h modulo p is produced, and g is set to g = h(p-1)/q mod p. This yields either g = 1 (with extremely small probability) or a g with an order exactly equal to q, which is fine.
p could be generated as a so-called "safe prime". I.e. random odd integers u are generated until both u and p = 2u + 1 are both prime. Then set g = 2: the order of g is then necessarily equal to u or 2u, and both are fine. Generating a safe prime is computationally expensive, but having g = 2 yields a slight performance boost when doing the actual Diffie-Hellman.

When the whole process is fully described, as in Appendix A of FIPS 186-4, it can be verified, which guarantees against DH parameters which have been made weak on purpose.