Counter Mode with a sequence of zeros bits plaintext, is it secure? I had a quiz last week in computer security course. There was a confusing question that I am still looking for a good and clear answer.

First, I know that counter mode with a good block cipher is widely accepted and most likely unbreakable as long as the counter (IV) is not being reused.

The question was about using counter mode with a strong block cipher, say AES. The IVs are independently generated. Suppose we encrypt two messages M1 and M2 where M2 is zeros, a sequence of zero bits, and get ciphertexts C1 and C2. Assume C1, M2, C2 are known by an attacker, would it be possible to decrypt, reveal M1?

Since in counter mode C = M ⊕ E(K,(nonce,IV))

for M2, the C2 = E(K,(nonce,IV)) , since M2 is zeros and xoring with zeros does not do anything.

I know that C1 ⊕ C2 = M1 ⊕ M2 but not sure if it is useful here.

My answer was the attacker will not be able to know (M1) because of the strength of the block cipher and the encryption process depends on the key, nonce, and IV which won't be broken if the attacker knows pair of plaintext and it corresponding ciphertext.

I am confused because what I have learned the strength of the counter mode depends on a good block cipher and non-reused IV, but what will happen if the input was zeros, and  E(K,(nonce,IV)) was exposed to attacker?

I did not feel I was right, and still confused about it.

Hopefully I can get a clear answer with appreciation.

This all depends on the IVs. If they are independently generated, the IVs will not only be different (so $IV_1 \neq IV_2$), but also their sequences will not overlap with overwhelming probability. In that case,  then everything should be fine, so $C_2 = E(K,(nonce,IV_2))$, and $C_1 = M_1 \oplus E(K,(nonce,IV_1))$.

However, if they are reused (so $IV_1 = IV_2$), then $C_2 = E(K,(nonce,IV_2)) = E(K,(nonce,IV_1))$, so $C_1 = M_1 \oplus E(K,(nonce,IV_1)) = M_1 \oplus C_2$, and therefore $M_1 = C_1 \oplus C_2$.


Edwards / Montgomery ECC over binary extension fields I recentely had a discussion about the redesign of our ECC code for the library I'm collaborating on and the person I was discussing with came up with Edwards and Montgomery curves over binary extension fields. I suspect he just did this because "why not?" as it seems to be straight conclusion to think they exist for the binary case and they are special for the prime field case.

This made me think and look into the addition law for Edwards curves over prime fields and it looks like you can't trivially do this over binary extensions fields.

So I had the following questions regarding (twisted) Edwards / Montgomery curves over binary extension fields:

Do they exist?
Are they any special, like Curve25519 and Curve448 are (i.e. easy side-channel resistant implementation)?
Are there standardized curves for them?

I suspect 1) to tell me "yes", because these curves can theoretically normally defined via the equations. I don't know about 2) but suspect they aren't special (or I would have heard of them) due to the vastly different implementation of the underlying field arithmetic between the prime and binary case. I doubt 3) holds, but I may have just missed them.

So I had the following questions regarding (twisted) Edwards / Montgomery curves over binary extension fields:

  Do they exist?

Yes[1].  They have the form $$d_1 (x + y) + d_2 (x^2 + y^2) = x y (1 + x) (1 + y)$$ where $d^2 \ne {d_1}^2 + d_1$.  The identity is $(0, 0)$; negation sends $(x, y) \mapsto (y, x)$.  If $d_2 \ne \alpha^2 + \alpha$ for any $\alpha$, then like (nonbinary—represent!) Edwards curves, binary Edwards curves have a relatively simple complete addition law, detailed in the EFD.

  Are they any special, like Curve25519 and Curve448 are (i.e. easy side-channel resistant implementation)?

BBE251[2] is the binary Edwards curve over the field $\mathbb F_2[t]/(t^{251} + t^7 + t^4 + t^2 + 1)$ with coefficients $$d_1 = d_2 = t^{57} + t^{54} + t^{44} + 1.$$  Like Ed448-Goldilocks, BBE251 was chosen to optimize certain performance metrics within this shape, subject to security constraints detailed in the paper; for example, the small Hamming weight and convenient shape of the polynomial $t^{251} + t^7 + t^4 + t^2 + 1$ makes reduction cheaper, and the small degree and Hamming weight of $t^{57} + t^{54} + t^{44} + 1$ makes multiplication cheaper.

The accompanying software computes a batch of thousands of scalar multiplications in somewhat fewer cycles per key on average than contemporary software for elliptic curves over prime fields of similar conjectured security levels.  Even though software doesn't make fast binary field arithmetic easy, the simple complete addition laws make for easy bit slicing in batch computation.

(Side note: There's nothing particularly special about Curve25519 and Curve448 among Montgomery curves over nicely shaped prime fields that makes them encourage side channel resistance.  Their equations $y^2 = x^3 + A x^2 + x$ have small coefficients $A$, which makes for a cheaper ladder, but that's a performance optimization, not a security concern.  Their primes $2^{255} - 19$ and $2^{448} - 2^{224} - 1$ make for fast constant-time reduction algorithms, but it's not clear that there's any security analogy here when the premise is a bit-sliced batch algorithm anyway.)

  Are there standardized curves for them?

Not to my knowledge.

There has been relatively little interest in these curves, it seems, perhaps in part because without a batch advantage they are extremely slow to compute in constant-time software, and perhaps in part because the security of binary field curves seems shakier and not as well-understood—or at least not as confidently understood—as large prime field curves[3].

More recent performance results like [4] are heavily dependent on CPU support for binary field arithmetic, and even then it's not clear that binary Edwards curves are competitive in performance with other alternatives, particularly alternatives that take advantage of fast endomorphisms.


Quadratic sieve for DLOG performance - theory vs actual? Is there any report on comparing quadratic and number field sieve performance in theory vs actual data for discrete logarithm over primes?

Is actual data better than theory in any way unexplained (I think I read this somewhere and cannot recollect)?

My query was more about distinction between theory and practice of quadratic sieve and distinction between theory and practice of number field sieve and not between distinction between quadratic and number field sieve.

To my knowledge, there are two reports that deal with the crossover point between the Gaussian integer sieve—which is the rough analogous of the quadratic sieve for discrete logarithms—and the number field sieve over prime fields:

Weber (1998) computed discrete logarithms over a 85-digit (~283 bits) prime, and concluded that at that size point the Gaussian integer sieve was faster.
Joux and Lercier (2003) not only compared the two algorithms, but made some improvements of their own to the number field sieve for discrete logarithms. They concluded that the number field sieve was faster already at the 100-digit (~332 bits) range.


decoding a Ed25519 key per RFC8032 RFC8032 Edwards-Curve Digital Signature Algorithm (EdDSA) 5.1.3 Decoding states the following:

  Decoding a point, given as a 32-octet string, is a little more
  complicated.

  First, interpret the string as an integer in little-endian
     representation.  Bit 255 of this number is the least significant
     bit of the x-coordinate and denote this value x_0.  The
     y-coordinate is recovered simply by clearing this bit.  If the
     resulting value is >= p, decoding fails.

My questions are...

32 octets is 256 bits. I'm assuming the index of the first bit is 0 instead of 1, which would make 255 the last bit. So why not say that it's the last bit instead of the 255'th bit?
Quoting the previous section, "To form the encoding of the point, copy the least
significant bit of the x-coordinate to the most significant bit of
the final octet.". So to encode we set the most significant bit and to decode we look at the least significant bit? So we're not looking at the same bit? That doesn't make a lot of sense to me.
When you interpret the string as an integer I'm assuming you're supposed to interpret it in two's compliment? eg. where if the first bit is 1 then you assume that the number is negative? The RFC isn't at all clear imho..

I'm assuming the index of the first bit is 0 instead of 1, which would make 255 the last bit.

Yes. That's made clear by example at the end of section 2, showing bits numbered starting from 0. In this RFC the  i'th bit really is the (i+1)th bit when numbering things the way America does with floor levels and the way many others standards number bits. I accommodate diversity rather than fight it, that's coward but makes life easier.

  When you interpret the string as an integer I'm assuming you're supposed to interpret it in two's compliment?

Sign comes after the decoding to integer. That same section 2 states that integers are non-negative and have a non-signed representation, and section 3.1 states how "negative" elements of GF(p) are encoded:

  The encoding of GF(p) is used to define "negative" elements of GF(p): specifically, x is negative if the (b-1)-bit encoding of x is lexicographically larger than the (b-1)-bit encoding of -x.

My brain hurts parsing that: if $x$ is negative then the $(b-1)$-bit encoding of $x$ (which the statement seems to try to define) is undefined yet, making the definition at best self-referential, at worst preposterous. I get that "lexicographically" combined with little-endian implies that low-order bit matters most in the comparison made.

The Ed25519 paper has something on the tune of that part of the standard, with $\mathbf F_q$ where the standard has GF(p), followed by the helpful

  If $q$ is an odd prime and the encoding is the little-endian representation of $\{0,1,\dots,q-1\}$ then the negative elements of $\mathbf F_q$ are $\{1,3,\dots,q-2\}$.

An element $x\pmod p$ of GF(p) is defined to be negative if and only if $((x\bmod p)\bmod 2)=1$ where the two-arguments operator $\bmod$ (recognizable by not having an opening parenthesis immediately on its left) produces non-negative integers less than its second argument; and that quantity $((x\bmod p)\bmod 2)$ is what's stored as a spare bit.

Thus in the question's quote and what follows, the first $(b-1)$ bits of the $b$-bit representation of point $(x,y)$ on the curve are $y$, little-endian, considered a non-negative integer; and the last bit (the high-order bit of the last byte) defines the sign of $x$. The method stated is enough to fully recover $y$ then $x$ as elements of GF(p), and thus the point.


Can multi-encrypted file be decrypted with one password only? Let's say I have a single file I want to encrypt with AES and I encrypt it twice (first encrypt the unencrypted file, then encrypt the encrypted file again). The first time I use password 'ABC', the second time I use 'DEF'. So in theory the attacker would have to decrypt it first by providing 'ABC' as password which would result in still encrypted garbage data - so they would provide 'DEF' and then they succeed. I wonder, though, if they may decrypt my file with only one password - perhaps there exists a password that is neither 'ABC' nor 'DEF' that successfully decrypts the file and they accidentally succeed with this password when bruteforcing.

In other words:

ABC -> DEF -> plain file

XYZ (exists or not?) -> plain file

Does the existence of 'XYZ' depends on the algorithm(s) used and will it always/never/sometimes exist?

Theoretically speaking, there is a possibility that a specific hashing algorithm can hash two separate passwords that both result to the same hash, however the odds of such an event making much of a difference in a brute force attempt is minimal. In addition, if there are two separate file containers (one inside the other), a brute force attempt would stop after decryption the outside container. My recommendation for encryption would be AES-256 encryption with SHA-512 hashing as those are currently accepted as industry leading algorithms. Should you care to, veracrypt will give you an option nest encryptions such as Serpent-Twofish-AES which will in turn make decryption take more time.


Pollard Rho pseudorandom function In Pollard Rho's Algorithm, a function $f$ with pseudorandom properties is required. Through this property, the birthday paradox can be leveraged to find a collision. But not all functions are pseudorandom. I am trying to understand what makes a function a good pseudorandom function.
Consider the following sample functions
$f(x)=a x+b \bmod N, a, b \in \mathbb{Z}_{N}$
$f(x)=x^{2}-2 \bmod N$
$f(x)=x^{2} \bmod N$
How can i show that these functions are not good pseudorandom functions?

In general a function $F:\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$ is a PRF, if you can not distinguish it from a real random function. For that you can play a game with an adversary. The adversary get eather a real random function or your random function. If the adversary can distinguish these functions better than with negigible probability, the function is not pseudorandom. If he can't distinguish them that good, the function is pseudorandom. In Katz & Lindell's textbook (2nd edition) on page 448ff you can find more about this. But for a PRF you need to arguments and I don't see, that your functions are defined over two.
Therefore I think you mean pseudorandom generator PRG instead of PRF. For the game with the PRG an adversary only gets two strings and he has to distinguish a real random string from a string that was constructed by the PRG. If he can distinguish them better than with negigible probability, the PRG is not pseudorandom. If he can't, it is pseudorandom.
For both games you don't look at one case, but for all cases. So if the adversary can find a strategy to only distinguish 1% correctly, he "won" the game and the PRF or PRG is not pseudorandom.
In your case: For your first function I can't tell weather it is a PRG or not, because I don't know more about $a$ and $b$. For the rest you can build an adversary, if N is known, that can distinguish them pretty easily. If you want to learn how to write a correct proof for that, you should definitely look into Katz & Lindell's textbook (2nd edition) or Katz & Lindell's textbook (3nd edition).
In general: Easy mathematical function like linear or quadratic functions are no good PRG in general. Even logistic functions aren't. For beginners in cryptographie and learning abouot PRG you mainly assume you got a PRF and then build another based on it and then proof is using reduction. In practise you can use a hash-function as a PRG.


What is the minimum recommended number of rounds for Argon2? I'm hashing passwords with argon2 using Python's passlib library and am wondering how many rounds I should use to future proof security. The default uses 2 rounds but I'm wondering if it'd be sensible to increase this. The documentation doesn't make any specific recommendations.

TL;DR: Yes, you probably should increase this, even though not by that much.

First, we need to identify the Argon2 variant in-use which is Argon2i for Passlib.

Now if we take a look at section 5.7 of the Argon2 specification, we will learn that there are some special attacks if only 1 or 2 rounds are used which is why you want the round value to be larger than that. Some might recommend to use something like 10 rounds.

In practice, I'd recommend following the same methodology as I laid out for Argon2d: Find out how much memory you can use, pick a lower bound for the round count (eg something like 5?) and then maximize memory usage within your time limit and perhaps tweak the time with the round number.


display an image encrypted with ECB On wikipedia there is an example of a picture encrypted with ECB:

http://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Electronic_codebook_.28ECB.29

I just wanted to know how an encrypted file could be displayed as a picture ?

This is off-topic, but arbitrary binary data can be read as image data using for example the Netpbm family of file formats. For example, here's how to read 10000 bytes of random data as a 100x100 grayscale image:

$ cat > image.pgm
    P2
    100 100 255
    ^C
    $ dd if=/dev/urandom of=image.raw bs=10000 count=1
1+0 records in
1+0 records out
10000 bytes transferred in 0.001229 secs (8136380 bytes/sec)
$ od -A n -t u1 image.raw >> image.pgm

You can then open image.pgm for example in Gimp.


Verion of crypto_box() which doesn't allow the sender to decrypt previously sent messages Libsodium's crypto_box() family of functions allow the sender to send messages using its public/private keypair knowing the receiver's public key, and allow the receiver to verify the identity of the sender knowing its public key.

However, since those functions work by calculating a shared symmetric key, the compromise of the sender's private key would allow the attacker to decrypt all messages previously sent using the same combination of sender's private key and receiver's public key.

There's another function, crypto_box_seal(), which does not have this weakness, since it uses an ephemeral keypair, but it doesn't allow verifying the identity of the sender.

Is there a function which allows both things - verify the identity of the sender and make sure previously sent messages can't be recovered without knowing the private key of the receiver?

I was thinking of doing what crypto_box_seal() does, but instead of using Poly1305 as an authentication tag, use the output of crypto_sign_detached() on the hash of the rest of the output (i.e. on ephemeral public key and ciphertext). That is, for each message, we generate an ephemeral keypair, encrypt plaintext using it, then sign the whole thing using our long-term private key and use that as an authentication tag. Would that make sense? Is there perhaps a better way?

In order to verify the identity of the sender, the messages needs a signature, that the receiver can verify using the sender's public key.

After encrypting the message with crypto_box_seal(), sign it with crypto_sign().

The receiver can verify the signature and remove it with crypto_sign_open() and then decrypt the rest.

What you suggested also works, but you'll have to implement all the bits yourself.


How do I calculate Base64 conversion rate? Basically I need to have a base64 encoded signature that has to be 96 characters long. However, I do not know what length I need to have the signature at so when I encode it, it can be that exact size. Does anyone know how to convert it? Also, does anyone know how to convert it in base64 encoding or any byte size encoding?

However, I do not know what length I need to have the signature at so when I encode it, it can be that exact size.

Well, base64 uses 4 characters (from an alphabet of size 64) to encode 3 bytes (3 bits contain 24 bits; 24/4 = 6 bits per base64 character).
Hence, if the signature was 72 bytes long, that would translate to 72/3*4 = 96 characters you require.
Now, base64 typically has a === trailer to signify the end of the encoding; are you counting that?


How to define a FHE scheme whose plaintext space is infinite using boolean circuits? There are many kinds of fully homomorphic encryption scheme by using boolean circuits. And the plaintext space $\mathcal{P} = \{ 0,1 \}$.

If there is a -bit FHE scheme, we can construct a FHE scheme which can encrypt all the messages.
For a string $x \in \{ 0,1 \}^{*}$ and $x = x_{1} \Vert x_{2} \Vert \cdots \Vert x_{n}$, we can define
$$\mathrm{Enc}_{pk} (x) = y = \mathrm{Enc}_{pk} (x_{1}) \Vert \mathrm{Enc}_{pk} (x_{2}) \Vert \cdots \Vert \mathrm{Enc}_{pk} (x_{n})$$
where $x_{i} \in \{ 0,1 \}$

However, if I want to define a FHE with $\mathcal{P} = \{ 0,1 \}^*$, there is a problem.

Naturally,
$$\mathrm{Enc}_{pk}: \mathcal{P} \rightarrow \mathcal{C}$$
$$\mathrm{Dec}_{sk}: \mathcal{C} \rightarrow \mathcal{P} \text{ or } \{\, \bot \,\}$$
$$\mathrm{Eval}: \mathcal{B} \times \mathcal{C}^* \rightarrow \mathcal{C}$$
where $\mathcal{B}$ is the set of all the boolean circuits.

Given $C \in \mathcal{B}$ such that $C \colon \{ 0,1 \}^{n} \rightarrow \{ 0,1 \}^m$, if $c \leftarrow \mathrm{Eval} (C, c_{1}, c_{2}, \ldots, c_{l})$, we have
$$|\mathrm{Dec}_{sk}\left( c_{1} \right)| + |\mathrm{Dec}_{sk}\left( c_{2} \right)| + \cdots + |\mathrm{Dec}_{sk}\left( c_{l} \right)| = n$$
and
$$|\mathrm{Dec}_{sk}\left( c \right)| = m$$
But, how can we know the size of $|\mathrm{Dec}_{sk}\left( c_{i} \right)|$ when we ask the access to $\mathrm{Eval}(\cdot, \cdot)$?

I believe we have a more fundamental problem with we try to handle arbitrary length plaintexts.

Suppose that we have any encryption scheme $\mathbb{B}$ (not necessarily FHE, or even asymmetric) that tries to handle arbitrary length plaintexts.  Suppose also we also had a $\mathbb{B}$ encrypted ciphertext, which we can see is 1000 bits long.  We don't know the key, however, we can deduce that there are, at most $2^{1000}$ possible plaintexts that this might correspond to.

What does that deduction give us (given that we don't know the value of any of those $2^{1000}$ plaintexts?  Well, it'd be a pretty good guess that the plaintext isn't more than 1 Gigabyte long, even if the decryption process could potentially have a plaintext which is longer than the ciphertext.

Because of this, there is a limit to the amount of length hiding we can do, if we try to handle unbounded plaintexts.


For public-key encryption, why does COA resistance imply CPA resistance? My professor told me:

  If a public-key crypto-system is secure against ciphertext-only attacks,
  then it is also secure against a chosen-plaintext attack.

Why is this true? Is there a proof that confirms this?

I was/am assuming that for public key encryption, COA means "other than the public key, ciphertext only".  Otherwise, any secure symmetric cipher with the key published becomes a "COA resistant" PKE scheme.  With that in mind, access to an encryption oracle cannot possibly help an attacker, since the attacker can already encrypt any plaintext using the public key. $\:$ Therefore, COA resistance implies CPA resistance. $\:$ (for public-key encryption, with my assumption on the definition of COA)


How much data do I leak if I use the first bytes of a file as AES-CBC IV? I found a piece of code that uses the first 16 bytes of the input file as IV. This immediately set off some flags in my head, but I have no idea how bad it really is. So, how bad is it? Obviously we're storing the first block in plaintext as the IV, but can we get any other information out?

The danger I see with using the beginning of a file as the IV is that the beginning of files tend to be fairly predictable.  For example. Linux shell scripts tend generally have a first line of "#!/bin/bash" - 11 characters (12 counting the Linux end-of-line LF character). If each file has a separate key this isn't much of a risk, but if the same key is used for multiple files then the IV reuse can result in problems (see this question or this question, or this question for examples)


Why is it not possible to increase the size of RSA keys indefinitely? According to this primer on elliptic curves by Ars Technica, when composite numbers get "too" big, they become easier to factorize with Quadratic Sieve and General Number Field Sieve.

While this is not explained in detail on the site, it is a common understanding that RSA encryption is in a squeeze trap where the RSA modulus is getting larger and larger as factorizing algorithms and equipment get more and more capable, at the same time getting closer to some sort of ceiling where, apparently the resulting security of the modulus drops.

Please enlighten me: Why is it not possible to increase the size of RSA keys indefinitely?

I've never heard that RSA becomes less secure when the modulus grows. Obviously the strength doesn't grow as fast as the number of bits, but that only means that it grows sub-exponentially.

If it keeps growing (without the growth going near zero) then there is no "trap". Check for instance here where the conclusion is that there is no exponential growth but super-polynomial growth of the time complexity (i.e. strength).

If you take a careful look at the article in Ars Technica then you'll see that the author mainly claims that the growth of the key size is not sustainable for low powered devices. ECC is certainly beneficial in those situations.

The statement "The gap between the difficulty of factoring large numbers and multiplying large numbers is shrinking as the number (ed: the key size) gets larger" is however false as fgrieu correctly identifies. It just doesn't grow as fast as you may at first assume. The key strength cannot be calculated the same way as with keys for symmetric algorithms.


How to know the difference between two ciphertexts without key stream in stream ciphers If I have two cipher texts lets say $C_1$ and $C_2$ of the same length encrypted through stream cipher technique using the same keystream. Let's say they are:

$$C_1: \texttt{96 C6 A1 08 E7 F2 33 3B 3F 5C AB}$$

$$C_2: \texttt{90 C6 A1 1E E6 F3 31 2B 37 4A B6}$$

$C_1$ is encrypted as ($P_1 \oplus \text{Keystream}$) and $C_2$ by ($P_2 \oplus \text{Keystream}$) where $P_1$ and $P_2$ are corresponding plaintexts.

I am asked to tell how can I differentiate between corresponding plain text $P_1$ and plain text $P_2$ from $C_1$ and $C_2$ as an attacker without knowing the keystream?

So, I think the answer would be since both ciphers are encrypted through the same key stream, they would have similarities where the same plain text and keystream value exists. In this way, I can differentiate the other parts of the plain text. Is there anything more to it?
Thanks.

Let's say $C_1 = P_1 \oplus K$ and $C_2 = P_2 \oplus K$ where $P$ is a plaintext, $K$ is the key stream and $C$ is the ciphertext.

Then if you XOR the two ciphertext together you get:

$$C_1 \oplus C_2 =\\
P_1 \oplus K \oplus P2 \oplus K =\\
P_1 \oplus P_2$$

There are all kinds of interesting properties of the XOR of two plaintext together. For instance, one of the most common characters is the space, so you can easily guess many characters by just flipping a bit (space is 0x20 or 0b0010_0000 after all). You can see that a lot of combinations are not possible or unlikely and you can perform frequency analysis.

This becomes even more powerful if you have 3 or more ciphertexts, as you can compare each and every pair, and if there are $n$ ciphertext then there are ${n \cdot (n - 1)} \over 2$ combinations to be made.


Proofs by reduction and times of adversaries I have some difficulties to understand, when we construct a reduction, how we determine the time for the constructed adversary to break a target security property.

In general these details are not explained in books.

Do you have some examples in which the time $t$ for the adversary $A$ is not equal to $t'$, the time for the constructed adversary $A'$ to break something supposed secure?

Is the time very important?
Why are the resources given to the adversary not sufficient to describe a security reduction?

Reductionist security

In a reductionist security proof for some cryptographic protocol $\Pi$
to some alleged hard problem $P$ means, that we can build an algorithm
$\cal B$ for solving $P$ if we have access to a hypothetical algorithm
$\cal A$ that efficiently breaks the security definition for the
protocol $\Pi$.

In general, showing a polynomial time reduction only shows asymptotical
equivalence of the problems. In practice-oriented security (or concrete
security) for reductionist security proofs, one wants to relate the
running times of the hypothetical adversary against a protocol $\Pi$
with the running time of the concrete reduction. This may then be seen
as showing "practical equivalence".

Tight vs. non-tight reductions

Let the adversary, i.e., the algorithm $\cal A$, take time $t$ and win
with probability $\epsilon$ in the security game of $\Pi$ and say we can
use $\cal A$ to build an algorithm $\cal B$ to solve $P$ and $\cal B$ runs
in time $t'$ and wins with probability $\epsilon'$.

Then, we are interested in tight reductions, i.e., that $t\approx t'$
and $\epsilon\approx \epsilon'$. If $\cal B$ takes much longer, i.e.,
$t'>>t$, and has much lower success probability, i.e.,
$\epsilon'<<\epsilon$, then the reduction is called non-tight (which is
not desirable).

Why not?

If the reduction is tight (and we assume that the security definition of $\Pi$ is
meaningful - which is important, as otherwise even a tight security
proof may be meaningless for practical applications of the protocol),
then we know that breaking the protocol $\Pi$ is at least as hard as
solving the alleged hard problem $P$. And then, we know that when we
take the security parameter for the protocol as the current status
indicates, then we are secure.

If on the other hand the reduction is not tight, then we only have the
assurance that the protocol $\Pi$ requires at least as much effort as a
certain fraction of what we think it requires to break $P$, e.g.,
breaking RSA, since it takes much less time to break the protocol $\Pi$ than it takes for the reduction to the problem to work. Now, this means that we may have to take a
much larger security parameter for the protocol to still achieve
reasonable security.

If we increase the security parameter, we consider the gap that is introduced between the adversary and the reduction and we need to choose them in a way that we can guarantee security of the protocol relative to the concrete reduction.

Why is this a problem?

We have to take larger security parameters, which makes the schemes
typically more inefficient. Secondly, what the advocates of
concrete security criticise, is that often a paper may not indicate that
the security reduction is non-tight and thus someone implementing the
protocol may choose the security parameters as if the reduction were tight.
Consequently, the so implemented protocol may be (highly) insecure in
practice.

A brief example

For instance, the original reduction for the RSA-FDH
(RSA full domain
hash) signature scheme is not tight. It bounds the probability $\epsilon$
of breaking RSA-FDH in time $t$ by $\epsilon'\cdot q_H$, where $\epsilon'$
is the probability of inverting RSA in time $t′ \approx t$ and $q_H$ is the
number of hash queries made by the adversary $\cal A$. Consequently, the
reduction looses a factor of $q_H$. Now, assume that you want to have a security
level of 80 bits and you assume that $\cal A$ can make $2^{60}$ queries, then
one should use a security parameter for the signature scheme such that inverting the RSA function cannot be achieved in fewer than $2^{60}\cdot 2^{80}=2^{140}$ operations. If one takes the ECRYPT recommendations
for key sizes for instance, 80 bit security is equivalent to 1248 bit for the RSA modulus. This would apply
if the reduction would be tight. However, the reduction is non-tight and one would actually require a modulus size of about 4000 bits.

Choosing the security parameter for the scheme according to the reduction (in the example 4000 bit) we can be sure that we can cope with an adversary in practice (in the example against 1248 bit RSA). Basically, we have an idea how hard it is to break RSA today and then we need to adjust the security parameter accordingly.


Blum Blum Shub vs. AES-CTR or other CSPRNGs Following on from D.W.'s comments on a previous question, what properties does Blum Blum Shub have that make it better / worse than other PRNGs? Are there significant implementation difficulties or security issues with BBS?

Blum-Blum-Shub is a stream cipher: given a short key, it produces an effectively unlimited-length stream of pseudorandom bits.  Other well-known examples of stream ciphers include AES-CTR and RC4.

Blum-Blum-Shub gets mentioned a lot by non-expert cryptographers.  I suspect this is because it comes with a "proof" of security, which sounds like a wonderful thing to have.  It might not hurt that BBS was mentioned in Applied Cryptography, and some developers may have walked away from that thinking that BBS is the bee's knees.

However, I personally don't recommend BBS.  The proof of security turns out to be highly misleading, and it comes with some fine print that makes the proof close to useless in practice.  You are probably better off using AES-CTR (AES in counter mode).  AES has been carefully vetted and is widely trusted.  AES-CTR should provide excellent security -- while also providing excellent performance.

BBS has two problems:

BBS is very slow -- excruciatingly slow.
Also, the existence of the "proof of security" is highly misleading and usually misinterpreted.  Practical folks almost always draw the wrong conclusions from the "proof of security".

These two problems are linked.   The standard proof of security says that if you choose a modulus N that is large enough, then no attacker will be able to efficiently break BBS.  However, the standard proof does not say how large N has to be, to achieve any desired level of security.  More recently, researchers have worked out how large a modulus you need, and (here comes the fine print:) it turns out N needs to be ridiculously large to have any decent level of provable security.  I'll summarize some of their results below:

Result 1. Suppose you use BBS with a 768-bit modulus.  You've read that 768 bits is enough to make factoring infeasible, so this sounds peachy.  You've read that it is safe to extract O(lg n) bits in each iteration; here n = 768, and lg n = 9.58, so you decide to extract 9 bits in each iteration.  You use it to generate a pseudorandom stream of 107 bits (about 1MB of pseudorandom data).  How much security do you get?  Answer: the security proof guarantees security against any adversary that uses at most 2-264 steps of computation.  Yes, this is an utterly ridiculous and useless statement!  To put it in plain English, the security proof guarantees absolutely nothing useful at all.

The lessons is: With natural-sized parameters, there is no guarantee that your use of BBS will be secure in practice.  The "proof of security" is useless for ordinary-sized parameters.

Result 2. Suppose you learn about this result, and decide to use a longer modulus.  Suppose you decide to use BBS with a 6800-bit modulus, and extract 5 bits on each iteration.  Suppose you extract no more than one million pseudorandom bits from the BBS generator.  Then, there is a proof showing that it will take at least 2100 steps of computation to break BBS (given plausible assumptions).  This means you should have a reasonable level of security.  My estimate is that, on my machine, producing one million bits (128KB) of output with BBS would take about 5-10 minutes, whereas with AES-CTR it would take less than a second.

In other words, to achieve even a mild degree of security in practice, BBS needs an enormous modulus -- far long than anything you'd use with RSA.  This large modulus makes BBS very slow.  It's far slower than AES -- and probably far weaker, too, as AES is believed to be safe for use even if you extract far more than one million bits of pseudorandom output.

Result 3. Here's another way to think about it.  A third researcher worked out the ratio in level of security between BBS and factoring.  He found that it's possible that there could be an attack that breaks BBS and is 1054 n3 times faster than any algorithm for factoring algorithm (for factoring the BBS modulus).  For instance, for a 1024-bit modulus (n = 1024), someone might be able to break BBS 1063 times as fast as they can factor.  Since we know you can factor a 1024-bit modulus with fewer than 1024 steps of computation, this guarantee about 1024-bit BBS is utterly useless: it is no guarantee of security at all.

As another example, for a 8192-bit modulus, the result says that there might be some clever algorithm for breaking BBS up to 1065 times faster than we know how to factor a 8192-bit modulus.  This is a huge ratio.  It says that BBS might be far easier to break than RSA is.  It means our proof of security for BBS is meaningful only if we use an enormous modulus, and only if we believe that factoring a modulus of that size is stupendously hard.  If we're willing to assume that factoring such a modulus is stupendously hard, we can deduce that breaking BBS is pretty hard; but because we need to use such an enormous modulus, the resulting BBS scheme will be enormously slow.

For more details, see the following research papers:

Another Look at Tightness, Sanjit Chatterjee, Alfred Menezes, and Palash Sarkar, Selected Areas in Cryptography 2011.
Concrete Security of the Blum-Blum-Shub Pseudorandom Generator, Andrey Sidorenko and Berry Schoenmakers, Cryptography and Coding 2005.
and, this sci.crypt post from Dan Bernstein: Re: BBS PRNG strength recommendation parameters

Footnote on terminology: Theorists sometimes call stream ciphers by the name "pseudorandom generators" (PRGs).  Confusingly, this is not the same as a "pseudorandom number generator" (PRNG).

The term "pseudorandom number generator" (PRNG) is not always used consistently.  There are two possible meanings.  Some folks use it as a synonym for stream cipher.  Personally, I prefer to reserve PRNG for a scheme that is used to generate pseudorandom numbers, using no explicit input (but somehow gathering entropy from the environment).  With my preferred terminology, you use a PRNG to generate a short cryptographic key; then you use a stream cipher (a PRG) to stretch the short crypto key into a very long keystream of pseudorandom bits.  But others use the term differently.

Given this opportunity for confusion, if the meaning of the term is not clear from context, it may be best to avoid the term PRNG.


Why is a Diffie-Hellman key exchange required when RSA is already being used for key exchange in TLS? Specifically with TLS,

What is RSA used for during key exchange?
What is Diffie-Hellman used for?
Since RSA already provides authenticity and confidentiality, why is Diffie-Hellman used during the exchange?
I've heard DH exchanges aren't secure. Is that something to be worried about in an RSA with Diffie-Hellman exchange?
If DH is used for forward secrecy. What's wrong with just generating new RSA key pairs and exchanging keys with that?

The use of Diffie-Hellman along with RSA is the one thing I don't understand about modern Public-Key Cryptography.

What is RSA used for during key exchange?

RSA can be used either (a) for signing the key agreement transcript with some other mechanism of key agreement (ciphersuites TLS_*DH*_RSA_WITH_*), or (b) for the client to encrypt a premaster secret key it sends to the server as an authenticated key agreement (ciphersuites TLS_RSA_WITH_*).

The premaster secret determines the key under which records exchanged by the peers in the session are symmetrically encrypted and authenticated, e.g. with AES-GCM.

In both cases, the server does a private key operation to prove its identity: in (a), it signs the key agreement transcript with the server's long-term public key, producing a signature that the client (and anyone else) can verify; in (b), it decrypts the client's premaster secret key, proving it is able to decrypt messages encrypted to the server's long-term public key.

Note that in TLS 1.3, RSA key agreement is going away.

  What is Diffie-Hellman used for?

Diffie–Hellman, over finite fields or over elliptic curves, can be used for ephemeral or static key agreement.

In the ephemeral case, both parties generate and exchange a fresh key pair and use it to agree on a premaster secret key, which they then authenticate by another means, such as an RSA or ECDSA signature.  (Note that in principle you could use DH for key agreement and authentication, but nobody does this in TLS.)

In the static case, at least one of the parties, typically the server, has a long-term DH public key, which the other party, typically the client, combines with a DH private key to derive a premaster secret.  The server proves its identity by deriving the same premaster secret from its private key and the client's (ephemeral or static) public key.  (Static DH isn't used much.)

  Since RSA already provides authenticity and confidentiality, why is Diffie-Hellman used during the exchange?

Diffie–Hellman provides a fast key agreement procedure, with a small number of rounds trips, that supports fast key erasure: as soon as the session is done, all copies of the DH private keys, the derived premaster secret, the derived master secret, etc., can be erased by the peers.  Fast key erasure means compromising the long-term identity keys does not enable retroactive decryption of the session.

In contrast, with RSA key agreement, future compromise of the server's long-term identity key trivially enables an adversary to retroactively decrypt past sessions, because the session keys were all encrypted to the server's long-term identity key.

  I've heard DH exchanges aren't secure. Is that something to be worried about in an RSA with Diffie-Hellman exchange?

There are lots of security issues one might be concerned about.  Maybe your friend is concerned about historical mistakes in supported ciphersuites; maybe your friend is concerned about timing side channels in finite-field arithmetic over general primes; maybe your friend is concerned about dynamic DH group choices and insufficient validation; maybe your friend is concerned about choices of elliptic curves.  But I can't read your friend's mind: you'll have to be more specific.

  If DH is used for forward secrecy. What's wrong with just generating new RSA key pairs and exchanging keys with that?

You could generate a fresh RSA identity key for every session, ask your certification authority to sign a certificate for that key, and then use that for RSA key agreement.

This would be the most stupidly expensive TLS stack ever, because generating RSA keys is extraordinarily expensive compared to generating DH keys (and takes an unpredictable amount of time to boot), sensible certification authorities store their keys in hardware security modules that you don't want to have attached to your TLS front ends, and sensible certification authorities have elaborate audit trails around certificates including Certificate Transparency logs that you can explore at crt.sh.

You could devise an RSA-based key agreement protocol with ephemeral RSA keys and without involving your CA, but RSA keys are still extraordinarily expensive to generate, and it would take additional round-trips between the peers, and you would still have to find some way to authenticate them.


Detecting steganography in the stream of short messages I have stream of millions of short n-bit (n<30) messages generated by some random number generator. The source of random number generator is not available to me.

I suspect there are messages used to convey information generated by some third parties and injected into the stream. I what to test the hypothesis of such messages existing.

As far as I understand, the injecting of such messages would lead to the existence of at least two different sources of randomness: the one from original random number generator and the rest from encryption algorithms used by third parties. So testing my hypothesis is equivalent to detecting those modes.

My knowledge of random number generation is very limited and I would appreciate all kind of hints, pointers, ideas and references to the relevant literature.

Adding twist on this question.
Suppose I control the PNRG of the source (source sending only random messages without payload). Third party wants to hide their messages in my stream.

The new questions:

Can I identify those messages injected if PRNG of the source (algorithm) in given to me?
Can I choose or modify PRNG in such way to allow injected messages to be identified?
Can third party identify the PRNG of the stream being modified in such way to allow for easy detection of non-source originating messages?

Proof of security:

Let $(x_1, ..., x_n)$ be the messages you caught.

Let $(p_1, ...)$ and $(q_1, ...)$ be three streams of random messages known to both communication partners. Let these be from a true random number source generating non-autocorrelated data.

Let $(n_1, ...)$ be another stream of data from the same source.

Since there is no correlation, it is impossible to distinguish $p_k$ from $q_k$ or $n_l$ without knowing the actual data stream.

To communicate, now pick $p_k$ if bit k of your message is $0$ and $q_k$ if it is one. If you do not wish to communicate simply send $n_k$.

Note: This all depends on a true RNG. When utilizing a PRNG, this is possible, however there exist security proofs http://en.wikipedia.org/wiki/Blum_Blum_Shub that have a security guarantee that makes this at least as hard as integer factorization.

For your twists, it really becomes a question of how much information you and the attackers have:

No. Again, Cryptographically secure RNGs are indistinguishable from true RNGs with reasonable computation power (otherwise they would not be secure...) and therefore, without knowing more about its seed, any sequence of messages is a legitimate output. Even slight shortcomings can be circumvented by utilizing an injection method like the above that uses another (differently seeded) PRNG of the same type.
Sure. Just break it. If you restrict the number of possible messages to 1, injection is only possible through side channels (e.g. the number of messages, their arrival timing, etc). Whether you can detect these depends on your exact setup.
At this point, it is not even about PRNGs anymore. If your adversary just added a MAC http://en.wikipedia.org/wiki/Message_authentication_code to their messages, they can detect your attempts at forging. (Note that this is only very losely related to question 2).


Exponent operation over element of G I found a definition of an exponent operation over the element of $\mathbb{G}$ in this paper (page 4):

$$ (g^a)^{\% b} = g ^{a \text{ mod } b}$$

I couldn't understand the rest of the paper (Decrypt primitive).

We have $D = g^r g^{M_S} = g^{r + M_S}$

How could they compute: $(D)^{\% M_T}$. In this paper, they have written it in a form:

$$(D)^{\% M_T} = g^{(r + M_S) \text{ mod } M_T}$$

But the exponentiation in $D$ is already computed, we cannot run the $\text{ mod }$ operator before the exponentiation.

Here are captures of the paper:

Thank you in advance for your help.

Assuming that $M_T$ is the order of $g$, then it's real easy to compute $(D)^{\%M_T}$: it's the value $D$.

That is, if $M_T$ is the order of $g$, then we have the identity $g^x = g^{x \bmod M_T}$ for any $x$, and in particular, $g^{r + M_S} = g^{(r + M_S) \bmod M_T}$.

The paper is just noting that the $\bmod$ operation happens implicitly here.

BTW: I've never seen the notation $(g^a)^{\%b}$ before; I don't believe that's very standard...


Inversion Free Elliptic Curve Operations Is there a way (different than projective closure) to obtain inversion free elliptic curve addition formulas ?

Pick pretty much any projective coordinate system, and there is a plethora of inversion-free addition formulae.  For example, here's a library of inversion-free formulae for addition and doubling in short Weierstrass curves with $a = -3$, which covers all the NIST prime curves and many curves deployed for DH and signatures before Curve25519, using standard projective coordinates: https://hyperelliptic.org/EFD/g1p/auto-shortw-projective-3.html

However, if you want affine coordinates in the end, I don't think you're likely to find a way to avoid inversions altogether—at best you can put off inversions until the end and do only a small number of them, possibly only 1, depending on what you're doing.  E.g., $x$-restricted scalar multiplication on a Montgomery curve—as used by the X25519 Diffie–Hellman function—requires only one inversion at the end of the computation.


Extract private RSA key from USB cryptographic token using Bardou et al. attack (variant of "million message attack") There is a side channel attack on tamper-resistant USB cryptographic tokens using padding-oracle, described by Bardou, Focardi, Kawamoto, Simionato, Steel and Tsay, titled "Efficient padding oracle attacks on cryptographic hardware" (INRIA; CRYPTO 2012, LNCS Volume 7417, 2012, pp 608-625), full paper, brief description. This attack uses vulnerabilities in implementation of PKCS#1v1.5 padding and is an evolution of "million message attack", discovered by Bleichenbacher. Bardou was able to cut cost of attack from 1 million decryption requests down to several tens of thousands requests.
My question is: If somebody owns an vulnerable USB token (listed in the paper), and there is a single RSA key recorded inside this token, can he setup this attack to extract stored private key from this token?
Update: there is FAQ on Bardou web-site: http://www.lsv.ens-cachan.fr/~steel/efficient-padding-oracle-attacks/faq.html

What are the prerequisites for these attacks?
You need access to the UnwrapKey function. This could be achieved, for example, directly by putting malware on the host machine, or indirectly if the unwrap key functionality is exposed via a network protocol.
What are the consequences of these attacks?
The modified version of the Bleichenbacher attack reveals a plaintext encrypted under an RSA key. That plaintext, in the context of the PKCS#11 UnwrapKey command, is a symmetric key. The same attack can also be used to forge a signature, though this takes longer. Our paper gives full details.
The Vaudenay CBC attack may reveal either a symmetric key or a private RSA key if it has been exported from a device under a symmetric cipher like AES using CBC_PAD.
Do the attacks in the paper reveal the private half of RSA keypairs?
Like the original algroithm, our version of the Bleichenbacher attack does not reveal the private half of the RSA key used for encryption.

Riccardo Focardi has online paper Practical Padding Oracle Attacks on RSA with nice description of padding attacks, including Bleichenbacher and Bardou. He also gives a link to Nate Lawson's repsonse to RSA claims (a-la Our tokens are not vulnerable). And after this paper RSA again says: "No smartcard cloning"

Their attack does not recover the private key.  Instead, it gives the attacker a way to decrypt an arbitrary ciphertext of the attacker's choosing.  (This is not the same thing.)

If the attacker has a ciphertext $c$, the attacker can query the hardware device tens of thousands of times and then based upon the responses, deduce what the decryption of $c$ is.  If the next day the attacker runs across another ciphertext $c'$ that he wants to decrypt, he needs to issue another tens of thousands of queries to the hardware device.  That's pretty bad -- but it's not as bad as revealing the private key.

So, the answer to your question is: no, their attack does not reveal the private key.

(I think all of this is already covered in the links you mentioned in the question, so I'm not sure whether I understood what you were asking.)


ECB vs. CBC, I've seen the pictures, but what's the actual strength difference? I hope that this is not a duplicate because I'm looking for nuance.  I understand the difference between ECB and CBC for a block cipher, and I understand that ECB is susceptible to replay attacks, but my question is just from the standpoint of strength.  If I have cipher that has 256-bit key and 128-bit data that is used to encrypt a file on a disk, the mathematical complexity does not increase between CBC and ECB for cracking the cipher?  I read a lot of answers saying "ECB is insecure", but there's a difference in theory and practice.  I expect to only have 1k 128-bit blocks.

I have an extremely power constrained system, and I'm trying to determine if the 10% overhead required for CBC over a ECB architecture matters from the standpoint of security.  The reason is that if I do have a significant gain using CBC over ECB, perhaps I should just use a smaller cipher size because I'd basically be trading up circuits.

Any suggestions from the engineering perspective would be appreciated.

There is no good way to calculate a strength difference between ECB and CBC. ECB is broken as a generic cipher - it is not indistinguishable under chosen plaintext attack - as repeating blocks will confer information to an attacker. That particular piece of information doesn't let itself be quantified compared to the amount of bits within the key. It's even completely separate from the key size by definition (AES-256-ECB will be as broken as AES-128-ECB).

CBC with a static IV is vulnerable for the first blocks that could be identical. CBC with a predictable IV is vulnerable as well. However CBC - when used correctly - is secure for confidentiality of data at rest.

The key stays protected by the block cipher itself. If that's "cracking the cipher" then any mode is OK. However, the key only exists to protect the confidentiality of the plaintext. And if that is compromised the security of the system is compromised. So the security of the cipher is inconsequential.

Side note: replay attacks can happen in transport security. They can happen even if the ciphertext is authenticated. Replay attacks have little to do with ECB or CBC mode as neither is a good fit - on its own - for transport mode security. ECB mode is simply susceptible to repetition of plaintext blocks; that's different from replay attacks.


Is there a library that output LFSR images given parameters? I'm looking for a library that given parameters; feedback polynomial, initial values then it will produce $\LaTeX$ / Tikz codes to include in Latex documents or LFSR images. Is there such a library?

This Question and answer are provided to test the limits of this Meta question.

Yes, there is a python library LFSR-Automatic-Draw  that can output $\LaTeX$ Tikz code and that can be converted to PNG images by
pdflatex -shell-escape lfsr.tex
The library has many parameters to draw;

One can print the feedback polynomial on the bottom
One can enable/disable printing the name of the boxes
One can  enable/disable printing the initial values
Font size, box sizes, colors, arrow sizes, etc.

Sample outputs are

And, the library now can output multiple images per clock that can be converted to loop-animation


Verify signature from set of public keys, but not revel which specific key it was Does a system exist where it is possible to verify a signature is from a public key in a specific set of public keys, but also not know which key it was?

The idea being you know a member of a group signed the message without reveling who it was.

Yes:  https://en.wikipedia.org/wiki/Ring_signature

$\color{white}{I needed twenty-five more characters.}$


Describing Discrete Logarithm Assumption I'd like to work out how exactly we should describe the discrete logarithm assumption (say, if we are writing a paper).

Consider this:

Let Gen be a group-generation algorithm on input $1^n$, which outputs a group description $(G, g, p)$ where $G$ is a group, $g$ is a generator of $G$, and $p$ is the order of the group.

Let $(G, g, p)$ be outputted by $Gen(1^n)$.  Select $a \in_R \mathbb{Z}^*_p$. We say the discrete logarithm problem is hard with respect to $Gen$ if for every probabilistic polynomial time algorithm, $A$,  there exists a negligible function $negl$ such that $Pr[A(g, g^a)= a] = negl(n)$.

My main confusion is about $a \in_R \mathbb{Z}^*_p$.

Should $a$ be chosen from $\mathbb{Z}_p$ not $\mathbb{Z}^*_p$ ? After all, $p$ is the order of $G$, so we should be able to pick any element from $G$?
Is $\in_R$ a common notation? I've also seen $\leftarrow_R$. Does it make sense as something that says we are picking $a$ uniformly at random?
Instead of $a$, should I say that we choose $h \in_R G$? That is, choose a random group element rather than a random exponent?
Should the probability be equal to $negl(n)$ or $\leq negl(n)$? Does it matter, and why?

Should $a$ be chosen from $\mathbb{Z}_p$ not $\mathbb{Z}^*_p$ ? After
  all, $p$ is the order of $G$, so we should be able to pick any element
  from $G$?

Yes, $\mathbb Z_p$ should be used as there is not reason to require that the $a$-th root needs to exist for arbitrary elements.

  Is $\in_R$ a common notation? I've also seen $\leftarrow_R$. Does it
  make sense as something that says we are picking $a$ uniformly at
  random?

$\in_R$ is somewhat common, as are $\gets_R$ and $\stackrel{\$}{\gets}$, ideally you will pick one notation and clarify its meaning in a dedicated "notation" section or you just embed the relevant clarification into the wording, e.g. "Select $a\in_R\mathbb Z_p$ uniformly at random".

  Instead of $a$, should I say that we choose $h \in_R G$? That is,
  choose a random group element rather than a random exponent?

The definition from the Introduction to Modern Cryptography by Katz and Lindell uses a random group element here, but given that $g^x$ is a random group element for random choice of $x$ and that $g$ is a generator, so there exists exactly one $x$ for each group element, I'd say these definitions are identical.

  Should the probability be equal to $negl(n)$ or $\leq negl(n)$? Does
  it matter, and why?

As $\operatorname{negl}(n)$ is any function that grows slower than any polynomial it doesn't matter whether $=$ or $\leq$ is used. However $\leq$ would seem more natural, as you are essentially "bounding" the probability to be negligible and $\leq$ immediately conveys this bounding aspect to the reader instead of hiding it behind the definition of $\operatorname{negl}$.

Just for the fun of it, here's the definition from the aforementioned Introduction to modern Cryptography by Katz and Lindell (2nd edition):

$\newcommand{\opn}{\operatorname}\newcommand{\mc}{\mathcal}$

  The discrete-logarithm experiment $\opn{DLog}_{\mc A,\mc G}(n)$:

  Run $\mc G(1^n)$ to obtain $(\mathbb G,q,g)$, where $\mathbb G$ is a cyclic group of order $q$ (with $||q||=n$), and $g$ is a generator of $\mathbb G$.
  Choose a uniform $h\in\mathbb G$.
  $\mc A$ is given $\mathbb G,q,g,h$ and outputs $x\in\mathbb Z_q$.
  The output of the experiment is defined to be $1$ if $g^x=h$, and $0$ otherwise.

  Definition 8.62 We say that discrete-logarithm problem is hard relative to $\mc G$ if for all probabilistic polynomial-time
  algorithms $\mc A$ there exists a negligible function $\opn{negl}$
  such that $\Pr[\opn{DLog}_{\mc A,\mc G}(n)=1]\leq\opn{negl}(n)$

The book priorly defines $\mathcal G$ to be a function generating a group and $||\cdot||$ to be the bit-length of a number.


RIPEMD versus SHA-x, what are the main pros and cons? RIPEMD is a family of cryptographic hash functions, meaning it competes for roughly the same uses as MD5, SHA-1 & SHA-256 do. The Wikipedia page for RIPEMD seems to have some nice things to say about it:

"designed in the open academic community"
"not [...] constrained by any patents"

I rarely see RIPEMD used in commercial software, or mentioned in literature aimed at software developers. This old Stackoverflow.com thread on RIPEMD versus SHA-x isn't helping me to understand why.

What are the pros and cons of RIPEMD-128/256 & RIPEMD-160/320 versus other cryptographic hash functions with the same digest sizes? Why isn't RIPEMD seeing wider commercial adoption?

Initially there was MD4, then MD5; MD5 was designed later, but both were published as open standards simultaneously. MD5 had been designed because of suspected weaknesses in MD4 (which were very real !). So MD5 was the first (and, at that time, believed secure) efficient hash function with a public, readable specification. MD5 was immediately widely popular.

The original RIPEMD was structured as a variation on MD4; actually two MD4 instances in parallel, exchanging data elements at some places. RIPEMD was somewhat less efficient than MD5. Also, since it is based on MD4, there were some concerns that it shared some of the weaknesses of MD4 (Wang published collisions on the original RIPEMD in 2004). Last but not least, there is no public freely available specification for the original RIPEMD (it was published in a scientific congress but the article is not available for free "on the Web"; when I implemented RIPEMD for sphlib, I had to obtain a copy from Antoon Bosselaers, one of the function authors). So RIPEMD had only limited success.

NIST saw MD5 and concluded that there were things which did not please them in it; notably the 128-bit output, which was bound to become "fragile" with regards to the continuous increase in computational performance of computers. So they designed "SHA" with a 160-bit output, soon amended into SHA-1 (the older SHA being colloquially renamed "SHA-0"). Being backed by the US federal government is a strong incentive, and the NIST did things well, with a clear and free specification, with detailed test vectors. So SHA-1 was a success.

The authors of RIPEMD saw the same problems in MD5 than NIST, and reacted with the design of RIPEMD-160 (and a reduced version RIPEMD-128). RIPEMD-160 appears to be quite robust. However, it appeared after SHA-1, and is slower than SHA-1, so it had only limited success. The most notable usage of RIPEMD-160 is within PGP, which was designed as a gesture of defiance against governmental agencies in general, so using preferring RIPEMD-160 over SHA-1 made sense for that.

Since then the leading role of NIST in the definition of hash functions (and other cryptographic primitives) has only strengthened, so SHA-2 were rather promptly adopted, while competing hash functions (such as RIPEMD-256, the 256-bit version of RIPEMD-160, or also Tiger or Whirlpool) found their way only in niche products.

Summary: for commercial adoption, there are huge bonus for functions which arrived first, and for functions promoted by standardization bodies such as NIST.

As for the question of whether using RIPEMD-160 or RIPEMD-256 is a good idea:

RIPEMD-160 received a reasonable share of exposure and analysis, and seems robust. But its output length is a bit too small with regards to current fashions (if you use encryption with 128-bit keys, you should, for coherency, aim at hash functions with 256-bit output), and the performance is not fantastic. The usual recommendation is to stick with SHA-256, which is "the standard" and for which more optimized implementations are available.
RIPEMD-256 is a relatively recent and obscure design, i.e. it did not receive as much attention as the SHA-*, so caution is advised.

So my recommendation is: use SHA-256. You will probably not get into actual security issues by using RIPEMD-160 or RIPEMD-256, but you would have, at least, to justify your non-standard choice.


Text messaging application - AES with or without message authentication I want my application to have confidentiality and integrity.

Let's say I have managed to securely share an AES key between two parties in my messaging application.

The applications communicate by sending XML messages. The XML has two tags, one for the actual text message and one for the timestamp the message was sent. This is in order make sure a replay attack cannot take place.

The XML message is encrypted with the AES algorithm and then it is sent to the recipient.

Should in this scenario add message authentication? Since the key is only known by the two parties, it should be enough to provide both confidentiality and integrity.

The worst case scenario I can think of, is someone sending a random stream of characters which will be decrypted successfully in a well formed XML message with a correct timestamp, since in any other case the message will be ignored by the receiver.

Non-authenticated symmetric encryption is malleable, meaning that an attacker who intercepts an encrypted message can modify it in ways that result in (at least partially) predictable changes to the decrypted plaintext even if they do not know the encryption key.

The exact ways in which this can be done depend on the mode of operation used, but the most obvious examples are streaming modes like CTR and OFB, where simply flipping any bit of the ciphertext will flip the corresponding bit of the plaintext.  Thus, an attacker who could guess a part of your encrypted XML message could manipulate it in nearly any way they like by replacing characters with different ones — replacing authorized user IDs with a different ID, changing ="false" to ="true" , altering the XML markup itself, etc.

Other non-authenticated encryption modes like CBC are malleable in less obvious ways, such that modifying the ciphertext will, as a side effect, typically garble at least some of the nearby plaintext in unpredictable ways.  However, it may still be possible to modify messages encrypted using these modes, if the attacker can arrange their modifications so that the garbled parts of the resulting plaintext will be ignored by the recipient (e.g. by wrapping them in an XML comment).

The point of all this is that, if you want your encryption to be secure against active attacks (i.e. attacks that may involve the attacker constructing their own messages, possibly by modifying intercepted ones), then you need some form of message integrity protection.  This can be achieved by applying a MAC on top of a traditional non-authenticated encryption mode, or by using an authenticated encryption mode that handles both confidentiality and integrity protection.  You could even achieve it e.g. by digitally signing all your messages with some public-key signature scheme.  But if you allow an attacker to actively send forged messages and don't have some way to detect it, they can do a lot more than just "sending a random stream of characters".


Cracking linear congruential generator knowing a, b, m and scaled numbers I was reading the book "Cryptographic engineering", one of the variation of linear congruential formula is as follow: $X_n = a_1X_{n-1} + a_2X_{n-2} \pmod {2^{31}-1}$

$a_1$ and $a_2$ are two prime numbers respectively

Given 50 scaled consecutive number $[s_{1}, s_{2}, ... s{50}]$, is there an efficient way to work backward?

If brute forcing is used, it will need to go through $2^{64}$ numbers.

What would be the efficient way to solve the formulas?

Given an equation (for any modulus $Y$)

$$X_n = a_1 X_{n-1} - a_2 X_{n-2} \mod Y$$

you can just transform it into:

$$X_{n-2} = a_2^{-1}(a_1 X_{n-1} - X_n) \mod Y$$

So with $X_n,X_{n-1},a_1,a_2$ you can calculate $X_{n-2}$ directly. Furthermore: $a_2^{-1}$ is not division in the real numbers, but the multiplicative inverse in a finite group / ring, also called modular multiplicative inverse. If $a_2$ is coprime to $Y$, this inverse exists.


Curve25519 - Alice can decrypt her own message to Bob? I'm developing an application with multiple clients and one server.  All clients will have the same hard-coded Curve25519 key pair as well as the server's public key.  The server will have its own key pair as well as the clients' public key.

The idea was to allow communication between server and clients without any concern that the data from one client could be intercepted and decrypted by an attacker possessing the client key pair, nor could they originate messages that appeared to be from the server in order to control other clients.

I'm using libsodium and the crypto_box functions, and noticed that the following scenario works, which really puzzles me:

Alice has a key pair, pKa and sKa.
Bob has a key pair, pKb and sKb.
Each also have each other's public key (pKa and pKb)

Alice wants to send a message to Bob, so she passes pKb and sKa to crypto_box.
Bob can decrypt the message by passing pKa and sKb to crypto_box_open.
However, Eve has a copy of Alice's key pair and intercepted the outgoing message.  She uses crypto_box_open and passes in pKb and sKa, the same keys that were used to encrypt the message. This yields the plain text message.  She changes the message, re-encrypts it, and sends it on to Bob.

I'm relatively new to crypto, so I'm sure I must be doing something wrong or just misunderstanding the application of the technology.  If someone could help me out, that would be awesome.

However, Eve has a copy of Alice's key pair and intercepted the outgoing message.  She uses crypto_box_open and passes in pKb and sKa, the same keys that were used to encrypt the message. This yields the plain text message.  She changes the message, re-encrypts it, and sends it on to Bob.

As you correctly observed, Eve having Alice's private key is insecure. It allows Eve to decrypt and replace messages with arbitrary contents. In any public key encryption system it would allow Eve to at least replace messages, though some would not allow decryption.

An equally serious issue would be for messages going the other way. If Bob sends Alice a message, Eve who has Alices keys would be able to read and modify the message.

In short, private keys must be kept private. You cannot share a key-pair between multiple users unless they all trust each other completely. In your situation, the normal thing to do would be for each client to have their own key pair.


What is the entropy per Diceware word if a random symbol is inserted into a random position in the word? On the Diceware page is this little gem:

  For extra security without adding another word, insert one special character or digit chosen at random into your passphrase...  Inserting a letter at random adds about 10 bits of entropy.

By that statement, does that mean adding a random character to a random position in a Diceware word adds 10 bits to each word?

What would be the entropy per Diceware word if random printable ASCII character is used instead?

What would be the entropy per Diceware word if a random Diceware word is used as the random symbol in a random position per Diceware word?

How exactly can this be calculated?

If you add a truly random character into a truly random position of a word (uniformly chosen), you get "entropy of position" + "entropy of character" as addition to the entropy of the word. (Not exactly, it's a bit less). The entropy of character is the size of the possible characters. 64 possible characters would be $log2(64) = 6$ bits of entropy. Entropy of position are the numbers of possible positions where the character can be placed. With a word with a length of 4 characters you can get 5 positions. (length of the word plus 1. "foo" has 4 pssibilities: "?foo", "f?oo", "fo?o" and "foo?".)

Example: You got the word "hello". Now you want to add one character of a possiblity of $26+26+10 = 62$ characters (small and big letters and numbers) into the word. Possible outcome: "h9ello", "helalo", "heXllo", ...
Entropy of "hello": Let say 0, because it is a constant value in this example. Entropy of character: $log2(62) = 5.95$ bits. Entropy of position: $log2(4+1) = 2.32$ bits. Whole entropy: 8.27 bits.
Problem: That's not entirely true, because you lose a bit entropy to a specific effect. Look at the example "hello": You could add an "e" after, but also before the e in the word. It's not possible to distingush this two possibilities ("heello" and "heello"), they are the same. That's one possibility less than we have calculated. You can do this for every letter of the word. Words like "hhhhh" are even worse, because every time the random character is a "h" you can't tell where in the word it was added.


Twofish MDS multiplication I wasted the last 2 days finding literature and/or some illustrative explanations on how to perform correct multiplications against the MDS-Matrix in Twofish over $\operatorname{GF}(256)$ with $x^8 + x^6 + x^5 + x^3 + 1$.

There seems to be no method - all algorithms I found are using pre-computed MDS tables, which isn't helping me understand it at all.

Could someone provide me with a simple and easy-to-use algorithm for this multiplication?

Each byte act as a polynomial in $\operatorname{GF}(2^8)$

You will multiply the elements of the matrix in (Galois Field) $\operatorname{GF}(2^8)$ and add them in $\operatorname{GF}(2^8)$

here is a link where you can find a wonderful explanation for $\operatorname{GF}(2^8)$


Do I need to provide entropy to secp256k1_ecdsa_sign() ? using secp256k1_ecdsa_sign()  I noticed the same data signed multiple times, coming back with the same signature. I always thought that signatures are different because random data is somehow involved.

looking at my  (production) code, this is my call:

    secp256k1_ecdsa_signature sign(const pb::sha256 &in) {
        secp256k1_ecdsa_signature sig;
        if ( 1 != secp256k1_ecdsa_sign(pb::TheCTX::instance()->CTX(),
                                       &sig, in.data, key_data, NULL, NULL) ) {
            qDebug() << " error sig";
        }
        return sig;
    }

This is the function signature:

int secp256k1_ecdsa_sign(const secp256k1_context* ctx,
                         secp256k1_ecdsa_signature *signature,
                         const unsigned char *msg32, const unsigned char *seckey,
                         secp256k1_nonce_function noncefp, const void* noncedata)

Question1: Where is randomness coming from? The default secp256k1_nonce_function, when i pass in NULL is nonce_function_rfc6979.

Question2: Did I do something wrong? Can my private-keys be derived from my signed messages?

Please help... kinda freaking out.. ty

Question1: Where is randomness coming from? The default secp256k1_nonce_function, when i pass in NULL is nonce_function_rfc6979.

Obviously, there is no randomness involved when RFC 6979 is used. The title of that RFC is "Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)". In this case identical messages will generate the same signature value.

As the RFC reads: "Even slight biases in that process may be turned into attacks on the signature schemes." So the deterministic signature scheme makes sure that the replacement of the random value doesn't have any bias. Fortunately, this is exactly what a pseudo-random-generator (PRG) is able to generate when the hash over the message is used as key. In the RFC a HMAC algorithm is used as PRG. So the true random value is replaced by a pseudo random value that depends on the message.

  Question2: Did I do something wrong? Can my private-keys be derived from my signed messages?

No, as long as the security considerations in section 4 of the RFC holds you should be fine.

Notes:

Generating the same signature value for message input is not necessarily a problem and it is not a generic requirement for signature schemes. For instance, the PKCS#1 v1.5 signature scheme is fully deterministic. However, for ECDSA, it is possible to calculate the private key value using simple mathematical equations if no (pseudo-)random value is present.
You should consider if deterministic signature generation is OK for your specific protocol. For instance, if sign-and-encrypt is used then a deterministic signature may give information about the plaintext message, breaking the confidentiality requirement (although if the signature is verifiable, this is already  the case if the signature and public key is available to an adversary).
Other API's may choose to use some kind of default secure random generator instead of deterministic signature generation. For instance, Java will use the highest priority secure random generator if no specific random generator is explicitly indicated during initialization of signature generation algorithm;


Why ssh-gen makes difference between PEM and PKCS8? Correct me if I am wrong, but PKCS8 is format to store private key info. It could be binary-enoded (DER) or Base64 encoded (PEM).

man ssh-config

-m key_format
             Specify a key format for the -i (import) or -e (export) conver‐
             sion options.  The supported key formats are: “RFC4716” (RFC
             4716/SSH2 public or private key), “PKCS8” (PEM PKCS8 public
             key) or “PEM” (PEM public key).  The default conversion format
             is “RFC4716”.

I am confused with "PKCS8 Public Key" (while RFC-5208 is "Private-Key Information Syntax Specification Version") but I also can't understand what is "PEM public key" here? PKCS8 could be PEM or DER. What does it mean?

Oh, I have found an answer. PEM here is PKCS#1 (RSA) key. Not sure why ssh-keygen used this terminology.  And PKCS#8 could be used for Public keys as well since RFC-5958 which obsoletes RFC-5208. A very good article is https://tls.mbed.org/kb/cryptography/asn1-key-structures-in-der-and-pem and this question is also good: https://stackoverflow.com/questions/20065304/what-is-the-differences-between-begin-rsa-private-key-and-begin-private-key

Here is PKCS#1(RSA):

[foo@bar ~]$ ssh-keygen -f .ssh/authorized_keys -e -m PEM
-----BEGIN RSA PUBLIC KEY-----
MIIBCgKCAQEApPGAMzobORnBJdPD0VvBif0cBkRC1KgTi4rDmscp+4F8Ke6nE/jE
.....
rf/DnkvPoJPiRLBnyjmyWsQ0dWHnRbSZSwIDAQAB
-----END RSA PUBLIC KEY-----

And here is PKCS#8

[foo@bar ~]$ ssh-keygen -f .ssh/authorized_keys -e -m PKCS8
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEApPGAMzobORnBJdPD0VvB
...
yk/avnG/lceGqChXgjxcHEKQRJYZRTnqrf/DnkvPoJPiRLBnyjmyWsQ0dWHnRbSZ
SwIDAQAB
-----END PUBLIC KEY-----


how to mathematically prove a key exchange algorithm I want to know the basic methodology that can be used to prove that a key exchange algorithm is secure. I am not asking about any specific algorithm. I want to know what should be proven and how to prove in an abstract way.

I guess the best place to begin is with the paper that started it all: Entity authentication and key distribution, by Bellare and Rogaway. In a nutshell, they define a protocol to be a secure mutual authenticated key exchange if it fulfills the following four criteria (I will explain the term "matching conversation" below):

Matching conversations $\Rightarrow$ both parties accepts, meaning that both parties believe they are participating in an authentic session. Note that this is criteria is basically a simple "sanity check" of the protocol: if there are no adversaries the protocol should "work".
If a party accepts $\Rightarrow$ there should exist some matching conversation out there. This is the first "real" security requirement. What this basically says is that a protocol provides secure mutual authentication if all that an adversary is able to do is act like a wire between the protocol participants. An adversary which faithfully relays all protocol messages between the parties is called a benign adversary.
Benign adversary $\Rightarrow$ both parties obtain the same key and in accordance with the distribution chosen for the key space. Again, this is basically a sanity check of the protocol.
Session key is protected. This means that if the parties managed to agree on a shared key, the attacker should not be able to learn anything about it. This is formalized by a game between a challenger (one of the parties) and the adversary, where the challenger gives the adversary either the real key or a random string (from the same distribution). If the adversary is not able to distinguish these two settings, we say that the session key is protected.

Thus if you are to prove a key exchange algorithm secure you need to show that it provides the four points above. Usually you do this using a reduction to an underlying assumption, like the existence of secure encryption functions and MAC's. The term matching conversation means that if party A sent out ($\alpha$) and received ($\beta$) the following messages: $(\alpha_1, \beta_1), (\alpha_2, \beta_2) ... (\alpha_n, \beta_n)$ (in that order), then B have a matching conversation if he received ($\alpha$) and sent out ($\beta$): $(\alpha_1, \beta_1), (\alpha_2, \beta_2) ... (\alpha_n, \beta_n)$ (in that order). There are some more technicalities to this definition dealing with who sent the first message and so on, but the gist of it is that A and B have matching conversations if they received what the other party sent out (and in the right order).

Note that this is only one approach to this subject and is by no means the right way of defining a secure key exchange. Another common approach e.g. deals with a simulation framework of interactive turing machines, and proves that a protocol simulates an ideal functionality defined in this model. These are in some sense much more elaborate and complex than the simple approach given by Bellare and Rogaway, but are also much more general.


Trusted Third Party Cryptanalysis Labs? There's no doubt that third party cryptanalysis is an essential part of the crypto ecosystem.  It's how we know that there's some degree of practical "goodness" to a new algorithm or protocol.

Unlike a number of other information products, a robust third party testing, analysis and validation industry doesn't seem to have evolved for crypto.  For example, NIST's CAVP and CMVP are very specific and focused in scope while the Common Criteria PP's are focused on modules and implementations rather than the constituent algorithms.

Are there trusted third parties - labs, academic institutions, government agencies, to whom new algorithms and concepts can be submitted for cryptanalysis?  If so, who are they and how can one contact them?

Many thanks,

Adam

Does such an entity exist?

No, not really.  There isn't any organizations who's in the business of doing public cryptanalysis, and there certainly aren't any organizations that are sufficiently trusted for the cryptographical community to say "we know algorithm X is secure - organization Y said so".

Let's go through the likely suspects:

NSA (and other TLAs) - they have the internal resources to do a decent cryptanalysis, and while it's not guaranteed to catch everything, they'll catch most weaknesses.  However, they are certainly not in the business of soliciting contributions, they are most certainly not interested in publishing their results, and even if they did, no one would trust that they're revealing all that they know.
NIST (and other standards bodies) - you might think otherwise, but they typically don't have the resources to do an exhaustive analysis themselves (NIST, at least, does have the resources to analyze results found by other people, but they don't pretend to have the wherewithal to do it entirely in house).
IACR - actually, the IACR is not in the business of doing cryptography; instead, they're there to promote cryptographical research in others (and they do a very fine job at that IMHO).  If you want to organize a cryptographical conference, the IACR might be of some help; if you want some cryptanalysis done, well, the best the IACR can do is point you at some relevant researchers.
Private organizations - I believe that there a few companies that will accept submissions, and publish analysis on them (for pay); however at present, most of them consist of a single researcher who will do analysis for hire.  Not horrid; however they don't have the "clear credentials" that everyone will accept as weighty (assuming, of course, that they don't find anything).

You appear to be wondering "there's CAVP and CMVP, which people accept; why isn't there the analogue for cryptanalysis?".  Well, CAVP and CMVP is mostly a list of checkboxes; the reviewer has a list of requirements (things like: encrypt this AES block with this key; did you get that result); meet all those requirements, and you'll get the certification.

Cryptanalysis can't be put into such a checklist - instead, the analyst needs to figure out if there are any clever ways to break the system - it's hard to put cleverness as a checkbox item.

And, ultimately that's why there aren't any 'trusted organization'; even if someone where to say 'looks secure to me', there's always the possibility that someone else would find something.  The best we have is have a lot of independent people look at it; it's possible that everyone missed something, but it's less likely.


Confused with the role of AES round keys AES works when each plaintext block is arranged in a 4x4 array of bytes called states. State goes through 10 rounds of encryption consisting of 4 operations: bytesub, shiftrow, mix columns and add round key. I know how it all works but in preparation for my exam I have two  questions which I don't understand.

How will the algorithm be affected if the addroundkey wasnt used in any round? Also in another scenario where In each round, in the Add Round Key, instead of computing a bitwise XOR between the state and the key, what would happen if we use a bitwise OR?

My theory is that if the addroundkey wasn't used, then attackers can easily reverse the operations because the symmetric key isn't required.

You are correct: if the AddRoundKey step is skipped, no key material is ever used, so decryption is trivial.

In case of using a bitwise OR, information would be lost in the encryption process. XOR is reversible, but OR isn't, so no decryption would be possible.


Cloneability of AES-128 I would like to implement an anti-counterfeiting scheme for tools my company manufactures. This would ideally be done via RFID/NFC tags. However, the environment in which these tags operate would either be behind a heavy firewall or not web-enabled at all. So a database of unique, valid numbers isn't feasible. I'd rather have some sort of generic key programmed to the tag that the software could then verify. However, since all the tags will contain common data, this presents the possibility that a tag could be cloned since the data (or at least a portion of it) on the tag will be identical.

In other words, I am not interested in protecting the contents of the secret message. Rather, I am concerned about ensuring that the tags cannot be cloned and then embedded on other, counterfeit tools.

While AES-128 is high security, I am questioning whether or not this encryption method is cloneable. If so, what other encryption technologies might I want to look into? I've been looking into the Algebraic Eraser and SecureRF, which use a public-key methodology.

Basically, there are two ways of doing this: the symmetric and the asymmetric way.

For the symmetric way: you put in a secret key, which can be derived from a master key. In that case it makes sense to have a static, unique UID per card, which you can use to derive a key for the tag with the master key. Then that key is put on the card, and you can then create e.g. a challenge-response protocol for it. The inspection system needs to have the master key and do the derivation as well, so to be able to verify the challenge-response.

Of course somebody being able to steal an inspection system and/or retrieve the master key from it is of course the weak point of the system. A lot of these systems have methods of using a new master key / derived key in case a master key gets stolen (and this is detected).

Of course you can also put on a private key and (card verifiable) certificate, signed by a higher level certificate. That way the inspection system can first read out the certificate, verify it using a parent certificate in a trust store, and then again verify a challenge signed with the private key. Of course, a smart card chip costs more than a chip that implements challenge-response, doubly so if it contains a private key - and therefore an asymmetric co-processor (Montgomery multiplier), because these CPU's are too slow and possibly too vulnerable against side channel attacks.

This is the asymmetric way, and it only requires a trusted public key to be present in the inspection system.

As always, with NFC tags or contactless (smart) cards, the more complex / secure the more expensive. Prices quickly go down on higher volumes though.


Montgomery Reduction I'm taking a hardware cryptography class and working on a problem that focuses on Montgomery Reduction.

So by definition:
Computing $a * b \text{ mod } N$

Pick $R$, s.t. $R > N$, $gcd(R,N) = 1$
Compute $N^{-1} \text{ mod }R$
$a’ = a * R \text{ mod } N$
$b’ = b * R \text{ mod } N$
$c’ = (a’ * b’) * R^{-1} \text{ mod } N$
$c = c’* R^{-1} \text{ mod } N$

Claim: $c ≡ a * b \text{ mod } N$

Proof: $c’R^{-1} ≡ (a’b’)R^{-1} R^{-1} ≡ (a’ * R^{-1}) * (b’ * R^{-1}) ≡ a * b \text{ mod } N$

If $R=2^k, x * R, ÷ R, \text{ mod } R$ are trivial an option to implement modular exponentiation.

Now I am ask to solve for this given the following 25 modulo 109 w.r.t. 128. The question I have is since I only have $a= 25$, does this mean there is no $b$ value?  And if that is the case, I can ignore calculating the $b’ = b * R \text{ mod } N$ expression and also remove it from calculating the $c$ equation?

Consult the transcript from the class, there is an example he works through which is very similar to this problem. Fundamentally you're trying to solve the problem c = (T + T(-N^-1) (mod R)N)/R (mod N). I suggest creating an equation in Excel (or other tool of your choice). Test your equation using the inputs from the example problem (EXAMPLE INPUTS: T=69, N=109, R=128, -N^-1 = 27). When you're confident your equation is working for that (EXAMPLE PROBLEM SOLUTION = 61), then plug in the values for this problem. Hint: T = 25 for this problem.


Differential cryptanalysis - breaking the last round of FEAL4? I've been trying to learn cryptanalysis. I've come across this resource which proved very helpful:

http://theamazingking.com/crypto-feal.php

So far I've been almost successful in breaking FEAL4 using differential cryptanalysis - I've got three of four rounds down and working on the last one. Basically the method (as I understand it, anyway) uses differential characteristics to isolate a particular subkey, allowing one to brute-force it independently of the others.

But apparently, for instance breaking the last round (as done on the webpage) yields 4 subkeys which are, from the attack's point of view, equally valid. This means the complexity of breaking the next round increases by a factor of 4, which in turn increases exponentially as more rounds are broken.

So my question is - is the method shown on the webpage "flawed" in some way, or is this result simply a consequence of the key space being so much larger than the block space (2^192 vs 2^64), which means there are many equivalent keys for a given ciphertext?

No, it's not flawed.  You're just running into a fact of life; differential cryptanalysis generally doesn't just give you the entire key (or even subkey) in one shot.  It generally gives you partial information about the key, and if you want the entire key, well, you need to work at it more.

In this phase of the attack, you know that the last round subkey is one of four possibilities. Here's one obvious way to continue the attack on the next-to-last (penultimate) round subkey: you introduce the same set of differentials advanced one round (so that it has a probability 1 of surviving the first round, and fails on round 2).  In the example they gave, this would be an input differential of 0x00000000 on the left side, and 0x80000000 on the right.

Then, for the output of each differential, reverse the last round operation (using each of the 4 possible last round subkeys), and see if there is a possible next-to-last round subkey that makes that differential work, and if so, what is that next-to-last round subkey is.

If you do this is a number of differential pairs, it is quite likely that an incorrect guess to the last round subkey will not allow any next-to-last round subkey work for at least one of the differentials; that is, for one of the differential outputs you'll have in hand, there will be no value that the round 3 subkey can take on that would make that a possible output.  That means that you can eliminate the three incorrect guesses of the last subround key.  In addition, that also gives you four possible values for the round 3 subkey.

So, to recap, this next phase of the attack verified the last round subkey, and also gave us most of the next-to-last round subkey.  It should be fairly obvious how this attack continues.  Note that continuing this attack doesn't cause any exponential blow-up, as we are able to verify the remaining subround key bits left unverified by the previous attack.

Now, if there is a problem with this example of differential cryptography, it is that it is somewhat atypical of how differential cryptanalysis usually works; it's not really misleading, but it is rather simpler in this case.  There is almost never a probability 1 differential through most of the cipher.  Instead, we generally need to work with differentials with a considerably lower probability of holding, and use statistical methods to figure out when the differential holds.


How does the sponge construction avoid the weaknesses present in Merkle–Damgård hash function? How are the weaknesses of the Merkle–Damgård construction (i.e. the Herding attack, multicollisions, length extension, expandable messages) avoided in the sponge construction?

There's two ways to answer this.  One would be to go over the individual M-D weaknesses you list and show why the sponge construction is resistant to them.  For example, if you consider length extension, the attacker knows:

The permutation $F$, capacity $c$, bitrate $r$ and padding rule used in the sponge instance;
The length of a message $m$ and its hash output $h$, but not the content of $m$.  For simplicity, we'll assume the output length is $r$.

To perform a length extension, the attacker has to guess the content of the $c$ capacity bits, and test each guess against some sort of oracle that will tell them whether they hit the correct $c$-bit combination.

The other, more general way to answer is to remark that the sponge construction is random oracle indifferentiable.  This means that any attack that distinguishes a random oracle from a random sponge can only succeed with negligible probability.  As the sponge functions page puts it:

  One could exhaustively list all the properties that a hash function should resist to and assign them resistance levels. Alternatively, claiming the security of a concrete function with regard to a model means comparing the success probability of an attack on the concrete function against that on the model. This allows compact security claims, which address all the possible properties at once, including future requirements not foreseen in an exhaustive list.


Multi Message security in Random Oracle Model I have been learning about ROM in class and was wondering what an example of an encryption scheme that is multi-message secure in the random oracle model would look like? I have learned how to prove multi-message security in the standard model but I'm not sure how this translates to multi-message security in ROM, what are the main differences / things I need to look out for between these?

The random oracle model is needed, if you work with hash-functions and want to prove security with them. The reason is, that collision resistance often does not satisfy all condition you want for a proof.
For proofs under the ROM you need a cryptosystem that uses a Hash-function. One example is the RSA Full Domain Hash Signature. I think you learned about the reduction proof. When you build the reduction you have to simulate the RO. So if you assume an adversary for the reduction, you have to simulate the communication between the adversary and the RO. This is mainly just rewriting the definition of RO, but you can also make use of some tricks: The reduction knows the communication and the reduction can "program" the result of the RO. In Katz & Lindell's textbook (2nd edition) on page 448ff you can find such a proof for the RSA Full Domain Hash Signature.
I couldn't find a proof for EAV-Mult security under ROM. But it should be pretty similar to EVA-Mult in general, expect simulating the RO.