Pailler and Gentry - homomorphic encryption Paillier cryptosystem is a probabilistic asymmetric algorithm for public key cryptography. Doesn't homomorphic encryption schemes have regular effects on the plaintext, and does that mean Pailliers cryptosystem missing the nonce? What is that I am missing?

I am also trying to understand if there are a disadvantage of Gentry's fully homomorphic scheme in terms of security (e.g. besides that the scheme is homomorphic how would it stand next to AES for example). Note that I do not refer to its impractical use due to its many series of computations.

Can anyone shed some light on these things for me, or perhaps point me in a direction where I can find information about it (I have been looking around, and the actual paper Gentry wrote is quite difficult to grasp for me and Pailliers cryptosystem eludes me a bit in this aspect).

You seem to have some conceptual misunderstanding. A homomorphic property of an encryption scheme does not necessarily mean that it is deterministic.

There are examples like textbook RSA which has a multiplicatively homomorphic property (multiplying ciphertexts modulo the modulus gives you a ciphertext to the product of the two hidden plaintexts modulo the modulus), but is insecure due to its deterministic property, i.e., no IND-CPA security. Loosely speaking, you can test against given ciphertexts by trial encryptions using the respective public key with candidate plaintexts.

What is clearly true is that homomorphic encryption schemes can not be secure against adaptively chosen ciphertext attacks (IND-CCA2) as the homomorphism prevents this type of security. But everything below is possible. For instance, Paillier is secure against chosen plaintext attacks (IND-CPA), but is additively homomorphic.

Another (from the point of math) more simple example is additively homomorphic aka "exponential" ElGamal, which is simpler for illustration.

There you work in a cyclic group of prime order $q$, e.g. the order $q$ subgroup of $Z_p^*$ with $p$ being a safe prime, generated by $g$. This version of ElGamal is IND-CPA secure (and thus probabilistic) and works as follows: Let $y=g^x$ be the public key and $x\in Z_q^*$ be the private key. You encode a message $m\in Z_q^*$ as an element $g^m$. To encrypt this message $m$ you choose a random $k\in Z_q^*$ (the randomizer) and the ciphertext is $(g^k, g^m\cdot y^k)$ (note that decryption yields $g^m$ and you have to compute discrete logarithms to get back $m$ - so this is only attractive for small message spaces but this does nothing to the example here). It is easy to check that given two ciphertexts to $m$ and $m'$ and randomizers $k$ and $k'$ respectively and multiplying them componentwise gives you a ciphertext to $m+m' \bmod q$. Note that the resulting ciphertext is a ciphertext with respect to randomness  $k+k'  \pmod q$ and if both $k$ and $k'$ are random and hidden (which is the case) so is  $k+k'  \pmod q$. So this scheme is additively homomorphic but still probabilistic (IND-CPA). Same holds for Paillier and FHE schemes are usually also probabilistic - as it is the case for Gentrys first construction (I just used ElGamal as it is simpler to present).

Hope this helps - its hard to type such answers on a mobile :)


Randomness measure of a sequence over a finite set If $S$ is a finite set (such as outcomes of a dice). If I have a sequence $x_0 ... x_n$ of elements over $S$, how can I measure randomness quality of such a sequence as compared to measuring quality of random bits?

The simplest approach is the bias away from uniformity of the sequence, $\epsilon$. $P(x_n = \text{any member of S}) = \frac{1}{|S|} \pm \epsilon$. So a regular die has 6 possible outcomes and thus a cardinality of 6.  Therefore in the case of a perfectly fair die, $P(x_n = \text{any member of S}) = \frac{1}{6} + 0.$

The USA's NIST organisation aims for $\epsilon = 2^{-64}  $ when characterising a sequence as 'fully' random. And this leads to issues of mensuration as it's very difficult to generate and managed the amount of data needed for an accurate determination with such small bias.

We therefore resort to stochastic methods within acceptable bounds of certainty, like chi-square tests.  To that end, see How many rolls do I need to determine if my dice are fair? Cryptographic tests typically use a confidence level of 0.1%.


Question about decryption I have a question about decryption.

Let's say I have a bunch of files that are encrypted. Someone gains access to those files, and finds out that he already has one of them, unencrypted.

My question is, can he use that file to make a comparison with the encrypted version of the file to find the key, therefor be able to decrypt all the files?

One would certainly hope not; if he can, then we would consider the encryption method "broken".

One of the things we expect from any encryption method is the resistance to a "known plaintext attack" (of which your question is an example); that is, even if he is given a number of plaintext/ciphertext pairs, he still is unable to decrypt another ciphertext that is encrypted with the same key.

Actually, we go father than that; we also ask encryption methods to be resistant to "chosen plaintext attacks"; that is, even if the attacker can ask that messages of his choosing be encrypted (and he then gets the resulting ciphertext), he still is unable to decrypt a target ciphertext.


how secure is Twofish really? So I heard that Twofish is much more secure than AES, because it is not vulnerable to bruteforce and only supports 256 bit.
Also I heard that is not vulnerable to most side channel attacks.
And Twofish might be much more secure because there is no known attack to it, while in AES there is a known theoretical attack.
From what I have heard twofish is not the encryption standard because it is too slow, but has a much higher security index.
So are those claims true? Is twofish really more secure? Everybody says different things. Would it be the better choice for classified top secret data?

So I heard that Twofish is much more secure than AES, because it is not vulnerable to bruteforce and only supports 256 bit .

Neither AES nor Twofish is vulnerable to brute force attack on the key in practical scenarios. Both support key sizes of 128, 192, and 256 bits, which makes them equally resistant to brute force attack.

Also I heard that is not vulnerable to most side channel attacks .

Quoting wikipedia:

Twofish's distinctive features are the use of pre-computed key-dependent S-boxes...

The use of pre-computed tables can be vulnerable to side channel attack. The table(s) contents are key-dependent, so the situation is not exactly the same as it is for AES (where the table(s) contents are known by the adversary), but it's still a cause for concern.
Additionally, side channel attacks target the practical implementation, so the theoretical algorithm is not really inherently more or less secure in regards to side channel attacks (some are just easier to secure then others). There are still concerns such as Power Analysis, Acoustic Analysis, Rubber Hose Cryptanalysis, etc.

And Twofish might be much more secure because there is no known attack to it , while in AES there is a known theoretical attack .

There are theoretical attacks on Twofish. Wikipedia has a section on the side:

Best public cryptanalysis
Truncated differential cryptanalysis requiring roughly $2^{51}$ chosen plaintexts.
Impossible differential attack that breaks 6 rounds out of 16 of the 256-bit key version using $2^{256}$ steps.

So clearly there are attacks on Twofish. They do not constitute a practical break of the cipher; Neither do any of the cryptanalytic attacks on the theoretical AES algorithm (meaning: attacks that do not use side channel analysis).

From what I have heard twofish is not the encryption standard because it is too slow , but has a much higher security index .

This appears to be accurate (as you might know already...)

So are those claims true ? Is twofish really more secure ? Everybody says different things . Would it be the better choice for classified top secret data ?

AES-256 is standardized for use to protect the confidentiality of classified top secret data. Twofish is not. It is not really a choice for people who actually have classified top-secret data to protect: AES-256 is the answer.


Optimal same-base exponentiation? I've (finally) implemented the answer to this question in our library, which stated how to transform montgomery curves (and points) to weierstrass curves (and points).

Now, for scalar multiplication, we currently use our Weierstrass code, but want to replace it in the long run. Clearly the Montgomery ladder is the algorithm of choice when it comes to scalar multiplication on Montgomery / Edwards curves. However the ladder usually is given very simplified (always double and add but swap what is doubled and what is added based on the bit in question).

I'm asking for the best, side-channel resistant technique to implement scalar multiplication on Montgomery / Edwards curves.

Note:

Same-base pre-computation speed-ups are welcomed.
Advanced projective coordinate tricks (tripling and such) are welcomed as long as they don't break side-channel resistance.

My definition of the "best" technique: It should be as fast as possible and as side-channel resistant as possible (side-channel resistance has priority).

As you suggest, you can speedup the exponentiation using pre-computed values. However, you will face the following problems:

the table with the precomputed values can become rather large, and
the table lookup is in general not constant time.

An example of how these problems can be addressed can be found in the Ed25519 implementation of Bernstein et al.; details are discussed on page 13 of their paper. They use a Brickell exponentiation with a standard trick to reduce the size of the table by 50%, and they use constant-time table lookup (where all possible values are loaded from memory and then combined with logical operations).

Note that because the cost of constant time table lookup is proportional to the size of the table, it is not efficient to represent the exponent as a series of larger chunks (e.g. 16bit->65536 elements in the table). It is more efficient to represent the exponent as a series of smaller chunks (e.g. 4bit).


On The Next Bit Test I would like to know what $O(v(n))$ really means in detailed and simple words please.
I found it everywhere in the literature I am reviewing but I cannot find what the intuition of it (especially if it means the Big O Notation, then what it has to do with the Probability here; also what is $v$, it is never defined except in another paper as a constant -but maybe not related directly to v in this formula-).

Many Thanks.
References 1 , 2

But this notation is defined (informally) in the first paper.

The notation $O(\nu(n))$ is used for any
function, $f(n)$, that vanishes faster than the inverse
of any polynomial, that is for every polynomial, $\mathrm{poly}
(n)$, and $n$ large enough, $f(n) \leq 1/\mathrm{poly}(n)$

Therefore, what it means is no probabilistic polynomial time (PPT) algorithm $A$ can guess the next bit at inverse polynomially decreasing error rate.
Given any PPT algorithm $A$ this error probability decays super-polynomially, for example at a rate $\exp(-\log^2 n)$ which goes to zero faster than any polynomial.
Claim: $\exp(-\log^2 n)$ is less than $n^{-c}$ for any constant $c$ for $n$ large enough.
Proof: Look at the reciprocal. $$\exp(\log^2 n) > n^c$$ if and only if
$$\log^2 n > c \log n$$ which will clearly happen as soon as $$\frac{\log^2 n}{\log n}>c$$ i.e., as soon as $\log n>c$.
Note that $\exp(\log^{1+\epsilon} n)$ is superpolynomial for all $\epsilon>0.$
Edit: The superpolynomial convergence is essentially what is referred to as negligibility.


Does ChaCha20 counter actually increment through iterations? RFC defines:

state = constants | key | counter | nonce

Suggested on multiple places is to set counter to 0 or 1.

It is still unclear to me what the function of counter is. Why not just use larger 128bit nonce, instead of a 32bit counter + 96bit nonce?

Does the counter at position of 13th byte actually increment by one? Can I extract the number of iterations from the state of ChaCha20? From the specification, Id say that the state gets randomized after as much as one iteration.

This brings me to a 2nd question - if it is customary to set counter to 0 or 1, we can consider this is public. Does this mean then that nonce can also be made public (just like IV for block ciphers) without compromising the security? (of course provided that key stays confidential)

Thank you all for answers!

You seem a bit confused about how the various parts of the ChaCha20 cipher actually fit together, so let me start from the top down and see if I can clarify things.

At the highest level, the ChaCha20 encryption algorithm is a synchronous stream cipher: given a secret key and a (possibly) public nonce, it generates a pseudorandom keystream which is bitwise XORed with the message to be encrypted.  Repeating this process (i.e. XORing the encrypted message with the same pseudorandom bitstream again) then lets the receiver reveal the original message again.

(The purpose of the secret key is to ensure that no-one else can generate the same keystream, and thus decrypt the messages.  The purpose of the nonce is to ensure that we never use the same keystream for encrypting two different messages, since that would allow an attacker to cancel out the keystream by XORing the encrypted messages together, leaving them with the bitwise XOR of the original plaintext messages.  So, no, the nonce doesn't need to be secret — all it needs to be is unique.)

The keystream is generated by concatenating a sequence of 512-bit blocks, each of which is generated by applying the ChaCha20 block function to an initial 512-bit input block consisting of the key, the nonce, a block counter and a fixed 128-bit constant.  The reason why the block counter is needed is because the ChaCha20 block function is deterministic, and would thus always produce the same output block if given the same input.  We don't want the keystream to consist of just the same 512-bit block repeated over and over, so we include a counter in the input block to make sure that every input to the ChaCha20 block function is different.

(This is essentially the same as the CTR mode construction for making a synchronous stream cipher out of a block cipher, except with the ChaCha20 block function used in place of the block cipher.)

Finally, going one level deeper yet, the ChaCha20 block function scrambles its input by iteratively applying 10 "column rounds" and 10 "diagonal rounds" to it, in alternating order (and then finally XORing the scrambled result with the original input to make the whole thing non-reversible).  Each of these column rounds and diagonal rounds, in turn, consist of four (possibly) parallel applications of the ChaCha20 quarter round  function, which takes a 128-bit slice of the full 512-bit block and scrambles it in a particular way, as described in the linked RFC.

All that iterated scrambling ensures that even tiny changes to the input block (like, say, incrementing the block counter by one) will cause the output of the block function to look completely different.  Thus, even though the successive inputs to the block function for any given message are all the same except for the counter, the keystream obtained by concatenating the scrambled output blocks is effectively indistinguishable from random, unless one knows all the inputs that went into generating it (including, in particular, the secret key).

Of course, to deterministically generate the keystream from a given key and a nonce, we need to decide how to choose the initial counter value for the first block, and how to increment it for the later blocks.  (If we don't do it consistently when encrypting and decrypting, the keystreams will be different and we won't get the original message back!)  The obvious choice would be to number the blocks consecutively as 0, 1, 2, 3, 4, …, but in principle other methods could work just as well.

Indeed, the RFC you linked to describes the ChaCha20 encryption algorithm as taking the initial counter value as an input, in addition to the key, the nonce and the message to be encrypted (or decrypted), and describes it as follows:

  A 32-bit initial counter.  This can be set to any number, but will
    usually be zero or one.  It makes sense to use one if we use the
    zero block for something else, such as generating a one-time
    authenticator key as part of an AEAD algorithm.

Note that this is the initial counter value, used to generate the first 512-bit block of keystream, and incremented by one for every subsequent block.  So if the initial counter value is set to 0, the blocks will be numbered as 0, 1, 2, 3, 4, …, whereas if it's set to 1, the blocks will be numbered 1, 2, 3, 4, 5, … instead.

So why would you choose to set the initial counter value to something other than 0?  Well, probably because you want to start the keystream at some later block number, e.g. because you already used block 0 for something else.

In particular, the AEAD_CHACHA20_POLY1305 authenticated encryption scheme works by using block 0 of the ChaCha20 keystream to generate the one-time Poly1305 key for protecting the integrity of the encrypted message, and then using the rest of the keystream starting from block 1 to actually encrypt the message as described above.


Appropriate key for AES 256 GCM I am updating a system that has Rails' OpenSSL on one side and Python's cryptography.io on the other.

The Rails side has to generate keys for the AES-256-GCM and here are two methods that appear to work:

SecureRandom.hex
# => "3d499a7b8f57773281ca2d47698a0062"

OpenSSL::Cipher::Cipher.new("aes-256-gcm").random_key
# => "\x1A\xAC\x8F\xC4mX\xAE\xDE\x04\xE1\x83\x8F\xFF^\x8C3KJ\xBE\vt\xE4\xBC\x14B\xDEro\xB8\xF5Yy"

Due to the transmission, it is currently easier to use SecureRandom.hex, but I believe that its reduced charset would make it less secure for any given length. Is this a valid concern (meaning I should spend more time making the OpenSSL version work), or is it reasonable to use SecureRandom.hex to generate keys?

The different charsets are simply the result of different encodings. A secure random number generator will generate a sequence of bits indistinguishable from pure random. These bits can then be encoded in several ways. In your case the SecureRandom.hex is returning base64 encoded bits, while OpenSSL::Cipher::Cipher.new("aes-256-gcm").random_key is returning ASCII encoded bits (where bit sequences that have no ASCII representation are prefixed with \x and hex encoded).

These two methods do not, in fact, return the same number of random bits:

In [7]: from binascii import a2b_base64

In [8]: openssl = b'\x1A\xAC\x8F\xC4mX\xAE\xDE\x04\xE1\x83\x8F\xFF^\x8C3KJ\xBE\vt\xE4\xBC\x14B\xDEro\xB8\xF5Yy'

In [9]: len(openssl)
Out[9]: 32

In [10]: secrand = a2b_base64('Z6sBQRGKll7FEKz3ebfUiGupwhPS3QVm')

In [11]: len(secrand)
Out[11]: 24

As you can see, SecureRandom.hex generates 24 bytes = 192 bits, and OpenSSL::Cipher::Cipher.new("aes-256-gcm").random_key generates 32 bytes = 256 bits.

Since AES-256-GCM requires a 256 bit key I recommend using OpenSSL::Cipher::Cipher.new("aes-256-gcm").random_key.

EDIT

Since the value SecureRandom.hex returns in the question was updated to be a hexidecimal encoding the amount of random bits it generates is no longer 192. It actually generates less random bits now, since a base64 encoded string can encode more bits than an equally long hex encoded string.

In [1]: from binascii import unhexlify

In [2]: k = unhexlify('3d499a7b8f57773281ca2d47698a0062')

In [3]: len(k)
Out[3]: 16

So now we have 16 bytes = 128 bits.

In general, assuming a secure random number generator, the number of bytes of entropy that an encoded string of length $n$ has is:

ASCII - $n$
base64 - $\frac{3n}{4}$
hex - $\frac{n}{2}$
binary - $\frac{n}{8}$

You can multiply any of those terms by 8 to get the equivalent values in bits rather than bytes.


It is reasonably safe to leave an AES encrypted RSA private key public? The owner of the RSA key can't store the key, so they need to hand the key to an untrusted entity for storage. Before they hand it over they encrypt it using AES with a multi-word phrase they can remember.

The idea is that I could generate a private key and store it outside the entity in a non-secure location but not worry (as much) about it since it is protected by a passphrase.

The private key might be stored in several places - in fact and I have to assume they are all publicly-accessible (like a web page). But when the entity wants to do something with the key it requests it back from the storage places and then (with the users password) decrypts it and uses it for what is needed.

Based on skimming the relevant RFCs, I can't find any outright problems. Key derivation from the password is performed via PBKDF2, and best I can tell, the choice of cipher is left up to the implementation. As long as a good cipher is chosen, a truly random 30-character passphrase consisting of uppercase letters, lowercase letters, and digits should have roughly 178 bits of entropy. This is significantly higher than that of a 128-bit key, which is considered to be secure.

It still gives me a bad feeling that I can't shake. But as long as keys are only ever decrypted on trusted devices, I can't personally find a reason why it would be unsafe.

Not that this should be considered an endorsement by any stretch of the imagination.


SHA-1: number of possible inputs, number of possible outputs, how many inputs have the same output, From Wikipedia I read SHA-1 function produces an output of 160 bits and expects a max message size of $2^{64}-1$ bits. Is that right?

If I order all possible inputs I would produce $\approx 2^{2^{64}}$ different bit array inputs, right?

Not sure at this point if message 0 is different from message 00.

Can we say that SHA-1 receives a bit array of maximum $2^{64}-1$ elements as input?
If the bit array has less than $2^{64}-1$ elements it is like receiving 0's for the rest (or maybe start receiving 0's until...)?

I'm not good at big numbers... Maybe the difference is small. If 0 bit array is different than 00 bit array maybe still the number of possible inputs is $\approx 2^{2^{64}}$.

Then $2^{160}$ is $\approx 2^{2^8}$.

So there are $2^{2^{64}}$ possible inputs for $2^{2^{8}}$ possible outputs. It means that there are $\approx \frac{2^{2^{64}}}{2^{2^8}}$ inputs for each output. But $\frac{2^{2^{64}}}{2^{2^8}}$ is $\approx 2^{2^{64}}$.

If $2^{2^{64}}$ is the whole universe it looks like almost the whole universe is inside each bucket (hash output).

Does it mean that if I take randomly two different inputs of the set of
$2^{2^{64}}$ elements the probability that they belong to the same bucket is very high?

From Wikipedia I read SHA-1 function produces an output of 160 bits and expects a max message size of $2^{64}-1$ bits. Is that right?

Yup, looks right.

  If I order all possible inputs I would produce approx. $2^{2^{64}}$ different bit array inputs, right?

Yes. The number of possible inputs is the sum of the number of possible $l$-bit strings for $l$ from $0$ to $2^{64}-1$:

$$\sum_{l=0}^{2^{64}-1} 2^l \;=\; 2^{2^{64}} - 1$$

  If the bit array has less than $2^{64}-1$ elements it is like receiving 0's for the rest (or maybe start receiving 0's until...)?

Actually, SHA-1's padding is designed to prevent this from occurring. If $\text{SHA-1}$ is to be a secure cryptographic hash function, it shouldn't be possible to come up with any two messages $m_1$, $m_2$ such that $\text{SHA-1}(m_1) = \text{SHA-1}(m_2)$ (i.e. a hash collision). If it were true that $\text{SHA-1}(m) = \text{SHA-1}(m \| 0)$ ($\|$ is concatenation), that would violate this requirement.

  If $2^{2^{64}}$ is the whole universe it looks like almost the whole universe is inside each bucket (hash output).

That's a good intuition.  $2^{160}$ is a huge number, but $2^{2^{64}}$ is beyond astronomical (it's estimated that there are fewer than $2^{266}$ atoms in the visible universe).  This is what makes cryptographic hash functions so interesting.  We know that there is an incredibly astronomically massive number of colliding input pairs, but we just can't find any (or at least, we can't with a good hash function: SHA-1 is broken, and someone has most likely already found a collision).

  Does it mean that if I take randomly two different inputs of the set of $2^{2^{64}}$ elements the probability that they belong to the same bucket is very high?

If a bucket means a given hash output, then no, the probability is quite low. Let's assume that SHA-1 was a strong, unbroken hash function. Choose one input from the set of $2^{2^{64}}-1$, call it $m_1$, and let $h_1 = \text{SHA-1}(m_1)$. Note that $h_1$ is one of $2^{160}$ possible values. Now choose at random the second input, call it $m_2$, and let $h_2 = \text{SHA-1}(m_2)$. The probability that $h_2$ ended up being the same value as $h_1$ is $1/2^{160}$.

This explanation might better match your intuition: The $2^{2^{64}}-1$ possible inputs are divided into $2^{160}$ equal-sized buckets (approximately equal-sized, at least). All of these buckets are massive, but there are so many buckets that the probability of choosing two values in the same bucket is still quite low.


sign data and append certificate VS sign data and certificate I am currently writing my masters thesis in which I need to develop a licensing module for an application.

The license itself is a JSON Web Token which is signed using a RSA private key.

Since we have the requirement that resellers should also be able to create  and sign valid licenses I thought about using a PKI where my company owns the root CA and creates an intermediate certificate for each reseller (so that they can sign their licenses). The root certificate will be part of the final binary ("hiding" the root certificate in that binary is a totally different story). In order for the application to verify the license it needs to check the license's signature and needs to verify the whole certificate chain - that means that the certificate chain (except the root certificate of course) needs to be part of the license.

To my actual question: Should I

only sign the JSON Web Token and then append the certificate chain to the license or
include the certificate chain into the JSON Web Token and then sign everything altogether?

I have read through some articles that say that one should not hash secrets / through some articles that discuss about MAC-then-encrypt vs encrypt-then-MAC, but none of them can be applied to my problem (since there is neither a secret, nor an encryption involved).

Even if it makes no difference whether I sign only the JWT or the combination of both (JWT + certificate chain) I need to provide some arguments that support and explain the final decision.

Assuming you're using standard PKI certificate standards rather than rolling your own approach there's not really a security benefit to including the certificate chain in the JWT that's covered by the signature.

Each (non-root) certificate is signed by the issuing certificate. So it's already covered by a signature that traces back to your root certificate. Signing it again within the JWT doesn't provide any additional protections.

I also can't see any particular security risk with including the certificate chain within the signed portion of the JWT. A signature exists to prove the authenticity of a known message. So has to be secure when the signed text is known. Including a known certificate chain does not therefore introduce any particular risks.

So really you need to drive this decision from other application design considerations.

Including the certificate chain in the JWT has one advantage I can see which is that you can parse the message using a standard library rather than having to pre-process it.

However in most scenarios that would be out-weighed significantly by the downsides of including the certitificate chain in the JWT which are:

You're signing a lot more content than you need to so are wasting a bit of CPU
You can't seperate the token from the certificate chain. That's likely to reduce the flexibility in the application design.

EOver time you may want to be able to just deal with the license in parts of the application where you know the certificate chain has already been processed, or allow it to be resolved dynamically. By keeping the certificate chain out of the signed JWT you can more easily split the two concerns apart to be dealt with by different parts of the application.

This wil also help if you wanted to move to encrypting the token in future rather than just signing it. By keeping the certificate chain seperate you can work with it before decrypting and checking the token which will make it easier to setup the validation routine.


Testing hardware random number generators? I would like to know how to test hardware random number generators.
What techniques, tools or tricks to solve the problem ?
Any practical difficulties, implementation complexities etc.

NIST has a lot of information on testing random number generators at http://csrc.nist.gov/groups/ST/toolkit/rng/index.html that might be of value to you.


Deriving a key from a pseudo-random string I would like to know if deriving a key from a pseudo-random string with a single iteration is secure.

Concretely, I am designing a system where a secret key is derived in the client side, and then sent to the server for authentication. The steps are as follows:

User enters email and password
Derive k0 <- pbkdf2(password: password, salt: email, alg: 'sha256', iteration: 10000)
Derive k1 <- pbkdf2(password: k0, salt: password, alg: 'sha256', iteration: 1)
Send to server: (email, k1)
Server derives pbkdf2(password: k1, salt: somerandomstring, alg: 'sha256', iteration: 20000) and compares it with the hash in the database

k0 is the 256-bit secret key. The client uses it to encrypt things using a block cipher. The client needs to send something to the server for authentication purposes. But the server should not know the client's secret key. My idea is that step 3 prevents the server from knowing the client's secret key.

But I am wondering if 1 iteration of pbkdf2 is enough. I think it is sufficient because k0 is pseudo-random, and the attacker shouldn't be able to figure it out from k1. (Exhaustive search takes 2^256 steps). Is this correct?

EDIT

For clarification, here is my design so far:

## Register

Client
* User enters email and password
* Derive k0 <- pbkdf2(password: password, salt: email, alg: 'sha256', iteration: 10000)
* Derive k1 <- pbkdf2(password: k0, salt: password, alg: 'sha256', iteration: 1)
* POST to '/register': (email, k1, kdf, kdf_iteration)

Server
* Generate salt <- 256bit random string
* Derive k2 <- pbkdf2(password: k1, salt: salt, alg: 'sha256', iteration: 20000)
* Create a user with (hashed_password, salt) = (k2, salt)
* Login the user and reply with a session key

## Login

Client
* User enters email and password
* GET '/prelogin': (kdf, kdf_iteration)
* Derive k0 <- pbkdf2(password: password, salt: email, alg: 'sha256', iteration: 10000)
* Derive k1 <- pbkdf2(password: k0, salt: password, alg: 'sha256', iteration: 1)
* POST to '/login': (email, k1)

Server
* Look up user (hashed_password, salt)
* Derive k2 <- pbkdf2(password: k1, salt: salt, alg: 'sha256', iteration: 20000)
* Check k2 == hashed_password, and reply with a session token

EDIT2

Clarification on what this is for:

This is to add end-to-end encryption for an open source note taking app (https://github.com/dnote/cli).

Basically, the client can sync the data with the server. Before leaving the client, all data is encrypted using k0 which server does not know.

The server should have no idea about how to decrypt the data, so I decided to derive k1 from k0 to send to the server rather than sending k0 directly to the server.

The problem with this scheme is that $k_1$ can be calculated from $k_0$. That may not be a huge issue, but it can easily be avoided.

You can make sure that $k_0$ and $k_1$ are derived from the original master $k$ which is derived from the password. So you would have k = PBKDF2(password, mail, iteration_count) and k0 = KDF(k, "Enc") and k0 = KDF(k, "Auth").

If you've just PBKDF2 with SHA-256 you could define the second KDF(k, label) as PBKDF2(password: k, salt: label, alg: 'sha256', iteration: 1).

Other options are given in my other answer on the followup question.


Reason for difference in assumptions for practical private-key and public-key crypto Theoretical cryptography tells us that everything in the world of private-key cryptography (CCA-secure symmetric encryption, message authentication codes, etc.) can be built from one-way functions and that public-key cryptography (e.g., CCA-secure public-key encryption) can be build from the stronger notion of one-way trapdoor permutations. In addition, it is known that both one-way functions and one-way trapdoor permutations can be built based on certain number-theoretic assumptions such as the hardness of integer factorization and the discrete log assumption.

In the case of practical private-key cryptography, however, constructions are almost never based on number-theoretic assumptions, but rather on much more "high-level" assumptions, for instance the assumption that AES is a pseudo-random permutation (here I'm ignoring some technical details, e.g. that a pseudo-random permutation must be defined for infinitely many key sizes, at least to be secure in an asymptotical sense).

In contrast, all known public-key constructions (including those used in practice) seem to be based on either number-theoretical assumptions (e.g., RSA, DDH) or, in a few cases, assumptions regarding linear codes or ideal lattices - all of which seem rather "low-level" compared to e.g. the AES or DES assumptions used for private-key schemes.

This seems to explain why the public-key crypto schemes used in practice today are orders of magnitude slower than the private-key schemes used in practice.

Is there any explanation for this difference in the level of assumptions underlying the private- and public-key crypto schemes used in practice today? Is this due to historical reasons, or is there some other, perhaps mathematical, reason why no efficient public-key schemes today are based on assumptions on a similar high level as e.g. the AES? Have I missed some fast public key encryption schemes based on assumptions on such high level?

AES is not a one-way permutation; it is a permutation, for sure, but whoever can apply it can also apply its inverse. Crudely said, the AES decryption key is identical to the AES encryption key. A one-way permutation would be like a hash function: everybody can compute it in one direction, with no secret value, but nobody knows how to do it in the other direction.

Right now, we do not know how to make one-way trapdoor permutations without resorting to number theory. It is not that it is impossible; only that we did not find any. On the other hand, we have some good candidates for one-way functions (practical hash functions) which are considerably more efficient; therefore, for practical cryptography with systems that only need one-way functions, we use hash functions, not number theory. A hash function based on number theory has been tried but its performance is so abysmal that nobody is really interested in it.

Historically, the whole world was secret-key-only with no number theory; algorithms had evolved as ways to make big jumbles of bits. At best, some of these scrambling systems were designed to be permutations: these are modern block ciphers. We seem to know how to mix bits together so that the result cannot be unravelled (i.e. AES seems to be secure as a block cipher, and that's not for lack of trying to break it); but we don't know how to do it and disassociating the powers to encrypt and to decrypt. In other words, when we design a block cipher, we can inject the key, which selects the actual permutation, but we don't know how to inject it in such a way that the inverse permutation is not revealed as well. The only tools we have found yet to do that involve algebra and number theory, and they are slow.

On the other hand, the same algebraic tools open extra possibilities, namely asymmetric encryption and signatures. These extra features are so useful that we tolerate the performance issues implied by the use of these algebraic tools. So that's the historic point of view: the question is not why we don't make symmetric cryptography with number theoretic tools; rather, it is why we use the slow, cumbersome number theoretic tools at all. And the answer is that we don't know anything better for asymmetric crypto.


Security of RSA signature using PKCS 1.5 I'm using mbedTLS to generate RSA signatures, and using PKCS 1.5 I get consistent signature output.

I wanted to ask/confirm here that this is secure? There's surely got to be a reason for the PSS scheme, but some googling around left me feeling 1.5 is unbroken and 2.1 is just for a proof.

Consistent signatures a great for testing, and anything that RELIES on good entropy for security is a huge risk in my mind. So if someone can confirm my common sense isn't broken I'd much appreciated it.

Provided you follow PKCS#1 v1.5 verification exactly, and don't attempt shortcuts like checking only the hash part of the message hash representative, it should be fine.  There's no security reduction to the RSA problem proven, like there is for RSA-FDH or RSASSA-PSS, and certainly no reduction to factorization, like there is for Rabin–Williams, but no weaknesses have been published in RSASSA-PKCS1-v1_5.

If you do take shortcuts like checking only the hash part of the message hash representative, you may set yourself up Coppersmith- or Bleichenbacher-style attacks when $e = 3$, like the attack poncho sketched a while back.


How can we prove that two discrete logarithms are equal? Suppose there are two elements $a = g^x$ and $b = h^x$, where $g$ and $h$ are generators in $Z^*_p$ and $p$ is a large prime. How can we prove that $a$ and $b$ have the same discrete logarithms with respect to $g$ and $h$ respectively without leaking the knowledge of $x$?

Are you limited to working with $g$ and $h$ being generators of the entire group $\mathbb{Z}_p^*$? In that case
you have a problem with knowledge extraction in the proof of knowledge (basically, since you are not working in a field "in the exponent", but in $\mathbb{Z}_{p-1}$, the required multiplicative inverses might not exist).

However, when you work in a large
prime order $q$ subgroup of $\mathbb{Z}_p^*$ and $g$ and $h$ are
generators of the order $q$ subgroup, you can use a standard honest-verifier zero-knowledge proof of knowledge
that you know $x\in \mathbb{Z}_q$ such that $\log_g a = \log_h b$ (i.e., $a$ and $b$ contain the same discrete logarithm w.r.t. $g$ and $h$ respectively) without revealing anything about $x$. This proof is quite standard and based on Schnorr's proof of
knowledge of a discrete logarithm.

The idea proof between a prover and
a verifier on common input $(p,q,g,h,a,b)$ runs as follows (where $x$ is only known to the prover):

$P$: choose uniformly at random $r\in \mathbb{Z}_q$ and send $(k,k')=(g^r,h^r)$ to
the verifier $V$
$V$: choose uniformly at a random challenge $c\in \mathbb{Z_q}$
and send $c$ to $P$ (I took the set $\mathbb{Z_q}$ as challenge space, the
set size depends on the soundness error you are tolerating)
$P$: compute
the response $z=r+x\cdot c \bmod q$ and send $z$ to $V$
$V$: Verify
whether $g^z=k\cdot a^c$ and $h^z=k'\cdot b^c$ holds and accept if this
is true or reject otherwise.

Correctness is easy to verify and special soundness as well as
honest-verifier zero-knowledge is also quite straightforward to show.


HKDF: ikm, salt and info values As indicated at

Key generation for AES-GCM-256 file encryption

I'm currently working on a file encryption software. In the above thread it was suggested that, for performance reasons, I use a combination of scrypt and HKDF.

But how should I go about using HKDF to derive a new key for each file? As suggested in the above thread, I intend to produce a single master key via scrypt and from that I want to derive file encryption keys via HKDF.

So far I have come up with two possible ways of doing this:

(1) Run HKDF (extract-then-expand) with the scrypt result as input key material (ikm) and a NEW random salt for each file to be encrypted

(2) Run HKDF (extract-then-expand) with the scrypt result as ikm, a FIXED random salt, and a random 'info' value for each file to be encrypted

Which - if any of these - is the better or correct way of doing what I want? As I understand it, NIST Special Publication 800-56C, explicitly dsicourages re-using the same ikm and just varying the salt. But I don't exactly understand why and their use case (shared secret Z as ikm) is different from mine.

The salt is not required to make HKDF secure. Using a static salt doesn't make too much sense - you should be perfectly fine with using an empty salt. Either you can use an empty salt, or a new random salt. This salt could be generated and prefixed per file. If it is large enough (say 128 bytes) then it would make each encryption key unique so you don't have to depend on filename or other meta information (that could be part of Input) to derive the file encryption key.

The salt makes the HKDF function easier to proof, but I haven't heard on any attacks on KDF's without it - including those that directly use a hash function while they should not.

There is little need to perform the extraction of key material from the output of scrypt. Basically you can already create a key from the output of scrypt. So there is no need to derive the pseudo-random key (PRK) for using HKDF-extract. That way you should be fine with just applying HKDF-expand, making the calculations slightly less computationally intensive.

So you would have:

IKM = scrypt(password, salt1)
K = HKDF-expand(IKM, Input, 256)

where Input is any canonically encoded information that defines the file to be encrypted.

You could also go for:

IKM = scrypt(password, salt1)
PRK = HKDF-extract(IKM, salt2)
K = HKDF-expand(PRK, Input, 256)

In this case Input can even be empty if salt is random enough. The salt can be stored (prefixed) with the encrypted file.

Note that salt1 is used for scrypt which according to the org. answer of your previous question should only be used once. Therefore it cannot be used for HKDF.


On the fly key generation for cloud storage objects Cryptographic key management involves storing and managing encryption decryption keys , certificates , signatures etc .

If the requirement is just to store and manage object specific keys ( say amazon's s3 store objects ) do we really require a key management solution like the one from porticor or an appliance ?
Instead can't we generate object specific keys "on the fly" using  HKDF using a master key and object id as inputs, so that we dont have overhead of storing and managing keys each time ?

Instead can't we generate object specific keys "on the fly" using HKDF using a master key and object id as inputs, so that we dont have overhead of storing and managing keys each time?

Sure you can. I've got an even easier method. Just use the same key for everything. No key derivation or key management needed. Or even better, don't encrypt anything. No keys, no management, much simpler.

My point is, there are no solutions, only tradeoffs. Your proposal has its benefits, but also has its disadvantages (assuming object ids are public, an attacker need only steal one small piece of information, the master key, and all objects are compromised as pointed out by Ricky).


how do we calculate set intersection using homomorphic encryption? I am new to this field. I want to learn how homomorphic encryption can be used for PSI. I am aware of other SMC protocols but I never understood how to use schemes like Paillier for PSI calculation. For example Alice and Bob have two bloom filters(with set cardinalities: |$ B_{Alice} $| and |$B_{Bob}$|they want to compare and see if they match. Alice sends the encrypted (encrypted using paillier) bloom filter to Bob along with the public key. Now, how does Bob build the Binary AND, i.e., how does he calculate E(|$ B_{Alice} $| $  \wedge  $ | $ B_{Bob} $|)?

I'm not sure where Bloom filters necessarily come in.
The "standard" way to use additively homomorphic encryption (that's what Paillier is) for set intersection is the oblivious polynomial evaluation (OPE) technique.
It works like this:

Alice generates a polynomial whose roots are the items in her set: $p(x) = \prod_{a \in A} (x-a)$. She encrypts the coefficients of $p$ using an additively homomorphic scheme, under her own key. She sends the result $E_k(p)$ to Bob.
For each $b \in B$, Bob chooses a random value $r_b$ and uses the homomorphic property of the encryption scheme to evaluate $E_k\Big( r_b \cdot p(b) + b \Big)$. This requires only additive homomorphism since $b$ and $r_b$ are known to Bob. Note that: if $b \in A$ then $p(b) =0$ so the result is $E_k(b)$; otherwise the result is the encryption of a uniformly random value. Bob sends all of these ciphertexts back to Alice.
Alice decrypts the ciphertexts and computes the plaintext intersection with $A$.

This technique dates back to:

  Efficient Private Matching and Set Intersection by Michael Freedman, Kobbi Nissim, Benny Pinkas (see Sec 4.1)


How do I apply differential cryptanalysis to a block cipher? I have read a lot of summaries of block ciphers particularly with regards to the NIST competitions stating that reduced-round block ciphers are – for example – vulnerable to differential cryptanalysis.

I have a general idea that the application of differential cryptanalysis is to look at the difference between inputs; Wikipedia makes that fairly clear. However, I could take any two inputs for any given block cipher and I am pretty certain I'd be staring at random differences.

I am aware this is the idea of a well written block cipher; however, assuming a broken or vulnerable cipher (feel free to provide simple examples) how do I go about choosing differences to try?
Are there any clues in algorithm design that would inform a decision on which values to choose?
How does being vulnerable to differential cryptanalysis impact a cipher in the wild?
If all I have are differences between known plain-texts and known keys as my analysis and a captured ciphertext as my data to exploit, what can I actually deduce?

Basically it's analysis of a cryptographic cypher by the means of finding a relationship between the difference in the input data and the output data.
Ideally, the slightest difference in input data (cleartext), even a single bit, should produce a completely different cypthertext. However, if the cypher is not well-designed, a correlation between the two resulting cyphertext might be observed. This correlation in turn might be exploited to find out the key.
This, obviously requires a chosen-cleartext-attack; which means the attacker should have access to the encryption mechanism, and thus use it to encrypt any number of cleartexts he or she choses. Therefore, this kind of attack is generally applied against temper-proof hardware which one could use but not get hands on the key itself.

As per AES, see this excerpt from the Wikipedia article on differential cryptanalysis:

  For example, if a differential of 1 => 1 (implying a difference in the
  LSB of the input leads to a output difference in the LSB) occurs with
  probability of 4/256 (possible with the non-linear function in the AES
  cipher for instance) then for only 4 values (or 2 pairs) of inputs is
  that differential possible. Suppose we have a non-linear function
  where the key is XOR'ed before evaluation and the values that allow
  the differential are {2,3} and {4,5}. If the attacker sends in the
  values of {6, 7} and observes the correct output difference it means
  the key is either 6 xor K = 2 or 6 xor K = 4, meaning the key is
  either K = {2,4}.
  In essence, for an n-bit non-linear function one would ideally seek as
  close to 2-(n-1) as possible to achieve differential uniformity. When
  this happens, the differential attack requires as much work to
  determine the key as simply brute forcing the key.

Here are a few links for warming up:

A simplified AES algorithm and its linear and differential cryptanalyses
Impossible differential cryptanalysis of Mini-AES
Low Complexity Differential Cryptanalysis and Fault Analysis of AES

And here are a couple of better articles on the subject:

A Tutorial on Linear and Differential Cryptanalysis
A stochastic model for differential side channel cryptanalysis

Not top quality links, and especially not as practice-oriented as you seem to be looking for, but I think these last two could give you a bit of grip on the subject.


Why is the Domingo-Ferrer cryptosystem not used in practice? The Domingo-Ferrer cryptosystem is a fully homomorphic cryptosystem. It works fast enough. I have only seen known-plaintext attacks. Is this a reason not to use it in practice? Or are there more significant shortcomings due to which it is not recommended to be used?

TLDR: The scheme is symmetric only, its "provable security" argument is flawed, and it is practically insecure when even a modest amount of plaintext is available to attackers.

I'm commenting on the scheme in: Josep Domingo-Ferrer, A Provably Secure Additive and Multiplicative Privacy Homomorphism, published in proceedings of ISC 2002. I ignore the 1996 scheme, which in some sense is a subset.

The paper introduces a symmetric encryption system allowing computation (addition, subtraction, multiplication of plaintext) performed on the ciphertext without key, provided that the results remain below a certain bound ($10^5$ to $10^{20}$ in the proposed parametrizations).

Provable security is claimed for arbitrarily powerful adversary, but under the assumption that only a small number $n$ of plaintexts (including computed results) are known to an adversary: $5$ to $50$ in the proposed parametrizations.

This is an extremely serious limitation. Combined with the fact that it is a symmetric cryptosystem (encryption requires a secret, which also allows decryption of any plaintext or computed result known in ciphertext form), that greatly reduces the practical interest of the system.

In particular I see no credible case for offloading computation to a party with cheaper computational power, for the cost of encryption is going to be prohibitive compared to calculations of practical interest. And if we assume that all ciphertext is public, any party that encrypts of decrypts in legitimate use can get at all the plaintext.

Update: Worse, the information-theoretic security argument is flawed. In a nutshell, it shows that the adversary can't find the key under the assumption that limited information about plaintext is available, but fails to account for

equivalent keys, allowing to decipher without knowing the actual key
considerable information about the plaintext made available merely because it must be small enough that the homomorphic property is usable without overflow.

ACM DL shows 35 papers under cited by. Two notable ones are

Ueli Maurer and Dominik Raub, Black-box extension fields and the inexistence of field-homomorphic one-way permutations, in proceedings of Asiacrypt 2007: credit is given for having shown that there would be practicals applications to the objects which existence is disproved.
A 2018 self-citation in Anonymous and secure aggregation scheme in fog-based public cloud computing, acknowledging that the scheme is

  only secure against ciphertext-only attack

Sadly absent from that citation list are two specific refutations of the paper:

David Wagner, Cryptanalysis of an Algebraic Privacy Homomorphism, in proceedings of ISC 2003. The author's paper page has readable slides, and the article (ps).
Feng Bao, Cryptanalysis of a Provable Secure Additive and Multiplicative Privacy Homomorphism, accepted at WCC 2003 (I could could not locate that one).

On my first glance at the paper, I found it less than fully satisfying from a modern academic perspective:
- The security proof gives no quantitative bound of the advantage for adversaries (the claim is that parameters can be made big enough that this advantage is negligible).
- Parameter $s$ is said to be secret, but its is a small integer from $5$ to $53$ in the proposed parametrizations, and can be estimated from ciphertext size and plaintext bound. The academically correct thing to do is to consider $s$ public.
- It is considered that the system could remain secure when the number of leaked plaintexts exceeds $n$. But the argument boils down to: our analysis does not demonstrate that the secret key is computationally easy to find.


Elliptic Curve Point at Inifnity in Projective Coordinates I'm implementing an elliptic curve system primarily for ECDSA verification. I've evaluated different point representations and decided that using Jacobian projective coordinates suits best for my needs. Using this representation the point at infinity $\infty$ corresponds to $(X:Y:Z)$ = $(1:1:0)$.

As it is required to check for the point at infinity $\infty$ inside the point doubling and point addition functions, I'm currently comparing all three coordinates of an elliptic curve point to $(1:1:0)$. My question here is, if it would already be enough to check only for $Z=0$. As you can imagine this could make some difference in terms of performance, as doublings and additions are repeatedly called for point multiplication and omitting the check for $X$ and $Y$ would thus reduce some time.

Is checking for $Z=0$ enough? Could there be any corner cases for which I get $Z=0$ but actually have not reached the point at infinity? I've tested it with a high number of ECDSA verifications, and it seems to work but who knows if I have really tested the "special" cases especially on curves with 512-bit order.

The curve equation for an elliptic curve in Jacobian form is

$$Y^2 = X^3 + aXZ^4+bZ^6.$$

If $Z=0$, then $Y^2=X^3$, and all points satisfying this are of the form $(\lambda^2 :\lambda^3:0)$, where $\lambda$ is in the finite field you are working over. Projectively, these are all equal to $(1 : 1 : 0)$, and therefore the only point on the curve satisfying $Z=0$ is $(1 : 1 : 0)$. This is why we refer to it as the point at infinity, and not a point at infinity (points with $Z=0$ can be thought of as lying at infinity).

Assuming that your points are one the curve, it is therefore enough to check that $Z=0$.


Proof of Communication I desire an algorithm in which Alice sends a block of data $X$ to Bob, with proof that the data was both sent and received.  Ideally this would take the form of a public-key signature of the block $X$ by both Alice and Bob, so that each is in possession of (X + sign(X,A) + sign(X,B)).

Further let us assume that Alice and Bob both may have motivation to lie about having sent/received the communication.  Bob may choose to lie depending on the contents of $X$ once he sees it, and Alice may lie to attempt to discredit Bob.  Therefore the signatures or other proof of communication must be revealed simultaneously to both Alice and Bob.  At no point may either be in possession of the proof while the other is not.

I'd put a bounty on this if I had any reputation, but hopefully people will just consider it an interesting challenge.  Some notes that may help:  This is closely related to the Two-Generals problem (for which there is no two-party solution), however due to cryptography orders may not be forged, so I hold hope that there may be a two-party solution.  If not, a multi-party solution (using witnesses) is acceptable.  An example of an algorithm which simultaneously reveals information is Diffie-Hellman, but the shared secret there cannot be chosen by either party, so cannot itself contain any information.

This sounds like "fair exchange," the subject of many good research papers. In general you need a third party to give any security guarantees, but "optimistic fair exchange" involves the third party only when one of the parties tries to cheat (i.e., when both play honestly there is no involvement from the third party).

Incidentally, Diffie-Hellman is most certainly not fair: whoever sends first lets the other party compute the key before the original sender can.


How many Hashes to find a digest of 2^{n−k}? Given an n-bit cryptographic hash function $H$, how many messages should we expect to hash before  finding a message $x$ such that $H(x) < 2^{n−k}$ for some integer k?

My take: Shouldn't it simply take on average $2^{n-k}/2$ to find the hash?

The expected number of hashes would be $2^k$.

Here's why: if we model the hash function as a random Oracle, then each distinct message would have probability $2^{-k}$ of satisfying $H(m) < 2^{n-k}$.  The probability for each message is independent, and so the expected number of trials before you hit an event with probability $2^{-k}$ is $2^k$.


Can an RSA private key have several public keys? Ok, so my cryptography lecturer in University posed this question at the end of the RSA key generation lecture as a brain teaser.

I have been thinking about this and I think I have come up with a way ( I am aware it's not practical and very vulnerable - but I would love for you guys to punch holes through it ):

Use RSA to generate public and private key pair.

Make an additive hash function that takes in any input and adds the
ASCII value of each character and gives that as an output. ( I am aware additive hash has horrible distribution, for example, ABC, BAC, ACB all have the same hash output -- but theoretically, this can be used as an advantage to solve our problem )

Now take your public key and generate several possible keys by jumbling up the on and off bits.

Give these jumbled up keys to potential customers.

Put our hash function on the server.

When a customer puts in his jumbled up public-key - Hash function
calculates the hash - which should be similar to original public key generated by RSA. The customer gets access.

Once again I am aware that this is very vulnerable and terrible. It cant be used in the real world. But does it answer the question my lecturer posed?

EDIT:

I am sorry for the confusion. This question has nothing to do with collisions and exploiting the maths ( Those are definitely valid ways to do that - but they weren't what my lecturer was referring too - they were discussed in the lecture itself. ). The way my lecturer asked this question was - " come up with ways to make several public keys related to a single private key - nevermind how vulnerable your solution is ".

@pg1989 has not only the right answer but the only answer if you assume the goal is to have multiple RSA encryption exponents that correspond to the same decryption exponent.

\begin{align}
e_1 \cdot d & \equiv 1 \pmod{\phi(N)}\\
e_2 \cdot d & \equiv 1 \pmod{\phi(N)}\\
(e_1 - e_2) \cdot d & \equiv 0 \pmod{\phi(N)}
\end{align}

But since $d$ is relatively prime to $\phi(N)$, by Euclid's lemma $\phi(N)$ must divide $e_1 - e_2$ :

$$e_1 \equiv e_2 \pmod{\phi(N)}$$

In other words, any two public RSA exponents that share a private exponent must differ by some multiple of $\phi(N)$.

I highly suspect this is what your professor was thinking. Although, as @Thomas points out if the multiple is small and someone gets hold of both public keys, they can factor $N$. Now, maybe if you use a big multiple...

[Update]

As @fgrieu notes in a comment, I have conflated $\phi(N) = (p-1)(q-1)$ with $\operatorname{LCM}(p-1, q-1)$. Replace the former with the latter in the above derivation for the right answer.


Toy cipher -- does it have a name? When I was perhaps nine years, I borrowed a book from the library on various maths and CS topics. It outlined various simple ciphers, including one that I used a lot, just for fun. I can't remember the name of the book, or the name of the cipher, so I hope you can help me with the latter one.

It is a monoalphabetic substitution cipher with words as key. The key, an arbitrary word in the alphabet, is concatenated with the alphabet itself, and then duplicate letters are removed (keeping only the first occurrence). The resulting word is the cipher alphabet.

For instance, using the modern English alphabet and the key "STACKEXCHANGE", the cipher alphabet would become "STACKEXHNG" (key, later duplicates removed) concatenated with "BDFIJLMOPQRUVWYZ" (alphabet without letters from key):

plain  : ABCDEFGHIJ KLMNOPQRSTUVWXYZ
cipher : STACKEXHNG BDFIJLMOPQRUVWYZ

Of course, this cipher is insecure past the "highest" letter in the key (Y=Y, Z=Z), but it's still interesting as a practical explanation of substitution ciphers (perhaps even more, due to its weaknesses).

To repeat my question: does this scheme have a commonly known name? Or is known to be attributed to a person?

This is a simple substitution cipher, specifically a mixed/deranged alphabet cipher. See wikipedia's description:

  Substitution of single letters separately—simple substitution—can be demonstrated by writing out the alphabet in some order to represent the substitution. This is termed a substitution alphabet. The cipher alphabet may be shifted or reversed (creating the Caesar and Atbash ciphers, respectively) or scrambled in a more complex fashion, in which case it is called a mixed alphabet or deranged alphabet. Traditionally, mixed alphabets may be created by first writing out a keyword, removing repeated letters in it, then writing all the remaining letters in the alphabet in the usual order.
  Using this system, the keyword "zebras" gives us the following alphabets:

 Plaintext alphabet:    ABCDEFGHIJKLMNOPQRSTUVWXYZ
Ciphertext alphabet:    ZEBRASCDFGHIJKLMNOPQTUVWXY


How does RFC 5652 authenticated data confirm origin and data integrity? My reading of RFC 5652 Authenticated-Data does not give receiver confidence in originator of message, and therefore can not provide data integrity certainty.

Originator process is:

1. generate random message key
2. encrypt message key for (each) receiver
3. generate message MAC using message key
4. send to receiver

Why can't an attacker do this?

1. intercept message
2. modify message (since it is not encrypted)
3. generate a new random message key
4. encrypt message key for receiver using receiver public key
5. generate a new MAC
6. send to receiver

How would receiver know that it was not from originator?
How would receiver know that message has been changed?

How would receiver know that it was not from originator?

The recipient doesn't know the sender with this scheme. It can be anybody.
Why? There's no secret involved in the sending process that is unique to the sender and thus anybody can create such a message, as you already noted.

  Why can't an attacker do this?

He can. However this looks more like a building-block for other schemes and as such these may implement advanced sender-authentication mechanisms which would prevent such an attack.

  How would receiver know that message has been changed?

The recipient always knows that the message is unaltered with respect to the sender, because the MAC is valid. The fact that the sender may change is not covered with this scheme (and in fact, an attacker does change the sender to himself with the obvious attack).


How much would this AES modification improve security? How much would using AES-CTR like 3DES improve security?

Like so (Using a 512-bit key split into two; $K_1$ & $K_2$, and seperate nonces for all stages):

Encrypt plaintext $P$ with key $K_1$
Decrypt ciphertext $C$ with key $K_2$
Encrypt muddled text $M$ with key $K_1$

How much would this improve AES's security?

EDIT:
After being asked to clarify my idea pseudocode (python like) is available below:

nonces = urandom(16), urandom (16), urandom(16)
key = 'legorooj'*8 # Example purposes, IRL I use Scrypt

msg = 'random message'

data1 = aes_ctr.encrypt(msg, key[:32], nonces[0])
data2 = aes_ctr.decrypt(data1, key[32:], nonces[1])
final_data = aes_ctr.encrypt(data2, key[:32], nonces [2])

Decryption would be the reverse operation of course.

It would not improve security at all.

For AES-CTR mode, encryption and decryption use the same algorithm: generate the key stream using the counter and then XOR the plaintext with it. Because of that, step 1 and 3 would completely cancel each other out, and you would be left with the "decryption" in step 2.

If you'd just use the first two steps then you would actually two independent keystreams. However, as they both rely on the AES algorithm then if the algorithm is broken, your scheme may still be broken as well. This is why usually that kind of construction is created with two algorithms that are rather distinct from each other.

You keep trying to "improve" a cryptographic primitive that is already considered secure. Why not try to improve one of the many problematic schemes? Preferably you would try and first understand the scheme before trying to improve it, like you tried to do for AES-CTR.


Flaw in the security definition of *Stateful* Authenticated Encryption? I'm in search of the correct definition of a stateful authenticated encryption scheme (sAE), and its related security notion. This has been treated several times in the academic literature, however, all the papers I've read contains a discrepancy between how they state the security goal in informal English and their formal security game. In particular, their formal specification of the security game always contains a flaw that allows for a trivial win for the adversary.

Formally, a sAE scheme $\mathcal{SE = (K, E, D)}$ consists of three algorithms, a key generation algorithm $\mathcal{K}$, an encryption algorithm $\mathcal{E}$ which is both randomized and stateful, and a decryption algorithm $\mathcal{D}$, which is deterministic and stateful. The encryption and decryption algorithms are subject to the correctness requirement that if they both start in the initial state, and for $i = 1, 2, \dots,$ if $C_i = \mathcal{E}_K(M_i)$ and $M_i' = \mathcal{D}_K(C_i)$, then it must be that $M_i = M_i'$ for all $i$.

The first paper to formally define a notion of security for sAE was Bellare et al in Authenticated Encryption in SSH: Provably Fixing the SSH Binary Packet Protocol.
They define the interaction between the encryptor and decryptor to be in-sync, if at any point in time, the sequence of inputs to the decryptor is a prefix of the outputs of the encryptor. They are out-of-sync if they are not in-sync. This is their informal statement of the security game capturing stateful privacy IND-SFCCA (note that this paper splits the security of an sAE scheme into an individual security requirements for privacy and one for integrity, whereas later papers merge these into one combined game. The game formulations are still very similar, and are also equivalent in terms of security: Appendix B):

And this is their formal definition (Appendix A. Def. A.2):

The flaw: In the formal definition, the $\mathcal{D}_K$ oracle returns something other than $\perp$ if: (1) $j > i$ i.e., $C$ is a proper out-of-sync message or (2) $C \neq C_v$, i.e., the submitted ciphertext was not the latest ciphertext output from the encryptor. Notice a flaw with this?

Assume the attacker first asks his $\mathcal{E}_K$ oracle for some messages $M_1, M_2, M_3$, say, and are given back $C_1, C_2, C_3$. He then calls $\mathcal{D}_K$ on $C_2$. Notice that $i = 3$ and $j = 1$, so (1) is not true, but (2) is, since $C_2 \neq C_1$. Hence we enter $\mathsf{phase} = 1$, and the adversary receives the decryption of $C_2$ and can trivially win the game.

Now you might simply dismiss this as a trivial "typo"/oversight, and that the authors really meant to write something equivalent to their informal description. However,
this security definition, with the same flaw, has been repeated in several other papers by different authors:

On the security of TLS-DHE in the standard model (Def.5, Fig. 1 and Fig. 4)
On the security of TLS-DH and TLS-RSA in the standard model (Def.7 and Fig.1)
On the security of the TLS protocol: a systematic analysis (Appendix B.1, and Fig. 6)

In addition, you have the paper by Brzuska et al Less is More: Relaxed yet Composable Security Notions for Key Exchange, who provides a summary of the above definition (Def.16, p. 29) in their own (and different) framework, recreating the same flawed behavior!

So what's going on here?

Answering my own question since there haven't been any response.

In fact there is no flaw in the definition. Nor in my attack per se!

However, the entire point of this definition is to rule out non-stateful schemes (and stateful schemes that doesn't incorporate the state in a sufficient manner) as being secure. In particular, when the adversary asks for the decryption of $C_2$, the decryption algorithm is in state "1", not "2", i.e., expecting to receive a ciphertext created by an encryptor who was in the "1" state when he created it. Thus, if the stateful scheme is worth its salt, the decryption of $C_2$ better result in failure, i.e., $\perp$. Hence, it's no problem to return the "decryption" in $\mathsf{phase} = 1$ anymore, since it will not give the attacker any distinguishing advantage.

I mistakenly thought that this attack applied generically to all encryption schemes, but forgot that non-stateful schemes should fail this definition.


Is all of encryption based on xor? For a long time I've been under the impression that all of encryption uses xor at its basic level.

Is this true? What other method could be used to encrypt plaintext with a key? Asymmetrically, as while as symmetrically?

There are hundreds of ciphers, aes, blowfish, ect. They are all different, but do they all rely on xor?

It is a dumb question, however it was never asked (at least on google).

You don't have to use XOR, but rather, it tends to be convenient.  One of its convenient properties is that it is its own inverse.  Also, XOR implements addition in $\mathbb F_{2^n}$, making XOR a key component of working in finite fields of characteristic $2$, if you want to use them in an algorithm.

The "one-time pad" is usually defined as taking a random key the same size as the input and XORing them together to produce the ciphertext.  If you changed XOR to addition, whether $\mod 256$ or considering the entire input to be one large number, it would still be perfectly secure.  It just wouldn't be its own inverse - decryption would require subtraction instead of addition.

RC4 was considered secure for years, and though somewhat broken in modern times, it can serve as an example.  RC4's algorithm revolves around swapping bytes in an S-box, then determining a byte to XOR with the plaintext.

If you modified RC4 to do $\mod 256$ addition instead of XOR, it would have the same security as standard RC4.  However, it then wouldn't be its own inverse; decryption would require an RC4 that uses $\mod 256$ subtraction.


PKPA to Supercede TLS/AES etc? I wont give the name of the company, but here's a quote from a white paper they published:

  Our innovative Polymorphic Key Progression Algorithm (PKPA) technology is designed to overcome the flaws and inadequacies associated with today’s encryption algorithms.

I know enough about crypto to be dangerous, but my thoughts are that this is a technology that is trying to solve a problem that doesn't exist. They cite numerous hacks, but am I wrong in assuming that such hacks are very seldom the result of the crypto technology, and instead usually the result of someone leaving the keys in the car?

Sounds like snake oil for me.
The phrase you cite can be easily googled and tracked back to a white paper by CipherLoc in which they suggest that AES can be broken by using frequency analysis of english text when reusing the same encryption key for many inputs. In their explanation they deliberately ignore the role of a random IV with AES which should make such attacks infeasible. And their "solution" against this is this "PKPA" thing which somehow scrambles the data before encryption to make such frequency analysis impossible. Apart from that this is not intended to replace AES but instead used additionally to it.


Secure scheme to share symmetric key using asymmetric keys and certificates with N parties I need to distribute symmetric AES key into number of end points which will use it to decrypt data. The AES key will be the same on all end points, it is not possible to generate unique on every end point.

I am thinking about using asymmetric keys and certificates stored on USB cryptographic token to provide access to encrypted AES key and decrypt it with private key.

Is there any cryptographic scheme that can ensure that N of private keys will be able to decrypt AES key (assuming that the cryptogram of AES is same on all endpoints)?

The AES should be encrypted by public key and distributed.

This is easy, if you are willing to take a huge storage overhead, just encrypt the AES key with all the public keys and store the ciphertexts along with the public key hashes for retrieval.

So let $K$ be your AES key. Let $(pk_i,sk_i)$ be your, e.g. RSA, public key encryption keypairs, where the private key is unextractable on a smartcard. Then you want to have a data-structure, which doesn't reveal any information about $K$ by itself, but allows for retrieval of $K$ using any $sk_i$.

The solution to this is simple: Store $\large{\parallel}^n_{i=1}$$\left(h(pk_i),E_{pk_i}(K)\right)$, that is a list of pairs of public key hashes and the corresponding encrypted AES key, on each endpoint for an arbitrary (potentially insecure) hash function $h$ and a secure public key encryption scheme $E$ e.g. RSA-OAEP. The idea being that when you want to access the key with any given smartcard, you compute the hash of the public key you have on your card and iterate over the list of public key hashes, to find the ciphertext most relevant to you. If you wouldn't do that and would just try to decrypt each ciphertext, which is a possibility, then this would be quite slow, because smart-cards are not exactly known for their speed when it comes to private-key operations.


Will compression help defeat single letter frequency attack against a mono alphabetic substitution cipher? Alice has a long message to send. She is using mono alphabetic substitution cipher. She thinks that if she compresses the message it may protect the text from single letter frequency attack by Eve. Does the compression help? Should she compress the message before the encryption or after the encryption? Defend.

Will compression help defeat single letter frequency attack against a mono alphabetic substitution cipher?

What user466720 said about ciphertexts being uncompressable is applicable to modern ciphers such as AES. It does not apply to monoalphabetic substitution ciphers, since such a cipher does not change the entropy of the data.

Per fgrieu's comment, you should assume that the attacker knows whichever compression algorithm is used.

Compression, unlike the monoalphabetic substitution cipher, does change the entropy of the data. When a monoalphabetic substitution cipher is applied to the compressed data, the encrypted data will therefore have the same entropy as the compressed data. As such, an attacker will not be able to conduct a frequency analysis on this data. That is because they do not know what the entropy is (which is a requirement of performing frequency analysis).

If you were to apply the cipher, then compressed the encrypted data, the attacker could decompress the encrypted data, and then perform frequency analysis on the decompressed data, assuming they can figure out the compression algorithm used. This is a fair assumption to make, since no aspect of the compression algorithm is secret and their specifications are freely available to all people.


Mitigating the effects of server-compromise in an end-to-end encrypted system I'm working on a chat system that will be end-to-end encrypted, and I've run into a problem. As you know, in end-to-end encrypted chats, the server isn't trusted at all; it's why we have fingerprint checking etc.

The problem came about when I was considering group chats. If Alice, Bob, and Eve are communicating, and Jill decides to join the server, we'll have to re-do the key exchange for her. But what if Jill is a malicious attacker? We'll be giving her the encryption keys! The solution I had in mind was to place each "trustworthy" client's public key in a file on the server, just like SSH does, and then the clients can identify themselves with a digital signature on connection. Now, as D.W. pointed out, this requires trusting the server, which is against standard end-to-end spec. In fact, any solution that allows the server to choose who is in the chat requires trust in the server.

Because what if the server is compromised or dishonest, and instead of attempting an MITM attack, it decides to add his own public key to the authorised_keys file? Then he can connect as a legitimate user and steal the session key. (This is how SSH does it, and I'm not sure how it mitigates this possibility, so as a side-question, clearing this up would be helpful.)

In an end-to-end encrypted system, what degree of control does the server usually have? I mean Signal Messenger has to have thought about this scenario and mitigated it.

Let me direct my question like so: what is the recommended practice for deciding who is a part of an end-to-end encrypted group chat? By recommended practice, I mean to communicate that an answer that draws from a well known and trusted protocol, or thing, like the signal protocol, would be optimal. The requirements are that the server should not be trusted and confidentiality and security for the clients should hold up in the adversarial model. They should also hold up if the server is compromised.

Obviously if the server cannot decide who is in the group, then the clients would somehow have to authorise each additional member, but seamlessly. How should I handle this? The idea is that the server is always up and clients can join and disconnect at any time, like a chat room.

Trusted server

That's right.  There are several standard approaches to handling group key management with a trusted server:

Group key: Use a single group key known to everyone in the group.  Anytime someone is removed from the group, change the group key and update everyone who is supposed to still have access.  Use a symmetric key for the group key; this makes encryption and decryption efficient.
Individual keying, with server proxying: Give each person their own individual symmetric key, which is shared only with the server.  Each person has a secure connection with the server, secured with this key, and the server forwards messages (decrypting and re-encrypting).  This is a hub-and-spoke model, with the server responsible for determining who is allowed to see the messages.  When someone is removed from the group, the server will stop forward messages to them.
Signed list of group members: Have the server sign a list of group members, along with a timestamp.  For instance, each group member could be indicated by its public key.  It's important to include a way for the server to prove freshness of the signed list (e.g., include a timestamp in the signed data).  This solution is vaguely similar to what you sketched in your question, except you seem to have overlooked the need for a timestamp and a signature.  Clients will have to periodically poll the server to check for updates to the list of group members.

If you use public-key encryption to encrypt all messages between group membesr, this will be unnecessarily expensive/slow, because it would require all clients to use public-key encryption to encrypt each message, and require $O(n)$ public-key encryptions per message sent.  However, each client could exchange a symmetric key with every other authorized member of the group (using the public key provided by the server), cache this symmetric key, and use it for all subsequent messages, which will be more efficient.

Yes, this is a pain, but it's a necessary pain.

No, your solution isn't secure, for exactly the reason you mentioned: because the list of group members is unsigned, it can be modified by a man-in-the-middle.

All of these solutions require trust in the server.  That is unavoidable: it's part of your problem specification that the server determines who is authorized to be in the group.  Thus, a malicious server can just add himself to the group and read/modify all the traffic.  Once you start from a world where the server is empowered to decide group membership, you must trust the server.  There's no way to avoid trusting the server, if the server is empowered to decide who is part of the group -- in that model, there's no way to build a solution that doesn't involve trust in the server.

Untrusted server

The simplest approach is to have a single group leader who is in charge of group membership, and who has complete control over the list of people in th group.  The most natural model is that the group leader be the first person to create the group -- so the group owner is one of the members of the group, and controls who the other members are.

You can easily support that model, without trust in the server.  Simply take any of the three solutions above, but replace "server" with "the group owner's machine".

There are other approaches one could imagine -- e.g., once someone is in the group they can never be removed (revocation is impossible); or, all members must approve each group member and any member can kick anyone out of the group at any time -- but the usability consequences of those seem horrible, so I can't imagine they are going to be attractive.


Are there any Secp256k1 ECDSA test examples available? Are there any available test cases for testing elliptic curves like secp256k1 (Korblitz curves from http://www.secg.org/collateral/sec2_final.pdf)? For curves like P192 there are for example those values: http://point-at-infinity.org/ecc/nisttv .

Moreover, what other ways one should test an implementation of an elliptic curve to make sure it is working correctly in all the scenarios used in encryption software?

Are there any easy to understand examples/tutorials of how to program and test elliptic curve algorithms that are available online?

Here are five test vectors for secp256k1, which I just generated with my own code. My code is a generic implementation of elliptic curves; it has been tested for many curves for which test vectors were available (in particular the NIST curves) so I tend to believe that it is correct. Each test vector is a value $m$ (chosen randomly modulo the curve order $n$) and the coordinates $(X, Y)$ of the point $mG$, where $G$ is the conventional generator defined in section 2.7.1 of SEC 2.

m = AA5E28D6A97A2479A65527F7290311A3624D4CC0FA1578598EE3C2613BF99522
X = 34F9460F0E4F08393D192B3C5133A6BA099AA0AD9FD54EBCCFACDFA239FF49C6
Y = 0B71EA9BD730FD8923F6D25A7A91E7DD7728A960686CB5A901BB419E0F2CA232

m = 7E2B897B8CEBC6361663AD410835639826D590F393D90A9538881735256DFAE3
X = D74BF844B0862475103D96A611CF2D898447E288D34B360BC885CB8CE7C00575
Y = 131C670D414C4546B88AC3FF664611B1C38CEB1C21D76369D7A7A0969D61D97D

m = 6461E6DF0FE7DFD05329F41BF771B86578143D4DD1F7866FB4CA7E97C5FA945D
X = E8AECC370AEDD953483719A116711963CE201AC3EB21D3F3257BB48668C6A72F
Y = C25CAF2F0EBA1DDB2F0F3F47866299EF907867B7D27E95B3873BF98397B24EE1

m = 376A3A2CDCD12581EFFF13EE4AD44C4044B8A0524C42422A7E1E181E4DEECCEC
X = 14890E61FCD4B0BD92E5B36C81372CA6FED471EF3AA60A3E415EE4FE987DABA1
Y = 297B858D9F752AB42D3BCA67EE0EB6DCD1C2B7B0DBE23397E66ADC272263F982

m = 1B22644A7BE026548810C378D0B2994EEFA6D2B9881803CB02CEFF865287D1B9
X = F73C65EAD01C5126F28F442D087689BFA08E12763E0CEC1D35B01751FD735ED3
Y = F449A8376906482A84ED01479BD18882B919C140D638307F0C0934BA12590BDE

For self-testing an elliptic curve implementation, I suggest first verifying that multiplying $G$ by $n$ (the expected curve order) indeed yields the point at infinity. Then, do the following many times:

Choose two random integers modulo $n$; call them $a$ and $b$.
Compute $c = a + b$.
Compute points $P = aG$, $Q = bG$ and $R = cG$.
Verify that $P + Q = Q + P = R$.

If you go through this a few dozen times with no errors then chances are that your implementation is at least mostly correct.

A must-have reference on elliptic curve implementation is the Guide to Elliptic Curve Cryptography. It is not free, but worth its price. Good university libraries will let you read it without spending a dime on it.


How does AEAD guarantee authenticated encryption and plain AES does not? This is a follow up to my earlier question. This is more out of curiosity in how AEAD (like CCM or GCM) works compared to encryption in other modes (like CBC or ECB).

Suppose you have AES-256-CBC encrypted blocks of data, each encrypted with a proper nonce (no collisions). How is it less safe and non-authenticated compared to the same blocks of data, but encrypted with AES-256-GCM? What sort of an adversary attack does AEAD prevent that no other mode can prevent?

I understand that if the adversary replaces the entire ciphertext block with another valid ciphertext, this will go undetected in non-AEAD capable mode, but will be detected with AEAD.

However, if data is encoded with a nonce that's clearly visible (one common implementation prepends the ciphertext with a nonce), then it is possible to replace the entire ciphertext with a previously valid ciphertext (since the nonce is known).

Do I understand correctly that a proper implementation requires that you store all previously used nonces and never reuse them?

However, if data is encoded with a nonce that's clearly visible (one common implementation prepends the ciphertext with a nonce), then it is possible to replace the entire ciphertext with a previously valid ciphertext (since the nonce is known).

This is known as a 'replay attack', and is typically handled at a higher level.

One easy way is the TLS approach; it just keeps a record counter on both sides, and the counter (which increments for each record) is included with the AAD.  If someone were to replay the record, the counter of the original encryptor (which was at some original value) and the counter of the decryptor (which would be at some larger value) would not be the same, and hence the integrity check would fail.

Another approach is the DTLS and IPsec approach; they don't assume a reliable transport (packets sent by one side might not make it to the receiver, or packets might be received out of order), hence counters on the two sides would not necessarily be synced.  Hence, what the do is have the encryptor keep a counter, which is explicitly sent in the packet (and which is included in the AAD).  Then, the receiver checks the counter to see if it's one it has seen before; if so, it rejects the packet.  This protects against replay attacks; if the attacker replays the packet with the original counter value, then the packet will be rejected by the above logic; if it adjusts the counter, then the GCM integrity check will fail.

Of course, there are other possible strategies; these are just two which are used in practice.

  Suppose you have AES-256-CBC encrypted blocks of data, each encrypted with a proper nonce (no collisions). How is it less safe and non-authenticated compared to the same blocks of data, but encrypted with AES-256-GCM?

I just showed you how GCM can protect against replay attacks; there are also message-reordering attacks which the higher level protocol needs to protect against.  GCM itself protects you against other attacks which modify a message to something that the valid encryptor hasn't produced.  On constrast, CBC mode does not; the attacker can do a number of modifications of CBC-encrypted messages without being detected (unless you also include some sort of MAC, which anyone sane would)


Theoretical notion of white-box Is there any theoretically safe notion of white-box?

I have been reading about white-box [1, 2, 3] recently. It seems white-box deals with code obfuscation and its not known whether a perfect white-box exists.
I am curios about theoretical notion behind this. For a stream cipher, the theoretical notion is PRF. For block cipher it is PRP. For a hash function, it is one-way function. Is there anything comparable for white-box?
I am looking for something which is not necessarily practical, but we can actually show this achieves perfect white-box, like a really scrambled code or something.
UPDATE. I vaguely remember reading something on the line of

White-box would be possible if a super-huge memory exists. The memory could be loaded as a look-up table with the plaintexts as the look-up-keys and the ciphertexts the look-up-values. Since the encryption-key is not involved in the look-up table (it has been used previously to create the look-up table), it cannot be recovered but encryption would be still possible.

But I could not retrieve the source. Does anybody know anything about it?

Caution: White Box Cryptography is out of my comfort zone, and I have not been following the latest developments in the field. The following is my current opinion, which I present in hope of seeing it challenged, and learning in the process.

As I see it, the traditional goal of White Box Cryptography (and the one the industry would like most) is to design software that computes a standard public keyed cryptographic transformation (such as a keyed PRP, ideally AES) with a particular instance of the secret key embedded in the software, such that leaking the software does not leak the key.
I know no serious claim that this is even close to be achieved. On the contrary, WBC competitions that focused on the above goal with AES as the PRP have AFAIK all ended with quick key extraction.
With respect to that goal, it seems we do not even have practically secure WBC, and thus much less theoretically secure WBC. Contrast with the better situation in symmetric crypto, where we have practically secure PRPs and PRFs, but arguably no theoretically secure construction from first principles.

Yet a variant of WBC as defined above is practically feasible if we allow to construct the keyed transformation with WBC in mind: for example it's trivial to make a practically secure WBC implementation of the AES-256 lookalike WES-256, defined as:
$$\begin{align}
\text{WES-256}:\quad&\{0,1\}^{256}\times\{0,1\}^{128}\to\{0,1\}^{128}\\
&P\mapsto\text{WES-256}(K,P)\underset{\text{def}}=\text{AES-256}(\text{SHA-256}(K),P)
\end{align}$$
If we take that variant definition, security of WBC follows from that of more traditional constructs.

My conclusion is that I know no good definition of the theoretical goal of WBC, thus can't answer the question!


Dual of a complex lattice We know that for a real full-ranked lattice $\Lambda$, with real square matrix $\mathbf{B}$, the dual lattice $\Lambda^{\vee}$ has matrix $(\mathbf{B}^{-1})^T$.
Now If we have a complex lattice with $N \times N$ complex matrix $\mathbf{C}$, what would be the matrix of its dual lattice? Would it be the same? Or we need to put complex conjugation?
Thank you!

Let $G=\{a+ib:a,b\in \mathbb{Z}\}$ be the Gaussian integers (something similar can be done with the Eisentstein integers defined via third complex roots of unity as well).
$G$ is the ring of integers of the complex field $\mathbb{C}$. With the inner product of $x,y \in \mathbb{C}^n$ defined via the hermitian inner product
$$
x\cdot \overline{y}=x_1 \overline{y_1}+\cdots+x_n\overline{y_n},
$$
the dual lattice of a lattice $\Lambda \subset \mathbb{C}^n$ is defined as
$$
\Lambda^{\ast}=\{x \in \mathbb{C}^n: x \cdot \overline{u} \in G~for~all~ u \in \Lambda\}.
$$
The lattice $\Lambda$ itself is of course the set of all vectors
$$
\xi M,
$$
where $\xi=(\xi_1,\ldots,\xi_n) \in G^n$ is arbitrary and $M$ is a complex $n\times m$ generating matrix for $\Lambda.$


Is there a secure cryptosystem that can be performed mentally? I, myself, do not plan on getting into a situation where I would be unable to use a computer in order to communicate securely.  However, I can think of many practical situations in which mental cryptography would be useful.

Is there a secure cryptosystem that is simple enough to be performed mentally?

Clearly, one of the challenges is remembering >100 bits of entropy to leverage, but I am assuming that this can be done beforehand.

How susceptible would any such system be to side channel attacks (like trash rummaging)?

(Converted to answer from a comment.)

If pen and paper are permitted, one could probably carry out the RC4 algorithm fairly easily using 256 numbered pieces of paper (small post-it notes might be ideal, since they'd be harder to move by accident) arranged in a 16 by 16 grid (I'd suggest numbering the notes in hex for easier indexing), with two coins or something to keep track of the $i$ and $j$ indices.  The algorithm itself is simple enough to memorize, too.  To destroy the internal state, just shuffle the notes (and cut them up and burn them if you want to be sure).

The hard part would be key setup.  The usual way of keying RC4 is not only laborious to do by hand (it's more or less equivalent to 256 encryption steps), but doesn't really shuffle the state all that well.  The standard remedy for that is to discard the initial part of the output, which makes for even more work for our would-be computerless cryptographer.  If you can safely carry around the state as a stack of notes, you can do it once and then just keep churning out more of the same keystream for each message, but if not, some alternative key setup mechanism would be highly recommended.

Also, there's always Solitaire, although it needs a deck of cards and has significantly worse biases than RC4.  In fact, the design of Solitaire bears a strong resemblance to RC4, and was almost certainly inspired by it.  Given the known weaknesses of Solitaire, if you want a hand cipher using playing cards it might be better to go with RC4-52 (i.e. standard RC4, only with 52 instead of 256 elements in the state array), although I don't know if anyone's done any serious cryptanalysis of that.  (It's almost certainly weaker than normal RC4, but I'm not sure how much weaker.  Probably still better than Solitaire, though.)


Purpose of hashing last block in Merkle-Damgård? Is hashing the last block in the Merkle-Damgård necessary in preventing collisions? i.e.  What if I just outputted $z_B || L$, where $z_i$ is the hash of the last block of the message, L is the length of the message and B is the number of blocks, instead of $H(z_B || L)$?

The purpose of hashing the last block is simply to prevent leaking information like, $L$, the length of the input. It's also important so that if $L\leq \langle 2 \rangle$, then $H$ is still compressing the input.

That being said, if you don't hash the last block of the Merkle-Damgård transform, $H$ is still collision-resistant, assuming that $h$ is collision resistant.

Let $\Pi=(Gen,H)$ and $\Pi'=(Gen,h)$. Assume $h$ is a collision-resistant hash function. Suppose for a contradiction that we can find a poly-time adversary $\mathcal{A}$ that finds a collision in $H$ with non-negligible probability $\delta(n)$. We will now construct a poly-time adversary $\mathcal{A}'$ that will find a collision in $h$.

$\mathcal{A}'$ begins by running $\mathcal{A}$ and finding a collision in $H$ such that $H^s(x)=x_B\Vert L=x_B'\Vert L'=H^s(x')$ and $x\neq x'$. Since the length is sent in the open and $x_B\Vert L=x_B'\Vert L'$, then it must be the case that $L=L'$. Define $\mathcal{A}'$ to output whatever $\mathcal{A}$ outputs.

Because $|x|=|x'|=L$, then we can find a collision by proceeding inductively. Since $x\neq x'$, then there must exist some $i$ where $1\leq i\leq B$ such that $x_i\Vert z_{i-1} \neq x_i'\Vert z_{i-1}'$.

Working backwards from the output, find the first such $i$. It must be the case that $h^s(x_i\Vert z_{i-1}) = h^s(x_i'\Vert z_{i-1}')$ and so we have found a collision in $h$. Have $\mathcal{A}$ output $x_i\Vert z_{i-1}$ and $x_i'\Vert z_{i-1}'$.

But this means that we have found a collision in $h$ by calling $\mathcal{A}$ only a polynomial number of times which implies that $\mathcal{A}'$ also runs in polynomial time i.e.
$$\text{Pr[Hash-Coll}_{\mathcal{A}',\Pi'}(n)=1]$$
is not bounded by any negligible function, contradicting the collision-resistance of $h$.