Computing only one byte of a cryptographically secure hash function Let $H$ be a cryptographically secure hash function, like SHA256. The output of $H$ is $N$ bytes long, with $N$ usually in the order of $32$ for commonly used hash functions.

Now, be $X$ a string, I can compute $Y = H(X)$, which is a sequence $Y_0, \ldots, Y_{N-1}$ of bytes. Now, I was wondering: is there any way to have some $H^{(i)}$ so that $\forall X,\; H^{(i)}(X) = H(X)_i$ (i.e., a function that extracts the $i$-th byte of $H(X)$) but so that computing $H^{(i)}$ is faster than computing $H$, then extracting the $i$-th byte?

In other words, if I want to just compute one byte of $H$, can I avoid carrying out some computations and save some CPU?

(I hope not. If not, is there a proof for this?)

For SHA-256, given its structure, the savings achievable when computing a single byte of the output is small. Argument: the computation consists of 64 rounds in cascade (or several times that for input of at least 56 bytes); full diffusion is achieved after 8 rounds, therefore all but the last 7 rounds must be computed in full (and then a large fraction of the rest, varying with which byte is kept), therefore savings are (much) less than 7/64 on the rounds, and a little extra operation on the output (worth less than 8 32-bit additions). Thanks to tylo for reporting that diffusion is much slower than I stated.

This is largely true for all common hash functions, but we can not generalize to any hash function. It is easy to construct a hash function of cost about proportional to the width needed (but somewhat inefficient, or insecure).


The exact difference between a permutation and a substitution I've noticed confusing definitions about permutation and substitution, preventing me from understanding the difference.

A permutation changes the order of distinct elements of a set, but this can be written as a function changing one element by another, exactly as a substitution.

So, how exactly can we distinguish between these two notions?

This question is interesting since we have these two notions in block ciphers, in which S-boxes perform substitution. The problem is that this table is used to replace one element by another, exactly like a permutation.

As noted in this answer and this answer to another question, permutation is just a mathematical term for a function $\sigma:X{\rightarrow}X$ that maps a finite set $X$ onto itself, in such way that for each $y \in X$ there exists exactly one $x \in X$ such that $\sigma(x) = y$. This is also equivalent to how the term substitution is used in cryptography, so your question is indeed justified.

For instance, the term Pseudo Random Permutation denotes a function that might also have been described as a Pseudo Random Substitution (but never is).

As D.W. pointed out in a comment below, the terms P-boxes (permutation boxes) and S-boxes (substitution boxes) have a specific meaning in block cipher design. Suppose you have a P-box and a S-box that both map a bit-string of length $n$ to another bit-string of length $n$. In such case the P-box can be expressed as a function $\sigma:[0..n-1]\rightarrow[0..n-1]$ that maps one index in the bit string to another, while the S-box, simply put, does more. This means that there are only $n! = \Pi_{i=1}^ni$ different P-boxes that map one bit string of length $n$ to another, while there are $2^n!-n!$ different S-boxes that map any bit string of length $n$ to another, without being a P-box and without mapping two different inputs to the same output.

Using the term Permutation in the specific meaning described in the above paragraph is unambiguous within the field of block cipher design. However, I would recommend using the term P-box, which, to the best of my knowledge, is never used in a meaning that differs from above.

Why? Well, for instance, a block cipher designer who hypothetically decides to incorporate e.g. the RC4 key schedule for setting up the S-boxes used in a block cipher, would be technically correct to refer to the operation that sets up those S-Box as a "permutation" (because one property of such a S-box might be best understood by looking at the setup in terms of permutation decomposition). The result would clearly not be a P-box, though.

Consequently, the best answer is probably that the distinction must be clear from definitions made in the context where the terms appear. When in doubt, avoid terms that might cause confusion.


Are there any hash functions that use integers of arbitrary bit size (e.g., int63)? More precisely, I am looking for hash functions where the internal state can be decomposed as a vector of integers of size 63. That is, machine integers where one of the bits is fixed and unusable.

It would be possible to modify some scheme to move use 63-bit words, but that would require cryptanalysis and new choices for constants. I am not aware of any hash families that would be parametric with regard to word size and allow such uneven values.

Instead I would recommend using any existing hash that internally uses 32-bit words and that does not use many shift or rotation instructions. Modular addition, as well as bitwise operations can be computed on 63-bit values while ignoring all but the 32 low bits.

RIPEMD-160 seems like a decent candidate if 80-bit collision resistance suffices, or perhaps RIPEMD-320 if it does not. Only something like one fifth of the arithmetic instructions are rotations. Even if you need 3-4 instructions to implement rotation, the rest of the function should still dominate runtime.

Note that in the case where the limitation is due to tagged integers losing one bit, it may still be possible to do full 32-bit arithmetic, including rotations, on your 63-bit values without extra performance loss. (Depending on the interpreter/compiler.)


Genuine encryption from only one source? Is there any technique so that if I encrypt data, the ciphertext would be genuine and if someone else tries to encrypt the same data the ciphertext could be determined as fake or just invalid?

I want to create a network in which the user has to register to get a ciphertext (like a token) and only after getting a genuine ciphertext would they be allowed to communicate with other users in the network. The ciphertext would contain their identity.

However, if I simply use any simple encryption method, the user would be able to fake their identity by encrypting the data in the same format and method. I do not want to use a server/database to verify the identity. That is why I was thinking of ways to disallow fake ciphertexts.

If this is possible can you suggest a solution to achieve this? If not can you suggest an alternative?

I think the solution to your problem is a digital signature as CodesInChaos pointed out. Here is how it would work:

When a user registers with your server they are given a token which will consist of (at a minimum) the user's id. The server also uses its private key to digitally sign the token (or more likely a hash of the token).

Now, say user1 and user2 have done this and now want to communicate. They each send their token and digital signature to the other user. They each take the token and signature that they received from the other user, and use the servers public key to verify that the signature was correct. If so they proceed to communicate.

There are some things you will want to think about before using this, however. You might want to kick people out of the network. That will require some additional work.


Determining the primitive root $g$ of $p$, given $B=g^b \pmod p$ This is related to Diffie-Hellman key exchange.

Suppose you're given a prime $p, b \in \{0,1,...,p-2\}$, and $B$, such that
$$
B= g^b \pmod p.
$$

Assuming that $$\gcd(b, p-1)=1$$ How could you determine the primitive root $g$?

If $\gcd(b,p-1)=1$ you have  $u\cdot b + y\cdot (p-1) = 1$ where $u=b^{-1} \bmod {(p-1)}$. With Euler's theorem $B^{p-1} \equiv 1\bmod p$ you get
$$g \equiv B^u \bmod p.$$

Right you are with your comment, I have included the changes. Euler's theorem is used at the penultimate step:
This is the 'easy case' on page 4 of the reference given by SEJPM
$$g^u \equiv (B^u)^b \equiv B^{ub} \equiv B^{1-y(p-1)}
\equiv B \cdot (B^{p-1})^{-y}\equiv B \cdot 1^{-y}\equiv B \bmod p$$
Example: $p=11, b=7, B=4$.  Compute:
$$u \equiv 7^{-1} \equiv  3 \bmod {10}$$
$$g \equiv 4^3  \equiv 9 \bmod {11}$$
and check:
$$9^7 \equiv 4 \bmod 11$$


SHA-1 – Why is it hard to find a certificate collision? Why is it it’s so much harder to execute a successful collision on certificates than it is on text data?

I assume this has to do with the fact the certificate actually is a file that contains signed (and therefore encrypted) data. However, why does this complicate things? Of course an attacker doesn’t possess the private key but why would this make a difference from a technical point of view?

I already read there’s several ways to find collisions. The goal is to find the path of the least resistance (in "reasonable" amounts of time). The only successful MD5 certificate collision I was able to find is a “chosen-prefix” collision. In this case they were also depending on the probability of some of the functions of the CA, like the serial number counter, the time between request, processing and issuing and the amount of certificates issued on average.

In this scenario it’s necessary to have a CA that (unknowingly) cooperates in the process (which isn’t a requirement with non-signed files. If this is the case, then we should be safe. Because:

No collision can be made after the certificate has been generated;
All CA’s only issue SHA-2 certificates;
(both are assumptions but in the ideal world scenario)

Does it actually work out like this?

Why is it it’s so much harder to execute a successful collision on certificates than it is on text data?

It's not.  Actually, the attacker does have to worry about the sequence number that the CA will use, however as we seen from the successful MD5 attacks, that's a solvable problem.

What's more difficult is coming up with a useful (to the attacker) collision.

If all we want is to generate two colliding certificates signed with SHA-1, we can take advantage of the fact that RSA certificates have some random-looking data in the middle (the "RSA public key"), and a nontrivial percent of random moduli are easy to factor (and hence is easy to find the corresponding private key).  So, all we'd need to do is a) guess the initial parts of the certificate (already solved problem), b) generate a collision in the initial parts of the RSA modulus, giving us two top portions and c) then search for a common lower section of the modulus where we can factor both.  Then, we can have the CA sign one (which requires us to have the private key, which w do), and then we can use the other (which also requires us to have that private key, which we do).  Bingo, we have a collision.

However, it's not a useful collision; all we've done is use one modulus with the CA, and another in practice; that doesn't allow the attacker to, well, attack anything.

What the attacker really wants is to have the CA sign one certificate for 'innocent1.com', and then have the certifcate for, say, 'microsoft.com' and hashes to the same value (and so they can use the same signature in that certificate).  To do that, the attacker needs to form two certificate prefixes (one with innocent1.com, and the other with microsoft.com), and form a collision where the two hash states join together to form a common one.

So, what the collision method needs to do is, instead of starting from a common state (and finding two distinct sets of blocks that both result in a common state), start with two predetermined hash states, and find a set of blocks that shepherd them into a common state.  We know how to do this with MD5; the current attacks on SHA-1 doesn't do this.

Now, it wouldn't be prudent to assume that the attacks on SHA-1 couldn't be extended to do that.

  No collision can be made after the certificate has been generated

True (even for MD5 certificates); however the base SHA-1 attack was published 10 years ago.  It's only now that someone has published that they actually performed the attack, however that doesn't mean that someone else didn't do it first.

  All CA’s only issue SHA-2 certificates

I've been told (thanks Ajedi32) that CA's only issue SHA-2 (or better) certificates now; however that doesn't address certificates in the field that haven't expired yet.  Yes, you can't attack them now; you could attack them a year ago...

Also:

  I assume this has to do with the fact the certificate actually is a file that contains signed (and therefore encrypted) data.

Actually, a certificate does not include any encrypted data (ASN.1 encoding doesn't quite count as encryption :-).  Because anyone is supposed to be able to parse a certificate, it can't include any encrypted (unintelligible without the key) data.


Why can you use shorter keys with elliptic curve Diffie Hellman key exchange? I am a layperson interested in how cryptography works. I would like to know why you can use shorter keys with elliptic curve Diffie-Hellman (ECDH) than with the discrete log DH key exchange. Both have to be large enough to withstand brute force attacks. So I assume there must be some attacks that you can use to try and crack the DLP that can't be used on ECDH and that would force you to chose a longer key for it to be safe. Thank you in advance for your help.

There must be some attacks that you can use to try and crack the DLP that can't be used on ECDH and that would force you to chose a longer key for it to be safe.

Indeed, there are algorithms applicable to DLP in groups that are a subgroup of $\Bbb Z_p^*$, but not to Elliptic Curve (sub)groups:

A variant of (G)NFS. See e.g. this article about solving a 768-bit DLP. That used to be the record before this December 2019 announcement about solving a 795-bit DLP.
Index calculus, which in not quite as efficient, but still much more efficient than generic algorithms like baby-step/giant-step and Pollard's rho, which can attack the DLP in any group.

This website specifically lists recommendations for key size. Depending on crystal ball hypothesis, 250-bit ECC (giving the equivalent of about 125-bit symmetric security against classical computers running distributed Pollard's rho) is conjectured to be about as safe as 2000 to 8800-bit DLP in $\Bbb Z_p^*$ (the discrepancy is mostly due to the lesser confidence about the implausibility of better algorithms in $\Bbb Z_p^*$).


Is it cryptographically insecure to use fixed-length AES-GCM messages? Is there any weaknesses to encrypting fixed-length messages? Should a random amount of padding be added to the message to decrease the odds of some sort of attack?

An adversary who obtains AES-GCM ciphertexts but does not know the key cannot obtain any information about the plaintexts except their lengths. This is (in a highly simplified form) the definition of the claim that AES-GCM is secure. This is true for any secure authenticated cipher.
If your plaintexts are intrinsically all the same size, this is an ideal situation, because the ciphertexts leak no information at all about the content of the plaintext.
If your plaintexts can have different sizes and the size of the plaintext leaks some information that you want to keep secret, then padding plaintexts so that they all have the same length is a possible solution. Beware that the generation of the message, the padding process, the unpadding process and the processing of the unpadded messages are likely to take time that depends on the length of the plaintext, so it may still leak through timing. Appending padding to the message may not be the best solution: depending on how the message is structured, it may be easier to construct a secure system if you arrange each part of the message to have a fixed size, and concatenate those fixed-size parts. That way the assembly and parsing of messages is less likely to reveal confidential information through side channels.
Adding a random amount of padding is unlikely to help security. In particular, if the same message is likely to be transmitted many times, an adversary can average out the lengths, which will negate the uncertainty of the random padding. However, it can help in some scenarios where you want to hide which message was transmitted for privacy (for example, to make it harder to figure out which file a user download on a server). Still, the only fully reliable way is to have fixed-size messages (in the download privacy example, this would mean padding all files to the length of the largest one).


Do people not care about side channel resistance? Recently, I have been browsing a lot through libraries that implementing Shamir secret sharing. I see a lot of code that implements this cryptographic algorithm without any side channel (timing/branch/cache) resistance or with casual mistakes. Where I come from, side channels in cryptographic code are a big no-no, and I instinctively stay away from using these kinds of libraries.

Although Shamir secret sharing is pretty obscure, people actually use these implementations. We know (thanks Ilmari Karonen)
 that side channels matter, so why do the main (most popular) libraries not protect against them? Are the developers sloppy or uneducated?

Edit: I removed the question whether side channels were relevant, because this question already has an answer.

Edit: Related question: Why do crypto libs use table lookups when they're vulnerable to timing attacks?

Some implementers take notice of side-channels. An excerpt which is most relevant to your question:

  Another important point is that when timing attacks apply, they are all-encompassing: if the context is such that secret information held in a system may leak through external timing measures, then everything the system does may be subject to such leaking. This is not limited to cryptographic algorithms. Research on timing attacks tends to focus on secret keys because keys are high-value targets (a key concentrates a lot of secrecy), and cryptographers talk mostly about cryptography; however, even if all cryptographic algorithms in your system are protected against timing attacks, you are not necessarily out of trouble in that respect.

In your specific scenario, you worry about an attacker who could run his own code on the same hardware as your system, at roughly the same time as you use Shamir's Secret Sharing to split or reassemble shares for your secret data. In that setup, you ignore most "physical" side channels such as power usage, electromagnetic emissions, or noise, since exploitation of these channels requires the attacker to be in the close vicinity of the target hardware. The attacker is supposed to be remote, which limits possible side channels to what can be measured remotely or from attacker's code running on the hardware, i.e. mostly timing. Therefore, I concentrate here on timing attacks, and their countermeasures, dubbed "constant-time crypto". Practical incarnations of that attack scenario would be a multi-user Unix server (attacker is another user with a shell account), or (since this is 2017 and not 1997 any more) a cloud farm that hosts VM, and runs your VM and the attacker's VM on distinct cores of the same physical CPU.

The quoted paragraph above explains that not everything is cryptography. Indeed, you reassemble your data shares in order to have the full data in that computer, presumably in order to do something with that data. If timing attacks apply to the reassembly of shares, they should also apply to whatever you are going to do with that data. Displaying, looking for words, computing values... all of these will leak timing-based information.

In other words, if timing attacks apply to your setup, you are mostly doomed. Some specific usages will be safe: for instance, if the reassembled file is then only sent "as is" to a remote host (through some SSL or similar channel). But, in general, if you are in a timing-attack setup, then you may as well give up; or, more proactively, try to arrange for attackers not being able to run their code on your hardware.

Note that there have been lab demonstrations of cache-timing attacks from external attackers, who do not run their code on the hardware, but exercise an existing service to perform (indirectly) the same cache-measuring actions. Whether such attacks are applicable "in the wild" is still an open question.

To sum up, it may make sense not to fret too much about side-channel leaks on big systems (embedded systems are quite a different story) because such leaks would be part of a much bigger issue that should be addressed holistically.

Of course, one may also point out that it is rather unavoidable that, in a world where everybody can write three lines of code and push it on GitHub, most of that stuff will be, indeed, sloppy.


Is ISAAC considered secure as a cryptographic random number generator? The ISAAC site claims it is secure, but I wasn't aware of any trusted 3rd party sources that verified its security.

I had a short look at the page - it contains only some implementations, no specification.

The page ISAAC and RC4 from the same author contains some theoretical elaboration about ISAAC and its relatives IA and IBAA, but I'm not sure if this can be called specification.

Non-existence of a formal specification is a major drawback for anything which claims to be a serious cryptographic algorithm, and might be the deciding reason that nobody really looked at the security of this primitive.

So my recommendation would be to use other, better documented algorithms instead, if security is of importance (and not only speed).


Can Whirlpool take advantage of AES-NI? Whirlpool uses a modified version of the AES / Rijndael algorithm.

Can Whirlpool take advantage of AES-NI instructions (or possibly other specialized constructs) on Intel and Intel compatible processors?

Or is the underlying AES algorithm modified too much for AES-NI to be compatible with the algorithm?

As an additional (optional) question: would it be feasible and secure to adjust Whirlpool to be able to use AES-NI if Whirlpool is not compatible?

It cannot. The AES-NI extensions add six new instructions used to accelerate AES. Whirlpool uses a Rijndael-based cipher as its round function. From a page on the hash, the cipher works as so:
The Whirlpool hash function

WHIRLPOOL uses Merkle-Damgård strengthening and the Miyaguchi-Preneel hashing scheme with a dedicated 512-bit block cipher called $W$. This consists of the following. The bit string to be hashed is padded with a '1'-bit, then with a sequence of '0'-bits, and finally with the original length (in the form of a 256-bit integer value), so that the length after padding is a multiple of 512 bits. The resulting message string is divided into a sequence of 512-bit blocks $m_1$, $m_2$, ... $m_t$ which is then used to generate a sequence of intermediate hash values $H_0$, $H_1$, $H_2$, ... $H_t$. By definition, $H_0$ is a string of 512 '0'-bits. To compute $H_i$, $W$ encrypts $m_i$ using $H_{i-1}$ as key, and XORs the resulting ciphertext with both $H_{i-1}$ and $m_i$. Finally, the WHIRLPOOL message digest is $H_t$.

This can be expressed mathematically where $\mu$ maps input to the matrix $M_{8 \times 8}[\operatorname{GF}(2^8)]$, $W$ is the 10-round, 512-bit Whirlpool block cipher, $IV$ is a string of 512 0-bits, $M$ is the full message with a length of $t$ blocks, $m_i$ is a 512-bit block from $M$ at position $i$, and $m_t$ contains up to 512-bits of Merkle-Damgård padding (a 1-bit, as many 0-bits as necessary to pad the block to an odd multiple of 256, and a 256-bit right-justified binary representation of the total length of $M$).
\begin{align}
\eta_i &= \mu(m_i)\\
H_0 &= \mu(IV)\\
H_i &= W_{H_{i-1}}(\eta_i) \oplus H_{i-1} \oplus \eta_i\\
\operatorname{Whirlpool}(M) &\equiv \mu^{−1}(H_t)
\end{align}
The $W$ cipher and the $\mu$ function are described in more detail in the Whirlpool paper.
The AES-NI extension
To see whether or not AES-NI can accelerate $W$, we have to look at the purposes of each instruction. Reading through the Intel whitepaper on AES-NI, the instructions do the following:

AESENC performs a single round of encryption using the provided round key. It performs the ShiftRows, SubBytes, and MixColumns steps on the data. The MixColumns step involves using the $\operatorname{GF}(2^8)$ polynomial $x^8 + x^4 + x^3 + x + 1$, whereas Whirlpool uses $x^8 + x^4 + x^3 + x^2 + 1$. In addition, SubBytes uses the AES S-box which Whirlpool does not use.* The different polynomial alone makes this instruction unusable for Whirlpool.

AESDEC is identical to the above, but uses the inverse steps (i.e. the steps InvShiftRows, InvSubBytes, and InvMixColumns). The Whirlpool block cipher does not involve decryption, making this instruction useless.

AESENCLAST is the same as AESENC, but it is intended for the final round of encryption. The primary difference is that it does not perform the MixColumns step. Unfortunately, it still performs SubBytes which uses the AES S-box, not the Whirlpool S-box.

AESDECLAST is identical to AESENCLAST, but runs the inverse transforms.

AESIMC passes the round keys through the InvMixColumns transformation to make them suitable for decryption. This still involves the incompatible polynomial, so it would not work even if Whirlpool could benefit from accelerated decryption.

AESKEYGENASSIST implements the AES key schedule. It takes the cipher key and generates the necessary round keys. Whirlpool does not use a dedicated key schedule. Each round function acts as the key schedule, creating the round keys for the next round.

Now, even if these instructions could be used for Whirlpool's block cipher, they only operate on 128-bit blocks (although apparently it is possible to do 256-bit blocks as well, according to section 2.1 of this paper). Whirlpool's block cipher uses 512-bit blocks. The instructions would not work.
In summary, the instructions for encrypting and decrypting rounds are completely incompatible with Whirlpool. The only other instruction performs the AES key schedule, which Whirlpool does not use. You may be able to modify Whirlpool to use the unmodified AES rounds, but then it would no longer be Whirlpool. If you do need a hardware-accelerated cryptographic hash however, you could use the new Intel SHA extensions. These are used to accelerate SHA-1 and SHA-256. Alternatively, you could use a dedicated hashing algorithm that is designed to be accelerated by AES-NI, as is shown in this paper.
* Just because a cipher uses a different S-box than AES does not automatically disqualify it from being accelerated by AES-NI's implementation of SubBytes, if the S-box is similar enough. This is the case for Camellia, for example.


Is tweakable block-cipher based on the Merkle-Damgård construction secure if $F$ is a PRP Assume $F$ is a pseudo-random permutation (PRP) then the tweakable block-cipher based on the Merkle-Damgård construction (take this as the way I understand, here is the equation):

$F_k[t](m) := F_{F_k(t)}(m)$

is a secure tweakable block cipher. This is marked with two stars in my notes.

First question: is it right or wrong?

Second question (if it is right): will a standard argument - that distinguishes the real world from the ideal world - work?

Minematsu studied this construction, and some generalizations thereof, in Section 5 of Beyond-Birthday-Bound Security Based on Tweakable Block Cipher. Minematsu, however, uses a PRF to derive keys instead of the block cipher.

The idea is simple: the tweakable SPRP security of this construction, for $q$ queries distributed arbitrarily over $t \le q$ different tweaks, is the security of $t$ instances of $F$, plus the distance from the key derivation to uniformly distributed keys.

The security of $t$ instances of $F$ is otherwise known as multi-key or multi-user security, and we can bound it as $t \cdot \mathbf{Adv}_{F}^{\text{sprp}}(\mathcal{D})$, i.e., at most $t$ times the security of any single instance.

So we have
$$
\mathbf{Adv}^{\widetilde{\text{sprp}}}_{F}(\mathcal{D}) \le \mathbf{Adv}^{\text{prf}}_F(\mathcal{D'}) + t \cdot \mathbf{Adv}^{\text{sprp}}_{F}(\mathcal{D''}) \,,
$$
for a distinguisher $\mathcal{D'}$ making $t$ queries and a distinguisher $\mathcal{D''}$ making at most $q$ queries. The first distance can be refined by the PRP-PRF switch, so we end up with
$$
\mathbf{Adv}^{\widetilde{\text{sprp}}}_{F}(\mathcal{D}) \le \frac{\binom{q}{2}}{2^n} + (t + 1) \cdot \mathbf{Adv}^{\text{sprp}}_{F}(\mathcal{D''}) \,.
$$

So this construction is secure until approximately $2^{n/2}$ blocks are queried and, assuming a perfect block cipher with $\mathbf{Adv}(\mathcal{D}) \le t/2^k$, around $2^k/t$ evaluations.

Imagine for example a concrete instance of AES-128 where an attacker queries $2^{64}$ different tweaks $x_i = \text{AES}_{\text{AES}_k(t_i)}(0)$ then tries $2^{64}$ keys $k_i$ until $\text{AES}_{k_j}(0) = x_i$. Each attempt has success probability $2^{64-128}$, since there are $2^{64}$ distinct keys. Then, $\text{AES}_{\text{AES}_k(t_i)}(1)$ must also be equal to $\text{AES}_{k_j}(1)$.


Proof that this is not a secure pseudorandom function? $p$ is a large prime number. Consider the following function $F:\mathbb Z^*_p \times \mathbb D\rightarrow\mathbb Z^*_p$ where $\mathbb D=2,....,p-1$.
$F_k(x)=x^k \bmod p$
Proof that it's not a secure pseudorandom function.

What I‘ve tried:
I give a value to $x_1$ and obtain $y_1$, then I set  $x_2 =y_1+p$. At the end $y_1$ is equal to $y_2$. Could this be right or is it  totally wrong?

Hint: multiplicative property.

What you have tried does not work because $y_1=y_2$ does not hold in general when $x_2=y_1+p$ (further, adding $p$ is identity in $Z_p$ ).

You want to build a distinguisher for $F_k$. Arguably, $F_k(1)=1$ is enough for that, but you can build a more general distinguisher from $F_k(x_1\cdot x_2\bmod p)=F_k(x_1)\cdot F_k(x_2)\bmod p$.


Are there two known strings which have the same MD5 hash value? Is there an example of two known strings which have the same MD5 hash value (representing a so-called "MD5 collision")?


Understanding BLS12-381 Curve I have some basic understanding of ECC - but pretty far from advanced concepts. I've been reading about BLS12-381 curve here and here, but I can't seem to fully understand it.

The things that I think I understand:

The order of the curve is $≈2^{381}$
The security level of the curve is 126 bits

The things that I don't understand:

What is the size of the private key for this curve? Assuming I'm right about the order, is it 381 bits?
The materials mention two generator points which produce public keys of different size - why is that? Shouldn't all points on the curve be of the same size?
What exactly is the subgroup $r$ and what is its significance?

The 12 in BLS12-381 means that the embedding degree is 12 and the 381 means that the prime in the finite field $\mathbb{F}_p$ is of 381 bits.
Now talking about your bulletpoints:

The order is not $\approx 2^{381}$. The order is the number of points on the curve. A naive way is to find the coordinates $y$ in the equation $y^2=x^3+4$ for $x\in \{0, p-1\}$, or a better way you can run Schoof's algorithm.
The security level is around $128$ bits. In fact, you need a subgroup of order $r \approx 256$ bits to have this security level because Pollard's $\rho$ attack (the fastest known algorithm to find discrete logs on elliptic curves) has a complexity $\approx \mathcal{O}(\sqrt{r})$ and indeed for BLS12-381 $r \approx 2^{256}$.
The private key is a scalar in $\mathbb{F}_p$ which means $\in \{0, p-1\}$. So yes the size is $381$ bits.
The order of the curve is not prime. If it is prime all the generators will have the same order (and thus public keys of the same size) as all subgroups will have the same order as the curve. In fact, according to Lagrange theorem, the subgroups orders divide the group order so if it is a prime the subgroups orders will be equal to the group order. So, since in BLS12-381 it is not a prime, you have generators of different orders (which all divide the curve order). The reason behind this choice is that we can implement efficient pairings (https://eprint.iacr.org/2012/232.pdf).
see above.


Brute forcing an HMAC Given current technology such as GPUs and GPU cracking software I was wondering if anyone has an idea on how long it would take to brute force the key used to derive an HMAC?

CodeInChaos has it right about the infeasbility of this against a random key; however, lets run the numbers to see how extremely correct he is:

Let us assume we are attacking HMAC-MD5 within TLS; this has a 128 bit key.

The fastest GPU server (actually, it has 25 GPUs internally) can test about 400 billion keys per second.

Let us assume that we, having a huge budget, have assembled 1 million of the above units; that means that we can test $4 \times 10^{17}$ keys per second; sounds impressive.

However, it'll take an average of $2^{127}$ keys tested before we recover the HMAC-MD5 key; at $4 \times 10^{17}$ keys per second, that'd be $4 \times 10^{20}$ seconds, or about $10,000,000,000$ years.  I'd call that somewhat impractical; if nothing else, the sun will become a red giant and destroy our set up before we're likely to find a result.

It gets even worse if we talk about HMAC-SHA1; that uses 160 bit keys; that increases the amount of time we'd expect to take by about 4 billion.

Yes, if what we're talking about is a key derived from a password, GPUs can be used.  However, when we're talking about random keys, they don't come close to scratching the algorithm.


RSA decrypt long messages (javascript) I am attempting to encrypty/decrypt a long message in RSA using javascript (with crypto-js and jsbn libraries).

I posted this on stackoverflow too but I figured someone here on crypto might be able to help as well.

so far, to encrypt/decrypt short messages I have the following code:

function encrypt(signedCert, msg) {
    key = new RSAKey();
    m = asciiToHex(msg);
    m = new BigInteger(m, 16)
    //n and e retrieved from the digital certificate
    key.setPublic(signedCert.msg.subject.pk.n, signedCert.msg.subject.pk.e);
    var ctxt = key.doPublic(m).toString(16);
    return ctxt;
}

function decrypt(sk, ctxt) {
    key = new RSAKey();
    c = new BigInteger(ctxt, 16);
    key.setPrivate(sk.n, sk.e, sk.d);
    var ptxt = key.doPrivate(c).toString(16);
    var ptxt = hexToAscii(ptxt);
    return ptxt;
}

this works like a charm when the message is short. but, for the life of me, I can't figure out how to encrypt/decrypt when the message is long!

can anyone help? thanks :)

I don't know much about the library you're using but it looks like you're trying to encrypt/decrypt the cipher-text using RSA directly.

Using RSA in this way isn't secure unless extreme care is taken.

This isn't the correct way to use RSA. Typically, what you do is use RSA to encrypt a secret key. This secret key is then used with a conventional symmetric cipher, such as AES, to encrypt your payload. Then your payload can be any length you like.

There are standards such as PCKS#1 v2.0 that deal with how to do this securely.


Applications of machine learning in classical ciphers? Machine learning is definitely applicable in analyzing simple shift ciphers like Caesar and affine ciphers, as well as substitution ciphers like Vigenère, but is it possible for machine learning to solve problems involving more complex ciphers such as Hill ciphers, where characters are mixed up and ruin frequency analysis?

A cryptanalyst finds the right key for decryption, while a machine learning model finds a suitable solution in a large space of possible solutions. With enough data, the machine learning model could find a good solution. How much data is needed to reliably use machine learning for breaking complex ciphers such that it's less work than brute-force search could be a challenge.


Multiplication encryption with a small number Given a big number $x$(1024 bits) and a large prime $N$($N>x$), I want to encrypt it with a smaller number $y$(128 bits).
$$Enc(x) = xy \mod{N}.$$
Is it safe? If not, how do I evaluate its leakage?

The most basic security is "Indistinguishability in the presence of an eavesdropper". This is based on a simple experiment. An adversary $A$ sends two messages $m_0$, $m_1$ to a challenger $C$. The challenger encrypts one of the messages (randomly chosen, say  $C$ chooses $b \in \{0,1\}$ uniform random and encrypts $c_b = Enc(m_b)$). The ciphertext is then send to $A$. The adversary now has to find out, which message was encrypted and sends $b'=0$ or $b'=1$ to $C$. If $b = b'$ we say $A$ wins.
Now we look at your Encryption: $A$ knows $Enc(x)$ and $x$. With the extended euclidean algorithm $A$ can compute $y$ and therefore can distinguish $c_b$. So $A$ wins the experiment and the Encryption system does not even provide the most basic concept of security.


Can a message encrypted with one AES-256-GCM implementation always be decrypted with another? I have a cookie being encrypted with AES-256-GCM in Rust using ring. I need to decrypt the cookie in Node.js. I'm using the standard crypto library, but it's just not working.

My understanding is that different implementations of AES-256-GCM algorithm should be compatible as long as they

Use the same key
Use the same ADD, and
Use the same IV/nonce. (Node.js calls it IV, ring calls it nonce.)

Is this correct?

I just want to double-check before spending even more time on this.

Yes.

HOWEVER....

An implementation may put the content of the encrypted message wherever it wants, and format the encrypted message any way it wants, including different text encodings such as Base64

You will need to take that into account, when decrypting the message, the input must be formatted in the way that an implementation is expecting, and that may be very different than what you have, or that a different implementation may output.

There may also be other things which are not part of the message, such as the expected size of the auth tag or nonce, but all implementations following the spec will deal with variations in size correctly, as long as they are told to do so.

For example, implementation A may output the data in this way [nonce][message][tag], and it may expect 3 inputs for decryption, output data stream, auth data, and key, then extract the nonce and tag from the message automatically, since that implementation only uses 96-bit nonce and tag sizes.

Implementation B may output the message, tag, auth data, and nonce as a Base64 formatted strings inside an XML file, and only take the same XML file and the key as inputs, and will detect the size of the nonce and tags from their specified lengths in the file, decode from B64, and decrypt the message.

As long as you can translate the encoding from one to another, you should be able to make them compatible. The dev documentation of those projects should show what output format they use, and if there are runtime options to modify that format.


Recovery of blowfish encryption key? Is it possible to recover key used for blowfish encryption, if I have encoded and decoded string as well as initialization vector tables (bfp and ks0-3)? I don't know the length of the key.

No, not unless the input for the key small enough to be brute forced or guessed. For any secure block cipher the key cannot be retrieved even if you have the input (block of plaintext) and output (block of ciphertext). And there are no known attacks on Blowfish that break the cipher significantly.

So it really doesn't matter how the block cipher is used. There may be attacks on the mode of operation, such as CBC/PKCS#5/7 padding oracle attacks. Those may leak information about the encrypted message, but not about the key.

The small block size of Blowfish makes it harder to use in a secure mode of operation, which is probably the main reason why Bruce Schneier doesn't recommend it anymore (besides that it is an old algorithm, and there are simply better ones available by now).


Dieharder How can I make my input file suitable for Dieharder? I created my random numbers and I saved them into a txt file. My input file includes just 0 and 1. Here is the link of my file
And I of course read some answer before asking that question but I could not understand how can I create an input file for diehard. Do diehard have some prepared comment for converting our input file for itself or we should do it by hand? If we should do it how? I see too many parameters like generator see type count numbit ...
Could you please help me?

Update: I actually answered this question but I have some troubles related my account so the answer is just lost so I am writing again

Many thanks for your answe rI think it finally worked with that

just to be sure: what is d? when I looked other example I sometimes saw b instead of d

I have just 0 and 1 so numbit should be 1 I guess, right?

and you wrote some numbers and they are actually random numbers right? (In my case it is jut 0 and 1 instead of 3129711816 85411969 2545911541)

And I want to test how much my numbers are random with this file and this code script right?

Also When I tried without changing my file as a header file, it worked with this code script: dieharder -a-f your-file.txt and what does thos script mean? OK it worked but I couldnt change my file like header file and I dont know what it means

Update-------------------------------------------------------------
Hello, I still have some troubles regarding matching of accounts so I am updating here
1)Happy Christtmas to you too!
I have not a bin file! Why do you think that. I am trying to produce quantum random numbes and my numbers will be either 1 or 0 and after producing them, I save it a txt file! WHat is the problem with txt file. I really dont understand your point. And studyong with diehard how many numbers should I have at least? 2000000 is not enough??
What are the other techniques
2)And can you please explain my questions, if you have seen them like what is d or is my header file correct?...
3)How can I convert my txt file as a binary file???
4)What is the other techniques for testing how much my numbers are random? Can NIST be ok?
5)For instance I used this line for converting bin file perl -ne 'print pack("B32", $_)' < instructions.txt > instructions.bin is that ok? And I used 10000000 data and I convert it as binary file and it was extremely fast. I think it should has been slow?
Important note: I am using dieharder 3.31.1 version

Personally I never bother with ASCII and just go binary as it's easier, but so be it. There's a lot of good stuff on this page, but in essence what you need to do is...
One.
To use it with an ascii formatted file:

     dieharder -g 202 -f your-file.txt -a

   (your-file.txt should consist of a header such as:

    #==================================================================
    # generator I did it myself
    #==================================================================
    type: d
    count: 100000
    numbit: 32
    3129711816
      85411969
    2545911541
    etc...

Two.
Please read https://crypto.stackexchange.com/a/61546/23115. This is important. Dieharder is a glutton and craves loads and loads of data. 2,500,000 ASCII characters is way too low and the result will be absolutely meaningless other than just failing.  The example in the linked answer sucked up 246 GB of binary bits so as not to rewind the data sample. That's more than a terabyte of ASCII.
Tip.
Randomness is a function of sample size. The size of your data set indicates alternative tests, such as the original diehard, or NIST's randomness test suite. The latter is pretty common in the literature for modern RNG designs, and I prefer it.

dieharder -a -g 201 -f your-file.bin to do it in binary without all that header nonsense.


Is there a public key semantically secure cryptosystem for which one can prove in zero knowledge the equivalence of two plaintexts? If Alice encrypts two messages $a$ and $b$, such that $x=E(a)$, $y=E(b)$. Can Alice prove (without revealing $a$, $b$ or the private key) that $a = b$?

Obviously the proof must not be too long and it should be practical to compute and verify (either interactively or non-interactively).

This is possible for the Pohlig-Hellman symmetric cipher, even if the ciphertexts are encrypted with different keys. But P-H is not public key.

If such a cryptosystem exists (and it is commutative or provides public re-encryption),  then one of the limitations in Mental Poker protocols could be solved. The problem is the existence (or not) of a protocol that can provide both semantic security and abrupt drop out tolerance (without any threshold scheme).
Edit: It seems that the encryption needs to be deterministic to be able to support drop-out tolerance, and I see no way to overcome this. Without determinism, I was only able to veto the cards of a single player from a new deck.

See What is the theoretical and practical status of mental poker? for a related question.

Yes.  Such proofs are possible for El Gamal.

It involves a zero knowledge proof of equality of a discrete log, together with the homomorphic property of El Gamal encryption.

Recall that given $E(a)$ and $E(b)$, anyone can form $E(a/b)$ using the homomorphic property of El Gamal.  Suppose $E(a/b)=(r,s)=(g^k,h^k a/b)$ (where $g$ is the generator and $h$ is the public key).  Then proving that $a=b$ is equivalent to proving that $a/b=1$, i.e., that $(r,s)=(g^k,h^k)$ for some $k$, or in other words, that $(g,h,r,s)$ is a Diffie-Hellman 4-tuple.  There is a standard zero-knowledge protocol to prove this fact.  That's all you need.


secp256k1: is it theoretically possible to generate same signature with different key, message hash and k? For a given private key $d$, random $k$ and message hash $h$ is it possible that there exists a different set of $d$, $k$ and $h$ which produces the same signature using $\text{secp256k1}$ curve?

We want $(r,s)$ same for two different set of $d,k,h$
In ECDSA

$r = x_0([k]G) \bmod n$ where $k \in [1,n-1]$ and $x_o$ is the x-coordinate of the scalar multiplication $[k]G$
$s = k^{-1}\cdot (h+r\cdot d)$ where $h$ is the left  most bits of $h$ to fit in the group order ( for simplicity we called it $h$ again).

Now we want same $(r,s)$ for $d,k,h$ and $d',k',h'$

$r = x_0([k]G) = x_0([k']G)$ although this may indicate that $k=k'$ it is not. The reason is that the coordinate field $p$ is smaller than the order $n$ of the base point. Therefore we can have solutions other than the trivial.

$s = k^{-1}\cdot (h+r\cdot d) = k'^{-1}\cdot (h'+r\cdot d')$,
then with $k'=k$ we have;
\begin{align}
   (d'-d)\cdot r &= (h-h') \\
  \end{align}
then with $k'\neq k$ with $c = k^{-1}$ and $c' = k'^{-1}$ ( for our eyes) we have;
\begin{align}
   c'\cdot h + c' \cdot r \cdot d &= c\cdot h' + c \cdot r \cdot d' \\
   c'\cdot h -c\cdot h'  &=  c \cdot c \cdot d' -c' \cdot r \cdot d \\
   c'\cdot h -c\cdot h'  &=  r \cdot ( c \cdot d' -c' \cdot d) \\
  \end{align}

As we can see by knowing $r$;
Either

we need to find a proper $d'$ for a given $d$ for given different hash values. This is free since we found the private key by just arithmetics.
OR, we need to find a message that produces desired hash value $h'$ so that we have equality. This is hard since we need to break pre-image resistance of SHA256.

As we can see it is possible but hard.
For the case $k'\neq k$ the calculations are similar.


Ciphers with identical round keys Ciphers like PRINCE or LED seem to use identical round keys. Does anybody know other cipher (may include hash functions, MACs or AEADs) that has the same property?

LED and prince ciphers are designed for lightweight purpose (to save area, energy..etc) , They have no key schedule. Other ciphers that have no key schedule are Zorro, Midori, LS-designs (Fantomas & Robin).
The above mentioned ciphers use round constant addition for protection.


Run AES for 2 rounds I am trying to figure out AES in two rounds with 128 keys. If I have a known plaintext and the ciphertext that comes from this procedure. I get another plaintext which is similar to the previous with the difference of only one byte. I don't know the keys. Everything is  128 bits. How much will be the final ciphertext be affected?

I am taking this step by step for the two plaintexts (with one-byte difference) and I see that:

XORing with the first key: Only the different byte will change.
Byte substitution: Comparing the result of the 2 cases everything will stay the same except form the different byte.
Shift byte: The two outcomes will change the same way and the different byte will still be one just in a different place.

(is that correct so far?)

Then comes the mixcolumn... Here I am confused as to how much the result will be affected if I compare the two cases.

Any help with that?

The difference of one byte before MixColumn will propagate to the whole column. The goal of this step is to mix the four bytes together to get another four bytes. Look at the definition and try it yourself.

Also, there is some nice property here. There are $256$ possible values for the XOR difference of the two bytes and since MixColumn is linear, the XOR difference of the two columns after applying MixColumn will be the same as applying MixColumn to the difference of the columns before. So there are only $256$ possible values for the entire difference of the two columns after MixColumn.

To make it clear: if $C_1$ and $C_2$ are the two columns that differ in only one of the four bytes, then there are $256$ values for $C_1 \oplus C_2$, and we have $\mathrm{MC}(C_1 \oplus C_2) = \mathrm{MC}(C_1) \oplus \mathrm{MC}(C_2)$, so only $256$ possible values for $\mathrm{MC}(C_1) \oplus \mathrm{MC}(C_2)$.

I think it's a nice property.


How to check runtime of e.g. Ed25519 signature algorithm As mentioned here the verification of a Ed25519 signature takes roughly 3 times as the time for the generation of a signature. Two questions on that:

1) Can I assume that this is a rule of thumb for this algorithm? I can imagine that the ratio of the times differ for different CPUs

2) How can I exactly see (using the algorithm) why verification takes (much) longer?

In elliptic curve cryptography, the main operation is point multiplication: given an integer $k$ and a point $P$, compute $kP$ ($P$ added to itself $k$ times).

If the point $P$ is known beforehand, the computation can be sped up by using precomputation tables.

EdDSA signing requires computing $rB$ where $B$ is a fixed point (the "base"), therefore can be sped up.

EdDSA verifying requires computing $sB - hA$, i.e one fixed point multiplication and one "random" point multiplication ($A$ comes from the signer's public key). If you assume the fixed point multiplication is twice as fast than random point multiplication, then the result is that verification is three times slower than signing.

But of course, it depends on the implementation. In a naive implementation that doesn't optimize the fixed point case, verification will be two times slower than signing. It also depends on the size of the precomputation tables used.

This is described abstractly in sections 3.3 and 3.4 of the RFC 8032 (which are slightly confusing due to the $2^c$ factors), and more concretely in 5.1.6, 5.1.7 for Ed25519 and 5.2.6, 5.2.7 for Ed448 (which explain that you can ignore the $2^c$ factors).


Is there an existing cryptography algorithm / method that both encrypts AND compresses text? So I'm trying to find a method of encryption that not only obfuscates text, but also compresses the result.

For example, if I encrypted ninechars, the ideal result would be less than nine characters.

Otherwise, if this is not possible, is there a method where I can set a limit on the amount of characters in the result? In other words, no matter how long the input is, the result will always be 50 characters long.

The closest results that I have found are Caesar Encrypt and XOR Encrypt, but they seem to simply result in the same amount of characters as the original input. The others I have found increase the size.

TL;DR I pretty much need a "hash function" that is reversible.

So I'm trying to find a method of encryption that not only obfuscates text, but also compresses the result.
  For example, if I encrypted ninechars, the ideal result would be less than nine characters.

Even without encryption, it's not possible for a reversible data compression scheme to shorten all of its inputs.  This can be easily proven using the pigeonhole principle: for any given length $\ell$, there are fewer strings of length strictly less than $\ell$ than there are strings of length at most $\ell$.  Thus, if the compression scheme maps all strings of length at most $\ell$ to strings of length less than $\ell$, it must necessarily map some distinct input strings to the same output string, and thus be irreversible.

(In fact, a similar argument can be used to show a stronger result, namely that, if a lossless compression scheme makes any input string shorter, then it must also make some input string longer.  I'll leave proving that as an exercise.)

  Otherwise, if this is not possible, is there a method where I can set a limit on the amount of characters in the result? In other words, no matter how long the input is, the result will always be 50 characters long.
  TL;DR I pretty much need a "hash function" that is reversible.

This is also impossible, by a similar argument.  There is a finite, fixed number of strings of length 50 (namely, $k^{50}$ for a $k$-letter alphabet), whereas the number of possible input strings of unbounded length is infinite.  Thus, not only does any function mapping arbitrary unbounded inputs to 50-character outputs need to map some distinct inputs to the same output, but it actually has to map infinitely many inputs to some output.

In fact, to show that such a function cannot be reversible, it's enough to consider only inputs that are 51 characters long.  Clearly, there are more 51-character inputs than there are 50-character outputs, so some distinct inputs have to map to the same output.

Of course, if you allow some inputs to increase in size, then you can make other inputs shorter.  This is basically what ordinary data compression algorithms like LZW do — they rely on the fact that most of the possible inputs to the compressor look essentially like random noise, whereas most of the typical inputs (like plain text, program code, uncompressed image or audio data, etc.) have a lot of repetitive, non-random structure.  Such repetitive data can be encoded more compactly, making it a lot shorter; meanwhile, if the input does not happen to be repetitive enough to compress well, the compressor will just insert a short marker (at a minimum, a single bit, but in practice usually a few bytes) indicating that the data could not be compressed, and then include the input verbatim.  Thus, the compressor can compress some common types of inputs significantly, at the cost of very slightly increasing the length of the random-looking inputs that make up the bulk of the full input space.

Anyway, none of this really has anything to do with cryptography.  If you want to both compress and encrypt data, the standard way is to first compress it, and then encrypt it.  (You cannot compress it after encryption, since encrypted data does look random to anyone who doesn't know the key, and has no apparent structure that a compressor could exploit.)

As other answers have pointed out, though, even this standard method has risks.  One risk comes from the fact that any encryption scheme that can handle arbitrarily long messages must necessarily reveal at least some information about the length of the message.  This may allow an attacker to, say, distinguish the message YES (three characters) from the message NO (two characters).

This is true even without compression, and needs to be kept in mind when designing any cryptosystem, but adding compression to the mix makes it harder to predict and defend against.  For example, even if you were careful to always use fixed-length messages (like, say, POSITIVE and NEGATIVE instead of YES and NO), it's quite likely that running such messages through a compressor will produce output whose length varies.

More importantly, if the attacker can control some of the data being compressed and encrypted, they may be able to learn information about the other parts by observing the length of the compressed message.  For example, let's say the attacker can make you generate, compress and encrypt messages of the form TO <ID>: STATUS <POSITIVE/NEGATIVE>, where <ID> can be controlled by the attacker.  The attacker may then be able to request two encrypted messages, one for <ID> = POSITIVE and one for <ID> = NEGATIVE, and see which one compresses better.

Of course, these are all just toy examples, but similar weaknesses have led to real attacks.  For example, as mentioned in otus's answer, the CRIME and BREACH attacks on SSL are based on the same principle as the chosen-plaintext toy attack described in the previous paragraph.  Even the passive attack described earlier above, based on just observing naturally occurring message lengths, may be used to e.g. eavesdrop on encrypted VoIP conversations.

That said, the lesson to take home here is not just that data compression is dangerous and should be avoided.  Rather, it's that the leakage of plaintext length is dangerous, and, since it cannot be completely avoided, must be kept in mind when analyzing any crypto protocol.  Compression is an additional complication on top of that, since it can make the message length depend on its content in non-trivial and non-local ways.


How Were secp*k1 elliptic curve generators chosen? The Koblitz elliptic curves specified in the SEC2 document https://docs.google.com/viewer?url=http%3A%2F%2Fwww.secg.org%2Fcollateral%2Fsec2_final.pdf all have the nice feature that the parameters are highly non-arbitrary; the modulus is simply a few powers of two put together, and the a and b parameters are 0 and 7. The group order can be forgiven; that's just a number that you get given the other parameters of the curve. However, the choice of generator seems to be very arbitrary. Why did the SEC not choose simpler parameters for the generator (eg. x = 1000, y is even) instead?

Well, I'm not privy to how Certicom selected these parameters, however I can tell you that it doesn't really matter; if the generator they selected is weak, then all generators on that curve are weak.

In particular (and assuming that the curve has a prime number of points on it; this is true for the Certicom curves):

If you can solve the discrete log to a specific generator $G$, you can solve it to any base (by solving two instances of the generator $G$ problem)
If you can solve the computational Diffie Hellman problem with a specific generator $G$, you can solve it to any base (by solving $\log p$ instances of the generator $G$ problem).

Hence, if there is a weakness with their generator, then their curve is weak (except possibly against the decisional Diffie-Hellman problem; I don't know of a similar reduction there).

Demonstrating the first reduction is quite straight-forward; suppose thatwe are  given an Oracle, that, given $aG$, recovers $a$ (with $G$ being our distinguished generator).  Then, given an instance which consists of $H$, and $aH$, with $H$ being an arbitrary point, we call the Oracle twice, once with $H=bG$, and once with $aH = cG$, recovering $b$ and $c$.  Then we can compute $a = b^{-1}c \bmod q$ (where $q$ is the order of the curve); this is our answer.

The computational Diffie-Hellman case is somewhat more complex.  For that, we suppose that we have an Oracle that, given $aG$ and $bG$, computes the value $abG$.  Then, the problem we are trying to solve is, given $H$, $aH$ and $bH$, compute the value $abH$.

To see how to we proceed, let us designate $c$ as the value $H = cG$.  Now, we don't know the value of $c$, however we can compute the point $c^2G$ (by using our Diffie-Hellman Oracle, with the inputs $cG$ and $cG$).  Extending this observation, we can compute $c^kG$ with $\log{k}$ calls to the Oracle.  So, we compute $c^{q-2}G = c^{-1}G$ (with $\log{q}$ Oracle calls, and $q$ is the curve order).  Then, with $aH = acG$ and $bH = bcG$, we can compute $abH = abcG$ with two more Oracle calls.


How can I avoid side channel attacks to scalar multiplication of Ed25519? I'm a beginner at working with Edwards Curves, and I'm trying to implement an Ed25519 signature. I have a question from a text.  Please see the illustration below (in Python).
At the part of scalar multiplication it simply uses the double-and-add method:
def point_mul(s, P):
    Q = (0, 1, 1, 0)  # Neutral element
    while s > 0:
        if s & 1:
            Q = point_add(Q, P)
        P = point_add(P, P)
        s >>= 1
    return Q

Is that safe enough?
Why doesn't it use a constant time method like x25519 for DH key exchange?
There is the Montgomery ladder as method of scalar multiplication of X25519 for DH key exchange to prevent side channel attack. How about Ed25519?
How can I protect against side channel attack when using scalar multiplication?
How can I modify the function?
I will implement with a hardware design after finishing the python implementation. Is there any method to prevent the attack?

As pointed out in section 8.1 of the RFC, "the example implementations in this document do not attempt to be side-channel silent".

You can't write the algorithm as is. Basically, you need to always compute the point addition:

T = point_add(Q, P)
Q = select(Q, T, s & 1)
P = point_add(P, P)
s >>= 1

The select function (also called "conditional copy") selects one of the two operands depending on the value of the third, in constant time (or "side-channel silent" to be more precise). This means that you can't use branches, but just arithmetic operations.
The basic idea is to compute q ^= (q ^ t) & -b where q and t are the input and b is the select bit. If it is 0, q will stay the same; if it's 1, the -b will equal to 0xFFFF... and q will be set to t. You have to be careful to use the correct data types for it to work - though since you'll implement it in hardware that will be easy to handle. Of course, you'll need to do this for every word of every number in the elliptic curve points involved. There are many examples, here is one of them.


What are the differences between ephemeral-static ECDH and static-static ECDH? As I know ECDH can be used with a fixed public key. I read there are two types of static ECDH, ephemeral-static ECDH, and static-static ECDH.

What are the differences between these two types?

Static static Diffie-Hellman isn't that commonplace. It uses two static key pairs (where both the public and private keys are static, not just the public key) to establish the secret. Generally those keys are trusted keys: the public keys are commonly embedded in signed certificates. That way static-static Diffie-Hellman can be not just used to derive a secret (session) key, but also to authenticate both parties.

Note that it is required to use a nonce generated by (at least) one of the parties for static-static Diffie-Hellman: without this nonce the derived secret would always be the same, as there is no fresh data within the Diffie-Hellman calculation itself.

Static-static Diffie-Hellman is not provide forward secrecy: if either one of the private keys is found by an adversary then the shared secret can be calculated (using the public key of the other party) and all security is lost.

With ephemeral-static Diffie-Helman one party generates a new key pair for each key agreement.

Only the party with the static key pair can be authenticated by the key agreement itself. The other party with the ephemeral (transient or fleeting) key pair can authenticate itself after the key agreement. As it knows now that the session is to a trusted party, that authentication could be anything from signature generation to simple password validation over a secure channel.

Ephemeral-static Diffie-Hellman is does not provide forward secrecy. If the static private key is found by an adversary then the shared secret can still be calculated for this and every other connection that was created by it.

Generally ephemeral-ephemeral Diffie-Hellman is used. This provides forward secrecy: the other sessions are still secure even if one or both of the private keys is found. Both key pairs are regenerated for each key agreement. Fortunately, DH key pair generation is nowhere as slow as RSA key pair generation. RSA or ECDSA can be used to authenticate one or both the parties.

All of the above goes for both Diffie-Hellman using a multiplicative group (just DH) as well as ECDH. More info can be found in the document NIST Special Publication 800-56A, Revision 3: Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography. Take a look at the C(0e, 2s) for the static-static and C(1e, 1s) for the ephemeral-static scheme.


Substitution Cipher vs. Permutation Cipher What is the difference between Substitution Cipher and Permutation Cipher?

In a substitution cipher I have seen that there is a random choice of 26 alphabet characters for encryption and decryption and that it can't be broken by brute force attacks because the sample space for key encryption is 2**88 which is very large. Hackers can use frequency analysis to get the encrypted message.

What about permutation cipher, then? What is this and why it comes under poly-alphabetic and substitution comes under mono-alphabetic?

Substitution Ciphers

Substitution ciphers replace units of plaintext with units of ciphertext.

A simple example is the Caesar cipher, which specifies the substitution of each plaintext letter with the letter which is found some fixed number of places away in the alphabet. The Caesar cipher is easily broken by trying all possible offset values, where the number of offset values is equal to the alphabet size.

For example, if the offset value is $s = 3$, then the plaintext $caesar$ will be encoded as the ciphertext $fdhvdu$.

The class of cipher's to which the Caesar cipher belongs is the monoalphabetic substitution ciphers.

Another class of substitution cipher are polyalphabetic substitution ciphers. The Vigenère cipher is a simple example which substitutes plaintext values for ciphertext values using a series of Caesar ciphers which are defined by a keyword.

The keyspace $|K| \approx 2^{88}$ mentioned in your question can be derived from a Vigenère cipher with a 26 character alphabet and a keyword $k \in K$ which is 26 characters long. The calculation is $26!$ which tells us the number of different configurations in which we can arrange 26 characters.

This brings us to the concept of brute force complexity. Brute force complexity is a measure of the computational effort which is required exhaustively find a solution to a problem. In order for brute force complexity to be meaningful in a cryptographic context it is necessary that there aren't any shortcuts which can be taken to reduce the space which must be searched.

The Vigenère cipher does not usually meet this requirement. If the length of the plaintext is greater than 26 characters, or the same keyword is used to encrypt multiple messages, then an attacker can use frequency analysis techniques to recover information about the encrypted messages.

Both of these constructions are very old. Claude Shannon's information theory and it's application to cryptographic systems as information-theoretic security is sometimes credited with transforming cryptography from an art into a science and is an important foundation in modern cryptography.

Essentially Shannon sought to quantify information leakage in the context of cryptography, and proved that the one-time-pad satisfied a property known as perfect secrecy - it cannot be broken by any adversary, even one given unlimited computational power and time.

Permutation Ciphers

Permutation ciphers attempt to hide information from an adversary by rearranging the plaintext so that it can no longer be recognised. A simple example is the rail fence cipher which transposes a plaintext by arranging it diagonally into a number of rails. In practice this is highly insecure since the number of rails is small and can be attacked by brute force.

Modern Block Ciphers

Some modern Ciphers such as AES apply both substitution and permutation repeatedly in rounds by applying a construction known as a substitution-permutation network (SPN). AES is much more secure than any of the ciphers mentioned above, and is not vulnerable to frequency analysis in the same way as alphabetic ciphers are. For a better understanding of AES I recommend reading: A Stick Figure Guide to the Advanced Encryption Standard (AES)


The mathematical similarity and difference between code-based PKE and multivariate DSS In code-based public key encryption schemes, a public key is formed by matrix-multiplying 2 linear matrices to the left and right side of a easily decodeable error-correcting code, so that it'll be difficult to extract useful information that may be used to decrypt ciphertexts.
In multivariate digital signature schemes, a public key is formed by compositing linear equation systems to the inner and outter parts of a easily solvable multivariate (usually quadratic) equation system, so that the resulting composition cannot be easily reversed.
From my understanding, the composition with linear systems is the biggest similarity between code-based PKE and multivariate DSS, and I wonder:

Is there any other aspect where code-based and multivariate cryptosystems are similar?

What are the important differences between code-based and multivariate cryptosystems?

Multivariate schemes tipically work with a central polynomial map $\mathcal{F}(X) : F_2^n \mapsto F_2^m$ which is a quadratic map that defines $m$ quadratic equations on $n$ variables. Then select $T,S$ as invertible affine transformations. The public key $P(X) = T \circ F \circ S(X)$ is written as $m$ quadratic forms in $n$ variables over $F_2$.
However, as every Quadratic Form $q_i(X)=X^T Q_i X$ can be linearised using Tensors, this is, a dot product of $\overline{q_i}(x \otimes x)$ where $\overline{q_i}$ is the $n^2$ vector reshape of the matrix $q_i$.
Then rewrite the public key as a $m \times n^2$ matrix $\overline{P}$ where the $i$th row encodes the $i$-th columns of the quadratic forms. This is a rectangular matrix which doesn't allow an attacker to compute the input value $X$ from the output $Y$. From here the goal is to either attempt to solve by obtaining the affine transformations $(T,S)$ which we refer to the Isomorphism of Polynomials ($\mathcal{IP}$), solving the underlying non-linear quadratic system over $F_2$, which is a subinstance of the PoSSo problem, called the $\mathcal{MQ}$ problem or studying the MinRank $\mathcal{MR}$ problem.
For example, an HFE public key can be computed using pure Linear Algebra, without working in Polynomial Rings and Finite Fields. Either deriving the Quadratic Forms as I did here or using Tensors. But you still need to apply Berlekamp's to find roots over $F_q$.


Can physical object hiding be quantified with entropy? If it works in the virtual world, why can't the same principle work in the real world?

For example if you want to hide a private key, you need a virtual haystack to hide it inside, which is the entropy of it's random source.

So if we want to generate a 21.9 bit key we need to select one random one out of 4000000 possibilities.

The same way in the physical world if we have a 10 m^3 size room, but only 2m^3 area can be used to hide things, then if we were to hide a small object like a dice which is like 0.5 cm^2, then we have 4000000 possibilities, which would be 21.9 bits.

So could the real world hiding of object be quantified in the same way ( excluding the fact that our eyes have a wide vision range so it would be easier to find, but also we could not go through all possibilities as fast as a computer could)

If you can quantify it with a probability distribution, yes—any probability distribution has an entropy.

Here's an analogy: Suppose a line of 256 people each flip a coin, and put it in their left hand if it comes up heads or their right hand if it comes up tails; then they close both hands in a fist.  If you can't watch them flipping and placing the coin in their hands, you can't tell which hand each person has the coin in.  The probability distribution on your state of knowledge about where the coins are has 256 bits of entropy.

The fact that it's people playing the which-hand game instead of a CPU storing a 256-bit key in a register in silicon is immaterial; entropy is a property of the probability distribution characterizing your state of knowledge.


Converting normal alphabets to 64 bit plain text How can I convert a normal alphabetical text (say hi) to a 64 bit or 128 bit binary digit input for DES?

What's asked requires choices not explicit in the question:
1. Character encoding into bytes
The most common and recommendable convention nowadays is UTF-8, which encodes any character as a sequence of 1 to 4 bytes, including any ASCII character as 1 byte. For these, UTF-8 is compatible with many other earlier conventions that encode each character to a single byte. The Latin alphabet and Arabic numerals are encoded incrementally, per the poor man's ASCII table
    a $\to$ 0x61     b $\to$ 0x62     …   z $\to$ 0x7a
    A $\to$ 0x41     B $\to$ 0x42     …   Z $\to$ 0x4a
    0 $\to$ 0x30     1 $\to$ 0x31     …   9 $\to$ 0x39
      $\to$ 0x20 (space)
Note: the prefix 0x introduces hexadecimal in this answer, and some common computer languages.
Therefore, the two-character hi gets encoded to the two bytes 0x68 0x69 per UTF-8, ASCII, ISO/IEC 8859-1, Windows-1252, and many others conventions.
Encoding and decoding is built into many common computer languages, e.g. in Python
bytes('Hi', 'UTF-8') equals b'\x48\x69\xf0\x9f\x98\xb7' and
b'\x48\x69\xf0\x9f\x98\xb7'.decode('UTF-8') yields 'Hi'.
Other conventions are still in wide use, e.g. per UTF-16 LE with surrogate pair support, the three-character 'Hi' encodes to 0x48 0x00 0x69 0x00 0x3d 0xd8 0x37 0xde.
2. Padding
That is handling the last byte(s) to form the last (perhaps only) block for the cipher, of 64 bits or 8 bytes in the context of DES. There are several conventions around, the most common being:

Zero-padding. For a block cipher with $w$ bytes ($w=8$ in the case of DES), it is added $0$ to $w-1$ bytes at 0x00, as necessary to reach a multiple of $w$. That's fine for encodings (including UTF-8) that assign to byte 0x00 a no-operation or end meaning, but is not usable for arbitrary bytestring, because the decoder facing a last block ending in 0x00 won't know if that byte needs to be kept or removed.
hi per UTF-8 is padded to 0x68 0x69 0x00 0x00 0x00 0x00 0x00 0x00.
Various bytes padding, the most common of which nowadays being PKCS#7 padding. For a block cipher with $w$ bytes ($w=8$ in the case of DES), it is added $1$ to $w$ bytes which common value is the number of bytes added in order to reach a multiple of $w$.
hi per UTF-8 is padded to 0x68 0x69 0x06 0x06 0x06 0x06 0x06 0x06.
Note: The decoder handling the last block (if any) should get the value $x$ of the last byte, remove that byte, then remove the $(w-1+x)\bmod w$ byte(s) before that, thus leaving $0$ to $w-1$ bytes. That's compatible with some common variant of PKCS#7 padding such as ANSI X9.23, and minimizes the risk of padding oracle attacks.
Bit padding. It's common in cryptography for MACs, hashes, and sometime encryption (I know no official name; it's ISO/IEC 9797-1 Padding Method 2 in a DES MAC context). For a block cipher with $b$ bits ($b=64$ in the case of DES), it is added a single bit at one, then $0$ to $b-1$ bit(s) at zero as necessary to get to a multiple of 64 bits. In most contexts including DES, the bits are converted into bytes per big-endian convention, so that the single bit at one becomes byte 0x80.
hi per UTF-8 is padded to 0x68 0x69 0x80 0x00 0x00 0x00 0x00 0x00.

Finally, there's a specific
Bit numbering per the DES specification
and it matters when doing one's implementation of DES from scratch for educational purposes. Each of the 8 bytes is turned to 8 bits per big-endian binary, leading to a sequence of 64 bits numbered from 1 to 64. Bit $i\in[1,\,64]$ belongs to the byte at offset $\lfloor(i-1)/8\rfloor$ and extractible by shifting that right by $(64-i)\bmod8$ bit(s) then keeping the low-order bit.
In C: (blockOf8Bytes[(i-1)&7]>>((64-i)&7))&1 (the 64 can be omitted).
Thus hi per UTF-8 with zero padding is
0110100001101001000000000000000000000000000000000000000000000000
with the seven bits 2, 3, 5, 10, 11, 13, 16 set (at 1) and the other fifty-seven bits clear (at 0).

Note: Except in the insecure ECB mode of operation, the plaintext would be combined (likely, by exclusive-OR) with something before entering the DES block cipher.
Note: The question mentions “(…) 128 bit binary digit input for DES”, but nothing that requires more than one 64-bit block for hi.
Note: DES is insecure as a design choice due to its 56-bit key. It is obsolete at least for bulk encryption purposes in all its forms, including 3DES with 168-bit key, due to its 64-bit block size.


Signature verification vs decryption? I've found this explanation regarding signature verification but I still confused

In the example in the picture, the sender sign the hash using his secret key. The output of signing produces a signature.

The receiver takes as input the signature and with the public key (sent with the message) verify it using verification algorithm and produce the hash as output. According to what I understand, the receiver performs the revere action, which is equivalent to encryption /decryption, using private/public key instead of the same private key.

Any clarification, please?

This diagram is not accurate.  Hashing is not a separate step outside signing for the convenience of handling long messages; hashing is an integral part of signing that is necessary for security.  And the verification algorithm does not always return a hash that you can compute separately: it only returns a boolean that indicates a valid signature or not.  In particular, signature is not ‘encryption with the private key’, which is a contradiction in terms, and very few signature schemes even resemble that idea.  Here is an accurate diagram:

Note that hashing doesn't figure into this diagram, because it sits inside the signature algorithm and the verification algorithm; the user, who calls the signature algorithm or calls the verification algorithm, is not concerned with the hash function.

How does it work inside?  Let's examine an example of an RSA-based randomized signature scheme, RSA-PSS, which is related to (but better than) the standard RSASSA-PSS algorithm of IEEE P1363-2000 and PKCS#1 v2.1:

There is a hashing step inside, but it is randomized with randomization that is embedded in the signature, so it's not just that we compute $\operatorname{MD5}(m)$—which would make us vulnerable to collisions in MD5!  If we skipped the hashing step, using $s^3 \equiv m \pmod n$ as the verification equation, the signature scheme would be totally insecure, e.g. I could forge 3 as a signature on the message 9—this is why hashing is not a separate step for the convenience of long messages, but actually crucial for something to be a secure signature algorithm at all.

In other signature schemes like Ed25519, there is no hash concealed within the signature that the verifier compares against a recomputed hash: a valid signature under a public key $A$ is a pair $(R, s)$ of a point $R$ and a scalar $s$ such that $[s]B = R + [H(R, A, m)]A$; here we are working in an elliptic curve, namely edwards25519, with standard base point $B$.  The hash $H(R, A, m)$ uses inputs that are embedded in the signature, so like RSA-PSS the hash can't be computed separately without the signature; and then the hash figures into some fancy math that returns a boolean answer $[s]B \stackrel?= R + [H(R, A, m)]A$ directly.


MPC on boolean circuits I am reading about Yao's and GMW protocols and was wondering if there is any perfectly secure MPC protocol in the semi-honest setting, where the underlying circuit is a Boolean circuit (eg. n=3 and t=1)?

You can easily embed a Boolean circuit into the field $GF[2^k]$ for any $k$. Once you have done this embedding, you can then run any perfectly secure protocol. However, note that perfect security requires $t<n/3$ and so a minimum of 4 parties (with 1 corruption). For $n=3$ and $t=1$, it is possible to get statistical security.

Note that for the specific case of $n=3$ and $t=1$ you can also use a dedicated for Boolean circuits. For semi-honest adversaries, one example is High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority.


What are some of the alternatives to password based file encryption? With the ever increasing risk of attackers compromising password based encryption by brute forcing or guessing passwords, are there alternatives to this traditional scheme of deriving encryption keys from passwords. I realize that there are memory hard hash functions like Argon2 that creates derived keys from passwords, and because of the memory hardness slows down brute forcing to some extent. But still, if the password is weak in the first place and if the salt is known to the attacker, then brute force becomes trivial, considering ever increasing rate of computational power, provided by GPUs, ASICs etc.
Further more, when considering the problems associated with file encryption,  where it is required to generate a key (256 bits) to use in a symmetric encryption algorithm like AES, there is not a better user friendly method than asking the user for a password or a passphrase. Also, if we consider biometric methods like fingerprint detection, it is almost impossible as of now, to derive the same encryption key from biometric data all the time.
But are there, other methods, most preferably software techniques that I'm not aware of?

Hardware tokens (such as smart cards, FIDO U2F keys, and other secure storage elements), and normal files can all directly store cryptographic keys. For example, it's recommended to configure SSH servers to only use cryptographic key files.


PhD in cryptography using elliptic curves I am currently a MSc student in number theory and considering switching to a phD in cryptography. I would like to use number theory techniques. (i.e. RSA, elliptic curves, etc).

The purpose of all of this is to find a job outside of academia. I would like to find a job in the industry.  Here is my worry: in 10-20 years quantum computers will be able to "solve" these problems. Hence, number theory will become useless in cryptography.

Knowing this, will I be able to find a job in the industry in, say, 5 years?
My thought is that I will eventually have to adapt but so will everyone else. Will this be a problem for my career?

Kind regards.

If you want to end up in the industry, I strongly doubt a PhD is a good investment of your time, regardless of the rest of this discussion.

I believe a general purpose quantum computer, the kind that will send us all to relearn all our algorithm theory, is far from certain in 20 years. I won't even be surprised if someone publishes tomorrow a serious proof it can't be built. 10-20 years ago people were making similar predictions, and though quantum annealing seems to have moved forward, general quantum computers have not advanced much.

In the industry, people won't want to hire you because of your specific thesis and maybe not even because of your field of study. A PhD shows you are intelligent, capable of independent research, capable of finding and reading the latest literature, etc. These are marketable skills.

I read many PhD resumes on a daily basis. And though we do machine learning and artificial intelligence work, I won't throw out a cryptography PhD resume. However the real question with any PhD resume is: can they build production grade software? I believe our own requirements are common in the industry.


Why mounting/dismounting an encrypted file container takes only a few seconds? When the encrypted file container contains 100000 files and 500 GB of data, all of them must be decrypted/encrypted when the container is mounted/dismounted.
How can Truecrypt/Veracrypt perform this within a few seconds?

Think of it this way.
When you plug in a non encrypted external hard drive, does your computer read all of the data? No, it reads the partition table and some of the directory structure/MFT in order to display disk space usage and the root directory. The same thing occurs when an encrypted drive is mounted, whether it is Truecrypt, LUKS, or Bitlocker.
Disk encryption is block based, each block can be encrypted or decrypted independently of other blocks, to enable random access to the encrypted data. Only the data that needs to be read is read in order for the computer to understand what is being mounted, and thus only the blocks that need to be decrypted are decrypted.
Prior to disk access occurring, the mounting process must first determine the key and encryption method using the password or key material provided, this is very quick unless you have a custom iteration count.
Additionally, on many drives, the read/write speed is far slower than the cryptography speed the computer is able to handle, so there is no perceptible loss of performance due to encryption overhead.


How can a Encrypt-And-MAC scheme be insecure if the encryption is CCA secure? I was presented with this seemingly paradoxical information, and am hoping someone can explain what I'm missing here.

I have an encrypt-and-mac scheme here.If I want to transmit message m to Bob, I'd first Enc_k1(m) = c, MAC_k2(m) = t, and then send c||t over to Bob. So far, I understand that this scheme provides no integrity on the cipher-text itself, since the tag only verifies the original message and nothing else.

However, I am also presented with that Enc_k1 is CCA secure.

And then I was told that the Enc-and-MAC scheme is NOT CCA secure.

How can this be? If the encryption itself is CCA secure, the only way the scheme is not CCA secure is if and only if the MAC is not CCA insecure, but I have no idea if that even makes sense.

If it is possible, how can an attacker provide a possible CCA attack?

Note that the security notion targeted by MACs is not IND-CCA, but EUF-CMA (Existentially Unforgability against Chosen Message Attacks).
You can read the formal definition on page 156 here: https://cseweb.ucsd.edu/~mihir/papers/gb.pdf.

Suppose we have a MAC scheme $M =(\mathcal{K}, \mathsf{MAC}, \mathsf{VF})$ which is EUF-CMA secure. Let's create another MAC scheme $M' = (\mathcal{K}, \mathsf{MAC}', \mathsf{VF}')$ which is still EUF-CMA secure, but which provides absolutely no privacy of the message. It is defined as follows:

$$\mathsf{MAC}'_K(m) := m || \mathsf{MAC}_K(m)\\
\mathsf{VF}'_K(m, t) = \mathsf{VF}'_K(m, m' || t') := \text{return 1 iff } m = m' \text{ and }  \mathsf{VF}_K(m, t') = 1.$$

I leave it to you to prove that $M'$ is EUF-CMA secure. However, what can you say about the security of your combined scheme with $M'$ as the MAC function?

If you are interested in learning more about the E&A mode and the security of generic composition in general (i.e., EtA vs AtE vs E&A), then the standard reference is:
"Authenticated Encryption: Relations among notions
and analysis of the generic composition paradigm
" - containing full proofs and counter-examples.
For more on AtE and E&A in particular, look at "The order of encryption and authentication for protecting communications (Or: how secure is SSL?)".


extract ciphertext from encrypted SMIME file the main question of this message is how to get the true ciphertext from S/MIME file?

I created RSA keys and encrypted a message with S/MIME as follow :

1) generate private key : openssl genrsa -out maCle.pem 1024

2) create certificate(public key) : openssl req -new -x509 -key privkey.pem -out certif.pem -days 1095

3) encrypt using smime : openssl smime -encrypt -in plaintext -text -out mail.msg certif.pem

mail.msg looks like:

MIME-Version: 1.0
Content-Disposition: attachment; filename="smime.p7m"
Content-Type: application/x-pkcs7-mime; smime-type=enveloped-data; name="smime.p7m"
Content-Transfer-Encoding: base64

MIIBnQYJKoZIhvcNAQcDoIIBjjCCAYoCAQAxggEwMIIBLAIBADCBlDCBhjELMAkG
A1UEBhMCRlIxEjAQBgNVBAgMCUZSQU5DRVNFQjEQMA4GA1UEBwwHQ0lUWVNFQjEP
MA0GA1UECgwGT1JHU0VCMRQwEgYDVQQLDAtPUkdVTklUTkFNRTEPMA0GA1UEAwwG
U0VCU0VCMRkwFwYJKoZIhvcNAQkBFgpTRUJTRUJBRERSAgkAvllfFuC1s/owDQYJ
KoZIhvcNAQEBBQAEgYCzD+ShH91R3PEFTFJzcmW5Ie91AT9vHHCVJ1Sb78/oUHVi
PjS3PJyMD55MWGX+FmC/XYxtMNROP6CJ4nQIh6CmQIzXse/Yvg8WQOEJepC6AmDS
0b2xdQmiDO4Zb9C6ZUjWyH9KzOTwdZC+xm0WdAdB/psTXOL1api8P54H+hti9zBR
BgkqhkiG9w0BBwEwGgYIKoZIhvcNAwIwDgICAKAECBUxiu2WmkuFgCjdkDzatfYg
YwvXLmFl135Txjb0GEfl5EhV2zvXB6PLMFscOa6SOioR

when I decode the base64 from mail.msg I can see informations that are in my certificate (certif.pem).
So it seems mail.msg contains a certificate which is NOT encrypted (is that right?) So how can I extract this certificate and how can I extract the true ciphertext that matches with my plaintext?

I thought the certificate in mail.msg was the same in certif.pem but the beginning doesn't match except the first three characters :

certif.pem : MIIC3DCCAkWgAwI...
mail.msg   : MIIBnQYJKoZIhvc...

so what is this certificate?

the following command do what I want :

openssl smime -in msg -pk7out -out msg.pk7
openssl asn1parse -in msg.pk7


Cryptography systems based on NP complete problems There is any cryptography system that have a good reputation based on NP complete problem?
I read about the knapsack, but it was cracked.

No, the problem is np-completeness or even np-hardness is a worst case thing. In crypto, we don't want our systems to be unbreakable only in the worst case. We want them to be unbreakable at least in the average case. It would be better if it were unbreakable in the best case (or all cases).

Another, related, issue we have is that of generating hard instances of the problem. NP-completeness does not guarantee that we can easily generate hard instances of the problem. Compare this with factoring where we can easily generate hard to factor numbers.

There have been a few other good, related questions on SE that you might find interesting:

Are there public key cryptography algorithms that are provably NP-hard to defeat?
Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems?

I won't summarize them here. They are definitely worth a read though.


Simple homomorphic crypto for 32-bit integers I'm looking for a simple way to perform homomorphic crypto on 32-bit integers. My only requirement is that I can add and subtract from the plaintext value without actually decrypting it. The crypto need not be particularly strong - the implementation is designed to be a deterrent rather than something more concrete.

Are there any simple algorithms to do such a thing? I'm looking for something that's easy to understand and implement.

It depends on what you mean by "32-bit integer". If you want to add integers which will never exceed the range -231..231-1 (i.e. integers which fit in 32 bits), then Paillier cryptosystem will be fine. It uses mathematics which can be viewed as "slightly complex" so you could also rely on a simpler ElGamal encryption. With ElGamal, you do not add; you multiply. So you would have to represent integer value x with value gx, and, upon decryption, you would have to solve the discrete logarithm, which can be done with cost about 216 if you are sure that the exponent resides in a 32-bit range (232 is low enough that this can practically be sped up a lot with precomputed tables; e.g., store hashes of all gy where y is a multiple of 212: you only need to store a million hash values, and you do the discrete log step in an average of two thousands multiplications and hashing).

If by "32-bit integer" you mean modular integers, which "wrap around" at 32 bits, then things become much more complex. You could choose the group parameters for ElGamal such that the generator g has order 232 exactly, but security would have been quite nullified in the process. It would deter only low-grade attackers who indiscriminately balk at mathematics.


Is there something similar to a Bloom filter that allows you to test arbitrary predicates on the set? As I understand it, if you have a Bloom filter that was generated from the members of a specific set, you can test whether a given bit string is in the set (with some given false positive rate). The idea I had would be to run more complicated predicates on the set, like being able to query whether "there exists a member of the set which is less than target t" using a similar kind of filter. Does such a thing exist and allow you to make these queries without having to have the entire set on hand? How do they work if they exist?

If you want to answer arbitrary queries, no there is nothing like this. Essentially encoding a set into a Bloom filter is a process of lossy compression so that you gain efficiency in space, but the price you pay is that the data structure can answer only a specific query, i.e. set membership. Other information might have been lost because for this query it is not important.

As such, if you have a specific query in mind, you may be able to design an alternative data structure that satisfies your requirement.


Is the seed/salt input of a Key Derivation Function confidential? I'm implementing a security protocol and for the key management a scheme is proposed using a key derivation function on the remote device. Thereby the input seed is uploaded in plaintext to the remote device.
Now if both entities share the same masterkeys and generate sessionkeys from these masterkeys and the seed/salt, they derive the same sessionkey.

Now the thing I don't understand completely is that the random seed should be generated with a crypto-safe random generator, but can be uploaded in plaintext to the remote device.
Is that true? And is that because from a cryptanalysis point of view, using a deterministic random seed would leak information about the masterkeys?
As this is part of a thesis I would appreciate any literature on this.

Thank you in advance

Now the thing I don't understand completely is that the random seed should be generated with a crypto-safe random generator, but can be uploaded in plaintext to the remote device. Is that true?

Yes. The salt is used to make sure that you do not generate the same device key twice. The session key however still depends on the master key, so an attacker cannot generate the device key.

So the device keys will be unique and secure. The random number generator needs to be secure to assure the uniqueness. You'll need to extract a relatively large salt for that (say, 128 bits or 16 bytes for as good as complete uniqueness or 64 bits in case you like playing on the edge) for that as well.

Using a device-specific unique identifier is more common. The advantage of a (large enough) salt is however that you do not need state. You cannot by - accident or otherwise - use a the identifier for two or more devices. Usually the salt is used in addition to other derivation data, if used at all.

  And is that because from a cryptanalysis point of view, using a deterministic random seed would leak information about the masterkeys?

No, no matter what, a KDF should never leak information about the master keys. This is why KDF's are generally either build on a block cipher - which of course protects the key - or a one-way hash functions / HMAC.

Notes:

I would use the word "salt" instead of "seed" here. If used at all when talking about KDF's, the seed is generally the input seed or key, not the salt or any other derivation data.
The HKDF RFC has a nice section on the use of a salt.
It is strongly recommended - I would even say required - to authenticate the device keys after derivation as an attacker could otherwise distort the salt value or set it to a constant value; for this generate a MAC authentication tag over data known by both parties and return it to the server, which can then verify the data.
Often multiple keys are required. Unless those keys rely on additional transmitted data you can use just the one key to authenticate the device; usually that's a MAC key or - even better - a separate key. Creating a set of device keys takes additional key derivation data, generally an ASCII label such as "MAC", "ENC" and "AUTH" or a number 00, 01 and 02.


What is the difference between PPE and SPPE? Can somebody explain, in simple terms, the difference between Pseudo Random Permutation Ensemble and Super Pseudo Random Permutation Ensemble?

An efficiently computable Permutation Ensemble is (Weakly) Pseudo-Random

if and only if it is infeasible for an adversary with oracle access to

[a function that was chosen either from then Ensemble or uniformly from

the set of all permutations on bit-strings of the corresponding length]

to distinguish between those two cases.

An efficiently computable Permutation Ensemble is "Super" (= Strongly) Pseudo-Random

if and only if it is infeasible for an adversary with oracle access to

[$\hspace{.02 in}$[a function that was chosen either from then Ensemble or uniformly from

the set of all permutations on bit-strings of the corresponding length] and that function's inverse]

to distinguish between those two cases.


Finding the AES key with access to the function Say an attacker has access to a non-rate-limited API that takes (IV, data) and outputsAES-CBC(key, input, data), with the key remaining on the server side. However, the attacker can pass any (valid) IV and data that they want in an attempt to recover the key.

Is there any optimal way to recover the key with such access?

No. What you have access to is called an oracle. It is an entity that encrypts or decrypts arbitrary data with a given secret key. A modern and secure block cipher like AES remains secure from key recovery even in the face of an encryption or decryption oracle. If it was not, the cipher would be considered fatally broken. The best-known way to recover the key with what you have is exhaustive search (brute force).