Key space lower than Message spaces Let $\mathcal K$ and $\mathcal M$ be the key and message spaces respectively
 I know for fact that if $|\mathcal K| < |\mathcal M|$ then $\Pr[\operatorname{PrivK}_{\mathcal A,\Pi} = 1] > \frac{1}{2}$, knowing also that $\mathcal A$ is randomized and $\Pi(\operatorname{Gen},\operatorname{Enc},\operatorname{Dec})$ is an arbitrary encryption scheme with $|\mathcal K| < |\mathcal M|$

I'm trying to prove that but I find some problems :

I can't find any relation between the fact that $|\mathcal K| < |\mathcal M|$ and
$\Pr[\operatorname{PrivK}_{\mathcal A,\Pi} = 1] > \frac{1}{2}$, isn't the random bit $b'$ - the adversary generates to choose between the two messages - that defines whether the probability is higher or equal to $\frac{1}{2}$? I'm confused ?

For those of you who doesn't know about the $\operatorname{PrivK}_{\mathcal A,\Pi}$ experiment (Adversary $\mathcal A$ against the encryption scheme $\mathcal \pi$):

  The Adversarial Indistinguishability Experiment $\operatorname{PrivK}_{\mathcal A,\Pi}$ :

  The adversary $\mathcal A$ outputs a pair of messages $\mathcal m_0$ $ m_1$.
  A key $\mathcal k$ is generated using $\mathcal Gen$(A key generator) and then a bit $\mathcal b$$\mathcal  \in${0,1} is chosen. Ciphertext $\mathcal c $$\mathcal \gets$  Enc($\mathcal m_b$) is computed and given to $\mathcal A$. ($\mathcal c$ refers to challenge cipher).
  $\mathcal A$ outputs a bit $\mathcal b'$ $\mathcal \in$ {0,1}.
  The output of the experiment is defined to be 1 if $\mathcal b$ $\mathcal =$ $\mathcal b'$ and $\mathcal 0 $ otherwise. We write $\operatorname{PrivK}_{\mathcal A,\Pi} = 1$ if the output of the experiment is $\mathcal 1$ and in this case we say $\mathcal A$ succeeded.

1st answer:

I was writing a longer answer about proving the claim directly, with the cardinalities of the message space, ciphertext space and keyspace. Basically for a random message, not all ciphertexts are possible, thus for a random challenge, not both messages might be valid decryptions. If you assume that the attacker can try out all valid keys, just one of the messages might be a valid preimage for the challenge ciphertext. In that case, the attacker can find $b$. With randomly chosen messages, this results in a probability different than $1/2$.

2nd answer:

Actually, the proof of the statement is more elegant (in my opinion) with a contraposition ($A \rightarrow B$ is logically equivalent to $\neg B \rightarrow \neg A$) of the following statement:

Perfect secrecy requires $|K|\geq |M|$. If expressed in logic terms, we can say:

Perfect secrecy  $\rightarrow$ $|K|\geq |M|$.

Perfect secrecy means, the attacker has a probability of $1/2$. If the probability is anything else, it isn't perfect secrecy. Keep in mind, that an attacker with probability $< 1/2$ is equivlant to an attacker with probability $>1/2$, by simply flipping the output bit.

Perfect secrecy means basically: $\forall \mathcal{A}: Pr_{\mathcal{A}} = 1/2$. The inverse is: $\exists \mathcal{A}: Pr_{\mathcal{A}} \neq 1/2$
Inverting the statement $|K|\geq |M|$ is quite easy: $|K| < |M|$.

Therefore we get:

$|K| < |M|$ implies $\exists \mathcal{A}: Pr_{\mathcal{A}} \neq 1/2$

This is already quite close in what you tried to prove.


Database vs SAN vs Network Encryption Good day everyone! Please bear with me as this is my first post on the crypto exchange.  An interesting question was raised in a meeting recently about the double-encryption problem (i.e. same algorithm used on same message block twice yields weaker results).  However, the team was concerned that database encryption (such as Oracle or SQL Server's TDE) along-side SAN encryption might cause weaknesses.

For example, Wikipedia states (en.wikipedia.org/wiki/Multiple_encryption):  "Picking any two ciphers, if the key used is the same for both, the second cipher could possibly undo the first cipher, partly or entirely. This is true of ciphers where the decryption process is exactly the same as the encryption process—the second cipher would completely undo the first."

However, my understanding is that TDE protects against a SAN admin decrypting the disks and walking out with a copy of the database.  Not having TDE would be frowned upon by infosec unless it demonstrably causes weaknesses.

So when does double-encryption issues apply, or does it not at all here?  I am more hoping to understand the rationale behind when this does/does not apply.

If we presume that the two encryption methods are secure by themselves, then having double encryption will not introduce any weaknesses. Sure, the security of the encryption may be smaller than key size of the keys combined, but if you use two different keys then the security should not be smaller than the key strength of the smallest key used.

Of course, if the same symmetric key (and IV) are used then you could get into trouble as for some operations the encryption and decryption are identical. This is, for instance, the case for stream ciphers and counter mode encryption. However, if the same symmetric key is used for two different purposes then your key management is the issue rather than the methods of encryption. I presume though that key reuse is not performed as the SAN admin should not possess the TDE decryption key, according to the info in your question.

In short, as long as you don't presume that performing additional encryption makes the initial encryption stronger, then you should be OK. The double encryption problem as you state is mainly concerned about the fact that the key strength may not double even if you encrypt with two separate keys. But as far as I see, doubling the key strength is not your goal in the first place.


Proving that the least significant bit of an elliptic curve discrete logarithm is $0$ Suppose I have a secret value $a$ which maps to a public point on an elliptic curve $A = a \cdot G$, where $G$ is a generator of the elliptic curve of prime order $q$.

Can I prove to someone that the least significant bit of $a$ is $0$ using a non-interactive proof that does not expose the value of $a$? If I can, what would be the most efficient (in terms of proof size) way to do it?

Edit: this can probably be done using bit commitments (something similar to Confidential Transactions), but in this case, proof sizes are likely to be close to 10KB. Is there a way to do this more efficiently? Maybe somehow relying on the fact that $a$ is even?

Edit2: I've been reading a bit about Division Polynomials and I'm wondering if it is possible to use them somehow to prove that $a$ is even.

Take a look at SNARGs, e.g. Bulletproofs (which are range proofs).
The proof may be slightly too large though.

Assuming that $a \in \{0, \ldots, q-1\}$ is your representative,
you want to prove is that you know a bit decomposition of $a$ with
$a = a_1 d_1 + a_2 d_2 + ... + a_k d_k$
where all $d_i$ are even and $\sum d_i = p-1$.
E.g. $d_i = 2^i$ but $d_k < 2^k$ otherwise you can get wraparound.
This trick is found in some range-proof paper(s).
Without this, it may be possible to find, for odd $a$, a bit decomposition $a_i$
with $a' = \sum a_i d_i$,
and $a'$ even (due to wraparound, $a = a' \mod q$).
Hence you don't get a proof for "(representative of) a is even".

One question though: Why is the last bit zero? If you just want to split
the exponents into two groups, using squares and non-squares is more efficient w.r.t. ZK.
It's simple and efficient to prove that $a = b^2$ (with standard sigma
protocols).

It seems hard to somehow express "is divisible by 2" efficiently,
because all calculations happen over finite fields,
hence every (non-zero) element is invertible.
So there is no such thing as "even and odd".
(Also: $1$ is odd, $1 + p$ is even, but $1 + q \equiv 1 (q)$.)
But: Polynomials make sense, e.g. squares $f(x, y) = x^2 - y$
or bits $f(b) = b (b-1)$.
The vanishing/zero sets of polynomials are "algebraic",
which helps in the group setting.


There should be no limits to the exponent size if you're using power_mod.
"Too big" errors in a multiple-precision-capable library likely mean that you're trying to exponentiate-then-modulo; this creates huge numbers. If you use power_mod (cf. Python's pow), it keeps the number pruned within $\{0,\dots,n-1\}$ through the process so it never has to handle "exponentially large" numbers.


How can I generate cryptographic-quality 1/f noise, aka “pink noise”? Can anyone suggest how I'd generate cryptographic quality 1/f noise: aka 'pink noise', where the PSD follows 1/f.

I'd be happy to derive the pink noise from white noise (e.g. /dev/urandom), but I don't want to filter it in a way that would compromise the quality of the noise. All the references to 1/f noise I can find are from the audio/dsp world where they tend to use very crude approximations to convert white noise to 1/f noise which would introduce unwanted patterns.

The problem with answering this question as posed is that one would need to have a definition of "cryptographic quality" that applies to 1/f noise.  You'd need to talk about something like how many data points an intelligent adversary would need to observe to be able to distinguish your pseudorandom 1/f noise generator from truly random 1/f noise.

I suspect there isn't such a thing—in cryptography people normally want to transform non-white noises into white, not the other way around!  If you're designing, say, a stream cipher, it'd be catastrophic if keystream bytes are closely correlated to their neighbors!

But to me it doesn't sound like your question is fundamentally cryptographic, but rather statistical, in that you'd be happy with an insecure solution as long as it passed certain statistical tests (that you don't define):

  All the references to 1/f noise I can find are from the audio/dsp world where they tend to use very crude approximations to convert white noise to 1/f noise which would introduce unwanted patterns.

Without describing the patterns that you're seeing, it's hard to say anything.  But from previous experience, the challenges I've seen with simulating 1/f noise on a computer are:

You're generating samples, so there's a Nyquist frequency, and no energy above it no matter what you do.
1/f noise has progressively greater energy the lower down you look in the frequency spectrum.  Audio guys have the advantage that humans can't hear below 20Hz, so they come up with algorithms that have a lower frequency cutoff.

I've had decent success with the randomized algorithm from this page (the randomized but unweighted version), as long as the number of octaves fits the application. But I can tell that the upper octave in that algorithm is consistently a bit whiter than it should be.

Other than that I think the best I can do is suggest that you look at publications from the time and frequency field instead of audio/DSP.  For example, the NIST Time and Frequency Division has a lot of freely-available publications, some of which may be relevant:

http://tf.boulder.nist.gov/general/pdf/5.pdf
http://tf.boulder.nist.gov/general/pdf/190.pdf
http://tf.boulder.nist.gov/general/pdf/29.pdf
http://tf.boulder.nist.gov/general/pdf/2795.pdf

You should have better luck with the time and frequency literature because they don't have a 20Hz cutoff escape hatch like the audio people do.


Key space math clarification The following table specifies a cryptosystem based around a very simple encryption algorithm with four different plaintexts A, B, C and D (one corresponding to each row) and four different ciphertexts A, B, C and D. The encryption algorithm has five different keys K1, K2, K3, K4, K5 (one corresponding to each column). By writing EK(P)=C to mean that the encryption of plaintext P using encryption key K is C, the entire cryptosystem is defined as follows:

EK1(A)=B   EK2(A)=B   EK3(A)=D   EK4(A)=A  EK5(A)=C
EK1(B)=C   EK2(B)=C   EK3(B)=B   EK4(B)=B  EK5(B)=D
EK1(C)=D   EK2(C)=A   EK3(C)=A   EK4(C)=D  EK5(C)=A
EK1(D)=A   EK2(D)=D   EK3(D)=C   EK4(D)=C  EK5(D)=B

I am getting conflicted on this question. To me the key space should be 5. But some articles I've read say you do do k^2. If this was the case it would be k^5 = 32. Does it change how you compute this based on the algorithm or? I'm stumped.

This is not school related. I'm just wanting to learn some security and failing lol

the key space should be 5

Something is $5$, but that's not the key space.

The key space is the set $\{\mathtt{K1},\mathtt{K2},\mathtt{K3},\mathtt{K4},\mathtt{K5}\}$. We'll note it $\mathcal K$.

The size of the key space (or key space size for short) $\|\mathcal K\|$ is $5$.

The size of the key (or key size for short) in bits, that we'll note $k$, is the base-2 logarithm of the size of the key space, that is $k=\log_2(\|\mathcal K\|)$.
Here $k=\log_2(5)=\log(5)/\log(2)=2.3219\ldots$ bit.

  But some articles I've read say you do do $k^2$.

Read again: probably the article says that the size $\|\mathcal K\|$ of the key space $\mathcal K$ is $2^k$, where $k$ is the size of the key in bits. That is, $\|\mathcal K\|=2^k$. Or equivalently, $k=\log_2(\|\mathcal K\|)$.


Multiplying between generators degree I have to elements of multiplicative group of finite field with generator g -
$$g^x,g^y $$
Can I get? $$g^{xy} $$

The problem 'given a group and the elements $g, g^x, g^y$, find $g^{xy}$' is known as the Diffie-Hellman problem (or, more precisely, the computational Diffie-Hellman problem).

As for how difficult it is, well, we typically work with groups where this is difficult (by design; we often need to assume that the DH problem is hard).

As for how it might be solved, well, in a finite field multiplicative group, the best way of solving it is to solve the discrete log problem; this is, given $g, g^x$, recover $x$ (and from there, you can compute $(g^y)^x = g^{xy}$.  If you are in a group where recovering $x$ (or $y$) directly is infeasible, then solving the DH problem (to the best of our knowledge) is also infeasible.


RotWord in Rijndael's Algorithm I am currently learning Rijndael's Algorithm through this site where there is a slide show animation step-by-step.
I understand nearly all of the encryption process except part of Add Round Key.Looking at slides 16 & 17, it says:

    Applying the RotWord ... to the previous word Wi-1

What is the RotWord and how do we apply it? Is it the same transformation in all rounds?

I can deduct (from the result on slide 17) that the RotWord transformation has done a shift upwards by 1 on the word:

+----+                 +----+
| 09 |                 | CF |
+----+                 +----+
| CF |                 | 4F |
+----+ --- RotWord --> +----+
| 4F |                 | 3C |
+----+                 +----+
| 3C |                 | 09 |
+----+                 +----+

Is my assumption of this transformation correct?
If so, will the amount shifted by change every round or does it remain constant?

Yes. See also en.wikipedia.org/wiki/Advanced_Encryption_Standard. There is a pseudo-code in NIST's AES standard document which is very helpful for implementors. I have a Python code that very closely follows that pseudo-code in s13.zetaboards.com/Crypto/7385224/1/. For details of the design of AES, see J. Daemen, V. Rijmen, The Design of Rijndael. (Springer-Verlag, 2002)


Difference between ε-differential privacy and (ε, δ)-differential privacy I don't understand the necessity of introducing the additive term δ in the differential privacy definition. Moreover, reading different papers and blogs they say that because of the δ term the mechanism is "broken" (whatever that means).

I would really appreciate some help in understanding the role and the effect of the δ term.

Many thanks in advance!

The $\delta$ item is a relaxation of the $\epsilon$-differential privacy notion. The latter is a strong security notion because it requires an algorithm $\mathcal{A}$ to have very close output distributions on "neighbor" datasets $D_1,D_2$ that differ in a single record. From its formal definition

$\Pr[\mathcal{A}(D_1) \in S] \leq e^{\epsilon} \times \Pr[\mathcal{A}(D_2) \in S]$,

we can see that the probability difference should be small for every output set $S$ even if the probabilities $\Pr[\mathcal{A}(D_1) \in S]$ and $\Pr[\mathcal{A}(D_2) \in S]$ are negligible. In other words, such a requirement needs to hold for very unlikely events. Sometimes we want to relax this definition a little bit to cover more general cases as discussed here, so the $\delta$ item is introduced:

$\Pr[\mathcal{A}(D_1) \in S] \leq e^{\epsilon} \times \Pr[\mathcal{A}(D_2) \in S]+\delta$.

This essentially means that those highly unlikely "bad" events happen with probability $\leq\delta$. These "bad" events may break $\epsilon$-differential privacy but are properly bounded.


Blum Blum Shub Pseudo-Random Generator Requirements I am trying to understand the Blum Blum Shub pseudo-random generator originally described in A Simple Unpredictable Pseudo-random Number Generator

As best I can tell the requirements are:

For any $x_i$, only $x_i^2 \bmod 2$ is used (only the least significant bit)
$x_{i+1} = x_i^2 \bmod N$
$N = p\cdot q$
$p \ne q$
$p$ and $q$ are equal length primes
$p \equiv 3 \pmod 4$
$q \equiv 3 \pmod 4$
$\gcd(pq, (p-1)(q-1)) = 1$

I don't plan to roll my own crypto. Just curious.

Your understanding of the requirements are correct. To elaborate, the first requirement you specify can be explained as taking the parity of $x_i$. Also, the two primes are called Blum primes and the modulus is called a Blum integer, which means $p,q \in \mathbb P$, $p \equiv q \equiv 3 \pmod 4$, and $N = p \cdot q$.
There are a few other requirements, such as choosing a random $p$ and $q$ of approximately equal length (essentially the same requirements for generating RSA primes, modulo congruence relations). The initial seed, $x_0$, must also be sufficiently large and must be kept secret along with the primes. Finally, $p$ and $q$ are typically chosen such that $\gcd(\varphi(p),\varphi(q))$ is small in order to maximize cycle length. They must be strong primes, usually done by choosing safe primes (integer $p$ is a safe prime if $p,(p-1)/2 \in \mathbb{P}$) as the period divides $\lambda(\lambda(N))$, which results in short cycles if smooth.
If you wish to calculate any $x_i$ value directly from $x_0$ without first calculating $x_1 \cdots x_{i-1}$, you can use Euler's theorem to do $x_i = (x_0^{2^i \bmod \lambda(N)}) \bmod N$. Because of $\lambda$, you need to keep $p$ and $q$.
As usual, $\varphi$ refers to the Euler totient function and $\lambda$ refers to the Carmichael totient function.

Note that BBS is not a good CSPRNG. It is interesting from an academic perspective, but it does not provide a practical level of security, especially with realistic modulus sizes. It is also very slow.


AES encryption takes more time to decrypt than encrypt I am trying to find how much time an AES encryption and decryption takes for a given amount of data and key. In all the cases encryption takes way lesser processing time than decryption. I tried to get this answer somewhere else but can't find. May I know why does decryption takes a lot more time than encryption for AES 128/256 bit?

I am trying to implement a simple AES encryption in Arduino UNO. I use micros() to measure the time it takes to encrypt or decrypt.

Here is what I did for encryption:

Serial.print("Encrypted: ");
unsigned long start1 = micros();
String enc = aes_encrypt("this is data source","this is key");
Serial.println(enc);
unsigned long start2 = micros();
unsigned long diff1 = start2 - start1;
Serial.print("Time to encrypt the data: ");
Serial.print(diff1);
Serial.println(" microseconds");

As the commenters have said, it is impossible to answer without many more details about your particular implementation, but here is some background on Rijndael (pronounced 'rain-doll') that might help. Rijndael is the family of ciphers on which AES is based. AES is defined as Rijndael[1] with a block size of 128 bits and key lengths of 128, 192 and 256 bits.
Back in 1999, when the winner of the AES had not been chosen yet, Bruce Schneier published a paper[2] on performance of the proposed ciphers. The Pentium Pro CPU was a high end processor back then. On page seven of his report he states:

Rijndael is another variant of Square: a fast cipher that works very well across all platforms. It boasts a clean mathematical structure involving only table lookup and XOR operations. Although the encryption and decryption algorithms are not exactly identical, their general structure and performance are virtually indistinguishable.
Rijndael’s assembly language on both the Pentium and Pentium Pro processors is about 300 clocks per block. Unlike RC6 and Mars, there are no known CPU platforms (8-bit or 32-bit) on which Rijndael’s relative performance would be unduly negatively affected or on which timing attacks would be possible.

According to this, one of the algorithm's advantages is its resistance to timing attacks. This would definitely have been a factor in the decision to select Rijndael as the current AES.
Later, though, discussing performance on 8-bit smart cards, which I read as computing platforms with very restricted resources, he says about Rijndael:

Perhaps the only negative comment about Rijndael on smart cards is that the performance numbers in the paper do not include a decryption function. Including decryption would increase the code size somewhat (probably between 512 and 1024 bytes), and decryption speed would be slower (possibly twice as slow) than encryption speed due to the coefficients of the inverse MDS matrix.

Again, without details about your implementation, it is impossible to know what the cause of the discrepancy is. There is strong evidence pointing to the fact that encryption and decryption for a given key should take about the same time, but the Arduino UNO has an 8-bit RISC processor and even though it has 2K of memory, it can only consume it 8 bits at a time. You could be experiencing the same theoretical problem Schneier described.
[1] https://en.wikipedia.org/wiki/Advanced_Encryption_Standard - Check the section called Description of the cipher.
[2] https://www.schneier.com/paper-aes-performance.pdf


How does table size impact table lookup speed? Are there good discussions of how cache pressure impacts large 64k-ish lookup tables used in erasure coding and sometimes signature verification?
I'll focus on erasure coding in small characteristic and small degree, which gives a clean extremely performance sensitive application, and avoids off-topic side-channel discussion.
There is a classical log and exp table trick for doing multiplications in small extensions of fields of small characteristic, especially GF(2^8).
let ab_log = LOG_TABLE[a] + LOG_TABLE[b];
let ab = EXP_TABLE[(ab_log & ((1 << FIELD_BITS)-1)) + (ab_log >> FIELD_BITS)];

This works well in GF(2^4) and GF(2^8) where the lookup tables have size 16 and 256, respectively.  We'd have two 128k tables of the form [u16; 1 << 16] in GF(2^16) though, which blows the L1 cache.
We therefore always build GF(2^16) as an extension field, either of (a) GF(2^4) implemented by small multiplication tables, or else (b) of GF(2^8) implemented by a few 64k multiplication table,  or perhaps another pattern.  You could employ a "carry-less multiplication" instruction PCMUL instead, but it supposedly runs slower due to being designed for larger fields.
I'm confused by the anecdotal advise and benchmarks that (b) makes sense.  Yes, 64k just fits into L1 cache, but any machine doing GF(2^16) work does many other tasks too, probably making (a) more robust under different applications.
In short, why do large tables win as many benchmarks as they do?  Are benchmarks simply being run in a vacuum and not in production?  Or is the memory bandwidth often not that starved when the CPU can pipeline everything well?

To answer a specific question:

Are benchmarks simply being run in a vacuum and not in production?

Well, yes, pretty much.  If you are running a serious performance test on a specific routine, you deliberately don't run anything else (because whatever else the computer is doing at the time will jitter the timing of the routine you'll looking at, making the results less reliable).  And, yes, this gives an advantage to solutions which use a large amount of shared resources (such as cache space), over how they would perform in a more realistic environment.


Decode RSA given e,p and q_inv ( with respect to p) Suppose I was given e, p and q_inv. Where q_inv = 1 mod (p).
How would one go about computing N to decode the ciphertext?

In RSA $p$ and $q$ are chosen such that they are both prime numbers. I suspect that by $q_{inv}$ you mean the CRT coefficient, which is actually defined as $q_{inv} = q^{-1} \bmod{p}$. Thus, to find $q$ we need to calculate $q_{inv}^{-1} \bmod{p}$, and since $p$ is prime we can use Euler's Theorem to compute it as $q = q_{inv}^{p-2} \bmod{p}$. Note that this only works under the assumption that $p > q$, which is a standard assumption for RSA CRT. Knowing $p$ and $q$, we can now compute $N = p*q$.


Are there any industry standards for PRFs? I mean something like a NIST, ISO, FIPS or similar standard which defines a constructions for a PRF.

HMAC is the standard way to construct a PRF from a hash function.

FIPS PUB 198-1 - The Keyed-Hash Message Authentication Code (HMAC) (NIST standard)
RFC-2104 HMAC: Keyed-Hashing for Message Authentication (informational RFC)
ISO/IEC 9797-2:2011

(Unfortunately the above standards only describe it as a MAC, not as a PRF)

It's also very popular in practice. For example it's used in SSL/TLS, SSH, HOTP/TOTP.

I recommend using it with SHA-2 as the underlying hash function. Though technically the known weaknesses of MD5 and SHA1 don't apply to keyed use in HMAC, so even those obsolete hashes could still be used as PRF in the HMAC construction.


Encrypting 256 bit AES keys with AES ECB? What are the pros/cons of using AES ECB mode to encrypt encryption keys (data encryption keys or DEKs)? Aware of the significant weaknesses when it come to encrypting low-entropy data that's greater than a block size and also aware of AES Key wrapping functions (nice post). The low efficiency of AES KW in high throughput cases is an issue in our case (thousands/millions of fields flowing, each encrypted with own DEK).

In our case, the data encryption keys

are high entropy (hardware RNG + 4 PRNG sources + crypto-hash expansion) and
will be 128/256 bits long (concerns on even longer keys?)

We're avoiding AES-GCM etc to skip the IV to reduce the size since every byte is precious (big data/high volume)

Update:

Integrity of the DEK isn't a concern in the threat model. DEK tampering will trigger decryption failure affecting Availability. Availability is a concern at a higher system level. (Also, if an attacker can modify the DEK bits, they can simply delete the entire field/data payload just after the encrypted DEK)
The main concerns are Confidentiality and Integrity of the data itself.

If you are encrypting a 128-bit key, then it's "OK" since the key size is the same as the block size. However, if you encrypt a 256-bit key, then it's possible to tamper with the result. For example, you can drop one of the blocks and it "looks like" a 128-bit key, or you can make a 256-bit key be the same block twice (so it's of the form $k\|k$ where each $k$ is 128 bits, and so on.

Having said the above, even in the case of 128-bit key, you have the problem that an attacker can tamper with the ciphertext and you won't be able to detect it. It is true that the result will be random garbage, but in most cases, we like to be able to detect the tampering.


Trying to better understand the failure of the Index Calculus for ECDLP So I'm going to give you guys my understanding and then if you would be so kind as to tell me where I'm off the mark (hopefully I'm not completely wrong).

So basically the index calculus for the discrete log problem over $\mathbb{Z}_p$ takes advantage of the fact that even though we don't know the structure of $\mathbb{Z}_p^*$, we still have the homomorphism $\mathbb{Z}\rightarrow\mathbb{Z}_p^*$.  And thus we can still unambiguously write elements mod $p-1$ in terms of their prime factorizations.

And so since small primes occur the most frequently in these factorizations, then if we find enough elements of $\mathbb{Z}_p^*$ which can be written in terms of powers of some collection of small primes, then we can take the $\log_{\alpha}$ of both sides and form enough linear congruences to find the value of $\log_{\alpha}$ for each one of these small primes (this is the pre-computation part).  And then we finish by doing a similar procedure again but for an equation involving $\beta$.

The point wasn't to go into all the technicalities of this algorithm but to observe that the failure in the elliptic curve setting seems to boil down to the fact that there is no clear analogue of this trick when we shift settings from groups where the operation was to either add or multiply, followed by modding out, to a setting where the group operation involves the geometrically motived application of algebraic equations to relate points on a curve.  Since in this case there is no well understood UFD like the integers hanging around in the background to provide homomorphisms into any $\mathbb{Z}_p$ we want.

My understanding is that attempts to extend the Index Calculus to elliptic curves basically involve attempts to get $E(\mathbb{Q})$ to play the role of the integers.  But that these attempts have been met with at best marginal success and only for certain special families of elliptic curves.  While the problems encountered when trying to extend to the general case currently appear insurmountable.

I also want to clarify that being able to find in polynomial time the isomorphisms $\mathbb{Z}_p^*\rightarrow \mathbb{Z}_{p-1}$ in the finite field setting or $E(\mathbb{F}_p)\rightarrow \mathbb{Z}_{n_1}\times\mathbb{Z}_{n_2}$ in the elliptic curve setting would essentially crack the discrete log problem, correct?  And so it is the apparently random structure of these groups which lies at the heart of the difficulty of these problems.

You're essentially correct. Index calculus is impractical on elliptic curves because there is not a straightforward notion of smoothness in these groups.

In prime fields, there is the easy mapping from the multiplicative group to the integers, where smoothness is well-defined. Similarly, in extension fields there is the mapping to polynomials over the ground field, where smoothness is given in terms of irreducibility.

In elliptic curves there is no such simple mapping. One can't use decomposition into prime divisors, as in hyperelliptic curves, since every point is a prime divisor. One possible solution, as you have pointed out, is to try to lift the elliptic curve into $E(\mathbb{Q})$ or $E(\mathbb{Q}_p)$; this approach is full of obstructions, however, and has proven not to be very productive yet. The survey by Joe Silverman explains some reasons why.

Another approach is to try and decompose points into sums of a special pointset within the elliptic curve group itself. This is the summation polynomial approach of Semaev, but it only seems to work well for curves over extension fields, where the Point Decomposition Problem is tractable. Note also that recent advances have shown that in binary curves index calculus is actually asymptotically feasible.

Apart from direct attacks, there are some other ways to solve elliptic curve discrete logs using index calculus for special curves. The MOV attack uses the Weil pairing to map the logarithm to an extension field, where you can use the regular index calculus algorithms. The GHS attack maps the logarithm to a logarithm on a hyperelliptic curve of hopefully low genus, where index calculus attacks are also efficient.


Does my code have modulo bias I am writing a password generator in Go, but I want to make sure I am avoiding modulo bias.

My solution is to get a random number from crypto/rand in the range [0, len(alphabet) ** passwordLength),
and then encode that into the alphabet by dividing by len(alphabet), and using the remainder as an index into the alphabet.

if length == 0 {
    return "", nil
}
if len(alphabet) == 0 {
    return "", errors.New("Alphabet has length 0")
}

// Reading from rand.Reader once for each character would read more bits than necessary.
base := big.NewInt(int64(len(alphabet)))
max := big.NewInt(0).Exp(base, big.NewInt(int64(length)), nil)
num, err := rand.Int(rand.Reader, max)
if err != nil {
    return "", errors.Wrap(err, "Cannot get random data")
}

m := big.NewInt(0)
password := make([]rune, length)
// Add characters in reverse, so that the encoded characters
// follow the same order as the bytes read from rand.Reader.
for i := length-1; i >= 0; i-- {
    // Divmod sets num = num / base,
    // and m = num % base.
    num.DivMod(num, base, m)
    password[i] = alphabet[int(m.Int64())]
}

return string(password), nil

The goal is to generate string password of length characters among alphabet, with uniform distribution (assuming alphabet does not contain duplicate characters), while minimizing consumption of octets drawn from a source assumed uniformly random (hereafter just octets).

A bug in the original code suppressed the first character of alphabet on the left of the generated password, creating a bias for any remaining left character.

The current code seems correct: it generates a uniform arbitrarily large integer that can be thought as index of the generated password in a lexicography sorted vector of all possible passwords, then deduce the password by expressing that integer in a base corresponding to alphabet. This is conceptually clean, but:

Contrary to the objective, it frequently over-consumes octets. The underlying cause is that Go's implementation of rand.Int(rand.Reader, max) (by crypto/rand#Int or math/big/nat#random, I can't tell) repeatedly generates a uniformly random integer less than max rounded up to the next power of two, until that integer is less than max. For a password of 2 characters among 17, 2 octets are consumed at each iteration; the average is over 3.5 octets per password; 16 octets or more are consumed over once in 336, with no upper limit.
Average execution time is quadratic with the length of the password, rather than linear for simpler algorithms. That's because cost of modular division grows linearly with the length of the number divided.
While the language Go comes with an arbitrary precision integer library, not all languages do; and languages that do (like Java) sometime are used in an environment where that library is unavailable (e.g. most Java Cards).

Unless the length of alphabet is a power of two, whatever method introducing no bias can consume unbounded octets. Proof:

Assume a method always consume at most B octets and has no bias.
There's also no bias for a method always consuming exactly B octets, obtained by throwing away octets in the end as necessary.
That method has 2B possible inputs and length(alphabet)length possible outputs. It has no bias, hence the later must divide the former.
Hence length(alphabet) must be a power of two.

It is hard to tell if the use of big makes it more or less difficult to exhibit a timing dependency or other side-channel leaking some info about the generated password.

I can't tell what RNG is actually used, much less if it is cryptographically sound and properly seeded.

A fixed-precision algorithm

Note: this is work in progress, missing an implementation (more readable to the OP), and optimizations to reduce octet consumption when len(alphabet) is large.

Here is pseudocode for a method without arbitrary precision arithmetic. It is simple, fast, yields no bias, and is competitive with the question's method on consumption of random bytes when len(alphabet)<80 (in particular, on likelihood of large over-consumption for some parameters). All variables are non-negative integers less than 256*len(alphabet) and conveniently fit integer variables.

Set $n\gets 256$
[ $n$ is the number of possible input symbols (here, bytes) ]
Set $k\gets$ len(alphabet)
[ $k$ is the number of possible output symbols]
Set $r\gets0$
Set $s\gets1$
[ $s$ is the number of possible values for randomness buffer $r$ ]
Set the password to empty
For each character to be generated
[ $r$ is uniformly random with $0\le r<s<n$ ]

While $r\ge\lfloor s/k\rfloor\cdot k$

set $r\gets r-\lfloor s/k\rfloor\cdot k$
set $s\gets s-\lfloor s/k\rfloor\cdot k$
[ $r$ is uniformly random with $0\le r<s<k$ ]
Get one new uniformly random symbol $x$
[ $x$ is uniformly random with $0\le x<n$ ]
Set $r\gets r\cdot n+x$
Set $s←s\cdot n$
[ $r$ is uniformly random with $0\le r<s<k\cdot n$ ]

Let $y\gets r\bmod k$.
[ $y$ is uniformly random with $0\le y<k$ ]
Let $r\gets \lfloor r/k\rfloor$
Let $s\gets \lfloor s/k\rfloor$
[ $r$ is uniformly random with $0\le r<s<n$ ]
Append to the password the character at index $y$ in alphabet

Proof of correctness follows from the comments and arithmetic facts. More there, including why this is economical on randomness consumed (no claim of optimality). Despite the simplicity, I fail to find a reference in the literature.

Notation: to the Go programmer, $\lfloor r/k\rfloor$ is r/k and $r\bmod k$ is r%k.

Extension: One can modify $n$ at the second bullet of step 1 (e.g. to adapt to input symbols variably chosen by dice or coin throw). One can can modify $k$ after step 4 (e.g. to generate passwords always starting with a letter then also allowing digits), but that also requires re-initializing $r$ and $s$ (which looses some randomness), or careful adjustment of these variables.

Caution: I often get my answers correct only after many revisions, and we are only at the second version of the pseudocode itself.


Are lookup tables safe when they fit in a cache line? The typical cache line size of modern x86 machines is 64 bytes.  Is it safe to use lookup tables with secret data if the table does not exceed the cache line size, and is aligned accordingly?

I was thinking about how to make a constant-time GHASH (GCM) implementation.  I want to have a table of 128x4 128-bit entries.  Each two bits of the block being multiplied would determine which of four entries is XORed into the result.  Repeat 64 times, and you've multiplied the block by $H$.

As far as I can tell, this should be immune to timing attacks, because at no time does secret data determine which cache line is read.

The typical cache line size of modern x86 machines is 64 bytes.

This might not be true for all processors. You should retrieve that from system if you want to know that. Ideally you should split data further, in your example you can split it to a bit every 16 bytes, so you will support every machine with cache line size of 16 or bigger (and 16bytes is size of SSE register so most machines that come with SSE should have that cache size - so most CPUs in this millennium).

  As far as I can tell, this should be immune to timing attacks, because at no time does secret data determine which cache line is read.

We can only hope.

x86 and x64 processors aren't security devices. They don't come with any guarantees of data access time or any constant time guarantees. In fact, they are known to do anything they can to avoid being constant time, they want to do it faster if possible.

But hopes are (for example OpenSSL RSA relies on that) that this is indeed constant time. There aren't any guarantees from Intel nor AMD. But as far as we understand processors they produced - this is indeed true as of now.

However you should be careful. It isn't hard to introduce timing-attacks into your code - it's very easy to even introduce branch depending on secret if you are using anything but assembly. Best thing you can do is testing if something is indeed constant time on your machine. This doesn't mean it will always take same amount of time. Instead, different secrets shouldn't take different amount of time in long run.


Block cipher to encrypt 8 bytes/64 bits - Use 64 or 128 bit cipher? Here's the problem: I have a transport stream that I have been requested to encrypt between the transmitter and receiver. The data size is at most 8 bytes so it seems I can only use ECB as I only have a single block - the most I can do is pad to 8 bytes if its less, which I intend to do with random data (the receiver can figure out the correct length from the decrypted data).

I've been looking for 64-bit ciphers and came up with the most popular: DES, 3DES, TEA, XTEA, XXTEA, Blowfish. I've discounted DES, 3DES and Blowfish due to their code size (not enough space to implement it, and concerns over speed of encryption/decryption on the embedded platform we are using)

I'd rather not use TEA, as it seems insecure from what I've read.

Is there another 64-bit cipher that is more secure than TEA, but doesn't require lots of code space plus lots of constant data like Blowfish does?

Is it possible to use a 128-bit cipher and "trim" the result to 64-bits?

You can safely use ECB if all of the following conditions are met:

Your messages can be unambiguously encoded in a form with a fixed size which is equal to the cipher's block size. For example, your messages all have the same size which is smaller than the block size, or they're all smaller than the block size and they never have trailing null bytes.
You only need message confidentiality, not authenticity or integrity (i.e. you don't need to protect against an attacker who might modify the message in transit, possibly without knowing its content).
You don't mind that an observer can tell if you're sending the same message twice.

Even if you don't think you need authenticity or integrity checks, carefully consider the design of the whole system. What happens if an adversary submits fake messages (either made from whole cloth, or modifications of legitimate messages)? What happens if an adversary resubmits a previous message after having observed its effect?

If the messages are all produced and received by the same entity, and the sender and the receiver can agree on some kind of message identifier (e.g. a number that is incremented for each message), then there's a better mode: counter mode (CTR). CTR has several advantages:

By mixing the message number into the encryption, messages with identical content have distinct, unlinkable ciphertexts.
CTR turns a block cipher into a stream cipher, so you can send the exact number of bytes (of bits, even) that matches the length of the message.
CTR requires only encryption on both sides, never decryption, which can same a tiny bit of code size.

CTR only works if the sender and the receiver agree on the initial counter value for each message. Usually the initial counter value is sent as a prefix of the ciphertext, but if you already have a unique identifier for the message, you can repurpose it.

CTR requires distinct counter values for each block of all messages. For messages that are shorter than the block length, this requirement simplifies to not reusing a counter value for different messages.

Note that CTR does not help with message integrity. It even makes it trivial to make predictable changes to the ciphertext without deciphering it (flipping a bit in the ciphertext flips the corresponding bit in the plaintext).


Listing first 8 bits generated by LFSR Consider the primitive polynomial P(x) = x^4 + x^3 + 1, initialized with the bit string (shifting occurs from left to right, were the right-most bit represents the LFSR output): 1101.
List the first 8-bits generated by the LFSR, starting with the bit 1 that is the right-most bit of the initialization sequence above.
This was my work to solve this:
          s1 s2 s3 s4  output (s4 xor s3)

         [[ 1  0  1   1    0
          0  1  0]]   1    1
          1  0  1     0    1
          1  1  0     1    1
          1  1  1     0    1
          1  1  1     1    0
          0  1  1     1    0
          0  0  1     1    0

The answer is : 10110010. Is this because it is in result of what I have put in brackets?

A few things have gone wrong:

You've reversed the initial state, but continued to shift from left to right. If you do reverse then the shift is from right to left.
You've confused the output bit (the oldest bit in the register) with the feedback bit (the new value that is introduced after shifting)
The feedback rule for the polynomial $x^4+x^3+1$ is $s_{i+4}=s_{i+3}\oplus s_{i}$ and so in your notation would be $s_4$ xor $s_1$

With this borne in mind the first two rows of you table should read as follows:
s1  s2  s3  s4  feedback bit (s4 xor s1)  output bit (s1)
1   0   1   1   0                         1
0   1   1   0   0                         0...

and so on


Solution to Discrete Log as a Commitment Is the solution to a discrete logarithm a reasonable commitment scheme?
By my analysis, the following scheme is a reasonable commitment scheme:
Let $p$ and $q$ be large primes such that $q∣(p−1)$, let $g$ be a generator of the order-$q$ subgroup of $Z^*_P$. Let $m$ be a value from $Z_q$, and $c=g^m\text{ mod }p$. The commitment is $c$ and to open the commitment, the sender reveals $m$.
I believe this scheme is:

(Perfectly?) binding: The discrete logarithm only has one solution and so the sender can't reveal another value, $m'$, such that $c= g^{m'}\text{ mod }p$

(Computationally?) hiding: Obviously, this scheme is not perfectly hiding. But assuming the discrete logarithm is hard, receiver or an adversary can't determine the committed message prior to reveal, so I believe this provides computational hiding.

Is my analysis of the binding & hiding properties correct? Are there other flaws not captured by hiding and binding?

Obviously, this scheme is not perfectly hiding. But assuming the discrete logarithm is hard, receiver or an adversary can't determine the committed message prior to reveal, so I believe this provides computational hiding.

If the receiver had no other information about $m$, then you would be correct.
On the other hand, we typically assume that he has some information; the acid test is "if the receiver knew the committed value was either $m_0$ or $m_1$, he still cannot determine which it is from the commitment".
Obviously, your approach (or, for that matter, any deterministic method) cannot fulfill that requirement; you need to include some randomness to meet this criteria.


TLS 1.2 PRF with HMAC-SHA256 I am implementing support for TLS 1.2 for the IBM mainframe operating system z/VSE in Assembler language, but am having difficultly getting the PRF to work. I am validating with the values described in:
https://www.ietf.org/mail-archive/web/tls/current/msg03416.html
The first 32 bytes of my output are correct using this test case.
After the first 32 bytes I place the HMAC-256 32 bytes into a buffer and call the HMAC-256 again with the same secret. Is that correct or should I be concatenating the label and/or original seed date onto the first HMAC output?

Your description is vague but there are two levels of HMAC'ing required: you compute a series of intermediate values A0, A1, A2 ... where A0 is the 'seed' (see next) and each following value is HMAC_hash of the previous, and HMAC_hash each A1, A2 ... concatenated with 'seed' (see next) and concatenate those to produce P_hash and truncate to the final result.

Note an important change of scope: 'seed' in the P_hash and Ai formulas is the concatenation of 'label' and 'seed' from the PRF call. For clarity I use 'lbsd' as the name for this 'combined' version of 'seed'.

I find Java convenient for test/prototype code like this because you don't need to fiddle with low-level pointers, offsets, and such like C much less assembler, leaving it much easier to see (and verify) the logic. I display the series of 'A' blocks (A0, A1, A2 etc) and the corresponding pieces of P_hash which I notate P1, P2 etc.

So with this code

//nopackage
import java.nio.ByteBuffer;
import java.util.Arrays;
import javax.crypto.Mac;
import javax.crypto.spec.SecretKeySpec;

public class Cry46549 {
    public static void main (String[] args) throws Exception {
        // java Cry46549 hmacname <file_containing_secret_seed_output # label is constant

        byte[] secret = new byte[16], seed = new byte[16], label = "test label".getBytes("ASCII");
        System.in.read(secret); System.in.read(seed); int want = System.in.available();
        // WARNING only in test code, stream.available() isn't reliable

        byte[] lbsd = Arrays.copyOf(label, label.length+seed.length);
        System.arraycopy(seed,0, lbsd,label.length, seed.length);
        Mac mac = Mac.getInstance(args[0]); mac.init(new SecretKeySpec(secret,""));
        byte[] A = lbsd; dump("A0:", A); ByteBuffer bb = ByteBuffer.allocate(want+64);
        for( int i = 1; bb.position() < want; i++ ){
            A = mac.doFinal (A); dump("A"+i+":",A);
            mac.update(A); byte[] P = mac.doFinal(lbsd);
            dump("P"+i+":",P); bb.put(P);
        }
        byte[] R = new byte[want]; bb.flip(); bb.get(R); dump("result:",R);
    }
    public static void dump (String heading, byte[] a){
        System.out.println (heading);
        for( int i = 0; i < a.length; i++ ){
            if( i%8==0 ) System.out.printf("%04x", i);
            System.out.printf(" %02x", a[i]);
            if( i%8==7 ) System.out.println();
        }
        if( a.length%8!=0 ) System.out.println();
    }
}

and the data for the P_SHA256 case from your link, lightly edited and xxd-r'ed into convenient binary, I get the following output, with desired final result as you can see:

A0:
0000 74 65 73 74 20 6c 61 62
0008 65 6c a0 ba 9f 93 6c da
0010 31 18 27 a6 f7 96 ff d5
0018 19 8c
A1:
0000 9f 5b b1 29 e2 f8 0a a4
0008 7b 67 05 b3 3e 21 4c c5
0010 e5 09 f2 83 e8 7b 3b e5
0018 e1 da a7 44 92 27 7d a1
P1:
0000 e3 f2 29 ba 72 7b e1 7b
0008 8d 12 26 20 55 7c d4 53
0010 c2 aa b2 1d 07 c3 d4 95
0018 32 9b 52 d4 e6 1e db 5a
A2:
0000 fc 16 6a 08 80 91 f7 6f
0008 af 99 35 9a 69 93 8f 75
0010 c1 54 24 63 8f 61 38 46
0018 34 24 37 32 b6 28 72 7b
P2:
0000 6b 30 17 91 e9 0d 35 c9
0008 c9 a4 6b 4e 14 ba f9 af
0010 0f a0 22 f7 07 7d ef 17
0018 ab fd 37 97 c0 56 4b ab
A3:
0000 fe 5f 7d 49 75 e1 23 c0
0008 d4 33 a3 a2 61 b6 42 c0
0010 58 04 46 46 1a f0 88 f0
0018 c7 9f 43 45 72 a1 a1 a6
P3:
0000 4f bc 91 66 6e 9d ef 9b
0008 97 fc e3 4f 79 67 89 ba
0010 a4 80 82 d1 22 ee 42 c5
0018 a7 2e 5a 51 10 ff f7 01
A4:
0000 3e fb 20 52 e4 76 f9 6c
0008 64 8d ca 6d 2d 00 8f b9
0010 75 ef b6 a4 83 60 be ec
0018 fd 47 a8 51 2b e7 3e eb
P4:
0000 87 34 7b 66 71 5a 92 bf
0008 c6 21 f0 17 10 81 1a b3
0010 8f 71 0e 7b 33 2f 44 10
0018 9e 42 fd 63 e4 7f 62 c0
result:
0000 e3 f2 29 ba 72 7b e1 7b
0008 8d 12 26 20 55 7c d4 53
0010 c2 aa b2 1d 07 c3 d4 95
0018 32 9b 52 d4 e6 1e db 5a
0020 6b 30 17 91 e9 0d 35 c9
0028 c9 a4 6b 4e 14 ba f9 af
0030 0f a0 22 f7 07 7d ef 17
0038 ab fd 37 97 c0 56 4b ab
0040 4f bc 91 66 6e 9d ef 9b
0048 97 fc e3 4f 79 67 89 ba
0050 a4 80 82 d1 22 ee 42 c5
0058 a7 2e 5a 51 10 ff f7 01
0060 87 34 7b 66


What is the appropriate public key encryption for secure coin flipping? I quote Bobby's question here since I encountered the same one...

Random Coin Flip using ElGamal and a Trusted Party

Consider the following protocol for two parties to flip a fair coin.

Trusted party $T$ publishes her public key $K_{pub}$
$A$ chooses a random bit $b_A$, encrypts it under $K_{pub}$, and announces the ciphertext $c_A$ to $B$ and $T$
$B$ does the same and announces a ciphertext $c_B$ (where $c_B \neq c_A$)
$T$ decrypts $c_A$ and $c_B$, and announces the results. Both parties $XOR$ the results to obtain the random value $b_A\oplus b_B$.

It was shown that ElGamal was not appropriate for the encryption scheme. RSA seems to fail to work also. Since $c_A=m^e \mod N$. Then if $m=1$, $c=1$. If $B$ receives $A$'s cipher he will know the exact value of $m$.

So what should the appropriate encryption scheme be?

There is no asymmetric encryption scheme which would work here. Whatever algorithm is used, $B$ can always send the exact same message than $A$ (i.e. set $c_B = c_A$); when $T$ decrypts both messages, he gets the same value both times, and $b_A \oplus b_B$ ends up being zero.

ElGamal encryption just makes it a bit easier for $B$ to game the protocol inconspicuously: $B$ can send the same encrypted bit than $A$ (without knowing it) under a random guise, making it indistinguishable from an honestly encrypted bit. But the core issue is still there: this coin flipping protocol is inherently broken.


Using 32 hexadecimal digits vs ASCII equivalent 16-character password Assume I'm using a cryptographic algorithm to pseudo-randomly generate a string that is specified to be 16 characters long.  The string will be used as a passphrase when encrypting a file.

So, for instance the string is:

Z±¨Û‹'bó£´µ¼

The hexadecimal equivalent of that string is:

0x5AB1A81CDB8B279D62F3A3B405B51DBC

Is either variant "stronger", cryptographically speaking?  In other words, if I use the string as the passphase, or if I convert the hexadecimal numbers into a string and use that as the passphrase, is either one better?

They are both equal.

Passphrase security is based on the amount of entropy that the passphrase contains. In your case, both of your pieces of data are only different in the encoding. The actual entropy that they contain is the same.

You are generating a secret that is (assuming that the random source is really random) 16 bytes long. So it has 128 bits of entropy.

I should note that this answer assumes "cryptographically speaking". However, encoding your passphrase in UTF-8 or ASCII may (in practice) screw up your data. The other answers do a good job at explaining why.

Update: fgrieu correctly notes that this answer assumes that all the entropy in the passphrase is actually used. An example when this is not the case is when you generate a 256 bit key, from which you derive a 128 bit key for 128-bit AES encryption. Here the entropy is reduced to 128 bits.


LAT of an SBox, values are even This is probably a silly question, but I could not find any reference. For the DDT of an SBox, it is easy to see why all the values are even. Is there any related result for LAT (i.e., all its values are even)?
LAT, for an $n \times n$ SBox, is a $2^n \times 2^n$ matrix with row $\alpha$ and column $\beta$ defined as follows:
For all $n$-bit $\alpha$, $\beta$; count how many times $\alpha\cdot x \oplus \beta \cdot y = 0$ holds; and subtract $2^{n-1}$ from it; where $x$ is the vector of input variables, $y$ is the vector of output variables, and $\cdot$ is the dot product.

Let $N(\alpha,\beta)$ be the number of times the equation
$$
\alpha\cdot x \oplus \beta \cdot y=0 \tag{0} \label{0}
$$
holds. Then the LAT matrix entry is
$$
L(\alpha\cdot x \oplus \beta \cdot y )=
N(\alpha\cdot x \oplus \beta \cdot y)-2^{n-1}
$$
and since the second term is even (can prove $n=1$ case directly) we need to show that $N(\alpha\cdot x \oplus \beta \cdot y)$ is even.
The basic idea is that the set of vectors over $\mathbb{F}_2^n$ of the form
$$a\cdot x=c \tag{1} \label{1} $$ has even cardinality
for any constant $c\in \mathbb{F}_2.$ Observe that this applied to $\alpha\cdot x$ and $\beta\cdot y$ means that $N(\alpha,\beta)$ is also even if we can prove $\eqref{1}$.
To prove $\eqref{1}$ assume $a\neq 0$ in $\mathbb{F}_2^n,$ since if $a=0,$ the relation holds for all $x\in \mathbb{F}_2^n,$ i.e., for $2^n$ vectors.
If $a\neq 0,$ let $w$ be the Hamming weight of $a$ and let $s_a$ be the support of $a,$ i.e., $s_a=\{i: 1\leq i\leq n, a_i=1\}$. Then, the inner product $a\cdot x$ is invariant when the components $a_i$ in the complement of the support take on all possible $2^n-2^w$ values, since they don't feature in the inner product. Clearly $2^n-2^w$ is even.
Finally note that equation $\eqref{0}$ holds if and only if $\alpha\cdot x$ and $\beta\cdot y$ are both equal to the same constant $c$. So it holds an even number of times.
Remark: This argument also works for an arbitrary $n\times m$ S-box $S:\mathbb{F}_2^n\rightarrow \mathbb{F}_2^m$ for any $m\geq 1$.


McEliece post quantum cryptography Can someone explain me in basic simplistic english if possible how does McEliece asymmetric encryption works and why its quantum safe ? Thanks in advance.

How does the McEliece asymmetric encryption work?

The intuition is really quite simple here. Assume you have a message of $k$ bits. You then use a specific mathematical operation to create a larger intermediate value of $n$ bits with $n>k$ such that it is not immediately obvious what the original message was and such that you can recover up to $t$ bit-errors using a specific algorithm. You then actually introduce $t$ random bit errors into your message to get your ciphertext.

Decryption is essentially reversing the above knowing the special values used to "obfuscate" the original message and the algorithm to remove the errors.

The idea behind the security of this scheme is that you cannot be sure for every bit that you are seeing whether it has been changed or not and through the "obfuscation" a wrong guess will yield essentially unrelated values when trying to invert the "obfuscation".

  why its quantum safe?

The entire reason is that we don't know how to (efficiently) break it if we had a quantum computer even though we have thought about this for more than 20 years.


Big block cipher as memory-hard function I'm wondering, if something like block cipher with big block size is a good memory-hard function?

All memory-hard key derivation functions I've seen look more complex than that, which made me question my understanding of memory-hardness.

The following function looks memory-hard (memory tradeoff looks expensive) to me:

size = 16MB / (F() word size in bytes)
rounds = 1024
state = constants ⊕ (key || salt)

for (i = 0; i < rounds * size; i++)
   state[i mod size] = state[i mod size] ⊕ F(state[i + 1 mod size])

result = state ⊕ key

How memory-hard is this type-I generalized Feistel network key derivation function?

I've been toying around with your function, and I've come to the conclusion it's not memory hard. The amount of required memory can be reduced to at maximum digestsize * 3 * rounds.

The first problem is that the entropy does not avalanche throughout the state, but stays localized. For example, after 1 round the state of the 2nd block only depends on the state of the 3rd block. After 2 rounds it (indirectly) only depends on the initial state of the 3rd and the 4th block. This means that an attacker could precompute 1024 rounds on a large portion of the constant and not need per-password memory for that.

A possible improvement would be to turn around the mixing to state[i mod size] = state[i mod size] ⊕ F(state[i - 1 mod size]) so that each block depends on the previous instead of the next, but the fact that you're generating & hashing in the same order will always make tradeoffs possible. Changing that order, preferably in a data-indepent way (e.g. by reversing the order of the blocks after each round), would make that way more difficult.

To illustrate my point, here are 2 codes: 1 with, and 1 without a memory tradeoff on your function:

#!/usr/bin/env python3
from hashlib import sha512

blocks = 1000
rounds = 100
# pseudorandom constants created by hashing the literals "0", "1", ... "1000"
constants = [sha512(str(i).encode()).digest() for i in range(0, blocks)]

def mix(a, b):
    global operations
    operations += 1  # statistics
    b = sha512(b).digest()
    return bytearray(a ^ b for (a, b) in zip(a, b))

def more_memory(constant):
    state = list(constant)

    for i in range(0, rounds * blocks):
        state[i % blocks] = mix(state[i % blocks], state[(i + 1) % blocks])

    # Make a checksum for the entire state
    state_hash = sha512()
    for s in state:
        state_hash.update(s)

    return state_hash.hexdigest()[:32]

def less_memory(constant):
    def perform_round(sequence):
        first = None
        cur = next(sequence)

        try:
            while True:
                after = next(sequence)
                result = mix(cur, after)
                yield result
                if not first:
                    first = result
                cur = after
        except StopIteration:
            pass

        yield mix(cur, first)

    current = (s for s in constant)
    for _ in range(0, rounds):
        current = perform_round(current)

    # Make a checksum for the entire state
    state_hash = sha512()
    for s in current:
        state_hash.update(s)

    return state_hash.hexdigest()[:32]

operations = 0
print('Using a lot of memory: {} ({} mixing-operations)'.format(more_memory(constants), operations))
operations = 0
print('Using little memory: {} ({} mixing-operations)'.format(less_memory(constants), operations))

# Prints:
# Using a lot of memory: e58f5665a2c388fc1420d4d1667f83df (100000 mixing-operations)
# Using little memory: e58f5665a2c388fc1420d4d1667f83df (100000 mixing-operations)


Can data stay encrypted unless I'm eliminated? I work as a spy for a top secret and ruthless government organisation with a three letter acronym.  I know all their dirty secrets and where the skeletons are literally buried.  In order to protect myself from being eliminated when I’m no longer required, I’ve downloaded all the organisation’s data and securely encrypted it.  I’ve then distributed that encrypted data to friends and reporters.

Is there a technique whereby the data remains encrypted whilst I’m still alive?  Clearly I would have to actively take steps to ensure this, and these steps would end upon my disappearance.  So whilst I’m alive I do “stuff” perhaps every month, and the shameful secrets remain impossible to decrypt.

I’m aware of secret sharing and key /certificate revocation but not of their flavours.  It seems like the very opposite of revoking a public key though.  Would I have to keep sending newly encrypted copies out?  Is there a cryptographic way to protect myself like this?  I’ve read somewhere that Edward Snowdon has such a protective scheme.

Edit:  The things I know would bring down the organisation and my friends being reporters, they would publish it as soon as possible.  Hence the notion of them not mathematically being able to decrypt unless I'm eliminated.  I do not want to rely on their assurances that they won't break the story at the earliest possible opportunity.  This allows the organisation to leave me alone.

If your friends and the reporters can decrypt the data without any action from you, then even if you're alive they should be able decrypt. You could trust a certain threshold of them to not collude with each other unless they're certain you're dead, in which case secret sharing the key might work.

If you trust your parties to publish the secret material as soon as they can get it (and not destroy it), something like this might also work: suppose you hide the key in a certain location, encrypt the location such that breaking (brute-forcing) the encryption will take at least $t$ time given a large amount of computational power, and send the encrypted location to all the parties. Before $t$ time is up, you move the key to a new location, and again encrypt the location to all the parties. This way, even if you don't trust the parties to not collude, they will not be able to access it as long as you keep moving the key in time.


Long-term data protection, storage of old encrypted traffic and quantum cryptocalipse Tony Arcieri makes an interesting point in his Imperfect Forward Secrecy article which basically boils down to:

large entities such as NSA are storing encrypted internet traffic, also what's to stop smaller entities such as proxy owners from doing the same
that data should be considered as good as clear text when quantum computers of sufficient strength hit the shelves and as that date grows near more people will start logging encrypted traffic
quantum computers are getting stronger with a good pace (82-qbit computer last year, 512-qbit computer this year) and a not-unreasonable estimate is that quantum computers will hit the shelves in 10-20 years
when this happens much (all?) stored encrypted data will be compromised

Problem existed before of course due to growing strength of computing technology and many protocols where discovered to be flawed by design, but the promise of a computer which breaks modern cryptography and knowledge of existence of giant datacenters which store data encrypted by obsolete standards make it worse.

It doesn't seem acceptable any more to just protect against today's cryptographic threats and know that all of the data you thought secure will be freely available to a patient individual in a not distant future (think of credit card numbers for example, password patterns that many people use etc)

So the question is, what kind of encryption/hashing one can use today to protect against long-term data storage?

Clarification

The "quantum cryptocalypse" simply exasparates a previously existing issue as more parties are likely to store encrypted data and wait for a good cryptoanalytical tool.

Problem lies in the general focus on making data secure "now" which is fine unless there's a sufficient number of entities storing encrypted data to break it later.

Quantum cryptocalipse, real or not, will make a lot of people store encrypted traffic on tapes. Idea behind this question is to find a list of algorithms which are "future proof" to the best of our knowledge and such algorithms should probably be quantum-proof too

Bottom line

OK, so what's the bottom line? Is there an asymmetric cryptography protocol that is not compromised by Shore's algorithm? Are there alternatives to using OTP for session key exchange?

I can't agree with bullet 3. of the question stating quantum computers are getting stronger with a good pace (82-qbit computer last year, 512-qbit computer this year), at least in a context of cryptanalysis.

Even the marketing people praising the device alluded to do not pretend that it is of a kind useful for cryptanalysis: they state about it:

  The types of problems the quantum computer is designed to solve are called discrete combinatorial optimization problems. The most cited example of this kind of problem is the “traveling salesman problem”.

Importantly, there is no claim of exactly solving almost all TSP of a given size, which would be a big breakthrough with potential applications to cryptanalysis. This marketing text proceeds to describe how better solving the traveling salesman problem as applied to US trucking could be of economic and ecological significance, without giving any evidence that today's TSP solvers can't handle that task satisfactorily.

In a recent scientific pre-publication linked here, the term " quantum annealing processor " is used to describe the device. Entanglement of only 8 qubit is claimed (a single out of 8x8 arrays of 8 qubit). Even if these 8 qubit where a quantum computer, and if all 64 arrays where functional, 64 arrays of 8 qubit would not make a 512-qubit quantum computer.

Enough expressing my strong doubts about the usefulness of Quantum Computers for cryptanalysis in a foreseeable future, let's get positive.

To protect against hypothetical Quantum Computers of a kind and size useful for cryptanalysis, using twice larger keys for symmetric algorithms is ample; AES-128 is safe today against key search, I bet AES-256 will remain resistant (in practice, to all but side-channel attacks) even with quantum computers, for decades (the most forward-looking may want to use Rinjdael in its 256-bit mode with perhaps an even wider key).

Now there's the problem of asymmetric algorithms (used when we want a private key not shared with anyone else). The mainstream asymmetric algorithms (RSA, ECDSA, DH, ECDH..) with today's key size are conceivably not secure against said hypothetical QC. Update: and, contrary to what I initially wrote, forward secrecy can't fix that. Protocols with forward secrecy, like some options of TLS or IPSec, can prevent past intercepts to be broken in the event of future leakage of private keys, including by use of future QC. But we do not know practical means (wich excludes Quantum Key Distribution) to fully protect us against intercepts made today, and analyzed in the future using an hypothetical Quantum Computer of a kind and size useful for cryptanalysis, and able to break the step of a key exchange protocol that built an ephemeral/session symmetric key, using typically some variant of DH or ECDH. Towards that, we need better/stronger asymmetric algorithms; I'm incompetent about it. In the meantime, we can use large asymmetric keys (particularly for the scheme building an ephemeral/session symmetric key); that's arguably at least of some use against QC.

And we should care, a lot, about much more mundane things than QC; like compromise of our computing platform, side-channel attacks, bad TRNGs, implementation goofs, and traffic analysis.


Is there an escrow-like mechanism that doesn't involve a trusted 3rd party? We know that escrow mechanisms are easy to implement when it involves a trusted 3rd party. For example if A and B don't trust each other they can simply send their goods to C whom they both trust. Then C can distribute the goods to them fairly.

However, is there a primitive that achieves the same when there isn't a trusted 3rd party? Basically, A and B don't trust each other and they want to exchange something. Can they do this without involving any trusted party?

Yes they can!

This can be done through a public blockchain like bitcoin for instance.

Other blockchains such as Ehtereum provide more functionnalities like Smart Contracts. These would enable both parties to send their goods (cryptocurrency/ digital property of some good etc.) to a decentralized application - DApp - running on the blockchain (basically, a piece of logic code that would be cowritten by the two parties so it would wait to receive the expected goods from the expected parties until realeasing it to one another, effectively acting as a decentralised, no TTP, automated, bot-escrow).


Is there any reason not to use Single-Key EM with AES and a constant key? I've read recently the paper "Minimalism in Cryptography: The
Even-Mansour Scheme Revisited" by Dunkelman, Keller and Shamir where it is claimed that the following construction (Single-Key EM) is secure:

$$C=K\oplus E(P\oplus K)$$

with $E$ being a publicly known fixed permutation.

Is there any reason not to use the above scheme (as block cipher) with AES-128 and key $0^{128}$ as $E$?

As for the reasons why somebody may want to use it:

It can provide smaller implementations, enabling the hard-coding of the round constants
It may be faster for the same reason
It is more key-agile, allowing for much faster key switches (e.g. in a hashing / KFB scenario)

This is considered in §6 of Bogdanov et al., who go on to devise an alternative 2-round AES-based Even-Mansour cipher—$\text{AES}^2$. The problem is, essentially, that 1-round Even-Mansour is only secure up to $2^{n/2}$ blockcipher queries, for an $n$-bit block. Specifically, a collision between $\text{SEM}_K(P) \oplus P$ and $E(P) \oplus P$ immediately reveals $K$ (cf. §4.2 of Dunkelman-Keller-Shamir).

In general, you want an Even-Mansour cipher targeting $n$-bit security to have block size $2n$. This is the case with, e.g., Salsa20 and ChaCha's core functions, which are Even-Mansour-like, target 256-bit security, and work on 512-bit blocks. Several permutation-based CAESAR candidates, such as Prøst or Minalpher, work similarly.


What is the significance of $\prod \limits_{i=1}^{t}m_i > p \prod \limits_{i=1}^{t-1}m_{n-i+1}$ in Asmuth–Bloom threshold SSS? In this paper by Asmuth–Bloom on 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 \in 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 \lt M \leq M_C$, the solution is also unique in $GF(M)$.

Could you please explain significance of
$\prod \limits_{i=1}^{t}m_i > p \prod \limits_{i=1}^{t-1}m_{n-i+1}$ in Asmuth–Bloom threshold SSS?

One of the required properties with a secret sharing scheme is that if you have $t-1$ shares (where $t$ is the threshold), then you can't eliminate any possible values from being the shared secret.

Now, suppose that we had $t-1$ shares; with the Asmuth-Bloom scheme, we would learn the most if they happened to be shares $(y_{n-t+2})$ through $y_{n}$.  If you had those shares, then you could deduce the value $y \bmod \prod \limits_{i=1}^{t-1}m_{n-i+1}$

You also know that:

$0 \le y < M$
You really want the value $y \bmod p$

For you to learn nothing, we need to have all possible values of $y \bmod \prod \limits_{i=1}^{t-1}m_{n-i+1} + pk$ to be in the range $[0, .., M-1]$

This is guaranteed if $p \cdot \prod \limits_{i=1}^{t-1}m_{n-i+1} \ge M$, which (if we remember that $M = \prod \limits_{i=1}^t m_i$ is precisely the restriction they give.

BTW: what is this fascination with Asmuth-Bloom?  In my opinion, Shamir Secret Sharing is a better way of solving the problem; it's simpler, a lot easier to set up, has smaller shares, and it doesn't leak any probabilistic information like Asmuth-Bloom does.


Polynomials and efficient computability In public key crypto, the popular definitions of security (CPA, CCA1,2) depend on PPT adversaries. I'm trying to understand why adversaries should be PPT.

It's clear that adversaries should be at most probabilistic sub-exponential, because otherwise they could exhaust the message space. It's also clear that adversaries should be at least PPT, because any computer can run low-order polynomial algorithms (barring unusual cases) and there's no good way to distinguish low-order polynomials from very high-order (and practically inefficient) polynomials.

So why not allow the adversaries to be probabilistic quasi-polynomials? Where quasi-polynomial means its time complexity is larger than all polynomials and smaller than all exponentials, like $n^{log(n)}$. Is there some example showing why it would not make sense for an adversary to be probabilitic quasi-polynomial?

The reason I was taught why poly-time is the conventional way to define "efficient" algorithms is that it's the smallest notion closed under various forms of composition.

If we have an algorithm for deciding whether some input is in some language and we let $N$ be the length of the input, then we'd like to call all the following operations efficient:

Returning "yes" or "no" all the time costs one (or constant) time.
Reading the input costs $N$ time.
Calling one efficient algorithm taking time $A(N)$, then passing the result through an efficient algorithm taking time $B(N)$ gives a total time of $A(N) + B(N)$, so our class of "efficient running times" should be closed under addition.
If an algorithm taking $A(N)$ time on its own is efficient, and you have an algorithm with $A(N)$ steps where each step is a call to another efficient algorithm taking $B(N)$ time, then you end up with $A(N)B(N)$ time, so "efficiency" should be closed under multiplication.

Plug all that together and you get "polynomial in $N$" as the smallest possible "efficiency notion" - which does not of course exclude other, larger notions such as the ones mentioned above.

This is not so much a cryptography as a general complexity theory/theoretical CS point, which cryptographers have borrowed for their notions of security.


What is a good algorithm to scramble data in a 2-D grid I want to know if there exists an algorithm i can use where the input is a string of data and the output is a scrambled version of the same but in a 2 D array
ie given something like:

|1 2 3 4 5 6 7 8 9|

I want an output somewhat like:

|2 8 * 3 |

|7 9 4 1 |

|* 5 * 6 |

The scrambling would ideally be on the basis of a key and the same key or its pair can be used to unscramble the message.

It seems like you just want to permute a string.  E.g., transform the string "123456789"+ 3 blanks into the string "28_37941_5_6".  Putting it into a 2-d array is just formatting (e.g., agree its to be a 4x3 array and then after every 4 characters add a line break).

There are plenty of algorithms to randomly permute a string.  For example, the Knuth shuffle (aka Fisher-Yates shuffle) requires you to go through each element of a list and randomly swap it with itself or an earlier item in the list.  (That is for the i-th position in the list do a swap with the i-th position and the j-th position where j is a random number between 0 and i inclusive).  For example, this shuffle is implemented in python below:

import random

def knuth_shuffle(to_shuffle):
    for i in range(1, len(to_shuffle)):
        j = random.randint(0, i)
        to_shuffle[i], to_shuffle[j] = to_shuffle[j], to_shuffle[i]
    return to_shuffle

We can slightly modify this to take the random numbers as a "key" which tells us what permutation to do:

import random

def generate_key(input_length):
    key = []
    for i in range(1, input_length):
        j = random.randint(0, i)
        key.append(j)
    return key

def knuth_keyed_shuffle(to_shuffle, key):
    shuffled = to_shuffle[:] # create a copy of input to modify
    for i, j in zip(range(1, len(shuffled)), key):
        shuffled[i], shuffled[j] = shuffled[j], shuffled[i]
    return shuffled

def knuth_keyed_unshuffle(to_unshuffle, key):
    unshuffled = to_unshuffle[:] # create a copy of input to modify
    for i, j in reversed(zip(range(1, len(unshuffled)), key)):
        unshuffled[i], unshuffled[j] = unshuffled[j], unshuffled[i]
    return unshuffled

For example in python (after defining the functions above)

In [3]: text = list("123456789***")

In [4]: print text
['1', '2', '3', '4', '5', '6', '7', '8', '9', '*', '*', '*']

In [5]: key = generate_key(len(text))

In [6]: print key
[0, 0, 2, 2, 1, 1, 1, 6, 8, 2, 11]

In [7]: shuffled_text = knuth_keyed_shuffle(text, key)

In [8]: print shuffled_text
['3', '8', '*', '2', '4', '1', '9', '7', '*', '6', '5', '*']

In [9]: knuth_keyed_unshuffle(shuffled_text, key)
Out[9]: ['1', '2', '3', '4', '5', '6', '7', '8', '9', '*', '*', '*']

Some notes: first this will not be particularly secure.

Also, if you aren't particularly fond of using a list of integers as your key, you can encode it to a single integer between 0 and (n!-1) by using the factorial number system (factoriadic).  The key is essentially a number written in base factorial with the least significant digit first -- the first digit is 0 or 1; second digit 0,1, or 2; third digit 0, 1, 2, or 3, ... n-th digit is an integer from 0 to n inclusive.


Elliptic Curves - Proving that the group is not cyclic I have a question from Stinson: 7.14. The question states:

  Suppose that $p > 3$ is an odd prime, and $a,b$ is an element of $\mathbb Z_p$. Further, suppose that the equation $x^3 + ax + b$ is congruent to $0$ ($\mod p$) has 3 distinct roots in $\mathbb Z_p$. Prove that the corresponding elliptic curve group $(E, +)$ is not cyclic. Hint: Show that the points of order two generate a subgroup of $(E, +)$ that is isomorphic to $\mathbb Z_2 \times\mathbb Z_2$.

I've read through the elliptic curve material in the chapter preceding this question but I'm still a little hopeless. Can anyone explain or push me in the right direction on how to show/answer this?

I understand that points of order two (from the hint) follow the formula: $[2]P = \mathcal{O}$ but I'm not sure how this relates.

Can anyone explain or push me in the right direction on how to show/answer this?

The first obvious thing to ponder is "what does it mean that a 'group is cyclic'?  What properties does a cyclic group have, that noncyclic groups do not?"

(Broader hint: a cyclic group has a generator; noncyclic (finite) groups do not)

  I understand that points of order two (from the hint) follow the formula: 2P = 0 but I'm not sure how this relates.

It relates quite a bit, actually.  Can a cyclic group have two different elements of order 2?

Update: since Dexter has solved the problem, I'll lay out the proof I was originally trying to suggest.

One fundamental property of all finite groups is that, if $n$ is the number of group elements, we have $xP = (x \bmod n)P$ (for any integer $x$ and any element $P$).

In addition, a finite group is cyclic if it has a generator, that is, an element $G$ for which all elements can be expressed as $xG$ (for some $x$).  In addition, for any $P$, we always have $xG = P$ for some $0 \le x < n$.  In particular, $xG \ne 0$ for any $0 < x < n$.

Now, for the group in question, we have two distinct elements $P_1$ and $P_2$, both of order two (actually, we have three, we only need two).  That is, $P_1 \ne P_2 \ne 0$, and $2P_1 = 2P_2 = 0$.

Now, suppose the group is cyclic; if so, we have a generator $G$.  We know $P_1$ can be expressed as $P_1 = x_1G$ for some $0 \le x_1 < n$.  We also have $2P_1 = 0$, that is, $2 (x_1 G) = (2 x_1)G = 0$.  We know that $(2x_1)G = (2x_1 \bmod n)G$, and if that is the neutral element, we must have $2x_1 \bmod n = 0$.  The only value $0 < x_1 < n$ that can satisfy that is $x_1 = n/2$ (which implies that $n$ must be even).

However, by the same reasoning, if we have $P_2 = x_2G$, we have $x_2 = n/2$, but that would mean that $P_1 = (n/2)G = P_2$, and so the two points of order two were the same, but we know they aren't.

Hence, there cannot be a generator, and hence the group cannot be cyclic.

This proof may sound a bit lengthy, however, that's mostly because I spelled out the logic quite explicitly, listing the various assumed properties of groups.  Once you get more acquainted with group theory, this logic would be more natural.


What's the proper choice for the block size of a sponge-based hash? While having a discussion about the future of Keccak in our library, we came to the discussion of how to properly assign a "block size" to Keccak (or more generally any sponge-based hash if possible), especially for use with HMAC (mostly out of API compatibility reasons).
The block size itself is a phenomen from the days when Merkle-Damgard hashes were the hash-functions of choice (such as MD5, SHA-1, SHA-2) and the HMAC security proof relies on the fact that the key is padded to at least a full block size and thus the block size requirement can't be eliminated from the HMAC interface.

So what's the cryptographic standard / recommended practice to assign a block size to Keccak (or a sponge-based hash)?

The "block size" matters for Merkle-Damgård functions because the HMAC security proof relies on that block size. For other functions, and in particular sponge functions, the block size for HMAC is mostly a matter of convention.

In fact, HMAC uses two nested calls to the function because such a construction is more or less needed to ensure security with MD function. This is widely considered to be a flaw in the Merkle-Damgård construction. Sponge functions are supposed not to have that flaw, so a simple $H(K || M)$ should be a secure MAC (assuming a proper definition for the concatenation to avoid ambiguities).

So why HMAC is not formally needed to make a MAC out of a sponge function, it can still be used, and any "block size" will work, with no problem to security. The only constraint is that the block size must be larger than the hash function output size, because HMAC mandates that when the key is longer than the block size, the hash of the key is used instead; this cannot work if the block size is smaller than the hash output.

In the case of Keccak, the submission package states in section 5.1.1:

  Several standards that make use of a hash function assume it has an input block length and a
  fixed output length. A sponge function supports inputs of any length and returns an output
  of arbitrary length. When a sponge function is used in those cases, an input block length and
  an output length must be chosen. We distinguish two cases.

  For the four SHA-3 candidates where the digest length is fixed, the input block length
  is assumed to be the bitrate r and the output length is the digest length of the candidate
  n ∈ {224, 256, 384, 512}.
  For an instance with variable-length output, the output length n must be explicitly
  chosen to fit a particular standard. Since the input block length is usually assumed to
  be greater than or equal to the output length, the input block length can be taken as an
  integer multiple of the bitrate, mr, to satisfy this constraint.

And then, in section 5.1.3:

  HMAC [1, 25] is fully specified in terms of a hash function, so it can be applied as such using
  one of the Keccak candidates. It is parameterized by an input block length and an output
  length, which we propose to choose as in Section 5.1.1 above.

  Apart from length extension attacks, the security of HMAC comes essentially from the
  security of its inner hash. The inner hash is obtained by prepending the message with the
  key, which gives a secure MAC. The outer hash prepends the inner MAC with the key (but
  padded differently), so again giving a secure MAC. Of course, it is also possible to use the
  generic MAC construction given in [6], which requires only one application of the sponge
  function.
  From the security claim in [12], a PRF constructed using HMAC shall resist a distinguishing
  attack that requires much fewer than 2c/2 queries and significantly less computation than
  a pre-image attack.

So, in the case of Keccak (thus, presumably, SHA-3 too), the "block length" for HMAC is to be $1600 - 2x$, where $x$ is the hash output length, in bits (the "bitrate" and the "capacity" are such that their sum is $1600$, and the capacity is twice the hash output length).


Variants of Bilinear Diffie-Hellman Assumption Could someone point me to the paper/reference where the following variant of q-strong Bilinear Diffie-Hellman assumption was used?

Given $s \in \mathbb{Z}_p^*$ and $g, g^{\frac{1}{s}}, g^{s}, g^{s^2}, \ldots, g^{s^q}$ it is difficult to compute $g^{\frac{1}{s + c}}$ for $c \in \mathbb{Z}_p^*\setminus \{-s\}$.

Essentially, I am looking for the variant which has $g^{\frac{1}{s}}$ as a part of the public parameter.

To the best of my knowledge, this hard assumption is introduced by Boneh and Boyen in this paper.

But I don't think so the assumption that you mention being hard, because $c=0$ is a simple solution for it. Then the element $g^{\frac{1}{s}}$ should not publish. Also, this assumption is not bilinear because the challenge is an element in the cyclic group of $\mathbb{G}$ and it is not $e(g,g)^{\frac{1}{\alpha+c}}$.


can a weak cipher in a cascade weaken the result? So i am a real beginner .
And I use AES(TWOFISH(Serpent))) for my veracrypt file .
So I asked myselfe a Question :

When a Cascade is made the Key is split in parts for each algorythm .
So if We have AES(Twofish)) with the key : Test-password123 The "Test-pass" Part would be used for AES and the "word123" part gor twofish right ?
So if you would use something like rc4(AES)) cascade , The rc4 would weaken the AES cipher right ?

I'm tailoring my question specifically to VeraCrypt where needed.

  So if We have AES(Twofish)) with the key : Test-password123 The
  "Test-pass" Part would be used for AES and the "word123" part gor
  twofish right ?

No.
VeraCrypt (and any other somewhat decent encryption program for that matter) uses a so-called "password-based key derivation function" (more precisly PKCS#5 PBKDF2), which takes the full password and iterates a moderately fast function (a so-called hash function) very often. This is done so an attacker can't easily verify a guess for your password. Now the result (a sequence of bytes) is taken and split into different sub-keys (2-6 keys in the case of VeraCrypt)1.

  So if you would use something like rc4(AES)) cascade , The rc4 would
  weaken the AES cipher right ?

It depends, but in general no.
AES, Twofish and Serpent are so-called block ciphers, that means they take a block of (16) bytes and transform them into a different block of (16) bytes using the key, such that the transformation is reversible given the key and not if not given the key.
These block ciphers need to be run in a so-called mode of operation (XTS in this case). There is no known attack that performs (significantly 2) better than brute-force key search for this cascade, so you are required to perform at least $2^{256}$ operations which is infeasible.
In your concrete example, it depends on the mode of operation for AES. If this mode is a so-called stream cipher then there's a result that states that the encryption is at least as strong as the stronger algorithm.

1: Actually it runs this chain mulitple times to generate a set of key-bytes each time and then splits.
2: Actually double-encryption is only slightly better than single encryption due to the meat-in-the-middle attack.


Key size and finite fields in ECC (References) So somehow I know that the key size in ECC is defined over the number of elements in a finite field or that it is almost equivalent to that (Correct me if I am wrong). However, other than on Wikipedia I cannot seem to find any source (Article, Book, Encyclopedia with a trusted author, etc.) that states this and I am not allowed to use Wikipedia as reference for my work.
I have been scrolling back and forth in my book (Cryptography & Network Security, Sixth Edition) and on Google without finding anything that states exactly this except from Wikipedia. Also, I have looked through the references on Wikipedia and they don't really have anything even though they state it themselves.
Therefore, I would just kindly ask if someone knows of a trusted source where the author is shown that states this, unless I am wrong of course...

The security level is usually taken to be an estimate of the $\log_2$ of the expected cost in bit operations of the best attack attaining probability near 1 of success.  In the case of well-designed elliptic-curve cryptography for a curve $E/k$ over a field $k$, this is usually determined by the cost of the best algorithm for computing discrete logarithms in a subgroup of $E(k)$, the $k$-rational points of $E/k$, with large prime order $\ell$.

The expected attack cost for Pollard's $\rho$ is $O(\sqrt{\ell})$, so, e.g., we estimate a 128-bit security level for breaking X25519, which works in a group whose order $\ell$ is 252 bits; see the discussion at SafeCurves for more on Pollard's $\rho$ cost, and for references to other types of attacks on elliptic-curve cryptography.  The order $\#E(k) = h \ell$ of the group $E(k)$ can't differ from $\#k$, the cardinality of the field $k$, by more than $2\sqrt{\#k}$, by Hasse's theorem; see an earlier answer I wrote for more on the relationship between field $k$, subgroup order $\ell$, and cofactor $h$.

The private key size is usually taken to be the number of bits it takes to encode a secret scalar in $\mathbb Z/\ell\mathbb Z$.  (Again, by Hasse's theorem, $\ell = \#E(k)/h$ can't be much more than $\#k$, and won't be much less unless the group has an unreasonably large cofactor $h$.)  This number of bits can't be less than twice the maximum security size because of the generic Pollard's $\rho$ attack cited above.  In some cryptosystems, though, we don't exactly store an element of $\mathbb Z/\ell\mathbb Z$ but rather a seed that we hash into one as in standard EdDSA, and in others we store $\mathbb Z/\ell\mathbb Z$ alongside other data as in some nonstandard extensions to EdDSA.

The public key size is usually taken to be the number of bits it takes to encode a curve point in $E(k)$.  There are different encoding schemes available.  You could naively encode a pair of elements of $k$, but that's a waste of space with a lot of redundancy that attackers can exploit.  You could encode one coordinate, and transmit the other as a single bit, which requires some work for the receiver to decompress.  You could use fancier compression schemes like Elligator or Decaf, which have better security properties.

Since there are so many different types of cryptosystems and ways to use elliptic curves out there, nothing more specific can be said in general about ‘key size’ unless you have a more specific question.


Is there any examples of information-theoretic secure MPC for dishonest majority against malicious adversary? My research is to propose highly secure MPC protocol with some conditions.
Especially, I want to consider that

security against malicious (active) adversary
dishonest majority setting
information-theoretic security

I know SPDZ family that achieve 1 and 2 above and some protocols that achieve 1 and 3 above.
Could you tell me the MPC that achieves 1, 2 and 3 above?
I want to know this type of MPC as an example, however, I cannot find it.
I think this type of MPC cannot exist if it doesn't have very strong conditions.
The answer "I don't know this type of MPC" is also welcome.

What you are asking for is not possible, not even if you ask for passive security. Here is a sketch of a proof.
Suppose for sake of contradiction you have an $n$-party MPC protocol $\Pi$ for $f(x_1, \ldots, x_n) = x_1 \land x_n$, where the $x_i$'s are bits. This protocol is secure against a computationally unbounded adversary who can passively corrupt $\ge n/2$ parties.
You can take this $n$-party protocol $\Pi$ and construct a related 2-party protocol $\Pi^*$. Player 1 in $\Pi^*$ plays the role of parties 1 through $n/2$ in $\Pi$, and Player 2 in $\Pi^*$ plays the role of parties $n/2+1$ through $n$ in $\Pi$. So $\Pi^*$ is a 2 party protocol that takes input $x_1$ for Party 1 and $x_n$ for Party 2 and computes $x_1 \land x_n$.
The 2-party protocol $\Pi^*$ is secure against 1 corrupt party. Corrupting 1 party in $\Pi^*$ is like simultaneously corrupting $n/2$ parties in $\Pi$, and by our assumption $\Pi$ is secure in that scenario.
So now we have a 2-party protocol $\Pi^*$ for securely computing the AND of two bits, which is secure against a passive, computationally unbounded adversary (who corrupts 1 party). But this is known to be impossible. If you're asking about perfect security, it was proven in:

Kushilevitz: Privacy and Communication Complexity

The proof was later generalized to statistical security in:

Maji, Prabhakaran, Rosulek: Complexity of Multiparty Computation Problems: The Case of 2-Party Symmetric Secure Function Evaluation, section 4