In what aspects is the function based on four iterations of SHA-256 compression function weaker than the SHA-512 compression function? Let $F_{512}(B, C)$ denote the underlying function (single block manipulation function) of SHA-256. This function takes a 512-bit block $B$, 256-bit initialization vector $C$ and produces 256 pseudo-random bits (eight 32-bit words). Then I can define the following function (that operates on a 1024-bit block $B$ given a 512-bit initialization vector $C$ and outputs 512 pseudo-random bits):

$$G_{1024}(B, C) = (x_1 \oplus x_3) \mathbin\Vert (x_2 \oplus x_4),$$

where $$\begin{array}{l}
{x_1} = F_{512}({B_1}, {C_1}),\\
{x_2} = F_{512}({x_1} \oplus {B_2}, {C_2}),\\
{x_3} = F_{512}({x_2} \oplus {B_1}, {C_1}),\\
{x_4} = F_{512}({x_3} \oplus {B_2}, {C_2}),
\end{array}$$

$B_i$ denotes the first/second half of the 1024-bit block and $C_i$ denotes the first/second half of the 512-bit initialization vector.

Let $F_{1024}(B, C)$ denote the underlying function (single block manipulation function) of SHA-512. This function takes a 1024-bit block $B$, 512-bit initialization vector $C$ and produces 512 pseudo-random bits (eight 64-bit words).

Yes, $G_{1024}$ may be slower than $F_{1024}$, but is $G_{1024}$ weaker than $F_{1024}$ from the cryptographic point of view? If yes, in what aspects?

EDIT

I think that xoring the 256-bit $x_k$ with the 512-bit $B_i$ was a mistake, but I can also define the following function (that operates on a 1024-bit block $B$ given a 512-bit initialization vector $C$ and outputs 512 pseudo-random bits):

$$H_{1024}(B, C) = (x_1 \oplus x_3) \mathbin\Vert (x_2 \oplus x_4),$$

where $$\begin{array}{l}
{x_1} = F_{512}({B_1}, {C_1}),\\
{x_2} = F_{512}({B_2}, {C_2}),\\
{x_3} = F_{512}((x_1 \mathbin\Vert x_2) \oplus {B_1}, {C_1}),\\
{x_4} = F_{512}((x_1 \mathbin\Vert x_2) \oplus {B_2}, {C_2}),
\end{array}$$

$B_i$ denotes the first/second half of the 1024-bit block and $C_i$ denotes the first/second half of the 512-bit initialization vector.

Similarly, $H_{1024}$ may be slower than $F_{1024}$, but is $H_{1024}$ weaker than $F_{1024}$ from the cryptographic point of view? If yes, in what aspects?

The original question did not have $C$, introduced to address otus's comment. The next section of the present answer was written with that in mind, or equivalently $C_1=C_2$ and the second input of functions removed; we'll get $C$ back in the final section.

Yes, $G_{1024}$ is weaker than $F_{1024}$ from a cryptographic point of view. For example, about $2^{257}$ evaluations of $F_{512}$ have a sizable chance to be enough to find a 512-bit value $B$ such that $G_{1024}(B)$ is the all-zero 512-bit bitstring, when doing so should require an expected $2^{512}$ evaluations of $G_{1024}$, that is about $2^{257}$ times more work.

To form such $B=B_1\mathbin\|B_2$, we use incremental 256-bit $B_1$, compute $x_1=F_{512}(B_1)$, compute $B_2=x_1\oplus B_1$, know without computation that $x_2=x_1$, compute $x_3=F_{512}(x_2\oplus B_1)=F_{512}(B_2)$, until it happens that $x_1=x_3$ or we have exhausted all 256-bit $B_1$. This gives non-negligible odds to find $B_1$ with $x_1=x_3$, in which case $x_2=x_4$, and thus $G_{1024}(B)$ is the all-zero 512-bit bitstring.

Back to the question as it stood in its second major revision, with $C_1$ and $C_2$, presumably distinct in the first round of the 512-bit hash.

In that first round, for random $B_1$ and $B_2$, $x_1\oplus x_3=x_2\oplus x_4$ has odds about $2^{-256}$, and the expected work to find such $B_1$ and $B_2$ is about ${3\over4}2^{258}$ evaluations of $F_{512}$. With such $B_1$ and $B_2$ as first block, in the next round of the 512-bit hash, the round function will have its 512-bit chaining input $C$ such that $C_1=C_2$, and we can carry the previous attack on the second round. If that attack fails, we now can retry by redoing the attack on the first round, with one full try costing on average about ${5\over4}2^{258}$ evaluations of $F_{512}$ . $2^{260}$ evaluations of $F_{512}$ can with good probability exhibit a 2048-bit input such that the 512-bit intermediary hash after two rounds of $G_{1024}$ is all-zero; that's $2^{254}$ times easier than it should.

We can attack the full 512-bit hash obtained from $G_{1024}$ with length-strengthening, and find a 239-octet input hashing to all-zero with an additional $2^{136}$ work factor (because the length-strengthening forces 17 octets in $B_2$ of the second round). This is a break of first-preimage resistance by a factor of $2^{118}$, albeit specialized to the all-zero result.

Sure, that's not devastating, and in particular does not break a 256-bit security claim. But attacks only get better; they never get worse.

The last system can be attacked as follows: chose an arbitrary first block, yielding fresh $C_1$ and $C_2$ for the second block. For each, try to find find $B_2$ yielding $x_2=0$ and ending with the 17-octet length-strengthening prescribed for a 239-octet hash input; if none of the $2^{120}$ such values of $B_2$ is fit, try another first block. If one is found, try to find $B_1$ yielding $x_1=0$; otherwise start over with another first block. That yields a 239-octet string hashing to all-zero per the full 512-bit hash with length-strengthening. The length-strengthening was less taxing than in the previous system, and the attack is a break of first-preimage resistance by a factor of like $2^{252}$ (albeit still specialized to the all-zero result).

Comment: modern crypto does not design its cryptosystems by trial and error until no error is found. We want at least a security argument, if possible a proof under some security model and plausible assumptions.


Avalanche noise RNG for one-time pad use I came across this little HRNG widget and was really intrigued as I have been looking for a decent but afordable source for truly random bits to use in a one-time pad.

The question is, would a HRNG like this one generate bits with sufficent randomness to provide the perfect secrecy one-time pads are known for? Such a design is of course slightly less random than a quantum RNG using decaying radioactive materials, but is the output random enough to be relied on?

If yes, would XORing the output bits with the plaintext be enough?

If this is a good HRNG (look for security reviews) I suppose yes. But it would be excruciatingly slow (HRNG's are not known to be fast, generally you use them to get 256-512 entropy bits to seed a PRNG and go with that) and you still have the key exchange + reuse OTP problem.

Note this tool apparently integrates itself with the Linux entropy pool, so I'm not sure you can actually access its raw output directly without it getting mixed with the rest. Perhaps there is an API for that. Using the Linux pool also means you will starve the system from entropy as your program eats it all to create a one-time pad... probably not a good idea :)

Remember you still need integrity checking.


How do I verify a reset token if the token is hashed in DB? I've been searching around the web for best practice how-to on secure password reset system (email with reset url), and the idea to hash the token in the database, which I did not implement at first, seems to be the the most secure way to store the token.

Im currently following this guide, and he does not mention it (why?)

Im using bcrypts for password hashing allready, so thats what im using for this aswell.

How ever, the syntac for the verify is like this: Bcrypt.verify(non-hash, hash);

So my question is this:  If the reset-link only contains the token (which is not in db, the hash is) - how can I find the user in the db?

is it safe to append email/userID to the reset-link as well? None of the other services Ive seen have does this (afaik), only the token (do they not hash the token in the db?).

I dont want to make my own scheme that will create a security issue, so how do I proceed with this ?

Using asp.net web forms and c#

I was pondering this as well and it was hard to find answers.

My solution: don't hash the token with bcrypt. Instead hash it with e.g. SHA256 with no salt. It will be secure enough if the token is truly random data and long enough.

Then the hash will always be the same, so you can easily find it in the database. No need to iterate over all users or tokens in the database – that would be madness.

Some resources to validate my solution:

How to store the access token / password reset token in the database?
Pre-generating 'secure tokens'
Should password reset tokens be hashed when stored in a database?


Encrypting text using Caeser cipher in CFB mode I am interested in learning and understanding cryptography and its application in every day life. One thing I can't seem to get my head around is encrypting plaintext using a block mode such as CFB. I want to use a Caesar block cipher in CFB mode to encrypt the following plaintext: lucozade with a key: 3.

So in this case, I get that using the Caeser block cipher the ciphertext for lucozade would be oxfrcdgh as the letters have shifted three places to the right. What I can't do is this encryption using CFB mode. How do I go about doing that? Like would I have to use the ciphertext oxfrcdgh as the IV?

Any help would be great

Caesar cipher

You are confusing Caesar cipher with block ciphers.

In Caesar cipher the ciphertext is calculated as

$$c_i = p_i + 3 \bmod 26$$

There is no security in Caesar Cipher. A ciphertext only attack possible, as worst scenario.

CFB Caesar cipher

$c_i = c_{i-1} + 3 + p_i \bmod 26 $, with $c_0 = IV$

And, the decryption;

$p_i = c_i - 3 -c_{i-1} \bmod 26 $, with $c_0 = IV$

Example : $P=lucozade = \{11,20,2,14,25,0,3,4\}$

Let choose $IV = f = 5$

\begin{align}
  c_1 &\equiv IV + 3 + p_1 \bmod 26 \equiv 5 + 3 + 11 \bmod 26 \equiv 19 \text { that is } T\\
  c_2 &\equiv c_1 + 3 + p_2 \bmod 26 \equiv 19 + 3 + 20 \bmod 26 \equiv 16 \text { that is } Q\\
  c_3 &\equiv c_2 + 3 + p_3 \bmod 26 \equiv 16 + 3 + 2 \bmod 26 \equiv 19 \text { that is } T\\
  c_4 &\equiv c_3 + 3 + p_4 \bmod 26 \equiv 19 + 3 + 14 \bmod 26 \equiv 10 \text { that is } K\\
\end{align}


Is using /dev/hwrng for raw key material secure? Is using /dev/hwrng for raw key material secure (as long as you trust the hardware)?
I tested it using the rngtest tool and it has good output.

Isn't that a contradiction in terms?
/dev/hwrng could be a  block device to anything at all.  If you trust the hardware, then yes. If you don't' trust the hardware, then no. The thing is that you can't tell. Nano scale technology has to be taken on trust. See Can any part of Intel's (RdRand) random number generator be visually inspected?

rngtest

Irrelevant. The Mersenne Twister is a pseudo random number generator. And it will ace most randomness tests. Yet it's deterministic depending on the seed, and can be inverted by only looking at 624 outputs. You could simply reseed it with every restart and it will look really random. Like seeding with the time. Yet it will offer no cryptographic security. Prove that your hardware if not just:-
$$ \text{E}_{k  \oplus  id} (x) $$
where k = some shadowy agency’s key, id = a device identification/serial number and x is some counter and/or time. Perhaps using AES, or some other CSPRNG? Some form of NIST 800-90A HMAC_DRBG? It can’t be mathematically disproved by any analysis of the output data.
How can you confirm that what your generator is giving you is truly random? You can't. Last year's US intelligence budget was $60 billion. What did they spend it on?

Trumpet sounds! Build your own. It's relatively easy and the only way to have 100% certainty.


Create self signed certificate from modulus, private and public exponents of RSA I have the values of RSA public exponent $e$, the secret exponent $d$ and the modulus $n$.

How can I create (for example using openssl) a self-signed certificate using the RSA  key $(n,d), (n,e)$? Is it even possible?

Second question: Is it possible to get the factors of $n$ from $(n,d), (n,e)$?

Yes, it is possible to generate a self signed certificate. If you've got a private key that can sign with it using the required signature algorithm then that should always be possible. Tool usage (such as openssl, which can be used to generate self signed certificates) is off topic here, but basically you just create the To Be Signed (TBS) part of the certificate and then, well, you sign it.

Yes, you can get the factors from this answer which is about calculating the CRT parameters, but those include the $p$ and $q$ values.


AES ECB mode for both encryption and authentication Can AES ECB mode be used for both encryption and authentication, assuming the following conditions are always true?

Encryption of exactly 128-bit (1 block) size messages
Different keys used for both encryption and authentication
Authentication AES ECB uses encrypted ciphertext as input and outputs 128-bit MAC

[1] - For a single block, AES ECB is a secure MAC.

[2] - AES ECB encryption for a single block suffers from one of the problems that AES ECB suffers from in general, namely that it is deterministic. The same message encrypted with the same key results in the same ciphertext. How big of an issue is that for your application? Only you can answer that at the moment because we don't have the details of the application.

[1] - https://crypto.stackexchange.com/a/18947/706
[2] - https://crypto.stackexchange.com/a/8053/706


Post-Quantum security of Pseudo-Random Functions I am wondering what is the exact post-quantum security of a PRF. I know that for most symmetric mechanisms, it is assumed it is sufficient to double the key size, but I am looking for a more precise analysis in the case of Pseudo-Random Functions (like $2^{(n/2)}$ operations with Grover algorithm for the preimage).

To clarify, I am searching for (1) generic attacks (not on any specific PRF) (2) for an attacker that only has classical access to the PRF.

The best generic classical attack on a PRF is a generic preimage search for the unknown key.  Given an input $x$ and an output $f_k(x)$ for uniform random $k \in \{0,1\}^n$, the best known algorithm costs about $2^n$ trial evaluations of $f$ to find $k$.  Given multiple targets $(f_{k_1}(x), f_{k_2}(x), \dots, f_{k_t}(x))$, it costs about $2^n\!/t$ trial evaluations of $f$ to find at least one of the $k_i$, using a rainbow table search if it is done on a machine parallelized at least $t^2$ ways.

The best generic quantum preimage search costs about $\sqrt{2^n} = 2^{n/2}$ trial evaluations of quantum superpositions of $k \mapsto f_k(x)$, using Grover's algorithm.  Grover's algorithm doesn't parallelize well: if parallelized $p$ ways, it returns an answer in time $\sqrt{2^n\!/p} = 2^{n/2} / \sqrt p$ and therefore costs $2^{n/2} \cdot \sqrt p$ to run a machine $p$ times larger for $1/\!\sqrt p$ times as long.  In the single-target setting, Grover's algorithm is asymptotically optimal.  The best known batch advantage for a multi-target search (not known to be optimal but dramatic improvements seem unlikely) is modest, reducing the cost by a mere factor of $\sqrt[4]{t}$ to find the first of $t$ targets.

There is also a fantasy threat model where not only does the adversary have a quantum computer, but where you for some inexplicable reason compute quantum superpositions of $x \mapsto f_k(x)$ on behalf of the adversary.

While I don't know of any generic attacks, many particular cryptosystems are breakable using Simon's algorithm (random example) in this doubly unrealistic threat model where the adversary has a quantum computer, you have a quantum computer, I have a quantum computer, and everyone and their dog has a quantum computer, and you blithely compute secret functions on quantum superpositions of inputs on request from the adversary.

Solution: When strange men in dark coats ask you on the street for quantum superpositions of your secret functions, RUN AWAY!

More seriously, if you are tempted to evaluate secret functions on a quantum computer yourself, on behalf of anyone including puppies and unicorns and not just strange men in dark coats, take a moment to do a literature search to reconsider your life choices.


Looking for a secure PRNG that I can implement in hardware I'm trying to implement a (sort of) simple PRNG in hardware for fun. My idea would be to allow a user to enter a key using a keypad (or some dip switch settings that can be set and hidden) and to obtain a seed using photo, gyro and audio sensors feedback.

I understand I'll probably have to implement some form of modulo arithmetic in hardware. However, I thought up of a hardware-simple algorithm that would only need to use XOR gates. What are your opinions on it?

key = k bits taken from keypad entry
seed = k bits taken from environment sensors
while (true):
    seed << seed[3]             // rotate the seed if seed[3] is 1
    newSeed <- key XOR seed     // the new seed is XORed with the key
    output <- lsb(newSeed)      // output the lsb of the seed
    seed <- newSeed

It outputs the lsb of the newly calculated seed. I have no experience in algorithm design so I'm sure this is riddled with attacks. If the above is not sufficient for a PRNG, which should I use? Is there one which is known to be simpler for low-bit hardware?

First, you should not write your own CSPRNG - there are plenty of well vetted ones from which you may pick.

Second, your text and your pseudo code do not match (rotate key or rotate the seed).

Third, as I understand this algorithm it doesn't even give good randomness properties.  For example:

Main> let seed = `0x82398eeaf74239 : [64]
Main> let key =  `0x8732754279249  : [64]
Main> let out = take `{256} (prng key seed)
Main> out
0x5555555555555555555555555555555555555555555555555555555555555555


Does the Biclique attack on AES pose a credible risk to its security? I have heard a lot about the biclique cryptanalysis research on AES, which as far as I know is the closest anyone has got to breaking AES.

Exactly how close did they get? Does this attack propose a credible risk to my using AES today? Exactly how hard would it be to extend their work to fully break AES?

Simply put no.

As per the abstract, those attacks take at most 4 bits off the key space, this still results minimally in 124 bits of security. Put another way, to use these attacks you would need to expend effort roughly proportional to brute forcing an AES key where you already knew four bits of the key and this would take approximately $2^{124}$ operations.

For reference, the standard rule of thumb on security is it must provide about 80 bits currently. Of course, this is to be secure now and not 100 years from now and and something that provides 80 bites of security now could have those eroded later. However 124 is still more than enough of a safety margin.


Chosen-Message-Attack RSA-Signature I know that because of the multplicative property of RSA

$s =(s_1s_2) \bmod n = (m_1m_2)^d \bmod n$

If Oscar wants to sign now an own message $m$ he chooses another message $m_1$ with $\gcd(m_1,n)=1$ and he calculates $m_2 = m\cdot m_1^{-1} \bmod n$

After this part I don't understand the attack...

How is he able to sign now his own message $m$ ?

Suppose you want to obtain the signature $s = m^d \bmod n$ on a chosen message $m$.  Here is that attack.

You ask the signer to sign a random message $m_1$ and obtain the corresponding signature $s_1 = m_1^d \bmod n$;
You compute message $m_2 := m\cdot m_1^{-1} \bmod n$ and ask the signer to sign message $m_2$; you obtain the signature $s_2 = m_2^d \bmod n$.

From the pairs $(m_1,s_1)$ and $(m_2,s_2)$, the signature $s$ on chosen message $m$ can be recovered as $s = s_1 \cdot s_2 \bmod n$.

To see it, observe that $s \equiv s_1 \cdot s_2 \equiv m_1^d \cdot m_2^d \equiv m_1^d \cdot (m\cdot m_1^{-1})^d \equiv m_1^d \cdot m^d \cdot m_1^{-d} \equiv m^d \pmod n$.

Note that you could obtain the signature on message $m$ by only asking one signature to the signer.  Indeed, you can construct the pair $(m_1,s_1)$ in Step 1 above by yourself as follows: choose a random $s_1$ modulo $n$ and define $m_1 = s_1^e \bmod n$ (where $e$ is the public verification exponent).  We then have $m_1^d \equiv s_1 \pmod n$ as required.


Double randomised HMAC verification to prevent timing attack A way to prevent timing attacks for hash string comparison is to perform additional HMAC signing in order to randomize the verification process (see Double HMAC Verification).

In addition to the second HMAC hashing for each hash, a random salt of random length is added to both in order to make the hashing timing / process even less predictable.

My PHP implementation of this look like this:

function hmac_verify ($hash_original, $message, $key) {

    $hmac_salt = '...'; // was added at the original HMAC signing
    $random_salt = openssl_random_pseudo_bytes (rand(16,96));

    $raw_hash = hash_hmac('sha512', $message . $hmac_salt, $key, true);
    $hash_compare = base64_encode ($raw_hash); // $hash_original is in base64
    $hash_compare_safe = hash_hmac('sha512', $hash_compare, $random_salt, true);
    $hash_original_safe = hash_hmac('sha512', $hash_original, $random_salt, true);

    if ($hash_compare_safe === $hash_original_safe) return true;
        else return false;

}

The function is called in this way after decrypting the encrypted text in order to verify the decryption result:

if (!hmac_verify ($hmac_hash, $plaintext . $cipher_text, $key . $iv)) return "HASH ERROR";

Will this successfully prevent a timing attack? Am I doing anything unnecessary? Could something be improved?

Will this successfully prevent a timing attack?

Strictly speaking you should be checking if openssl_random_pseudo_bytes happens to be returning cryptographically strong numbers or not. If not, an attacker could guess be able to launch a timing attack practically as easily as without the extra HMAC.

(Got to love PHP... Even the function name: random "pseudo bytes"...)

You should also, if possible, HMAC the raw output rather than the base64. The base64 encoding function might itself even allow timing attacks (probably not but who knows), so you would be better off using the raw values. It is also faster.

  Am I doing anything unnecessary? Could something be improved?

The $random_salt is actually a key, so you should call it and treat it as such. You could reuse it across function calls, if you are after performance.

There is no advantage to generating a random-length key. You should be using a key size that matches the overall security strength you are aiming for, but e.g. 256 bits would be plenty.

The security of this relies on the security of HMAC. As long as the key is secret, no one will be able to learn anything about the original hash even if the final comparison leaked the value. And if the key is long enough it cannot be brute forced. Randomness does not help beyond generating a secure key.


Proof of Knowledge/Data Integrity using Hash Function Objective: A verifier wants to ensure that a block of data M is also known to a prover. The protocol should exchange little information and should not leak information about the value of M.

Proposed Protocol:
V -> P: challenge c
P -> V: response r = f(M, c)

Question:
What is a suitable and efficient function f?

What comes to mind first is to use a hash function, such as SHA2(c concatenate M), which may meet the objective. We could also compute SHA2(M xor c'), where c' is derived by repeating c as required to get to the length of M.

What concerns me is that SHA2(M concatenate c) will not meet the requirement. The prover could simply compute SHA2(M) partially up to the last full block of M, store the intermediate state of the hash function, and then delete the part of M that was already processed.
When confronted with a challenge c the prover can pick up the state where
it was left and finalize the computation without actually knowing M anymore.

Does anyone see such pitfalls with SHA2(c concatenate M) or SHA2(M xor c) or have other suggestions?

From your question, I believe that what you are looking for is a proof of storage. I will point you in the direction of one paper, and you can use that to look for other work on the topic.


How was 256-bit WEP cracked as well? WEP is now considered as insecure. But how about the 256-bit WEP?
Could someone explain why a 256-bit encryption isn't enough?

'A 256-bit WEP system is available from some vendors. As with the other WEP-variants 24 bits of that is for the IV, leaving 232 bits for actual protection. These 232 bits are typically entered as 58 hexadecimal characters. ((58 × 4 bits =) 232 bits) + 24 IV bits = 256-bit WEP key'

Yes.  256-bit WEP is insecure.  There are a broad range of attacks against WEP.  Most of them aren't affected by the key length.  Wikipedia has references to many attacks on WEP; for more, read those references.  Don't use WEP.  Go straight to WPA2.


Proof that perfect privacy implies that the number of keys is at least the number of messages I was reading a proof to the statement:

  Perfect privacy implies that $|K| = |M|$

where I am pretty sure that $K$ is the set of keys and $M$ is the set of messages.

The proof is the following, but I don't understand it (maybe because of the notation).

  Assume not, i.e., assume we have fewer keys than messages.
  Given a ciphertext $c$, there is a message $m$ and a key $k$ such that:

  $e(k, m) = c$, and $p_{k \in K}[e(k, m) = c] > 0$

  Let $P_c = \{ m \in M$ such that $e(k, m) = c$ for some $k \}$

  Since every $k$ maps exactly one message $m$ to $c$, and since we have fewer keys than messages, then there is an $m'$ not in $P_c$ such that no key $k$ maps $m'$ to $c$.

  Therefore $P_{k \in K}[e(k, m') = c] = 0$, which violates the perfect-secrecy condition that for all m and $m'$, $P_{k \in K}[e(k, m) = c] = P_{k \in K}[e_k(k, m'). = c]$.

where $k \in K$ means that $k$ is a key in the set $K$.

The first thing that I don't understand is the following notation: $p_{k \in K}[e(k, m) = c] > 0$. What exactly does this mean? Does $p$ refer to the probability?

I understood the following statement:

  Since every $k$ maps exactly one message $m$ to $c$

It makes sense that a function should just output one result for the same inputs.

  Therefore $P_{k \in K}[e(k, m') = c] = 0$

Does this mean that the probability that we encrypt $m'$ using $k$ results in the cipher $c$ is equal to $0$ because, as said before in the proof, $m'$ is a message that has no key $k$ that transforms it into $c$? If yes, I am still not 100% convinced.

  which violates the perfect-secrecy condition that for all m and $m'$, $P_{k \in K}[e(k, m) = c] = P_{k \in K}[e_k(k, m'). = c]$

If we assumed at the beginning that $p_{k \in K}[e(k, m) = c] > 0$, that the statement above makes also sense.

Again, I don't get the part of assuming $p_{k \in K}[e(k, m) = c] > 0$ (apart from the fact that I am not sure if $p$ should be $P$, i.e. if it is just a typo, and if $P$ (or $p$) refer to probabilities, as I was wondering above).

Moreover, I think the proof is not showing the case when the number of keys is greater than those of the messages.

Let $K$ be the set of all possible keys (for AES-256, this set has $2^{256}$ elements.)
Let $M$ be the set of all possible messages (for AES, it has $2^{128}$ elements).
Let $C$ be the set of all possible cipher texts (for AES, again $2^{128}$ elements).

I was reading a proof to the statement:

Perfect privacy implies that $|K|=|M|$

Actually this is $|K| \ge |M|$.
Perfect privacy condition is:
that for all $m$ and $m′$, $P_{k \in K}[e(k,m)=c]=P_{k \in K}[e(k,m′).=c]$
the probability that a cipher text $c$ is decrypted as $m$ is the same as being decrypted in $m'$.
Or in other words:
you can't find a difference between $m$ and $m'$.
In order to prove such statement you use reductio ad absurdum. Here you assume $|M| > |K|$.

The first thing that I don't understand is the following notation: $p_{k \in K}[e(k,m)=c]>0$. What exactly does this mean ?

Yes the $p$ is a typo and should be $P$. It means that there exists $k$ and $m$ such as $e(k,m)=c$ (which is trivial because we need a working algorithm...). Therefore the probability that given a $c$, $m$ is the plain text is at least $\frac{1}{|M|}$ (assuming a uniform distribution), hence $> 0$.
About this part:

Therefore $P_{k \in K}[e(k,m′)=c]=0$
Does this mean that the probability that we encrypt $m′$
using $k$ results in the cipher $c$ is equal to $0$ because, as said before in the proof, $m′$ is a message that has no key $k$ that transforms it into $c$? If yes, I am still not 100% convinced.

The first thing you must think of is that the $c$ is fixed. In order to encrypt a message $m$ to this $c$ you need a key $k$. Because $|M|$ is greater than $|K|$ (assume $|M| = 5$ and $|K| = 3$), there exists messages that won't have a mapping to $c$ (in this case $5 - 3 = 2$). Therefore there exists $m'$ such as there is no $k$ so that $e(k,m) = c$. Hence $P_{k \in K}[e(k,m′)=c]=0$
Because the statement of perfect secrecy is for all $m$ and $m'$ you can't have at the same time all probabilities being $> 0$ and $= 0$. Therefore you have a contradiction.


4th Root of RSA Modulus Attack algorithm I am trying to solve here a task but I have no clue on how to approach it. The last few days I tried to find a way but I have no clue :( Maybe someone of you could give me a hint on how to do it.

The following assumption is given: $p-q=O(\sqrt[4]{N})$

Using the given assumption I have to show that it is possible to retrieve $p$ and $q$ in time $\tilde{O}(1)=poly(logN)*1$.

The following hint is given: $N=pq=(\frac{p+q}{2})^2 - (\frac{p-q}{2})^2$, whereby I should first show that $\frac{p+q}{2}\ge\sqrt{N}$. For the proof I can assume that $p-q=2\sqrt{2}\sqrt[4]{N}$.

I am clueless. I tried first to show $\frac{p+q}{2}\ge\sqrt{N}$ but I am wondering on how to get the $\ge$. I tried to solve the hint with by replacing $p-q$ with $2\sqrt{2}\sqrt[4]{N}$ and try to get a solution. All I get is:

$N=pq=(\frac{p+q}{2})^2 - (\frac{p-q}{2})^2$

$N=pq=(\frac{p+q}{2})^2 - (\frac{2\sqrt{2}\sqrt[4]{N}}{2})^2$

$N=pq=(\frac{p+q}{2})^2 - 2\sqrt{N}$

I don't see how this could help me.
Thank you for every hint.

Thanks guys for the hints. Here is the first prove:

$0 \ge -(\frac{p-q}{2})^2$

$(\frac{p+q}{2})^2 \ge (\frac{p+q}{2})^2 - (\frac{p-q}{2})^2$

$ (\frac{p+q}{2})^2 \ge N$

$ \frac{p+q}{2} \ge \sqrt{N}$

It hope it's all correct and I did not mistype sth. I will see if I am able to figure out the next step :)

It hold that $0\ge-\left({p-q\over2}\right)^2$. We add $\left({p+q\over2}\right)^2$ on both sides and use $N=\left({p+q\over2}\right)^2-\left({p-q\over2}\right)^2$ (hinted, and easily established from $N=p\,q$ ). We get $\left({p+q\over2}\right)^2\ge N$. From that, by taking the square root of both sides (which we can do since the quantities are non-negative), we get $\frac{p+q}{2}\ge\sqrt{N}$, QED.

The fun part is after this warmup..

The general idea is to search for $s={p+q\over2}$, by searching integers $s$ incrementally starting from $s_0=\left\lceil\,\sqrt N\,\right\rceil$, until $s^2-N$ is the square of some integer $t$; that is $\exists t\in\mathbb N$ with $t^2=s^2-N$, or equivalently $\sqrt{s^2-N}$ is an integer.

Notice that ${p+q\over2}$ is an integer when $N$ is an odd composite, and we just proved ${p+q\over2}\ge\sqrt N$, thus ${p+q\over2}\ge s_0$, thus the above strategy insures $s$ will ultimately reach $p+q\over2$. When that happens, we'll have $t={p-q\over2}$, and we'll thus be able to get $p=s+t$ and $q=s-t$, leading to a factorization of $N$ (perhaps partial if $N$ has more than two factors).

Speed depends on:

How many $s$ there are to test, that is how high $s$ will get over $s_0$. With a little algebra, an upper bound can be found by assuming $p-q\le2\sqrt{2}\sqrt[4]{N}$, which is how I read one of the hints; or it can be directly found an asymptotic bound using the assumption $p-q=O(\sqrt[4]{N})$.
How fast we can determine that $s^2-N$ is not a square (or better, summarily skip a sizable fraction of candidates for $s$); for example, in base $10$, squares never have their rightmost digits among $\{2,3,7,8\}$ and that helps get rid of some $s$ without computing a square root. However, such tweaks (many are possible) are not necessary to get the desired asymptotic bound, with polynomial of unspecified order.

This is known as the Fermat factorization algorithm.


Multiple encryption of part of block Is there any security risk in encrypting parts of blocks twice? I'd like to get around block sizes and make encrypted messages just as long as the unencrypted ones:

Block 1: Byte 0 - 7
Block 2: Byte 8 - 15
Block 3: Byte 16 - 23
Block 4: Byte 21 - 29

In this example blocks 3 and 4 overlap by 2 bytes. I plan on using CAST-128.

Thank you very much for helping!

Florian

This technique is known as Ciphertext stealing. Ciphertext stealing avoids padding, but only works if the total message size is bigger than one block.

Ciphertext stealing secure in principle, but as @mikeazo already pointed out using ECB and using 64 bit block ciphers is generally a bad idea.
There are fancier length preserving encryption schemes. FFX mode is one example.
I strongly recommend adding a nonce/IV and a MAC. While these increase the size of the message, the security implications of not having them can be severe.

In particular the MAC prevents attacks that modify the ciphertext and watch the reaction of the decrypted and nonces/IVs ensure that encrypting the message twice doesn't leak that it's the same.


How confident can we be that nobody will crack a 128-bit key? In a context involving a block cipher like AES-128, excluding quantum computers, cryptanalytic breakthrough on AES and implementation attacks (poor TRNG, DPA..), and wrench, how confident can we be that by key search, "nobody will crack a 128-bit key" until 2100. Assume business as usual for humanity, use of 1 year worth of global production of electricity, 1 year worth of industrial production for the gear (used over a multi-year period).

Full disclosure: I'm trying to challenge my own half-baked opinion.

Updated: I leave it open if we allow multi-target attacks, where the same known plaintext is available enciphered under many random 128-bit keys. That makes a huge difference, but specifics of the block cipher become less important, which is good.

Note: we have a related question there; but it was considering a 256-bit key size, the methods adequate for that size need not be precise, and have not led to a definitive or even clear conclusion on 128-bit; plus answers are nearly 6 years old, and much more SHA-256 have been performed since then than I would have predicted at the time.

Note: We have another related question there at the 128-bit key level, but it restricts to currently available technology. Here, we must account for foreseeable technology more plausible than quantum computers usable for that cryptanalysis.

Note: 2100 and other limits have been set (instead of the original in the future of humanity as a species) for the sake of making a quantitative answer more falsifiable. Say, global apocalypse on that March 1 because a military subcontractor goofed on the leap year rule.

This question seems to be asking us how fast will computers grow. No cryptanalytic breakthrough and no quantum computing essentially means no attack faster than brute force.

So will humanity at some point in the future with significant resources be able to brute force 128 bit key?
I would answer, maybe. 256 bit key Almost definetly not.

Obviously predicting is hard especially the future but assuming humanity will not self destruct it will continue to progress and it is not unreasonable to assume it will come close to the limits of what is possible.

The main discussion on theoretical limits of brute force is in minim energy requirements. I suspect we may be short on physicists on crypto stack exchange so I will try.

Brute forcing a key requires enumerating the keys. And that requires changing bits. Each bit change erases some information and there is a minimal amount of energy required for that. Lauder's limit
https://en.m.wikipedia.org/wiki/Landauer%27s_principle

For brute forcing a 128 bit at room temperature this comes out 262.7 Twh(the annual electricity consumption of Spain) that is a lot But not something humanity can't achieve.  By lowering the temperature we can improve on this. And some say we could build another type of computer which doesn't erase information and this limit won't apply to it. Though such a computer might go against the spirit of the question which excluded quantom computers.

So we don't actually have any good theoretical limits to prevent humanity from brute forcing a 128 bit key eventually. Which leads to my answer. Maybe.

For 256 bits the same energy limit would put brute forcing well outside the realm of the possible.


How do I derive the time complexity of encryption and decryption based on modular arithmetic? I want to calculate the time complexity of two encryption and decryption algorithms.

The first one (RSA-like) has the encryption
 $$ C := M^e \bmod N $$
and decryption
 $$ M_P := C^d \bmod N. $$

Assuming $n = \log N$, $m = \log e$ and $k = \log d$, I think they have time complexities $O(n^2 · m)$ and $O(n^2 · k)$, respectively.

Are these two complexities same?

I also have another pair of algorithms, with
 $$ C := M · k \bmod N $$
and
 $$ M_P := C · k^{-1} \bmod N.$$

How does the calculation of the modular inverse $k^{-1} \bmod N$ contribute to the time complexity?

I'll be assuming the question considers time complexity in big-O notation only, because that's common, the simplest, and there is no indication of the contrary. The price to pay for this simplicity is that the resulting time complexity is often a poor way to compare the efficiency of different algorithms.

In this section I restrict to the standard algorithms for addition, multiplication and division (taught in elementary school using base $10$), because they are the simplest, and often used in cryptography (with a higher base like $2^{32}$, but that does not change the time complexity in $O()$ notation).
Computing $A+B$ or $A-B$ in $\mathbb Z$ has time complexity $O(a)$, where $a$ is the number of digits of $A$ (in any base), and $b=O(a)$ using the same convention for $b$. In a cryptographic context, we take the liberty of writing that time complexity $O(\log(A))$.
Computing $A·B$ in $\mathbb Z$ has time complexity $O(a·b)$, or $O(\log(A)·\log(B))$. When $b=O(a)$, that time complexity is $O(a^2)$, or $O(\log(A)^2)$.
Euclidian division of $A\in\mathbb Z$ by $N\in\mathbb{N^*}$, that is computing $R\in[0…N-1]$ and $Q\in\mathbb Z$ such that $A=N·Q+R$, has time complexity identical to that for computing $N·Q$, that is $O(n·q)$, or $O(\log(N)·\log(Q))$.
When performing modular multiplication $A·B\bmod N$ in a cryptographic context, it is typical, and assumed unless otherwise stated, that $a=O(n)$ and $b=O(n)$. It follows that the time complexity of modular multiplication is $O(n^2)$, or $O(\log(N)^2)$.
Modular exponentiation $A^B\bmod N$ with $B>0$ requires at least $\log_2(B)$ modular multiplications (baring shortcuts possible using the factorization of $N$), and less than ${3\over2}·\log_2(B)$ using square-and-multiply. It thus has time complexity $O(n^2·b)$ or $O(\log(N)^2·\log(B))$.
With standard RSA assumptions, computing $C^d \bmod N$ has time complexity $O(\log(N)^3)$; that's because $d$ has size in bits or digits proportional to that of $N$ (and further, close to that), thus the size of $d$ is $O(\log(N))$. This remains unchanged when the CRT technique is used and there is a fixed number of prime factors in $N$ (which reduces the computational cost "only" proportionally to the square of the number of factors).
In RSA, if the public exponent $e$ is fixed, or of bounded size (which is common, and mandated by FIPS 186), then computing $M^e\bmod N$ has time complexity $O(\log(N)^2)$; that's because it is done with a fixed or bounded number of modular multiplications (e.g. $17$ for the common $e=2^{16}+1$). On the other hand, $e$ is sometime allowed to be of the same order of magnitude as $N$ (e.g. in PKCS#1), in which (rare) case $M^e\bmod N$ has time complexity $O(\log(N)^3)$.
$O(\log(N)^3)$ is, of course, not the same as (and more than) $O(\log(N)^2)$. In practice, the RSA private key operation (using $d$) is often much slower than the public key operation (using $e$).
The most commonly taught algorithm to compute the modular inverse $k^{-1}\bmod N$ is the Extended Euclidian algorithm. It is easy to show that it requires at worse $O(\log(N))$ steps, and that the time complexity of any step is $O(\log(N)^2)$ in the worst case (e.g. on the first step for $k\approx\sqrt N$), which is enough for some to give the time complexity as $O(\log(N)^3)$. However, this is grossly pessimistic: the worst case in term of number of steps corresponds to steps of time complexity $O(\log(N))$, and longer steps correspondingly reduce the number of further steps. By induction, I come to the conclusion that the time complexity really is $O(\log(N)^2)$ (but I would not bet the house on that; I welcome a reference, a refutation, or a proof).
Computing $M·k\bmod N$ with the same assumptions as in standard RSA regarding $N$ and $M$, and assuming that $k$ has size proportional to that of $N$, has obviously the same time complexity as modular multiplication, $O(\log(N)^2)$.
Using the same assumptions, computing $C·k^{-1}\bmod N$ has time complexity $O(\log(N)^2)$; that is dominated by the modular inversion step, for any implementation I can think of that uses comparable care in the modular inversion and the modular multiplication.

Notice the importance of the assumption: standard algorithms for multiplication and division. By using the Karatsuba technique for multiplication and Barett reduction for Euclidian division, modular multiplication has time complexity less than $O(\log(N)^{1.585})$ rather than $O(\log(N)^2)$; that's useful, and used in some software implementations of RSA, reducing the time complexity of the private (resp. public) key operation to less than $O(\log(N)^{2.585})$ (resp. $O(\log(N)^{1.585})$). The exponent can go further down using Toom–Cook, which generalizes Karatsuba. Schönhage–Strassen multiplication has time complexity $O(\log(N)·\log\log(N)·\log\log\log(N))$.
Update: the ultimate theoretical technique is $O(\log(N)·\log\log(N)$, by David Harvey and Joris van der Hoeven's Integer multiplication in time $O(n\log n)$, published in Anals of mathematics, March 2021.
The crossover between classical and sub-quadratic algorithms depends a lot on the quality of the implementation, and in particular on how close to the CPU architecture it gets (that's an area where assembly language shines over C, which obstructs access to the carry bit, and often to the whole result of the product of two unsigned integers of the widest size natively supported). While nearly optimal implementations of the classical algorithms using assembly language are relatively common, implementations of sub-quadratic algorithms are often quite sub-optimal, or/and complex (and thus hard to prove right in all corner cases, with the possible exception of Karatsuba).
My usual online references for multiple-precision arithmetic are section 14 in the HAC, and Modern Computer Arithmetic.


Digital signature - how secure is it? I'm new to asymmetric encryption guys, I read about it thoroughly lately and I don't get one thing.

If, say, I have a message, I sign it by first hashing the message, then encrypting it with my private key. After that I publish message and signature together. Then if anyone wants to check it, they have to decrypt it with my public key and compare the hash.

My question is: how do they know my public key?

If I send it with message - then anyone can forge it by altering the message, replacing the open key and making a new valid signature. Or maybe it can be requested from me? If yes, then what if someone interrupts that request and replace my public key in response with theirs fake one?

One more thing: what if the public key is not available? For example if there is a system were each node can broadcast its public key - what if some of the nodes are offline for weeks - does it mean their signatures can not be verified? Maybe their public keys are saved on some kind of centralized database, where you could request my public key by, say, my email. But this database can be hacked and public key will be replaced by a fake one - and nobody will trust my signatures anymore.

You see, maybe I don't get some particular subtle moment here - an issue of how to trust a genuine public key in any given network system, given that hacker may somehow interrupt any connection and replace messages between nodes (or if it's a centralized DB - public keys may be replaced by hacker).

A public key ultimately needs to be securely exchanged out of band to fulfill the commitment part of the signature process.

Typically the public key is pre-distributed where it needs to be used. As an example, your web browser comes pre-installed with the public keys it needs to validate certificates signed by certificate authorities. This can be used to obtain new public keys that are not pre-installed.

You are probably looking for Public Key Infrastructure (PKI).


How difficult is it to get a key using simple XOR Recently someone gave me an algorithm as follows:

XOR = Key XOR Random1 XOR Random2.

They think that in order for someone to extract "Key" from XOR they would need Random1 and Random2.. but looking at the above algorithm, i think it should be fairly easy for someone to guess or extract the Key w/o Random1 and Random2. The data is just 256 bits long.

Thoughts?

That "algorithm" is fine, as long as the random values cannot be guessed by an attacker. The scheme is known as (trivial) secret sharing.

XOR with completely random data is called a one time pad or OTP. The security of the algorithm therefore depends on the random number generator. Of course there are additional operational requirements to obtain system security (if somebody just distributes his share of the key ...).


Secret only known on consensus Does a method exist where a secret is generated so that is is unknown until 3 or more people (predetermined) reach consensus that it should be revealed?

If I understand the question right, what you are looking for is a fair secret sharing protocol. Most secret sharing protocols are unfair. For example, in 3-out-of-4 secret sharing with 2 dishonest parties, once one honest party broadcasts their share, the two dishonest parties can privately collude to reconstruct the secret. Then if they refuse to participate, the 2 honest parties cannot reconstruct the secret.

Fairness is described as "if there is a player getting the secret in the recovery phase, then each player participating to the reconstruction process does too" [1]. That reference proposes such a protocol and you can find a number of others by looking at the references in that paper.


Why Crypto++ library's AES definition is so fast I am trying to compare the CPU cycle required for two encryption algorithms. One algorithm is AES and lets the other algorithm is B(code name). I implemented algorithm B and having fewer and simpler operations than AES and expected to take much less time/CPU cycles per encryption than AES
I am using an Intel i3, 10 gen processor, with 4MB cache. I am running both algorithms individually (with random 16-byte input) for $2^{20}$ times and taking the minimum and maximum required CPU cycles.
I see that for algorithm B CPU cycles are minimum=2707866 and maximum=4767402. But, for crypto++ definition of AES, the CPU cycles are minimum=2724 and maximum=29978194. I have performed the test multiple times and the results are almost similar. It is clear that the maximum time required for AES is much higher(7x) then algorithm B, but the minimum time for AES is much less.
I then recorded required CPU cycles for all $2^{20}$ AES encryption. I found that the first encryption is taking maximum cycles (29978194) and then the required CPU cycle reduced drastically and after 10-15 encryption it took almost same(approx 3000) CPU cycles for each encryption. For algorithm B every encryption took almost the same CPU cycles.
I do not understand the drastic reduction(10000 times) of CPU cycles for AES encryption(crypto++ library). Is there any voodoo of AES-NI? Can someone tell what kind of optimization is being done there?

Actually, your numbers seem shockingly high at 2724 cycles for one block - even with the key schedule.
Crypto++ uses standard AES-NI for the encryption of blocks and for the key generation they use AESKEYGENASSIST for the SBox (unfortunately).
Ideally the expected performance would be (for their implementation, not for one with an optimized on-the-fly key expansion):

~783 cycles for the keyschedule (as estimated by llvm-mca)
1x 1 cycle for the initial XOR of the key
10x 4 cycles for AESENC/ AESENCLAST

So overall less than 1000 cycles.
Even if we assume AES-256 here, we shouldn't get beyond 1500 cycles for the actual operations. 2700 is massively off from that and suggests inefficiencies in feeding AES data.
Also note that this kind of test is highly unfair to the AES-NI hardware because it only really shines if you give it 4 or more independent AES operations to calculate in parallel (due to latency of 4 cycles per round instruction but the throughput of 1 cycle per instruction). Furthermore note that Crypto++'s keyschedule implementation is ... rather lackluster, and optimized implementations compute a round key in less than 20 cycles, so less then 200 overall for the entire cipher.
You can find the translated key expansion code here. You can look the performance of the instructions up either at Intel's site or in Agner Fog's tables.

A fairer comparison would probably take the best non-AES-NI implementation, a AES-NI implementation of AES and an optimized implementation of your cipher and put them up against each other in these categories:

CBC encryption of long messages - measures the cipher latency and long messages "hide" the key schedule cost
CTR encryption of long messages - measures the maximal throughput
(Optionally) Stand-alone keyschedule computations with one encryption (which is roughly what you measured) - with an implementation optimized for fast key schedules (aka not Crypto++ as it currently stands)


identify if the functions are pseudorandom generator? Given a pseudorandom generator (PRG) with $G(x) = y_{1} || y_{2}$, where $y_{1}$ and $y_{2}$ are n-bit strings. $G'(x) := G(y_{1}) || G(y_{2})$. Is $G'(.)$ still a PRG?
I am guessing it's a No because $G'(x) := G(y_{1}) || G(y_{2})$ always outputs the concatenation of $G(x)$ with previously generated outputs as inputs. But I am not sure what's the formal way of explaining this.

In addition. $G''(x) = G(y_{1}) ||G(y_{1})\oplus G(y_{2})|| G(y_{2})$, is $G''(x)$ still a PRG? I would say No again in this case because the pattern is again the concatenation of $G'(x)$ with the $\oplus $ in the middle?

I think I might be entirely wrong on this. A pointer or two would be appreciated.

$G'$ is a PRG. Proof sketch: by assumption, $G(x)$ for a uniform $x$ is indistinguishable from a uniform string. This means that $y_1$ and $y_2$ (the halves of $G(x)$) are also indistinguishable from uniform strings, and finally that so are $G(y_1)$ and $G(y_2)$.


SHA1 usage for passwords, alternatives and advantages? My application can authenticate via openid and oauth (facebook, twitter, etc) and also with its own authentication system. I previously switched hashing from MD5 to SHA1 and during migration I had to customize so that accounts could verify both with MD5 and SHA1 and now I've removed the MD5 completely.

I read here somewhere that for passwords in fact SHA1 should not be used and bcrypt or something else instead since SHA1 is not specifically a password algorithm and instead is a hash function implementation while a password algorithm would have other more specific features. Can you tell me more about this? Should I switch from SHA1, is it important or premature / paranoia since I never even had a production security issue that I know? I can think of some possible actions:

Staying with the current implementation (SHA1 and salt) since the main function of my service isn't user accounts anyway
Passing the algorithm as a parameter to the encryption and thus being able to authenticate with different and new algorithm i.e. now using SHA1 and later its easy to switch
Become an OAuth provider and then being able to add ourselves just like we add twitter, facebook and other OAuth providers
Does the issue of "real" and "fake" salt mean a lot in practice or just for highest security? Am I using real or fake salt in detail, when the following is the implementation:

def __encrypt(self, plaintext, salt=""):
    """returns the SHA1 hexdigest of a plaintext and salt"""
    phrase = hashlib.sha1()
    phrase.update("%s--%s" % (plaintext, salt))
    return phrase.hexdigest()
def set_password(self, new_password):
    """sets the user's crypted_password"""
    import datetime
    if not self.salt:
        self.salt = self.__encrypt(str(datetime.datetime.now()))
    self.crypted_password = self.__encrypt(new_password, self.salt)
def check_password(self, plaintext):
    return self.__encrypt(plaintext, self.salt) == self.crypted_password

Please tell me if you can comment.

Thank you

If your password database will never be compromised, you can store plaintext passwords and nobody will be bothered. The only thing about plaintext passwords is that they can be accidentally remembered by admins who see them - a simple base64 will fix that. Equivalently, MD5 or SHA1, with salt or without, is just as fine.

If your password database is possibly compromised at some point in the future, a single SHA-1 with salt still means that 99% of the user passwords are crackable on a laptop - basically no protection at all, except inconvenience. So if this is the attack you are worried about, you need to switch to something which has a sequential iteration count that isn't trivially small. PBKDF2, bcrypt and scrypt are all good choices for this.

(Note: assuming your password database will never be compromised is a really bad idea, if it wasn't already obvious from the answer.)


What is the lightweight key exchange protocol of choice? Assume I have to implement a secure channel protocol by myself. Assume further that for some obscure reasons (library restrictions?) I can't use any of the pre-made libraries for SSH, TLS and such. Assume even further that there are only few algorithms available namely the neccessary ones, such as AES, GCM, ECDH, ECDSA and SHA-256. And of course I'd like to avoid patent issues if anyhow possible.

Now I know that it's hard to implement TLS right, as can be observed at those many vulnerabilities on the common libraries (LibreSSL, OpenSSL,...). And I strongly suspect the same to be true for SSH and IPSec (=IKEv2).

Let's ignore the record layer (in TLS terms) of the secure channel and focus on the key exchange - for this question.

What is the simplest key exchange protocol with proven security against as many as possible attacks?

What the protocol should do is clear: Do some operations and as few as possible message exchanges and output a strong random shared secret at the end that may only be known by the two authenticated parties. This common shared secret should (of course) enjoy the forward secrecy property and it may not be completely chosen by one party.

The complexity requirements are also clear: The protocol should be a lot simpler than TLS with its myriad of extensions and it shouldn't be much more computationally intense than TLS either.

As far as the research goes, I know about STS suiting most security notions but also being vulnerable to some attacks. I know that there is MQV but it also had issues and seems to be covered by patents.

I would personally use triple Diffie-Hellman, which is used often in secure instant-messaging protocols but unfortunately not very well-known beyond that. Essentially, both parties have a long-term identity DH keypair, which they must securely share beforehand (through some CA system, manual fingerprint confirmation like SSH, etc). In each session, both parties also generate an ephemeral DH keypair.

Both parties send their identity and ephemeral public keys to each other, and do this:

DH1 = DH(their_identity_public_key, our_ephemeral_private_key)
DH2 = DH(their_ephemeral_public_key, our_identity_private_key)
DH3 = DH(their_ephemeral_public_key, our_ephemeral_private_key)
SK = KDF(DH1 || DH2 || DH3)

This derives a shared secret that they can use with symmetric encryption etc like TLS (don't forget to derive different keys for the two directions, and to use authenticated encryption!)

Triple DH provides both security and authentication against active attackers, as long as both parties know (a hash of) the other's identity public key beforehand. It also has the following desirable properties:

Forward secrecy: the ephemeral keypairs are thrown away after the session is done, so even stealing the long-term keypairs in the future cannot compromise recorded past sessions
Simplicity: the scheme's security relies entirely on that of one primitive: Diffie-Hellman, and by simply plugging in different functions for DH you can use variants like X25519, NIST-standardized ECDHE, classical DH, etc. There is also no need to maintain multiple keys; only the identity key needs to be kept around and kept secret.
Deniability: this is a property that most protocols do not have: although the key exchange is authenticated to the two parties, after it happens the two ends cannot present cryptographic proof that the session ever happened, since both parties can forge a convincing transcript of messages. (For a non-deniable protocol, see ECDSA-signed ECDHE, very commonly in used in TLS. It uses Diffie-Hellman and has forward secrecy, but signing the key-exchange messages with an ECDSA key destroys deniability)


What is the security concept in printer cartridge? Based on this datasheet or this patent, one of the usage of PUF is printer cartridge identification and authentication. I was wondering why printer cartridge needs identification and authentication. In other words, what is the security concept behind it?

Furthermore,

what is the required protocol for it?

which item behaves as PUF?

who sends the challenge?

who verifies the correctness of the response for the given challenge?

A company can make more money if the printers it sells only work with the cartridges they sell, which does not work if there is competition. It's cheaper to force a vendor lock-in than it is to innovate and ensure that your product holds up to the competition. All the printer's authentication does is prevent you from using cartridges made by other companies. Think of it like DRM for ink. It's just capitalism.

There is no standard protocol. Each vendor is free to implement this in their own way. Most likely it's some form of challenge-response authentication done between the cartridge and the printer.


Is ECB mode secure if plaintexts are guaranteed to be unique? I've got a scenario where I need to encrypt many small (16-byte) plaintexts. I want to use AES-128 in ECB mode. Notably, each plaintext is guaranteed to be unique, though each may differ by only a few bits.

In this scenario, is ECB secure?

Yes, this is one case where ECB mode is secure.

It can be shown to be secure trivially from the indistinguishability assumptions of AES; that AES with an unknown key cannot be distinguished from a random permutation.  If the plaintexts are all 16 bytes long, then in ECB mode, this directly means that the ECB mode encryption of those plaintexts are indistinguishable from random.

I'm sure MrNerdHair already knows this, but for those people who may be reading this later, lets make this a bit more explicit.  The assumptions that I am making are:

Every plaintext message is 16 bytes (either they're all 16 bytes, or they are all less than 16 bytes and become 16 bytes after padding).  If the message is longer (and so ECB mode does two separate encryptions), the attacker may be able to take advantage of the lack of interaction between those two blocks
Every plaintext message is distinct.  This matters because ECB mode encryption is determanistic, and so if we encrypt the same message twice, the ciphertexts will be exactly the same; this may be exploitable.


Proving that two points on elliptic curve are within range Is it possible to prove that a point on an elliptic curve falls within a given range of another point, without revealing the distance between them. For example:

Let's say $X$ and $Y$ are two points on an elliptic curve such that $X = x \cdot G$ and $Y = y \cdot G$, where $G$ is the generator. The proover knows values of $x$ and $y$, and wants to prove to the verifier that $|x - y| < z$, where $z$ is some value supplied by the verifier.

Another option: prove that $\frac{x}{y} < z$, where $z$ can be a relatively small number (e.g. 2).

Is either of these possible?

The proof showing that,  given $G$ and $x \cdot G$ and a range $[A,B]$, $x$ is in the range $[A,B]$ is known as the range proof.
In your case, we can convert your statement as the range proof as, given $G$ and $H = xG - yG$, showing $x-y$ is in the range $[-z,z]$.

For example, the following papers (and a lot of papers) proposed efficient range proofs.

Jan Camenisch, Rafik Chaabouni, and abhi shelat: Efficient Protocols for Set Membership and Range Proofs (ASIACRYPT 2008)
Benedikt Bünz and Jonathan Bootle and Dan Boneh and Andrew Poelstra and Pieter Wuille and Greg Maxwell: Bulletproofs: Short Proofs for Confidential Transactions and More (IEEE S&P 2018)


Is this problem based on a known hard problem? Suppose I generated an $n$-dimensional vector $a_{(1)} = [a_1, \dotsc, a_n]$ with integer component (actually I can generate as many $a_{(i)}$ as possible). Now I need to get an vector $b = [b_1, \dotsc, b_n]$ such that $\langle a_{(i)}, b \rangle = c_{(i)}$, for all $i$. I don't know the value of $c_{(i)}$ but I can verify whether $c_{(i)}$ is correct (by an decryption algorithm which have $c_{(i)}$ as the key, like AES).
I want to know, is this problem hard? If true, what hard problem is it based on? I've read materials about the knapsack problem, subset sum problem even integer programming. But I don't think that they match.
Edited on Dec 3, 2014: Allow me to modify the question described above because it may not be meaningful. Now I have a group of equations $Ba = c$, where $B$ is an unknown matrix, $a$ and $c$ are known vectors. They are all $n$-dimensional (the previous question is one equation of this group, and I remove the restriction to $c$ because if I want to realize better security, I need to assume that $c$ is known). So in group $1$, we have
$$
Ba^{(1)} = \left[
\begin{array}{cccc}
b_{11} & b_{21} & \cdots & b_{1n}\\
b_{21} & b_{22} & \cdots & b_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
b_{n1} & b_{n2} & \cdots & b_{nn}
\end{array}
\right] \cdot \left[
\begin{array}{c}
a_1\\
a_2\\
\vdots\\
a_n
\end{array}
\right] = \left[
\begin{array}{c}
c_1\\
c_2\\
\vdots\\
c_n
\end{array}
\right] = c^{(1)}
$$
Now my question is:

As far as I know, if we have $n$ groups of $a^{(i)}$ and $c^{(i)}$ such that $Ba^{(i)} = c^{(i)}$, we can calculate $B$ easily. But what if we can get at most $n-1$ groups? I think there are infinite solutions, but can we recover part of $B$? Or all of the $\{b_{ij}\}$ are indeterminate? (Suppose $\{a^{(i)}\}$ are independent vector set.)
What if $B$ is an orthogonal matrix? How many groups are enough to recover $B$? And is it hard to calculate $B$ if $n$ is big?

This problem hugely depends on the distributions of the $c_{(i)}$, if they are independant or not, also on the size of the space in which each coordinate of the vectors are, and on the information you gain with each check if $c_{(i)}$ is correct.

Assuming the vector space is $Z_q^n$ and $n$ is polynomial in $\log q$, that $c_{(i)}$ are independant and uniformly distributed, and that your verification algorithm only tells you if $c_{(i)}$ is correct or not, let us look at the problem for one instance of $a$, $b$ and $c$.

If you take $b$ uniformly at random, you have probability $\frac{1}{q}$ to have $⟨a,b⟩=c$, which is exponentially small.

Moreover, there is no way to improve brute force on the value of $⟨a,b⟩$ because you don't learn anything beside the correctness of your $b$, so this is a problem you would call hard is cryptography.
Even if you have a polynomial number of instances, this won't help you that much because finding a $b$ such that even only one $⟨a_i,b_i⟩=c_i$ is already exponentially hard.

Of course, this is an information theoretical approach to the complexity of this problem, and I think the real assumption you want to reduce to is one that would allow you to use my results, i.e. an assumption which makes you learn nothing when you verify $⟨a,b⟩=c$.

I know this is not really a reduction, but that's all I've got to help you, I hope it is enough.

Let me edit to reply to yours.

First, say you have $q$ groups of $a^{(i)}$ and $c^(i)$.

Now if you know $c$, you are just asking to solve a system of $qn$ linear equations with $n^2$ unknown. Now I think the subject is quite known and you can find a lot of documentation on it easily.

Remark that $B$ being an orthogonal matrix corresponds to adding $n$ equations to the system. Even though they are no more linear, I think the subject has already been studied.

As for the complexity questions, if I'm not wrong you can solve the problem with an algorithm running in time polynomial in $n$, so one would consider it easy.


How does the index of coincidence work in the Kasiki test? I'm starting to learn about cryptanalysis and I am having a bit of difficulty understanding the Kasiski test's index of coincidence. I have a book (Cryptography Theory And Practice by Douglas Stinson) about it that I'm going through, but it seems to skip something, which is causing my confusion. More likely it's me who is constantly missing a line or something.

The book gives the example:

CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBWRVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGXWTRZXWIAK...

and uses CHR to find the possible keyword length. It occurs 5 times in the total ciphertext, which I did not type out completely. To show that the key is most likely 5 characters, the book also shows the index of coincidence for words of length m, from 1 to 5.

What I don't get is how it got the index of coincidences for the ms.

  With m = 1, the index of coincidence is 0.045. With m = 2, the two
  indices are 0.046 and 0.041. With m = 3, we get 0.043, 0.050, 0.047.
  With m = 4, we have indices 0.042, 0.039, 0.046, 0.040. Then trying
  m = 5, we obtain the values 0.063, 0.068, 0.069, 0.061 and 0.072.

Even with the formula to get the index of coincidence, I don't see how the values were gotten. Can someone please explain?

Kasiki's test and the index of coincidence are used to attack a Vigenère cipher (or other polyalphabetic ciphers with small alphabet and small key size) - they both try to get the length of the keyword.

Kasiki's test gets probable prime factors of the keyword length, while the coincidence index test gets us an estimation of the absolute length of the keyword.

The original Kasiki test

This is what was done with CHR in your example: We look at repeated sequences of three or more characters, and at which distances they occur. We collect all these distances, and look at the prime factors of these.

The idea is that probably such a repeated sequence comes from the same plain text sequence, which then randomly hit the same keyword position. They will only hit the same position if their distance is a multiple of the keyword length.

Of course, we also can get random hits here (where different plaintext sequences got encrypted by different key sequences to get the same ciphertext sequence) - so be careful which prime factors to select. Either combine this method with Friedman's test mentioned below, or try different keyword length's for further analysis.

The coincidence index

The coincidence index of a text is defined as

Here n is the size of the alphabet, ml the number of occurrences for the character l, k the total size of the text. (δ(xi, xi) = 1 if the characters at position i and j are equals, else 0. But for calculation the second sum is more convenient.)

The coincidence index of a totally random text would be $1/k$ (and this is also the total minimum), while for natural language texts it is higher (0.067 for english, a bit higher for German). For a ciphertext encrypted by a monoalphabetic cipher it is still the same as for the original plaintext, for polyalphabetic ciphers (like Vigenère) it is between those.

(Actually, there are different definitions of coincidence index, but the values you have seem to use this one.)

Column-wise coincidence index to get the keyword length

You now take guesses at the key length h, and writes the cipher text in h columns. Then (if we guessed right) effectively the letters in each column are encrypted with the same key letter, e.g. monoalphabetically. We now calculate the coincidence index of each column individually. If we had a good guess at the key length, the coincidence index is near the coincidence index of the original plaintext column (which, if long enough, is a good approximation for the coincidence index of the used language).

In your example, for the lengths 1,2,3,4 the coincidence indices are only around 0.045, which is not much higher than 0.385, the expected value for a random 26-letter distribution. For length 5, you see a sudden jump: the indices are around the value for English (0.067). For 6, it will likely get lower again.

This will get you quite similar results as the Kasiki test, but is easier automated.

Friedman's method

Actually, Friedman derived from this a formula which spares us the calculation of each column's coincidence index - we just need the global coincidence index of the ciphertext (and the one of the natural language) to get an estimation of the keyword length.

While the English Wikipedia page does not mention this formula, the german language Wikipedia shows this:

Here $E_S$ is the expected coincidence index for our natural language, $\phi(T)$ the total coincidence index of our text, n the alphabet size, k the text length.

Your example

Using your value for m = 1 (which is the global coincidence index) and 26 for n, we get approximately

$$h ≈ \frac{(0.067 - 0.0385)\cdot k }{  (k-1)\cdot 0.045 - k\cdot 0.0385 + 0.067} = \frac{0.0285·k}{0.0065·k +0.022}$$

For example, for k = 1000 we would get h ≈ 4.36.  This is (together with the previous check from the column-wise coincidence index) a good hint at a keyword size of 5.

When we have the keyword length, we can use other methods, like frequency analysis on each "column", to crack the whole cipher.


What does "Inverting the RSA function is as hard as factoring" mean (a rigorous explanation or intuitive will do)? I was reading that a current open problem is if inverting the RSA function is as hard as factoring.

Does this mean that, its an open problem whether, if given a subroutine that computes in probabilistic polynomial time (i.e. in BPP) the inverse of the RSA function, then its not actually known if we can factor numbers in (probabilistic) polynomial time (i.e. if an algorithm in BPP exists)?

We are dealing here with two assumptions and we always refer to $N=pq$ the product of two $n$ bit primes $p$ and $q$. The one is factoring and the second is the so called RSA assumption which is a formalization of "inverting the RSA function is hard".

These two assumption can be described as follows:

Factoring assumption: There exists no probabilistic polynomial-time algorithm
that, given an RSA modulus $N$, finds a non-trivial factor of $N$ with non-negligible probability in $n$.

RSA assumption: There exists no probabilistic polynomial-time algorithm
that, given the pair $(N,e)$ with $N$ being an RSA modulus and $e > 2$ with $\gcd(e,\varphi(N)) = 1$ and an element $y$ chosen uniformly at random from $Z_N^*$, computes $x\in Z_N^*$ such that $x^e\equiv y \pmod{N}$ with non-negligible probability in $n$.

Now you ask

  I was reading that a current open problem is if inverting the RSA function is as hard as factoring

Yes, this means that it is an open question whether these two things are equally hard. In a formal language this means whether a solver for the first problem yields a solver for the second and vice versa.

Now, it is quite obvious that when one has an efficient algorithm $\cal A$ that breaks the factoring assumption, this implies an efficient algorithm $\cal B$ that breaks the RSA assumption. Basically, if $\cal A$ outputs a non-trivial factor of $N$, say $p$, then $\cal B$ can efficiently comptue $q$ and thus knows $p$ and $q$ which allows to efficiently compute $\varphi(N)$ and futher to efficiently compute $d$ such that $e\cdot d \equiv \pmod{}\varphi(N)$ (e.g., using extended euclid) and outputs $y^d \mod N$.

Consequently, if the RSA assumption holds then the factoring assumption holds or equivalent if the factoring assumption does not hold, then the RSA assumption does not hold. However, it is not known whether the converse is true, i.e., if the factoring assumption holds then the RSA assumption holds or equivalent if the RSA assumption does not hold then the factoring assumption does not hold.

Latter would require to show that an efficient algorithm $\cal B'$ that breaks the RSA assumption implies an efficient algorithm $\cal A'$ to break the factoring assumption.  But as you said, this is an open problem.

If one could establish the latter result, then we would know that the RSA problem and the factoring problem are equally hard.


Using round constants to thwart slide attacks I'm partly unclear as to how the use of round constants in an iterated cipher makes it immune to slide attacks. I mean, I can see how it does from one perspective, but if the solution to slide attacks is by "making each round different", then shouldn't distinct round keys accomplish this, too?

Yes the different round keys help, but without the different round constants in key-schedule, all the rounds of key-schedule algorithm will be same. Thus these identical rounds may generate sliding round keys. For example

AES-128 uses 11 round keys, without the round constants, all the rounds of the AES key-schedule will be same. Thus there is chance that there exist two master keys $Ka$ and $Kb$, such that there corresponding round keys differ at only one place.

Suppose 11 Round keys for $Ka$ are: $ka,k1,k2,k3,k4.......k9,k10$
and 11 Round keys for $Kb$ are: $kb,k1,k2,k3,k4.......k9,k10$

if you set $Kb=k1$, then 11 Rounds for kb will be: $k1,k2,k3,k4,k5....k10,k11$

Now you see Both keys have same round keys with an offset of one except that last round key of kb and 1st round key of ka. These identical keys with offset of 1 place help in making slid pair, which is required for Slide Attack.

If each round will have different fixed round constant, generation of such identical round keys will not be possible, thus preventing Slide Attack.


Why does AES-GCM not require an auth key, but encrypt-then-mac does? The inputs to AES GCM mode appear to be:

an IV
a key
message to encrypt

The output is a cipher and auth tag.

However, if one were to manually perform an encrypt-then-mac scheme, the inputs required would be:

an IV
a key
an auth_hash (for decryption)
an auth_key
message

Then, you would compare auth_hash == HMAC(message, auth_key) before decrypting(message, key, IV).

So with the manual approach, there are 2 more inputs. Why is GCM able to do the same thing with less inputs?

AES-GCM does require an authentication key. You don't need to pass it because it is generated from the encryption key by encrypting an all-zero "plaintext" block:

  The hash subkey, denoted $H$, is generated by applying the block cipher to the “zero” block. The
  resulting instance of this hash function, denoted $GHASH_H$, is used to compress an encoding of
  the AAD and the ciphertext into a single block, which is then encrypted to produce the
  authentication tag.

(source - in "5.3 Primitives for Confidentiality and Authentication")


The trick is to take logarithms. The information you have above can be translated as
$$
\begin{align}
2 &= 3\cdot \log_{19} 2 + 1\cdot \log_{19} 3 + 0\cdot \log_{19} 5 + 0\cdot \log_{19} 7 \pmod{336} \\
5 &= 5\cdot \log_{19} 2 + 0\cdot \log_{19} 3 + 1\cdot \log_{19} 5 + 0\cdot \log_{19} 7 \pmod{336} \\
 & \dots
\end{align}
$$
This is basically a linear equation system modulo $336$ (the order of $19$ modulo $337$), at the end of which we obtain the logarithms of $2$, $3$, $5$, and $7$ in base $19$, which are $160$, $194$, $213$, and $6$. (This might require solving the system modulo each factor of $336 = 2^4 \cdot 3 \cdot 7$ individually and recombine with the Chinese remainder theorem).
Having those logarithms, we can use one of the other equations to find the logarithm of $205$. For example,
$$
205\cdot 19^{-1} = 2^6 \cdot 3^0 \cdot 5^0 \cdot 7^0 \pmod{337}
$$
can again be translated as
$$
\log_{19} 205 - 1 = 160\cdot 6 + 194\cdot 0 + 213\cdot 0 + 6\cdot 0 \pmod{336},
$$
from which we easily obtain $\log_{19} 205 = 160\cdot 6 + 1 \bmod 336 = 289$.


Knowing pre-encryption data, can we find the private key CryptoLocker used? One of our users seems to have been hit by CryptoLocker. As a result, he has a hard drive full of encrypted files. The ransom-ware claims to have used public key encryption on  the files.

If we know exact contents of some of the files prior to them being encrypted, would it be feasible to use those files to discover the private key?

If CryptoLocker does its job properly, then no, knowing part of the cleartext will not help you recover the rest. If that helped, then the encryption system would be called weak against known-plaintext attacks. From what I read, it seems that the CryptoLocker authors were competent(*), so no such luck.

(In particular, the asymmetric encryption with RSA-2048 is done only for a random symmetric key, and the bulk of the data is encrypted with a symmetric encryption algorithm like AES, using that key. This is the normal setup of hybrid encryption. This means that if you were to find weaknesses with regards to known plaintext, then you would have to look for them in the symmetric encryption algorithm, not the RSA part. The result, though, is the same: no known way to recover your data. Sorry.)

(*) I am here talking about the encryption. I believe the payment system may leave exploitable traces which would allow law enforcement agencies to track down the perpetrators. But this is likely to involve countries of questionable cooperativeness, so don't put too much hope in this.


Is there a technique to confirm that a given large integer value is a product of two primes? Given a list of 2048 bit integer values in which one or few 2048 bit integer values
may be product of two prime numbers and other values may be just 2048 bit odd integers numbers.

My question is -
Is there a way / technique (apart from brute-force) to confirm that a given 2048 bit integer value is product of two prime numbers or not?

Is there any pattern in an integer value which is not product of two prime numbers?

No, there is no known test that we can run on a 2048 bit composite number that would indicate whether it was the product of two primes, or whether it was the product of more than two primes.

About the closest we can get is a zero knowledge proof; we know how someone (who does know the factorization) can run an interactive proof with us that can demonstrate to us that there are only two prime factors (and not reveal anything else).  However, that does not appear what you're asking for.


Discrete logarithm problem in subgroup of index 2. ElGamal I need some insight for the following problem in ElGamal encryption procedure. It is stated that ElGamal problem in a group $\mathbb{Z}_p^*$ becomes easier in subgroups. Assume I have a subgroup of index 2. Can you explain how is easier the discrete logarithm problem in this case?

As an example, algorithms, such as baby step giant step  with time and memory complexity $$T=M=O(\sqrt{N})$$ or Pollard's rho  with time and memory complexity $$T=O(\sqrt{N}),\quad M=O(1)$$have complexities that depend on the size $N$ of the group over which the DL is defined.

So $N=\mathbb{Z}_p^{\ast}=p-1,$ while a subgroup of index 2 has size $N'=(p-1)/2$ and the complexity improves accordingly.


Computing youngest person among 3 while keeping ages private I already found a protocol to find out who is richer (older) between two parties, but Is there any protocol to find the youngest person among 3 parties, without revealing actual ages?

There might be better ways to do this, but I wanted to do it with only primitives found in VIFF (why? because it is the MPC framework I am most familiar with). There could be specialized protocols which are better.

In VIFF, we have access a primitive >= which returns 0 or 1 (false or true). We can do the comparison you seek using that plus some simple arithmetic on secret shared values. I think these are all passive protocols and do not guarantee fairness (if fairness even makes sense in the passive world).

Let the three parties be alice, bob and charlie. They have each secret shared their ages with the others. We'll let a,b,c be the variables that represent the secret shared ages.

We can compute who is the youngest as follows:

ab = (b&gt=a) # is a younger than b?
ba = 1-ab # is b younger than a?
ac = (c&gt=a) # is a younger than c?
ca = 1-ac # is c younger than a?
bc = (c&gt=b) # is b younger than c?
cb = 1-bc # is c younger than b?

a_score = ab + ac
b_score = ba + bc
c_score = ca + cb

# At this point we are guaranteed to have a score of 2, a score of 1, and a score of 0.
# Whoever has the score of 2 is the youngest.
reveal(a_score&gt=2) # if this is 1, then Alice is youngest
reveal(b_score&gt=2) # if this is 1, then Bob is youngest
reveal(c_score&gt=2) # if this is 1, then Charlie is youngest

This computation only reveals who is the youngest. It does not reveal ages or the overall order. It requires 6 calls to >=. This will also only return 1 person as youngest. To get all of the youngest, you would replace the 2nd, 4th, and 6th lines with another >= instead of a 1-XX.


Perfect Forward Secrecy with Pre-shared Key I've recently been looking at how to do perfect forward secrecy on a unidirectional connection (server can only push messages to client, client cannot respond).

What I've come up with is the idea of using a random shared key as a starting place and using this as a symmetric cipher key for the first pushed message. Once this message is pushed, the key is hashed, the result of this hash is the key for the second message. This continues to function as a sort of hash tree, ie:

$$
\begin{aligned}
   K_0 &= R &&
\\ K_1 &= H(K_0) &&= H(R)
\\ K_2 &= H(K_1)&&= H(H(R))
\\ \vdots &\qquad\vdots && \qquad\vdots
\\ K_n &= H(K_{n-1}) &&= H^n(R)
\end{aligned}
$$

If this is implemented correctly and the previous key is always destroyed fully (perhaps kept only in RAM) then I believe this could offer perfect forward secrecy assuming client and server can exchange the initial random value securely (the idea is that these be exchanged via QR code or similar mechanism).

The only disadvantage that I'm aware of to this approach compared to interactive Diffie-Hellman would be that if a server or client was compromised in this system, using the information within could allow a passive attack instead of an interactive (MITM) attack.

I doubt this is a new or unique idea at all, but just looking for some people to bounce this idea off before I attempt an implementation. I'm wondering if anyone has any thoughts on additional things to look out for that I may have missed or if I am catastrophically wrong and this won't work at all.

A possible deficiency is that if the use made of any $K_j$ allows it to leak, all later security is lost. That makes $K_j$ plain unsuitable in some uses, e.g. directly as keystream for short messages.

The $K_j$ must be wide enough that it is extremely unlikely that a cycle is ever reached in deriving them. For plausible parameters that translates to $n^2<2\cdot|K_j|\cdot\epsilon$, where $\epsilon$ is a small acceptable residual risk, and $|K_j|$ is the bit width of $K_j$. If $K_j$ was a 128-bit key, with 100 keys per microsecond for a decade, I get $\epsilon\approx2^{-19.4}$. That could be a problem when some requirement prescribes a very low $\epsilon$, like $2^{-40}$.

The above two can be solved with a wide key (and hash), derived into a working key (perhaps shorter) using a Key Derivation Function such as HKDF or one of these, preferably not using the same hash function as the one used to derive the $K_j$.

Another: if the adversary can only test a candidate key $K_j$ at relatively high cost $C_0$, and in some conceivable uses of $K_j$ like encryption of a known constant block, an adversary trying brute force and for which hashing has much cheapest cost $C_1$ gains an enormous speed boost from how the $K_j$ are derived; something like $\mathcal O(\min(n,C_0/C_1))$, neglecting cost of a memory fetch per hash. That can be solved by using, in order to derive $K_{j+1}$ from $K_j$, instead of a hash, a slow key-stretching function, such as scrypt or the lesser PBKDF2, with cost parameter(s) such that $C_1\approx C_0$.

Last one that immediately comes to my mind: the receiver must forget the current $K_j$ only after validating the next one, or some later one if lost messages are part of the assumptions. And in the later case it is probably a good idea to limit the number of consecutive messages that can be skipped, else there is a trivial Denial of Service Attack.


AES-encrypted 128-bit null block: lookup table? Let's say a 1MB file has many many consecutive null-bytes 128-bit blocks. Then, as AES works with blocks, the encrypted file will also have recurrent 128-bit-long patterns of aes_encrypt(000...0) (where 000...0 is a 128-bit long null block).

How isn't this a weakness?

As null-bytes blocks is very frequent in files, we could easily recognize "oh this recurrent pattern in cipher is certainly the result of the encryption of 128 null bits".

Then a lookup table:

Key                          Cipher of null 128-bits
----------------------------------------------------
Hello                        a8ff00ac..ff6b
easypassword                 b20fa312..ae27

could help to find the key, isn't it possible?

Is the fact it "works in blocks" not a weakness?

In practice we use something called a block mode.

The traditional block mode is cipher block chaining (see image). In this block mode we XOR the ciphertext of the a block with the plaintext of the next block. The first plaintext block will be XOR'd with a public initialization vector. This way we make sure that every ciphertext is different.

  How isn't this a weakness?

It is. In your case the block mode that is used is ECB, basically applying the block cipher to each block independently. ECB is considered insecure for normal use.

  Could you make a lookup table for all blocks of only zeros?

No. Because almost always keys are generated randomly, we would need to store $2^{128}$ entries in our lookup table. Our universe will never have enough disk space to store it.


Is the practice of "security through obscurity" violating Kerckhoffs's second principle? Security through obscurity is the reliance on the secrecy of the design or implementation as the main method of providing security for a system or component of a system.

Kerckhoffs's second principle:

  "It should not require secrecy, and it should not be a problem if it falls into enemy hands"

As stated here in the section "Security through obscurity":

  "It helps, I think, to go back to Kerckhoffs's second principle, translated as "The system must not require secrecy and can be stolen by the enemy without causing trouble," [...]. Kerckhoffs said neither "publish everything" nor "keep everything secret"; rather, he said that the system should still be secure even if the enemy has a copy."

But isn't the practice of security through obscurity still violating Kerckhoffs's second principle per definition?

And why are people even practicing security through obscurity if it, as stated, doesn't provide more security?

"It should not require secrecy, and it should not be a problem if it  falls into enemy hands"

Where "it" is the algorithm design itself, and not an input to it...

  But isn't the practice of security through obscurity still violating Kerckhoffs's second principle per definition?

Yes. Obscurity is hardly a defense that demands prohibitive computational cost from an attacker to work around. It makes the problem inconvenient, rather than computationally intractable.

However, it should be noted that "Security through obscurity" and "Security plus obscurity" are not the same thing.

Using algorithms that would be secure even if the adversary knew all about them, but additionally declining to let the adversary know about them is not worse than using a secure algorithm by itself. It is debatable if it is any better, as there is no such thing as "more secure" if it is already "secure".

  And why are people even practicing security through obscurity if it, as stated, doesn't provide more security?

Even the naive realize that secrecy is critical for cryptography to function. But:

They almost certainly don't have the knowledge that has been painstakingly gathered by years of failure and research (history of cryptography and modern research).

e.g. that security through obscurity is not sufficient

They may have never heard of Kerckhoff's principle
They probably have not heard of/do not understand linear/differential cryptanalysis/number theory/group theory and other modern analysis techniques.
They clearly don't understand that concentrating secrecy into a key is far more effective than keeping an entire algorithm a secret.

For a meatspace analogy: Your front door is not secure because attackers don't know that it is locked or what it is locked with, but because they don't have the key*.

They probably don't have the kind of confidence in their setup that comes about as a result of thorough research and analysis.

If you examine the work of a successful cryptographer, for example Daniel J Bernstein, then you will find no obscurity anywhere. All of the details of the designs and implementations are publicly available.

*Disregarding real-world details such as lock picks and lock models that are keyed alike.


Why is 128-bit considered "medium term" security? Why is 128-bit encryption considered good enough for medium term security only?  How is expected to be eventually broken?  Quantum computing or brute force attack?

Why is 128-bit encryption considered good enough for medium term
  security only?

Because in the long term it is expected that mankind will be able to carry out $2^{128}$ operations because it's not physically as impossible as $2^{256}$ operations.

  Quantum computing or brute force attack?

Assuming quantum computers work at a speed comparable to classical computers nowadays, they can break 128-bit encryption using $2^{64}$ operations (Grover's algorithm) which is considered feasible in the long-term, of course this should be considered additional to classical brute-force which may also be feasible at some point.


Is the number of creatable torrents limited? Currently, a magnet link containing a 40-digits long SHA-hash value, is assigned to every torrent which is created. Therefore, this hash should be unique to identify a torrent and send the right bytes (packages) to the right people. So therefore, there are $16^{40}$ (1461501637330902918203684832716283019655932542976) possible hashes to uniqueliy identify a torrent. What happens after this number has been reached or two torrents with different content have the same hash? (Although this practically never happens, there is a chance of $\frac{x+1}{16^{40}}$ where $x$ is the number of public torrents aka. assigned hashes, that your hashes collide.)

So to make long things short: What happens if two magnet-link-hashes are equal for different contents? What happens after every magnet-link has been used?

$16^{40}$ is a huge number. For instance, if you consider each torrent to consist in a single byte each (so they are quite uninteresting torrents), and you pack them all on 10 TB hard disks (for a torrent to exist, it must exist on at least one hard disk on the planet), and if each such disk weighs about 100g, then the total weight of the disks is about 24 billions of times the mass of the whole Earth.

So I am quite confident in stating that this number will not be reached.

Risks of collisions are actually higher. If you accumulate 160-bit hash values (outputs of SHA-1) then, on average, the first collisions should appear after about $2^{80}$ values (this is known as the birthday paradox). So the situation you describe may occur much earlier than after exhaustion of the $16^{40}$ space. But $2^{80}$ is still huge, and cannot be practically achieved ($2^{80}$ torrents mean more than one hundred thousand billions of torrents per human being on Earth).

If a hash collision occurred, then streaming either of the two colliding files would most probably cease to work; downloaders would obtain a mixture of both files. Other torrents would remain totally unaffected.

An interesting question is whether you could, given an existing torrent $T$, handcraft another $T'$ which hashes to the same value -- it would be used as a weapon to prevent usage of $T$. To do that, you would have to break second preimage resistance of the hash function. SHA-1 has a few known weaknesses, but for now there is no known method for obtaining a second preimage, except luck (try random values until one matches). Luck (aka "brute force") has average cost $2^{160}$, which is completely out of reach of today's (and tomorrow's and next decade's) technology.


Is there a way to slow down collision attacks using iteration? The simple way to iterate a hash function $H(H(m))$ only makes brute force preimage finding slower, but leaves collision attacks as fast since a collision in the inner hash function is a collision in the overall function.

Is there an iterative algorithm that also slows down brute force collision attacks? Without expanding the output size?

I am looking for something that reduces to the standard properties of the hash function, rather than only working for an ideal hash or a random oracle.

The use case is that a short hash is used, e.g. 128 bits with 64-bit collision resistance. Collision finding attacks should be slowed down sufficiently to be infeasible, e.g. to $2^{100}$ hash function calls.

As others have pointed out in the comments, using the message in the hash iteration can dissolve collisions in the inner hash again. Additionally, the round number can also be used, in case you have collisions over different rounds. But concatentation is just one possible way to combine these values as input.

If your assumption is just a general hash function, you should have a function $f$, and then set:

$h_1 = H(m)$
$h_{i+1} = H(f(h_i,m,i))$

Concatenation might be one possibility for $f$, but it could be problematic in Merkle-Damgard constructions. You could also use a hash function for $f$, but that wouldn't adress this problem. Alternatively, you could use an MAC instead, where you use the hash of the previous round and $i$  to derive the key, and you can choose from the various MAC algorithms. Alternatively, you could also use a block cipher directly as $f$, just like the MAC algorithms (well, some MACs are based on block ciphers). But you will have to keep in mind, that $m$ itself might be a lot longer. A more general way might be the assumption of a PRF.

On a similar note: Alternatively, you could use a  CSPRNG based on a hash function, seed it with the message, and then iterate just "far enough", that it matches your wanted number of iterations, and use that as output.

For your consideration of 128 bit, I would say CMAC/OMAC with AES could be used, e.g.$f:= CMAC_{h_i}(m||i)$


Guessing encryption algorithm based on key and ciphertext Is it possible to tell which encryption algorithm was used, assuming I have a key and a encrypted text?

To not complicate the situation let assume we are speaking about symmetric algorithms only.

Are there any common methods to discover encryption method?

The normal method is to reverse-engineer whatever software produces or consumes the ciphertext. The underlying idea is that in a practical attack situation, the attacker has some known interest in breaking the system; there is context. The context usually indicates what kind of algorithm is in use.

In some cases where the code to reverse-engineer is not immediately apparent, other clues can be gathered. For instance, a smart card which can encrypt data at relatively high speed must necessarily use some dedicated hardware, so data sheets from the smart card vendor can point to what algorithms are possible.

Many communication protocols strive for algorithm agility and therefore include an explicit header about what algorithm is used. For instance, in SSL/TLS, the set of algorithms which will be used by client and server is negotiated in plain view, so what encryption algorithm is used is perfectly known to everybody, including any attacker.

Now, if you envision a formal, unrealistic setup where you are just given a black box which encrypts data with an algorithm and a key that you do not know, then guessing the algorithm details would amount as a break, in an academic point of view. Good encryption is supposed to be indistinguishable from randomness, which implies, in particular, that any secure encryption algorithm is supposed to be indistinguishable from every other secure algorithm.


Using rainbow tables to find encryption keys of block ciphers? Hi I have a question in mind.

  Let's consider a block cipher whose key length is 36 bits.
  The bit-length of the plaintext is 256 bits, but there are only 16 possible plaintexts $m_0, m_1, . . . , m_{15}$. The encryptions are carried out in ECB mode and thus no IV is involved. We want to build a rainbow table such that, on input a ciphertext, we can readily find the key and the plaintexts.

How do we go about constructing a rainbow table for this purpose?

Define a function that takes the 4-bit plaintext identifier and the 36-bit key as input. For the purpose of the rainbow table you can treat it as an opaque 40-bit value.

The output of this function is the ciphertext you get when you encrypt the plaintext corresponding to the identifier with the specified key.

One you have this function, you can proceed with the rainbow table creation like you'd do for any other function.