Random Access vs. Parallelism modes of operation I am trying to understand some concepts regarding Random Read Access and Parallelism in mode of operations. I have written below what my concepts are regarding the two. If you can please correct where i am wrong, that would be great:

What is the difference between random read access and parallelism?

Ans: Random read refers to reading (decrypting) any nth block of data without calculating the previous n-1 blocks while parallelism is reading all or writing (encrypting) multiple blocks at the same time. Is that correct?
Random read access for decryption in general is good or bad?

Ans: It just adds convenience for the users at both ends.
Has random read access got any security implications if its possible in a particular mode of operation. For instance, CBC that allows random read access. Is it easier for an attacker to read any specific block he wants? Or it doesnt matter because the attacker can decrypt all or one block he/she wants.

I am not sure about this one

Random access (read, or write, or both) is a property of a mode of operation. Parallelism is a form of computation where multiple independent execution units can work together to complete an operation faster. They're somewhat orthogonal concepts, although random access does imply that a mode of operation is trivially parallelizable.

Random access is always a good thing because it allows more flexibility in how the mode of operation can be used (for instance, random access modes are desirable in full-disk encryption because you don't want to be waiting for your entire disk to be decrypted just to read a small text file on it). There are perfectly secure modes of operation available with either non-random-access and random-access. Random-access modes do generally tend to require a little more care with nonce/IV selection than modes without due to the constructions that tend to come up when designing for random access, but there is absolutely no reason to equate random access capability with security.

Random access has nothing to do with security; if a mode of operation that allows random access is insecure, then it is a bad mode of operation and should never be used, regardless of its random access properties. Whether an attacker does or does not leverage CBC's random access properties when decrypting has no impact on CBC's security properties (stated differently: CBC is what it is; the fact that it happens to allow random access during decryption has no bearing on its security properties).


A5/2: Ciphertext Only Attack A5/2 could be attacked with cipher-text only, using the Error Correction Code, in order to retrieve the session key.

For the purpose of simplicity suppose that the error correction code copy the plaintext 4 time.
e.g., for $=1010101$ we will encrypt the following bits: $1010101 \space 1010101  \space 1010101 \space 1010101 \space 1010101$.

Here's an example of a message and a corresponding cipher:

$'= 1010101 \space 1010101 \space 1010101 \space 1010101 \space 1010101$
$= 0110100 \space 1000001 \space 1101111 \space 0000101 \space 1010111$

Bold bits are from the same bit in plaintext.

How can I find the session key this way?

I guess I need to make some linear functions, such as:

$p_0 \oplus k_0 = 0$,

$p_0 \oplus k_8 = 1$,

etc...

But I can't really find the key this way.

The idea in [1] (disregarding reception errors) is to first remove the impact of the message. This is done by computing the syndrome

$\qquad\qquad\mathbf{H} \mathbf{v} = \mathbf{H} (\mathbf{m} \oplus \mathbf{k}) = \mathbf{H}\mathbf{k}$.

In the case of a ${1}/{5}$ repetition code, this could correspond to adding even number of (bold) codeword symbols together (since it is a repetition code they should be equal, right?), forming linear equations containing only keystream bits. Then, by exhaustively trying all $2^{16}$ starting states, it is possible to mount an attack (for each starting state) consisting of Guassian elimination, solving for the session key.

I found a reference implemenation at [2], which you might want to check out.

[1] http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2006/CS/CS-2006-07.pdf

[2] http://www.npag.fr/project-a52hacktool


How to provide integrity even though using Authenticated Encryption? Gilles made the following comment here:

using authenticated encryption does not guarantee integrity, only authenticity. You can't detect a rollback.

From what I gathered:

Authenticated Encryption provides authenticity of the data see here.

Authenticated Encryption is basically computing a MAC at the same time as you encrypt see here.

We have the usual 3 properties as follow:
confidentiality: only the authorized users can read the data (and understand it).
integrity: the users have the guarantee that the data have not been modified, or in other words only the authorized users can modify the data.
authenticity: the users have the guarantee that the data/entities are who they are (this is different from identification).
Gilles' scenario is the following:

Our beloved Alice store some data on a server, using Authenticated Encryption.
At some point Eve hacks into her server and take a copy of the encrypted data.
Alice store some data again on the server, still using her secure Authenticated Encryption.
Eve replace the data by the ones she took earlier (thus the tag is still valid).

Therefore we have a rollback. Bob accessing the data can see that they are authentic, i.e. they do come from Alice.
Can we consider that the integrity of the data is preserved or not ?
At the same time they have been modified (the replacement) but the previous data have not been modified (in order to keep the Authentication Tag valid). Should the property of integrity not being preserved in this case?
Is there any scheme at all that provide such property or is it something that should be provided using another way (e.g. a version system that is not kept at the same place as the data) ? In other words, is there any Encryption scheme that allows to detect roll backs (as far as I know, there isn't) ?

I do see that if the data have been modified then the Authentication is not provided anymore as the tag won't match. Or from a logical point of view:
$$\neg Integrity \implies \neg Authenticity$$
thus using the logical contraposition we get:
$$Authenticity \implies Integrity$$
Which seems to contradict Gilles' comment.

There are several concepts of integrity. Authenticity can be thought of as integrity of the association between data and its creator/modifier/sender. There is also integrity of the internal structure of data and multiple integrity definitions inside database management.

Note also, that cryptography cannot help to prevent integrity violations, it can merely help to detect them. Thus, when I mention that integrity is enforced cryptographically, it means that there are cryptographic means to detect unauthorized modifications, not to actually prevent any. In its strictest sense of the word, cryptography can not preserve integrity either.

Not all integrity concepts are straightforward to enforce cryptographically. Thus, the answer to the question depends on the exact definition of data integrity: if we consider the individual data item or content structure visible to Alice, the integrity of that is preserved.

However, considering the integrity of the history of versions of the database, integrity is not preserved.

If Eve has such access to the database that she is able to masquerade as Alice to the database, not much can be done. I assume in the following that Eve's access to the database does not include access to the database private keys or the authentication process between database and Alice.

To prevent unauthorized rollbacks such as these, versioning control is basically required. The database should have internal structures (metadata) indicating the latest update number, and Alice should include this number in her authenticated data. To enforce the association cryptographically, the database would need to sign the db-internal version number together with the version sent by Alice during each update. Bob can then compare the signed db-internal version to the version by Alice inside her authenticated data.

An alternative method to do this is, of course, blockchains. They are append-only databases, where rollbacks are not feasible. With blockchains, Eve's access to the database could be wider, and still rollbacks would be unfeasible. However, integrating blockchain-functionality into conventional databases would be a separate topic in itself - but if the rollback is a major problem in a database designed for some large-scale but well-defined function, blockchains might be worthwhile.


Writing encrypted data in place Is there a good reason not to write encrypted data in-place?

From the iOS 10 Security Guide:

Well, in this particular case, AES-GCM is being used.  As GCM adds authentication tags to the output stream, the size of the output stream is greater than the size of the input stream.  Writing the data in place would require a certain amount of buffering that could become difficult if the input stream is large enough.

Not to mention this helps defend against a power failure/crash in the middle of the encryption.  Imagine if the encryption process was stopped at some point.  When the system recovered how would it know where to start encrypting again?  With a separate encrypted stream the recovery process is easy - just start over at the beginning.


How random are permutations generated from Feistel networks with a small number of rounds? I wrote a toy pseudo-random permutation out of a Feistel network using blake2b. However, looking at the distribution of permutations for small n = 6, it's clearly not uniform unless many rounds are performed. I was under the impression that 3 or 4 rounds were sufficient. What am I missing?

The code below works as follows, to generate a random permutation of $n$ elements.

We find the smallest integer m such that $n \leq 2^{2m}$
We use blake2b in a Feistel network. Blake2b is keyed with a seed, which determines the random permutation, and is given a salt, which is the round number.
We compute a permutation on 2m bits integers using a Feistel network as described.
We transform that permutation into one that acts on $n$ elements by following the cycles, that is, iterating the permutation of $2^{2m}$ elements it until it produces a value < $n$.

To test this code, we then draw $100~n!$ pseudo-random permutation and perform $\chi^2$ test for an increasing number of rounds in the Feistel network. It's clear that for only 3-4 rounds, the permutations generated are not uniformly distributed.

import hashlib
import math
from collections import Counter
from scipy.stats import chi2

class Permutation():

    def __init__(self, n, seed, rounds=3):
        self.n = n
        self.rounds = rounds
        # n_bits is least integer suc that n <= 2**(2*n_bits)
        self.n_bits = 1 + math.floor(math.log(n, 4))
        self.seed = seed
        self.low_mask = (1 << self.n_bits) - 1
        self.high_mask = self.low_mask << self.n_bits
        self.digest_size = math.ceil(self.n_bits / 8)

    def __hash(self, msg, salt):
        h = hashlib.blake2b(msg, digest_size=self.digest_size, key=self.seed, salt = salt)
        return int(h.hexdigest(),base=16) & self.low_mask

    def __round(self, i, r):

        def to_bytes(m):
            b = 1 if m ==0 else 1 + math.floor(math.log(m, 256))
            return m.to_bytes(b, byteorder='little')

        low = self.low_mask & i
        high = (self.high_mask & i) >> self.n_bits
        low, high = high ^ self.__hash(to_bytes(low), salt=to_bytes(r)), low << self.n_bits
        return high + low

    def __p(self, i):
        result = i
        for r in range(0, self.rounds):
            result = self.__round(result, r)
        return result

    def __call__(self, i):
        j = self.__p(i)
        while j >= self.n:
            j = self.__p(j)
        return j

n = 6
fact = 1
for i in range(1, n + 1):
    fact *= i

for rounds in range(3, 10):
    cnt = Counter()
    for w in range(0,100 * fact):
        p = Permutation(n, seed = bytes('w=%d' % w, encoding='ascii'), rounds=rounds)
        ss = ''.join([str(p(i)) for i in range(0, n)])
        cnt.update([ss])

    x2 = sum((x - 100.0)**2/ 100.0 for p, x in cnt.items()) + 100.0 * (fact - len(cnt))
    print("n = %d,\trounds = %d,\tx2 = %f,\tchi2-cdf = %f" % (n, rounds, x2, chi2.cdf(x2, fact - 1)))

edit:
as a sanity check, I replaced blake2b with an actual random oracle

class RandomOracle():

    def __init__(self):
        self.known = {}

    def __call__(self, msg, digest_size, key, salt):
        entry = (msg, digest_size, key, salt)
        if  entry in self.known:
            return self.known[entry]
        else:
            v = os.urandom(digest_size)
            self.known[entry] = v
            return v

oracle = RandomOracle()

and this still produces non-uniformly random results...

The Luby-Rackoff theorem says that a 3-4 round Feistel network is a pseudorandom permutation for some sufficiently large block size.  As this paper by Patarin on Feistel networks with 5 or more rounds puts it:

  We will denote by $k$ the number of rounds and by $n$ the integer such that the Feistel cipher is a permutation of $2^n$ bits → $2^n$ bits. In [3] it was proved that when $k ≥ 3$ these Feistel ciphers are secure against all adaptative chosen plaintext attacks (CPA-2) when the number of queries (i.e. plaintext/ciphertext pairs obtained) is $m \ll 2^{n/2}$. Moreover when $k ≥ 4$ they are secure against all adaptative chosen plaintext and chosen ciphertext attacks (CPCA-2) when the number of queries is $m \ll 2^{n/2}$ (a proof of this second result is given in [9]).

If your domain size is very small, then indeed, your number of queries $m$ can easily exceed the bound.  If I understand your code right, you're doing cycle-walking on a Feistel network with a block size of 4, so by the time you hit $\sqrt{2^4} =$ four queries you've already hit that bound.

Incidentally this is why real-life format preserving encryption modes like those in NIST SP 800-38g use Feistel networks of 8 rounds (FF3) or 10 rounds (FF1).  Note that even then an attack was found against FF3 that required a revision to the mode.


What algorithm does PGP use to encrypt email? I know it uses RSA/DSA to create keys, but does it use that same algorithm for the actual cipher?

According to How PGP Works it uses a hybrid approach that generates a secret key for symmetric encryption.  The wikipedia page for GPG then indicates that CAST5, Camellia, Triple DES, AES, Blowfish, and Twofish are the supported ciphers.


Attack an stream cypher using 2 XORed LFSRs We know that the Key were generated by 2 16Bit LFSRs (output of both is XORed together -> key)

I already extracted a 64 Bit key sequence, but how can I calculate the polynom of the LFSRs (and the initialisation vector)? Since we have 2 LFSRs XORed together which means its non-lineary I can't use a Matrix to calculate the coefficients, or am I wrong?

I hope somebody understands my problem and can give me some hint.

the known keystream: 1010 1110 0000 0011 1111 0010 1011 1001 0001 0100 1101 0111 1001 0011 1110 1101

The fundamental property that you will use is that the output of an $A$-bit LSFR (using the $A$-bit feedback polynomial $P$) xored with the output of a $B$-bit LSFR (using the $B$-bit polynomial $Q$) is the same as the $A+B$ bit LSFR with the feedback polynomial $P \cdot Q$.  And, don't forget, when you multiply the feedback polynomials, you use polynomial multiplication modulo 2.

Hence, we know your output can be generated by a 32-bit LSFR; the obvious thing to do is use the Berlekamp–Massey algorithm to find the LSFR, and once you have the feedback polynomial, factor it.

If you get a 32 bit LFSR with two 16 bit prime factors, that immediately gives you your answer.

If it factors into smaller factors, well, you need to search for a way to combine the smaller factors to two 16 bit polynomials.  Here, you use the fundamental property in the other direction; for example, if the polynomials you find are 3, 7, 9, and 13 bits; then the obvious way to combine them are the 3 and 13 bit polynomials (which multiplied make up a 16 bit LSFR), and the 7 and 9 bit polynomials (which multiplied make up another 16 bit LSFR)

If BM finds a LSFR which is smaller than 32 bits, well, there are a couple ways for that to happen (after all, the fundamental property says that there exists a 32 bit LSFR that generates the output; it doesn't say that it's the smallest possible LSFR).  One possible reason for this is that a factor LSFR might be initialized to zero; in that case, that LSFR won't contribute anything.  Another reason would be that the two polynomials might share a factor.  In any case, what that means is that you likely won't be able to come up with a unique answer as to the original polynomials.


multiple keys via HKDF - whats better, one or two applications of HKDF-extract Assume for the sake of the question that I have two variable-length bit strings, each with 128 bit cryptographic randomness, and I want to extract two 128 bit keys via HKDF-SHA256.

Which alternative is better (if any), and why?

Use a single HKDF-extract on the concatenation of the two strings, and two HKDF-expands with different info strings to get two 128 bit keys.
Use two HKDF-extract operations, one for each bit string, and use a single HKDF-expand on each to get two 128 bit keys.

Or in other words, is it better to HKDF-extract on a longer IKM string and use multiple HKDF-expands, or is it better to use HKDF on independent but shorter IKMs.

My intuition tells me that, if my randomness strings are really as good as I claim, then two independent HKDF extracts are better, but using a single one on the concatenation is, in practice, just as safe, and safer if my input randomness is not actually as good as assumed, so two HKDFs might be more robust in practice.

Realistically, it probably doesn't matter, if all of your premises are accurate.

If it were me, I'd probably concatenate the inputs, then apply a HKDF to the concatenation to derive two keys -- but honestly, it's unlikely to matter.  This is very unlikely to be the weakest link in your system.  Pick something that's easy to implement and easy to understand, and move on: focus your energy on some other aspect of your system.


Error Detection/Correction Code-Then-Encrypt I've just studied about the error correction schemes and encryption.

First rule when using EDC/ECC is to first encrypt and then calculate them, and the major motivation we were told is that "EDC/ECC Then Encrypt causes KPA attacks on GSM protocols to be Ciphertext Only Attacks, because it adds much redundancy to the plaintext". source (slide #50)

However I couldn't find any example or explanation for that, so I'd appreciate any help regarding this.

The valid advice of adding an Error Detection or/and Correction Code after encryption rather than before has two unrelated justifications:

If the cipher is weak, adding redundancy to the plaintext (as EDC/ECC before encryption does) might allow attack. In particular, it is possible to test if a key is valid by checking if the redundancy in tentatively deciphered plaintext is valid (a refinement of that is used to break the GSM cipher in the question's reference). However, that consideration is not a concern for good modern ciphers, since these should be resistant to chosen-plaintext attack.
EDC/ECC is typically optimized to detect/correct errors affecting few bits of the transmitted message. If encryption is applied after EDC/ECC, and correspondingly decryption applied before EDC/ECC on the receiver side, then errors on the transmitted message tend to get amplified by decryption (depending on the cryptosystem, as detailed hereafter). When this happens, desirable EDC/ECC properties such as insurance of detecting/correcting any at-most-N-bit error in the transmitted message tend to be lost, or greatly reduced.

for stream ciphers, CTR mode, and OFB mode, only errors on setup parameters or the IV will get amplified, but the effect of any such error will ruin the whole decrypted message;
in ECB mode, a 1-bit error is amplified to potentially one block;
in CBC mode (resp. CFB mode), a 1-bit error is amplified to potentially one block, and 1 bit in the next (resp. previous) block;
other modes exist such that error is amplified to the message after the error, or to the whole message;
with authenticated modes, practically any error will prevent decryption.


Does NTRU decrypt correctly now? The NTRU public-key cryptosystem has a lot of interesting properties (being resistant to quantum computer attacks, being standardized by several important bodies), but it also has a pretty unique property:

  The decryption algorithm does not always work.  Sometimes it just gives wrong answers.

Has this been fixed?  Is it really a cryptosystem if having the private key is insufficient to decrypt the encrypted messages?

For instance, from Howgrave-Graham et al. (2003) one reads,

  “First, we notice that decryption failures cannot be ignored, as they happen much more frequently than one would have expected. If one strictly follows the recommendations of the EESS standard [3], decryption failures happen as often as every 212 messages with N = 139, and every 225 messages with N = 251. It turns out that the probability is somewhat lower (around 2−40) with NTRU products, as the key generation implemented in NTRU products surprisingly differs from the one recommended in [3]. In any case, decryption failures happen sufficiently often that one cannot dismiss them, even in NTRU products.”

Nick Howgrave-Graham, Phong Q. Nguyen, David Pointcheval, John Proos, Joseph H. Silverman, Ari Singer, and William Whyte. "The Impact of Decryption Failures on the Security of NTRU Encryption", Advances in Cryptology - CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings,
Lecture Notes in Computer Science, 2003, Volume 2729/2003, 226-246,
DOI:10.1007/978-3-540-45146-4_14

The likelihood of a decryption failure can be made arbitrarily small. IEEE P1363.1 says in appendix A.4.10:

For ternary polynomials with $d$ $+1$s and the same number of $-1$s, the chance of a decryption failure is given by [B30]:
$$\operatorname{Prob}_{(q, d, N)}(\text{Decryption fails}) = P_{(d, N)} \left( \frac{q - 2}{6} \right)$$
where
$$P_{(d, N)}(c) = N \times \operatorname{erfc} \left( \frac{c}{\sigma\sqrt{2N}} \right)$$
and
$$ \sigma(d, N) = \sqrt{\frac{8d}{3N}}$$

where $\operatorname{erfc}(x)$ is the Gauss error function.
As a practical example, for the EES1087EP2 parameter set where $N=1087$, $q=2048$, and $d=120$, the failure probability is $5.62·10^{-78}$, which is a bit less than $2^{-256}$. Those parameters have been chosen for a $256$-bit security level in general, and the failure probability is also smaller than $2^{-256}$. So exploiting a decryption failure requires just as much work as breaking other parts of the system.
Ps. The [B30] reference is to the paper "Hybrid
Lattice reduction and Meet in the Middle Resistant Parameter Selection for NTRUEncrypt" by P. Hirschhorn, J. Hoffstein, N. Howgrave-Graham, J. Pipher, J. H. Silverman and W. Whyte.


How to encrypt a symmetric key with a shared secret? I am reading this article (pdf) on the Diffie–Hellman key exchange. It states the following:

  At this point, the Diffie-Hellman operation could be considered complete. The shared secret is, after all, a cryptographic key that could encrypt traffic. But completion at this point is very rare, because the shared secret is an asymmetric key by its mathematical nature, and all asymmetric key systems are inherently slow.

  ...

  In most real applications of the DH protocol (SSL, TLS, SSH, and IPSec in particular), the shared secret encrypts a symmetric key for one of the symmetric algorithms, then transmits it securely, and the distant end decrypts it with the shared secret.

I'm trying to understand the point in an authentication scheme where two parties have exchanged keys with Diffie-Hellman, and now have the "shared secret".

How is the shared secret asymmetric if the "shared secret" is used to both encrypt and decrypt?
How exactly do i encrypt an AES key with the "shared secret" key?
Is it not possible to directly create a symmetric AES key with the DH key exchange?

How is the shared secret asymmetric if the "shared secret" is used to
  both encrypt and decrypt?

By its way of creation you can call it asymmetric. There are asymmetric public keys involved in agreeing on the shared secret, so it's asymmetric. You could also call it asymmetric as the knowledge of the shared secret is asymmetric. Only the endpoints know the shared (private) secret while everybody else (in the middle, like ISPs) only knows the public keys.

  How exactly do i encrypt an AES key with the "shared secret" key?

Usually, you don't. You feed the shared secret into something called a "key-based key derivation function" (KBKDF), which will accept your shared secret (a large number) and generate cryptographic keys (for use with AES for example) from that.

  Is it not possible to directly create a symmetric AES key with the DH
  key exchange?

You could do it. However, AES accepts at most 256-bit long keys. If you end on a 256-bit shared DH secret, then the group parameters are really weak and it's easy to find the shared secret just given the public keys.


Possible CPA or CCA attack when using AES-CBC mode under the following situation? Both client and server know a shared key in advance. Both sides us EVP_BytesToKey() derive a pair of same key and same IV. Then, client and server start transferring data encrypted by AES-CBC mode using this pair of key and iv.

Is there any possible CCA or CPA? Should I use randomized IV every time? Is it safe to transfer IV in plaintext with the encrypted data?

Can CPA be avoided if I use randomized IV every time? How should I mitigate CCA?

TLDR: Don't invent your own protocol, use an existing one.

Reusing an initialization vector with the same key is always a problem, even if the attacker is read-only. For CBC, you can see whether a beginning part of one message is the same as the beginning part of a different message (and you get to know the length of the common prefix, on block-level).

With a CPA (chosen-plaintext attack) and an IV known before chosing the plaintext, the attacker can (with several tries) decrypt about everything. This was used in the BEAST attack.
With a constant (but unknown) IV, a possible attack I can imagine now is guessing prefixes of the unknown plaintext and encrypting it, to see if they match.

All of these are prevented by using a random IV for each message, chosen after the plaintext of that message (or at least the first plaintext block) is given to the "encryption machine". This IV can be sent with the message itself, commonly before the first ciphertext block.

As far as I can see, a CCA (chosen-ciphertext attack) does not gain much from the fixed IV: you can still do a padding oracle attack by modifying the ciphertext block before the last block of a message and see if the message decrypts properly (assuming a padding scheme like PKCS 7), or can be read by the receiving application.

To prevent most CCAs, use a MAC together with your encryption (in the encrypt-then-mac order, i.e. calculate the MAC from the ciphertext including the IV and maybe other message meta data you might want to protect), and check the MAC before starting to decrypt. You can derive the MAC key from the same secret as you derive the encryption key. This has the side effect that it does not just protect the privacy, but also integrity/authentication.

There might be a lot more weaknesses hidden in your example protocol. Don't invent your own, use an existing one. For example, TLS with a preshared-secret ciphersuite should work for your needs (as much they are outlined in the question).


What is the intuition of canonical-embedding in homomorphic encryption based on RingLWE? In the cryptosystem based on Ring-LWE, the noise amount is measured by canonical-embedding norm.
What is the intuition behind canonical-embedding?

Consider the $m^{\text{th}}$ cyclotomic ring $R = \mathbb{Z}[\zeta] \cong \mathbb{Z}[X]/\Phi_m(X)$, where $\zeta$ is the $m$th primitive root of unity and $\Phi(X)$ is the $m$th cyclotomic polynomial. There are many possible bases for this ring, including the power basis $\{ \zeta^0, \zeta^1, \ldots, \zeta^{n-1}\}$, where $n = \phi(m)$ (Euler totient function).

In lattice crypto, it is useful to have a notion of a short ring element. The metric used is often a function of the coefficients of the polynomial in $R$. However, different bases of this ring can result in different coefficients, including cases where 'short' elements have long coefficient vectors.

It is necessary, then, to define geometric quantities independently of the basis representation of $R$. This the use of the canonical embedding $\sigma$, which creates a map $\sigma\colon R \mapsto \mathbb{C}^n$ that is independent of the representation of $R$.
$$ a \in R,  \ \ \sigma(a) = \left<a(\zeta_m^i)\right> \ \ \text{for all } i \in (\mathbb{Z}/m\mathbb{Z})^*
$$We can now define all geometric quantities with respect to the canonical embedding. This results in a 'canonical embedding norm' which is really just any norm taken with respect to the canonical embedding. E.g. For $a \in R$, $||a||_2^{can} = ||\sigma(a)||_2$ or $||a||_\infty^{can} = ||\sigma(a)||_\infty$

There are many other useful properties of the canonical embedding, such as coordinate-wise addition and multiplication.


Any weakness when performing SHA-256 repeatedly? Is it significantly easier to reverse a SHA-256 hash if you know that the input was a 32 byte output of SHA-256?

I assume for most outputs of SHA-256 there will be zero, one or two possible 32 byte inputs.

Mapping and storing all of the values is infeasible, but I am still worried that constraining the input to being exactly 32 bytes may weaken SHA-256.

Is this a valid concern?

Answer

No, that would not be possible. It would be very weird indeed if a hash was suddenly invertible if the input was of a specific form - it would basically mean that the hash would be broken. Iterating over all the possible values of those 32 bytes is certainly not an option either.

Peculiarities

That does not mean that such a structure doesn't have it's peculiarities though, the first link provided by mikazo is a good summary of what to expect.

If you want to avoid such peculiarities then I would suggest you follow the suggestion by CodesInChaos to use a HMAC construct with a fixed key instead of SHA-256 directly. As e.g. length extension attacks not feasible with SHA-3 (Keccak) you can probably use that without reverting to a HMAC.

Notes

The inner state of SHA-2 is basically the output (after padding & inclusion of the message size); so a 32 byte input is certainly not an issue in itself, as the inner state is exactly the same size.
Your scheme may have some properties that can be compared with a hash based PRNG


Proper number of salt bytes for Rfc2898DeriveBytes/PBKDF2 I know that .NET's Rfc2898DeriveBytes requires at least 8 bytes of salt, but how many bytes are ideal?

When a user is created, or changes their password, my server stores a new random salt for that user, and a "hash", which is really just some number of bytes from Rfc2898DeriveBytes (ed: .NET's implementation of PBKDF2), using the user's password and the salt, and 5000 iterations.

My client app connects to the server via SSL, sends the user's user name, the server sends the salt for that user, the client calls Rfc2898DeriveBytes with the user's password and the salt, and sends that "hash" to the server for authentication.  If the server receives an invalid user name, it returns a random salt, so that the client doesn't know whether the user name or the password is invalid, and so some time is wasted to hamper hacking.

My understanding about salt is that it's really only intended to get different keys for the same password, which would lead me to think that 8 random bytes should suffice, but since I'm sending it over SSL, I'm wondering if a longer salt would increase security somehow.

Besides the number of salt bytes, how many "hash" bytes would be best?

Short Answer: 8 bytes are fine

Longer answer: The point of the salt in a password hash is, to prevent the precalculation of a list of hashes, usually done in the form of rainbow tables. If someone still wants to do precalculation, he will have to build one rainbow table for every single possible salt value, thus you are increasing the storage requirements of your adversary.

With a 8 byte salt, the adversary will need to build $2^{64} \approx 10^{19}$ tables. The size of those tables varies depending on the types and length of password you are trying (you can find a nice overview here), but you typically expect something in the 2-3 digit gigabyte range ($10^{11}-10^{12}$ byte). Putting this together, storing rainbow tables for 8 bytes of salt would require something in the range of $10^{30}$ bytes, which is completely impossible.


Using an integer ring with RSA I'm new to RSA and instead of using RSA to encrypt a symmetric encryption key to encrypt data with (although it might help to understand) I would like to use an integer ring with RSA.

My question is what are the minimum/maximum values of $P$ before being turned into $E$ cannot be recovered, and how can I encrypt with a ring, i.e $1 \leq P \leq 26$ and $1 \leq E \leq 26$

It seems to be asked textbook RSA with plaintext and ciphertext in the set $\{1,2,\dots,25,26\}$. That's wholy unreasonable, for in RSA the public key gives the mapping of plaintext to ciphertext, and with such small set it is trivially inverted. Let's see how it can be done nevertheless.

Textbook RSA operates on the set $\{0,1,\dots,N-1\}$ with $N$ the product of distinct primes. In order to use the desired set, I propose to use $N=26=2\times13$, and assimilate $0$ with $26$. We can now use textbook RSA, where encryption goes $C=P^e\bmod N$ ($P$ is the plaintext, $C$ is the ciphertext that the question calls $E$, and $e$ is the public exponent).

$\lambda(N)=\operatorname{lcm}(1,12)=12$, the public key $e$ must be coprime to that, and $e\times d$ must be one above a multiple of $\lambda(N)$, therefore we must have $e$ one of $1$, $5$, $7$ or $11$, with $d=e$ (within some multiple of $12$). $d=e$ means encryption and decryption are the same operation. Beside, ciphertext and plaintext are identical for $e=1$.

For example, with $e=5$, the plaintext $P=2$ is enciphered into $C=P^e\bmod N$, that is $C=2^5\bmod26$, that is $C=6$. And $C=6$ is deciphered into $P=C^d\bmod N$, that is $P=6^5\bmod26$, that is $P=2$.

We end up with a dumb mono-alphabetic substitution cipher with only four possible keys, one of which leaving plaintext unchanged, all with three fixed points $1$, $25$, $26$, and such that encryption and decryption are the same.


How do I classify my RSA encryption strength? So I generated 2 1024 bit prime numbers, I generated N and got a 2048 bit number, does that make my encryption 2048 bit or 1024 bit?

The key length specified for RSA is the length of the modulus $n$ in bits. Thus, if you generate $n=p*q$ and get a 2048 bit modulus, your RSA encryption is 2048 bit.


CMAC vs HMAC security strength From the perspective of a Birthday Paradox attack, isn't it true that CMAC based on AES-128 is weaker than HMAC-SHA-1? The attack on CMAC-AES-128 requires about $2^{64}$ operations whereas the same attack on HMAC-SHA-1 requires $2^{80}$.

Regardless from the comparison of the CMAC-AES-128 with HMAC-SHA-1 it seems to me that running the birthday attack with about $2^{64}$ operations on CMAC-AES-128 is "somewhat trivial", so it can't be considered to be secure anymore. DES that has a key size of 56 bits can be broken easily with $2^{56}$.

What are your thoughts?

Comparing a brute force attack on DES (with $2^{56}$ operations) to a birthday attack on CMAC (with $2^{64}$ operations) would appear to be an apples-to-Volkswagen comparison; they are assuming two things are similar, when they really aren't.

The brute force attack on DES involves obtaining a single plaintext/ciphertext block pair, and then going through the possible DES keys, and looking for a key that encrypts that plaintext block into that ciphertext block.  The key here is that, once the attacker does have that plaintext/ciphertext pair, he no longer needs anything else from the attackee Alice -- he runs all these trial encryptions on his own hardware, and if he feels the search isn't going fast enough, he just buys more hardware.  The speed of the attack is limited only by the attackers budget.

On the other hand, the birthday attack on CMAC involves asking Alice for the MAC of a huge number of messages (and then digging through those MACs to find a duplicate).  The key point is that we need a great deal more from Alice; it is not sufficient to obtain a limited number of bits, instead if we need to generate the MAC of $2^{64}$ messages, that means that we need to present those $2^{64}$ messages to Alice, and we need her to compute the MACs of all those messages.

That's the key point: Alice will compute those MACs only so fast, and the attacker cannot speed it up by parallelism or anything.  If Alice is able to generate only 1 MAC per nanosecond, that means that it'll take over 500 years to generate the MAC for all $2^{64}$ messages.

In summary: any attack that requires $2^{64}$ exchanges with Alice cannot be considered "somewhat trivial"; even if a brute force attack with the same abstract effort would be.


Homomorphic OR operations Is there an encryption scheme that provides efficient homomorphic OR operations at the ciphertext space? Of course any fully homomorphic encryption can be used but I do not require or want additional homomorphic operations.

For any $x,y$ represented by $\{0, 1\}$, $x \lor y = 1 - (1-x)(1-y)$. It follows, any one-multiplication homomorphic scheme would do. It also follows, just additively homomorphic scheme would be not enough.


ed25519 ssh public key is always 80 characters long? I am creating some ssh keys using ed25519, something like:

$ ssh-keygen -t ed25519
$ ssh-keygen -o -a 10 -t ed25519
$ ssh-keygen -o -a 100 -t ed25519
$ ssh-keygen -o -a 1000 -t ed25519

But I notice that the output of the public key is always the same size (80 characters):

ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIB8Ht8Z3j6yDWPBHQtOp/R9rjWvfMYo3MSA/K6q8D86r
ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAILYAIoV2OKRSh/DcM3TicD/NK/4TdqwwBPbKgFQKmGZ3
ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAICpuH/fqCFLbAConChyVH6rZzSaxlnHSwQk6qvtPsf5E
ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAICip4hl6WjuVHs60PeikVUs0sWE/kPhk2D0rRHWsIuyL

Is there an option/param like when creating RSA keys that may influence the length of the key, or by design will always be 80 (68 removing the ssh-ed25519) characters?

Is there an option/param like when creating RSA keys that may
  influence the length of the key, or by design will always be 80 (68
  removing the ssh-ed25519) characters?

No, there can't be any such option.
First note that only the last 43 characters of your sample public keys are variable. As this is Base64-encoding, they can at most encode $43\cdot 6=258$ bits of information, which is enough to fit the 255-bit $y$-coordinate and 1-bit for the sign of the $x$-coordinate (this is called point compression).

Next note, that EdDSA (the signature scheme in use here), requires a group to work with and Ed25519 is the variant of EdDSA that fixes this group to the points on the Edwards-25519 curve (which operates on a 255-bit field). Now because your group is fixed and your public key is a point of the curve, it can only possibly have a maximal length of 256-bit (or 80 characters in SSH encoding).

Now there are "more secure" curves (eg Ed448-"Goldilocks") available than the one used by Ed25519 which have longer keys, but the signature scheme wouldn't be called Ed25519 anymore...


Real world performance of (still theoretical) Grover's Algorithm Grover's Algorithm is a quantum algorithm for searching "black box" functions and could be used to reduce the search space for things like symmetric ciphers and hashes by as much as half (quadratic speedup). This would effectively reduce e.g. SHA-256 to 128 bits or AES-128 to 64 bits.

... in theory, of course. Nobody's built a QC that can run Grover's Algorithm yet and I doubt one will exist that can do it for anything other than toy problems for quite a while.

That being said I have a question about how Grover's algorithm works.

My understanding is that in Grover's algorithm there is a classical step in which the classical function must be evaluated for a given point to test if that point is the correct answer.

If that's the case, could you practically limit the performance of a post-quantum search by designing an intentionally expensive and inefficient algorithm? I'm thinking of some of the memory-hard compound hash monstrosities like CryptoNight that are used in the cryptocurrency world as block hash / mining functions. Would a slow complicated memory-hard algorithm effectively limit the performance of Grover's algorithm in the real world by making each iteration terribly slow? So even if you get quadratic speedup, 2^64 or 2^128 searches of something that takes 250ms of classical compute time per search would still take an absurd amount of time.

Thoughts?

You are right. Indeed, Grover's algorithm has to evaluate the function that is attacked in each iteration (actually the algorithm complexity measure in which you get the square root speed-up is query complexity). And of course, if you make that function more expensive you also make an attack more expensive -- classical as well as quantum. However, here we are switching from asymptotic statements to exact statements. These tend to depend on the exact architecture of a device. E.g., many functions will have different speed on different CPUs even if the clock speed is the same. The problem is that we do not yet know which architecture a future quantum computer will have.

The common thing in research papers is to measure exact complexity of quantum algorithms in terms of T-gate depth. However, this makes two assumptions. First, that the gate set used will be CNOT, T, and second, that T gates dominate execution time (which in this setting is pretty likely). This makes it hard to determine which kind of functions will be especially slow on a quantum computer.

Moreover, also the relation between cost of memory compared to cost of execution time is still open for quantum computers. Hence, it is not clear if a memory-hard function is better than a function that is slow, independent of the available memory. There exist architectures for qubits where keeping state is a lot easier than manipulating it. In these cases the bottleneck would probably be speed, not memory. However, this is all just a look into a crystal ball..., at most confined guessing.


Why is a number of shares that is greater than a threshold required to construct secret? In this][1] paper of Asmuth–Bloom threshold SSS, the algorithm is as follows:
Shares Distribution
To distribute n shares of a secret $K$ among the set of participants
$P = \{ p_i : 1 ≤ i ≤ n\}$, the dealer D does the following:

A set of integers $\{ p, m_1 < m_2 < · · · < m_n \}$, where $0 ≤ K < p$, is chosen subject to the following conditions:

$\gcd(m_i , m_j)=1$ where for $i\neq j$
$\gcd(p , m_i)=1$ ,for all $i$,
$\prod \limits_{i=1}^{t}m_i > p \prod \limits_{i=1}^{t-1}m_{n-i+1}$

Let $M =\prod \limits_{i=1}^{t}m_i$. The dealer computes $$y = K+ap,$$
where a is a positive integer generated randomly subject to the condition that $0 ≤ y < M$

The share of the $i^{th}$ participant,$1 ≤ i ≤ n$, is $$y_i = y~ mod ~m_i$$

Secret  Construction
Assume $C$ is a coalition of $t$ participants to construct the secret.
Let $M_C =\prod \limits_{i=1}^{C}m_i$

Given the system $$y \equiv y_ i \mod m_ i $$  for $i ∈ C$, solve y in $GF(M_C  )$ uniquely using the CRT.

Compute the secret as
$$K = y \mod p$$

According to the CRT, y can be determined uniquely in $GF(M_ C)$ . Since $y < M ≤ M_C$ , the solution is also unique in $GF(M)$.
In the [this] [2] original paper the author given to  recover $K$ , it clearly suffices to find y. If $y_{1},y_{2}.......y_{t}$ are known, then by the Chinese remainder theorem modulo $M_C =\prod \limits_{i=1}^{C}m_i$ .
As  $M ≤ M_C$ this uniquely determines $y$ and thus $K$ . On the other
hand, if   only $t-1$ shares were known, essentially no information about  the secret can be recovered

How to prove formally that the number of participants lesser than threshold number $t$ cannot get secret?
[2]:https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1056651
[1]: http://pdfs.semanticscholar.org/440d/fa8ab99301d4ea3a8b19c0748575915aef15.pdf

To show that the adversary could not retrieve the secret, you can show that two different secrets will implies the same shares, and then an adversary that has access to these shares could not retrieve the secret.

To show that the adversary has no bit of information about the secret when he has $t'$ strictly less than $t$ shares, you can show that if you take two different $K_1$ and $K_2$, and compute the cardinality of $a$'s (for $k_1$ and for $K_2$) such that you obtain the $t'$ shares. Because they are the same, and because $a$ is uniformly picked at random, you deduce the perfect secrecy.
First I'm claiming that $a$ is chosen unifromly at random in $\{0, \dots, M-1 \}$ (I can give you more details, if you aren't not convinced.
Let $\left(y_1, \dots, y_{n-1}\right)$ a vector of shares.\newline
We call $\psi$ the isomorphism given by the chinese remainder theorem from $\mathbb{Z}_{m_1} \times \dots \times \mathbb{Z}_{m_n} \times \mathbb{Z}_{p}$ to $\mathbb{Z}_{Mp}$, and $\phi$ the invert isomorphism.

$$Card \{a \in \{0, \dots, M-1 \} / \exists \left(z, z'\right) \in  \mathbb{Z}_{m_n} \times \mathbb{Z}_{p}, \phi \left(K_1 + a*p\right) = \left(y_1, \dots, y_{n-1}, z, z'\right)\}$$

$$ = Card \{a \in \{0, \dots, M-1 \} / \exists \left(z, z'\right) \in  \mathbb{Z}_{m_n} \times \mathbb{Z}_{p}, \phi \left(K_1\right) + \phi\left(a\right)*\phi\left(p\right) = \left(y_1, \dots, y_{n-1}, z, z'\right) \}$$

$$ = Card \{a \in \{0, \dots, M-1 \} / \exists \left(z, z'\right) \in  \mathbb{Z}_{m_n} \times \mathbb{Z}_{p},  \phi\left(a\right)*\phi\left(p\right) = \left(y_1 - \left(K_1 \mod m_{1} \right), \dots, y_{n-1} - \left(K_1 \mod m_{n-1}\right), z - \left(K_1 \mod m_{n}\right), z' - \left(K_1 \mod p\right) \right) \}$$

Because $p \mod p = 0$, we deduce, that necessarily  $z' = K_1 \mod p$ (and such $z'$ exists).

$$ = Card \{a \in \{0, \dots, M-1 \} / \exists z \in  \mathbb{Z}_{m_n},  \phi\left(a\right) = \left(\frac{y_1 - \left(K_1 \mod m_{1} \right)}{p \mod m_{n-1}}, \dots, \frac{y_{n-1} - \left(K_1 \mod m_{n-1}\right)}{p \mod m_{n-1}}, \frac{\left(z - \left(K_1 \mod m_{n}\right)\right)}{p \mod m_n}, 0\right) \}$$

$$ = Card \{a \in \{0, \dots, M-1 \} / \exists z \in  \mathbb{Z}_{m_n},  a = \psi\left(\frac{y_1 - \left(K_1 \mod m_{1} \right)}{p \mod m_{n-1}}, \dots, \frac{y_{n-1} - \left(K_1 \mod m_{n-1}\right)}{p \mod m_{n-1}}, \frac{\left(z - \left(K_1 \mod m_{n}\right)\right)}{p \mod m_n}, 0\right) \}$$.

This cardinal doesn't depend of $K_1$ (it's equal to $m_n$).


A periodic PRNG based on hash function? I need a PRNG which provides 128 bytes numbers.

Let's say that given a symmetric key $K$ and an internal state $s$ I use the PRF HMAC-SHA512 this way:

The output is PRNG($K, s$) = HMAC-SHA512$_K$($s$ || 0x01) || HMAC-SHA512$_K$($s$ || 0x02) where $||$ represents a concatenation. The next state is $s_{i+1}$ = HMAC-SHA512$_K$($s_i$ || 0x03) || HMAC-SHA512$_K$($s_i$ || 0x04).

I am wondering if my PRNG can be periodic?

I mean, is it possible that given the initial internal state of the PRNG noted $s_0$ and the symmetric key $K$, to have an integer $n$ such that $s_n = s_0$?

Any PRNG with a finite state size is eventually periodic. The maximum period possible is $2^n$ for an $n$-bit state, but the average with a well mixed state is $2^{n/2}$.

Here the hash function used is SHA-512, but the state is 1024 bits. A first guess would be a period of $2^{512}$, rather than the $2^{256}$ mephisto gives.

Let's look at the cycles. Both halves of the state are generated with HMAC-SHA512, so they would enter cycles of about $2^{256}$. However, because the inputs are different, they have their separate cycle structure. The two cycles are likely to be different lengths. The overall cycle is about as long as the least common multiple of the two lengths.

Two uniformly distributed random numbers have a small expected GCD, meaning the LCM would be close to their product. The lengths here are not uniformly distributed, but I believe the same is still more or less true. So the cycle length should be close to the $2^{512}$ expected with a 1024-bit state.


Has there ever been more then a theoretical difference between preimage resistance and second preimage resistance? In other words, has there ever been a point in time in which having the content of a message has actually helped break a hash function?

Yes, it has happened. If you look at the SHA3 hash zoo, there are a number of hashes who has the best attack listed as "2nd preimage".

One general place this can occur is if you have a hash function with a weak message compression step, but a fairly strong finalization step.  Here, we might not be able to generate first preimages (because we don't know what needs to be presented to the finalization step to generate that image), but we may be able to do a second preimage (because we attack the weak message compression, and generate the exact same data to the finalization).


How would I make a secret notation alphabet more secure? Disclaimer: I was looking for a place to ask this question on SE and this site seems to be the most fitting. If this question doesn't belong here, feel free to redirect me.

Just out of boredom and curiosity, I've started to develop my own secret notation alphabet (for manual use, no computers involved). It's based on Elian Script, although I scrambled the letters in a non-obvious way (no ROT13 or similar) and expanded on the form a bit. I still feel as if it wouldn't be that hard to "decode" my notations, though.

So my questions would be:

what further methods are there for making an alphabet 'safer', except using different letters and scramble them?
what methods are there for text-encryption that could be used for manual everyday use? (like leaving out punctuation, for example.)

A Michael Kjörling notes, what you basically have is a monographic substitution cipher.  These are generally easy to crack using frequence analysis; for example, if we know that the underlying text is in English, we can be fairly sure that the two most frequently occurring symbols correspond to the letters T and E (and that any symbol that occurs unusually often between them is probably H).

To make your cipher stronger against frequency analysis, you want to somehow make the symbol frequencies in your ciphertext as uniform (and as uncorrelated with nearby symbols) as possible.  There are many ways to do that, but the requirement that the resulting alphabet should still be something one could learn to write fluently rules out most of them.  Still, there are some things you could do:

Come up with multiple (preferably completely different-looking) symbols for the most common letters in English.  The number of symbols per letter should be approximately proportional to its frequency.  Alternate between the symbols randomly, or according to some rule of your choosing, or just as you feel like.
Conversely, consider merging some rare letters together under the same symbol(s).  This works best for letters that have shared historical roots, such as I / J or U / V / W.
Consider making up separate symbols for common or distinctive letter combinations like TH, QU or ING.  These should also have multiple variants according to their frequency.  Some particularly common words should probably have dedicated symbols.
Conversely, consider encoding rarer letters using two symbols, e.g. as the symbol for a more common similar letter plus a modifier symbol (which could be used for multiple letters to make it more common, and which could also have a stand-alone meaning or just be used as "chaff").
Introduce lots of stylistic variations to your symbols, so that it's hard for a would-be decipherer to know if two symbols are the same or not.  This is most effective if some variations (like line length, or the presence of dots or loops) are essential for distinguishing some symbols but vary arbitrarily for others.
Make it hard to tell where one symbol ends and another begins, e.g. by allowing symbols to be combined or written in unusual order.
Introduce random meaningless "chaff" symbols into your writing.
Make lots of misspellings, either more or less systematically (e.g. randomly interchange S / Z or C / K in words where it doesn't matter, spell some words phonetically or in "txt spk"), or just drop or interject random letters into words where it doesn't introduce ambiguity.
Use idiosyncratic jargon, so that even if the text is decrypted, it may still not make sense.
If you don't use dedicated symbols for common words like "the", consider substituting them with other words.  A substitution like, say, "the" → "cat" could really frustrate a cryptanalyst.
Drop unnecessary common words entirely.  You don't really need all those articles, do you?

Edit: Last but not least — don't write too much.  With enough ciphertext to analyze, any combination of these measures can still be cracked by a clever, skilled and persistent cryptanalyst.  Your best defense is making sure that there simply won't be enough text for a reliable analysis to be possible.

Oh, and never write down anything both in cipher and in plain.  Even a short bit of known plaintext in the hands of a skilled cryptanalyst can make all these tricks useless.  Look up e.g. the Rosetta stone for a historical example.


Does anyone know an easily creatable asymmetric cryptosystem for usage in VDF? I've read multiple papers about VDFs (1, 2, etc.).
I look for a lighter alternative to El-Gamal regarding cryptosystem creation.
It can be anything exotic too, but it would be nice to have at least some security.

(Let's assume I know what I'm doing; This is my small research)

I would like to know if anyone knows a cryptosystem that could fulfill these criteria:

Creation of public key with 100% guarantee that private key will exist (Or open key validation would work) (I want to pick a valid public key and compute private key by brute force later)
Light creation of cryptosystem. There shouldn't be a need to factor large integers or derive difficult parameters. It could have a small amount of calculations, but I want to avoid brute-force.

ElGamal has some good parts, but won't work for my case:

El-Gamal allows creation of public keys without private ones. So if the generator operates on the whole cyclical group then we can have shorter keys too.
Integer factorization is one of the ways to create an efficient generator. I want to avoid factorization.

ECC is even harder to set up:

To derive a new ECC cryptosystem I have to choose several parameters and a big prime number. I want to create cryptosystems on the fly so it's not very convenient. Let's say it may be solvable somehow (for the sake of this example) -- prebuilt cryptosystems.
Public key generation, though, won't work for 100%. As elliptic curve public key points can't be validated such as ElGamal's because we never operate in the whole group.
Also this means that order of the base point has to be brute-force-adjusted to have the maximum number of points in a group. Because elliptic curve (under a field) contains point count related to it's base point. So this creates a brute-force need when creating a cryptosystem. I would like to avoid it.

RSA

Won't work because there is no way to validate the public key.

NTRUencrypt

Private key has to be of a certain form so that polynomial multiplication would work during decryption (wiki). I would like to know if it's possible to use it as the basis for this kind of VDF.

I would like to get any guidance or even samples of cryptosystems that would work under such scenario.

Thanks.

The issue of having to factor a large number in ElGamal appears only if you set the group order to be an arbitrary prime $p$. In this case, to find all subgroups of $\mathbb{G}$, you need the factorization of $p-1$.

However, this issue entirely disappears if you take $p$ to be a safe prime, i.e., a prime number of the form $p = 2q+1$, where $q$ is also a prime. Finding such primes is not so hard, and testing primality does not require to compute any expensive factorization.

Once you have $p$, sets $\mathbb{G}$ to be the sugroup of quadratic residues (i.e., squares modulo $p$) of order $q$ in the field of order $p$. Note that every quadratic residue (except $1$, of course) generates the full group of quadratic residues, and testing whether a number is a quadratic residue can be done efficiently. Therefore, there is no possibility that some ElGamal key in this group is invalid: any quadratic residue $h$ not equal to 1 is uniquely associated to a secret ElGamal key $s$, which is the unique $s$ such that $g^s = h$ ($g$ is some fixed generator of the group). Even though brute force to find the key is not efficient (that's the whole point of it, in fact), it is guaranteed to succeed (in exponential time) in finding the unique ElGamal key.

Therefore, it seems to me that a properly instantiated ElGamal scheme should suit all your needs.


What are the relations between cryptanalysis of block ciphers such as AES and Kendall's tau coefficient? Studying AES on Wikipedia, I noticed a statement regarding some ongoing studies on the use of Kendall's Tau coefficient in cryptanalysis:

  According to the Snowden documents, the NSA is doing research on whether a cryptographic attack based on tau statistic may help to break AES

This paper on Kendall's tau refers to the Pearson correlation coefficient, and in the related Wikipedia article we can read:

  Pearson correlation coefficient is a measure of the linear correlation between two variables X and Y

It's somehow straightforward to think at the variables in this statement like the variables in linear cryptanalysis... is this correct?
Is the application of Kendall's tau a sort of power-up of Linear Cryptanalysis? How?

Here is a wild guess as to what this reference may actually mean.

TL;DR; The Kendall $\tau$ can be used to measure how close different rankings of key guesses resulting from stages of the attack are, to track if the attack is getting close to the real key ranking, in some sense.

Aside: The paper On Probability of Success in Linear and Differential Cryptanalysis by A A Selcuk, available here is an excellent reference on probability of success in linear and differential cryptanalysis, where ranking of keys is also mentioned.

Please note that the idea of Pearson correlation coefficient is quite general, however it does measure correlation between random variables, including the type of binary random variables encountered in linear cryptanalysis, for example, if we focus on a single Sbox $S(\cdot)$,
$$
\textrm{corr}_{a,b}(S)=\sum_{X \in \{0,1\}^n} (-1)^{a\cdot X\oplus b\cdot S(X)}
$$
is exactly a Pearson type of coefficient for the pair of binary random variables
$$
(-1)^{a\cdot X},(-1)^{b\cdot S(X)}.
$$
However, I don't think this is where the interesting direction of this argument lies.

For sure, we choose $a,b$ in order to maximize the correlation, and eventually do this for $r-1$ rounds in order to attack some input key bits into the $r^{th}$ round by partial decryption of the ciphertext, conditional on those guessed keys. Specifically the key  guess which maximizes the overall correlation dependent on whatever $a_i,b_i$ choices in a collection of Sboxes away from zero as we compute biases over a large set of plaintext/ciphertext pairs are hypothesized to be more likely to be the correct key guess.

However, how does this actually work in practice?

We obtain a ranking of key guesses from most likely to less likely, based on the correlation samples obtained. We keep a count of how many times each key guess satisfies the hypothesized linear expression, and rank guesses according to how biased they are. I will refer to the most likely key as the highest ranked. There is an actual correct ranking which puts the correct key on top and all the rest below it. In fact the collection of rankings which put the correct key on top, and the rest arbitrarily are all admissible.

Let's recall the wikipedia reference to Kendall's $\tau.$

  The Kendall tau rank distance is a metric that counts the number of pairwise disagreements between two ranking lists. The larger the distance, the more dissimilar the two lists are. Kendall tau distance is also called bubble-sort distance since it is equivalent to the number of swaps that the bubble sort algorithm would take to place one list in the same order as the other list.

The evidence is that AES is very strong against differential cryptanalysis. This means that it will require a huge number of plaintext/ciphertext pairs to break it this way.

To make things simple, consider attacking AES in a sequence of attacks using $K_i=2^{(i+N)},$ for $i\geq 0,$ plaintext/ciphertext pairs, where $N$ is some large integer. This is conceptual of course, since $N$ has to be impractically large.

Say we look at the ranking of the key guesses that result from each of these attacks (by doubling the number of P/C pairs used at each step as $i$ increases). If we want to gauge how we are progressing as $i$ increases, we would like to find out if some kind of convergence in the key ranking is occuring towards the correct ranking. Let $\pi_i$ be the ranking corresponding to the $i^{th}$ attack.

One way of doing this would be to compute the Kendall $\tau$ coefficient between the different rankings $\pi_i.$

A similar argument could be made for differential cryptanalysis as well, since both attacks rely on collecting enough plaintext/ciphertext samples so that the correct key guess has the highest rank, rank 1, with high probability.


What does "securely realize" mean? I was wondering what "securely realizes" means. I see this in some cryptographic papers but I don't know what it means for a protocol to "securely realize" a function $F$.  Is it just a fancy way of saying "uses" or does it mean something else?

A standard approach in cryptography is to separate out the ideal specification (of what a scheme is supposed to achieve) from the particular instantiation (the implementation of the scheme).

To specify the security and functionality goals, sometimes cryptographers specify an "ideal functionality", which is an idealization of what we are hoping to achieve.  Then, one designs a specific instantiation -- a particular scheme -- and proves that the scheme meets the goals set out in the "ideal functionality".  We describe this by saying that the scheme securely realizes the ideal functionality.  How to prove that is another can of worms entirely... but that's what is meant by the terminology.

This kind of approach and terminology is common in, for instance, theoretical work that adopts an "ideal world/real world" formalization (including, e.g., simulation-based security; indifferentiability; universal composability; and other lines of work in cryptography).  See Wikipedia on universal composability for a high-level introduction.


SHA256 output to 0-99 number range? Is it mathematically possible to take a SHA256 hash and turn it into a 0-99 number where each number in 0-99 range is equally likely to be picked?

As a 256 bit hash means the highest value possible is 2^256, this is not a nice or "round" number for the purposes of simplifying a hash down to ranges more natural for humans.

If you mean exactly as likely, no, because the number of possible hashes is not a multiple of $100$.  This is assuming all the hashes are exactly equally likely.  You can come very close just by taking $SHA256 hash \pmod {100}$  This will be within one part in $\frac {2^{256}}{100}$, which is a very small number.  If you want truly equal, check that the hash is in the range $[0,100\lfloor \frac {2^{256}}{100}\rfloor)$ and take it $\pmod {100}$  If it is above that, hash something else and try again.  Your odds of failing the check are very small, and your odds of failing twice are very small.
In the general case: if one wants a result in the range $0..n\text{-}1$ then use $\bmod n$ and discard if the output  $>n\lfloor  \frac {2^{256}}{n}\rfloor$ and try another input. This is called the discarding technique; it is commonly used to extract a number in a range from a (pseudo) random number generator.


PKI Multiple Samples start to expose Private Keys? My understanding is that using a PKI, public/private key pair is generally secure to send message to people.  That is, encrypt a message using the recipient's public key so they use their private key to decrypt the message. My question is if encrypting the same "String" and sending them to multiple people starts to increase the possibility of cracking the private keys of the recipients as the number of samples go up.

For example, lets say I have the public key for the following people:

ALICE
BOB
CAROL

I would like to secretly send each of them the same string so I encrypt that string in each of their public keys.  In each data-set, it is clear to attackers that the same string is encrypted and sent to these 3 people.  The public key would likely be present so it is clear to which private key the sample of encrypted data belongs.  The hacker would not know what string has been encrypted, just that it is the same to all recipients.

Does this pose a situation where discovering the private keys can become simpler with more samples (More strings send to the users) and/or by increasing the number of recipients?  Ultimately, does this condition decrease the effective privacy of the PKI encryption/decryption method?

There's a wide gap between plaintext recovery and key recovery.  Of course, what is of interest to users is the confidenitality of their plaintext, but if an attacker can merely recover a single plaintext (which might happen outside the domain of crypto if the user just leaves it on the tube on their way to work!), that doesn't mean they can recover the next one—while if they can recover the key, they now have all the power of the legitimate user.
Public-key encryption is necessarily randomized so that if you send the same message to three people, or even send the same message to the same person three times, I still can't tell that just by looking at the ciphertexts without breaking the crypto.


Constructing set membership proof for private set Is it possible to construct a set membership proof to show $\delta \in \Psi$ where $\delta$ is publicly known and $\Psi$ should stay only known to the prover?

It seems rather impossible but I would like some confirmation.

Yes. $\:$ The verifier(s) need(s) to know a statistically binding commitment to $\Psi \hspace{-0.02 in}$.


Why does decryption in RSA not fail with 2 different moduli? In RSA, we choose $p,q$ and calculate $\phi(n)=(p-1)(q-1)$. We then choose a public key $e$, and calculate its inverse modulo $\phi(n)$: $d\cdot e=1 \mod(\phi(n))$.

But then, when we decrypt a ciphertext $y=x^e \mod(n)$, we use the different modulus $n$ rather than $\phi(n)$: $x=y^d \mod(n)$. This is equal to $x^{e\cdot d \mod(n)}$, which supposedly equals $x^1$. But I don’t understand this last step, because we chose $d$ such that $e\cdot d=1 \mod (\phi(n))$, not such that $e\cdot d=1 \mod(n)$

The question assumes, wrongly, that $a^b\bmod n$ is the same as $a^{b\bmod n}$ or $a^{b\bmod n}\bmod n$. In general these are three different quantities, as demonstrated with $a=5$, $b=5$, $n=3$:
$$\begin{array}{}
a^b\bmod n&=&\left(5^5\right)\bmod 3&=&3125\bmod 3&=&2\\
a^{b\bmod n}&=&5^{(5\bmod 3)}&=&5^2&=&25\\
a^{b\bmod n}\bmod n&=&\left(5^{(5\bmod 3)}\right)\bmod 3&=&25\bmod3&=&1
\end{array}
$$
Note: going from the second to third expression of the last line uses the result obtained above.


Understanding the impact of partitioning oracle attacks on stream ciphers Yesterday I came across some conversation discussing partitioning oracle attacks, against authenticated stream ciphers like ChaCha20 and Salsa20 with poly1305 for MAC.
As I understand it (though the paper is a little dense), the exploit requires:

an interactive client/server where messages are encrypted under keys derived from passwords.
the encryption is "non-committing".
The server responds indicating if decryption was a success.

Though this discussion raised a number of concerns for me:

These multiple key things seem crazy, I always understood symmetric ciphers like ChaCha20-256 required searching a $2^{256}$ bit keyspace for a single correct key. I read that you can actually calculate using linear equations approx 200,000 valid keys for decryption. Is this really true, if so we shouldn't consider the bit-strength $2^{256}$ even for ECDH agreed on keys should we?

In an example local application where one uses say, libsodium's secret box (Xsalsa20+Poly1305) and Argon2 to derive a password and encrypt some file, if this file is stored on a system with no other API or info, is this vulnerable to this attack? (e.g. by calling libsodium and watching if the MAC primitive is successfully verified) or are "offline/stored" files like this safe? i.e. like a padding oracle attack, does this whole thing require that the server knows the correct key, and as such can give away information?

Is this only an issue with password-based keys? Doesn't this attack also mean one can reduce the keyspace for ECDHE agreed keys to $2^{256}/200k$ when destined for use with ChaCha/Salsa?

In short, we can call this a speed-up password search on non-committing AEAD schemes like  AES-GCM and ChaCha20-Poly1305 with low oracle calls. If your password has good strength then you are safe.

A committing encryption scheme is a scheme that computationally intractable to find a pair of keys and a ciphertext that decrypts under both keys.
The defined  targeted multi-key collision resistance
(TMKCR) security by the following game in which for a given target key set $\mathbb{K} \in \mathcal{K}$ for a randomized adversary $\mathcal{A}$ must produce a nonce $N^*$, associated data $AD^*$, and a ciphertext $C^*$ such that $\text{AuthDec}_K(N^*,AD^*,C^*) \neq \perp$ for all $K \in \mathcal{K}$. And the advantage is defined as
$$\textbf{Adv}_{\text{AEAD},\mathbb{K}}^{tmk-cr} = \Pr \left[ \textsf{TMKCR}_{\text{AEAD},\mathbb{K}}^\mathcal{A} \right] \implies \textsf{true}$$
As one can see, if the attacker somehow partitions the keyspace then they can reduce the oracle queries this means the attack has less online interaction to be detected.
For example, consider AES-GCM which is not committing, and select two keys and an arbitrary ciphertext then the adversary will look for creating a valid tag so that when during decryption the tag is valid [1]( note; AES-GCM doesn't require decryption to validate the authentication tag, however, separating decryption and tag validation requires to pass on the data, and usually this is not preferred for performance reasons)
The aim is the recovery of a password $pw$. Consider that you want to test the membership of two passwords $S_1^* = \{pw_1,pw_2\}$. Create two keys $K_1 = PBKDF(salt,pw_1)$ and $K_2 = PBKDF(salt,pw_2)$ (the salt can be found by sniffing!), now use Dodis et, al's approach  [1], construct a ciphertext $C'$ with a tag such that it decrypt correctly under the keys $K_1$ and $K_2$. Now send the splitting value $\hat{V}$ to the server. If the server indicates the decryption is successful then $pw \in S_1^*$. With iterating this procedure the attacker can find the password in $|\mathcal{D}|/2 +1$ queries while the default brute-force requires $|\mathcal{D}|$ queries. This attack has degree 2, if $k$ degree is possible then this will decrease the query amount substantially.
With SageMath code they were able to find $k=2^{16}$ colliding ciphertext very quickly. They simulate their adaptive partitioning oracle attack that constructs splitting ciphertexts of size $k$ iteratively for different sets of keys until the oracle returns valid. At this point, the adversary performs a binary search in $\log k$ queries to find the secret.

On the left, on the above picture, their success rate, and on the right is the time to generate the $k$-way collisions.
It turns out that multi-key collision attack on the Poly1305 is harder than GCM due to the appended 0x01. They are only able to generate at most 10, compare to GCM that reaches 18 degrees.  this still gives a factor-
of-ten speedup in partitioning oracle attacks
Misuse-resistant schemes like AES-GCM-SIV also applicable to this attack.
Attack on protocols

Shadowsocks
OPAQUE

Countermeasures

Limiting the length of the ciphertext
Entropy requirements on shared secrets
Use committing AEAD scheme, there is non in any standards, yet!.
Use single key Encrypt-then-HMAC ( long live HMAC ) or KMAC.

Questions

These multiple key things seem crazy, I always understood symmetric ciphers like ChaCha20-256 required searching a $2^{256}$ bit keyspace for a single correct key. I read that you can actually calculate using linear equations approx 200,000 valid keys for decryption. Is this really true, if so we shouldn't consider the bit-strength $2^{256}$ even for ECDH agreed on keys should we?

First, a small correction. If the keys are uniformly generated then on average it is not $2^{256}$, one bit less. let $k$ be the target key that the adversary search with a way to test the correctness of the key. Since each key has $\Pr[k_i = k] = 1/2^{256}$ to be correct then the expected number of guess is;
$$\sum_{i=1}^{2^{256}} i \cdot \Pr[k_i = k] = \sum_{i=1}^{2^{256}} i \cdot \frac{1}{2^{256}} = \frac{2^{256} (2^{256} - 1)/2}{2^{256}} = 2^{255} - {\textstyle\frac12}.$$
Of course, during the search, there will be many false positive keys to be eliminated, which doesn't add much to the search time.
As we talked about above, they search for a possible password space $\mathcal{D}$ where $|\mathcal{D}|= 800000$. The committedness of the scheme enables the attacker to reduce the oracle calls substantially.
If you are using a strong password or generating them with ECDHKE plus KDF call then you will be safe. The point is that humans tend to use bad passwords including cryptographers.

In an example local application where one uses say, libsodium's secret box (Xsalsa20+Poly1305) and Argon2 to derive a password and encrypt some file, if this file is stored on a system with no other API or info, is this vulnerable to this attack? (e.g. by calling libsodium and watching if the MAC primitive is successfully verified) or are "offline/stored" files like this safe? i.e. like a padding oracle attack, does this whole thing require that the server knows the correct key, and as such can give away information?

This attack requires an oracle that returns a value like the padding oracle attacks. If there is no return, then there is not a test even for a normal online password guessing attack $k=1$. They have looked at the libraries the use OPAQUE and AEAD schemes and saw that some of them are not applicable. See the emits error column. The attack on Shadowsocks was interesting since the attacker had a side channel to test.

Is this only an issue with password-based keys? Doesn't this attack also mean one can reduce the keyspace for ECDHE agreed keys to $2^{256}/200k$, when destined for use with ChaCha/Salsa?

If the keys are uniform randomly generated then the attack will not work. It is a password search.


For Diffie-Hellman, must g be a generator? Due to a number of recently asked questions about Diffie-Hellman, I was thinking this morning: must $g$ in Diffie-Hellman be a generator?

Recall the mathematics of Diffie-Hellman:

Given public parameters $p$ (a large prime) and $g$ (always referred to as a generator of $\mathbb{Z}^*_p$).

Alice chooses $a$ at random and sends $A \gets g^a \mod{p}$ to Bob.
Bob chooses $b$ at random and sends $B \gets g^b \mod{p}$ to Alice.
Alice computes $S \gets B^a \mod{p}$
Bob computes $S \gets A^b \mod{p}$

From the math above, I don't see anything that would require $g$ to be a generator, so the math should work even if $g$ is not a generator.

As far as security goes, clearly having $g$ be a generator is best as $|g|$ (or the order of $g$) will be greatest when $g$ is indeed a generator. Is that the only reason for choosing $g$ to be a generator?

First, we are talking about multiplications, so we work in $\mathbb{Z}_p^*$, not $\mathbb{Z}_p$.

By definition, any integer $g \in \mathbb{Z}_p^*$ is the generator for... the subgroup generated by $g$, i.e. the set of $g^k \mod p$ for all integer values $k$. The order of $g$ is the smallest $k \geq 1$ such that $g^k = 1 \mod p$.

For soundness (Alice and Bob end up with the same shared key), any $g$ will do.

For security, we need the order of $g$ to be a multiple of a large enough prime value, usually denoted $q$. It is not necessary that $g$ generates the whole of $\mathbb{Z}_p^*$. It is not necessary that the order of $g$ is exactly $q$.

If the targeted security level for Diffie-Hellman is "$t$ bits" (i.e. the system will resist attacks up to at least computational effort $2^t$), then $p$ must be big enough (see this site for estimates, but, roughly speaking, you need a 1024-bit integer for $t = 80$) and the size of $q$ must be at least $2t$ bits. Also, the DH private keys ($a$ and $b$) must be randomly and uniformly generated integers of size at least $2t$ bits. It is not necessary that $a$ and $b$ are generated uniformly among integers modulo $q$, only that they are generated among a large enough range (this differs from DSA, in which we need a random $k$ which MUST be generated uniformly in the $[1, q-1]$ range).


Is RC4 cipher just xoring plaintext with a random sequence seeded by key? After reading about RC4, it seems that it's nothing else than:

the plaintext stream is just XOR'ed with a pseudo-random sequence that
is initialized/seeded with the key

Is there something else in the algorithm?

Is there a general name for stream ciphers that use a XOR with a (pseudo-random) sequence seeded by key?

Is there something else in the algorithm?

No, that's it: just a pseudorandom generator (which in RC4's case turned out not to be that random) whose output is XORed with the message.

  Is there a general name for stream ciphers that use a XOR with a (pseudo-random) sequence seeded by key?

Yes — it's stream cipher.

(While you could certainly apply a stream cipher using different invertible binary operations (e.g., addition or subtraction modulo 256), that provides absolutely no benefit over XOR, so nobody ever does it. In both theory and practice, everybody will think of XOR when you say "stream cipher".)


Break AES-CFB mode having access to a AES-CTR black box I need help for a "simple" problem

Let's suppose an intercepted ciphertext C encrypted with an AES-CFB mode of operation, using key K and some IV (IV is probably at the begining of C)

The system let us access to a black box encrypting any tupple (plaintext, IV) using AES-CTR mode with the same key K.

I succeed compute the keystream of the CTR mode using output of the black box, but I still need the keystream of the CFB mode before decrypting C.

Anyone has an idea how to do it ?
Thanks

It is quite easy, try to imagine if you have only one block of plaintext and you encrypt it under CFB or CTR with the same IV...
(using the black box you can actually get the encryption of any IV of your choice)


Why are the shiftrows in AES in a fixed order? Can the order be changed? It seems AES uses fixed shiftrows as follows:

B0  B4  B8  B12  No shift
B1  B5  B9  B13  Right-shift 3 places
B2  B6  B10 B14  Right-shift 2 places
B3  B7  B11 B15  Right-shift 1 place

Would it make a difference to security if the rows were shifted differently?
Not to disturb the carefully selected shifts (0, 1, 2 and 3 shifts), but just the order of them: For example:

Right-shift 3 places
No shift
Right-shift 1 place
Right-shift 2 places

No it would not make a difference to security, but it will no longer be AES since it does not match the specification.

As long as all 4 rows have a different rotation count through 0-3 bytes, the permutation will fully mix the state after 2 rounds.


Algorithm to find primes $q$ and $p$ with $q\, |\, p - 1$? I understand that if $p$ is prime then $p-1$ must be composite (at least divisible by $2$ as it is even). But how does an algorithm find a prime $q$ such that $q \cdot r = p - 1$. I thought prime factorisation is such a hard problem?

The critical facts enabling to find such $p$ in practice are:

We can easily tell with practical certainty if an integer with many thousand bits is prime or not, using a primality test such as Miller-Rabin, even though we are typically unable to tell all its factors when it is not prime.
About $1.4/b$ integers of $b$ bits are prime. Thus it is more likely than not that randomly trying $b$ integers of $b$ bits will uncover a prime (for $b>4$).

Hence a possible method to find a somewhat random large prime $p$ with some large known random prime $q$ dividing $p-1$ is:

first randomly select a suitably large prime $q$
for successive $r$ of suitable size

compute $p\gets q\,r+1$
if $p$ is prime

output $p$ and stop.

There are refinements to this. Obviously, we can restrict to even $r$. That's a special case with $s=2$ of a more general tweak: for any small prime $s$, it must hold that $q\,r+1\bmod s\ne0$, thus $r\bmod s\ne-q^{-1}\bmod s$. This allows to build a sieve of possible $r$, eliminating most candidates without a full primality test.

There are standardized algorithms to generate such $p$ and $q$, including deterministically from a seed. See FIPS 186-4 appendix A.1


In cryptographic protocols, what protects against an attacker dropping messages? In some cryptographic protocols I have seen messages protected for confidentiality, authenticity, replaying attacks, reordering attacks, etc.

What protects a protocol from an attacker in a privileged network position (e.g. in control of a majority of the fibre networks connecting countries) from just dropping messages altogether, thus stopping the two parties from communicating (a “Denial Of Service”)?

For example: if a protocol includes a sequence number, the receiver sees messages #233, #234, and #236. What should the receiver do if they missed receiving the #235 message?

Not much in the cryptographic protocols themselves. But you can do other things to get around such attacks:

Request signed read receipts, or received receipts. So, if I send a message from my phone to yours, it sends back a reply that your phone has received the message (or that you have opened it). If such a receipt is signed, your attacker might be able to drop the messages, but won't be able to hide that fact from you.
Have another mode of communication to verify. I'll send you a message over wifi, and if I can't verify whether or not you received it over wifi, I will send you a text message over my cellular network. I might even call you. Hopefully, your attacker doesn't have serious control over both networks.
Distribute the work of sending the message broadly. Send each message through multiple channels through a protocol that can handle such sending without displaying the same message multiple times. Perhaps this protocol is advanced enough to make sure that no one party sees all of its traffic... otherwise, you're living in a post-apocalyptic world much like the one we happen to be in. Whoops.

At the end of the day, this would probably only be an issue if you're a competitor of Verizon's or a merged TWC/Comcast, or something like that. Maybe Microsoft could build some such bullshit into Windows. But none of those corporations would, because they'd be hit with gigantic criminal sanctions and civil lawsuits and face legitimate market harms as well.

But... I don't think cryptography is meant to handle this problem.


The importance of randomness in the creation of a key Why does it matter what kind of random number generation is used during key generation?

E.g. this answer states 7-8 words selected truly at random make a strong password. My problem's with the "truly" here. My thinking is - whatever key I chose with whatever random number generator, the information isn't available afterwards and an attacker can never know which random number generator I used, so he cannot use that to break the key. On the other hand, I can use "just count up" or a super sophisticated hardware generator and both might come up with "12345678" as a key. Of course, an attacker would start with trying keys like "111111" or "3456789", so he will break "12345678" earlier than, say, "93298762", but "using a good random number generator" or "selecting truly randomly" does not mean I cannot get "12345678" as key.

When humans generate random key, there is some bias. For instance, in your example "93298762" there are only 2 turning points where as normally there should be 4 (you can argue that it is a single sequence and it is not long enough to seriously speak about statistics, but nevertheless...)

Even if an attacker does not know what generator you used, it makes sense for him to check first (after dictionary) the keys that a human would generate. This reduces essentially the entropy and thus the resources needed to brute-force the key. That's why it is important that generator has much entropy.

In cases where a human participation is possible, like password generation, a good generator will eliminate keys that have relatively high probability to be generated by a human (dictionary keys, keys with human specific anomalies). That's why when such generator generates a key "12345678" it would eliminate it and proceed with generating until the likelihood with human generated keys is below some threshold.


Is CBC block cipher mode susceptible to reordering attacks? Regarding reordering attacks, is CBC block cipher as vulnerable as ECB? why? If CBC can prevent reordering attacks (that is, after reordering, the decrypted plaintext will make nonsense so the receiver can detect that it must have been tampered with during transmission), why do we still need mechanisms like sequence number to prevent reordering attack?

CBC is almost as vulnerable to reordering attacks as ECB. Sometimes you can get garbage, but you can certainly move e.g. two blocks and know that the second block will decrypt to the same plaintext as the original.

With ECB you cannot easily change the last block if padding is used. If the last block doesn't contain correct padding then an error may be generated during decryption. With CBC this is extended to (the last part) of the first-to-last block of the ciphertext.

All this is quite useless though. To protect modes such as ECB and CBC against change you should simply add an authentication tag over the ciphertext (and IV, if that is send). If active attacks are possible then padding oracle attacks may be possible as well; an authentication tag would protect against both.

So adding an authentication tag (MAC) or using authenticated encryption (such as GCM mode) is the best way to protect the message integrity and authenticity. That way you don't have to rely on the plaintext message / padding to detect errors.

You can of course have two ways of reordering ciphertext when it comes to CBC. You can reorder the blocks in a message or reorder the messages themselves. Sequence numbers protect against the latter.

This is quite a separate issue; reordering messages can be performed regardless of which mode is used. CBC certainly won't protect against the reordering of messages.


Why elgamal is still discussed As I understand, if two users have a shared key, it is possible to encrypt a message using symmetric key encryption.

So when a secret key is shared through Diffie-Hellman asymmetric key exchange, it means that the users have their shared key. So why can't AES keys be generated from shared keys, and why not use only AES for message encryption after this point?

Actually I am confused about this: if there is a shared key from a DH key exchange, why are we still talking about ElGamal asymmetric message encryption, isn't it confusing for a learner like me, to study that , firstly a secret key is sufficient to do encryption using faster symmetric encryptions and also talking about an asymmetric encryption that is based on shared secret key. Isn't learning Elgamal unnecessary and confusing? If not, is there any particular application that uses elgamal, because I do not find any solid application.

So why can't AES keys be generated from shared keys, and why not use only AES for message encryption after this point?

That is exactly what is done.

  if there is a shared key from a DH key exchange, why are we still talking about ElGamal asymmetric message encryption

Remember, DH is just one way to exchange a key. DH has its problems (no authentication). Using ElGamal is another way someone could exchange a key. It would typically be used as follows: Use AES to encrypt a large message with a random key for Bob. Encrypt that random key using Bob's ElGamal (or RSA if you prefer) public key. Send both to Bob. Bob decrypts the random key using his private key, then uses AES to decrypt the message. You are correct in that ElGamal (or any public-key cipher for that matter) is rarely used to send encrypted messages.

  Isn't learning Elgamal unnecessary and confusing?

If you are only learning DH and nothing else, then definitely not. DH does not provide digital signatures, does not provide authentication, does not provide encryption. It only exchanges a key (and is succeptible to a man-in-the-middle attack). Learning about ElGamal can provide the opportunity to discuss all these other things that you do not get with DH alone. That said, when I took a network security class we didn't discuss ElGamal at all. We instead learned about RSA as a way of doing digital signatures, signing a DH key exchange, exchanging a key, etc.

So, a question you didn't ask, but might be thinking now:

  If we learned about DH and RSA, isn't ElGamal unnecessary?

The answer is no. ElGamal has some other interesting properties and uses that a professor might still want you to learn about. ElGamal is semantically secure out of the box (RSA is only semantically secure if you have random padding). ElGamal has homomorphic properties that make it useful in applications like e-voting. You can create an elliptic curve variant of ElGamal. ElGamal also leads to a fairly simple threshold cryptosystem.

That said, I can see why some professors would skip ElGamal in an undergraduate crypto or network security course.


What are the benefits of algebraic eraser key exchange? Since this question hast just been updated I am wondering what the benefits of this scheme are. The only motivation I could find with a quick search are speed and power efficiency.

Am I missing anything?

Beside speed and power efficiency, there's also claimed resistance to attacks by quantum computers; quoting Iris Anshel, Derek Atkins, Dorian Goldfeld, Paul E. Gunnells: Post Quantum Group Theoretic Cryptography (2016-12-05), at SecureRF website:

  (..) unlike the classic protocols, these group theoretic protocols are not based on finite cyclic abelian groups. Instead, the underlying algebraic object is the braid group, an infinite non-abelian group. The security of these group theoretic protocols is not based on any problem known to be susceptible to a quantum attack, which makes them viable candidates for post-quantum asymmetric cryptography. In addition, since the data transmitted over public channels is contained in the Braid group, linear algebra/permutation based attack are not applicable to the protocols (..)

Also, there is novelty, which allows a patent, which serves some interests; obviously those of the patent holder, but occasionally those of the customer: when one purchases a door cylinder or lock with a patented physical key feature (which abound), one might gain some small level of protection against unauthorized key reproduction by someone who temporarily gets hold of the key, and better insurance that extra keys ordered from a shop will actually work, if the patent holder actively uses it as a legal leverage to enforce a key reproduction policy including proving possession of the key reproduction card sold with the cylinder/lock, and quality control. Similarly, the holder of a patent for a cryptographic technique can try to use the patent as leverage to force implementations to pass some security and/or interoperability tests, both of which potentially beneficial to customers.

Note: I'm making no statement about the claims of resistance to attacks by quantum computers, the validity of the patents, or their licensing policy.


Advantage of $\operatorname{GF}(2^8)$ over $\mathbb Z/2^8\mathbb Z$ in AES/Rijndael The Galois Field is used in the mixColumns step of the Rijndael-Algorithm. Over $\operatorname{GF}(2^8)$ (irreducible polynomial: $x^8 + x^4 + x^3 + x + 1$), the first value of a matrix multiplication (all numbers are hex numbers) would be:

$$\begin{bmatrix} \mathtt{1e}\\\mathtt{27}\\\mathtt{98}\\\mathtt{e5}\end{bmatrix}\cdot\begin{bmatrix} 2 & 3 & 1 & 1\\...&...&...&...\end{bmatrix} = \begin{bmatrix} \mathtt{28}\\...\\...\\...\end{bmatrix}$$

If I calculate the same matrix multiplication in the realm of natural numbers the result is:

$$(\mathtt{1e}\cdot2)+(\mathtt{27}\cdot3)+\mathtt{98}+\mathtt{e5} = \mathtt{22e}$$

Okay, $\mathtt{22e}$ is bigger than $2^8-1$, but we can just take $\mathtt{22e} \bmod 2^8 = \mathtt{2e}$ and the result would be well within the boundary of an byte.

As a non-mathematican I wonder what's the advantage of the calculating in the $\operatorname{GF}(2^8)$ over calculating with the natural numbers modulo $2^8$, because both methods seem to be feasible. I have two ideas in my head but did not find any confirmation nor disprove. Is it about efficiency because the $\operatorname{GF}(2^8)$ is perfectly aligned to the byte architecture of a computer? Or does the $\operatorname{GF}(2^8)$ provide better diffusion than the calculation via natural numbers? Or is it something else?

One important property of the mixColumns step is that it is Maximum Distance Separable (MDS).  That is, if $M$ is our multiplication matrix, if you take any two distinct input vectors $V$ and $V'$, and compute $M \cdot V$ and $M \cdot V'$, the total number of bytes distinct in $V$ and $V'$ plus the total number of bytes distinct in $M \cdot V$ and $M \cdot V'$ will always be at least 5 (the dimension of the matrix $M$ plus 1).

It turns out that this is an important property used in the proof of security of AES against differential and linear cryptanalysis.

Now, if you replace the $GF(2^8)$ multiplications within the MDS matrix with $Z/256$ multiplications, it turns out that you cannot have the MDS property; neither the matrix used within AES, nor any other matrix has the MDS property.

This is fairly easy to show; to start with, consider $V = \{0,0,0,0\}$ and $V'=\{128,0,0,0\}$; these obviously differ in 1 bytes, and so for the MDS property to hold, all for values of $M \cdot V$ and $M \cdot V'$ must differ.  However, if lsbit of $M[0,0]$ is 0, then the first byte of $M \cdot V$ and $M \cdot V'$ will be the same, and hence MDS will not hold, and hence the lsbit of $M[0,0]$ must be a 1.  Along the same line, if we consider the other bytes of $M \cdot V$ and $M \cdot V'$, and additionally, $V'=\{0,128,0,0\}, \{0,0,128,0\}, \{0,0,0,128\}$, we find that all bytes of $M$ must have an lsbit of 1.  Finally, we consider $V'=\{128,128,128,128\}$.  If all the lsbits of $M$ are 1, then $M \cdot V = M \cdot V'$; that is also a violation of the MDS property (as well as making decryption difficult...)


reducing false positives in searchable encryption Practical techniques for searchable encryption proposed by Song et al. [1] have a false positive rate of $l/2^m$ where $l$ is left half of encrypted bits and $m$ is right half and $l+m=n$ where $n$ is number of bits of the word being encrypted. For getting clarity on these bits please refer the figure 3 in page 6. (paper).

Especially when the input domain of words being encrypted is not so random say serial numbers, sequence ids etc. the false positives are simply high.

Is there any subsequent work done or techniques available for reducing the false positive rate ?

[1] – Song, Dawn Xiaoding, David Wagner, and Adrian Perrig. "Practical techniques for searches on encrypted data." Security and Privacy, 2000. S&P 2000. Proceedings. 2000 IEEE Symposium on. IEEE, 2000.

Additional Storage approach

A trivial way is with additional storage. by making the $l$ to be complete string instead of few $left$ bits shown in the figure above. so technically $|l|=|n|$ and $|m| = 0$.

This way the entire string is covered for search. Now rest of the scheme is same except that the stream cipher bits $S_i$ in the figure above are $\oplus$'ed with entire $l_i$ and store the encryption of $F_{ki}(S_i)$ separately for matching. Now there is an additional over head of storing $F_{ki}(S_i)$ bits. In reality, if we use AES for $F_{ki}(S_i)$ operation would result in 128 bits additionally which might be an over kill. If we use some length preserving encryption like FNR we could reduce the size of additional storage needed to size of word itself. Even in this case, we need double the storage of input text as premium for reducing false positives.

Not sure of any other approaches so far. I have made a quick proof-of-concept which could be found here. The test cases written for both that has false positives and also that will not have any but needs additional storage