How robust is my coded output? I create codes and ciphers and as a hobby and I was wondering if there was any outfit that would 'test' your output to see how resilient it is. Is there a group anywhere that will accept code, try to break it, and report back to you with results? Or is there anyone who would do it on their own?

Thanks,

No. Usually the Kerckhoff principle is considered. That means that the security of a cipher should rely on the key alone. The algorithm itself should be considered known. You could think of the algorithm as a single key that anybody that knows the algorithm possesses. Such a key should not be considered secure.

There is no generic way of testing the security of an unknown cipher, even if the plaintext and ciphertext are known. A block cipher is supposed to be a PRP - a pseudo random permutation - where the specific permutation is chosen using the key. Of course you could find relationships between the plaintext and the ciphertext for very weak ciphers. Usually attacks are on specific design or implementation details of the cipher, not directly on the ciphertext.

Basically to test the cipher you should create a paper formally describing it. The paper should indicate why you think the cipher is secure. You'd then have to find experts to take a look at it and possibly attack it. The best way to do that is to enter it into a competition.

If you're just experimenting, try to study attacks on other ciphers first. Then try and perform similar attacks on both your and other ciphers. See why other ciphers are broken.

If you subject your cipher to a competition prepare to be tossed out in the first round. Remember: the old ciphers of pioneers such as Bruce Schneier and Ron Rivest would be tossed out in the first round as well.


Using Montgomery ladder to calculate the coordinates In one of my assignments I need to solve the problem below:

  For a Montgomery curve $3y^2 = x^3+x^2+x$ over ${\mathbb{F}}_{11}$ and point $P = (9,8)$, compute the $x$ coordinate of $3P$ using the Montgomery ladder.

I just need a hint to get an idea and not the whole answer. if anyone with some useful links would also be appreciable. As I tried to search google for this but was not able to get any idea.

Is it that I need to find it as $3P = 2P + P $ because I found one question about scalar multiplication here. but then I think it is not the correct way to use the Montgomery ladder.

The Montgomery Curve is introduced by Peter L. Montgomery for speeding up the Pollard and Elliptic Curve Methods of integer factorization. Montgomery Curves are in the form $By^2=x^3+Ax^2+x$ and it is also represented as $M_{A,B}$.

Addition and Doubling Formulas of Montgomery Curves

Given Montgomery Curve $By^2=x^3+Ax^2+x$ and the point $P_1 = (x_1,x_1)$ and $P_2 = (x_2,x_2)$ than the addition and doubling, $P_3 = (x_3,x_3) = P_1+P_2$ as follows

Addition formula in Affine Coordinates: $(P1 \neq \pm P2)$

\begin{align}
\alpha & = (y_2 − y_1)/(x_2 − x_1)\\
x_3 & = B \alpha^2 − A − x_1 − x_2\\
y_3 & = \alpha (x_1 − x_3) − y_1
\end{align}

Doubling formula in Affine Coordinates: $(P1 = P2)$

\begin{align}
\alpha & =  (3x_1^2 + 2 A x_1 + 1)/(2 B y_1)\\
x_3 & = B\alpha^2 − A − 2x_1\\
y_3 & = \alpha (x_1 − x_3) − y_1
\end{align}

As usual, these are calculated from the geometrical meaning of addition.

Montgomery Ladder

The Montgomery Ladder is an algorithm to calculate $[x]P$ for a given scalar $x$ and a point $P$.

Represent $x$ in binary $x= x_0 + 2x_1 + 2^2x_2 + \cdots + 2^mx_m $ and let $m= \lfloor \log_2 x \rfloor$.

  R0 = 0
  R1 = P
  for i from m downto 0 do
     if xi = 0 then
        R1 = point_add(R0, R1)
        R0 = point_double(R0)
     else
        R0 = point_add(R0, R1)
        R1 = point_double(R1)
  return R0

Calculation

Now, $x=3 = 1 + 2\cdot 1$, i.e. $x_0=1$ and $x_1 =1$

$m= \lfloor \log_2 3 \rfloor = 1$. Therefore, we visit the loop twice.

since $x_i =1$ we will be always in the else case, or simply we run the below.

  1. R0 = 0
  2. R1 = P
  3. R0 = point_add(R0, R1)
  4. R1 = point_double(R1)
  5. R0 = point_add(R0, R1)
  6. R1 = point_double(R1)
  7. return R0

$R_0 = \mathcal{O}$
$R_1 = P$
$R_0 = \mathcal{O} + P = P$
$R_1 = P + P = [2]P$
$R_0 = [2]P+P = [3]P$
$R_1 = [2]P+[2]P = [4]P$
return $R_0 = [3]P$

The given Montgomery Curve $3y^2=x^3+x^2+x$ than it is $M_{1,3}$ so $A=1,B=3$ and $P=(9,8)$

$[2]P = (1,10)$ by the below simple sage math point doubling.

k.<a> = GF(11, modulus="primitive")
k.modulus()
A = k(1)
B = k(3)
x1 = k(9)
y1 = k(8)
alpha  =  (3*x1^2 + 2 *A * x1 + 1)/(2 * B * y1)
x3 = B * alpha^2 - A - 2 * x1
y3 = alpha *(x1 - x3) - y1
print x3
print y3

$[3]P = [2]P+P = (5,2)$ by the below simple sage math point addtion.

k.<a> = GF(11)
A = k(1)
B = k(3)
x1 = k(9)
y1 = k(8)
x2 = k(1)
y2 = k(10)
alpha = (y2 - y1)/(x2 - x1)
x3  = B * alpha^2 - A - x1 - x2
y3  = alpha * (x1 - x3) - y1
print x3
print y3

Notes :

One might say that we don't need step 6 since we are not returning it. Keep in mind that that is a need for protection from side-channel attacks.
This ladder algorithm from Wikipedia and it is not an optimal one. See The Montgomery Powering Ladder for a better version.
There is also a full coverage chapter "Montgomery curves and the Montgomery ladder" by Bernstein and Lange to further read.


Achieving 256-bit encryption strength with PBKDF2 - HMAC-SHA1 I am interested in the theoretical consideration of the bit strength of an encryption key and its precursor.

Assume a given environment as follows:
a. My encryption algorithm is AES-256
b. My key derivation function is PBKDF2 with HMAC-SHA1 with
   b1. Salt strength of 128 bit (32 chars of a truely random hex string)
   b2. Iteration count is 4096

My objective is to achieve 256 bit "encryption strength" based on the above environment

Evidently, I can not achieve a "true 256-bit total strength" with the environment as stated above, since the randomness provided by the SHA1 in the PBKDF2 standard is at most 160 bit.
From RSA Document "PKCS #5 v2.0: Password-Based Cryptography Standard", March 25, 1999:
"The length of the derived key is essentially unbounded. (However, the maximum effective search space for the derived key may be limited by the structure of the underlying pseudorandom function"
and

"....Thus, even if a long derived key consisting of several pseudorandom function outputs is produced from a key, the effective search space for the derived key will be at most 160 bits. Although the specific limitation for other key sizes depends on details of the HMAC construction, one should assume, to be conservative, that the effective search space is limited to 160 bits for other key sizes as well."

My questions is:
Since the most I can expect is "160-bit encryption strength" from my existing environment, if I feed the result of the PBKDF2 output to a Skein 512-512 hash function, and use the left-most 61 hex (=244 bit) characters of its output as an encryption key, will I then have my sought-after 256-bit total encryption strength (I have added the 12 bit extra "strength", due to iteration count, to my calculations)?

As others have pointed out, you are never going to get more strength out of it than you put into it; you are just going to make it so the attacker has to go after the password instead of brute forcing the key.  And because nobody would try to brute force a 128 bit key, stretching to 256 bits isn't going to do any good. The attacker will go after the password. (I'm assuming that the salt is not secret.)

However, there is still a good reason to move from SHA1 to SHA256 for deriving a 256 bit key with PBKDF2. There is a bug in the design of PBKDF2. If you extract 256 bits from PBKDF2-HMAC-SHA1 then the attacker can go after the first 128 bits using only half of the hash compressions that you did to generate it.

This shouldn't be a problem where the attacker needs the entire 256 bits as in your usage, but there are cases where this does give a 1 bit advantage to the attacker.

So I would strongly recommend that you use HMAC-SHA256 as your PRF in PBKDF2 when deriving a 256 bit key.


Why is SHA-512 limited to an input of $2^{128}$ bits? Both SHA-384 and SHA-512 are limited to an input size of less than $2^{128}$ bits. Considering SHA-512 has a higher output size, couldn't it include more input data?

The standard FIPS.180-4 defines a padding scheme that limits the upper input size.

  Then append the 128-bit block that is equal to the number $l$ expressed
  using a binary representation.

Where the $l$ is the message length. Therefore, according to the standard, you can hash at most $2^{128}$-bit-sized input messages.

This upper limit, actually, due to the Merkle-Damgård (MD) design of SHA-512. MD based hash functions are vulnerable to length extension attacks and appending the length simplifies the security proof.


If the Riemann hypothesis solved "Sir Michael Atiyah claims to have demonstrated a simple solution to the Riemann hypothesis".

If solved, what results we will have in Cryptography?

Nothing. The Riemann hypothesis would have some implications about the distribution of prime numbers. No cryptosystem uses the distribution of prime numbers for security, so there would be no effects on any current cryptosystem.

One cryptosystem in particular, RSA, uses prime numbers. But it doesn't use the distribution of prime numbers in any way, just the difficulty of factoring composite numbers which are the product of two large primes.

As a (strained) analog it would be like thinking that finding some information about the relation of total roadway length to population in countries and wondering how it would change mapping. Sure, maps draw roads, and countries, but the statistical information isn't relevant.


Exponential cipher theory misunderstanding Say I pick modulus $m=2633$ and key $e=13$

My private key $d$ is $13$ inverse in $\bmod 2632$ which I need to compute

$(e,m)$ is my public key that anyone can use to encrypt message for me and then send it to me as:

encrypt message: "TH" ($T=19, H=07$) as $1907^{13} \bmod 2633$

but since $(e,m)$ is public anyone can compute my private $d$ using EEA

so where is the security? I know I do not understand this, could anyone explain?

Exponential cipher is a symmetric-key algorithm, not public-key one. So you don't have any public and private keys. You only have one secret key and it's used for encryption of messages between people that know the key.

The security of exponential cipher is not in the computiation of $d$ from $e$, which is easily computable by EEA as you said. The security of this cipher lies at the principle of discrete logarithm problem, as well as Diffie-Hellman key exchange does.

The principle:

You have prime modulus $m = 2633$, secret key $e = 29$, where $\gcd(e,\ m-1) = 1$ so $e$ has inverse $\textrm{mod}\ m-1$ and you can compute your key $d$ for deciphering:

$d = |e^{-1}|_{m-1} = |29^{-1}|_{2632} = 2269$

The only thing you have to keep secret is the key $e$.

The encryption pattern is ($c$ for ciphertext block, $p$ for plaintext block) :

$c = |p^e|_m$.

So you can encrypt "TH" (T=19, H=07) as $c = |1907^{29}|_{2633} = 2199$.

To decrypt:

$p = |c^d|_m = |2199^{2269}|_{2633} = 1907$ = "TH"

Discrete logarithm problem:

Consider a possible attacker who has modulus $m = 2633$, block of ciphertext $c = 2199$ and corresponding block of plaintext $p = 1907$. What does he know:

$c = |p^e|_m$

$2199 = |1907^e|_{2633}$

which means $e =|\log_{1907}{2199}|_{2633}$

The discrete logarithm problem says that it's not possible to compute the key $e$ from this equality in reasonable time (for higher numbers of course).


How to use openssl securely? I don't want openssl to log my keys and passwords... but I don't use gpg as I need more manual control for my purpose. I also don't like gpg  and would like to use openssl without logging.

Does openssl too engaging in logging when I open the interpreter

  Openssl

My main question revolves around linux logging when others have access to my offline pc?

If you are afraid that somebody can get access to your private keys or passwords, disconnect your machine from network and never connect it again; transfer public keys that you want to publish via USB stick; when you need to encrypt or decrypt something, use USB stick, put there the needed files, attach it to your offline machine, encrypt or decrypt on this machine, put result back to USB stick.

Depending on how important are purposes you use openssl for, you may want to put your machine in some room with proper electromagnetic and sound isolation :) And first of all, make sure nobody gets physical access to this machine :)


Is it accurate to say that SHA-3 (keccak) is based on Merkle-Damgård? I know that sponge functions are different in many ways. Yet I'd like to know if SHA-3 can nonetheless be said to be "based", if not simply "inspired", by the Merkle-Damgård construction. To be more precise it seems to be a wide-pipe construction followed by an entropy collection procedure.

Is it accurate to say that SHA-3 (keccak) is based on Merkle-Damgard?

No. That is about as accurate as saying that airplanes are based on motorcycles, because they both have engines.

In MD, the input to the hash is converted to a key, which is used by a block cipher to encrypt the initial value, then the entire encrypted value is the hash.

In a sponge based hash, the input is XOR'd into the initial value, then the entire value is ran trough a permutation, and finally a small piece of the permuted value is used as the hash


Changing algorithms during encryption Inspired by "Guarding against cryptanalytic breakthroughs: combining multiple hash functions", I am curious if there is a cryptographic reason to use only one algorithm during encryption.

For example, start with Blowfish, move to AES, switch to DES, etc, in a defined, but semi-unpredictable fashion (maybe basing which one to choose next off the last 4 bits of the most-recently-encrypted block's original plantext).

Would changing algorithm (but keeping the key identical, for sake of argument) have any cryptographic value? Could such a scheme be more resilient to cryptanalysis?

As many of the other answers have said the proposed method above is only as strong as the weakest cipher used (this is especially dangerous if the same key is used for all the ciphers).

Furthermore, basing the cipher transitions on the plaintext opens up the door to a range of timing side-channel attacks if any of the ciphers are faster or slower that each other.

One way you could guard against cryptanalytic breakthroughs is to use secret sharing to split a message $m$ into $n$ plaintexts ($p_i$) that must be combined to recover the original message.
$$ m = p_0 \oplus p1 ... \oplus p_n $$
These $n$ plaintexts could then be enciphered by $n$ ciphers.

$$ciphertext = cipher_0(key_0, p_0)|cipher_1(key_1, p_1) ... |cipher_n(key_n, p_n)$$

The size of the ciphertext increases with the number of ciphers (size of message $\times n$), but you could ensure that even if $n-1$ of the ciphers were broken the message would remain secret. This also requires $n$ keys.

One could try some sort of key expander to expand a $key$ to a different key for each cipher:

$$key_0 = cipher_0(cipher_1( ... cipher_n(key, key)), cipher_1( ... cipher_n(key, key)))$$
$$key_1 = cipher_n(cipher_0( ... cipher_{n-1}(key, key)), cipher_0( ... cipher_{n-1}(key, key)))$$

but I don't have much faith its security (theoretically it is probably as weak as it's weakest cipher) and when one is so concerned with cryptanalytic breakthrough it would be foolish to introduce a "trusted" key expander (why not then introduce a trusted cipher and use that). I have asked the key expander issue as a separate question ( Designing a key expander out of ciphers ).


How insecure is AES-128-CTR to encrypt any kind of data using the Ethereum keystore file format? I am using the Ethereum keystore file format to encrypt any other data such a plain text or JSON.

Here is an example of pseudocode of the implementation:

MY_PASSWORD = "VeryDifficultPasword432131!@!#%"
MY_TEXT = "This is my secret text"

iv = randomBytes(16)
kdfparams = {
    dklen: 32,
    n: 262144,
    r: 1,
    p: 8,
    salt: randomBytes(32)
}
key = scrypt(MY_PASSWORD, kdfparams)
ciphertext = encryptCipheriv("aes-128-ctr", MY_TEXT, key, iv)
mac = sha3(key[16:32], ciphertext)

With this code I can generate the keystore file that looks like this:

{
    "crypto" : {
        "cipher" : "aes-128-ctr",
        "cipherparams" : {
            "iv" : "83dbcc02d8ccb40e466191a123791e0e"
        },
        "ciphertext" : "d172bf743a674da9cdad04534d56926ef8358534d458fffccd4e6ad2fbde479c",
        "kdf" : "scrypt",
        "kdfparams" : {
            "dklen" : 32,
            "n" : 262144,
            "r" : 1,
            "p" : 8,
            "salt" : "ab0c7876052600dd703518d6fc3fe8984592145b591fc8fb5c6d43190334ba19"
        },
        "mac": "102aedfe8c308c735a76295f9908d9b7de40fb1c07f2f71e05de7a0b2f323a12"
    }
}

This is the standard file that store millions of dollars of people in Ethers.

Questions:

Is this secure?
If not, why?
If yes, is also secure
encrypting plain text or JSON (no hexadecimal format)?
Is secure to set a smaller kdfparams.n?

Edit:
To clarify why I'm asking this is because another person said this:

  This is not secure at all. This implementation contains many basic errors. One example is using
  an insecure random number generator, which utterly destroys the
  security of the encryption. Another is using AES-128-CTR without
  authentication.

The worst purely cryptographic weakness is the password (1). The worst (and much worse) practical weaknesses are likely to be in the implementation (6) (7), and those (4) (5) that cryptographers dismiss as out of scope of encryption (the question's only stated objective).

Candidates for weaknesses, from cryptographic (but still to consider) to implementation:

The password: it is hard to remember a password with over about 48 bits of entropy (that's about equivalent to a 16-digit number, like 3141592653589793 or 2718281828459045, and more than envisioned by the obligatory XKCD). Using N=262144=218, r=1, p=8=23, buys at the very least 18+3+1=22 bits (see this) compared to a straight SHA-256 hash followed by AES-128, I guess about 32 bits stronger, thus the key might be about 80-bit good, which is not entirely unbreakable by brute force but still quite secure.
AES-128: this has a 128-bit key, no known purely cryptanalytic attack better than brute force, and is thus much better than the password.
CTR mode: with AES's 128-bit block, the only way key-stream reuse could kick in would be a bad random number generator for the IV (see 6)
The size of the plaintext can be effortlessly deduced from the size of the ciphertext. This is explicitly not a theoretical weakness of encryption, since length is excluded from what a cipher is supposed to hide about plaintext. However, that can be a practical weakness. Say analysis of ciphertext concludes that it is 17267095423 octets; and there exists, somewhere in the prosecution's exhibits a file with exactly that size, demonstrably predating search and seizure of the ciphertext, and which mere detention is illegal.
Lack of detection of (intentional or accidental) ciphertext alterations, corresponding to predictable alteration in the plaintext: again this is explicitly not a theoretical weakness of encryption, but can allow some attacks if the adversary can alter the ciphertext (example: if the plaintext is an executable or PDF with a known fraction, that can allow changing what the executable does to about anything, or make the PDF display as about anything). Authenticated encryption (AES-GCM..) solves that.
Random number generator: if this is bad, or worse gets more or less stuck (obligatory XKCD and Dilbert which turn to reality all too often), that would enable recovering plaintext in many scenarios, including repeatedly enciphering different English text or email addresses with the same password.
A side channel, that is broadly speaking unforeseen or unmitigated leak of information in the implementation or usage context. There are so many:

Password recovery from the password holder by exploiting a procedural goof (password on a postit note, master password list), rubber-hose cryptanalysis (obligatory XKCD), legal variants (involving use of expressions on the tune of contempt of court), bribery, chemical impregnation..
Password recovery by shoulder surfing, key logger (software or hardware), camera, microphone (a good audio capture of the sound of keys when entering a password leaks a lot of info about the password, especially when correlated with known keyboard entry by same operator under same conditions)..
Straight compromise of plaintext as shown on screen (with TEMPEST variants of that), printed, while transmitted to a printer or remotely accessed by a network, or just "temporarily" stored..
Straight compromise of the OS of the machine doing encryption or decryption (getting temporary root access is enough, means in 7.7 are game to the attacker).
Cryptanalytic side channel at a distance, including DPA and electromagnetic variant DEMA, and hypothetically timing if the machine doing the encryption/decryption is accessed by a network and does not use AES instructions.
Cryptanalytic side channel from a process running on the same hardware (including another VM), including cache-based targeting for AES when not using AES instructions, or more general ones (Meltdown, Spectre) which are all the rage these days.
Exploitation of various software bugs; that's huge.


What, cryptographically speaking, is a "long message"? I have read about long message attacks on some cryptographic hash functions. However, I don't quite understand what is being referred to as a "long message".

Also, do long message attacks only apply for such "long" messages or can they also be used (any exceptions?) with "normal" messages? ("Normal" as opposed to "long", I mean)

Thank you.

EDIT:
Actually, I thought I wanted a general explanation, but I guess it might be better that I specify the source of my misunderstanding. Reading Gauravaram and Kelsey's Cryptanalysis of a class of cryptographic hash functions in trying to understand second-preimage attacks, I came across the generic long message second preimage attack on GOST in Appendix Section E.1 (page 26) and it got me wondering on the meaning (and pertinence) of the so-called "long message" attack.

Hope this clarifies my question better.

Without the specific reference I can't be sure this is what you are talking about, but generally a "long message" attack is a way to defeat second preimage resistance with less complexity than expected.  It uses a time-space tradeoff to find a second preimage with complexity $2^{n/2}$ for a $n$-bit hash function (normally you would expect $2^n$).

In the simplest form, what you do is generate a message that is $2^{n/2}$ blocks long, which will consequently have about $2^{n/2}$ "intermediate" hash values (output from the hash function upon processing each block).  You store those hash values in memory, and then try repeatedly hashing random messages until you find a message $m$ such that $h(m)$ is equal to one of the intermediate hash values.  This will take about $2^{n/2}$ tries, since you have $2^{n/2}$ targets to shoot for.

At this point you can split the long message on that target intermediate value and "splice" the message $m$ into that place, and it will still produce the same final output.  What this effectively does, is find a collision somewhere in the interior of the message and replace that substring with the new colliding one.  Since collisions are generally easier to find than second preimages (because of the birthday paradox), this leads to an effective second preimage attack.  Particularly, it requires only about $2^{n/2}$ time and $2^{n/2}$ memory, instead of $2^{n}$ time.

However, this is purely an academic attack since most hash functions use the Merkle-Damgard construction to handle large messages, and it includes a block at the end which specifies the length of the message.  In the above attack the two messages will not have the same length.


Memory-hard operations in work-factor hash functions I'm playing around with work-factor hash functions, and I'm looking for a memory-hard operation to make it resistant to GPU / parallel hardware attacks. I considered a very large (i.e. 64K) s-box that gets shuffled based on the state per round, but I have a feeling that there are ways to optimise such an operation for minimal memory usage.

My current best scheme is as follows:

state = pass
while(length(state) < 32768)
{
    state += sha512(state);
}

Is such a scheme guaranteed to require a lot of memory, or can it be optimised? I know there are tricks to reduce memory usage when computing hashes. Are there other simple operations that provide such guarantees?

The pseudocode you are showing here is not "memory-hard" - one can recreate the long sbox from the short "pass" when needed, by only 512 SHA-512 calls.

These calls are of increasing input length (i.e. need more time), but even this can be cut short by conserving part of the hash state during the loop (as SHA-512 is an iterative hash function and not a random oracle), allowing to calculate the result in $O(n)$ time ($n$ being the output length, in your case 32768).
This shortcut can be removed by appending the new hash result in front instead of at the end (or by another kind of shuffling between the rounds of your loop), but there might be other ones I can't think of right now.

Also, 64 KB of memory is not "very much" - you would need (scalably) many of those S-boxes which all are accessed (and changed) often, to be memory-hard.


Is Cramer-Shoup backdoorable? We recently had the question whether it's possible to have multiple private keys with one public key for the cramer-shoup cryptosystem.

There it was stated that finding such "secondary" private keys is possible if $log_{g_1}(g_2) \bmod q$ is known. However computing this discrete logarithm is infeasible as both $g$s need to be random.

But the description also mentions that shared group parameters are allowed, meaning a party A could generate the $g$s so other partys could use them.

Now let's assume this party A to be some standardization body, like NIST, getting the $g$s by somebody (for example the NSA). Now let's further assume that there exists some $a$ for which $g^a_1\equiv g_2 \pmod q$ holds and that the supplying party knows $a$.

Can the supplying party (knowing $a$) anyhow break the security of Cramer-Shoup (=IND-CCA2) if honest parties use the backdoored parameters?

Note: "honest parties" use the standardized group and choose their private keys following the specification and assume security of the parameters.

A Cramer-Shoup public key has the form:

  $B = g_1^{b_1} g_2^{b_2}; \quad C = g_1^{c_1} g_2^{c_2}; \quad D = g_1^{d_1} g_2^{d_2}$

and an encryption of $m$ has the form:

  $g_1^r, ~ g_2^r, ~ m B^r, ~ (CD^\mu)^r$

where $\mu$ is a hash of the first 3 components.

CCA security proof breaks down:

In the CCA security proof, you observe that if you know the private key then you can generate the challenge ciphertext as a function of $g_1^r$ and $g_2^r$ (mirroring how the receiver would actually decrypt), which gives:

  $g_1^r, ~ g_2^r, ~ m [(g_1^r)^{b_1} (g_2^r)^{b_2}], ~ [ (g_1^r)^{c_1 + d_1 \mu} (g_2^r)^{c_2 + d_2 \mu} ]$

Then the first step of the proof is to replace $g_1^r, g_2^r$ with $g_1^{r_1}, g_2^{r_2}$ with $r_1, r_2$ random. This change is indistinguishable by DDH, but not if the discrete log of $g_2$ with respect to $g_1$ is known, as in your case. The rest of the proof follows from an information-theoretic argument.

Explicit CCA attack unclear:

Even though the proof seems to break down, I'm having trouble demonstrating an explicit attack on CCA security. You can definitely break the hybrids of  the CCA security proof without even consulting the decryption oracle. But we know the scheme remains CPA-secure (see below), so this it's possible that there's a problem only in the proof while the scheme remains CCA secure (though I doubt that).

CPA security maintained:

Even if you give the adversary everything but $b_1$ -- including the discrete log of $g_2$ with respect to $g_1$ -- you can still argue that the scheme is CPA secure. That's because we still have $r, b_1$ chosen uniformly, so $g_1^{r b_1}$ is pseudorandom given $g_1^r$, $g_1^{b_1}$. In particular, the third ciphertext component (the only one that involves the plaintext) is pseudorandom.


If I encrypt data with two different ECC Private keys, how secure is the result? I'm wondering whether encrypting data with two different 256-bit ECC keys will result in a more secure encryption (minimum 384 bit equivalent) or will result in data that's effectively encrypted with a different (unknown) 256-bit key (or weaker).  The keys will be different, but will be based on the same curve.

Another acceptable option would be to do something like encrypt / decrypt / encrypt with 3 different keys (like Triple-DES, but with ECC), again based on the same curve.

I'll be using a hardware crypto chip that can do ECC encryption with 256-bit keys (uses "NIST standard P256 prime curve"), but I'd like to be able to have something a bit more secure, and I don't want to have to switch to software encryption (speed and memory limitations in an embedded device).

The purpose of this is to encrypt keys for general distribution, so the cyphertext will be public, with access for an extended period of time (several years).

I'm a programmer, not a mathematician, so please phrase answers accordingly.

TL;DR: If you separate the keys then you're fine.

In my answer I'll outline an encryption algorithm using two ECC keys and achieving (nearly) squared security and the general result for how to properly use two keys in group-based cryptography.

First note that a private key $a_1$ is a random integer used to multiply a base point on elliptic curves like $P=a_1\times Q$. Now observe that adding a second key $a_2$ to the mix yields $P'=(a_2\cdot a_1) \times Q$ which is equivalent to some $P'=k'\times Q$ and thus not stronger than simple discrete logarithm.

Now if you were to calculate two different public keys, security of these keys will actually multiply: $P_1=a_1\times Q, P_2=a_2\times Q$ requires you to break both instances of the elliptic curve discrete logarithm problem (ECDLP). The best speed-up for your keys only would be $\sqrt2$ which is absolutely negligible if we are talking about numbers like $2^{128}$.

On a side note it may be noted that this idea is obviously true, because you've just created two ordinary, unrelated public ECC keys (on the same key) of which you can find many, many more samples on the internet (all with the same type of mathematical relation). Also note that this independence doesn't hold for finite field discrete logarithms as the Logjam attack has demonstrated impressively.

So in (first  section) conclusion one could say: If you don't relate your public keys (and you use multpiles) you're fine.

Now, how can we use this actually for proper encryption. There are multiple ways to do this:

Do a standard KEM/DEM encryption and use ECDH twice for the KEM part
Do an ordinary ECC encryption (ECIES?) and just apply it twice with different private keys to the message.

The first approach should only be preferred if you don't already have a (working, tested and known-safe) implementation of ECIES (or some other ECC based encryption) at hand. If you dou have such an implementation, by all means use it and apply it twice (with different private ECC keys) and you're done.

If you don't have such an implementation, you have to go for ECIES. I'll leave the details to Wikipedia, but in a nutshell, ECIES works with two functions to encrypt data: $\operatorname{Encaps()}$ and $\operatorname{Encrypt()}$. Encaps will provide you with a session key which you can use to bulk-encrypt the data as well as with some data that allows $\operatorname{Decaps()}$ to recover the session key (given the private key). In ECIES, Encaps basically is ECDH: You put in the public key, it chooses a random exponent and will output you the exponent multiplied with the basepoint ($P_s=k\times Q$) and the hashed ECDH result ($s=H(x(k\times P))=H(x((k\cdot a)\times Q))$) which you then can plug-into the bulk encryption. Now what you do, is you use Encaps twice (with two different public keys obviously) and the securely combine the keys together (e.g. using HKDF).

Now the bulk encryption should also be at a comparable security level ($\approx$ 256-bit) and if it is, then you should be safe until general quantum computing is able to break ECC.


Is key derivation of a token shared secret necessary for usage of token in TOTP as specified by RF6238? TL;DR: Is it necessary to generate a 'random' key from a shared token secret string before putting it into a TOTP algorithm that follows the RFC 6238 specification? Or is it okay for me to put the token secret directly into the TOTP algoritm (of course with proper base32 or hex format depending on the algorithm used)?

Long Version:

Hello, currently I am trying to solve a challenge that relates to me generating the correct 10-digit TOTP based on my userid and certain string combinations. However, currently I cannot seem to generate the correct output, even though I have followed the RFC 6238 specification correctly (as can be seen here: https://tools.ietf.org/html/rfc6238#section-1.2), and even borrowed the code provided in the RFC to generate the TOTP.

As some background, the task provider has given me a sample input and output like specified below:

Sample Input:

  Shared key: "ninja@example.comHDECHALLENGE003" (without double quotes)

  Hash function used: HMAC-SHA-512

  T0 = 0, Timestep = 30 seconds (as per specified in RFC6238)

  Expected TOTP of 10 digits

Sample Output:

  Successful TOTP generated: 1773133250, for time of Mon, 17 Mar 2014 15:20:51 GMT

  base64 encoded POST Authorization username/password request: bmluamFAZXhhbXBsZS5jb206MTc3MzEzMzI1MA==

  (I have decoded the sample POST authorization to be 'ninja@example.com:1773133250' hence why I can say that the sample TOTP output is 1773133250)

In an attempt to replicate this result, I inputted the shared key "ninja@example.comHDECHALLENGE003" into the totp algorithms that I used with a hex representation of the key, i.e. 6E696E6A61406578616D706C652E636F6D4844454348414C4C454E4745303033, especially for the TOTP algorithm that is shown in the RFC 6238. Unfortunately it seems that I cannot get the correct result and instead got the output like this:

Attempted input:

  Hex encoded seed for HMAC512: "6E696E6A61406578616D706C652E636F6D4844454348414C4C454E4745303033" + "6E696E6A61406578616D706C652E636F6D4844454348414C4C454E4745303033";

  Time inputted (the message that is going to be hashed) is 1395069651L, representing the time received in sample output

Result of attempt (same output from custom script, other Python modules, and the Java implementation given in RFC6238 documentation):

  Generated TOTP: 0490867067

After some more reading though, I have noticed that it seems that the token shared key/secret that is entered into the TOTP main function (i.e. the one that is going to be encoded into SHA-512) derived from a random generator or a key derivation function, according to the RFC 6238. With this in mind, my main question then would be (sorry after a long explanation haha):

Is it possible and actually necessary for me to first input the shared token to a key derivation function first, before then inputting it into the TOTP algorithm (i.e. do the Key Derivation first, then input into the SHA portion of the TOTP)? If so, should I then use the same shared key as he salt of the key derivation function?

No, you do not have to do any key derivation. The shared secret is just an arbitrary byte string which is used to key the HMAC function.


Lightweight Asymmetric encryption algorithm I'm an embedded systems researcher, and new in the crypto field. Actually, I need to know if there are any lightweight asymmetric encryption algorithm especially considering the time needed for key generation.

I found that NTRU is considered one of the most lightweight asymmetric crypto systems, is this correct?

When an embedded device needs asymmetric crypto to encrypt, (e.g. measurements it makes) or check authenticity (e.g. of commands or firmware updates it receives), there is no need for a private key or key generation in the device, and nothing beats RSA and Rabin on simplicity and speed (for RSA: with $e=3$, which is safe when used with proper padding); plus RSA and Rabin are well known, and patent-free. In these applications, RSA and Rabin main drawbacks are that cryptograms are at least the size of the private key (e.g. 256 bytes for 2048-bit RSA); however only a fraction of that needs to be overhead not conveying actual data (e.g. 66 bytes for RSA-OAEP with SHA-256).

When and if a device needs a private key (see final note), Elliptic Curve Crypto (e.g. ECDSA, ed25519) has many advantages, including very easy key generation, significantly faster computations for the private-key operation (e.g. signature generation), smaller keys, and smaller minimum size of cryptograms. But there is debate about if some particular implementations are patent-encumbered in some jurisdictions, or not.

On the RSA vs ECC debate: RSA private-key (except perhaps its key generation) can be made fast, using dedicated hardware, as used in many Smart Cards. Dedicated hardware is also used in all modern Common-Criteria security-certified embedded devices using ECC that I am aware of, thus if ECC might allow to do without the burden of dedicated hardware in some contexts, that's uncommon in such security-certified devices.

NTRU can also be considered, but is alleged to be patent-encumbered in some jurisdictions, and is a relatively recent player, thus is of less recognized security, in no FIPS standard, nor endorsed by ANSSI (French) or BSI (German). In particular the signature part of it (NTRUSign) was broken in 2006 (Phong Q. Nguyen and Oded Regev, Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures, in Journal of Cryptology, 2009; preliminary version in proceedings of Eurocrypt 2006); and the break and fix cycle on NTRUSign has hardly stabilized (Léo Ducas and Phong Q. Nguyen, Learning a Zonotope and More: Cryptanalysis of NTRUSign countermeasures, in proceedings of AsiaCrypt 2012).

Note: having a private key in a device is useful only when some of the other entities that have to authenticate such device, or send it confidential data, can not be trusted to hold and properly use a common secret key. If all such other entities can be trusted, symmetric crypto with device-unique diversified keys (derived from a master key and device serial number) can be made functionally equivalent to full-blown asymmetric crypto everywhere (when combined with asymmetric crypto, restricted to public-key operation on the devices, to authenticate said other entities, and encipher to them); that solution is much simpler and faster on the device side.


Do PBKDF2 keys generated at a lower iteration count leak information? Assume the threat model here is that the server is not to be trusted and the client is trusted. A user registers for an account and the client chooses an iteration count of 50,000 to generate a 512 bit key for the user.

The key is then split in half: the first half is kept locally as the encryption key, and the second half is sent to the server as the user's "password".

key = pbkdf2(password: inputted_password, salt: some_salt, cost: 50000, size: 512)
encryption_key = key.first_half
server_password = key.second_half

server_password is sent to the server to authenticate.

Assume now that on some subsequent login session, the client is tricked by some irrelevant means into computing server_password using a lower iteration count of 3,000 instead of the real value of 50,000.

So the client is tricked into using a lower cost:

key = pbkdf2(password: inputted_password, salt: some_salt, cost: 3000, size: 512)
server_password = key.second_half

and this server_password is sent to the server.

My question is, does this "weaker" derived password leak any information to the server on what the nature of the user's original inputted password is?

Knowledge of server_password computed with 3,000 iterations instead of 50,000 makes it over 16 times faster to brute-force inputted_password and find encryption_key than was otherwise possible.

server_password can take much more values ($2^{256}$) than inputted_password can be tested, and PBKDF2 behaves like a random function, thus the first inputted_password found matching (if any) is the true one with overwhelming certainty.

Having found inputted_password, the adversary computes encryption_key by applying the same relatively low cost technique that generated it in the first place. That also allows to check that inputted_password is right (that is, the user did not misskey while s/he was tricked to use a lower iteration count; but even if that was, that could be worked around by trying small variations).


How is n-bit security calculated with nested encryption? What will the total $n$-bit security be if I encrypt a message with a 128-bit XOR cipher and then take that ciphertext and encrypt it with a 128-bit key.

Is the total security level now 256?

One definition on n-bit security said;

  n-bit security means that the attacker would have to perform $2^n$
  operations to break it

But say you are brute forcing then is this $n$ the total amount of combinations or just the expected number of combinations?

This solution considers the cipher as AES with 128-bit key and the X-OR is the one-time pad.

A careful investigation will show that 128-bit XOR is not going to help.

$$c = F_{k_1,k_2}(p) = E_{k_1}(p\oplus k_2)$$

The Ciphertext-Only attack;

If you give only one ciphertext then there is no solution. Since the decryption of the given ciphertext with every possible key is a valid plaintext and we cannot distinguish. If we assume that it is in English or another language we can only reduce the key space.

The Known-Plaintext Attack

Now, assume that we have a plaintext-ciphertext pair with $k_1,k_2$. Now we can brute-force but this will be $2^{256}$. $$p = F^{-1}_{k_1,k_2}(c) = D_{k_1}(c) \oplus k_2$$ Since once we
decrypted we cannot determine the $k_2$, we have to search for it.
Now assume that we have more than one plaintext-ciphertext pairs encrypted with the same keys $k_1,k_2$.

Execute the key search only $k_1$ for both cyphertext simultaneously.
$$p_1 = F^{-1}_{k_1,k_2}(c_1) = D_{k_1}(c_1) \oplus k_2$$ $$p_2 = F^{-1}_{k_1,k_2}(c_2) = D_{k_1}(c_2) \oplus k_2$$

For every iteration check the if;
$$ p_1 \oplus  D_{k_1}(c_1) =  p_2 \oplus  D_{k_1}(c_2) $$
then we find the $k_1$ and $k_2$ where the $k_2$ is the $p_1 \oplus  D_{k_1}(c_1)$

The total complexity will be $\mathcal{O}(2 \cdot 2^{128}) = \mathcal{O}( 2^{129})$

The key-space is $2^{256}$ but the provided security is $2^{129}$


Why is triple-DES using three different keys vulnerable to a meet-in-the-middle-attack? Among other sources, this wikipedia entry states that triple DES using three seperate keys (k1, k2, k3) is vulnerable to meet-in-the-middle-attacks, while triple DES using only two keys (k1, k2, k1) is not.

Why is this attack possible if all the keys are different, but not if the first and the third are the same?

The main difference is that with two 56 bit keys the maximal security level is 112 bit, and thus an attack that has a cost of $2^{112}$ operations is no attack, whereas for three 56 bit keys the maximal security level is 168 bits, and an attack that has a cost of $2^{112}$ operations counts as an attack.

This means that two-key 3DES is still a bit weaker than three-key 3DES, but not as much as we'd expect of an ideal 168 bit cipher.

With meet-in-the middle the cipher gets split into two halves, which are attacked separately. The cost of the attack is the sum of the attacks on the two halves, which is dominated by the more expensive half. So meet-in-the-middle is possible if you can split the cipher in a way that the more expensive half is cheaper to attack than guessing the whole key. (Disregarding memory use)

With two keys, one half has (k1,k2) and the other k1. Attacking the first half costs $2^{112}$ operations, attacking the second half costs $2^{56}$ operations. For a total of $~2^{112}$ operations.

With three keys, one half has (k1,k2) and the other k3. Attacking the first half costs $2^{112}$ operations, attacking the second half costs $2^{56}$ operations. For a total of $2^{112} + 2^{56} \approx 2^{112}$ operations.

So meet-in-the-middle gives us an attack with $2^{112}$ operations against either of them, but it's only better than brute-force when using three keys.


After Google's breakthrough: When will quantum computers break today's encryption? Google announced a breakthrough on the way to building usable and useful quantum computers.

Since I'm not a cryptographer, I wanted to ask when quantum computers will be able to break the crypto algorithms used today and whether this breakthrough has significantly changed the predictions.

Also, when will good post-quantum crypto libraries be available so that programmers can slowly begin replacing currently used crypto with post-quantum cryptography or go with a hybrid solution?

Since I'm not a cryptographer, I wanted to ask when quantum computers will be able to break the crypto algorithms used today and whether this breakthrough has significantly changed the predictions.

No, despite being on the front page of Nature, Google's result has no impact on cryptography for the foreseeable future.

The news about the (rather regrettable) term ‘quantum supremacy’ means that Google claims to have demonstrated ‘solving’ some problem on a quantum computer faster than anyone has been able to solve that problem on a classical computer.  In one sense, this is a remarkable achievement, because nobody had been able to do it before.  In another sense, it is the tiniest achievement imaginable: after decades of research, they found a problem, among all possible computational problems one might imagine whether or not solving it has any utility whatsoever, that they were able to demonstrate a quantum computer is better at than a classical computer.  (Maybe ‘quantum non-uselessness’ would be a better term than ‘quantum supremacy’, or perhaps ‘quantum non-futility’ since the problem they found is not terribly useful itself.)

The ‘problem’, in this case, is, given a random quantum circuit of about 50 qubits chosen by a challenger, to apply it on an all-zero initial state, and measure the result in the $\{0,1\}$ basis.  A choice of quantum circuit gives rise to a probability distribution on the outputs of this procedure—run the circuit on all zero inputs, measure the result in the $\{0,1\}$ basis—and nobody has shown a way to sample from this distribution as efficiently on a classical computer.  The results are then verified by statistical tests computed using classical simulation with about $2^{50}$ computations (which puts a bit of a damper on the prospect of verifying results like these on, say, 100-qubit circuits).

What Google has not demonstrated is anything that is useful for running quantum circuits like Grover's algorithm or Shor's algorithm, which requires substantially larger numbers of qubits and error correction at a scale we're nowhere near.  For more details, see Scott Aaronson's Supreme Quantum Supremacy FAQ.

To the best of my knowledge, no quantum computer has ever factored a number larger than 21 using Shor's algorithm, and there's no reason to suspect that other quantum factoring methods will meaningfully scale; see fgrieu's past answer on quantum factoring records (which I hope he will keep updated if the literature changes so I don't have to!).  Scott Aaronson estimates that if configured to run Shor's algorithm, Google's quantum computer could maybe manage factoring a number ‘up to the hundreds, depending on how much precompilation and other classical trickery was allowed’

  Also, when will good post-quantum crypto libraries be available so that programmers can slowly begin replacing currently used crypto with post-quantum cryptography or go with a hybrid solution?

Symmetric-key cryptography is not seriously threatened by quantum computers as long as you already meet a classical 128-bit security level by using ≫128-bit keys like 256-bit keys, which you're already doing, right?

There is an ongoing competition, NIST PQC, to settle on candidates for standardization of post-quantum public-key cryptography—encryption, key agreement, and signatures.  Aside from the NIST PQC candidates' reference implementations, available via the NIST PQC web site and in SUPERCOP, there are also some prototype libraries of post-quantum cryptography candidates, such as liboqs (open quantum safe), and experiments in deployment in protocols such as SSH and TLS.


Diffie hellman small shared secret Is there a way to prevent the shared secret to be a small value (eg 4) to avoid easily succeeding brute force attacks?

In $g^a \bmod p$, I understand that choosing $p$ not a multiple of $g^a$ is a first step.
But other than that, are there fast ways to achieve that goal?

Thanks

$p$ is a prime number and $g^a\bmod p$ will fall between $[1, p-1]$, so $p$ will never be a multiple of $g^a \bmod p$ unless $g^a= 1\bmod p$.
In Diffie Hellman, the secret exponents $a,b$ are chosen uniformly and randomly from $[1,q-1]$, where $q$ is a very large number. The probability that $Pr[g^{ab} = 4]$ or more generally $Pr[g^{ab} = x]$ for any $x$ in the group is negligible. This implies that for any integer $y=poly(n)$ where $n$ is the security parameter and $poly(\cdot)$ is any polynomial, $Pr[g^{ab} \le y]$ is negligible as well. So you don't need to worry about the key being a small value.


Matyas–Meyer–Oseas for super-fast single-block hash function Is it basically safe and correct to use the Matyas–Meyer–Oseas construction to turn a fast block cipher like AES into a really fast single block hash function?

By single block hash function I mean one that hashes, say, 128 bits of input and produces 128 bits of output. I don't need variable or larger message sizes and if I did I'd use SHA-2, SHA-3, etc., but those are a lot slower for really short fixed length messages. Benchmarks show that this AES construction is more than 10X as fast for hashing single block length messages on a machine with AES-NI CPU extensions.

If I'm understanding Matyas–Meyer–Oseas, the hash function would consist of AES initialized with a static predefined key and then used to encrypt a single block of input ("ECB" mode). The result of encryption would then be XORed with the original block to produce an output hash. Further initialization of the cipher with subsequent blocks wouldn't be done since you're only hashing messages whose size is equal to the block size.

If you're curious the application would be Winternitz one-time signatures. Winternitz signatures involve a whole lot of iterative hashing of single block size messages. Preimage resistance is important so a good hash function is needed but for compact signatures you want to increase the height of the "columns" in the signature.

Is it basically safe and correct to use the Matyas–Meyer–Oseas construction to turn a fast block cipher like AES into a really fast single block hash function?

Mostly, yes.  It is one standard approach to convert a permutation into a one-way function (at fairly small expense).  It does have some odd properties (e.g. it's easy to find the fixed point, that is, the block that hashes to itself), but those are typically not a concern.

  If you're curious the application would be Winternitz one-time signatures.

That brings up some concerns.  For one, Winternitz one-time signatures consist of a series of $H(x)$ values, and you can forge if you can find any of the $x$ values.  You are using the exact same $H$ function for each iteration; what an attacker can do is compile the list of $H(x)$ values he's looking for, and compute $H(y)$ for various values of $y$; if it happens to match any of his target $H(x)$ values, he wins.  For example, if your signature consists of 34 Winternitz chains of length 255 each (that's 256 bits, plus checksum), then there are an expected 4000+ hashes that are potential targets [1]; that cuts your security by 12 bits.  This can be mitigated somewhat by using different AES keys for the different chains, but that's not free, and it only reduces the concern.

The existing proposals for doing Winternitz, such as XMSS or LMS, get around this by stirring in a different value for each Winternitz iteration (and so each $H$ invocation is distinct), and hence such multicollision attacks do not apply.

The other objection depends on why you're using a OTS (and not a more standard signature algorithm, such as RSA or E[Cd]DSA).  One potential reason is for Quantum Resistance; for that, 128 bits of hash output don't cut it.  Now, there are other potential reasons (e.g. your signer or your verifier has constrained resources), and so this objection might not apply.

[1]: Note: not only the hash that appear in the signature are potential targets, but any hash latter in the chain as well.


RSA Key Generation Parameters - public exponent, certainty, string-to-key count I want to know what values are appropriate for the public exponent and certainty when generating an RSA Key (for example using Bouncy Castle RSAKeyGenerationParameters function).

What is the significance of the the string to key count (s2kcount) which appears to be optional input for the BcPBESecretKeyEncryptorBuilder bouncy castle function?

Is there an authoritative source that has a simple and answer to what to enter for the public exponent, certainty and string to key count? I have checked the RFC 4880 and other posts but have been unable to understand them to work this out.

Short answer: public exponent $65537$, certainty $5$. Terms and Conditions May Apply.

I have no clues about string to key count.

Whenever one wants to know " what values are appropriate ", there's the problem of defining appropriate: is there some normative context, e.g. FIPS 186-4? I'll assume that reference.

This, and all standards I know, agree that public exponent can be $65537=2^{16}+1$, and that's a choice that one will regret only on the grounds of performance of the public-key function (used for encryption and signature verification, not decryption or signature generation). A few standards allow $3$ which seems safe with a padding scheme randomizing the message, and can improve said performance by a factor like 8.

Answering the BouncyCastle-and-Java-specific part of the question (which is largely off-topic) would require the effort of ensuring that certainty is actually used as a number of Miller-Rabin primality tests with random base, and for random primes half the key's modulus size. I have no true assurance this holds, and assume it blindly.

FIPS 186-4 only allows $1024$, $2048$, and $3072$-bit public modulus, and requires using random $p$ with auxiliary conditions on the factorization of $p-1$ and $p+1$ at the $1024$-bit level, without stating a rationale for when the auxiliary conditions are required. Some think these are pointless, other including me believe they make some sense when generating extremely many keys, in order to repel down to entirely hopeless levels the possibility that methods derived from Pollard's $p-1$ can factor one of the many moduli with better odds than general methods can factor a single modulus.

Whatever the reason, with the assumption that BouncyCastle uses random primes, FIPS 186-4 leaves us with the only applicable generation method that of appendix B.3.3, at step 4.5.1 of which we are told to " test $p$ for primality as specified in Appendix C.3, using an appropriate value from Table C-2 or C-3 in Appendix C.3 as the number of iterations. ", with a rationale given for these in appendix F.3, telling us we should use table C-2 if we want residual odds of having a composite matching the standard-estimated security level of the key, or table C-3 for $2^{-100}$ odds.

Here are these tables; what interests us for certainty is the values given for " $p$ and $q$ " (which size is, we assume, half the key's modulus size). For example, the bottom entry in the first table tells us that certainty of $4$ is enough to generate each of the two $1536$-bit prime required for $3072$-bit RSA key and odds of generating a composite less than $2^{-128}$. Higher values further reduce the bound for these odds (which is mostly pointless), and make key generation slower (but less than proportionally, so using $4$ instead of $5$ only gives a moderate gain).

Appendix F.1 in FIPS 186-4 gives the method used to compute these tables, and can be used for reduced certainty (thus somewhat faster key generation) for keys larger than $3072$-bit. Actual odds of choosing a composite are believed to be significantly lower than given by theses tables and method.

Note: Nothing in this answer shall be understood as suggesting that generating RSA keys using BouncyCastle with certainty of $5$ may be FIPS 186-4 conformant.


How does Poly1305 in the NaCl library calculate a MAC? I've been reading about Poly1305 as implemented in the NaCl library, more specifically I've been referring to this Java implementation of NaCl.  My understanding of XSalsa20Poly1305 (in this implementation, at least) is that it prepends 32 zero-bytes to the clear-text, encrypts with XSalsa20 as per normal, uses the 32 encrypted zero-bytes as a the key for calculating a 16-byte Poly1305 MAC, and then discards the encrypted zero-bytes.  Do I understand this correctly?  Is this the standard way that Poly1305 is used?

I don't know if this is the standard way, but I do know that poly1305 is a single-use-only MAC function. You can never use the same poly1305 key twice for different messages or an attacker could forge MACs, apparently. So this sounds like an easy, safe, and computationally inexpensive way to use the encryption cipher you're going to use anyway to generate a unique strongly-randomized poly1305 key for each message.


decrypting el gamal encrypted messages in regards to k being used i am trying to understand the differences of using k in the following scenarios to better understand the protocol and most importantly the consequences of using such k.

so i wonder, some user, call him A sends two messages to B using El gamal. some user C, is not happy he's not invited, so he listens and gets those two messages. he works really hard and gets the decryption of the first message sent. can he also the second in those cases:

first case: A sends two messages E(m) and E(2m), but uses a different random k each time. i think she should be worried, but the second message is still safe.

second case: A sends two messages E(m) and E(2m), but uses the same random k for both messages. however, C doesn't know that she didn't change this random value.

could you please elaborate on the safety regarding those two cases? i am pretty sure in the second case the message is not so confident and probably decrypted because he obtained a decryption of the first message, and same k was used twice, so he just needs to filter the message to make sense.

would really appreciate if you could give a mathematical explanation to help me understand the material better.

A sends two messages E(m) and E(2m), but uses a different random k each time. i think she should be worried, but the second message is still safe.

We needn't be worried at all (unless we're concerned about the feasibility of the attack that recovered the first message).  If a decryption of one message allows you to break an unrelated message, then El Gamal itself is broken.  That is, if we have a magic box (called an Oracle in crypto-speak) that, given a public key, an encrypted message with its decryption, and a second encrypted message, and that magic box is able to produce the decryption of that second message, then we can break El Gamal.

Consider this: the attacker (who has such a magic box) gets an encrypted message C to B, which he wants to decrypt. Here's what the attacker can do: he generates a second message, and then encrypt that with B's public key.  Then, he has all the necessary inputs to the magic box, and the magic box will produce the plaintext of the C.  We don't believe that there's such a feasible way to decrypt encrypted messages with just the public key, and so we don't believe there's any such magic box.

  A sends two messages E(m) and E(2m), but uses the same random k for both messages. however, C doesn't know that she didn't change this random value.

Actually, C can easily see that the same $k$ value was used; part of the ciphertexts is the value $G^k \bmod p$; because that value depends only of $k$ (and the group parameters $G, p$), that value will be the same in both ciphertexts.

In addition, assuming that the two messages were to the same public key, if he knows one message, he can easily recover the other.

That's because the other parts of the two ciphertexts are $H^k \cdot M \bmod p$ and $H^k \cdot M' \bmod p$ (where $k$ is the shared $k$ value, and $M, M'$ are the two messages).  If he divides the two (modulo $p$, the operation of performing modular division is considerably different than division in the reals), and multiply the message $M$ he knows, he gets $M \times (H^k \cdot M') / (H^k \cdot M) \bmod p = M \cdot (M' / M) \bmod p = M'$


Public-Key Deterministic Encryption : Why does not provide perfect security? I've got a question about an assignment . The question is "Why a Public-Key Deterministic Encryption Algorithm does not provide perfect security ?" . I suppose it means according to Shannon .

Any help could be awesome!

Deterministic encryption means that if the same plaintext is encrypted twice, it results in the same ciphertext. This is intrinsically a breach of security.

“Absolute security” is not a technical term — but deterministic encryption breaks many definitions of security, including perfect security. If two ciphertexts are identical, it reveals the fact that the plaintexts are identical — and identical plaintexts lead to identical ciphertexts.

This is particularly bad in the presence of an encryption oracle: if the attacker can submit plaintexts for encryption, then the attacker can verify guesses about the plaintext corresponding to a ciphertext.

This is why most encryption algorithms (for example RSA PKCS1 v1.5 with salt, RSA OAEP, block cipher modes for encryption or authenticated encryption such as CBC, CTR, OCB, CCM, EAX, GCM, …) include some form of unique input to the encryption of each message (typically random, though whether more than unicity is important depends on the mode): salt, counter or IV.


What will be the MAC size of AES CBC-MAC if there are suppose 10 blocks in the AES CBC-MAC? What will be the mac size of AES CBC-MAC if there are suppose 10 blocks in the AES CBC-MAC?
Will it always be 128 bits MAC size for no matter how many numbers of blocks?

Yes, the CBC-MAC algorithm simply issues the last block of CBC mode as authentication tag. For AES this will always be 128 bit as that is the block size of AES (which is independent of the key size used).
The authentication tag is sometimes shortened to fewer bits (taken from the left hand side) for reasons of efficiency. This is however independent of the input size. $Tlen$, the size of the tag, is a security / configuration parameter of most MAC algorithms and authenticated modes of encryption such as CCM. $Tlen$ is commonly larger than 64 bits (smaller sizes will really influence security), a multiple of 8 bits (i.e. a certain number of bytes) and of course smaller than or equal to the output size of the algorithm that produces it.
Generally a protocol specifies the authentication tag size(s) that should be used. Generally the security in bits changes linearly with the authentication tag size for cipher based algorithms such as CBC-MAC. Other (more efficient) algorithms such as GMAC used in GCM however will degrade security faster (!).
Note that CBC-MAC is not AES CMAC, which should be used for dynamically sized messages.


Quantum vs. regular computing time to break ECC? How long exactly would it take for a regular computer to crack an elliptic curve public/private key via bruteforce, vs. a quantum computer using Shor's algorithm with a couple thousand qubits?  Can anyone reference me a source?

I'm assuming the digital computer will take thousands of years, but how long exactly is the polynomial time achieved by theoretical quantum computers?

It's hard to answer given that there is no quantum computer to perform benchmark on. However, let us assume a quantum computer which would perform quantum operations as efficiently as our current standard computer can perform classical operations (this might be a bit unrealistic but it's hard to come out with realistic assumptions regarding quantum computing given the state of advancement of this research field). The complexity of Shor's algorithm being $O(\log^2 n \log \log n \log \log \log n)$ according to Wikipedia, one can observe that this is better than the complexity of the best known classical algorithms for performing the multiplication of two $\log n \times \log n$ matrices. A quick search over some papers such as this one indicates that an optimized implementation of matrix multiplication of size $1024\times 1024$ can take less than a second, hence it does not seem unreasonable to assume that if a quantum computer was executing an optimized implementation of Shor's algorithm, factorization of a 2048 bit integer would take very little time - say, less than a few minuts.

For a regular computer performing a discrete logarithm over an elliptic curve is not done with brute force as you suggest, but using the Rho-Pollard algorithm, whose complexity is $O(\sqrt{p})$, where $p$ is the order of the curve. Still, executing this algorithm on well-chosen curves of size higher than $256$ bits is completely impractical.


XOR with constant key in CBC mode I have a hypothetical encryption scheme where somebody uses the one-time pad in CBC mode. That is, the block cipher is $E(k, m) :=k⊕m$, and that block cipher is used in CBC mode.

Now, I am assuming that a message $m=m_1||m_2||m_3||m_4$ is used for encryption.

How to compute $m_3⊕m_4$ from the resulting ciphertext (without using the key)?

Also: using this, how can I prove that it is IND_CPA insecure?

Remark: in One Time Pad the pad is used once, thus this is not OTP, since here $k$ is reused.

Hint for part 1: Write the relations between $k$, the message blocks $m_i$, the ciphertext blocks $\small C_i$ with the convention $\small\text{IV}=\small C_0$. Then, find equations that allow computing the desired $m_3⊕m_4$ from known quantities.

Hint for part 2, textbook variant: What is the definition that a cipher is not IND-CPA secure? Exhibit whatever that asks.

Hint for part 2, shortcut variant: IND-CPA implies that, for random plaintext, nothing can be learned about the plaintext given the ciphertext.


AES CBC encoding of decomposable OAuth2 tokens We're building a stateless RESTful API that relies on the content of OAuth2 tokens to identify users and what they have access to. Users authenticate with other means and are given a token, which they then use to authenticate API requests for an hour or so till it expires.

Since we want it to be stateless, we can't use random tokens with a lookup table. The token basically consists of username + start timestamp + end timestamp. (The token is considered valid if it has a valid user and the current time is between the start and end timestamps.) We encrypt the token before sending it to the user and decrypt it each time we get it back in a request.

If we naively encrypt the token with AES in ECB mode, the ciphertexts for a given user's tokens end up very similar to one another, because the usernames encrypt to the same ciphertext every time, and I assume somebody who knew what they were doing could XOR a few tokens together and recover the key fairly easily.

If we encrypt them in CBC mode instead -- with a fixed IV, so we can decrypt them later -- I assume the attack is a little harder (maybe a lot harder? maybe not harder at all?), but the ciphertexts still end up very similar.

What we're currently doing to get around this is reverse the token (bytewise) before encrypting in CBC mode, so the highest-entropy bytes get encrypted first and feed into the rest of the chain, and there's no obvious similarity between ciphertexts, and at least we don't look stupid. But, as they say, anyone can design a cryptosystem they themselves can't break.

Questions, then:

Is this actually doing any good?
Is there a known best practice we should be following instead?
If there isn't a known best practice, are there any obvious improvements?

(Note: All of this is happening over SSL so we're not particularly worried about man-in-the-middle attacks etc. But we don't want to encourage any otherwise authorized users to try to forge tokens, either.)

It probably is doing some good, although there's probably

a simple attack, depending on how long your fields are.

You should use a MAC or authenticated encryption, depending on whether or not you

want to keep $\:$ username + start timestamp + end timestamp $\:$ confidential from someone

who gets access to a user's computer while that computer has a token from your site.


128 bit AES CBC bit flipping on second block I have a 128 bit AES cipher in CBC Mode with the IV prepended to the message. I am aware of the security issues here, but that is exactly the point of my example. I would like to change the plain text message via bit-flipping, which I have partially implemented in the example below:

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Random import get_random_bytes

key = b'WOAH, SO SECRET!'
block_size = 16 # in bytes (128 bit)

def encrypt_data(data):
    iv = get_random_bytes(block_size)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    enc = cipher.encrypt(pad(data, block_size, style='pkcs7'))
    return iv + enc

def decrypt_data(data):
    iv = data[:block_size]
    cipher = AES.new(key, AES.MODE_CBC, iv)
    padded_params = cipher.decrypt(data[block_size:])
    return unpad(padded_params, block_size, style='pkcs7')

# 128 bit blocks for better visualization
plain = b'Hello everybody!' \
        b' This is a very ' \
        b'cool message,wow'

wanted = b'THIS CAN CHANGE!' \
         b' This is a very ' \
         b'cool message,wow'

cipher_text = bytearray(encrypt_data(plain))

for block in range(len(plain)//block_size):
        for i in range(block_size):
                block_idx = (block*block_size)+i
                xor_byte = plain[block_idx] ^ wanted[block_idx]

                cipher_text[block_idx] ^= xor_byte

result = decrypt_data(bytes(cipher_text))
print(result)

Above code outputs:

b'THIS CAN CHANGE! This is a very cool message,wow'

Which is exactly what I want!

However, I only ever managed to change the first block sucessfully, by changing the preceding block of the cipher message (in this case IV, which does not affect the rest of the message). If I modify my example with a wanted message like that:

wanted = b'Hello everybody!' \
         b'THIS CAN CHANGE ' \
         b'cool message,wow'

My code outputs:

b'g\x114\xb4\xc4\xd6\xd6\x16\xcf\x88\x87\x99\xea@\xe4\x11THIS CAN CHANGE cool message,wow'

I understand, that this happens due to the fact of using CBC mode and the impact of blocks on each other as described here. But what exactly am I missing here? How can I change my message to the desired output after decryption?

b'Hello everybody!THIS CAN CHANGE cool message,wow'

I'd appreciate any push in the right direction.

There is only one way I see how to avoid having this block of garbage in you plaintext after CBC bit flipping attack, but it requires to be able to see the result of the decryption and to know the whole plaintext you are attacking, which may not be the case in most practical scenarios.

Say you want to alter the third block of plaintext, P3:

Do your CBC bit flipping attack on P3 by modifying C2, the normal way
get the modified plaintext. P2 should be garbage
now modify C1 in order to “repair” P2, that is, C1 = (the garbage you got) XOR (the original P2)
this is going to mess up P1, so you now you modify the IV to “repair” P1


Why is this function pseudo random (PRF)? First, I want to clarify this is not homework. I encountered this question (here How can I prove that a function F isn't a pseudo random function?) while studying for a test coming soon.

$F'_k(x) = F_k(0||x) || F_k(1||x)$
$F'_k(x) = F_k(0||x) || F_k(x||1)$

(Here $||$ representing concatenation, $F$ is a PRF).

I know that the second function is not a PRF and I came up with an adversary for it by myself.

As for the first fuction, I read comments saying it is a PRF, but I couldn't find a way to formally prove this.
I know the method of proving these kinds of questions.

I should assume by contradiction that $F'_K$ is not a PRF, namely it has an adversary $D'$ that distinguishes between $F'_K$ and a random function $f'$ with non-negligible probability.  Using $D'$, I should construct an adversary $D$ that distinguishes between $F_K$ and a random function $f$ with non-negligible probability - which is a contradiction.

I thought of the following reduction for constructing $D$:

Given an input $x$, and a oracle access $O$ (for $F_K$), $D$ runs $D'$ on $O(0||x)||O(1||x)$. Then, $D$ answers what $D'$ answers.

If $O=F_k$ , then $D$'s probability of distinguishing is equal to $D'$'s.
If $O=f$ (the random function) - Well, here I'm stuck.

This is not exactly the way you're going about it, but I find it an easier way to deal with this kind of construction in general. First we switch to an information-theoretic setting, then go back to the concrete construction. This is very similar to proving the security of counter mode encryption.

First, we replace $F_k$ by a real random function $G$. Every new input to $G$ results in a uniformly random output $G(x) \in \{0,1\}^{n}$. Now we have the corresponding
$$
G'(x) = G(0\|x)\|G(1\|x)\,.
$$
Since every call to $F_k'$ gives you two free calls to $F_k$, we have
$$
\mathbf{Adv}^{\mathrm{prf}}_{F_k'}(D) \le \mathbf{Adv}^{\mathrm{prf}}_{F_k}(D') + |\mathbf{Pr}[D(G') = 1] - \mathbf{Pr}[D(\$) = 1]| \,,
$$
for a distinguisher $D'$ that performs at most $2q$ queries, by the triangle inequality (the first term being $\Delta_D(F_k', G')$, and the second being $\Delta_D(G', \$)$. $\$$ represents the ideal random function).

Our goal now is to distinguish $G'$ from a uniformly random function from $\{0,1\}^{n-1}$ to $\{0,1\}^{2n}$, to determine the second term of the above inequality. Notice that the inputs to $G$ are properly domain-separated: there are never any collisions between $0\|x$ and $1\|x$ for any distinct $x$.

More concretely, take any set of (distinct) queries $((x_1, y_1), (x_2, y_2), \dots, (x_q, y_q))$, where $y_i = \mathcal{O}(x_i)$. The probability that $G'(x_1) = y_1$, $G'(x_2) = y_2$, $\dots$, $G'(x_q) = y_q$ is $\left(\frac{1}{2^{n}}\frac{1}{2^{n}}\right)^q = 2^{-2nq}$. The probability for a random function is also $2^{-2nq}$, as each output has independent probability $2^{-2n}$.

The definition of advantage is
$$
|\mathbf{Pr}[D(F) = 1] - \mathbf{Pr}[D(\$) = 1]|\,,
$$
for any distinguisher $D$. From this we conclude that the advantage of any attacker against $G'$ is $0$, since it has exactly the same probability distribution as the random function. So we conclude that
$$
\mathbf{Adv}^{\mathrm{prf}}_{F_k'}(D) \le \mathbf{Adv}^{\mathrm{prf}}_{F_k}(D') + 0 \,.
$$


Cannot understand Block Cipher example I learned modern block cipher and saw this example.

How many padding bits must be added to a message of 100 characters if
8-bit ASCII is used for encoding and the block cipher accepts blocks
of 64 bits?

There was a solution, but I totally didn't understand.

Solution
Encoding 100 characters using 8-bit ASCII results in an 800-bit
message. The plaintext must be divisible by 64. If |M| and |Pad| are
the length of the message and the lengeth of the padding.
|M| + |Pad| = 0 mod 64 --> |Pad| = - 800 mod 64 --> 32 mod 64

What I'm curious are following questions..

Why encoding 8 characters using 8-bit ASCII results in 800-bit message?
What padding means?
What last sentence means? (difficult to understand)

Why encoding 8 characters using 8-bit ASCII results in 800-bit message?

That is not correct, 8 ASCII characters is 8-bytes times 8-bits per byte which is 64-bits.

The question seems to be: Encoding 100 characters using 8-bit ASCII results in an 800-bit message.

That is 100 ASCII characters is 100-bytes times 8-bits per byte is 800-bits.
What padding means?
Since block based encryption with a block mode such as ECB or CBC means that the input must a  multiple of the block size because the data is processed one block at a time and partial blocks can not be processed.
What last sentence means? (difficult to understand)
Basically answered above.
See Padding (cryptography)
and especially: PKCS#5.

Note: ASCII is one 8-bit byte per character—only.


Why should the primes used in RSA be distinct? The two primes $p$ and $q$ part of the public key need to be distinct.
What's the reason for them to be distinct? Is it because factorization of $p^2$ where $p$ is a prime is relatively easier, or is there some other reason?

The main reason why the prime factors $p$ and $q$ of RSA modulus $N$ must be distinct is stated in the question: if they are equal, given $N$ (which by definition is public in RSA), it is trivial to find $p=q=\sqrt N$.

A secondary reason is that with $p=q$, a few messages $x\in\{0\dots N-1\}$ can't be reliably deciphered from $x^e\bmod N$: all those $x$ such that $x\equiv0\pmod p$ encipher to $x^e\bmod N\;=\;0$. This would not be so much of a problem, because those $x$ are rare when $p$ is large, and in practice (when proper padding is used) $x$ is substantially random over $\{0\dots N-1\}$, thus the problematic $x$ are used with negligible probability.

Update: as pointed by Ricky Demer, there's an additional reason: with $p=q$, the private exponent $d$ would need to be computed with $d\equiv e^{-1}\pmod{p\cdot(p-1)}$ rather than the usual $d\equiv e^{-1}\pmod{\operatorname{lcm}(p-1,q-1)}$

If $p$ and $q$ are suitably large and randomly chosen, they are distinct with overwhelming probability, thus the need that they are distinct is often not specified without invalidating quantitative theoretical results. In an implementation, if an explicit test is made, it can only hope to ever catch some gross malfunction of the key generator; same for customary tests that $p$ and $q$ are different enough, like FIPS 186's prescription that $|p-q|>2^{\lfloor\log_2(N)\rfloor/2-100}$ .


Some simple questions about tweakable ciphers I have read a few papers on tweakable ciphers (didn't understand them well, though) and looked at many of the questions and answers on this exchange: What is a tweakable block cipher, Tweakable Block ciphers, Tweaking Even-Mansour Ciphers [video]. However, there are a few things I'd like cleared up.

Are the tweaks always just a string of bits? And are they usually shorter than the key?
It seems DES-X is a tweakable cipher where the tweaks are the pre- and post-whitening that use secret extra keys. Does this mean some tweaks are necessarily secret? The reason I am asking is that I got the impression from the papers I read that tweaks are always public.
In view of Q2, what other tweakable ciphers (if any) use secret tweaks or ones that may be secret if desired?
If a tweak is secret does this add strength to the cipher as well as variability?
If a tweak is appended to a key, does this mean to the session key or to each subkey? I am a little confused because I thought part of the idea of tweaks is that they are easier to change than producing new keys through a complex key schedule (for instance).
Perhaps this should be a separate question, but: the term permutation seems to mean two different things. 1) a bit-wise (say) permutation, i.e. excluding XORs, S-boxes, etc. and 2) a complete block cipher encryption that produces an apparently random permutation of the input, i.e. typically including XORs and substitutions, etc. In relevance to tweakable ciphers, when I look at some models I see the cipher is denoted by $E_n$ but when I look at models based on the Even-Mansour ciphers I see $P_n$. I assume the $E$ refers to an cipher that may include several operations (perms, s-boxes, etc. as for $DES$, $AES$, etc.) but the $P$ refers only to bit-wise permutations (or perhaps byte-wise). Is this assumption correct?

Much obliged to anyone who can help.

Suppose the tweakable cipher uses a secret key $k$ and a secret tweak $t$, then syntactically you can regard $K=(k, t)$ as the total secret key.  So, in this case, the 'tweakable cipher' is just an ordinary block cipher, with a longer key.  In order to get a notion different from the usual block cipher, you'll need the tweak to be non-secret.


Private key can't be traced (GPG)? I am very new to cryptography. I was reading about GPG/PGP Basics when a doubt arose:

As per my understanding, everyone knows the algorithm (from GPG) with which I generated my key pair. If I show my public key, will it be impossible to trace back my private key? Even after knowing both algorithm and public key?

This is actually a rather interesting question whose solution is obvious to all cryptographers, but I guess nobody cared yet to write it down.

After all, our computers that generate secret keys (not just GPG / RSA) are deterministic machines. These deterministic machines implement well-defined routines to generate keys of well-defined format which are later published and serve as an "image" of the function generating the keys. Note that this question can be extended to all ciphers, like good old symmetric encryption and message authentication codes because there you can verify your guess for the start value of the procedure just as easily.

Now for the two parts of your question as I see it:

The algorithm is deterministic and thus it should be possible to reproduce it
The algorithm is well-defined and thus it should be possible to work it backwards ("backtrack it")

To understand the specific case of GPG we need a brief overview of how the algorithm works:

Take a large random value and convert it to an integer
Test if the integer is prime (with high probability)
Repeat the first two steps until two primes were found
Multiply the primes together, this is (along with another constant) is your public key output
The primes now form the secret key (along with a "counter-part" to the above "constant")

As you can see, inverting the algorithm would imply actually factoring the public key modulus. However this is computationally impossible for classical computers for sufficiently large primes ($>2^{1000}$), so you can't backtrack the algorithm.

But how about guessing a starting value for the randomness and then trying all options out? Well, it turns out this doesn't work, because while you could try to guess the random values, each has $2^{128}$ or more possible values and as such you can't try them all out using a classical computer during a human life-span.

Wait, didn't we establish that computers are deterministic, so why is there more than one possible value!?
Computers are indeed deterministic, but the things they use and the things that use them aren't deterministic. Computers take that randomness and "compress it" into short byte strings, which are then used to derive the "large random values" I talked about. So, where does this randomness come from? It could be random keystrokes by the user, network timing, CPU scheduling times, HDD delays (which are created by the air in the HDD cases), mouse movement by the user and actual random number generators which are fed by physically random processes (similar to the Double-slit experiment and other quantum events).


IND-CCA2 post-quantum key exchange QUIC requires that servers reuse keys so that session resumption works.  That breaks many post-quantum key exchange systems.

I am looking for a post-quantum key exchange algorithm with the following properties:

Fast (Lattice-based)
IND-CCA2
The chosen key depends on randomness from both parties (this is important for many uses of channel binding).

NewHope is a key-exchange protocol based on the Ring-Learning-with-Errors (Ring-LWE) problem. NewHope512-CCA-KEM and NewHope1024-CCA-KEM are IND-CCA-secure key encapsulation mechanisms which target level 1 and level 5, respectively, (matching or exceeding the brute-force security of AES-128 and AES-256, respectively). Google is working on deploying post-quantum key-agreement in TLS by combining NewHope with an existing key-agreement (X25519)as the combination CECPQ1. Please find a GoLang implementation of NewHope in GitHub.


AES CBC mode is good for encrypting 15-20mb files and then sending it in parts? I want use CBC mode for sending and receiving files (avi, mp3, docx, jpeg) max up to 20mb. But also I want cut this file after encryption on sending site for example on 2mb size and send each file separately to receiver and on his site i will again join all 10 files together to one and then decrypt it.

Is CBC good mode for this? I have read some topics here (cryptography) that CBC is not good for sending only "part" of the file. But I don't know if this is also my case because: yes I am sending only parts of whole files but on the receiver site my code will wait until all parts are downloaded and then I will join all files together. After that I will encrypt whole 20mb file.

Is it OK to use CBC for this case? I am not trying to encrypt/decrypt only some parts of the file but always whole file after I join all sending parts correctly.

CBC can be used to make messages confidential even in transport security. After all, TLS often still uses CBC mode to encrypt the data frames. I'd say however that CBC is not the perfect mode for the job:

there are certain issues with using the last ciphertext block as IV for separate messages - so you would normally have to use the random number generator to generate a fresh IV and send it with the encrypted block of data;
you need to figure out if you want to use padding or not, CBC can only handle data that is precisely N times the block size, padding also introduces overhead;
CBC with a padding mode is vulnerable against padding oracle attacks, i.e. you should avoid communicating decryption errors to the sender now and in the future; if you do not do this then an attacker can decrypt your blocks and therefore your files.

For this kind of encryption counter (CTR) mode is much easier to get right. It doesn't require padding and you can simply keep counting for the next blocks. The only thing that is really a negative is that reusing a counter (initiated using the the nonce/IV) may completely destroy confidentiality. You can skip to an offset in the stream as a bonus.

If you also want protection against changes of the files you could use an authenticated mode of encryption such as GCM. In general authenticated modes use CTR mode under the hood. Of course using GCM and skipping together may be harder to get right.

Note that ciphertext size may be used to guess which files have been send. You could easily fingerprint collections of files by just monitoring the file sizes, if those file sizes are known in advance.

CBC makes this slightly more difficult as you don't know what part of the last ciphertext block contains plaintext / padding. Relying on such a small change for security doesn't seem to be a good idea though. But it is an advantage of CBC over CTR, even if it is a small one.


Converting EdDSA Keys to EC-KCDSA keys I'm trying to create BIP32 like key derivation for EKCDSA by riding over a  BIP32-EdDSA derivation

Can anyone tell me if there is a glaring problem with my conversion technique?

PrivateECKCDSA = First32Bytes(Hash512(PrivateEdDSA))
PublicECKCDSA = Convert_ED25519_to_Curve25519_public_key(PublicKeyEdDSA)

Can any buffer be considered an ECKCDSA private key? I know that because we are using curves and fields there might be some limitation (I'm really clueless about this).

Also can every EdDSA public key be converted into curve25519, or are some excluded?

If no named this conversion I'd like to call it the Yaffe Bender key conversion.

Can anyone tell me if there is a glaring problem with my conversion technique?

PrivateECKCDSA = First32Bytes(Hash512(PrivateEdDSA))
PublicECKCDSA = Convert_ED25519_to_Curve25519_public_key(PublicKeyEdDSA)

This conversion makes no sense.

There is no meaningful connection between what you have called PrivateECKCDSA and PublicECKCDSA, so they in no way constitute a key pair.
If by Curve25519 you mean X25519, the public key conversion also doesn't make sense because ECKCDSA needs a full point, not just an $x$ coordinate.
Why are you even doing ECKCDSA over Curve25519?  Are there any protocols that use this?

If you have to use ECKCDSA you most likely have to use a curve standardized by KISA, which is unlikely to have any relation to the curve edwards25519.
If you don't have to use ECKCDSA, why don't you just use Ed25519 signatures?

A note on nomenclature these days: Curve25519 means the Montgomery curve $y^2 = x^3 + 486662 x^2 + x$ over $\mathbb F_{2^{255} - 19}$, while X25519 means the Diffie–Hellman function of $x$-restricted scalar multiplication on Curve25519.  Edwards25519 means the twisted Edwards curve $-u^2 + v^2 = 1 - (121665/121666) u^2 v^2$ over $\mathbb F_{2^{255} - 19}$, while Ed25519 means the EdDSA instance with edwards25519, SHA-512, etc.

  Can any buffer be considered an ECKCDSA private key? I know that because we are using curves and fields there might be some limitation (I'm really clueless about this).

An ECKCDSA private key is a near-uniform random scalar modulo the order of the curve.  For a curve with a 256-bit order, like NIST P-256, you can generally use a uniform random 32-bit string as the private key.

  Also can every EdDSA public key be converted into curve25519, or are some excluded?

Can't meaningfully convert an Ed448 key to an X25519 key.  But if you restrict your question to converting Ed25519 keys to X25519 keys, then the answer is essentially yes: edwards25519 and Curve25519 are birationally equivalent with a map that extends to a group isomorphism, and to almost every Curve25519 public key there are two corresponding Ed25519 public keys.  However, the birational map has a handful of exceptional cases, like $u = 0$, $v = -1$, etc.  So be careful!

  If no named this conversion I'd like to call it the Yaffe Bender key conversion.

Who seeks eponymy, might learn humility!


Schnorr proof of group with unknown order (but the prover know the order) We assume that we have $n = pq$, where $p = 2p'+1$, $q = 2q'+1$, and all $p, q, p', q'$ are large primes. Pick $g' \gets_R Z_n^*$, and compute $g = (g')^2 \bmod n$. Then we have a generator $g$ for $QR_n$. The order of $g$ is $p'q'$.

Both prover and verifier are given $n$, $g$, and $h = g^x \bmod n$. The prover is given $p', q'$, and the witness $x$. Now the prover knows the order of $g$. Both parties start the Schnorr proof.

The prover picks $y \gets_R Z_{p'q'}$, computes $a = g^y \bmod n$, and sends $a$ to the verifier.
The verifier sends a random $e \gets_R \{1, \ldots, n/4\}$.
The prover sends $z = ex + y \bmod p'q'$ to the verifier.
The verifier accepts if $g^z \equiv h^ea \bmod n$.

It seems that this procedure works ok. But when I want to prove the special soundness and special HVZK, I was stuck.

For SHVZK, it seems that the simulator does not know $p'q'$, and thus it cannot perfectly simulate the interaction. A similar problem happens when I want to prove the special soundness. Given $z_1 = e_1 x + y$ and $z_2 = e_2 x + y$, I cannot compute the inverse of $e_1 -e_2$ to recover $x$ since I do not know $p'q'$.

I am wondering whether there is something wrong?

You are not wrong. This indeed does not work. The way out typically in these situations is to use a proof over the integers. There is quite a bit of work around zero knowledge over groups of unknown order. See Section 3.7 of this thesis by Geoffroy Couteau. Since he is active here, let's hope he weighs in.


Why is the IV passed in the clear when it can be easily encrypted? The initialization vector (IV) is exclusive or'd against the plain text before encryption for the first block sent in order to prevent an attacker from learning that duplicate message blocks are being sent.  This technique is often used with streaming modes like CBC.

I have researched some of the questions that were asked about whether it was safe to pass the IV in the clear.  The general consensus seems to be that the IV can be safely passed in the clear, but the IV should be random to prevent certain kinds of attacks.  Using a counter for the IV is also thought to be vulnerable as well and only randomly generated IVs should be used.  I don't really understand this since the reason stated for passing a random IV is that it can not be easily guessed.

In any case, my question is as follows:

It should be relatively easy to send the first block of a message encrypted, but without any IV processing.  This first block could contain the IV which would then be used for all remaining blocks of the message.  Since the IV in the encrypted message is random, there should never be any duplicate first blocks.  How come this is not being done and isn't it at least a little safer than sending the IV in the clear?

Depending on the mode of operation, transmitting the IV encrypted (with the same key as used for the rest of the process) can actually weaken security a lot.

For example, in the CFB and OFB modes, the IV is encrypted and the result XORed with the first block of the plaintext to produce the first block of ciphertext.  Thus, an adversary who knows the encrypted IV can trivially undo the XOR to recover the first block of plaintext!  The same is true for the CTR mode, if the IV/nonce is used directly as the initial counter value.

The CBC mode works differently, and does not break as catastrophically if you encrypt the IV before transmitting it.  However, as Henrick Hellström has pointed out, knowing the encrypted IV still lets an adversary figure out whether the first block of the plaintext consists of all zeros.


Can you use a dynamic key and data size for KMAC? I've asked before if some kind of canonical encoding should be used on the input parameters of SHA-3 before it could be used as replacement for HMAC.
However, if I read the current NIST specifications in NIST SP 800-185 correctly, there is no Keypack function defined. The Keypack function prefixed a key size to the key so that the key and message data are kept separate. Currently the key just seems to be zero-padded up to the next block boundary using the function bytepad(encode_string(K), 168) for KMAC128 and bytepad(encode_string(K), 136) for KMAC256.
Does that mean that there is no canonical encoding for key and data? Is it safe to use a dynamically sized key and data within KMAC so that bytepad(encode_string(K), 136) || X != bytepad(encode_string(K'), 136) || X' for K != K?

Yes, however it does take a deeper look into the standard.
KMAC128 is defined as:

newX = bytepad(encode_string(K), 168) || X || right_encode(L).
return cSHAKE128(newX, L, “KMAC”, S).

So there seem to be no encoding of the size of the key, which that there could be multiple K, M key message pairs that would result in an identical value of bytepad(encode_string(K), 168) || X (because A || BC = AB || C).
However if we take a look at the encode_string(S) function:

Return left_encode(len(S)) || S.

This means that the (bit) string encoding canonically encodes the key including the size of the key (len(S)). That means that any key with a different size will be encoded in such a way that the division between key K and message X is clear.
The canonical encoding is still present even though the encode_string has a more generic name compared to earlier KMAC drafts where it was called Keypack(K, l)  and took the length as explicit parameter.


AES vs other types of encryption such as Twofish I am kinda of confused about what are some major differences between AES, Twofish, and other types of common encryption algorithms.

Rijndael (aka AES) and Twofish were both candidates and finalists for the Advanced Encryption Standard contest, a three year selection process which yielded the selection of Rijndael as the standard.

Contest submissions were required to be block ciphers of block size 128 bits and support key sizes of 128,192 and 256 bits. Submissions were put through rounds of cryptanalysis and assessment by prominent members of the cryptographic community. NIST, the competition organiser, made the final decision that Rijndael would become the AES.

At a high level both AES and Twofish are 128 bit block ciphers supporting 128,192 and 256 bit key sizes. Both ciphers are (despite a small number of theoretical attacks) secure in the computational/pragmatic sense that nobody has yet found a way to break them. Both ciphers are based on heuristic constructions, meaning that we don't have a proof of security showing a reduction to some known hard problem, instead their security is based on the fact that nobody has broken them yet. Both ciphers satisfy the pseudorandom permutation (PRP) function model in that their output cannot be distinguished from a random permutation in the block size.

High-level differences between the ciphers are that AES and Twofish are based on a substitution-permutation network (SPN) and a Feistel-network respectiveley. These networks are applied in rounds where AES has 10,12 or 14 rounds depending on the key-size, Twofish always applies 16 rounds.