Why does orthogonal basises makes it easier to solve SVP in lattices? I've been looking through https://courses.maths.ox.ac.uk/node/view_material/12662 and it mentions that:
Some bases make SVP easier:

A “good” basis has shorter vector norms
A “good” basis has nearly orthogonal vectors

I assume the reason for shorter vector norms being helpful is that there if we use an algorithm such as LLL, we will have a better starting point and that there will be less to reduce?
However, I'm unsure exactly why nearly orthogonal basis vectors makes SVP easier. Is it only because it somehow makes it easier for algorithms such as LLL(-BKZ) to reduce the basis vectors?

Is it only because it somehow makes it easier for algorithms such as LLL(-BKZ) to reduce the basis vectors?

You have this somewhat backwards --- the point of basis reduction is to find a basis that is "shorter" and "more orthogonal", which you then use for useful applications.
Babai's nearest planes is a fairly well-known algorithm to solve an approximate form of CVP, that is defined relative to some fixed basis $B = [b_1,\dots,b_n]$ of a lattice.
If $x\in\mathbb{R}^n$, and:

$v$ is the output of Babai's nearest planes, and
$v_{opt}$ is the closest vector to $x$,

then one can prove that:
$$\lVert v-v_{opt}\rVert_2^2 \leq \frac{1}{4}\sum_{i = 1}^n \lVert b_i^*\rVert_2^2$$
where $\{b_1^*,\dots, b_n^*\}$ is the Gram-Schmidt orthogonalization of $B$.
Note that as the Gram-Schmidt orthogonalization applies solely elementary operations, one has that:
$$\det([b_1^*,\dots, b_n^*]) = \det B$$
e.g. the total product $\prod_{i=1}^n \lVert b_i^*\rVert_2 = \det B$ is kept invariant.
It should be easy to see that the error bound in Babai's nearest planes will be minimized if this "$\det B$ amount of mass" is "spread out evenly" through all of $\{b_1^*,\dots, b_n^*\}$, e.g. if the basis is short and nearly orthogonal.


Are there any Cryptography Algorithms that involve Lots of Number Theory? I am looking for a good, meaty cryptography algorithm that involves a good amount of number theory in which I can explore. I'm researching, and AES (Advanced Encryption System) seems interesting, but does not really seem to involve number theory all that much.
EDIT: Not RSA.

The Falcon digital signature algorithm is as "meaty" as one can be.

It has an NTRU-like key generation procedure and public key lattice structure;

its security is based on conjectured difficulty of lattice reduction in classical and quantum computers;

its efficiency is based on number-theoretic transformation and fast discrete normal distribution sampling;

its compactness is based on entropy coding.

Some more to be listed.


Where can I find a sample of data with a known entropy to see how well NIST SP 800-90B does on it? I'd like a sample of true random data from a source that has a known entropy.  It's not easy to even produce true random data in sufficient quantity --- much less know the entropy of the source.  For instance, my only chance at grabbing true random data is waiting for /dev/random.
I'm spinning my hard drive and using the system as hard as I can to feed the kernel with enough entropy.    Meanwhile I'm collecting data up to 1,000,000 so as to satisfy NIST SP 800-90B because I'd like to estimate the entropy of /dev/random using the state of the art in entropy estimation.  (I'm aware of various problems with NIST SP 800-90B, but I have not found anything better out there that has been received the due scrutiny from the scientific community.)
How am I spinning my system?
$ while true; do sudo find /; done

How am I collecting the data?
$ cat /dev/random >> random.bit

Why am I not collecting it quickly from /dev/urandom?  Because that does not make sense.  I'd like to estimate the entropy.  I won't get more entropy from using a PRNG to process true random data.  As far as I can tell, using a PRNG might just make it harder for the estimators.  (Any thoughts on that?)
Do you know of any sample of random data out there that has a respectful entropy estimation that I can use to see how well NIST SP 800-90B does on it?  Is there any work done that states the entropy of Linux's /dev/random?

The question really asks for a sample of data from a source with a known entropy rate.

I suggest starting with the simplest: sources with zero entropy rate. Examples from which the first megabytes can be readily obtained:

a source producing only bytes at zero.
a source cycling over the 256 bytes incrementally.
a source consisting of the SHA-256 hashes of bytestrings of increasing length, in lexicographic order.
/dev/random or /dev/urandom modified to replace the input of their built-in PRNG with zeroes.
a source producing the bytes of $\pi$ (e.g. using Bellard's method).

NIST SP 800-90B tests won't help distinguish the last three from a source with some entropy. That illustrates these (or similar) tests can't reliably detect even a total lack of entropy, unless some hypothesis is made on the nature of the source.

We can use a lightly conditioned source. It's easy to make one from a microphone in front of something emitting noise (a fan will do), sampled by an ADC (sound input of a PC will do), and the bytes from some number of samples fed thru some light conditioning (like: group $n$ 16-bit samples and output the sum modulo 256 of the $2n$ bytes). That's a better fit for what NIST SP 800-90 is designed to work on. It'll be interesting to see how the gain of the microphone preamplifier, the position of the microphone, and parameter $n$, all influence the results. This source doesn't have a known entropy rate, though.

We can manufacture a source with biased but (presumably) independent bytes and a known biased distribution leading to (at most) a certainly known entropy. One way is to take /dev/urandom (or any source which output can't be discerned from that of a perfect true random source), group bytes by two to form an integer in $[0\ldots2^{16})$, and output the high-order byte of that unless the integer is less than $k$, for some parameter $k\in[0\ldots2^8]$. This leads to a source with byte zero having probability $(2^8-k)/(2^{16}-k)$, and the others $2^8/(2^{16}-k)$. Entropy in bit/byte is easy to compute as a function of $k$, and goes (for $k$ up to $100$):


Why crypto hash functions must be collision resistant and how to find resistant? Why cryptographic hash functions must be collision-free and is there any methods to evaluate whether a function is not resistant to collision?

Thanks,

If a hash function is not collision-resistant (there is no such thing as collision-free in hash functions because their output has a fixed length) then an adversary can break the function with little effort. More formally (but still quite informally):

You have a set $X$ of possible inputs. For each input $x \in X$ the hash function $F$ will output $h=F(x)$. Note that there are more than one $x$ that will give the same $h$ as a result, and the set of all possible results of $F$ is finite, unlike $X$. The function's job is to make it hard for the attacker to find any $x'$ so that $F(x') =  F(x) = h$.

Edit: I also found this question which is relevant to this one


MPC protocols for high school kids I was explaining MPC to a high school student. He was excited and asked me for some examples. The only ones that I could think of are by using garbled circuits. Are there some simple MPC protocols for operations such as addition, multiplication, exponentiation, max, min that I could easily explain to an high school student?

Edit: I got good responses for addition and average operations. Are there any simple protocols for other operations as well?

Here's a simple example for addition which can be extended to other operations as well.

Suppose there $X$ number of children in a classroom and everyone has a score ranging from 0 to 100. We want to calculate the average of the scores of all students without the teacher or the other students knowing what their classmates have scored.

Here's how we can achieve this.

Step 1 :

Make them each right down the score that they have got on a piece of paper and make sure no one is colluding. This only works if everyone does it honestly.

Step 2:

Tell each student to select $X$ numbers and write them down preferably on small bits of paper since there are $X$ number of students such that these numbers will add up to the score they want to keep secret. The range can be from $-∞$ to $+∞$.

Step 3 :
Tell each student to distribute $ X-1$ bits to every other student so that each students ends up with $X$ bits in the end.

Step 4 : Now that each student has $X$ bits of paper , tell them to add up all numbers they have in front of them and write the value they got on the board.

Step 5: Add all these numbers and you will get average of the scores of each student.

You could calculate the average without anyone knowing what their score was.

You can cross verify by taking the average of the actual scores.


Strength of Sha512Ctr PRNG What is the cryptographic strength of sha512ctr when I simply concatenate a counter and 64 bytes from a cryptographic random number generator (in this case RNGCryptoServiceProvider from .net), and some additional optional data such as the user environment block?

Your proposal is more or less what NIST SP 800-90A describes as "Hash_DRBG". From a pure cryptographic point of view, there's nothing bad with it. A few remarks can be made from a more engineering standpoint:

It's not very fast. SHA-512 is a reasonably fast hash function on 64-bit architectures, but that statement is about the amount of input data that SHA-512 can absorb. Each SHA-512 instance processes input data as blocks of 128 bytes, but outputs only 64 bytes. One can hope for, possibly, about 150 MB/s of output on a recent x86 CPU. By comparison, AES/CTR (with the dedicated opcodes) will go at 5 GB/s. Moreover, on 32-bit architectures, especially small ones (microcontrollers), SHA-512 is terrible. AES/CTR (on systems with a hardware implementation of AES) and ChaCha20 (on all others) will be a better bargain.
If you concatenate a counter, a 64-byte seed, and "additional data", and the total length exceeds 111 bytes, then each SHA-512 instance will require the processing of several blocks (111, not 128, because of the SHA-512 internal padding), and performance will further decrease. It would be better to first process the seed and the additional data into an aggregate 64-byte value (e.g. with a SHA-512 call), and use that aggregate value along with the counter into SHA-512/CTR.
"Userland" PRNG have some potential security issues. For instance, a call to fork() (on a Unix-like system) will duplicate the internal state; the parent and the child will then produce the same pseudorandom output from their shared state. A similar point can be made about virtual machine snapshots. Generous use of an uncloneable random source can help mitigate such issues (e.g. RDRAND on recent x86 CPU). Going through the kernel (/dev/urandom or equivalent) can help with that: the kernel is resilient to cloning by fork(), and it has direct access to the hardware, allowing to use random sources such as RDRAND, which are tricky to invoke from .NET code.
Assuming an attack that can compromise the internal state, the attacker will learn enough to not only predict the next pseudorandom bytes, but also previously generated output, by "rewinding" the counter. If you do not use fresh randomness, a compromise of future output, under that scenario, is unavoidable; however, forward secrecy should be maintained: even after full memory compromise, past generator output should be forever out of reach. Such a property can be obtained by "ratcheting" (in simple words, replacing the current seed with a one-way hash of it). If you look at NIST SP 800-90A, this is what happens at the end of the Hash_DRBG_Generate process, after producing the requested output.


Building cryptographic primitives using additive maps? Suppose we have a one-way function F(x) that exhibits the property F(a + b) = F(a) + F(b). Such a function could be used as a cryptographic primitive, no?

Yes, take an elliptic curve group $E$ with a point $P$ of prime order $p$ such that the discrete logarithm problem is hard. Then we have a cyclic subgroup $\langle P\rangle$ of $E$ generated by $P$ of order $p$.

Define the map $F: \mathbb{Z}_p \rightarrow \langle P\rangle$ as $F(a):=a\cdot P$ (scalar multiplication) which gives you such a linear map (homomorphism and actually it is an isomorphism) as you have that $F(a+b)=F(a)+F(b)$.  Apparently, if the discrete logarithm problem is hard, this map is one-way. The first addition is in $\mathbb{Z}_p$ and the second addition is the "abstract" addition in the elliptic curve group.

This fact is used in various constructions when instantiating DL based crypto with elliptic curves, such as homomorphic commitments, making ElGamal additively homomorphic (aka exponential ElGamal) etc.


KDF and number of iterations for GPG I gather, from reading the GPG manual, that symmetric encryption based on a password uses one of a variety of Key Derivation Functions (KDF). Although not explicitly mentioned I assume that PBKDF2 is the default as the other options appear to be legacy algorithms from the PGP standard.

However I can't find any information on the number of iterations that the KDF does by default of whether there is a way to change that value manually. I want to know this because it would have an impact on the required complexity for the password (e.g. number of words generated using the diceware method) to achieve a given level of security.

Use gpg --s2k-mode 3 --s2k-count N, where N is the number of iterations you want to use.  The manual page says the default is 65536, and you can use any number between 1024 and 65011712.

If you like to tweak the defaults, I suggest making this number as large as you can bear it, without introducing noticeable slowdown (e.g., ideal would be to make the passphrase mangling process take about a second or so).

See also this answer to a different question, and the following questions/answers on IT Security.StackExchange:

What is purpose of --s2k-* GnuPG options?
gpg --perfect-code
an answer to "gpg encryption security"
an answer to "Good file encryption tools"
Do OpenPGP/GnuPG apply slow hash to password when encrypting/decrypting key?


How does `d-KCA` help secure the zcash protocol? I have been going back and forth between part 2 and part 4 of the Explaining SNARKs series.

In part 2, it is claimed that Bob has an idea about the polynomial and want to test whether Alice knows it by sending her $(g, s.g, ..., s^d.g)$ and checking the answer $P(s).g$.
In part 4, it is claimed that now Alice return 2 polynomials $a' = P(s).g$  and $b'=\alpha P(s).g$ computed from $(g, s.g, ..., s^d.g)$ and $(\alpha.g,\alpha s.g, ..., \alpha s^d.g)$. But now Bob only check that $b'=\alpha.a'$ and that if it is the case then Alice knows with high probability $(c_0,...,c_d)$.

My question:
What is the use of the d-KCA knowing that:

If Bob knows $P$ and the probability that Alice answers correctly without using P is very low, then the verifiability is ensured already.
If in the d-KCA, Alice sends back $a'=\beta .g$ and $b'=\beta \alpha .g$, we have $b'=\alpha . a'$. So if Bob only check that equality he can be fooled.

I am really wondering what I am missing...

Two points:

Bob does not know $P$ which is partly the point of the protocol.
Alice could respond with the $\alpha$-pair $(a',b') = (\beta g, \alpha\beta g)$, there is nothing wrong with that. This implies that her coefficients are $c_0=\beta, c_i=0$ for $i>1$.

However, this will only do her any good if her coefficients $(c_0, \cdots, c_d)$ actually present a solution to the QAP.


Crack SHA1 hash code Given a set of SHA1 hash code, if we knew a portion of the plaintext for each particular hash code, and also the remaining portion of the plaintext is a constant value for each hash code.
Is it possible for us to recover what is the constant value?

Yes, but unless there is a significant break through in the crypto-analysis of SHA-1, the only way to retrieve the constant value is by brute forcing it. In other words, trying all the values, calculating the SHA-1 over the plaintext and the constant and comparing it with the given hash value.


Has the ECDH protocol been designed just for key exchange or is it widely used for key exchange? As far as my understanding of the ECDH goes, after systems are encrypted using ECDH protocol, any data that comes out of the first system will be encrypted and can only be decrypted at the receiving end. Literature says that ECDH is used for the purpose of key exchange(when data is encrypted using symmetric encryption methods like AES) but can I not communicate application data via ECDH (regardless of whether or not I'm further encrypting the data at application layer using something like AES-CTR or DES) ?
PS: I'm trying to establish encrypted communication between 2 BLE devices.

As far as my understanding of the ECDH goes, after systems are encrypted using ECDH protocol

Stop right here, you cannot encrypt data using ECDH. ECDH is an algorithm, not a full fledged transport protocol (or protocol for securing data at rest, for that matter).

Literature says that ECDH is used for the purpose of key exchange(when data is encrypted using symmetric encryption methods like AES) but can I not communicate application data via ECDH

That's correct. The only thing that is required for ECDH is the public key, and - in specific situations - a nonce. The public key of the sender / receiver is send to the other party for key agreement. Anything else is outside of the ECDH algorithm, and you cannot use the public key to encrypt data directly.

PS: I'm trying to establish encrypted communication between 2 BLE devices.

Right, so you need to follow the Bluetooth protocols and ask us crypto specific questions about it, or ask StackOverflow when it comes to implementation specific questions. The IT security site can be asked about things like key management and practical security of the protocol.
If you want to encrypt just a specific message you may need to look at (EC)IES which uses ECDH for message based encryption. Beware that the scheme requires a trusted, static public key though (otherwise you obviously don't know who can decrypt, and you're therefore susceptible to MitM attacks).


Does QUIC use a 96-bit MAC tag? If so, what are the implications? Does QUIC use a 96-bit MAC tag?  If so, what are the implications regarding forgery of messages?

One can argue about whether security for adversaries running in time $2^{96}$ is feasible or not, and the current standard is to require 128-bit security (or at least 112). However, an attack requiring sending in the range of $2^{90}$ messages to attempt to forge is way beyond feasible. The success probability of an attacker shouldn't exceed something reasonable, but what is reasonable is also subjective. NIST recommends that for block cipher modes of operation, the probability of a breach shouldn't exceed $2^{-32}$. For that reason, with a random IV, you can only use CTR or GCM to encrypt $2^{32}$ different messages (since the IV is of length 96 and you have a birthday problem). For MAC tags, taking 96 bits is more than enough...


Minimum Nonlinearity of boolean function I have studied many literature on boolean functions. The nonlinearity of a boolean function is defined as min of hamming distance of the function from all the linear functions in the set. There is also formulas for calculating nonlinerity of boolean function  in terms of no of inputs (n). Now i have following two doubts

Is the nonlinearity of all boolean functions in the same boolean space(say V5) is same or different for different functions ? IF different then how to calculate nonlinearity of each one seperatly ?
How to calculate minimum nonlinearity of a given boolean function in a given boolean space say(V5).

You can give a boolean function by it's truth table.
For example if $f(x, y, z) = x + z$ you have the following truth table:

  x   y   z   f(x, y, z) = x + z
 ----------------------
  0   0   0     0
  0   0   1     1
  0   1   0     0
  0   1   1     1
  1   0   0     1
  1   0   1     0
  1   1   0     1
  1   1   1     0

just enumerating the last columns gives you $(0, 1, 0, 1, 1, 0, 1, 0)$. This $f$ is by its definition clearly a linear function. If you want to enumerate all linear functions you can look at the Hadamard matrix and Hadamard transform.

To calculate the linearity of a boolean function $g$ as explained in this question you take the minimum Hamming distance between the output vector of $g$ and all linear functions.

So if your function would for example be $g = (1, 0, 0, 0, 1, 1, 0, 1)$ the Hamming distance to $f$ would be.

g: 1 0 0 0 1 1 0 1
f: 0 1 0 1 1 0 1 0
------------------
   1 1 0 1 0 1 1 1 => HD 6 => non-linearity at most 6

In fact if you where to try all linear functions you would find $h = (0, 0, 0, 0, 1, 1, 1, 1)$ with

g: 1 0 0 0 1 1 0 1
h: 0 0 0 0 1 1 1 1
------------------
   1 0 0 0 0 0 1 0 => HD 2

and this is the lowest value so the non-linearity of $g$ is 2.

I hope this answers your second question.

Now we can answer your first question simply by finding examples.
Here are two 4-bit functions with different non-linearity:

[1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]
Non-linearity here is 2. It cannot be more than 2 because the middle two bits are swapped from

[1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
which is clearly linear (depends only on highest value bit). And it cannot be less than 2 because the function is non-linear and balanced.
[1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0] has non-linearity 4.

This, I hope answers your first questions negatively. Not all functions have the same non-linearity.


Hiding identifying data while allowing matching? I do research with people about their illegal drug use, and for one project I'm doing surveys with them when they visit a needle exchange.  So over time the same people get repeatedly surveyed as they visit the exchange many times over.

In order to link together multiple surveys from the same person across time (because we want to track things like engagement with drug treatment and changes in level of drug use), I ask them to give me some information that they can remember from visit to visit but which would at least moderately limit the ability of someone to identify them from it: the first two letters of their mother's first name, the day of the month on which they were born,and their gender.  E.g. a woman (F) born on [month]/20/[year] whose mother's name is Jane would get the code JA20F.

So every survey gets this code as a unique identifier, and you can link multiple surveys done by the same person without having to record blatantly identifying info like names and dates of birth (or ask a street-based drug user, potentially with mental health problems as well, to remember a unique study ID from visit to visit).  Not perfect from a security point of view, and not unique if you have thousands of people, but when the data is being entered on a single laptop with full disk encryption and all study files are stored encrypted and you have a Federal Certificate of Confidentiality (protects research data on illegal activity against subpoena), and there's only about a thousand people using the service, probably good enough.

But storing that identifier still bothers me.  I'd really like to do something to it at the point of data entry so it can't be 'reversed' back to the potentially identifying day of birth, gender, and first two letters of mother's first name.  My initial thought was to hash the unique identifier before storing it, which again is better than nothing but anyone who knows the format of the unique identifier could easily use a rainbow table approach to unmask it.  As I understand salting, self-salting would mean the hash was different each time for the same individual, so I'd lose the ability to link surveys done by the same person.  And using a single salt would just make the salt the vulnerable piece of data.

Does anyone have any ideas (or well established techniques I'm just ignorant of) for one-way hashing a string which a) is not vulnerable to rainbow tables, but b) produces the same output every time from the same input?

Any transformation of the identifier, including those in the question, is bound to have at least one drawback: after a transformation of cryptographic quality, it will be next to impossible to re-agregate identifiers that refer to the same person but have been slightly garbled (perhaps because there are two common spelling of the mother's name).

Even ignoring that, I do not see a convenient and bulletproof solution, basically because you start from a very short identifier.

One improvement would be to encrypt the identifier using a secret key, with format-preserving encryption, so that the encrypted result remains short, compatible with existing practice, and the encryption demonstrably can't introduce more collisions than there is originally. A most serious problem then is protecting the secret key, and limiting its use (which is necessary since it is enough to encipher a few chosen inputs to break the system).

Better than nothing is making this key passphrase-protected (like a PGP key is), with the passphrase entered on the laptop by the legitimate user at the beginning of data-collection activities. Standard key stretching techniques can make that quite safe against passphrase search, while still robustly detecting an accidental mis-keying. While we are at it, all data collected should be kept encrypted with standard techniques (using a different key, possibly protected by the same passphrase for convenience).

Even better is moving the key in a Smart Card, protected by user PIN with consecutive errors counter. Next step (recommendable, and quite easy even with standard Smart Cards) if moving at least a building block of the format-preserving encryption into the Smart Card itself, so that the key never leaves the Smart Card (said building block could be AES or a MAC, and the corresponding key, used in the round function of a Feistel cipher). Ultimately, the sensitive data could be held in the Smart Card itself and inaccessible without the PIN.

Beware however that nothing in the above can resit an active compromise of the laptop (e.g. key logger) performed before sensitive data is entered.


Signing a GPG Public Key I am trying to manually create a GPG Public Key (see here). I am able to generate a GPG Public Key with a correct hash, but fail to RSA-sign that hash in a way that is accepted by the GPG CLI. For the GPG Public Key I have created see here.
To sign the hash I am using a private key on a PKCS#11 HSM. The HSM supports various signing mechanisms. I have tried signing with RSA-PKCS-PSS (with hash algorithm SHA512 and mask generation function MGF1-SHA512), SHA512-RSA-PKCS, and SHA512-RSA-PKCS-PSS, but neither produces a signature that the import command of the GPG CLI accepts. I suppose the GPG CLI expects a different padding.
Unfortunately, RFC 4880 does not explicitely cover GPG Public Key signature padding, but only specifies that EME-PKCS1-v1_5 and EMSA-PKCS1-v1_5 functions are used for PKCS#1 encoding. A quick search through the GPG source code shows that both PKCS#1 v1.5 and PSS are used at some points.
Does anybody know what padding exactly is supported in the import command of the GPG CLI?

You're barking up the wrong tree.
To answer the stated question, OpenPGP doesn't support or use RSA-PSS, at least not yet. For RSA signature, EMSA-PKCS1-v1_5 from PKCS1, referenced as rfc3447 (which republished PKCS1v2.1) and actually copied for your convenience into rfc4880 13.1.3 (though without the precomputed DigestInfo encodings), is the hash and padding together. Other PGP signature algorithms don't use padding (or only trivially). And it's not just the CLI; PGP protocols and formats are the same for all modes of GPG.
But your padding is fine; it's the hash that's wrong. In your posted message-and-decode, the signature given is a valid v1_5 signature for the SHA512 hash
89 6e e3 83 f0 24 e7 ba 4e 12 87 36 bd dd 55 fb 1d 8e 20 b0 f2 72 c6 3c e3 53 29 23 47 41 28 c9 b7 f4 51 ea 39 cd 1c ae ee 29 c2 e4 d4 13 fb 05 dd 89 bd 6b f7 20 76 63 95 f5 f8 b7 79 b2 d1 1b
-- or to be exact, since the v1_5 signature scheme includes hashing, it is the signature for data with that SHA512 hash. However, as shown in your previous Q&A, the correct hash for this publickey is 2f 9b ad fd 89 90 e9 34 f3 15 c6 9c c5 8e 45 12 47 29 fe ab e6 18 a2 e2 71 fb bf e1 9e 20 10 8a 86 ea d9 dd 5b 87 58 87 45 85 98 2a 68 14 e9 e2 ef 9e b6 07 12 1d 9b 7c 15 8f 58 79 c2 92 c5 e9. The former value is in fact the SHA512 hash of the latter, aka the hash of the hash. Probably you have given the hash value as data to a signing mechanism that both hashes and signs its input -- as v1_5 signature implementations usually do, so they can ensure the same hash is applied to the data as is encoded in the DigestInfo. In particular a mechanism named 'SHA512-RSA-PKCS' almost certainly applies the hash (SHA512) AND pads and modexps the result.
To fix your actual problem, you should give the data not the hash as input to the signing mechanism, and not change anything relating to padding in any way.


How did "Secure Voice" work on the old Air Force One's? I recently visited the "Museum of Flight" where they have an old SAM 970, previously known as "Air Force One".

Inside there is a comm station with many buttons designated "Secure Voice", as can be seen on the lower row of controls in the attached picture. The plaque says "During the Johnson and Nixon eras, "Air Force One" was equipped with a radiophone on which secret voice messages could be scrambled and sent. It rarely functioned properly and was removed to save weight." Therefore I suspect that the buttons and controls in question is not related to this radiophone.

Does anybody know what kind of Secure Voice communications they used these controls for, and how these works?

As a bonus, if the radiophone that rarely worked could be explained as well, I'd really appreciate it :)

They used a scrambler[wikipedia] (not “encryption“ and definitely not a “One-Time-Pad” as some think [comment] [comment]) to transmit messages via a SatCom (read: military satellite) system. The scrambler they used back then was (let's just call it) “non-optimal” and has been replaced with an enhanced system. That's also what the sign is hinting at, among other things.

Scramblers and jam resisting implementations are only distantly related to cryptography, but somewhat comparable to how synchronizable, bit-wise stream ciphers and/or lightweight hash algorithms work. Yet, the goal of scramblers is different from a security perspective.

Scramblers use a secret spreading sequence or secret hop sequence, or some other information that must be kept secret from a potential jammer and/or listener. This mostly (and certainly back then) assumed sender and receiver to have a shared secret… somewhat like a seed for an (CS)PRNG. Back in the days, those shared secrets were stored analogue, while meanwhile things have (in most cases) been digitalized.

As a matter a fact: at the time of writing this, there is only one scrambling system for achieving jam resistance without any shared secret: BBC coding. BBC coding is able to provide unkeyed jam resistance. For a quick read on the subject, you can check (for example) the MilCom2012 paper The Glowworm hash: Increased Speed and Security for BBC Unkeyed Jam Resistance (PDF).

I'll skip the “Bonus” about “the radiophone that rarely worked“ as that would push this Q&A too much into the off-topic area and will quickly become too broad. Instead, I'll add an aside…

Aside: In case you'ld like to dive into the current state of scrambling and jam resistance, you could take a look at a related meta question I once asked, which happens to contain a whole list of related papers. Using your favorite search engine, you'll be able to find the related papers as PDFs.


Is PyCryptodome's export_key with passphrase secure? When exporting a private key with PyCryptodome, DER format, PKCS#8 and a suitably strong passphrase, is the resulting exported key secure enough to place somewhere that you would not normally want sensitive information stored, such as a database or on a hard drive?
From PyCryptodome.readthedocs.io:

For ‘DER’, the PBKDF2WithHMAC-SHA1AndDES-EDE3-CBC scheme is used. The
following operations are performed:

A 16 byte Triple DES key is derived from the passphrase using
Crypto.Protocol.KDF.PBKDF2() with 8 bytes salt, and 1 000 iterations
of Crypto.Hash.HMAC.
The private key is encrypted using CBC.
The encrypted key is encoded according to PKCS#8.

Well, it's sort of secure. There are no serious issues, but there are a few problems:

3DES - A cipher composed of three rounds of the DES cipher. DES has a key size much too low at only 56 bits, but running it three times (first in the encryption direction, then the decryption direction, then the encryption again, hence the acronym "EDE") brings the key size up to 168 bits, although the effective keyspace is only 112 bits due to a meet-in-the-middle attack that applies to this type of construction. Although it's deprecated, 3DES is not considered breakable like DES. It's just that there are faster and more secure alternatives.
The other issue with 3DES is the fact that it has a small block size of 64 bits. This causes severe security issues to open up as more data is encrypted under a single key. Because a private key is small (the size is measured in mere kilobytes), the small block size is a non-issue.

Small salt - The salt size is too small at only 8 bytes (64 bits). This is unlikely to be a serious issue in practice. An attacker would need to build an incredibly large rainbow table to attack a 64-bit salt. Building a rainbow table for hashes with a random salt was possible back in the days when a 12-bit salt was used, but not today with a 64-bit salt.  I'd recommend 128 bits though.

Low PBKDF2 iterations - PBKDF2 is a function that hashes a password slowly, forcing anyone trying to crack the hash to use the same slow function. 1000 iterations of PBKDF2 is not much. It's far better than using a hash of the password directly, but it's not ideal. It would be better to use at least 100,000 iterations, or even to switch to a superior memory-hard KDF like Argon2.

Overall I'd say it's likely secure enough, but it's not ideal and isn't something I would use if I could help it.


Parallel Pollard's Rho: Number of distinguished points When using the parallel version of Pollard's Rho algorithm for discrete logs, each processor performs its own random walk to find distinguished points, and reports the starting point and the distinguished point to the server. If two processors report the same distinguished point, then the server can re-do the random walk and find where the collision occurred and solve the discrete logarithm.

The average number of steps each processor must perform before finding a distinguished point depends on the number of distinguished bits. On average it is $2^d$ where $d$ is the number of distinguished bits.

If the attack is being run on systems with lots of slow processors (e.g. 100,000 GPUs each with thousands of threads), then its possible to come up with the required number of distinguished points without each processor coming close to $2^d$ iterations.

Suppose we have a 128-bit discrete log problem. We need ~$2^{64}$ group elements to solve it. We can do this with $2^{32}$ distinguished points with $32$ distinguished bits.

Suppose we are using a 50 billion processors that each do 20 steps per second (generate a trillion points per second).

So that is ~$2^{40} (\dfrac{1}{2^{32}})$ = $256$ distinguished points per second.

It will take about 194 days to find $2^{32}$ distinguished points.

But if each processor only walks $20$ steps per second, then each processor could only have walked at most $335,232,000$ steps, far less than the expected $2^{32}$.

That means each distinguished point reported to the server represents at most $369,782,000$ steps taken. So the total number of points between the starting points and distinguished points is far less than $2^{64}$

Question:

Does this mean it will require far more than $2^{32}$ distinguished points?

I think it will because the total number of points reported isn't enough to make a collision probable. We could say that each distinguished point represents $2^{32}$ points, but since the walks were so short, its more likely that any collision was the result of one random walk stepping into the starting point of another random walk, in which case the collision is useless (they call this a "Robin Hood" in the literature).

I think Parallel Pollards Rho favors a few very fast processors over many slow processors. Or many slow processors with short walks (fewer distinguished bits, more distinguished points) and lots of storage.

The expected number of points $\sqrt(\frac{n\cdot \pi}{2})$ is calculated via the birthday paradox and it applies to the number of calculated (not just distinguished/reported) points. As you said, each distinguished point represents $2^{32}$ points. Even if a collision is not reported (because it is not on a distinguished point), the two walks which collided will continue on the same path and eventually find the same distinguished point. That is where the ...$+\frac{1}{\theta}$ comes from in the complexity in the original Oorschot et Wiener paper. $\theta$ is the probability that a point is distinguished. So you have, the number of computations until a collision occurs, + the number of computations before that collision is reported i.e. before you reach the next distinguished point.

In practice, I haven't had a problem with Robin hoods, but Oorschot et Wiener seem to suggest that to avoid Robin hoods you need to take $\theta$  small enough that trails are long.


Is RC4 +XOR secure for small data? I need to encrypt transmission between my device (with AVR processor) and base. I create packet data - it will be encrypted into string:

PacketData {
  int packetN;
  string data;
  CRC16 checksum;
  string nextKey;
}

As you can see, key will be changing after each packet.

First, I tried to use XOR encryption, but I forgot that if attacker know plaintext, all encryption will be without sense.

Now, I have an idea - first, use RC4 on data with key, and XOR result with same key. I see bad side of this solution - key will be same for both operations, and I want key length ~64 bits. Handshake will be written on device (8 characters), and connection will be made when base sends encrypted packet with handshake. Also, data size will be usually between 4 and 32 bytes, sometimes more.

Is this encryption give me sufficient safety? After reading about RC4 in WPA, I see that is problem in WPA implementation. Maybe I should use (when connected) two keys, for RC4 and XOR, both sended in encrypted packet?

Please, tell me what do you think about it. It must be light solution (because tiny processor) so I can't use AES. My solution is right?

Disclaimer: the only reason to go this way is if you have an 8 bit CPU. Otherwise, select AES.

Sending nextKey in the data packet is silly. What you want is key + iv. Look up the CipherSaber 2 variant of RC4. This covers the attack used on WEP just fine. Bear in mind though this wants a good RNG (probably hardware RNG) and 10 bytes of iv. Unless you can store the iv counter, there's no good way to reduce it. There are other possible attacks on RC4 though, the most worrying is the one that can be used against 1 billion messages to reveal the first 128 bytes of message. A plausible workaround is simply eating the first 256 bytes off the stream (don't bother sending just discard).

Your key length here won't be 64 bits though. That's too small. You need at least 128 bits.

We do have to keep in mind that RC4 and all its variants are weakening. There is simply no good explanation for the fact it is as strong as it is today. It really should not be. The next attack might doom it.

EDIT: Answer no longer good. A recently published attack against RC4 is no longer mitigated by the CS2 variant. I was not expecting this.


How do two parties put together the AUTH data in the SKEME protocol? SKEME is a Key Exchange protocol used in the Internet Key Exchange (IKE).  It contains three phases:  SHARE, EXCH, and AUTH -- these are defined in Section 3.2 of the linked SKEME document.

I am trying to understand a confusing part (to me at least) about the AUTH phase of SKEME. There is a bit of background to cover before I can get to my actual question, please bear with me...

SHARE

  Phase SHARE is intended to establish a key $K_0$
  between $A$ and $B$

  In SHARE the parties exchange "half-keys" encrypted
  under each other's public key and then combine
  the half-keys via a hash function to produce $K_0$

But this whole phase is skipped if the two parties instead use a Pre-Shared-Key instead of Public Keys. This is defined here:

  3.3.2 Pre-shared key and PFS

  In this mode, the protocol assumes that the parties already share a
  secret key, and that they use this key in order to derive a new and
  fresh key

  In this mode of SKEME the SHARE phase can be skipped and the
  pre-shared key used as $K_0$

This is the mode of SKEME that I am concerned with, so we take it at face value that $A$ and $B$ have Pre-Shared-Key $K_0$

EXCH

  The next phase, EXCH, is used to exchange Diffie-Hellman exponents.
  Notice that this phase is independent of SHARE.

  EXCH:
  $A$ --> $B$: $g^x$ $mod$ $p$
  $B$ --> $A$: $g^y$ $mod$ $p$

Standard Diffie-Hellman exchange, nothing too complicated here. Both parties now have the DH shared secret.

AUTH

  The authentication of this Diffie-Hellman exchange is accomplished in
  the following phase, AUTH, which uses the shared key $K_0$ from SHARE to
  authenticate the Diffie-Hellman exponents.

  AUTH:
  $A$ --> $B$: $F_{K_0}$ ($g^y$; $g^x$; $id_A$; $id_B$)
  $B$ --> $A$: $F_{K_0}$ ($g^x$; $g^y$; $id_B$; $id_A$)

  Notice that the key $K_0$ shared in the SHARE phase can be known only to
  A and B ...
  The inclusion of $g^x$ in the first message serves to authenticate (to $B$)
  that $g^x$ came from $A$; the value $g^y$ in the same message is used to prove
  to $B$ the freshness of this message (assuming $g^y$ was freshly chosen by
  $B$);

And this is where I get confused.

I know $A$ put calculated $g^x$, and can understand how $A$ knows this value. But from what I understand, $B$ calculated $g^y$, and only shared $g^y$ $mod$ $p$.

Therefore, how does $A$ know $g^y$ to include in the formula above? Similarly, how does $B$ know $g^x$ to calculate the same $F_{K_0}$ to validate the value provided by $A$?

how does $A$ know $g^y$ to include in the formula above?

Actually, what they mean here is, in fact, $g^y \bmod p$; that is, the value that $A$ received.  It wouldn't work to insert the literal values $g^x$ and $g^y$; apart from the fact that $A$ doesn't know the second one, there's also the practical difficulty that since $x$ and $y$ are (perhaps) 256 bit random values, the bit representation of $g^x$ and $g^y$ may consist of circa $2^{256}$ bits in length; rather too long to process.

In general, when the group we're working in is understood, we often write $g^y$, with the fact that we're talking about operations in the group, and not as an integer, being implied.


How is QKD (Quantum Key Distribution) advantageous over McEliece/AES? I don't understand the popularity of the idea of QKD (often coupled with OTP). From what I can tell, a quantum-safe key exchange algorithm like McEliece has just as much security while operating over current networks, through repeaters, and not requiring single-photon emitters. Combining this with AES seems convenient and practical.

Why would one ever choose QKD over McEliece?

The only reason I can discern is that there is some possibility that a yet-to-be-discovered algorithm may weaken McEliece or AES.

Because it's the Holy Grail of cryptography.
To be specific, it's not unbreakable as the layman's literature suggests. It's that a quantum transmission of key material cannot be intercepted without the sending/receiving parties noticing. It is the Observer Effect in physics and a fundamental part of the Universes. Knowing that you're being spied upon in many ways gives you the advantage.
And if you can securely transmit a lot of key material, you can then use one time pad (OTP) techniques for the encryption.  And OTPs are provably secure via information theory. McEliece/AES being limited key length based ciphers are not.  Just because the academic community can't break McEliece or AES, doesn't mean that they haven't already been by state actors, or will be tomorrow by Alexander Verykleverkov in his university dorm room. Perhaps Shor's 3rd improved algorithm might work against McEliece. The point I'm labouring is that you can prove photon interception/OTP security now, but not McEliece/AES. All we have is an absence of evidence for them.

The only reason I can discern is that there is some possibility that a yet-to-be-discovered algorithm may weaken McEliece or AES.

You've answered your own question :-)  Israel can keep defence-related documents sealed for 70 years.  The UK had 50. Their transmission may have been intercepted or copied and stored. You cannot guarantee that they won't be teaching McEliece/AES breaking in high schools by 2091.
That's why there is a market for QKDNs. See all the interest in this older answer, and ponder the quotation at it's end. It's incredibly alluring, and if you want one, buy one of these:-

It's a node for commercial QKDNs. Cerberis from ID Quantique.


Dependent keys on Encrypt Then MAC It is generally bad form to reuse the same key for encryption and authentication in an "encrypt then MAC" scheme. For example, in the naive encrypt then MAC scheme, we use a randomized CBC block cipher and MAC the cipher text but an attacker can pass in all 0 messages to violate the CPA security condition.

However, what if we used dependent but not the same keys?

For example, if the key used for MAC is of the form $k' = k \oplus V$ for some fixed value $V$. Is this still bad form, i.e. would there be an encrypt then MAC scheme which is insecure?

This is indeed best way to do it. As the final $(cbc\oplus cipher)$ encrypted by a different key even if we pass 0 messages it do not reveal any information. Previously passing on 0 messages gave encrypted cbc (which is later $\oplus$ed encrypted ($cbc\oplus cipher$) to reveal information) now as the key used is different even if the encrypted cbc (on passing 0 messages) is known it wont reveal information.

Hope this helps.


Adversarial Indistinguishability I am trying to devise an encryption scheme such that an adversary can win the following game with probability at most $1/2 + \epsilon$.

Adversary gives challenger two plaintext messages $m_1$ and $m_0$
Challenger chooses one the two at random and encrypts it and gives adversary the cipher
Adversary determines which of the two messages was chosen.

The key space has to be smaller than the message space.

Any ideas?

An adversary can easily win this game with $\epsilon = 0.5$ when the scheme under examination is any block cipher in ECB mode.

Simply set $m_0$ and $m_1$ to the same block value, $q$. This guarantees that you'll get the encryption of $q$ back, which we'll call $r$.

Then you can distinguish between $q$ and some other block value with probability $1$ on subsequent trial by checking whether $r$ is returned or not.


Is there a way to generate sound one-time pads out of public information? Is there a way to 'mangle' a public data-source (for example, the current date  in YYYYMMDD or the top New York Times headline) to form a one-time pad that will sufficiently hide the pad's source?
What other issues would such a scheme be running into?

Disclaimer: I am not an expert cryptographer and am just interested in the matter - I do not intend to implement this cryptosystem.

Very short answer: No
Quite Short answer: No, because a scheme can only be a One-Time-Pad if the entire pad is perfectly random and secret.
Concise answer: It sounds like you're trying to build a stream cipher. The security of it really comes down to how much of the scheme you think can be kept secret. If I listen in to your wifi and hear you requesting a certain resource, then I can work out what your data-source was, calculate the pad myself and decrypt your data. This tends to be bad!

Full answer:
Any scheme 'like' the One-Time-Pad (OTP) breaks down into two sections: first we form a pad and second we combine the pad with the plaintext. The second of these tends to be through the xor operation (denoted $\oplus$), but this doesn't really matter for this question.

So, the first section: generating a pad. For the OTP, we assume the pad is perfectly random and secret. If so, then the scheme is perfectly secure. However, this means we somehow have to transmit a large amount of secret information to the other person before we can send them the message, which in most cases just means we pass the difficult problem of key distribution upstream.

So, how do we get around this problem? We take a small key that can be more easily distributed, and expand it with a method that everyone involved knows to form a stream cipher. This is a function that tries to expand a small key into a suitably large key stream to pad the message with, and we have some pretty tough requirements of it. In particular, we demand that the key stream appears random. That is, someone seeing even a large amount of the keystream should not be able to differentiate it from truly random data (within 'reasonable' computation effort).  If they cannot differentiate it from random data, we decide that the output ciphertext is sufficiently secure.

Before I try and pull things together, I'd like to point you to Kerckhoffs's principle.
 Basically, for any real level of security in the modern world, we require that a cryptographic algorithm should be secure even when the attacker knows everything about it except for the key. Note that 'the key' is a vague notion - one can draw the algorithm-key boundary pretty well wherever they like - but good practise says the key should be as small as possible (eg algorithm=RandomAccessMachineSimulator; key=MyCryptoAlgorithm) without compromising the security of the algorithm.

So, how does your situation work? Well, turning a large amount of not-very-random data into a small about of 'quite random' data is a question of [extracting the entropy][Note 5]. A naive way of doing it would be to simply pump all your input data through a key derivation function like PBKDF2, but I won't go into this in much detail chiefly because there's a bigger problem: What do you keep secret?
 - Keeping the entire algorithm secret: If you want to keep everything secret from an attacker, then how do you tell the person you're messaging how to decrypt it? Somehow you must privately give your ally all the required details. At this point though, why not just give them an AES key that you can then use to communicate securely?
 - The data-source is secret: This makes a bit more sense. All the 'fiddly' computer bits (eg the entropy extraction) can be exchanged insecurely (eg email), then you send them the data-source (URL?) in secret. However, (assuming that for some reason this time we can't just send a key instead) anyone listening to your HTTP requests will hear all URLs loaded, and by testing each one of them will find your key very efficiently.

[Note 5] - Is there already a good description of this somewhere?


Diffie Helman key space: 128 bit primes About the Diffie-Hellman key exchange, I have a question related to the key space, as far as I know the key space is of course all the possible keys to be used, for instance, say that $p$ and $\alpha$ are the large prime and primitive root respectively so the key is $K=\alpha^{xy}\pmod{p} $ for secret $a$ and $b$. Now, according to this, I'd say that the key space is the set $\mathbb{Z}_p$, which sounds good to me.

My problem comes now, since I was just reading about new techniques on key exchange using fractal methods that make a comparison between this new method and DH, it states at some point that "The DH key space for 128 bit is limited by how many primes existed in the finite field of $\mathbb{Z}_p$, where $p$ is the largest prime that can be represented by a 128-bit value", so I got a bit confused about what it really means.

"The DH key space for 128 bit is limited by how many primes existed in the finite field of Zp, where p is the largest prime that can be represented by a 128-bit value", so I got a bit confused about what it really means.

I believe that the appropriate meaning to the quote is "I have no clue about cryptography, here are some plausible sounding buzzwords that I've heard".

No one uses (or, should use) a 128 bit prime for Diffie Hellman; the current conventional wisdom to use (at least) a 2048 bit prime with a large prime subgroup; this is often done by using a "safe prime".

Now, sometimes we perform Diffie-Hellman based on an elliptic curve, which might also be based on a prime curve.  However, even in this case, a 128 bit prime is still too small; the conventional wisdom is to use at least a circa 256 bit prime (Curve25519 comes close enough).

If the author of the fractal method isn't aware of this, well, that doesn't indicate that he knows all that much about cryptography.  That would certainly call into question anything he has to say about his fractal key exchange.

BTW: "key space" isn't a very useful way to think about DH security.  If the size of the large prime subgroup is $q$, then the "key space" size is $q$; however there are generic attacks that recover the shared secret in time $O(\sqrt{q})$, hence you aren't as secure as the size of the key space would indicate (and, for some groups, there may be even faster attacks).


Why isn't the IND-CCA property inherited when sending redundant ciphertext? Suppose that in order to avoid loss in transmission, a secret key encryption scheme $(Gen, Enc, Dec)$ is modified to be $(Gen, Enc', Dec')$, such that the message m is encrypted independently three times as $Enc'(m)=(c_1,c_2,c_3)$, each $c_i=Enc(m)$.

For decryption, the 3 transmitted ciphertexts are decrypted using $Dec$. If at least 2 recover to the same message, that message is output as the decryption. Otherwise, an error message will be output.

So, I am wondering if $(Gen, Enc, Dec)$ is indistinguishable under a chosen-ciphertext-attack (IND-CCA), why isn't $(Gen, Enc', Dec')$ IND-CCA, too? Is that because there is the possibility that we may receive the error message? I mean $(Gen, Enc', Dec')$ uses the same $Enc$ and $Dec$, why doesn't it inherit the IND-CCA property?

[EDIT: I am assuming a public key system here]

IND-CCA2 summary:

get encryption key.
make decryption queries on chosen ciphertexts.
obtain challenge ciphertext on $m_L$, $m_R$, two equal-length messages chosen by you, the attacker. The challenger is suppsed to randomply pick one, encrypt it and return the ciphertext.
make decryption queries as in 2. except that queries on challenge ciphertext are disallowed.
guess if the challenger encrypted $m_L$ or $m_R$

In IND-CCA2 decryption oracle, Step 4 logic is "decrypt only if the ciphertext is not the same as the challenge ciphertext".

How would you define "same" in the modified case? (Does the decryption oracle require all three pieces to match? If so the new scheme is clearly not IND-CCA2 - the attacker can ask for decryption of a ciphertext where one piece is random). Once "being same" is properly defined, it will be simple to check if the new scheme is IND-CCA2 or not .

By the way, you probably need IND-CCA2 instead of IND-CCA.

Also, you should check out the R-CCA security notion, where Step 4. is replaced by:

make decryption queries as in 2. except that if ciphertext decrypts to one of the challenge messages, the oracle returns "INVALID".

I recall seeing this definition of R-CCA but don't recall where. If you want, I can dig thru the references and post a link.

[EDIT:] One reference for R-CCA is this IACR eprint article, Section 1.3.


Can I use HKDF to improve security of HMAC used with weak hash function? I am writing a framework which encrypts/decrypts files (or streams, in general) with symmetric key using block cipher (for example, AES). To authenticate encrypted file, I use HMAC, which is initialized with a key derived from supplied password (using PBKDF2 and then HKDF function). It is calculated during encryption phase (I first encrypt, then HMAC). The result of the HMAC function is placed in the header of the encrypted file. On decryption, I check HMAC of the encrypted text. If calculated HMAC and HMAC from the file header match, then supplied password is correct and encrypted text is not corrupted.

My question is about hash function that is used with HMAC. Obviously, the best solution would be just to use some strong hash function (like SHA-256). However, I am experimenting with a thought of using weaker, but faster function, because I would like to improve performance of my framework (SHA-256 is not the fastest one). Using weaker hash function for HMAC does not necessarily mean that HMAC is affected. For example, Bruce Schneier wrote that broken SHA-1 does not affect HMAC.

What about using HMAC with MD4? From various sources I have learned that it is NOT recommended. But what if instead of plain HMAC/MD4 I use PBKDF2_MD4 as input for HKDF function, which takes PBKDF2_MD4 output as its input (e.g. as PRK) and expands entropy? Then I can retrieve this expanded entropy and use it (for example, first 16 bytes, whatever) instead of original HMAC output to authenticate encrypted file.

My question is - if HMAC_MD4 is considered insecure, is HKDF(PBKDF2_MD4) is also insecure? If MD4 is definitely a no-go, what about MD5?

I have read this paper on HMAC security based on various hash functions (including MD4, MD5 and others), which says that using these weak hash functions allows to perform a forgery attack. In my case, I am not concerned with forgery. I just need to verify that encrypted text is not corrupted and can be decrypted with the password provided. Obviously, using weaker hash function must not help an attacker to recover the password or, in general, get access to the unencrypted text.

Thank you for your attention.

First of all: accelerating PBKDF by using a faster hash doesn't make sense; an attacker is likely to receive the same speedup.

On 64 bit machines SHA-512 or one of the 384, 256 or 224 derivatives is likely to be faster than SHA-256. So you might be able to increase security and have a faster hash algorithm.

MD4 should probably not be used for anything anymore, including HMAC. MD5 is still considered secure for key derivation, but I personally would not feel comfortable using it for anything.

If you are not worried about forgeries you could simply go for a checksum over the ciphertext and a check value of some kind to see if the password is correct. I'm wondering though if the consequences of not protecting against forgeries is fully understood (e.g. with regards to padding oracle attacks). It may well be that failing to protect against forgeries allows attacks on the cipher or cipher mode of operation.

Currently I would go for PBKDF2, bcrypt or even scrypt, then perform HKDF-Extract to obtain an encryption key. For the KDF functions I would use SHA-512. Then I would use AES-GCM for authenticated encryption. Many processors will be able to accelerate AES-GCM fine, may it ever come to that.  Possibly I would use another KDF extract to create a different key that I would just use to check if the password entered was correct (in my opinion the work factor of the PBKDF should protect the key, not the size of the ciphertext as that may be small).

Alternatively you could use a NaCl compatible library such as libsodium, which has been optimized for security and speed.


How to test an implementation of a homomorphic scheme? I want to implement the following homomorphic encryption scheme from On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption by Lopez-Alt et al. I use C++ and I want to know before start to write code how am going to test my application, what test cases would be useful to imagine for such an application ?

I think to feed my application with inputs behind limits and other tests like this which are considered for every application, but maybe there are some kinds of tests for cryptographic implementations, special things that must be taken account.

For example, if I were to implement a hash function I would test it so that it hasn't significant more collisions than expected by theoretical results. I believe that the same stragegy applies in my case.

The best work I know on "How to test an implementation of a fully homomorphic scheme" is the work from Tancrede Lepoint and Michael Naehrig. The article has been published at AFRICACRYPT 2014. Basically, you need to compare the efficiency (in space and time) of the most important operations: KeyGen, Encrypt, Add, Mult, Decrypt.

Links

A Comparison of the Homomorphic Encryption Schemes FV and YASHE.
Slides.
GitHub Poc.


Does a two-way fixed-length hash function exist? Just wondering if a two-way fixed-length hash function exists. I'm not talking about encryption where your output is the same size if not larger than your input. I guess the best way I can put it is "like SHA or MD5, but also reversible." (I know SHA and MD5 aren't reversible by design, but you get the point).

What I understood from your question is that you want to map your data uniquely such that the output has less bits relative to the input. You can use data compression techniques to compress your data. Then, if you need the security, use cryptography. Although hash functions are able to compress your data, but they can't be reversed by everyone. This goal is opposite of their nature and their duties.


How should short term keys (keys stored in RAM or volatile memory) be described by PKCS#11? How are short term keys usually implemented by PKCS#11?

Is the proper way to distinguish between keys that are more temporary/stored in volatile memory and those stored in non-volatile memory to label them "session objects" or "token objects" using the CKA_TOKEN attribute?  Or is there another attribute or property in the spec that I am missing?

If a power-off event occurs for a device, is it valid to consider that to be an event which closes the session and allows session objects to be destroyed?

Is the proper way to distinguish between keys that are more temporary/stored in volatile memory and those stored in non-volatile memory to label them "session objects" or "token objects" using the CKA_TOKEN attribute?

Yes, temporary keys are indeed session objects.

  Or is there another attribute or property in the spec that I am missing?

No there is no other property that I know of. Just setting CKA_TOKEN to false should do the trick.

  If a power-off event occurs for a device, is it valid to consider that to be an event which closes the session and allows session objects to be destroyed?

Absolutely. I'd be very annoyed if a FIPS or Common Criteria verified product would not invalidate sessions on reboot (or, more likely, automatically remove all sessions on power off).

When the power is off the token may be transported to Siberia without the device noticing this. Clearly this should be reason to invalidate a session.

Destruction of keys when they are no longer needed are strong requirements both for FIPS and Common Criteria.


Trustless exchange without a third party Is there a cryptographic (or even not entirely cryptographic) way of exchanging objects between Alice and Bob that would not require a third party, and Alice and Bob would not need to trust each other? For example, Alice and Bob have Y and X objects (some information) and want to exchange them (in other words both Alice and Bob after transaction will have access to the set Y∪X). How can they do this directly to each other?

Is it possible to solve this problem, for example, using private keys, zk-proofs, etc? Is it possible to solve it in principle?

Thank you!

No, without some kind of trusted information there is no way of identifying the parties, so Alice and Bob are never able to trust that they have transferred the data to the right party.

Even if they meet in person they need to have some trusted data (such as facial features of a person, remembered from when they met before) otherwise they may confer data to an imposter.

I'm assuming here that you need to keep the data confidential. That is not apparent from your question. If this isn't the case Alice and Bob could simply publish the information for all to see.

Of course, Alice and Bob would still not be confident that the right entity posted the data, i.e. the authenticity of the data cannot be proved.


Do I need to know the curve for ECIES decryption? Let's assume that I have key pair generated using the following curves: brainpoolP256r1, brainpoolP320r1, brainpoolP384r1 or brainpoolP512r1.
Do I need information which curve was used to decrypt message? Can I infer which curve was used based on the private key?

This awfully looks like homework, but hey, here we go. Each curve has an order, which is the number of points on the curve (specifically, the number of points into a subgroup of prime order of the curve, but in the case of the Brainpool curves, the subgroup is the whole curve). A private key is a non-zero integer modulo the curve order; i.e. if the order is $n$, then the private key is a number between $1$ and $n-1$. In practice, the size of the private key, expressed in bits, will be close to the size of $n$ (the size in bits of an integer $x$ is the integer $k$ such that $2^{k-1} \leq x \lt 2^k$).

Curves brainpoolP256r1, brainpoolP320r1, brainpoolP384r1 and brainpoolP512r1 have orders of size 256, 320, 384 and 512 bits, respectively. Thus, look at the size of your private key; this should allow you to infer which curves you are talking about.

(Technically, a 255-bit integer, for instance, could be a valid private key for all four curves, since it would be in the accepted range for all four curves; however, probability that a private key, chosen uniformly in the range for brainpoolP320r1, ends up being a 255-bit integer, while it had a whole 320-bit range to chose from, is less than $2^{-35}$, so it won't happen often. In that sense, your answer won't be absolutely guaranteed to be correct in a mathematical sense, but it can be a good guess nonetheless.)


Will entropy be lost by using a DRBG? Lets assume we have a DRGB (deterministic random bit generator) which is seeded by a good true RBG (random bit generator). Before any bit has been read from the DRBG, the entropy is clearly the number of bits of the seed.

But is entropy lost, when I read out the bits of the DRBG?
From an information theoretical point , one could say that entropy will diminish by 1 with every bit I read from the DRBG.
But how could this be defined from a complexity theoretic point?
Does there exist a precise mathematical definition of a "complexity theoretic entropy measure" ?

Maybe that question sounds a bit philosophical, but it also has practical impact, because one can decide when its time to reseed.

A Deterministic Random Bit Generator (DRBG) would typically be used, when you have entropy input that is either

biased,
inefficiently generated, or
both of the above.

If you have a True Random Bit Generator that outputs unbiased bits efficiently, there is no apparent reason to use a DRBG in the first place. This is particularly true in case you require information theoretic security. Using a DRBG means you get pseudo random bits with computational security, typically expressed in the conventional way as 128-bits of security, 256-bits of security, etc.

This means that reseeding of DRBG, such as NIST SP 800-90A, should not be expected to be designed to address loss of entropy in the information theoretic sense, but only in a practical sense. It is done to reduce the risks (not eliminate the risks) associated with internal states being compromised through side channel attacks, etc.


How to implement a hash function $H \colon \{0,1\}^* \to \mathbb{Z}_p^*$? I would like to implement a hash function $H \colon \{0,1\}^* \to \mathbb{Z}_p^*$ such that $p$ is a prime number and $\log_2(p) > 256$. I am wondering if it is a good idea to use the hash function SHA-256.

Since $\log_2(p) > 256$, can I just use the output of SHA-256 and apply the modulo $p$ on it?

I would also like to prevent the all-zero (0000…0000) output from SHA-256, is it correct for example to add the value $1$ to the output of SHA-256? Is there a better way?

A possible method is to build $k=1+\lceil\log_2(p)/256\rceil$ 256-bit hash functions $H_i(x)$ per the HMAC construction, by choosing $k$ arbitrary distinct 512-bit constants $c_i$, by defining
$$H_i(x)=\operatorname{SHA-256}\Bigl((c_i\oplus\mathsf{opad})\|\operatorname{SHA-256}\bigl((c_i\oplus\mathsf{ipad})\|x\bigr)\Bigr)$$
then build
$$H(x)=\Bigl(\bigl(H_0(x)\|H_1(x)\|\dots\|H_{k-1}(x)\bigr)\bmod(p-1)\Bigr)+1$$
where for computation of $\bmod$ the $256k$-bit bitstring $H_0(x)\|H_1(x)\|\dots\|H_{k-1}(x)$ is converted to integer per (say) big-endian convention.

$H(x)$ is slightly biased towards zero, but the advantage an adversary can get from that is negligible.

There would be two issues when directly using $H(x)=\operatorname{SHA-256}(x)$ as considered in the question (or $H(x)=\operatorname{SHA-256}(x)\bmod p$ which is equivalent if $\log_2(p)>256$ ):

Except for $p$ just above $2^{256}$, it is easy to recognize such $H$ from a random function $H \colon \{0,1\}^* \to \mathbb{Z}_p^*$, because $H(x)<2^{256}$.
It is quite possible that there exist $x$ with $\operatorname{SHA-256}(x)$ the all-zero 256-bit bitstring, so that $H(x)$ is not in $\mathbb Z_p^*$; however we know no computationally feasible way to exhibit such $x$, thus this might not be a practical issue.


Which is the best AES mode of operation? Is there any reason to choose, say ECB over CBC? Or GCM over AEX? Or CTR over CFB? Is there a best AES mode of operation? And, when required, which is the best padding to use?

There are 2 major types of mode of operation:

The mode requires an initialization vector, which is subdivided into

1.1. a random IV. AES-CBC falls under this category, and

1.2. a unique nonce. AES-GCM and AES-CCM falls under this category.

For either of these subcategory, you should use a mode that provides authenticity guarantee (ideally choose an AEAD mode), so you should go with AES-GCM, or less preferably AES-CCM.

The mode is a DAE (deterministic authenticated encryption), which many may not had encountered.

The AES-KW specified in NIST-SP-800-38-F is one such example, but it sometimes expands the ciphertext. I would recommend you look at AES-SIV in RFC5297.

For the other modes I've not mentioned, ECB simply eats your privacy for breakfast and you won't be able to implement XTS mode that interoperates with other mainstream systems.


Can a compressed checksum be considered unique I'm kind of guessing that the answer may be no. Since the compression is trying to reduce the output size using various optimization methods, this may cancel the properties of a hash algorithm.

But take the following Python code:

>>> import zlib
>>> import hashlib
>>> zlib.compress(hashlib.sha256('data'.encode('utf-8')).digest())

Can the output from the zlib compression be considered unique?

Note that since the hash value is quite random, it cannot be compressed efficiently:

>>> len(zlib.compress(hashlib.sha256('data'.encode('utf-8')).digest()))
41
>>> len(hashlib.sha256('data'.encode('utf-8')).digest())
32

TL;DR: The zlib output is at least as unique as the SHA-256 output.

Compression libraries like zlib have to encode the data in such a way that it is recoverably, which implies that they can not reduce the uncertainity (entropy) of the data.

Because of this logic, the entropy of the encoded hash has to be the same as the one of the hash. Now as hashes tend to have near-perfect entropy, this means that the the encoded data has the at least same entropy and thus must be at least as unique as the hash itself. Additionally, the compression may work non-deterministically when encoding data and thus even add entropy resulting in multiple unique encodings of the same hash (thus "increasing" the uniqueness).


Difference between when select x from $\mathbb{Z}_{p-1}$ and $\mathbb{Z}_p$ in discrete logarithm Problem? Reading "Security Arguments for Digital Signatures and Blind Signatures" paper, I confused by some questions.

Q1. when it refers to "El Gamal signature scheme",

The key generation algorithm: it chooses a random large prime $p$, of length $n$ polynomial in $k$, and a generator $g$ of $(\mathbb{Z}/p\mathbb{Z})^*$, both public. Then, for a random
secret key $x \in \mathbb{Z}/(p − 1)\mathbb{Z}$, it computes the public key $y = gx \mod p$

why $x$ select from group $\mathbb{Z}_{p-1}$,but not $\mathbb{Z}_p$? what is the difference?

$\mathbb{Z}_p=\mathbb{Z}/p\mathbb{Z}$ denotes a finite field that is just integers mod the prime $p$, i.e., $\{0,1,\ldots,p-1\}$. This field (by definition of a field) has two operations: addition and multiplication, where the multiplication group (denoted by $\mathbb{Z}_p^*$) is defined only on the non-zero elements $\{1,2,\ldots,p-1\}$. Then, since $g$ is a generator of the multiplicative group of size $p-1$, the exponent $x$ should be sampled from $\mathbb{Z}_{p-1}=\{0,1,\ldots,p-2\}$ (which by the way is not a finite field).


Relation between entropy and min-entropy I understand that the entropy is the number of bits that can encode a set of messages. However, I don't understand what the min-entropy is and how it is related to entropy.

Let's describe a simple password case: if a password is 100 random bits, is the min-entropy also 100?

There is min-entropy, Shannon entropy, and max entropy. (Plus a few more definitions, but let's only focus on these.) All of these measures are greatest, for a given number of outcomes, when each outcome occurs with equal probability. (In such case all three are equal.)

$$\text{min-entropy} \leq \text{Shannon entropy} \leq \text{max-entropy}$$

Min-entropy describes the unpredictability of an outcome determined solely by the probability of the most likely result. This is a conservative measure. It's good for describing passwords and other non-uniform distributions of secrets.

$$\text{min-entropy} = -\log_2{(p_{\text{max}})}$$

Say you have an algorithm which produces 8 digit numeric password. If the number 00000000 occurs 50% of the time, and the remaining $10^8 - 1$ passwords occur with equal probability, then the Shannon entropy would be about $14.3$ bits, but the min-entropy is precisely $1$, which is $-\log_2{(0.5)}$.

Min-entropy can be associated with the best chance of success in predicting a person's password in one guess.

Shannon entropy is defined to equal $$\sum_{i=0}^n{-p_i\log_2(p_i)}$$ for a probability distribution $p$ with $n$ possible outcomes. Shannon entropy describes the average unpredictability of the outcomes of a system.

It also measures how much information is in a system (on average). Shannon entropy is the smallest possible average file size for a compression algorithm designed specifically with the distribution $p$ in mind.

Max-entropy is defined solely on the number of possible outcomes. It is equal to $-\log_2(n)$. It's not particularly useful in cryptography or passwords. It's a measure of the number of bits you would need to have to designate one bit pattern for every possible outcome.

The three quantities are always the same for a uniform distribution. This is because $p_i = p_\text{max} = \frac{1}{n}$.

$$-\log_2(p_\text{max}) = -\log_2 (\frac{1}{n}) = \log_2 (n)$$

$$\sum_{i=0}^n{-p_i\log_2(p_i)} = n(\frac{1}{n} \log_2 (\frac{1}{n})) = -\log_2 (\frac{1}{n}) = \log_2 (n)$$

This is why passwords picked from a uniform distribution (using a secure RNG) are said to be stronger than human generated passwords. Humans are biased in which password they choose. (Their password distribution is non-uniform.)


Is it OK to just hash a symmetric key to derive an authentication key? I'm using xsalsa20poly1305 for encryption in my program from libsodium. The recommended size for chunks is 4 kB. In that case, poly1305 will have authentication only for the the individual 4k chunks. Not the whole message.

I would like to authenticate the whole message again with poly1305 or HMAC-SHA256 or whatever. It's well known that reusing the same key for encryption and authentication is a bad idea. Please correct me if I'm wrong there.

My question is: Is it OK to calculate SHA-256 or SHA-512 of my current key and use it as the key for authentication (in an open-source project where everyone will know the algorithm I'm using)?

Please note that in my application, it's absolutely not possible to have more than one symmetric key, because that key is derived from ECDH.

Yes this is "OK".

  Please correct me if I'm wrong there.

You are correct.

It's effectively ratcheting the original key.

However there may be a more elegant solution such as using static keys for auth and ephemeral keys for key agreement (i.e. use Ephemeral-Ephemeral Diffie-Hellman for each new message).


How to prove that finding a cycle in a cryptographic hash function is hard? I want to show that finding cycles in a cryptographic hash function is hard.

My thought: assume there a black box, that given a cryptographic hash function $h$, finds some $x$ and $r$ in polynomial time, such that applying $h()$, $r$ times gives $x$:
$$ h(h(h\ldots(h(x))) = x $$

Can this be used to prove the function is not collision resistant or pre-image resistant?

How to prove that finding a cycle in a cryptographic hash function is hard?

In a uniform random function on a space of $n$ elements, the distribution on the length $s$ of a chain starting at any $x$ before it repeats, i.e. the smallest $s$ such that $h^s(x) = h^{s - q}(x)$ for some $q < s$ or equivalently the number of distinct elements in $\{x, h(x), h(h(x)), \dots, h^{n - 1}(x)\}$, is $$p(s) = \frac{(n - 1)! \, s}{(n - s)! \, n^s},$$ whose expectation grows with $\frac 1 2 \sqrt{2 \pi n}$ (Harris 1960, Eqs. 3.2, 3.4, 3.11; paywall-free).*
Standard collision search algorithms work by following such a chain with a tortoise–hare algorithm to find the point where a non-cyclic initial chain coincides with a cycle.  But your black box somehow finds just the cycle without any initial chain.  Although the distribution of cycle sizes is weighted more toward smaller than larger cycles with expectation $\frac 1 4 \sqrt{2\pi n}$ (Harris, Eq. 3.11), the number $q$ of elements that are themselves on cycles has the same distribution as $s$ (Harris, Eq. 3.12).
For, e.g., a 256-bit hash function as you need for the standard 128-bit collision resistance, the expected probability of stumbling upon an element on a cycle by chance is about $2^{-128}$.  Even for a 128-bit hash function like MD5, although the expected probability of stumbling upon an element on a cycle by chance is about $2^{-64}$, the expected cost of confirming that it is on a cycle is $2^{64}$ steps, for a generic algorithm, although maybe there's a clever way to speed this up in batch or in parallel like the van Oorschot–Wiener collision search machine.
If, for some particular $b$-bit hash function aimed at random oracle applications like SHA3-256, you found a way to find an element on a cycle with substantially higher probability than $2^{-b/2}$, or a way to confirm whether an element is on a cycle or not with substantially lower cost than $2^{b/2}$, it would likely be worthy of publication and cast serious doubt on the security of the hash function.

My thought: assume there a black box, that given a cryptographic hash function $h$, finds some $x$ and $r$ in polynomial time, such that applying $h()$, $r$ times gives $x$:
$$ h(h(h\ldots(h(x))) = x $$
Can this be used to prove the function is not collision resistant or pre-image resistant?

It is not a priori clear that this black box is helpful for finding collisions or preimages: clearly it does not itself find a collision, and it's not parametrized by an image for which it could find a preimage.
Of course, the field of generic collision search is a black art underlying a surprising array of cryptanalytic attacks including the usual hash function collision search, Pollard's $\rho$ for factorization, Pollard's $\rho$ for discrete logarithms, hash function preimage search including AES key recovery, and so on.
So it would not surprise me if a black box with this capability could be fruitfully used to accelerate a generic collision search, or if it could be proved not helpful, but it would be an interesting theorem either way!

* Harris 1960 is an excellent compendium of probability distributions for various quantities in various important types of random mappings.  Read it!


Retrieve timestamp from TOTP value TOTP (Time-based One-Time Password) as I understand is an algorithm that uses the current time as a variable along with a shared key to generate a secured token. Wiki page for reference: http://en.wikipedia.org/wiki/Time-based_One-time_Password_Algorithm

What I wanted to know is whether it is possible to determine the timestamp data (time + timezone) from a particular TOTP value? I can generate the shared key which was used to generate the TOTP value.

The problem I'm facing is that we make use of TOTP to perform validations between our offline Android/iOS clients and our server. However, once in a while we encounter a user whose TOTP tokens fail to authenticate. We ask them the same sundry questions about current time synchronisation and to check their timezone. Often times, users have a hard time determining even this.

So, I was wondering whether I could simply work out the timestamp + tz information myself from the faltering TOTP token, provided I have access to the shared key used to generate the said TOTP token.

Thanks for reading and any help would be greatly appreciated.

In theory, it is not:

TOTP, like HOTP, is based on a Hash-based message authentication code (HMAC),
which in turn relies on a cryptographic hash.

Both the key, and the HMAC message (a time counter in TOTP) are hashed using the specified cryptographic hash.

One key goal of cryptographic hashes is:

it should be infeasible to generate a message that has a given hash

By definition, TOTP uses the SHA-1 hash function, which can be considered reasonably secure in this context.
Thus, it is impossible to determine either the key, or the time counter from just the hash value, even less so from the TOTP result, which is only a truncated part of the hash value.

In practice, maybe:

If you know the key you can itterate through a set of likely time counter values (e.g. now +/- one minute; now +/- x hours for timezone issues) and find the correct time counter value.

In fact, this is a variation of a brute force attack, with a limited set of likely inputs.


Password derived hash to encrypt known plaintext as password check The title sounds way too adventurous for what it actually is. I am currently building a system which features some encryption. There is already a system in place, which is built after that scheme if somebody is interested in more context: https://stackoverflow.com/a/44925718/5395110.

As a next step I have to plan user authentication (typical username-password-login). First I thought of a standard password-hash approach using Argon2i hashing. That sounded reasonable but then I realized that with enough bad luck I would essentially give the attacker a free pass to the data in combination with the already built system. To prevent that I thought of integrating password checking into the existing system and get rid of any hash stored as plaintext.

What I came up with:

User inputs password and sends it to the server
The password gets hashed with Argon2i => hashed password
Hashed password is used to decrypt a AES-256-GCM-secured ciphertext
If the ciphertext can be decrypted and is equal to a known static plaintext then the decryption was successful and the password is valid

So my question: Is a password checking system that uses a password-derived key to decrypt a authenticated block cipher to determine validity a reasonable alternative to just saving the hash?

The advantages are that there is no hash which can be extracted so an attacker would have to first find the key to the AES-container and afterwards find the plaintext to an Argon2i hash which seems like a very unrealistic task.

The bad feeling I have with this method is that it would probably work but completely miss the point of a authenticated block cipher since what I'm essentially doing is generating a HMAC of the hashed password(secret) and the known plaintext reference password(message) in a weird and unnecessary complicated way.

To be entirely honest the Idea is pretty intresting but wouldn't help a lot. AES is, mainly because it's widely used, a pretty cheap thing to do, so there's basically just one step more after hashing, so it wouldnt make a lot of a difference in that part. but one thing that I think may be intresting would be (but for a different reason):

Not encrypting a static String, but rather use the hash to create or encrypt a random Private Key generated while the user is signing up, while keeping the Pubkey readable and offer it to the user.

If you now use that specific key to sign something (similar to a canary report) and the user can check that it was signed with his key, then he can be relatively sure that for example no password reset happened because one cant reset the password without resetting the keys.


Question about TLS v1.2 Ciphers on my Web Server I need some help to understand the Ciphers being used by my web server running TLS v1.2.

What I understand is that my web server is configured to use only the listed methods of encryption. I suspect that it is telling the clients that it uses TLs v1.2, but my questions are:

How is DHE, ECDHE being used with RSA?
How is CBC, GCM being used with SHA?
Which one is the better one to use?
Should I used ECDSA instead of ECDHE?

ciphers:
|       TLS_DHE_RSA_WITH_AES_128_CBC_SHA (dh 1024) - A
|       TLS_DHE_RSA_WITH_AES_128_CBC_SHA256 (dh 1024) - A
|       TLS_DHE_RSA_WITH_AES_128_GCM_SHA256 (dh 1024) - A
|       TLS_DHE_RSA_WITH_AES_256_CBC_SHA (dh 1024) - A
|       TLS_DHE_RSA_WITH_AES_256_CBC_SHA256 (dh 1024) - A
|       TLS_DHE_RSA_WITH_AES_256_GCM_SHA384 (dh 1024) - A
|       TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA (secp256r1) - A
|       TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256 (secp256r1) - A
|       TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (secp256r1) - A
|       TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA (secp256r1) - A
|       TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384 (secp256r1) - A
|       TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (secp256r1) - A
|       TLS_RSA_WITH_AES_128_CBC_SHA (rsa 2048) - A
|       TLS_RSA_WITH_AES_128_CBC_SHA256 (rsa 2048) - A
|       TLS_RSA_WITH_AES_128_GCM_SHA256 (rsa 2048) - A
|       TLS_RSA_WITH_AES_256_CBC_SHA (rsa 2048) - A
|       TLS_RSA_WITH_AES_256_CBC_SHA256 (rsa 2048) - A
|       TLS_RSA_WITH_AES_256_GCM_SHA384 (rsa 2048) - A

How is DHE, ECDHE being used with RSA?

[EC]DHE means ephemeral Diffie-Hellman, so the master key is negotiated using DH parameters generated for the session. The server will generate these parameters and sign them via RSA using the private key corresponding to the servers long-term certificate.

  How is CBC, GCM being used with SHA?

CBC and GCM are the modes that the block cipher (AES) will operate in. SHA is the hash function used in the pseudo-random function (generally HMAC) that derives keys from the master key, and in the case of CBC mode also provides message integrity.

  Which one is the better one to use?

GCM is preferred, in general prefer using an AEAD mode of operation (more info on authenticated encryption here).

  Should I used ECDSA instead of ECDHE?

ECDSA is for signing data while ECDHE is for establishing a shared secret e.g. the master key. To use ECDSA you would need a server certificate that uses an ECDSA keypair. These are not very common currently. But if you did have an ECDSA certificate you would use it in conjunction with ECDHE, e.g. ECDHE-ECDSA-AES128-GCM-SHA256.


discrete logarithm equality for independent groups Given two different safe primes $p_1$, $p_2$ we construct the subgroups $G_1$ of prime order $q_1 = \frac{p_1-1}{2}$ and $G_2$ of prime order $q_2 = \frac{p_2-1}{2}$. Let $g_1$ be a generator of $G_1$ and $g_2$ be a generator of $G_2$.
We assume that the discrete logorithm is hard in both groups.

Alice randomly selects some secret value $ s \in \mathbb{Z}_{min\{q_1, q_2\}} $. Alice calculates $ x_1 := g_1^s \in G_1 $ and $ x_2 := g_2^s \in G_2 $ and a cryptographic hash $ H(s) $.
Alice sends $x_1$, $x_2$ and $H(s)$ to Bob via a secure channel.

Is there some pratical way that Bob can be sure that Alice indeed has sent values $ x_1 = g_1^a $ and $ x_2 = g_2^b $ such that $ a = b $? If not, can Alice provide additional data without revealing $s$ to convince Bob?

This question is somewhat related to "How can we prove that two discrete logarithms are equal?". However in our case two generators from two different groups are used instead of two generators from one group.

EDIT: Regarding the comments from poncho and Yehuda Lindell I further clarify what I mean by "discrete logarithm equality for independent groups":

I would like to use the following definition for $dlog_{g}$:
 $ {dlog}_g(g^e) := $ smallest $ x \mid x \geqslant 0, g^x \equiv g^e \pmod p $

Given $ s_1 = dlog_{g_1}(g_1^s) $ and $ s_2 = dlog_{g_2}(g_2^s) $
then $ dlog_{g_1}(g_1^s) \ $ equals $ \ dlog_{g_2}(g_2^s) \ $ iff $ \ s_1 = s_2 $

Let me assume for simplicity that $q_1 \leq q_2$. You want to prove that the discrete log of $x_1$ in $G_1$ is the same that the discrete log of $x_2$ in $G_2$, and that this discrete logarithm seen as an integer is smaller than $q_1$. This suggests that you should rely on a zero-knowledge proof for a relation over the integers. The most natural method to do this kind of proofs is to work over a group of unknown order, as, intuitively, if the prover does not know the order of the group he cannot reduce the exponents modulo this order - and the relation should hold over the integers.

So, let $G$ be a group of unknown order where the discrete logarithm is hard (for example, the subgroup of squares of an RSA group). Let com$(\cdot)$ be a perfectly hiding integer commitment scheme over $G$ (e.g. the Fujisaki Okamoto commitment scheme). Let $s \le q_1$ be your secret exponent. In addition to $x_1 = g_1^{s} \in G_1$ and $x_2 = g_2^s \in G_2$, the prover sends a commitment com$(s) = c$ over $G$.

Let us take the protocol suggested by professor Lindell as a basis. Consider the following modification of this protocol:

the answers are not computed modulo $q_1\cdot q_2$, but they are instead computed over the integers. For this not to break the zero-knowledge property, the mask $r$ should be taken, say, 160 bits longer than $s$, so as to statistically mask $e\cdot s$ over the integers.
The prover proves knowledge of $s$ which is the discrete log of $x_1$ and $x_2$ and the value committed in $c$
The prover additionally proves that the value committed in $c$ is lower than $q_1$. The classical method to do so is as follows: both players compute $c’$ from $c$ and $q_1$, a value that commits to $s’ = q_1 - s$ (the Fujisaki-Okamoto scheme is homomorphic, it is essentially com$(m;r) = g^mh^r$). Observe that $s \leq q_1$ is equivalent to $s’ \geq 0$. moreover, by a classical result of Lagrange, an integer is positive if and only if it can be written as a sum of four squares. Therefore, the prover computes this decomposition of $s’$ into a sum of four squares (via the Rabin-Shallit algorithm), commits to them, and proves that $s’$ is the sum of the squares of these committed values. Such a protocol is known as a range proof and is described in several papers, e.g. this one.

Once this protocol is complete, the verifier is convinced that the prover knows an integer $s \leq q_1$ such that $g_1^s = x_1$ and $g_2^s = x_2$. One can refine the protocol to make it more efficient, but I tried to make the answer as intuitive as possible.


Are applications aware of data records received before and after tls rehandshake? It seems that a tls endpoint can pump more data records even when it has received a re-handshake request from peer.

Also in dtls, new data records would get accepted even while rehandshake is in progress since any of the endpoint does not have way to tell whether those records originated after a handshake message. This is because re-transmission of handshake message gets a new record protocol header sequence number. So looking at record protocol header sequence number is not a good way to tell the ordering of events.

Do the endpoints have any way to tell which data they received before re-handshake completed and which one they received after rehandshake?

Section II-B talks about this. The answer to this is implementation-dependent. For example, if you're using GnuTLS, you can get some non-fatal error codes if you try to read after parameters change. Then you can look in your logs and distinguish data from before you got the error code from data that's timestamped afterwards. But you may have to be actively looking or polling for it.

You may have better luck on Stack Overflow with this one for particular implementations.


wireless network security protocol In network security, encryption and integrity done by the same algorithm that is AES-CCM in that MIC generated by CBC-MAC and encryption done by CTR mode. So suppose I want to do encryption with any stream cipher algorithm, can I use some hashing mechanism like HMAC separately for integrity purposes?

Yes, and that's how it's normally done. This even applies to AEAD schemes like GCM, CCM, and EAX (which all encrypt with CTR and MAC as a separate matter with some other algorithm); with non-AEAD schemes, you have systems like CBC+HMAC in TLS, and (with stream ciphers for encryption) ChaCha20+Poly1305 (which are two completely independent algorithms). However, this is something that's really hard to get right, which is why standardized AEAD schemes are so nice (AEAD means there's a well-analyzed specification of exactly how to combine them).


Deterministically combine more than one source of entropy What is the proper/canonical way to do this?
For example, $0 < r1 < 1$ and $0 < r2 < 1$. Presuming uniformly distributed probabilities for the two, combining/averaging them is going to bias very quickly towards $0.5$.
The specific use case I have is a game/simulation I'm programming. An entity has a random number it was given that's specific to it; Their individual behaviours also have random numbers associated with them. For the purposes of most behavioural calculations, I only use the behaviour random number, but for a few I want to incorporate the entity's random number. Simply averaging them will result in less randomness.
Desired Outcome : Deterministically combine more than one source of entropy
So “Entity A” may have a small random number, and so most of its attributes are skewed small. It's behaviour random number happens to be big, so most of its behaviour attributes are skewed large. When combined the two random numbers deterministically result in $n$, and so some of its behaviour attributes skew towards $n$.
RE: Off-Topic
My question is not specific to game development. The particular use case is. How do cryptographers deterministically combine sources of entropy? I assume they have uses case for this outcome.

Set $r = r_1 + r_2 - \mathsf{floor}(r_1 + r_2)$. One (possible) advantage of this approach is that the result will be uniformly random in [0, 1] even if only one of $r_1$, $r_2$ is uniformly random. (Assuming the two values are independent.)

In Python you can also express this as

r = (r1 + r2) % 1.0


Can I use SHAKE-256 on 32-Bit Microcontroller? SHA-512 cannot be really run on a 32-bit ARM microcontroller since it uses the 64-bit constants, but since SHAKE-256 uses only 32-bit values, can it be run on a microcontroller with 32-bit registers?

SHA512 cannot be really run on a 32bit ARM microcontroller since it uses the 64bit constants,

Sure it can; a 32 bit ARM microcontroller can do the 64 bit additions (by performing the addition in 2 32 bit steps and including the carry from one to the other); it can also perform the 64 bit shifts/rotates required by breaking up the operation into multiple steps.
Now, it won't be quite as efficient as it would be if the processor handled 64 bit operations natively, but that's quite different from saying it can't do it at all.

since SHAKE256 uses only 32-bit values, can it be run on a microcontroller with 32bit registers?

Again, the microcontroller is quite capable of performing all the operations required.
What I don't know (and is not immediately obvious) is which would perform faster on an ARM; SHA-512 or SHAKE256 (and that might depend on the size of the input...)