XTS mode with the tweak key as the sole secret The keyspace of XTS is $2^{512}$ due to its use of two distinct keys, and the most effective attack (a meet-in-the-middle attack) brings this down to $2^{384}$. This implies that knowledge of either the main key or the tweak key does not significantly reduce security. What confuses me is the idea that the scheme is still secure even if the main key is known and only the tweak key is kept secret. This idea I got from an answer to another question which notes that an attack revealing the main key but not the tweak key is not a fatal attack, leaving the scheme with a remaining $2^{256}$ keyspace. Looking at a diagram of XEX mode and trying to imagine how it would remain secure when $K_1$ is known, I could not think of any possible way it'd be true:

$K_1$ is the main key and $K_2$ is the tweak key.

XTS mode, sans ciphertext stealing, is defined as:

$$C_{ij} = E_{K_1}(P_{ij} \oplus (E_{K_2}(i) \otimes \alpha^j)) \oplus (E_{K_2}(i) \otimes \alpha^j)$$

Here, $i$ is the sector number and $j$ is the block number within the sector. For the purpose of this question, only one sector matters so $i$ can be considered a constant. Since this makes it such that $E_{K_2}(i)$ is a secret value that never changes, we can define $K^\prime = E_{K_2}(i)$, giving us:

$$C_{j} = E_{K_1}(P_{j} \oplus (K^\prime \otimes \alpha^j)) \oplus (K^\prime \otimes \alpha^j)$$

Because $K_1$ is not secret for our purposes, we can model $E_{K_1}$ as a public PRP $\pi$:

$$C_{j} = \pi(P_{j} \oplus (K^\prime \otimes \alpha^j)) \oplus (K^\prime \otimes \alpha^j)$$

If we simplify things and look at a single $j$, we can say $K^{\prime\prime} = K^\prime \otimes \alpha^j$. Now we have:

$$C = \pi(P \oplus K^{\prime\prime}) \oplus K^{\prime\prime}$$

This can't possibly provide data-at-rest security! It looks to me that knowledge of $K_1$ allows an attacker with a plaintext/ciphertext pair to easily derive $K_2$, which, according to the above-linked answer, is not true. Where is the error in my logic?

Actually, you can't remove the $E_{k_2}$ as you did. You had:

$$C_{j} = E_{K_2}(P_{j} \oplus (K^\prime \otimes \alpha^j)) \oplus (K^\prime \otimes \alpha^j)$$

Let me replace the term $(K^\prime \otimes \alpha^j)$ with $K^{\prime\prime}$ and eliminate the $j$ to makes things easier to read. The result is:

$$C = E_{K_2}(P \oplus K^{\prime\prime}) \oplus K^{\prime\prime}$$

This form is that of a type of Even-Mansour cipher. It is a block cipher formed with a public (pseudo-random) permutation $\pi$ and one or more keys with a length equal to the block length. It looks like:

$$C = \pi(P \oplus K_a) \oplus K_b$$

XEX mode uses the same construction to make a tweakable block cipher. In XEX the permutation used is not public. (It is  a block cipher with a secret key.) For an EM block cipher the permutation does not need to be secret. (Therefore you can use a block cipher with a non-secret key.) Its security claims just depend on the block size, the assumption that $\pi$ is a pseudo-random permutation, and that the keys are unpredictable and from a uniform distribution.

You cannot eliminate the $\pi$ as you did.

$$\pi(P \oplus K_a) \oplus K_b \neq (P \oplus {K_a}^\prime) \oplus {K_b}^\prime$$

Given plaintext ciphertext pairs:

If you omit $K_a$ then you can trivially recover $K_b$.
$$C = \pi(P) \oplus K_b$$
$$C \oplus \pi(P) = K_b$$

If you omit $K_b$ then you can trivially recover $K_a$.
$$C = \pi(P \oplus K_a)$$
$$\pi^{-1}(C) = P \oplus K_a$$
$$\pi^{-1}(C) \oplus P = K_a$$

If both keys are present, then the best attacks on a generic single round*EM cipher require about $D$ plaintext/ciphertext pairs (D for data) and $T$ evaluations of $\pi$ (T for time) such that $DT \geq 2^n$ where $n$ is the block size.

As for the question "So in essence, the output of $\pi$ will necessarily not be known because of the [correction: $K_a$] added to the input?"

Yes, basically. The exact behavior is a bit subtle and I don't want to cause confusion. So actually either $K_a$ or $K_b$ being unknown is sufficient to make the ciphertext impossible for the adversary to predict IF no plaintext/ciphertext pairs are known.

I actually mean $K_a$ added to the input of $\pi$ makes the new output of $\pi$, that is $\pi(x \oplus K_a)$, impossible for the adversary to calculate because the "real" input, that is $x \oplus K_a$, is not known by him.

If you skip the second XOR ($K_b$) then from one pair you can recover $K_a$ as described above using the inverse of $\pi$.

Similarly if have secret $K_b$ the adversary can compute $\pi^{-1}(x)$ but not $\pi^{-1}(x \oplus K_b)$. The adversary needs to know the difference between $E^{-1}(C) = K_a \oplus \pi^{-1}(C \oplus K_b)$ and $\pi^{-1}(C \oplus K_b)$ to recover $K_a$.

So you can't recover the pre-key ($K_a$) efficiently without knowing the post-key ($K_b$). You can't recover the post-key easily without knowing the pre-key. Both are essential. One protects the other from being recovered.

I hope that makes sense. I struggled to phrase it in a way that made sense without resorting to formal arguments. I will look for references later.

The claim that an EM cipher is secure may not pass the smell test, though. And that's because I forgot to emphasize that you can't actually make a claim to that their security level is equal to their key-size. $|K_a| + |K_b| = 2n$ but the worst case security level is $O(n / 2$) if measured in terms of $min(D + T)$. And you don't limit $D$.

It's better to use larger block ciphers or permutations for that reason. I recall reading using more rounds brings the security level closer to $n$ bits.

(If for some reason we lost the ability to use typical block ciphers we would be perfectly fine using only one round EM ciphers with a "standard" block size of 256 bits instead of 128. We also wouldn't need double the key bulk if we did this. The different subkeys can be generated by KDF. For the single round version there is no loss in security on the generic construct if the pre- and post-keys are equal.)

Also the symmetry of the construct makes informal reasoning a bit easier. Whatever logic applies to encryption or the forward public permutation function also applies to decryption and the inverse permutation function. ie.

$$E_1(P, K_a, K_b) \text{ corresponds to:}\\
\begin{align}
 X &= P \oplus K_a; \\
 Y &= \pi(X); \\
 C &= Y \oplus K_b
\end{align}$$

$$E_2(P, K_b, K_a) \text{ corresponds to:}\\
\begin{align}
 X &= P \oplus K_b; \\
 Y &= \pi^{-1}(X); \\
 C &= Y \oplus K_a
\end{align}$$

* Rounds in the context of EM ciphers refers to the number of times $\pi$ is used. One round is XOR → permute → XOR. Two is XOR → permute → XOR → permute → XOR. And so on.


CSPRNG's (ELI5) What's the purpose of multiple seeds/ regenerating sources of entropy (i.e. /dev/random)? Why is there a need to generate more than one high entropy seed? It would seem like if the original source of entropy is high quality, than some 512 bits should be more than enough to seed a CSPRNG which has no strong (or known) weaknesses, and pretty much endlessly generate new random numbers and re-seed itself. The average user needs very few cryptographically strong random numbers over the life time of a computer, almost surely (<106) will be enough for all of said users potential applications.

On the other hand reading about cryptographic RNGs / encryption as some one that deals with them occasionally in code, and knows a bit of math, (but not highly technical literature by any means), one gets a highly disjointed sense of what people consider correct seeding procedure, how often a seed should be re-used, /dev/random vs. /dev/urandom, etcetera.

Would re-seeding to generate some 106 random bytes really be enough to find a weakness in CSPRNG and in such a way as to make the original entropy source weak enough to regenerate it with a human lifetime?

I'm not sure if this is more of a Math Stack Exchange or Stack Overflow question. But I would really like to see some mathematically / logically convincing guidelines. I can reference some specific CSPRNGs (but I'm not sure whether that helps or hurts the discussion).

Check out NIST SP800-90A.

8.6: Seeds

  Reseeding is a means of restoring the secrecy of the output of the DRBG if a seed or the
  internal state becomes known. Periodic reseeding is a good way of addressing the threat of
  either the DRBG seed, entropy input or working state being compromised over time. In
  some implementations (e.g., smartcards), an adequate reseeding process may not be
  possible. In these cases, the best policy might be to replace the DRBG, obtaining a new
  seed in the process (e.g., obtain a new smart card).

8.6.8: Reseeding

  Generating too many outputs from a seed (and other input information) may provide
  sufficient information for successfully predicting future outputs (see Section 8.8). Periodic reseeding will reduce security risks, reducing the likelihood of a compromise of the data that is protected by cryptographic mechanisms that use the DRBG.

But also:

9.2: Reseeding a DRBG Instantiation

  The reseeding of an instantiation is not required, but is recommended whenever a
  comsuming application and implementation are able to perform this process. Reseeding
  will insert additional entropy input into the generation of pseudorandom bits.

It depends on the random number generator if a reseed is necessary. For hash based algorithms, the time before the algorithm hits the same state is very high, so reseeding is certainly not directly required for that reason.

NIST specifies 2^48 calls as maximum to DRBG (e.g. 10.1, table 2) before the DRBG should be reseeded. Even if you take just one bit, then this would still be more than 10^6 that you mention. This is for the hash and AES based algorithms. The number of calls to the 3DES and Dual_EC DRNG's is much lower though, so in the end it depends on the DRNG in use.

Note that stating that 10^6 of random numbers is enough for anyone is like stating that 64 KiB is enough for anyone. I would not make that statement in the same way that Bill didn't.

Reseeding should not have to happen very often if leakage of the state can be avoided (beware of side channel attacks). Saying that it should never happen is however taking it too far. That said, if my computer wouldn't reseed for a week, I would not loose any sleep over it.


Attacking historical ciphers methodology It's more a theoretical question of how would you approach it. All you know about the ciphertext it's was generated with a historical cipher. The ciphertext appears to be random, BUT it's divided into sets of six letters. By historical ciphers I mean: mono (Ceasar), polyalphabetic (Vigenere), homophonic or polygraphic ciphers (Playfair, HillCipher).

I interested what methods would you use (Kasiski, Friedman, what else) and why and in what order to make the attack the most efficient (Friedman first?)

If you don't know the system, you just check one after the other:

frequency analysis of bigrams detects Ceasar and Playfair. Try Caesar first then Playfair.
Auto correlation method for Vigenere (for each x: count the number of occurances, where letter at position i and i+x are equal. For the correct codeword length, it will spike)
If you have a Hill cipher, you lost.


Is the GOST block cipher broken? Is the GOST cipher broken or known to be weak and insecure? Please try to simplify your answer since I am a programmer and not a cryptographer and please consider this web page and tell me if the claims made there are true.

There are two ways a cipher can be broken: theoretically and practically. If the paper is correct then:

  Our fastest attack achieves a nearly feasible $T=2^{101}$ (cf. Section 28.6 and [28]). (emphasis mine)

If we verify this claim then we get:

  If we have a diverse population of at least $2^{79}$ diﬀerent 256-bit GOST keys generated at random, with access to $2^{32}$ CP per key, one can recover one of these 256-bit keys in total overall time of about $2^{101}$ GOST encryptions.

Now theoretically a cipher is broken if there is an attack that is (significantly) faster than brute force. Simply said, $2^{101}$ is a darn amount better than $2^{255}$ required for brute force. So if this claim is correct then the theoretical security of GOST is much lower than it is supposed to be. Hence it could be called broken.

Of course, nobody is going to invest that amount of memory or processing power to even prove this point. SHA-1 has a much lower effective security margin and it took a very long time before a collision could be found.

Given the structure of the paper I would say that it's likely that the claims are correct. That doesn't mean that anybody can now attack GOST. It does show that too many kinds of attack are possible. These kind of attacks will only get stronger. This is a clear indication that it would be wise to upgrade. The block size of 64 bit is also a good reason to upgrade, 64 bit is considered on the low side for many applications of block ciphers.

That all said, these specific cryptographic attacks can not be used to attack any well designed / implemented protocol that makes use of GOST. 101 bit security is generally thought to be out of reach, i.e. the "nearly feasible" in the text.


Difference between XORing the IV and just pre-pending it to the plaintext before encryption with AES-CBC The normal way of using AES-CBC is to XOR the IV with the first plaintext block

This way you have to pass the IV along the ciphertext.

What if instead of XORing we just put a fixed size randomIV in front of the plaintext:

Encrypt(randomIV + plaintext) = C1

And we don't have to send/tansmit separatly the IV since it is inside C1.
Decryption works similarly:

Decrypt(C1) = randomIV + plaintext

And we just remove the randomData (fixed size) to end up with the plaintext.

In essence, the first block of random data, when encrypted will work EXACTLY as a randomIV since it will be XORed with the second block

Except from performance loss (having to encrypt an additional block instead of XORing), can you think why this might not be secure.

If I got you right, you propose to encrypt IV and then run the same CBC-mode encryption using the encrypted IV; it just gives an adversary one more ciphertext block.


One Time Pads and reuse of the decrypted message? How is it insecure when Alice encrypts a message with a One-Time-Pad to Bob, and Bob then uses the decrypted message from Alice as the next One-Time-Pad?

For example: Alice sends Bob a message Hello World with the Key of Orange Fish which they both shared earlier. Vvlyu Atzdk (Hello World). Then Bob uses Hello Word (which he decrypted with Orange Fish) as the key for the next message.

If Bob’s message back to Alice Hello Alice encrypted with Hello World to Oiwwc Wzznh (Hello Alice). I’m sure this is detectable, but I’m curious how it could be broken.

First things first: what you are describing there is not a one-time-pad!

As I explained in another answer of mine:

  Per definition, OTP requires the “key“ to be…

  a truly random one-time pad value,
  generated and exchanged in a secure way,
  at least as long as the message, and
  only to be used once.

What you describe (eg: using a key going Orange Fish) can merely be compared to a simple, keyed substitution cipher with security boundries comparable to a regular Ceasar cipher. Differently worded: your encryption technique is no where near the cryptographic security a real one-time-pad can provide.

Now, to the core of your question: if Bob would base his key on the plaintext of what Alice send him, you would practically be creating a ciphertext by combining two plaintexts (which should actually remain secret).

To attack such a simple “cipher“, an attacker could simply exploit the statistical bias coming from the fact that both the key as well as the ciphertext are regular, human language. Letter frequencies et al would quickly help differring the key from the plaintext. The fact that the space character doesn’t even get encrypted, makes it even easier to recover the plaintexts. The result of using such an “encryption“ would be that an opponent would quickly be able to successfully attack it, and recover both the message Alice tried to secretly send to Bob, as well as the message Bob secretly tried to send to Alice as a reply.

Simpler said: your idea incorporates more than the usual danger of leaking a single secret… because it practically risks the leaking of two secrets: the plaintext which is being send, and the previously received plaintext which is reused abused as key to encrypt the plaintext to be send.

As for an example of the cryptanalytic side of things, I’ll refer you to this question and its accepted answer, as they provide a lengthly and indeep insight on how one could extract a keyword from a keyword cipher – including a practical example. When reading that Q&A, keep in mind that your “algorithm” may seem similar, but actually is much simpler and incorporates more insecurities than what they are talking about there.

Long story short: the fact that Bob and Alice are risking to leak both their secrets twice is pretty inacceptable from a cryptographic point of view. Yet, I am sure every potential attacker will be more than happy when you allow him to gain a complete transcript of your communication in such an simple way; especially since you are including all those nice carbon-copies of the plaintext, which are (ab)used as keys.

Honestly, if I were a cryptanalytic opponent facing your idea in a practical situation, I’ld probably put you on my Christmas-card list for providing me with one of the easiest and most amusing jobs ever.


How can I prove I'm the recipient of an encrypted message without revealing my identity and the message? Alice wants to leave a message for Bob. So she encrypt a signed message with Bob's public key.

Then leaves it at a dead drop service.

Then later Bob arrives and checks the messages and attempts to trial decrypt all of them to see if there are any addressed to him.

When Bob finds Alice's message, he manages to decrypt and read it.

However in order to avoid the vandalization of the dead drop, he can only remove the message from the dead drop if he can prove he is indeed the recipient.

Is there a way to do that without revealing the message and his identity?

One possible approach to this may use a commitment scheme.

That when Alice deposits the message $m$, she signs $m$ resulting in the signature $\sigma$, then she picks a (eg 256-bit) random string $r$ and encrypts $(r,m,\sigma)$ into the ciphertext $c$. Now she creates a commitment $\rho$ (eg a SHA-256 hash of $r$) for $r$ and publishes $(\rho,c)$ at the dead drop.

When Bob retrieves the message, he decrypts $c$, yielding $(r,m,\sigma$) and then opens the commitment (e.g. presenting $r$ such that $H(r)=\rho$) to the operator, who can now know that Bob was indeed able to decrypt the ciphertext. But because $r$ is a random string it doesn't leak anything about $m$.

Of course, while this solution works, it assumes that Alice is actually "honest" and doesn't encrypt something without also leaving the solution to the commitment behind (and thus taking up space that can never be reclaimed). Of course it depends on your concrete situation whether this suffices or whether you want a more sophisticated scheme (of which there some I think).


Generally accepted standard(s) for key managment? I am using an application of which in its privacy policy it has been stated the they use generally accepted standards to protect data. They encrypt data on their servers.

So, what is/are the "generally accepted standard(s)" for key management?

There are some agreed as universal, but then some might disagree it's generally accepted:

ISO 27001/27002 land, as it's generally accepted standard for data protection, too. It has a section on key management, based around bloody obvious goals: cryptographic keys have to be protected against modification, loss, destruction and leakage. It requires system to have certain procedures around key management:

key generation
certificates of public key generation
key distribution/activation procedures
key storage and authenticated key access
key change procedure
working with leaked keys, key revocation, etc.
business continuity goals (what if revoked keys protected unique data)
... I certainly forgot something here, haven't touched the standard in years, but aforementioned procedures are really important even outside ISO formalism.

NIST has this beautiful document, which can be accounted as a standard in some circles.
Some time ago, I've been asked to write a novice-friendly blog post about typical key management procedures you modern app developer may want to understand. It also somehow outlines the generally accepted standard measures for key management and protection, yet I've tried to make explanations as simple and accessible as possible.


Find Lower bound on key space with relaxed definiton of perfect secrecy Consider a relaxed definition of security. Let $\epsilon < 1$ be a constant and say we only require that for any distribution over $M$ ,any $m \in M $, and any $ c \in C$

$$
|Pr[M=m|C=c] - Pr[M=m]| < \epsilon
$$

I want to find a lower bound on the size of key space $K$ relative to $M$ for any encryption scheme that meets this definition.

I believe that this 'relaxed' definition gives the same minimal key length as the standard perfect security definition; that is, the number of keys $|K|$ must be at least as large as the number of possible plaintexts $|P|$.  This is true for any $\epsilon < 1$.

Suppose we had a set of keys that was smaller than the number of plaintexts, or $|K| < |P|$.  In that case, we pick a possible ciphertext $c$ and see that can be decrypted to at most $|K|$ distinct plaintexts (depending on the key); hence there must be a plaintext $p_0$ that it cannot decrypt to.  Let us call plaintext $p_1$ a plaintext that it can decrypt to.

Then, consider the probability distribution:

$M = p_0$ with probability $\epsilon$

$M = p_1$ with probability $1 - \epsilon$

$M$ is any other plaintext with probability 0

If we consider the equation with $m = p_0$, we have:

$Pr[ M = m | C = c ] = 0$ (because that plaintext is impossible with that ciphertext)

$Pr[ M = m ] = \epsilon$

And hence $|Pr[M=m|C=c] - Pr[M=m]| = \epsilon \not< \epsilon$, and so we find that the required inequality does not hold.

Hence, that relation can hold in general only if $|K| \ge |P|$, which is the same bound as what perfect secrecy requires.


RFC 3526 - What does pi mean? In RFC 3526 there are a series of primes listed as standard parameters used for Diffie-Helman. The primes are list in two formats. One is the long format, where the number is given in hex. For example:

  FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
  29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
  EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
  E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
  EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
  C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
  83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
  670C354E 4ABC9804 F1746C08 CA237327 FFFFFFFF FFFFFFFF

Then they have the short hand version:

$$2^{1536} - 2^{1472} - 1 + 2^{64} * ( [2^{1406} pi] + 741804 )$$

Obviously, the short version takes less space in code. The question is: how do I interpret it? What is the meaning of the $pi$ term in the square brackets?

$\pi$ is the transcendental number 3.1415926...

It's there in the formula to show this specific number was not chosen with a specific cryptographical backdoor in mind; it seems unlikely that anyone was able to select the value of $\pi$ (unless Carl Sagan was correct, of course :-)


Applicability of IBM's projected 50-qubit quantum computer Q to cryptanalysis? IBM announced Q, a project for a 50-qubit universal quantum computer, according to the press realease. Here is more PR spin, and the research sub-page.

What would be the applicability of that to cryptanalysis?

What would be the applicability of that to cryptanalysis?

It wouldn't appear to have any direct applicability to cryptanalysis, for two reasons:

50 Qbits is just not enough to attack any cryptographical problem; to apply either Shor's or Grover's algorithm against any realistic problem, you'll end up needing thousands.
It doesn't appear that they're addressing the decoherence issue.  That is, in a quantum computer, you'll end up getting random perturbations to the running state.  Cryptographical computations take quite a long time (far longer than we can go without expecting such a random event to occur), and are quite sensitive to such perturbations.  What they'll need to do is run error correction logic (which has multiple physical qbits stand for the one logical one, and has logic to detect such a perturbation on one of the physical qbits, and correct it).

Now, I'm not saying that what IBM is trying to build is useless; for one, it would appear that the computations that Chemical modeling requires fits nicely into what they have.

And, while this isn't immediately useful for cryptography, it is another step towards a Real Quantum Computer (where "Real" means "can actually solve an interesting cryptographical problem).


Certificate public key keyexchange, Which key exchange is used in browsers? I have a question regarding the keyexchange happening in web browsers. If you check the certificate here on crypto.stackexchange you can go under details and see that the public key is type RSA (2048 Bits). Does this mean that StackExchange is generating a private key via RSA between them and me to encrypt my messages?

The RSA encryption algorithm implies two types of keys: a public key and a private key. The public key is composed from the public exponent $e$ and modulus $n$. The private key is composed from the private exponent $d$ and modulus $n$. The relationship between them is $(e,d)\ ≡\ 1\ (mod\ φ(n))$. To encrypt, you rise the plaintext to the power $e$ and to decrypt you rise the ciphertext to the power $d$ (both operations are done modulo $n$). More detalis here. The traffic between you and StackExchange is encrypted under the TLS protocol. The TLS protocol uses a hybrid encryption scheme. That is, you first generate a random key, say K, that you'll encrypt with RSA using the public key of StackExchange. The StackExchange will decrypt the key K using its private key.
From now on you will both use a symmetric algorithm (AES 256) to encrypt your data. The encryption key for this symmetric algorithm will be the K key, which you previously encrypted using RSA. More detils about TLS here.


Cryptography used for login and signing transactions My bank uses a smartcard reader (separate module not connected to the computer) as depicted below:

When I need to log into my account it provides me with a challenge and  I need to provide some details:

I need to provide the 8 digits, enter my pin and then it returns an 8 number sequence which is then to be entered after which you are logged in.

A similar mechanism is employed for signing transactions but using the M2 button (blue one) rather than the M1 and instead of a random number you need to first give the amount and then the timestamp. I'm interested in the cryptography used behind it (if it's symmetric, assymetric or a combination of both) and how the signing is actually done.

a user guide can be found here.

While I am not familiar with this particular device or bank, this looks a lot like Chip Authentication Program (CAP)

It's fairly standard in the UK, where banks use this to authenticate initiating a bank transfer to a new recipient. There is a python implementation (for study - it's obviously a bad idea to actually use this, as it would permit your PIN to be captured by malware on your local PC) available at http://sites.uclouvain.be/EMV-CAP/Application/

As I understand the protocol, your smartcard is used to sign a "cancel transaction" request using a shared MAC key (the key being securely stored on the smartcard). There is more information on the protocol at the wikipedia page: https://en.wikipedia.org/wiki/Chip_Authentication_Program#Protocol_details


Why doesn't this dummy mutual authentication protocol provide mutual authentication? I am a student taking a cryptography course so forgive me if this comes off as a silly question.
This is an assignment question:

  $Alice \rightarrow R \rightarrow Bob$
  $Alice \leftarrow [R]B \leftarrow Bob$
  $Alice \rightarrow [R+1]A \rightarrow Bob$

  Why doesn't this protocol provide mutual authentication?

Here's a plausible scenario:

Alice sends $R$. Trudy intercepts it and sends it to Bob impersonating Alice. Bob sends back $R$ signed by him to Trudy. Trudy now impersonates Bob and sends $R$ with Bob's signature to Alice impersonating Bob. Alice sends $[R+1]$ signed by Alice which Trudy can now use to impersonate as Alice to Bob.

If that is a valid attack. Wouldn't this work with every protocol? After all we're merely just relaying message back and forth among the two parties.

I think you've got all the right ideas but I think you're lacking an understanding about how Public Key Cryptography works.

Trudy can only impersonate Alice in this scenario with a replay attack (or if some kind of authentication credentials are returned...like an http cookie, Trudy could steal that too). Since she does not have Alice's private key, she can only successfully respond to Bob's challenge by waiting for Alice to respond and stealing response. In this simple scenario, Bob will be unable to tell if Trudy sent the message or if Alice did.

In reality, Bob and Alice have everything needed to create a secure protocol. Because Bob and Alice have the capability to verify the message was sent (using eachother's public keys), they can also encrypt messages only the other can decrypt. Bob can sign his challenge he has generated, encrypt this using Alice's public key, and then send it all to Alice.

Alice then decrypts, verifies Bob sent it using his public key, and can generate the response, sign it, and encrypt the same way Bob did.


"NP-complete" authentication systems Are there any symmetric authentication systems based on the hardness of an NP-complete problem? I understand that it doesn't really matter, since NP-completeness is about the worst case, and in crypto we care about the average case, but I still feel it's somewhat interesting...

You could use the turtle block cipher with CMAC, maybe.

The turtle block cipher claims a cipher design that is based on "an NP-Complete Subproblem".

Block ciphers can be used to produce authentication tags via algorithms such as CMAC.

I'm not sure if this combination necessarily qualifies the authentication as being based on an NP-Complete subproblem too.


Do I have to recompute all hashes if I change the work factor in bcrypt? The well-known article about why we should use bcrypt for hashing passwords mentions the work factor - some parameter to the algorithm that determines how long one hashing should be in terms of number of computations. This as the article says allows for keeping up with Moore Law - when we have faster processors in the future we just increase the work factor and continue using bcrypt.

One question arises - if I use bcrypt and want to increase the work factor the do I have to recompute all hashes? If so - how do I do that if I'm not supposed to store plaintexts? If I don't need to recompute them - how will the function with greater work factor deal with passwords hashed with smaller work factor?

To increase the work factor, there are three approaches you could take:

Rehash all passwords immediately, continue the same hash

Take the hash currently stored in the password file, and hash it a few more times.
We may (see below) be able to do this immediately with every entry in the password file.

Example: let's switch from a work factor of 10 (i.e., hashed 2^10 times) to the same hash function with a work factor of 11 (hashed 2^11 times).
To do that, we pull the old hash value from the password file -- that has already been hashed 2^10 times -- and use the same salt to hash it another 2^10 times to create the new hash value, and replace the old hash with the new hash.

Then we somehow tell the "login" program and the "passwd" program (or the equivalent), instead of using a work factor of 10, they now need to use a work factor of 11.

See "Is it possible to increase the cost of BCrypt or PBKDF2 when its already calculated and without the original password?"
for more discussion of this approach.

Alas, in some cases you can't simply "continue" to hash like this -- say, you want to switch to a completely different hash algorithm, or you want to change the salt,
or your current hash function has a "setup" or "finalize" step that interferes with "continuing" to hash like this.

Rehash all passwords immediately, without continuing the old hash

Take the hash currently stored in the password file, and hash it a few more times.
We can do this immediately with every entry in the password file.

Example: let's switch from MD5 (hashed once) with a 3-character salt, to bcrypt with a work factor of 11 (i.e., hashed 2^11 times) and a fresh 32-character salt.
To do that, we pull the old hash value from the password file, and replace it with a new hash value:

new_hash = bcrypt( old_hash, new_salt, work-factor=11 ).

Then we somehow tell the "login" program and the "passwd" program (or the equivalent) to use this somewhat awkward hash function:

bcrypt( MD5( password, old_salt ), new_secure_salt, work-factor=11 )

See
" Is this password migration strategy secure? "
for more discussion of this approach.

Rehash passwords one at a time, as people log in

Many UNIX-like systems are already set up so the sysadmin can change the "preferred" password algorithm, work factor, and salt length at any time.
Later, whenever a user logs in by typing their password, the system updates that user's row in the passwd file to use the system's current "preferred" work factor etc.
See a, b, c, d, e, f, g, h, i, j, k, L, m, n, o for how to tweaking the appropriate configuration file in order to set the "preferred" algorithm etc.
Typically this involves pluggable authentication modules (PAM).

Many passwd files (or thier equivalent) store, for each user,
not only the the salted hash,
but also the user-unique salt, the ID of the hashing algorithm used, and the work factor
(often dollar-sign delimited).
That allows us to gradually switch to a completely different password hash algorithm and salt width.

details:

For example, let's say we want to switch from inadequate amounts of salt and some obsolete hash to bcrypt with a work factor of 11.
The sysadmin sets the "preferred" algorithm, salt, etc. to "bcrypt with a work factor of 11", etc.

The next time a user logs in, resets their password, or changes to a new password -- i.e., uses the login or passwd programs -- those programs:

1) Hold on to the plaintext password the user typed in for a few moments.

2) Check the passwd file to see if that user's hash already uses the latest algorithm, work factor, and salt width. If so, continue with 4.

3) Authenticate the user with whatever old, obsolete algorithm the passwd file indicates for that user. If successful, additionally create a unique new salt with the latest salt width.
Run that salt, and the plaintext password that we're still holding on to, through "bcrypt with a work factor of 11" (or whatever today's preferred algorithm is) to get the new hash.
Update the passwd file for that user with the new hashing algorithm ID, the new work factor, the new salt, and the new hash.

4) Authenticate the user with the shiny new algorithm the passwd file indicates -- the latest algorithm, work factor, and salt width.

5) Then the server must forget the plaintext password.

After a month or two, if some rows of the passwd file still indicate some old, obsolete hashing algorithm and work factor -- i.e., those users haven't logged in for a month or two since you made the change -- you might send them a mail or call them on the phone and ask them nicely to log in soon.

After a few months, if there's still some user whose row of the passwd file still indicate some obsolete algorithm -- i.e., that user hasn't logged in for months -- perhaps you could reset that password and generate a new random unguessable password, more-or-less the same as if that user had forgotten the password and gone through the normal "I forgot my password" process.
If the user ever comes back, go through the normal "I forgot my password" process again to reset the password back to whatever the user wants to use.

See "Migrate old md5 passwords to bcrypt passwords"
for more discussion of this approach.

further discussion

"How to upgrade a password storage scheme (change hashing-algorithm)"
has some discussion of both the "Rehash all passwords immediately, without continuing the old hash" and the "Rehash passwords one at a time" options.

All of the above approaches have the advantage that your users can continue to use the same password -- it's a "transparent upgrade".
Alas, that means they all have the same flaw:
If any of your users was using a short or otherwise easy-to-guess password,
and then the bad guys somehow get their hands on old server backup tapes (you do make backups, right?) that contain the old, easy-to-crack hashes,
then the bad guys could use one of several infamous utilities to discover those easy-to-guess passwords -- passwords which will still work just fine after any of the above approaches.

The knee-jerk response of some system admins is to force your users to change their password every 90 days to one that is significantly different from any previous password they've ever used this year, and this time reject proposed new passwords unless they jump through a bunch of unnecessary hoops to make the password strength checker happy.


Why is a Feistel network bijective? EDIT: Fixed for clarity of intention

I was reading "The FFX Mode of Operation for Format-Preserving Encryption" when I came across Figure 1 (see below). It's obvious why it's reversible (top-down then down-top) but it's not clear why it should strictly be bijective instead of not-injective or not-surjective? What rules out the possibilities of collisions or skips that make it strictly one-one in both directions?

For example: The round function (Fk) can be block cipher or hash based and we pick a subset of output bits into the next round. A collision at say, Fk(n,T,0), in round zero would then map two inputs at the top to a single input at the bottom. Why is that not an issue? Sorry if I'm missing something but it's been a long night and have missed my morning coffee.

Example Feistel network from FFX paper:

why it should strictly be bijective instead of injective or surjective?

Actually, it is injective and it is surjective; the term bijective just means that it satisfies both the properties of injectivity and surjectivity.

Injective does not mean that there is a 'skip' (that's "not surjective"); instead, it states that no two different inputs give the same output; that is, if $a \ne b$, then $F(a) \ne F(b)$.  This follows immediately from the reversibility (invertibility) of the function; if we did have two different inputs that gave the same output, then we couldn't invert the output to get the input.

Similarly, surjective doesn't mean 'has collisions' (that's "not injective"), instead, it states that every output is possible, that is, for every $x$, there is an $a$ with $F(a)=x$.  This can be shown by noting that the size of the input and the size of the output are the same, and that they are both finite.  As each output has a unique input, then by the pigeon hole principle, every output is possible (because every input is possible).

The above conversation was about functions; now, FFX is a keyed function.  What this means is that FFX, with a fixed key, is a bijective function (because it is both injective and surjective).


How do quantum key distribution systems tolerate noise? It seems to me that any noise in the signal would result in Alice and Bob generating different keys, without a simple way to tell the difference.

How do quantum key distribution systems tolerate noise?

That question is essentially A.1 of this lengthy post, with some elements of answer in B.1

For your convenience, here’s quoting those specific sections of his linked answer:

  A. Issues prevent direct use of sifted bits

  …

  Errors creep in the sifted bits

  The many imperfections of the model (heavily simplified compared to the actual hardware and the known laws of quantum physics, even at the time the [article][2] was written) are such that, without Eve messing, sizably many sifted bits differ at Alice's and Bob's end. Sifted bits are thus unusable as key to a [cipher][3], for decryption would likely fail.

  …

  B. Classical cryptography rooted in information theory fixes them all

  Secret-Key Reconciliation protocol remove errors, and more

  Coding theory and error detection and correction are used to build a secure Secret-Key Reconciliation protocol additional to sifting, also running over the classical channels. Its objectives are to

  remove or fix errors in the sifted bits, with bounded low odds of the contrary;
  obtain an upper bound on the actual error rate, which is attributed to Eve spying the quantum channel;
  obtain and minimize an upper bound on the information leaked by running the protocol over the classical channels, that Eve is assumed to scrutinize;
  deduce a lower bound of what entropy (if any) remains in the rest; if there is less than some headroom, QKD failed.

  Such reconciliation protocol can loose little-enough entropy as to be usable in practice, and be information-theoretically provable; but no simple such one is known. A most scrutinized milestone is the cascade protocol in: Gilles Brassard and Louis Salvail's Secret-Key Reconciliation by Public Discussion, in proceedings of Eurocrypt 1993.

  …


How are calculated numbers in AES S-box? I have a problem calculating the 0x02 value of the AES S-Box.

I followed the steps descibed in “How are the AES S-Boxes calculated?”, but my answer is not correct.

0x02 is 00000010

Input = 0  0  0  0  0  0  1  0 (LSB First)
Row 0 = 1  0  0  0  1  1  1  1
Bit 0 = 0  0  0  0  0  0  1  0 = 1

Row 1 = 1  1  0  0  0  1  1  1
Bit 1 = 0  0  0  0  0  0  1  0 = 1

Row 2 = 1  1  1  0  0  0  1  1
Bit 2 = 0  0  0  0  0  0  1  0 = 1

Row 3 = 1  1  1  1  0  0  0  1
Bit 3 = 0  0  0  0  0  0  0  0 = 0

Row 4 = 1  1  1  1  1  0  0  0
Bit 4 = 0  0  0  0  0  0  0  0 = 0

Row 5 = 0  1  1  1  1  1  0  0
Bit 5 = 0  0  0  0  0  0  0  0 = 0

Row 6 = 0  0  1  1  1  1  1  0
Bit 6 = 0  0  0  0  0  0  1  0 = 1

Row 7 = 0  0  0  1  1  1  1  1
Bit 7 = 0  0  0  0  0  0  1  0 = 1

LSB is 11100011, MSB = 11000111, than (XOR) to the final vector 0x63,
the result is 0xa4, but it should be 0x77

What am I missing or what might I be doing wrong?

You forgot to compute the inverse of 02 first. The inverse of 02 is 8d (as $02 \cdot 8d = 01$ in the AES $GF(2^8)$ representation). You then apply the affine transform to the value 8d.


What form of ECC can we use to make sure our newly invented ECC based crypto-systems are quantum secure? It seems a lot of crypto-systems that are based on elliptic curves are susceptible to quantum computing attacks.

Hence, what forms of ECC cryptosystems are quantum secure, and how can we prove that?

Is there any good place to start with ECC (before moving on to different adaptations of ECC)? I have seen some resources but the math behind those papers seems very confusing, I don't even know what kind of math it is.

Traditional Elliptic Curve Cryptography (working in the group of points on an elliptic curve over a finite field) is vulnerable to an attack by a quantum computer running Shor's algorithm and is thus not considered a Quantum-Safe.

However there is a true Post Quantum Key Exchange algorithm which uses the mathematics of elliptic curves and is considered secure by experts who have studied it so far. This key exchange is known as Supersingular isogeny key exchange.


RSA: Probalistic algorithm to compute $x$ from $y$ and $(n,e)$ with probability $\epsilon>0$ given set of weak ciphertexts? Suppose there exists a set of ciphertexts $S \subset Z_n^*$ of size $\epsilon (p-1)(q-1) $ for $\epsilon>0$, that is easy to decrypt, i.e. there exist some algorithm $A_1 : \mathcal C \rightarrow \mathcal P \cup \{\text{void}\}$ that given ciphertext $y \in S$ and public key $(n,e)$ outputs correspoding plaintext $x$ and otherwise returns $\text{void}$.

I want to create a probalistic algorithm $A_2$ that given ciphertext $y$ and public key $(n,e)$ returns corresponding plaintext $x$ with probability at least $\epsilon$.

In the textbook a hint is given: Use $A_1$ as a subroutine and the RSA multiplicative property $$e_K(x_1x_2 \bmod n) = e_K(x_1)e_K(x_2) \bmod n$$

I've already proven that if $y\in Z_n \setminus Z_n^*$ then the secret key $(n,d)$ can be computed easily, which in turn yields the ciphertext $x$.

However, I'm stuck in the case $y\in Z_n^*$.

I've tried to consider how to split $y$ into prime factors $\prod_i p_i$, and then use the RSA multiplicative property, but this gets me nowhere.

Also, I've tried to consider picking plaintexts (or ciphertexts) at random, and then see if the product of their encryption their yields $y$.

Note:

For $y \in Z_n^*$, I cannot simply run $A_1$, because then the probability of returning $x$ would be $0$.

Let $d_k$ denote decryption and $x = d_K(y)$. I further assume that $\epsilon < 1$.
First note that $A_1$ calculates a randomly chosen cipher text $y$ with probability $\epsilon$.
But the task is to construct a probabilistic algorithm $A_2$ which decrypts a fixed cipher text $y$.
Therefore, proceed as follows:

choose a random $r \in Z^*_n$
calculate $y' = y* e_K(r)$
Use $A_1$ to decrypt $y'$ to $x'$
calculate $x = r^{-1}*x'$

This algorithm calculates the decryption of $y$ with probability $\epsilon$:
 - In step 2, $y'$ lands with probability $\epsilon$ in $S$
 - In step 3, the calculation yields
$$x'= d_k(y') = d_k(y*e_K(r)) = d_K(y)*d_K(e_K(r)) = d_K(y)*r = x*r$$


What is standard email encryption practice? So I've recently got an email client set up with an encryption plugin, but I'm not sure what's happening behind the scenes.

What I haven't been able to find anywhere online is what is the standard way to encrypt emails? Do I encrypt with my private key, then your public key? The other way around? Do I encrypt with your public key, then sign with my private key? There's so many different options, and I can't seem to find what people consider the 'standard'.

While setting up the plugin, it automatically detects my keys stored with GPA and associates those with email addresses. I can also import keys from keyservers for contacts. However, if I email someone that I don't have a public key for, it warns me and wants me to download their public key before proceeding, so I know that it is using it in the encryption process.

If I were to encrypt a message by hand, ie using GPA, what steps would I need to take?

Step 1: Generate your key pair
First you would generate your OpenPGP key pair e.g. with gnupg. The key generation format of pgp keys is complex, but you should know that the key pair consists of a public key, which is used by the sender to encrypt for the recipient(you) and the private key, which is used by the recipient to decrypt the message.
Step 2: Share your public key and collect public keys
In the next step a sender needs the public key of every recipient. To do this step, you can give your public key to the other person using an usb stick or you upload it to a public key server.
You also collect the public keys of users you want to send encrypted mails to.
Step 3: Encrypt and send message
You write your message and encrypt it for the recipients.
You might also sign the message, which guarantees that the recipient can verify that the message has been created by you. After the encryption you send the message to the recipients.
Step 4: Decrypt message and verify signature
If you recieve a message you decrypt it and if the message is signed, you verify the signature to be sure the message is sent by the sender to whom you have the public key.
Overview: Encryption process
If you encrypt a symmetric session key is generated. With this session key your message is encrypted. After the message encryption is completed you encrypt the session key with the public key of the recipient. After that you can optionally create a hash of the encrypted message and sign this hash with your private key, this is called a signature.
After these things are done the message gets saved in the OpenPGP format.
Notes:
This is a simplified answer, which does not exactly match all details of openPGP e.g. there is an encryption key pair and a signing keykey pair, but it should give you a general overview about how hybrid encryption works and openPGP works.


New to cryptology, studying key exchange I'm just getting an overview of some of the concepts in key exchanging at the moment, and I'm a bit disoriented on a few topics, namely key stretching, key derivation functions and perfect forward secrecy.

Regarding key stretching, I understand the idea is to make it more difficult to brute-force a password, but the materials I'm reading come a bit short on any kind of technical explanation.  The wikipedia article makes it sound like all it does is feed a plain text passphrase through a hashing algorithm.  If that's so, why differentiate between hashing and key stretching?  Does a salt count as a method of key stretching?  What are other methods?

About key derivation function, I understand the whole thing that there is a master key and session keys are derived from that.  But what is the specific application of key derivation?  Is it closer to key agreement (Diffie-Hellman) or key exchange (PKI)?  Can you cite a real-world example where I might encounter key derivation? (For instance, I know that if I wanted to secure a tunnel through IPSec, I might use IKE, which means I'd be dealing with Diffie-Hellman, which is key agreement.)

I think I'm pretty well grounded on Perfect Forward Secrecy; it's basically the diametric opposite of key derivation.  But I'm hazy on the difference between Forward Secrecy and Perfect Forward Secrecy.  What exactly changes the situation from FS to PFS?

I know these must be very basic questions for this forum, but I'm just getting my feet wet in the world of cryptology.

Key stretching usually means using a Password-Based Key Derivation Function (PBKDF), these are designed to be more resource intense than standard hashing, which is designed to be as fast as possible. A salt is used to prevent that two derived keys are differentely so that you'd need to brute-force each password independentely.
Usually you derive a key from a master secret if you negotiated a key beforehand and need a key for a cipher or a MAC. Key-Derivation-Functions are usually hash-functions with some slight modifications. A real world sample would be TLS, where you derive a key after negotiating a master secret using either DHE or ECDHE. TLS v1.2, see Chapter 5
There's no difference between PFS and FS other than naming. Wikipedia


Can Base64 be seen as a way of encryption if we use different index table? As we know, the index table (which maps bytes in [0, 63] to characters) of Base64 encoding is public, so everyone can decode Base64 strings from others.

But what if we use a shuffled index table and keep it secret? Can we see Base64 with this new table as some sort of safe encryption, and the shuffled table as cipher?

Can we see Base64 with this new table as some sort of [..] encryption [...]?

Yes, technically it does constitute a form of encryption as knowledge of a secret key is required to recover plaintext from ciphertext.

  Can we see Base64 with this new table as some sort of safe encryption [...]?

NO! This is essentially a monoalphabetic substitution cipher applied on the Base64 encoded data. This can be seen as you can always take your table $T$ and then find a new $T'$ that undoes the base64 table encoding first and then applied after standard Base64 encoding.

Now while the key size is (theoretically) respectable with $\log_2 (64!)\approx 296$ bit, this cipher suffers from all the usual problems such ciphers have, including:

Ciphertext-only attacks are possible using frequency analysis, as there are only 64 valid plaintext values and they will probably occur with different frequencies.
Known- and chosen plaintext attacks are devastating as there are only 64 mappings to be uncovered and usually plaintexts have quite a bit of structure allowing to guess the rest / uncover significant parts of the plaintext.


Using pairings to verify an extended euclidean relation without leaking the values? Let $P_i(x)$ be polynomials $i=1,...,n$, $s$ some value, and $g$ a generator of a group $G$ where the discrete logarithm is hard.

Assume a prover wants to convince a verifier having access to the values $g^{P_i(s)}$ that it knows polynomials $q_i(x)$ such that the following equation holds:

$q_1(s)*P_1(s)+q_2(s)*P_2(s)+\ldots+q_n(s)*P_n(s) = 1.$

The prover thus sends the verifier the values $g^{q_i(s)}$ and
uses bilinear maps to verify the correctness of the answer.

Can the following equation tell me whether it has correctly computed the $q_i(s)$:
$$e(g^{q_i(s)},g^{P_i(s)}) = e (g,g)$$
where $e$ is a bilinear map $G\times G\rightarrow G_1$.

So basically I want my bilinear map to verify on the exponents while hiding them. Is the second part of the equation correct? Or should it be 1, or $e(g,g)^{ord(G)}=1$?

Well, assuming the equation holds, $\Pi_{i=1}^n e(g^{q_i(s)},g^{P_i(s)}) = e (g,g)$ must also hold, due to the bilinearity of $e$. (Conversely, the equation only holds mod |G_1|.)

To see why, recall that the fact that the mapping $e$ is bilinear translates into $e(g^a,h^b)=e(g,h)^{a*b}$ for all elements $g$ and $h$ in $G$ and for all integers $a$ and $b$. Thus, we always have $e(g^{q_i(s)},g^{P_i(s)})=e(g,g)^{q_i(s)*P_i(s)}$ and by multiplying all these equalities together we get that $$\Pi_{i=1}^n e(g^{q_i(s)},g^{P_i(s)}) =e(g,g)^{q_1(s)*P_1(s)+\cdots+q_n(s)*P_n(s)}.$$
Now what you want to check is if $q_1(s)*P_1(s)+\cdots+q_n(s)*P_n(s)=1$: if it is true, we can replace the expression in the left-hand side of this equation in the pairing equation above by 1 and thus get
$$\Pi_{i=1}^n e(g^{q_i(s)},g^{P_i(s)}) = e (g,g)$$
as stated in the beginning.

For $e(g,g)$ is a group element of $G_1$, it must hold that $e(g,g)^{|G_1|}=1$, as for any other element of $G_1$.

For the actual value of $e(g,g)$ itself, we can only say it is an element of $G_1$ (by definition of $e$). It can be the neutral element of $G_1$ in which case $e(g^a,g^b)=1$ for all $a$ and $b$ and thus does not provide you with a way to check the extended euclidean equality, since you'll basically get $1=1$ for all possible values of $q_i$ and $P_i$.


Is it possible to find plaintext from ciphertext if (n) and (a) are known for RSA? I have a couple of questions pertaining to a RSA problem. I need to decipher some ciphertext and find out what the original plaintext was.

Modulus: $n = 2537$ and exponent: $a = 11$

Encrypting function: $E(x) = x^{11} \mod 2537$

Using Fermat's Little Theorem to start, I have successfully encrypted some plaintext and decrypted it, so I do know what the other required numbers in this particular RSA system are, however if initially I am only given $n$ and $a$ can I:

Mathematically work out some plaintext, if the ciphertext, $n$, and $a$ are known? If so would I basically step through the encryption process in reverse?
If not, what is the best/most effective cryptanalysis method to work out what the original plaintext is, if $n$ is relatively small (2537) and $a$ is relatively small (11)?

Note: This is needs to be calculated using the 'maths' behind the system and not a specific computer function.

For small numbers the easiest ways to break RSA are:

Brute force the private (decryption) exponent. I.e. find the smallest value $b$ such that $(x^a)^b \mod n = x$ for all $x$.
Factorize the modulus (trial division is simplest and works fine for small numbers), then use the factors to generate the private exponent.

Assuming you are supposed to use the maths, 2. is probably expected.


Is base64 the best two-way hash function to encrypt and transmit a set of integer numbers via the internet? I am writing a mobile game and I need to save my game data on my game server, so crackers can not find and access the saved files(data) on their mobile. The game data can be expressed by numbers, so it does not really matters if I use Base64 as a means to securely pass the data via a network and/or to prevent data corruption while sending the data via wire.

I need a hash function to prevent the deciphering the game data. So I digged a little and found some, but I am not sure if I can and/or should use them.

MD5 – Can I use MD5 as a two-way function? If I can break the data in 64 bit portions, will I be able to recover the original message without a pre-calculated lookup table?
Base64 – that can be easily used in both ways which is good cause it is easy, but this is also easy for hackers and crackers.

I don’t know how SHA and other kind of checksums and integrity checks work, or if they are aproperiate for this kind of data (numbers).

MD5 – Can I use MD5 as a two-way function? If I can break the data in 64 bit portions, will I be able to recover the original message without a pre-calculated lookup table?

MD5 is a hash function, not a cipher. Differently stated: you will not be able to encrypt or decrypt anything by simply using a hash function.

You could compare MD5 hashes with each other, but that would need you to “pre-calculate” hashes to which you would then compare those other hashes. But hashes will prevent you from learning about the original message (hashes are made to prevent that – among other things). Same goes for recovering the originally hashed data: you can’t. The reason is simple… a hash is not a compression tool which enables you to decompress contained data later on. There’s simply not enough information contained in a hash to do that (if recovering the original file from a hash were possible, everyone would be sharing short MD5 messages and things like torrents would have never been invented).

So – No, you can not use MD5 to recover the original message.

  Base64 – that can be easily used in both ways which is good cause it is easy, but this is also easy for hackers and crackers.

Base64 is nothing but a simple encoding method. A way to represent data. It has nothing to do with cryptography in the sense that it would be able to provide any kind of security. It is neither a hash, nor a cipher. All Base64 does is that it enables you to represent and transmit (mostly binary) data in a human-readable way. For example: Base64 comes handy when I would want to send you a binary file like an executable via email, but can not (or don’t want to) use the option to attach that file. With Base64, I could simply copy-and-paste the data as a message… which you would then need to convert back to binary data after receiving it.

Long story short – You can not (and should not) expect Base64 to provide any kind of security.

  I don’t know how SHA and other kind of checksums and integrity checks work, or if they are aproperiate for this kind of data (numbers).

SHA is also a hash, just like MD5. Hash functions are fundamentally different from checksums like CRC32. Checksums are mainly build and used to verify the integrity of data (for example: during data-transmission, or after data storage), while cryptographic hash functions also target things that go well beyond data integrity checks. You could use a hash to provide what a checksum does, but a checksum can not provide all the things a hash can provide… things like “collision resistance” for example. In that sense, you could say hashes are “smarter” (but also slower to calculate).

To give you a hint related to all of your questions: What you are actually looking for is called a ”cipher”… an  ”encryption algorithm”.

Some humble advice

Now, please don’t get me wrong… but you should really start from scratch with your research, since you are obviously getting most of the things you have been digging up absolutely wrong and trying to implement cryptography in your software with your current knowledge level is bound to fail.

To help you understand the fundamental things you are currently mixing up, I would humbly advise you to start reading the following two:

https://en.wikipedia.org/wiki/Encryption
https://en.wikipedia.org/wiki/Cryptographic_hash_function

After reading (and understanding) those Wikipedia articles, slowly work your way up to the point where you can be confident that you know what you are doing and talking about.

On your way, things like the Handbook of Applied Cryptography (available for free as online version) will definitely come handy as it is easy to read once you grasped some minimal basics of crypto.

As said, please don’t get me wrong and please don’t take my advice as some kind of personal offense. I just do not want to see you fail securing your software or maybe even messing up the security of your game server, just because no one pointed you to the fact that you are currently simply too misinformed to even think about implementing cryptography in your game all by yourself.

On the positive side: you were smart enough to ask before doing something wrong, which is good. Therefore, I am confident that – with a bit time and effort – you’ll quickly reach a point where you’ll look back on this question and smile. Yet, think in weeks… not days or hours. Crypto can’t be learned in a day. In contrast, cryptography can be so tricky to implement that even experts sometimes fail to do it correctly because they missed a tiny detail somewhere. Gaining a somewhat useable level of knowledge so that you can implement it in your game and server surely won’t happen by tomorrow.

EDIT

Adding part of the comments that followed up this answer:

  OP:
  … May you please advise me on finding an easy encrypt/decrypt with acceptable level of security? I prefer the method is common enough so I can use built in libraries while implementing both on server and client sides
  ME:
  Depends on the coding languages you’re using, but AES is available on about every platform and there are many libraries (eg: OpenSSL) out there supporting it. So, that could be an option… especially because you probably have the best chances finding "HowTo" tutorials related to it. Besides that, you’ll have to consider thinks like "keys" and “key exchange” (for authentication and encryption) but all that is too broad to wrap it up in a single answer or comment. If I were you, I would take things step-by-step and when in doubt – ask here or (if it’s source-related) at StackOverflow.
  OP:
  … I am a bit familiar with keys and two way keys concept and I think I can use AES by reading some tutorials …

That should wrap it up completely.


trying to understand multiplication + reduction in binary finite fields The wikipedia.org article on Finite field arithmetic provides an example of multiplying $83$ and $206$ in $\mathbb{F}_{2^8}$ with $x^8+x^4+x^3+x+1$ as the reducing polynomial (in fact it is the reducing polynomial for AES). Quoting it:

Multiplying $83$ and $206$, whilst ignoring the carries, yields $16,254$ or (in binary) 11111101111110.

The reducing polynomial is then converted to binary (100011011), shifted forward to match the length of the number being reduced (eg. multiplied by a power of two) and then XOR'd (subtracted) against the number to be reduced. It seems like it's supposed to do this until the number being reduced is less than the reducing polynomial (in binary).

Here's the example wikipedia gives:

      11111101111110 (mod) 100011011
     ^100011011
       1110000011110
      ^100011011
        110110101110
       ^100011011
         10101110110
        ^100011011
          0100011010
          ^100011011
            00000001

My question is...  why is the last XOR done? 0100011010 is less than 100011011..

The last XOR is done, to get rid of the $x^8$ term. Polynomials in $GF(2^n)$ do have a maximum degree of $n-1$.


How long does it take to crack DES and AES? Suppose that a single evaluation of a block-cipher (DES or AES) takes 10 operations, and the computer can do $10^{15}$ such operations per second.

How long would it take for to recover a DES key, using a brute-force search? How about a 128-bit AES key?

Assume that 1 evaluation of {DES, AES} takes 10 operations, and we can perform $10^{15}$ operations per second. Trivially, that means we can evaluate $10^{14}$, or about $2^{46.5}$ {DES, AES} encryptions per second. This is a simplistic view: we are ignoring here the cost of testing whether we found the correct key, and the key schedule cost.

So on our hypothetical machine, a 56-bit DES key would take, on average, $2^{55}/2^{46.5} = 2^{8.5} \approx 362$  seconds to find. Similarly, a 128-bit AES key would take $2^{127}/2^{46.5} = 2^{80.5}$ seconds $\approx 2^{55}$ (or approximately $36$ quadrillion) years to find.


Can a proof be constructed to show there is no distinguisher? Let's assume a simple algorithm like the Skein hash function.

Is it possible, given the algorithm, to construct a proof that it does not have a particular distinguisher, something like:

$P(xyz)$ is the probability that $xyz$ is truly random over some alphabet,

Given $\vert y \vert = l$, for some fixed length l, $z = f(x)$ (i.e., $z$ is dependent on $x$).

Not in general, of course, but for a particular such distinguisher.

There are a number of distinguishers that it it would be easy to prove are not present in a hash function.

For example, I can easily prove that Skein does not have the distinguisher "the 2nd bit in the output is equal to the first bit of the output with probability 1". The proof would be a simple example of a message whose digest does not have this property (which should be fairly easy to find).

For more interesting distinguishers, the problem becomes much harder (on a side note, is the distinguisher really interesting if I can prove it doesn't hold for a particular hash function?).

My gut feeling is that yes, one could come up with an "interesting" distinguisher and then show that it doesn't hold for the hash function, but I can not offer more than a gut feeling.


Question about Fermat's little theorem Why is $g^e \mod p = g^{e \mod (p-1)} \mod p$ if p is prime. I don't get it. It follows from Fermat's little theorem.

Fermat's little theorem $$a^p \equiv a \pmod{p} \Leftrightarrow a^{p-1} \equiv 1 \pmod{p}(p \nmid a)$$

so next divides $e$ with $p-1$:$$e=(p-1)r+s;$$ $$s\equiv e \pmod{p-1};$$
so we get $$g^{(p-1)r+s} \pmod {p} \equiv (g^{p-1})^rg^s \pmod{p}$$
 follow Fermat's little theorem $g^{p-1} \equiv 1\pmod{p}$ finally we get :$$g^{(p-1)r+s} \pmod {p} \equiv (g^{p-1})^rg^s \pmod{p} \equiv g^s \pmod{p}$$ $\Leftrightarrow$
$$g^e \pmod{p} \equiv g^{e \pmod{p-1}} \pmod{p}$$


Does changing the order of the steps within a round affect the security of AES? I was trying to understand the internal structure of AES (Advanced Encryption Standard)

The Standard order of steps within a round:

Substitute Bytes
Shift Rows
Mix Columns
Add Round Key

Substitute Bytes, Shift Rows & Mix Columns satisfies the two most important properties required for a secure cipher i.e confusion and diffusion

Substitute Bytes provides Confusion i.e. that each binary digit (bit) of the ciphertext should depend on several parts of the key.

Shift Rows along with Mix Column provides Diffusion i.e. if we change a single bit of the plaintext, then (statistically) half of the bits in the ciphertext should change

Changing the order of Step 1 and Step 2 won't have any effect. But to what extent can we change the order of other steps? Does it weakens the security of AES, and if so, how?

Short answer

Changing the order of the operations does not weaken the security of $\mathop{AES}$ (nor does it increases it).

Long answer

Remark: While ShiftRows and SubBytes are commutative ($f\ g : A \rightarrow A,\ f \circ g = g \circ f$). They are not commutative MixColumns. Therefore changing the order of operations will not produce the same result. But this is not relevant because we are looking from the security point of view.

The order of the operations inside the round function does not matter. This can be shown by observing the propagation of the byte dependence over 2 application of the round function.

In this analysis I'm ignoring the key addition because this operation can be placed anywhere in between all the operations given some tweaking. Thus we can see that the diffusion of a difference is the same as the one in the original specifications. The main reason of this result is due to the strong alignment in Rijndael.

Also this is further explained in Chapter 3 and 5 of The Design of Rijndael by their implementors.


Decryption issue with self-coded AES-128 I have written my own AES-128bit implementation in Java, till yesterday I thought it would be alright. (I was working on the encryption)
Now I’m trying to decrypt my encrypted cleartext, but this fails..

So, I hope I can ask such questions on here..

My Cleartext is: abcdefghijklmnop

This will be converted to the State Matrix (4x4, hexadezimal):

61 65 69 6d
62 66 6a 6e
63 67 6b 6f
64 68 6c 70

After that, it is going through the 10 rounds (The Key is generated randomly at the beginning, after that computed for every next round, will change that to a hash function later):

Round 1:

    2c d3 db c6
    3c 31 83 91
    21 a9 f5 0d
    48 9c 69 0a

Round 2:

    9f 81 b2 c8
    6e 4a 61 94
    0a b8 cb a3
    a4 4c 6c 57

Round 3:

    01 3e a4 af
    f0 69 fe 64
    1f de 19 e1
    cf a6 78 9e

Round 4:

    d0 c9 40 e5
    bd 81 de dc
    8c 5a fd e2
    61 84 37 65

Round 5:

    19 51 92 00
    63 f4 e9 33
    15 48 8e ba
    13 ae 7e 7a

Round 6:

    1e 75 41 3d
    34 ed fe 24
    f6 02 64 39
    ea 94 50 b1

Round 7:

    a9 6a 6e 8a
    7d 84 59 dd
    b3 11 f3 d2
    4d d8 e2 9c

Round 8:

    e4 c3 89 0a
    60 0a 29 e9
    91 68 2c e4
    13 23 e0 d8

Round 9:

    24 c2 1c db
    87 8c 22 bc
    0b a8 3d e9
    35 c2 3f 21

Round 10:

    a9 58 3c 76
    c0 db 39 20
    58 db 80 3d
    b6 63 b4 4e

And the KeyBlock from the beginning is:

d2 66 1b 52
08 fb 35 20
76 e9 11 1c
d3 7d 36 e0

And now, if i do the encryption backwards (with reversed tables and so on), i got this:

Round 1:

    bf 5b d2 27
    df 15 d0 d8
    a6 70 69 07
    b8 4c 4c 47

Round 2:

    89 16 66 bc
    1c 22 0e 56
    bc db f0 77
    7f b1 9e d4

Round 3:

    bf ac 65 b8
    70 70 8c a4
    ef 6b 38 cc
    63 13 ef 3e

Round 4:

    28 ba 4b bd
    44 63 d2 8c
    33 aa ab 76
    ba 71 02 00

Round 5:

    ef 45 ee b9
    fd e3 ce 09
    1a 91 de 70
    b2 95 22 2b

Round 6:

    6c 95 6a c3
    91 12 ec 27
    62 df b7 49
    ad ac 11 56

Round 7:

    8a f5 d9 c7
    68 0d be 3e
    b0 58 45 bc
    68 a1 ad b9

Round 8:

    45 11 77 dd
    84 cd f0 87
    20 06 e8 3e
    fe 32 4b e3

Round 9:

    97 77 6c 8f
    8c 36 c5 a7
    56 ef f9 22
    2d 4f 7d 03

So as you can see, there is something going on wrong.. I used this paper as main source of information (It’s in German), and I also used many other sites and Wikipedia (English Version) about Rijndael.

If someone can tell me anything with this information, that would be very very very cool, besides that I can also provide the source via email.

All of your encryption rounds are incorrect, either due to incorrect round function or key schedule (or state alignment). Showing round 0 (round key addition before first round) will help show if the keys are being added correctly to the state.

The key expansion is also very important, if that is not done correctly it will not work at all.

I will assume the decryption is also incorrect, but did not test, since whatever method fixes the encryption code should be applied to all code, resulting in correct outputs.

Given your plaintext and key, your state data should look as below.
The key schedule values are shown as a column in 32-bit unsigned value format, which is reverse byte order from the state array:

Key schedule
Round 00  d37608d2 7de9fb66 3611351b e01c2052
Round 01  d3979464 ae7e6f02 986f5a19 78737a4b
Round 02  602b1bbc ce5574be 563a2ea7 2e4954ec
Round 03  ae1a2098 604f5426 36757a81 183c2e6d
Round 04  92b7cba1 f2f89f87 c48de506 dcb1cb6b
Round 05  ed3103ae 1fc99c29 db44792f 07f5b244
Round 06  f6f4e5b9 e93d7990 327900bf 358cb2fb
Round 07  f96281ce 105ff85e 2226f8e1 17aa4a1a
Round 08  5b922d98 4bcdd5c6 69eb2d27 7e41673d
Round 09  7c61ae06 37ac7bc0 5e4756e7 200631da
Round 10  2bd6c1f7 1c7aba37 423decd0 623bdd0a

Plaintext and initial state
6162636465666768696A6B6C6D6E6F70

  61 65 69 6d
  62 66 6a 6e
  63 67 6b 6f
  64 68 6c 70

Round 0
  b3 03 72 3f
  6a 9d 5f 4e
  15 8e 7a 73
  b7 15 5a 90

Round 1
  e6 98 e8 00
  50 b2 f6 9e
  ab 2f 59 ef
  20 2a 9c 9b

Round 2
  3d 9c 10 14
  a9 7b e0 70
  23 36 5a 2a
  3d ec 58 6a

Round 3
  09 7b 15 83
  9e 40 b6 0c
  7d c8 eb a1
  5c 53 83 0f

Round 4
  27 6f bf b1
  8e 3e ac fe
  ec 2d e3 b2
  9d 79 ef d3

Round 5
  97 a3 91 e3
  e5 0a e3 e4
  c7 7c b1 f5
  cd e6 c1 20

Round 6
  64 ec 55 c1
  57 dd 8c 42
  52 2d 8f ec
  af 61 02 3f

Round 7
  16 c2 99 a8
  bb ce b3 80
  99 f9 dc bb
  64 01 d4 f2

Round 8
  9f 92 3e 56
  7f 4c 17 92
  c9 8f 8b 98
  96 25 9b c0

Round 9
  57 83 ab a9
  da 95 39 be
  3c 34 5a bf
  71 6b 7f 61

Round 10 (final ciphertext)
  ac db b2 d9
  eb a8 42 8a
  68 72 d6 23
  c4 bf 3d b0

Ciphertext
ACEB68C4DBA872BFB242D63DD98A23B0


Understanding the distinguisher for a PRG Given the following definition of a psuedorandom generator, I'm having trouble understanding what exactly the "distinguisher" D is outputting, and when?

As said before, the distinguisher D outputs a bit.

I would like to add that the advantage is a measurement for how good the distinguisher is doing. Say you have two distributions which are computationally indistinguishable, then $adv_D$ is negligigle close to 0. On the other hand, if the two distributions are easy to distinguish, then $adv_D$ would be close to 1.

On your formula, the advantage of D is:
$$adv_D = |Pr(D(X)=1) - Pr(D(Y)=1)|$$.

If the distributions are indistinguishable, a distinguisher cannot succeed on doing its job, i.e. distinguishing the two distributions. Then, the output of D is the same regardless of having distribution X or distribution Y as input.

If you need further reading I strongly recommend you having a look at the paper "On the Role of Definitions in and Beyond Cryptography", by Rogaway. There he explains clearly the concept of distinguisher.


ECDH public keys restrictions I know that Bob can calculate the shared DH key without knowing the private key. If he sends to Alice a public key = 1, then the the DH key would be 1.
Can i achieve something like this in ECDH? where Bob can calculate the shared key without knowing the private key?

Similarly, just send the identity element $\mathcal{O}$ as the public key.
Alice must be a fool to not validate the public key to fall into this trap. The first rule is to check that $P \neq \mathcal{O}$

Update per user's comment

How can i find the identity element of curve 25519?

The identity of some curves like Curve25519 is the point of infinity ( represented as $\mathcal{O} \text { or } \infty$) and this can't be represented in the affine coordinates. We need to use projective coordinate systems.
We took the Curve25519 equation $$y^2 = x^3 + 486662 x^2 + x$$ and convert it into homogeneous equation $$Y^2 Z - X^3 - 486662 X^2 Z - X Z^2$$
Now the points are triple $(X:Y:Z)$ where actually a point now represent a line $(\lambda X:\lambda Y: \lambda Z)$
The point at infinity is $(0:1:0)$ and this cannot be treated as an affine point.
Any affine point $(x,y)$ can be turned into homogenous by $(x:y:1)$ and any homogenous point other than the infinity $(X:Y:Z)$ can be turned back with $(X/Z,Y/Z)$.


Limiting password length to "prevent hash function splitting into multiple hashes"? Given we are using well-known hashing functions for passwords, i.e. SHA256, SHA512, BCrypt or, PBKDF2.  Our Information Assurance SMEs have advised that we truncate the input into these hashing functions:

  …to prevent the hashing function splitting it into multiple hashes.

I have not heard of hash functions doing this, in fact, I had assumed that hashing a string down with a hashing function would produce a fixed length string - am I incorrect to make this assumption?

The infamous "LANMAN hash" used in older Windows versions had a problem where it split passwords into 7 byte chunks and computed a hash for each separately. This, together with lack of salt, and other poor design decisions meant that a password of "keyboard42" and a password of "KeyBoarMint" store the same first value, making it uniquely vulnerable to a time-space tradeoff called "Rainbow tables" in which an adversary pre-calculates lots of data and then needs very little work to reverse an password hash.

Not only are the modern schemes you've mentioned proof against such attacks, even in the 1970s a competently designed password hash was not vulnerable to Rainbow tables. The advice you were given is very poor.


Why does LastPass use exactly 100100 PBKDF2 rounds LastPass encryption scheme is recently changed to use more PBKDF2 rounds, specifically 100100. This seems like a really weird number choose. From what I understand brute force time scales linearly with rounds because more rounds simply mean that each hash takes longer/more memory to compute. Being just over 100k, it feels like there could be some weird prime number tricks that they are trying to avoid, but I honestly can't come up with anything, and it doesn't seem to be for backward compatibility with un-upgraded vaults either because those used to be 5k rounds IIRC, which would make it 105000 if they just slapped the extra 100k rounds on top.

So, why did they pick such a weirdly specific number instead of just straight up 100k? I don't get it.

LastPass uses PBKDF2 with SHA256. The number of iterations (also called count) in PBKDF2(PRF=SHA256, Password, Salt, iterations, dkLen) is used against the password crackers. With the increase of the computation power, the developers change the number of iterations from 5000 to 100100 and there is nothing special about it other than being large. Having different numbers from others only can be considered a pre-countermeasure that may be helpful in the future. You can still adjust the iteration number to any value that you want.

The salt, on the other hand, is used as a countermeasure against Rainbow Tables. Actually the salt simply killed the Rainbow Tables. They are no longer helpful if the sites use a salt-based password hashing.

With a good PBKDF function with properly used salt, the only way to break is the brute-forcing the possible password and combinations. The number of iterations linearly increases the cost of brute-force. That is, if you double, the attacker with the same system need double time.

Keep in mind that there is an old saying inside the US National Security Agency (NSA):

$$\texttt{Attacks always get better; they never get worse}$$


If a new hash function were made that simply truncated sha-256 to the first N bits, how much insight would it provide into sha-256? Clearly it would provide perfect insight if all 256 bits were used. What about if 255 were used? Would the general behavior and properties of "sha-255" be expected to be close to sha-256? What about "sha-5?" I imagine at some point the insight we can gain must break down, but am not sure exactly where that is.

sha-256 has such a large range of potential outputs that it is impossible for me to do certain experiments with it to analyze the behavior. But I presume that I couldn't, for example, truncate outputs to the first 10 bits or whatever, and then assume that observed behavior will extrapolate to the real sha-256, or else we would likely be able to know far more about it than we can.

I like to learn by experiment and observation. Are there any constructs with behaviors similar to cryptographic hash functions like this, but that I can actually exhaust the range of, and gain any insight into the secure constructs from?

My guess is no because of the lack of some insights into the secure constructs, but I'm not certain. Is insight already lost at "sha-255?"

If this provided any insight, we would consider SHA-256 to be broken.  In general, we expect the $n$-bit truncation of SHA-256 to resemble an $n$-bit uniform random function.  For example, finding a 10-bit partial preimage costs an expected ${\approx}2^{10}$ trials; finding a 10-bit partial collision costs an expected ${\approx}2^5$ trials.

That said, there are often simplified versions of cryptographic primitives for study:

One obvious simplification of SHA-256 is to reduce the number of rounds from 64—for SHA-256 as for most cryptographic primitives with rounds, the first (and, for unbroken cryptosystems, only) attacks published in the literature are on reduced-round variants.
Aside from varying the number of rounds, Keccak supports any power-of-two word size from 1-bit to 64-bits; SHA-3 is based on 64-bit Keccak with a 1600-bit state, but you could study 1-bit Keccak with a 25-bit state (with any number of rounds).
The SHA-3 candidate BLAKE came with several toy versions BLOKE, FLAKE, BLAZE, and BRAKE.


Is it safe to publicly announce the prime number in Shamir three-pass protocol So say, I want to use a prime number p for anyone that wants to communicate with me using Shamir's Three Pass Protocol.

I will be maintaining my secret keypair (encryption exponent, decryption exponent) and will be expecting other parties to create their own secret keypairs according to the public prime p.

Assuming we have some method of authentication, so we won't be susceptible to man-in-the-middle attacks from that perspective.

But, is it safe to publish the prime number publicly?

But, is it safe to publish the prime number publicly?

It has to be. Otherwise the other party would not have access to it and could not participate in the protocol. It is called a "public prime" and not a "secret prime" for that reason.

  So say, I want to use a prime number p for anyone that wants to communicate with me using Shamir's Three Pass Protocol.

If this isn't a hypothetical question and you actually plan to use this for securing real communications, you will want to consider learning about other more standard techniques such as Diffie-Hellman key agreement and hybrid cryptosystems. There are much more efficient and better studied methods for creating secured communication channels than the three pass protocol. Also, you'll want to find a pre-existing software library that already implements the relevant algorithms.


What was NIST’s reason to switch naming from MD… (Message Digest) to SHA… (Secure Hashing Algorithm)? When NIST introduced SHA-0 in 1993, they – for the first time – switched their naming convention from MD-n to SHA-n. Since both point to similar constructions (read: hashing algorithms with the same cryptographic goals), I am wondering why NIST chose to change the naming from „Message Digest“ to „Secure Hashing Algorithm“. A look around didn’t return useful information related to this.

Was there a specific reason to change the existing naming convention? Does it in some way indicate that there was change in cryptographic goals (and if, which ones) or was it simply the result of a standardization decision, potentially based on terminological changes within NIST definitions?

In case there’s an official statement explaining this change in naming convention, I’ld also appreciate a pointer to it for reference purposes.

When NIST introduced SHA-0 in 1993, they – for the first time – switched their naming convention from MD-n to SHA-n

Actually, MD-n was not NIST's naming conventions; it was RSA Security's (a private company) naming convention.  Before SHA (which was the original name; SHA-0 is retroactive terminology given to distinguish the original proposal from what was finally adopted: SHA-1), NIST didn't define any hash functions.


Why encrypt symmetric keys first with RSA and then the private-key with a PW? In for example the Microsoft Encrypting File System, the SYM-Key is first encrypted with a RSA-Pub-key and its corresponding private-key is then encrypted using a users password. Why not encrypt the SYM-key directly with the PW?

There are a few likely, closely related reasons for this:

you need both a password and the encrypted private key to decrypt (i.e. you need two factors);
it is possible to attack the password for the encrypted symmetric key using an offline attack, even if it is using a key derivation function such as PBKDF2.
private keys can also be stored on smart cards that perform the private key operation, that way the decryption key can be stored even more securely, and protected against offline attacks.

Reason 2 is of course also possible for the encrypted private key, but generally we can assume that the encrypted private key is less accessible to an attacker.

Another possible advantage is that you may not need a password or private key to encrypt the symmetric key. If this is an actual advantage is of course dependent on the use case. For file systems it seems like a useful feature, but I don't think it will be the one that tips the balance.

The major drawback is of course that you cannot just remember a private key; you need some kind of connected computing or at least storage device for the encrypted private key. If you store the private key and leak it (e.g. copy it over and not securely delete it) then a lot of the advantages can be lost.


Question about block erasure codes I have a question about linear block erasure codes that are described in this paper.
I briefly describe the idea behind the linear erasure codes and then I ask my question.

Given a set $d=\langle x_i \in GF(2^q)|i=1,\cdots,k\rangle$ of data packets, the general idea of (systematic) erasure codes is to generate $n-k$ extra packets $e=\langle y_j \in GF(2^q)|j=1,\cdots,n-k\rangle$, such that given any $k$ packets out of the set $\{x_1,\cdots,x_k,y_1,\cdots,y_{n-k}\}$ one is able to decode the original set $d$.

To generate the extra packets, we consider an $(n-k) \times n$ generator matrix $G'$ and compute $e=G'd$.

The paper claims that if the rows of the generator matrix are selected from a Vandermonde matrix:

$$
V=\begin{bmatrix}
1 & \alpha_1 & \alpha_1^2 & \dots & \alpha_1^{k-1}\\
1 & \alpha_2 & \alpha_2^2 & \dots & \alpha_2^{k-1}\\
1 & \alpha_3 & \alpha_3^2 & \dots & \alpha_3^{k-1}\\
\vdots & \vdots & \vdots & \ddots &\vdots \\
1 & \alpha_m & \alpha_m^2 & \dots & \alpha_m^{k-1}
\end{bmatrix}
$$
where $\alpha_i \in GF(2^q)$
then the computed vector $e$ has the desired property.

Now my question: Assume $n-k=2$, i.e., any loss of 2 packets can be recovered.
Let,
$$
G'=\begin{bmatrix}
1 & \alpha_1 & \alpha_1^2 & \dots & \alpha_1^{k-1}\\
1 & \alpha_2 & \alpha_2^2 & \dots & \alpha_2^{k-1}
\end{bmatrix}
$$

By definition of the erasure codes, the submatrix consisting of any two columns of the matrix $G'$ must have rank 2. But we know that for $\alpha_1, \alpha_2 \in GF(2^q)$ and $\alpha_1 \neq \alpha_2$, we may have $\alpha_1^s = \alpha_2^s$ for some $s$.
It means that the matrix

$$
\begin{bmatrix}
1 & \alpha_1^s \\
1 & \alpha_2^s
\end{bmatrix}
$$
has rank 1 rather than 2. So, it means that if packets $x_1$ and $x_{s+1}$ are lost, they cannot be recovered using the set $e$.
Generally, the fact that an $m\times m$ Vandermonde matrix is non-singular,
does not mean that any submatrix of it has full rank, does it?

Did I misunderstood the concept or is it the fault of the paper?

Ok, I found the answer.

The answer is yes, singular submatrices may happen in a Vandermonde matrix. Look at this paper for an approach to avoid singular submatrices while creating a generator matrix:

http://oatao.univ-toulouse.fr/2176/1/Lacan_2176.pdf


Can I use a government-issued certificate in Outlook? My government issues certificates for many purposed, including e-mail signing.
The government doesn't provide e-mail addresses, but it does declare my e-mail in the certificate.

Can I use this certificate to sign e-mail in S/MIME?
Can I use this certificate to sign e-mails using Microsoft Outlook?
Can I use this certificate to sign e-mails in any system, that's not my own developement?

If your email is indeed in the cert and the key usage is there, you would expect that you can sign with it, providing that:

the certificate is compatible with the email client;
the signing generation is compatible with the email client;
that you have the entire certificate chain present (otherwise the receiver may miss an intermediate certificate).

And of course the receiver must have a compatible mail client as well and trust the (root) certificate of that government in his own certificate store.

If the Outlook mail client - or any other mail client - is compatible depends on the details. They can often be made compatible by including specific plugins.

Note that Outlook, like many other Microsoft products, depends on the PKI capabilities of the host operating system, i.e. Windows.


Encryption and HMAC in a PSKC file This is the PSKC standard

https://tools.ietf.org/rfc/rfc6030.txt

In Section 6.1

  6.1.  Encryption Based on Pre-Shared Keys

They have the following

Plain Text = 3132333435363738393031323334353637383930
Algo = aes-128-cbc
pkcs#5 padding
Encryption Key = 12345678901234567890123456789012
IV = 000102030405060708090a0b0c0d0e0f
Encrypted text = ESIzRFVmd4iZABEiM0RVZgKn6WjLaTC1sbeBMSvIhRejN9vJa2BOlSaMrR7I5wSX

How do they get this? I tried using openssl command line

echo 3132333435363738393031323334353637383930 | openssl enc -aes-128-cbc  -nosalt -iv 000102030405060708090a0b0c0d0e0f -a -pass pass:12345678901234567890123456789012

I get the following

HgFUJvBN9ztHcsIXNjvoTJJfOsoIq7XlOpdYCn+nk2TxQFrOJGhN+dYOHpFuIBQn

Likewise for the hmac-sha1

key = 1122334455667788990011223344556677889900
hmac-sha1 = Su+NvtQfmvfJzF6bmQiJqoLRExc=

I do it with openssl command line

echo  3132333435363738393031323334353637383930 | openssl sha1 -hmac 1122334455667788990011223344556677889900 | openssl enc -base64

(stdin)= eb6093578fdb69477f9a3322dcda28ce28b8aa1e

echo eb6093578fdb69477f9a3322dcda28ce28b8aa1e  | openssl enc -a -e

I get

ZWI2MDkzNTc4ZmRiNjk0NzdmOWEzMzIyZGNkYTI4Y2UyOGI4YWExZSAgDQo=

What am I doing wrong?

0: you have the wrong CipherValue. The one you show is in MACMethod/MACKey and is the encryption
of the MAC key, see 6.1.1. The encryption of the subject key is in Key/Data/Secret/EncryptedValue
and is AAECAwQFBgcICQoLDA0OD+cIHItlB3Wra1DUpxVvOx2lef1VmNPCMl8jwZqIUqGv.

1: openssl enc in most cases, including the one you used, does password-based encryption.
This does not encrypt or decrypt with the "key" you specify, instead it considers that a password
and runs it through a "stretching" or "derivation" function to produce the actual key.
See https://stackoverflow.com/questions/22085107/perl-cbc-des-equivalent-in-java
and https://stackoverflow.com/questions/11783062/how-to-decrypt-an-encrypted-file-in-java-with-openssl-with-aes .
For "direct" encryption and decryption you must use -K (uppercase) with the key in hex.

2: the example data in the RFC is in hex, although it doesn't say so.
For the key and IV this is okay because enc -K -iv take hex, but the data must be binary.
Hex 313233...30 is ASCII 12345678901234567890 but with no terminating newline
which echo automatically adds; preventing this varies depending on your system and/or shell, which
you don't specify, so I use perl instead.

3: XMLenc data for block/CBC contains the (actual binary) IV concatenated with
the ciphertext, with the combined result encoded in base64.

Thus (with binmode because I tested partly on Windows):

  echo $k
  12345678901234567890123456789012
  echo $i
  000102030405060708090a0b0c0d0e0f
  echo $i |\
  perl -ne "open O,'>temp';binmode O;print O map{pack('H2',$_)} ($_=~/(..)/g)"
  # that puts the binary IV at the beginning of temp
  perl -e "print '12345678901234567890'" |\
  openssl enc -aes-128-cbc -K $k -iv $i >>temp
  # that APPENDS the encryption of the data to temp
  openssl base64 <temp
  AAECAwQFBgcICQoLDA0OD+cIHItlB3Wra1DUpxVvOx2lef1VmNPCMl8jwZqIUqGv

4: MAC is computed on the encrypted value; also dgst -hmac takes the key as actual bytes (not hex)
in a C string, but the MAC key in this example contains a null byte which is impossible in a C string.
If you really want, you can do the HMAC as two hashes with tweaks of the key:

  echo $h |\
  perl -ne "open O,'>pad1';binmode O;$_=~s/[[:space:]]//g;\
  $_.='0'x(128-length($_));print O map{pack 'C',hex($_)^0x36}($_=~/(..)/g)"
  echo $h |\
  perl -ne "open O,'>pad2';binmode O;$_=~s/[[:space:]]//g;\
  $_.='0'x(128-length($_));print O map{pack 'C',hex($_)^0x5C}($_=~/(..)/g)"
  cat pad1 temp |openssl sha1 -binary -out tmp1
  cat pad2 tmp1 |openssl sha1 -binary -out tmp2
  openssl base64 <out2
  Su+NvtQfmvfJzF6bmQiJqoLRExc=

And there you are.


Partial Known Message Pre-Image Attack on SHA-1 If the last 448 bits of a sha1 block input are known (only the first 64 bits are unknown). Is it possible to do a preimage attack using SAT solvers or something else? Or do I have to brute force all $2^{64}$ possibilities? Is this a kind of reduced sha1?

If you know the last 448 bits, we can assume that this part actually the padding part with length at the end, then you will have 64-bit unknown data for the input to pre-image attack. Since you know the output hash value you can set up a system of equations. In this case, the hash function can be considered as

$$\operatorname{F}:\{0,1\}^{64}\times\{0,1\}^{448} \to \{0,1\}^{160}$$

Now, for every output bit, set up an equation by algebraic evaluation of SHA-1. You will have 160 equations and 64 unknowns.

This type of system is called over-defined when there are more equations than unknowns. However, keep in mind that the system may be inconsistent that means there is a collision there an that has an expected negligible probability.

According to Bard, Courtois, and Jefferson paper;

  if the system of equations is sparse or over-defined, then the SAT-solver technique works faster than brute-force exhaustive search. If the system is both sparse and over-defined, then the systems can be solved quite effectively.

The only problem that we can't see, immediately, the degree of the equations. If they are low degree then the SAT solvers, as Mini-SAT, can be faster than brute-force, according to the result of the paper.


NTRU less secure than previously thought? A new paper (https://eprint.iacr.org/2015/552.pdf) says:

  This makes it possible to asymptotically and heuristically break the NTRU cryptosystem in subexponential time (without contradicting its security assumption).

Does this mean NTRU is less secure now? By how much?

No, this result (as it stands) is of no practical use against NTRU as typically used.  To quote the paper:

  Note that there is a large value hidden in the o(1) term, so that our algorithm does not yield practical attacks for recommended NTRU parameters.

In addition, while it is subexponential, it's just barely so; they estimate the time as $2^{ (\ln 2/2+o(1))n/ \log \log n}$; even if we ignore the $o(1)$ term, this grows just slightly slower than an exponential function.

On the other hand, it may be that this attack might be useful against the use of NTRU as a somewhat homeomorphic cipher (which requires the error terms to be much smaller).  In addition, perhaps this result can be sharpened to be strong enough to be useful against NTRU.  So, while this isn't fatal to NTRU, the book isn't closed either.


Quantum Cryptography Used in a messaging application Is it possible to create a messaging application and apply a quantum cryptography technique to encrypt the messages between two parties within the application?

NO, if "messaging application" is software running on an stock consumer-grade computer or variant (including mobile phone, tablet): in any of its standard meanings, Quantum Cryptography requires specific hardware.

For Quantum Key Distribution (actually quantum privacy amplification), which is how quantum cryptography does encryption, you'd need a specific interface; an optical fiber running to the recipient or ultra-precise alignment towards the receiving device in line-of-sight (with no fog/smog); AND the inconvenience of exchanging initial secret keys in sealed envelopes or equivalents (see this). QKD is a working solution looking for problems, and failing at that.

Quantum Computers are currently about as common as manmade objects on Mars, and as useful to make or break practical cryptography. Quantum Computing is an immature technology, and it is uncertain when (and even if) it will metamorphose into something practical, in particular for cryptography. At even odds, I would bet that controlled fusion will be first (that would make the energy wasted on cryptocurrency mining a non-issue).

Among doable things with a sensible use of the word "Quantum", I only see "Quantum-Safe Encryption", or otherwise said "Encryption by Post-Quantum Crytography". That is encryption believed safe even from hypothetical quantum computers usable for cryptanalysis. Using the common AES-256-GCM qualifies, and is easy, but that's symmetric encryption. For the convenience of public-key cryptography, we'd have to pick something in the realm of Post-Quantum cryptography; the state of that nascent art is presently competing there.

Another semantically justifiable thing is bragging for a "Quantum Random Number Generator". The OS's cryptographically secure RNG likely qualifies (any TRNG or matter is ultimately quantum-based anyway), and if it was not it would be hard to disprove the claim that it is.