Attack on stream cipher that XOR's the output of two LFSRs There are two LFSRs of different lengths: LFSR-17 and LFSR-25. LFSR-17 Initially contains a two byte seed, with a 1 injected into the fourth bit, for a total of 17 bits. LFSR-25 operates in the same way.

Of the 40-bit key, 2 bytes is seeded into the first LFSR and 3 bytes into the other. If the outputs of each LFSR were simply XORd to produce the keystream, how could we launch a known plaintext to retrieve the key?

There is another method named algebraic attack.

Name each of the keys initial keys by $l_{1i}$ and $l_{2i}$.
Since the LFSRs are linear and the combining function, x-or, is also linear compute algebraic equations
Solve them. They construct a linear system of solutions.

Since only 38 bits are keys, you will only need 38-bit output if the if the equations are linearly independent.

if you use the Gaussian elimination method it will have $40^3$ operations.


What differences between Menezes–Vanstone ECC and ElGamal ECC? After researching ECC encryption, I found that we can use ElGamal cryptosystem with  elliptic curve and can we use  Menezes-Vanstone cryptosystem with elliptic curve. What is the essential difference between the two systems? Which one is better with regards to complexity/performance?

The essential difference between these two encryption schemes is that for standard ElGamal encryption on elliptic curves the plaintext space is the set of points in your elliptic curve group while in Menezes-Vanstone (which can be considered as a variant of ElGamal) the plaintext space is $F_p^*\times F_p^*$ where $F_p$ is the field over which your curve is defined. So what does this mean?

This means that when using ElGamal over elliptic curves you have to map the message to an elliptic curve point before encryption, while when using Menezes-Vanstone you can take your message string, split it up into to halves and interpret these two strings as elements of $F_p$ each.

Alternatively, you can use other "encoding free" variants of ElGamal such as "hashed ElGamal" that avoid the task of mapping
messages to points on the curve. In standard ElGamal on elliptic curves you would compute
the ciphertext as $(C_1,C_2)=(kP,M+kY)$ where $k$ is a random integer, $M$ the message $m$
mapped to a point on the curve, $Y$ the public key and $P$ the generator point.

In hashed ElGamal, the ciphertext is $(C_1,C_2)=(kP,m\oplus H(kY))$ where $H:G\rightarrow \{0,1\}^n$
is a hash function that maps points on the curve to $n$ bit strings. Consequently, you can encrypt $n$ bit
messages, for instance 256 bit if you use SHA-256 for $H$. For the input to $H$ you need to encode the points of the curve in a suitable way.

Regarding performance, standard ElGamal on elliptic curves costs two scalar multiplications and one point addition, where Menezes-Vanstone costs you two scalar multiplication and two multiplications in $F_p$. So Menezes-Vanstone will be cheaper from a computational point of view.

Regarding ciphertext expansion, to encrypt a message (mapped to a point on the curve) with ElGamal, the ciphertext will contain 2 elements of the curve group (which in affine coordinates will be four elements of $F_p$ - and you can bring it down to ~ 2 elements of $F_p$ when using point compression). In Menezes-Vanstone to encrypt a message (which fits into two elements of $F_p$) the ciphertext will contain one element of the curve group (2 elements of $F_p$) and another two elements of $F_p$ (so you have four elements of $F_p$ and using point compression you  come down to ~ 3 elements of $F_p$).

When using ElGamal on elliptic curves you can prove that it provides indistinguishability under chosen plaintext attacks (IND-CPA security), where Menezes-Vanstone does not provide IND-CPA security (this paper shows that it is not a probabilistic encryption scheme and thus not IND-CPA secure). So you should definitely not use the Menezes-Vanstone scheme.

Alternatively, a standardized scheme for public key encryption on elliptic curves is ECIES, which provides stronger security guarantees (IND-CCA security) than ElGamal does (there are ElGamal variants such as Cramer-Shoup wich are IND-CCA secure, but not that efficient as ECIES).


CPA-security of CTR mode I'm self-studying Katz' book (2nd ed), and I have a small question about Theorem 3.32, which says:

  If $F$ is a pseudorandom permutation, then $CTR$ mode is $CPA-$secure.

They present a proof there, but I think that another proof is viable, which is basically a corollary of a theorem they presented earlier.

My proof is the following. Consider Theorem 3.31, which says

  If $F$ is a pseudorandom function, then $m\mapsto \langle r, F_k(r)\oplus m \rangle$ ($k$ is the key, $r$ is uniformly chosen) is a $CPA-$secure encryption scheme.

So, why don't we simply prove that $G_k(\cdot)$ defined as
$$G_k({\tt ctr}) = \langle F_k({\tt ctr}+1), F_k({\tt ctr}+2),\ldots,F_k({\tt ctr}+\ell)\rangle $$
is pseudorandom? we would have by the cited theorem that $CTR$ mode (which is the encryption scheme described in the theorem using $G_k$) would be $CPA-$secure.
Of course, showing that $G_k$ is pseudorandom if $F_k$ is does not impose a problem, since any distinguisher to $G_k$ can be turned into a distinguisher to $F_k$.

Everything makes sense, I don't see why this proof would not work and why did they bother writing a 2 pages long proof for what could be a corollary! (the only thing I think could fail is that the theorem used was proven for length-preserving $F_k$, but -I think- the proof also applies to the general case).

Anyone can point me to a mistake in my argument? btw, this could also prove that $OFB$ mode is $CPA-$secure.

Thanks in advance

One gap in your proposed argument is that $ctr$ is known to the adversary (it is included in the ciphertext), whereas saying "$G_k(ctr)$ is pseudorandom" implicitly assumes that both $k$ and $ctr$ are kept secret.  This is a minor point, because $G_k(ctr)$ is pseudorandom even if the adversary is also given $ctr$.

A more serious gap is that to prove CPA security, you must deal with the fact that the adversary can obtain multiple ciphertexts for messages of its choice.  If, for example, $ctr$ was always the all-zeros string (which would preserve the pseudorandomness of $G_k(ctr)$), the scheme would definitely not be CPA secure, because it would be breakable by a "two-time pad" attack.  So a correct proof must deal with the possibility that $ctr$ might be repeated from one message to the next, or more generally, that $ctr+i=ctr'+j$ for some two initial counter values $ctr, ctr'$ and offsets $i,j$ for two ciphertexts.  This issue is what most of the Katz-Lindell proof is dedicated to addressing, and is the source of the "birthday term" $q^2/2^n$ in the analysis.


Does sending the same message with 2 different keys in OTP leak information? Suppose a common message ($M$) is XOR'ed with two different keys $K_1,K_2$ producing two ciphertexts $C_1,C_2$. Thus,

$$M \oplus K_1 = C_1\\
M \oplus K_2 = C_2$$

On observing $C_1$ and $C_2$, an adversary can obtain the value of $C_1 \oplus C_2 = K_1 \oplus K_2$. Is this scheme semantically secure? Note that $|K_1|=|K_2|=|M|$ and the keys are randomly chosen from a uniformly distributed large key space ($\approx 2^{255}$).

As long as the keys $K_i$ are only used once, this is semantically secure.  To see it, observe that if $K_i$ is a uniformly random value in $\{0,1\}^{|M|}$ then so is $C_i = M \oplus K_i$.


When is AES chosen instead of a stream Cipher (e.g., RC4) during an SSL connection? During an SSL handshake, the browser sends a list of cipher suites to the server, from which the server selects one option.

For data encryption, two of the several possibilities for the ciphers in this suite are AES (a block cipher) and RC4 (a stream cipher).

I understand that AES would be a better choice for applications where all the data is available at once, permitting the use of large blocks. RC4 on the other hand is more suited for applications where  continuous data (that may not be available all at once) is to be encrypted (e.g., real-time data).

My question is: By the time the cipher suites are negotiated (the very first steps of the handshake),  the server is not yet aware of what kind of data the browser is going to ask for. For example, by this time, the server does not know whether the browser will be downloading some large file (suited for AES than RC4).

As a result, the server may select a poor cipher for the process. Can anyone give me some idea on how SSL handles this challenge (of choosing the optimal cipher for the task at hand)?

I understand that AES would be a better choice for applications where all the data is available at once, permitting the use of large blocks. RC4 on the other hand is more suited for applications where continuous data (that may not be available all at once) is to be encrypted (e.g., real-time data).

No, this is not accurate. The block size of AES is just 128 bits. It makes no difference with practical data sizes on the web, since at most you add 16 bytes to ciphertext size.

And anyway, many modes of operation, like GCM which is one of the more common choices with modern servers and browsers, turn AES into a stream cipher.


Paillier Cryptosystem - Practical applications? I wonder: are there any real-world practical applications using the Paillier cryptosystem , as introduced in [1], or some derivations of it?

I'm aware of quite a few schemes proposed in literature how to use it for voting, zero-knowledge proofs and such, and also of many prototypical implementations online, but I can't seem to find any application where a Paillier(-based) scheme was effectively used...(also, I don't think there is any standard defining it).

[1] Paillier, Pascal (1999). "Public-Key Cryptosystems Based on Composite Degree Residuosity Classes". EUROCRYPT. Springer. pp. 223–238

Yes, for example CryptDB uses the Paillier cryptosystem to implement homomorphic encryption for columns that require it. See CryptDB: Protecting Confidentiality with
Encrypted Query Processing (pdf) for a description.

Whether you consider that use "effective" is another matter. Earlier this month there was a back and forth between the CryptDB developers and some Microsoft researchers who claimed to have several attacks on CryptDB. However, as far as I can tell they were on the other forms of encryption CryptDB uses.


Have I made any glaring mistakes in my use of Yao's garbled circuits? I would like to use garbled circuits to provide a service that allows people to vote where they do not need to reveal their votes to my server or to anyone else. Let's assume that I have secure ways to generate garbled circuits, perform oblivious transfer for the inputs, and to evaluate the circuits. Let's also assume that every person who will vote has a login to my service, that they have a working public/private keypair, and that the server has a copy of their public key. I will use this because in this scenario voters won't be able to easily connect to each other, and must communicate through the server.

This is just for a school project/my own interest. I will be very clearly advertising that the project was not done by security experts.

This is how I have envisioned the general flow of information:

The server, knowing the number of voters and having the ids of all the voters (as in, their logins to the service), crafts a garbled circuit which will compute the outcome of the vote.
The server gives this circuit to every voter, as well as the public keys of every other voter that will be participating.
Every voter retrieves their input from the server using oblivious transfer.
Each voter then encrypts their input with the public keys of every other voter. They then send their encrypted input back to the server.
The server then distributes every voter's input to every voter by giving them the version encrypted with the receiving voter's public key.
Every voter decrypts the others' inputs with their private key.
Every voter evaluates the garbled circuit.
Voters send the output of the circuit to the server.
If the server notices any of the outputs are different, it broadcasts that the vote is bad. Otherwise, it broadcasts the outcome of the vote.
Each voter checks that the broadcasted outcome is the same as the outcome they computed.

Have I missed anything obvious here? Do you see any ways to make it more efficient?

Unfortunately, the answer to your question is yes. You have made glaring mistakes. In particular, Yao's garbled circuits are suited for two-party computation only, and here you wish to carry out a multiparty computation. One huge problem that arises with your entire approach is that if the server colludes with one of the voters, then they can learn the inputs of all of the parties. (I haven't looked at all the fine details of the way you propose working, since this inherent problem arises at the onset.)

There is a protocol that generalizes Yao garbled circuits to the multiparty setting; it is called BMR. However, it is less mature and harder to implement.

If you wish to do a simple voting protocol with people voting just for and against, and you wish to just know how many voted in favor, then using an additively homomorphic encryption scheme like Paillier is the way to go. However, like everything in cryptography, it is very hard to get this right if you try to design it yourself. You should look at papers on voting protocols and then choose one of them to implement.

Alternatively, if it's for a school project, then think of a two-party application that is interesting and use garbled circuits.


What is the more accurate way of stating the correctness of a PK encryption scheme? Is it more accurate to state that a public key encryption scheme is correct if for all $m \in M$ and $(pk, sk) \in \operatorname{Gen}(1^k)$
a. $\operatorname{Dec}_{sk}(\operatorname{Enc}_{pk}(m))=m\;$ or,
b. $\Pr[\operatorname{Dec}_{sk}(\operatorname{Enc}_{pk}(m))=m] = 1 - \operatorname{negl}(k)\;$ or,
c. does it depend on the scheme or some other factor?

Deciding among a or b is a matter of choice of definition of public-key encryption. Clearly a is desirable, and b is a fallback in order to allow some interesting cryptosystems. The definition is chosen according to the cryptosystem studied, as in c.
As pointed by poncho in comment, in b as it stands, the meaning is that for all keys and messages, there's negligible probability that decryption does not yield the original message. The encryption algorithm is re-expressed as a deterministic algorithm with an extra input $r$ for the random allowing to achieve CPA security, and it's really meant that
$$\Pr[\operatorname{Dec}_{sk}(\operatorname{Enc}_{pk}(m, r))=m]\quad=\quad1 - \operatorname{negl}(k)$$
where the probability is computed over all inputs $r$ randomizing the encryption. Such tolerance for rare failures is necessary for some cryptosystems, e.g. those based on Hidden Field Equations.
There is at least one other popular alternative to b: we can require that all except vanishingly few keys allow certain encryption and decryption of all messages $m\in M$. We thus compute the probability that there exists a message $m$ and random input $r$ making encryption/decryption fail over the set of keys produced by $\operatorname{Gen}(1^k)$ (or even more precisely, over the set of random inputs to that algorithm re-expressed as a deterministic one with random input $r$). That's the definition of public-key encryption given by Jonathan Katz and Yehuda Lindell's Introduction to Modern Cryptography 2nd edition. Their rationale is allowing RSA with a probabilistic prime test. They explicitly choose to ignore the exceptions.
Update: in IMC 3rd edition, that changed slightly. The probability is computed over the randomness of $\operatorname{Gen}$ and $\operatorname{Enc}$. I think it will stick as the standard definition of public-key encryption.
Yet other cryptosystems are correct with a only, e.g. RSA with proven primes, or ECIES when working with families of curves and generators of proven order.


Inverting the encryption equation of a symmetric cipher I've just started a cryptography course. I am beginning to understand the concepts (I'm only in week 2) but I just can't get my head around the theories and principles when written as equations.

I've been posed the below question to answer:

  Consider a very simple symmetric block encryption algorithm in which 64-bit blocks of plaintext are encrypted using a 128-bit key. Encryption is defined as:

  $$C = (P ⊕ K_0) ⊞ K_1$$

  Show the decryption equation, that is, show the equation for $P$ as a function of $C$, $K_0$ and $K_1$

  $C$ = ciphertext
  $P$ = plaintext
  $K$ = secret key
  $K₀$ = leftmost 64 bits of secret key
  $K₁$ = rightmore 64 bits of secret key
  $⊕$ = bitwise exclusive or (XOR)
  $⊞$ = addition mod $2^{64}$

I simply don't understand what the function of $⊞$ serves.

Can anybody assist me with tackling this problem? I just don't know where to start other than to $P = (C.....)$ possibly? I'm unsure as to what the 'addition mod 2⁶⁴' refers too.

EDITED FOR CLARIFICATION

So if for example, our plaintext is:-

messagea (ASCII)

01101101 01100101 01110011 01110011 01100001 01100111 01100101 01100001   (binary - 64 bit)

and our 128-bit secret key is:-

mysecretpassword (ASCII)

01101101 01111001 01110011 01100101 01100011 01110010 01100101 01110100 01110000 01100001 01110011 01110011 01110111 01101111 01110010 01100100 (binary - 128 bit)

To achieve the first past of the algorithm, "C=(P⊕K₀)", I XOR the plaintext against the first 8 characters (64 bits) of the secret key to get the following:-

01101101 01100101 01110011 01110011 01100001 01100111 01100101 01100001

01101101 01111001 01110011 01100101 01100011 01110010 01100101 01110100 ⊕

00000000 00011100 00000000 00010110 00000010 00010101 00000000 00010101

Now, how do I then apply '⊞K₁' to the above? I am aware that I need to do something with the above to the last 64-bits of the key but I'm unsure what calculation. If someone could walk me through it, that'd be great. Thanks

Addition modulo $N$ in the above example is another way of key mixing that adds more non-linearity to the cipher as it operates across a group of $N$ bits, vs XOR which is addition modulo 2 on individual bits. For example, where $N=2^6$ or 64:

$44 ⊞ 44 = 24$

$44 ⊕ 44 = 0$

Addition within larger groups is also used in mixing operations such as Pseudo Hadamard Transformations. Key addition instead of XOR also plays a prominent role in the block ciphers Twofish and IDEA.

Edit:
Here are posts with more detail on the choice of addition:

What exactly is addition modulo $2^{32}$ in cryptography?

Why Addition Mod 32?


Can the round function $F$ in a Feistel Network be practically any non-invertible function? This question might seem silly, but how true is the fact that the round function $F$ does not have to be invertible?

I am curious to know this, because non-invertible functions can be very lossy, i.e., can lose much of the information related to the input, hash functions for example.

Yes you could use a hash function as round function, but if you are using the "same key" over all rounds, you are vulnerable to slide attacks. Using a hash function is not a very good idea.

Your round function should not introduce biases, should not lead to special differences (attack: differential cryptanalysis), and it should also not be writable as a linear equation (attack: linear cryptanalysis). You should take care of how your round function will work when the round keys are slightly modified (attack: related key attacks), and you should take care of impossible differentials. If you got all that right, you can use any $F$ which passed these criterions.

Short answer is, $F$ needs to be carefully selected. And “yes” you are interested, that $F$ will "loose as much information about the input" as possible.

Your second question:

  This question might seem silly, but how true is the fact that the round function $F$ does not have to be invertible?

Your round function does not need to be invertible, because the classic balanced Feistel construction will create two halves, where only one half is modified, and the other kept in clear text/unmodified. After each round both halfes are exchanged and the modified half becomes the fixed one and the previously unmodified half is now encrypted. If you now reverse the order of the keys/rounds you can decrypt the message again. The Feistel construction itelf is invertible.


AES-PMAC-SIV AE algorithm AES-SIV is a very robust and safe algorithm but performance isn't great. AES-PMAC-SIV, should provide a great parallelization, increasing performance and ensuring the same robustness. Indications of this can be found on the GitHub pages of Miscreant  and on the IETF mailing list.

How does it compare to the other authenticated encryption (AE) algorithms? Does it have the technical potential to become a popular algorithm and overcome the other AE algorithms, that is, is it technically (security properties / performance) superior in (many?) aspects to other currently (somewhat) widely used AE schemes?

I don't think it will become popular. AES-SIV has a main usage as key wrapping mechanism for its deterministic encryption properties. But keys are generally pretty small; parallel computation is certainly not required for minimal amounts of data.

With regards of performance: yes it can be parallelized. But on a modern machine you may need a lot of enhancements to beat AES in CTR mode + AES CMAC on a single thread that uses hardware acceleration. Intel's AES-NI + GCM acceleration can get throughput of 2 Gbps (that bits, mind you) on a single core of a Westmere chip (that's an old chip doing 2.4 GHz) - and that's within an actual IPSEC tunnel. You may want to go faster, but it might be that other components of your system cannot keep up. For server components that can have any amount of connections: if you have a 8 core chip (and 8 connections) you may easily saturate a 10 Gbps network card.

AES-PMAC still requires a single AES block encrypt per plaintext block. So even though it can be parallelized it will be outperformed by special MAC constructs such as GMAC or Poly1305 that do not require block cipher calls for each block of plaintext. You'd need at least another thread to make up for the difference in performance, and they you'd still need to manage the multi-threading.

I presume that the authentication tag is relatively secure, even if only the first x bytes are used for authentication tag. That's maybe nice for embedded platforms, but those commonly don't go for multi-threading / parallel computation. It's certainly an advantage over other MAC constructs that do not have this property, but not over others such as AES-SIV, AES-EAX or AES-CCM.

The one good reason why it may get popular is when the cryptographic community decides to switch from authenticated encryption to encryption that is largely impervious to nonce reuse (nonce misuse resistance).

But note that GMAC, as used in GCM mode, may actually performed in parallel as well; putting the parts together requires some additional calculations displayed here. So GCM-SIV may also be executed in parallel, using a less computationally expensive MAC calculation. GCM in SIV mode sidesteps the issues with the nonce that makes it extremely sensitive to nonce reuse. MAC calculations that use a block cipher are simply not that efficient.


How is the quality of a password calculated and what does it mean? While using Keepass and using it to generate random passwords, I always have noticed the "quality" section but truthfully have never known what it actually means.

So my questions are;

How much entropy is enough?
How much is overkill?
How does entropy actually apply to the length of time it may take for an attacker to guess a password?
How is entropy calculated and how may my addition of a new character affect the number of bits?
What is the theoretical max?

Thanks!

How much entropy is enough?

For a password, something around truly 96-bits of entropy is enough. After all password usually go through some slow password hashing which increases the work load for attacks significantly. And even with a super-fast verification function 96-bit should be just out of reach of attackers.

  How much is overkill?

Going above 500-bit is very likely to be overkill, even for an actually imperfect source of entropy. If your entropy is "true" (ie what is reported would actually be the entropy), then there's literally no point in going beyond 256-bit and maybe even 192-bit.

  How does entropy actually apply to the length of time it may take for
  an attacker to guess a password?

Entropy denotes the uncertainity in a string1 and is measured logarithmically in bits. So if you increase the entropy by one, the string is twice as uncertain and thus can take twice as many values which means an attacker has to try twice the amount of passwords. Shortly put: Let $l$ be the actual entropy (in bits), then there are $2^l$ possible different values to be tried.

  How is entropy calculated and how may my addition of a new character
  affect the number of bits?

What I strongly suspect this tool to be doing is to analyze the character set used in your password, looking for common words in a dictionary and then making its guess for the entropy (try this by comparing the entropy of potat with potato, the latter being reported at 12 bits and the former at 20). The upper bound for the entropy is $$\leq{|\Sigma|}^n$$ where $\Sigma$ is the alphabet / group of characters that the tool estimates could appear in your password and $n$ is the length of the password. For example if you use upper-case it's gonna include those as opposed to excluding them if you don't have an upper-case letter.
Note that what the tool reports is an estimate at best and the actual entropy can be significantly lower due to a bad RNG being used, an implementation flaw or you simply having bad luck and hitting a string that's more easily guessed / guessed sooner by an attacker.

  What is the theoretical max?

Theoretically there's none. Practically it's limited by the size of your RAM probably (because the password has to fit in there).

1Actually the uncertainity in a random variable, but that's details here.


Public key cryptography instead of passwords for web authentication The usual way for a user to authenticate themselves to a website at the application layer is with a shared secret - the user's password. If a user is connecting to a bank, they give the bank their password, and the bank stores the password, hopefully not in plaintext, but as a salted hash run through a slow KDF.

There are some weaknesses to this scheme, for example the fact that users tend to reuse passwords across websites, and that many server operators do not take the appropriate precautions when storing their users' passwords. Even if a user randomly generates strong passwords for each website, the server could still lose the password, so the user must trust the server operator to safely store the password.

If a public key scheme was used, similar to SSH key authentication, the user would not have to trust the server. The server could store the user's public key, which compromises nothing if stolen. If the user's private key is stolen, they can still revoke the key, preventing the thief from using it.

SSH supports this kind of authentication.
Are there any existing systems that do authentication to websites, as opposed to SSH servers, like this?

Basically, are there any systems that replace user passwords with signatures from the user's private key?

The WebAuthn standard sounds similar to what you are describing.


Index Calculus for Discrete Logarithm I'm studying the Index Calculus method for Discrete Logarithm. In the book "Introduction to Cryptography with Coding Theory" by Trappe it's told that, if $$\alpha^k\equiv \prod p_i^{a^i} \mod p$$ holds, then $$k\equiv \sum a_i L_\alpha(p_i) \mod (p-1).$$ However, it doesn't show why. Can you explain to me?

Given $$\alpha ^{k}\equiv \prod p_{i}^{a^{i}}  \mod p$$

take $\log$ of both sides to base $\alpha$

\begin{align}
\log_\alpha(\alpha ^{k}) &\equiv \log_\alpha(\prod p_{i}^{a^{i}})  \mod p\\
k &\equiv \sum \log_\alpha(p_{i}^{a^{i}})  \mod p-1 \quad\text{;by Little Fermat}\\
k &\equiv \sum a_i \log_\alpha(p_{i})  \mod p-1\\
\end{align}

Here $\log_{\alpha} = L_{\alpha}$.


What happens to entropy after hashing? What happens to entropy after hashing?

Suppose you have a key with entropy $k$. Can entropy $k$ be increased by hashing the key?

The answer rather depends on what you mean by 'entropy'; if you mean 'Shannon Entropy', then no, a deterministic function cannot increase entropy.

For example, if the unhashed password has only 7 different possible values, then the hashed version of the password will also have (at most) 7 different possible values; you've made things look more obscure, but you haven't actually changed anything as far as entropy is concerned.

The standard definition of Shannon entropy is:

$H(X) = \sum -p_i\  log_2 p_i$

Where $p_i$ is the probability of the $i$th possible sample value.  That is, the Shannon entropy is defined solely in terms of probability distribution, and not how that probability distribution appears.

If we have a Hash function $SHA$ which doesn't have any collisions, then it has no effect on entropy; that is, $H(X) = H(SHA(X))$; that's because the probabilities involved in the probability distributions are precisely the same; if a specific password $x_i$ had a certain probability, then the hashed form of that password $SHA(x_i)$ will appear with that exact probability in the hashed distribution.

And, if the Hash function $SHA$ does have a collision, that is, if $SHA(x_i) = SHA(x_j)$, then (assuming both $x_i$ and $x_j$ have nonzero probability), then $SHA$ will actually reduce the entropy.  And, this is not a violation of collision resistance; collision resistance only states that it is hard to find such a collision, not that one does not exist.

This is easier to see in the extreme case; suppose we have two possible passwords ("Mary" and "Susan"), and both of those passwords have probability $0.5$; this means that the entropy of the password is 1 bit; an attacker can perform go through all possible values by checking on two different passwords.  If you hash the password, you may come up with two images (39e74b4e80ba656f773669ed60315a and 98e15403b2b1ea5022fc42b3490cc76e in hex) that look different, however there are still only two possible values, and so the effort an attacker would have in trying those two values in unchanged.


For SHA3-512, SHA512, and Whirlpool, which algorithm has least probability for collision and preimage collision? For comparing these 3 hash functions SHA3-512, SHA512, and Whirlpool. Which one is strongest against collision and preimage attacks. Are they fundamentally the same because of the same size output? Please disregard all other characteristics of the algorithms.

Generic expected pre-image resistance for a hash function with $n$-bit output is  $\mathcal{O}(2^n)$
Generic expected collision resistance for a hash function with $n$-bit output is $\mathcal{O}(\sqrt{2^n}) = \mathcal{O}(2^{n/2})$ due to the generic birthday attack on the hash functions.

\begin{array}{|c|c|c|c|}\hline
\text{name} & \text{output size} &  \text{pre-image resistance} & \text{collision resistance} \\ \hline
\operatorname{SHA-512} & 512 & \mathcal{O}(2^{512})& \mathcal{O}(2^{256}) \\ \hline
\operatorname{SHA3-512} & 512 & \mathcal{O}(2^{512}) & \mathcal{O}(2^{256}) \\ \hline
\operatorname{Whirlpool}& 512 &\mathcal{O}(2^{512}) & \mathcal{O}(2^{256}) \\ \hline
\end{array}

Therefore they have the same as long as there is no attack better than these on any of these.

Note 1 There is not pre-image collision. There is pre-image attack or pre-image resistance.

Note 2 SHA-512 is vulnerable to length extension attack. Prefer the SHA3-512 or Blake2 series.


How come hash salt doesn't make a hash ineffective? I am not a cryptography expert. I watched this video regarding hashing and salting as part of the course User Authentication With Express and Mongo in teamtreehouse.com.

I understand from the video that a hash is a representation of a password stored in the DB, used to prevent say company workers from copying password (the hash will be suited to a password given in authentication) and first created by passing the password in a hash function (simple hash function in this case).
I also understand that salting a hash is randomizing the hash.

What I didn't understand from the video is how would an hash keep being evaluated properly if we change it (salting it), each authentication anew. In other words, how could it still match the password.

Edit: Maybe I should have ask: What is the mechanism that creates the salt, juxtaposing it to the hash, and make sure the password will comply to the hash+salt combination.

The salt is stored in plaintext next to the hash and the same salt is used when checking a password.

Its purpose is to slow down attackers who obtained a copy of the database:

They must attack each password on its own (they need to try each input for each hash instead of trying each input and comparing the output to all hashes at once).
They can't make use of huge precomputed lookup tables ("rainbow tables") since salting is essentially equivalent to giving each user their own hash function.

There is no need to keep the salt secret or store it more safely than the corresponding hash.

(This is as opposed to pepper, which is mixed into the hash in the same way but is fixed per application and not stored in the database. This tries to defend against attackers who obtained database access, but not the application's program code or configuration files.)


Reversible Decryption in Symmetric Key Algorithms I am currently learning the Internal Working of Symmetric Key Algorithms, like DES, AES, BlowFish, IDEA just to name a few.

These are all quite complex Encryption alogrithms, which requires a lot of confusion and diffusion of the Plain Text to produce the
corresponding Cipher Text.

But one thing that most of these (if not all) have in common is the fact that their decryption algorithms are sort of reverse of
the encryption algorithm used to encrypt them.

For Ex:-

  DES decryption requires the Key Portions to be revealed in reverse order (Ex. if K1, K2, K3....K16 were used for encryption, then
    for decryption the same encryption algorithm must be feeded keys in order K16, K15, K14...K1)

  IDEA decryption requires some ulteration in Key Generation, and the pattern of subkeys. And the decryption subkeys are
    actually the inverse of the encryption subkeys.

  BlowFish decryption process requires the reversal of P-array values

  AES decryption requries the reverse of encryption process (inv Sbox, inv CMatrix etc)

The question is, why are the encryption and decryption so much similar.

1) Are these algorithm's made while keeping their decryption process (Easy Reversibility without any extra algorithm/hardware) in mind?

2) Or is this a property that Symmetric Key Algorithms exhibit in general?

Why are encryption and decryption so similar?
Block ciphers are designed with reversibility in mind. Of course, to maintain data privacy, they are only reversible with the proper key. This is because a block cipher with a given key is a permutation. It is a bijection of all possible block-sized inputs to all possible block-sized outputs. This makes it possible to reverse, if given the key. The exact permutation is selected by the key, so what ciphertext block a given input maps to depends on the key. They are designed with this in mind to keep decryption simple.
Take the following permutation of a set of four different elements, chosen at random:
$\pmatrix{0&1&2&3\\1&3&2&0}$
Because it is a bijection, there always exists an inverse:
$\pmatrix{0&1&2&3\\3&0&2&1}$
As you can see, the permutation maps $1$ to $3$, so the inverse permutation maps $3$ back to $1$. A block cipher does just this, except the permutation is not fixed. Rather, it is "chosen" by the key. Each key selects a different permutation from all possible permutations. Additionally, there are far more than four elements. AES encryption permutes a set of $2^{128}$ different elements, chosen by the key. Decryption simply gives you the inverse, allowing you to recover the plaintext. All the complex math behind block ciphers is necessary because it would be impossible to store every bijection ($2^{128}! \times 2^{128}$) in a table.
Is this a property of all symmetric ciphers?
Block ciphers are not the only symmetric ciphers. Stream ciphers do not need to be reversible, as all they do is generate a pseudorandom stream of data, called the keystream, which is XORed with the plaintext. Decryption does not require running the stream cipher in reverse, but generating the same keystream (by selecting the same key) and XORing it with the ciphertext.
It may be interesting to note that it's possible to turn a regular block cipher into a stream cipher by using a mode of operation like counter mode, or CTR, which generates the keystream by encrypting an ever-increasing counter. Decryption with CTR mode actually involves using the block cipher in the encryption direction, so it's possible to implement CTR (or any other mode that turns a block cipher into a stream cipher) without ever needing to implement decryption. See the following diagram from Wikipedia:

Is this a property of all symmetric permutations?
Also no! Although it's pretty common for block ciphers to be designed to make the inverse permutation easy to implement, not all permutations do this, even if they are technically reversible. This is common for public permutations. That is a permutation that is fixed and does not require knowledge of a secret key to invert. They are common in sponge constructions, which get their high security by ensuring a substantial portion of the input to the permutation is secret, alleviating the need for a key. An example of a public permutation is Gimli, which was designed only in the forward direction:

Like Keccak, Ascon [15], etc., we evaluate performance only in the forward direction, and we consider only forward modes; modes that also use the inverse permutation require extra hardware area and do not seem to offer any noticeable advantages.

In addition to being easier to implement, there is no need to cryptanalyze its inverse. While it may not be intuitive, the fact is that sometimes the inverse of a permutation is less secure than the permutation in the forward direction. This was the case for the FROG block cipher. It was an AES candidate during the NIST AES competition which did not make it past the first round. It displayed slower diffusion in the decryption direction (the inverse permutation for a given key) than in the encryption direction.


A login token algorithm Hi illuminated crowd of cryptography.

I am currently working on a login token for a web API.

The feature for the token is to be a mostly featureless identifier. The only property I need is, that I should be able to distinguish it from a random number before I query my database if it is actually valid.

I also don't want the token to be large.

This is what I came up with.

Receive a Username/Password, validate against database, collect user-properties. This can be rather expensive.
Generate a login token to be used for subsequent calls of the user, until the token expires, timeout is not part of the token.

create a UUID
Encrypt it with AES-128 using a server key plus a user specific IV
SHA-1 the original UUID (fake SHA won't matter)
append the encrypted payload to the hash
encrypt again to generate the token

write the token with the user-object to a memory-hash-db

To test the validity of the token, I decrypt the token.
Then decompose the token into hash and encrypted payload.
Decrypt the UUID, hash it and compare to given in token.
If they match, try the lookup in the db.

This is a lot of calculation and hashing. I suppose it is rather fast, yet, the token is only valid for about 10 minutes (at max). Is it worth the effort? Doing a DB lookup may be faster for the in-memory cache.

So, an alternative would be to simply create a random number, big enough, and store it into the cache-database and lookup the token every time. Given the characteristics of UUIDs, an attacker should have a hard time to guess a token currently valid in the database.

Content encryption is established and MITM attacks are avoided using HTTPS.

What is your experience with this situation - is cryptography improving security in this case? What is a good algorithm to create such a token?

UPDATE:

After reading about AES-GMAC and AES-GCM as suggested in the comments, I decided to drop my original idea and use GMAC instead. It offers some nice features:

it is proven
it is approved by NIST
it is standardised, I already have a token-generator build in no time.
I can easily expand the token with encrypted information, if required.
tokens are acceptable in length (<100char BASE64)

My original question has been answered by giving me the hint to use a MAC on the token instead of cryptography. With AES-GMAC I get both, just in case :-)

Not using a MAC or crypto would make an attack with guessed tokens very easy. The MAC protection makes this very hard to hit.

Thanks for your help!

For a featureless identifier a simple random number + MAC thereof should work.

You don't actually need encryption because your number doesn't contain any sensitive information and checking the MAC allows you to verify that this is actually a token that you generated.

This requires only a symmetric key for MACing on the server.


What is the length of an RSA signature? Is it the same as the bits of the key (So a 2048 bit system will yield a 2048 bit signature)? At most as the key? Or something else entirely?

PKCS#1, "the" RSA standard, describes how a signature should be encoded, and it is a sequence of bytes with big-endian unsigned encoding, always of the size of the modulus. This means that for a 2048-bit modulus, all signatures have length exactly 256 bytes, never more, never less.

PKCS#1 is the most widely used standard, but there are other standards in some areas which may decide otherwise. Mathematically, a RSA signature is an integer between $1$ and $N-1$, where $N$ is the modulus. In some protocols, there can be some wrapping around the signature, e.g. to indicate which algorithm was used, or to embed certificates. For instance, in CMS, a "signature" contains the RSA value itself, but also quite a lot of additional data, for a virtually unbounded total size (I have seen signatures of a size of several megabytes, due to inclusion of huge CRL).


DSSP reduction to DSSI In  “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies" by DeFeo, Jao and Plut, a reduction from the Decisional Supersingular Product (DSSP) problem to Decisional Supersingular Isogeny (DSSI) problem is mentioned.
However, I could not find such a reduction anywhere, or even some kind of idea how to compute such a reduction.

Question: How to reduce DSSP to DSSI?

Alternativly some source for post-quantum cryptography reductions featuring the given problem?

Suppose given a DSSP instance $\phi$, $(E_1,E_2,\phi')$ as defined in the paper. The goal is to use a DSSI oracle to decide if $\phi'$ is "parallel" to $\phi$ with "distance" $\ell_B^{e_B}$, that is, whether there exist $\ell_B^{e_B}$-isogenies $\psi,\psi'$ that make the following diagram commute.

$$\require{AMScd}\begin{CD}
E_0 @>\phi>> E_3\\
@V\psi VV @VV \psi'V\\
E_1 @>>\phi'> E_2
\end{CD}$$

By definition of the DSSP problem, we are in one of two worlds:

$(E_1,E_2)$ were chosen by picking an $\ell_B^{e_B}$-isogeny $\psi$ and computing $(E_1,E_2,\phi')$ to satisfy the diagram; in particular, $E_1$ is $\ell_B^{e_B}$-isogenous to $E_0$.
$(E_1,E_2)$ were chosen randomly among all pairs of $\ell_A^{e_A}$-isogenous supersingular curves over $\mathbb F_{p^2}$; in particular, $E_1$ is random.

Hence by applying the DSSI oracle with respect to $\ell_B^{e_B}$-isogenies to $E_1$, we may distinguish between those two worlds with high probability.

There is a chance of false positives: A random curve $E_1$ may still be $\ell_B^{e_B}$-isogenous to $E_0$ by chance, and it's unlikely that $E_2$ would be $\ell_B^{e_B}$-isogenous to $E_3$ in that case. However, it is not hard to show that the advantage of our constructed DSSP oracle is at least $1-\varepsilon$ times that of the DSSI oracle, where $\varepsilon$ is the proportion of curves $\ell_B^{e_B}$-isogenous to $E_0$ within the set of all supersingular elliptic curves over $\mathbb F_{p^2}$.
Typically, parameters are chosen such that $\ell_B^{e_B}\approx\sqrt p$, hence since the number of supersingular elliptic curves over $\mathbb F_{p^2}$ is lower bounded by $p/12$ we have $\varepsilon\leq (\ell_B+1)\ell_B^{e_B-1}\cdot 12/p\approx1/\sqrt p$ which is exponentially small in $\log p$. Therefore our DSSP oracle has non-negligible advantage assuming the DSSI oracle does.

Note that the DSSI problem is only stated for $\ell_A^{e_A}$-isogenies in the paper. I assume the intention was to leave the degree variable, or at least (by symmetry) also allow Bob's degree $\ell_B^{e_B}$, which I used above.


What is the benefit of zero knowledge identification (Fiat Shamir) over a standard digital signature? Let's say there is a public key $v$.
Peggy has to prove to Victor that she has the corresponding private key $a$. Of course she doesn't want to disclose $a$ to Victor, but just to prove that she has the key.
Question: What is the benefit of "Solution 2" described below (a.k.a. Fiat-Shamir), which seems more complex and using zero knowledge proofs, when there is an easy solution (see Solution 1)?
Solution 1 (easy):

Victor generates a random number $r$, encrypts it with the public key $v$, and sends the encrypted message $r_E$ to Peggy
If Peggy has the private key $a$, she can decrypt $r_E$ into $r$, and send $r$ back to Victor and claim: "Hey Victor, here is $r$, this is the proof I can decrypt your message $r_E$, so this proves I have $a$"
If Peggy doesn't have the private key $a$, she cannot decrypt $r_E$, so she cannot prove anything.

I don't know the name of this simple scheme, but I think this can be done with nearly any public/private key encryption algorithm, and it seems safe.
Solution 2 (Fiat-Shamir, interactive zero knowledge proof):

$a$ is the private key, $v = a^2 \pmod n$ is the public key

Peggy generates a random number $r$ and sends $x=r^2 \pmod n$ to Victor

Victor sends 0 or 1 (randomly) to Peggy

If Peggy receives 0, she has to send $r$ to Victor (he can then check if $r^2$ is $x$ modulo $n$)
If Peggy receives 1, she has to send $y = r \times a \pmod n$ to Victor (he can then check if $y^2 \times v^{-1}$ is $x$ modulo $n$)

Repeat from step 2 at least $k$ times: the higher $k$ the smaller the probability ($2^{-k}$) of passing the test succesfully without actually knowing $a$

What is the benefit of complex Solution 2 when you can just do Solution 1?

Solution 1 has some weakness when the verifier is malicious. If the prover's private key $a$ is used for decryption, Solution 1 provides the verifier with a decryption oracle, i.e., a malicious verifier can decrypt any ciphertext encrypted with the public key $v$. On the other hand, Solution 2 reveals nothing about the private key $a$ because the random number $r$ (which masks the private key $a$ when the verifier sends a bit 1) is chosen by the prover rather than the verifier.


Brute-force attack given small search-space and hash prefix Suppose we have a value $secret which is a random 56-bit (7-byte) string. Suppose an adversary wishes to discover $secret.  The adversary cannot directly see $secret, but he can see substr(sha1_hex("$secret $salt"), 0, 8) (where $salt
is public -- and perhaps irrelevant to our calculations).

Since $secret is only 56-bit, it may be vulnerable to a brute-force attack by a modern supercomputer -- if you can find an offline test. An attacker might use the hash-prefix as a test:

    function brute_force_hash_prefix($targetHashPrefix, $salt)
      $candidates = array()
      foreach possible $candidate which is 56-bits long
        $candidateHashPrefix = substr(sha1_hex("$candidate $salt"), 0, 8)
        if ($candidateHashPrefix == $targetHashPrefix)
          $candidates->add($candidate)
      return $candidates

However, the test is not deterministic -- the attacker only has the first 8 hex digits (32-bits) of the SHA-1 hash. This creates a risk of false-positives (ie the brute-force attack may return multiple $candidates which all yield the same first 8 hex digits).

The question: statistically speaking, how many $candidates should one expect to produce?

(Why would one care? If the odds are that only one $candidate will come through, then it's basically over.  Then again, if there are thousands or millions of candidates, then the attacker has narrowed the field...  but still needs to find some additional means for testing/filtering $candidate.)

If you have an $m-$bit output decent hash function (such as SHA1) and you're hashing $k-$bit values, and your list $L$ of candidates is not tiny ($2^{56}$ which is the size of possible candidates, isn't) the function will behave like a random mapping on any substring of its' output.

If your prefix consists of 8 4-bit characters, then you'll
be filtering roughly one out of every $2^{32}$ candidates during precomputation.

Thus, at the end of precomputation, you'll have $2^{24}$ candidates left.

In a large enough list is expected that whatever the correct input is, it has shown up as part of an unknown subset of roughly $2^{32}$ inputs in your filtered candidate list. Since you only have $2^{24}$ candidates left, it's likely that most of them are actually the unique candidate.


PBKDF2 uses HMAC-SHA1 to generate keys, but what is the key for the HMAC? I was reading up on PBKDF2 and noted the following:

DK = PBKDF2(PRF, Password, Salt, c, dkLen)

PRF is a keyed HMAC, but I can't seem to find out what they use as key for the HMAC?

PBKDF2 uses the password as the PRF key.

From the RFC:

  The first argument to the pseudorandom function PRF serves as HMAC's
     "key," and the second serves as HMAC's "text." In the case of PBKDF2,
     the "key" is thus the password and the "text" is the salt.


Block cipher linearity (in relation to hill ciphers) So while I knew hill ciphers were a form of block cipher (I'm assuming all the ones I have solved to date were ECB or something similar), so that got me thinking. Is it possible to use hill ciphers in other modes (ctr, ecb, cbc etc) on a binary alphabet?

A) Could you provide formula/examples of how it would work?
B) How would one launch a plain text attack against these?
C) How would I protect against this attack?

CTR. Assuming d is even (for the nonce and counter), and the nonce and counter are d/2
CBC.
Any other relevant block cipher it could function as

Yes, you can convert the Hill Cipher into almost any mode of operation. For simplicity, assume that $M$ represent the key matrix and $P$ represent the plaintext vector and $C$ is the corresponding ciphertext vector with $C = M\cdot P \pmod{26}$. For simplicity, we omit the mode 26 for the rest.

ECB mode: we can assume that Hill cipher is already in ECB mode. As usual, divide the message into the correct matrix size, you also need a padding scheme.
CBC mode: generate an $IV$ which must be unpredictable, however, this is your least concern, as usual, $ C_0 = M\cdot(P_0\oplus IV) \text{ and } C_i = M\cdot(P_0\oplus C_{i-1})$. You also need a padding scheme.
CTR mode: $C=P \oplus [M \cdot  (\text{nonce ||  Counter})]$. Here one may need to take care of the counter since it is a Matrix. One can consider each cell of the Matrix as a mod 26 counter. No need to padding.
CMC-MAC: Since you have CBC mode, you have it, now. Remember, in CMC-MAC the IV is all zero.

Note 1: For CBC-MAC we don't need just AES, we can use any secure block cipher.

Note 2: the $\oplus$ can generate a number greater than 26. You need to use $+ \bmod26$

And a final note: The Hill cipher is vulnerable to known-plaintext attack which means that it is broken! You cannot build a secure mode of operation from a broken cipher!


Gaussian function in lattices Probability density function of gaussian distribution is
$$ 1/{\sqrt{2 \pi} \sigma}  \times {e^{{(x-c)^2/ 2{\sigma}^2  }}}  $$
in lattices we assume $$ \sigma =s/\sqrt{2 \pi}  $$so the gaussian function becomes
For $$X \in R^n$$ $$\rho_s(X)=1/s^n \times e^{-{\pi}||(x-c||)^2/s^2}$$ but it is given as
$$\rho_s(X)=  e^{-{\pi}||(x-c||)^2/s^2}$$ can you explain why is this difference?

The Gaussian function over a lattice, if you define it with or without the scaling factor $1/s^n$, is not a probability distribution, since it does not sum to 1. In order to construct a probability distribution, that samples points proportionally to the Gaussian function, one has to rescale anyway by dividing by the sum of the Gaussian over all lattice points (even though this is an infinite sum, it is well defined and one can compute sharp bounds on it). So any scaling factor you apply to the Gaussian function will be cancelled out by this normalization anyway, so you might as well define the Gaussian without it.


Determining nonce between unsynced systems It's my first venture into cryptography, and I'm struggling with how to use a nonce in an encryption standard between two digital radios.

The two radios support AES encryption, only requiring a 128-bit key and a nonce for the encryption/decryption of each packet. To my understanding, the key should be the same for either radio, all the time. The nonce however needs to change with every packet sent/received. My question is: how will the two radios agree on a continuously changing nonce for any given transmission/reception? Example: when Radio A picks its nonce to encrypt its message, how should Radio B know which nonce to use to decrypt the message?

The radios may not necessarily be synced in time so that can't be used. Is there any way to do this without using time as the nonce? Does the nonce need to be agreed upon ahead of time in an un-encrypted exchange?

Any guidance on this is appreciated.

The standard approach is to have the sender pick his nonce (either randomly, or as a counter), and send it with the packet.  The decryptor then knows what nonce to use to decrypt, because it's right there.  Because nonces aren't assumed to be secret, this works.


Distributed Asymmetric Key Decryption with threshold Threshold decryption of public-key encryption schemes allows the decryption key to be distributed among trustees. Then, to decrypt the ciphertext it requires at least threshold t trustees to run the decryption protocol in order to get the plain text.

Now, most of the literature is either based on generic multiparty computation (which I am not keen on for some reason) or based on distributed RSA decryption and sharing RSA functions.

Are there any other ways of achieving distributed asymmetric key threshold decryption?
Will elliptic curves be a good choice for distributing the decryption?

I assume you say on the threshold encryption scheme, in which a dealer generates $(PK,SK_1,\dots,SK_n)$ and distributes the secret keys to users indexed by $1,\dots,n$, and if a combiner obtains $t$ partially-decrypted ciphertexts, it can retrieve a plaintext.

Dodis and Katz showed a generic construction of CCA-secure threshold encryption scheme from a secret sharing scheme and a CCA-secure labeled PKE scheme.
See the paper, Dodis and Katz: Chosen-Ciphertext Security of Multiple Encryption (TCC 2005).
DDH-based constructions (in ROM) are proposed by Gennaro and Shoup: Securing threshold cryptosystems against chosen ciphertext attack (EUROCRYPT 1998, JoC 2002).
You can also find a pairing-based construction in Boneh, Boyen and Halevi: Chosen Ciphertext Secure Public Key Threshold Encryption Without Random Oracles (CT-RSA 2006).


Problem reproducing AES results First of all, I just implemented AES because I wanted to understand how it works and as a challenge to see if I could do it and I won't use to encrypt anything important, ever.

The (German) Wikipedia article of AES linked to a flash animation which demonstrated precisely how AES-128 in ECB mode worked. I implemented AES exactly as shown in that animation and I am able to reproduce the same encrypted byte array they get in the result.

In that example the hex string: 328831e0435a3137f6309807a88da234 encrypted with the key 2b28ab097eaef7cf15d2154f16a6883c results in the encrypted hexadecimal string 3902dc1925dc116a8409850b1dfb9732 and I get the same result.

Encrypting given test vectors however does not work with my algorithm and neither does encrypting the examples given in the animation with an AES encryption tool (which encrypted the test vectors correctly) work. Is there anything wrong with that flash animation or am I missing something obvious?

I think the flash implementation is wrong: (using Linux, OS X terminal etc.)
not true, see below

echo 328831e0435a3137f6309807a88da234 | xxd -r -p > plain.dat
openssl enc -e -aes-128-ecb -iv 00 -K 2b28ab097eaef7cf15d2154f16a6883c -in plain.dat -out plain.dat.out -nopad

yields

hd plain.dat.out

00000000  57 16 aa fa 2c c6 8b 9b  8b 9b e5 0d 30 e3 f2 06  |W...,.......0...|

And I do trust openssl to give the right results.

Are you sure you use raw bytes (not ASCII representations of hex or something like that?). This is one block, using a 16 byte key. I tried the first of the AES-128 test vectors using openssl in the same way, and that gave the right result.

Post your code if you are in doubt.

Added:

I remembered that the order in the blockstate and keystate are different than one would think! Specifically, the block used in the flash implementation is really

32 43 f6 a8 88 5a 30 8d  31 31 98 a2 e0 37 07 34

Because a block is put into the state by column, not by row!
The same holds for the key, which is really

2b 7e 15 16 28 ae d2 a6 ab f7 15 88 09 cf 4f 3c

(which is, probably not by accident, the same as the one used in the test vectors you linked to)

So the flash implementation is right, but you need to realise that you have to put the blocks from the test vectors in by column, not by row. I made the same mistake in my initial answer as well. So if the state is a matrix a[i][j] and the block is b[i], we see that a[i][j] = b[4*j+i], and similarly for the key. See page 9 of the AES document, e.g.


DES S-Box properties Two of the properties that lead to the design of DES S-Boxes are:

For any non-zero 6-bit difference between inputs, no more than 8 of the 32 pairs of
inputs exhibiting that difference may result in the same output difference.
This is a criterion similar to the previous one, but for the case of three S-boxes.

The book i am reading (Understanding Cryptography from Christof Paar and Jan Pelzl) translates the second one to: A collision (zero output difference) at the 32-bit output of the eight S-boxes is only possible for three adjacent S-boxes.

Can anyone explain me the first property? I have searched for that property on google but the statement is always the same and i can't understand it. At first i thought that the non-zero 6-bi difference was between two different inputs to an s-box. But then it talks about 8 pairs of the 32 pairs (the only 32-bit input is the one before the expansion) that exhibit the 6-bit difference. Am i the only one finding this explanation confuse as hell?

As for the second criterion and assuming the book explanation i assume that you can't have something like (O = output of s box):

O(s1) = O(s2) = O(s3) = O(s4) = O(s5) = O(s6) = O(s7) = O(s8)

but you can have:

O(s1) = O(s2) = O(s3) && O(s4) = O(s5) = O(s6) or some combination of three adjacent s-boxes.

I hope you understand my questions and you can help because i would like to clarify this.

First property says-
If you consider a 6-bit Inpput Difference(Difference means XOR in case of DES).i.e  6-bit binary number which is the xor of two inputs(obviously both 6 bits).When you enter both of these inputs to Sbox and get two outputs each of 4 bits and xor the outputs what you get is called Output Difference.

Total 64 inputs are possible hence 32 pairs having a same difference.

So this property says for any  non-zero 6-bit input difference there can be maximum 8 possible different 4 bit output difference and not more than that.

Hope i am clear


Is there any concrete reason to call BLAKE more secure than BLAKE2? I read a blog article which discussed SHA-3. I noticed it mention that security was often compromised in the name of speed (not always a bad thing, of course). It gave some examples:

  What I'm saying is that although they care deeply about security, they are also looking for compromises to gain speed. This can be seen with the push for 0-RTT in TLS, but I believe we're seeing it here as well with a push for either KangarooTwelve (K12) or BLAKE2 instead of SHA-3/SHAKE and BLAKE (which are more secure versions of K12 and BLAKE2).

This is explicitly claiming that BLAKE is more secure than BLAKE2. I wasn't able to find anyone else claiming that, so I went to read the actual paper to see what changes it made to the original:

Fewer constants used. The original argument was that the constants improve diffusion.
Fewer rounds used (from 14 to 10 for 256-bit digests and from 16 to 12 for 512-bit digests).
Fancy features such as hash trees and personalization values added.
Some generic security trade-offs made (in regards to salt and IV processing).
Extensive speed and memory optimizations for implementations in software.

The first two points do not increase security at all, and arguably reduce security. Reducing the rounds was done because the best preimage attack was only found against a 2.5 round variant. This improves speed considerably at the expense of security (at least on a theoretical level). The reduced number of round constants reduce diffusion in the name of a lower ROM footprint.

It's possible that the author of the blog post mentioned simply read about it using fewer rounds and claimed the security was meaningfully reduced as a result, or it could be that it may have practical implications. My question is whether or not there is any concrete reason to consider BLAKE2 to be less secure than BLAKE and to use the latter instead for that reason (when speed is not an issue).

I guess that reducing the rounds is indeed the main reason to call it less secure. Generally attacks are over a specific number of rounds. If better attacks are found then the reduction of rounds could mean that Blake2 gets broken while Blake is not.

How secure something is is up for discussion for the simple reason that we cannot predict the future. I guess that the authors were confident enough in the overall structure of Blake to make the changes.

Neither algorithm has been broken so up to now they are right and Blake2 is as secure as Blake. The full rounds version of neither is affected by the attacks.

However as an attack is more likely to affect Blake2 you can still argue that Blake2 is less secure if an uncertain future is taken into account. With so few rounds broken you can argue that the difference is minimal (AES has many more broken rounds) but it's there.


Using secp256k1 keys for encryption We are making a system where users can share files with other people but nobody should be able to figure out that all these different files belongs to same user on blockchain.

these are the steps we have followed.

bip39 specification for generating master public keys and private keys and their 2**32 -1 child keys.
If a user wants to store this file, A new child key will be generated with a new AES key will be generated. The file will be encrypted with this AES key (GCM) mode,appending nonce and tag with ciphertext.
AES will be encrypted with this child private key.
Now float a contract, with the location of this encrypted data, encrypted AES key and child public key and saved on the address generated from the public key based on some mechanism.
If a user wants to share this file with other user, just generate a key based on the other user public key and users private key, and encrypt the AES with this common key so the other user can decrypt and read it.

My question is, How to encrypt AES key with secp256k1 keys since I couldnt find any implementation of this in either python or golang.
The other question is, Is it safe to encrypt AES keys with child secp256k1 keys.

I figured out an Answer, https://pypi.org/project/eciespy/, this library uses private/public key generated from Sep256k1 curve for encryption and decryption.

from ecies.utils import generate_eth_key
from ecies import encrypt, decrypt
k = generate_eth_key()
prvhex = k.to_hex()
pubhex = k.public_key.to_hex()
data = b'this is a test'
decrypt(prvhex, encrypt(pubhex, data))
b'this is a test'


MD5 hash: retrieve an element of a source string Suppose you have a string, precisely an MD5 hash string, which basically it is computed in the following way:

"element1:element2:element3"

So, in order to get the hash (MD5 hash) you can issue the command:

echo -en "element1:element2:element3" | md5sum

MD5_hash_output

Given that MD5 is a one-way function (it is now considered broken, no more secure...etc), think that you want to retrieve element3 and you know:

element1
element2
MD5_hash_output

Is my reasoning correct if I say:

you can get element3 if there's a rainbow table which includes MD5_hash_output
you can get element3 if it is guessable (easy to guess: a default device password ...for instance)

It may sound a trivial question...the answer is, of course, that MD5 is a one-way cryptographic function..but I just wanted to have some other different opinions

TL;DR; The success depends on the size of the element3.

The MD5 pre-image resistance theoretically is broken bu not practically. Instead of the generic preimage attack with $\mathcal{O}(2^{128})$ complexity, there is an attack by;

Sasaki and Aoki: Finding Preimages in Full MD5 Faster Than Exhaustive Search, EUROCRYPT 2009.

This attack requires $2^{123.4}$ complexity. MD5, however, is not practically broken. You cannot reach the 123-bit search space in a meaningful time. Consider the collective power of BitCoin miners; in 2020/1/17 they reached 126.1314 Exahashes per second, that makes

$2^{67}$ SHA256 double hashes in a second, and
$2^{92}$ SHA256 double hashes in a year. So you need $2^{21}$ years with that power.

Apart from the above; we don't expect special data would make the pre-image attacks easier.

The below is totally depending on the size of the element3

  you can get element3 if there's a rainbow table which includes MD5_hash_output

Actually, using only once, a rainbow table is not necessary. You can build one with a special reduction functions; like $$R(md5(previous)) := \texttt{element1:element2:} \mathbin\| md5(previous)|_{target\;length}$$

The size of the table depends on your target length. It may not be possible to build one after $2^{63}$ (not an exact number) due to the memory requirements to process.

Instead of building the Rainbow Table, if it is only used once, just search the all possible space. As seen above, there is a limit on the search space that one can achieve in a meaningful time. If you somehow agree with all the Bitcoin Miners (though some of the use of special hardware that cannot be changed), you can search the 8-byte space less than a second. If not, maybe one can use the Summit Supercomputer to reach $\approx 2^{63}$ in a day and $\approx 2^{73}$ in a year (those are calculated on SHA-1 capabilities). Therefore 12-byte is far far away.

  you can get element3 if it is guessable (easy to guess: a default device password ...for instance)

If you have the collection like the commons password, knowledge about the target, etc. you can easily check them with some script.


When encrypting twice with two separate keys, can a single key decrypt both steps? Is it possible that if a plaintext is encrypted first with a key, $n_1$, and then this ciphertext is again encrypted using the same algorithm but a different key, $n_2$ that the resulting ciphertext could be converted back to the original plaintext with a single key?

For example:
keys $n_1$, $n_2$, and $n_3$

$p_1$ = "plaintext"

$p_2 = C(n_1, p_1)$

$p_3 = C(n_2, p_2)$

Is  this possible:  $Dec(n_3, p_3) = p_1$?   (where $C$ is an encryption algorithm taking the key and plaintext)

An example I can think of is the Caesar Cipher (the key can be seen as the shift). Where first a shift of 4 is used, and then a shift of 6. A shift of 16 would reveal the plaintext in a single operation (a single key).

Obviously this is a trivial example. Are there any cases where this could happen with a stronger algorithm, such as AES?

It is possible with the old Pohlig-Hellman cipher.

Here's how it works:

The global parameter is a prime $p$
A secret key is a value $k$ which is relatively prime to $p-1$
To encrypt a message $M$, you compute $C = M^k \bmod p$, and that's you
To decrypt a ciphertext $C$, you compute $k^{-1} \bmod p-1$, and then compute $M = C^{k^{-1}} \bmod p-1$

With this system, if you encrypt with $k_1$, and then with $k_2$, the resulting ciphertext is $C = (M^{k_1} \bmod p)^{k_2} \bmod p = M^{k_1k_2} \bmod p$; hence, this is identical to encrypting with the key $k_1k_2 \bmod p-1$, and so can be decrypted by that key.


Logarithm in Private Set Intersection Is the logarithm in the private set intersection protocol mentioned in Section 3.4, Step 5 of http://www.ece.umd.edu/~danadach/MyPapers/set-int.pdf, a base 10 or 2? How do we find this out?

It is of base $2$ since it is the number of bits needed to represent in binary form $n$.


Degree of a big S-box Assume we have a big S-box (i.e. $15*15$). We have truth table of it. (so $2^{15}$ output).
How can we find its degree without using Algebraic Normal Form of its Boolean functions.
Or with ANF, can you help me to write the algorithm of implementing.

Take the field with $2^{15}$ elements, identify its elements with 15-bit 0/1-strings (in any linear way -- the polynomials will be dependent on the choice, but not the resulting maximal Hamming weight) and find the polynomial $p(X)$ of degree $2^{15}-1$ with $p(x) = S[x]$ for all $2^{15}$ values $x$ via Lagrange or Newton interpolation. If $p(X) = \sum_{i=0}^{2^{15}-1} p_i X^i$ then the degree you are looking for is the maximum of all Hamming weights (= number of zeros in binary representation) of exponents $i$ where $p_i\ne 0$.

So if for example $p(X) = p_7 X^7 + p_{257} X^{257}$ with $p_7\ne 0$, $p_{257}\ne 0$ then the degree is $3$, as maximum of Hamming weight(7) = Hamming weight($2^2+2^1+2^0$) = 3 and Hamming weight(257) = Hamming weight($2^8+2^0$) = 2.


Why should keys be hidden from an eavesdropper for a pseudorandom function? What advantage would knowing the key used for a given pseudorandom function give over having access to an oracle for that function $F_k(\cdot)$ and the actual key $k$ which will be used?

Thanks very much in advance

With $k$ the adversary can compute $F_k(x)$ for some $x$ using the evaluation algorithm, and compare it to the answer of its oracle on $x$.


Choosing between additive or multiplicative group for Diffie-Hellman I am trying to construct a theoretical Diffie-Hellman key exchange protocol. However, i cannot understand the difference between choosing an additive group or a multiplicative group. I believe an additive would make it much more simple, but would a multiplicative group make it more difficult to break? What would be the difference between the use of those 2 kinds of number groups?

From an abstract algebraic point of view the two are one and the same, a group.

However, depending on how that group is defined additional structure may make additional operations possible or easy that are detrimental to your security.

For example:
In a finite field of prime order calculating logarithms is hard but division is easy.

More mathematically the two problems are

calculating $x$ given $g$ and $g^x$
calculating $x'$ given $g$ and $x' \cdot g$

and they have totally different complexities.

Both addition and multiplication in this case define a group but integer multiplication is not hard to invert.

And, the usual disclaimer, please don't design your own crypto unless for exercises. ;)


Is there an avalanche effect using block cipher modes of operation? I am studying cryptography and various block cipher modes of operation.

Suppose I changed one bit in the last block of the message. Wouldn't
that imply no change in all encrypted blocks except for the last one?

At least based on the description of how various modes work (CBC, OFB, etc), I don't see why that wouldn't be the case.

However, if that is true, then the encryption mode lacks the avalanche effect property, doesn't it? A single bit change in any place should completely change the encrypted text.

Could someone correct my observation, or explain why lack of avalanche effect is not dangerous?

We don't mind the lack of avalanche because of the IV.

The problem that not having full avalanche would have is that if we encrypt two related messages, for example, two messages that differ only in the last block, is that the ciphertexts would be related, for example, they differ only in the last block.  Obviously, that'd not be good - at the very least, we'd be leaking that the plaintexts are related.

However, with the modes in question, this isn't a concern.  If we do encrypt two related messages, we select a different IV for each message.  It turns out that choosing a different IV makes the ciphertexts look completely different, even if the plaintexts are related (or even identical).

One cavaet to the above: with CBC mode, if the IV's were related (for example, had a small bit difference), and the first plaintext block happen to have the same bit difference, then this is leaked.  That's why we specify that the CBC mode IV's are "random" (that is, unpredictable); other modes don't have this restriction.


Asymmetric or Symmetric encryption I'm currently looking into OpenSSL and its API and I'm not really familiar with cryptography.
So I was looking at the example on asymmetric encryption of an envelope. And it says the message is symmetrically encrypted with a session key that is then encrypted with the actual asymmetric key.
Then my question would be how are the session keys generated and how could I search to find this concept in some other programming language.

The session key can be generated with a CSPRNG by Alice. Alice and Bob will already have static key pairs that don't change. Alice and Bob will create ephemeral key pairs, and these are newly generated every session.

Alice then signs her ephemeral public key with her static private key and sends this to Bob - this public key doesnt have to be encrypted in any way as it is a public key. Bob receives this, and verifies the signature using Alice's static public key. Bob goes through the same protocol so Alice can have his ephemeral public key.

Now there are two ways that this can go - a KEX (key exchange) or a KEM (key encapsulation mechanism).

For a KEX, both Alice and Bob combine their own ephemeral private key with the others public key, using DH(E) or ECCDH(E). This leaves them both with the same shared secret, which can be passed through HKDF to create a correctly formatted symmetric key of the desired length.

For a KEM, Alice would create a symmetric key of desired length, sign it with her static private key, and then encrypts it with Bob's ephemeral public key, and sends it to Bob, who can decrypt and verify they key. RSA would have to be used for this.

For a programming languages there's usually a module for pseudorandom numbers (PRNG) and for cryptographically secure pseudorandom number generators (CSPRNG). In Python, the random module is a PRNG, and the secrets module or os.urandom is a CSPRNG. For cryptography, there is a PyCryptodome or cryptography among some others.


Hill Cipher - Unknown plaintext attack, known key I was wondering if I have the key and the encrypted Hill Cipher message(s). I can definitely figure out the charset involved. But the order is missing. Assuming that I use 37 modulo or higher. How would I go about cracking it?

You don't. You just decrypt it. I can't think of a language that uses more than 36 letters apart from the Chinese family but then again I'm not a linguist.

Decrypt to a reasonable $n$ and then use the character frequencies to infer the language (and hence the modulo). Some trial and error may be required untill you get it right but for values of $n$ less than $2^{32}$ it shouldn't give you any practical problems on a desktop computer.


Elgamal with secret key equal to zero possible? From various sources (e.g. this paper, page 3), the key generation algorithm of Elgamal samples the secret key $x$ from $\mathbb{Z}_q$, which is identifiable to $\{0, 1, 2, \dots, q-1\}$.

My question is: what happens when the sampled $x$ is, say, zero? Indeed, in this case, the public ley $h$ is equal to 1, and encrypting plaintext $m$ with randomness $r$ yields $(g^r, m)$. This seems to me like a serious issue. The same happens with $x = 1$. In this case $h = g$, it is easy to notice that $h$ is equal to $g$ and deduce that the secret key is $1$.

Of course,this "methodology" does not extend to any value of $x$ (testing whether $g^x$ is equal to the public key), since this is pretty much a brute force attack, by assumption computationally infeasible. I also understand why the scheme can be proven secure, though: because $q$ is so large that the case $x = 0$ or $x = 1$ happens with a negligible probability. Yet, in practice, it can happen... Do implementations take that into account?

It's worse than that: if $x = 1283767$, then the ciphertext will be $(g^r, m \cdot g^{r \cdot 1283767})$, which an adversary can immediately detect by checking whether $h = g^{1283767}$ and subsequently exploit to decrypt messages!  The same trick works for $x = -1$, $x = 42$, and $x = 123456789$.

We pick $q$ and $g$ so that the space of values for $x$ is so large that if we choose $x$ uniformly at random, the adversary's probability of success at guessing it is negligible, below $2^{-128}$—so small that you should be more worried about cosmic rays flipping bits in your RAM than you are about this event.

There are much better attacks recovering $x$ from $h = g^x$, requiring you to choose $q$ to have thousands of bits.  You should be much more worried about how you're using Elgamal encryption and how you shoehorn arbitrary messages in your application into integers mod $q$, and even more worried about articulating higher-level application security goals.


Limit the length of AES encoded output to certain value First let me be clear upfront that am not Crypto expert. I'm having a problem where I will have to use NFC card. Now given the limitation of NFC cards memory sizes, I will need to constraint my system to generate encoded data up to X amount of character.

Is there a way to limit character of AES encrypted data to not exceed certain limit? It would be easy with hashes but the data have to be reversible.

AES operates on 128 bits of data. We can use modes of operation to turn AES (and any block cipher for that matter) into something that can handle longer (or shorter) data. If you want the ciphertext to be limited to X bits (above you said characters, I'm switching this to bits to make things easy), X must be at least as long as the plaintext data (compression may change that, but you must be very careful).

Using a stream-like mode (which would turn AES into a stream cipher) such as CTR mode, the plaintext text length and ciphertext length will be the same. Using a mode like CBC, the ciphertext will be slightly larger (at most 255 bits longer).

The two modes I listed above only provide confidentiality guarantees. This can be devastating to security, however. Especially if you are using a stream-like mode. To add integrity, you can use something like HMAC or an authenticated encryption scheme. If at all possible, you should do this as it would prevent entire classes of attacks. Authenticated encryption will make the output of the cipher longer than the plaintext, because it adds an authentication tag to the data.


Long term storage of encrypted data Say that I have 16-32 GB of data, and I want to devise a system for storing this data in an encrypted form. This system needs to meet two core objectives:

The data needs to remain as pristine as possible for a very long time, which in this case means 10-50 years.
No one but me should be capable of decrypting the data.

Here's the system that I've come up with so far:

Two copies of the data are stored, each on its own flash drive.
These flash drives are encrypted using VeraCrypt.
Every year, on a specific date, I mount both devices, and copy the contents of one onto the other.

Are there any obvious holes in this system? Will copying the data as described above keep the data "fresh"?

Answering question 1:
I see the following flaws in your model:

flaw 1: Any currently known data storage device is prone to accrue errors and data degradation no matter what you do. They also have an expected lifetime, with a different failure rate. USB devices have less durability (on average) than hard-drives, for instance. This means that you may lose both drives at the same time, and probability for this to happen increases dramatically over time, no matter how good you conserve the drives.

Solution:
replace unreliable USB technology with hard drives or tape, which are more appropriate for long term storage (although they also are not invulnerable).

flaw 2: Having only two devices means that you will have a RAID-1 equivalent. With that approach, if you lose a drive, you need to replace it and resilver from the surviving one. That puts a lot of stress on the surviving drive, and in case of failure during the process, you lose data.

Solution: You need to add more drives to reduce the probability to have a single source of data.

flaw 3: Copying the data on a yearly basis means that any silently corrupted data in drive A will be copied into drive B, so you are unwitingly damaging your data.

Solution: Use a hashing tool like ‘hashdeep’ to bulk create checksums of your files in both drives, and use a comparisson script to check and compare both drives individually on a regular basis. Your full-checksum-test will evaluate any damaged data in a drive and you can copy and replace from the other drive.

flaw 4: If you use a single large file as container with VeraCrypt, the above flaw 3 is harder to resolve. A failure in a portion of your large container file means you will need to fully resilver the entire dataset.

Solution: You may prefer to use LUKS encryption, or file based encryption like gpg for your full dataset, so that the 'hashdeep' process is executed over individual data files and isolate errors won't affect the full encrypted container. This way you can individually isolate damages and replace files from any of the surviving disks after your regular (monthly or yearly) full-checksum.
As a side note, for that long storage time, a separate set of replicas in RAID1 in a remote location is convenient. Also mixing drive technologies so that you don't hit a controller bug that will affect all your drives.
Answering question 2:
Nobody can for sure ensure you 100% that any current encryption algorithm or its implementations is free of bugs, flaws or vulnerabilities. Considering that long time, your best option is always to mitigate the physical access to the drives, on top of the encryption applied, keeping them stored safely in locations where you and only you will be able to access them during this time.
Obviously your threat model must be studied further depending on whether you are storing only personal love letters to be protected from ex-girlfriends or whether you are storing valuable trade secrets that a Court may seize.
Good luck.


Small exponents and the RSA problem I need some help with the following statement from the book A Graduate Course in Applied Cryptography* - Dan Boneh and Victor Shoup, in 8.10.1    The key derivation problem, page 320 of v0.5:

  Later, we will see examples of number-theoretic transformations that are widely used in
  public-key cryptography. Looking ahead a bit, we will see that for a large, composite modulus
  $N$, if $x$ is chosen at random modulo $N$, and an adversary is given $y := x^3 \bmod N$, it is hard to compute $x$.

To be specific, my doubt is related to how do we really prove that RSA problem can keep hard, despite small and known exponents $x^3 \bmod N$, for an adversary who doesn't know $x$. The authors said that "we will see examples" in the book. But I couldn't find them. Can you please give me some direction for such proof?

Can you please give me some direction for such proof?

You're looking for a proof that the RSA problem is hard?  No such proof is known (even in the specific case of $e=3$).  Furthermore, there is no known reduction to a 'more fundamental' problem, such as factorization or discrete log.

The closest we can get is a proof that if you can find the 'decryption exponent', that is, the value $d$ such that $y^d \equiv x \pmod N$, you can factor $N$ (and using the value $d$ is how the holder of the RSA private key recovers $x$ in practice).  However, this does not show that there isn't another way (that's easier than factoring) to recover $x$.

The only 'proof' we have that the RSA problem is hard is 'lots of smart people have looked for a way to solve it, and they haven't found one'


Is there a cipher that uses part of the already-computed ciphertext in the encryption scheme? Are there any famous ciphers that, to determine the encrypted letter at position n in the ciphertext, it uses the encrypted letter at position n-1 in the ciphertext?

I tried google but I couldn't figure out how to phrase my search terms correctly to find something like this.

The concept you mentioned is used in self synchronising stream ciphers. For example, CFB mode of a block cipher uses
$$C_0=IV$$
$$C_n=E_K(C_{n-1})\oplus P_n, \quad n \geq 1$$
with $C_n,P_n$ denoting the $n^{th}$ plaintext and ciphertext blocks.
So if you substitute "block" for "symbol", this is the same as what you want. CBC mode also gives a self synchronising stream cipher.

Moustique is a self synchronising stream cipher designed by J Daemen.


TLS encryption with a self-signed PKI and Python’s asyncio module I want to enable TLS encryption with a custom / self-signed PKI for
a self-contained distributed system built with Python 3’s asyncio.

I’ve read Python’s ssl docs as
well as several tutorials:

http://www.area536.com/projects/be-your-own-certificate-authority-with-openssl/
http://datacenteroverlords.com/2012/03/01/creating-your-own-ssl-certificate-authority/
http://carlo-hamalainen.net/blog/2013/1/24/python-ssl-socket-echo-test-with-self-signed-certificate
https://blog.cloudflare.com/how-to-build-your-own-public-key-infrastructure/
http://blog.gosquadron.com/use-tls

From all this, I extracted the following steps in order to create a minimal
example for a simple client and server with a self-signed PKI.

It seems to work as expected, but I’m unsure if I missed anything or create
non-obvious bugs which could reduce or nullify the security of the system.

Here is what I did so far:

I'll create one root CA which signs a CSR for each machine.  Each machine will
have its own certificate and key.

Considerations for the root CA:

The key length should be 2048 bits, or better, 4096 bits.
A strong passphrase should be used.
The key should not leave the machine (except if you store it on an SD card
and hide it somewhere save).  Level of paranoia should depend on the security
needs.
The certificate should not use the same FQDN as any production system.

Generate the key and a self-signed certificate:

$ openssl genrsa -aes256 -out ca.key 4096
$ openssl req -new -x509 -nodes -key ca.key -out ca.pem -days 1000

Create a key and a certificate signing request (CSR) on a machine:

$ openssl genrsa -out server.key 4096
$ openssl genrsa -out client.key 4096
$ openssl req -new -key server.key -out server.csr
$ openssl req -new -key client.key -out client.csr

Now you can sign the device key with your CA cert:

$ openssl x509 -CA ca.pem -CAkey ca.key -CAcreateserial -req -in server.csr -out server.pem -days 365
$ openssl x509 -CA ca.pem -CAkey ca.key -CAcreateserial -req -in client.csr -out client.pem -days 365

Minimal Python example.  We need different SSLContexts for the client and
server, because they do some things differently.  Both, client and server, will
use TLS 1.2 with ECDH-AESGCM.  They will verify each other’s certificates
against the root CA cert.  The client also checks the server’s host name.  ECDH
keys are only used once per SSL session and compression is disabled:

import asyncio
import ssl

@asyncio.coroutine
def handle_client(reader, writer):
    data = yield from reader.read(100)
    print(data)
    writer.write(b'cya')
    yield from writer.drain()
    writer.close()

@asyncio.coroutine
def client(addr, ssl_ctx):
    reader, writer = yield from asyncio.open_connection(*addr, ssl=ssl_ctx)
    writer.write(b'ohai')
    data = yield from reader.read(100)
    print(data)
    writer.close()

addr = ('127.0.0.1', 5555)
loop = asyncio.get_event_loop()

# Setup server
server_ctx = ssl.SSLContext(ssl.PROTOCOL_TLSv1_2)
server_ctx.verify_mode = ssl.CERT_REQUIRED
server_ctx.options |= ssl.OP_SINGLE_ECDH_USE
server_ctx.options |= ssl.OP_NO_COMPRESSION
server_ctx.load_cert_chain(certfile='server.pem', keyfile='server.key')
server_ctx.load_verify_locations(cafile='ca.pem')
server_ctx.set_ciphers('ECDH+AESGCM')

coro = asyncio.start_server(handle_client, *addr, ssl=server_ctx)
server = loop.run_until_complete(coro)

# Run client
client_ctx = ssl.SSLContext(ssl.PROTOCOL_TLSv1_2)
client_ctx.verify_mode = ssl.CERT_REQUIRED
client_ctx.check_hostname = True
client_ctx.load_cert_chain(certfile='client.pem', keyfile='client.key')
client_ctx.load_verify_locations(cafile='ca.pem')
client_ctx.set_ciphers('ECDH+AESGCM')

loop.run_until_complete(client(addr, client_ctx))

# Shutdown
server.close()
loop.run_until_complete(server.wait_closed())
loop.close()

The script will output

b'ohai'
b'cya'

as expected and TLS seems to work.  Are there any problems with it or things
that could be done better?

Thanks for your feedback.

Since I stumbled on this checking something else, a few minor points

A CA doesn't sign a CSR; it signs (issues) a cert that has some important data taken from the CSR but much data different.
The Subject names of the CA cert and all server and client certs it issues should be unique, and preferably mnemonic. The CA and client names don't need to be FQDNs, or domainnames at all, although if they are FQDNs that helps make them unique, and usually mnemonic. For a server, either the CommonName part of the Subject or the SubjectAlternativeName extension if used should -- and for many but not all clients must -- match the 'hostname' used by the client(s) to connect to the server. Normally this is the FQDN, but in test and intranet settings it might not; your example shows connecting to the loopback or 'localhost' address 127.0.0.1.
ECDH-AESGCM is not a ciphersuite or even a keyexchange in SSL/TLS; ECDH+AESGM is an OpenSSL shorthand for 8 different cipher suites -- only 2 of which work with an RSA key+cert, namely ECDHE-RSA-AES256-GCM-SHA384 and ECDHE-RSA-AES128-GCM-SHA256.
You don't visibly specify the temporary (ephemeral) ecdh parameters (curve) so you are presumably getting a default from Python; OpenSSL itself doesn't have a default, although 1.0.2 up has a nondefault option to automatically use the client preference.
Since you've chosen everything else pretty strong, you should make sure the ECDHE curve isn't unacceptably weak. I would hope it can be found in the Python source; if not, monitor an actual connection with Wireshark or similar to check.


How important is hardware based crypto in Quantum-safe TLS in mobile devices? Microsoft Research  published an approach to Quantum-safe TLS here, namely RLWE-ECDSA-AES128-GCM-SHA256.

One highlight is that when it's used with ECC, there is only a slight performance hit.

Assuming this becomes a popular way to have quantum-safe TLS, how important is it that manufacturers optimize for this?... in other words, is a brand new CPU instruction needed, or will the existing cryptographic instructions be sufficient?

As a layman, I'm trying to get an idea how long it would take to get quantum safe TLS on a mobile device, where power and other constraints apply.

My assumption is if websites aggressively implement RLWE-ECDSA-AES128-GCM-SHA256, battery life and performance will suffer on most phones, until the hardware market catches up.

Ring LWE schemes are relatively simple on a computation level -- the large majority of time is spent doing vector multiplication (another significant portion is sampling the error distribution). This is ideal for parallelization. So typically, RLWE implemented using the AVX2 instruction sets are significantly faster (for example, see a 3x speed improvement for one popular RLWE scheme: New Hope). I'm not sure on the ubiquity of AVX2 instructions on mobile devices, perhaps someone else can chime in.

That said, RLWE just isn't very computationally expensive in general. The paper above mentions that in terms of performance, the AVX2 implementation is in "the same ballpark" as state of the art ECDH implementations that use Curve25519 (which is one of the fastest ECC curves). I couldn't immediately find benchmarks comparing the two, and I don't know how to quantify "the same ballpark", but I've never heard anyone complain that RLWE is too costly performance-wise. So I don't think that the mobile CPU is the bottleneck.

Concerning RLWE, people do complain about the bandwidth of the key exchange. Even the best RLWE schemes still require much more data transfer (see the nice chart in the Frodo paper), which can significantly increase latency for poor connections. This appears to be corroborated by the results of Google's post-quantum TLS experiment, CECPQ1.

So I don't think battery life and/or performance will suffer much at all. Users with poor internet connections will certainly suffer a bit, but let's be honest -- they already suffer. The average page weight is in the megabytes, even for mobile. A few extra kilobytes in the handshake is a pittance compared to the amount of javascript and other assets most websites require. I realize this argument may not be valid for other protocols, but it does show that the average user probably doesn't have to worry about websites aggressively implementing hybrid post-quantum cipher suites.


How can I extract randomness from a JPEG file? In a previous question I asked if (and why) BlueRand can or cannot be considered as a TRNG.

Established that it's not a TRNG (due to the reasons explained by some users in the previous question), is it possible to create a TRNG that uses JPEG images as entropy source? How can I extract randomness from a JPEG image?

All original JPEGs are sources of true entropy due to:

Noise on the image sensor.  However small it might be, it is unavoidable due to the very nature of the stochastic photoelectric effect on the silicon detectors, be they CCD or CMOS. There are also other noise sources such as reset noise, thermal noise etc. This means that what ever you take a photo of, it will contain truly random noise across the image sensor.
Compression.  Once the image is captured by the sensor, the JPEG algorithm kicks in.  Various processes occur that have the effect of reducing the intensity of high frequency noise both level and colour wise.  So the randomness /entropy of the image drops significantly, perhaps to only 10% of that originally captured.  This remaining noise is then losslessly compressed into a final jpg file.  You could look up the JPEG algorithm.  The consequence of the lossless compression is that tiny changes to the input image result in huge changes to the compressed jpg file.  This is akin to changing a word in a zip file which then results in a totally different zip.  It’s also akin to the avalanche effect.

Since every original JPEG file ever taken throughout the known universe is unique, this forms a perfect source of entropy.

Since the format of a jpg file is highly structured, it cannot be used directly as a source of uniformly distributed random numbers.  It has huge correlations between bytes as you would expect of a standardised file format.  This is why you have to treat the file as one sequence of unique bytes, some of which are hugely correlated whilst others are totally fixed such as the golden byte.  Never ever open up the file and work on the image.  You have to extract the entropy out of the jpg file itself, after measuring it with something like a minimum entropy calculation.  I have a JPEG based true random number generator called a Photonic Instrument which you can see.  Ignore the dumb ass  humour and focus on the science, especially the Kullback–Leibler divergence graph.  It produces JPEGs with a  min. entropy of approx. 100 kbits /frame, which is about 5 bits /byte, and can do 4 frames /s.

You will have a true random number generator if you extract less than 100 Kbits from each frame / file.  This is the golden rule of true random number generation.  A common way to extract entropy is by hashing.  It can be any kind of hash function, and not necessarily cryptographic at all.  In fact, cryptographic hash functions can lead to the Cryptographic Hash Function Extraction Fallacy, which means if you use one you risk producing random looking output from any kind of rubbish input like a simple counter.  I avoid them like the plague and am suspicious of any generator using them.  Since you know that JPEGs are a source of true entropy in this case you  are okay using one for this example, but you could do better.

You have to ignore the bleating of the theoreticians who say there are no extractors that work on all sources.  You just have to ensure that [entropy out] < [entropy in].  Otherwise there wouldn’t be a thriving commercial market selling true random number generators would there?  Hash it and there you go.  You can use any of them (like MD5) but they don’t go over 1024 bits.  You could write your own as I did which is a simple substitution permutation network with a block size of up to 512 kbits.  That can hash my 20 Kbyte frame in one go.  Alternatively, use SHA-1 several times over the jpg, making sure you add a counter to change the initial state, or use a kinda of block chaining hash mode.

This is all a lot of talk so try this…  Take 10 pictures with your phone of anything at all.  Hash each picture with SHA-1.  The resulting 200 bytes will be truly random.  Go from there and prove the naysayers wrong…