Can one trade off the number of iterations for key length with the PBKDF2? When using the PBKDF2, is one taking on significant risk if one chooses to lower the number of iterations and choose to have very long keys?

Can I XOR my message with a a very long key (plain-text sized) generated using PBKDF2? Will this make XOR encryption as strong as a one-time pad?

When using the PBKDF2, is one taking on significant risk if one chooses to lower the number of iterations and choose to have very long keys?

Yes. PBKDF2's method of generating keys longer than the length of PRF output is... a really bad idea. I'll use the same notation that the Wikipedia article on PBKDF2 currently uses to explain why.

The derived key is defined to be $$DK = T_1 \| T_2 \| ... \| T_{dklen/hlen}$$ where $\|$ means concatenation.

The way each $T$ is derived is very important to this question.

Each one of these $T$ are calculated by iterative hashing. $U_1, U_2, U_3, ...$ each need to be computed sequentially for each block of output $T$. $U_2$ needs the result of $U_1$. $U_3$ needs the result of $U_2$. And so on. But each $T$ block does not have any dependency on the sequential hash computed by other blocks.

$T_2$ can be computed without calculating $T_1$. Each block is solely a function of the password, salt, cost parameter, and the output block number (subscript $i$ of $T_i$). Denoted in the article as $$T_i = F(Password, Salt, c, i)$$

If you use PBKDF2 in applications like password authentication or for deriving a stream cipher's key-stream then this is  a problem. The password storage example is easier to demonstrate as a problem.

Each block of output can be computed independently of the other. In that sense using PBKDF2 with $dklen = hlen * k$ is basically the same as publishing $k$ hashes for a single password. To test if a candidate password is correct, a password cracker does not need to compute all $k$ blocks of $T$. It suffices to compute only one of them.

If any one block doesn't match the hash you are trying to crack then you know the password is wrong. A hash based PRF with output length $m$ will only produce false positives with a probability of $2^{-m}$, low enough that we don't need to consider it in estimating the password cracker's cost-per-password-test.

As the legitimate party trying to hash a password by telling PBKDF2 to output $k$ times the PRF output length you are forcing yourself to do $c * k$ work. The password cracker on the other hand only needs to test one block and thus only needs to use $c$ work per guess.

The same logic applies to a PBKDF2 style stream cipher. To encrypt every block of plaintext you have to do $c$ work per block. Someone that wants to brute-force decrypt a single block of ciphertext, on the other hand, only needs to do work proportional to $c$ once per guess. You make the eavesdropper's job $k$ times easier than yours if you need to encrypt $k$ blocks. Not only that, once someone correctly decrypts one block they will know what password was used to compute every other block.

The bad guy never needs to do more than $c$ work to recover the password used to derive EVERY $T$ block. If you decide you want $k$ blocks of output and you compensate by decreasing $c$ by a factor of $k$ you are just making the hacker's job easier. This is a huge flaw in PBKDF2's design.

If you really needed to use PBKDF2 for key derivation (as opposed to Argon2 or scrypt), or something like it, then what you should instead do is use the CPU-time you've budgeted to password hashing to deriving one key with a length no greater than $hlen$. Call this the master key. Take all the resources in your budget and put them into computing just one block of output that's as strong as you can afford to make it. Your passwords will be $k$ times more difficult to brute force this way.

If you need more key-bits than $hlen$ then use your master key to derive child keys. You derive the master key from a password using a password-based KDF. Then you derive each child key using a key-based KDF.

A password-based KDF is designed to be expensive to compensate for passwords being weaker than keys. A key-based KDF lets you derive new keys from a single strong secret key very efficiently. (Or just use one key with an authenticated encryption algorithm. Which is what one normally would do.)

Always be wary of password hashing scenarios where you're incurring unnecessary (including redundant) expense for yourself. If you were planning to spend that much time hashing you should have spent it with a single stronger hash.

And speaking of stronger hashes you should be using Argon2 for now, both for password-database user authentication and for key derivation. Argon2, along with scrypt and "balloon hashing", is what's called a "memory-hard" algorithm. It is designed to make heavy use of RAM, in addition to CPU time (which is all PBKDF2 and bcrypt do for you). Memory-hard functions are thought to be more resistant to CPU-based, GPU-based, and ASIC-based password cracking.

Edit: Clarification in response to a comment

Suppose the absolute maximum amount of compute time (work) you can dedicate to password-stretching is some number denoted $W$. Consider $C_D$, the cost a defender pays to generate their entire derived key (per password entry), and $C_A$ the cost an attacker pays to test a candidate password.

We'll ignore the PRF parameter because the question is only about trading off number of iterations (c in the wiki article) and the key length (dklen in the article). Instead of worrying about dklen, hlen, and the number of blocks $T$ and doing the arithmetic to convert between each variable let's simplify things by measuring hlen in terms of PRF's output length.

Instead of dklen bytes and hlen bytes per block T, let's just say dklen and hlen are in units of $T$'s block size. This is easier because hlen is automatically 1 by definition. We can use $k = \lceil dklen / hlen \rceil$, the number of T in

DK = T1 || T2 || ... || Tdklen/hlen

The cost of generating one block T is however much work is needed to compute $c$ iterations of the PRF function. The cost to generate the entirity of DK is $k$ times the cost to generate one $T$. So we get $C_D = k \times c$.

For the defender to maximize the strength of their password-hash they will want to set $C_D = k \times c = W$. This is the trade-off between iteration count and key length. If you want to double your key length ($k = 2$) then you need to half $c$.

On the other hand the attacker doesn't need to generate all of DK. It suffices to generate any one $T$ and check that block to see if their password guess was correct. Therefore no matter what value $k$ is, $C_A$ always equals c.

The ratio $\frac{C_D}{C_A} = \frac{k \times c}{c} = k$. So if you double $k$ then you force the good guys to do twice as much work as the password crackers. If you triple $k$ then the defender does three times as much work per password tried as the bad guys. You want to minimize the ratio to give the attacker the smallest advantage. Therefore you are always better off using $k = 1$. That's why I said use a key-based KDF if you need more than hlen bytes of output.

Joke answer: Or you could set $k = 0$ and use Argon2 instead. It's stronger and it has the advantage that you don't need to think about this kind of stuff... as long as you follow the recommended procedure for choosing parameters.


Proof of the basic differential privacy composition theorem The basic composition theorem in differential privacy states, that if I have mechanisms $M_1$, which is $(\epsilon_1, \delta_1)$-differential private, and $M_2$, which is $(\epsilon_2, \delta_2)$-differential private, then $M=(M_1,M_2)$ is $(\epsilon_1+\epsilon_2, \delta_1+\delta_2)$-differential private. (It works for more than two mechanisms, but 2 is enough to illustrate my questions.)

For the proof of this theorem, most papers refer to Dwork et al. "Our Data, Ourselves: Privacy Via DistributedNoise Generation" (section 2.2 thm 1, see pictures below) and I have 2 questions on this proof.

The theorem is most of the time stated like above, without any restrictions on the mechanims. But am I right when I say: To be correct, we always(!) need to assume some form of independence? I.e. that the randomness in the mechanisms must be independent? It looks like that, when reading the proof, but it is never stated in the theorem statement (in all other publications I read), that got me worried...
There is one step in the proof that I can't follow: After they use the differential privacy-inequations for each single mechanism, they say:

  If we look at the additive contribution of each of the δ terms, of
  which there are T, we notice that they are only ever multiplied by
  probabilities, which are atmost one. Therefore, each contributes at
  most an additive δ.

I don't understand this part. The $\delta$ terms are not just multiplied by probabilities, but also by the $exp(\epsilon)$ factor. And this factor is not always smaller than 1. It would be helpful if someone can explain that step in the proof to me in more detail.

Thanks in advance for any help.

Here is the proof copied from the paper:

You are right, we need to assume the coin toss of mechanisms are independent to each other, as stated in the proof.

You are right, again. The proof in the paper seems to be problematic. Here's the modified proof:
\begin{align}
Pr[(x_1, x_2) \in S] &= Pr[x_1 \in S_1] Pr[x_2 \in S_2 | x_1 \in S_1] \\
&\le (\min(1, e^\epsilon Pr[x_2' \in S_2 | x_1 \in S_1]) + \delta )Pr[x_1 \in S_1] \\
&\le \min(1, e^\epsilon Pr[x_2' \in S_2 | x_1 \in S_1])Pr[x_1 \in S_1] + \delta \\
&\le \min(1, e^\epsilon Pr[x_2' \in S_2 | x_1 \in S_1])(e^\epsilon Pr[x_1' \in S_1] + \delta) + \delta \\
&\le e^{2\epsilon} Pr[(x_1', x_2') \in S] + 2\delta
\end{align}

The key to avoid the problem you stated is instead of using
$$
Pr[x \in S] \le e^\epsilon Pr[x' \in S] + \delta
$$
we use
$$
Pr[x \in S] \le \min(1, e^\epsilon Pr[x' \in S]) + \delta
$$
for the inequalities.


MD5 pre-fixing with an unkown postfix Is the MD5 prefixing attack still valuable to an attacker if he doesn't know the postfix of the string?

For instance,  what if the following sanity check was being used:

if attacker_controlled_sanity_code == md5(attacker_controlled + secret_key)

Clearly not an RFC compliant HMAC.  Despite the fact that the attacker doesn't know the entire md5'ed message mean that the prefix attack in md5 is useless?  Is there another problem with using a broken hash function in this way?

If the attacker does not know the value of $secretkey$, he cannot predict in advance the value of $MD5( attackercontrolled + secretkey)$.  However, what he can to is create two different messages $M$, $M'$ such that:

$MD5( M + secretkey) = MD5( M' + secretkey) $

He cannot predict this common value in advance; however, if he is able to submit $M$ and observe the generated tag, he immediately knows the tag for $M'$

This is a violation of the security properties that message authentication codes are supposed to provide.


Limitations of Elliptic Curve Cryptography? Simple question, what are the limitations of ECC, both in terms of application and how secure it is?

I heard that the NSA were able to read emails a few years back due to a backdoor they had discovered on a particular NIST elliptic curve. Is this something we can continue to expect, and what other potential drawbacks exist?

This is a rather open ended question, but I'll try to answer:

Limitations:

most ECDSA implementations require a secure random generator - if the same random value is reused (for different plaintext) then the private key parameter can simply be calculated;
ECDSA requires a hash function and cannot be (easily?) used for signatures with message recovery (then again, the signatures are generally much smaller than e.g. RSA in the first place);
ECC doesn't provide a direct method of encryption, instead EC-IES is commonly used - which means that that a key pair generation has to be performed and that the public key must be send along with the ciphertext;
ECC is much more efficient than RSA for signature generation and decryption, but it's still much slower than symmetric algorithms;
ECC requires some agreement on which type of curve and curve parameters to use;
support for ECC - especially more modern curves - is lacking from many libraries.

Security:

the fact that the calculations can be performed on relatively small integers (compared to e.g. DH/DSA or RSA) makes the algorithm rather efficient but it may also help quantum crypto-analysis;
many curves - such as the most used curves by NIST over prime fields - require additional verification of the public key to be performed;
RSA is much easier to understand than ECC (and a better understanding aids the security of protocols and implementations);
RSA is still much better researched, e.g. with regards to side channel attacks.


Proof of knowledge outside of Zero Knowledge Are there interesting protocols for which proof of knowledge is required, but not zero knowldege?

Is Proof of Knowledge an interesting proof by itself?

If you don't have any zero knowledge requirement, then a proof of knowledge is achieved by just having the prover send the "witness" in the plain to the verifier. Thus, no, a proof of knowledge that has no privacy requirement is not interesting.

Note that it can be interesting to have a witness indistinguishable proof of knowledge, or a witness hiding proof of knowledge. These are not full blown zero knowledge but have meaningful privacy requirements.

The best place to read about witness indistinguishability and witness hiding is in Oded Goldreich's book on the Foundations of Cryptography (Volume 1). (Note the errata on strong witness hiding.) You can also look at Uri Feige's PhD Thesis, which is extremely clear and easy to read (but less general than the treatment in the Foundations of Cryptography).

The reason why one would want these not "full blown" zero knowledge notions is that it is possible to achieve them more efficiently in some sense. In addition, they can be used as important stepping stones to full zero knowledge.


tripartite diffie hellman with Weil pairing I try to understand how the tripartite Diffie-Hellman key exchange works.
I read Joux's paper for this: https://www.semanticscholar.org/paper/A-One-Round-Protocol-for-Tripartite-Diffie-Hellman-Joux/845e96c20e5a5ff3b03f4caf72c3cb817a7fa542/pdf

However on page 388 he states the following equality which I don't see why it is true:
$F_W(a,P_b,Q_c) = F_W(a,Q_b, P_c)$

where $F_W(x,y,z)= e_m(y,z)^x$.
For me the first value of the equality is the inverse of the second one?

This does indeed appear to be a typo. Using that $e_m$ is bilinear and alternating, one calculates
$$\begin{align*}
F_W(a,P_b,Q_c)
\;&=\; e_m([b]P,[c]Q)^a
\\&=\; e_m(P,Q)^{abc}
\\&=\; e_m(Q,P)^{-abc}
\\&=\; e_m([b]Q,[c]P)^{-a}
\\&=\; F_W(a,Q_b,P_c)^{-1}
\text.
\end{align*}$$

(However, note that these are only different if the order of $e_m(P,Q))$ does not divide $abc$; in particular, we need $e_m(P,Q)\neq1$.)


Adversary model for malicious but selfish adversaries? Covert adversaries have the property that they may deviate arbitrarily from the protocol specification in an attempt to cheat, but do not wish to be caught doing so.
Does this model includes also the case in which  adversaries do not cheat in case it does not maximize their utility function, e.g., they lost an escrow?

There is a close connection between covert adversaries and selfish ones. In particular, if you know the utility function of the selfish adversary, then you can compute the deterrent factor that you need for covert adversary. However, it is important to note that the model of covert adversaries considers corrupt and honest parties, where here corrupt would mean selfish. It does not cover the scenario of all parties being selfish (and so all parties may deviate from the specified protocol if it is in their interest).

In order to see how to model this scenario, a good starting point is Rationality and Adversarial Behavior in Multi-Party Computation by Lysyanskaya and Triandopoulos (from CRYPTO 2006).


Indistinguishability game hop I am trying to prove that changing an input in a security game from a randomly permuted set to a set that is permuted using a pseudorandom permutation (PRP) results in a negligible distinguishing advantage between the two games. Does anyone know of any good examples in the literature of this kind of game hop. I have already read through the Shoup 2006 paper on games.

While I cannot point you to a specific paper that works as a great example for this technique, the idea is quite simple.

Assume two distributions $X,Y$ which have the same support, so random variables distributed according to one of these distributions are drawn from the same set.
Now assume you got a probabilistic adversary $A$ that takes as input $misc$ and a value $x$ that drawn according to $X$ and tries to solve some problem. Here $misc$ covers any additional inputs. As $X$ and $Y$ have the same support, we might also chose $x$ from $Y$ -- $A$ should at least accept such $x$ as input.

Let's switch to the games. Assume you got two games. In both you generate $misc$ the same way. But the games differ in how $x$ is chosen. In game 1 you chose $x$ according to $X$, in game 2 you chose $x$ according to $Y$. You might already see that if the success probability of $A$ differs, depending on if he plays in game 1 or in game 2, we can use this to distinguish the two cases, i.e. we can use this to decide from which distribution $x$ was chosen.

Say $A$ wins in game 1 with higher success probability than in game 2. Then we can built a distinguisher $D$ that takes a value $x$ and outputs 1 if $x$ was chosen from $X$ and $0$ if it was chosen from $Y$. $D$ simply runs $A(misc,x)$ and outputs 1 if $A$ succeeds. $D$ will distinguish the two cases exactly with $A$'s difference in success probability depending on which game he plays.

Hence, we can argue that if $X$ cannot be distinguished from $Y$ with probability greater $\epsilon$, the difference in $A$'s success probability between game 1 and game 2 must be limited by $\epsilon$.

That's how one game hop works. You can extend this arbitrarily. The important thing is that between two consecutive games you must only change the distribution of one of $A$'s inputs.


Computing IV for CBC from PBKDF2 + HKDF Note that this question is somewhat similar to Can I use my random IV (for AES) as a salt for PBKDF2?

My current encryption format computes two random PBKDF2 salts (encryption and HMAC, 8 bytes each) and also a random IV (16 bytes) to use with AES-CBC. This adds 32 bytes to the final message, which can be a lot for short messages (plus another 32 bytes of HMAC and a couple of bytes of "header").

My thinking is that I can generate all three values (IV and two keys, 640 bits) from the salt and password:

Generate a 16-byte salt
Use PBKDF2 (for some number of iterations) to stretch salt+password into 512-bit pseudo-random key (PRK).
Use HKDF-Expand on PRK to generate IV, enc_key, and hmac_key.

The full specification is available at RNCryptor-Spec v4.

I believe that generating the IV this way is secure, and possibly marginally more secure than generating and sending a random IV, since the attacker cannot manipulate the IV if it is computed from the PRK. The inclusion of a 16-byte per-message random salt means that key/IV combinations should not repeat any more often than for a randomly-selected IV.

OpenSSL's enc format uses a somewhat similar approach, but I have never seen a cryptanalysis of it. TLS 1.0 computed the IV in a non-random way which could be manipulated by the attacker, which led to vulnerabilities (however, my approach includes a random seed, and I believe is not vulnerable to that, even if an implementation fails to verify the HMAC).

This approach is space efficient and seems possibly more secure than an independent random IV. However, I can't find any reference that explicitly approves it (other than Thomas Pornin's answer linked above, which at this point is good enough for me).

Are there problems with using a KDF to generate the IV with a random salt? Is there any document that explicitly evaluates it?

If I'm reading your specs correctly, you do this:
$IV||VAL||K_E||K_A=KDF(PBKDF(PW,Salt,Iterations))$. (Order doesn't matter here)

As far as I know this is common practice and shouldn't pose any security threats, as the IV is in fact unpredictable as it needs to be.

If I may I'd suggest you using EAX, CCM GCM mode if available, as this is easier than using CBC+AES and HMAC. If you can't use EAX/GCM/CCM, you may want to use CTR, as this poses you at less severe constraints regarding the IV (unique instead of unpredictable).


How do you find the preimage of a hash? What is a preimage and how do you find a preimage of a hash?

In both mathematics and cryptography, given a function $H$ from set $A$ to set $B$, and an element $b$ in $B$, a preimage of $b$ by $H$ is any $a$ in $A$ such that $H(a)=b$.

In cryptography, a public function $H$ from set $A$ to finite set $B$ is:

First-preimage-resistant when for a given random $b$ in $B$, it is hard to exhibit a preimage of $b$, that is, $a$ in $A$ with $H(a)=b$.
Second-preimage-resistant when for a given random $a_0$ in $A$, it is hard to exhibit another preimage of $b=H(a_0)$, that is, $a$ in $A$ with $a\ne a_0$ and $H(a)=H(a_0)$.

A preimage can in principle be found by trying various values of $a$ in $A$ (other that $a_0$ for second-preimage), and computing $H(a)$ until it matches $b$ (the given $b$ for first-preimage, or $b=H(a_0)$ computed from the given $a_0$ for second-preimage). Depending on the definition of $H$, there can be better methods.

A common design goal of practical cryptographic hash functions is that the expected effort to find a preimage (of either kind) is not much less than $|B|/2$ times the effort for computing $H(a)$ once, where the notation $|B|$ designates the number of elements in the set $B$. When $B$ is the set of exactly $n$-bit bitstrings $\{0,1\}^n$ (as is common for cryptographic hashes) the quantity $|B|/2$ becomes $2^{n-1}$.


About the security of GnuPG private key on-disk storage GnuPG on-disk storage of secret key material is encrypted with AES-128, with an encryption key generated via an iterated and salted SHA-1 hash of the given passphrase.

Is this usage of the SHA-1 hash function secure, and, if so, will it remain secure, even in the distant future?

It is likely secure, yes, when it comes to SHA-1.

The S2K function, as you mention, simply repeatedly inputs the 8-byte salt and encoded passphrase  into the ongoing hash function until a certain number of bytes has been processed (the work factor for this function). Then it produces a key that is smaller than the hash output size.

Now this output is an AES key, and we can assume that this key cannot be retrieved, nor is it stored. As you control the salt and secret key, it is impossible to use the collision weakness of SHA-1: even a collision in the output of S2K would be useless. Similarly, a pre-image attack on S2K is useless as well, as the output of the S2K hash is simply not available.

The only possible issue could be that SHA-1 is shown to have such short cycles that multiple inputs could produce the same S2K output. In that case it might be easier to find a matching input, as multiple input values would match. But there is the salt, the relatively short password, the high cycle size of SHA-1 etc. that makes this highly unlikely; this is really grasping at straws.

That all said, S2K is far from perfect. SHA-1 is easy to put in hardware (if it is not already there in current CPU's), S2K doesn't use memory to make e.g. hashing password on a GPU or other specialized hardware tough.

The biggest weak point is and remains the password. I'd rather spend my time making sure that the user is pushed really hard to use a strong password. Because if the password is much smaller than 50 bits then all the cryptography in the world is not going to matter.

Dictionary / brute force attacks on the password will always be more efficient, basically. Spend your time avoiding those.


How to compare two CSPRNGs? Let's say I am given to CSPRNGs: RNG1 and RNG2.
I want to select the best one of the two for cryptography.
How should I do it?
Any of the two RNGs can be initialized with a secret key during
tests and any number of bytes can be generated from each RNG.
Are there statistical test suites already out there for this purpose?

The best one is the most reputable one. That is, the one which had been widely used, studied, and standardized.
If both fall into that class, choose the one which uses more secure or larger-state primitives under the hood.
Example: when comparing the NIST-standard Hash-DRBG using SHA-256 versus HMAC-DRBG with SHA-1, I would personally choose the first due to larger state and security margin of SHA-256.


Are longer passwords really safer against brute force attacks? If we take two password strings of different length and attempt to bruteforce match them, it is obvious that the longer one will take longer to crack on average. However if we assume that when selecting a password our maximum password length is given ,does it really matter how long the actually selected password is, if it is then padded to the maximum length?

Example:

Max Length: 10 characters

Password A: "abc" -> padded to "abc0000000"

Password B: "abcdefgh" -> padded to "abcdefgh00"

Now we have two strings of equal length, which theoretically should both be equally hard to crack, despite the actual password entered being shorter. This assumes that the padding technique is of course kept secret.

Is there anything wrong with this reasoning? Is this actually done in practice? If not, why not?

If we take two password strings of different length and attempt to bruteforce match them, it is obvious that the longer one will take longer to crack on average.

Actually, that might be obvious to you, but it's not true.

A brute force search is one where an attacker has a long list of passwords, and tries them in succession.  Now, if the attacker is at all intelligent, they'll put passwords that are likely to occur near the front of the list, and unlikely ones near the rear.  That is, the 'goodness' of a password is not its length, but instead how unlikely it is to guess.

In particular, a password of 123456789 is considerably worse than a password of 2u,7J$n even though the latter is two characters shorter.

And, because the entire strength of a password is how unlikely it is to be guessed, a fixed transform (like you suggest) will add no strength.  If the attacker guesses the real password abc, they'll run it through the known transformation, yielding abc0000000 and check that against the underlying password logic; that has the same likelihood to succeed as it would have been if we had not added the 0 characters.


Does the following Diffie-Hellman problem hold in bilinear groups $G\times G \rightarrow G_T$ For every PPT distinguisher A there exists a negligible function $neg(·)$ such that for all $\lambda$

$|\Pr[A(1^\lambda, g,g_1^a,g_1^b,g_1^{ab}) = 1] - \Pr[A(1^\lambda, g,g_1^a,g_1^b,g_1^z) = 1]| \leq \textsf{negl}(\lambda)$

where $g$ is a generator of group $G$ of order $p$ where $p$ is a prime of length approximately $\lambda$, $g_1 = g^r \in G$, and $r,a,b,z$ are randomly chosen from $Z_p$

Hint: suppose we modify the problem so that $r, a, b, z$ are selected uniformly randomly from the interval $[1, p-1]$; how do the probability distributions of $(g^{ra}, g^{rb}, g^{rab})$ and $(g^{ra}, g^{rb}, g^{rz})$ compare?

Hint: if we actually select $r, a, b, z$ from $\mathbb{Z}_p$, what is the probability that at least one of them are selected outside the interval $[1, p-1]$?  Can you show that this probability is negligible?


Can AES-CBC be safely used in combination with RSA, or must it be CBC-MAC? The plan is to encrypt files using an AES-256 in CBC mode secret key. The secret key itself will be encrypted with a RSA 2048-bit public key.

Is using AES-CBC sufficiently secure if used in conjunction with RSA?

Or must the files be authenticated with AES as well using CBC-MAC, in addition to encrypting the symmetric key with RSA and the data with CBC?

It may be assumed that integrity is required for both the symmetric key and the data.

It depends on the system if RSA + CBC mode is secure. It could be but better options are available.

CBC mode, if correctly applied, can certainly provide confidentiality of the message. In that case however you must make sure that padding oracles and - more generically - plaintext oracles do not apply to CBC mode. If RSA with PKCS#1 v1.5 padding is used - often the default - then padding oracles may also apply to RSA (Bleichenbacher attack).

CBC mode doesn't supply integrity / authenticity of the plaintext message. Although an attacker cannot flip each individual bit (like with CTR mode), an attacker may still garble plaintext blocks by changing, moving or inserting/deleting  blocks of plaintext. Then again, as anybody with the public key can perform RSA encryption. So an attacker may as well generate a complete message and encrypt that. The addition of CBC-MAC or authenticated modes of encryption like GCM encryption won't help you achieve authenticity / integrity of the message.

If you want to achieve integrity / authenticity then it is recommended to first sign the message with a private key and then encrypt both using hybrid encryption. If you would not encrypt the signature then you would loose the anonymity property and you could leak the hash over the message. You would of course need a key pair generated by the sender for that, and the receiver should trust the public key of the sender.

CBC mode would still be vulnerable against padding oracles this way so although you could use it then you are better off using e.g. AES in counter mode (making sure that the IV is properly random or at least unique).

In the end I'd recommend something like RSA-OAEP (or RSA-KEM if you can find a good implementation) with CTR mode. If you need integrity and authenticity then perform RSA-PSS with a SHA-2 512 or SHA-3 512 bit hash and encrypt both the message and the signature.

Notes:

Performing encrypt-then-sign - where the ciphertext is signed - is more dangerous as anybody could replace the signature. This is a problem if the keys of the attacker are trusted by the system.
Your security parameters aren't all that well balanced; RSA-2048 has a strength of about 112 bits (according to NIST, 2017). Using that with AES-256 with a strength of 256 bits is fooling yourself. I'd use a combination of AES-128 with a 3072 bits key or use AES256 and a much higher key size such as 8192 bits or beyond. If you want optimal security you could think of switching to Elliptic Curves or an asymmetric encryption algorithm that delivers post quantum cryptography.


Cracking lowest plaintext bit in Padding oracle attack with PKCS#5 I have been working on a C implementation of padding oracle attack on a block encryption algorithm using CBC mode of operation. I understand the concept fine but I can't seem to find an answer to the following question(despite looking up similar questions on stackoverflow and this site):

When we send a Ciphertext block concatenated at the end of a block we manipulate to the padding oracle, why do we assume that first success means that the XOR operation produced a 1 and not 2,3,4,5,6 or 7 for that matter?

To add more information for those not in the know, PKCS#5 is a padding scheme for plaintexts of blocksize 8 bytes where the last block contains n number of padding bytes each containing the value n. So, lets say we send (C1||C2) where C2 is the original Ciphertext and C1 is a block whose lowest byte we vary from 0 to 255 so as to get a successful validation from the padding oracle. A successful validation, in my opinion, means that the padding is correct, i.e. the resultant plaintext byte is 1 if there were just 1 padding byte and 2 if there were 2 and so on...

Why do all the implementations of this attack assume that the first success from Oracle means we got a 0x01 in the last byte from the oracle? Is it because the probability of getting a 0x02 in the last byte and the penultimate byte while only varying the last byte is lower? If yes, does that mean there may be instances where this algorithm would fail to decode ciphertext?

Why do all the implementations of this attack assume that the first success from Oracle means we got a 0x01 in the last byte from the oracle? Is it because the probability of getting a 0x02 in the last byte and the penultimate byte while only varying the last byte is lower?

Largely, yes.  Remember, our general assumption is that an attacker is happy with an attack that only works most of the time.  In this case, assuming that the attacker has no initial information about the plaintext block under attack, then a random C1 that causes us to have valid padding would correspond to an 01 padding byte with probability circa $1 - 1/255$ of the time.

In addition, if you find a C1 that might reveal the last byte, and might have a longer padding pattern, there's a very easy test; try C1 with the penultimate byte modified; the resulting decryption will still have valid padding if it had an 01 padding byte, and have invalid padding if it was anything else; hence it would be easy to catch.


secret sharing of product of 2 numbers Does evaluating the products of shares $a_jb_j$ give a secret sharing of $ab$?
I think it's a no, but I am not sure on how to prove it.

The primary secret sharing methods in use for multiparty computation today are Shamir's and additive. I'm going to assume that you understand both.

Additive
No. When you go to reconstruct, you would have (simplified for 2 parties) $a_1b_1+a_2b_2\neq(a_1+a_2)(b_1+b_2)$. To prove it in the general case you would have to extend that analysis to $n$ parties.

Shamir
Yes and no. In Shamir's we say that $a_i=p(i)$ for some polynomial $p$ and $b_i=q(i)$ for some polynomial $q$. Now lets assume that $p$ is used to share $s$ (i.e., $p(0)=s$) and $q$ is used to share $t$. It is the case that $a_ib_i=(p*q)(i)$ and $(p*q)(0)=st$. So, $a_ib_i$ is indeed a valid share from some polynomial which evaluates to $st$ at $0$. There are, however, two problems.

The polynomial $(p*q)$ does not have random coefficients. The coefficients will depend on each other
The degree of the polynomial changes. Lets say that both $p$ and $q$ have degree $r$ (thus it takes $r+1$ shares to reconstruct the secret). The polynomial $(p*q)$ has degree $2r$, so it would take $2r+1$ shares to reconstruct $st$.

For these reasons, MPC protocols which use Shamir have a multiplication protocol which fixes these issues.

Another possibility
I don't even know if this is a secure secret sharing method (I'm hoping someone can comment). But you could use multiplicative secret sharing.

Fix a multiplicative group, say $\mathbb{Z}_p^*$.

Let $a_i$ be shares of $s$ such that $s=\displaystyle\prod_i(a_i)$ and similarly $b_i$ are shares of $t$. Then thanks to the commutativity of multiplication $a_ib_i$ would be a multiplicative share of $st$


SRP-6 vulnerabilities when N is small I'm one of the developers of an application which uses SRP-6 as the authentication mechanism. The authentication part of the code is very old and uses N with only 256 bits (all arithmetic is done in modulo N). After receiving reports of stolen passwords we upgraded to SRP-6a with the size of N 1024 bits.

We are still investigating (both on the client and server side) how the passwords were stolen/broken. I know that SRP-6 with such a low N value is vulnerable to man-in-the-middle attacks and "two-for-one" guessing (SRP-6 Improvements and Refinements paper by Thomas Wu). The attacks were probably made only on the client side, but this made me very curious.

Would it be possible for an attacker to launch an offline dictionary/brute-force attack on the B public key:

  B = (k*v + g^b % N) % N
  N - 256 bits long
  b - 152 bits long (random private key - generated using OpenSSL library)

Is it possible with modern technology? Could the attacker somehow predict or find out the random value b, extract v=g^x % N, then perform a discrete logarithm and find x?

Solving a 256-bit discrete log is absolutely doable, and quite quickly, these days; there are public tools that can do it, though they may require some expertise to use.

On that note, even a 1024-bit modulus is not particularly conservative: it is generally agreed that well-funded organizations today could break logs of that size as well, but at a very large cost. The current minimum recommended modulus size for RSA, Diffie-Hellman, SRP, etc is 2048 bits.

That being said, I would also put my money on a client or server-side break-in before arriving at the conclusion that the log was being broken.


Is knowing the distribution of input domain only way to do cipher text only attacks? Imagine there is a $n$ bit block cipher. The attacker has harvested some how all possible $2^n$ cipher texts for some given key. Without the knowledge of the distribution of input domain as in frequency counts or some statistical information of input data. Is it possible to perform ciphertext-only attacks? Are there any examples?

Edit: Stated in other way, what does it take to launch ciphertext-only attacks on block ciphers? Can you provide any examples?

Since for any fixed key the encryption algorithm is a bijection from the set of $n$-bit strings onto itself, the set of all possible ciphertexts is regardless of the key and algorithm always the set of all $n$-bit strings and does not provide any information.


Is RC4 a problem for password-based authentication? This is a follow-up question to Does TLS use RC4-drop[n]?.

As mentioned in section 6 of RFC4345, there are weak distinguishers for RC4 keystreams available that even work for keystreams that originate from different keys, and regardless of the distance from the start of the keystream. Doesn't that make an attack on schemes that send user passwords in RC4 protected connections?

I'm thinking about protocols that always send the password at a well known offset, e.g. TLS protected IMAP and SMTP.

Theoretically, it should even be possible with an HTML authentication form, but the position of the password in the response might not be as obvious in that case.

Has anybody ever tried to recover a password from a number of RC4 protected IMAP or (authenticated) SMTP connections? Because of the BEAST attack, many mail services now default to RC4 for encrypting user connections (which always include the credentials at a fixed offset), and depending on the mail client used, authentication might happen frequently (especially IMAP clients often keep a number of IMAP connections open, which might be forced to reconnect even more frequently by an active attacker).

By George, you're on to something.

To answer the question you asked, I don't know of anyone actually attempting to recover a password this way, or it even being discussed.  However, it does appear to be feasible, given enough encrypted streams.

How many are enough?  Well, I've started running a few simulations; preliminary results indicate that with perhaps 2 billion encrypted streams that encode the same password, the attacker may be able to deduce enough information to narrow possible passwords to a reasonably small set.

I'll update this answer as I get more precise information on the number of streams needed; however, I've seen enough to be fairly confident that this attack can work.

UPDATE

I have experimentally verified the fact that you can decrypt RC4 if you get the same message encrypted enough times, albeit with somewhat more than I suggested above.  In particular, I encrypted a 16 character password using RC4/DROP-512.  With 8 billion encrypted messages (with the RC4 key for each message being chosen randomly and independently), I was able to successfully recover the exact password by analyzing the statistics for the streams.

I'll be writing up an eprint article detailing my observations.


Shared modulus attack on RSA Consider a scenario in which a group of people use a common modulus $n$ in the textbook RSA crypto system,
where $n=pq$, $p$ and $q$ are large distinct prime numbers.

Is there any chance for an attacker outside the group to view the original message?

Let me explain my solution. Assume the group members receive the same message. So $c_1= m^{e_1} \bmod n$ and $c_2= m^{e_2} \bmod n$. Assume $e_1$ and $e_2$ are co-prime. So if we can find $x, y$ satisfying $e_1x+ e_2y=1$ then an attacker can view the original message. Am I correct?

When you have a RSA key pair, it means that you know the private key (otherwise this is not "your" key pair). The private key format, normally, contains the two factors $p$ and $q$ (at least so it goes with PKCS#1). Even if all you have are the modulus $n$, the public exponent $e$ and the private exponent $d$, the factorization of $n$ can still be worked out from $e$ and $d$ (see this answer for a detailed description). The bottom-line is that if two people "share the same modulus" then they also both know the private keys of each other. In effect, there is only one actual key pair and they both know it.

The "shared modulus" situation is thus mostly irrelevant.

A second, most important point is that what you described ($c = m^e \pmod n$) is not RSA. It is often, confusingly, called "textbook RSA"; in the same way, a car engine, resting on the floor, could be called a "textbook Ferrari". RSA, as an asymmetric encryption algorithm, is a combination of several operations; the modular exponentiation is the most CPU-intensive of them, but not the only one, and the other operations are very important for security. In the case of PKCS#1, what enters the exponentiation is the padded message; the padding includes random bytes.

Even if you imagine a setup where the same message $m$ will be encrypted twice, once with $(n,e)$ and once with $(n,e')$ (same modulus, but distinct exponents), what will be really exponentiated will be, in the first case, a padded value $x$ that includes $m$ and some randomness, and, in the second case, another padded value $x'$ that includes $m$ and some other, distinct randomness. This would avoid the reconstruction of $m$ by an attacker observing both encrypted messages.


RSA Encryption and Signature - Weak Padding Assume that I have an plaintext $m$ and it is padded with $randompad||00||m$ and then it is encrypted with RSA and a public encryption key so we get the encrypted $Sm$.

Then to assure its integrity we use our signature key and we publish the verification key. The input to the signature is this (so again we have padding) $01||Sm$. Then the signature $Sign$ is calculated and we send both $Sign$ and $Sm$ to the receiver.

Is there anyway somebody could change our message assuming that he knows the public encryption key and the verification key as well?

In order to verify it or decrypt it all the padding bytes on the left are discarded.
I've been reading the RSA-survey but I can't find any attacks that would work, only if somebody made us sign another message like a blind attack. Do you have any suggestions? Would a key-only attack work in this case?

Yes, there is an attack that has a fair chance of success, like $2^{-8}$ per $Sign$ (and perhaps $Sm$) submitted; or even more depending on exactly how the encryption padding is removed/verified. The attack does not require submitting a message for signature to a party knowing the signature private key. I consider the attacker successful whenever she manages to submit something that the receiver accepts, deciphering and recovering the message $m$, even when the attacker gets no clues about $m$.

More hints: The attacker needs no other input than the signature verification public key, and perhaps the size of the encryption modulus. The attacker's expected cost for a success may be $2^{15}$ modexp (more or less depending on exactly how the signature padding is removed/verified, and for some interpretations of that how much the bit size of the signature modulus exceeds the bit size of the encryption modulus, rounded-up to the next multiple of 8).

The big picture: the attacker repeatedly chooses $Sign$ arbitrarily, and weeds out some appropriate subset of them for submission, by making just what the receiver would do, as far as the attacker can; because there is (explicitly at least) little more than one byte (the $01$) of verifiable signature padding, a sizable fraction of $Sign$ are an acceptable signature for some $Sm$, and (critically) the adversary can find that $Sm$. The adversary submits those $Sign$ (and the associated $Sm$ if that's part of the protocol) that pass that (very weak) signature verification test; and because there is (explicitly at least) little more than one byte (the $00$) of verifiable message padding, a sizable fraction will also decipher to some $m$.

Like most simple attacks exploiting a lack of enough padding (here: in a signature scheme allowing message recovery), the cost of the attack (expressed in number of modular operations) is mostly independent of the size of the signature modulus.

To better grab how the system and attack works, we need to further define what the parameters are. Let the signature modulus be $N$ of $n$ bits, and the encryption modulus be $N'$ of $n'$ bits. The result of the encryption step is a number up to $N'-1$, thus $Sm$ is a bytestring of $\lceil n'/8\rceil$ bytes when it is used in the signature padding $01||Sm$, which has one more byte. Thus $01||Sm$ is a bytestring representing an integer of exactly $\lceil n'/8\rceil\cdot8+1$ bits, and the cryptosystem can sign the result of any encryption when $N\ge(2^{\lceil n'/8\rceil\cdot8}+N')$, including but not limited to if $n\ge(\lceil n'/8\rceil\cdot8+2)$ bits. Perhaps the system is intended for $n=(\lceil n'/8\rceil\cdot8+8)$. If $n$ was much more, the signature padding would be shown as $00..01||Sm$.

We must also reconstruct or assume what exactly the receiver does:

receive $Sign$;
perhaps (that's untold) reject the submission if $Sign\ge N$;
compute $Sign^e\bmod N$, making that a bytestring of $\lceil n/8\rceil$ bytes;
reject the submission if the leftmost byte of that is not $01$;
consider the remaining bytes of the bytestring of (3.) to be $Sm$ (or if $Sm$ is explicit in the receiver's input, fail if the remaining bytes do not match $Sm$);
perhaps (that's untold) reject the submission if $Sm\ge N'$;
compute $Sm^{d'}\bmod N'$ and convert that to a bytestring of $\lceil n'/8\rceil$ bytes;
perhaps (that's untold) reject the submission if the leftmost byte of that bytestring is not $00$ (that corresponds to checking the few zero bits that customarily are on the left of $randompad||00||m$ in order to make the corresponding integer less than $N'$);
assuming that $m$ has fixed width $w$ bytes, reject the submission if the $(w+1)$th byte from the right of the bytestring of (7.) is not $00$ (or, assuming that $m$ is a bytestring of variable width not containing $00$ such as a C or UTF-8 string, recover $w$ and $m$ by scanning that bytestring from the right until a $00$ is found, rejecting the submission if the bytestring contains no such byte);
Having found no rejection reason, accept the message $m$ extracted from the bytestring of (7.).

The attack should be obvious by now: the attacker repeatedly selects $Sign$ e.g. randomly in $\{0\dots N-1\}$, and performs (3.), until the bytestring obtained has a $01$ on the left so that it pass (4.), and the remaining $Sn$ pass (6.) if applicable [note: I have not included (6.) in my estimate of the attack's cost, but the increase would be by a factor of $2^{\lceil n'/8\rceil\cdot8}/N'$, which is less than $2^8$]. The attacker submits those surviving $Sign$ (and perhaps the matching $Sn$ if that's required). In the first option of (9.), the odds of success of the attacker are $2^{-8}$ per attempts (and more in the other option), assuming no step (8.).

A speedup (and a practical attack even when $n\gg n'$) is possible when $e$ is very small, like $3$, $5$, $17$; that is left as an exercise to the reader. The conclusion should be: use strong padding (not: do not use very small public exponents).


Cost of attacking Mobile OTP with a fake server You want to obtain a 74-bit secret $K$. There is an oracle that will provide you with the following value for several values of $T$:

$$(\mathrm{MD5}(T_{\mathrm{dec}}||K_{\mathrm{hex}}))_{\mathrm{hex}}[0..5]$$

$T_{\mathrm{dec}}$ is the number of seconds since 1970 divided by 10 (i.e. it's the current time in units of 10s), written out in decimal notation and encoded into bytes in ASCII;
$K_{\mathrm{hex}}$ is $K$ written out in hexadecimal notation and encoded into bytes in ASCII;
$x_{\mathrm{hex}}[0..n-1]$ means the first $n$ hexadecimal digits of $x$.

In other words, the oracle provides the first 6 digits of the MD5 hash of a time-dependent string concatenated with the secret.

The practical application is that you are impersonating a mobile OTP server, and the oracle is a client tricked into attempting to authenticate with you. $K$ is the client secret (in-device secret plus user PIN) which you are trying to obtain. And this question is inspired by Mobile OTP - Secure? on Security Stack Exchange.

Since each value from the oracle provides 24 bits, with $4$ values from the oracle, you should have enough information to brute-force $K$. (Assume $T$ is perfectly known, i.e. your clock is synchronized with the client's, but can't influence it.) The cost of a brute-force search is $2^{74}$ MD5 computations.

Are there known weaknesses that make finding $K$ less expensive? (We're taking the MD5 hash of several strings with a common prefix and a common suffix.) Would more values from the oracle help?

If  $\mathrm{MD5}$ had been computationally indistinguishable from a random oracle (for the fixed message size under consideration), there would demonstrably be no method better than brute force search of $K$ to recover $K$ or otherwise predict the next outputs of the function.

However, $\mathrm{MD5}$ is known to fall short of this goal. In particular, we know how to quickly make 1-block collisions, and there is a theoretical preimage attack slightly better than brute force.

Thus there is no insurance that the function described is secure, but I do not see that any current result on $\mathrm{MD5}$ endangers it. Perhaps there is a differential attack of some kind with enough $(\mathrm{T}, (\mathrm{MD5}(T_{\mathrm{dec}}||K_{\mathrm{hex}}))_{\mathrm{hex}}[0..5])$ pairs, but I do not see that as a practical threat even with thousands on pairs, in light of the short key $\mathrm{K}$.

On the other hand there are several truly worrying aspects of the scheme:

there is no salt (the same $\mathrm{K}$ and $\mathrm{T}$ yield the same cryptogram regardless of user or other parameter);
there is no other attempt to slow down brute force search;
the 74-bit key is short.

These three cardinal errors combined make the scheme quite vulnerable to a brute-force attack. Assuming $n$ users have used their authenticating device at the same known time $\mathrm{T}$ once, and have used it at three other known times (not necessarily the same among users), and the cryptograms have been gathered, the key of one user is recovered with better than 50% odds, and fair confidence against false positive, after an effort of $0.7 \cdot 2^{74}/n$ $\mathrm{MD5}$ rounds. That's simply by trying keys for the common $\mathrm{T}$ and, in the rare case that the result is a match for a user, further testing the key with other known data points for this user.

Also, the key generation is not specified here. If the key was not true random but, say, a password, or generated by a poorly seeded RNG, that would be a further weakness. Update: We learn that $K$ consists of 64 bits chosen at random, plus 10 bits from a 4-digit $\mathrm{PIN}$. If the users choose their $\mathrm{PIN}$, then $0000$, other $\mathrm{PIN}$s with 4 identical digits, and birth years, are going to be strongly overrepresented. That can be used to speed up a brute-force attack, significantly.

Rather than this scheme, it would be better to use industry standard primitives fit for the job, like $\mathrm{PBKDF2}$ or, better, $\mathrm{Scrypt}$. At the very least, the user ID or some form of salt should be part of the cryptogram's input.

Update: For example, with $\mathrm{PBKDF2}$ and keeping $\mathrm{MD5}$ as the underlying primitive, the function generating the one-time password could be replaced with $\mathrm{PBKDF2}(\mathrm{PRF}\leftarrow\mathrm{HMAC\_MD5}, \mathrm{Password}\leftarrow K||\mathrm{PIN}, \mathrm{Salt}\leftarrow\mathrm{UserID}, \mathrm{Count}\leftarrow 512, dkLen\leftarrow 3 \mathrm{bytes})$

Rationale: Using $\mathrm{Salt}$ (e.g. a User ID) insures that a brute force attack can not be leveraged against multiple users, avoiding the $/n$ factor above. The $\mathrm{Count}$ parameter is a compromise between increasing the effective key length (doubling $\mathrm{Count}$ has the same effect on a brute force attack as growing $K$ by one bit), and the computational cost of an authentication (growing linearly with $\mathrm{Count}$ on both the device and server side). With the given parameters, assuming 1000 users in the same 10 seconds, the scheme is about a million times harder to break than the original. Using $\mathrm{HMAC}$ increases assurance against theoretical attacks, even though $\mathrm{MD5}$ is less than perfect.


How to reverse x XOR (x >>> 1) XOR (x >>> 2) Short version:

What is the inversion of $f(x) = x \oplus (x \lll 1) \oplus (x \lll 5)$ when the last 4 bits of $x$ are known?

Long version:

Hi,

a friend a mine and I are giving each other crypto challenges to break. This time, he gave me a "one-way" function which is defined as followed:

$R(x)= x \oplus (x \lll 1) \oplus (x \lll (x\ AND\ 15)) \oplus ((x\ AND\ 15) \lll 1)$

Or if you define $i = x\ AND\ 15$:

$R(x) = x \oplus (x \lll 1) \oplus (x \lll i) \oplus (i \lll 1)$

Given you can bruteforce $i$ (since it is ranged from 0 to 15), there are a few things you can do:

For $i = 0$: $R(x)$ can be reduced to $R(x)=x \oplus (x \lll 1) \oplus x \oplus (i \lll 1)=(x \lll 1) \oplus (i \lll 1)$ which can easily be reversed.

The same applies to $i = 1$ which allowes you to reduce $R(x)$ to $x \oplus (i \lll 1)$.

However, things get more complicated for $i \ge 2$ since the xor's no longer negate themselves, but since you "know" the last 4 bits of $x$, you can try to reverse the function by building upon $i$:

Given that $x_{28-31} = i_{0-3}$ and $0 \le i \le 3$

$x_{27} = x_{27} \oplus x_{28} \oplus x_{27 + i}$

$x_{26} = x_{26} \oplus x_{27} \oplus x_{26 + i}$

...

$x_{n} = x_{n} \oplus x_{n + 1} \oplus x_{n + i}$

($x_n$ or $i_n$ are the $n$th bit of $x$ / $i$)

However, i really have no clue when it comes to $i \gt 3$ since you cant access the plain bits anymore.

// EDIT: The $f(x)=x\oplus (x \lll 1)$ can easily be broken by defining that $x_0=0$ and then calculating the rest using $x_{n}=x_{n-1} \oplus x_{n}$ but I wasn't really able to expand this to the problem above.

In order to invert $f(x) = x \oplus (x \lll 1) \oplus (x \lll 5)$ (where all quantities are 32-bit), we do not need the low-order bits of $x$; given $f(x)$ we can find $x$.

Let's first solve $f(x)=1$ for $x$. We must have (where $x_i$ is bit $i$ of $x$, with $i=0$ for the low-order bit)
$$\begin{align}x_{0}\oplus x_{31}\oplus x_{27}&=1\\x_{i}\oplus x_{(i+31\bmod32)}\oplus x_{(i+27\bmod32)}&=0\;\text{ for }1\le i<32\end{align}$$

This is a system of 32 linear equations with 32 unknowns, and the tried and tested method of Gaussian elimination yields
$x_0=1$, $x_1=1$, $x_2=1$, $x_3=0$, $x_4=1$, $x_5=0$, $\dots$, $x_{27}=1$, $x_{28}=0$, $x_{29}=0$, $x_{30}=1$, $x_{31}=1$, which we can combine into $x=\mathtt{0xCAF84657}$ which indeed is such that $f(x)=1$ (see second part for alternative methods, based on polynomial arithmetic or brute force).

Given the rotation-invariant structure of $f$, it follows that for $0\le i<32$, the solution of $f(x)=(1\lll i)$ is $x=(\mathtt{0xCAF84657}\lll i)=k_i$.

And because $f$ is linear, we can solve $f(x)=y$ by combining with $\oplus$ those $k_i$ such that bit $i$ of $y$ is set; the combination being the desired $x$.

Or, for a more direct expression, we can write $x=y\oplus(y\lll1)\oplus(y\lll2)\oplus\dots\oplus(y\lll27)\oplus(y\lll30)\oplus(y\lll31)$ where the rotations $i$ in the terms are those such that bit $i$ is set in $k_0=\mathtt{0xCAF84657}$ (argument: this is such that $y=1$ yield $x=k_0$, and the rest follows by linearity and rotation invariance).

The Boolean matrix defining the system of equations is circulant; that allows finding $k_0$ by finding the inverse of the Boolean polynomial $1+z+z^5$ modulo $1+z^{32}$ using the Extended Euclidean algorithm for polynomials; see related answer.

More directly, with the indexes of the bits set in $x$ [resp. $y$ ] the coefficients of the Boolean polynomial $X(z)$ [resp. $Y(z)$ ], we have
$$y=f(x)\iff Y(z)=F(z)\,X(z)\bmod(1+z^{32})\;\text{ with }F(z)=1+z+z^5$$
thus inverting $F$ modulo $1+z^{32}$ (if possible) gives us $G$ which is to $f^{-1}$ what $F$ is to $f$.

In Mathematica, the Extended Euclidean algorithm for Boolean polynomials $1+z+z^5$ and $1+z^{32}$ is invoked as
{g,{u,v}} = PolynomialExtendedGCD[1+z+z^5, 1+z^32, z, Modulus->2]
giving the following result, where g of 1 at the beginning confirms that $f$ is invertible, and the bits sets in $k_0$ [and the rotation counts in the expression for $f^{-1}(y)$ ] are given by the coefficients of u, which I isolated on the second line:
{1,{
1+z+z^2+z^4+z^6+z^9+z^10+z^14+z^19+z^20+z^21+z^22+z^23+z^25+z^27+z^30+z^31
,z^3+z^4}}

For my initial answer, I actually neither did this, nor solve the linear system. If the problem was for more than 32-bit variables, I'd do that; but here I used brute force and wrote this C code which output 0xCAF84657 in about 5 seconds:

#include <stdio.h>
#include <stdint.h>
int main(void) {
    uint32_t x=0;
    do
        if ((x^((x<<1)^(x>>31))^((x<<5)^(x>>27)))==1)
            printf("0x%08lX\n",(unsigned long)x);
    while(++x);
    return 0;
    }


Decrypt digital signature using RSA public key with openssl I have a digital signature that was created using the following algorithm: a SHA-256 hash of the body of the message is calculated. It is then signed using an RSA private key and the result is base64-encoded.

Now, I have the RSA public key corresponding to that private key which was used to encrypt the hash. I want to decrypt the digital signature using the RSA public key so that it gives me the SHA-256 hash of the body of message that was sent by the server. I can later compare this with the SHA-256 hash of the body of the message that was received.

I am unable to recover the SHA-256 hash (I'm expecting to get 64 hex characters). Here is what I am doing:

I save the public key in the following format in a file, pub.key:

-----BEGIN PUBLIC KEY-----
the key itself
-----END PUBLIC KEY------

With the following command:

openssl rsa -noout -text -pubin < pub.key

It tells me that the key is of length 2048 bits.

I save the base64-encoded digital signature in a file called sig.txt and then use the -verify option of openssl to retrieve the data.

openssl rsautil -verify -in sig.txt -inkey pub.key -pubin

This gives me the error:

RSA_EAY_PUBLIC_DECRYPT: data greater than mod len: rsa_eay.c

Please note that the signature in the file sig.txt is in base64 encoded form.

How can I use the RSA public key to decrypt this signature to recover the SHA-256 hash?

openssl rsautl expects a signature in binary format, not Base64-encoded. You should also check the signature scheme used. PKCS#1 v1.5 and PSS (PKCS#1 v2) are your best bets

The -verify switch is a bit misleading, the command only outputs the decrypted hash. You have to compare with the expected hash yourself.

Beware of the fact that the output will be the DER encoding of the SHA-256 hash.


AES with no SubByte - recover the key I was wondering if it was possible to recover an AES-128 blockcipher key, knowing that there is no substitution box (it can be seen as the identity mapping). I thought it would be feasible.

I implemented this AES version and I tried, first, a DFA.
Because MixColumn and ShiftRow are both linear operations we can inject manually a fault on a given byte at the 9th round, before the mix column. Then I used phoenixAES to compute the last round Key, but it is not working (I have modified the Sbox in the phoenixAES programm).

The only other solution I see now is to express each round key as a function of the master key (the key schedule is now linear) and to use the fact that $$AES(P)=AP+K$$ where K depends only on the round keys (we can compute its exact expression) in order to solve a linear system, but it seems really grueling.

Do you know if the Rijndael box is needed to perform a DFA on AES (the error diffusion should be the same with every box ?!)

Do you see an other way to solve this problem ?

where K depends only on the round keys (we can compute its exact expression) in order to solve a linear system, but it seems really grueling

Actually, it doesn't look bad at all; that's 128 linear equations in 128 variables (over $GF(2)$); Gaussian elimination should be able to give you an answer in $128^3 \approx. 2,000,000$ bit operations; hardly infeasible (and certainly easier than any fault attack).

The only tricky bit is that the 128 equations are likely not linearly independent (a random set of 128 $GF(2)$ linear equations over 128 variables is linearly independent circa 29% of the time); if they are not linearly independent, then there will be multiple solutions (or none at all); multiple solutions imply multiple keys that are all correct solutions; your Gaussian elimination code will need to deal with that situation.


A way around digital signatures? Scenario: I have to protect the integrity of some files that will be exchanged between entities $A$, $B$, $C$. Entity $A$ creates the file (e.g. configuration) and sends it to $B$ and $C$. Entities $A$ and $B$ are considered trusted but entity $C$ is semi-trusted (by default it is trusted but we assume it could be compromised at some point). The communication channel between $A \leftrightarrow B \leftrightarrow C$ is considered secure (e.g. VPN).

Now, I obviously cannot rely on HMAC since I would have to share a secret with potentially compromised $C$. But I would prefer to avoid implementing a PKI and digital signatures for this purpose. Is there any way around a PKI that will protect the integrity of my files?

As owlstead wrote in the comments, you don't need a real public key infrastructure to use public key signatures for this. You can have A create a key-pair, then distribute the public key to B and C in advance, before any communications start.

A symmetric setup isn't much more complex either. You need two secrets, one between A and B, one between A and C. Calculate two MACs for each file, with either key. B can verify one, C the other. Even if E gets the secret key from C modifies a file, they can only calculate one of the MACs for modified messages.


Which is more secure for hashing: SHA512 or BCrypt with the same salt reused over and over? Setting aside questions of if BCrypt should even be used in this way, I was just wondering which one would be more secure hypothetically.

If you want to know why I don't just use random salts as per BCrypts default, it's because there is no way of telling which hash digest is the one that should be checked against in my specific use case. Hence, I have to hash the entered string and check if the result is present in a database table. If the salt is randomized there's no way to determine if the digest is present in the table short of checking each one.

If it makes any difference, the data being hashed is not passwords, they are randomly generated hexadecimal strings of 32 characters.

bcrypt is a password hashing method. That means that it expects a password as input parameter. It has been designed so that it is hard to perform an offline test of guessed passwords by having an explicit work factor.

It accepts (or requires) a salt so that:

repeated passwords do not show up;
that it is impossible to build a (rainbow) table.

Now your entry is not a password. It is a secret value consisting of 16 bytes or 128 bits. That it is encoded as 32 hexadecimal digits doesn't make any difference, assuming that each hexadecimal digit is equally likely.

Correctly guessing a fully random 128 bit secret is similar to guessing a 128 bit AES key. This is not likely to happen soon. For this reason you do indeed not need bcrypt for the additional work factor

Similarly, if it is indeed fully random, then you do not need a salt either. The salt makes the result probabilistic, so that you don't get the same value back. However, this seems at odds with your requirements to lookup the hash.

If you don't want to expose your secret then you could use a key based key derivation function (KBKDF) rather than a password based key derivation function (PBKDF). Such a function transforms a secret into another secret of given size. If you don't use a salt then the result will be deterministic and you can check for the value in a table. HMAC-expand is one of the later algorithms that you could use.

For your use case you could also use a more generic Pseudo Random Function (PRF) directly. HMAC is a good example of a PRF that can be used for derivation as well. If push can to shove you could also use a SHA-256 I suppose, as a poor man's KDF / PRF. Theoretically hash functions may not adhere to strict requirements for key derivation, but in practice a symmetrical-crypto-based hash function such as SHA-2 will probably fit your need.

Whichever scheme you use, it makes sense to make sure that your scheme doesn't perform the same operation on the original secret as the KDF/PRF/Hash. If you want to make sure that it doesn't: use a KBKDF with a specific label and/or static random value.


Verify hash of plaintext through ciphertext Suppose that Alice runs a paid archival service.

Bob wants to download a well-known plaintext M with hash H(M) from Alice by sending her the hash.
Alice does not want to send M to Bob without Bob paying and Bob does not want to pay unless Alice sends him the real thing.
Thus, Alice encrypts M with some temporary key K into: E(M, K) and sends that to Bob alongs with H(K).
Bob checks that E(M, K) is indeed M encrypted with K, knowing only {E(M, K), H(K), H(M)}.

Is step 3 possible under some crypto system?

Answering in a pragmatic way (it might help, depending on the background of the question):

Even if step 3 is possible, it does not matter, since this will not add any additional security value.

Because: Bob still has to trust Alice that she will send him K in case that he pays the money. So Bob could also simply trust Alice, that she has already send him the correct encrypted text E(M, K) in the first place.


Why do the discriminant and primality of the group order of an elliptic curve affect security? In a book about cryptography and elliptic curves, there was a mention that not all curves are secure, and a statement than in order to pick a secure curve the curve must satisfy 3 requirements.

The curve's equation is $y^2 = x^3 + ax + b\quad\pmod p$
with $4a^3 + 27b^2 \neq 0\quad\pmod p $
and the order $\#E(\mathbb F_p)$ of the Elliptic Curve group is prime.

The third point is weird since in DLP like Diffie-Hellman modulo $p$, the order $p-1$ can be any number not necessarily a prime (maybe it can be extra secure if it's a prime I don't know).
I understand the first statement of course but I'm completely lost on why the other two statements must be true for an elliptic to be secure. So if someone can explain why statements 2/3 must be true for a good elliptic curve and what can happen if these two conditions aren't true. Any small example with small $p, a, b$ will be really appreciated so I can understand the mathematics behind it.

$y^2 = x^3 + ax + b\bmod p$ is the Short Weierstrass equation. The theory behind it is here

Using Bezout’s Theorem, it can be shown that every irreducible cubic has a flex (a point where the tangent intersects the curve with multiplicity three) or a singular point (a point where there is no tangent because both partial derivatives are zero). [Reducible cubics consist of a line and a conic, which are easy to study.]
An irreducible cubic with a flex can be affinely transformed into a Weierstrass equation:
$$Y^2 + a_1 XY + a_3 Y = X^3 + a_2 X^2 + a_4 X + a_6$$

And this can be converted into a short Weierstrass equation if $p$ is larger than $3$. The transformation can be achieved by
Change $y\longrightarrow y-(a_1x+a_3)/2$, now the new equation has of the form $$y^2=x^3+Ax^2+Bx+C.$$
And now change $x\longrightarrow x-A/3$, now  the new equation has of the form $$y^2=x^3+ax+b.$$
The reason for $p \neq 2,3$ can be seen from the divisions. Also one should note that the two changes of variables are invertible, therefore their composition, too. This concludes that the rational points on both equations are in bijective correspondence.
For $p=2$ and $p=3$ there are other short forms. In Cryptography we work in either binary extension fields ($\mathbb{F}_{2^m}$) which no more secure and large prime fields ($\mathbb{F}_{p}$) and on their extensions ($\mathbb{F}_{p^m}$).

If the discriminant is not different than zero ($\Delta = 0$) then the curve is singular then the DLP is easy. Geometrically, this means that the graph has cusps, self-intersections (node), or isolated points.
Cusp;  when $\Delta=0$ and $a=0$ ( $y^2 = x^3$);

Intersection or Node;  when $\Delta=0$ and $a\neq 0$ ( $y^2 = x^3 +3x +1$);

Acnode (isolated point); $y^2 + x^3 + x^2$, at $(0,0)$

Note these draws are not in the finite fields where we cannot see such figures to see those. A curve with the finite field just points when we draw on the plane as below and we cannot see the above singular points, however, we can still calculate them.

The above is the point of the curve over $\operatorname{GF}(307)$  with the curve equation $ y^2 = x^3 + x^2 + x$ and this curve group is isomorphic to $ Z/160 + Z/2$

And, Wolfram has a nice page about those singular points.

This is not completely true. Some curves have prime order ( i.e. $\#E(\mathbb F_p)$ is a prime) and all of the elements other than the identity can be a generator ( see the blow theorem).
Some curves don't have prime order, like the Curve25519, it has a co-factor $h=8$ i.e. $h = \frac{\#E(\mathbb F_p)}{n}$ where $n$ is the order of the generator point $G$. In this case, we chose the largest prime and select a generator for it.

There is also twist security related to the order that one must consider. Although the NIST P-224 has co-factor 1 ( i.e. it has prime order), it doesn't have the twisted security.

Theorem: Let $E$ ben elliptic curve group over the finite field $\mathbb{F_q}$. Then $$E(\mathbb{F_q}) \simeq \mathbb{Z_p} \text{ or } \mathbb{Z_{n_1}} \oplus \mathbb{Z_{n_2}}$$ for some integer $n \geq 1$, or for some integers $n_1,n_2 \geq 1$ with $n_1|n_2$.
If the order of the curve is prime then it must be $E(\mathbb{F_q}) \simeq \mathbb{Z_p}$.


Diffie-Hellman protocol: Clarifications I'm reading the Wikipedia entry where we have

  Alice and Bob agrees on a prime number, p, and a base, g, in advance. For our example, let's assume that p=23 and g=5.
  Alice chooses a secret integer a whose value is 6 and computes A = g^a mod p. In this example, A has the value of 8.
  Bob chooses a secret integer b whose value is 15 and computes B = g^b mod p. In this example, B has the value of 19.
  Alice sends A to Bob and Bob sends B to alice.
  To obtain the shared secret, Alice computes s = B^a mod p. In this example, Alice obtains the value of s=2
  To obtain the shared secret, Bob computes s = A^b mod p. In this example, Bob obtains the vlaue of s=2.

Now, I understand that the protocol is not unbreakable but it works because there is no efficient way to figure out the secret number for Eve quickly.

Is it correct that the main task for Eve is to solve for either a from A=g^a mod p or b from B = g^b mod p but that both of these can  only be done by guessing every number from 1 to p-1 (worst case)?

If so, why is this considered more than polynomially hard since the computation is linear in the size of the prime p?

Your assumption is correct, that is called the Discrete Logarithm Problem.

The complexity of the problem is linear to the number of elements of the group but exponential to the number of bits of the group's size (These days you usually use a 2048 bit prime for a DH exchange, meaning that there are ~ 2^2048 elements in the group)


Why is the Pedersen commitment computationally binding? This is how the Pedersen commitment seems to work:

Let $p$ and $q$ be large primes such that $q \mid (p-1)$, let $g$ be a generator of the order-$q$ subgroup of $Z_p^{\star}$. Let $a$ be a random secret from $Z_q$, and $h=g^a \bmod p$.

The values $p$, $q$, $g$ and $h$ are public, while $a$ is secret.

To commit to a message $m \in Z_q$, the sender chooses a random $r \in Z_q$ and sends the commitment $c=g^mh^r \bmod p$ to the receiver; while in order to  open the commitment, the sender reveals $m$ and $r$, and the receiver verifies that $c=g^mh^r \bmod p$.

Moreover, the Pedersen commitment scheme is known to be:

information theoretically hiding: given a commitment $c$, every value $m$ is equally likely to be the value committed in $c$. For example, given $m$, $r$, and any $m^{\prime}$, there exists $r^{\prime}$ such that $g^m h^r = g^{m^{\prime}} h^{r^{\prime}}$. In fact, we have that $r^{\prime} = \frac{m-m^{\prime}}{a} + r$.
computationally binding: if the sender can find different $m$ and $m^{\prime}$ both of which open the commitment $c$, so $g^m h^r = g^{m^{\prime}} h^{r^{\prime}}$, then he can solve the discrete logarithm $\log_g(h)=\frac{m^{\prime}-m}{r-r^{\prime}}$. If we assume the discrete logarithm is hard, the sender cannot open the commitment with another value.

My question concerns the computationally binding property:

We know, from the information theoretically hiding bullet point, that given $m$, $r$, and any $m^{\prime}$, the sender is able to compute an $r^{\prime}$ such that $g^m h^r = g^{m^{\prime}} h^{r^{\prime}}$. But doesn't this mean that he's been able to open the commitment with a different message $m^{\prime}$ without even having to compute a discrete logarithm?

The misunderstanding you have is with the sentence "the sender is able to compute an $r'$..."

Actually, that's not true, and the "information theoretically hiding" bullet point does not state that.  What it does state is that, for every $m'$, there exists an $r'$ that satisfies the relation; however it does not imply that a real sender can find such a value.  In fact, the "computationally binding" bullet point specifically states that a real sender cannot (assuming he is unable to solve Discrete Log problems).

Instead of talking about the senders capabilities, the information theoretically hiding bullet point talks about the receiver; that is, even if the receiver had infinite computing power, he still cannot get any information from the commitment as to what is committed to (because all possible values are equally likely).  Now, the Pedersen commitment scheme is asymmetric in this (because a computationally unbounded sender can change commitments); on the other hand, it turns out that a commitment scheme between two computationally unbounded parties is actually impossible; the Pedersen scheme is as close as we can come.


Why is a non fixed-length encryption scheme worse than a fixed-length one? I have the following definition (highlights by me):

  An (efficient secret-key) encryption scheme $(Gen,Enc,Dec)$, where $Gen$ and $Enc$ are PPT algorithms and $Dec$ is a Deterministic Polytime Algorithm, is one-time computationally-secret if for any PPT adversary $A$ it holds that the probability of the following experiment is negligibly biased from $1/2$:

  The adversary outputs two messages $m_0$ and $m_1$ of the same length.
  Let $k \leftarrow Gen(1^n)$ and let $b \in {0,1}$ be chosen uniformly at random. $c \leftarrow Enc_k(m_b)$ is computed and given to $A$
  A outputs the bit $b'$
  The output of the experiment is 1 $\iff b'=b$

I wonder why $m_0$ and $m_1$ should be of the same length, why is better than considering a non-fixed length encryption scheme?

The only drawback that comes to my mind is that if you are able to know something about the encryption of two messages of different length before they are actually encrypted (note that the key is generated in Step 2) then it would justify the choice of fixed-lenght. But I cannot think of a reason why it must be so.

Any ideas?

The encryption scheme in the experiment you describe does not have to be fixed-length. We simply require that the two messages the adversary sends to its oracle have the same length. The restriction is on the adversary, not on the encryption algorithm.

So why do we put this requirement on the adversary? The reason is that in every practical encryption scheme, ciphertexts leak information about the length of the corresponding plaintexts --- the longer the plaintext, the longer the ciphertext. So cryptographers basically threw their hands up in the air and said, "Fine, we'll just concede that length-information leaks. Can we make sure no other information leaks?" Requiring the lengths of $m_0$ and $m_1$ to be the same ensures that the adversary can't guess which one was enrypted simply by looking at the length of the ciphertext it gets back. Therefore the experiment you describe measures an adversary's ability to find some other way that information leaks.


Advantages and disadvantages of hash-based signatures We know hash-based signatures (Winternitz signature, HORS(T) signature) that are quantum-safe and efficient. They can be stateful or stateless, one-time or multiple-time. But why are they not widely used in practice? Or maybe they are, please tell me some applications, advantages and disadvantages.

This table—of Ed25519 vs. the lattice-based post-quantum candidate Dilithium vs. SPHINCS+ variants at a comparable post-quantum security level, with a tradeoff between signature size and signing time—may help explain:

\begin{equation*}
\begin{array}{r|rr|rr|rr}
\text{sig scheme} && \text{sig bytes} && \text{cycles to sign} \\
\hline
\text{ed25519}
  & \times1= & 64
  & \times1= & 45\,400 \\
\text{dilithium3}
  & \times42= & 2\,701
  & \times101= & 4\,600\,060 \\
\text{sphincss192sha256simple}
  & \times266= & 17\,064
  & \times46\,000= & 2\,105\,269\,820 \\
\text{sphincsf192sha256simple}
  & \times557= & 35\,664
  & \times1\,850= & 84\,025\,740
\end{array}
\end{equation*}

Median cycle counts taken from SUPERCOP measurements on a 2019 AMD EPYC 7702 with 64 x 2000MHz cores; see the full results https://bench.cr.yp.to/results-sign.html for more details, comparisons on different machines, and additional signature schemes.

Although hash-based signatures are reasonably well-understood and based on conservative design principles, they are thousands of times costlier than the modern standard for signatures secure against a classical adversary, the elliptic-curve signature scheme Ed25519, and hundreds of times larger.  (That said, the verification costs of SPHINCS+ aren't quite so bad.)

The stateful signature scheme XMSS has been deployed in OpenSSH, which is a little silly because (a) stateful signatures are a serious foot-gun for operators, and (b) there's no need to deploy post-quantum online authentication mechanisms for a long time—it is only important to deploy them once quantum computers are becoming a serious threat so that future sessions cannot be forged by a quantum adversary.

(In contrast, post-quantum encryption and post-quantum key agreement are important to deploy as soon as possible—and OpenSSH is experimenting with that too—to prevent a future quantum computer from retroactively decrypting past sessions.)


Implementing AugPAKE over ECC The AugPAKE spec says it can be implemented over elliptic curves. This sounds very promising, but they don't actually back that claim. Can this really be achieved? If so, how would one go about mapping the existing protocol to elliptic curves?

Yes for sure you can do that. Mapping this protocol to an elliptic curve setting is just like mapping DH key exchange to ECDH key exchange. In AugPAKE you work in a prime order $q$ subgroup of $Z_p^*$ and in the EC setting you use a prime order $q$ elliptic curve group.

Observe that in the EC setting a multiplication of group elements in AugPAKE is then point addition and exponentiation in AugPAKE is then scalar multiplication.


Why rogued certificate from hash collision is harmful I cannot understand why rogued certificate is thought harmful though It can be used to impersonate some website. The attacker can craft a rogued certificate with different identities and public key but the same signature through hash collision, such as md5 collision. But the attacker cannot aquire the private key corresponding to the public key in the rouged certificate. So in the handshake stage of SSL, the attacker can't decrypt the PreMasterKey encrypted by the public key, then the negotiation will be fail.
Can anyone tell me where I was wrong. Truly appreciated.

Very basically, the hash collision it can be used to fool CA's to sign a certificate that stores one set of information in the certificate's attributes, while there the requester uses it to create one or more certificates with different attributes.

The attributes in the certificate are as important as the public key that is being signed. They contain, for instance, the information of the holder. For web certificates the most important holder attribute is the domain name of the server. It is of course of vital importance that the name cannot be changed. Another part of the attributes is the key usage, which defines how the key should be used. One very important bit is the bit that defines if the certificate can be used as CA certificate. If it can be set then the user may simply start acting as an intermediate CA, issuing certificates himself, for any domain.

The public key stored in the certificate is only one part of information that is signed. That you can also sign another public key is not so much of a problem as the private key still needs to be controlled by the party sending the certificate request. This would only be a problem if the location of the private key is somehow part of the security properties covered by the certificate.

All in all, you seem to be focusing too much on the Public Key part and too little on the Infrastructure part of PKI. The attack isn't really a problem during the handshake of TLS, the attack is on the trusting of the certificate. The PKI method of establishing trust is used by TLS, it is not defined by it.


What is the border between an ideal functionality and a protocol? In the context of the UC framework, what is the border between an ideal functionality and a protocol?

It seems to me that it depends on the level of granularity required for proofs.

For example, the same protocol ${\Pi}_{1}$ may be described in more than one way:

${\Pi}_{1}$ requires parties to interact just with one ideal functionality ${F}_{2}$.
${\Pi}_{1}$ requires parties to interact with another protocol ${\Pi}_{2}$, that is equivalent to ${F}_{2}$, but it is explicit that it requires parties to interact with ideal functionalities ${F}_{3}$, ${F}_{4}$, ${F}_{5}$.

The only difference between the two cases is how detailed is the description of what ${\Pi}_{1}$ does. So, in general, ideal functionalities are a kind of terminal nodes in a graph of dependencies.

Does it make sense?

There are conceptual errors in the question. Protocols define how parties should interact among themselves and with ideal functionalities (so, it does not make sense to say that one protocol requires parties to interact with another protocol). Moreover, an ideal functionality describes abstractly the behavior of something, while a protocol describes how this behavior is achieved (protocols realize ideal functionalities). Finally, in the description of a protocol the number and the level of abstraction of the ideal functionalities that are assumed as available is up to the designer.


Hash functions vs Stream Ciphers in terms of Speed We know that it's possible to create a hash using a stream cipher (for instance, RC4 or AES in Counter Mode). As stated here: "A Pseudo Random Generator (PRG) and a hash function are both Pseudo Random Functions (PRFs), but they have different security considerations". Whether or not it's advisable to do so, is there a correlation between the way of a hash function being created and its speed? For instance, are cryptographically secure hash functions (such as SHA-1) faster than a hash function created using a stream cipher, or the opposite? Is each case entirely different?

Take this paper as an example. In page 6 you'll see the protocol. As described, the protocol uses a PRG which takes as an input something of size k and produces something of size m. The authors say that they implemented the PRG using AES in Counter Mode. The reason for not using a hash function is because we want the output to vary and sometimes being really big (say 100.000) where when using a hash function the output is fixed (i.e. 160 for SHA-1). For the sake of argument, let's say that the size of the output is not a problem (we use something small like 160) and that we don't take security into consideration.

Which PRG would be faster? A stream cipher (like AES in Counter Mode) or a Hash Function like SHA-1?

There is a lot of confusion in this question. Hash functions provide collision resistance. However, under a pretty reasonable assumption, they can be used to obtain a PRG or a PRF. Thus, hash functions and stream ciphers can be used to obtain a pseudorandom generator. This is true. (Although RC4 is broken and CANNOT be used for this purpose any more.)

Now, the question is: what is faster? A hash function, a stream cipher, a block cipher, and so on. The answer is very simple! It depends on the function in question and on the platform. If you have an AES-NI instruction set, then this is incredibly fast. It is also a very good option since its security is better studied than any stream cipher that hasn't yet been broken. Hash functions (like the SHA family) are actually pretty slow in comparison. Once Intel puts SHA-2 into hardware, then we'll have to see, but from what I understand it will be slower than AES. If you don't have AES-NI, then things like Salsa20 are a good option. However, my preference is always AES, and unless you really can't use it for some reason, that is always my recommendation.


What is the non-programmable random oracle model? I would like to know the difference between the random oracle model and

the non-programmable random oracle model.  What is the difference?

The main difference (from a cryptographic point of view) is whether the simulator is capable of choosing the answers to the oracle queries or not. In more detail, to prove the simulation-based security of a cryptographic construction in the random oracle model, the simulator is assumed to be able to choose answers for the queries that parties make to the random oracle. This property is referred to as programmability of the random oracle. In the context of non-interactive zero-knowledge (NIZK) proofs, for example, this makes the simulator able to create a convincing but fake proof. On the other hand, the non-programmable random oracle (NPRO) model restricts the simulator such that it can no longer choose the answers for the queries. Instead, the simulator is empowered by seeing all the query/answer pairs, made by the parties during the protocol. This restriction on the simulator (or more generally, the security reduction) makes the underlying proofs preferable, as they rely on fewer properties of the random oracle and so can be considered as a step toward getting rid of it.


chacha20-poly1305 padding and length encoding The AEAD construction for chacha20-poly1305 described in the IETF proposal encodes message lengths into the text that is to be hashed. The newer proposal goes further and pads associated data and plaintext to multiples of 16 bytes.

Can anyone explain what the purpose of that is? The chacha20-poly1305 implementation found in OpenSSH doesn't do anything like that, and as far as I can see, neither does NaCl. Those are still considered secure so I wonder what's going on.

The reason for the padding (and re-positioning of the AAD length) in the later draft is to make implementations easier and faster - i.e. not for a security reason.

The rationale for this change was actually documented on the CFRG mailing list by Alyssa Rowan:

  Instead of the lengths directly following their ciphertexts:

  draft-agl-tls-chacha20poly1305-04:

  AAD | len_AAD | ciphertext | len_ciphertext

  this final version of the AEAD pads the Additional Authenticated Data
  (if any) and ciphertext to a 16-byte block boundary (using between
  0-15 zero bytes) and moves the lengths to the end:

  draft-nir-cfrg-chacha20-poly1305 (the final AEAD specified here):

  AAD | padding1 | ciphertext | padding2 | len_AAD | len_ciphertext

  which is more efficient to implement (block-aligned, and the recipient
  knows the lengths are at the end, instead of having to jump backwards
  to find len_AAD). Thanks to Niels Moeller for that idea.


how do you calculate the private exponent in asymmetric key encryption Here is an excellent paper on the math of asymmetric key encryption: http://www.mathaware.org/mam/06/Kaliski.pdf

See the example on Page 6.

The public key = $55$
Primes used to calculate public key are $5$ and $11$.

$e = 3$

Now see the appendix:
$L = \mathrm{LCM}(p-1, q-1) = 20$

The paper states $de = 1 \mod L$

I can't figure out how he gets the value of $d = 7$

You compute the modular inverse of $e \pmod {20}$ with the Extended Euclidean Algorithm, but in this simple case with $e=3$ you can guess $d=7$ because $3\times 7 = 21$.


What encryption/decryption method should I use when multiple users should have access to the encrypted information? Ok, I am in a little bit of cryptographical fix :D

I need to figure out a way to encrypt and decrypt data handled by a website.
The website is intended only for a certain group of people who will use it to upload and search sensitive information.

Data is entered by them using a browser, which should be encrypted before sending and storing it in the server/database.

On the other hand when these users search for a value (say, account number) in the database, it is queried whether present in the database and if yes, it is decrypted and displayed on the browser.

The whole point of encryption/decryption is to make sure that website hosters, owners and administrators do not understand the data values.

It is a website that has multiple users who might be accessing the same data/values from the same database. If we have 1000 registered users, the information uploaded by each of them should be available to all of the 1000 users.

The problem here is that this is not a person to person encryption/decryption (like sending an encrypted email), therefore I am not sure if the private and public key cryptography can be implemented in it's raw form. What is the logical way to implement cryptography in this situation?

Here's an example scheme that should work with $\mathcal O(r)$ operations for $r$ registrations and $\mathcal O(n+r)$ operations for $n$ documents and $r$ revoked (simultaneously) user accounts, but of course would perform all (eg search) operations client-side. This also involves only $\mathcal O(n+r)$ keys. Doing something like this (securely, partially) server-side is possible but more complex, this is called searchable or structured encryption and allows you to eg search for specific keywords / tags without the server learning the precise keyswords. This is eg deployed by pixek (RWC 2018 slides PDF) where apparently these three schemes are used: One, Two, Three.

The initial setup goes like this:

Define a (random) symmetric key $K$ for the entire database.
Define a (random) symmetric key $K_i$ for the $i$-th document.
Encrypt the $i$-th document using $K_i$ and store $\operatorname{Enc}_K(K_i)$ "next to the document" ie so that you can find this ciphertext when you know which document to access.

The per-user registration goes like this:

Encrypt $K$ under a user-specific public key. This is what happens upon registration. This public key may be stored symmetrically encrypted on the server using the user's password.

Revokation then works like this:

Upon revokation pick a new $K'$. Re-encrypt all $K_i$ with that $K'$ and encrypt the new $K'$ under the public keys of all the users and replace the old encryptions of $K$.

Accessing a document then goes like this:

The user retrieves their private-public keypair.
The user requests their encrypted copy of $K$ and decrypts it.
The user requests a document with its encrypted per-document key, decrypts this key and decrypts the document.

Because this question will probably come up:

  Why not use the global key to encrypt all the documents directly?

The idea is to a) limit the amount of ciphertext available under a single key and b) that if some user has access, they learn $K$, and so you would have to actually re-encrypt all the documents after their access gets revoked in case an admin leaks the ciphertext blobs. If you also update the per-document key on each document update any user will only be able to decrypt documents they have already seen this way.


Point of Diffie-Hellman key exchange when public keys are known Since the basic version of Diffie-Hellman key exchange protocol is vulnerable to Man In The Middle Attack, some sort of authentication is needed. It was mentioned that RSA digital signature can be used to handle this case. However, I don't understand that if the public keys of the two parties are known to each other, what would be the point of using DH at all? One of them can just propose a shared key k, compute its hash value and send the (k, h(k)) encrypted with the other one's public key. I appreciate if anyone can clarify the benefit of using DH in case of known public keys.

Diffie-Hellman allows for forward secrecy. In the protocol you describe, if the private key is ever leaked all previously exchanged keys are leaked.

If we only use RSA to authenticate keys created with Diffie-Hellman, past keys are safe even if you lose control over your private key in the future.


Are all binary-additive stream ciphers reciprocal? I'm writing a thesis focused on Maurer's provably-secure stream cipher. Long story short, this cipher works by expanding a short key into a long keystream and then XORring this keystream with the plaintext in order to obtain the ciphertext (and vicecersa).

Take this definition of a binary-additive stream cipher: a cipher where the plaintext, ciphertext and keystream are binary strings and where the ciphertext is produced as a XOR addition of the plaintext and the keystream.

Also, take this definition of a reciprocal cipher: a cipher in which the encryption and decryption algorithms are identical (they're the same involution).

With these two definitions, can I state that binary-additive stream ciphers are all reciprocal ciphers? I think so, since if the ciphertext is the XOR of plaintext and keystream, than the plaintext must be the XOR of the keystream and the ciphertext.

Since additive stream ciphers are involutions, i.e.,
$$
E_K(\cdot)=D_K(\cdot)
$$
for all possible keys $K$,
they are also reciprocal.