Bounding security of password authentication given entropy An adversary Craig tries to log-in as Alice on a system that will only accept the right password, leaks (only) if an attempt succeeds, and allows many attempts.

Alice's password choice is modeled as a random pick in a finite set of $m$ possible passwords $P_i$ each with probability $p_i$, with $0\le i<j<m\implies p_i\ge p_j>0$ , and $1=\displaystyle\sum_{0\le i<k}p_i$ .

Assume Craig has a perfect model of Alice's password choice and tries up to $n$ passwords $P_i$ by increasing $i$ (with $0\le n\le m$), stopping if he logs-in. That success for Craig has probability $q_n=\displaystyle\sum_{0\le i<n}p_i$ .

We know $n$, $m$, and the password distribution's Shannon entropy $H=\displaystyle-\sum_{0\le i<m}p_i\cdot\log_2(p_i)$ . For a uniform distribution of the $p_i$, we'd have $q_n=n/m=n/2^H$ . But we do not know said distribution.

How can we rigorously, and tightly, bound Craig's success probability $q_n$ ?
Clarification: it is asked upper and lower bounds of $q_n$ as a function of $(n,m,H)$.

What if we additionally have the min entropy $H_\text{min}=-\log_2(p_0)$ or some other interesting metric of the probability distribution?

Now there are $u$ users Alice, Bob.. that (we assume) have chosen their password independently of each others, but per the same distribution. Craig knows user logins, and tries $P_i$ for each user before moving to $P_{i+1}$. He stops when he logs into the account of any user, or has made $n$ tries, with $0\le n\le (m-1)\cdot u+1$ .

What does the bounds become?

Suggested numerical illustration: for $n=1000$ out of $m=2^{48}$, $H=20$-bit entropy, what bound can we get for $q_n$? If we additionally assume $H_\text{min}=12$? Or with $u=2^{10}$?

Does some property that actual distributions of password choice tend to have let us tighten the bounds?

Optimizing attacker's success probability constrained by $H$ and number of passwords

Let's tweak the notation a little bit to make it less cumbersome: the passwords the adversary tries have probability $p_i$ for $0 \leq i < n$, and the passwords the adversary doesn't try have probability $q_j$ for $0 \leq j < m$.  The adversary succeeds with probability $\sum_i p_i$.

We seek an extreme point of $f = \sum_i p_i$ among the zeros of $g$ and $h$ where
\begin{align*}
  g &= H + \sum_i p_i \log p_i + \sum_j q_j \log q_j,
    &&\text{entropy constraint;} \\
  h &= 1 - \sum_i p_i - \sum_j q_j,
    &&\text{total probability constraint.}
\end{align*}
These extreme points are zeros of $$d(f - \lambda g - \mu h) = df - g\,d\lambda - \lambda\,dg - h\,d\mu - \mu\,dh$$ for Lagrange multipliers $\lambda$ and $\mu$.  Since $$d(x\log x) = \log x\,dx + x\cdot(1/x)\,dx = (1 + \log x)\,dx,$$ we have
\begin{align*}
  df &= \sum_i dp_i, \\
  \lambda\,dg &= \lambda\,dH + \sum_i \lambda (1 + \log p_i)\,dp_i + \sum_j \lambda (1 + \log q_j)\,dq_j, \\
  \mu\,dh &= -\sum_i \mu\,dp_i - \sum_j \mu\,dq_j.
\end{align*}
Thus if $dH = 0$ while $dp_i$ and $dq_j$ are nonzero (we hold $H$ fixed but allow the probabilities to vary), we obtain from $0 = d(f - \lambda g - \mu h)$ the system of equations
\begin{align*}
  0 &= 1 - \lambda (1 + \log p_i) + \mu, \\
  0 &= -\lambda (1 + \log q_j) + \mu,
\end{align*}
and from $g\,d\lambda = 0$ and $h\,d\mu = 0$ we get the entropy and total probability constraints as before.  Since $\log$ is injective, this system implies that the $p_i$ are all equal, and the $q_j$ are all equal; call the common values $p/n$ and $q/m$, respectively.  From the total probability constraint, we have $p = 1 - q$.  The entropy constraint reduces to $$H = -p \log (p/n) - (1 - p) \log [(1 - p)/m].$$  The adversary's success probability $p$ must be optimized by minimum/maximum uniform probability mass distributed to the first $n$ passwords consistent with this entropy constraint.  There are two solutions, because $H$ is increasing for $p < n/(n + m)$ and decreasing for $p > n/(n + m)$, corresponding to the attacker's minimum and maximum success probability.

Inverting $H$ is tricky, but we can approximate it in this case without too much trouble.  Let $n = 1000$ and $m = 2^{48} - 1000$ as in the question.  For the minimum value of $p < n/(n + m) = 1000/2^{48}$, we might use the approximation that $\log (1 - p) \approx 0$, so that
\begin{align*}
  H &= -p \log (p/n) - (1 - p) \log [(1 - p)/m] \\
    &\approx -p \log (p/n) + (1 - p) \log m \\
    &= \log m - p \log (p/n) - p \log m \\
    &= \log m - p \log (p m/n).
\end{align*}
To solve this, let $W(x e^x) = x$ be Lambert's W function.  Suppose $y = x \log (a x)$; then $e^y = e^{x \log (a x)} = a x e^x$, so that $e^y/a = x e^x$, from which $x = W(x e^x) = W(e^y/a)$.  Thus, since $\log m - H \approx p \log (p m/n)$, we can recover $p \approx W(e^{\log m - H}/(m/n)) = W(e^{-H} n)$.  For $H = 20 \log 2$ so that $e^{-H} = 2^{-20}$, we get $$p \approx W(2^{-20} \cdot 1000) \approx 0.000952766 > 2^{-11}.$$  For the maximum value of $p > n/(n + m)$, we can use bisection on the decreasing function $H$ (on a range much more amenable to naive numerical computation) to find $$p \approx 0.757204 < 4/5.$$  Thus, $$2^{-11} < p < 4/5.$$

Multi-user setting

Suppose Alice, Bob, etc., all use the same distribution on passwords.  If there are $u$ users, the adversary's probability of success at breaking at least one of the $u$ users with the $i^{\mathit{th}}$ password is given by $\hat p_i = 1 - (1 - p_i)^u$.  This is the complement of the probability that every user picked a password other than $P_i$.  The adversary's probability of success after trying the first $n$ passwords is $\hat p = 1 - (1 - \sum_i p_i)^u$.  To optimize this, we simply replace the objective $f$ in the above procedure by $f' = 1 - (1 - \sum_i p_i)^u$.  We obtain the modified system of equations
\begin{align*}
  0 &= u \bigl(1 - \sum\nolimits_\iota p_\iota\bigr)^{u-1} - \lambda (1 + \log p_i) + \mu, \\
  0 &= -\lambda (1 + \log q_j) + \mu,
\end{align*}
which as far as I can tell doesn't change the extreme points, only the value of the adversary's success probability at those points.  Suppose $u = 2^{10}$; then since $2^{-11} < p < 4/5$,
\begin{gather*}
  1 - (1 - 1/2^{11})^{2^{11}} \approx 1 - e^{-1} \approx 0.63212 \\
  1 - (1 - 4/5)^u = 1 - (1/5)^{2^{10}} \approx 1,
\end{gather*}
so we have $$1/2 < \hat p < 1.$$
That is, the adversary's probability of success in a multi-target attack guessing a thousand passwords out of $2^{48}$ possibilities with 20 bits of entropy for any of a thousand users is guaranteed to be better than a fair coin toss coming up heads, and may be essentially 1.  Note that this multi-target attack still costs $n\cdot u$ queries, just like the single-target attack costs $n$ queries (unless the password database is amazingly badly designed).  In this case, it costs $2^{20} \approx 10^6$ queries.

Addendum: If number of passwords is unbounded then entropy is unbounded for any success probability no matter how close to 1

Fix $0 < \varepsilon < 1$.  Let $p_0 = 1 - \varepsilon$ and $p_i = \varepsilon/m$ for $i = 1, 2, \ldots, m$.  The Shannon entropy of this distribution is
\begin{align*}
  H &= -(1 - \varepsilon)\log(1 - \varepsilon) - \sum_{i=1}^m (\varepsilon/m) \log(\varepsilon/m) \\
    &= -(1 - \varepsilon)\log(1 - \varepsilon) - \varepsilon \log (\varepsilon/m) \\
    &= -(1 - \varepsilon)\log(1 - \varepsilon) - \varepsilon \log \varepsilon + \varepsilon \log m.
\end{align*}
If $\log m$ is unbounded above, so is $H$.

The adversary's chance of success at a single guess, trying the first password with probability $p_0$, is $1 - \varepsilon$, which can be made arbitrarily close to 1, while the Shannon entropy of the whole distribution is made arbitrarily high, by adding more equiprobable passwords other than the first one.

What this counterexample demonstrates is that for any Shannon entropy, the probability of success after the first trial can be made arbitrarily close to 1.  On the other hand, the min-entropy of this distribution is $-\log (1 - \varepsilon)$, no matter how many other choices there are.

In general, if the min-entropy of the distribution on passwords is $H_\infty$, then the best chance of success at a single guess is $e^{-H_\infty}$.  If the min-entropy of the distribution on passwords given that it is not the first one is $H'_\infty$, the best chance of success at a single guess after the first one is $e^{-H'_\infty}$, so the best probability of success after two trials is $$\Pr[T_0] + \Pr[T_1 \mathrel| \neg T_0] \Pr[\neg T_0] = e^{-H_\infty} + e^{-H'_\infty} (1 - e^{H_\infty})$$ and so on, where $T_0$ means success after the first trial, $T_1$ means success after the second, etc.  In the uniform case, this reduces to a hypergeometric distribution as one might expect.


end-to-end encrypted chat app with symmetric + public key encryption, TLS and cert pinning A big drawback of end-to-end encrypted messaging services is that, as soon as you lose your device, you lose all your messages. Your private key is gone after all. I was wondering though, wouldn't it be possible to do the following in a chat app for iOS, using certificate pinning and TLS for all communication with the server:

as soon as a user logs in in the app, an asymmetric keypair is generated and stored locally, and the public key is sent to the database;
when user X starts a chat with user Y, X's device generates a symmetric encryption key, stores it locally, encrypts it using Y's public key (downloaded from the central database), and sends the cyphertext to the database;
Y's device, as soon as it comes online, downloads the cyphertext, decrypts it using it's private key, and stores it locally.

Now, X and Y both have the key generated by X's device and can send messages to each other using symmetric encryption, and nobody, except for X and Y of course, has the symmetric encryption key. When, lets say, X gets a new phone, the following will happen:

X logs in on the new device and sends the new public key to the database.
Y's device will notice that a new public key was uploaded, downloads this key, encrypts the symmetric encryption key (that it received in step 3) with X’s new public key, and sends the cyphertext to the database.
X's device downloads the cyphertext, decrypts it using its private key, and can now download all old messages and decrypt them.

So, I guess my question is: what am I missing that makes my design unsafe? Is it just not smart to store keys in the database for a long time, even when they are encrypted with strong asymmetric encryption (lets say like 8192 bits, just for fun)?

Also, I am an iOS developer, and all keys would be stored in the iOS keychain, which is a very safe way of storing information locally. Nothing is 100% secure, I know, but storing stuff there is pretty much the best you can get on iOS as far as I know.

One problem is that the server is in complete control of authentication and trust, and could easily claim that X has a new key-pair, causing Y to encrypt the symmetric key for a server-controlled key. So at least against some attack scenarios you effectively lack end-to-end encryption.

Another issue is that the use of a long-term symmetric key to directly encrypt the messages means that there is no forward secrecy. If the symmetric key is at any point compromised, all communications between the parties can be decrypted, even those that happened far before.


Difference between DER encoded signatures in JavaScript, Java, and C++ I'm trying to understand the DER-encoded signatures for the secp256k1 (ECDSA) curve better, so I have the following data array: 000102030405060708090a, which is a hex-encoded version of an array containing the numbers 0 to 10.

Also, I have the signed it with the following private key: fabb33890c65b059996546344a7e8c5adc09167fe9e09ddd6cbcac5a84790f7f, and corresponding public key:
{x: '1b6ae9e65a66ee3de4d04d479a806fc0f3266a0aa12e0c03f8c0f31e1bbf98fd', y: 'abc78ffe0a5381472098738d0d14b0c0f1bdda149ccf5866a4b523b8bcc9fba6'}

In Java, I get the following DER signature: 3045022065A67F8FF9CB5EA8BE899E94CB338FE09E2E596BC047D936FC2B96DC013B5DFC022100BE123D3F143AF91E4551AAFAE49C9187F64E323F5660D6C6198A9446C3F818A1, with the following code:

BigInteger priv = new BigInteger("fabb33890c65b059996546344a7e8c5adc09167fe9e09ddd6cbcac5a84790f7f", 16);
PrivateKey privateKey = getPrivateKeyFromECBigIntAndCurve(priv, "secp256k1");
byte[] data = DatatypeConverter.parseHexBinary("000102030405060708090a");

Signature signature = Signature.getInstance("SHA256withECDSA");
signature.initSign(privateKey);
signature.update(data);
byte[] signed = signature.sign();
DatatypeConverter.printHexBinary(signed);

However, in JavaScript using the Elliptic or any other library, I get the following signature: 304502210099d0c79559ab4e5484a116e858ce7f59b91050cf4931a925438d876fad500ed2022067fd6e1012ed7ebcd772546bd5bf130f8af1b8282c5395f4a7164bc55255975c, using the following code:

const ec = new EC('secp256k1');
const key = ec.keyFromPrivate(privateKeyHex, 'hex');
const signature = key.sign(msg, { canonical: true });
signature.toDER('hex');

In C++, using the library botan and with the code beneath I get the following signature: 304402201EE0F965F837E7C0874C99B6C2B8C7475C7DD748AC9521B40A3BEDDB58A7722A02205125EFB0E36F6ABB59A97AFAB5D2795BCBA3D1A181D97D20587B6DC2CED5299A.

Botan::AutoSeeded_RNG rng;
Botan::PK_Signer signer(*privateKey, rng, "EMSA1(SHA-256)", Botan::DER_SEQUENCE);
signer.sign_message(data, rng);

Is there a reason for these differences, because signing it in one language and verifying it in another language will give an error. Also, if possible, how would I get the result of Java using JavaScript? My guess is that it has something to do with the encoding.

Thanks in advance!

Is there a reason for these differences

You do realize that ECDSA is randomized [1], that is, signing the same message twice with the same private key will generate two different signatures.  This is normal, and not due to you using three different ECDSA implementations.

All three signatures are DER-encodings of 'a list of two integers, both of which are 32 byte positive values', which is the expected encoding of an ECDSA signature.  Note: in DER, if you encode a value between $2^{255}$ and $2^{256}-1$, that uses an additional byte.  That happens about half the time (for both integers) in an ECDSA secp256k1signature, and accounts for the slight length differences in your examples.

  because signing it in one language and verifying it in another language will give an error.

Have you tried it?

  I'm trying to understand the DER-encoded signatures for the secp256k1 (ECDSA) curve better,

Ok, here is the break down (using the first signature as an example)

30 - This is a magic number that says "this is a list of objects"

45 - This signifies that the list of objects takes up 45 hex (69 decimal) bytes (not counting the magic number or the length field itself)

02 - This is a magic number that says "this is an integer"

20 - This says that this integer takes up 20 hex (32 decimal) bytes

65A67F8FF9CB5EA8BE899E94CB338FE09E2E596BC047D936FC2B96DC013B5DFC - These 32 bytes are the integer (in bigendian notation)

02 - This is a magic number that says "this is an integer"

21 - This says that this integer takes up 21 hex (33 decimal) bytes.  This is one byte longer because DER states that "if the top bit of an integer is a 1, the integer is negative", and so to encode a positive integer with a msbit of 1, we need to prepend a 00 byte (increasing its length by 1)

00BE123D3F143AF91E4551AAFAE49C9187F64E323F5660D6C6198A9446C3F818A1 - These 33 bytes are the integer (again, in bigendian notation).

The two encoded integers are the r, s values of the ECDSA signature

[1]: actually, there are deterministic versions of ECDSA, where the message and the private key are used to generate the 'randomness' used to generate the ECDSA signature - I assume that's not in play here, or at least, your three examples don't use the exact same method of doing determinism.


Is it safe to encrypt a public key alongside a message with AES? If I have a message M and a public key P, and I encrypt them alongside one another:

CIPHER = AES(M + P, aes_key)

Is CIPHER now weakened if someone knows what P is? It seems like if I encrypted only P:

CIPHER = AES(P, aes_key)

that it should be possible to recover aes_key from CIPHER. I realize that this is different than encrypting M + P, but is a weakness introduced?

My goal is to be able to send a signed encrypted message without revealing the originator publicly.

Probably not in this case, although not for the reason you gave.

As @Sadeq points out in the comments, AES is resistant to known-plaintext attacks. This means that by simply knowing M+P or P (the entire plaintext you've encrypted) it should not be possible to recover the AES key.

However, key recovery isn't the only attack and it raises a deeper question: authentication.

This design which sends the signer's public key along with the message seems to imply that the recipient doesn't already know what key the message should be signed by.

If the recipient doesn't know exactly what key the message should be signed by in advance, then he probably shouldn't just accept any random public key for the signature. Even when the AES key is negotiated perfectly securely, the CBC and CTR modes suggested by @sadeq can allow an active attacker to manipulate the decrypted plaintext in well-controlled ways. An attacker could possibly anticipate the signing key and replace it with his own, or selectively corrupt bits of it and observe the recipient's timing and behavior to identify the actual signing key.

It also raises the important question of how the AES key was negotiated securely. How do the sender and recipient know they're not talking to a man-in-the-middle? Maybe you've already addressed that somehow, I don't know.

Of course, there are systems which enable one to securely accept a new public key. For example, if it is signed by a trusted third-party like a certificate authority. But these systems are usually not optimized for anonymity and they raise additional complications for your goal. Address issues of key enrollment, revocation, expiration, etc. from the beginning.

As usual, the strong authentication problem is the harder one here. Solve the authentication and then come back and think about the encryption. It will be much easier to identify and prevent the active attacks that way.


Can the OpenSSL random number generator be considered cryptographically secure? The OpenSSL Random Number generator documented here
uses an OS-provided entropy source coupled with a MD5 hash function.

Does it impact the quality of randomness to use a broken cryptographic hash such as MD5 for random number generation?  The topic is partially addressed in this question, with a focus on SHA1 rather than MD5 tough.

And if any impact, of which nature? Is it a risk of the RNG being predictable?

Back to OpenSSL: Though selecting another hash function seems to be doable at compilation time, there is no (apparent) configuration setting to change the MD5 to SHA2. So if there's any impact, I'd expect that most OpenSSL instances today are affected.

Can the openSSL random number generator be considered cryptographically secure?

Yes.

  Does it impact the quality of randomness to use a broken cryptographic hash such as MD5 for random number generation?

Not as far as we know. The question you link does, in fact, cover this topic adequately. To quote it to answer your question:

  And actually, collisions in a PRNG output are nothing to be feared. You would expect these to occur naturally (but infrequently) as you produce the output. Random numbers repeat sometimes. What's important is that again given a long sequence of output, we can't at the moment discover the input sequence and therefore the generator's internal state.

This CSPRNG is, with modern (2019) hardware, secure, with there being a very minimal risk to the RNG being predictable.


What is the diffrence between Feistel networks and SPN? I recently read about the concept of Feistel Networks and Substitution Permutation Networks but what is exactly the difference between the two ?

In a Feistel networks (from the German IBM cryptographer Horst Feistel), the input is divided into two blocks ($L_0$ and $R_0$) which interact with each other. Main example is DES.

basic construction:

In a SPN (Substitution Permutation Network), the input is divided into multiple small blocks, applied to a S-box (substitution), then the bits positions are mixed (permutation). The key addition may occur before or after these two operations.

Present block cipher:


What is the advantage of using the socialist millionaire protocol to authenticate vs HMACing some random number? Say Alice and Bob have a shared secret $s$.

Alice and Bob establish an encrypted channel and verify that it hasn't been MitM'ed by exchanging $r_1$ and $r_2$, where $r_1$ and $r_2$ are randomly generated by Bob and Alice respectively and sent over the channel. Alice computes $\operatorname{HMAC}(C \mathbin\| r_1, s)$ and Bob computes $\operatorname{HMAC}(C\mathbin\|r_2, s)$ where $C = \operatorname{HASH}(\text{Communication-channel})$ and they exchange values:

A & B: $C = \operatorname{HASH}(\text{Communication-channel})$
A → B: $r_1$, $\operatorname{HMAC}(C \mathbin\| r_1, s)$,
B → A: $r_2$, $\operatorname{HMAC}(C \mathbin\| r_2, s)$
A & B recalculate $\operatorname{HMAC}(C \mathbin\| r_2, s)$ and $\operatorname{HMAC}(C \mathbin\| r_1, s)$ and verify that they match the received values.

At this point Alice should trust that Bob knows $s$ and has the same value of $C$, and vice versa.  If Eve had carried out a MITM attack on the channel, the HMACs would fail, because $C$ would be different for Alice and Bob.

What differences would there be if the socialist millionaire protocol was used to establish that $s$ is shared?

The problem with the HMAC-based solution you drew up is if the shared secret $s$ has low entropy; for example, it's actually a password that could conceivably be in a dictionary.

In this case, someone could listen to the exchange $r_1, \operatorname{HMAC}(C \mathbin\| r_1, s)$, and go through his dictionary of possible values of $s$, and see if any one of them makes the HMAC be the expected value; if so, he can MITM (or just pretend to be either Alice or Bob).

If this is a possibility, it's generally a good approach to use a Password Authenticated Key Exchange; this is a protocol that solves the socialist millionaire problem, and also generates a secret value which is the same on both sides if both sides have the same password.  This secret value is useful because it can be used to derive keying data; then can be used to prevent MITM attacks after the PAKE protocol has completed.

Now, one thing that a PAKE protocol can't prevent is someone making a guess at the shared secret $s$, and attempting to log in using that value -- if his authentication attempt is successful, he knows that he guessed correctly.  What PAKE can do is prevent any more efficent approaches; to test 1000 possible passwords, the attacker would need to attempt 1000 authentication requests.

On the other hand, if you have a strong $s$ which is immune to a dictionary attack (for example, it's a 128 bit random number), and you don't care about Perfect Forward Secrecy (which a PAKE will also provide), then a PAKE is overkill -- your simpler approach using HMAC may be preferable (and, don't forget, you would need to bind the rest of the conversation with the authentication exchange, such as generating a shared key based on $s$).


Will varying plaintext compensate for a fixed initialisation vector? This is a follow-up question to Relative merits of AES ECB and CBC modes for securing data at rest.

I need to store encrypted Personal Account Numbers (PANs) in a database. The only encryption option I have available is CFB mode with a fixed (0x00) IV. I can choose my cipher, and have chosen AES-256.

Encryption and decryption are performed without the need for the application to 'know' the key, which is stored securely 'elsewhere'.

For the sake of this exercise, the PANs are 16-byte numbers (16 decimal digits); the attack I'm currently addressing is theft of a copy of the database, with all the encrypted PANs, any of which can be repeated.

I fully understand that the use of a constant IV is a weakness, but this is beyond my control.

Will any of the following options mitigate the weakness?:

I have an 8-byte binary clock available whose contents change once every microsecond or better, and which repeats every ~130 years. I prepend this clock to the plaintext PAN before encryption, and discard it after decryption.
The same, except that I prepend and discard two copies, to complete the first 16-byte block.
I generate 8 bytes of random data and prepend.
I generate 16 bytes of random data and prepend,

Specifically, I should like to know:

a. Are 16 bytes sufficient while 8 are not?

b. Are random bytes sufficient while the µsec clock is not?

c. Do these options completely compensate for the weakness of the fixed IV?

At the risk of flogging a dead horse, some additional comments, following the excellent answers (especially from @D.W.)

I have always agreed to the principle of 'Do not roll your own', but now, even more so.
I think it relevant to point out that these 'messages' never transit, but are only stored 'at rest', and that the attack I'm defending against in this exercise is 'they stole my database'. So I'm not sure what
D.W.'s chosen plaintext attack is a real eye-opener.
In this scenario (input, charge, store, perhaps retrieve for refund), I'd like to understand better what advantages authentication would bring me.
I'd welcome further comment on using the TOD clock as an IV. Here are some additional details:

The TOD clock is 64-bit integer representing the elapsed time since 00:00 on Jan 1,1900.
The clock is updated in such a way that bit 51 is guaranteed to be updated once per microsecond. Bits 0-51 are the unsigned number of elapsed microseconds.
On faster machines, bits in the range 52-63 are also updated at their corresponding frequencies.
The system in question runs as a single image on a single real machine.
Clock synchronisation is unlikely to set the clock backwards, but let's analyse that case:
If at peak I'm doing 100 encryptions per second (the real number is a lot less), and I assume the slowest clock (1M per second). Let's suppose that the clock gets set back by 5 seconds (I believe that to be extraordinarily extreme. It's GMT, by the way so there's no daylight saving)
Now, I apply the birthday paradox to 1000 encryptions (5*(100+100)) in 5 million; the probability of two or more synonyms is less than 1.3E-7

I recommend that you prepend a random 16-byte prefix.  Prepending a random 16-byte prefix, before encrypting with your CFB mode, will be just as good as using a random IV. The argument is pretty similar to Using CBC with a fixed IV and a random first plaintext block.

If we use CFB with an all-zeros IV and a random 16-byte value prefixed to the message before encryption, as you suggested, we get a scheme that looks like this:

$C_0 = 0$

$C_1 = E_K(C_0) \oplus IV$

$C_2 = E_K(C_1) \oplus PAN$

where $E_K(0)$ is a constant and $IV$ is your random 16 byte value. Since a constant xor-ed with a random value is itself random, the above has the same properties as:

$C_1 = IV$

$C_2 = E_K(C_1) \oplus PAN$

which is the standard CFB construction (with a random IV) with different indices.

Strictly speaking, the 16-byte prefixes don't need to be random.  The above approach is probably secure as long as the 16-byte prefixes are all unique. If you pull 16 random bytes from a well-seeded crypto PRNG, they should all be unique. But I don't trust your other schemes to produce unique values.  Therefore, I don't recommend using any of your other approaches.

Note that while this technique of prepending a random prefix works for some modes, such as CBC or CFB, other modes, such as OFB or CTR are totally broken in such a scenario.


Would this method allow fast authenticated encryption using only a single encryption operation per block? [This approach is flawed. A different speculative approach using an RNG instead of the cipher as a source of entropy was posted as a separate question]

Assume $E$ is a block cipher, $C_0 = IV$ and $P_0 = 0$

Encryption:

Add an additional block to the message and store the key in it, ie. $P_n = Key$.
Encrypt all non-final plaintext blocks $P_k, 0 < k < n$ in the following way:
$C_k = P_k \oplus E(C_{k-1} \oplus P_{k-1})$
Encrypt the final plaintext block $P_n$ (containing the key) in the following way:
$C_n = E(P_n \oplus E(C_{n-1} \oplus P_{n-1}))$

Decryption:

Decrypt all non-final ciphertext blocks:
$P_k = C_k \oplus E(C_{k-1} \oplus P_{k-1})$
Decrypt the final ciphertext block:
$P_n = D(C_k) \oplus E(C_{n-1} \oplus P_{n-1})$

Authentication

Verify $P_n = Key$

Note the number of encryption operations is actually $n+1$, so the title is slightly inaccurate (mentioning that would have made it too long). Also, it may not be completely essential to store the key - A non-secret value might work, but I'm being cautious for now..

Please try be constructive, as even if this is flawed in its current state it might be possible to fix it without adding a significant amount of expensive operations.

This does not meaningfully authenticate the ciphertext. Your encryption is the same as OFB, meaning no block depends on the previous plaintext; for instance, $$C_2=P_2\oplus E(P_1\oplus (P_1\oplus E(IV\oplus 0)))=P_2\oplus E(E(IV)).$$ That means confidentiality should be fine; however, it provides no authentication except of the length of the message.


Successful Cryptanalysis Research/Attacks on Zero-Knowledge Proofs? A robust implementation of any cryptosystem (E.g., AES) has a comprehensive cryptanalysis research/attacks on it.

Are there any successful cryptanalysis research/attacks on zero-knowledge proofs?

For most symmetric cryptosystems, such as AES, the best way to study their security is to design various types of attacks, and to analyze the resistance of the primitive to these attacks. With zero-knowledge proofs, things are in general a bit different:

Zero-knowledge proofs are, in some sense, a "higher level" primitive, which means that they can be (and are, in general) constructed from other primitives.
Unlike symmetric cryptosystems, where the number of "standard primitives" is relatively small, there are hundreds of proposals for zero-knowledge proofs. This means that getting confidence in their security using cryptanalysis would require designing attacks for hundreds of different, non-standardized (and not much used in practice) primitives. That would be kind of a waste of effort.

For the above reasons, the usual (and best) approach to study the security of zero-knowledge proofs is through provable security. Usually, this is done by reducing the security properties of the zero-knowledge proof to the underlying lower level primitive it was built from. This way, cryptanalysts can simply focus on this underlying primitive to give us confidence in the security of the proof. Roughly, the zero-knowledge proofs we know of belong to four categories:

Some have unconditional security. This means that we can prove that they satisfy completeness, soundness, and zero-knowledge, without making any assumption. This is the case e.g. for the standard proof for graph isomorphism, or for the famous Schnorr protocol for knowledge of a discrete logarithm (which only satisfies honest-verifier zero-knowledge). For these proofs, no cryptanalysis is needed.
Some can be reduced to generic assumptions. For examples, the general solution to zero-knowledge proofs for NP from the seminal paper of Goldwasser, Micali, and Rackoff, can be based on any one-way function. This means, in particular, that we can build a proof for any NP statement, whose security (here, soundness is unconditional and zero-knowledge is computational, but we can also get the reverse) would reduce to the assumption that AES is secure. Hence, we can use all cryptanalytic efforts on AES (or SHA3, or any symmetric primitive you can think of) to our advantage when constructing a ZK proof.
Some proofs reduce to specific, well known assumptions. This is usually the case for more "advanced" zero-knowledge proofs. For example, Jen Groth's sublinear zero-knowledge arguments, which allow to prove statements from linear algebra with communication $O(\sqrt{N})$ ($N$ is the size of the statement), is secure under the discrete logarithm assumption. This means that cryptanalytic efforts can focus on algorithms for solving the discrete logarithms, if we want to study the security of these protocols.
Finally, some recent zero-knowledge proofs have more ad-hoc underlying assumptions. This is in general the case of zk-SNARKs, where we give up the reduction to standard and well-known assumptions, in exchange for extreme efficiency (i.e., the proof is non-interactive and of constant size). For these "extreme" proofs, it would make sense to have a specific cryptanalytic research, but as the area is still very young, there are not much results in this direction at the moment.


Is it possible to decrypt an RSA ciphertext with only $N$ and $e$? Is it possible to perform RSA decryption if one only knows $N$ and $e$?

Failing that, what is the maximum key length where brute-force is still practically feasible?

The current best way of decryption an RSA ciphertext (assuming good padding was used) is to factor $N$ into its prime factors $p$ and $q$, and from that, reconstruct the decryption exponent $d = e^{-1} \bmod lcm( p-1, q-1 )$

The current record for factoring an RSA-type modulus (with large prime factors, and not of a special form) is 768 bits.

It is likely that, in the next couple years, slightly larger modulii will be factored; the record for "largest general number factored" has been slowly increasing; someone might manage to factor a 1024 bit number within the next decade.  There is little reason to expect that RSA modulii significantly larger  will be vulnerable to factoring in the near future.


If a cipher has key length shorter than plaintext, then it is not perfectly secure I am trying to verify the statement above. So far I only know that a One-Time-Pad is the only “perfectly secure” cipher. It has a key length which is exactly the same as the plaintext. I think the statement is true but I don't know how to prove it…

Can anyone give me some hints or point me to an according reference or two?

Here's a more "down to earth" example. The following cryptosystem with plaintext space $\mathcal{M} = \{a,b,c,d\}$, keyspace $\mathcal{K} = \{1,2,3,4\}$ and ciphertext space $\mathcal{C} = \{A,B,C,D\}$ has perfect secrecy:

$$\begin{array}{c|c c c c}
& 1 & 2 & 3 & 4 \\
\hline
a & A & B & C & D \\
b & B & C & D & A \\
c & C & D & A & B \\
d & D & A & B & C
\end{array}$$

if the key is chosen uniformly at random independently of the plaintext (the table should be read as saying that, for example, encryption of the plaintext $a$ with the key $3$ yields the ciphertext $C$). The perfect secrecy means that an attacker who obtains a ciphertext has no "hint" about what the plaintext may be: for example if an attacker obtains the ciphertext $C$, it could be the result of encrypting the plaintext $a$ with the key $3$, or the plaintext $b$ with the key $2$, or the plaintext $c$ with the key $1$, or the plaintext $d$ with the key $4$, and all those cases will occur with probability $1/4$. By comparison, the following cryptosystem:

$$\begin{array}{c|c c c c}
& 1 & 2 & 3 & 4 \\
\hline
a & A & A & C & D \\
b & B & C & D & A \\
c & C & D & A & B \\
d & D & B & B & C
\end{array}$$

does not have perfect secrecy because if an attacker obtains the ciphertext $A$, he knows that the plaintext is not $d$, and it is also more likely that the plaintext is $a$ (which is the case with probability $1/2$) than $b$ or $c$ (probability $1/4$ each).

On the other hand, with the following cryptosystem with keyspace $\mathcal{K}' = \{1,2,3\}$:

$$\begin{array}{c|c c c c}
& 1 & 2 & 3 \\
\hline
a & A & B & C \\
b & B & C & D \\
c & C & D & A \\
d & D & A & B
\end{array}$$

an attacker obtaining the ciphertext $A$ knows that the plaintext is not $b$, so this system does not have perfect secrecy either, and it is easily seen that any cryptosystem with fewer keys than plaintexts will have the same problem.


Necessity for finite field arithmetic and the prime number p in Shamir's Secret Sharing Scheme Shamir's original paper (PDF, 197kb) describing a threshold secret sharing scheme states:

  To make this claim more precise, we use modular arithmetic instead of
  real arithmetic. The set of integers modulo a prime number $p$ forms a
  field in which interpolation is possible. Given an integer valued
  data $D$, we pick a prime $p$ which is bigger than both $D$ and $n$. The
  coefficients $a_1,...,a_{k-1}~$ in $q(x)$ are randomly chosen from a uniform
  distribution over the integers in [0, $p$), and the values $D_1,...,D_n$
  are computed modulo $p$.

Where:

$D$ is the secret to be shared
$n$ is the number of shares
$k$ is the threshold number of shares needed to reconstruct $D$
$q(x)$ is a $k-1$ order polynomial with $q(0)=D$ and the coefficients $a_1,...,a_{k-1}~$
$D_1,...,D_n$ are individual shares (points on the polynomial $q(x)$)

Can someone please explain (in the simplest possible manner) the reason that Shamir's Secret Sharing Scheme uses finite field arithmetic? Also, why must the size of the Galois field be a prime number with the requirements that Shamir put forth?

The reason for asking these questions is: I would like to implement Shamir Sharing in Javascript using a field of size $2^8 = 256$, which:

will obviate the need for a big integer library for Javascript, such as jsbn
will simplify the math.

Whatever the size of the secret to be shared, it could be broken down into byte-length segments and the math performed on those segments. The resulting share would be a concatenation of the results of the necessary operations on each segment.

To find the secret, the shares can again be broken down into byte-length segments. The polynomial interpolation can be done with the corresponding byte-length segments from the shares to get individual segments of the secret. The segments can then be concatenated to form the complete secret.

Would this work and be cryptographically secure?

If there is indeed an absolute necessity for a prime number $p$, could I use any small prime number with the concatenations described to perform the necessary operations in Javascript and still remain cryptographically secure?

There is no reason in Shamir's scheme for the finite field $\mathbb F$
to have a prime number $p$ of elements; the field can have $p^m$ elements for
suitable prime $p$ and integer $m \geq 1$.
So, using $F_{2^8}$, the field with $2^8$ elements is perfectly all right.
However, choosing $m = 1$ has the advantage that calculations in $\mathbb F_p$
can be done using the
standard arithmetic unit included in microprocessors and the like (followed
by integer divisions for doing the mod $p$ operations) whereas using
$\mathbb F_{p^m}$ requires having a library already available (or developing
one) or building a processor for arithmetic in the field.

Given that you have the capability of doing arithmetic in $\mathbb F_{2^8}$,
you can use this field if you like. But, (as you say) in Shamir's
scheme, the secret is just one element of the field (one $8$-bit byte),
and so, if the Secret to be shared is several bytes long, you will
need to process each byte separately into its (one-byte) shares, and
concatenate the $i$-th share bytes into the $i$-th Share of the Secret.
Keep in mind that each byte  can be divided into at most $255$ shares
(the point $q(0)$ on $q(x)$ cannot be used for obvious reasons),
and so if you need to have more than $255$ shares to distribute, you
will have to use a different field. Finally, to maintain cryptographic
security, as the shares corresponding to each byte of the Secret are
being computed, you should do exactly what you say you are doing
in your comment:
use a different set of "randomly chosen coefficients" for $q(x)$,
rather than re-use the same set over
and over again for finding the shares of all the bytes.


AES encryption using a Diffie-Hellman key exchange I have two systems which need to encrypt their communication by AES-128. The key for the AES encryption should be exchanged with the Diffie-Hellman (DH) algorithm.

Now, I've read about DH and got a lot of question marks over my head. These are my questions:

Typically with AES-128, you need a password and a key which will be generated from the password. What exactly will be exchanged with DH, is it the password or the key? In other words, what is the secret that Alice and Bob will calculate?
If I use a 1024 bit prime and a 256 bit private secret for DH, the calculated secret will consist of a lot more than the required 128 bit for AES-128. How can I transform the secret to match the required 128 bit? Is there a standard to do it, because the two systems use different programming languages?

You see, there is a lot of confusion. Maybe you could help me and shed some light on it.

There is nothing related to passwords in AES. AES uses 128-bit keys, i.e. sequences of 128 bits. How you come up with such a key is out of scope of AES. In some contexts, you want to generate these 128 bits in a deterministic way from a password (and possibly some publicly known contextual data, like a "salt"); this is a job for password hashing. In other contexts, in particular the one you are talking about, there is no password.

In Diffie-Hellman, computations occur modulo a big prime p, and the resulting shared secret is an integer modulo p, i.e. a value ranging from 0 to p-1. This value has some "structure" so you should not truncate it blindly. The "safe" way is to apply a hash function on an encoding of that value, for instance SHA-256. The hash function output is then what should be used as key (with possible truncation to get the proper length; at that point, this is safe). There are standards which describe such a process in full details.

Of course, you are in the process of reinventing your own homemade kind-of-SSL, and that is a thoroughly bad idea in general (unless you are doing it for pedagogical reasons, e.g. as homework). A really secure protocol will need key exchange, proper symmetric encryption, integrity checks and at least one-sided authentication, so you will have to assemble at least three cryptographic algorithm. Every single detail can doom your security, both in the design and in the implementation. This is hard. It took two decades of hard labour, from hundreds of the best cryptographers, to come up with a decently secure version of SSL.

So there is a standard, it is called TLS (the "standard" name for SSL).


Does the output of a cipher have to be no longer than the input? I have recently been playing around with cyphers and creating some simple ones to practice and improve my programming skills, and I recently created a cipher which in my opinion is very complex and secure, even utilising binary, and then I started to wonder whether or not my cipher could actually be used, so after doing a little bit of research I found out that, apparently, a cipher isnt good unless its the same length as the original? so if you input "password" my cypher outputs "[.##4959#12#41#8#{20", a very complex algorithm is used here, and my idea was that this cipher would be used with short pieces of text/numbers, like passwords or bank account numbers. so is my cypher useless?

a cipher isnt good unless its the same length as the original?

This is completely false. In fact, with most modern block cipher modes of operation, you will get ciphertext lengths that are longer than the original input. In fact, a ciphertext length longer than the input is a requirement for integrity protections (which is a must-have these days).

  so is my cypher useless?

This we cannot judge given the information you've posted. Ciphertext to plaintext length ratio is meaningless when it comes to determining the utility of a cipher. If you want to know if your cipher is useful, you need to 1) publish the full details of the algorithm, 2) describe its benefits when compared to existing ciphers (what new capabilities does your cipher give me that I don't already have with AES), 3) get a bunch of really smart cryptographers to work on breaking it for years.


Security of integrity protection with HMAC vs AEAD I'd like to know how the security of the integrity protection compares between:

HMAC-SHA-256 with an 32 byte tag or a truncated 16 byte tag
AES-GCM with a 16 byte tag
AES-CCM with a 16 byte tag or with a 8 byte tag

Assuming that no side-channel data is leaked and all algorithms are used securely.

For any $k$-bit MAC, an attacker blindly guessing a tag has a one-in-$2^k$ chance of successfully forging a message.  Thus, the expected number of attempts needed to forge a message by brute force is $2^{256}$ for a 32-byte tag, $2^{128}$ for a 16-byte tag, and $2^{64}$ for an 8-byte tag.

In practice, attempting $2^{128}$ forgeries is far beyond the reach of any plausible attacker, whereas $2^{64}$ attempts might just barely be feasible in some scenarios.

As far as I know, the best non-brute-force attack on HMAC-SHA-256 is the generic birthday attack on iterated MACs described by Preneel and Oorschot (1999), which allows an attacker to forge a message after finding an internal state collision in the MAC computation.  For SHA-256, this would require obtaining MACs for about $2^{128}$ messages, and can thus be safely ignored.

In fact, Bellare (2006) has proven lower bounds on the security of HMAC that are close to the upper bounds given by Preneel and Oorschot, assuming that the hash function used satisfies certain security assumptions (in particular, that its compression function is a PRF, or at least a PP-MAC).  Thus, assuming no disastrous new attacks on SHA-256 arise, HMAC-SHA-256 with at least a 16-byte tag should be secure against any feasible attacker.

For GCM / GHASH, there do exist attacks better than brute force.  In particular, Ferguson (2005) shows that an attacker can forge an $n$-block message with a $k$-bit tag with probability $n/2^k$.
GCM limits the maximum message length to $2^{32}-1$ blocks, so, for a maximum-length message, the forgery probability is about $2^{32}/2^{128} = 1/2^{96}$ for a 16-byte tag, and about $1/2^{32}$ for an 8-byte tag.

While the former is still generally acceptable, the latter may not be, especially as GCM has an unfortunate property, also described by Ferguson, whereby each confirmed successful forgery reveals information about the authentication key, and thus makes successive forgeries much easier.  Thus, echoing Ferguson's recommendation, I'd advise against using GCM with a tag length shorter than 16 bytes.

As for CCM, I'm also not aware of any attacks better than brute force.  The Preneel and Oorschot attack is not directly applicable to CCM (even though it does apply to CBC-MAC), because the tag is encrypted using CTR mode with a unique nonce, and thus an attacker cannot directly detect internal collisions in the CBC-MAC state.  Even if it did apply, the CCM specification limits the total amount of block cipher evaluations made with a single key to at most $2^{61}$, which is less than the expected number of queries needed to find one collision (although not very much less; a more conservative limit would be, say, $2^{40}$ cipher evaluations per key).

Jonsson (2002) has proven a lower bound on the security of CCM mode that is similar to the Preneel and Oorschot bound, in that the success probability of an attacker making $q$ forgery attempts comprising a total of $m$ blocks, and having access of $n$ blocks of valid messages, has a success probability less than $q/2^k + (m+n)^2/2^b$, where $k$ is the bitlength of the tag, and $b$ is the blocksize of the underlying cipher ($b = 128$ for AES).

This bound is rather conservative, and indeed, Jonsson himself has conjectured, but not proven, a bound on the forgery probability that is linear rather than quadratic in the number of encrypted blocks.  In fact, Fouque et al. (2008) have managed to prove this, but only for a variant of CCM mode using independent encryption and authentication keys.  As far as I know, for regular CCM, this question is still open; of course, as long as the number of blocks processed with a single key remains well below $2^{64}$, it is purely of academic interest.


What does "learnable with oracle queries" mean? I came across the following quotes in reading papers on obfuscation (1, ibid, and 2):

  The next result follows from the fact that point functions are not exactly learnable (since a uniformly chosen point function is statistically indistinguishable from the all-zeroes function given a polynomial number of membership queries).

and

  A family of circuits $C \in C_n$ is obfuscatable against general adversaries iff $C$ is (nonuniformly) efficiently and exactly learnable using membership queries.

and

  Of course, if the function is (exactly) learnable via oracle queries (i.e., one can acquire a program that computes the function by querying it at a few locations)

What does it mean to say a program is learnable using membership queries? Or alternatively, I've seen it as "learnable with oracle queries". And what is the impact of it? Does it mean that we can learn what exactly the program does or just enter input and receive the result of the program running in each step? Without knowing which mathematical action influenced it?

A family $\mathcal{C}$ of circuits/functions is "learnable with oracle queries" if there is an efficient "learning" algorithm $L$ that, given oracle (or "black box") access to any $C \in \mathcal{C}$, outputs a circuit $C'$ (or other representation) that is equivalent to $C$, i.e., it agrees with $C$ on all inputs.

Oracle ("black box") access to $C$ means that $L$ can repeatedly query any values $x_i$ in the input domain of $C$, and receive $C(x_i)$ as the answer.  Note that $L$ does not see how the output value $C(x_i)$ is computed, how many steps it takes to do so, etc.  It just gets the value itself.

For example, consider the class of functions $\mathcal{C} = \{C_w(x) = \langle x, w \rangle \bmod 2 \}$.  Each function $C_w(x)$ is simply the mod-2 inner product of some fixed $w \in \{0,1\}^n$ with the input $x \in \{0,1\}^n$.  (This is often called the class of "parity" functions.)  This class is learnable with oracle queries: given oracle access to some $C_w$ (where $w$ is initially unknown), the learning algorithm simply queries its oracle on $e_1=(1,0,\ldots,0)$, and receives $C_w(e_1) = \langle e_1,w\rangle = w_1$.  It similarly queries all the other standard vectors $e_i \in \{0,1\}^n$, and receives each bit $w_i$ in response.  After $n$ queries it knows $w$ entirely, which is equivalent to knowing a circuit for $C_w$.

What this has to do with obfuscation: if a class $\mathcal{C}$ is learnable by oracle queries, then one can obfuscate (according to the "virtual black box" definition) any code that computes a member of that class.  The obfuscator is essentially just the learning algorithm: given any program/circuit that computes a function $C \in \mathcal{C}$, the obfuscator simply uses the code to answer the queries of the learning algorithm (by just running the code on the query).  The obfuscator then outputs whatever code/circuit $C'$ the learning algorithm outputs.

This is a VBB obfuscator because a simulator that is given only black-box access to the function $C$ can do exactly the same thing (run the learning algorithm, using the oracle to answer queries).  Notice, however, that this obfuscator is not actually "hiding" anything about the function that it's obfuscating; in fact, it's arguably revealing everything about that function!  This still comports with the VBB definition of obfuscation, however, because any code that computes the function reveals everything about the function.  So one might as well give out a "canonical" representation of the function, like the one computed by the learning algorithm.


Is it possible for the Rho method against an Elliptic Curve to take more than the sqrt of the total state space? Is it possible for the Rho method against an Elliptic Curve to take more than the sqrt of the total state space? It the reason why this is not generally done because of a meet-in-the-middle attack?

The Rho method is probabilistic, so it's possible you could find the solution within the first few iterations, or after you've generated almost the entire space.

The probability starts getting in your favor around the square root of the order, because that's when the probability reaches approximately 50%. Since the probability increases quadratically, it's very likely to find a solution shortly after passing that point.


Help understanding syntax used in security proof I am looking through this paper and am trying to understand the proofs better. One of the theorems the authors are proving (Theorem 5.1) contains syntax of Adv followed by "cdh" in the superscript and some values as parameters within parentheses after. I've posted an image of the theorem in question for convenience. What does this syntax mean and what do the parameters for it mean?

A simple way to understand it is to consider that the best algorithm we know to break CDH in $\mathbb{G}$ has advantage (id est: probability to win) is $\mathbf{Adv}^{\text{cdh}}_{\mathbb{G}}$.

You can suppose that this parameter is very small (exponentially small).

The goal of this theorem is to prove that if an adversary could break ake of SPAKE, $\mathcal{D}$, then this advantage (probability to win) is smaller of the right expression.

By looking the right expression, you deduce it's small (because $\mathbf{Adv}^{\text{cdh}}_\mathbb{G}$ is exponentially small)


What is the definition of dummy password? Recently, I try to read some papers about Password Authenticated Key Exchange (PAKE).  I can’t understand the meaning of “dummy password .” Can someone gives a concrete definition of it. And what is the difference between password and dummy password?

The context for this question is the following sentence:

  then, we modify the protocol so that $\pi$ in $y$ is a dummy password

It appears this term is only used in the proof. In this context "dummy password" is to be understood as
"some value that syntactically fits the requirements of a regular password including matching the length of the replaced password but is not actually the password to be used in this exchange".
The point here is that an adversary cannot distinguish between the actual password being contained in a value and some other "fake password" being contained in a value which then allows one to argue that an adversary learns nothing about the password given that they can't even tell whether the real one is used thus helping in proving that the exchange leaks nothing about the value of the password.


Vulnerabilities of AES method that uses MD5 to create the key Are there security vulnerabilities given the would a user be able to access the original text and the encrypted text with AES using an MD5 as a key?

In other words, if the user had both the original and encrypted text, is it possible for the user to encrypt and decrypt their own text or an altered version of the site's text?

I am specifically wondering about this based on the security of the MD5 hash.

Full Code:

class AESCipher:

def __init__(self, key):
    self.key = md5(key.encode('utf8')).hexdigest()

def encrypt(self, raw):
    raw = pad(raw)
    iv = Random.new().read(AES.block_size)
    cipher = AES.new(self.key, AES.MODE_CBC, iv)
    return b64encode(iv + cipher.encrypt(raw))

def decrypt(self, enc):
    enc = b64decode(enc)
    iv = enc[:16]
    cipher = AES.new(self.key, AES.MODE_CBC, iv)
    return unpad(cipher.decrypt(enc[16:])).decode('utf8')

No, if the input key has enough entropy then using an MD5 hash will not reduce the security of AES. And AES protects the retrieval of the key from any combination of plaintext and ciphertext. MD5 can be seen as a poor man's (Key Based) Key Derivation Function or KDF which extracts (compresses) the entropy found in the input key material.

However, a lot of times MD5 is used instead of a Password Based Key Derivation Function or PBKDF (bcrypt, scrypt, PBKDF2 and the newer Argon2 variants are well known PBKDF's). If the input is a password or text then it is likely that a low amount of entropy is present. In that case it is easy to guess the input of MD5. The resulting AES key may seem secure and randomized, but the adversary may guess the input - for instance by using a dictionary attack - and perform the MD5 calculation to retrieve the AES key.

MD5 has been broken and the usage of MD5 is a red flag, often indicating that the developer hasn't got a clue about cryptography. This is true regardless if MD5 is used in a secure setting or not. The use of MD5 is often not by design, but because the developer copied another bad example of cryptography. In your case, the MD5 hash is hex encoded and then used as 256 bit key. Although using 128 bits (max) of entropy as 256 bit key doesn't break AES in practice, it does show that the developer wasn't a cryptographer himself.

If the quality is that bad, you can almost be certain that other errors have been made. In your example code, CBC mode could be used directly to achieve transport security, making padding oracle attacks a distinct possibility.

Please learn at least the basics of encoding and cryptography. Whatever you do, don't use self-made protocols like the one in your question. Try and use higher level frameworks or transport protocols such as TLS instead. You have been warned - and it is good you asked.


Is the IV value in Davies Meyer construction public? I am learning the construction of Davies-Meyer to construct a hash function from block ciphers. The definition that I found is

$$H_i=E_{m_i}(H_{i-1})\oplus H_{i-1}.$$

where $E_k$ is a block cipher with key $k$.

My questions are:

1) Who is $H_0$, is the Initial Value (IV) as any hash function, that is Is that value public?

2) Suppose the follow case: the key size is 64 and the block size is 32, What happens if I need to evaluate the hash of the message $1$?

With respect to the question 2), I think that is necessary to complete with zeros until complete 64 bits the message $m_0 = 1$, then

$$H_1=E_{0000..00001}(IV)\oplus IV$$

but In this case it is easy to retrieve $m_0$ because the plaintext and the ciphertext are know. Where I am make mistake?

(See also Why are the Davies-Meyer and Miyaguchi-Preneel constructions secure? for a related question.)

Is that value $H_0$ public?

Well, one property that a hash function has is that anyone can evaluate it.  To evaluate a Davies-Mayer hash, you need the value $H_0$, and so yes, it needs to be public.

  I think that is necessary to complete with zeros until complete 64 bits...

Minor correction there: while Davies-Mayer requires us to pad the message so that it is an even multiple of block sizes long (64 bits in your toy example), we wouldn't want to append zeros.  The reason is that we hope that the hash function is collision-resistant (that is, someone couldn't find two different messages that hash to the same value); with the pad-by-appending-0's method, what someone could do is take a message, and append a 0 bit; as long as the original message wasn't a multiple of 64 bits, then the post-padded versions of the two messages would be identical, and so the hashes would be identical.  What we could do instead is either append a '10000...000' pattern, or append a pattern that includes the original text length.  Actually, common hash functions that are based on Davies-Mayer (SHA-1, SHA-2) do both.

  In this case it is easy to retrieve $m_0$ because the plaintext and the ciphertext are known

First, a minor correction: the concern is not that we keep the message secret, but instead that it should be infeasible to find preimages; that is, given a hash value, it should be infeasible to find a message that hashes to that hash value (and it doesn't matter if the message that the attacker finds is the same message that was originally hashed).

In any case, no, it is not easy to find a value $m_0$, if we assume that $E$ is a strong block cipher.  With strong block ciphers, we make the assumption that, given a plaintext/ciphertext pair, we cannot recover the key.  This implies that there isn't a direct way to immediately recover $m_0$.

Of course, with the parameters that you give (32 bit block size), what an attacker could do is try $2^{32}$ different $m_0$ candidates; if he hashes all those values, he is likely to find one that hashes to the $H_1$ value.  Because of this, Davies-Mayer requires us to use block ciphers with much larger block sizes.


How to choose the linear approximations to build a path through a SPN in Linear cryptanalysis? so I am reading up on Linear Cryptanalysis using Heys' Tutorial. I understood how to get "good" linear approximations of the S-boxes though I cannot seem to find a reasonable approach to combining them together. In the paper on page 12 the approximations used seem to be specifically hand-picked to work for the particular P-boxes. Anyway they pretty much appear out of nowhere and I am not sure how one would approach finding them in the first place.
This seems to be a optimization problem but I am having trouble formulating it. Please enlighten me, maybe I am on the wrong track somewhere.

I think this is what you are asking. You have to respect the permutation layer, otherwise canot apply the piling up lemma.
The approximations must be "joined together" between rounds by respecting the P-box mapping, so that they can be "added together with cancellation" to get multiround linear characteristics.
Say you apply an approximation $$a\cdot x\oplus b\cdot S(x)$$ to Sbox $S_{1,1}$ [round 1, 1st sbox] whose output constant $b$ is [1,0,0,1]. If you follow the wires at the output of this Sbox, you can see that you need to apply some linear approximation $$a'\cdot x \oplus b \cdot S(x)$$
where $a'=[1,0,0,0]$ to Sboxes $S_{2,1},$ and $S_{2,4}$. Then you use the fact that the key bits cancel and apply the piling up lemma to get a 2 round approximation involving Sboxes $S_{1,1},S_{2,1},S_{2,4}$.
Where is the optimization? You need to stick to relatively low hamming weight $b$ vectors to avoid turning on too many S-boxes since the piling up lemma is multiplicative and each new active S-box reduces the overall bias. You also want to find the highest individual bias characteristics.
In general, this needs to be checked exhaustively.
The following answer gives more general details about linear approximations:
Help with linear cryptanalysis


What exactly is inside a private key? May sound stupid to many, but I would like to have some pointers on what exactly is contained inside a private key. I have decent understanding of public/private keys/certificates (have created them many times) and their purpose but would like to take a step back and see what is inside them using a "dump" utility or something - Would I be able to see big prime numbers etc contained inside the private key?

Is there a utility to show me the "logical content" of the output of the following command as opposed to a bunch of ASCII characters?

openssl genrsa

generates

-----BEGIN RSA PRIVATE KEY-----
MIIBPAIBAAJBANdINmZY7VuoRy5VZYwnVIAE/0sd/HkaDVXfMNpwVeKo7K2XLC6U
jpnPFP2MaDEqxs0T6cKVMmt5FsNGyfdKbvcCAwEAAQJBAMGuPQrtPHY2uftsZtSl
2bbnSAr7qlYFYzP7fYc4g3xLWSc5viAe7KgsU7+jXNCqEvflf4iOxhCadUK07APG
…
-----END RSA PRIVATE KEY-----

Any pointers appreciated. Same question also applies to the public key btw..


Length of truncated HMAC output RFC 2104 says:

  Applications of HMAC can choose to truncate the output
  of HMAC by outputting the t leftmost bits of the HMAC
  computation for some parameter t [...]. We recommend
  that the output length t be not less than half the
  length of the hash output (to match the birthday
  attack bound) and not less than 80 bits (a suitable
  lower bound on the number of bits that need to be
  predicted by an attacker).

Obviously, different lengths of HMAC outputs provide different levels of security. What's not obvious to me, is: If one needs the security provided by a 128-bit MAC, why is HMAC-SHA-256 suitable to generate such (half the length of the hash = 128 bits) but HMAC-SHA-512 is not (half the length of the hash = 256 bits)?

HMAC doesn't suffer the issue with collision resistance (in other words: the birthday bound does not apply). This is simply because an attacker doesn't have the secret key used to generate the HMAC authentication tag, so there is no way to build a huge table of possible outputs that can be compared against.
So usually the security of a hash is defined as half the number of output bits because of the birthday bound. To get the same level of security you can therefore output half of the output bits of HMAC because the birthday attacks do not apply.
You can use HMAC-SHA-512 to generate 128 bits of security by using the leftmost 128 bits (and it may even be slightly faster than HMAC-SHA-256 for large messages on a 64 bit CPU). However, it won't deliver the maximum security that can be provided by HMAC-SHA-512 - not that you would ever need 512 bits of security.

Note that the 80 bit security is half the output size of SHA-1 (or RIPEMD-160 for that matter). Nowadays 80 bits is not considered (all that) secure anymore.


Alternative block cipher design paradigms to SP-networks and Feistel-like ones? Before I familiarized myself with the type of cryptography that became popular with the rise of the information age, I was very much into what the community seems to call "classical" ciphers: Caesar shift ciphers, the Vigenère cipher, grilles, scytales, the Playfair cipher, the Enigma machine, and a few other techniques that might not qualify as ciphers. There were two kinds of ciphers, substitution and transposition (there was also a distinction between codes and ciphers). Still, I saw much more variety among cipher designs during that period of my life than after learning the classifications of information age algorithms used by modern cryptographers, like SP-networks and Feistel designs.
After understanding what a Feistel cipher—and all Feistel-like designs—is and what a substitution-permutation network is (before learning this one, I could actually see a little more variety), it seems like all I could up with were designs that fell into either category. Maybe three years ago, I discovered the ARX classification, and I figured that most ciphers that wound up in that those would always be Feistel-like ciphers. Later, I learned of Speck, which has a really unorthodox design (no swapping of the halves after each round). I didn't think of it as a different kind of structure until I saw that the CryptoLUX article on lightweight block ciphers lists it (ARX) as one. It also lists "generalized Feistel network" and "generalized Feistel structure", but I think those can be relabeled as "Feistel-like". And looking back on Speck, it seems like it cannot be classified as either a Feistel-like cipher or an SP-network.
So, my questions are:

Are ARX block ciphers considered there own class of block cipher separate from SPNs and Feistel-like ones?
Are there other schemes out there besides Feistel-like designs, SPNs, and ARX?

Are ARX block ciphers considered there own class of block cipher separate from SPNs and Feistel-like ones?

Generally speaking, yes. ARX ciphers typically only use simple CPU instructions (Addition, Rotation, and Xor) and are typically designed to ensure constant time execution as well as to facilitate efficient SIMD implementations.

The s-boxes and split state that are so prevalent among SPN and Feistel Networks generally aren't present in ARX designs. I'm sure if you wanted you could come up with/find an example of an ARX Feistel network or build an SP network from ARX instructions, but I'm not sure what advantages it would offer.

Are there other schemes out there besides Feistel-like designs, SPNs, and ARX? Or is there really nothing new under the sun?

Typically, the ARX/SPN/Feistel part of the algorithm is used to create a "pseudorandom permutation", and the pseudorandom permutation is then used as part of a cipher construction to provide encryption.

The basic cipher construction is the iterated key or Even-Mansour construction. AES can be modeled like this, as an interleaved application of a key addition layer with the pseudorandom permutation.

A more recent cipher construction that can be built from an arbitrary pseudorandom permutation is the sponge construction. Technically the duplex
construction is a stream cipher, rather then a block cipher. I think that this is actually a key point: The presumption that a block cipher is the best way to encrypt is not necessarily true.

Permutation based

Permutation based constructions are usually more versatile, and often times offer an all-in-one solution (authenticated encryption, hashing, MACs); While you could construct all of the above via a block cipher, it is much more straightforward from an implementation perspective to use a permutation based construction like the sponge construction.

Homomorphic Ciphers

There exist "linear" secret key ciphers, like this one from Fully Homomorphic Encryption Over The Integers. Typically these sorts of ciphers are designed to facilitate homomorphic encryption and/or to instantiate public key cryptosystems. They are often times built from number-theoretic perspectives, and clearly do not resemble any of the other cipher categories (and you would not use them for the same reasons).


Extracting Private Keys in Diffie Hellman I know that the security of Diffie Hellman Key Exchange depends upon the discrete logarithm problem, but is it possible to extract the private keys if we know more? Say that in addition to modulus ($q$), primitive root ($g$) and public keys of Alice and Bob ($g^a$ and $g^b$ respectively), if we knew the calculated key ($g^{ab}$) as well, will it be possible to extract individual keys of Alice and Bob ($a$ and $b$) without using a brute force method? I know it sounds silly and serves no practical purpose at all, but the question was bugging me.

Thanks,

Edit: Added $g$ and other variables for clarity.

This is as hard as computing the discrete logarithm: Assume you have an algorithm $\mathcal{A}$ that given $g^a$, $g^b$ and $g^{ab}$ efficiently computes $a$ and $b$ for uniform $a$ and $b$. You can use this algorithm to compute discrete logarithms as follows: Given $h = g^a$, choose a uniform $b$, compute $g^b$ and $h^b = g^{ab}$. Now give $g^a$, $g^b$ and $g^{ab}$ to $\mathcal{A}$ to obtain $a$, the discrete logarithm of $h$.


Changing password hash and iv on (successful) user login I've implemented a system for my login page (with php) that will update the password hash and initialization vector (for openssl) on each login. So essentially, every time the user successfully logs in, the initialization vector for openssl is re-created in the following way:

1. generate 16 random bytes.
2. Hash the bytes with SHA256.
3. Store the hash in the database.

For encrypting the passwords:

1. Grab the newly created IV.
2. Cut the IV to a 16-byte-long string using a secret algorithm.
3. Use the shortened IV in the openssl_encrypt function,
   along with the secret key and plaintext password.

Overall, the password is stored as a SHA256 hash of the openssl output, and the IV is stored as a SHA256 hash.

How strong is this method? Does updating the database user credentials increase or decrease the chances of a decryption in any event?

the initialization vector for openssl is re-created
  1. generate 16 random bytes.
  2. Hash the bytes with SHA256.
  3. Store the hash in the database

if you generate 16 random bytes (128b), there is no reason to hash it

  password is stored as a SHA256 hash of the openssl output.
  How strong is this method?

you're encrypting the password what has a principial weakness - it is reversible. Once someone get access to your system (therefore all the code and configuration including your secret key), all user passwords are to be revealed. The user passwords should be stored as salted hash, so they are unrecoverable.

Seems you are effectively storing a salted hash of the password, that is good. However the sha256 is relatively fast function, you better to use PBKDF2 (slow hash) to mitigate dictionary or brute-force attack. There is a nice article how to do it properly

  Does updating the database user credentials increase or decrease the chances of a decryption in any event?

The problem is once someone get access to the database and  and all the configuration, the adversary will have all information needed to decrypt all the passwords.

Next - if the passwords won't change themselves, I see no reason for re-hashing the passwords, it just increases complexity of your application.


Is there a way to systematically calculate the public exponent $e$ in RSA? I'm learning RSA in one of my classes and we were given a problem:

  $p = 5$, $q = 11$

I have done the following steps:

  $n = 5 \cdot 11 = 55$
  $\phi = (5-1)\cdot(11-1) = 40$

I know that to find $e$ we have to find an integer co-prime with $\phi$, where $\phi$ is $40$ and $\gcd(e,40) = 1$.

Is there an algorithm I can use by hand that can give me $e$? I know there can be numerous values. The method the professor has shown is to just enumerate each prime and find the first divisible into the totient $\phi$. I assume he will give us small numbers in the exam but still, doing it by trial and error can be time consuming.

I understand one can use extended Euclids algorithm to find the inverse of $e$, which I can do provided I know what $e$ is.

I just struggle with finding $e$.

The question asks how to systematically pick the public exponent $e$ in RSA. I'll stick to public modulus $N$ that is the product of exactly two distinct odd primes $p$ and $q$, but the choice of $e$ is not fundamentally different in multiprime RSA.

What's an acceptable public exponent $e$?

The public exponent in RSA should be an integer $e>1$ with $\gcd(e,p-1)=\gcd(e,q-1)=1$, so that $e$ will have an inverse both $\pmod{p-1}$ and $\pmod{q-1}$; or, equivalently, such that $e$ will have an inverse $\pmod{\phi(p\cdot q)}$. This insures that $e$ is odd, for we have assumed that $p$ and $q$ are.

Also, $e$ must not reveal so much information (about $p$ or $q$, or $\phi(p\cdot q)$) that it significantly simplifies factorization of $N$. This rules out some non-iterative constructive methods like $e=\max(p,q)$, or $e=(p-1)(q-1)+1$, or $e=(p-1)(q-1)-1$ (which do insure that $\gcd(e,p-1)=\gcd(e,q-1)=1$, assuming $\min(p,q)>3$ for the last formula).

Some RSA definitions, most notably PKCS#1, require $e<N$. There is no stated rationale for that requirement.

An old, straightforward (but non standard) method to chose $e$

If we ignore the requirement that $e<N$, one straightforward method is to set $e=N$, which satisfies all other requirements provided that $\min(p,q)$ does not divide $\max(p,q)-1$ (which does not hold in the example in the question, but is extremely likely for large random primes $p$ and $q$; and is certain if $2\min(p,q)>\max(p,q)$, or if $p$ and $q$ have exactly the same bit size, or if $2^{k-1/2}<p<2^k$ and $2^{k-1/2}<q<2^k$ for some integer $k$; all of which are common requirements for $p$ and $q$, listed by increasing selectivity).

This choice of $N$ as the public exponent historically is the first method that was considered, before RSA got named (C. Cocks, A Note on "non-secret encryption", classified GCHQ note dated 20 November 1973, re-typeset here). It is demonstrably as safe as can be with respect to attacks factoring $N$ (or equivalent to that), since we do not reveal anything beyond $N$, which we make public anyway; however, as noted by Chris Peikert, the RSA problem (of finding $x$ knowing $x^e\bmod N$) might be easier for this choice of $e$ (we have no indication of that).

A PKCS#1-conformant (if not standard) method to chose $e$ from $N$

An idea is to select $e$ as a prime with $N/3\le e<N$; such $e$ is acceptable, since it is a prime at least $\max(p,q)$, thus co-prime to $p-1$ and $q-1$. We can pick the smallest prime at least $N/3$, or the highest prime less than $N$. For small $N$ we can restrict to $e$ in a table of pre-computed primes: $7$, $17$, $41$, $97$, $257$, $769$, $1153$, $2113$, $4129$, $12289$, $18433$, $40961$, $65537$, $163841$, $270337$, $786433$.. (I have picked values with at most 3 bits set in their binary representation, which slightly simplifies raising to the $e$th power). Since these choices of $e$ do not depend on the factorization of $N$, they can't help factorize $N$ (but we have no idea if that's a bad or good choice w.r.t. the RSA problem).

The above methods are uncommon, for reasons explained below. To my knowledge, standard and safe methods to chose $e$ somewhat use trial an error in the choice of $e$ from $p$ and $q$, or the choice of $p$ and $q$ from $e$; and most such methods have additional objectives.

Should $e$ have other characteristics?

There is incentive not to chose $e$ too large, for a large $e$ slows down the public-key operation (about proportionally to the bit size of $e$) with no tangible benefit provided proper padding is used. That's one good reason not to use any of the above methods. FIPS 186-4, appendix B.3.1 puts the limit at $e<2^{256}$. In fact, $e\ge2^{32}$ has become uncommon, for it has caused interoperability hurdles with some RSA implementations (formerly including that bundled in Windows); and unduly long waits for users of Smart Cards.

Some standards/security authorities set a lower bound on $e$, typically $e>2^{16}$. That's of debated rationality when using a proper padding scheme.

It is common to choose $e$ prime, because this decreases the amount of trial and error, for odds that a prime $e$ and much larger prime $p$ meet $\gcd(e,p-1)=1$ are $(e-2)/(e-1)$ (thus quickly converging to $1$ when $e$ grows) if either $e$ or $p$ is random; while odds are lower if we remove the condition that $e$ is prime (the odds become mostly independent of the magnitude of $e$; as a hint to that, odds that two large integers each uniformly chosen below some limit $m$ are coprime converges to $6/\pi^2\approx60.8\%$ when $m$ grows). As an aside, if $e$ is composite, revealing it as part of the public key arguably reveals even so slightly more information about $p$ and $q$ (or about $\phi(N)$ or $\lambda(N)$) than if $e$ was a large prime, for there are less possible $p$ and $q$ knowing $e$.

There is also incentive to choose $e$ of the form $2^i+1$, because that's allowing the fastest computation of $x^e\bmod N$ for a given size of $e$ (only $i$ modular squaring and one modular multiplication are required). If we combine with $e$ prime, that leaves the Fermat primes $F_j=2^{(2^j)}+1$ with $0\le j\le4$ as the only candidates (it is conjectured that there exists no other Fermat prime, and known that there are none of manipulable size).

Choice of $p$ and $q$ before search of $e$ by trial and error

RSA key generation as in a textbook typically choose $p$ and $q$ first. An unobjectionable method to then chose $e$ is to try values of $e$ that are moderate random primes in some suitably large interval, until one $e$ is found such that $e$ does not divide $p-1$ or $q-1$. Such $e$ is acceptable w.r.t. both $p$ and $q$ (assumed much larger, random and independent primes) with odds $(e-2)^2/(e-1)^2$, thus high for all but very small $e$. If we specify a large enough interval for $e$ (e.g. $2^{16}<e<2^{17}$) and the choice of $p$ and $q$ is without relations to the primes in that interval, it is not even necessary to insure that the $e$ tested are distinct to find a suitable $e$ quickly, with overwhelming odds.

Some (including the teacher in the question) select $e$ as the lowest prime at least some fixed minimum (chosen no less than $3$) dividing neither $p-1$ nor $q-1$ (or not dividing $\phi(N)$). Notice that doing so often reveals some information about $\phi(N)$: if in a large collection of public keys known to have been generated by the same device we see keys where $1/4$ of the $e$ are $3$ (thus $25\%$ of $e$), $9/16$ of the other $e$ are $5$ (thus about $42.2\%$ of $e$), $25/36$ of the other $e$ are $7$ (thus about $22.8\%$ of $e$), and generally $(r-2)^2/(r-1)^2$ of the other $e$ are $r$ for $r$ the successive primes starting from $11$, we have reverse-engineered the choice of $e$, and know that for the few public keys of the form $(N,23)$, $\phi(N)$ and $\lambda(N)$ are a multiple of $3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19$, which can be used to speed-up a straight brute-force search of these quantities (it is likely that there is at least one such public key if we gathered $27600$ of these). It might give a feeling of discomfort, although we do not know that such knowledge can significantly improve one's ability to find $\phi(N)$ or $\lambda(N)$ knowing the public key, or otherwise derive a working private key, or factor $N$ (rationale: these goals are equivalent, factorization of $N$ is by far the most efficient avenue known to reach any of these goals, and we do not know how to use a known moderate divisor of $\phi(N)$ or $\lambda(N)$ to speed up that factorization).

We can also choose $e$ as an (odd) random integer (not necessarily prime) in some similar interval until $\gcd(e,p-1)=\gcd(e,q-1)=1$. It will require significantly more trials, but success is also virtually insured; and by the same reasoning as above, whatever little extra information we leak is not a worrying security issue.

Hand computation of small $e$ for moderate $p$ and $q$ expressed in decimal

We can easily test divisibility by the primes $5$, $3$, $11$, $37$, $101$. We'll pick the first $e$ in this list that is suitable. Odds that none is suitable are only $0.0068\%$.

If neither of $p$ and $q$ has a $1$ or $6$ as its rightmost decimal digit, then neither $p-1$ nor $q-1$ is divisible by $5$, and we select $e=5$. That won't do for the example in the question (because $q=11$ ends in $1$), but is enough for $p=14627$, $q=15959$ (because neither $7$ nor $9$ are $1$ or $6$).

Otherwise, we sum the digits in $p$; subtract $1$; recursively sum the digits in the result, until the result is single-digit; if that digit is not divisible by $3$, $p-1$ is not, and we do the same test for $q$; if we find that $q-1$ is not divisible by $3$, we select $e=3$. That's the case for $p=5$, $q=11$ in the question (because neither $4$, nor $1$, are divisible by $3$).

Otherwise, we use similar techniques for $e=11$, $37$, and $101$; the divisibility rules are explained here.

Choice of $e$ before search for $p$ and $q$ by trial and error

Real-world RSA implementations tend to choose $e$ first, typically because

very commonly, $e=2^{16}+1=65537$ is required, because that's the minimum value recognized as acceptable by all security authorities, thus unobjectionable and well-supported;
sometime $e=3$ is required, because that gives the best speed of the public-key RSA operation, with no known drawback if proper padding methods are used;
having a fixed $e$ simplifies the transmission of the public key; in that case, one of the Fermat primes $F_j=2^{(2^j)}+1$ is typical.

With $e$ prime, we can pick a prime $p$ such that $p-1$ is not a multiple of $e$, and it insures $\gcd(e,p-1)=1$. The contrary has odds only $1/(e-1)$ for random prime $p$, and that's rare enough to be mildly hard to test for the very popular $e=2^{16}+1$.

An unobjectionable method reducing guesswork (especially for the smaller $e$ like $3$) is to chose $e$ prime, then when it comes to the choice of $p$ chose a secret $f$ uniformly random with $0<f<e-1$, then only explore candidate primes of the form $p=(2k+(f\bmod 2))\cdot e+f+1$, which insure $p$ is odd and $\gcd(e,p-1)=1$. $f$ should be randomly drawn again when it comes to the choice of $q$.


Does a bigger key mean more security - if we do not change the structure of the algorithm? Let's say I have 128-bit cipher in which each round needs to get 768 key bits. Let's consider 10 rounds.
It can be easily 128-bit key cipher. I can do key schedule and produce 7680 bits of keys (let's say with HKDF). But I can also use for example 512-bit key. Then I still need key schedule, but the main key is stronger. And cipher still works on the same 128-bit blocks with the same speed (because it is using still 768 key bits in every round).
Will only by increasing the size of the main key from which I create the round keys I make the algorithm more secure? It is harder to broke main key in this case, but rounds remains the same weak (attacker still have to broke just 768-bit in every round). So maybe we should say that it make stronger key schedule only, not actual cipher? Is it make sense to increase the main key size in that case?

Generally speaking, more than 128 bit security is not required - except maybe for protection against multi-target attacks where large amounts of ciphertext become available to the adversary. The reason for this is that no system will be able to perform $2^{128}$ operations. So if there is an analysis that threatens the structure or number of rounds used, then increasing the rounds or updating the algorithm will likely strengthen the security of the cipher more than increasing the key size.
Quantum computers are not really an exception to this but because of how they work, they often have a different value for the security in the first place. So for a block cipher you can generally assume that Grover's algorithm reduces the security for quantum computers to 64 bits. For this you'd need a full fledged quantum computer with enough qubits and error correction, not the expensive toys we have now.
Still, that means that upgrading to 256 bit security may be a good idea, so that 128 bits of security is restored when considering quantum computing / multi-target attacks. Going higher doesn't make much sense. If it is smart to increase the number of rounds depends on the algorithm. Maybe a conservative number of rounds was already used. On the other hand, the extension of the key schedule may require that more rounds are used. A good example is of course AES, where 10, 12 or 14 rounds are used depending on the key size.
This might not be necessary if the internal state and / or number of rounds is large enough already. But please be aware that HKDF is not an efficient way of expanding keys. You don't want a very heavy key scheduler because of the amount of instructions (which in turn mean gates when using an hardware implementation) required to execute it. And HKDF would also be considered way too compute intensive during initialization. This may be fine in your situation, but it doesn't work for a generic cipher.


What do numbers in a crypto algorithm stand for? Is there a convention? What do the numbers stand for in the names of cryptographic functions, for example AES-256, RSA-1024 or SHA-256?

Do they always refer to key sizes, or is it a different measure for every algorithm?

Is there some convention about this?

In AES-256 and RSA-1024, the numbers refer to the key size. For SHA-256, it refers to the output size. Though there is no hard, fast rule. For example, in the SHA-3 family, there are hash functions with variable length output, SHAKE128 and SHAKE256. The numbers there refer to the security level.

Then again you have secp256k1, the elliptic curve used, among other places, in BitCoin. It's name stands for:

  sec comes from the standard, p means that the curve coordinates are a prime field, 256 means the prime is 256 bits long, k means it is a variant on a so-called Koblitz curve, and 1 means it is the first (and only) curve of that type in the standard.

Then you have hash functions like MD5, which is the 5th version of function designed by Ron Rivest. It's output size is 128 bits. There is also the stream cipher RC4, again by Ron Rivest. There is also an RC2, RC5, and RC6, but I'm not sure where RC1 and RC3 are. :)

From the comments:

  Don't forget SHA-512/224, which is SHA-2 with an internal state of 512 bits and 224 output size, while SHA-224 is SHA-2 with an internal state of 256 bits and an output size of 224 :)


Disadvantages of AES-CTR? On paper, it sounds *very* good to me:

secure
fast (in my tests it's somewhat slower than ECB (but without most of the weaknesses, more on that below) but faster than every other alternative I tested, which were ECB, CTR, CBC, OFB, CFB written in order of performance (link to benchmark code) )
simple to understand
does not require padding (which I guess significantly reduces the chance of implementing padding in an insecure manner)
support parallelization (for both encryption and decryption)
support random access

.. the only disadvantage I can think of, is that because it does not require padding, implementations in practice will probably reveal the exact message length, as compared to revealing circa-message-lengths (e.g. padded schemes may reveal something like the message is within 15 bytes of this length, while non-padded schemes may reveal the message is *exactly* this long), and if that's a concern, it's not like it can't be mitigated by just adding padding anyway.
I guess I'm missing something, so...
What are the disadvantages?

Disadvantages:

Message length: In Cryptography, usually, the message length is not considered secret. There are approaches that you can add random values to the end or beginning or both if this is really an information leak for you. The random approach depends on your actual data case. It is also possible that a pre-determined fixed size can be used as the e-mail can be limited to 512 characters. In the end, at least the upper bound is revealed in all of the cases.

The (IV, key) pair reuse is a real problem that can eliminate the confidentiality with the crib-dragging technique. This doesn't reveal the encryption key.

Lack of authentication Like all unauthenticated encryption modes, the bare CTR mode lacks integrity and authentication. A single bit of flipping can have catastrophic results due to the malleability of the CTR mode.
The AES-GCM mode that uses the CTR mode of operation provides you all-in-once, however, it has the same  (IV, key) pair reuse problem. There is a Synthetic Initialization Vector (SIV) mode as nonce-misuse resistance ( paper, rfc8452 ) that eliminates this. SIV mode can still leak that the same message is sent under the same key, so an observer can distinguish this.

Long message distinguisher:  The CTR mode is designed with a Pseudo-Random-Function (PRF). When using AES in CTR mode, we use it with Pseudo Random Permutation (PRP); $$E_k\colon \{0,1\}^n \to \{0,1\}^n.$$ Whit PRP as long as the message blocks are not repeated the sequence $E_k(0), E_k(1), \dots, E_k(\ell - 1)$ with $\ell < 2^n$ is not repeated. If the message with length $\ell$-block has no repeated block this is no problem. If we approach the message as uniform random block then we expect a collision $\ell \approx \sqrt{2^n} = 2^{n/2}$ by the birthday paradox/attack.
When used with AES-128 for long messages check for the repeat. The repeat enables the attacker to distinguish this from uniform random with non-negligible probability.
In short, a duplicate ciphertext in any position leaks that the messages are different.

Message size per key: although NIST say 64 nonce and 64 bit counter, one should stop using a key well before $2^{64}$ block. This is due to using a PRP (AES) instead of PRF in CTR mode.

Other advantages:

No need for the decryption: CTR mode doesn't require decryption of the block cipher, it always uses them for encryption. This is very helpful in constraint environments. Simplifies the software and hardware code, too.

No need PRP: Doesn't need a block cipher (PRP) at all. A hash function can be used like in the ChaCha series.

Prepocessing: the keystream generated by the CTR mode can be prepared before. This can help to use buffers.

CTR mode has CPA security.

A little history of CTR
CTR mode was introduced by Whitfield Diffie and Martin Hellman in 1979

Privacy and Authentication: An Introduction to Cryptography as an invited paper on Proceedings of the IEEE, 67 (1979), pp. 397–427.

A concrete Security of Treatment of Symmetric Encryption, Bellare et. al, 97 provides the security bounds.

See also; Comments to NIST concerning AES Modes of Operations: CTR-Mode Encryption, by Lipmaa et al. for other details of advantages and disadvantages.


Is there a way to change encryption scheme from AES to FHE without data leakage? So let's say that we have encrypted some data using symmetric encryption in this case AES. And we want to change it to homomorphic encryption but without decrypting the data and encrypting it again using FHE. Do you know if this is possible in any way?

If you are talking about FHE (as stated in the title, but not in the question body) then yes, this is possible.
Encrypt the symmetric key $k$ that was used to originally encrypt the data as well as the symmetric ciphertext $c$ under the FHE public key. Then homomorphically evaluate the decryption circuit of the symmetric encryption scheme on those ciphertexts. By the correctness of the FHE scheme the result will be a ciphertext encrypting the original data under the FHE public key.


Cryptographical formalization of computational privacy Yesteryears problems of communication privacy has been well defined in cryptography through Asymmetric cryptography.

Due to rise in Cloud computational model , computational heavy tasks are being outsourced to a remote server for economic reasons, and  there is need for computational privacy .

Is there any crypto formalization for computational privacy ( other than homomorphic encryption ) ?

It depends on how strict you are. In the traditional cloud computing sense, where one party "sends their data to the cloud" for all the computations to be performed, no. There aren't any other methods other than homomorphic encryption.

The most common techniques for computation on encrypted data besides homomorphic encryption are garbled circuits and secret sharing based schemes. The problem with them is that they are much more interactive than the traditional cloud computation model, where the data is encrypted and sent off.

Recent research, however, has been looking at cloud-assisted multi-party computation. In this paradigm, the cloud is a party of the MPC, but without any input. See Outsourcing Multi-Party Computation and Cloud-Assisted Multiparty Computation from Fully Homomorphic Encryption. I'm not completely aware of all the details (had forgotten about these works until working on this answer), but maybe these are headed in the direction you were thinking of.


What does AES256-CTS-HMAC-SHA1-96 mean in relation to Kerberos? I'm not completely clueless as to what it means, but I'd like to understand it at a higher level.

The highest encryption type used by Active Directory domain controllers for Kerberos authentication traffic is AES256-CTS-HMAC-SHA1-96.

The first part: AES256-CTS. That's AES with a 256-bit symmetric key operating in Cipher Text Stealing mode. Where does the 256 bits of key material come from?

The last part: HMAC-SHA1-96.  I get that it's using a hash-bashed message authentication code, using SHA1 for the hash. But what does the 96 mean? An SHA1 hash is 160 bits...

Decoding AES256-CTS-HMAC-SHA1-96

AES256 = AES using 256-bit key
CTS = ciphertext stealing
HMAC-SHA1-96 = HMAC using SHA-1 hash function with mac truncated to 96 bits.

The benefits of HMAC truncation are discussed in FIPS PUB 198-1, chapter 5.
For HMAC-SHA1 96 bits is very common truncation, used for instance by IPsec/ESP.

For figuring out what key material is used, it is decided by Kerberos. Please, read the appropriate standards.


Dieharder input file with a sequence of only binary numbers I have a RNG producing sequences of binary numbers, ad I would like to run Dieharder test using them as an ascii txt input file. However I haven't been able to do it properly. Should I use a header like:

type: b

count: 2500000

numbit: 1

1

0

0
...

Thanks.

You can generate an example of the ascii input by running:

dieharder -o -f example.input -t 10

It will basically be something like:

#==================================================================
# generator mt19937  seed = 3865342443
#==================================================================
type: d
count: 10
numbit: 32

However note, that dieharder will expect that each line of ascii file is either integers in the range 0  to  2^31-1 or decimal with at least ten significant digits (details are here). So maybe in your case, it's easier to produce raw binary files.

Btw, you'll need about 20GB or even more (for raw file) for proper testing. Otherwise, it's hard to say if test failed due to PRNG or too many rewounds (last tests require lots of data and even with 20GB in the standard mode, dieharder will rewound file multiple times).