Familiar key signing over video call Say that a friend of mine and I have both generated new PGP keys, and we want to use a video call to verify each other's new keys because we live on opposite sides of the planet. While we could both somehow share our public key and then read back the fingerprint, reading a fingerprint is a bit cumbersome, especially given that we both have to do it.

After I came across this "problem", a potential solution dawned on me, but I wanted to check here whether it will actually securely verify the new keys.

I download what purports to be my friend's new key from somewhere.
I encrypt and sign a message containing two random English words using my friend's alleged new key.
We start the video call, and I tell my friend the first word in the email.
My friend decrypts the message and checks that the word was indeed the first word.
My friend then tells me the second word in the email (which I can verify since I sent the email).

I believe that if we both get our words "right" according to what was in my original mail, I can now trust that the key I have is my friend's new key. Furthermore, my friend can now trust that the key that signed that email is my new key.

While this may seem like a very roundabout way of achieving this, it is actually very simple to do if you're on a UNIX box:

shuf -n2 /usr/share/dict/words | tee /dev/stderr | gpg -sear <friends-key> | mail -s "Key verification keywords" <friends-email>

My question (finally) is now whether this scheme truly does verify our new keys, or whether there is some gaping hole I've missed?

Update 1: Come to think of it, the signature here can easily be forged as an attacker can just re-sign the encrypted blob with their own key. However, if the fingerprint is also included inside the encrypted part of the message, I believe it would still be secure.. The new command would be:

(shuf -n2 /usr/share/dict/words; gpg --fingerprint <my-key>) | tee /dev/stderr | gpg -sear <friends-key> | mail -s "Key verification keywords" <friends-email>

The friend would then check that the signing key has the same fingerprint as the one contained in the message before trusting it.

EDIT: I only say video call because it would be easier for someone to pretend they're my friend if all I had to go on was the voice.

So your protocol goes like this:

Alice generates a key pair $(a_{priv}, a_{pub})$ and sends $a_{pub}$ to Bob.
Bob generates a key pair $(b_{priv}, b_{pub})$ and sends $b_{pub}$ to Alice.
Alice generates a message $m$ and sends $Enc(Sign(m, a_{priv}), b_{pub})$ (or $Sign(Enc(m, b_{pub}), a_{priv})$, I'm not sure which of both is usually used by PGP) to Bob.
Bob decrypts and checks the signature to get a message $m'$.
By a video call both verify that $m' = m$.

Your key verification scheme is based on two ideas:

If Bob did succeed to decrypt some message encrypted by Alice using $b_{pub}$, then Bob must be in possession of the corresponding private key $b_{priv}$.
If Alice knows the content of a signed message which could be verified using $a_{pub}$, then Alice must have been the signer and be in possession of $a_{priv}$.

But this doesn't work in presence of a man-in-the-middle attack for the previous key exchange and the exchanged message.

Assume Eve is able to intercept all messages between Alice and Bob.

Then the attack goes this:

A → E: $a_{pub}$
Eve generates a new key pair $(a'_{priv}, a'_{pub})$.
E → B: $a'_{pub}$
B → E: $b_{pub}$
Eve generates a new key pair $(b'_{priv}, b'_{pub})$.
E → A: $b'_{pub}$
A → E: $Enc(Sign(m, a_{priv}), b'_{pub})$
Eve decrypts the message, strips the signature and re-signs and re-encrypts.
E → B: $Enc(Sign(m, a'_{priv}), b_{pub})$
Bob checks signature and decrypts, and gets the same $m$ as sent by Alice.
Video call verification shows that "everything is okay".

If the message also contains parts of the key to be used, that would have to be changed by Eve as well, of course.

So no, you can't get around checking the actual finger print of the keys (or something derived from it).


how to compute the correlation between two binary vectors? We find different equations to compute the correlation or correlation coefficient:

$\begin{align*}
corr &= \frac{a+d}{a+b+c+d}\\
     &= \frac{(a+d) - (b+d)}{a+b+c+d}\\
     &= \frac{(a+d) - (b+d)}{\sqrt{(a+b)*(c+d)*(a+c)*(b+d)}}
\end{align*}$

where a(0,0), b(1,0), c(0,1), d(1,1), which formula give the correct result?

The math

The correlation coefficient between an array of boolean vectors is a value between 0 and 1 defined by the following equations, covariance and standard deviation:

$\operatorname{cov} (X,Y)=\frac{1}{n}\sum_{i=1}^n (x_i-\overline{X})(y_i-\overline{Y})$

$\sigma_X=\sqrt{\frac{1}{n}\sum_{i=1}^n (x_i-\overline{X})^2}$

$\sigma_Y=\sqrt{\frac{1}{n}\sum_{i=1}^n (y_i-\overline{Y})^2}$

Where $\overline{X}$ is the average value of a set, and $X$ is the set of $x$ values, which would be the first array in your variables [0,1,0,1] , and $Y$ is the set of $y$ values, the second array [0,0,1,1]. Note the array indexing is 1-4 for the equations, but will not be so in computer code.

The correlation coefficient is the final equation:

$\rho_{X,Y}= \left|\frac{\operatorname{cov}(X,Y)}{\sigma_X \sigma_Y}\right|$

$\rho_{X,Y}= \left|\frac{\sum_{i=1}^n (x_i-\overline{X})(y_i-\overline{Y})}{\sqrt{\sum_{i=1}^n (x_i-\overline{X})^2} \ \cdot \ \sqrt{\sum_{i=1}^n (y_i-\overline{Y})^2}}\right|$

In the scenario where $\sigma_X$ and $\sigma_Y$ are both 0, the vectors are most likely completely correlated, and a different comparison must be made. If one of them is 0, the results are probably not correlated. You will probably not run into these situations if you are analyzing an s-box for bit independence.

Your example

Because your dataset is small, it is easy to use as an example, but is still a bad example, because the correlation coefficient is 0:

The standard dev of your X and Y sets is both 0.5, but the covariance is 0:

$0 = \left|\frac{0}{0.5 * 0.5}\right|$

Now, if you change your X,Y to [0,1,0,1],[1,0,1,0], you can see that they are completely correlated [y = not(x)], and the math agrees, as the covariance calculation is -0.25:

$1 = \left|\frac{-0.25}{0.5 * 0.5}\right|$

Optimization and code

You may notice that standard deviation looks like the square root of covariance between the same set, and for this calculation it is. You may also notice you cancel out the 1/N in the final equation. The intermediate calculations of average values and subtractions are also the same, so you can combine them all into a single calculation. Careful optimization will also help compensate for any floating point rounding errors.

Optimized pseudocode for the final equation on arrays of X and Y would look something like this:

mean_X = ArithMean(X)
mean_Y = ArithMean(Y)

For i = 1 to N
    val_x = X(i) - mean_X
    val_y = Y(i) - mean_Y
    deltasum_c = deltasum_c + (val_x * val_y)
    deltasum_x = deltasum_x + (val_x * val_x)
    deltasum_y = deltasum_y + (val_y * val_y)
Next i

CoVariance = deltasum_c
StdDeviation_xy = Sqrt(deltasum_x * deltasum_y)

If StdDeviation_xy <> 0 Then COR = Abs(CoVariance / StdDeviation_xy)
Elseif deltasum_x = deltasum_y Then COR = 1
Else COR = 0


Why is a Feistel network not a type of substitution-permutation network? I understand what substitution-permutation networks look like. I understand what Feistel networks and Feistel-like networks look like. A Feistel network or a Feistel-like network features substitution and permutations, so why is it considered distinct from an SP-network?

In the substitution step of a typical Substitution-Permutation Network (e.g. in AES SubBytes), the whole state is broken in parts and each part substituted. That's not the case in (the core of) a Feistel cipher, where at each step/round some sizable part of the state is bound to remain unchanged (in order that each step be reversible).


Difference in one time key and one time pad and many time key These terms are confusing me. One time pad is when you use one key for one message. That is what One time key is.

Secondly, what is the connection of many time key, can i use one time pad many times, will it become many time key.

A one-time key is when the encryption scheme is set up such that only one message may be encrypted with a key. A many-time key is when multiple messages may be encrypted with a key. (A one-time-pad is a special case of a one-time key.)

The semantic security definitions for one-time and many-time keys for block ciphers may help. In both, an adversary $A$ submits two plaintext messages $m_1$ and $m_2$ to a black box that internally chooses one of $m_1$ and $m_2$ at random (namely, $m_i$ with $i \in \{0,1\}$ at random), encrypts $m_i$ with a randomly chosen key $k$, and outputs the ciphertext $C = E_k(m_i)$. Adversary $A$ wins if they can find a way of successfully guessing which of $m_1$ or $m_2$ were encrypted and output as $C$.

For the one-time key security model, the attacker gets to submit only one pair of messages. He must then launch his attack having only one input/output to observe. For the many-time key security model, the attacker gets to submit and observe a nearly unlimited number of message input/output pairs. (The choices of $i$ and $k$ remain fixed across each submission for the many-key model.)

To be secure in the many-time key model, the encryption scheme $E$ used above must be randomized. If it is not, then $A$ will break semantic security easily. $A$ will make three random messages and submit $m_1$ and $m_2$ in the first round and get back $c_1$, then $m_1$ and $m_3$ in the second round and get back $c_2$. If $c_1 = c_2$ then the ciphertexts are equal which means the encrypted plaintexts were equal, so the blackbox is encrypting the first message (which was the same in both submissions). If the ciphertexts are different, then the blackbox is encrypting the second message (which was different between the submissions). (Note that security for $E$ does not have to be randomized in the one-time key model.)

Example: CTR mode with a fixed IV is secure in the one-time key model, but insecure in the many-time key model. CTR with a nonce is secure in both models.


$t$-out-of-$n$ Secret Sharing over $\Bbb Z_2$? Is it possible to construct a $t$-out-of-$n$ secret sharing scheme over $\Bbb Z_2$?

Shamir Secret Sharing allows for an arbitrary threshold $t$ and an arbitrary number of participants $n$, but requires the field to have at least $n$ elements. Is there a similar construction that works over $\Bbb Z_2$?

Addendum

One approach could be to use Shamir SS over the finite field $\Bbb F_{2^{\log n}}$. Then, to share $x\in\Bbb Z_2$, this value is first embedded in this field and then it can be secret shared. However, this has an (apparently) innecessary overhead (even though it could be amortized if we share more than value)

The question does not ask specifically for being in Shamir. This is a very interesting question, and has been studied in depth, with Ronald Cramer leading the effort. I refer you to the paper Algebraic Geometric Secret Sharing Schemes and Secure Multi-Party Computations over Small Fields as a starting point in your research.


How could you find the preimage of an isogeny function? How do you know if an isogeny is surjective or not, and how do you tell how many points on E maps to E'? Does the answer lie in the degree of the isogeny function?

Isogenies are always surjective, but there's a nuance. They are surjective over the algebraic closure. The correct statement would be "for every $\mathbb{F}_{17}$-point on the green curve there are three $\bar{\mathbb{F}}_{17}$-points on the blue curve which map to it".

To find the preimages of a point, write down a polynomial system and find its solutions. A computer algebra system (e.g., SageMath) may help. The number of solutions is obviously related to the degree of the polynomial system.


XOR Encryption with bcrypt password de-biasing Objective:  To have a very simple to verify, but very secure small message encryption.

Idea:  Message ⊕ bcrypt( Password).  We remove password biases with bcrypt and then XOR resulting key with the Message.

Implementation.

Limitation: Only messages up to 320 characters long are supported.

10 bcrypt salt values are hard coded:

Salt1 =  $2a$12$geKv/Jdb2zSGEtnn3AuXXe
Salt2 =  $2a$12$h1V42zCLf/F5F7RbueVuZe
Salt3 =  $2a$12$UTX8OMvg1CI3/pnbT0F5Mu
. . . . . . .
Salt10 =  $2a$12$Yq9Vo0yefk6zJlEvJmBf6O

Suppose we have

Message=My safe code is 29540323, my bank card pin is 6926

Password= 32GateKeepers

The message is 50 characters long. bcrypt produces keys 32 characters long. So we need 2 keys to match message length:

Key1 = bcrypt(Password, Salt1) = e8.4zyJT9m9R/KX./Kd2juSHn25IqGUO

Key2 = bcrypt(Password, Salt2) = emTDJsUVCLFE3Jm8Cjx2S2/WmXEVrrU.

Key (50 characters) = e8.4zyJT9m9R/KX./Kd2juSHn25IqGUOemTDJsUVCLFE3Jm8Cj

Code = Message ⊕ Key = 40,65,14,71,27,31,47,116,90,2,93,55,15,34,43,14,29,114,81,6,90,70,97,123,66,18,88,48,81,37,52,33,14,77,55,37,56,23,117,38,42,34,102,44,64,106,91,1,113,92

Question: Is bcrypt de-biasing good enough to use in XOR encryption?

Specific Problem: Attacker knows that the same password was hashed with ten known salts for longer messages.

Specific Question: If the attacker has 10 hashes of the same password with 10 known salts. Given the nature of hashes, does this weaken the password?

Any time you perform more than one evaluation of a password-hashing algorithm where it is a legitimate option to perform it only once you are doing something wrong. Here is why:

If one hash evaluation costs $C$, then 10 hashes with with the same cost-parameter will costs $10 \times C$.
Hashes can be evaluated by a cracker with a cost per candidate-password proportional to $C$. (Probably a lot less than C since they can build or buy systems optimized for and dedicated to password cracking.)
Given $x = H(\text{salt}, \text{password})$, one can guess a candidate password $p$ and compare $x$ to $y = H(\text{salt}, p)$.

If $x \neq y$ then $\text{password}$ is not $p$.
If $\text{password}$ is not $p$ then $x = y$ with only $1 / N$ probability where $N$ is the size of a hash's image set. *

Given knowledge of some $n$-bit long subset of one hash output's bits, a cracker can similarly evaluate the hash of one candidate password with a cost $\le C$ with a $2^{-n}$ false positive rate.

If the adversary knows one character of plaintext (8 bits), then out every 256 candidate passwords, 255 candidates can be eliminated with work proportional to $C$. Only 1 out of every 256 will need two or more hash function evaluations to check for false positives.
Because each 32 byte block can be tested independently, the password cracker will rarely have to do proportional to $10 \times C$ work but the legitimate password-holder will always do $10 \times C$ work,
The cracker has a significant advantage over the honest party compared to an alternate method: Use a single password hash evaluation (a password based key derivation function) to calculate  one key and use that key with a typical symmetric key message encryption algorithm.

One can put key derivation functions (which you can think of as hash functions used to deterministically generate keys) into two categories: password-based KDFs and key-based KDFs.

"Password hashes" (or "slow hash algorithms" as non-experts sometimes say) are used to describe password-based functions that "stretch" passwords. Passwords are usually low entropy (that is they're relatively predictable) and so password hashes and PB-KDFs are designed to be artificially slow for both legitimate parties and password crackers to evaluate with the hope that it makes password cracking less "profitiable".

Standard or "fast" hash algorithms are not necessarily insecure just because they are fast. If passwords were as unpredictable as a 128 bit key then password bases could just store SHA-2 hashes of passwords (preferably still salted for off-topic reasons) with no loss to security.

The right way to do things is to increase your password hashing algorithm's cost parameter by a factor of ten. You're doing the same amount of work, $$1 \times (10 \times C) = 10 \times (1 \times C)$$ so your CPU-time budget doesn't increase. On the other hand, the adversary, with only one slower hash function to crack, now needs to always do proportional to $10 \times C$ work instead of just $C$ work.

If you need more key material than a PB-KDF can give you without multiplying the amount of work you need to do, then derive just one master key from the PB-KDF and feed the derived key to a KB-KDF. You can derive many keys from a key-based key derivation function much faster than the run time of a password hashing function.

If for some reason you must use only hash algorithms instead of a stream cipher, then do
$$K_M = bcrypt_{10 \times C}^\text{**}(\text{salt}, \text{password})$$
$$K_i = \text{SHA-512}(K_M \| i \| \text{nonce})$$
$$\text{ciphertext}_i = \text{plaintext}_i \oplus K_{i + 1}$$

And send
$$\text{ciphertext} \| \text{HMAC-SHA-512}(K_0, \text{ciphertext})$$
because you need message authentication in addition to message secrecy.

In my previous cost analysis I treated the key-stream computation as if it were zero. If you choose a large $C$ then this is a reasonable assumption. Otherwise assume little $c$ is the cost of a "fast" hash. You CPU cost is $10 \times C + 13 \times c$. (Since HMAC is 2 more hashes and you derive one more key for HMAC.) And the adversary's cost is $10 \times C + c$. But both are approxmately $10 \times C$.

For your specific proposal, assuming you're using ASCII encoding of plaintext, you can easily infer 32 bits of every full 32 byte block because no standard ASCII character has a byte value with the most significant bit set.

For other types of plaintext it won't necessarily be so trivial, but you should assume that there are some other ways to guess at plaintext. If there is uncertainty then the adversary could just compare more plaintext-guesses to the same hash evaluation. You get more false positives obviously, but this doesn't prevent cracking. False positives can be distinguished from true positives by evaluating a hash with each salt then looking at the decryption to see if it makes sense. (Check if it contains real dictionary words, or do statistical tests comparing it to reasonable plaintext.)

* Assuming the hash function is unbiased, which is reasonable for good password hash algorithms and many common not-good ones. (SHA-1 and MD5 included among other bad ones.) For the plain-old password hashing use case (not your use) false positives (which are so improbable that it's safe to say they won't happen) are just as good as true positives.

** Use Argon2d if an optimized implementation is available instead of bcrypt. bcrypt is fine if it has an optimized implementation. Same for PB-KDF2 and balloon hashing.  (Don't request PB-KDF2 output length that is too long.) You can use scrypt as well if there is an optimized implementation and if you can give it a large CPU and RAM allowance. ... I'm beginning to see that people hear the "Use ___ instead of ___ for password hashing" advice that's beginning to reach a larger audience now and are taking away the cargo-cult-like idea that it means "Always substitute [password hashing function] for [normal hash algorithm or encryption algorithm]". That's wrong. Only use password hashing functions for password storage and for derivation of a master key.

Edit: Argon2d. not Argon2i.


Hashing - Digital Signing and Trivial Stretching Two very basic questions:

1. Digital Signing

Why is it not possible to just simply replace the hash value from the request?

Examples:

 - Mallory creates two different documents A and B, that have an
   identical hash value (collision).
 - Mallory then sends document A to Alice, who agrees to what the
   document says, signs its hash and sends it back to Mallory.
 - Mallory copies the signature sent by Alice from document A to
   document B. Then she sends document B to Bob, claiming that Alice
   signed the other document (document B).
 - Because the digital signature matches the document hash, Bob's
   software is unable to detect the modification.

Reference: http://en.wikipedia.org/wiki/Collision_attack

It's not transmitted, a secret and at the same time you just send the hash eventually? How does this work out?

  Hash functions are also great for signing data. For example, if you're
  using HMAC, you sign a piece of data by taking a hash of the data
  concatenated with a known but not transmitted value (a secret value).
  So you send the plain-text and the hmac hash. Then, the receiver
  simply hashes the submitted data with the known value and checks to
  see if it matches the transmitted hmac. If it's the same, you know it
  wasn't tampered with by a party without the secret value. This is
  commonly used in secure cookie systems by HTTP frameworks, as well as
  in message transmission of data over HTTP where you want some validity
  to the data.

Reference : https://stackoverflow.com/questions/4948322/fundamental-difference-between-hashing-and-encryption-algorithms

2. Digital Signing

I can't see why this code produces less colitions than the second one
As soon as you have a conflict with two inputs, how does it help to append the same two values for the next recursive loops?

Not recommended:

hash = sha512(password + salt);
for (i = 0; i < 1000; i++) {
    hash = sha512(hash); // <-- Do NOT do this!
}

Recommended:

hash = sha512(password + salt);
for (i = 0; i < 1000; i++) {
    hash = sha512(hash + password + salt);
}

I was reading that part five times and although it kind of makes sense I am having a hard time fully comprehending it.

  Now, hash1 has a probability of collision of 0.001%. But when we do
  the next hash2 = sha1(hash1);, all collisions of hash1 automatically
  become collisions of hash2. So now, we have hash1's rate at 0.001%,
  and the 2nd sha1 call adds to that.

Reference : https://stackoverflow.com/questions/4948322/fundamental-difference-between-hashing-and-encryption-algorithms

Response to Question 2 :

algorithm 1 : change the algorithm into this, it will be easier to explain

hash1 = sha512(password + salt1);
hash2 = sha512(password + salt2);
for (i = 0; i < 1000; i++) {
    hash1 = sha512(hash1); // <-- Do NOT do this!
    hash2 = sha512(hash2); // <-- Do NOT do this!
}

For 2 different inputs hash1 and hash2, if there is a collision on iteration 10 then the next 990 iterations will crunch the very same work and output the same hash1 and hash2.

The more you hash, the more intermediate collisions you could create at iteration 12, 15, 20, 100, 101, 314 .... Every additional iteration increase the probability of collision.

if Bob run this code (half of the previous loop)

hash1 = sha512(password + salt1);
for (i = 0; i < 1000; i++) {
    hash1 = sha512(hash1); // <-- Do NOT do this!
}

And if Alice run this code (half of the previous loop)

hash2 = sha512(password + salt2);
for (i = 0; i < 1000; i++) {
    hash2 = sha512(hash2); // <-- Do NOT do this!
}

As of previous comment, security decreases, because Bob and Alice could impersonate each other because of the increased collision probability. When the algorithms complete

P(hash1 == hash2) > 1000 * P(sha512(password + salt2) == sha512(password + salt1) )

If there are more than Bob And Alice, John, Joe, Jack and Jeremy are running this loop, then the probability of collision is still increased by devastating effects of the "birthday paradox".

algorithm 2: something is different on each iteration, that is the big difference.

hash1 = sha512(password + salt1);
hash2 = sha512(password + salt2);
for (i = 0; i < 1000; i++) {
    hash1 = sha512(hash + password + salt1);
    hash2 = sha512(hash + password + salt2);
}

If there is a collision at iteration i, then the next iteration i+1 is more than likely to produce a non-collision. Every iteration has provably the very low collision probabilities of sha512 when provided with different input. Split the algorithm between Bob and Alice, when the algorithm completes

P(hash1 == hash2) == P( sha512(password + salt2) == sha512(password + salt1) )

Note : It is possible to have different values of salt at each iteration, as suggested by the referenced page.


How to change the master password in a password manager For a personal project, I'm building a password manager, based off the project in this syllabus from Stanford http://crypto.stanford.edu/~dabo/cs255/hw_and_proj/proj1.pdf

Since I don't exactly have to take the class for the credit and strictly follow the instructions, I've gone ahead and changed some things (like I added a MySQL DB for the backend). What I'm wondering is this: how do you handle someone changing the master password? I have a master password that is used just like the syllabus says, but what if I want to flesh it out more, and have an option to change your master password (seems like something a password manager should have!). How do I implement this? The straightforward way is to simply decrypt everything then re encrypt everything with the new master password. I was just wondering if there's something that's not so inelegant that I'm missing.

In the context of most Password Managers that use encryption, you will generate a Master Data Encryption Key (MDEK) which will serve to encrypt all the passwords and the user's password would be the Key Encrypting Key (KEK) to encrypt the MDEK. This way, the MDEK stays the same when you change your Master Password derived KEK that wraps the MDEK.


Does exponentiation by squaring work on Montgomery curves? Consider the point multiplication $Q=[d]P$, where $P$ a point on elliptic curve multiplied with an integer $d$ to get another point $Q$ on the same curve. This operation can be computed by a predefined sequence of point additions and point doublings. Is it possible to apply the same technique to Montgomery curves, as group operations in Montgomery form seem simpler than in short Weierstrass form?

Yes, exponentiation by squaring can be applied to any associative binary operation with identity (that is, to any monoid, which includes groups like elliptic curves as a special case), independent of the particular representation.

However, the main advantage of Montgomery curves is that there is an improved algorithm (appropriately named Montgomery ladder) for point multiplication, which does not require the $y$ coordinate of the input point and achieves better resistance against side-channel attacks since it performs the same sequence of operations for all exponents of a given length (one addition and one squaring per bit), so you might want to use that instead if you are already going for a Montgomery curve.


Does AES CTR mode store header information in encrypted files? According to the movable-type.co.uk website,

  In the ‘counter mode’ used in this implementation, a counter which changes with each block is first encrypted, and the result is bitwise xor’d with the plaintext block to get the ciphertext block (so the plaintext is not actually directly encrypted). A unique ‘nonce’ is incorporated in the counter to ensure different ciphertexts are always generated from the same plaintext every time it is encrypted; this number is stored at the head of the ciphertext to enable decryption. A combination of seconds since 1 Jan 1970, a millisecond-timestamp, and a sub-millisecond random number gives a very effective nonce. (To resist cryptographic attacks, the nonce does not need to be secret or unpredictable, but it is imperative that it is unique). In this implementation, the initial block holds the nonce in the first 8 bytes, and the block count in the second 8 bytes…

So, it says that the “nonce is stored in the cipher text to enable decryption”. Is that true for every AES CTR mode implementation? And if we want to decrypt a certain block from the middle, do we first have to extract the nonce from the first 8 bytes and the block count from the following 8 bytes?

I would like to ask if that is true for every AES CTR mode implementation?,

Doesn't have to be. You can store the nonce anywhere. You could even send it to the recipient via a different channel (e.g., email the ciphertext and use SMS to transmit the nonce). Storing it at the beginning has its advantages. For example, if streaming the data, you can begin decrypting immediately.

  and If we want to decrypt a certain block from the middle, we first have to extract the nonce from the first 8bytes and block count in the second 8 bytes ?

Yes, if you want to decrypt a particular block in the middle, you must extract the nonce first, and figure out what the proper counter value should be. Then you can decrypt.


What is the longest AES key that has been recovered in practice? I can recover something trivial like a 16-bit AES key in practice. I'm confident that a 64-bit AES key can be recovered. However, I have been unable to find any documentation of the biggest AES key that anyone claims to have recovered in practice. Are such competitions held, and is there a recognized progress meter that is kept?
Edit:  I'm talking about brute-forcing intentionally weakened keys, i.e. repeating the first X bits of the key to the end.

Are such competitions held, and is there a recognized progress meter that is kept?

No. It is generally believed that $2^{128}$ AES keyschedule and encryption operations are out of reach for just about anyone. If and when that changes and $2^{128}$ draws in to be a more realistic number perhaps people will do that.

However, I have been unable to find any documentation of the biggest AES key that anyone claims to have recovered in practice.

This is usually not an interesting publishable result unless you also have found some major optimization to some part of the computation and thus not very desirable to do for academics.

As for search speeds:

On a CPU - assuming you get lucky with instruction scheduling - one round of AES with a keyschedule computation (very optimistically) costs you about 3 CPU cycles on a single core. For each AES instance there are 10 such steps, so around 30 cycles overall for on-the-fly key scheduling and encryption of one block - using only throughput not latency numbers. This amounts to about 1-2 billion AES key tests per core per second on a modern CPU. Assuming it is one of the beefiest around it has 64 physical cores and two CPUs on a mainboard amounting to say 200 billion AES key tests per second per mainboard. Feasibly a determined attacker can acquire and operate say ten thousand such mainboards amounting to $2\times 10^{15}\approx 2^{50}$ key tests per second. Then a realistic upper bound for how long would want to have this hardware run non-stop would be say 10 years if determined which adds another factor of $\approx 2^{28}$ amounting in total to $2^{78}$ AES keys using 20,000 of the current beefiest CPUs run for 10 years with a highly optimized implementation.
As for GPUs: A top-end Nvidia Pascal GPU hits about 32GB/s of AES throughput. That is 2 billion AES instances per second without the keyschedule, with the keyschedule it will probably drop down to ~800 million AES instances per second. Even if we assume that later GPU generations give a 5x performance increase to this number we'd only be looking at the performance of 1-2 additional CPU cores for a lot more power draw, so this is likely not worth it.
As for FPGAs, this paper claims around 120Gb/s throughput from an FPGA that has ~150 thousand lookup tables. Nowadays there are FPGAs around that are 25x larger. Using the usual (optimistic) factor of 3 for the keyschedule we're looking at around 8 billion key tests per second and card. This might be worthwhile if you can cool it properly but chances are it's a better investment of power to use more CPUs (which draw comparably much).
As for ASICs, this paper claims $678\times 10^{-6}$ bits per clockcycle-gate as the best result (ish). Assuming a GPU-sized die running at say 1GHz this would amount to $2\times 10^{16}$ bits per second or $2^{47}$ AES instances per second. Dividing this by our usual factor yields about $2^{45}$ instances per second. Assuming then that you can in fact produce, power and cool such a large die and somehow stack say 8 into a server mainboard's PCIe slots it would give you $2^{48}$ tests per board or almost $2^{90}$ tests in 10 years using 10,000 boards with 8 GPU-sized dies each running at 1GHz for 10 years.


Combining a keystream generator with a block cipher I understand that:

A stream cipher's security is diluted if the same key is used more than once. This is fixed by using an additional initialization vector in the keystream's computation.
A block cipher run in the most simple way, electronic codebook mode, has negligible security due to pattern preservation. This is avoided by using cipher-block chaining or another mode of operation.

Consider that using a keystream generator like in stream ciphers to produce a string of keys for encipher individual blocks of a message with a block cipher:

Does not fall prey to the problems that reusing a key plagues stream ciphers with because of the avalanche effect present in block ciphers.
Does away with the need to use more complicated modes of operations in a block cipher due to each block being encrypted with a different key.

Is this analysis correct? Are there implementations like this that are already out there?

Under your scheme, the keystream generated by the stream cipher will be the same for each message enciphered with the same key. While your scheme does not encrypt identical blocks of plaintext in the same message to the same value, it does encrypt identical blocks of plaintext in different messages to the same value, meaning that XORing two ciphertexts together will give clues to the structure of the plaintext inside. This can quickly become relevant when used, for example, in a network protocol, because the sorts of structured data computers like to exchange with each other frequently include significant repeated or predetermined segments.

Completely beside the issue of whether your scheme provides confidentiality, it can't replace using "complicated" block cipher modes of operation, because its performance would be abysmal. It's not obvious from the definition of a block cipher, but there is a reason that all the popular block cipher modes of operation vary what they do with the plaintext or what they do with the ciphertext but never get inventive with what they do with the key. In block ciphers, a significant amount of computation is put into expanding the key into a "key schedule," or list of the subkeys that will be used in each round of the cipher. Once the key schedule has been calculated, subsequent blocks can re-use the same data if the key hasn't changed, meaning that encrypting 1,000 blocks with a single key is much, much faster than encrypting them to different keys. If you wanted to change the key for each block, you'd have to re-do the key schedule operation each time, and that would suck.

Finally, a note on IVs. An external source of entropy, in the form of an IV, is required for probabilistic encryption schemes. Probabilistic encryption guarantees that the same message encrypted twice will not produce the same ciphertext, and that property is needed to assure semantic security. However, semantic security is a very strong requirement, and while using deterministic encryption (for example, by calculating an IV deterministically as I suggest in the comments on Maarten's answer) means you won't have semantic security, for many applications it's good enough. Consider implementing strong encryption on a microcontroller, where entropy is scarce and available sources are easily tampered with: deterministic encryption will leak that you've encrypted the same thing twice, but that's usually much more acceptable than courting the spectre of a full-blown break if someone somehow manages to poison your PRNG.


Why does a Galois field have to have an order of $p^n$ where $p$ is prime? I was reading about this in a cryptography book last night.  I have a hunch about this, but I can't quite put my finger on it.  I think this is a similar situation to an affine cipher, where the multiplication factor has to be relatively prime with the size of the alphabet in order for the function to be surjective.  Obviously for practical purposes, it would have to be $p^n$ where $p$ is the arity of the number system and $n$ is the bit width of a memory unit.  But is there also a theoretical basis for requiring that a Galois field be of size $p^n?$

Fix a finite field $k$ of $q$ elements, with additive identity $0_k$ and multiplicative identity $1_k$.

For any integer $n$, let $[n]$ be the $n$-fold sum of $1_k$.  Clearly $[a + b] = [a] + [b]$ and $[a\cdot b] = [a] \cdot [b]$.  Since $k$ is finite, for any $n$, in the sequence $[a]$, $[a + 1]$, $[a + 2]$, etc., there must be a repeat; let $p$ be the smallest integer so that $[a] = [a + p] = [a] + [p]$.  Then $[p] = 0_k$, and in the sequence $[1], [2], [3], \ldots, [p]$, the element $[p]$ is the first zero element.
$p$ is called the characteristic of the field.  Suppose $p$ were composite, with factors $1 < a \leq b < p$ so that $p = a\cdot b$.  Then $0_k = [p] = [a\cdot b] = [a] \cdot [b]$, but $[a]$ and $[b]$ are nonzero because $[p]$ was the first zero element in the sequence $[1], [2], [3], \ldots, [p]$.  This is impossible in a field, so $p$ must be prime.
The set $\{[0],[1],[2],\ldots,[p-1]\}$ forms a subfield $k_p$ of $k$, since it is by construction closed under addition and multiplication.  Thus the extension field $k$ forms a vector space over the subfield $k_p$.  Being finite, this vector space is necessarily finite-dimensional, of dimension $n$, and thus has exactly $p^n$ elements.  Hence $q = p^n$ for some $n$.


Why is the simulation required in these identity-based encryption security proofs? In identity-based encryption papers (i.e.this) it is very difficult for me to understand security proof. I don't know why they prove assumption (BDH, BDDH) for security of their scheme. Some uses random oracle and most of them try to simulate the scheme. Why is the simulation required in these security proofs?

(I assume you are asking about this paper based on your previous questions.)
They do not prove BDDH in their security proofs.

  Assume that an attacker $A$ breaks IND-sMID-CPA of the above scheme
  with probability greater than $\epsilon$ within time $t$ [...]. We show that using $A$, one can construct an attacker $B$ for solving the
  BDDH problem.

In security proofs by reduction, we assume the proposition is not true (here: assume the proposed scheme is not IND-sMID-CPA) and show the proposition being false would imply some contradiction (here: solving BDDH problem which is believed to be hard). In this case assuming existence of attacker $A$ against IND-sMID-CPA security of the proposed scheme, they construct algorithm $B$ for solving the BDDH problem. Attacker $A$ is expected to participate in IND-sMID-CPA experiment, so through the reduction algorithm $B$ should simulate the experiment for $A$ and since this proof is in the random oracle model, $B$ should simulate random oracle as well.

  problem B is reducible to problem A if an algorithm for solving problem A efficiently (we call this algorithm $A$) (if it existed) could also be used as a subroutine to solve problem B efficiently.

In this context:

A = breaking IND-sMID-CPA
B = BDDH problem

reduction algorithm $B$ uses adversary $A$ as a subroutine. $B$ doesn't know how $A$ works; the only thing $B$ knows is that $A$ is expecting to attack problem A. so given an input instance of problem B (here BDDH), reduction algorithm should generate (simulate) an instance of problem A for $A$.

Chapter 3.3.2 of Introduction to Modern Cryptography explains "proofs by redcution".


Elliptic Curve is DH function or PKI? can we reuse same ECC key on TLS for long terms or it must be used just once? (i mean can we use ECC like RSA?)

is there patent free ECC implementation ?

Yes, TLS supports ECDSA for signing and ECDH for key exchange. You can read about it RFC 4492. Notice you don't get RSA, but you get signing and key exchange which are major functions of TLS.

Related material:
How do I create an ECDSA certificate with the OpenSSL command-line
SSH key-type, rsa, dsa, ecdsa, are there easy answers for which to choose when?

As far as patents go, see this question. I am not aware of any ecc libraries that claim to not violate patents. Bouncy castle says it is up to you to figure that out. Openssl's ecc implementation was supposedly built to avoid patent issues.

Is elliptic curve a DH function or PKI
Neither really. There are elliptic curve variants of ElGamal and RSA. Depends exactly what your definition of PKI is though as you can have ECDSA certificates with a public and private key. You can then start a PKI by signing other certificates, etc.


Is zero IV with AES-CBC safe if CPA is not possible and indistinguishability is not an issue? Is using zero IVs with AES-CBC safe, if chosen-plaintext attack (CPA) is not possible and ciphertext indistinguishability is not an issue?

Practical example:

Alice operates an online service that stores user data on a cloud-based database.  Alice is worried about the possibility of someone making off with the database, so wants to encrypt certain data to ensure recovery in that eventuality is impossible.

Alice is mainly concerned about data that are sensitive in their own right, such as those that identify an individual, or are tokens such as CC numbers.

Examples are:

Social security numbers
Addresses of residence
Phone numbers
Credit card numbers

Alice knows chosen-plaintext attacks are a concern, so uses a per-user key to prevent an attacker from loading the database with known-plaintexts.

However, Alice thinks ciphertext indistinguishability is a non-issue because knowing two ciphertexts equal doesn't usually lead to knowing the actual plaintext.

Is Alice safe in assuming data benefits from this kind of encryption and is secure from cryptography?  (i.e. Wholesale data breach.)

One problem I can think of is:

If a user's phone number and credit card number are coincidentally identical, attacker can gleam this information from the encrypted database.  They then only need to obtain the former to also get the latter.
If the first 16 bytes of the user's address is somehow identical to their social security number, again, the attacker can determine this from the encrypted database.

Are there any other problems?

Furthermore, is using AES-CBC this way any safer than using AES-ECB?

Furthermore, is using AES-CBC this way any safer than using AES-ECB?

Yes, using CBC mode is (almost?) always safer than using ECB mode.

  Is using zero IVs with AES-CBC safe[...]?

No it is not safe, because if you re-use a key with that construction you will leak the common prefix between messages, at block granularity. That is if you have three messages encrypted with CBC with the same IV and key $m=A\parallel B\parallel C\parallel G$ and $m'=A\parallel B\parallel D\parallel G$ and $m''=A\parallel E\parallel F$, with $A,B,C,D,E,F,G$ being 16-byte blocks, you can tell that $m'',m'$ and $m$ share the first block in common and you can tell that $m'$ and $m$ share the first two blocks in common, of course you don't actually directly learn the value of these shared blocks.

Note that either changing the key or the IV for each message fixes the above problem.

  There are more modern modes (which are authenticated) which only leak equality of messages upon a (IV,Key) re-use: That's kinda what I'm
  looking for. Which modes are those?

These modes are called nonce-misuse resistant authenticated encryption modes (nmrAE). The two standard suggestions for this are AES-SIV and AES-GCM-SIV or AES-PMAC-SIV, both of which will offer standard authenticated encryption security if you use different (IV,Key) pairs with each message and will both offer (some) security if such a pair is re-used and of course they offer authentication as well and only leak equality of the underlying messages upon a re-use.


Why is g is less than p in Diffie-Hellman? In non-authenticated DH, p and g are made as public record. p needs to be a large prime number and g should be smaller than p.  Why does g need to be smaller than p?

It's an element of the field of all integers modulo $p$, and these are represented by the numbers $0,\ldots, p-1$. And $g$ will be one of them.


Authentication and encryption of messages I have a hybrid scenario of public key cryptography in which messages between users are encrypted using AES with a symmetric key generated ad hoc.

A typical hybrid system scheme considers for every message to send the couple composed of:

The message encrypted with the symmetric key
The symmetric key (using AES GCM I suppose I have to include also the IV used and additional data? - And what additional data could I use?) encrypted with the recipient's public key

I want to sign the messages in order to authenticate the sender and - if possible - to authenticate also the data.

I want to ask you if in my scenario would it be better if:

1) I authenticate the message in plaintext enciphering it with the sender private key, then encipher the result (x) with the AES KEY obtaining y and lastly send the pair (AES key enciphered with recipient's public key; y)

2) I encipher the message with the AES key, then I encipher the AES key  with the recipient's public key obtaining x and then I apply my private key to the pair (symmetric encyphered message, x). Finally I send the result.

I also checked the answers to this question in order to understand better this topic:
Should we sign-then-encrypt, or encrypt-then-sign?

In order to allow data authentication should I add to one of the above schemes a MAC? How?

And, finally, does AES GCM provide for authentication in itself without other constructs to work with?

First and foremost, you don't mention why you feel the need to invent your own crypto protocol. "Don't roll your own crypto" is a common saying around here for a reason: there are so many small things to be aware of when implementing a crypto protocol, and if you do any one of them wrong, your entire protocol will be insecure. Designing crypto protocols really needs to be done by committees of experts - preferably in an RFC to give the public a chance to point out things that you missed.

For the use-cases you describe, why are you not using an off-the-shelf SSL/TLS or PGP library?

If this is just for your own learning, then cool, but if you plan to use this for real then please tell me the name of the project or product it will be in so I can, umm, take a closer look -_-

The following assumes that this is just a learning project.

You keep saying

  encipher with the private key

What does that mean? That doesn't really make sense as a concept. I know that with RSA the public key and private key have the same format and can both be used for either encipherment or decryption, but in general with other algorithms (DSA, ECC, many of the post-quantum proposals) the two keys look very different and only the public key can be used for encipherment.

Are you trying to do a digital signature? If so, you need to calculate the signature for the massage, and attach the signature string to the packet in some way.

At it's core, your question seems to boil down to Should we sign-then-encrypt, or encrypt-then-sign? I'm not really clear what additional information you're asking for, but let's look at how some standard protocols solve this problem:

TLS / SSL

TLS takes a different approach by using authenticaled key exchange prior to sending any messaged: during the initial handshake when the connection is opened, both parties use public-key crypto to authenticate themselves, and to establish a shared AES key that only those two people know. Once that has been done, you don't need to use public-key to authenticate each message because if the message decrypts properly with the shared AES key, then it must have been sent by the other person.

PGP

This is a little closer to your use-case. You can read about all the packet types that PGP supports in section 5 of the PGP RFC-4880. My understanding is that the programmer or end-user has the choice of whether they do

sign-then-encrypt (like your option 1)

Symmetric-Key Encrypted Session Key Packet (Tag 3)
    Signature Packet (Tag 2)
        data

or encrypt-then-sign (like your option 2)

Signature Packet (Tag 2)
    Symmetric-Key Encrypted Session Key Packet (Tag 3)
        data

So this doesn't really help with your core question of sign-then-encrypt vs encrypt-then-sign.

Bottom line:

You've asked a lot of questions here, and I have only answered some of them. I suggest you go back and study the fundamentals of cryptography. I think some of your questions would answer themselves.
For any practical use, please for the love of God, use a standard library of either TLS or PGP.


How would using only one s-box affect security of Blowfish? Schneier says:

  Fewer and smaller S-boxes. It may be possible to reduce the number of
  S-boxes from four to one. Additionally, it may be possible to overlap
  entries in a single S-box: entry 0 would consist of bytes 0 through 3,
  entry 1 would consist of bytes 1 through 4, etc. The former
  simplification would reduce the memory requirements for the four
  S-boxes from 4096 bytes to 1024 bytes, the latter would reduce the
  requirements for a single S-box from 1024 bytes to 259 bytes.
  Additional steps may be required to eliminate the symmetries that
  these simplifications would introduce. Additionally, four different
  10- or 12-bit indexes into a single large S-box could be used instead
  of the current series of S-boxes.

Just theoretically, how would using same s-box instead of 4 different affect the security of Blowfish (considering no other change is made)?

By "eliminate the symmetries", he probably means rotations? Is this really required, since round keys already break the symmetries?

Because I didn't get any answer, I did some experments with Blowfish's F function and here are my observations:

Because Blowfish's F function is not bijective, on average only every second value is returned and therefore different input can output same value (F(x) = F(y)). By reducing number of S-boxes this non-bijectivity becomes even worse. About 8 to 32 of inputs will result in F(x) = 0. But problem is worse, because addition hides problem; With F() with XORs instead of additions about 2^18 inputs will output 0. This happens, because (S(X) xor S(X) xor S(X) xor S(X)) or (S(X) xor S(X) xor S(Y) xor S(Y)) ... is always 0. So addition breaks symmetries a bit.

I have also found comment by David Wagner on question about strength of Blowfish with broken F (((S_1[a] + S_1[a]) ^ S_1[a]) + S_1[a]). He overlooked that also the same input byte is used. So he was answering my question.

  For what it's worth (which is not very much), I don't immediately see
  any plausible way to exploit this on the full Blowfish, though I
  haven't spent any serious amount of time thinking about this.  16
  rounds, with key-dependent S-boxes, forgives many sins.

https://groups.google.com/forum/#!topic/sci.crypt/21SwIdSqOo8

Considering the S-box is unknown, addition and 16 rounds I think it should be fine, but I don't think it's a good idea.


Why does HKDF use HMAC(salt, key) instead of HMAC(key, salt)? I've been looking over the HKDF specs (RFC 5869), and something I noticed is that in the key and salt are reversed:

2.2.  Step 1: Extract

 HKDF-Extract(salt, IKM) -> PRK

 Options:
    Hash     a hash function; HashLen denotes the length of the
             hash function output in octets

 Inputs:
    salt     optional salt value (a non-secret random value);
             if not provided, it is set to a string of HashLen zeros.
    IKM      input keying material

 Output:
    PRK      a pseudorandom key (of HashLen octets)

 The output PRK is calculated as follows:

 PRK = HMAC-Hash(salt, IKM)

Neither the spec nor the paper seem to address the order.

To me it seems like HMAC(salt, IKM) would be weaker against a brute force search of IKMs, as the digest of the salt can in this case be precalculated by an attacker (assuming the salt is a non-secret value or zero).

What is the benefit of using it this way?

To me it seems like HMAC(salt, IKM) would be weaker against a brute force search of IKMs, as the digest of the salt can in this case be precalculated by an attacker (assuming the salt is a non-secret value or zero).

Yes, it is slightly faster to brute force, but if the IKM does not have enough entropy to give brute force resistance, then a small factor will likely not be significant. In that case you would want to use a slow iterated function.

With a short IKM and a single block of output from the Expand step, you need eight calls to the compression function, two of which can be avoided if the salt is reused between calls. So the actual speedup is only 25%.

  What is the benefit of using it this way?

It has to do with the security proofs (see in particular Section 6 and Appendix C).

If you feed the IKM directly into a hash function, there are some possible distributions for the IKM that would be dependent on the hash function structure (Lemma 2). By using a random (secret or not) salt as the HMAC key. the function is randomized and the distribution is independent.

Additionally, that order means that if the HKDF salt is a secret key the Extract function becomes a PRF. That is discussed in e.g. Appendix D of the paper.

Also, note that HKDF-Expand uses the normal order, because there the PRK is already a cryptographic key.


Convert homomorphically encrypted decimal number to homomorphically encrypted binary number I am trying to convert a homomorphically encrypted integer to a homomorphically encrypted binary number (in vector form like {Ciphertext(1),Ciphertext(1),Ciphertext(0),Ciphertext(1)}), which I cannot really get the remainder (and any other "intermediate results") without decryption.
Is there really a way to do this?

The question could be change to "How to evaluate mod $N$ under FHE". For CKKS scheme, there exist approximations for that: https://eprint.iacr.org/2018/153.pdf


substitution-permutation network construction I want to understand more about substitution-permutation network, if we modify it
instead of carrying out the key-mixing, substitution, and permutation steps in alternating order for r rounds, the cipher instead first applies r rounds of key-mixing, then carries out r rounds of substitution, and finally applies r permutations.
How this could affect the security, and what is the security of this construction?

Assuming your key mixing layer uses XOR:

$M \oplus K_0 \oplus K_1 \oplus ... K_r$
$K_0 \oplus K_1 \oplus ... K_r$ effectively compresses into one, single key
Equivalent to $M ^ K$ in terms of security

More importantly, since the only key addition layer is at the front, and the S-box and permutation layer are assumed to be publicly known, a single known plaintext attack could break the construction: Simply encrypt the known block of information and then invert the permutation and S-box layers on the ciphertext. This leaves us with $M \oplus K$, which, since we know $M$, means we can do $M \oplus M \oplus K$ and recover $K$. Granted, $K$ is only the XOR sum of $K_0 \oplus K_1 \oplus ... K_r$, but we don't actually need the values of $K_0, K_1, ... K_r$ individually. We only need their sum in order to perform the encryption/decryption operation.

It is important for there to be key addition layers before and after the application of a round function, if the round function is to provide security. They do not have to be immediately prior to or after each application, i.e. adding a key, iterating the core permutation a bunch of times, then adding a key again is a valid strategy as well.


Groth-Sahai proofs and the hidden-bits model In the Groth-Sahai proof system, the authors mention (section 1.2) that one of the reasons behind the inefficiency of previous NIZK proof systems is their reliance on the hidden-bits model. Then, they state that other previous work avoided this by using bilinear pairings (but still used a reduction to CSAT, which is not the focus of their proposal.) Thus, I understand that, in their system, they follow the bilinear pairing approach to avoid the inefficiency stemming from the hidden-bits model.

Then, in the description of their framework (section 5), they use a Common Reference String (CRS) that includes some carefully chosen group elements and mappings. Among these mappings, there is $\iota_1,p_1,\iota_2,p_2,\iota_t,p_t$, where the $\iota$'s allow moving from the "witness domain" to the "commitment domain" and the $p$'s the other way around. The security of their proposal relies on the hardness of applying the $p$ mappings without an appropriate trapdoor.

Now, my doubt is: How is this avoiding the hidden-bits model? I mean, there is a predefined CRS with public information, which is later used by a prover to "hide" information from a verifier, since the verifier cannot apply the inverse mappings (the $p$'s). Which is precisely the hidden-bits model if I'm not mistaken.

Is it just that, with the statement in section 1.2, they rather meant that they create an "efficient version" of the hidden-bits model? Have I just got something messed up?

The hidden bits model is an abstraction of the CRS where the prover is able to reveal some random bits and not others (and where these are guaranteed to be uniformly distributed). The Groth-Sahai approach indeed uses a trapdoor in the CRS but its not the same as the hidden bits approach since the trapdoor is used in a different way (in the hidden bits model the trapdoors are the preimages of each block which enable revealing the bits).


Determine Encryption Used by Examining File Headers? I have an encryption problem that I hope you might be able to help me with.

I have a bunch of encrypted files.  Some of them were encrypted with mdecrypt.rijndael-256 in PHP and some were encrypted with mdecrypt.tripledes.  A database used to exist that mapped the filename of each encrypted file to the appropriate encryption algorithm used for that file.  That database has long been wiped from the server and now I only have the encrypted files that are either AES or 3DES.  So my question is, is it possible to determine which algorithm was use to encrypt each file by examining a header or something?  An added bonus would be if you could provide a example of how to determine the algorithm using a php script (although that's secondary and I can probably figure that out if I know what to look for).

Thanks.

That depends. A file cannot be directly encrypted by a block cipher. You need at least a mode of operation for that block cipher and an IV. I guess you should first determine the correct encryption format that was used.

If your file is directly encrypted you could try and decrypt using one of the two methods. If the result looks like a file then the right mode must have been chosen. You can e.g. test this by using the file command on Posix systems after decrypting the first kilo byte of the file (into a separate, partial file).

Alternatively you could perform a simple randomness test on the result. If that fails, then it is likely a correct file and the correct algorithm. This may however lead to more false positives than the method used above. You may want to test which of the partially decrypted files is least random and chose that algorithm.


Doubts about Authenticated Data Structures logic I am studying the theory of authenticated data structures, like Merkle Trees and I have a doubt: Why use them?

For example, to be sure that a cloud provider didn't modify my files, why do I have to ask for a particular data block and have the cloud reply with a hash path from the leaf to the root to authenticate all the tree (and then all the database)?

Isn't it simpler to ask a for particular piece of the DB (suppose the DB is divided in blocks) and receive from the cloud provider that block with a digital signature?
In this way, I can ask continually for a lot of blocks without using a Merkle tree at all.

I am reading materials about the RSA accumulator, bilinear maps, Bloom filters, etc., and every time I read about different protocols built over particular data structures.

Since using these techniques has a computational cost (e.g., RSA accumulators can be expensive) my question is as asked before:
Instead of having a single digest that authenticates the entire set or DB, why not require different pieces of data with the digital signature?

I hope you can answer my strange question!

Thank you!

One reason I see is that simple signatures only prove the data block was produced by you, but not that the block is what you queried for.

A simple example: suppose you have 4 data blocks $d_1,d_2,d_3,d_4$ which you can query by index, i.e. on query = 1, the server should return $d_1$.

Now when using a signature scheme, you store $(d_1,d_2,d_3,d_4)$ as well as their signatures $(s_1,s_2,s_3,s_4)$. Later you query 3, and the server returns $(d_{x},s_{x})$. At this point, you can verify that $s_x$ is indeed a signature of $d_x$. But how can you be sure $d_x$ is $d_3$ you asked for? What you have got can be $(d_1,s_1)$ for example, which will pass the check. Remember that the main spirit of using a cloud is that you store your data in the cloud without having to keep a local copy. Now you won't be able to tell whether you get the right answer.

If you use a Merkle tree, then you will get a tree like this:

Now when you query 3, you will get $(d_3',h0',h11')$. You can hash $H(h0'||H(H(d_3')||h11'))$. If the result is the same as the root you saved, you must have got $d_3$ as you requested, as the path is unique for this item.

A similar issue when using signatures is that what if the server returns an old version of the data item? There is no way to tell because the signature does not prove freshness. When using a Merkle tree, the root is updated every time you update the data, so it gives you freshness guarantee.


Why do we use hex output for hash functions? Why do we use hex representation as default for the output of a hash functions result?

For example the sha256 hash function: the output of sha256 in hex representation uses 64 characters, while using base64 on the raw output produces 44 characters.

Demo:

<?php
$password = "password";
$sha256 = hash('sha256',$password);
echo 'sha256('.strlen($sha256).'): '.$sha256.'
';

$sha256Base64 = base64_encode(hash('sha256',$password,true));
echo 'sha256('.strlen($sha256Base64).'): '.$sha256Base64.'
';

Output:

sha256(64): 5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8
sha256(44): XohImNooBHFR0OVvjcYpJ3NgPQ1qq73WKhHvch0VQtg=

Hexadecimal is traditional -- by this, I mean that there first were command-line tools that used hexadecimal for output, then other people using the hash functions found it fit to stick to hexadecimal, if only to be able to compare their values with the output of the aforementioned tools. That's how traditions get established: a more-or-less random choice at the start, then the need for interoperability and backward compatibility kicks in.

In the case of hexadecimal in cryptographic algorithms, one can probably trace it to the use of C language for reference implementations. Most algorithms are described with a specification (mathematical description, usually typeset in LaTeX), and a reference implementation that produces basic test vectors. For better or worse, the reference implementation is usually in C (or sometimes C++). In C, there is no standard facility for Base64 encoding (some programming platforms offer that, or external libraries, but it is not standard); but hexadecimal is easily obtained with a simple printf() with a "%08x" format string. As a very classic example, consider the MD5 specification (RFC 1321), which contains a reference implementation that does hexadecimal output.

The tradition is well entrenched; for the SHA-3 competition, NIST actually asked for reference implementations in C, and known-answer tests with a fully-specified text format that was hexadecimal throughout.

It must also be said that hexadecimal is convenient for debugging: the human developer can easily observe hexadecimal output and map these to individual bits, by doing the simple conversion in his head. Base64 is not as simple, because it entails 64 glyphs instead of 16, including some which are prone to induce visual confusion (1 vs I vs l, 0 vs O...). Also, many algorithm internally use 32-bit or 64-bit words, that map well to CPU registers; 32 and 64 are multiples of 4 but not of 6, so Base64 encoding again implies some non-trivial splitting.


Statistical attacks on a list of MD5/SHA-1 hashes? I have a list of MD5 and SHA-1 hashes where the input string is of the form

secret1000
secret1001
…

all the way up to

secret2000

Are there any attacks, analytical techniques that can give me any insights on the input strings?

The comments sum it up perfectly…

  Poncho’s comment:
    None are known, and it would be a significant result, as you really do see hashes like that in practice...

and

  Maarten Bodewes’s comment:
    MD5 and SHA-1 have been broken for collision, but then the input should still be formatted in a specific way. More importantly for your question: there is still no chance of finding the input (without "guessing" it correctly); they are still one-way-functions.


Magic Number to calculate number of rounds for M-R in FIPS 186-4 In Fips 186-4, there is an algorithm in Appendix F (at page 117 in my copy of the 2013 version) to calculate the number of rounds of the Miller-Rabin primality test to random bases.

Does anybody know where the magic number 2.00743 comes from or do I really have to work through the paper Average Case Error Estimates for the Strong Probable Prime Test by I. Damgard et. al

This constant is used to approximate $(\pi(2^k) - \pi(2^{k-1}))^{-1}$, as shown in (4.1) of the Damgard et al. paper:

$$
p_{k,t} \le (\pi(2^k) - \pi(2^{k-1}))^{-1} \sum\nolimits'_{n \in M_k} \bar{\alpha}(n)^t \,.
$$

Most of the formula in the NIST document, between the square brackets, is dealing with the $\bar\alpha$ sum. The left side is dealing with the prime difference approximation.
From Propositon 2 of the Damgard et al. paper, we have

$$
(\pi(2^k) - \pi(2^{k-1})) > 0.71867 \frac{2^k}{k}\,,
$$

from which we can replace $(\pi(2^k) - \pi(2^{k-1}))^{-1}$ by $\frac{1}{0.71867 2^k / k}$ $=$ $1.39145 \cdot k \cdot 2^{-k}$ $=$ $2.00743 \cdot \ln(2) \cdot k \cdot 2^{-k} $.

The $\ln(2)$ term probably comes from the approximation $\pi(2^k) \approx \frac{2^k}{ \ln(2^k)} = \frac{2^k}{k \cdot \ln(2)}$, as in the proof of Proposition 2.


How many bits of entropy can I expect from /dev/urandom in iOS? Apple's latest security documentation indicates that it now uses CTR_DRBG for generating pseudo-random numbers (previously Yarrow instead of CTR_DRBG), using "timing variations during boot" and "interrupt timing once the device has booted" as seeds. Calls to the iOS API SecRandomCopyBytes will retrieve random bytes from /dev/random by default. Apple's random(4) man page seems to suggest that their /dev/random is non-blocking, but that it somehow does not need to block in order to ensure fresh entropic bytes:

  /dev/urandom is a compatibility nod to Linux. On Linux, /dev/urandom
  will produce lower quality output if the entropy pool drains, while
  /dev/random will prefer to block and wait for additional entropy to be
  collected.  With Yarrow, this choice and distinction is not necessary,
  and the two devices behave identically. You may use either.

NIST's DRBG validation list indicates that Apple is using AES-128 in counter mode as a pseudo-random function for CTR_DRBG.

So, how many bits of entropy can we expect out of SecRandomCopyBytes? If I query it for 256 bits of entropy, will I instead get 128 bits of reasonably entropic data, potentially followed by another 128 bits of less entropy data due to the lack of blocking in iOS's /dev/random?

I mailed Craig Federighi recently about this, concerned that macOS wasn’t capable of generating >128bit quality keys.

He responded!

  “The source you were referencing is out of date.  You can find more current informations here:   FIPS certification document, section 7: "The NDRNG feeds entropy from the pool into the DRBG on demand.  The NDRNG provides 256-bits of entropy.””


Problem understanding SHA-256 I'm reading this paper:  fips180-4-draft-aug2014

I'm on page 23 where they have two values for SHA-256: T1 and T2. While I understand the operations done, I don't understand the bigger picture. Why do we need T1 and T2 in this case? What do the values T1 and T2 represent?

The paper defines it as "T Temporary w-bit word used in the hash computation." But why go through so many shifts and other operations?

It is in the part of the internal block cipher of SHA2 that has 64 or 80 rounds depending on the mode, SHA256 has 64, SHA512 has 80 rounds.

  Why do we need T1 and T2 in this case?

Except the $T_1$ and $T_2$, everything is linear. In the picture, they are the blue and red word additions ($\color{red}{\boxplus}$). Being only linear is not a good idea in Cryptography. It is easy to attack since one can setup linear equations and solve by Gaussian Elimination. Nonlinearity is necessary but not sufficient. It uses the confusion and diffusion paradigm with many rounds where the key of the block cipher is the message.

  What do the values T1 and T2 represent?

Values changes according to inputs but the function definitions are fixed.

  But why go through so many shifts and other operations?

You can consider the shift operations as the diffusion part of the design, in order to affect each output bits with many key bits and many input bits in lesser rounds.

Of course, all of these above cannot claim that SHA256 is secure. It is designed to be secure with the previous knowledge about hash designs. Yet, SHA2 is not broken even theoretically i.e. even one bit less than the classic generic attacks

pre-image attack that has $\mathcal{O}(2^{256})$
second pre-image attack $\mathcal{O}(2^{256})$
collision attack  $\mathcal{O}(2^{128})$ due to the generic birthday attack.

Best known attacks are on the reduced rounds like preimage attack for 42 of 64 rounds with a $2^{248.4}$ complexity.

Even it is theoretically broken, it might not have a practical effect. For example, a full round pre-image attack with $2^{200}$ cannot be used in practice.

The previous hash of NIST SHA-1 is broken and the first forge is generated, see list of attacks on SHA-1. For SHA-2, the time will show. As said Attacks always get better; they never get worse.


Why do we use multiple rounds of encryption? I understand that DES and AES use multiple rounds of encryption to secure the cipher text output, what is the real reason this is carried out?

Is there a certain point performing multiple rounds becomes pointless not relating to security; as of course performance becomes an issue at some point?

Do all encryption algorithms require multiple rounds in order to make them secure?

Using the same scheme multiple times will allow for efficient crypto-analysis. If the cipher cannot be analysed then this will be considered detrimental to security. The cipher itself doesn't need to be hard; it just must be hard to reverse without the key. The rounds themselves do not provide enough confusion to be considered a full cipher themselves.

Having rounds where the same scheme is repeated allows for efficient implementation, making the code size much smaller and easier to protect against side channel attacks.

Yes, the required number of rounds can be limited to the best attack available. Generally any cipher with rounds will have successful (if theoretical) attacks over a number of rounds. The problem is that you don't know which attacks will be devised in the future.

So in the end some kind of margin is in order; there is a non-trivial balance between future proofing an algorithm and performance. To what number of rounds an algorithm is tweaked is often subject to discussion.

Having at least 3 "spare rounds" is probably advised. That doesn't take into account the complexity of each round (Threefish is used with 80 lightweight rounds while AES uses a minimum of 10, more complex rounds). You'd expect more "spare rounds" when a lot of rounds are required in the first place.

Generally block ciphers will use rounds, but stream ciphers may use different ways of generating a key stream. Asymmetric encryption such as RSA generally doesn't use rounds at all.

It's certainly not a theoretical security requirement to use rounds.


Crypto++: How to re-generate pseudo random integers in Crypto++ I'm using Crypto++ to implement my protocol to mask a value $y_i$ by a pseudo-random value $r_i$ such that $m_i=y_i \cdot r_i$. Since there are many $r_i$'s I want to generate them using PRNG and then only store the seed for the PRNG. With the seed any I can regenerate $r_i$, then compute $r^{-1}_i$ to remove $r_i$'s. But in crypto++ the seed (key) cannot be accessible.

So my question is: how can I use PRNG of crypto++ to accommodate the above technique?

Let $r_i  \stackrel{R} \leftarrow \mathbb{Z}_p$ and $y_i \in \mathbb{Z}_p$, where p is a prime number.

Formally, what you're really looking for is a key derivation function (KDF).

The Crypto++ API includes a PasswordBasedKeyDerivationFunction class, but that doesn't really seem optimal for your purposes; since you already have a high-entropy random seed, what you really want is a simple key-based KDF, not a fancy key-stretching KDF meant for use with passwords.

Fortunately, it's not hard to implement one yourself.  A very simple approach would be to use your "seed" as the key for a stream cipher (or to, say, AES in CTR mode), and use the keystream (which you can obtain by encrypting a bunch of null bytes) as your source of random bytes.

(You can then convert these random bytes into uniform random integers in your desired range e.g. by rejection sampling: to generate a random number between $0$ and $m$ inclusive, first find $k = \lceil\log_2m\rceil$, i.e. the length of $m$ in bits, then generate a random $k$-bit string.  If this bitstring, interpreted as a binary number, is less than or equal to $m$, you're done; else, toss it out and repeat.  It's not hard to prove that, on average, you'll end up rejecting less than half of all bitstrings (since $m \ge \frac12 2^k$).  Note, however, that this does potentially leak some statistical timing information about the most significant bits of $m$, which might matter if you want to keep it secret.)

Alternatively, with only slightly more work, you can implement a standard construction like HKDF (RFC 5869), or one of the DRBG algorithms from NIST SP 800-90A (note: do not implement Dual_EC_DRBG!).  CTR_DRBG, in particular, is very similar to the simple "use seed as key to AES-CTR, take keystream" suggestion above.


An example of of an information theoretically secure protocol that is not cryptographically secure Does there exist a protocol $\pi$ for some functionality $F$ which is information theoretically secure protocol that is not cryptographically secure for some threshold number of corrupt parties? Intuitively, such a protocol cannot exist, because if a protocol is not secure in the presence of a poly time adversary, then it must be insecure even in the presence of an adversary with unbounded computational power. However, I have constructed a protocol $\pi$ for a functionality $F$, which seems to be information theoretically secure protocol but not cryptographically secure.

Consider three parties $P_1, P_2,P_3$ with private inputs $p,q$ and $\phi$ respectively, where $p$ and $q$ are prime numbers. They wish to compute the functionality $F(p,q,\phi) = (\phi,\phi,p*q)$ i.e. party $P_3$ must receive the product of the two prime numbers as the output.

I design the following protocol to achieve the functionality: Party $P_1$ sends $p$ to party $P_3$ and party $P_2$ sends $q$ to party $P_3$. Party $P_3$ computes the product $p*q$.

The view of party $P_3$ in this protocol is $(p,q,p*q)$, where as its view is only (p*q) in an ideal implementation of the functionality $F$. Let consider the case where $P_3$ is an adversary (with no coalitions). If $P_3$ has unbounded computational power, then the two views are equivalent, and hence the protocol is information theoretically secure. Whereas, if the adversary can run only efficient algorithms (polynomial time algorithms), then the view of out protocol $\pi$ given more information that the ideal implementation of $F$, assuming factoring to be a hard problem.

My doubts are the following:

(1) Am I right to conclude that the protocol $\pi$ described above is information theoretically secure but not computationally secure, in the presence of one corrupt party.

(2) Does the simulator $S$ designed for showing the equivalence of an ideal implementation and a proposed implementation always need to be efficient? Is it dependent on the adversary's computational capabilities?

In order for information-theoretic security to imply computational security, you need to require that the simulator run in time that is polynomial in the running time of the real adversary. This is the standard definition, specifically to avoid protocols such as you presented in your question.

So, the answer is:

If you allow the simulator to be unbounded in running time (and irrespective of the running time of the real adversary) then information-theoretic security does not necessarily imply computational security.
If you restrict the simulator as I described, then information-theoretic security does imply computational security.

In my opinion, it makes no sense to allow the simulator to be unbounded if the real world party is (and this is the case in the real world). Therefore, I strongly argue that you must restrict the simulator as described.


What are the fastest attacks on ECDLP? Consider the ECDSA protocol, which is applied in different environments e.g. the Bitcoin system (for user addresses, and transaction signing).

What are the greatest threats in terms of algorithms that could solve the underlying discrete log problem for groups over elliptic curves? I found:

General Number Field Sieve
Pohlig-Hellman
Baby-Step-Giant-Step
Pollard's Rho

(excluding quantum algorithms)

to be the most efficient. Are all of them able to solve the ECDLP and if so, what is their complexity (runtime)?

If you wanted to compute secp256k1 discrete logs, you would use Pollard's rho, except of course the cost is far beyond your budget so it won't do you any good anyway.

The number field sieve is applicable to finite fields and to elliptic curves that admit embeddings into relatively small finite fields.  Such elliptic curves are called pairing-friendly, and are not normally used for ordinary ECDH key agreement or ECDSA or EdDSA signatures like Bitcoin—secp256k1, for instance, does not admit such an embedding, so the NFS is inapplicable.
Pohlig–Hellman is used for groups of composite order: it speeds up the computation by doing it separately modulo each factor; you can then reassemble an answer with the Chinese remainder theorem.  Although some elliptic curve groups used for discrete-log-type key agreement or signatures like edwards25519 have composite order, they typically have one large >250-bit prime factor and a very small cofactor like 4 or 8.  Secp256k1 has prime order, so Pohlig–Hellman is inapplicable.
BSGS and Pollard's rho both cost $O(\sqrt n)$ operations where $n$ is the order of the group, typically a >250-bit integer as in edwards25519, secp256k1, nistp256, etc.  However, BSGS also has $O(\sqrt n)$ memory cost, so the area*time cost—which is a proxy for euro or joule cost—is $O(n)$ even if we unrealistically assume $O(1)$ random access to memory.  In contrast, Pollard's rho costs $O(\sqrt n)$ time on a machine of constant space and thus $O(\sqrt n)$ area*time.  Pollard's rho can also be naturally parallelized to trade space for time without increasing the overall cost.  There are also some small optimizations that apply to Pollard's rho for elliptic curves, but they only change the constant factors a little; it remains $O(\sqrt n)$.
If you knew the secret scalar were in a restricted range $[a,b]$, you could use Pollard's kangaroo, which costs $O(\sqrt{b - a})$ time on a machine of constant size.  The kangaroo method too can be parallelized without increasing overall cost.  If, say, $b - a \approx 2^{100}$ for your secp256k1 target, then this would be within reach for you while none of the above methods would be feasible.  But it would be surprising for anyone to choose a scalar restricted enough that Pollard's kangaroo finds it substantially faster than rho.


Universal hash functions with homomorphic XOR property Let $H = \{h_r : U \rightarrow [m]\}$. What are the currently known most efficient algorithms such that $H$

is a universal family and
fulfils the homomorphic XOR operation property $\forall h \in H \forall x,y \in U: h(x \oplus y) = h(x) \oplus h(y)$?

I believe that the internal GHASH function from GCM would meet that criteria (if you trim off the length word, and require universality only with equal length inputs [1]); it can be defined as:

$$\operatorname{GHASH}_k( M_n, M_{n-1}, …, M_0 ) = \sum k^i M_i$$

With the input $M_n, M_{n-1}, ..., M_0$ being the input message divided into 128 bit blocks, $k$ being the universal hash key, and the arithmetic (both the additions and the multiplications) done over the field $\operatorname{GF}(2^{128})$

It meets the criteria:

It is universal (for equal length messages); for random $k$ and any two distinct equal length messages $M, M'$, we have $\operatorname{GHASH}_k(M) = \operatorname{GHASH}_k(M')$ with probability $\le |M| / 2^{128}$
It meets your homomophic requirement; this is because addition in $\operatorname{GF}(2^{128})$ is exclusive-or, and we have $k^i M_i \oplus k^i M'_i = k^i( M_i \oplus M'_i)$
It is quite efficient (especially with AES-NI instructions); I can't say that it's the most efficient possible...

[1]: You cannot get both the homomorphic properties and the universality (across messages of different lengths) to hold simultaneously.  The homomorphic property requires that $h_k(0) = 0$ and that $h_k(00) = 0$, hence we have two different messages $0$ and $00$ which hash to the same value with high probability (actually, 1), thus $h_k$ is not a universal hash family.


How is multiplication in field $GF(2^{8})$ done? I am working on AES and I am stuck on multiplication in $GF(2^{8})$ field.

In terms of polynomial it is easy; I just have to multiply polynomials modulo $(x^{8} + x^{4} + x^{3} + x + 1)$. But I do not understand multiplication with $x$, following an example given in NIST specification:

  {57} • {13} = {fe}

solution:

  {57} • {02} = xtime({57}) = {ae}
  {57} • {04} = xtime({ae}) = {47}
  {57} • {08} = xtime({47}) = {8e}
  {57} • {10} = xtime({8e}) = {07},

thus

  {57} • {13} = {57} • ({01} $XOR$ {02} $XOR$ {10})
   = {57} $XOR$ {ae} $XOR$ {07}
  = {fe}

I am unable to understand a single step in this, please also explain the x_time() function too.

Also, how is $x^{i}$ calculated? I need this for the $rcon[i]$ matrix.

Edit: this question has been marked as a possible duplicate of Understanding multiplication in the AES specification. I have already read this but the explanation is not sufficient, I am unable to understand the concept hence I have posted this question, because I need a somewhat detailed answer.Thanks.

Consider we want to obtain $\mathtt{0x57} \cdot \mathtt{0x02}$. First we see this one by polynomial method
$$
\begin{array}{lcl}\tag{3}
\mathtt{0x57} \cdot \mathtt{0x02}&=&(01010111)_2 \cdot (00000010)_2\\
&=&({x}^{6}+{x}^{4}+{x}^{2}+x+1)\cdot x\\
&=&{x}^{7}+{x}^{5}+{x}^{3}+x^2+x \\
&=& (10101110)_2\\
&=& \mathtt{0xAE}
\end{array}
$$
The relation $(3)$ means that when an element of $\alpha \in\operatorname{GF}(2^8)$ multiplied by an element $\mathtt{0x02}$ we shift the binary mode of $\alpha$ in the left side.

Now, if the first bit (from left) of $\alpha$ is  $1$ we should $\operatorname{XOR}$ the results with $\mathtt{0x1B}= (00011011)_2$ since when the first bit is  $1$, it means we have $x^7$ in the representation of $\alpha$ and by multiplying by $x$ we get $x^8$ and we use the polynomial $x^4+x^3+x+1$ instead of $x^8$ in our calculation.

We call this operation x_time(). For instance, let we want to get $\mathtt{0x57} \cdot \mathtt{0x04}$. The element $\mathtt{0x04}=(00000100)_2$ is equal to $x^2$. Therefor to obtain $\mathtt{0x57} \cdot \mathtt{0x04}$ we use the function x_time() two times. In $(3)$ we got $\mathtt{0x57} \cdot \mathtt{0x02}=\mathtt{0xAE}$.

In the rest, to obtain $\mathtt{0xAE} \cdot \mathtt{0x02}$, first we shift the binary mode of $\mathtt{0xAE}=(10101110)_2$ in the left side that implying that $$
(10101110)_2 \stackrel{shift\, to\, left}{\Longrightarrow} (01011100)_2 \tag{4}
$$
The first bit of $\mathtt{0xAE}=(10101110)_2$ is $1$ and hence we $\operatorname{XOR}$ the result obtained in $(4)$, with $(00011011)_2$ as follows
$$
 (01011100)_2 \quad \operatorname{XOR}\quad (00011011)_2=(01000111)_2=71=\mathtt{0x47}
$$
I suggest you to obtain other cases as an exercise.


RSA Signature : Process of Sign the message and Verify I have read that the RSA numeric signature works as the following:

Generation of keys : $p,q,N,e,d$
Process of signing the message $m$ (which is BigInteger) : it uses the secret key $sk=(p,q,d)$ so that $s=m^d\bmod N$ where $N=p*q$.
Why do we use the secret key to sign the message?
How I can hash the message ?
Process of verification that uses the public key $pk=(N,e)$ and a couple (message $m$, potential signature $s$), and consists in:  verifying whether the signature is valid (return true) or not (return false).

Can I get more information and explanation here in the verifying process? (I have read somewhere they use encrypt method and others use decrypt method).

We do use the secret key to sign the message as otherwise anybody would be able to sign messages (in your name!)
You can hash a message by passing it to cryptographically secure hash function, like SHA-2/3 and interpret the resulting digest as integer $m$.

The verification (of plain RSA, please note: RSA is never deployed like this) of RSA-signatures works as follows:

Obtain the message $M$ and the signature $s$ and the public key $(N,e)$
Hash the message $M$ to get the "numerical" message $m=h(M)$.
Compute $m'=s^e \bmod N$.
Accept the signature (= return true) if and only if $m=m'$, otherwise reject the signature (= return false)

The third step is the plain RSA-encryption, hence it is sometimes referred to as "encryption".
The signing equation you cited above corresponds to the decryption operation of RSA public key encryption, therefore to ease understandability for beginners it is often described as "encryption using the private key" or as "decryption".


Can we associate HMAC signed messages with each other? Assume:

$hmac(K, m) = M$
$hmac(K, m') = M'$

Can we associate that $M$ and $M'$ were signed by the same $K$?

Given $M$ and $M'$ and that we know they were signed with the same $K$, can we calculate the string similarity between $m$ and $m'$?

Edit: I originally asked the wrong question. The original question is known as a distinguishing attack and this paper (among many others) demonstrate it's possible.

To answer the new question, Mihir Bellare has proved that HMAC, applied to a Merkle–Damgård hash function such as the SHA-2 family, is a "privacy-preserving MAC" (PP-MAC) if the compression function of the underlying hash function is itself a PP-MAC.

Basically, the "privacy preserving" property means that even an attacker who gets to choose two equally long sequences of multiple (unique) messages, and submit them to an oracle who picks one of the sequences and returns the MACs of those messages (computed with a random secret MAC key) cannot tell with a non-negligible advantage which sequence the oracle picked.  (The actual PP-MAC game in the HMAC paper even allows the attacker to submit the messages to the oracle one pair at a time, and possibly adjust their later choices based on the returned information.)

As far as I know, no attacks have been published on any widely used reputable* M-D type hash functions that would contradict the assumption that their compression function is a PP-MAC.  This includes the SHA-2 family, as well as the obsolete SHA-1, and even the really obsolete and broken MD5 hash.  (Indeed, the collision attacks on MD5, which violated the assumptions of the old HMAC-MD5 security proof, were the original motivation for this new proof.)

As for SHA-3 (Keccak), it's not actually a Merkle–Damgård hash, so the standard HMAC security proof does not directly apply to it.  However, I do believe that the original Keccak paper itself asserts the PRF (and thus PP-MAC) security of HMAC-SHA3, as a corollary of its "flat sponge claim".

*) To some extent, this is a circular claim, since any hash function whose compression function was demonstrably not a PP-MAC would almost certainly be viewed with plenty of justified suspicion, even if this somehow failed to affect its collision or preimage attack resistance.


how to obtain the plaintext in counter mode using the AES block cipher I want to obtain the plaintexts.

Sentence1

9d567b9ae76c8a1c72c9075e28d3537a8325bed6043620216c5d796fa65ef24d46a059
9b0c337e9f32465dae103cdb852cddc2e49ab525e923bf364e5c7602f31ee40805ef36
5340e83ef1ee2220fadb2d58ac6e8cf3d0348c34b7a48887a85d8a864bcd5f4ff5b3dc
0b33ada6b92c069f

Sentence2

8c507dc8ce4fb7556bc1554124c54029c420b8d71c36202177547f6ba00bf34356a00a
d2067c65d026444ee20f2a979930c0d1e488b422ff2ffa3b45427018f35bb34739bb72
4b01f571e0af2538bd9e7f50eb608aa9

They were encrypted with the same nonce and key in the counter mode using the AES block cipher. The plaintexts are English sentences.

I guess the first word is 'the' in sentence2.
When I found the 'Enc' in the sentence2. I thought the first word of sentence2 is 'Encrypted'.

I know that the keystream is combined the nonce and the counter value in the Counter Mode.
But, I don't know what should I do after this.

I can't guess the word anymore. How can I know the nonce and obtain full plaintexts??

Any help will be really helpful to me!! Thank you!

You can't obtain the nonce without having the key which was used for the block cipher.

For CTR mode the ciphertext is $c = m \oplus s$ where $m$ is the message and $s$ is the keystream (which is derived from the key $k$, a nonce and a counter, but this is a minor detail, important is, that re-using the nonce results in the same keystream).

Take two messages $m_1$ and $m_2$ and their corresponding ciphertexts $c_1$ and $c_2$. If we XOR those ciphertexts we get: $c_1 \oplus c_2 = m_1 \oplus s \oplus m_2 \oplus s = m_1 \oplus m_2 \oplus s \oplus s = \mathrm{???}$. Just apply the rules of XOR and you will see, what you get.

Our exercise sheet you are trying to solve, provided another hint: XORing a " " (space) with a letter (in ASCII) flips between lower- and uppercase, e.g. $\mathrm{‘a\verb!’!} \oplus \mathrm{‘\;\verb!’!} = \mathrm{‘A\verb!’!}$. If you XOR two plaintext messages in a character position, where one plaintext message has a space, what can you tell about the other message if you see a letter in uppercase or lowercase?

Now, you might ask yourself: How do I figure out, which of the two plaintexts contains the space? Use the other ciphertexts (there are 11 of them on the task sheet with the same nonce!). What will most of them tell you, if you XOR them with a ciphertext, you presume to have a space at position $i$?

Looking forward to see your solution tomorrow!

Your friendly teaching assistant

PS: You can ask on our Mattermost chat too ;-)


Proving a user's identity after the user has forgotten his private key and password First some background. I am building an application where people send each other emails with messages inside that need their sign-off. Once the participants receive the email they're also given a callback link (the link is generated by cc-ing an email address tied to our app server, and then the app sever sends all the participants an email back with a link). Users click on that link, gets taken to a site, where the site's frontend generates a pair of keys locally inside the browser's localstroage, and the user can either say yes or no to the message, while signing his response + message with the key. We then store the signatures, should there be disputes later on they can search and find who agreed / disagreed to what when.

We've accounted for when the user flushes the browser or the browser flushes itself. The secret key is encrypted with the user's password and stored on the server (like protonmail), so if the user still remembers the password the secret key can be recovered locally in the browser.

But the problem is that I would expect most people won't be using this on a regular basis, so they will likely forget the password or that this site even exists in the first place. This means that their signatures are essentially worthless since there's nothing tying those signatures to these user's identity if they forget and resets their password and gets a new key pair.

One bit of information I do know is the user's email address. When they click on the link to agree / reject the message I right away know they are the owner of a particular email address. Let's assume for a minute that they're not likely to lose access to the email. With that assumption, is there some way I can tie a signature to a user's identity, even after that user has lost the private key (he 99% isn't even aware what a key is or that he has one) and lost his password to our site? To prove that, "Yes, that was you and only you who signed this message 1 year ago". Somehow tie the user's ability to access a particular email address to a signature?

The reason to use signatures is that it is not fakeable. If we only used regular logins then an argument can be made that the app server can just make up whatever it wants. But now we're saddled with a new problem which is how to reliably tie that signature to a user's identity.

Any help / ideas would be greatly appreciated!!

The easiest way to manage this sort of situation is to send people an email confirming that they signed a document.  This is akin to the standard password reset pattern of "if this was not you, please notify us immediately."

If you try to make it stronger, you run into the issue that the server is the only party here that is verifying identity.  It is the entity that is saying "this signature came from someone who can read XYZ's email address."  If the server cannot be trusted, then there is no trustable entity verifying anything.  And, given your situation, its unlikely the users themselves are adding any verification into the system.

One other tool you can use to build up trust is to use a blockchain like approach for the records.  When people sign contracts, they also sign the chain of contracts.  That would make it much harder to forge a single signature from years ago without invalidating every other signature in that time.  You could also require the users to review recent signatures, building more belief into the blockchain.

But in general, if you're not going to take the time to build in a full identification system (which involves an in-person meeting), then the strength of your system is built on its auditing, not in its initial signing algorithm.


Uniqueness of representation of $y$ to the bases $g$ and $h$ Let $G$ be a cyclic group of order $n$, with $n$ an RSA modulus.
Let $g$ be a random element generating $G$, and $h$ another element which discrete logarithm to the base $g$ is unknown.

Given an element $y \in G$, a representation of $y$ to the bases $g$ and $h$ is a pair $(x_1, x_2)$ such that

$$y = g^{x_1} h^{x_2}.$$

This definition can of course be extended to tuples of arbitrary length, but I am mostly concerned with the case of two bases. This concept is useful, e.g., in the proof/signature of knowledge of representation.

My question is: is such a representation unique?

That is, is there a pair $(x_1', x_2') \neq (x_1, x_2) : y = g^{x_1'} h^{x_2'}$ ? Why/why not?

This representation is not unique. If $k$ is the discrete logarithm of $h$ with relation to base $g$, then $$y = g^{x_1}h^{x_2} = g^{x_1}(g^{k})^{x_2} = g^{x_1 + k \cdot x_2}$$

Then for any $m$, $$x_1' = x_1 + m \cdot k,$$ $$x_2' = x_2-m$$ is another pair such that $y=g^{x_1}h^{x_2}=g^{x_1'}h^{x_2'}$.

We can reduce the discrete logarithm problem to finding a second pair $x_1', x_2'$. Given a second pair, we can efficiently compute:

$$ m \equiv x_2 - x_2' \mod n$$
$$ k \equiv (x_1' - x_1) \cdot m^{-1} \mod n$$
$$ k \equiv (x_1' - x_1)(x_2 - x_2')^{-1} \mod n$$

So finding a second pair is at least as hard as solving the discrete logarithm problem.


Definition of cryptographic advantage vs. probability of success In game-based security definitions, like for example the one defining IND-CPA security, a given cryptosystem is said to be secure if any probabilistic polynomial time adversary has only a negligible advantage of winning the game, where the advantage is defined to be

$|Pr[b^{\prime}=b] - \frac{1}{2}|$,

being $b$ the attacker guess, and $b^{\prime}$ the challenger flipped coin.

However, sometimes I run into papers, like for example this one, where they write something like this (see page 30):

$Adv^{CPA}(B) \geq \frac{1}{2} Adv^{CCA1}(A)-Adv^P(A).$

Clearly, they seem to be treating the adversary advantage as if it was just a probability, and not as the advantage that follows from the definition I just wrote (and it's also given at the beginning of the paper). Is it correct to mix the terms of advantage and probability in this way? Can you just divide the advantage by $2$, like if it was a probability?

I just mentioned this paper as an example, but I have found many others where the same thing seems to be happening.

Advantage and success probability are just words. Their meaning is in practice decided by how the speakers of the language use the words. You have observed that people use the terms advantage and probability in this way. One could probably argue that this is confusing or illogical or something like that, but such is language.

About dividing by two: remember, the advantage is just a number, and numbers can be divided by two and compared to other numbers. Sometimes, we are able to prove that one number is larger than the difference of two other numbers.

(As for the equation you mention, I think two terms are "advantages" and one term is a "probability".)