CBC-MAC key can be added to ciphertext? I use AES both CBC and CBC-MAC to encrypt some stuff. I generate one key for CBC and one different key for CBC-MAC.

Does the second key (for CBC-MAC) need to be secret?
How to join such key with the ciphertext? By contatenating it at the end?

From the sound of your questions, it almost appears that you have some confusion between the CBC-MAC key and the CBC-MAC tag.

The CBC-MAC algorithm takes the message (in this case, most likely the ciphertext) and a secret key; it outputs a tag (which can be public).  The security property of CBC-MAC is that someone who does not know the key cannot generate a valid message, tag pair, even if he sees a huge number of valid message, tag pairs (of course, he is not allowed to suggest a message, tag pair that he has been given).  Actually, it works even if he is allowed to specify the messages.

The idea is that if the receiver (Bob) gets a message and tag pair that validates, that means that the sender (Alice) must have generated it.  After all, only someone who knows the key is able to generate such a pair, and the only two are Alice and Bob (and Bob knows he'll never generate such a pair, so Alice must have sent it).

With that in mind, your questions:

  Does the second key (for CBC-MAC) need to be secret?

Absolutely; if the attacker is given that key, then all security bets are off.  He can easily generate a valid MAC tag for any message he picks.

  How to join such key with the ciphertext? By concatenating it at the end?

No, you don't send out the key with the ciphertext; it needs to be secret.  On the other hand, you can send the tag with the ciphertext; concatenating the tag at the end is one common approach.


Zero-knowledge proofs in blockchain I would like to know if I am understanding this correctly.
Zero-knowledge proofs need a prover, verifier and witness.

So if we have a blockchain where person A pays person B 100 dollars.
In blockchain, is person A the prover? It proves to the other nodes (the verifiers) that person A has 100 dollars. A witness applies a hash function to the verifier..

Am I understanding this wrong?

I think you are mixing concepts.

In an interactive proof system, you have two communicating entities: the prover and the verifier, where the prover tries to convince the verifier about the validity of some statment.

The witness you mention is not another entity. To understand that, we need to know what kind of problems make sense to be dealt with in a proof system, which are the problems in the so called Non-deterministic Polynomial Time class, or $NP$ for short. Imagine all problems (not only those in $NP$) as being described by a string $x$. A problem $x \in NP$ has the additional property that, it can actually be efficiently verified to belong in $NP$ when you are given a value $w$ related to this $x$. More interestingly, if you are not given this $w$, it is (conjectured) to be hard to decide whether or not problem $x \in NP$. This is why these $w$'s are typically called witnesses.

Now, getting back to proof systems, it makes sense that they deal with problems where the prover needs to prove something that is not trivial to obtain. This is where witnesses (and $NP$ problems) come in. So, in order for the proof system to be meaningful, we restrict to $NP$ problems where the verifier cannot do the computation unless she interacts with the prover, who knows a valid witness for $x$.

Summarizing, the prover needs to have a witness in order to convince the verifier of the validity of the ($NP$) statement being dealt with.

A proof system being zero-knowledge further requires that the verifier does not gain any knowledge beyond the validity of the statment. Specifically, that she does not gain any information about the witness being used by the prover.

Note that I have introduced interactive proof systems. But there are non-interactive proof systems too. Actually, these are the ones you most probably want to use in a blockchain. As the name implies, in an interactive proof system, the prover needs to be active during the proof process and several communication rounds take place. But in a blockchain, assuming this would be doable is probably very unrealistic: blockchains are of a highly decentralized nature and you cannot expect the prover to be active at all times (even more assuming that blockchains are expected to last "forever"). In a non-interactive proof system, the prover just "creates" the proof and sends it to the verifier, who can verify the proof without further interaction.

Finally, then, getting back to your payment example: "The prover needs to use a witness in order to demonstrate to the other nodes (the verifiers) that she owns 100 dollars". How is this witness used depends on the nature of the proof and would most certainly not be just a hash function (although using hash functions is one step of a common approach to convert interactive proofs into non-interactive ones which, as I said, would be needed in a blockchain).

Note: I have been extremely vague (and possibly incorrect if we are being strict) when introducing the related concepts, specially in the definition of the complexity class $NP$. If you are interested in precise definitions, I urge you to lookup  some more formal source. You can begin with Wikipedia and the links therein, or any textbook on computational complexity theory, or the original works on knowledge and interactive proof systems by Goldwasser, Micali and Rackoff.


Security of Shamir secret sharing with regards to the threshold Consider Shamir Secret Sharing Scheme (SSSS). This is completely unfounded, but my intuition tells me that the threshold k we set (AKA the number of shares required to construct the original secret) with regards to the total number of shares distributed (n)  has a profound relation with the security of the whole system.

There are two scenarios I'm imagining where the threshold that would affect the security.

  1) When k = n.

  2) When k is dramatically lower than n.

Is any of this true?

Absolutely no information about the secret is gained by having fewer than $k$ shares.  This is true regardless of what $k$ is, and for an adversary with unlimited computational power.  The secret is information theoretically hidden.

In at nutshell the reason for this is that, for every possible value of the secret, there exists a polynomial that interpolates it and the all the shares obtained.

Each share is a point on a degree $k-1$ polynomial $f$.  The secret is also a point on the polynomial, typically it is taken to be the point $(0,S)$ (i.e. $f(0)=S$, so the constant term of the polynomial is the secret $S$).

SSS uses the following fact: for every $k$ points, there exists exactly one polynomial of degree $k-1$ that goes through all these points. This can be shown using Legrange interpolation.

Let's say that you knew $k-1$ shares and were trying to figure out if $S'$ was the secret.  You think to your self, well if $S'$ is the secret, then I must have that $f(0)=S'$.  Then, I would have a total of $k$ points on $f$, namely $k-1$ from the shares I know of and I'm assuming you have the point $(0,S')$.  Such an $f$ always exists and could very well have been the polynomial generated by SSS, and so I cannot rule out $S'$ as the secret.

This is true for every value of $S'$, and so I gain no information about $S$.

Edit: a tangent about the case of $k=n$.  You can actually do something much simpler than SSS.  Randomly sample $n-1$ bit strings $s_1,\cdots,s_{n-1}$.  Then let $s_n=S\oplus s_1\oplus\cdots\oplus s_{n-1}$.  Note that the $s_i$ satisfy $S=s_1\oplus\cdots\oplus s_n$.  If any one share is unknown (WLOG, say $s_n$ is unknown), then $s_n$ is functionally a OTP that protects $S$.


Wikipedia pseudo code is unclear about how to pad SHA-512 In Wikipedia pseudo code of SHA-512 the padding section says pad 1 bit then 0 bits. It then goes on to say append length without 1 or 0 padding. What does that mean?

https://en.wikipedia.org/wiki/SHA-2#Pseudocode

  append length of message (without the '1' bit or padding), in bits, as 64-bit big-endian integer

The appending of message length in sha-2 as a 64 bit integer without 1 and 0 padding is a bit confusing. How is it different from SHA-1?

Richie is of course correct; the padding needs to be done to form a final block that can also contain the length. As the length encoding is itself static in size, there is no need to pad the length itself.

This is the same as SHA-1 except that the size of the various elements (block size, length encoding) differs.


Does a cryptographic oracle have to be a server? I've been told that oracles are always servers and that oracle attacks are always online, but I'm not convinced that's true. However, I have limited understanding of this topic since I'm still learning and the book I just read didn't discuss it at all. The definitions I've seen of the term don't specify whether oracle attacks are always online/involve servers either.

Is an oracle always a server?
Can padding oracle attacks happen offline (e.g. an encryption tool)?
Can partitioning oracle attacks happen offline (e.g. an encryption tool)?

Please explain things in layman's terms.

In Theory: No. How the Oracle is implemented or named is not important, only how it works.
In Practice: Everything that leaks information can be abstracted as an Oracle. So it is also possible to use the client as an oracle, or the systems processing the cryptosystems. The Server Client system is only the most common way how stuff works and communicates in the world wide web, but the important aspect is, that cryptography is used for a lot more that only "the internet".
A good example are operating systems. They are (for simplicity) offline systems, but you could also identify oracles and other mechanism in the cryptographic applications used for the OS. OS also use block ciphers, therefore it can be possible to make an offline padding oracle attack.
I hope I was able to give an adequate answer!


Prove that function G is not a pseudo-random generator I'm trying to do the following assignment:

  Let $G:\{0,1\}^n \rightarrow \{0,1\}^{n+1}$ and $G':\{0,1\}^n \rightarrow \{0,1\}^{n+2}$ be two pseudorandom generators. Prove
  that the function $G'':\{0,1\}^n \xrightarrow{}\{0,1\}^{2n+3}$ defined
  by $$G''(s_1, \dots, s_n) = (G(s_1,\dots,s_n),G'(G(s_1,\dots,s_n)))$$
  is not a pseudorandom generator.

I know that despite $G$ and $G'$ are pseudorandom functions, the way in which they
are combined makes the new function vulnerable. Letting $G''(s_1,\dots, s_n) = (y_1, \dots, y_{2n+3})$ is possible to create $(y_{n+2}, \dots, y_{2n+3})$ from $(y_1, \dots, y_{n+1})$. I think it's possible to crete a distinguisher that exploits this fact, but I don't know how to prove it.

Any help about how to move on?

You can construct a discriminator which applies G' on the first half of the output in question and compares it to the second half. If they match claim it came from G'' otherwise call it random.

This discriminator has no false negatives and a false positive rate of $2^{-n-2}$.

The ability to build an efficient discriminator with non negligible success probability proves G'' is not pseudo random.


AES and Homomorphic Encryption Is it possible to do the following?

Input would be to generate a new AES key, encrypt the private data with that key, encrypt the AES key with the FHE key, and send the FHE-encrypted AES key along with the AES encrypted data to the compute node.

It is possible to do, but depending on the performed operation, it may not be useful at all, so you have to choose the operation carefully.

The ultimate goal of FHE is to perform generic computations over encrypted data. That is, you have a generic function $f$ and you want to be able to compute it using encrypted inputs, so that:

\begin{equation}
f(\mathsf{Enc}(x), \mathsf{Enc}(y)) = \mathsf{Enc}(f(x,y))
\end{equation}

If you encrypt the AES key, and perform generic computations on the encrypted key and some other encrypted input, then, thanks to the homomorphism of the FHE scheme, you will obtain after decryption the computation over the key and the other input to the function. Therefore, depending on the computation (i.e., the function $f$), this could produce a different AES key, and the AES encrypted data cannot be retrieved with the resulting key.

However, that does not mean that what you suggest is not useful at all. A possible scenario is that the operation you perform over the encrypted data does not modify the original value, for example, when FHE is used for implementing a proxy re-encryption functionality. In this case, the original message would be the AES key encrypted under some public key $pk_1$, and the homomorphic function is actually decrypting the AES key under $pk_1$ and encrypting it again under $pk_2$. This way, when someone uses $sk_2$ to decrypt the result, he will obtain the original AES key.

Suppose that you have your AES key, $K$, encrypted under $pk_1$, that is, $\mathsf{Enc}_{pk_1}(K)$. You also have a FHE scheme so that $f(\mathsf{Enc}_{pk_2}(x), \mathsf{Enc}_{pk_2}(y)) = \mathsf{Enc_{pk_2}}(f(x,y))$, for some other public key $pk_2$. Now simply set $x = sk_1$, and $y = \mathsf{Enc}_{pk_1}(K)$, so:

\begin{equation}
f(\mathsf{Enc}_{pk_2}(sk_1), \mathsf{Enc}_{pk_2}(\mathsf{Enc}_{pk_1}(K))) = \mathsf{Enc_{pk_2}}(f(sk_1,\mathsf{Enc}_{pk_1}(K)))
\end{equation}

As you can see, if $f$ is designed to decrypt ciphertexts using the corresponding secret key, that is, $f(sk_1,\mathsf{Enc}_{pk_1}(K)) = K$, you are implementing a proxy re-encryption scheme that transforms ciphertexts from one public key to another, without altering the original message:

\begin{equation}
f(\mathsf{Enc}_{pk_2}(sk_1), \mathsf{Enc}_{pk_2}(\mathsf{Enc}_{pk_1}(K))) = \mathsf{Enc_{pk_2}}(K)
\end{equation}

There are other types of use cases; see for example the ones in mikeazo's answer.


If plaintext is random, how does it affect my choice of encryption algorithm? I want to encrypt a key file, which is assumed to be truly random (generated with hardware RNG, for instance). Given that there are no patterns in the plaintext, what implications are there for my choice of encryption algorithm? Could I get away with something as trivial as a Vigenere cipher (or XOR equivalent)? Assuming the keyspace is substantially large to prevent brute-force attacks, what other vulnerabilities are there when the plaintext is random?

Generally, no, but it depends somewhat on what you want to do with your random file.

For example, let's say you want to send the random file to your friend for use as a one-time pad.  Since you're worried that someone might be intercepting messages between you and your friend, you decide to encrypt the pad with a simple Vigenère cipher, like this:

$$P'_i = (P_i + K_{i \,{\bmod}\, L}) \bmod N$$

where $P$ is the original one-time pad, $P'$ is the encrypted pad, $K$ is a key (of length $L$) known to you and your friend, and $N$ is the size of the alphabet.

However, let's say that an adversary does intercept the encrypted pad $P'$ and saves a copy of it.  When your friend uses the decrypted one-time pad $P$ to send you a message $M$ encrypted as

$$M'_i = (M_i + P_i) \bmod N$$

the adversary intercepts that too, and uses the encrypted pad $P'$ they captured to decrypt it:

$$\begin{aligned}
M''_i &= (M'_i - P'_i) \bmod N \\
&= (M_i + P_i - P_i - K_{i \,{\bmod}\, L}) \bmod N \\
&= (M_i - K_{i \,{\bmod}\, L}) \bmod N
\end{aligned}$$

Now they have a string $M''$ which is simply $M$ encrypted with the same simple Vigenère cipher that you used to encrypt $P$ into $P'$ (except that the key has been negated, but that's a minor detail), and they can use standard Vigenère cipher breaking techniques to try and recover $M$ fairly easily.


Why SHA-512/256 when we already have SHA-384? Both of them are just SHA-512 with different IV's and truncation. What's the point of having 2 of them? (Actually we have 3 of them as SHA-512/224 is the exact same thing.)

The truncated versions of SHA2 are introduced in 2005 and in the Cryptographic hash Workshop, in 2005, Kelsey listed the reasons as;

Interoperability and security reasons
Need drop-in replacement for SHA1 (MD5)
Have unbroken hashes of wrong size

ECDSA/DSA key sizes
File and protocol formats

Though not mentioned by Kelsey or any other NIST document, the truncation also helps to mitigate from the length extension attack of the SHA series that is due to the Merkle-Damgård construction's architecture problem.
Using different IV enables the domain separation that enables us to have two different random oracles *. It makes sure that the truncated versions have different results. With the domain separation  $$\operatorname{SHA-224}(m) \neq \operatorname{SHA-256}(m)|_{224}$$ where $|_{224}$ is the truncation

What's the point of having 2 of them

If you have an already implementation that uses SHA-256 and you want to mitigate from the length extension attack then SHA512/256 is a good choice. Also, it possibly may increase attack strength.

Also, when you need only 256 but hash output, if you use the SHA512/384 you need to trim that yourself. Not a good idea in the case of programming and in the case of security since you are using the same random oracle.

The ECDSA/DSA key sizes: ECDSA-384 signing SHA512/384 is a good choice especially for 64-bit devices since SHA512 is designed for 64-bit.

Someone tried to use SHA512 and has problems with TLS 1.2. if you are adopting ECDSA-384 signing SHA512/384 is a good choice as above.

For SHA512/224 and simply for 224-bit usage is due to the Triple-DES security, $112 \cdot 2 = 224$. There is a very extensive answer for this by Fgrieu SHA-224 Purpose.

*A random oracle is like a kind of hash function and the same concept applies to hash functions.


How to compute secure sum using secure multparty computation? Suppose there are three voters $P$, $Q$ and $R$, and each will vote only on one candidate out of $X$, $Y$ or $Z$, with a 6 bit vote vector corresponding to $X
$, $Y$ and $Z$ respectively (with 2 bits each for a candidate. E.g., $( 01, 00, 00 )$ signifies a vote for $X$).

How can any voter find out the total number of votes cast for each candidate without disclosing their preferences by the use of secure multiparty computation?

Each 6 bit vote vector is encrypted and sent to the some third party who will then take the product of ciphertext votes and then decrypt the product to yield a bit vector which shows the total number of preferences received by each candidate (Paillier cryptosystem).

What homomorphic property must be held by the cryptosystem in the plaintext and in the ciphertext space to satisfy the objective?

Finally, I need some theoretical explanation finding secure sum using SMP (with and without random seed) and SMC to sort the numbers.

In general, there are many techniques for secure multiparty computation. However, the problem of voting is much broader than this, and if you are really interested I suggest looking into the voting literature in depth.

One of the big questions is the model: typically, you cannot run a regular MPC protocol since that requires interaction among all the parties. One solution (which is an old work, but one that I really like), separates between an election service provider and the actual election being held. Actually the work talks about auctions, but a similar idea can be used. See Privacy Preserving Auctions and Mechanism Design.

For more modern work on elections, see Helios (which is the scheme used by the IACR). I suggest looking at Wikipedia - end-to-end verifiable voting for some sources, but note that a lot of research is needed. In general, secure tallying is a tiny part of what is needed for a real election (and the easiest to solve).


Key space: Dense and sparse I'm taking a cryptography class and I come across these terms dense and sparse key space allt he time. What do they mean?

As far as I can I understand, dense key space means that there are more combinations of the keys in that particular space and sparse the opposite. If yes, assuming I use elliptic key cryptography i.e.

  y^2 = x^3 + ax^2 + bx + c,

How is it that elliptic key cryptography is more dense(less sparse) than the RSA cryptography?

Please tell me if I need to be clearer.

This "dense key space means that there are more combinations of the keys in that particular space and sparse the opposite" is pretty much it.

Depending on cryptographic algorithm, key space can be less or more sparse. This depends on what primitives and possibly, what hard problems the security of the algorithm is based on.

Symmetric cryptographic algorithms use just one key and use simple algebraic or logical operations. Because these operations generally work with all possible input values, they key spaces can be (and usually are) dense. For many symmetric algorithm, each possible combination of bits of input key space is valid key (maximally dense), for some others bits less.

Public key algorithms use separate public key and private key, with specific semantics: it should be reasonably hard (likely require brute-force search of key space) to discover private key if public key is know. This kind of more complex semantics put more requirements into the operation of the algorithm. Algorithms become more complex, much slower and the key sizes they use become larger. The currently known public key algorithms are based on some problems known to be hard.

For instance, RSA is based on integer factorization problem: it is hard to factor composite number built from two prime numbers to prime numbers that make up the number. This is actually already quite close to the reason why RSA's key space is sparse. The RSA key for common 2048-bit key size is built from two 1024-bit primes. Prime number theorem describes how to estimate number of primes smaller than specify number. Math question How many all prime numbers p with length of bits of p = 1024 bits? answer can be used to estimate how sparse RSA key space is: only $\frac 1 {2ln 2^{1023}}$ out of 1024-bit bit combinations are acceptable prime numbers, and it is required to have two such primes. This means that only around every millionth of number between $2^{2047}$ and $2^{2048}$ is acceptable, which could be considered relatively sparse.

(Note: in RSA also public exponent needs to be chosen. For simplicity I've not considered full RSA key generation here, feel free to refer NIST's FIPS 186-4 standard in case you want more detail).

When considering elliptic curves, important number to consider is prime number n, one of the curve parameters. For most curves, (nearly) any number smaller than n will be acceptable private key. Thus it is easy to see that the key space is considerably denser than RSA.

Note: for EC, some of formats for the public key take twice as much bits to represent than the strength of the curve (or private key). Still, they are significantly denser than RSA of equivalent strength.

Relation with security

The sparse/dense key space has some relation with strength of the cryptographic algorithm. If only acceptable keys are prime numbers, then possible attackers may skip many of keys with little processing. Thus the strength of the algorithm can be considered to be at most the effective key space, this does not, however, remove any other algebraic reasons why there would be even better (easier) ways to attack the algorithm.

Please, tell me if I need to be clearer.


HKDF on output key material of previous HKDF I understand the typical way to use HKDF is to make one call to HKDF to obtain multiple keys. Is it safe to use HKDF the following way to generate different keys ? If not, why?

key0 = HKDF-extract-and-expand(0 salt, Z(DH key exchange), x co-ordinates of public points as info).

key1 = HKDF-expand(key0, info1)
key2 = HKDF-expand(key1, info2)

Also, is it safe to replace HKDF-expand for key1 and key2 with sp800-108 or HMAC_SHA256(key0, counter)? i'm curious if there are any subtle differences between them that make them not interchangeable ?

It's not necessarily unsafe to create keys that way, but:

the x-coordinates of the public key are already used for calculating Z, so I don't see why inclusion in the KDF makes any difference;
without the x-coordinates, you may as well use HKDF-extract only to derive key0;
key2 is now derived from key1, while it is better to derive them both from key0.

As for point 3, there is no need for the security of key2 to rely on both key0 and key1.

Generally KDF's are interchangeable and even less well studied ones commonly use one-way functions such as hash algorithms with well distributed pseudo random output. However, HKDF comes with 2 advantages:

a more rigorous security proof and;
a split between extract and expand.

It would make sense to use it for those reasons.


What is the purpose of calculating the N modulus in the encryption phase of asymmetric cryptography? I was reading a paper entitled : "Mathematical Underpinnings of Asymmetric Cryptography". I came across this

If $N$ is the product of two large prime numbers $p$ and $q$, say 300 digits each, and $e$ is just coprime with $(p-1)(q-1)$ so it can be a relatively smaller number, my problem is that if I am to raise a certain numerical representation of my text, say $M$, to the power of $e$, it will still be smaller than $N$, therefore $M^e \bmod N = M^e$. So the modulus is not doing anything. I realize that you can just add $kN$ ($k$ being an relative integer), but that's missing the whole point.

What am I missing?

What am I missing?

Not much; you've just come across one of the reasons why we never use "raw RSA".  Instead, whenever we use RSA (say, for encryption), we always pad out the message so that, after padding, it's not much smaller than $N$.  This prevents the message from being less than $N^{1/e}$ (which, as you point out, would be completely insecure), and it also prevents subtler attacks based on the homomorphic properties of raw RSA (namely, $RSA(x)RSA(y) = RSA(xy)$


How do we find the subkey out of a differential cryptanalysis? I understand the differential cryptanalysis up to the "finding the last subkey" part. If XORing with the key doesn't change the differentials, how can testing different key affect the equations we found?

EDIT: I think I kinda get the answer now. Although I'd like a confirmation:

After getting all those probabilities on the differentials at different stage in the cipher. You test these probabilities with real pairs of messages and ciphertexts and you see if for an hypothetical key the probabilities you found hold. If they don't it's probably because you had a bad key, if they do then you probably have a good key.

EDIT2: Mmm, actually no I still don't understand. Even with a bad key, probabilities we found still should apply...

The key does not effect the cipher' differentials threw the equation (x+k)+(x'+k)=x+x' (the + sign means xor)

How you can yes the key is X1+k=x2
And threw the xor k=X1 +x2

X1 is the value beffor the xor with the key value k. X2 is the output of X1+k

To make this attack work beffor you must find a differential for the two input pairs threw a chosen plaintext attack x'+x= D1 (differential 1)
Then the corresponding cipher text outputs y'+y=d2 then you follow the differential path that you have made. (Threw this attack you can drop one round as once you found 1 key then the other key must also follow suit to be able to get the cipher text wanted)

To lower the probability of the correct key you repeat this process with a new path and a new chosen plaintext. If keys match between the two keys found then the probability goes up.

If this doesn't help try http://www.theamazingking.com/crypto-diff.php

And
http://www.cs.cmu.edu/~hannes/diffLinAES.pdf

Some defenses against DC is adding more rounds or by trying to get differential uniformity for the s-box.


Find prime $p$ such that $a^x\equiv b\pmod p$ for many $x\in[1,p)$ Given haphazard large integers $a$ and $b$ (like few thousand bits), can we efficiently find (and how) some integer triplet $(p,x,k)$ with

$p$ a large prime (like a thousand bits)
$a^x\equiv b\pmod p$
$k$ sizable (say of 10 bits or more if possible) and dividing $p-1$
$a^{(p-1)/k}\equiv 1\pmod p$

These conditions match the title, since $x_j\gets j\,(p-1)/k+(x\bmod((p-1)/k))$ gives $k$ distinct $x_j\in[1,p)$ with $a^{x_j}\equiv b\pmod p$.

Late addition: in a variant with reduced applicability, one of $a$ or $b$ would be an output instead of a given, with the constraint that it should be unremarkable modulo $p$ (at least not among $0$, $1$, $p-1$) when the other is haphazard.

You asked for my one-in-a-million attack; here is what it looks like:

Step 1: find a large prime factor of $b^i - 1$, for some small $i$.  This can be done by iterating through the various small values of $i$ (starting with $i=1$ naturally), use the known factorizations (e.g. $b^2 - 1 = (b+1)(b-1)$), and then for the various subfactors, scrap off the easy small factors and hope what's remaining is a prime (e.g. $b+1 = hp$, for some small $h$ and prime $p$.

If this step succeeds, then we have $a^{0} \equiv b^i \pmod p$; check to see if this yields an $x$ (i.e.. if $a^{n(p-1)/i} \equiv b \pmod p$ for some $n \in \{0, …, i-1\}$).

An initial estimate is that we will manage for find just an appropriate $p$ (and $x$) about 1 in 1000 arbitrary $b$ values in the "thousand bit" range.

Step 2: find $k$.  To do this, find the small factors of $p-1$, and for various small (not necessarily prime) factors $k$ in the appropriate range, check if $a^{(p-1)/k} \equiv 1 \pmod p$.  If $a$ is random, this happens for a particular $k$ with probability $1/k$ (actually, perhaps a bit less if $i > 1$ in the previous step...)

Again, a very rough guess would be that this may succeed about 1 every 1000 times (that we have a factor $k$ of the appropriate magnitude, and that $a$ happens to be in that subgroup).

If both steps succeed, you have $p, x, k$ as requested (although, looking back at it, perhaps a probability of "one in a million" is a tad optimistic; "one in ten million" might be closer...


Does libsodium sealed box leak key ids? I am using python and libnacl, which is a libsodium wrapper, to develop an application where users can deposit encrypted data.

Alice uses libnacl.sealed.SealedBox(keyBob) to encrypt her message and uploads it to a database for Bob to download it.
Bob and Eve can read the database and observe there I a new entry. Neither Eve nor Bob cannot tell that the message was sent by Alice. Bob can decrypt the message and therefore knows that he is the recipient.

Eve also knows Bob's public key.
Can Eve tell that the message's recipient is Bob?

edit:
VincBreaker pointed me at the documentation of libsodium sealed box where you can find:

  ephemeral_pk ‖ box(m, recipient_pk, ephemeral_sk, nonce=blake2b(ephemeral_pk ‖ recipient_pk))

This tells some "ephemeral" public key is included in the sealed box.
What does "ephemeral" mean?
To be precise is there a way to link the ephemeral_pk to Bob's actual public key?

The answer from the libsodium web site

  Only the recipient can decrypt these messages, using its private key. While the recipient can verify the integrity of the message, it cannot verify the identity of the sender.

While Bob can decrypt the message and cannot verify the identity with his public and private key pair, there is no way the Eve can determine with the only public key.

To understand the sealed box we must first see the crypto box.

Crypto Box Structure

Cryptobox encrypts and authenticates a message $m$ using the sender's secret key and receiver's public key and a nonce $n$.

$$c = box(m,nonce,recipient_{pk},sender_{sk})$$

The receiver, verifies the and decrypts the $c$ by using his secret key and sender's public key.

Sealed Box Structure

A sealed box constructed only using the public key of the recipient. The sealed box is;

$$sealed\_box = ephemeral_{pk} \| box(m, recipient_{pk}, ephemeral_{sk}, nonce)$$
$$nonce = blake2b(ephemeral_{pk} \| recipient_{pk})$$

an ephemeral private and public key pair (generated and used once) is generated and later the ephemeral private key is destroyed.

Therefore, the sealed box contains no information about the sender.
Since the sealed box can only be opened by the $recipient_{sk}$ the Eve cannot understand the recipient, too.

However, Eve can look for who downloads the message. Without it how is going to Bob know that there is a message for him? The best way to protect from this is;

Bob check himself
Bob uses Private Information Retrieval to hide the data he access.

Also, this answer for What is the difference between a sealed box and a normal box in libsodium? might be helpful.


Authenticated Encryption of UDP packets I am working on a UDP based file transfer protocol. Congestion Control, Resending of packages and other UDP challenges are dealt with - speedtests shows that the protocol is up to 10 times faster than e.g. HTTP for transferring large files when the latency/rtt is > 100 ms (e.g. between Europe and the US).

The protocol will be used in a server/client architecture - where a server will send/receive data to/from many clients.

Servers are running .NET - and clients will be written in .NET, Java (Android), and Swift (OS X, iOS).

And - it's now time to make the UDP protocol secure.

Some requirements:

Must be secure and fast :)
Must be supported on .NET, OS X and Java
Must support some kind of SessionID - so that the server can separate different clients from another and use the appropriate key for each client.

Reading this post I agree with the approved answer by Otus:

Don't roll your own protocol, but use (D)TLS.
If you must roll your own protocol, use an authenticated encryption mode.
If you can't, at least use standard encryption and MAC.

Here are my thoughts regarding these 3 alternatives:

DTLS
The reason I am a bit sceptical towards DTLS is that I am unable to find any good/trusted implementations for it in C#. BouncyCastle is a museum of old crypto and bad ports according to  Inferno. Eldos has another implementation, but I am unsure of the quality + it's a bit pricey.

Authenticated Encryption Mode
AES-GCM is a good AEAD candidate, and also fast. Inferno has a .NET implementation and there seems to be good candidates for Java and OS X /iOS we well (OpenSSL). However - I'm a bit sceptical to getting all these libraries to work together correctly - just a gut feeling. SessionID could be included as AdditionalData (AEAD).

Standard Encryption and MAC - here's what I'm currently thinking:

Get TLS1.2 Cert Client retrieves the TLS1.2 certificate of the server through a .NET HTTPS call. The client has also authenticated the server by making this call.
Handshake. Client generates a KEY - and encrypts this with the public key of the server. The client sends a "handshake" UDP package to the server containing:

SessionID - A Guid generated by the client. Used to identify client for all subsequent communication. (I do not wish to use a combination of IP/Port to identify client - due to the parking-lot problem)
A SHA-256 Hash of (1) + (3) + KEY (often referred to as MAC)
The Generated KEY - AES-256 encrypted with the public key of the server.

The server and client now has a shared private KEY that they both use to synchronously encrypt/decrypt messages that they send/receive - very similar to the way SSL/TLS works I guess. (Doing async encryption/decryption with the private/public key of the server will be extremely slow)
Each subsequent UDP package sent by the Server will contain:

SessionID - GUID. Plain text. Server uses this to lookup key on its side.
A SHA-256 Hash of (1) + (3) + KEY. This way - the plaintext SessionID is authenticated.
Payload encrypted with AES-256

The advantages - as I see them - are that I am using standardized (and relatively simple) building blocks that are well-proven and easy to implement/test/debug on all platforms. I also get an authenticated SessionID into the mix.

What are your thoughts? Is 3. a feasible option - or should I abandon this approach?

You can use DTLS here.  C# can call any C API via P/Invoke.  OpenSSL, BoringSSL, Network Security Services (NSS), and mbedtls all provide C interfaces to DTLS.

Unless there are existing bindings, you will need to implement at least some of the P/Invokes yourself, but this is much easier than writing your own cryptographic protocol.

It would be very nice if you could open-source these bindings, for the benefit of those who follow in your footsteps.

Also, note that AES-GCM is, in the absence of hardware support, very tricky to implement in a way that is immune to cache-timing side-channel attacks — so tricky, in fact, that many production implementations are not hardened against such attacks.  Implementations that are immune to cache-timing attacks deliver suboptimal performance.  ChaCha20-Poly1305 is an efficient, secure, and portable alternative.  It is several times faster than pure-software AES-GCM while being immune to many side-channel attacks.  Since you mention mobile devices, you probably will not have hardware support for AES, so ChaCha20 is both faster and easier to implement securely.


homomorphic encryption E(x+y)=E(x) . E(y)? I'm new to cryptography and I was trying to familiarize myself with ZKsnarks .
here is an explanation on this blog : https://blog.z.cash/snark-explain/
in the middle of the page from $E(x) = g^x$  it reaches to $E(x+y)$ = $E(x) \cdot E (y)$ which doesn't sound right to me because generally we have :

$$[a \cdot b] \bmod n = [ (a \bmod n) \cdot (b \bmod n) ] \bmod n$$

there fore the equation above should be :

$$E(x+y) = [E(x) \cdot E (y)] \bmod p$$

and same goes for the multiplicative property of RSA .
could you please tell me what is it that I'm missing ?

could you please tell me what is it that I'm missing ?

Typically, when we write $a \times b$, the operator $\times$ needn't be multiplication over the integers (or reals or complex numbers).  Instead, it is often some group/ring/field operation that is somehow analogous to the more common multiplication operations we all learned in grade school.

That's exactly what is happening here.  In this case, the elements $a, b$ (or, in this case, $E(x), E(y)$) are understood to be elements in the group $\mathbb{Z}^*_p$, and so the multiplication is done in that group.  That multiplication can be implemented by performing a standard integer multiplication, and then taking the result modulo $p$; writing that out explicitly gives your result.

So, why do we do such a short-hand? Are we lazy?  Well, partially, yes, we have no reason to clutter the equations with things that are well-understood.  On the other hand, sometimes we work with things, such as extension fields, or elliptic curve groups, which do not have such a simple "do a normal addition/multiplication and then fix things up" way of looking that things; trying to write things out explicitly in the 'grade-school approved notation' would be tricky...


Shamir's Simple Sharing Scheme - preventing partial recovery of data In SSSS, if you recreate the original secret with one of the decoder inputs being slightly damaged (e.g. one or two chars incorrect), you receive a slightly damaged version of the original secret. So if the original secret was "Abraham Lincoln", decoding using a slightly damaged input might still get you "Ab%aham Lincoln", for example.

What's the best way to encode and decode the secret, on top of SSSS, such that any variance at all in the inputs causes the decoded secret to be completely useless?

One obvious way would be to encrypt the secret before using SSSS. Are there any alternatives? In particular, any alternative that would not require each user to have a final decryption key (for decoding the secret that comes out of SSSS) as well as their SSSS decoding keys?

With SSS you are sharing field elements, so if the secret to be shared is larger than one field element, you are going to have to break up the secret somehow and share the parts. I am not aware of any standard method that allows you to make the sharings dependent on one another. Probably the best way is to encrypt the secret with a key and then share the key (using Shamir) and the encrypted secret (e.g using an appropriate erasure code) and store the share/fragment parts at different locations.

Note that this is not a problem of SSS. In SSS if a share is slightly corrupted it cannot be used in reconstruction.

You could also pick a field large enough for your secret.


XSL on serpent and rijndael - which is most affected? So I've often looked at serpent and thought it was a very strong contender in AES. Not so long ago I was looking for evidence as to why it didn't beat rijndael. So far, the closest I've got answering that is this:

  The 32 rounds means that Serpent has a higher security margin than Rijndael; however, Rijndael with 10 rounds is faster and easier to implement for small blocks. Hence, Rijndael was selected as the winner in the AES competition.

Which is from the wikipedia article and is marked citation needed. So further down the page I came across this other interesting piece of information:

  The XSL attack, if effective, would weaken Serpent (though not as much as it would weaken Rijndael, which became AES). However, many cryptanalysts believe that once implementation considerations are taken into account the XSL attack would be more expensive than a brute force attack.

Also citation needed. So my question is now - to what extent is this true? Is Serpent more resistant to XSL attacks? Given that XSL works by representing a cipher as a system of equations, isn't it then only a matter of finding an efficient way to solve a particular set of equations? I.e. isn't the very fact an algorithm can be represented as a set of equations the key issue, or are there certain sets of equations that are provably harder to solve?

(I'm really interested in working out which has the better security margin, but given these statements I think the first step for me is to clarify the XSL issue).

First, from a direct witness of the events (i.e. myself): Serpent was indeed felt as "too slow" when compared with Rijndael, by a factor of 2 to 3. The performance of Rijndael was not the best there was on a PC (RC6 was faster) but it wasn't abysmal on any platform, especially 8-bit smartcard (contrary to, say, RC6). Serpent performance was consistently lower than Rijndael's. See this page for benchmarks of the AES candidates on various software platforms at the time of the competition.

XSL attacks were discovered in 2002, hence after the choice of Rijndael as the AES; therefore, they could not have been a parameter in the choice.

In their paper, Courtois and Pierprzyk "show" that AES (i.e. Rijndael) with a 256-bit key, and Serpent with a 192-bit or 256-bit key, are "broken", which means that the attack ought to recover the key with less work than the CPU needed to evaluate the block cipher $2^{256}$ times (resp. $2^{192}$). They certainly did not go below $2^{128}$, so the break is only theoretical and unverifiable. That's part of the problem, too: the analysis is based on a number of probabilistic assumptions on an equation-solving algorithm in a situation where it is out of the question to actually run it on existing hardware. So XSL attacks are an effective break only insofar as their description is intellectually convincing. Don Coppersmith has publicly expressed that he was not convinced. And when Coppersmith says that your research stinks, it is time to worry.

Anyway, that an algorithm can be represented as a set of multivariate polynomial equations is not the key issue: any algorithm which can be implemented as a circuit is amenable to such a representation (e.g. because a NAND of $x$ and $y$ is equal to $1+xy$, when computing modulo 2, and every boolean operator can be built out of NAND gates). Generally speaking, solving a set of multivariate polynomial equations is hard. Courtois and Pieprzyk argue that the specific structure of the equations in the case of Rijndael and Serpent can be exploited into running a dedicated variant of Shamir's re-linearization solving algorithm fast enough to be considered, academically speaking, as a "break".

The interesting part in XSL attacks is that resistance grows with the number of rounds, but not exponentially, contrary to more mundane differential or linear cryptanalysis. The bad part of XSL is that most cryptographers do not believe that it works as advertised, or at all. On the other hands, most think that Serpent is a more "conservative" design than AES, with a correspondingly "higher" security margin (but there is no really scientific way of quantifying such a "margin" so these are really all fuzzy feelings).

On the matter of attacks of debatable success, you could consider cache timing attacks, which are not an issue with the algorithm per se, but with its implementation. At least that attack could be demonstrated in lab conditions (the debate being whether the lab conditions have any similarity with whatever could occur in the field). Serpent is "naturally" immune to such attacks, because the normal implementations on software platforms will not use any table at all.


Number of bits specified in standards implementation? Currently deployed RSA and discrete logarithm implementation uses $1024$ to $2048$ bits.

Hypothetically speaking if a crypto team produces a faster algorithm that moves current factoring and discrete logarithm capability to say $8192$ bits (four times today's recommendations) is there any provisions in the standard to increase the implementation to beyond $8192$ bits?

Can corporations and banks solve the issue in a matter of days?

I'm not sure if you talk about generic products or your own product, but generally 1024 bits is not considered enough anymore, and 2048 is considered borderline secure. It's still used a lot, but I'd say 2048 bits is now the bare minimum.

You're not naming any standard so we don't know if it can handle larger bit sizes. If you're talking about the RSA / DSA standards themselves: sure they can handle any kind of bit size. Implementations commonly only allow bit sizes that are a multiple of 8 or 32 bits, but that's an implementation detail.

A 1024 bit key only offers up to 80 bits of security (against the best attacks) and 2048 bit keys offer about 112 bits of security (source: NIST / keylength.com. For higher strength ciphers it is often better to look at Elliptic Curve cryptography which offers higher security for smaller sized keys. Unfortunately both RSA and EC are not secure against (large scale) quantum computers.

Corporations and banks cannot solve anything in days. To name just one issue: bank cards (smart cards) often can only handle up to 2048 bit RSA. But even if they support 4096 bits then it will be impossible to update or replace all the cards in days. Performing large scale redeployment of all keys would certainly also pose issues.


Why is NON DISCRETE logarithm problem not hard as the DISCRETE logarithm problem (so computationally hard)? I've already read this question about the difference between discrete and non discrete logarithms.
But I still have problems to clarify my mind about why the Discrete Logarithm Problem is computationally hard while the NON Discrete Logarithm Problem is not, as I read in my Cryptography and Security book.

What are the computation differences? Why can I, for example, easily break a non discrete logarithm cipher but not a discrete one?

The main point is that the entire apparatus of calculus applies to exponentiation over the real numbers. For instance, if $a$ and $b$ are close, then $g^a$ and $g^b$ are close as well. The exponential function and its inverse are nice, so you can use infinite series for your computation, and some partial sum will be close enough to the correct answer. Or since exponentiation is monotonic, you can use binary search.

The groups we use for cryptography are usually discrete, and the apparatus of calculus no longer applies. For example, there is no sensible distance measure that relates the distance between $a$ and $b$ and the distance between $g^a$ and $g^b$. And this means things end up being more difficult.


Is this streamable combination of encryption and MAC secure? I want to combine encryption and MAC.

For encryption I use AES-256 with CBC and PKCS5Padding.
For MAC I use HmacSHA512.

I use the Encrypt-then-Mac approach (calculate MAC over the ciphertext and deliver it with the ciphertext)

The algorithm should be able to process streamed data, and if I calculate the MAC once over the whole ciphertext, there are two possibilities:

Prepend the mac to the ciphertext:

This is a very bad idea, because the encryption part has to encrypt the whole text before it can output the mac. Therefore it's not streamable. On decryption, we have to process the whole ciphertext before knowing if is compromised (also not fully streamable).
Append the mac to the ciphertext:

Better idea, but the decryption part can only check the MAC in the end. Before that, it did output many bytes that could have been changed by an attacker, or it has to wait until it sees the MAC (not streamable again).

So I need a solution which divides the ciphertext into parts and then calculates a MAC for each part. Because the ciphertext shouldn't be much larger than the plaintext, I choose a MAC block size that is greater than the encryption block size (for example 4 kB).

I want to use a pattern like (with $c_X$ = part X of the ciphertext, $m_i$ = part X of the MAC):

$$ m_1 || IV || c_1 || m_2 || c_2 || m_3 || c_3 || \dots $$

The calculation of the first MAC is clear ($k$ being the MAC key):

$$ m_1 = MAC(k, IV || c_1) $$

But then we meet problems. If we just use

$$  m_X = MAC(k, c_X), $$

this wouldn't be secure. An attacker could change the blocks in order, he could duplicate or remove whole blocks, and so on.

So I thought about an idea similar to CBC mode in encryption:

$$ m_X = MAC(k, m_{X-1} || c_X) $$

Is this now secure? And is there a difference to this one?

$$ m_X = MAC(k, c_1 || ... || c_X) $$

It looks like your protocol is secure for integrity purposes, i.e. the receiver will only accept a stream if it is the same as the one sent by the sender (assuming the MAC is not broken).

But if your possible attack scenarios contain a (partial) chosen plaintext attack, the use of CBC makes it weak against the BEAST-like attack against the confidentiality part, mentioned in the comment by CodeInChaos.

For CBC to be secure against chosen-plaintext attacks of the BEAST-style, it is important that each block's "effective initialization vector" (i.e. the previous block or the IV for the first block) is sent not earlier than the content of the block is fixed. If you send your stream in MAC-block pieces (i.e. $m_i || c_i$) and you send one such full piece before the (plaintext of) the first block of the next piece is known, an attacker which can both observe the ciphertext and chose this block of plaintext can use this to verify guesses about other parts of the ciphertext.

In your context of file encryption, quite likely the full file is already fixed when you start encrypting it, thus this attack is not possible. But make sure you document this limitation when creating your program. Alternatively, use other modes like CTR instead of CBC, which are not weak against chosen plaintext attacks.


Differential & linear characteristics for integer multiplication What are the probabilities of differential & linear characteristics for the function that XORs the high and low bits from a $n \times n \rightarrow 2n$ bit multiplication?

I remember reading somewhere that this function (which seems very fast in software) has excellent non-linearity.  This suggests applications in (say) a Feistel network (where invertability is not required).


secret and unique random number generator within a range I am trying to think of a way to generate secret and unique random numbers within a range.

Say we have a public range [1-n], how could we have a maximum of n users choose a random number within this range and ensure that no one else chooses the same number.

The difference between this question and others is that we want to keep the chosen number a secret this time.

It would be okay to have a third party facilitate the process, however, I would still like the third party to not learn anything about the final number generated for the user.

Is this feasible?

A first cursory reading suggests that a format-preserving cipher like NIST SP 800-38G FF1, which makes an easy way to pick permutations of odd-sized blocks with short keys, might help.  But you asked that nobody learn anything about the final number generated by the user.  Here's a simple-minded protocol with approximately five minutes of effort put into it.  Maybe if you put more effort into it you could find a secure multiparty computation that doesn't require a trusted third party.

Pick an authenticated cipher $E_k$ like crypto_secretbox_xsalsa20poly1305.  Pick a DH function $(a, P) \mapsto [a]P$ with standard base point $B$, like X25519.  Enlist the help of a dealer Dale and an independent trusted third party Trent.

Each user generates secret scalar $p_i$ and publishes $P_i = [p_i]B$.
Dale picks a permutation $\pi$ of $\{1,2,\dots,n\}$ uniformly at random.  (You could use FF1 for this, but you might as well just do a Knuth shuffle unless $n$ is so gigantic this protocol isn't feasible anyway.)
Trent picks a permutation $\tau$ of $\{1,2,\dots,n\}$ uniformly at random.
For each $i$, Dale picks a blinding factor $b_i$ uniformly at random and sends $P'_i = [b_i] P_i$ and $\pi(i)$ to Trent.  Dale should make sure to send these messages to Trent in the order given by $\pi$.
On receipt of $P'_i$ and $\pi(i)$, Trent computes $u_i = \tau(\pi(i))$, picks $q_i$ uniformly at random, computes $k_i = H([q_i]P'_i) = H([p_i q_i b_i]B)$, computes $c_i = E_{k_i}(u_i)$, and returns $Q_i = [q_i]B$ and $c_i$ to Dale.
Dale sends $Q_i$, $b_i$, and $c_i$ to the corresponding user, encrypted with their respective public key the usual way if need be.
Each user computes $k_i = H([p_i b_i]Q_i) = H([p_i q_i b_i]B)$ and opens $c_i$ with $k_i$ revealing their unique number $u_i$.

In this protocol:

Each user learns only their own number $u_i = \tau(\pi(i))$: without knowledge of $\tau$ or $\pi$, which are independent uniform random permutations, they can't invert $\tau$ or $\pi$; and without the other users' secret keys or blinding factors $b_i$ they can't decrypt any traffic over the channels between Dale, Trent, and the other users even if eavesdropped.
Dale, knowing only $\pi$, $P_i$, $b_i$,  $Q_i$, and $c_i$, can't compute any $u_i$ without knowledge of $p_i$, $q_i$, $\tau$, or $k_i$: the number is chosen by a uniform random permutation $\tau$ known only to Trent, and encrypted with the user's public key $P_i$ using an ephemeral key pair $(q_i, Q_i)$ known only to Trent and a secret session key $k_i$ shared only by Trent and the user.
Trent, knowing only $\tau$, $P'_i$, and $\pi(i)$, can't compute $i$ or which $P_i$ the blinded key $P'_i$ corresponds to without knowledge of $\pi$ or $b_i$, and so can't tell which user $i$ gets $u_i$: the number $\pi(i)$ is chosen by a uniform random permutation $\pi$ known only to Dale, and the public key $P'_i$ is blinded with the uniform random secret $b_i$ known only to Dale.

CAVEAT CRYPTATOR: I'm a pseudonymous bird on the internet and scratched this out without review or careful thought about it.


How can semi-weak DES keys be leveraged to attack DES? I see how DES weak keys can be leveraged under chosen plaintext attack where an adversary feeds the ciphertext encrypted by a weak-key back to the DES encryption function and gets plaintext as a result.

The probability that both keys from the semi-weak key pair are used seems to be very small ($6/2^{56} \times 1/2^{56} \approx 1/2^{110}$) making chosen ciphertext attack significantly slower as compared to exhaustive key search ($1/2^{56}$). If this logic is correct, then how can one leverage semi-weak keys to attack DES?

The answer is that they cannot. DES weak keys will be chosen with such a small probability that they don't matter at all. The only reason that weak keys are of interest is when you want to use a block cipher as an "ideal cipher" like in order to construct a collision resistant hash function. These sort of constructions break completely when a cipher has weak keys. But, this is not a criticism of DES or other block ciphers; they are made to be pseudorandom permutations and are not made to be hash functions. Rather, in my personal opinion, this is a criticism of people who try to use primitives designed for one purpose for something completely different.


Is there a quick way to know the length of a message hashed using SHA3? Let M be the message that has been padded for use into the SHA3 (standardized Keccak) hash function.
Is there a way, like it's the case for SHA1, to know the total length of the message M just by looking at the last block?

For example, in SHA1, I can give you the last block (that was padded) and you can extract the total length of the message (I'm not worried about security here).

Is there anything similar with SHA3 or do I need to count each block separately?

In some specific cases the answer is yes, in other cases the answer is maybe. SHA-3 has four flavors 224, 256, 384, and 512. Now the “block length” given a particular version is 1152, 1088, 832, and 576 bits respectively. Block length is in quotes because this is only the first step in message pre-processing.

All this means is that given the particular variation of SHA-3 that is being processed, the input message will be broken down into 1152, 1088, 832 or 576 bit chunks. Keep in mind this step is completed before any padding actually occurs so the last chuck doesn’t necessarily have to be one of previously mentioned lengths.

Now you have a_set_of_bit_strings, and we’re interested in the last location, or a_set_of_bit_strings[-1] as per python’s notation. At this particular location if the length of the bit string is not one of the following values 1152, 1088, 832 or 576 it will be padded to one of those lengths as outline in FIPS 202.

Next based on the particular SHA-3 implementation all bit strings contained in a_set_of_bit_strings will be back appended with zeros until their length is 1600 bits as per the width specified in FIPS 202. For the purpose of my explanation I DON’T consider this step padding, because it’s not variable based on input message length. People like to use "sponge" to describe this, but I feel it just adds confusion (I don't mean the crypto definition, I mean it's just misinformation). It just means that over each iteration of SHA-3 security(ie collision resistance) is achieved through bits that aren't included in each "block", because in reality the XOR operation can be manipulated to shift all leading bits to either 1 or 0, but you have no control over tailing bits. Hence the strongest version SHA-3(512) splits the message input into the least number of bit chunks!

Things get interesting when the message you’re trying to hash has a bit length that is an integer multiple of one of the following values 1152, 1088, 832 or 576. In this particular situation no padding occurs, and instead an empty string is appended to the end of your message. Why this happens you can determine for yourself.  It’s also important to note that this empty string is then passed to the padding protocol outline in FIPS 202. So to answer your question if the bit length of your message is an integer multiple of 1152, 1088, 832 or 576, and matches with its respective SHA-3 implementation, then yes, if you hand me a_set_of_bit_strings[-1] and it’s equal to ‘’ (An empty string) then I’ll know the input message’s length is an integer multiple of 1152, 1088, 832 or 576. But this is a very specific situation. Past this I have not investigated.

I’ve included my SHA-3 bit orientated code below, it’s gross and hacky but it might help you see what’s happening at the end points. The function you’d be interested in would be sb(), and should investigate value set_main[-1] in sb() . If you want to check it against other open source implementations use online_convert().

Link to SHA-3 Code

I will investigate values that aren’t multiples of 1152, 1088, 832 or 576.


ECC How do the Curve, its number of bits of security and key size affect the maximum size of ciphertext? First of all, excuse me if this question is too noobish.

I'm trying to understand how these things are relate: Curve type, its 'number of bits of security', size of the key and the maximum ciphertext size.

Comparing to RSA, I know, that size of the key directly affects the maximum size of ciphertext: it can never exceed the key size and in practice is even smaller than that.

Is this still holds for ECC?

If so, what's the limitations on the size of the key in terms of a specific Curve? Is it even possible to allocate keys of different sizes? Or, given that math is discrete, does each curve has a hard ceiling for a key size?

If on the other hand, the key size is unlimited, is it true that no matter how large it is, the effective hardness of encryption will never exceed the 'number of bits of security' of specific Curve? If so, does increase the key size only gives you a larger limit on the ciphertext size?

The standard way to do public-key encryption with elliptic curves has no limit on ciphertexts.  It works roughly as follows, with many details omitted for practical instances:

  Parameters.

  Fix an elliptic curve $E/\mathbb F_p$ over a finite field $\mathbb F_p$, e.g. $p = 2^{255} - 19$ and $E\colon y^2 = x^3 + 486662 x^2 + x$ (Curve25519).
  Fix a standard base point $G \in E(\mathbb F_p)$ of large prime order $\ell$, e.g. $G = (9, \dots)$.
  Fix a hash function $H\colon \mathbb E(\mathbb F_p) \to \mathbb \{0,1\}^{256}$, e.g. SHA-256 on the little-endian encoding of the coordinates.
  Fix an authenticated (symmetric) cipher $E_k$, e.g. NaCl crypto_secretbox_xsalsa20poly1305.

  Public keys.  A public key is the encoding of a point $P$ on the curve with coordinates in $\mathbb F_p$.

  Encryption.  To encrypt a message $m$: Pick an integer $b$ with $0 \leq b < \ell$ uniformly at random.  Compute $k = H([b]P)$, the encapsulated symmetric key.  Compute $c = E_k(m)$, the authenticated ciphertext.  Compute $Q = [b]G$, the encapsulation of the symmetric key.  Transmit $Q$ and $c$.

  Private keys.  A private key is an integer $a$ with $0 \leq a < \ell$ chosen uniformly at random.  The corresponding public key is $P = [a]G$.

  Decryption.  To decrypt a message given $Q$ and $c$, knowing the private key $a$:  Compute $k = H([a]Q)$.  Compute $m = E_k^{-1}(c)$, or drop it on the floor if authentication fails.

This structure is sometimes called ECIES, or sealed box.  It works because $$H([a]Q) = H([a][b]G) = H([b][a]G) = H([b]P),$$ so the sender and receiver are guaranteed to use the same key $k$.  The size of the message is limited only by the authenticated cipher $E_k$, and most authenticated ciphers have very large limits on message size, measured either in gigabytes or so big I don't even remember the word for it (what's more than a zettabyte?).

The field size $p$ and the group order $\ell$ are related by Hasse's theorem—they can't differ by more than approximately $\sqrt p$, so they are of the same order of magnitude.  The security offered by the curve is at most about $\log_2 \sqrt \ell$ bits, e.g. for Curve25519 you get at most the gold standard ~128-bit security, because a generic attack costs approximately $\sqrt \ell$ curve operations.  Of course, if you use AES-128, you won't get 128-bit security because it is much cheaper to attack multiple AES targets than to attack multiple Curve25519 targets.

The ciphertext expansion is only the constant overhead of the encoding of a curve point, and whatever ciphertext expansion $E_k$ has (typically a 128-bit authentication tag).

Some people call it ‘hybrid encryption’ when you combine a public-key operation like this with a symmetric-key cipher.  This is a poor choice of terminology, because it suggests that the public-key operation without the symmetric-key is itself a form of public-key encryption.  That is not the case here, or in any scheme similarly based on ephemeral/static key agreement, and that is generally a poor design with bad security and usage limitations even when it can technically be done with RSA.

The only way RSA is used in practice for encryption has the same separation, whether with RSA-KEM or with essentially any use of RSAES-PKCS1-v1_5 or RSAES-OAEP: encapsulate a uniform random symmetric key $k$ in an $e^{\mathit{th}}$ root modulo $n$, and encrypt the message with $E_k$.  Unlike attempting to shoehorn the message $m$ into $m^e \bmod n$, this has no limits on the message size or on the structure or distribution of messages that can be concealed.


Can a CCA-secure cryptosystem be used as a CMA-secure MAC? Can every CCA-secure cryptosystem be used as a CMA-secure MAC?
I know that every CCA-secure system is CPA-secure, but I'm not sure about CMA. From what I understand: for a system to be CCA-secure, it must be both CPA and CMA-secure. So I feel if it is known that the system is CCA-secure then it might be used as a CMA-secure MAC, but not too sure and any insight on this would be appreciated. Thanks!

Let $(\mathsf{KGen},\mathsf{Enc},\mathsf{Dec})$ be a CCA secure encryption scheme. I'm assuming you're asking about the following construction of a MAC $(\mathsf{KGen'},\mathsf{Mac},\mathsf{Vfy})$:
$$\mathsf{KGen'}(1^n) := \mathsf{KGen}(1^n) \qquad \mathsf{Mac}(k,m) := \mathsf{Enc}(k,m) \qquad \mathsf{Vfy}(k,m,\tau) := (\mathsf{Dec}(k,\tau) \stackrel{?}{=} m)$$
If that is what you're asking about, then no. This construction is generally not even unforgeable under a no-message attack. Let $m^*$ be some arbitrary fixed message from the encryption scheme's message space. We can construct a new encryption scheme $(\overline{\mathsf{KGen}},\overline{\mathsf{Enc}},\overline{\mathsf{Dec}})$ as
$$\overline{\mathsf{KGen}}(1^n) := \mathsf{KGen}(1^n) \quad \overline{\mathsf{Enc}}(k,m) := 1\|\mathsf{Enc}(k,m) \quad \overline{\mathsf{Dec}}(k,b\|c) := \begin{cases}\mathsf{Dec}(k,c) & \text{if } b=0\\ m^* & \text{otherwise}\end{cases}$$
It is easy to show that this scheme is also CCA secure, but I will leave this as an exercise to the reader. It is however trivial to forge the above MAC when instantiated with this scheme. Just output $m^*,0^{\ell(n)+1}$, where $\ell(n)$ is the length of a ciphertext under $\mathsf{Enc}$.


Customizable Crypto Algorithms in Hardware Several companies offer customized cryptographic algorithms, for example Crypto AG (www.crypto.ch/en/company):

  The individually created customer algorithms are unknown to anyone
  else and are not used by anyone else. A cryptographic attack is not
  possible, even from an identical unit.

Only the customers know the algorithms:

  Autonomous profiling of algorithms: you are the only one who knows the
  algorithm. Not even Crypto AG has access to it. Moreover, you can use
  a second additional algorithm when collaborating with other
  organisations.

These algorithms are hardware-based:

  Hardware-based encryption is the foundation for maximum cryptographic
  diversity – for speed reasons on the one hand and for its immunity to
  tampering on the other (no readout of data). This approach also
  ensures that the encryption processes remain cryptographically
  separated from the network. No common operating system is needed
  (viral resistance).

Thales offers something similar and calls it Programmable Cryptography
(www.thales-esecurity.com/solutions/by-technology-focus/programmable-cryptography)

A company called Mils offers customized algorithms as well
(www.mils.com/en/technology/customized-algorithms/)

How does this work?
How can they offer a cryptographic algorithm that can be customized by non-specialist customers without support and not run the risk of creating an insecure algorithm? (Ignoring the assumption that this might be the goal)

Note that Crypto AG states that the algorithms runs on hardware. Depending on what they mean by hardware (I understand it as a non-programmable logic circuit with fixed gate connectivity), this severely narrows the available algorithms.

Your doubts are absolutely valid. Disguising the algorithm is not a valid argument for security. It also contradicts to Kerckhoffs Law.

  It (the algorithm) should not require secrecy, and it should not be a problem if it falls into enemy hands;

Designing cryptographic algorithms (ciphers, hashfunctions, ...) is a long and complicated process. In academia such algorithms are proposed and are analyzed afterwards by other researchers for a long time trying to break them. For AES, it took about two years from publishing to standardization.

If you take a look at linear or differential cryptanalysis, you will notice that innocent looking S-boxes for example can be highly biased reducing the cipher's security drastically. Same applies to other parts of the cipher.

This contradicts highly to the promised security. I would not trust these algorithms at all, nor a machine designing them.

For the hardware part. They could use some sort of FPGA-based HW. This would allow the company to implement the different algorithms on the same boards easily. Speed is a valid point. However, I doubt that their generated algorithms are side-channel proof, which means one could get information about the algorithm itself or the payload that gets en-/decrypted by measuring power, timing or EM for example. If so, the point of "unkown algorithm" would be broken.

TL;DR

Hiding the algorithm is not a good idea.
Refrain from inventing your own crypto.
Do not trust companies that break both :P

Hope this helps


Is it secure to use the hash of key as the IV in AES encryption? I need to store some sensitive data for a program. For each copy of the program, there will be a unique key for encrypting one (and only one) file using AES encryption (OFB). The key will not be changed (probably forever).

Is it secure if the hash value of the key is used as the IV?

Update:
The key is computer generated.
The user of the program have no access to the key since it's obtained by the program via secure Web API.
The user can only edit a portion of data stored in the file via the program.

No, it is not secure.

From NIST 800-38:

The OFB mode requires a unique IV for every message that is ever encrypted
under the given key. If, contrary to this requirement, the same IV is used
for the encryption of more than one message, then the confidentiality of
those messages may be compromised

Given your description, you are apparently safe, because at any one time you have one file only.

However:

A malicious user may store away an earlier version of the file and do a comparison after a change and learn which bits flipped in the first block where that happened.
In the future, you may add a second file and not remember the rule above.

A unique (not necessarily truly random) IV per message is still recommended.


ECDH Man-in-the-middle active attack We have Alice and Bob. The man in the middle can manipulate(remove, add something etc.) A sent from Alice and B sent from Bob, how can he figure out what the common key K(A,B) is, without knowing kpr(a) and kpr(b)? Everything is based on Elliptic Curves.

Diffie-Hellman (and variants such as ECDH) protect against passive eavesdroppers, but not (at least by themselves) against active man-in-the-middle attacks. An active MITM can substitute his own keys for Alice and Bob's keys during the initial exchange, something like this:

Alice -> Bob (intercepted by Mallory): Hi Bob, I'm Alice and here's my public key: [Alice's public key]

Mallory -> Bob: Hi Bob, I'm Alice and here's my public key: [Mallory's public key]

Bob -> Alice (intercepted by Mallory): Pleased to meet you Alice, I'm Bob and here's my public key: [Bob's public key]

Mallory -> Alice: Pleased to meet you Alice, I'm Bob and here's my public key: [Mallory's public key]

Alice then computes a shared key based on her private key and "Bob" (actually Mallory)'s public key, and uses that to encrypt data to/from "Bob" (actually Mallory). Similarly, Bob computes a shared key he thinks is shared with Alice, but is actually shared with Mallory. Mallory uses the two public keys and his own private keys to compute both shared keys, and uses them to decrypt and reencrypt the messages passing between Alice and Bob.

This is why it's important to couple DH key exchange with some sort of authentication. For instance, in TLS's ephemeral DH and ECDH modes, the server signs its DH parameters (including its DH public key) to insure that they haven't been tampered with.


How to plot the distribution of a ciphertext? Is there any plot or visualizing program  that can plot the distribution of a plaintext and then the distribution of the ciphertext after applying a ciphering encryption algorithm? I am interested from stream ciphers

What you are looking for is a histogram plot.

For example, the distribution of letters in the english language looks like this:

The plot of a ciphertext from a strong cipher should have all bars about the same height (a fairly uniform distribution).


How can I study the math behind cryptography? I am a junior in high school and I am currently studying algebra 2. Where can I go to learn about the mathematics behind cryptography? I have a very basic knowledge of cryptography, but I am really interested in things like, why is a 2^256 bit cipher so secure? I would really like to learn about things like that so I can learn to make my own and analyze other ciphers.

Are there any good books or websites where I could learn about cryptography from a mathematical perspective?

Speaking from my own experience, Nigel Smart's book Cryptography: An introduction is a good place to start. I would say that you can read and understand it without any prior knowledge of cryptography at all. It is also free.


Niederreiter cryptosystem I can't understand how Niederreiter cryptosystem
works. If $c=mH^{'T}$ than why we cannot compute $m$ directly by multiplying $c$ with the $(H^{'T})^{-1}$? Can you give me an example of a "fast decoding algorithm"?

Thank you!

In the Niederreiter system, the plaintext is mapped to some error vector of weight $t$, where the code correction capability is $d=2t+1.$

With the trapdoor information (permutation) this can be decoded by the legitimate receiver by syndrome decoding.

Without the trapdoor information, this is equivalent to decoding a random vector, which is hard, as in the McEliece cryptosystem.


Is it possible to use structures other than finite fields? I have some difficulties to understand why we are using finite fields in cryptography.

Why do we use field? Why not ring or group? Is that really necessary that the field is finite? Why not real field?

One does not always use finite fields in cryptography. RSA for instance is based on
residue class rings, discrete logartihm based cryptosystems work on suitable
additive/multiplicative groups but these are also finite rings/groups.

Why one uses finite algebraic structures and not the field of the
reals?

Elements of the field of the reals do not necessarily have a
finite representation and thus cannot be represented on computers
precisely (only approximations as floating point numbers of a certain precision). Consequently, field operations may only yield approximations of the resulting element. Working with such fields would introduce errors in the arithmetic operations, which we do not want in cryptography. Using finite fields allow to represent all elements precisely and also the output of any arithmetic operation in the field.
Furthermore, finite structures used in
cryptography provide us with hard problems useful for constructing cryptographic protocols, such
as the hardness of the discrete logarithm problem over suitable finite fields. Logarithms over the reals in contrast are easy to compute.


Prove that the $x^8+x^4+x^3+x+1$ is irreducible over $\mathbb{Z}_2[x]$ I am new to this field. I am doing some cryptography course and have encountered $\text{GF}(2^8)$ in the famous AES algorithm. Although I do not have a strong relevant math background with this stuff(ring/field), I am really interested in it. My textbook has a question which says to prove that:

$$x^8+x^4+x^3+x+1$$ is irreducible over $\mathbb{Z}_2[x]$.
I am stuck at this point where I don't have much intuition about proving irreducibility over the whole $\mathbb{Z}_2[x]$.
Any help will be much appreciated!

Definition: A non-constant polynomial is said to be irreducible if it is cannot be factored into a product of two non-constant polynomials. In other words; if $p(x) = q(x)t(x)$ and it is irreducible then either $q(x)$ or $t(x)$ is a constant polynomial.
One way to prove that is $p(x) = x^8+x^4+x^3+x+1$ is irreducible over $\operatorname{GF}(2)[x]$ is checking the divisibility by the lower degree irreducible polynomials. First degree 1, then degree 2, then degree 3, and degree 4 will be enough to determine since a degree 8 can be factored into two polynomials with possible degrees as $1\cdot 7,2\cdot 6, 3\cdot 5$, and $4 \cdot 4$.
Below all the arithmetic is performed on $\operatorname{GF}(2)[x]$

degree polynomials are $x$ and $x+1$. We can check the divisibility by setting $p(0) \stackrel{?}{=} 0$ or $p(1) \stackrel{?}{=} 0$. $p(0) = 1 \neq 0$ and also $p(1) = 1 \neq 0$. Therefore degree one polynomials doesn't divide $p(x)$. This is by the factor theorem and here a nice proof in Math.SE.

degree polynomials, where we have four polynomials;

\begin{align}
 & x^2+x+1\\
 & x^2+x \\
 & x^2+1\\
 & x^2\\
 \end{align}
Let see why $x^2+1$ is not irreducible;
\begin{align}
(x+1)\,(x+1)&=x\,(x+1)+1\,(x+1)&&\text{by distributivity}\\
  &=x^2+1\,x+1\,x+1&&\text{.}\\
  &=x^2+(1+1)\,x+1&&\text{.}\\
  &=x^2+(0)\,x+1&&\text{since the coefficients are in }\operatorname{GF}(2)\\&=x^2+1
\end{align}
with a quick check that only $x^2+x+1$ is irreducible. To see that $p(x)$ is not divisible by $x^2+x+1$ perform division and look for the remainder. One can use this Sage script
R = PolynomialRing(GF(2),'x')
x = R.gen()
p = x^8+x^4+x^3+x+1
q = x^2 + x + 1
p.quo_rem(q)

the output is $(quo = x^6 + x^5 + x^3, rem = x + 1)$, . i.e cannot divide.

degree irreducible polynomials

\begin{align}
 & x^3 + x + 1 \\
 & x^3 + x^2 + 1
 \end{align}

degree irreducible polynomials

\begin{align}
 & x^4 + x + 1 \\
 & x^4 + x^3 + 1\\
 & x^4 + x^3 + x^2 + x + 1
 \end{align}
These polynomials are generated with SageMath
degree=4
R = GF(2)['x']
for p in R.polynomials(degree):
     if p.is_irreducible():
         print(p)

To test all the division use the below
R = PolynomialRing(GF(2),'x')
x = R.gen()
p = x^8+x^4+x^3+x+1
lst = [ x^2 + x + 1,  x^3 + x + 1,  x^3 + x^2 + 1,  x^4 + x + 1 , x^4 + x^3 + 1, x^4 + x^3 + x^2 + x + 1]

for t in lst:
    print(p.quo_rem(t))

The output is
(x^6 + x^5 + x^3, x + 1)
(x^5 + x^3 + x^2 + 1, x^2)
(x^5 + x^4 + x^3, x + 1)
(x^4 + x, x^3 + x^2 + 1)
(x^4 + x^3 + x^2 + x + 1, x^3 + x^2)
(x^4 + x^3 + 1, x^3 + x^2)

Therefore $p(x) = x^8+x^4+x^3+x+1$ is irreducible over $\operatorname{GF}(2)[x]$

Note 1: low degree irreducible binary polynomials are important in Cryptography since they reduce the required arithmetic. Gadiel Seroussi, in 1998, made a huge list in Table of Low-Weight Binary Irreducible Polynomials. The list contains binary irreducible polynomials up to 10000 degrees.
Note 2:  A014580 from
The On-Line Encyclopedia of Integer Sequences contains a list of binary polynomials, encoded in binary, or evaluated when $x=2$. The $p(2)$ is 283.
2, 3, 7, 11, 13, 19, 25, 31, 37, 41, 47, 55, 59, 61, 67, 73, 87, 91, 97, 103, 109, 115, 117, 131, 137, 143, 145, 157, 167, 171, 185, 191, 193, 203, 211, 213, 229, 239, 241, 247, 253, 283, 285, 299, 301, 313, 319, 333, 351, 355, 357, 361, 369, 375,...
The bolds irreducibles are listed in this answer.
Note 3:  A001037 keeps the number of degree-n irreducible polynomials over $\operatorname{GF}(2)$. There are 18 in degree 8 and $p(x)$ among the lowest possible weight.
degree 1  2  3  4  5  6  7   8
count  1, 2, 1, 2, 3, 6, 9, 18

and this can be counted by $$L_q(n) = \frac{1}{2} \sum_{d|n} \mu (\frac{n}{d})q^d$$


Property that prevents determining key from ciphertext and plaintext What is the property (if it is not Forward Secrecy) that prevents (good) symmetrical encryption algorithms from being vulnerable to an attack vector that requires only decrypted data, and the corresponding encrypted data, and allows the attacker to either:

Obtain the encryption key OR
Obtain some data that is useful to determine some information about the plaintext of a future intercepted ciphertext.

This is a follow-up question to Tom Leek's answer saying that the property mentioned is not Forward Secrecy, that asks, "Then what is it?"

Note that this is not about hashes, or asymmetric encryption (or any other session-token-based method), as those questions can be found at the corresponding links.

(Note, this question was moved from security.SE, which is why most of the links above lead there)

As mentioned in the comments, it appears that you are seeking to understand what provides a cipher with resistance to known plaintext attack. "Diffusion" and "Confusion" I think are the answer here.

Diffusion

"Diffusion" means that the terms/bits of the algebraic expression of the cipher are inter-dependent. Without diffusion, different subsections of the state will act independently, and so can be attacked independently. With diffusion, different subsections of the state will be dependent on the values of other subsections of the state. More diffusion leads to a greater number of terms in the expressions that represent the cipher.

Confusion

"Confusion" means that the algebraic expressions of the cipher are non-linear, which makes them difficult to work with. Non-linearity increases the degree of the ciphers equations. Ideally, the non-linear expressions are not even approximately similar to any linear expressions.

A linear cipher can often times be easily broken with negligible time/space complexity, regardless of how many rounds or how much key material is applied. The linearity means that we can view the ciphertext as a simple equation of key + message bits, which can be easily solved if you know the message bits.


How to calculate time taken by encryption? First of all, I know that this all it's very complicated, I know that CPUs are complex beasts, and may not work at their full potential all the time, they can have more than one core, and the calculations may very well be reordered, optimized, or vectorized, there are different cryptographic libraries, etc.

However, I need a simple, straightforward formula, very approximate formula for calculating the time taken by the encryption algorithm on a specific CPU. For simplicity, let's consider 2 situations:

CPU has 1 core, and 2.8GHz, algorithm is AES-128-CBC, data size
to encrypt is 1024 MB
CPU has 4 cores, operations are ordered
hypothetically as they "should be", algorithm is AES-128-CBC, data
size to encrypt is 1024 MB

I know that 1Hz means 1 second, and a CPU that has 2.8GHz performs about 2.8 billion operations per second (which means 2.8 billions cycles per second). I also know that:

$$ \text{cycles per byte (CpB)} = \frac{\text{cycles per second (CpS)}}{\text{speed (S)}} = \frac{2.8GHz}{\text{speed (S)}}$$

and, of course:

$$ \text{time (T)} = \frac{\text{data size (DS)}}{\text{speed (S)}} = \frac{1024 MB}{\text{speed (S)}}$$.

But I don't have the speed (bytes per second), and also, even if I had one, how to calculate time needed by encryption? I mean, I only have data size (DS) and cycles per second (CpS), but it seems I still need bytes per second (BpS) or cycles per byte (CpB), and of course, time (T).

I know that the best way is to do the actual measurement, but I need to make some assumptions about the hardware I don't have, and I need some encryption time for those devices (approximate time of course).

How can it be calculated? Are the information I have enough? What else do I need to calculate the time needed by AES-128-CBC to encrypt 1024 MB of data on 2.8GHz CPU?

The speed depends a lot  on the exact model of the processor, and on the software. New(-ish) processors with hardware support for AES are much faster than older processors without it (AES-NI in x86 processors) and an optimized implementation might be quite different from a generic one, especially if the latter doesn't even use the hardware support...

For older processors (without hardware support), some speed tests can be found here. The best numbers for Core 2 family processors were around 12 clock cycles per byte for CTR mode, which would make for about 230 MB/s at 2.8 GHz. For newer processors with AES-NI support, some numbers here, ranging from 600 MB/s to 1500 MB/s per core for CBC mode and 700 MB/s to 2600 MB/s for GCM mode with processors from 2010 to 2015 (with various clock speeds).

(A quick and dirty test with the OpenSSL command line tool on a low-end Xeon processor from around 2012 gave figures in the same ballpark as in the previous link.)

Note that if you care about speed, it seems you shouldn't be using CBC mode. For many processors on the list (as well as the one I tested on), AES-128-GCM is quite a bit faster than AES-128-CBC. And that's without any authentication in addition to CBC encryption. I assume the reason is that CBC encryption is inherently linear: encrypting a block requires the ciphertext of the previous block. This will limit the number of parallel operations the processor can do. For the same reason, multiple cores will not help in encrypting a single, long, chain. The authentication part of GCM encryption is also fast, because there's special hardware support for that, too. (the CLMUL instructions)


Showing the pairwise XORed random variables are independent If $X_i$'s are $3$ independent random variables defined over $\{0,1\}$ with biases $\epsilon_i$'s for $1\le i \le 3 \;$  and $\epsilon_1 = \epsilon_3 = 0.$ Then $X_1 \oplus X_2$ and $X_2 \oplus X_3$ are independent.

What I have done is, since $\epsilon_1 = \epsilon_3 =,$ hence $\Pr[X_1 = 0] = \frac{1}{2} = \Pr[X_3 =0].\\\\$ Also since $X_i$'s are independent, hence $X_1\oplus X_2, \;X_2 \oplus X_3$ and $X_3 \oplus X_1$ are uniform over $\{0,1\}.$
Now, $\Pr[X_1\oplus X_2 = b \mid X_2 \oplus X_3 = b] = \dfrac{\Pr[X_1\oplus X_2 = b, X_2 \oplus X_3 = b]}{\Pr[X_2 \oplus X_3 = b]}, b\in \{0,1\}.$
$X_1\oplus X_2 = b, X_2 \oplus X_3 = b \implies X_1 \oplus X_3 = 0$ and $\Pr[X_1 \oplus X_3 = 0] = \frac{1}{2},$
We know $\Pr[X_2 \oplus X_3 = b] =\frac{1}{2}.$ Hence $\Pr[X_1\oplus X_2 = b \mid X_2 \oplus X_3 = b] = 1.$
But $\Pr[X_1 \oplus X_2 = b] = \frac{1}{2}.$ Since $\Pr[X_1 \oplus X_2 = b] \neq \Pr[X_1\oplus X_2 = b \mid X_2 \oplus X_3 = b]$ so they are not independent.
What am I missing ? This is a question from Douglas R. Stinson's book "Cryptography-Theory and Practise" with question number $4.12$, page $134.$
Can anyone help me through this. Thank you.

If two binary RVs are uniform, they are independent if and only if the probability that they are equal is the same as the probability that they are unequal (so knowing one does not help in guessing the other).
$$
P[X_1 \oplus X_2=X_2\oplus X_3]=P[X_1=X_3] =P[X_1\oplus X_3=0]
$$
which is clearly $1/2$ since $X_1,X_3$ are unbiased and independent.


How is LUKS dm-crypt secure if the key is stored with the encrypted data? I've posted this question over at superuser, but haven't had any success at getting answers. That's why I've posted it here. Furthermore, I believe this is a more appropriate place for it as it is questions about design of the encryption system and not about its usage.

How is LUKS dm-crypt secure if the key is stored with the encrypted data? To me, this seems like hanging a door key on the door it locks. Is a passphrase enough to secure it?

And a continuation: If it is secure to keep the key with the encrypted partition/container, am I correct in assuming that LUKS header backups can also be treated as normal files and not secret data?

The key is not stored with the encrypted data, the encrypted key is. This is part of the header. In short, when the volume is created a random key (the master key) is generated and this random key is encrypted using a key derived from the passphrase, and spread out (using an algorithm called 'afsplit'). This key derivation is designed to take a relatively long time (half a second or so), so it's relatively expensive to try passphrases as an attacker.
By design the system's security depends on the passphrase's quality; a bad passphrase is somewhat protected due to the long time per try, but would fail in the end. The header also contains an independent check to see that the passphrase that was entered has resulted in the correct master key.

The header is not secret but essential to open the volume: it contains all the parameters that have been used when the volume was created, so that (with a correct passphrase) the master key can be recomputed from the header (and this key is used to decrypt the actual file system data). So it's always stored with the data. It is recommended to backup the header (to a separate system, say a USB drive), but this is just to prevent data loss when the header would get corrupted (if a bit is changed, you cannot recompute the correct master key any more).


Is it possible to break SHA-512? Is it possible to break the SHA-512 hash algorithm?

Are there any successful attacks out there?

Is it possible to break the SHA-512 hash algorithm?

We don't know. That is: it is impossible to prove that there aren't any attacks possible on SHA-512. But that doesn't mean that it can or cannot be broken.

  Are there any successful attacks out there?

No, except length extension attacks, which are possible on any unaltered or extended Merkle-Damgard hash construction (SHA-1, MD5 and many others, but not SHA-3 / Keccak). If that's a problem depends on how the hash is used. In general cryptographic hashes are not considered broken just because they suffer from length extension attacks.

The SHA-3 competition was created to replace SHA-2 in case it would be broken in the same way as it's predecessor, SHA-1. However during the competition it became clear that SHA-2 in itself looks pretty secure.


RSA: unknown public exponents Suppose I intercept the same message m sent to 2 friends. I know what the message is and I know the used modulus n, as well as the ciphertexts but I don't know the respective public exponents. I.e. my system of equations is:

$c_1 = m^{e_1} \ mod \ n$
$c_2 = m^{e_2} \ mod \ n$

Is there a way to retrieve the public exponents, without using bruteforce?

A practical example:

$n = 221$
$m = 127$
$c_1 = 155$
$c_2 = 43$

Hint: seen as a discrete logarithm problem, there's an attack of cost $O(\sqrt{\min(e_1,e_2)})$.

I see no improvement on the asymptotic cost without factoring $n$.

Update: I think it is rigorously provable that if one could solve this problem in polynomial time with sizable probability for proper choice of $n$ and random other parameters, then we could factor $n$. Proof is left as an exercise to the reader by the usual method: invoke the hypothetical algorithm solving the problem in a polynomial-time algorithm that factors $n$.


Does encrypting data multiple times using different passwords increase security? Does encrypting plain-text data multiple times using different passwords provide a greater level of security?

If so, what encryption algorithm would be best for such a use? Would it be beneficial to use different algorithms for each iteration?

I also had an idea to use 1 algorithm if the password starts with A-N and another if the password starts with O-Z. Is something like this beneficial?

There is a terminology gap in your question. Lets assume that you want to encrypt message $m$, and for that purpose you'll be using the encryption function $E$ such that the encrypted message will be $E(m)$. Now you ask whether your message will be more secure if you encrypt it for example as $E(E(E(m)))$. Well if this encryption is stronger than $E(m)$, then you might as well have selected in advance the algorithm $E'$ such that $E'(m)=E(E(E(m)))$. Does $E'(m)$ mean that you encrypt something 3 times? Well according to the custom terminology the answer is no, $E'(m)$ is a single iteration of the algorithm $E'$ which happens to consist of three iterations of $E$. If those three iterations were not to yield the optimal result then no one would bother to invent such algorithm $E'$. You may argue that the number of iterations represents some cost/performance tradeoff, but in this case the algorithm $E'$ would have been defined as $E'(m,n)=E^n(m)$ where $n$ is the number of iterations to employ (you'll find a similar concept in KDFs such as bscypt, scrypt, Argon2, etc. EDIT: But then a KDF is of course a one-way transformation as @tylo mentioned below, where multiple iterations do make sense). So the bottom line is that there is no such thing as "encrypting something multiple times", you'll always be just encrypting something, and this encryption may employ under the hood multiple iterations of one or more steps in the encrypting process.

Now to the point of your question, if you have multiple passwords then the strongest security you'll get is by concatenating these passwords together, pass them through a KDF, and use the resulting key for encryption. Your entropy for the entire process is the same, but if the encryption process is broken into iterations each one using only part of the entropy gives the attacker the luxury of keeping interim results and thus speeding up the cracking. So encrypting with a single iteration using a single password yields stronger encryption then multiple encryption iterations with multiple passwords which sum up to the same entropy as the password in the first option.

Concerning your idea of using different algorithms depending on password, well in that case you may leak information about your password if the attacker can guess the algorithm. So, you'll get better security by using an algorithm which is independent of message content or password.


Applicability of physical unclonable functions for public-key cryptography Can physical unclonable functions (PUFs) be used to protect secrets against physical tampering in the context of public-key cryptography?

Some solutions (i.e. ChipDNA or QuiddiKey) apparently use PUFs to protect their private key that are used to perform ECDSA. Some MIT slides about Physical Unclonable Functions and Applications mention private/public keys, implying that this is possible.

From my basic understanding of PUFs, a database of challenge-response pairs is created during manufacturing and we can authenticate a chip when it provides the correct response(s) to challenge(s) as long as challenges are not reused. How is the PUF "fingerprint" derived to a secret key?

Caveat: my understanding of Physically Unclonable Functions is partial, and my limited exposure to would-be PUF systems is old. I offer a tentative current opinion, hopping there will be constructive contradiction, and that I'll learn something new.

I know no practical system (or credible blueprint for such) where possession of a PUF can be assimilated to possession of a private key (the way we can with a Smart Card holding a private key, as long as it does resist attempts to extract the private key, as designed).

It is known how to achieve that after enrolling of a PUF with some PUF reading device (hereafter reader):

The reader+PUF can perfom a private-key operation.
When the PUF is separated from the reader, the private key can't be extracted from the reader (even if the reader is not tamper-proof), and the reader can no longer perform private-key operation.
The PUF itself can't be cloned in such a way that the unmodified reader will accept the cloned PUF (and perfom private-key operation).

However:

Moving the PUF to a new reader can only move the private key associated with the PUF to that new reader if some associated enrollment data is also moved to that new reader (e.g. thru an online connection, or with some traditional data storage moved along the PUF).
An attacker with the PUF, and said enrollment data, and the reader's full design (or the reader itself if not tamper-proof) can find the private key, then perform private-key operations without the PUF or/and simulate reader+PUF.

Some realizations (existing at least at the prototype stage) integrate the PUF, the reader, and perhaps enrollment data on the same piece of silicon. This does prevent attempts to make exact silicon-level copies, but won't resist extraction of the private key or more educated attacks.

Note: all the above holds if we replace private key by secret key.