Does a different exponent and base but same key help to resolve discrete logarithm? E.g.:

$k = N^a \mod P$

The attacker knows the prime $P$ and $N$, which is also a prime and

(1.) prime root of $P$ or
(2.) has a cycle size of $s$, so $1 = N^s \mod P$, (and for $\forall s'<s$, $1 < N^{s'} \mod P$

The attacker want to resolve variable $a$ with some discrete log. algorithm for a certain $k$.

About the $k$ he knows:

$k = M^b \mod P$

With $M \neq N$ but $M$ has same properties as case (1.) or case (2.) (same cycle size as $N$). For this equation he knows all variables $k,b,M,P$. Does the attacker help this knowledge about $k$ (in case (1.) or (2.)?

(3.) Somehow the attacker got knowledge of all variables ($a,b,N,M,P$) for one $k$. Does it help him to resolve $a'$ for other $k'$ (with same $N,M,P$), in case (1.)/(2.)?

.

side node:

The sets of generated $k$ values are equal for $N$,$M$ in case (2.):

$\{N^c, \forall c \in \mathbb{N}\}=\{M^d, \forall d \in \mathbb{N}\}=S$

with $|S|=s$. The numbers in it have just a different order. (In case (1.) $s=P-1$)

(4.)side question:

bottleneck of this would be the size of $s$, right? No matter how big $P$ is, it would not help security with same $s$.

Does the attacker help this knowledge about $k$ (in case (1.) or (2.)?

No; suppose you had an Oracle that could recover $a$ given $N, P, k, b, M$, then you could recover $a$ just given $N, P, k$ (that is, solve the Discrete Log problem).  Because we believe that the Discrete Log problem (given appropriate choices for $N, P$) is hard, we can conclude that constructing such an Oracle is also hard.

Here is how we would use such an Oracle; we already have been given $N, P, k$, and so all we need to do is construct $b, M$.  This can be done by selecting a $b$ relatively prime to $P-1$ and random otherwise; we can then compute $M = k^{b^{-1} \bmod P-1} \bmod P$; such a $b, M$ pair satisfies $k = M^b \mod P$, and so satisfies the Oracle's preconditions.  We then supply $N, P, k, b, M$ to the Oracle, and recover $a$

A similar method can be constructed for your question (3)


Match bcrypt hash with plaintext I have a bcrypt hash: $2b$10$kn7yEh2nYiDqDYNY.hjiZOtASBKT9uO4KozbFWDW2XLYnW58nkpq and a list with given plaintext passwords. How can I get the password from the list?
Is $2b$10$kn7yEh2nYiDqDYNY the salt?
TOMATCH="$2b$10$kn7yEh2nYiDqDYNY.hjiZOtASBKT9uO4KozbFWDW2XLYnW58nkpq"
SALT=b"$2b$10$kn7yEh2nYiDqDYNY."

for word in words:
    hash = bcrypt.hashpw(word.encode('UTF-8'), SALT)

    if TOMATCH == hash:
        print(word)
        break

However, with this I get ValueError: Invalid salt. What am I doing wrong here?

The bcrypt hash value consists of the following parts:

$2b — this indicates that the hash is generated according to the OpenBSD implementation of bcrypt.

10$ — this is the "cost" parameter, indicating that the password is hashed with 210 (i.e. 1024) iterations of the blowfish cipher. A higher cost parameter results in password hashes that are harder to crack by brute force.

kn7yEh2nYiDqDYNY.hjiZO — This is the 128-bit salt value, encoded in base64 as 22 ASCII characters

The remaining characters correspond to the 184-bit blowfish hash value, encoded in base64 as 31 characters.

If you check the length of your string, I think you'll find that it's actually one character short, which would explain why you're getting error messages. If this character is simply missing, you could always try appending every possible character from 0-9, A-Z, a-z, . and /. One of them ought to work.
Incidentally, I think it would make more sense to use the checkpw() function in the bcrypt module instead of trying to extract the salt yourself. Here's some code that can check every possible last character. It will take a long time to run if the word list is large.
def check_partial_hash(h, words):
    import string
    for last_char in list(string.digits + string.ascii_letters + '/.'):
        hash = h + last_char
        for word in words:
            if bcrypt.checkpw(word.encode('UTF-8'), hash.encode('UTF-8')):
                return (word, hash)
    return None

partial_hash = u'$2b$10$kn7yEh2nYiDqDYNY.hjiZOtASBKT9uO4KozbFWDW2XLYnW58nkpq'
word_list = [ u'foo', u'bar', u'asd', u'baz' ]
check_partial_hash(partial_hash, word_list)


Decrypting only message product - is it possible? Ok, I'm looking for a way to be able to decrypt ONLY message product and not individual messages. The message product can contain an arbitrary number of messages as long as it's greater than some margin. Probably it's impossible, but I need to make sure.

Suppose it's some weird inverse DKG: you have 5 shares of a public key and can encrypt messages (numbers) using any share. However, you can decrypt only product of messages, that contains at least one message encrypted with each share. However, there is NO escrow key and no possibility to decrypt just one message.

I've been thinking about id-based encryption schemes, but it always seems to have escrow key and allows to decrypt individual messages. Commitments do not work with an arbitrary number  (>=5) of messages in a product. Any ideas?

Is it even possible in theory to design such scheme?

I know, the problem is kind of weird, but it bugs me that I can't find a solution or prove that there is no solution at all.

What's wrong with the obvious solution:

Each party creates a public-private key pair.
The public key is the combination of all public keys.
Encryption is done in a nested fashion to all public keys.
Decryption is done sequentially by all holders of key shares.

If some special property of a symmetric sharing scheme is desired replace the last two with
3. Encryption is done by creating shares according to the symmetric scheme and encrypting each share with a different public key
4. Decryption is performed just as in whatever symmetric sharing scheme was desired

Of course the size of the public key is linear in the number of shares. This is just the obvious solution not a great one.


Timing attack on RSA as used by CryptoLocker? So far I have researched timing attacks on RSA, We all know the ransomware named CryptoLocker uses RSA 2048 bit encryption. Now, is it possible to break the encryption using a timing attack. I have been gathering information about CryptoLocker, it’s a ransomware which encrypts files in the system with RSA 2048 bit encryption and asks for a ransom to release the private key stored in the server and decrypt the files infected. As it is a 2048 bit encryption it is not possible to break the key, however with a side-channel attack researchers have attacked even 4096 bit RSA encryption. Timing attack is a side channel attack.

So my question is, is it possible to attack the cyber criminal's server by performing a timing attack?

No, it's not possible to recover the private RSA key; not with a timing attack, not with a debugger, not with any technical means.  There isn't enough information on the victim's computer.
The timing attack you describe requires timing the decryption operation, which could reveal the decryption key.  But the malware isn't ever decrypting anything, it's just encrypting the victim's data.  The malware doesn't even have the decryption key until after you pay the ransom.
All a timing attack could tell you about RSA keys during encryption is the encryption key, but that's just the public key that your machine's virus retrieves from their server.  The whole point of asymmetric encryption security is to separate encryption secrets from decryption secrets.
EDIT
I reread your question more carefully, and I now understand that you're asking if it's possible to attack the criminal's server, not the client-side malware.  Yes, servers can obviously be attacked.  And yes, side-channel attacks are one of the many potential tools that could be used to attack it.  But the thief doesn't operate just one server, he's operating a large farm of them; the client-side malware simply keeps testing for servers until it finds one that responds.  In order to recover your own data, you would need to identify the correct server containing your key, hack into it, and exfiltrate all the data from it before he wipes all the stored private keys (either in response to the attack or because you didn't pay him in time.)  Even if such an attack was successful, it will do little to help with future attacks as each private key is reportedly generated on request.


The encryption scheme is secure? I have a scheme and I don't know that this scheme is semantic security or not.

Secret keys $\{s_1,s_2, x_1,x_2\}$ and public parameter $p$ (large prime number).
Encryption E(m): $C_1 = s_1m + x_1k \bmod p$ and $C_2 = s_2m + x_2k \bmod p$ where $k$ is pseudo-random number.

(Note: This answer is based on $k$ being generated by applying a pseudorandom function to a unique message-ID – counter – each time.)

It depends how many times you want to encrypt with it.

If you want it as a complicated OTP, then it's secure. In order to see this, just ignore the $x$ parts and note that $s_1m \bmod p$ and $s_2m \bmod p$ are to independent encryptions under random keys $s_1,s_2$ (note that $s_1$ and $s_2$ have to be uniform in $\{0,\ldots,p-1\}$. For this, you don't need $p$ to be large (just big enough to contain $m$).

If you want to encrypt many times, then it is certainly no longer information theoretically secure. However, just ignore $s_1,x_1,s_2,x_2$ and think of them as public constants. Then, you are encrypting by $m+k \bmod p$ where $k$ is pseudorandomly generated. This is like a type of "counter mode". As long as the RANGE of the pseudorandom function is $\{0,\ldots,p-1\}$ you should be able to prove it.

In both cases, it is overly complicated…


What if n of RSA is same for two people over the network? I was just going through RSA encryption scheme and was trying to figure out how to do all maths. I was suddenly struck by the question that (e,n) is public to the people. How easy it becomes to attack one's system if you find out that you are using same n as someone else?

How easy it becomes to attack one's system if you find out that you are using same n as someone else?

I'd be pretty easy to recover someone else's private key, even if they're using a different public exponent e; you know the factorization of n (your private key tells you that), and so it'd be simple to compute the private exponent that corresponds to their public exponent.

As a follow up, you might want to estimate the probability of two people, who are using good random number generators [1], just happen to pick the same value for n, for any secure size of n (hint: how many possible values of p and q are there?)

[1]: this 'good random number generator' cavaet is needed, because we have found duplicated RSA modulii in the field; this happened because they used a bad random number generator (more specifically, bad entropy)


How to encrypt with elliptic curve cryptography (ECC)? I need to ask this, as I am not allowed to comment and don't quite understand an existing answer because I don't have a cryptography background and never looked into how ECC works.

Why can't you encrypt a message with a public key generated via ECC?
How can two peers Alice and Bob agree on shared secret (symmetric key), both of which having elliptic-curve-based public-private key pairs?
Could schemes be based on a plain Diffie-Helmann key exchange, where you use the other's public key as authentication (signing messages)?

Why can't you encrypt a message with a public key generated via ECC?

Well, for starters, you need to realize that ECC is a collective term for a number of protocols that use elliptic curves to do cryptography.  Some of these protocols (ECIES, ECElGamal) are public key encryption methods (that is, they have a public encryption key, and the private decryption key, and the public encryption key allows you to encrypt a message, but not decrypt it); with these, you most certainly can encrypt with the public key.  Of course, there are other protocols (ECDH, ECDSA, EdDSA) which do other things, and are not intended to encrypt messages.

  How can two peers Alice and Bob agree on shared secret (symmetric key), both of which having elliptic-curve-based public-private key pairs?

Actually, yes, Diffie-Hellman translates nicely to elliptic curves, that version is called ECDH, and is widely used.  ECDH works mostly like classical DH (with the minor differences being mostly the validity checking that you need to do on the public shares)

  Could schemes be based on a plain Diffie-Helmann key exchange, where you use the other's public key as authentication (signing messages)?

It doesn't make sense to use a public key as 'authentication'; to make sure that the message came from you, you need to stir in something that not everyone knows.  This could be a private signature key, or it could be a secret shared between you and the intended recipient.  If it's something everyone knows, then everyone can produce that message, and so it wouldn't actually serve as 'authentication'


Proving one time pad is perfectly secret I'm reading about one-time pad in "Introduction to Modern Cryptography" by Katz and Lindell. I can understand the definition of perfect secrecy. However, how is OTP proven to be perfectly secure ? I'm quite rusty on probability, so please explain the steps.

The proof in the book goes like this,

$M$ is the set of messages (all possible bit strings of length $\ell$), the message space. $K$ (the key space) is equal to the message space, and the cipher is computer as $c=k\oplus m$, where $k$ belongs to $K$ (chosen uniformly at random) and m belongs to $M$,
\begin{align*}
    \Pr&[C=c\mathrel|M=m] \\
    &= \Pr[M \oplus K = c \mathrel| M = m] \\&\quad\text{(How did the random variable $C$ become $M\oplus K$ here?)} \\
    &= \Pr[m \oplus K = c] \\&\quad\text{(where did the conditional probability go ? what rule should I apply here ?)} \\
    &= \Pr[K = m \oplus c] \\&\quad\text{(what is this ?)} \\
    &= 1/2^\ell \\&\quad\text{(how should I arrive at this finally ?)}
\end{align*}
I did not understand any of these four steps. Please explain the reasoning behind these steps. This result is being used to show that it satisfies the definition of perfect secrecy. Please help me understand this result.

First, be careful about case:

The uppercase letters denote random variables in some probability space.
The lowercase letters denote particular values in the domains of the corresponding random variables.

For example, if the probability space is $\Omega$, then $C\colon \Omega \to \{0,1\}^\ell$ is a random variable for the ciphertext in the one-time pad system, and $c \in \{0,1\}^\ell$ is a particular value of a ciphertext, which at some sample $\omega \in \Omega$ might be the value of $C(\omega) = c$.

The random variable $C$ is related to the random variables $M$ and $K$ by $C = M \oplus K$, which is the standard mild abuse of notation for random variables meaning that $C(\omega) = M(\omega) \oplus K(\omega)$ in any sample $\omega \in \Omega$.  Any fixed values $c$, $m$, and $k$ might or might not be related by $c = m \oplus k$, although if in some sample $\omega$ we have $C(\omega) = c$ and $M(\omega) = m$ and $K(\omega) = k$ then $c$, $m$, and $k$ are indeed related by $c = m \oplus k$.

For any fixed message $m \in \{0,1\}^\ell$, in the event $E = \{\omega \in \Omega \mathrel: M(\omega) = m\}$ where the message $M$ takes on the value $m \in \{0,1\}^\ell$, what can you conclude about $C$?  In other words, if for any $\omega$ we have $M(\omega) = m$, what can you say about $C(\omega)$?  Can you use this to eliminate $C$ from the ellipsis in $\Pr[\;\cdots \mathrel| M = m]$?

Next, if you have an equation about the random variable $K$ without reference to $M$, given an equation about $M$, recall the definition of independence of random variables and how it relates to conditional probabilities.  Finally, use the probability mass function for $K$, and you'll have an answer.


In a safe finite field elliptic curve, why is p not n? From what I understand, in order for a curve to be safe, it would appear that $n$ being the order of the cyclic subgroup of the curve, is a prime. Also, it is the theoretical upper-bound on the number of private keys the curve can issue, thus it should be a good candidate for being the limit on the size of the field.

However in practice, it looks like we always choose a different $p$ than $n$. Why do we do this? Also, I'd understand that if $p$ is smaller than $n$, but why do we sometimes have a larger $p$ than $n$? It won't be possible to have up to $p$ private keys when the subgroup has order $n$ right? Lastly, I see some tutorials referring to $p$ as the characteristic of the curve, what does that mean?

I'd love to understand the above a bit further, and I guess in general my question is, given $n$, how would I choose $p$ for a safe curve?

Also, I'd understand that if p is smaller than n, but why sometimes we have a larger p than n? It won't be possible to have up to p private keys when the subgroup has order n right?

I suspect you're using an analogy with more normal discrete log problem, where the value is a value between 0 and $p-1$; obviously, you can't have more than $p$ values.

In contrast, the standard way of viewing an elliptic curve point is that is a solution $(x, y)$ to an equation such as $y^2 \equiv x^3 + ax + b \pmod p$ for fixed values $a, b, p$ (or a special "point at infinity", an artificial group member that's needed to make the group closed).

As a point consists of two values, each of which are between 0 and $p-1$, we have $p^2+1$ values that are potential candidates to be group members.  It should be obvious that the vast majority of those potential solutions aren't actually solutions to the equation; it turns that that there will always be approximately $p$ solutions (within the "Hasse interval"); and this "approximately" can be slightly larger or slightly smaller than $p$ (but always within $\sqrt{2p}$)

  given n, how would I choose p for a safe curve?

At your level of understanding, you don't.  The issues in selecting a curve are subtle, and you currently don't know nearly enough.  Instead, you should rely on someone who does know what they are doing to choose a good curve (which specifies $p$ and $n$) for you.

  Lastly, I see some tutorials referring to p as the characteristic of the curve, what does that mean?

Elliptic curves are defined using an equation over a field; for cryptography, we always use a finite field (as we generally prefer our ciphertexts to be expressible in a bounded number of bits).  A finite field always has exactly $p^k$ elements, where $p$ can be any prime, and $k$ any positive integer. We define the characteric as the value $c$ where we always have $\underbrace{x+x\ +...+\ x}_{c\text{ times}} = 0$ for all field elements $x$ (and where addition is the field addition operation).  It turns out that, for all finite field, we have $c=p$ (even if $k>1$).

Currently, it is most common to have elliptic curves with $p$ being a large prime and $k=1$; in this case, you can perform the field addition and multiplication operations modulo $p$ (for $k>1$, it gets more complicated), and the modulus $p$ is the characteristic.


What does this protocol mean? Does this mean that the message is being added onto the hashed(message, tag) ?

m || H(m, "secret")

So the output would be something like:

"RandomMessage"+N8HqKCG01b

Yes, || means concatenation. If H means HMAC and 'secret' is a secret key then this is secure.

Usually hmac accepts key as first argument and message as second. If this protocols MACs the key using the message instead of MACing the message using the key, I don't know whether that is secure.

If H is a hash instead of a MAC, then this is insecure.


Is it okay to use a hash of a timestamp as the IV for AES? The message format includes a datetime field in the clear. Is it okay to also use this field (or some hash thereof) as the initialization vector?

In this case, CBC is the mode being used.

It depends on the chaining mode. With recent modes like EAX and GCM, the IV just needs to be non-repeating, so a timestamp is OK (as long as you take care never to issue two messages with the same timestamp: this can be a problem if you emit two messages in, say, the same millisecond, or if the sender clock is somehow reset through manual action or NTP; notably, consider that the NTP protocol is rarely protected at all, so an active attacker may play tricks on your clock).

With CBC, the IV must be uniformly random, and, depending on the situation, should be unpredictable by the attacker. For instance, if the attacker can trigger the encryption of some messages of his own choosing, he may use a predictable IV to obtain precise block encryptions which he could then use to alter some other messages in a controlled way. A timestamp is highly predictable. A tempting design would be to compute the IV with HMAC over the timestamp, using a shared secret key for that; on a general basis, use a Key Derivation Function to extend your encryption key into two keys, one for HMAC and one for the actual AES encryption (make it three keys: one for the HMAC-for-IV, one for encryption, and one for the MAC which you of course add to the message to thwart active attackers). However, making your own designs is known to be dangerous, and modes like EAX and GCM already do that job better.

To sum up: using a timestamp is a bit tricky since it is only mostly unrepeating. And it will not work well with all chaining modes.


How to solve custom made ciphers? How would you go about solving basic custom made ciphers - e.g. one generated from this website http://www.wikihow.com/Write-a-Custom-Cipher-Carefully?

This is solving it without knowing the method of the cipher beforehand.

It's not clear what they actually mean by half of their things, or if there is any benefit of using them together. That site doesn't want to create any meaningful security, it's just to play around with numbers and letters.

They state to use Vigenere, that's okay, usual classic cipher, which can be broken if the text is long enough.
"Caesar box code": I have no idea what that means, unless they mean basically the same as a Vigenere cipher with length 5. This is kind-of pointless with a fixed block size, because that's one part of what makes Vigenere decent for a classical cipher.
"Skip letter code": No idea again, what they actually do. If you leave out letters, that's just not reversible. Going backwards comes down to guessing.
Railfence is a fixed transposition of letters, which is again pretty pointless.
Reverse: Same as railfence.
Encoding with morse or similar: Fixed codes like morse are just replacing one set of symbols by another, just takes time if you do it by hand.

What do we do if we don't know what was used? Well, first security by obscurity is bad in reality, because the scenario is unrealistic against serious adversaries. But for toying around: It's not that difficult just to try the various combinations of "algorithms". A computer will probably solve any such system within seconds. Building things from classical (broken) ciphers are not maknig things complicated for today's advanced machines.


Non-interactive Zero-knowledge proof signature validation without public key I'm looking for a method for a scenario with following requirements:

At least 3 people (A,B,C,...) are in a Network where they can broadcast messages to everyone but not communicate with a specific person, so that they can't get answers to their broadcasts.

Every member has a public address "Apub, Bpub, .." (max ~100 bytes) which was derived from a private secret "Apriv, Bpriv, .."

A signs a message with Bpub and broadcasts it to the network.
B broadcasts a request (based on his Bpriv/Bpub without revealing these 2 keys) to validate, that the message from A belongs to him

Is C able to validate the request from B, without knowing Bpriv/Bpub and therefore not knowing his identity?

A shouldn't be able to proof, that the message was signed for himself without knowing Bpriv.

Are there existing code examples for this, which are free to use and free from patents?

First, before I answer your questions: Money rewards are not forbidden, as far as I know, but that's not how it goes here. Feel free to check out the according question on crypto-meta.

I think, there are few conceptual misunderstandings in your scenario.

First, a signature scheme uses the private key (also called signing key) to sign messages, and it uses the public key (aka verification key) to verify, that a signature matches to a given message (under consideration of this verification key).

Then, you also want to use the public key as address set a limit of ~800 bit, which is a bad idea, because common schemes based on RSA or Schnorr groups (like ElGamal signatures, DSA, etc.) are recommended to be larger (1240 bit at least).

And then, your scenario is quite weird, or maybe you used the wrong expressions. But if A broadcasts a message, he can not sign this message for B (signing requires the private key). If you meant "encrypt the message with the public key $B_{pub}$", it would make sense, but why would B send a request if this message was meant for him?And why would C not know the public key of B, if this was also used as address?

Maybe you should clarify your scenario, because right know I tend to the answer "no, it's not possible".


How to calculate chance of missing an error with overlapping hashes? Assume that I have a huge file, which I split up into blocks.  Each block is hashed with a hash function of $x$ bits.  The chance of an error going undetected in a block should therefore be $1/2^x$.

Now, let's assume a block is $y$ bytes in size, meaning there are $2^y$ possible values for that block of data.  As $y$ gets bigger, there are more possible collisions for any given hash value, yet the chance of such a collision occurring seems to remain the same (correct?).

For my purposes, I need to split the data in many blocks, the more the better, but the more blocks, the more hashes which at some point take quite a lot of space to store.  So I want to use a hash where $x$ can be small while still having a high chance of detecting errors.

So I got this idea that instead of hashing every block with a hash function of $x$ bits (illustation 1), I instead hash every block with a hash of $x/2$ bits.  However to ensure that it is still possible to detect errors at the same rate as before, I add a second hash over every group of 4 blocks of $x/2$ bits (illustration 2):

Illustration 1

 |-----|-----|-----|-----|   4 hashes of x bits

 Total bits = 4*x

Illustration 2

 |-----|-----|-----|-----|   4 hashes of x/2 bits
 |-----------------------|   1 hash of x/2 bits

 Total bits = 5*x/2 = 2.5*x

Are these equivalent, how do they differ if not and how can I compare them?

Another possibility would be:

 |-----|-----|-----|-----|   4 hashes of x/2 bits
 |-----------------------|   1 hash of x bits

 Total bits = 4*x/2 + x = 3*x

I couldn't find much on this topic through the usual sources.

The usual way this is performed is through a Merkle tree, of which you will definitely find information on the Internet. What you can do is to separately hash each block (for performance reasons) and then hash the hashes together (in the correct order). Then you can simply store just the resulting hash.

In your scheme you perform a hash with half output. But you only want to trust the block after you've also verified the additional hash. So basically your "half-hashes" over the blocks are pretty useless. You may just as well hash the 4 blocks together or use a Merkle tree as described above.

Note that none of your constructions is likely to have more security than the output of a single hash (the state of both the single block hash and four-block hash would be the same after the first block), even though the output is larger than that. That said, I don't directly see how it could be less than the security of a single hash either.


Combining md5 collisions to create more collisions Given X1 and X2 such that md5(X1) = md5(X2) and Y1 and Y2 such that md5(Y1) = md5(Y2), and knowing the following property of md5:

  if md5(a) = md5(b), md5(a|s) = md5(b|s)

is there a way to find Z1, Z2, Z3, and Z4 such that md5(Z1) = md5(Z2) = md5(Z3) = md5(Z4)?

Let $f$ be the compression function of a Merkle–Damgård hash function $\operatorname{MD}_f$, like MD5.  Suppose we have a cheap algorithm $C(h)$ which returns message blocks $m_0 \ne m_1$ such that $f(h, m_0) = f(h, m_1)$.  We can use this with the standard initialization vector $\mathit{iv}$ to find a two-way collision $(m_0, m_1) = C(\mathit{iv})$, so that $$\operatorname{MD}_f(m_0) = f(\mathit{iv}, m_0) = f(\mathit{iv}, m_1) = \operatorname{MD}_f(m_1).$$  Can we use it to find a four-way collision $(m_0, m_1, m_2, m_3)$?

Answer: Yes, we can use an algorithm $C$ for finding two-way MD collisions to find $2^n$-way collisions with only $n$ calls to $C$.

Let $(b_0, b'_0) = C(\mathit{iv})$.

Then $f(\mathit{iv}, b_0) = f(\mathit{iv}, b'_0)$.

Let $h_1 = f(\mathit{iv}, b_0) = f(\mathit{iv}, b'_0)$.
Let $(b_1, b'_1) = C(h_1)$.  That is, use the common hash as a new initialization vector to find a new collision.

Then $f(f(\mathit{iv}, b_0), b_1) = f(f(\mathit{iv}, b_0), b'_1))$, etc., so the messages \begin{align} m_0 &= b_0 \mathbin\| b_1, \\ m_1 &= b'_0 \mathbin\| b_1, \\ m_2 &= b_0 \mathbin\| b'_1, \\ m_3 &= b'_0 \mathbin\| b'_1 \end{align} constitute a four-way collision.

Lather, rinse, repeat for as many distinct collisions as you want.

This family of attacks, and their impact on concatenating hash functions, is described in more detail in Antoine Joux, ‘Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions’, in Matt Franklin, ed., Advances in Cryptology—CRYPTO 2004, Springer LNCS 3152, pp. 306–316.


Security of Deterministic Encryption Scheme A deterministic encryption scheme is a cryptosystem which always produces the same ciphertext for a given plaintext and key, even over separate executions of the encryption algorithm.

Although we cannot achieve semantic security or indistinguishability for deterministic encryption due to lack of randomness in cipher text, there is an analysis of maximum possible security for deterministic encryption.

I could not understand much from these papers though. Can somebody say what that means in simple terms? How can we achieve it, if we want to implement it?
I suppose I need deterministic encryption because I want to be able to search on the ciphertext.

The papers I tried to understand:

Bellare, Mihir, et al. "Deterministic encryption: Definitional equivalences and constructions without random oracles." Advances in Cryptology–CRYPTO 2008 (2008): 360-378.
Boldyreva, Alexandra, Serge Fehr, and Adam O’Neill. "On notions of security for deterministic encryption, and efficient constructions without random oracles." Advances in Cryptology–CRYPTO 2008 (2008): 335-359.

You might be limiting yourself at the wrong aspect there.

Your goal is the ability to search on ciphertext; and you just look at deterministic encryption in your set of tools.

In order to use DE securely, the messagespace HAS TO contain enough entropy in order to protect from brute-force search. The only way to solve this is adding entropy at random either in the encryption process and/or the message (e.g. extend message by a couple of random bits at the start).

But what you actually want is "Searchable Encryption", google scholar will help you out. For example Abdalla et al. published "Searchable Encryption Revisited: Consistency Properties, Relation to Anonymous IBE, and Extensions" and Boneh et al. published "Public Key Encryption with Keyword Search". However, I don't know if there are any implementations of these schemes, and probably they are quite huge: PEKS based on IBE, which is based on pairings in elliptic curves.


Challenge-Response Phases in IND-CPA The IND-CPA game has two challenge-response phases

A key is generated by running $Gen(1^n)$ and challenger selects a bit
b {0,1} uniformly at random.
Adversary gets input $1^n$.
Can query the oracle a polynomial number of times with messages and gets $E_k(m)$ back.
Attacker sends messages $m_0$, $m_1$, challenger returns $E_k(m_b)$.
Can query the oracle a polynomial number of times with messages and gets $E_k(m)$ back.

Why are these two challenge-response phases (3,5) necessary? I understand why at least one phase is necessary (ex: to ensure that deterministic algorithms are not IND-CPA secure), but why both?

You need to allow queries before the attacker outputs $m_0,m_1$ since maybe the queries help the attacker choose $m_0,m_1$ that are "easier" for it to attack.

You need to allow queries after the attacker receives back the challenge ciphertext $c=E_k(m_b)$ since knowing $c$ may make it possible to generate a plaintext whose encryption helps to know what $c$ is.


Modifying Mix Mode Modular Arithmetic in IDEA Cipher IDEA uses Mix Mode Modular Arithmetic that includes Addition Modulo $2^{16}$ and Multiplication Modulo  $2^{16}+1$. If Multiplication Modulo with  $2^{16}$ is used instead of $2^{16}+1$ (where $2^{16}$ is not a prime field) how this modification affects IDEA (specifically Decryption & Probability distribution).

If replacing IDEA's multiplication modulo $2^{16}+1$ by multiplication modulo $2^{16}$ (and dropping the replacement of $0$ by $2^{16}$ on input, and vice versa on output), then

For the cipher to be reversible, we need to use odd subkeys for these that enter a multiplier ($k_1$, $k_4$, $k_5$, $k_6$ of rounds, and half rounds for the first two). This follows from the fact that $x\mapsto k\cdot x\bmod m$ for $0\le x<m$ is reversible if and only if $k$ is coprime with $m$; that is, when $k$ is odd for $m$ a power of two.
There is no longer any operation in the modified IDEA that diffuses a bit flip to the right within a 16-bit word. This is a complete disaster. For example, it allows a trivial distinguisher: randomly changing the high order byte of 16-bit words of input has no action on the low-order bytes of the 16-bit words of the ciphertext output! And I guess key recovery (perhaps of an equivalent key) is feasible by attacking the cipher and sub-keys bit-by-bit within 16-bit words.


basic question regarding two-time pad attack Dan Boneh's Crypto 1 Course includes a lesson on stream ciphers with the following slide:

He asks the question:

And the answer he gives is $m \oplus p$, which is why this is insecure.
But I don't see why this is correct.
If:

$m = 0011$
$k = 1100$
$p = 1010$

then
$$m \oplus k = 1111$$
and
$$(m \oplus k) \oplus p = 0101$$
and
$$m \oplus p = 1001$$
so
$$m \oplus p \neq ((m \oplus k) \oplus p)$$
What am I doing wrong in the above?

This is not the two-time pad attack this is the malleability of the OTP or any stream cipher. Malleability means that the active attacker can change the ciphertext into another ciphertext that can be decrypted without any error during the decryption. That is why we need integrity and authentication.
How it works; you sent $m\oplus k$ on the communication channel, the active attacker captures (and probably stops, too) and modifies the ciphertext with $p$ then the message is $m \oplus k \oplus p$, when the receiver decrypted with key $k$ they will get the modified message $m \oplus p$. This can be very dangerous if the message is known or the format of it known. For example, the attacker can turn Attack at the noon! to Attack at the moon!
For the last equation;
$$m \oplus p \neq (m \oplus k) \oplus p$$
This is what we expected except $k=0$.


How to use ElGamal to encrypt zero? ElGamal encryption algorithm is as follows:

To encrypt a value $m$, it chooses a random value $r$, and calculates

$c_1=g^r$ $mod$ $q$

$c_2=m*h^r$ $mod$ $q$

where $g$ is the group generator, $x$ is the private key and $h=g^x$ is the public key.

But if $m$ is 0, then $c_2$ will always be 0. How to deal with this?

Well, you can't.

In standard ElGamal the message space is defined as the elements of the group $\mathbb{Z}_q^*=\{1,\ldots,q-1\}$. So $0$ is not in your message space.

You could take exponential ElGamal, i.e., encode messages in the exponent of $g$. So instead of computing $$c_2=mh^r \mod q$$ you compute $$c_2=g^mh^r \mod q.$$ Note however, that firstly your message space must be that small that discrete logs can be efficiently computed (as decrypting requires computing discrete logs). Secondly, this gives you an additively homomorphic scheme and no longer a multiplicatively homomorphic scheme.

Or as @Guut Boy correctly mentions in his comment, you may also use a simpler mapping as the above. For instance you may simply map the message space $\{0,\ldots,q-2\}$ to $\{1,\ldots,q-1\}$, i.e., adding 1 to your message before encryption and subtracting 1 after decryption, such that $0$ maps to $1$ and thus avoids the problem.

Which approach is more suitable for you depends on your application (which, however, is not clear from your question).


mutual authentication using MAC I have the following protocol for mutual authentication ($V=$ verifier, $P = $ prover, $r_V$ and $r_P$ random values, $h_k$ a keyed hash function)

$V\rightarrow P:r_V$
$P\rightarrow V:r_P,h_k(r_V,r_P)$
$V\rightarrow P:h_k(r_P,r_V)$

My question is why does the prover send back to the verifier $h_k(r_V,r_P)$? Can't he just send back $h_k(r_V)$? Or is this less secure.

(EDIT: question before edit asked about case where $r_v$ is missing from hash, that's why the answer is mostly about it:)

This would totally break security of the scheme. Assume that protocol looks like this (only change is in step 2 - missing $r_v$):

$V\rightarrow P:r_V$
$P\rightarrow V:r_P,h_k(r_P)$
$V\rightarrow P:h_k(r_P,r_V)$

Let's assume that Eve sees message from step 2. She can now start another authentication session and send to $V$ the same pair $r_P,h_k(r_P)$ again and get authenticated as $P$ (in as many separated sessions as she wants).

You can prevent this by requiring that each $r_P$ can be used only once but tracking used values is way more expensive and error-prone than simply including challenge from $V$ in hash.

Please note that if you drop $r_P$ from step 3 as well and Eve sees all messages then she can pretend to be $V$ in communication with $P$ as well.

If protocol looks like:

$V\rightarrow P:r_V$
$P\rightarrow V:r_P,h_k(r_V)$
$V\rightarrow P:h_k(r_P)$

then you can force $P$ to sign whatever message you want (impersonating $V$ ) or force $V$ to sign whatever you want performing man-in-the-middle attack and changing $r_P$. This can potentially lead to some replay attack if you use strong MAC or to secret key recovery if MAC is not chosen plaintext secure.


Simple compression functions an sponge functions for educational purposes For block ciphers, there are the very well designed schemes of Simple-DES and Simple-AES, which have been created not for security but for teaching the design principles of the real algorithms while maintaining the possibility to calculate them by hand and guarantee an easy demonstration.

Are there any such simplified functions for Merkle-Damgard compression functions or sponge functions available?

Many of the designs in the NIST SHA-3 competition came with toy variants for study.  For example:

The winner of the competition, Keccak, has parameters for:

word size—the SHA-3 standard is 64-bit, but it is formally defined for 1-bit, 2-bit, 4-bit, 8-bit, 16-bit, and 32-bit words too, for study or for smaller variants like Ketje and Keyak; and
number of rounds—the SHA-3 standard is 24 rounds, but that is overkill, so KangarooTwelve uses 12 while still providing comfortable collision resistance, and Kravatte uses 6 without aiming for collision resistance.

The popular BLAKE2 was derived from BLAKE, one of the SHA-3 finalists, which uses HAIFA, which is similar to Merkle–Damgård and Davies–Meyer but with improvements, came with several toy versions: BLOKE, FLAKE, BLAZE, and BRAKE, each with simplifications on the real BLAKE.  All admit reduced-round variants too, of course.

You could, of course, take any block cipher you like, and apply it with Davies–Meyer, or any of various block cipher constructions, and study the result.  One easy target for cryptanalysis might use AES-256 in one of those forms, so that you could apply the Biryukov–Khovratovich related-key attacks.


How to find the encoding of an RSA public key? What practical methods is there to reconstruct an RSA public key in unknown format?

As an illustration, in a database I find this (which doesn't look like ASN to me):

0x0602000000A40000525341310004000001000100170D33754DB739E6298F70465182848A72C980F7D15D45E3EC91448AFC6088FCED3A880A7CAD8EEF053064F6932183A29A102D3A390E99ECDE03B4456AD5B0389CB3213160511EE2B5473F887294A7572F12A351A70D9DC7C155DFA3C9763986299AE555CFE166123FC2A904199D6A3B0C6AD3F519A849CF4397D91085B30EE6

The first step is to check how much data we have. That gives an idea of the size of the public modulus: although it is possible to compress an RSA public modulus $N$ to less bits than its bitlength $\lceil\log_2(N-1)\rceil$, this is uncommon; and most RSA public key formats are larger than the public modulus, and only much larger for digital certificates. Here, excluding the 0x prefix (meaning hexadecimal in many computer languages), the given is 276-character uppercase hex; that probably is hex, coding 138 bytes or 1104 bits, which suggests a 1024-bit RSA public key (the next lowest common size, and also one of the lowest common size).

Next is to confirm this; guess the endianness; and locate the public modulus $N$. The data coding $N$ typically is visually random-like (here, pointing towards the end of the data blob). As a quick test we can use that the low-order bit is set; and the hypothesized bitlength (if exact, which is typical) gives us another bit set. When we have an hypothesis on the location and coding of $N$, we can check it with an often-sufficiently-selective test: the public modulus is a composite with no factor quickly found. With a factoring program that finds factors less than $b$, odds that an incorrect odd guess pass this test are less than
$$\epsilon(b)=\prod_{p\text{ prime, }2<p<b}{p-1\over p}$$
That's residual odds below 5.1% to wrongly conclude that a guessed encoding is correct if we only check for at-most-32-bit factors, and perhaps less than a percent for the program I use, gmp-ecm (todo: justify); this is often good enough (especially if we have several examples).

Our data seems to use little-endian byte ordering, transformed to hex using big-endian ordering of the two characters of each hex byte. With that convention, the last 256 characters "170D3375..85B30EE6" would be a 1024-bit (128-byte) public modulus of 0xE60EB385..75330D17, which passes the above test. No other simple ordering that I checked does.

Immediately before that is "01000100", which by the same convention decodes to 0x00010001 and would be the common public exponent $e=65537=2^{(2^4)}+1=F_4$ (the fourth Fermat number).

Immediately before that is "00040000", which by the same convention decodes to 0x00000400, and that would be 1024, the conjectured bit length of the modulus (with $e$ always on 32 bits, as in early Windows CryptoAPI, explaining why there is no length for $e$).

The "52534131" immediately before matches "RSA1" in ASCII, and that could be a format indicator.

Searching for that string, it comes that Microsoft used that as a magic number for RSA keys, followed by bitlen and pubexp on 32-bit (strongly reinforcing the credibility of the above three educated guesses) in a RSAPUBKEY:

typedef struct _RSAPUBKEY {
  DWORD magic;
  DWORD bitlen;
  DWORD pubexp;
} RSAPUBKEY;

[contributed by CodesInChaos]: The first 8 bytes are a PUBLICKEYSTRUC:

typedef struct _PUBLICKEYSTRUC {
  BYTE   bType;    // 0x06 = PUBLICKEYBLOB -- The key is a public key.
  BYTE   bVersion; // 0x02
  WORD   reserved; // 0x0000
  ALG_ID aiKeyAlg; // 0x0000a400 = CALG_RSA_KEYX -- RSA public key exchange algorithm.
} BLOBHEADER, PUBLICKEYSTRUC;

[contributed by Maarten Bodewes]: The overall structure is a PUBLICKEYBLOB:

PUBLICKEYSTRUC  publickeystruc;
RSAPUBKEY       rsapubkey;
BYTE            modulus[rsapubkey.bitlen/8];

Note: The above formula for the size of the modulus field can only be valid if bitlen is a multiple of 8; and then it is prudent and customary to use only multiples of 64, or even 128 for good measure.


Can one generalize the Diffie-Hellman key exchange to three or more parties? Does anyone know how to do a Diffie-Hellman or ECDH key exchange with more than two parties?

I know how to do a key exchange between 2 parties, but I need to be able to have a key agreement between 3 or more parties.

The standard Diffie-Hellman key exchange algorithm (or family of algorithms) works in an cyclic group with generator $g$, and relies on

$$ {y_A}^{x_B} = (g^{x_A})^{x_B} = (g^{x_B})^{x_A} = {y_B}^{x_A}, $$

where $y_A$ and $y_B$ are publicly transmitted, while $x_A$ and $x_B$ remain private.

With three parties, we still have

$$((g^{x_A})^{x_B})^{x_C} = ((g^{x_A})^{x_C})^{x_B} = ((g^{x_B})^{x_A})^{x_C} = ((g^{x_B})^{x_C})^{x_A} = ((g^{x_C})^{x_B})^{x_A} = ((g^{x_C})^{x_A})^{x_B}. $$

As each party wants to let its own key private, each exponentiation needs to be done at different locations, which means some parties have to send their second-step results to the other parties.

One possible protocol could be the following:

A, B, C each generate their private keys $x_A$, $x_B$, $x_C$.
A, B, C each calculate $y_A = g^{x_A}$, $y_B = g^{x_B}$, $y_C = g^{x_C}$.
A sends $y_A$ to B, B sends $y_B$ to C, C sends $y_C$ to A.
A calculates $z_{CA} = {y_C}^{x_A}$, B calculates $z_{AB} = {y_A}^{x_B}$, C calculates $z_{BC} = {y_B}^{x_C}$.
A sends $z_{CA}$ to B, B sends $z_{AB}$ to C, C sends $z_{BC}$ to A.
A calculates $k_{BCA} = {z_{BC}}^{x_A}$, B calculates $k_{CAB} = {z_{CA}}^{x_B}$, C calculates $k_{ABC} = {z_{AB}}^{x_C}$.

The above equality means that the three parties now know a common secret $k_{ABC} = k_{CAB} = k_{BCA}$.

This obviously generalizes to more than three parties, but it needs one additional group exponentiation per participant more for each additional participant (i.e. in total $n^2$ exponentiations).

All of this works in all groups, so also in the elliptic curve groups (where this is usually written as point multiplication instead of exponentiation).

In practice it might be easier to exchange secret keys with some "hub" node, which then creates a common secret and sends it to each participant, like Dennis proposed in his answer.


Digital Certificates genereted from Hardware Security Module Software library without hardware based source of entropy will provide enough security to generate digital certificates. However Hardware security Modules provide hardware based source of entropy and apis to generate certificates along with other crypto operations. But buying HSM just for making certificates will be kind of spending much for just one feature. Is there any other way or device to make strong digital certificates?

HSMs are not purchased just for the feature of generating certs.

HSMs also store the certificates very securely. You cannot use the cert in the HSM unless you are authorised
HSMs also provide very secure management of the HSM itself - for e.g. you can create smart cards for 5 admins & say that atleast any 3 of the cards have to be used to administer the HSM
HSMs provide very high speeds for signing. If you are doing really huge amount signings per second, then this reduces the load on your software.
HSMs also provide high speeds for key generation. This may be important for temporal certificate generation - each certificate is used only for one signing.


In coin flipping protocols, why aborting is allowed, and why the non-aborting party flips a coin at the end? To convey how an adversary can bias the coin, most often a simple commitment-based two party coin-tossing protocol is given, as in [1]:

Alice sends Bob the commitment $c = commit(x)$
Bob sends Alice the bit $y$.
Alice sends Bob $decommit(x)$, Bob verifies Alice actually chose $x$.
Both compute result $r = x \oplus y$

It is said that Alice can place a bias of $1/4$ towards her choice after she receives Bob's bit $y$; if the result is what she wants, she plays along, if not, she aborts, forcing Bob to flip a coin on his own, which has $1/2$ chance of her choice coming up.

I understand the protocol and how a bias can be exerted. What eludes me is why such protocols are of interest:

Why is either party allowed to abort at will? The only point abortion makes sense is when Bob fails to verify, but they can abort whenever they want. If only such an abortion is allowed, the bias-by-abort scheme fails since Alice cannot abort upon seeing the result after the second step.
After Alice aborts, why does Bob flips a coin on his own? If the coin was flipped in case of a dispute, Bob can choose the way it suits him. If Bob could've just generated a random bit without having to prove anyone it is not biased, he would not have bothered with the protocol in the first place.

[1]: https://eprint.iacr.org/2012/643.pdf - Section 1, Example 1.1

1.
You usually allow parties to abort at will at any stage of the protocol since a malicious adversary can always do that in a real protocol execution, and therefore this is not something we can enforce.
A bit more formally, the best we can simulate (for a tutorial on simulation-based proofs see this) is an adversary that can abort, since that's unavoidable anyway.

2.
I didn't read the details of the paper but I assume that in the description, Bob still throws a coin if Alice aborts.
This is done precisely to break the bias imposed by Alice with the abort.
This works because Bob is honest (since Alice is malicious as she aborted) so the output, that is, the coin tossed by Bob, will have a uniform distribution.


Can RSA encryption produce collisions? In RSA, a message is encrypted by $m^e \pmod N$. $N$ is the modulus, $m$ is the message and $e$ is the public exponent. (I know that $m$ should not be greater than $N$.)

My question is, can $m^e$ be greater than $N$ (obviously, before taking the modulus)?

In that case is there a possibility like  $ m_1^e=m_2^e \pmod N$, i.e. can we get a collision?

Correction to Henricks answer: collisions are impossible (unless someone did something wrong).  That is, if:

$e$ is a proper RSA exponent (that is, relatively prime to $p-1$ and $q-1$, where $p$ and $q$ are the factors of $N$), and:
$m_1 \neq m_2 \mod N$ (that is, you're not trying to encrypt the same message twice),

Then we will always have $m_1^e \neq m_2^e \mod N$

This is rather implied by the fact that the RSA operation can be inverted using the decryption exponent; if two different messages collided, then that couldn't be inverted uniquely.


Shamir's ID based signatures I am currently implementing Shamir's ID based signature algorithm as proposed in Adi Shamir, Identity-Based Cryptosystems and Signature Schemes. Advances in Cryptology: Proceedings of CRYPTO 84, Lecture Notes in Computer Science, 7:47--53, 1984.

However I am stuck with generating the private key for a certain identity. The paper states that "the only difference between users is the value of i, and the secret key which corresponds to i is the unique number g such that

$g^e = i (\mod n)$.

This g can easily be computed by the key generation center, but if the RSA scheme is secure, no one else can extract e-th roots mod n." Where:

$g$ is the private key belonging to $i$.
$i$ is the ID for which the private key is to be generated.
$n$ is the product of two large primes $p, q$.
$e$ is a large prime which is relatively prime to $\phi(n)$

However, I am lacking the number theoretic background knowledge to derive the formula for the private key, given the knowledge of $p$, $q$, $\phi(n)$. I guess I have to apply Fermat's little theorem somehow. Please give me a hint for a solution.

PS: A question for the ID based crypto pros - do you recommend any more modern approaches? Shamir's paper the to be most suitable for my purpose and should be secure given a suitable bitlength is chosen.

Addendum: So concluding from DrLecter's answers, I have tried to map the needed functionality reusing as much as possible from an existing RSA implementation (RSA functionality denoted by *).

pk_i = (e, n) => public key of id i (i = m denotes master key)
sk_i = (d, n) => private key of id i (i = m denotes master key)
sig_mi = (s, t) => signature of message m signed by i
hash'(x) => hash function making full use of Z_n
hash''(x) => hash function with bitlength l such that 2^-l sufficiently small (e.g. SHA256)

Pseudocode:

//Generate private key sk_i for identity i
sk_i getPrivateKey(i, sk_m) {
    return sk_i(decrypt*(hash'(i), sk_m), sk_m.n) //hash' making use of full range of Z_n
}

//Receive public key pk_i for identity i
pk_i getPublicKey(i, pk_m) {
    return pk_i(hash'(i), pk_m.n) //hash' making use of full range of Z_n
}

//Sign a message with private key sk_i
sig_mi sign(message, sk_i) {
    r = rnd()
    t = r^e (mod sk_i.n)
    s = sk_i.d * r^hash''(t, message) (mod sk_i.n) //sk_i.d = g as generated by function getPublicKey
    return sig_mi(s,t)
}

//Verify a message with signature sig_mi
boolean verify(message, sig_mi, pk_m) {
    return (sig_mi.s^pk_m.e (mod n) == hash'(i)^pk_m.e * t^hash''(t, message) (mod n)) //hash'' with bitlength l such that 2^-l is sufficiently small (e.h. SHA256)
}

Compute $d$ such that $ed\equiv 1\bmod{\varphi(n)}$ using extended euclidean algorithm. Then compute $g = i^d\bmod{n}$.

This is basically RSA decryption.


TPM and Remote attestation I’m a little unclear on this subject:

  TPM chips to enable remote attestation. This mechanism works as follows. At boot time, the host computes a measurement list ML consisting of a sequence of hashes of the software involved in the boot sequence, namely the BIOS, the bootloader, and the software implementing the platform. The ML is securely stored inside the host’s TPM. To attest to the platform, a remote party challenges the platform running at the host with a nonce nU . The platform asks the local TPM to create a message containing both the ML and the nU , encrypted with the TPM’s private EK. The host sends the message back to the remote party who can decrypt it using the EK’s corresponding public key, thereby authenticating the host. By checking that the nonces match and the ML corresponds to a configuration it deems trusted, a remote party can reliably identify the platform on an untrusted host.

Lets say a TPM is in one of the nodes of a cluster (in the infrastrusture of cloud) . we know during boot time TPM startes performing integrity measurements :
basically two way of doing this;
1-SRTM (Static Root of Trust for Measurements) (bios-bootloader-kernel)
2-DRTM (Dynamic Root of Trust for Measurements).(running applications : thats something unclear to me too).

those measurements are finally extended to the TPM and saved in the PCRs.

A user is willing to verify the integrity of the cloud platform ,thus a trusted third party has to verify that for him.And finally attest him with a response of trusted/untrusted platform .Lets apply it on the 1st quote.

my questions:

Remote attestation is for authenification or validating the integrity?
Does the authenitification equals integrity of the platform?
The TTP requests measurement list are those measurements meant to be hash
values of SRTM and DRTM protocols?
How does the trusted third party verifies those measurements?

encrypted with the TPM’s private EK

There's something wrong with the document you're reading. Encrypting with a private key is nonsense. A private key can be used to decrypt or to sign. Here, “signed” is clearly meant instead of “encrypted”. That's a sign that the author of the document doesn't know what they're talking about. I strongly recommend reading more reliable material.

In addition, the EK isn't used to sign a platform attestation. That's an AIK. Using an EK to sign a platform attestation would be a privacy violation. The EK is used inside the TPM to decrypt data as part of the AIK enrollment protocol.

The part about hashes of software is correct. The main CPU and the TPM cooperate to calculate a hash of all the code that is executing on the main CPU. Upon request, the TPM can sign a message that says “the hash of the code that is executing on the main CPU is …”. This message is signed with an AIK, which is a key pair for which only the TPM has the private part. When a verifier wants to know the state of the platform, it sends a request to the TPM containing a nonce. The nonce is included in the signed reply.
$$
\mathsf{verifier} \rightarrow \mathsf{TPM}: \mathrm{nonce} \\
\mathsf{TPM} \rightarrow \mathsf{verifier}: \mathrm{hash}, [\mathrm{nonce}, \mathrm{hash}, \ldots]_{\mathrm{AIK}_{\mathrm{priv}}} \\
$$
The fact that the message has a correct signature guarantees that it was produced by the TPM at some point in the past. The fact that the correctly signed message includes the nonce guarantees that it was produced by the TPM at some point after the verifier generated the nonce: this prevents replay attacks.

A valid attestation authenticates the platform. In addition, it guarantees that the platform is in a certain state. This alone does not say anything about the integrity of the platform. In order to guarantee the integrity of the platform, the verifier must know what the correct value is for the hash of the platform state (or a set of correct values, if more than one value is possible).

This protocol does not require a trusted third party once the TPM has been provisioned with an AIK and the verifier has enrolled this AIK. However, in practice, an infrastructure will often separate the verifier from the relying party. The relying party is an entity that wants to communicate with the platform, and is only willing to do so if the platform is in a good state. However the relying party does not know what a good state is, so it relies on a trusted third party to perform the verification.


Why is Byte-at-a-time ECB decryption a vulnerability? I've been working on the Cryptopals Cryptography challenge problems, and I recently solved one where you recover a plaintext given a encryption oracle. The oracle produces a ciphertext in ECB mode AES.

You are given a base64 encoded piece of plaintext (encoded so that it isn't immediately human readable). The only thing you have control of is the plaintext you enter into the oracle. The key for AES is randomly generated each time, and you're not supposed to see it either.

More information on the problem here: Set 2, Challenge 12

What confuses me is that at the end of the problem a little box says

  This is the first challenge we've given you whose solution will break
  real crypto. Lots of people know that when you encrypt something in
  ECB mode, you can see penguins through it. Not so many of them can
  decrypt the contents of those ciphertexts, and now you can. If our
  experience is any guideline, this attack will get you code execution
  in security tests about once a year.

How can this vulnerability be used in real life? To crack the plaintext, you need access to it, as well as an encryption oracle (which contains the key). Is it ever possible to have this much control over a system? And if you did, why couldn't you just directly print out the plaintext or key?

The vulnerability happens when:

You send an INPUT to the server.
The server appends secret to INPUT -> INPUT||secret
The server encrypts it with a secret key -> encrypt(INPUT||secret, key)
The server returns, or you get access in some way to the resulting cipher.

Let's assume the block size is 8. Steps;

All you have to do to decrypt the first byte of "secret" is to send a block of 7 bytes (block size -1). Let's assume we send: AAAAAAA. We get a cipher back, this cipher is our "target".
Next we try AAAAAAA with every other possible bytes: AAAAAAAA, AAAAAAAB, AAAAAAAC, ... Let's assume the cipher returned at STEP1 is the same as when we send AAAAAAAw. That means we know for sure the first byte of the secret is w. We discovered the first byte, yay!
Send 6 bytes (block-size - 1 - known bytes) + w (the byte we discovered previously). Get cipher.
Brute force the last byte until you know the second bytes...  Repeat all steps until you discovered secret.

See? We never actually needed to know the key and yet we discovered secret.

A concrete scenario where this could happens:

Website creates a secret code for each user for the duration of their session, but wants to remain stateless so it saves the code in their cookie, encrypted. Except that the cookie also contains the username (which the user can control/modify). Now the encrypted cipher is username||secret_code. Given this scenario, a user can easily find out what his secret_code is.


XOR cipher Pseudo-random key strength When implementing a XOR cipher with a pseudo-random key equal in length to the plaintext, Is there a significant difference in potential key strength between keys drawn from a pool of either 1000 or 5000 possible characters? (that is, each character in the key may be any one of up to five thousand possible characters) Or is this not likely to be a deciding factor in overall security for a simple XOR?

Edit:
I apologize if my original phrasing was ambiguous. I have hopefully improved it a bit.
(Character pool = A group of distinct character from which the cipher key may be generated.)

There are a reasonable number of assumptions I'm going to have to make to try and answer this question. For perfect security, we require that the keystream is truely random, and never reused (OTP,shannon).

I've decided to add in a short answer here: STOP! There's absolutely no need to use a reduced character set thing anyway - you can just use your random number generator to generate a random byte and then treat your plaintext as a series of bytes rather than as characters.

Now, I take it you're intending to obey the no-reuse requirement, which leaves us with the question of what happens when my data isn't quite random enough?
Firstly, lets try and work out what a pool of 1000 characters would mean. To run an xor-cipher, we somehow translate the string of characters into a string of bits, using one of many character encodings. There are $2^8=256$ bits in a byte, so I deduce that by character you mean that each character is encoded into two-bytes (which is roughly how UTF-16 seems to work if you don't require very strange characters), meaning there are a total of $2^{16}=65536$ possible characters.

Now, how are you picking $1000$, or indeed $5000$ from them? If they're not randomly sampled from the total options, then you risk letting through some very significant information. For example, if your set is based around "common" characters then because of the way the character sets are constructed there are certain bits which are more likely to be set / not set in your collection of characters.

If you have managed to sample them totally randomly, then at the very least you're loosing out against a naive attack since there are only $1/5$ of the values to check.


MAC-then-encrypt in SIGMA protocol for authenticated key exchange The SIGMA protocol proposed in 2003 and used in TLS 1.3 and IKE stands for "SIGn-and-MAc" and can optionally protect identity using encryption.
The SIGMA-I variant illustrated below indicates that it uses a MAC-then-encrypt approach:

Here $\{\dots \}_{K} $ denotes encryption of the information between the brackets under a symmetric encryption function using key $K$.
Is there a particular reason to use MAC-then-encrypt rather than encrypt-then-MAC for key exchange protocols? I wasn't able to find a better answer than it seems arbitrary when looking at a comparison between MAC-then-encrypt and encrypt-then-MAC.
Edit: RFC 7366 linked in this related answer gives some hints that encrypt-then-MAC should be preferred (D)TLS communication (none is said about handshaking). In particular, it  states:

TLS and DTLS use a MAC-then-encrypt construction that was regarded as secure at the time the original Secure Socket Layer (SSL) protocol was specified in the mid-1990s, but that is no longer regarded as secure.

Interestingly, H Krawczyk (the author of SIGMA) wrote in 2001 The Order of Encryption and Authentication for Protecting Communications (or: How Secure Is SSL?)—before SIGMA.

Arnaud asked me to clarify this issue.
It is true that one should use an authenticated encryption mode or encrypt-then-MAC, and the paper says that explicitly. Indeed, the explanatory text in the paper following the figure shown above (Section 5.2 of https://webee.technion.ac.il/~hugo/sigma-pdf.pdf) addresses this issue.
It says:

We stress that the encryption function (as applied in the third message) must be resistant to active attacks and therefore must combine some form of integrity protection. Combined secrecy-integrity transforms such as those from [16] can be used, or a conventional mode of encryption (e.g. CBC) can be used with a MAC function computed on top of the ciphertext [3, 26].

Namely, the encryption denoted  $\{...\}_{K_e}$ needs to use an authenticated encryption scheme. (The need for authenticated encryption is also repeated in Appendix B that shows a more complete protocol in the form of SIGMA-R).
The fact that there is a MAC (on the identity) under the encryption is just because the MAC is (an essential) part of the SIGMA protocol and is completely unrelated to encryption (in particular, needed even if you do not care about protecting identities). So while it looks like "MAC-then encrypt" it has no relation to this mode of encryption.
Note: The reason the text says that authenticated encryption is only needed for the third message is that, as said at the beginning of that same paragraph,  SIGMA-I protects the identity of the initiator from active attackers and the identity of the responder from passive attackers.   So encrypting the identity of the responder only needs security against passive attacks for which UNauthenticated encryption suffices. This is really an academic remark since in practice one would use the same encryption scheme for both flows, namely, authenticated encryption for both.


Decrypt AES-encrypted data with another key Here is a plain question, all filled with pseudo-real data :)

We have a string: "hello" and two keys for AES: GoodKey and BadKey.
We encrypt our string with GoodKey, and receive something like "lehho".
What will happen if we try to decrypt "lehho" with BadKey? Will decryption algorithm make no sense at some point (like 1/0 makes no sense) OR will it give us some other result, like "goodbye" (which is not original "hello" because of the wrong key)???

Usually you require a mode of operation for a block cipher such as CBC or CTR to encrypt data. CBC or CTR is then configured with the given block cipher & key. The mode takes an IV or nonce as additional parameter, but I'll leave the IV out of my answer as the IV value is inconsequential if the wrong key is used.

A block cipher such as AES will simply encrypt or decrypt a full block of bytes. For each possible plaintext block there will be precisely one ciphertext block, given a specific key. The result of a bad key will have the same size, but it will be indistinguishable from random otherwise.

A block cipher itself however is not secure and can only encrypt precisely one block - you need the mode of operation too. In that case it depends on the mode. If the mode does not apply padding - e.g. CTR - then the result will be indistinguishable from random, and you won't get an error. If you use CBC (and a padding algorithm instead of ciphertext stealing) then you will probably get a padding error (about 255 in 256 times).

If you always want to receive an error instead of garbled ciphertext or a padding error you need to integrity protect your ciphertext. You can do this by using an authenticated mode of operation such a GCM or by applying a (H)MAC over the ciphertext.


DH Key Exchange Protocol Since I am not able to comment under the topic, I would like to ask here why in question 2 old post, we cannot distinguish the two distributions, even with unlimited computational power? Also, what can be said about the distribution of exponents a+b modp when b is taken at random from Zp, but a is fixed?

Any help would be appreciated a lot.

It's easier to take the questions out of order.

  what can be said about the distribution of exponents a+b mod p when b is taken at random from Zp, but a is fixed?

If $b$ is a uniform independent random value from the range $[0, p-1]$, that is, the probability of each possible value is $1/p$, and $b$ is distributed independently from $a$, then $a+b \bmod p$ is a uniform independent (of $a$) random value from the range $[0, p-1]$; that is, the probability of $a+b \bmod p$ being any possible value from the range is also $1/p$, and information about the distribution of $a$ (such as having it be a fixed value) does not change this.

The easiest way to see this (for a fixed $a$) is to note that, for any target value $c = a+b \bmod p$, there is a unique value of $b = c-a \bmod p$ that must be selected for the value $a+b \bmod p$ to be that value.  The probability of $b = c-a \bmod p$ occurring is $1/p$ (because that value is in the range, and we assumed the probability of all values in that range be $1/p$), hence the probability that $c = a+b \bmod p$ is also $1/p$.

With this, your first question is easy:

  I would like to ask here why in question 2 old post, we cannot distinguish the two distributions, even with unlimited computational power?

Alice sees either $g^b$ or $g^{a+b}$; an adversary with unlimited computational power can solve the discrete log, however that gives him either $b$ or $a+b$ (for random $b$); both probability distributations are identical, and so he cannot distinguish them.


Meaning of difference Δ delta I tried to understand some crypto text but I am new to this.

Does this:

  Let $X,X'$ be $\ell$-bit values, and $\Delta X=X\oplus X'$

means that $X$ and $X'$ have $\ell$ bits and $\Delta X=X-X'$ or something else

means that $X$ and $X'$ have $\ell$ bits[...]?

Yes.

  means that [...] $\Delta X=X-X'$[...]?

Yes and no. Fundamentally what $x-y$ means is $x+(-y)$, but for bit-strings over $\mathbb F_2$ this becomes $x+(-y)\bmod 2$ for each bit, and $-y\equiv y\pmod 2$, i.e. $y$ and $-y$ behave the same. As this means that addition is just XOR, we write $x\oplus y$ to indicate this.

Also note that $\Delta X=X\oplus X'$ is the bitstring that has a bit set iff $X$ and $X'$ differ in that bit position and so it's the "difference" ($\Delta$) between the strings.


ECDH - when are the domain parameters shared and how? I'm trying to understand Diffie–Hellman based on Elliptic-curves.
Can one explain at which point of time the domain parameters are shared? Are they shared trough a public channel and can they be always the same? Are they shared at a specific different point of time?
Literature doesn't clearly answer my question...
I'd like to create a concept to establish a secure communication channel between two devices that "don't know each other but want to establish a secure channel"

How the parameter set to use is established depends on the (application) protocol entirely. They need to be established before the key agreement operation takes place, but there aren't really any other requirements. Usually they are shared by name or OID (short for Object Identifier usually encoded using Abstract Syntax Notation One or ASN.1) in the protocol, but it is also possible to just allow a single curve for a specific (version of) a protocol. Quite often the domain parameters are simply listed and given an index number in a protocol as well, if just to save space.
Sometimes the entire set of parameter values are simply send over (which is what I would call "sharing"). This is for instance the case for some smart card based protocols as it is a bit unwieldy to store all the curves in the limited storage available. In general you want to trust the party that sends over the parameters though. If some curves or sizes are optional then you may need to come to some kind of agreement between the parties about which curve to use, although I haven't seen many flexible protocols like that. Sharing parameters isn't all that common, usually well known curves are used so there is no need to share the parameter sets.
When it comes to card verifiable certificates in ePassports, the root certificate defines which domain parameters are to be used. The underlying keys (it contains 3 levels) will always use the same curve as the root. And staying with ePassports, there is also a scheme called PACE where the new domain parameters are calculated from a previous set (the sets only differ w.r.t. base point G of course, not the entire set).


How to convert projective to jacobian co-ordinate in ECC? I am doing a small project using elliptic curve in cryptography. My doubt is, can I directly convert a projective to a Jacobian coordinate system without using the affine conversion in elliptic curve cryptography? Actually, I am stuck at this point…

If the question is how to take a point in projective coordinates (a triplet $(A,B,C)$, where the corresponding affine coordinate is $(AC^{-1}, BC^{-1})$), and you want to convert it into the same point in Jacobian coordinates $(D, E, F)$ (where the affine coordinate is $(DF^{-2}, EF^{-3})$), I believe this works:

$$D = AC$$

$$E = BC^2$$

$$F = C$$

We can easily see that $DF^{-2} = AC^{-1}$ and $EF^{-3} = BC^{-1}$, hence $(D,E,F)$ refers to the same point as the original, and this conversion takes only three multiplies.


Which ciphers produce random ciphertext? I already know AES produces a "random" output.
5e4e6440826d6afc4535fbf078455f791159701a9df624ddd4e4dda84523b6a7
Its ciphertext doesn't follow a pattern and is indistinguishable from noise.

Is this common for most ciphers?

Strictly speaking, we can't know for sure that the output of AES is indistinguishable from random noise. It's conjectured to be true but no "proof" of that fact exists.

For most commonly-used ciphers, it is conjectured that their output is indistinguishable from random. Specifically, modern ciphers are conjectured to be "strong pseudorandom permutations", which means that an adversary given encryption and decryption oracles for the cipher can't distinguish it from a random permutation.


Can or can not D-Wave's quantum computers use Shor's and Grover's Algorithm to find encryption keys? Why? I read that a company called D-Wave Systems has and is manufacturing quantum computers of 128 qubits.

Can they or can they not use Shor's and Grover's algorithms for finding RSA-keys? If they can't then why not?

And how come it was so hard for the team at MIT to create and maintain a stable 5-qubit quantum computer ion trap if D-Wave has already succeeded in creating Q-computers with more qubits?

It feels like something with this D-Wave computer is off..? Would be extremly grateful if anyone could enlighten me.

D-Wave's "Quantum computers" are NOT general purpose quantum computers. They can only do quantum annealing, which allows a small subset of problems to be solved. They can't run Shor's or Grover's algorithms, as these aren't quantum annealing problems. It's also still an open question whether D-Wave's machines even provide any speedup over classical simulated annealing systems.


Why is it difficult to encrypt large amounts of information using quantum key distribution? An article last month claimed that Toshiba Corp. and Tohoku University recently broke the record for the amount of data encrypted using quantum key distribution by transmitting "a few hundred gigabytes".

But QKD is merely a protocol for transmitting symmetric keys - the actual encrypted data is later sent over an insecure channel where presumably bandwidth is not a limitation (or at least any limitations are completely separate from the encryption protocol). Moreover, my understanding is that once you've transmitted a single symmetric key, the amount of data that you can encrypt with it is effectively unlimited:

The answer at https://crypto.stackexchange.com/a/2473/76433 claims that for AES-128 the risk of compromise is "very likely" after $2^{64}$ blocks of encrypted data are transmitted, but the answer at https://crypto.stackexchange.com/a/5101/76433 says that for AES-256, after $2^{50}$ blocks of data transmission the probability of data leakage is still only $2^{-29}$. The answer at https://crypto.stackexchange.com/a/66261/76433 is more conservative and recommends only encrypting 64 GiB of data per symmetric key in order to keep the collision risk down to $2^{-64}$.

So it seems that after you've transmitted a mere 256 bits of symmetric key data via QKD, the amount of data you can encrypt is effectively unlimited. (If you want to be extremely conservative and you want the risk all the way down to $2^{-64}$, then maybe you'd need to transmit a few keys in order to transmit "a few hundred gigabytes" of data.) And modern QKD technology can easily transmit millions of bits per second (although whether or not they are actually secure is a separate question). So why is it impressive that large amounts of data were transmitted?

More broadly, is there any real advantage to having a QKD system that can transmit more than ~256 bits? (Again, I'm putting aside any practical security risks of QKD and assuming for the sake of argument that it is indeed secure.)

I believe the end goal is to use the QKD data as a one-time pad, so the QKD rate would need to be the same as the plaintext data rate.  That is the only guaranteed-secure method.  (Although I think QKD might be a bit of a scam.)

Also, you can't use a key forever.  I recently made a 400Gbps AES-GCM encryptor.  You're not supposed to send more than 2^32 blocks with the same key, because it starts to get easy to forge tags after that.  This corresponds to ~8 hours' worth of data.


What is the difficulty of DLP in GF(P^Q) with a subgroup with a prime order of L Given a finite field GF(P^Q), having a subgroup with a prime order of L (P,Q,L are all primes), how difficult is it to find the discrete log, is it related to P and Q or is it related to L, or to both. What is the time required? O(sqrt(L)) ?

Does index calculus apply to Galois fields?

First there are the "generic" discrete logarithm algorithms like Shanks's "baby step, giant step" and Pollard's $\rho$, which run in $O(\sqrt{L})$ and are thus of exponential complexity (in the size of $L$). Those algorithms work in virtually any group.

In the special case of the multiplicative groups of finite fields, we have subexponential algorithms (i.e, algorithms which are "in between" polynomial and exponential). The index calculus algorithm has many variants whose complexity varies slightly depending on the relative sizes of $p$ and $q$ (see the Wikipedia page and its references), but the details are not very important unless you want to specialise in discrete log algorithms (in which case, read the references mentioned above). What's important for cryptography is that due to such algorithms, cryptosystems based on the discrete log in finite fields must use larger keys than those based on the discrete log in elliptic curves for the same level of security.

Also, the "quasi-polynomial" algorithm of Gaudry et al. works for small $p$ (basically, when $p \le q$), and such cases should therefore be avoided, but they were rarely used in the first place anyway.


Does AES encrypting /dev/zero and feeding output to AES again increase entropy of the ciphertext? I just thought about what would change if would pipe the output of

openssl enc -aes-256-ctr -pass pass:"$(dd if=/dev/urandom bs=128 count=1 2>/dev/null | base64)" -nosalt < /dev/zero | pv -pterb  > file

to AES again. What this does is take a passphrase out of urandom and encrypt the output of /dev/zero - so taking 1 passphrase and an endless number of zeros, which outputs random numbers. this way AES is used as a random number generator. This line can be used to fill up a file on a disk with random numbers. It's way faster than dd'ing /dev/urandom to a file. One can also substitute "file" with /dev/null, just to see how fast the system is encrypting and writing to null.

So I wonder what happens if I would feed the output of that line to AES again. **Would the output change in a way?

As I think it should not change anything — the randomness of the output should be exactly the same, shouldn't it? Is there a practical way to measure the entropy of the output?** I think no, as it should be good enough to not have any statistical anomalies, so there's no way of measuring an increased/decreased entropy - or am I missing/confusing something?

First lets quickly analyze your commands:

$(dd if=/dev/urandom bs=128 count=1 2>/dev/null | base64) : take a block of 128 pseudo-random bytes and put it into a single line encoded as base 64, throwing away anything printed to standard error
openssl enc -aes-256-ctr -pass pass:(1) -nosalt < /dev/zero :

perform OpenSSL key derivation on the base 64 string from step (1) without a salt: basically two subsequent runs of HMAC-MD5 to create 256 bits of output;
use the resulting key to perform AES-256 CTR encryption on an endless stream of zeros to get to the counter mode key stream;

pv -pterb > file : perform some metrics before dumping the key stream to file.

Now your question is if you would replace the /dev/null with the input file, using a new block of 128 bytes taken from /dev/urandom as password. Well, the good news is that it will add another amount of randomness to the original stream. How much entropy that entails depends on the internal characteristics of the used /dev/urandom implementation. Of course, if you would use the original password then you would cancel out the operation and produce a file with all zeros.

Using CTR to create a fast PRNG is a good idea that is used quite a lot. But remember that although it is very fast, it doesn't reseed. Using /dev/urandom is a bad idea if you want to have as much entropy as possible though. For this kind of use /dev/random is a better choice.

Using a bad password generation mechanism such as the default OpenSSL one will however bring back the maximum amount of entropy to 128 bit max due to MD5 being used to derive the key. If you consider that you could have up to 128 bytes of entropy, that's quite a shame. You would be better off using the -K option which allows for hexadecimal encoded keys instead. In that case you retrieve 32 bytes of randomness and use the full 256 bits of that directly for AES-CTR.

So if you want to increase the possible entropy, try and use this:

openssl enc -aes-256-ctr -K "$(dd if=/dev/random bs=32 count=1 2>/dev/null | od  -v -An -tx1 | tr -d ' \n')" -iv 00000000000000000000000000000000

and use it on any number of zeros. Note that on some systems this may deplete the entropy pool if you perform a lot of these commands.

Here -K is used to replace the password with a 256 bit key, which is supplied in hexadecimals using the dd if=/dev/random bs=32 count=1 2>/dev/null | od  -v -An -tx1 | tr -d ' \n') command, where od creates hexadecimals including spaces and newlines, which are removed using the tr command. The IV can be kept to all zero as the key will differ for each command anyway.

Final note: writing random data to an intermediate file is usually not a good idea. You are much better off programming this. In case you require OpenSSL then you could use C or any wrapper library for your choice of language that gives you enough functionality.


Why does key generation take an input $1^k$, and how do I represent it in practice? In my lecture, the lecturer said:

  Let $K$ be the key generation algorithm. Given a security parameter represented in unary, $1^k$, $K(1^k)$ will output a keypair $(pk; sk)$, known as the public key and the private (or secret) key, respectively.

My question is: When I want to implement the cryptosystem, how should I represent this $1^k$?  When I implement the key generation procedure, do I literally require callers to pass me a string of $k$ one-bits that the procedure will never use?  And, if so, why is it there in the first place?

The $1^k$ is a formalism that's only there to make the theoreticians happy.  You can safely ignore it.  When you actually implement the cryptosystem, you don't try to pass the string $1^k$; instead, you pass $k$, the security parameter (a representation of how much cryptographic strength is desired from the key generation algorithm).

I wish I could leave it at that, because this is nothing deep: it's just something stupid and not important in any fundamental, conceptual sense.  However at this point you're probably going to be saying "huh?", so I suppose I have to explain.

Why is it there?  For totally stupid reasons.  Its only purpose is to help remind theoreticians that key generation should be efficient: its running time should be polynomial in the security parameter.

In more detail, we want the security of our cryptosystems to be parametrizable (totally reasonable so far): for instance, if you want 80-bit security, you should be able to pick the parameter $k=80$ and get corresponding security.  Theoreticians also want to impose the requirement that all of the cryptographic operations are pretty efficient (still pretty reasonable): increasing the security parameter doesn't slow down the crypto too much.  Some theoreticians work in the context where performance is measured in asymptotic complexity (somewhat unreasonable in practice, but we can let that one go as it is still useful and understandable).  So, they formalize the requirement that crypto operations be efficient by requiring that the asymptotic running time of all crypto operations (key generation, encryption, decryption) be polynomial in the the security parameter.

Are you following so far?  So far, nothing is totally unreasonable -- but get ready, here comes the silly part.  Our standard notion in complexity theory of what it means for an algorithm to be efficient is that the algorithm's running time is a polynomial in the length of the input to the algorithm.  The theoreticians want their formalization to fit within this standard complexity-theoretic framework.  Therefore, they formalize the requirement that crypto operations run in polynomial time by passing a special dummy padding string as input to the operations whose length is given by the security parameter.  Why pass the dummy string?  Well, those operations are going to completely ignore the dummy string, so passing this extra useless string seems completely pointless.  It is pointless from a practical perspective, but from a theoretician's perspective, it lets them require that the cryptographic operations have a running time that is asymptotically polynomial in the length of their inputs -- and it will follow automatically that their running time is asymptotically polynomial in the security parameter (because they artificially ensured that the length of the inputs is the same as the security parameter).  This makes the theoreticians happy.

Like I said, it's stupid and pointless and exists only to make the theoreticians happy.  When it comes time to implement the cryptosystem, ignore it.

P.S. Perhaps I should reveal at this point that I have a bit of a theoretician in me, and sometimes it makes me happy too -- but I still realize how silly it will look to someone who cares more about using crypto than about proving theorems in complexity theory.


Schnorr Identification Scheme under active adversary According to the paper “GQ and Schnorr Identification Schemes: Proofs of Security against Impersonation under Active and Concurrent Attacks” by Mihir Bellare and Adriana Palacio, the Schnorr identification scheme is secure under an active adversary who changes messages. I have been told that Schnorr is actually not secure against such an adversary but I am not able to find any new literature on it. Any ideas?

It is important to consider the model in which security is proved. In this case, the attack proceeds in two phases: first a phase where the adversary as a verifier interacts with the honest prover, then a phase where the adversary as a prover interacts with an honest verifier. The adversary wins if the honest prover accepts. The paper proves, under reasonable assumptions, that the adversary cannot win in this model.

However (see the comment at the end of Section 2), this model is very restricted and not so useful. In more useful models where the adversary interacts with the honest prover and the honest verifier at the same time, the Schnorr identification protocol is absolutely hopeless, which isn't surprising since it wasn't designed with those models in mind.


Attack vector difference when not allowing repetitions in BIP-39 We are using a 12-word scheme BIP-39 mnenemonic key generating scheme that creates an entropy of 128-bit that is then used to generate a seed that in turn derives a private key for the user. It chooses randomly 12 words out of 2048.

There are $2048^{12} = 5.444518 \cdot 10^{39}$ combinations that form the entropy for the seed.

This scheme allows duplicate words. Some users are irritated by that and write emails to support and I wonder how much entropy would get lost by only allowing unique words.

That would be $\frac{2048!}{(2048-12)!} = 5.271538 \cdot 10^{39}$ variations.

In conclusion the latter solution has only $\frac{5.271538 \cdot 10^{39}}{5.444518 \cdot 10^{39}} \approx 96.8\% $ the number of possible seeds than the non-unique one.

Is that mathematicallly correct and is that a neglectible hit on security given the increase in user friendliness?

There is no impact on security.

The seed combinations can have more entropy than the 128-bit key you feed into it. Assuming the function you use to convert the 128-bit key into the 12-word seed is injective, then you won't even be able to reach all possible seeds with the keyspace you have, since $2048^{12} \gg 2^{128}$.

The entropy in 12 random words picked from a set of 2048 is $\log_2(2048^{12}) = 132$ bits. If you only allow unique words, it is $\log_2(\frac{2048!}{(2048-12)!}) \approx 131.95$ bits. These are greater than 128.


On getting beyond LSB in discrete log In discrete log we employ sophie germain primes $p=2q+1$ where $q$ is a prime.

Then we know least significant bit $x_0$ in $$g^{2x+x_0}=h\bmod p$$ where $2x+x_0$ is discrete logarithm of known $h\bmod p$ with respect to known generator $g$.

Suppose $g^2=r\bmod p$ then why cannot I reduce the problem to $$r^{x}=hg^{-x_0}\bmod p$$ and let $x=2x'+x'_{0}$ where $x'_0$ is lsb of $x$ and recursive solve the problem of finding $2x+x_0$ which is discrete log of $h\bmod p$ with respect to generator $g$?
Suppose I know $x_0$ in $g^{3x+x_0}=h\bmod p$ where $x_0\in\{0,1,2\}$ holds (that is if it were easy to solve for the last ternary digit of discrete logarithm when $p=2q+1$ would the problem be any easier?

If $p = 2q+1$ where $q$ is prime, and then we can efficiently solve for $x_0 \in \{0, 1\}$ for $g^{2x+x_0} = h \pmod p$, if $g$ is a generator.

This is true; this is a special case of the observation "if $g$ has order $a \times b$ with $b$ small, then if $g^y = h$, then we can find $y \bmod b$ quickly (specifically, in $O(\sqrt{b})$ time).

As $g$ is a generator for the entire group, it has order $2q$, and so we can find $y \bmod 2$ quickly (or, as you put it, find $x_0$ where $y = 2x + x_0$)

  Suppose $g^2 = r$, then why cannot I reduce the problem to $r^x = hg^{-x_0} \pmod p$

Well, I suppose you could, but solving that would be as difficult as the DLog problem (actually, that's provable; given an Oracle to do that, you can solve the entire DLog problem).  The previous observation doesn't help you solve this problem; $r$ has order $q$, which is a prime; it doesn't provide any magic ways to compute $x \bmod 2$; the best it can do is find $x \bmod q$ in $O(\sqrt{q})$ time, and we have more efficient ways than that.

  Suppose I know $x_0$ in $g^{3x+x_0} = h \pmod p$, which $x \in \{ 0, 1, 2 \}$, would that help.

Yes, if you had an Oracle that could find $y \bmod 3$, then you could efficiently solve the DLog problem.  That said, we don't know any way to do that efficiently (assuming that the order of the group wasn't a multiple of 3).


Do any Identity-based Encryption Systems support messaging between domains? Identity Based Encryption is covered under RFC 5091 (specifying the algorithm), 5408 (specifying data structures), and 5409 (using IBE with Cryptographic Message Syntax). However, every IBE implementation that I've seen and used are nothing more than glorified web-mail systems.

Do any existing IBE systems allow secure messages to be sent from one domain/realm to another? Is there any compatibility between vendors?

I've now spoken with representatives from two IBE vendors. The Voltage system allows "federation" by which one Voltage appliance can exchange system parameters with another Voltage appliance. It's not clear if this is done using RFC 5091, RFC 5408 and RFC 5409. The other vendor does not support such a mode of operation.


Fastest random number generator I just read High performance physical random number generator by K.H. Tsoi, K.H. Leung and P.H.W. Leong. It proposes a physical RNG of speed 400 Mbps. Is this the fastest random number generator at this moment?

The problem with questions that ask for “the fastest” is, that such questions always raise the counter-question: compared to what exactly? Also, your question doesn’t specify if you mean cryptographically secure physical random number generators, or any physical random number generator.

Anyway… 400 Mbps doesn’t really come anywhere near the word “fastest”.

If you take a look at “An optical ultrafast random bit generator”, which was published in Nature Photonics (Volume 4, Issue 1, pp. 58–61) by Kanter et al in 2010, you’ll see that their physical random bit generator operated at a rate of 300 gigabits per second. I’ld say that somewhat fits the word “faster”.

Besides that, you’ll most certainly also will want to check out “Real time demonstration of high bitrate quantum random number generation with coherent laser light”, published by Symul at al (ANU, Appl. Phys,. Lett. 98, 231103) in 2011.
In short: researchers at the Australian National University are generating true random numbers from a physical quantum source.

Currently (meaning: at the time of writing this answer), their Quantum Random Number Generator seems to be the best fit for the word “fastest”.

To learn more about the QRNG, you could either start by reading this ScienceDaily article,  or you can skip that and directly visit the “ANU Quantum Optics – Quantum Random Number Generator” webpage.

An aside: as others already hinted  at in their comments ⁽¹⁾ ⁽²⁾, even simpler RNGs already tend to break the 400 Mbps mark.


Proving a Hash in Another Hash I'm new to cryptography in general, and have this basic question.

Provided  H(x) means a hash of x
and z = H(H(x) + H(y))

given y or H(y), how do we prove that y or H(y) is a part of z? How do we "split" z into H(x) and H(y) so that we can compare H(y) to our y?

Help is greatly appreciated.

I assume you mean H to be a one-way function. The way you 'prove' that you know half of the input of a one-way function (i.e. y or H(y) for the outer H()) will be to produce the other half of the input (i.e. x or H(x)) and show that H() of the two parts together gives you z.

In general, if your H is a Pseudo-random-function (which any good crypto-hash function is), then ANY possible combination of y and z has an infinite number of xs that will combine in the way you ask.


RSA finding the inverse of the public exponent I have a very basic doubt in RSA key generation and its usage.

In RSA key generation you choose two large prime numbers of a very large order. Then you multiply them.(eq $p \cdot q = N$) Now, $\phi(N)=(p-1)(q-1)$. Now you find a number $0 < e < \phi(N)$ such that $e$ and $\phi(N)$ are coprime. {$e,N$} becomes your public key. Now you compute $d$(private key) such that $ed \equiv 1 \bmod{\phi(N)}$.

Now suppose you encrypt something (say $m$) with your the public key: $c=m^e\bmod{N}$. To decrypt with the private key, you do $c^d\bmod{N}$.

Now my doubt is that you found out the inverse of $e$ modulo $\phi(N)$, but when you are decrypting you are doing it in modulo $N$. How is this possible?

The answer comes from Euler's Theorem. Note: math below is done modulo $N$ unless otherwise specified and draws heavily from group theory.

That theorem says that any element of a group (say $m$) raised to the order of the group, in this case $\phi(N)$ is congruent to $1$ (i.e.,  $m^{\phi(N)}\equiv 1\bmod{N}$). Furthermore, this holds for multiples of $\phi(N)$ (i.e., $c\cdot\phi(N)$ where c is an integer).

In the case of RSA, you find $e,d$ such that $ed\equiv 1\bmod{\phi(N)}$. Note then that $ed=c\cdot\phi(N)+1$, where $c$ is some integer.

Thus $c^{d}=m^{ed}=m^{c\cdot\phi(N) + 1}=m^{c\cdot\phi(N)}\cdot m^1$. From the Euler's Theorem, $m^{c\cdot\phi(N)}=1$, so that term goes away and you are left with the original message.


Logical OR operation in a homomorphic additive cryptosystem Suppose we have a cryptosystem homomorphic for addition (say Paillier's). Is there a way to perform a logical OR operation between two binary values (with a binary result).

We can, of course, obtain the encoded result of addition between two values (by multiplying the encoded values):

$Enc(x + y) = Enc(x) \cdot Enc(y)$

and that gives us something close to a logical OR, except if both $x$ and $y$ have value $1$, in which case the result will be $2$, when it should be $1$.

Therefore another way to solve the problem might be to figure a homomorphic function: $F: \{1, 2\} \rightarrow 1; 0 \rightarrow 0$.

Does such a function exist?

Conversely, is there any way to prove that a true logical OR operation would break some fundamental properties/limitations of (non-full) homomorphic cryptosystems (and that I am wasting my time looking for one)?

Well, the problem is with logical OR and subtraction (which Pallier can also do), you've got FHE; that is, you can compute any combinatorial function of encrypted (binary) inputs.

Here's how it works, you can construct the NAND function:

$NAND(x, y) = (Enc(1) - x)\  OR\  (Enc(1) - y)$

If we limit $x$ and $y$ to being either encrypted 0, or encrypted 1, then the result of this is an encrypted 1 unless $x$ and $y$ are both an encrypted 1; in that case, the result will be an encrypted 0.

The $NAND$ function is complete; that is, we can create any combinatorial circuit using enough of them.