Examples of multi output bit balanced Boolean functions I am trying to find out and learn more about Balanced boolean functions.
Wikipedia states that " a balanced boolean function is a boolean function whose output yields as many 0s as 1s over its input set", and states that an example of this is XOR.
I want to know how the same works for multi-output bit functions, where the output is a concatenation of two boolean functions essentially. Truth tables with examples for single and multi output to understand what this exactly means would be good to analyze it more.

As in the other answer a vectorial boolean function with $m$ coordinates $f : \{0,1\}^n\to\{0,1\}^m$ are viewed as $m$ boolean functions $f_i : \{0,1\}^n\to\{0,1\}$.
However, it is not enough to consider $f$ to be balanced when the $f_i$ are all balanced.
For example consider $m=2,$ and $f_i(x_1,x_2,x_3)=x_1\oplus x_2,$ for $i=1,2.$
The truth table for $f_i$ is $[01100110]$ in the natural order. However, the function $f(x_1,x_2)=(f_1,f_2)$ does not have a property that we would call balanced since its truth table would be $[00,11,11,00,00,11,11,00].$
A natural requirement for a balanced vectorial boolean function with $m$ output coordinates is that all $2^m$ output $m-$tuples occur equally often in its truth table.
One way to ensure this holds is to stipulate that for all nonzero vectors $(a_1,\ldots,a_m)$ in $\{0,1\}^m,$ the boolean function $\langle a,f \rangle=a_1 f_1\oplus a_2 f_2 \oplus a_m f_m$ is itself balanced.
So if we had $f_1=x_1,f_2=x_1\oplus x_2,$ in the above example our function would be balanced with truth table $[00,11,01,10,00,11,01,10]$.
Usually we require other properties in addition to being balanced, such as high algebraic immunity, correlation immunity [=resilience if balanced], high nonlinearity, etc.
There is a good survey by Claude Carlet easily discovered online entitled "vectorial boolean functions". Early papers by Nyberg gave examples of nice balanced vectorial functions. Clearly if $m=n,$ and the function is balanced, you a nice $m\times m$ S-box, since each output pattern occurs exactly once and we have a permutation.


What is the importance of 1 < d < φ(n) and 0 ≤ m < n in RSA? I'm a first year Maths undergraduate and we have recently gone onto RSA. I understand the majority of the algorithm using Fermat's Theorem etc.

From the algorithm stated on Wikipedia:

  4) Choose an integer $d$ such that $1 \lt d \lt φ(n)$ and $\gcd(d, φ(n)) = 1$; i.e., $d$ and $φ(n)$ are coprime.

  5) Determine $e$ as $e ≡ d^{−1} \mod {φ(n)}$; i.e., $e$ is the modular multiplicative inverse of $d \mod {φ(n)}$.

I don't understand the importance of $1 < d < φ(n)$.

Also why must the message $M$ to be encrypted be an integer $m$ such that $0 ≤ m < n$ (here $n$ is the product of two distinct primes $p$ and $q$)?

From the algorithm stated on Wikipedia:
"4) Choose an integer d such that 1 < d < φ(n) and gcd(d, φ(n)) = 1; i.e., d and φ(n) are coprime. 5) Determine e as e ≡ d−1 (mod φ(n)); i.e., e is the modular multiplicative inverse of d (modulo φ(n))"
I don't understand the importance of 1 < d < φ(n).

You can use a d greater than φ(n), but it needs more computation time than a d less than φ(n).
Also, d and e in 4) and 5) should be swapped. You may see 8.2.1 Handbook of Applied Cryptography

Also why must the message M to be encrypted be an integer m such that 0 ≤ m < n
(Here n is the product of two distinct primes p and q)

If m is less than 0 or not less than n, you can not recover m; since decryption gives you a number(m') 0 ≤ m' < n.


Diffie-Hellman key agreement with both Server Authentication and Perfect Forward Secrecy I am trying to find the protocol with the least overhead, which still meets the following requirements:

Server Authentication of server identity to client. The client has an authentic copy of the server long term public key.
Perfect Forward Secrecy.
Confidentiality, integrity, authenticity of payload, including:

Replay protection.
As little clear text Handshake and Header data as possible, to aid application specific implementations of traffic analysis counter measures.

The protocol operates over TCP (or equivalent, or higher). Serialization of messages is assumed. In particular, both sides are presumed to maintain a state that, at all times, unequivocally determines which content encryption key to use for decrypting any packet that arrives from the other side.
No Client Authentication of client identity to server. This is presumed to be done by the protected application layer, if necessary.
The Client and Server share fixed, implementation specific security parameters, including Diffie-Hellman domain parameters, KDF and AE algorithm choices etc. However, these parameters might differ between different implementations.

I have seen the CurveCP protocol, which appears to have slightly different design criteria.

This is what I came up with:

$Label_i$ denotes a fixed, implementation specific octet string. Different labels will be used for key derivation at different steps in the protocol.

All protocol messages have a header that consist only of a protocol version field and a length field. Both are included as authenticated data in the MAC calculation if the message is encrypted.

The long term key pair of the server is denoted $S^0$.

$Client$: Generate ephemeral key pair $C^1_{publ}, C^1_{priv}$
$Client \rightarrow Server$: $Hello_C^1 \leftarrow C^1_{publ}$
$Server$: Verify that $C^1_{publ}$ is not congruent to 0, 1 or -1, and that it belongs to the right subgroup.
Both $Client$ and $Server$: Calculate the intermediate shared secret $M^1_{tmp}$ from $S^0$ and $C^1$. Calculate $k_{tmp} \leftarrow KDF(M^1_{tmp},Label_0)$
$Server$: Generate ephemeral key pair $S^1_{publ}, S^1_{priv}$.
$Server \rightarrow Client$: $Hello_S^1 \leftarrow AE_{k_{tmp}}(S^1_{publ})$
$Client$: Verify and decrypt $Hello_S^1$. Verify that $S^1_{publ}$ is not congruent to 0, 1 or -1, and that it belongs to the right subgroup.
Both $Client$ and $Server$: Calculate the shared secret $M^1$ from $S^1$ and $C^1$.
Both $Client$ and $Server$: Calculate $k^1_S \leftarrow KDF(M^1,Label_1)$ and $k^1_C \leftarrow KDF(M^1,Label_2)$
Both $Client$ and $Server$: Set $Ctr_S \leftarrow 0$ and $Ctr_C \leftarrow 0$
... $Client \rightarrow Server$: $Packet_{Ctr_C} \leftarrow AE_{k^1_C}(Ctr_C||"m"||Message)$
... $Server \rightarrow Client$: $Packet_{Ctr_S} \leftarrow AE_{k^1_S}(Ctr_S||"m"||Message)$

... later rekey before the counters wrap around to zero, as follows:

$Client$: Generate ephemeral key pair $C^i_{publ}, C^i_{priv}$
$Client \rightarrow Server$: $Hello_C^i \leftarrow AE_{k^{i-1}_C}(Ctr_C||"hello"||C^i_{publ})$
$Server$: Verify and decrypt $Hello_C^i$. Verify that $C^i_{publ}$ is not congruent to 0, 1 or -1, and that it belongs to the right subgroup.
Both $Client$ and $Server$: Calculate the intermediate shared secret $M^i_{tmp}$ from $S^{i-1}$ and $C^i$. Calculate $k_{tmp} \leftarrow KDF(M^i_{tmp},Label_0)$
$Server$: Generate ephemeral key pair $S^i_{publ}, S^i_{priv}$.
$Server \rightarrow Client$: $Hello_S^i \leftarrow AE_{k_{tmp}}(S^i_{publ})$
$Client$: Verify and decrypt $Hello_S^i$. Verify that $C^i_{publ}$ is not congruent to 0, 1 or -1, and that it belongs to the right subgroup.
Both $Client$ and $Server$: Calculate the shared secret $M^i$ from $S^i$ and $C^i$.
Both $Client$ and $Server$: Calculate $k^i_S \leftarrow KDF(M^i,Label_1)$ and $k^i_C \leftarrow KDF(M^i,Label_2)$
Both $Client$ and $Server$: Set $Ctr_S \leftarrow 0$ and $Ctr_C \leftarrow 0$

...etc.

Does this protocol meet the requirements, or is something missing?

$Adversary\:$ receives $C^1_{publ}$

$Adversary\:$ adaptively queries an oracle that implements:

take $C^2$ as input, generate $S^1_{publ}$, set $\: k_{adv} = KDF\left(\left(C_2\right)^{S^0_{priv}},label_0\right) \:$, $\:$ output $\: AE_{k_{adv}}\left(S^1_{publ}\right)$

Note that $\:Adversary\:$ can (with, heuristically, overwhelming accuracy) test whether or not a given

value was used as $k_{adv}$ on a given query to that oracle (since the encryption is authenticated).

$Adversary\:$ guesses $k_{tmp}$ and then runs the rest of the protocol with $\:Client\:$.

If the guess was correct, then $\:Client\:$ will accept with $k_S$ and $k_C$ known to $\:Adversary\:$.

(There is slightly more that the adversary can do, which I'll

explain if you don't think the above justifies my next sentence)

It seems that it would be very difficult to prove security against the above sort of attack

without proving that even if the oracle instead outputs [if $\: C^2 = C^1_{publ} \:$ then $\perp$ else $k_{adv}$],

it would still be infeasible to distinguish $k_{tmp}$ from a randomly chosen key.

That is the analogue of CCA2 security for Diffie-Hellman+your-KDF.

You could reduce the main security assumption to KDF-Diffie-Hellman by having

$Server$'s$\:$ long
term key pair be for signatures, replacing the step 6 message with

$S^1_{publ}\;||\;\text{sign}_{S^0_{priv}}\left(C^1_{publ}\:||\:S^1_{publ}\right)\;$, $\;\;$ and then removing step 4 and the "decrypt" part of step 7.

Both of these methods use two messages, and I will assume they are done using Elliptic Curves

and that the $AE$ in step 6 of yours does not include an IV (since the plaintext has high min-entropy,

and that particular plaintext doesn't actually need to be confidential). $\;\;$ In both of these protocols,

the length of the first message is $\:2\hspace{-0.03 in}\cdot\hspace{-0.03 in}k\:$,$\:$ where $k$ is the (confidentiality) security parameter.

In your protocol, the length of the second message if $\:(2\hspace{-0.03 in}\cdot\hspace{-0.03 in}k)+\sigma\:$,$\:$ where $\:Adversary$

has a trivial attack that will violate explicit authentication with probability $1/(2^{\sigma})$

and cause $\:Client\:$ to reject otherwise. $\;\;$ In my protocol, the length of the second

message is $\:(2\hspace{-0.03 in}\cdot\hspace{-0.03 in}k)+(4\hspace{-0.035 in}\cdot\hspace{-0.03 in}k_{\hspace{.01 in}0})\:$,$\;$ where $\hspace{.02 in}k_{\hspace{.01 in}0}\hspace{.01 in}$ is the authentication security parameter.


Difference Between PEM vs P12 vs CRT vs JKS vs keystore vs PKCS vs x509 certificates Sorry noob here. I am so much confused about lot of files used client authentication certificates. Can anyone guide me on the difference between PEM vs P12 vs CRT vs JKS vs Keystore vs PKCS vs x509 certificates?

I got some information from Wikipedia,
In cryptography, X.509 is a standard defining the format of public key certificates.

**Certificate filename extensions**

There are several commonly used filename extensions for X.509 certificates. Unfortunately, some of these extensions are also used for other data such as private keys.

.pem – (Privacy-enhanced Electronic Mail) Base64 encoded DER certificate, enclosed between "-----BEGIN CERTIFICATE-----" and "-----END CERTIFICATE-----"
.cer, .crt, .der – usually in binary DER form, but Base64-encoded certificates are common too (see .pem above)
.p7b, .p7c – PKCS#7 SignedData structure without data, just certificate(s) or CRL(s)
.p12 – PKCS#12, may contain certificate(s) (public) and private keys (password protected)
.pfx – PFX, predecessor of PKCS#12 (usually contains data in PKCS#12 format, e.g., with PFX files generated in IIS)
PKCS#7 is a standard for signing or encrypting (officially called "enveloping") data. Since the certificate is needed to verify signed data, it is possible to include them in the SignedData structure. A .P7C file is a degenerated SignedData structure, without any data to sign.[citation needed]

PKCS#12 evolved from the personal information exchange (PFX) standard and is used to exchange public and private objects in a single file.[citation needed]

https://en.wikipedia.org/wiki/X.509


How do I calculate CRC32 mathematically? I want to calcuate the CRC32 algorithm using polynomials directly but I don't know how. I found the generating polynomial listed here https://en.wikipedia.org/wiki/Cyclic_redundancy_check. This corresponds to 0xedb88320 in the example code.

Can someone please define a mathematical specification that calculates the same result as this algorithm?

The most common CRC32 is borrowed from the 32-bit Frame Check Sequence in the 1988 edition of CCITT V.42, section 8.1.1.6.2, available here, which gives a mathematical definition (note: remove the obviously spurious $1$ after $x^{30}$ in the English edition).

I prefer this alternate definition with some of the math on polynomial replaced by equivalent operations on bits:

Consider the message as a sequence of $n$ bits in chronological order (if the message is structured in words or bytes: with low-order bit first unless otherwise specified).
Append $32$ one bits, forming a sequence of $n+32$ bits.
Complement the first $32$ bits of that sequence.
Form the binary polynomial of degree (at most) $n+31$, with term $x^{n+32-j}$ present (resp. absent) when the $j$th bit in the result of the previous step is one (resp. zero), for $j$ with $0<j\le n+32$.
Compute the remainder of the polynomial division of that polynomial by the binary polynomial $x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^8+x^7+x^5+x^4+x^2+x+1$, forming a binary polynomial of degree (at most) $31$.
Form the $32$-bit sequence with the $j$th bit one (resp. zero) when the term $x^{32-j}$ is present (resp. absent) in that polynomial, for $j$ with $0<j\le 32$.
Append that $32$-bit sequence to the ORIGINAL message (if it is to be converted to bytes: the first bit of that sequence shall be the low-order bit of the first byte unless otherwise specified).

Note: Inserting $32$ bits at step 2 allows a receiver to process bits of the message and $32$-bit sequence uniformly as they are being received, without knowing the frontier between the message and the final 32-bit sequence until after the end of that sequence. Step 3 makes it likely that suppression of bits in the message is detected including for zero bits at the beginning of the message.

Note: In term of binary polynomials (according to the conventions in steps 4 and 6), the combination of steps 2 and 3 changes $M(x)$ to $M(x)\cdot x^{32}+\displaystyle\sum_{i=n}^{n+31}{x^i}+\sum_{i=0}^{31}{x^i}$.

Note: Steps 4, 5 and 6 can be replaced by:

repeat until the sequence has exactly 32 bits:

if the first bit is one:

complement the 7th, 10th, 11th, 17th, 21th, 22th, 23th, 25th, 26th, 28th, 29th, 31th, 32th and 33th bit.

remove the first bit.


Possible hashing scheme Plaintext(binary) : 10101100 //very short for easy understanding

Suppose we have 4 predefined schemes/functions,

rotate (101 -> 011)
flip (1101 -> 1011)
exchange (11011 -> 10111)
stretch (1100 -> 11001100)

We create a function that checks for '0' or '1' in each position of plaintext(binary)

function in simple terms, (suppose plaintext in binary 10101100)

Bit at position 1 is 1, so perform rotate() on plaintext.
Bit at position 2 is 0, don't perform flip() operation.
Bit at position 3 is 1, so perform exchange() on output of step 1.
Bit at position 4 is 0, don't perform stretch operation.
Bit at position 5 is 1, so perform rotate() on output of step 3.
Bit at position 6 is 1, so perform flip() on output of step 5.
Bit at position 7 is 0, don't perform exchange().
Bit at position 8 is 0, don't perform stretch().

In this the output would be dependent on the input, hence it may serve as a hash to the plaintext.
These functions are just for example, more complex functions may be used.
I've used just 4 functions however more functions can be used.

I don't know if this is already the logic in existing hashing schemes but had this thought in mind. Will this work as a proper hashing scheme? (I suppose no)

I don't recommend inventing your own hashing algorithm unless if you are knowledgeable and careful. The available hashing functions are good SHA 3 was chosen based on an open competition, you may just use it.

I don't see a point of coming up with a new hash function.


What kind of adversary is the cloud? I just started some work on computation over encrypted data in the cloud. We're still in the early planning stages, and to really understand the kind of security we can offer I need to determine what kind of attacks to expect from an untrusted cloud server. My basic question is whether the cloud represents a semi-honest, covert, or malicious adversary.

My cryptographer's instinct tells me to expect the worst and assume that all untrusted cloud servers are malicious adversaries. However, for many of the commercial cloud services it seems silly to expect them to actively attack their customers. This leads me to think of cloud providers as semi-honest. Am I way off-base here?

It depends upon what trust you have in the cloud.  If you don't trust the cloud provider, a malicious model (treating the cloud as malicious) might make sense.

The so-called "semi-honest" threat model almost never makes sense in practice.  It amounts to assuming that someone is malicious ... but not malicious enough that they'll deliberately, actively try to subvert your security.  That's a very weird kind of assumption to make.  The "semi-honest" threat model is basically a theoretical construct that has no good practical motivation in its own right.  There may be a few special places where the "semi-honest" threat model might make sense in practice.  However, my view is that the "semi-honest" threat model is inappropriate for most practical systems engineering purposes.

Please understand: if you're using (say) Amazon EC2 for your cloud provider services, usually the threat to worry about isn't that Amazon is deliberately out to get you.  Rather, the more realistic threat is that Amazon gets penetrated by some malicious third party and the attacker is then out to get you.  Or, that an Amazon insider (e.g., one of Amazon's sysadmins) tries to get you.  Or, that Amazon has an inadvertent security breach that exposes your data.  For conciseness, we often summarize those by saying "Amazon is untrusted" or "the cloud is untrusted", but that doesn't mean that our primary concern is about Amazon the company itself.

Conversely, just because I'm pretty sure that Amazon the company isn't out to get me doesn't mean that it's safe to treat the cloud as trusted.  I still have to worry about whether there might be an inadvertent vulnerability or breach in Amazon's systems that lets the attacker take control of Amazon EC2 and thereby attack me.  If I'm worried about that sort of thing, I need a protocol that essentially treats the cloud provider as untrusted.


How many codes can I safely generate using the same HMAC key? Can an attacker guess the key given enough codes for the same key? And if so, how many times is it safe to use the same key?

I don't think there is any official limitations when it comes from standardization bodies such as NIST. However, there do seem to be some papers such as New Generic Attacks Against Hash-based MACs.

They show that HMAC may have less security than previously thought after the birthday bound. Generally, if you have a hash output size of, say 256 bits for SHA-256 then you may have to start worrying after $2^{128}$ messages. This is of course not a limit that should worry you.

Even for SHA-1 you're probably going to be fine. However, you may want to stop using (MD5 for which the bound is a worrying $2^{64}$) and SHA-1 by now for other reasons than just the output size; there are too many attacks on those hash functions and attacks only get better.

Just use a modern hash function - SHA-2 or SHA-3 - as base for HMAC and you'll be alright. For SHA-3 you might want to take a look at KMAC as well, although support for that particular MAC is sparse.


garbled circuit vs fully homomorphic encryption Consider an outsourced database to an untrusted cloud (think CryptDb), the question is how to compute a function $f(.)$ on the data.

I think I understand how (fully or partially) homomorphic encryption works in this situation:

Encrypt the input.
Outsource both the ciphertexts and the (public) function.
The cloud evaluates the functions on ciphertexts, results are also in ciphertexts.

How would garbled circuit (GC) be used in this case? Is it:

Garble the circuit and upload to the cloud.
Garble the inputs and upload to the cloud (ciphertexts).
The cloud evaluates the circuit. Results are in plaintext.

What are the trade-offs between these two approaches, supposing I don't care whether the results are in the clear or encrypted? It looks like both can be used to compute arbitrary functions over ciphertexts.

But if GC can be used only once (true?), is it possible to use the same garbled inputs for more than one GC, or one needs to construct a (GC,garbled input) pair for every single evaluation of the function $f(.)$?

Yes, standard GC are not re-usable, thus by means of GC you may outsource the computation of a single function on a single input (i.e. you delegate a function described by a Boolean circuit and later you may ask the evaluation of the function on a single input not fixed in advance).

Indeed this is the approach to Verifiable Computation proposed in a paper of Gennaro, Gentry, Parno (https://eprint.iacr.org/2009/547). Here, “verifiable” means that you also want a proof that the server computed the input on the expected function. How would you extend this idea to multiple inputs? To this scope the authors employ FHE.

But maybe this goes beyond your question since the aim of the authors is to achieve verifiability. As said in a previous post, re-usable GC have been proposed but they are indeed based on FHE.


Generating the keys for the RSA cryptosystem in probabilistic polynomial time In general every public key cryptosystem ``has'' a probabilistic polynomial time algorithm $G$ such that $G(1^k)=(\textrm{public key}, \textrm{private key=trapdoor})$; $G$ is called the key generator. Now for the RSA cryptosystem the keys, can be found in the following way:

  Bob decides the key length $k$, then $G(1^k)=((n,e), d)$ where $n=pq$
  with $p$ and $q$  prime numbers, $n$ has length $k$ (as bit string),  and $e\in\mathbb
 Z^\ast_{\phi(n)}$. The two primes $p$ and $q$  and are chosen in a
  random way, $\phi(n)$ is simply $(p-1)(q-1)$, $e\in\mathbb
Z^\ast_{\phi(n)}$ is randomly chosen and finally $d$ is calculated  in
  polynomial time with the extended Euclid algorithm. The couple $(n,e)$
  is setted as  the public key, whereas $d$ is the secret key.

I don't understand why this algorithm has probabilistic polynomial running time. Who ensures that I can find two random primes and $e$ in a reasonable time?

thanks in advance.

Short version: All the cool kids are using Randomized Algorithm !

Boring version:

Any deterministic (part of a) crypto system can be broken !  [Goldwasser Micali]
Primes density is pretty high (higher than one intuitively expects) as we talk of big numbers. Prime No. Theorem : #of primes between $1$ and $x$, $\pi(x) = \frac{x}{ln(x)}$ , So if randomly picking no.s usually means you have a fairly high chance of getting a prime.. :)
Primality checking with Rabin Miller (probabilistic) is way faster than AKS (deterministic)


Argon2id internal iterations vs multiple Argon2id calls ? TLDR;
Is there a security risk if rather than setting the iteration parameter to 12 (for example), we set it to 3 but call the function 4 times?

I'm asking that for 2 reasons:

Firstly, we use SRP protocol where the deprecated SHA1 is replaced by Argon2id inside our PWA (Progressive Web App, so in JavaScript) but Firefox and Google currently discuss to inform user when an operation take too much CPU or RAM. Their goal is to fight against website that doing bitcoin's mining in the background. I don't want this require user's confirmation each time we use Argon2.

Secondly, as we can't known which CPU/RAM are available for the smartphone in JavaScript, we can't known the ideal number of iterations to ideally doing, so we need to find this with the help of a chronometer, we can call Argon2id as many time as possible until 3 seconds elapsed. Of course, we also keep in memory the number of calls used the first time, to do the exact same number of calls the next time we want to compare.

BTW, the last RFC 8018 of January 2017 still recommend PBKDF2 and this KDF is natively supported in browser (WebCrypto API) and faster than any external library, so may be the solution is to not use Argon2 and to use WebCrypto PBKDF2, with the same method of multiple calls until 3 seconds elapsed?

I'm adding my solution here for the record.

Rather than calling multiple times the Argon2d function when the user sign in, we can do something smarter, with a research of the best settings when the user sign up.

We can inform him we will take few seconds to adjust the security while 5 ~ 10 seconds. So if the browser block the process and warn the user, he's already informed and can let continue the process.

Technically, we trying different settings from the lower values (1MB / 1 iteration) until the delay measured require at least 1 second. Then, we could save the settings to use for this user's device. When the user sign in, we simply use the associated settings, and this will not take more than 1 ~ 2 seconds. So in theory this shouldn't be blocked by the browser, and we increase security in following the device's capabilities.

Some real tests:

Apple iPhone 4S (512MB - 1Ghz): ~1.7s ==> m=1MB,t=1
Apple iPhone 5 (1GB - 1.3Ghz dual-core): ~1.2s ==> m=4MB,t=1
Samsung S8 (4 GB, 2.3GHz / 1.7GHz quad-core each): ~1.4s ==> m=24MB,t=2
NUC i3 (8GB - 1.7Ghz quad-core): ~1.4s ==> m=24MB,t=2

Any feedback are welcome.


Spoofing protocol nonce Amy and Betty have a shared key $k$, and the protocol below is to provide a mutual authentication for both Betty and Amy.

A sends B : $n_a$
B sends A : $n_b \;\|\; E(k, n_a)$
A sends B : $E(k, n_b)$

Where

$n_a$ is a nonce from Amy
$n_b$ is a nonce by Betty

Can spoofing take place here where someone pretends to be Amy even without knowing the shared key?

Yes, there are several ways in which Mallory could pretend to be Amy.

One obvious way, which doesn't even involve Amy herself in any way, would be for Mallory to perform steps 1 and 2 of the protocol normally, as if he were Amy.  Then, given Betty's nonce $n_b$, Mallory can start a second, parallel instance of the protocol, again pretending to be Amy, and submit $n_b$ as Amy's nonce.  The response from Betty then contains $E(k, n_b)$, which Mallory can send back to Betty to complete the original authentication protocol:

M(A) → B: $n_a$ (= arbitrary nonce chosen by Mallory, pretending to be Amy)
B → M(A): $n_b \;\|\; E(k, n_a)$
Second, parallel session:
1'. M(A) → B: $n_b$
2'. B → M(A): $n_b' \;\|\; E(k, n_b)$
M(A) → B: $E(k, n_b)$

Of course, if Amy is also willing to respond to authentication attempts initiated by Betty (or by Mallory pretending to be her), then Mallory can perform the parallel steps 1' and 2' with Amy instead of Betty.  Thus, even if Betty's smart enough to check whether the nonce she receives in step 1' matches her own earlier nonce (or even if she simply refuses to participate in more than one authentication exchange at a time), she will not be able to detect this version of the attack.

As owlstead suggests, the way to defeat this attack is to disambiguate the encrypted values sent in step 2 and 3, so that the value from step 2 cannot be used by Mallory in step 3.  Some possible ways to do this would be to:

Include a step number in the encrypted strings, e.g.:

A → B: $n_a$
B → A: $n_b \;\|\; E(k, 2 \;\|\; n_a)$
A → B: $E(k, 3 \;\|\; n_b)$

Include both nonces in each encrypted strings (in different order), e.g.:

A → B: $n_a$
B → A: $n_b \;\|\; E(k, n_a \;\|\; n_b)$
A → B: $E(k, n_b \;\|\; n_a)$

Include the (assumed) identities of the sending and receiving parties in the encrypted strings (NOTE: does not protect against the modified attack where Mallory contacts Amy instead of Betty for steps 1' and 2'), e.g.:

A → B: $n_a$
B → A: $n_b \;\|\; E(k, id_b \;\|\; id_a \;\|\; n_a)$
A → B: $E(k, id_a \;\|\; id_b \;\|\; n_b)$

All of the above, e.g.:

A → B: $n_a$
B → A: $n_b \;\|\; E(k, 2 \;\|\; id_a \;\|\; n_a \;\|\; id_b \;\|\; n_b)$
A → B: $E(k, 3 \;\|\; id_b \;\|\; n_b \;\|\; id_a \;\|\; n_a)$

Personally, I would recommend the last option, if only because it makes the encrypted strings self-documenting: $E(k, 3 \;\|\; id_b \;\|\; n_b \;\|\; id_a \;\|\; n_a)$ can be read as "Amy ($id_a$) authenticating with nonce $n_a$ to Betty ($id_b$) with nonce $n_b$ in step 3", which is exactly what the message is supposed to communicate.

Also, obviously, the encryption method $E$ needs to be non-malleable, and the combining operation $\|$ should not introduce any ambiguity.  In fact, calling $E$ "encryption" is somewhat misleading here: the protocol works fine even if $E(k,m)$ is just a MAC, but has obvious attacks if $E$ is a malleable (but still semantically secure) encryption scheme like CTR mode encryption, as Mallory can simply take $E(k, n_a)$ and turn it into $E(k, n_b)$ by flipping the appropriate bits.

The protocol as described also has other potential issues, depending on how it's used.  For example, if Mallory can insert himself as a middle-man between Amy and Betty, then he can simply relay any messages he receives from Amy to Betty, and vice versa, thereby trivially convincing both that they're talking directly to each other, even though both are actually talking to Mallory.
Fundamentally, without some extra out-of-band information, there's no way to prevent this attack from within the authentication stage of the protocol: as long as Amy and Betty just receive messages from some unspecified network, there's no way for them to tell whose hands they've passed through.

The only solution is for Amy and Betty to encrypt their subsequent communications using the shared key $k$ (or, better yet, an ephemeral session key derived from $k$ and the nonces $n_a$ and $n_b$, and preferably also the identities $id_a$ and $id_b$) with a secure, non-malleable encryption scheme to ensure that, even if Mallory can intercept their messages, he will not be able to decrypt or alter them.  (Of course, the messages should also carry sequence numbers / timestamps and sender / receiver IDs to prevent replay attacks.)


Padding size with a CBC Block cipher in TLS I'm currently looking at an encrypted Client Finished message in Wireshark from a TLS session. The cipher suite that was agreed on in previous messages was TLS_RSA_WITH_AES_256_CBC_SHA.

By my understanding, the encrypted message should have a Handshake Protocol header which is made up of the handshake type and the length. This should be 4 bytes in total. There should then be 12 bytes of verify_data, followed by a 20 byte MAC (SHA-1 digest size). This takes us to 36 bytes. Now according to RFC 2246 section 6.2.3.2, it should then be padded out so that the length in total is a multiple of the block length (in this case 16 for AES-256).

That means it should have 12 bytes of padding, where each padding value has a value of 12 (0x0C), followed by a padding length field which will also have a value of 12. What I don't understand is, if you add all that up, you get an encrypted length of 49 bytes, but the wireshark packet has 48 bytes.

Is anybody able to explain the difference?

In RFC2246, if you need 12 bytes of padding total, that means that you have 11 padding bytes, followed by a padding length field.  So, each padding byte has a value of 11 (0x0b), as well as the padding length field.  This is implied by the requirement that the total TLSCiphertext.length must be a multiple of the block size, and this TLSCiphertext.length includes the padding length field itself.


It is the IV shared in CBC mode? I don't know if the IV in CBC mode is equal in both sides of the encryption and decryption operations.

I know that the IV must be unpredictable, but has it to be MACed in the encryption side to be deMAC and "rebuilt" to use it in the decryption side ?

So you need to "transport" the IV along with the cypher-text to use it in the decryption ?

Yes, the IV is the same in both encryption and decryption for all modes that use an IV.  And yes, the decrypter must have access to the IV to decrypt the ciphertext.  The IV is not a secret.

The only caveat is that for CBC mode the IV must be unpredictable to an attacker whose data is being encrypted by another party.  Once the attacker has presented the data to be encrypted that IV need no longer be secret.


Is GCM still recommended? I stumbled across a forum thread where security researcher Thomas Ptacek
seemed to have negative feelings towards GCM. I had always thought from prior readings that GCM was the current gold standard for efficient, secure, easy-to-use AES modes?

Here is a summary of the “news.ycombinator” thread:

  tptacek: But CTR+HMAC is, in fact, a composed authenticated encryption mode. If you have a working system with CTR+HMAC, I'd recommend against spending effort switching to GCM, which is actually harder to get right.

  sargun: I thought AES-GCM was on its way out? Isn't poly1305-chacha20 what we should use now, given that it's quite a bit cheaper in terms of cost, and the keys are much smaller (32 bytes)?
  Also, the code for chacha is easily available.

  tptacek: I definitely personally prefer ChaCha/Poly to GCM, but GCM is unfortunately quite popular right now; of the unencumbered AEADs blessed by NIST, it's very performant and thus widely implemented.

I get that if you have a working crypto scheme like CTR+HMAC working, it isn't worth the effort to switch. What confused me is that he said GCM "is actually harder to get right." What would make GCM mode harder than CTR+HMAC?

The "hard part" about GCM implementation is resistance to side-channel attacks, especially cached-based. GCM is the combination of AES-CTR, and a custom MAC that relies on multiplications in a binary field (GF(2128)). Efficient implementation of that operation classically uses tables, which can lead to cache-timing attacks because the accessed table slots will depend on the secret data (though cache-timing attacks have never, to my knowledge, been spotted "in the wild", they work very well in lab conditions so the common wisdom is that they are a plausible threat).

If you have a recent enough x86 CPU then you have the AES-NI opcodes, which help for AES but also for multiplications in binary fields, making GCM both resistant to side-channel leaks and very efficient. But smaller devices do not necessarily have the luxury of such a hardware-assisted implementation. In fact, it may be argued that performance is much more likely to be an issue on small embedded CPU (say, the low-end 32-bit ARM CPU) than on big PC, where encryption only uses a small fraction of the available computing power.

For small CPU, Poly1305/Chacha20 will be faster, with a smaller footprint, and more resistance to side-channel attacks. Techniques for making a constant-time implementation of AES are still applicable (like the Kasper-Schwabe implementation) but will offer lower performance because a 32-bit small CPU has only 32-bit registers (the Kasper-Schwabe code uses bitslicing techniques to run 8 parallel AES instances over 128-bit registers, but with 32-bit registers this goes down to 2 parallel AES instances). For the binary field part, one can use plain integer multiplications, but with most bits cleared to avoid problems with carries, so there will be a lot more multiplications than with a prime-field based MAC like Poly1305.

GCM is there to stay because it got NIST blessing and thus made its way to many standards; it even convinced CPU vendors to include specialized opcodes, and this in turn will reinforce its position.

Meanwhile, research on AEAD modes is still active, and there is an ongoing competition with interesting candidates (e.g. NORX). Thus, while there is a bit of dissatisfaction over GCM because of implementation issues, the succession is still open. Poly1305+ChaCha20 got a little headstart by being there first, but that does not make it an automatic fallback.

A common problem to both GCM and Poly1305+ChaCha20 is the need for a non-repeating IV. Such an IV is easily managed in the context of a streamed protocol (such as SSL/TLS) but it can be a source of trouble for encryption of independent messages -- IV reuse is a mortal sin and is not easily tested for in a given implementation. An IV-less encryption system would need to be a two-pass method (which is not necessarily a problem for encrypting messages); a possible candidate would be a counter-intuitive MAC-then-encrypt construction, with (say) HMAC computed over the plaintext, and the HMAC value being used as IV for AES-CTR encryption.


Is double AES-CBC encryption with the same key and IV unsafe? If some plaintext encrypted twice with the same AES function (CBC-mode), same IV and same key, is it possible to retrieve either the key or the plaintext?

No, it is not possible.

The encryption step of CBC is $c_i = E(c_{i-1} \oplus p_i)$. When you double encrypt, the previous block ciphertext gets XORed with an independent block cipher output. The only place where something weird could happen is the beginning.

If you assume that the (identical) IV $I$ is prepended to the ciphertext, as is common, you get $I, E(I \oplus p_1), ...$ after the first encryption and then:
$$I, E(I \oplus I) = E(0), E(E(0) \oplus E(I \oplus p_1)), ...$$

This is wasteful, easily detectable due to the encryption of the zero block in every message, but not decryptable by an attacker. If the IV is not prepended, it is even more clearly not an issue. (However, there is no reason to believe it would be a good idea to do this either.)


Implementing a one-time pad without binary? I found a program which takes a purely alphabetical message, converts the letters to their ASCII values and combines them with the ASCII values of an alphabetical key (wrapping around when it gets to Z).

(The key being used is fully random and is required to be at least a long as the message.)

But from what I usually read about one-time pads, the message and the key are in binary, and the bits in the message is XORed with the key to produce the ciphertext. Combining the ASCII values sounds like a similar but obviously very different process.

Is this a valid way to implement a one-time pad? Or does the process merely resemble the binary XOR and doesn't have the same cryptographic properties as a one-time pad?

Actually, one-time pad can be implemented on the basis of any finite group operation; with these requirements:

The pad must consist of random group members; that is, each element in this pad must have equal probability of being any specific group member, and there must not be any correlation between different entries within the pad.
The encrypt and the decrypt processes are slightly different; if $\oplus$ is the group operation, $P_i, C_i$ is the i-th group element of the plaintext and ciphertext, $K_i$ is the i-th element of the pad, and $Inverse(x)$ is the group inverse of the element $x$, then the encrypt process is:

$$C_i = P_i \oplus K_i$$

while the decrypt process is:

$$P_i = C_i \oplus Inverse( K_i )$$

Now, when we work in the xor group, the inverse operation is actually the identity (because each element is its own inverse), hence we usually don't explicitly call this detail out.  However when we work in other groups, this distinction becomes important.

As long as the above is followed, the standard security proof for one-time-pads applies.


A proof-of-work random number generation system for Pokémon (The original question that was here was considered too confusing, unclear, and rambling. You can still view it in the edit history, but the content is no longer useful by itself, and cannot be reasonably reconstructed into a question suitable for this site. The question object is still here by decision of a moderator, as a placeholder to preserve any reputation gained by the answerers of this question while it was still active, as well as to preserve the original question content in case any new questions are built upon this one.)

It is hard to tell from this question, but I suspect that you may have managed to confuse yourself about what problem you have: i.e., that you've gotten caught up in a particular mechanism, and would benefit from taking a moment to step back and look at the actual requirements.  I found it hard to extract the actual requirements from your question.

In these situations, it's always a good idea to ask yourself the question: What is my threat model?  What kinds of threats do you need to defend against?  What kinds of attack vectors are possible for an attacker?

For instance, a crucial question is: do you trust the game software that is running the game?  It sounds like you want to say that you don't trust the software, but that leads you to an unsolvable problem.

Or, to put it another way, it seems like there's a simple solution to your problem.  Your game software can generate truly random numbers using a suitable random number source (e.g., /dev/urandom or CryptGenRandom).  There doesn't seem to be any reason to use a deterministic PRNG, and no reason for the random numbers to be derived from untrusted user inputs.  Doesn't this solve all your problems?  Why are you going into such complicated stuff, when there's a much simpler way to generate random numbers that also happens to eliminate the issues you're worried about?  Is there some requirement that I'm missing?

If you're about to say "but the user could modify the game software's RNG to bias its output", my response will be "yes, that's always possible, and nothing you will ever do will ever be able to stop that".  Realistically, you can't prevent reverse-engineering of your software.  The user who is running your software could always run a modified version of your software that gives them better stats, and no amount of cryptography is ever to make that impossible.
But in any case, these are the kinds of questions you should be working out when you think through your threat model.

I confess I had a hard time understanding what proof-of-work has to do with trusting that the random numbers you generate are trustworthy.


Unpredictability vs randomness I'm experimenting with creating an entropy source for an environment where I have no hardware available and the language is very high level (executed in a virtual machine). I know it's not a good idea but I don't have /dev/random or CryptoAPI and the only possible sources are things like http://random.org but they need a network connection and is discouraged.

I have tried to execute a tight loop and get entropy from the elapsed times which, because of the CPU scheduling and other processes activities, has some variance. This source of entropy is of very poor quality but it seems unpredictable as long as someone has not access to the physical machine where the generator is running. Nevertheless, if I run the "ent" tool through the values I get it shows that they are strongly correlated and not truly random.

If I then iterate Von Neumann unbiasing between 2-4 times, until the point the resulting data passes the chi square test of "ent" (BTW: this process always converges), it seems that I get truly looking random numbers.

My question is: would this random numbers be unpredictable because their source is unpredictable or am I masking possible errors and fooling myself? What would happen if I used this numbers to seed a PRNG based on AES in CTR mode with a key and IV?

The process of turning inputs that are hard to predict (formally, inputs that have some min-entropy) into bit strings that are cryptographically uniformly random is called entropy extraction. So there's your search term if you want to learn more theory.

The problem. The fact that your outputs produce values that can pass a given statistical test (or even a suite of standard tests) is a bit encouraging, but far from a guarantee. The tests in question know nothing about your entropy source or extraction function, but presumably an attacker will. Therefore an attacker may be able to exploit some non-uniformly random characteristic of the output that would go unnoticed by the test.

I have no idea how likely this is in your particular setting. But if you want to place your system on a more solid theoretical foundation, you need to use a proper entropy extractor.

The easy way out. Before continuing, I should say that in practice, a lot of people would simply take the output of the entropy source, hash it (using SHA-256 for example), and use the result to seed an AES-CTR PRNG.

PRNG Seed = SHA-256(Entropy)

Despite the fact that hash functions aren't really designed to take this kind of abuse (they are not random oracles!), so far this approach hasn't led to any practical attacks --- at least, that I know of. This might be good enough for you as long as you harvest enough entropy to make a brute-force attack infeasible.

If you're particularly paranoid and want to be a good cryptographer, read on.

The "Right" Solution. In order to construct an entropy extractor, first you need access to a random seed. Which seems a bit circular, but, crucially, the extractor seed does not need to be secret and it does not need to change. (In contrast, the PRNG seed most definitely does). So you could generate one elsewhere and send it over. The only restriction on the extractor seed is that it needs to be generated in a way that's independent of your entropy source, and you need to assume that an attacker can't influence the entropy source based on his knowledge of the extractor seed.

Now that you have a seed in hand, the question is how much effort you're willing to expend on implementation. You can use the seed as a key for HMAC-SHA256, and you'd probably be fine (see Randomness Extraction and Key Derivation Using the CBC, Cascade, and HMAC Modes by Dodis, et al.):

PRNG seed = HMAC-SHA256(Extractor Seed, Entropy)

If you want to be a bit more paranoid, find code that implements a polynomial hash over a finite field (this could probably be taken SSL's GCM code), use the entropy to encode the coefficients of a polynomial, and evaluate the polynomial at the value encoded by the extractor seed. (See, e.g., Leftover Hash Lemma, Revisited by Barak, et al.)

PRNG Seed = PolyHash(Extractor Seed, Entropy)

Regardless of which of these two approaches you take, in order to get a strong degree of security you'll need around 160 bits of min-entropy to generate a 128 bit PRNG seed (i.e., an attacker should not be able to predict your entropy with probability more than $2^{-160}$). Note that since there are likely redundancies in your entropy source, the strings you get from it may need to be considerably longer.


AES encryption for pairwise identifiers I'd like to map a random ID of 16 bytes (sourceID) to another random ID of 16 bytes (targetID).

The operation should:

only be reversible by me
be deterministic

There are about 1 million source ID's that need to be mapped. The target ID is public, while the source ID is private.

I was thinking of using AES with ECB to map the source ID to target ID.

mapID(sourceID, key) = targetID

What is the likelihood of someone being able to reverse the process if they only have the targetID?

Is this a terrible Idea?

No, this is not a terrible idea, this is an idea that is often used.

Basically you've described the main use of a symmetric block cipher for exactly the block size of AES. AES is fully deterministic and not reversible without the key.

A block cipher is a Pseudo Random Permutation (PRP) - basically a map - from a set of all possible plaintext to a pseudo-randomly ordered set of all possible ciphertext. The possible plaintext and ciphertext consist of all possible values for the given block size, in this case 128 bits. This maps perfectly with your input and output size.

Beware that:

source ID's will always map to the same target ID's, even in time;
an attacker can see from identical target ID's that the same source ID was used;
if an attacker can change the target ID then it will decrypt to a random source ID;
if an attacker can switch known target ID's the reversed source ID's will be switched as well.

If above can lead to problems depends on your use case / threat model.


How to find the interpolation polynomial of the DES S-boxes The Lagrange interpolation polynomial of the AES S-box has degree 254 and 9 terms in it. How about the DES S-boxes? How can we calculate the interpolation polynomial for S-boxes having a different number of input and output bits?


How does the HOTP dynamic truncation function generalize to longer hashes? HOTP, the HMAC-based One-Time Password algorithm from RFC 4226, uses a "dynamic truncation" function to turn the 20 byte HMAC-SHA-1 value into a 31 bit string. The dynamic truncation (from Section 5.3) works like this (and is probably useless):

 DT(String) // String = String[0]...String[19]
 Let OffsetBits be the low-order 4 bits of String[19]
 Offset = StToNum(OffsetBits) // 0 <= OffSet <= 15
 Let P = String[OffSet]...String[OffSet+3]
 Return the Last 31 bits of P

TOTP (RFC 6238) allows using SHA-256 and SHA-512 as the HMAC hash in HOTP, but doesn't seem to define a new dynamic truncation function for use with them:

  TOTP implementations MAY use HMAC-SHA-256 or HMAC-SHA-512 functions,
    based on SHA-256 or SHA-512 [SHA2] hash functions, instead of the
    HMAC-SHA-1 function that has been specified for the HOTP computation
    in [RFC4226].

Should I use low 4 bits of String[19] as offset, low 4 bits of String[length-1], or perhaps some other number of bits or a completely different truncation algorithm?

I managed to find it out by reproducing the test vectors.

TL;DR: The standard assumes that you use the low 4 bits of the last byte of the hash, regardless of its length. So replace 19 in the original DT definition with 31 for SHA-256 or 63 for SHA-512 and you are good to go.

Finding this out wasn't completely straightforward, as the standard only has a single test secret listed:

  The test token shared secret uses the ASCII string value
     "12345678901234567890".  With Time Step X = 30, and the Unix epoch as
     the initial value to count time steps, where T0 = 0, the TOTP
     algorithm will display the following values for specified modes and
     timestamps.

If fact, to reproduce the test vector values for SHA-256 and SHA-512 you have to extend that secret to 32/64 characters. I.e. use the ASCII strings "12345678901234567890123456789012" and "1234567890123456789012345678901234567890123456789012345678901234" instead.


Please punch holes in this authentication scheme Folks, I am undertaking a crypto course in Uni. Our professor asked us to try and design some authentication schemes which are resistant to active attacks. This was just a in class exercise to get us interested in the topic. It did the trick, I have been trying to come up with something using what we have learned so far.

Here is a authentication scheme I developed :

Please punch holes through it and tell me what attacks are these vulnerable to?

P.S - Notation explanation : Ka+(Rb) denotes the encrypted text that was generated by encrypting the nonce generated by Bob using Alice's public key. This text is decrypted by Alice using her private key Ka- and gets Rb. Alice then encrypts Rb with her private key and sends it to bob. Who then uses Alice's public key to decrypt the message and get text. If this text is same as Rb then alice Has been authenticated to Bob

Similarly Ka-(Rb) denotes encrypted text obtained by encrypting nonce generated by Bob using alice's private key

P.P.S - Before you guys suggest Man-In_middle attack : Here is why I think it wont work :

The protocol's description includes "Alice then encrypts $R_B$ with her private key". This has no standard meaning. Comments have clarified it is used an "RSA encryption scheme with proper padding" and I am taking as granted that encryption of $R_B$ using the private key half of $K_A$, denoted $K_A^-(R_B)$, is obtained by padding $R_B$ as in encryption, then applying the RSA private key exponentiation of $K_A$. This can be a valid form of signature (while RSA signature and encryption usually use different padding, it is possible to define a secure padding that works for both encryption and signature).

The protocol does nothing to prevent a MitM attack. In the usual definition of that, Charlie's goals are:

impersonate as Alice to Bob, or/and to Bob as Alice;
be able to understand all that Alice says to Bob, or/and Bob says Alice;
be able to make Alice believe that something Charlie decides comes from Bob, or/and make Bob believe that something Charlie decides comes from Alice.

In order to achieve every single of these goals, Charlie:

receives "I'm Alice" from Alice, relays that to Bob;
receives "I'm Bob" from Bob, relays that to Alice;
receives $K_A^+(R_B)$ from Bob, relays that to Alice; (I'm using the first drawing as reference, where's that before the next step)
receives $K_B^+(R_A)$ from Alice, relays that to Bob;
receives $K_A^-(R_B)$ from Alice, relays that to Bob, and also applies Alice's public key to that and removes any padding, thus getting $R_B$;
receives $K_B^-(R_A)$ from Bob, relays that to Alice, and also applies Bob's public key to that and removes any padding, thus getting $R_A$.

From then on, Charlie acts with respect to Alice using the (unspecified) protocol defined for Bob, including deciphering Alice's messages, and forwarding anything Charlie decides to Alice, which has no way to tell that it comes from Charlie rather than Bob; and similarly acts with respect to Bob using the (unspecified) protocol defined for Alice.

Charlie reached all his goals. The only thing that Charlie does not know is the padding used in $K_A^+(R_B)$ and $K_B^+(R_A)$ if that's random padding, but there is no indication that some use is made of it.

Further, if for some reason Charlie wants to choose his own nonce $R_C$ as in the second drawing, rather than use $R_A$ or $R_B$ (perhaps because the protocol is extended with "After authentication, perform the action defined in the low 20 bytes of the $R$ that I sent"), Charlie can still achieve that. In order to impersonate Alice w.r.t. Bob using an $R_C$ of Charlie's choice instead of $R_A$ chosen by Alice, Charlie

receives "I'm Alice" from Alice, relays that to Bob;
receives "I'm Bob" from Bob, relays that to Alice;
receives $K_A^+(R_B)$ from Bob, relays that to Alice;
receives $K_B^+(R_A)$ from Alice, discards this, computes $K_B^+(R_C)$ and sends that to Bob;
receives $K_A^-(R_B)$ from Alice, relays that to Bob, and also applies Alice's public key to that and removes any padding, thus getting $R_B$;
kills the session with Alice;
receives $K_B^-(R_A)$ from Bob, discards it.

From then on, Charlie acts with respect to Bob using the (unspecified) protocol defined for Alice, including deciphering Bob's messages, and forwarding anything Charlie decides to Bob, which has no way to tell that it comes from Charlie rather than Alice.
Kudos to mikeazo for finding a mistake, hopefully fixed.

In a comment to the present answer, the protocol is extended by adding:

  Alice sends Bob a pre-master secret encrypted in Bobs public key; then
  both of them use this premaster to calculate master secret.. and
  communicate using that key"

That extended protocol is still vulnerable to an attack where Charlie impersonate Alice with respect to Bob. Charlie performs as in the first attack, then

kills the session with Alice;
pretending to be Alice, sends Bob a pre-master secret of Charlie's choice encrypted in Bobs public key;
then Bob and Charlie use this premaster to calculate the master secret.

In fact, no addition after the protocol can protect against a MitM attack, unless it uses another public key of the participants, or another padding scheme with the existing key.

That's because Alice's behavior allows using her as a decryption oracle: by participating in the beginning of whatever extension of the protocol, Alice accepts doing steps that can be abused into the equivalent of decrypting anything with her private key, and since no other use is defined for her private key, making a fake connection attempt with Alice is as good as having Alice's private key.

The protocol can be strengthened, and the unclear "encrypt with private key" removed, as follows.

We consider an asymmetric encryption scheme with encryption $E_{Pub}(P)\mapsto C$ and decryption $D_{Priv}(C)\mapsto P$. We assume an infrastructure to verify the validity of public keys.

A participating entity $A$, when communicating with (alleged) entity $B$

sends I'm $A$, and receives I'm $B$;
checks that $B\ne A$;
obtains the authentic public key $Pub_B$ of $B$ (how is not part of this protocol; a common technique is that $Pub_B$ is sent together with I'm $B$ as part of a certificate, which is verified according to a master public key);
draws a secret random $R_A=R_{A0}||R_{A1}||R_{A2}$ where each $R_{Aj}$ is 256-bit;
enciphers $R_A$ using $Pub_B$, yielding $C_A=E_{Pub_B}(R_A)$, sends it, and receives an alleged $C_B$;
deciphers $C_B$ using $Priv_A$, yielding $R_B=D_{Priv_A}(C_B)$ (or an error, which aborts the protocol);
breaks $R_B=R_{B0}||R_{B1}||R_{B2}$ into $R_{B0}$, $R_{B1}$, $R_{B2}$;
sends $R_{B0}$ and receives an alleged $\widehat{R_{A0}}$;
compares $R_{A0}$ and $\widehat{R_{A0}}$ (an inequality aborts the protocol);
uses $R_{A1}\oplus R_{B2}$ as an AES-GCM key for communication from $A$ to $B$, and uses $R_{A2}\oplus R_{B1}$ as an AES-GCM key for communication from $B$ to $A$.

Messages are exchanged at steps 1, 5, 8, and 10 only. The order in which messages are sent and received in these steps is left unspecified, so that $A$ and $B$ can proceed without waiting for the other side between steps involving message exchange. Step 2. is necessary, otherwise an adversary reflecting what Alice sends will successfully make Alice accept whatever information she sends at step 10.

This protocol is better than the original. At least, a passive eavesdroper can not decode the information exchanged at step 10, as would have been possible in the original protocol. However this scheme is still NOT secure against a MitM attack assuming only that $E_{Pub}(P)\mapsto C$ perfectly preserves confidentiality. In particular, an attack is possible when $E_{Pub}$ encrypts each bit of the plaintext $P$ separately; finding this attack is left as an absolutely necessary exercise to any reader diving into protocol design.

When $E_{Pub}(P)\mapsto C$ is one of the RSA encryption scheme in PKCS#1, or when we remove steps 7. and 8. (making $R_{A0}$ and $R_{B0}$ pointless), I can not think of any mean for a MitM to intercept or alter any part of the plaintext exchanged at step 10, provided $A$ and $B$ act according to the protocol, and in particular never disclose or use any of $R_A$, $R_B$, $R_{A1}\oplus R_{B2}$, $R_{A2}\oplus R_{B1}$ other than as instructed.


Signal Protocol Header key encryption initialization vector In Signal Protocol when you use a Double Ratchet you have 2 options:

Normal encryption = header + ciphertext
Encrypted header encryption = encryptedHeader + ciphertext

The encrypted header encryption has the advantage of encrypting the public ratchet key pair and counter, this can also encrypt the message mac and possibly the ciphertext length encase needed over a network.

When encrypting a header you must have an initialization vector (aka IV) since the key will only change once receiving a new ratchet key pair (when moving a step in the DH ratchet (specified in the Double Ratchet documentation)).

You can read more about the function that header encryption must follow in DoubleRatchet - External Functions.

NOTES:

The header will be encrypted with "AES/CBC/PKCS5Padding" (in Java PKCS5Padding is actually PKCS7Padding) as specified in Java or in normal cryptography AES with CBC mode and PKCS7Padding as the padding
The ratchet public key is 32 bytes

From what I can think of I have 3 options for choosing the initialization vector now:

Generate a new 16 byte initialization vector and prepend it before the header
Take the first 14 bytes of the current ratchet public key (NOTE: the ratchet public key changes every DH ratchet step) and append the current counter as a short (NOTE: the counter increments every message and resets to 0 every DH ratchet step) which should generate a unique initialization vector, tho mostly predictable (NOTE: this is mostly predictable because this is considering if they actually have the ratchet public key and counter, with header encryption they are encrypted so they should be unknown to a malicious party)
Use the second option just with instead of taking the first 14 bytes of the ratchet public key taking for example the first 30 bytes (will result in 32 once appending the counter) or even the whole key.

So my question is, which should I choose?

Things to consider:

The first option gives a more random value, yet exposes it and also take 16 bytes more space.
The second option gives a less random value tho the first 14 bytes will still look random, the initialization vector is not exposed which possibly increases security and takes 16 bytes less space
Third option results in a bigger initialization vector making it more random

The security contract for AES-CBC is that the initialization vector must be uniform random and unpredictable in advance—mere uniqueness is not enough (nor even necessary).

It is safe to choose the IV as a pseudorandom function of a unique nonce, or even as a pseudorandom permutation of a unique nonce, which the sender and receiver can agree on—e.g., they could choose it to be a message counter, if they are both capable of counting—without sending any explicit IV over the wire.  Indeed, you could even use a message counter encrypted with AES under the same key, as long as the attacker has no control over the counter.

It is not safe to choose the IV as anything that an attacker can predict in advance, like a public key previously sent over the wire and a predictable counter.


Signature and hash function properties I understand the need for the hash function to be collision resistant and second pre-image resistant. For what reason, exactly, does a hash function need to be pre-image resistant?

If this property is not useful for signatures, what is the origin of this requirement, maybe privacy?

The question "why is preimage resistance needed for hash functions" is not really relevant. This is because collision resistance implies preimage resistance. Thus, it is just a fact that if you have collision resistance then you must have preimage resistance.

So, instead, I will relate to what preimage resistance is good for at all. In more technical cryptographic terms, a preimage resistant function is called a one-way function. One-way functions are the most basic cryptographic primitive and you can construct all of symmetric crypto from them (i.e., you can construct pseudorandom generators, functions, symmetric encryption, message authentication codes, and so on). [Note: you cannot construct collision-resistant hash functions from them in a black-box way.] Thus, from a theoretical perspective, these functions are very interesting; I say "theoretical" since the above constructions are all theoretical and not practical.

Note that preimage resistance is a necessary condition almost everywhere in cryptography, but it is usually not sufficient. This is because it does not mean that it's impossible to obtain half of the preimage, and it is also only meaningful for very high entropy - if not random - inputs. The use of preimage resistance in hashing passwords is used in practice, but is only heuristic. In order to analyze this properly, you actually need to model the function as a random oracle.

So, preimage resistance or one-wayness is a fact of cryptography. It is the minimal property that you need to do almost anything interesting in crypto (apart from all of the information theoretic crypto work which I won't discuss here). However, it is not a security notion that is usually of interest in and by itself.

A proof sketch that collision resistance implies one-wayness

Assume that there exists an adversary $A$ who can invert a function $H:\{0,1\}^*\rightarrow\{0,1\}^n$ with probability $\epsilon$ on a random input of length $2n$. We construct an adversary $A'$ who finds a collision in $H$. Adversary $A'$ chooses a random $r\in\{0,1\}^{2n}$, computes $y=H(r)$ and invokes $A$ on input $y$. If $A$ returns $s$ such that $H(s)=y$ and $s\neq r$ then $A'$ outputs $s$. Otherwise it outputs $\bot$. We now analyze the probability that $A'$ succeeds. We have that $A'$ succeeds if $A$ succeeds and $s\neq r$. Since the input is of length $2n$ and the output is of length $n$, we have that each output has on average $2^n$ premiages. Thus, the probability that $s=r$ is negligible. [This part of the proof needs some work, but I'll leave that to the readers as an exercise.] We therefore conclude that $A'$ succeeds with probability $\epsilon - neg(n)$ where $neg$ is a negligible function. Thus, if $\epsilon$ is non-negligible then the function $H$ is not collision resistant. We conclude that if $H$ is collision resistant, then $A$ could only succeed with negligible probability and so $H$ is one-way.


Does pepper *require* an HMAC? Assume you are already given a properly-salted, password hash $X$ from some slow PBKDF (e.g., like Argon2id).

Now, you want to apply some large (~256-bit) secret "pepper" $S$ to it before storing it in the database.

Is there a significant difference between storing it as an
$$\text{HMAC}\left(S,X\right)$$
(where $S$ is the secret key to the HMAC of $X$) versus a "much simpler/basic"
$$H\left(S\mathbin\parallel X\right)$$

where $H$ is just some SHA-2? (e.g., SHA-256/512)

No for this scenario where the message is statically sized, using a HMAC is not required. You can use a sufficiently strong hash such as SHA-2 or SHA-3 instead if you must.

That said, it would probably be more neat to use a HMAC or even KDF. The advantage is that these algorithms do take input keying material as a separate parameter. This might be interesting if you want to keep the pepper secret; you could store it in a hardware device and use it for HMAC, for instance.

Currently you are using the hash as poor-man's KDF. So if you can spare a few cycles you might go for a more luxurious option like HKDF (which is based on HMAC).


Does GHASH use XOR or addition? I've been looking into GHASH and some sites describe it as a polynomial:

A1*(H* *M-1)+A2*(H* *M-2)...C1*H(H* *M-N)+C2*H(H* *(M-N-1))...+len(A||C)*H+E(0)=t

while other sites replace the + with the XOR symbol, ^:

A1*(H* *M-1)^A2*(H* *M-2)...C1*H(H* *M-N)^C2*H(H* *(M-N-1))...^len(A||C)^H+E(0)=t

Which one is the correct one?

There is no difference in this context. XOR is sometimes called "carryless addition" because one bit addition mod 2 is identical to the one bit XOR operation. Multiplication is also carryless in this context.


How to compute $a$ in the complex discard method of NIST SP 800-90 I've got a question about the complex discard method that has been specified in NIST SP 800-90, appendix A.5.2, steps:

Use the random bit generator to generate a sequence of $m$ random bits, $(b_0, b_1, …, b_{m-1})$.
Let $c = \sum_{i=0}^{m-1}2^i \cdot b_i$.
If $c < r$, then
let $(a_0, a_1, …, a_{t-1})$ be the unique sequence of values satisfying $0 ≤ a_i ≤ r -1$
such that $c = \sum_{i=0}^{t-1}r^i \cdot a_i$ else discard $c$ and go to Step 1.

OK, so step 1 is the same as generating as many bits as required for the number, i.e. $m$ bits where $m$ is the number of bits required to encode $r-1$ where $r$ is the end of the range starting at 0 (and exclusive of $r$ itself, of course).

Then step 2 is basically interpreting those bits as a number.

Now step 3 suddenly introduces a set of output values for this random number generator, $(a_0, a_1, …, a_{t-1})$. These numbers need to confirm to the condition that added together after multiplication with $r$ to the power of $i$ up to $t$ that they are equal to $c$.

Wouldn't the numbers $a_i$ be too small in that case? How can the $a_i$ values be calculated?

Wouldn't the numbers $a_i$ be too small in that case

No, it's just a simple base conversion; you take the integer $c$, and represent it in base $r$; the values $a_0, a_1, ...., a_{t-1}$ are the digits of the resulting conversion.

There are lots of ways to do base conversion; the simplest (if not the most efficient) would be:

For i := 0 to t-1 do
    a[i] = c % r
    c = c / r

(with % being the modulo operation, and / being integer division rounding down)


Why does only length prepending improve the security of CBC-MAC I know that length prepending improves security of CBC-MAC. However, wouldn't inserting the length elsewhere (middle, end or any other part of message) be equally good? After all, even the length is processed by the underlying cipher block.

Well, let's try it, and see how hard it is to forge a message.

Let's say for illustrative purposes that each character is a block, and that numbers represent the length indicator section.  And let's start by putting the length indicator at the end.  So,

XXXXXXX7

represents a 7-block message, with the '7' indicator at the end.  Let's also say that,

$_{MAC}($XXXXXXX7$) = M_0$

represents the MACing of that 7-block message, with the resulting Tag $M_0$.

How hard is it to forge?  It is trivially easy.  All you need to do is request the MAC of three messages like so:

1) $_{MAC}($AAAAA5BBB9$) = M_1$

Note the '5' in the middle of the message.  For this first MAC, that is just part of the requested message -- only the '9' at the end has been added by the length-appending algorithm to indicate the total length of the message.

2) $_{MAC}($AAAAA5$) = M_2$

3) $_{MAC}($CCCCC5$) = M_3$

Then xor $M_2$ and $M_3$:

$M_2 \oplus M_3 = D$

And let $ E = B \oplus D$, and now you can trivially forge the Tag for a new message that you did not request from the MAC Oracle:

$_{MAC}($CCCCC5EBB9$) = M_1$

Note that the same logic applies if the length indicator is anywhere in the message except right at the beginning.


Is there an additive homomorphic encryption that supports exponentation For example say we have two numbers a and b. Now is there any partial homomorphic encryption scheme that allows to compute (a-b)^2 over the ciphertexts of a and b without round trips.

What you want is a cryptosystem that supports linear operations, and some bounded number of multiplications (supporting exponentiations by bounded values is equivalent to supporting multiplication, as to compute a*b homomorphically, you can always compute (a-b)²-a²-b² homomorphically and divide this by two). Without requiring a bound on the number of multiplications, this is just fully homomorphic encryption.
With a bound, it is known as somewhat homomorphic encryption (SHE). Most constructions for SHE are based on lattice assumptions (such as LWE). A noticeable exception is the Boneh-Goh-Nissim (BGN) cryptosystem which uses pairing based cryptography; the scheme is homomorphic for linear operations and one multiplication (e.g. one squaring as in your example), in any order (e.g. the function f:(a,b) -> a² + b² can be computed homomorphically with the BGN scheme). However, as decryption requires a discrete logarithm, the plaintexts must be small for the decryption algorithm to be efficient.
However, for your particular example, there is even a simpler way: there is a generic conversion from any linearly homomorphic encryption scheme (with some reasonable properties) to an homomorphic scheme that supports linear operations, then one multiplication, then a bounded number of linear operations (once the multiplication was performed, the ciphertext grows linearly with the number of additional linear operations you perform). The article is "Boosting Linearly-Homomorphic Encryption to Evaluate Degree-2 Functions on Encrypted Data". f:(a,b) -> (a-b)² is typically the kind of operations supported by this conversion. Such a cryptosystem can be constructed from the (additive variant of the) ElGamal cryptosystem, or the Paillier cryptosystem, for example. From the Paillier cryptosystem, you get such a degree-two homomorphic cryptosystem, with no restriction on the plaintext size as in ElGamal or BGN.


Chain several RSA encryptions without increasing the message size I would like to be able to encrypt the output of RSA with RSA again without having the output grow in size over time.

In other words, I have some data $D_0$ which I want to encrypt with RSA: $D_1 = \mathrm{RSAencrypt}_{K_1}(D_0)$. Then, I would like to be able to encrypt $D_1$: $D_2 = \mathrm{RSAencrypt}_{K_2}(D_1)$, and so on, until $D_n = \mathrm{RSAencrypt}_{K_n}(D_{n-1})$. I want the successive messages not to grow in size: $|D_1| = |D_2| = \ldots = |D_n|$.

Since I obviously want the process to be secure, I suppose I should use some padding. It actually works with RSA_NO_PADDING but as soon as I add some padding, the output is the maximum size which is too large for adding padding for a next round of $\mathrm{RSAencrypt}$.

I was wondering if there was a way to make sure the output does not exceed the size required for another encrypt (e.g modulus - 11), through a specific padding for instance.

I am going to try to explain better what I am trying to accomplish. I've read a paper (http://research.microsoft.com/pubs/102086/key_regression.pdf) about key rotation which consists in taking a RSA key, $K$, and rotate a number $N$: $\mathrm{encrypt}_K(N_0) = N_1$, $\mathrm{encrypt}_K(N_1) = N_2$, etc. I'm basically trying to implement it.

At every step, one can deterministically determine an information based on the number $N_x$.

Now given the RSA key pair, we can imagine the owner keeping the private key which is used for rotating $N$ while the public key is disclosed to a set of users.

Any of those users could therefore derive the previous versions of $N$ by applying $\mathrm{decrypt}_K(N_x) = N_{x-1}$. One would however be unable to determine the future versions of $N_x$ since only the owner of the private key is capable of rotating $N$.

Hope it helps clarifying the use case :)

In this scenario, you don't need to do any padding (except for the first encryption).

If what you're encrypting with RSA is a random number between 0 and the modulus size, then you don't need any padding.  Padding is there to prevent the attacker from using the multiplicative properties of RSA to derive one plaintext from a bunch of others; this attack involves finding smooth plaintexts.  When a plaintext is a random number from the full range, this is unlikely to ever happen, and so we don't need to worry about it.

Note that, unless the original message (D0) is also a random number between 0 and N-1, you'll want to pad that.

In addition, in the decrypt direction, doing multiple decryptions can be done far more efficiently than applying each decryption in succession; you could actually apply (say) 1,000,000 successive decryptions almost as efficiently as you can do one.

On the other hand, it is not at all clear what you hope to gain from this procedure.  What is the problem you are solving?


Homomorphic encryption methods that could support logical XOR, AND? Recently I'm researching about logical circuit calculation and I hope to use homomorphic encryption to protect the whole process. I've read Gentry's paper and use some websites like https://asecuritysite.com/encryption/hom_xor, and I wonder if there are some other methods?
Few days ago, I thought that position transformation like Caesar cipher could just support my thoughts. For instance, $(4 \gg 1) \oplus (5 \gg 1) = (4 \oplus 5) \gg 1$. But my professor told me that this is unreasonable and could even not be seen as "encryption" for lacking of random number. Is he right? Or maybe I could adjust this thought so that it is able to be accept as a "homomorphic" calculation for logical operation?

Partial and Fully Homomorphic Encryption
When a homomorphic encryption scheme supports a single operation on the encrypted data like

RSA has a modular multiplicative operation
Elgamal has a modular multiplicative operation
Goldwasser–Micali cryptosystem has x-or operation
Paillier cryptosystem has a modular addition operation

it is called partial homomorphic. When they support two operations they are called Fully Homomorphic Encryption (FHE) in the sense that one can build arbitrary circuits with them constrained to some conditions.
The two operations in the FHE scheme are usually addition and multiplication. In the bit-based case, the addition is XOR $\oplus$ and the multiplication is AND gates $\wedge$. Though neither the XOR nor the AND are universal logic gates, when combined they can construct any gate. And note that the randomization on the encryption requires a different design than the usual circuit design.
Public Key!
All FHE schemes that I know are based on public-key. Therefore if the randomization is removed then an attacker can use the public parameters to determine the encrypted values. If one looks at the Ind-CPA game for public-key encryption, we consider that the encryption oracle is free to the adversary. As a concrete example, consider TextBook RSA encryption (it has no padding, insecure, and it is multiplicative) with single-bit encryption then you can immediately deduce it, even for a byte or a word.
This is dangerous and we left it with the seminal paper of Shafi Goldwasser and Silvio Micali

Probabilistic Encryption, April 1984

You can also get the notion from the famous ECB picture of tux in Wikipedia.
There are many libraries for FHE that you may look at like HeLib, TFHE, Seal. If you like to read how some small circuits are designed, you can read from here Representing a function as FHE circuit and see some of the implementation papers, too.


What are the BLS12-381 settings? I can't find the exact type and settings for the BLS12-381 curve.

Is this type-3 in Symmetric XDH settings ?

BLS12-381 is a Type 3 curve, yes. I'm not aware of any difficulty of assuming SXDH for BLS12 curves, and there's no reason BLS12-381 in particular would be special in this respect.
(Almost all pairing-based protocols defined recently are designed for Type 3 curves, and almost all curves defined recently for pairing-based crypto are Type 3. If you come across anything else, it's probably quite an old protocol or curve that hasn't taken into account later cryptographic developments, and you should be quite suspicious of that.)


Encrypting data with two separate keys Goal
We want to find the most secure way to encrypt message of arbitrary length M with AES such that the recipient can only decrypt if they have both AES keys K1 and K2.
Preconditions:

AES keys K1 and K2 are independent and randomly generated, 256-bit keys
Assume we'll be running AES-GCM
Key exchange for the valid recipient has already be performed
Performance is not a concern (operation is performed less than once a couple of seconds)

Options (I could think of)
Option 1: XOR
Derive a new key K3 = K1 ^ K2 and perform encryption on M using K3.
Given that there are no known weak keys or known weaknesses in AES, only practical way for deriving K3 is by having pre-existing knowledge of K1 and K2.
Option 2: KDF
Compute $K_1\mathbin\|K_2$ (concatenation of the two keys) and feed the result to a KDF (perhaps HMAC based KDF) and use the resulting key as the AES key to encrypt M. I don't think this is significantly different from Option 1, but I'm listing it as an option anyway.
Option 3: Encrypt twice
Perform two layers of encryption:
C1 = Encrypt(M, K1)
C2 = Encrypt(C1, K2)

Send C2 as the cipher text. My intuition is that this should be no less secure than Option 1.
Additional Information/Clarifications
This question is gear towards the two keys being used as something similar to the cryptographic equivalent of "Multi-factor Authentication". In particular, the user has to obtain two different keys (through different means) before being able to decrypt the data.
This question could be extended to the case where there are N keys. The constraint is that all N keys will always be required to decrypt the data.

I would say that all of them are valid options, with the security differences they might have negligible. So I focused on other properties of the approaches:
Option 1: XOR
I think the most interesting property here is the malleability that gives us the XOR function. If I'm a keyholder under this chema, I could give n keys which XOR to my half to my n children, and their keys combined will be as good as mine.
Similarly, it the requisites went from 2-people to 3-people (such as including a new partner in the business), they could each provide a random half-key to combine with their now-new-half.
It also has the property of being commutative. This is silly from a cryptographic and technological point of view, but if you are giving two keys to two people, one might think to be more important to have the "first" key, or feel hurted on their big ego for only being given the "second" key. Here, both keys are equal rank, their order doesn't matter at all.
Option 2: KDF
This woud be similar to the above, but not allowing you such malleability (which you may consider good or bad).
You may want to combine them in lexicographical order, so that it doesn't matter the order in which they are provided. For the reasons provided above and less user errors by not being possible to provide them in an order it doesn't work.
Option 3: Encrypt twice
This option would be slower, although just doing two layers of encryption would not be a noticeable hit. You should perhaps be careful to do both things "at once" or with pipes, not using intermediate temporary files that might end up recovered. Although you would still have the same concern with the final decrypted item.
This solution would be subject to a Meet-in-the-middle attack. I don't think this would actually be a realistic concern, since you would still need to break AES.
A new keyholder could be added by encrypting the existing ciphertext with the new key.
Same comment as above about setting an order would be applicable.
Option 4: Split the key in two
Just for completeness, I'm adding the trivial solution of, instead of giving 128 or 256 bit keys to each of them, directly providing half the key (64/128 bit keys) to each one. This means each key is half the size, with no benefit over the other solutions, so I wouldn't recommend it.


What math makes it safe to offer a stolen-password check service? The database provider HIBP has 4 billion stolen passwords, and wishes to offer an API for websites to use during new-user signup (and password change) operations, so they can refuse to allow users to select a password that is known to have already been stolen.

HIBP is not trusted.

Does a way exist for a website to ask HIBP some question, and receive some result, that never allows HIBP to determine the password being inquired about (including against dictionary attacks) assuming that the password is NOT in the database.
Is the above possible, even if the password is in the database?  e.g. can I check HIBP for existence of the string "password123", and get a result that I can understand means "yes, that exists", but which leaves HIBP with no way to know what string I queried, nor whether it was found?

This sounds like an interesting homomorphic challenge to me, but I don't know this field in depth.

If we think of this as secure multi party computation then we want to calculate a function on two inputs the DB and the password. We want to know if the password exists. We don't want the db holder to learn anything about the password and the password holder to learn anything about the db beyond the answer to the question does the password exist. This is definitely solveable with generic secure multi party computation solutions. You had an extra requirement of the db holder not getting the answer to the question which I suspect may not be possible(it might be).
See: https://en.m.wikipedia.org/wiki/Secure_multi-party_computation


Is AES-256 over AES-128 weakening the original encryption? When transfering data using TLS the browser and server agree the cipher suite to be used - so for example this could be chosen as AES-128 and is (probably) outside of my control. If I separately encrypt a file using AES-256 and then Alice downloads this via her browser (using AES 128) have I still effectively got AES-256 security?

My reasoning goes like this: even if the AES-128 encryption on the TLS link was broken by Eve then all she would get is the AES-256 encrypted file and she would then have to break that encryption to see the plaintext.

Of course the AES-256 key is sent to Alice over a separate channel.

Obviously, as long as the AES-128 (TLS) channel is keyed independently from the AES-256 (file encryption), the TLS encryption cannot damage the file encryption.

Let us consider what would be true if it could.  If that somehow did weaken the file encryption, this would allow this attack on an encrypted file – he could take that encrypted file, and send it through his own encrypted TLS link.  He can then use the records from that encrypted link, and exploit the weakness to attack the file encryption.

Since he can do that, any weakness that would apply to the combination would also apply to the file encryption alone.  We don't believe that there's anything wrong with the file encryption (assuming that the AES-256 key is randomly chosen), hence there isn't anything wrong with the combination.


Are there any multiparty homomorphic encryption schemes? Are there any multiparty homomorphic encryption schemes ?
Most of the literature is about two party schemes .
Is there any generalization made for n party ?

The one I'm most familiar with is the SPDZ protocol. The authors have implementing AES via SPDZ with up to 10 parties.


Do probabilistic one-way functions imply deterministic one-way functions? Suppose $f$ is a probabilistic one-way function.  Then my question is, does there exist a construction of a deterministic one-way function $g$ based on $f$?
Or is it possible that probabilistic one-way functions exist but deterministic one-way functions do not?
EDIT: Probabilistic one-way functions are defined in definition 2.2.2 here.

Let's look at the definition in the linked thesis:

Definition 2.2.2 (probabilistic one-way function). A probabilistic function, $F$ (with randomness domain $R_n$), with a corresponding deterministic verifier, $V_F$ , is called one-way with respect to a well-spread distribution, $\mathbb{X}$, if for any PPT, $A$:
$$\Pr\bigl[x \gets X_n, r \gets R_n, V_F\bigl(A(F(x, r)), F(x, r)\bigr) = 1\bigr] < \mu(n).¹$$
$F$ is called one-way if it is one-way with respect to the uniform distribution.

I will assume, since you did not specify anything about the distribution, that we are looking at the uniform distribution.
This definition is a bit problematic since it does not contain any kind of correctness guarantee for the verifier. In particular, take any function $F$ and define $V_F$ to be the constant $0$ function. According to the definition above the pair $(F,V_F)$ is one-way. Clearly this is not what was meant.
Definition 2.5.1 defines efficient verifiability, though this definition doesn't quite fit for a one-way function as defined above since it talks about an ensemble of keyed functions. However, in the same spirit, I will assume that Definition 2.2.2 meant to require the following from $F$:

Definition (Effcient Verification). A function, $F$ satisfies efficient verification if there exists a deterministic polynomial time algorithm, $V_F$, such that:
$$\forall x \in X_n, r \in R_n, V_F(x, F(x, r)) = 1.$$

If that is the case then the following holds.
Theorem Let $F : X_n \to Y_n$ be a probabilistic one-way function with randomness domain $R_n$. Then the deterministic function $G : X_n \times R_n \to Y_n$ defined as $G(x,r)=F(x,r)$ is a deterministic one-way function.
Proof. Let $A$ denote an arbitrary PPT algorithm such that $$\Pr[(x,r) \gets X_n\times R_n, G(A(G(x,r))) = G(x,r)] =\epsilon(n).$$
Note, that since the distribution over $X_n$ is uniform it holds that
\begin{align}
\epsilon(n) = &\Pr[(x,r) \gets X_n\times R_n, G(A(G(x,r))) = G(x,r)]\\
=&\Pr[x \gets X_n, r\gets R_n, G(A(G(x,r))) = G(x,r)]\\
=&\Pr[x \gets X_n, r\gets R_n, F(A(F(x,r))) = F(x,r)]
\end{align}
where the last equality follows by the definition of $G$.
Now, consider the PPT algorithm $B$ that upon input $y$, executes $(x',r')\gets A(y)$ and outputs $x'$. By the definition of efficient verifiability, for all $x,x'\in X_n$, $r',r \in R_n$ it must hold that $$F(x',r') = F(x,r) \implies V_F(x',F(x,r))=1.$$
Thus,
\begin{align}
\epsilon(n) = &\Pr[x \gets X_n, r\gets R_n, F(A(F(x,r))) = F(x,r)]\\
\leq & \Pr[x \gets X_n, r\gets R_n, V_F(B(F(x,r)),F(x,r))=1] \leq \mu(n),
\end{align}
where the last inequality follows from the assumption that $F$ is a probabilistic one-way function.
Since the above holds for arbitrary PPT $A$, the theorem statement follows. $\quad\quad\Box$

¹Where $\mu$ denotes an unspecified negligible function.


Elliptic curves with field sizes that not byte-aligned Why there are abnormal field size like 521, 571, 233, 283 bits in prime and binary fields that are defined by NIST?

There are some good answers in the comments, let me summarize and add a comment at the end.
Binary fields
For fields of the form $\mathbb{F}_{2^m}$, so field with $2^m$ elements, there are attacks which use the fact that $m$ is a composite number. So in practice you would want $m$ to be prime, and in particular not a multiple of 8. Therefore in this case you're out of luck, you can't have a "byte-aligned" field. This is what poncho mentions.
Prime fields
For fields of the form $\mathbb{F}_p$, you would want to choose a prime such that you can efficiently do field arithmetic. In other words, you want to give the prime some structure such that the modular reduction becomes easy. Examples are:

Mersenne primes, i.e. primes of the form $2^n-1$. This makes the modular reduction extremely fast. Unfortunately there don't exist many, and the smallest one which achieves a $256$-bit security level is $2^{521}-1$. This is what SEJPM remarks.
Since there are not many Mersenne prime, you want to choose something a little different. In the NIST documents, they use so-called Solinas primes. An example is the prime for P-256, which is $p=2^{256}-2^{224}+2^{192}+2^{96}-1$.
Any other structure. A commonly used one is $2^{255}-19$.

What is important, is that being "byte-aligned" is not necessarily useful. In fact, there are many implementation tricks which use the fact that it is not. Take for example $p=2^{127}-1$. Any integer mod $p$ fits in four 32-bit registers, but only needs 127 bits. There is one extra bit which is "free", and there are circumstances where you can use this bit to speed things up. This is usually what is referred to as using a "redundant representation".
A note: this is kind of an ongoing discussion, but there are arguments why primes with any kind of structure are less preferred. The reason is that the structure of the prime will in some sense be carried over the elliptic curve group. This can have downsides, for example it makes "additive scalar blinding" harder, which results in a slow-down. I'm not saying one way or the other is better, but be aware that there are different opinions on this.


How to solve high exponent attack for same message in RSA I know Håstad's broadcast attack when e = 3, but what if e = getPrime(randint(350))?

If you have $e$ ciphertexts for the same message, then the attack is the same, you just have to apply the CRT with $e$ values, then computing the $e$'th root of the resulting value might need some work.  And this is assuming that all moduli are relatively prime of course. If that's not the case, there is $i,j$ and $gcd(N_i, N_j) \neq 1$. So you can factor one of  $N_i$ or $N_j$ and decrypt the message. Lastly, depending on the size of $e$ and that of the $N_i$ you might want to investigate attacks on "small private exponents" such as Wiener's attack or from Boneh et al.


Message mapping to elliptic curve in BLS signature In the BLS signature the subgroup $G$ of elliptic curve constructed with point $P$ with prime order $q$ by $G=\langle P\rangle $. The $h(x)$ is a hash function. The point $S$  is map (image) of $h(m)$ on elliptic curve. The signature is multiplying the private key in the point $S$.
Is the point $S$, also in $G$ and a multiple of point $P$ such as $kP$?

It depends on whether the pairing is a type 1 pairing or some other type of pairing. In a type 1 pairing, $S$ is a multiple of $P$. In any other type of pairing, $S$ is not a multiple of $P$.


Can any part of AES encrypted blocks be used as PRFed value? Suppose we need a PRF whose output space is 255bit.

Then, what I can do with AES with 128-bit security is producing 2 AES blocks that are of 256-bit.

Then, I will remove the most significant bit of one block so that I have 255-bit output.

Is it secure if I remove the top-bit of the one block to make it 127-bit?

Is it secure if I remove the top-bit of the one block to make it 127-bit?

Yes truncating the output of a PRF produces a new PRF, which can be easily seen by a simple reduction. Assume you had an adversary that could break the truncated PRF, then you would forward all queries to the untruncated PRF and truncate the result (which is a perfect simulation) and output whatever your truncated adversary outputs. This constructed adversary wins whenever the truncated adversary wins.

  AES with 128-bit security is producing 2 AES blocks

This is the tricky part. To compose two PRFs - and AES is assumed to be a PRP which can be used as a PRF if you do less than ~$2^{64}$ invocations - you'll need to ensure that for all possible queries the inputs to both calls are unique. Standard ways to achieve this are to use two different, independent keys for the sub-PRFs or to prepend a unique value, e.g. a single fixed bit which is always 0 for the left and always 1 for the right one.


Irreducible polynomial in Ring-LWE In Ring-LWE polynomials are chosen from the ring $R_q=\mathbb{Z}_q[x]/(x^n+1)$, where $n$ is a power of two.

As far as I understand, to create a ring the polynomial $x^n+1$ has to be irreducible (see the page 2, second paragraph, of this paper). But if we select $q=1\pmod{2n}$ (as done in many cases for efficient NTT multiplication), the field has $n$th roots of unity and the polynomial can be factored.

As an example let's take $q=17$ and $x^4+1$ can be factored in $(x+2)(x+8)(x+9)(x+15)$. Real implementations with $q=7681$ and $n=256$ can be factored similarly.

I can't understand where I am making a mistake. Thank you for your help.

The cited paper, as well as the theorem of R-LWE in that paper only requires $f$ to be irreducible over the rationals. For this requirement one usually uses $f = x^n+1$ with $n$ a power of $2$. This polynomial is reducible modulo $q$ but it is okay for the proof to go through.

The cited paper suggested to use cyclotomic polynomial $\phi_n = 1+x+x^2+...+x^{n-1}$ with $n$ prime. This polynomial is irreducible over $Z$. For some prime $q$, it is also irreducible over $Z_q$.

Ex:
$n = 11$, $q=17$,
$\phi_n = x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1$ is irreducible mod $q$.


Is 256 a reasonable length for a Diffie-Hellman safe prime? There's a program that uses the following OpenSSL function...

DH_generate_parameters(256, 5, NULL, NULL)

...to create DH parameters which are later used for hundreds of key exchanges (and the one-time keys used to encrypt login details sent over Internet).

The manual page says 256 is prime_len in bits. How secure is this value? (I have a bad feeling.)

Also, if I'm reading http://www.keylength.com/, does this correspond to "discrete logarithm key" or "discrete logarithm group" or am I looking in the entirely wrong place?

I'm guessing whoever made the program was confused about key lengths. A 256-bit DH modulus will not give 256-bits of security. It will provide far less.

If you're reading http://www.keylength.com, the value here corresponds to the "discrete logarithm group". These days you really want a minimum of 2048 bits.