Hash functions with variable and fixed length inputs I was told that a hash function (mostly looking at the SHA-* family) should have input strings of variant length provided first, and those of fixed length after (ie salt), in order to avoid some kind of collision attacks.

I haven't seen this explained anywhere, so I was wondering whether this holds and how so.

What I'm describing seems to be related to the length extension attack (also see Understanding the length extension attack) (thanks to Dan Anderson for bringing this up)

Suppose you want to hash a pair of bit strings $(m, r)$ with a hash function $H_0$ defined on bit strings, where $m$ is variable-length and $r$ is fixed-length—maybe a unique salt, or a secret key, or an unpredictable randomization.  We will consider possible functions $H(m, r) := H_0(\operatorname{encode}(m, r))$ for some encoding function (although there are other possible ways to hash tuples using an iterated hash function).

First, what security properties are you hoping for when you say ‘hash’?  Here are some possibilities:

Independence.
If $r \ne r'$, then the functions $m \mapsto H(m, r)$ and $m \mapsto H(m, r')$ are (effectively) independent functions.

Here we are modeling $H_0$ as a uniform random choice of functions with quirks like the length extension attack below; we are interested not in how $H$ behaves on different messages with the same $r$, but rather how $H$ behaves with different $r$.

This is important for password hashing, because techniques like rainbow tables provide a batch advantage trying to find inputs $m_1, \dots, m_n$ given the outputs $h_1 = f(m_1), \dots, h_n = f(m_n)$ of the same function[1][2].  However, you should use a serious password hash like scrypt or argon2 if you're hashing passwords, and they are already defined in terms of separate password and salt parameters.
Collision resistance.
It is hard for the adversary to find $(m, r) \ne (m', r')$ such that $H(m, r) = H(m', r')$.  This is a standard property of functions like SHA-256 and BLAKE2b; if it holds for $H_0$ we might hope that it holds for $H$.

This is important for commitments: you can prove to someone that you have a message $m$ without revealing it by picking $r$ uniformly at random and revealing $h = H(m, r)$; then when you want to reveal what the message was, you can give them $(m, r)$ and they can verify $h = H(m, r)$.
(Enhanced) target collision resistance.
It is hard for the adversary to find a message $m$ such that, given uniform random $r$ after choosing $m$, they can find $m' \ne m$ and $r'$ with $H(m, r) = H(m', r')$.

With mere TCR[3] (first introduced to the literature as the less-pronounceable UOWHF[4]), the adversary is restricted to $r' = r$; with eTCR[5], the adversary is allowed to choose $r'$, so eTCR is a stronger requirement.

(e)TCR is important for randomized signature schemes like RSA-PSS and Ed25519.  The first secure signature scheme in history, Rabin's, used a randomized hash.  Even if $H_0$ turns out to have collisions like MD5, there are choices for $H$ that remain eTCR to the best of our knowledge.  Using a TCR construction would have thwarted MD5 certificate forgery, including a particular attack used by the governments of the United States and Israel to sabotage Iran's nuclear program—but RSA, Inc., and the IEEE adopted $H_0(r \mathbin\| H_0(m))$ instead of $H_0(r \mathbin\| m)$ in the standards[6][7] for PSS signatures.  (More history.)
Pseudorandomness.
It is hard for an anyone who doesn't know $r$ to distinguish the function $m \mapsto H(m, r)$ from a uniform random function of the same shape.

Pseudorandomness is useful for many things including deterministic key derivation and message authentication codes.

These properties aren't exhaustive, but they're likely to be relevant in a wide variety of applications.

What encoding might we use to define $H$ in terms of $H_0$, and what properties does the resulting $H$ provide?  Let's assume $H_0$ is an iterated hash function, like essentially all of them, and let's assume for simplicity that $m$ an integral number of blocks long.

Suffix-MAC: $H(m, r) := H_0(m \mathbin\| r)$, putting $r$ at the end.

provides independence
provides exactly as much collision resistance as $H_0$: a collision in $H$ is a collision in $H_0$ and vice versa
provides at most as much (e)TCR as $H_0$ provides collision resistance: finding a collision in $H_0$ is enough to break (e)TCR of $H$—so, no (e)TCR for MD5 or SHA-1!
provides at most as much pseudorandomness as $H_0$ provides collision resistance, for iterated Merkle–Damgård functions with no output filter like MD5 or SHA-256: finding a collision in $H_0$ is enough to distinguish $H$ from uniform random—so, no pseudorandomness at all for MD5 or SHA-1!

Prefix-MAC: $H(m, r) := H_0(r \mathbin\| m)$, putting $r$ at the beginning.

provides independence
provides exactly as much collision resistance as $H_0$: a collision in $H$ is a collision in $H_0$ and vice versa
provides at least as much (e)TCR as $H_0$ provides collision resistance: an (e)TCR break of $H$ implies a collision in $H_0$, but finding a collision in $H_0$ does not necessarily help to find a collision in $H$—e.g., nobody has broken eTCR for MD5 in this form
provides no pseudorandomness for for iterated Merkle–Damgård functions with no output filter like MD5, SHA-256, and SHA-512, for which length extension attacks apply: given $H(m)$ but not $m$, it is easy to find $H(\operatorname{pad}(m) \mathbin\| m')$ for any suffix $m'$, which a uniform random function exhibits with negligible probability—so, no pseudorandomness for MD5, SHA-1, SHA-256, SHA-512!

Exception: If $m$ is fixed-length, then prefix-MAC provides pseudorandomness under reasonable assumptions about $H_0$ even when $H_0$ is MD5, SHA-256, or SHA-512.
Note that SHA-3, BLAKE2, SHA-512/256, and essentially all new designs in the past decade do not have this weakness, so $H(r \mathbin\| m)$ is pseudorandom—but they usually also provide separate keyed hashes like KMAC128 or keyed BLAKE2, which are better to use because they are effectively independent even if you happen to hash the message $r \mathbin\| m$ with SHA-3 or unkeyed BLAKE2.

Envelope-MAC or sandwich-MAC: $H(m, r) := H_0(r \mathbin\| m \mathbin\| r)$, putting $r$ at the beginning and the end.

provides independence
provides exactly as much collision resistance as $H_0$
provides at least as much (e)TCR as $H_0$ provides collision resistance
provides pseudorandomness under reasonable assumptions about $H_0$

This is a predecessor to HMAC and actually it provides about the same security as HMAC with less complexity, as long as $m$ is padded so that the $r$ keys appear in their own blocks; it was left in the dustbin of history mainly because someone noticed that it does not provide security if the trailing $r$ straddles a block boundary[8] and thereby gave it a bad reputation, but it has since been proved that with appropriate padding it is a perfectly good choice[9] (paywall-free).
HMAC: $H(m, r) := H_0\bigl((r \oplus \mathrm{opad}) \mathbin\| H_0((r \oplus \mathrm{ipad}) \mathbin\| m)\bigr)$, using prefix-MAC first to compress the message and then as an output filter, with two keys derived by a simple key schedule.

provides independence
provides probably about the same collision resistance as $H_0$
provides at least as much (e)TCR as $H_0$ provides collision resistance
provides pseudorandomness under mostly reasonable assumptions about $H_0$


How much time does AES decryption take? I am attempting to decrypt a 90 GB file that is encrypted using AES-256. I have the password. How long should this take to complete? I've had the process running for over 3 days with no progress.

I am attempting to decrypt a 90 GB file that is encrypted using 256
  AES. [...] How long should this take to complete?

If the AES implementation and the program doing the decryption are any good this is only bound by the speed of your drive, if your processor is newer than from about 2012. So for an SSD, you should be able to hit 200MB/s and with an HDD 50MB/s with little problems, if the program doesn't have some horrendous overhead and utilizes a sane implementation and with an older / weaker processor, you should still be able to saturate the HDD and run the SSD at about half speed.

Note however that certain platforms, e.g. standard python don't actually compile to machine code and thus are extremely slow, ie in a measurement I did recently I hit about 1MB/s with the interpreter. But even then it should "only" take you 25 hours. So chances are the program you are using is extremely poorly implemented and you should strongly consider using an alternative if you can.


Is a strong block cipher usable as a strong sponge function? From the literature, it looks like the security proofs of sponge functions depend on how well they approximate a random permutation, Since a block cipher also ideally behaves like a random permutation does that mean strong block ciphers make for strong sponge functions?

As in, can I expect:

extern char *input,*output;
extern int input_length,output_length;

char block[16] = {0};
char key[16] = {0};
for(i = 0; i < input_length; i++) {
    AES128_ecrypt(key,block,block);
    block[0] ^= input[i]
}
for (i = 0; i < output_length; i++) {
    AES128_encrypt(key,block,block);
    output[i] = block[0];
}

to be a cryptographically strong sponge hash of rate 8 bits and capacity 120 bits and hence be strong against $2^{60}$ attacks?

I believe that, in this specific case, you are correct; it would appear to take $2^{60}$ effort to find a collision in the above function.

On the other hand, there is one nit with this approach: this makes stronger assumptions on the block cipher than is typically assumed.  A block cipher behaves as a random permutation if it is keyed by a random unknown key; there is no such requirement that holds if it is keyed by a publicly known key.  AES is believed to act like a random permutation even with a fixed key, however that might not hold in general.  You could come up with an artificial block cipher that meets the normal requirements, but doesn't work as a sponge function.


Can we reduce Diffie-Hellman problem to "Discrete-log inversion" problem? Let $G$ be a cyclic multiplicative group of order $n$. Let $g$ be a (public) generator of $G$.
The Diffie-Hellman (DH) problem asks: Given $g^x, g^y\in G$ for $x, y\in \mathbb{Z}^*_n$, to compute $g^{xy}\in G$.

Let $O$ be an oracle that works as follows: it takes as input $g^x\in G$ for any $x \in \mathbb{Z}^*_n$, it outputs $g^{1/x}\in G$. In other words, $O(g^x)=g^{1/x}$. I call this the "Discrete log inversion" oracle for lack of a better name.

Can we use $O$ to solve the DH problem. I remember reading about this somewhere but can't locate the reference.

Note: $1/x$ is defined as the inverse of $x \in\mathbb{Z}^*_n$.

EDIT: To visualize such a group, let $n=15$ and consider the subgroup of $\mathbb{Z}_{31}^*$ generated by 7, which is $\{1, 7, 18, 2, 14, 5, 4, 28, 10, 8, 25, 20, 16, 19, 9\}$, containing exactly 15 elements. In this case $G=\{7^i \bmod{31}|i \in \mathbb{Z}_{15}\}$

The answer is yes; see Chapter 21 of Galbraith's book. Suppose we have your Fixed-Inverse-DH oracle $O(\cdot)$, and given $g^a$ and $g^b$ we want to find $g^{ab}$. We do this in two steps. First, we use $O$ to compute $g^{a^2}$ from $g^{a}$—this is a related problem called the Square-DH problem. Then we use the quarter-squares identity to compute $g^{ab}$.

To compute $g^{a^2}$ from $g^a$ using $O$, we perform:

$$
\begin{align}
x &= O(g g^a) = g^{1/(1+a) \bmod n} \\
y &= O(g / g^a) = g^{1/(1-a) \bmod n} \\
z &= O((xy)^{1/2 \bmod n}) = g^{1 - a^2} \\
w &= g / z = g^{a^2}.
\end{align}
$$

Let's call the above procedure $S(\cdot)$. Now, we use the quarter-squares identity

$$
(x + y)^2 - (x - y)^2 = 4xy,
$$

to compute $S(g^{a}g^{b}) / S(g^{a}/g^{b}) = S(g^{a+b}) / S(g^{a - b}) = g^{(a+b)^2 - (a-b)^2} = g^{4ab}$. Exponentiate to ${1/4 \bmod n}$ and obtain $g^{ab}$.


How are constructs with data-dependent swaps and rotations cryptanalyzed? Linear and differential cryptanalysis seem well suited for constructs with a (relatively) simple fixed structure of boolean expressions. But some ciphers incorporate swaps of array elements where the indices to be swapped are dependent on dynamic cipher state and others may include rotations by a variable number of bits. In the case of RC4, the entire cipher state is embodied in the permutation of a fixed set of integers.

This would seem to induce a combinatorial explosion in the number of expressions needed to track bias through the system. Is that a good thing?

Side-channel challenges aside, are such constructs unambiguously stronger than those made from fixed structures, or are they just harder to analyze?

What math is used to attack/analyze them?

Algorithms which swap bytes in an array are notoriously hard to analyze; the two main examples are RC4 (encryption) and MD2 (hashing). Being "hard to analyze" does not mean that they are strong; only that we do not have a generic framework such as differential cryptanalysis to apply to them. Both RC4 and MD2 are, academically speaking, "broken" (there are known attacks which are at least theoretically faster than what would be expected from the key/output length). Cryptanalysis is "ad hoc". For instance, in the case of RC4, the main result is due to Mantin and Shamir: they show that the probability of the second output byte of a RC4 stream to be 0 is about twice what it should be (1/128 instead of 1/256). The mathematics are elementary: they simply follow the algorithm description.

Being hard to analyze is not a good thing. It may slow down an attacker, but it also prevents algorithm designers from working efficiently. Simple, regular structures are preferred: we do not want algorithms that are just difficult to break; we want algorithms that we know are difficult to break.

Also, a RAM-based structure with a mutable array implies heavy implementation costs on very small architectures (smartcards, where RAM is the scarcest resource) and on dedicated circuits (FPGA, ASIC). On a PC, RAM access is relatively fast, but still not as fast as one could hope for. MD2 is known to be very slow and RC4 is outperformed by more recent stream ciphers. Hardness of analysis and performance issues make mutable arrays unpopular in recent algorithm designs.


Is it safe to send a hashed password over HTTPS or what is the most secure method of authentication? My rudimentary understanding of HTTPS and the Diffie-Hellman key exchange is that the client and server can establish a secured connection by generating the same key based on their private secrets and shared secret. That key is then used to encrypt/decrypt the data being passed back and forth between the two parties.
This means that I have established a secure connection, but says nothing about the identity of the client connecting to my server. It could be anyone with a browser. My question is, in order to identify a client after already having established an encrypted connection, is it safe to establish the user's identity by sending a username and hashed password over said connection? Is this a sort of standard procedure?
In most of my use cases, my client and server are going to be either NodeJS or Java applications that I have programmed, some running on the same machine and possibly on a different server in different locations, so I am not too concerned about creating any kind of system to allow users to sign up. Would a preset hashed password be secure enough, or should I use asymmetric keys like SSH? I'm just not totally sure what the pros/cons are or what the standard way to authenticate a client is. Do I even need to hash anything, or can I just have the user send a plaintext password and check it against my database since the connection is already encrypted anyway?

The most common way for web sites is to send the password itself to the server, which then uses a "password hashing function" (NOT a cryptographic hash) like Argon2id or bcrypt to create a digest (containing some settings, a unique per account salt, and the hash of the password), and then compares the digest to the value stored on the server for that user.
It's possible to do this twice: you can use a password hashing function on the client, then send the digest to the server, and then use another password hashing function on the full digest. This can be done with different settings for the work factor on the client and the server to reduce the workload the server needs to compute. The server should use a second salt, still unique per account. The big disadvantages of this are that most clients won't have code for a password hashing function, he per-account storage overhead is higher (need to store an extra digest, so probably about 64 bytes more per user), and the login process needs to send the client the work factor settings and one salt.
For some applications it's possible to have clients generate an asymmetric key pair, send the server the public portion, and then authenticate by signing a challenge the server sends. EG the server could send a 32-byte random value to the client, the client could sign it, and if the signature is valid for the stored public key the server grants access. SSH does this. Ed25519 SSH keys are small, and there's lots of support for SSH's format. The disadvantage is that users need to keep these keys stored, losing their private key means losing access, and leaking their private key allows attackers access (just like a password). If viable this is the most secure option.
There are also saPAKEs, like OPAQUE good article here, which don't require sending the server a copy of the password (or a hash of the password), but they're not standardized yet. I'd avoid these for now, but keep an eye out for them to become standardized. And do read that article, it describes common password use cases more thoroughly than I did here.


Is it important to defend against key substitution attack in ECDSA? When planning a file signature scheme (basically, just to sign all files content). Is it obligatory to defend against ECDSA key substitution attack?
ISO/IEC 14888-3:2018 NOTE 5 states:

  The mechanisms of EC-DSA, EC-GDSA. EC-RDSA and EC-FSDSA may be
  vulnerable to a key substitution attack[10]. The attack is realized
  if an adversary can find two distinct public keys and one signature
  such that the signature is valid for both public keys. There are
  several approaches of avoiding this attack and its possible impact on
  the security of a cryptographic system. For example, the public key
  corresponding to the private signing key can be added into the message
  to be signed.

  [10] Bohli J.M., Rohrich S., Steinwandt R. Key substitution attacks revisited:
  taking into account malicious signers. Int. J. Inf. Secur. 2006, 5 pp. 30–36

"May be vulnerable" may be read as "may be not vulnerable". I also heard opinions such that practically that attack is not applicable. For example, when the key source is a trusted CA or it's in HSM device. Also, common tools (like openssl) generate raw ECDSA signatures without protection against such attacks.

So the question may be rephrased to—is it still sane to use raw ECDSA signature in 2019? And not to use some schemes like CAdES.

So the question may be rephrased to—is it still sane to use raw ECDSA signature in 2019?

It's not insane, but you should use Ed25519 in any new applications: it is faster, simpler, and more confidence-inspiring.

However, the standard notion of security of a public-key signature scheme—EUF-CMA, or existential unforgeability under chosen-message attack—says nothing about whether a signature that is valid under one public key may also be valid under another public key.  Let's call this property public key uniqueness.

Some exotic applications may rely on public key uniqueness, e.g. the Let's Encrypt name ownership verification protocol Acme was accidentally designed to rely on it at first[1], but most signature schemes do not provide this additional property, because most applications don't need it: you don't bother verifying a message with a public key unless you know the public key is good to begin with.

Neither ECDSA, nor RSASSA-PKCSv1_5, nor RSASSA-PSS provides public key uniqueness out of the box.  There are many additional security properties that exotic applications might want: key anonymity, public key uniqueness, signature uniqueness (which Monero accidentally relied on[2] in their exotic application), verifiably unique pseudorandomness (a.k.a. VRF), etc.  But most applications don't need them.

Rather than worry about exotic properties that an application once made the mistake of assuming, you should focus on what your application actually does need, by writing down what resources you rely on, what resources the adversary can control that you take action on, etc.

As it happens, Ed25519 does provide public key uniqueness, because the public key is hashed together with the message as part of making a signature.  This is a generic structure that probably works to turn any EUF-CMA signature scheme without public key uniqueness into one with it, as the note you quoted suggests, although it has the consequence that it essentially rules out another exotic property, message recovery[3].


How to avoid side channel attacks when handling large numbers? For cryptography, the platforms have limited size as 32 or 64-bit operations. We definitely need big numbers to implement the encryption/decryption and digital signatures for cryptosystems like RSA, Elliptic Curve, etc.

We have seen lots of side channel attacks due to timing differences or power usages analysis.

How are large numbers handled in cryptography and cryptanalysis?
What are the good libraries against side-channel attacks, including time and power analysis?
Can we have a countermeasure to Acoustic cryptanalysis by a specific big number implementation?

I recently wrote a big page on how big integers are implemented in BearSSL. There are several ways to represent integers in RAM and compute operations on them; also, note that for cryptography, we usually need big modular integers, which is not the same as big plain integers. BearSSL's code is constant-time, thus nominally immune to timing attacks (subject to the usual caveat that integer multiplication opcodes are not constant-time on some CPU).

Timing attacks are attacks for which the physical measure is based on elapsed time. They are special in that they can be performed remotely (either by measuring response time over a network, or by using the target computer's own abilities at knowing the current time); all other side channel attacks require the attacker to have special hardware in the physical vicinity of the target system. Timing attacks are the ones where you have to worry about the whole planet. For more information on timing attacks, see this page.

Smartphones muddy that picture a bit, because they have a lot of sensors that can be leveraged by hostile code, hence "remotely"; think for instance of microphones, cameras and accelerometers. With smartphone hardware, a nominally sandboxed application with access to some of these sensors might leverage some side channels on other operations that occur in the phone. Power analysis, though, should not be in that category, because smartphones don't include hardware for really precise measurement of their own power consumption.

BearSSL does explicitly not do anything against side channel attacks other than timing attacks. Being constant-time does procure a level of protection against some aspects of power analysis (simple power analysis can reveal which code branches the CPU follows, but one of the requirements of constant-timeness is that conditional branches do not depend on secret data, so this does not leak any secret information). Differential power analysis can leverage the difference between writing a 0 or a 1 in a given register or memory slot; you need some really good oscilloscope to pull that off. To protect against differential power analysis, the usual protection is to add random masking, a complicated process since it not only depends on the algebraic properties of your computation, but it also requires a source of good randomness, which might itself be targeted by differential power analysis.

An important point to make is that differential power analysis, and defence against it, depend a lot on the precise hardware involved. As such, there cannot really be such a thing as a "software library immune to power analysis". At best, you have a system that combines software and some specific hardware, which can be declared resilient to some extent. Smart card manufacturers are the people you want to talk with about such issues.


The security of an encrypt-and-MAC I would like to know what is the security of an encrypt-and-MAC with different keys for each transaction

For example: the one-time-pad with $k_1$ and the HMAC with $k_2$

$$C = M \oplus k_1\\
MAC = HMAC(k_2,M)$$

The ciphertext is $C||MAC$. The two keys $k_1$ and $k_2$ change for each transaction (for each $M$).

The answer to this question follows directly from the answers to Should we MAC-then-encrypt or encrypt-then-MAC? and the comment thread here.  In short: Your scheme is computationally secure (IND-CCA2 and INT-CTXT) assuming that HMAC is a computationally secure privacy-preserving MAC; but your scheme is wildly impractical, as fgrieu explains, so it is not very interesting from a practical perspective.  In addition, this is far from the best possible construction.

If you want advice on what construction to use, I suggest you ask a new question specifying your requirements and let folks suggest a construction.  In practice standard schemes for authenticated encryption should suffice for almost all real-world situations.


HASH Algorithm for 8 bits MCU I need to implement the HASH algorithm (MD5 & SHA-1) on an 8 bit MCU. I hear it can only be implemented on 32bit and sometimes 16bits MCU. Is that possible? I will appreciate link where possible. A program in C language most preferred.

Someone answered it in another "exchange" site: https://electronics.stackexchange.com/questions/1830/md5-implementation-for-microcontroller

There you have links to C implementations, etc.

And yes, it's possible to implement MD5 and SHA1 in 8bits, you'll just have to worki with 16 (or 32) bits operations, not that hard...


does SHA* collide more or less than a random function? There were several questions here regarding how surjective SHA-1/2 is, how many values don't have a pre-image from a fixed size input. I and others answered when modelling the relevant hash function as a random function.
The question is can we venture if common hash functions are likely to collide more or less often than a ideal random function. Are there other cryptographic hash functions where we know exactly which direction such a weakness lies?

If we could prove anything one way or another about this, it would be a remarkable result worthy of publication in a cryptography journal, since—except for length extension issues in MD hashes—we usually expect these collision-resistant hash functions to behave like good little random oracles.

Of course, there are other families of functions which are not collision-resistant but from which random choices of function have bounded collision probability, namely universal hashes like Poly1305 and GHASH.  We can use these as building blocks for fast authenticators or PRFs.  But I don't think you were asking about those.


Diffie-Hellman Key Exchange I apologize if this is in the wrong section. I am completely new to Cryptography. I was presented with the following problem and I am trying to find something that will explain to me how to proceed.
Demonstrate the Diffie-Hellman key exchange using an elliptic curve y^2 = x^3 + ax + 9 mod p, where p = 223. Use XA = 8, XB = 15. Find a perfect generator point or a generator point with the highest order if a perfect generator cannot be found for the first 30 points. List the values of the order of both the elliptic curve and generator point.

This homework is about constructing a tiny finite Elliptic Curve group over a prime finite field, then showing Diffie-Hellman key exchange on that.
It's needed to understand

Modular arithmetic$\pmod p$, that is computation (including division) in the finite field of integers modulo $p$ (here $p=223$ but the same techniques apply for any prime $p$).
The notion of set of pairs $(x,y)$ matching an equation $y^2 = x^3 + a\,x + b $ in that finite field.
Under some conditions on constants $a$ and $b$, construction of a finite Elliptic Curve group on that set (with one extra identity element added). With the problem as we get it, it must be used $b=9$, and $a$ is left at the discretion of the reader.
The notion of order of a group/curve, and of order of an element in the group (a perfect generator is to be understood as an element of order the order of the group; equivalently, adding the element to itself repeatedly reaches every element of the group).
Diffie-Hellman key exchange on an arbitrary finite group with a states generator. That's the easy part. "Use $X_A = 8, X_B = 15$" is to be used in that part only; that would be the values chosen by parties.

Because $p$ is so small, it's possible to get away with explicitly finding the points $(x,y)$ forming the (non-neutral) elements of the group. In actual cryptography, we'd get say $p\approx2^{256}$ and about as many points, thus point counting would probably use the Schoof–Elkies–Atkin algorithm, that many users of crypto, including me, have never actually studied.


How to create reduction functions in rainbow tables? I have been trying to understand rainbow tables lately and one part is giving me trouble to understand here. Let's say I want to generate a table where the chains are 100 000 hash/plaintext long. I have 50 000 hash to reduce then.

Is it necessary to have 50 000 different reducing functions to avoid the collisions?
How do I create those reduction functions (not just take the n-first letters of the hash for instance) ?

Is it necessary to have 50 000 different reducing functions to avoid the collisions?

Yes. If you do not have different functions it is not a rainbow table. It is just a table of hash chains which is less efficient, especially for high coverage tables. However, the functions do not have to be unrelated, just different.

  How do I create those reduction functions (not just take the n-first letters of the hash for instance) ?

Any way you want, as long as it leads to an even distribution and different functions. The simplest is to:

Use the size of the search set (of passwords, keys or what have you) and take the hash value modulo that, so the last bits/bytes if the set size is a power of two.
Then, to create different reduction functions you can add the index of the function to the value. I.e. you add nothing for the first, 1 for the second function and so on. This is sufficient, since the next hashing step will cause these small changes to again give a completely different output.
Finally you turn the value into an element of the search set. E.g. encode it into lowercase letters if that is what you are looking for.

The simplest example is if you are looking for a binary key. For example, you are building a rainbow table for DES, which has 56-bit keys (ignoring parity) and 64-bit output.

You can use the last 56 bits of the output (i.e. the whole output modulo $2^{56}$) and add $i$ (again modulo $2^{56}$) for the $i$th reduction function. Pseudocode:

def R(i, x): # i'th reduction function
    return (x + i) % (2**56)

In the case of passwords, suppose you build a table for eight-letter lowercase passwords hashed with MD5. There are $26^8$ such passwords, so you can take the hash value, interpreted as a 128-bit integer and compute (x + i) % (26**8) instead.

(Or you could take the latter half of the hash as a 64-bit integer, then do the same.)


Is E91 safer than BBM92? I would like to compare the security of these two QKD protocols which both use entangled photons that are distributed between the users Alice and Bob. In the case of E91, the photon is measured randomly in 3 different bases which allows to violate a Bell inequality.

In BBM92, only measurements in two mutually unbiased bases are performed. This allows not to violate a CHSH inequality (S=2).

Does the violation of the Bell inequality lead to a higher security and therefore smaller assumptions needed to trust the source?

Can you give me a toy-model example that the source can use to deceive in the case of BBM92 but does not work in the case of E91?

The answer is both yes and no, as I explain below.
1. No, BBM92 is better (or at least, we initially thought so)
E91 was the initial idea which led to the more rigorous BBM92.
In the E91 paper, there is not actual security proof, ant the attack is not really specified: if the CHSH inequality is violated by only a few percents (say $S=2.05$), how many secret bits can Alice and Bob still share? With the techniques known in the early 1990’s there were no way to answer this kind of question. BBM92 was essentially a way to replace the Bell inequality with a more tractable entanglement witness, and to transfer the security proofs of BB84 to entangled state protocols. So in term of security, and practicality, BBM92 is much better than the E91 which is badly specified. And in practice, when a physicist says “E91”, he often actually means “BBM92”...
2. Yes E91 turns out to be better (because it is device independent)
To my knowledge, the first QKD paper actually using Bell inequality violation as an actual security parameter for QKD is the Barett, Hardy Kent paper of 2004 (arXiv/PRL). This was initially seen as a way to to perform QKD even if one does not trust quantum mechanics. This kind of protocols has now expanded to the domain of device-independent quantum cryptography, when one does not need to trust your devices to perform QKD. In this sense, variants of E91 can indeed be safer than BBM92.
Artur Ekert actually said of the latter development that it was “a very good example of when your ideas are more clever than yourself”.


Multiplication/Division in Galois Field (2^8) I'm attempting to implement multiplication and division in $GF(2^8)$ using log and exponential tables. I'm using the exponent of 3 as my generator, using instructions from here.

However I'm having trouble getting the expected answer for some of these trivial multiplications.

For $2 · 4$ this works:

$$ \begin{align*}
 \log_3(2) &= 25 \\
 \log_3(4) &= 50 \\
    25 + 50 &= 75 \\
 \exp_3(75) &= 8 \Rightarrow \text{ expected answer}
\end{align*}$$

However for $7 · 11$ this breaks down:

$$\begin{align*}
    \log_3(7) &= 198 \\
    \log_3(11) &= 104 \\
    198 + 104 &= 302. \\
\text{Mod it by 255, gives us 47.}\\
    \exp_3(47) &= 49
\end{align*}$$
instead of the expected 77.

From what I understand, we use modulus 255 because the 3 generator 'wraps around' on the 255th power (so the pattern repeats after that) thus we only need 0~254. Even if I'm wrong in this, $302 \bmod 256$ still doesn't give us $70$, where $\exp_3(70) = 77$ (the expected answer)

My observation for both multiplication and division is that it works fine until the result of addition/subtraction goes out of range of 0~255.

In GF(28), 7 × 11 = 49.  The discrete logarithm trick works just fine.

Your mistake is in assuming that Galois field multiplication works the same way as normal integer multiplication.  In prime-order fields this actually is more or less the case, except that you need to reduce the result modulo the order of the field, but in fields of non-prime order the multiplication rules are different.

Let's do 7 × 11, for example.  Noting that 7 = 1112 and 11 = 10112, we can calculate 7 × 11 in binary as:

    111 ×
   1011 =
   ------
    111 +
   1110 +
 111000 =
 --------

So far, everything works the same as in ordinary integer multiplication.  But whereas in the integers we'd propagate carries while doing the addition, and thus end up with

      1112 + 11102 + 1110002 = 101012 + 1110002 = 10011012 = 77,

in GF(2n) addition is done bitwise without carries (i.e. GF(2n) addition is the same as bitwise XOR), and thus we get

      1112 + 11102 + 1110002 = 10012 + 1110002 = 1100012 = 49.

(Of course, if the result exceeded the group order, we'd also have to reduce it modulo the reduction polynomial, but in this case that doesn't happen for n ≥ 7.)


Security of key bits under indistinguishability for randomized encryption My question is about symmetric randomized encryption. Let c=E(k,m,r) be a randomized block encryption function where r denotes a random input chosen for each message block m. k and c denote the symmetric key and ciphertext respectively. If E has indistinguishability of m0, m1 for any chosen plaintexts by an adversary given a chphertext c of mb for a randomly chosen bit b, how does this translate to security of key k given ci for any chosen plaintexts mi by allowing oracle access to the adversary? In the deterministic encryption there is the security condition that the computation of k given p,c is infeasible. How is this property assured by indistinguishability?

If you could guess the key, you could decrypt the challenge ciphertexts and figure out which plaintext is which.

Conversely, if the cryptosystem has ciphertext indistinguishability in this attack model, then you obviously can't figure out which plaintext is which, so you can't guess the key.


Oracle DBMS_RANDOM algorithm? Oracle DBMS offer builtin random number generator (pseudo to be accurate). DBMS_RANDOM is one of the available packages, it is however considered as insecure for cryptography.
Do we happen to know the algorithm used by this method ?

A quick Google search shows the source code is available in the file dbmsrand.sql, which says:

-- Delayed Fibonacci, pilfered from Knuth volume 2


Practical use of semi direct product of group in Cryptography Is there any example of semi-direct product used in any of cryptographic application? Does it help in choosing integers p, q in RSA?

Public key exchange using semidirect productof (semi)groups by Habeeb et al
https://eprint.iacr.org/2013/226.pdf


Simple: Hash Into a Prime Field If I have some bytes, and I want to compute a secure hash into a prime field which is 300 bits long I can:

Use a nice hash, like sha3_512, and then

modulo my prime field (introduces some bias).
toss bits most significant bits away until the number is < my prime (some bias toward smaller numbers)
toss bits most significant bits away until 300 bits, and then modulo my prime if needed (less bias?).
toss bits most significant bits away until 300 bits, then start over (hash the hash) if the number is too big (eventually converge).  (no bias, slow)
???? some better method ????

How important is the bias overall?

If I'm using the resulting hash as the hash for a EC signature scheme, it's insignificant...since the hash isn't protecting anything... it's just collisions that are a concern, which we've made worse by a fraction of a bit.
If I'm using the resulting hash as a "nonce" to protect a secret value during, for example, an mpc computation, it could be "leaky".  Over many uses of such a scheme someone might be use the bias to attack the key or the mpc.   The same holds for deterministic nonces used to reduce signature malleability, which is why I think they are a very bad idea.  See https://ecc2017.cs.ru.nl/slides/ecc2017-tibouchi.pdf, for just how bad this is.
If I'm using the resulting hash as the private part of an pairing based signature scheme (which requires mapping a message into the curve) , it seems to me that the bias just causes a similar collision loss.

Has anyone compared masking methods for bias?   Is there a good reference on best practices?  IS there a good analysis of the types of protocols for which such masking is a concern?

First thing to note is that, if your paradigm is the hash the message into a 512 bit value, and then map that 512 bit field into a value $(0, p-1)$, then (unless $p$ happens to be a power of 2, and very few primes are) there will always be some bias.  $p$ is not a divisor of $2^{512}$, and hence some values will have more 512 bit preimages than others (and going to a complicated hash-of-a-hash method doesn't change this).

Secondly, if this is the paradigm we need to live with, your method 1 (compute $hash \bmod p$) achieves the minimal possible bias; some values will have $\lfloor 2^{512}/p \rfloor$ preimages (and hence occur with probability $2^{-512} \lfloor 2^{512}/p \rfloor$, others will have $\lfloor 2^{512}/p \rfloor + 1$ preimages (and so occur with probability $2^{-512} \lfloor 2^{512}/p \rfloor + 2^{-512}$; no other possibilities.

Thirdly, the amount of this bias (for $p \approx. 2^{300}$) is truly tiny; the ratio between $2^{-512} \lfloor 2^{512}/p \rfloor$ and $2^{-512} \lfloor 2^{512}/p \rfloor + 2^{-512}$ is circa $1 + 2^{-212}$; to even detect a bias that tiny (and an undetectable bias cannot be exploited) you'd need to sample circa $2^{424}$ hashes before the bias can be detected; and you will never ever generate that many.

Fourthly, one nice thing about the modulo method is that it is easy to test (assuming you're using a vetted modulo routine).  With the methods that involve exceptions, well, those can be trickier (because you need to go through all the possible cases to make sure those are handled properly); with the modulo, there is only one case.


How to compute certificates using Diffie-Hellman key exchange with certificates and Elgamal signature scheme We consider the Diffie–Hellman key exchange scheme with certificates. We have a system with the three users Alice, Bob and Charley. The Diffie–Hellman algorithm uses p = 61 and α = 18. The three secret keys are a = 11, b = 22 and c = 33. The three IDs are ID(A)=1, ID(B)=2 and ID(C)=3.

For signature generation, the Elgamal signature scheme is used. We apply the system parameters p= 467, d= 127, α= 2 and β. The CA uses the ephemeral keys kE = 213, 215 and 217 for Alice’s, Bob’s and Charley’s signatures, respectively.

To obtain the certificates, the CA computes xi = 4*bi +ID(i) and uses this value as input for the signature algorithm. (Given xi, ID(i) follows then from ID(i) ≡ xi mod 4.)

Compute three certificates CertA, CertB and CertC.
Verify all three certificates.
Compute the three session keys kAB, kAC and kBC.

I am confused on how to solve for this problem. The book does not really clarify how to do it well.
In particular I have no idea what the 'bi' used to solve for xi in the signature is.

For Example: to get certificate A I know that I need to find CertA = [(kA,IDA),sig(kA,IDA)]

To find kA(the public key), I do α^a mod p (which I found to be 10)

To find the signature, I do Sa = (x-d*r)*kE^(-1) mod p-1, where r=  α^(ke)mod p
The question says that xi = 4*bi +ID(i), which would be the x, but I don't know what the bi is referring to, so I don't know how to solve for the signature.

And for the verification step, it says ver_subK_subpub,CA(CertB), but it does not say what the verification function is anywhere. How do I verify if it does not say how to?

I am currently working through this myself. I believe that the variable $b$ refers to the public key, which you will find using the $\alpha^a \bmod p$ equation you mentioned. Given that, you have all the information you need to find $x$.


Algebraic relationship between Original Key and Sub Key of DES Does there exist any sorts of algebraic relationship between Original and Sub Key of DES? I understand that by solving K-Maps of 64-bit Input/48-bit Output, I can get 16 algebraic relationships relating each sub key with the original key. Has someone done it already? Can this be of any use in exploiting the vulnerabilities of DES?

Laurie Brown and Jeniffer Seberry (see paper here performed a comprehensive analysis of the key schedule of DES, published in AUSCRYPT90 (conference series which later on turned into ASIACRYPT), and suggested some changes to strengthen the key schedule.

This is a good starting point to start hunting citations, and see what else has been done since then.


PAN authenticatable irreversible tokenization algorithm I need to implement algorithm to create authenticatable irreversible tokens from PAN, without using any secrets.

Is it possible? Is there any standards for that from associations?

I was thinking about HMAC but it needs to distribute secret symmetric key to all relevant parties. How to do it without distributing cryptographic key? Also it should prevent to create an oracle.

If the PAN space is sufficiently large then you can use a SHA3-256(Keccak family) and use the required number of bits of the output. I guess in that case you may have to maintain a Card-Data vault for the lookup thing.


Are EC public key values evenly distributed? At my Day Job(tm) we've encountered a bug wherein if the leading digit of the X or Y value of a public key are zero, "shit happens" (this bug is in our code - I'm not suggesting there's some problem with EC itself. It's just an encoding thing and it's not particularly interesting for this question).

Naively, this suggests that we should expect 1 out of 128 keys to trigger the bug, but that assumes that the X and Y values are evenly distributed. Are they?

If it matters, the curve is secp256r1.

Yes, the coordinates are more or less evenly distributed, between 0 and the order of the curve (exclusive). The Certicom curves such as secp256r1 generally have an order very near the maximum of the bit size, e.g. the secp256r1 curve has the following order $n$:

FFFFFFFF 00000000 FFFFFFFF FFFFFFFF BCE6FAAD A7179E84 F3B9CAC2 FC632551

So that means that there is about one in 256 chances that the first byte is completely zero for each coordinate.

This is slightly different for e.g. Brainpool curves as the order is randomly chosen (for the correct bit size, of course) and thus lower, brainpoolP256r1 has for instance the following prime order $q$ (same thing, different name):

A9FB57DB A1EEA9BC 3E660A90 9D838D71 8C397AA3 B561A6F7 901E0E82 974856A7

so the chances are slightly higher for brainpool curves that the first byte is fully zero (slightly lower than one in A9 of course, so about 1 in 169).

It gets even more "funny", as I've seen implementations fix this by making sure that the leftmost byte is set to 00 if it is missing, in case constant size X and Y coordinates are required. Of course, that fails if the first two bytes are set to zero, with a much smaller but non-negligible chance. The chance of it starting with 16 bytes of zero are of course negligible, but otherwise you'd better make sure.

A donkey doesn't stumble over the same stone twice, as we say in the Netherlands (A fox is not caught twice in the same snare.)

You can have the same fun with EC private keys or RSA private keys, by the way. The RSA specification lists how to create constant size, unsigned, big endian values that you require in the definition of the I2OSP (Integer to Octet String Primitive) definition.

Note that that definition is a rather mathematical way of saying that you need to prefix enough zero bytes. I've seen a crypto professor implement it using big integer arithmetic. This is definitely not required. It is just a formal description how it commonly looks in computer memory if you encode the value correctly. For more info, see my answers here on crypto and the implemention on SO for Java (shameless plugs, sorry 'bout that).

P.S. The chance of either coordinate starting with a zero byte is about $1 - {({255 \over 256})^2}$. That's ever so slightly lower than $1 \over 128$, but $1 \over 128$ is a good ballpark figure I guess.


How does cryptanalysis of the Playfair cipher work? I have a set of Playfair-enciphered data that I'm trying to crack without the key. I know I need to analyse bigrams; I've currently worked out what decrypts to th, er, in, and he, and have figured out where th and he are in the grid. However, now I'm stumped.

I've looked at the "Solution to Polygraphic Substitution Systems" field manual, but it didn't help. How do I complete the cryptanalysis of Playfair having a few bigrams decrypted and knowing where two of those go in the grid?

There are several algorithms available which can attack a playfair cipher.

Hill climbing might be one option. Basically it starts with a random key (assuming it's the best one) and decrypts the cipher. The resulting clear text is scored using a fitness function. Then small changes are applied to the key and if the resulting clear text of the modified key scores better, the modified key is regarded as the best key and the process of applying small changes to the key starts over again until no better key can be found.

Sometimes Hill Climbing does not find the best solution, the algorithm gets stuck at a local maximum. An effective way to resolve this issue is to use the Shotgun hill climbing (refer to the wikipedia link provided above).

The Simulated Annealing Algorithm is another option, see also here.

Or you can use the Genetic Algorithm. The algorithm mimics the process of natural selection.

If you are interested in an online playfair breaker: http://bionsgadgets.appspot.com/ww_forms/playfair_ph_web_worker3.html. I think here the hill climbing algorithm is used. It is coded in Javascript, so the source can be studied.

If you are interested in how a clear text can be scored:
Quadgram Statistics as a Fitness Measure.


Difference between server salt and client salt? Basically I am trying to understand the difference between server salt and client salt. I know that the client salt is used to make encryption harder for hackers, but I can't seem to grasp the concept of a server salt. Does anyone know?

Disclaimer: The following is tentative. Before the question I did not knew about client salt.
The client salt is combined on the client side with the password. When that's used, the client no longer sends the password, but a password-equivalent obtained by hashing. Client salt is often deterministic and near-public, e.g. < DNS of the realm, converted to uppercase> | <user name> (other reference). The  client salt's role is that compromise of what the client stores or sends, or what the server receives, does not leak the password (other than by exhaustive search requiring a new effort for each user).
The server salt is combined on the server side with the password (or the password-equivalent resulting from a password hash with the client salt on the client side, as above). A common practice is that server salt is random, and secret in whole of part (in which case that's pepper). The server salt's role is that compromise of what the server stores does not leak the password (or other information allowing login such as the above password-equivalent) other than by exhaustive search requiring a new effort for each user and server. Using pepper splits the information necessary to carry this attack in two: the hashed passwords+salts (typically in a database), and the pepper (typically in a config file or source fragment).


Bcrypt VS Scrypt, Again? I found this article on SO, but the answer was short, and the subject was closed,

What i don't understand, is:
Which one of the two limits memory usage to avoid custom Hardware to break the password?

Edit: there is an excellent discussion for beginners like me here:

The scrypt function is specifically designed to hinder such attempts by raising the resource demands of the algorithm. Specifically, the algorithm is designed to use a large amount of memory compared to other password-based KDFs, making the size and the cost of a hardware implementation much more expensive, and therefore limiting the amount of paralleling an attacker can use (for a given amount of financial resources).

It means that some hashing algorithms use few memory, so that specific, custom hardware can be created to brute-force it. Since they use few memory, those hardware aren't that expansive, and can be done, at some extent.

When you require a large ammount of memory, you assure it won't fit in those L1, L2 and even L3 caches of the processor, so external memory (slower) will be accessed. And also means that a custom hardware will require a large ammount of memory, for each processor, and that is very expensive, specially if it is fast...

edit Yes, including PBKDF2.... http://en.wikipedia.org/wiki/Scrypt

edit 2: also read the accepted answer on this: https://security.stackexchange.com/questions/4781/do-any-security-experts-recommend-bcrypt-for-password-storage


A secure function evaluation problem and an alternative of 1 out of n oblivious transfer? I am considering a "secure function evaluation" problem:

Consider two parties: A and B. A has a one-to-one mapping function $f(x)=k$. Basically, the function $f(x)$ can be regarded as a table of two columns. The first column is the domain of $x$ denoted as $D$. The second column is the range $K$.
The party B has a secret input $x_i\in D$. B sends its input $x_i$ to A  and A will return the corresponding $k_i$ to B.

The requirement is that A will learn nothing about the input $x_i$  and the output $k_i$. B will learn nothing about the function $f(x)$.

For the above problem, a possible solution is the 1-out-of-n oblivious transfer. However, when the size of the domain (or the table) is large. Using oblivious transfer will introduce both heavy computational and communication overhead.
Another possible solution I can think about is to model the function as a circuit. And then some techniques such as Garbled circuit may be utilized.

I think the above problem as been considered for a long time in the cryptography community. Any related works or thoughts on this problem will be helpful.
Especially, is there an alternative of the 1-out-of n oblivious transfer to increase its efficiency?

The problem is known in the literature as private function evaluation (PFE). A sender has input (a function) $f$; a receiver has input $x$, and only the receiver learns $f(x)$.

If you are willing to leak the topology of a circuit that computes $f$ (but not the identity of the gates), then using classical garbled circuits / Yao's protocol will work. These garbled circuit constructions are known to hide the gate functionality. You just can't use the latest optimizations in garbled circuits (starting from free-XOR) since they leak which gates compute XOR and which don't.

If you are willing to leak (an upper bound on) the # of gates in a circuit that computes $f$, then you can do standard SFE of a universal circuit. A universal circuit $U$ takes as input the description of a circuit $C$, and an input $x$, and outputs $U(C,x) = C(x)$. To allow $C$ to have $n$ gates, the size of $U$ must be at least $\Omega(n \log n)$. A construction achieving that size was described by Valiant, but it is apparently a very complicated construction. There is a simpler construction of size $O(n \log^2 n)$ with quite small constants by Kolesnikov & Schneider.

Leslie Valiant: Universal circuits (preliminary report), STOC 1976
Vlad Kolesnikov & Thomas Schneider: A Practical Universal Circuit Construction and Secure Evaluation of Private Functions, Financial Cryptography 2008

There are some more recent approaches for PFE by Mohassel and Sadeghian that avoid universal circuits and have linear cost $O(n)$. As above, the protocol leaks the number of gates in the circuit computing $f$. I don't know about how these protocols stack up against universal-circuit protocols in practice. Besides the one below, there is also a followup work that achieve active security.

Payman Mohassel & Saaed Sadeghian: How to Hide Circuits in MPC: An Efficient Framework for Private Function Evaluation, Eurocrypt 2013.

If you are willing to leak the fact that $f$ has some other special algebraic structure (e.g., it is a linear function) then there are certainly ways to exploit the structure for a more efficient solution.

Otherwise, if you are not willing to leak anything about $f$ then there is really nothing you can do better than 1-out-of-$n$ OT. If $f$ can be a totally random mapping, then there is no representation of $f$ that is significantly more concise than its truth table.


S-box Cryptanalytic Resistance In DES, different S-boxes were tested for cryptanalytic resistance and the most secure one was chosen for the algorithm itself.

How do different S-boxes offer different levels of security against cryptanalysis and how is this tested?

This is only a partial answer to the question, but still: The S-boxes where chosen to maximize confusion and to create an avalanche of change. For example, there were specific properties chosen to make the S-boxes resistant against differential cryptanalysis, by making sure that small differences between different inputs lead to larger differences in the outputs (i.e. the Hamming weight of the difference increases).  IIRC, the more straight-forward criteria about differentials include:

$HammingWeight(input_1 \oplus input_2) = 1 \Longrightarrow HammingWeight(output_1 \oplus output_2) \geq 2$
for any input difference $a$ and output difference $b$: $input_1 \oplus input_2 = a \Longrightarrow Probability(output_1 \oplus output_2 = b) \leq \frac{1}{4}$

Also note that the S-box design interacts with the design of the permutation P.  P makes sure that changes are distributed across all the S-boxes.

Some of the properties were chosen to resist specific attacks.  For example, the DES S-boxes could have been made more resistant against linear cryptanalysis, but they were not, because the designers were not aware of linear cryptanalysis at the time.

A paper describing the design rationale of the DES S-boxes was published in 1994.


How do these figures represent a boolean function? In the Wikipedia article "Bent functions",
there are some figures representing those Bent functions:

How do these figures represent a boolean function ?

The image description page for the larger image describes it pretty well.

Specifically, the line at the top of the figure:

shows the 4-ary Boolean function $f(x_1, x_2, x_3, x_4) = x_1 x_2 + x_3 x_4$ in a graphical form.  Specifically, interpreting each possible input as a 4-bit binary number (e.g. $(0, 1, 0, 1) \mapsto 0101_2 = 5$), the corresponding square on the line (starting from square 0 on the left, and counting up to square 15 on the right) is colored red if the output of the function is 1, and white if it is 0.

The square below the shows the Walsh matrix of order 16, the rows of which correspond to the 16 linear 4-ary Boolean functions (a.k.a. the Walsh functions), using the same representation as for the top row.  The squares marked with dots are those where the nonlinear function shown at the top differs from the linear function described by the row, and the number on the right counts the number of such dots on the line.

The second square below that is the complement of the Walsh matrix, showing the 16 non-linear affine 4-ary Boolean functions (i.e. functions which are linear except for the addition of a non-zero constant, which for Boolean functions can only be 1).  The dots and the numbers have the same meaning as before.

Looking at the numbers of the right, one can see that the number of inputs at which the given function $f$ differs from each affine 4-ary Boolean function is either 6 or 10 = 16 − 6, demonstrating that $f$ is equidistant (in the sense of absolute number of differences modulo 16) from each affine 4-are Boolean function, and is therefore a bent function.

The other image just contains four smaller but otherwise similar subfigures, showing that each of the four 2-ary Boolean functions of Hamming weight one (i.e. producing the output 1 for only one set of inputs) is also a bent function.


Number of shifts in DES key schedule In DES key schedule some rounds use one left shift while others use two left shifts. What is the reason behind this?

For the first part of the question regarding DES subkey generation, the reason there is a difference in the rotation amount is so that each subkey is different, and that all bits of the original key are used, and that there is a fairly equal probability that a bit will be in a subkey.

The rotations occur on the equal sized 28-bit halves of the 56-bit permuted key (after PC1), and are then sent to PC2 and reduced to 48-bits.

Because of the rotation constant, all 16 subkeys are different. If the rotation constant was 2, the subkeys would start to repeat after 14 rounds.

The combination of PC2 and the rotation constant means that each bit of the 56-bit key is used in approximately 14 of the subkeys. Bit 1 of 56 for example is used 15 times, whereas bit 2 is used 13 times. A complete list of bits (prior to PC2) used in the subkey generation are shown in this answer.


Is it possible to safely implement the Signal Protocol (X3DH) without using XEdDSA In the X3DH specification of the Signal Protocol it mentions having a signed pre-key in the key bundle.
This pre-key is signed using the identity private-key.
Because the identity private-key is in the X25519 Montgomery form, it cannot be used as a signing key.
Therefore signal implements XEdDSA to overcome this and converts the Montgomery form key into it's bi-rationally equivalent Edwards curve form, effectively allowing the same key to be used for key exchange and signing.
This is my limited understanding of what's taking place.
However, I'm wondering, is it possible to skip XEdDSA and still securely implement the Signal protocol (albeit modified) by having separate ed25519 keys (Edwards form) only for signing (using EdDSA).
In this situation:

Would the separate (ed25519) public key be sent as an additional
(long term) key in the bundle (same as the identitykey).
Would we only need to continue signing the signed-pre key (using this ed25519 key), or will this introduce the need to also sign additional keys (since our additional signing key no longer matches with the original identitykey, possibly presenting a verification problem).

Reference:
https://signal.org/docs/

It turns out this is possible and has been implemented in the libolm library of Matrix.

The solution adopted in this library is to generate a signing key for each
user. This is an Ed25519 keypair, which is used to calculate a signature on
an object including both the public Ed25519 signing key and the public
Curve25519 identity key. It is then the public Ed25519 signing key which is
used as the device fingerprint which Alice and Bob verify with each other.
By verifying the signatures on the key object, Alice and Bob then get the same
level of assurance about the ownership of the Curve25519 identity keys as if
they had compared those directly.

Reference: https://gitlab.matrix.org/matrix-org/olm/blob/master/docs/signing.md


Problem with the signature of message using ECDSA over GF(2^m) I'm trying to set up an ECDSA with Elliptic Curves over $\operatorname{GF}(2^m)$ with an example of toy with the following values:
Using the Weierstrass equation on binary finite fields. $$E: y^2 + x*y - [x^3 + a x^2 + b]$$

Let $E$ be defined over the field $\operatorname{GF}(2^7)$ ($m = 7$) with the equation
$$E: y^2 + x*y - [x^3 + 0*x^2 + 1]$$ where $a = 0$ and $b = 1$, using the irreducible polynomial $P(z) = z^7 + z + 1 \bmod 2$
The points are in decimal which has a polynomial representation. Example; $(z^2 + z; z^2 + z + 1) = (0110; 0111)$ in its binary representation and $(6, 7)$ in its decimal representation.I am using wolframcloud software to validate operations.

$d = 17$
generator $G = (124, 68) = (z^6 + z^5 + z^4 + z^3 + z^2, z^6 + z^2)$, a point that lives on the curve
$Q = [d]G = (40, 19)$, a point that lives on the curve too.
$k = 13$
$P = [k]G = (82, 100)$
$r = x(P) = 82$
$e = SHA(m) = 19$
$k^{-1} = 79$
$S = k^{-1} (e + d*r) \pmod{P(z)}$
$S = 79 (19 + 17*82) \pmod{P(z)}$
$S = 11$

Finally I obtained the value r and S that is the signature of the message: $(r, S) = (82, 11)$

Verification, and then suppose that the second entity know the same parameters over the curve without know d nor k. The second entity will carry out:
$P = [(S^{-1} * e) * G] + [(S^{-1} * r) * Q] \pmod{P(z)}\\
S^{-1} = 74\\
P = (74 * 19) * G + (74 * 82) * Q \pmod{P(z)}\\
P = 102 * G  + 67 * Q \pmod{P(z)}\\
P = (80, 87) + (38, 35) \pmod{P(z)}\\
P = (30, 92) \pmod{P(z)}\\
P.x = 30$
which is different from $r=82$: $P.x$ should be equal to $r$, but, it's NOT.

Now, We suppose that the second entity knows $d$ such that $Q = d * G$ then:
$P = (102 * G)  + (67 * 17 * G) \pmod{P(z)}\\
P = (102 * G)  + (107 * G) \pmod{P(z)}\\
P = (102 + 107) * G \pmod{P(z)}\\
P = 13 * G\pmod{P(z)}\\
P = 13 * (124, 68)\\
P = (82, 100)\\
P.x = 82 = r$
which is correct but the second entity doesn't know $d$.
Could someone help me, please and tell me how I can solve this problem?

Annex code in Wolfram language: To perform scalar multiplication through sum of points and doubling of a point I am using the following code with
; or just Try It Online!
(* Input example GF(2^7): *)
m=7;
k="10001"; (*BinaQy representation 10001 = 17 in decimal *)
lim = StringLength [k] + 1 ;
a=0;
Gx=z^6 + z^5 + z^4 + z^3 + z^2;  (* Gx = 124 *)
Gy=z^6 + z^2; (* Gy = 68 *)
IrreduciblePolynomialCCE= z^7 + z + 1;
Qx=Gx;
Qy=Gy;
For [i=2, i<lim , i++,
    c=StringTake [k ,{i}];
    (*Dubling*)
    {d, {inv, u}}=PolynomialMod[PolynomialExtendedGCD[Qx, IrreduciblePolynomialCCE],2];
    Lamda=PolynomialMod[(Qx + Qy*inv ), {IrreduciblePolynomialCCE, 2}] ;
    X3=PolynomialMod[(Lamda^2 + Lamda + a ), {IrreduciblePolynomialCCE, 2}] ;
    Y3=PolynomialMod [ (Qx^2 + Lamda*X3 + X3) , {IrreduciblePolynomialCCE, 2}] ;
    Qx = X3;
    Qy = Y3;
    If [c=="1",{
        (*Sum*)
        {d, {inv2, u}}=PolynomialMod[ PolynomialExtendedGCD[Gx + Qx, IrreduciblePolynomialCCE],2];
        Lamda2=PolynomialMod[(Gy + Qy) * inv2 , {IrreduciblePolynomialCCE, 2}] ;
        XX3=PolynomialMod [(Lamda2^2 + Lamda2 + Gx + Qx + a) , {IrreduciblePolynomialCCE, 2}] ;
        YY3=PolynomialMod [Lamda2*(Gx + XX3) + XX3 + Gy, {IrreduciblePolynomialCCE, 2}] ;
        Qx = XX3;
        Qy = YY3;
        },{0}
    ]
]
Print [Qx]
Print [Qy]

The result $Q = (z^5 + z^3, z^4 + z + 1) = (40, 19)$

First of all I would like to thank @fgrieu, @kelelaka and the moderator Maarten Bodewes for their support to solve my question.
I had an error to determine K^-1, S, y S^-1, I was also missing an important piece of information which is the order of G (n = 29)
Correcting my mistake we have:
GF(2^7), m = 7
E: y^2 + xy - [x^3 + ax^2 + b]
y^2 + xy - [x^3 + 0x^2 + 1] with a = 0 and b = 1
Irreducible polynomial P(z) = z^7 + z + 1 mod 2
d = 17
G = (124, 68) = (z^6 + z^5 + z^4 + z^3 + z^2, z^6 + z^2), Generator a point that lives on the curve
Q = [d]G = (40, 19), a point that lives on the curve too.
k = 13
P = [k]G = (82, 100)
r = x(P) = 82
e = SHA(m) = 19
n = order of G = 29
k^-1 = 9 (Here was my first mistake when taking modularization with P(z) instead of n)
S = k^-1 (e + d*r) mod n (Here was my second mistake when taking modularization with P(z) instead of n)
S = 9 (19 + 17 * 82) mod 29
S = 15
Finally we obtained the value r and S that is the signature of the message(r,S)=(82,15)
Verifying the signature:
P = [S^-1 * e mod n] G + [(S^-1 * r mod n)] Q
S^1 = 2
P = (2 * 19 mod 29 )G + (2 * 82 mod 29)Q
P = [9]G + [19]Q
P = 9(124, 68) + 19(40, 19)
P = (76, 50) + (98, 104)
P = (82, 100)
x(P) = r
This is how we check that the signature is valid.


What kind of cryptography should i use? I have a trusted third part A that issues an access token (xml file) to an untrusted client C that uses this token to log into an untrusted server S and access to the authorized files.
I want only that C can't manipulate the token changing the permissions stored inside.

I had thought to digitally sign the token with private key of A (RSA digital sign), so that if C changed the token, the signature wouldn't be valid yet and the token rejected from S.

The fact is that I would also like to encrypt the content of the entire token but I can't use the RSA encryption (A encrypts with S public key and S decrypts with his private key) because only A has public/private key while S hasn't.

Indeed, there is no direct network connection beteeen A and S, so If I used a symmetric encryption, how could I get the decryption key to decrypt token?

What kind of en/decryption should I use for this scenario?
Thanks

Your requirements include the following:

S can decrypt the token.
C cannot decrypt the token.

Since S must be able to do something that C cannot, it needs to know something that C does not.

Your approach of signing the token with A's signature is fine for ensuring its integrity (C won't be able to modify it) as long as S knows A's public key through a trusted method (e.g. provisioning when you install your application). To encrypt the token, you will need something else.

The most obvious solution is that S generates a key pair and submits the public key to A (in a way that other parties cannot tamper with — TLS would be fine, as S already has A's public key).

A does not need to trust S in any way (unless there is some authorization mechanism and not just anyone can obtain a token, but that would be a different problem which you don't mention in your question). If S submits a self-signed certificate, just accept it, and identify S by its public key. If that certificate is invalid (i.e. S does not know the associated private key after all), then S will not be able to decrypt the token. S already has the power to refuse to decrypt the token, so this attack vector does not have any security impact.

Be careful in your protocol about replay attacks. Depending on what goes into the token, it may be reusable for other purposes, so make sure that all relevant information (identity of S, identity of C, purpose of the token, …) goes into the signature.


Blind Hash Signatures? Is it possible to implement blind signatures with purely hash-based signature algorithms?

Any whitepapers, code samples, etc on the subject would be helpful.

It's impossible:

Impossibility of Blind Signatures From One-Way Permutations -  Katz, Schroder, Yerukhimovich


Is there a reason that the N value in scrypt is limited to powers of two? I have been looking at the scrypt hashing algorithm and am confused as to why the N value, which determines the overall cost, is limited to powers of two. There are only 3 things that the N value actually affects

The amount of times to mix with salsa (via two loops with N being the count)
The amount of memory required to compute a hash
And one seemingly minor portion of mixing:

The mixing that relies on N is this:

for (i = 0; i < N; i++) {
    j = 32 * (X[16] & (N-1));
    for (k = 0; k < 32; k++)
        X[k] ^= V[j + k];
    xor_salsa8(&X[0], &X[16]);
    xor_salsa8(&X[16], &X[0]);
}

Would using N values that aren't a power of two compromise this mixing in some way?

The operation:

X[16] & (N-1)

is really, mathematically speaking:
$$ X[16] \mathrm{\ mod\ } N $$
With a generic $N$, this operation must be done with an actual division, which is expensive; some CPU types don't provide it, and for CPU which do provide it (e.g. x86), it is quite slow (for instance, for 32-bit operands on an Intel Core2, division latency is 40 cycles). This would raise the computational cost by a non-negligible amount; correspondingly, it would decrease the memory hardness of scrypt (since, for a given CPU budget, it would be able to do less memory accesses).

However, when $N$ is a power of 2, the modulo can be done with a simple bitwise "AND", which is a matter of a single clock cycle.


SHA-512 - How difficult is it to find a hash digest beginning with at least twelve zeros? I know it's possible to find a hash value with multiple zeroes in it, I know of some BitCoin hashes with it, but how difficult is it to find/create a hash digest with 12 or more leading hex zeroes in it?

First, we need to model SHA-512 as uniform random.
Start hashing random values.
In hex we have 4-bits

We would expect about 1 in $2^4$ values to have a hash-value with 0x0 at the beginning.
We would expect about 1 in $2^8$ values to have a hash-value with 0x00 at the beginning.
We would expect about 1 in $2^{12}$ values to have a hash-value with 0x000 at the beginning.
We would expect about 1 in $2^{16}$ values to have a hash-value with 0x0000 at the beginning.
...
We would expect about 1 in $2^{48}$ values to have a hash-value with 12 hex zeroes at the beginning.

So we can say that we expect $\dfrac{2^{512}}{2^{4\cdot k}}$ values will have leading $k$ hex zeroes.

Little experiments
For random inputs the SHA-512 hashes with leading zeroes in hex;

random sample
none
1
2
3
4
5
6
7
8

1M
937670
58485
3604
225
16
0

10M
9375898
584890
36824
2231
149
8
0

100M
93752595
5856572
366283
23019
1446
75
9
1
0

1B
937501048
58591757
3663483
228262
14501
881
66
2
0

$1B \approx 2^{30.89}$ and to see 12 leading zeroes, the experiment must go to $2^{48}$ and that needs still $2^{18}$ more time. It is quite doable with a single CPU, though parallel processing is possible, too. Note that this is a Python experiment and took ~22 minutes for 1B.
For a CPU this may be hard to achieve since SHA-512, although a fast hash function, is still not a simple function to evaluate. If you have a GPU like GTX 1080 then you may reach $2^{48}$ SHA-512 hashing around 36 hours and if you have GTX 3080 then you may need 18 hours.


Proper Way to Encrypt Data with Two Keys? I'm going to develop a system that will have two keys. One supplied and generated by the system that's specific to an individual user and one from the user.

I plan on using AES.

Does it make sense to:

Concatenate the two keys to make a "master" key and then encrypt the data?
Encrypt with one key and the encrypt again with the other key?

Does it really matter? I can't see that it'd really matter, but maybe I'm missing something.

To begin with, some essential requirements are missing from your question at the time I write this, so I am going to assume:

$User$ trusts $System$.
$System$ trusts that $User$ will not pass $Key_{User}$ to any entity that $User$ does not trust to be $System$.

This implies, in particular:

$System$ is already authenticated to $User$, and $User$ already has a channel for passing $Key_{User}$ to $System$ with preserved authenticity, integrity and confidentiality.
The environment of $System$ is such that there is no risk $Key_{User}$ or $Key_{System,User}$ will be extracted from $System$ by an attacker. Alternatively, there is no risk it will happen without detection, in which case an auxiliary protocol exists for replacing the keys.

If the above conditions are met, both methods you describe in your questions are fine for generating an effective content encryption scheme. Just a few points:

Generating an effective key simply by concatenating two pieces contributed by two separate entities (as in your first method) is an unusual approach. I would probably prefer to combine them using a Key Derivation Function instead of simply concatenating them. However, given that $System$ and $User$ both trust each other, the only compelling reason for using a KDF instead of concatenation, would be if, in some sense, it would be worse if both entities are compromised, compared to if just one of them is compromised. A KDF will be better at hiding the other part of the key material, compared to just concatenation before the AES key schedule.
Encrypting the payload contents twice (as in your second method) is also a bit unorthodox, but it can be done in such way that you will get at least the same security, as with just one encryption key. Hence, you could in such case rather just encrypt $Key_{System,User}$ with $Key_{User}$ using a key wrap encryption scheme, and store the resulting cipher text $System$ side. Using key wrap encryption might provide additional benefits, such as the ability for $User$ to change $Key_{User}$ without $System$ having to decrypt and re-encrypt the entire content cipher test (if the key is used for stored data), and the ability for $System$ to give multiple users ability to decrypt the same cipher text, bu wrapping the same content encryption key using multiple user keys.


Concerns about use of MAC in my specification Here is the pseudocode for a routine I am designing:

encrypt(password, string):
  nonce1 := generate_random_nonce()
  nonce2 := generate_random_nonce()
  key := derive_key(nonce1, password)
  encrypted := cipher(nonce2, key, string)
  return (nonce1 || nonce2 || encrypted || mac(key, encrypted))

I realized that an attacker with the encrypted text might be able to brute force the key, since a mac is not slow to compute (like key derivation).

I thought about using a third nonce for the mac key instead of the ciphertext key, but the mac key should be secret so this isn't an option.

  How should I correctly use a MAC to authenticate the ciphertext (and thus plaintext) in this situation?

The pseudocode has a serious issue: changing the value of nonce2 in an otherwise valid cryptogram is not detected, and results in invalid deciphered plaintext. That would be fixed by

encrypt(password, string):
  nonce1 := generate_random_nonce()
  nonce2 := generate_random_nonce()
  key := derive_key(nonce1, password)
  encrypted := nonce2 || cipher(nonce2, key, string)
  return (nonce1 || encrypted || mac(key, encrypted))

but leaves two lesser issues:

The same key is used for cipher and mac; when not done properly, that can be a bad thing, and is a known recipe for disaster, e.g. if both cipher and mac used the key as an AES key for CBC encryption and CBC MAC, rather than using a carefully thought authenticated encryption mode like AES-GCM-SIV. With cipher chacha, and mac blake2b which is based on the chacha core, we should at least worry (even though I see no attack right now), and perhaps use something like proposed by Maarten Bodewes in that other answer.
We are told that derive_key is pkcs5_pbkdf2; this does key stretching, which is indispensable for any password; but PBKDF2 does not leverage the RAM and possibly multiple CPUs available at no cost to legitimate users, hence is orders of magnitude less safe against serious adversaries (using ASICs or FPGAs for password searching) than something state-of-the-art like scrypt.


Can a billion elliptic curve keys be generated on a laptop in less than an hour? I want my application to generate an EC key pair.

The first four bytes of the sha256 hash of the public key should contain a known IP address.

As hashes are one-way functions, I need to brute force this by generating four billion keys.

Is this possible, in under an hour, on a laptop?

Openssl is not the way to do this - generating just a thousand keys takes few seconds.  Four billion would take six months at 4s/thousand.

#!/bin/bash
time for a in {0..999} ; do
  openssl ecparam -genkey -name secp256k1 -noout -out key.priv.pem
done

Is openssl doing something which is unnecessary in making keys just to check the hash?

The very fastest elliptic curve algorithms can generate a key-pair in about 40k cycles on a modern CPU. A high end laptop has four cores running at about 3 GHz, so it can generate about 300k key-pairs per second, or a billion per hour. (The cost of SHA-256 is negligible in comparison.)

However, secp256k1 is nowhere near the fastest curve. It takes 10 times as long to generate a key-pair with many algorithms, according to the above link, so it would likely take tens of hours at least to iterate the search space. A more mainstream laptop and you may be looking at several days.

So if you just brute force generate key-pairs looking for a matching one, you can't get it done in an hour even with a much better implementation (unless you get lucky).


Using the same RSA keypair to sign and encrypt The RSA signature operation is basically the same as encrypting with the private key.  In particular, both operations use the same kind of keys.

Is it safe to use the same RSA keypair both for encryption / decryption and for signing / verification?

The short answer is no. This is a general piece of wisdom in cryptography: never use the same key for more than one thing. A “thing” means a specific scheme where all the parameters are fixed apart from the key itself and the message size. Don't use the same key to encrypt and sign; don't use the same key with both PKCS#1v1.5 and PSS; don't use the same key with different hash functions.

If you use the raw RSA operation ($M^d \bmod n$ or $M^e \bmod n$), then no, it is unsafe to use the same key, because an attacker could trick the private key holder into signing a message $M$ (i.e. generating $M^d$) which is actually an encrypted message ($M = P^e$), thus allowing the attacker to recover the original plaintext ($(P^e)^d = P$). (The dual attack leads to a forgery.) However, the raw RSA operation has a whole range of other flaws that make it unsafe as an encryption or signature scheme.

Encryption and signature schemes based on RSA use padding modes. The standard padding modes include discriminants so that an encryption payload does not look like a signature payload. Therefore, it is technically safe, cryptographically speaking, to use the same RSA key pair for signature and encryption, provided that the key pair is used safely for signature and used safely for encryption. Here, I mean safe in a narrow sense, assuming a “perfect” world where everything that should stay secret, remains secret.

The thing is, the world is not perfect. Implementations of RSA can leak partial information through side channels. Keys get compromised. Protocols using RSA sometimes use it in ways that are very brittle.

Using the same key for both encryption and signature can exacerbates weaknesses. RSA has a history of weaknesses, not in the mathematical algorithm itself (once you use proper padding), but in the way it's implemented. Decryption, especially, requires a lot of care, because some inputs are invalid, and the mere act of revealing whether an input is valid or not can allow oracle attacks, the best known of which is due to Bleichenbacher. The way RSA decryption is used in TLS¹ exacerbates this because it creates a second reason for invalidity: a ciphertext can be invalid for the decryption operation, or can be valid for decryption but decrypt to something invalid. This has led to a long series of practical attacks against TLS cipher suites that use RSA decryption. Using the same key for both encryption and signature has two downsides. Most obviously, if a vulnerability in decryption allows the attacker to recover the key, then anything that relies on a signature is also broken. Less obviously, even if the attacker can't recover the key, but can get some partial information about the decryption of invalid ciphertexts, they may be able to forge signatures. This is the case, for example, with the CAT variant of Bleichenbacher's attack, so that even clients that do not accept RSA decryption ciphersuites are still at risk if the server uses the same key for RSA signature ciphersuites.

Another reason is key management. Signature keys and encryption keys have different requirements in terms of backups, access control, repudiation, etc. The fallback for a signature key in case of a catastrophic event is to destroy it to avoid future forgeries, so a signature key does not need to be backed up extensively. Conversely, the fallback for an encryption key is to keep it around to decrypt existing documents, so it needs to be backed up reliably. In case of a leak of a signature key, pre-existing documents are not affected; it is only newly produced signatures that must be repudiated. Conversely, in case of a leak of an encryption key, the confidentiality of all pre-existing documents is at risk, whereas new documents simply need to be encrypted with different keys. The constraints push in different directions, so the keys need to be managed differently, they need to be different.

¹  That is, ciphersuites whose name starts with TLS_RSA_. Ciphersuites whose name starts with TLS_(EC)DH(E)_RSA use RSA signature, not RSA decryption, and are a lot more robust.


Why x00 is usually avoided in salt? In .NET Framework, there is a cryptographic Random Number Generator (RNG) provider which enables to generate a cryptographically strong sequence of random bytes. This provider contain, among others, two methods:

GetBytes which generates a sequence of random bytes, and
GetNonZeroBytes which does the same thing, except that the generated sequence will contain only nonzero bytes.

In every case I've seen where a salt is generated (for example for PBKDF2), the code similar to this is used, calling always the GetNonZeroBytes method:

var salt = new byte[128];
using (var rng = new RNGCryptoServiceProvider())
{
    rng.GetNonZeroBytes(salt);
}

I'm not sure, but from what I've seen, I believe that zero bytes are avoided in other languages/frameworks too.

Why GetBytes is always avoided? What's bad in having x00 in a salt?

Is there a limitation in one of the popular hashing algorithms (SHA512, PBKDF2, etc.) which prevents using the salt containing x00, or the zero bytes are avoided only by fear to having interoperability issues or the issues with the storage of the salt in some third-party database?

This is not a limitation of the cryptographic functions, like SHA or PBKDF,  since the zero byte isn't processed any differently.

Since the purpose of a salt is generally to travel alongside a human password, libraries that handle the password as a zero-terminated string might also handle the salt as such a string. Obviously, a 0x00 in the salt would terminate the salt per-maturely when it is processed as a string. If you're interested, you may want to view the code to see where the salts you saw generated actually get used and whether those APIs treat the salt as a string.

In general, there is no universal standard for how to format salt, so the way a salt is processed is left up to the designers of a specification. If you don't know what APIs a salt you generate will be plugged into, the safest strategy is to make the contents all non-zero so it will work with any API that evaluates the salt as a string.

Another (less likely) explanation: In general, there are some standards that require random values that be non-zero. For example, PKCS v1.5 encryption scheme (section 7.2.1 step "a") calls for 8 bytes of random padding of nonzero values. In this example the padding value is not a salt, but the existence of such requirements for random data in some specifications may lead a developer to cautiously always generate non-zero random data just to be safe.


Can an U2F public/private key-pair for signatures be used for encryption? I understand that this might be more a process question:

Given a U2F device which supports signatures using ECDSA public/private key pairs, is there a way to use the signing function of such a device to generate an encryption key?

I would like to understand if U2F could be used to improve the following scenario:

I use a password manager with a password vault file with 100 stored passwords.
I use a master secret to unlock the password vault, which leads the password manager to decrypt all 100 passwords.
I use a single password from the vault to log into a web-site and close the vault again.
An attacker that has access to my computer would have access to the master password, the password vault file and all 100 passwords.

How can we improve on this scenario:

I would like to encrypt each password stored in the vault with a specific encryption key.
I would like to use a second factor device to make sure that only one password is decrypted at a time when I perform a physical action.
U2F seems an ideal application for this, since it automates the process of storing individual credentials for individual 'sites', except that it performs signatures but not encryption.

Constraints:

The public/private key pair is generated inside the U2F device and the private key can not leave the device.
The device does not support any other operations but the signature operations based on the U2F specification, namely ECDSA.
The password vault should be treated as an insecure and static, i.e. the user has unlocked the vault and an attacker could see all data in it. The password manager has no means to perform any secret operation, any computation is visible to an attacker.
Communication between password manager and U2F device can be observed entirely by the attacker.

Pointers:

A comment in an answer to a similar question on security.stackexchange.com seems to indicate that there is no plausible way to use an ECDSA device to derive an encryption scheme

To answer @fgrieu's question:

The U2F device is meant to assist to decrypt a single encrypted password
An authentication scheme is not sufficient, since an attacker has access to all encrypted data and could bypass the authentication step if no encryption is involved.
Only a signature function exists on the U2F device
The U2F protocol is executed by the password manager as the server, so no external data storage exists. All U2F handle information and the ECDSA public-key are to be stored in the password vault.
The U2F device generates public/private key-pairs of which the public-key is returned as part of the initial registration. The private key remains securely stored on the U2F device.

No.

It is possible to derive keys from deterministic signatures (or non-deterministic signatures that can be converted into a deterministic value), for example Android uses Trusted Execution Environment's RSA signing plus scrypt to bind Full Disk Encryption keys to a specific device.

However, ECDSA signatures are not deterministic (there's RFC6979, which specifies deterministic use, but U2F doesn't use it), so each generated signature will be different for the same message and key, thus you cannot derive the same key from multiple signings.


Can the RSA accumulator scheme be converted to Elliptic Curve math? Is it possible to translate the RSA accumulator scheme directly to EC without requiring bilinear pairings?

In RSA we have:

$A_{n+1} = A_n^c$ st.             $\{c \: \textrm{prime} \: | \: c \in [\mathcal{A}, \mathcal{B}]\}$

$W = A_n$

$A_{n+1} \stackrel{?}{=} W^c $

Would this work in EC like this?

$A_{n+1} = c A_n$

$W = A_n$

$A_{n+1} \stackrel{?}{=} c W $

Where $A_0$ is a generator point on the curve and $c$ is prime.

If not, then why?

OK posting my own answer, not sure if this is correct, but:

The RSA accumulator scheme relies on the lack of knowledge of the totient function, which is used for computing inverse powers.

The EC scheme doesn't have this restriction so you're able to prove any value is a member of the set simply by computing its inverse.


semantic security of RSA variant I am thinking of a variant of RSA.
I know that RSA itself is not semantically secure as it is "deterministic". I have a "randomized" variant of RSA in mind.

Suppose that the public key is $<e,n>$. To encrypt a plaintext $p$, this variant first randomly choose a value $v$, and output the ciphertext as:
$$E(p)=<v,(v+p)^e \text{ mod }n>$$
The ciphertext consists of 2 parts, the value of $v$ in clear, and the ciphertext of $(v+p) \text{ mod }n$ computed using the original RSA.

Is this variant of RSA semantically secure? How do I prove it?

No it's not.

As a reminer: Semantic security is equivalent to IND-CPA. Semantic security is less commonly used, because most of the time proofs are less intuitive and more difficult.

In the IND-CPA game, the attacker chooses two messages $m_0,m_1$ and sends them to the challenger. The challenger chooses a bit $b$, and sends $Enc(m_b)$ to the attacker. The attacker wins if he can guess $b$ correctly. And we consider the encryption scheme secure, if the advantage of the attacker compared to random guessing is negligible.

So, let's play the CPA game with this variant:

The attacker chooses $m_0$ and $m_1$ arbitrary (but not equal)
He gets back $Enc(m_b)$. In your scheme that would be some value $v$ and $(v+m)^e \mod n$.
Since he knows both $m_0$ and $m_1$, he can check both possibilities by calculating both $(m_0 + v)^e$ and $(m_1 + v)^e$. Comparing that with the challenge, he immediately knows $b$
The attacker wins.

If you want to have an IND-CPA RSA variant, there is RSA-OAEP. In the random oracle model and with the RSA assumption, this is proven to be IND-CCA2, which is much stronger than IND-CPA.


Can the salting function complexity improve the hash robustness? I'm quite novice in security, and all examples I saw seem to salt the password by concatenating it, or by applying a simple binary OR or XOR. So the hash is based on "salt + password", "salt | password", etc.

If I'm right, a hacker should know how the password has been salted in order to retrieve a user password. So, can the complexity of the salting method improve the overall security?

First, good password hashing functions like PBKDF2 and scrypt usually take the password and salt as separate parameters, meaning the user does not have to worry about this. However, with some algorithms they do and in any case the theoretical question is important.

Some of those methods you mention are clearly worse than others:

Binary OR would be particularly bad and I hope it is never used. Any position where the salt has a 1 bit would be 1 regardless of the password bit, so about half the entropy in the password would be lost. (AND would be the same, just with bits reversed.)
XOR is not as bad, but two different salt-password pairs can lead to the same password hash. That makes a parallel attack on many users' passwords easier than it has to be.
Some sort of addition (e.g. byte-wise) would have the same problem as XOR.

The normal method is to concatenate. It loses no entropy and produces a unique input into the hash function for every salt and password. There is really no advantage to doing anything more complex as the user, because that would effectively be just another part of the password hash.


J-PAKE : About Schnorr NIZK proof for ephemeral private keys Reading J-PAKE Authenticated Key Exchange Without PKI document :
J-PAKE

  Round 1 : Alice sends out g^x1 and knowledge proof for x1, e.g :
      To prove the knowledge of the exponent for X = g^x1

My question is : Is then the recipient (the verifier) of g^x1 + NIZK of x1
    able to get the x1 value ?

No. The whole point of doing a zero knowledge proof (in this case, a non-interactive zero knowledge proof) is that the verifier does not learn any additional information besides the statement that is intended to be proved.

The Schnorr protocol allows to prove knowledge of the discrete logarithm without revealing the exponent. On top of that, the Fiat-Shamir heuristic can be applied to the protocol to produce a non-interactive version of the proof, still without revealing the exponent.


How key materials are generated in SSL V3 from master secret The generation of key materials is given by

key_block =
        MD5(master_secret + SHA('A' + master_secret + ServerHello.random +
            ClientHello.random)) +
        MD5(master_secret + SHA('BB' + master_secret + ServerHello.random +
            ClientHello.random)) +
        MD5(master_secret + SHA('CCC' + master_secret + ServerHello.random +
            ClientHello.random)) + [...];

The document says, it is done until "enough output has been generated". I think the "+" refers to append the data generated.

We need:

client write mac secret
server write mac secret
client write key
server write key
client write IV
server write IV

So these are generated by taking appropriate number of bits from the generated hash?

I couldn't understand why the document says "enough output has been generated". Any way we need the 5 parts from the master key.

You can use TLS 1.0 as guidance: it is the direct successor of SSL 3.0, so many things are quite similar, and in some respects TLS 1.0 is a bit clearer. In section 6.3 you will find the key generation process, with the exact sentence:

  To generate the key material, compute [...]
     until enough output has been generated. Then the key_block is
     partitioned as follows:

the important word being "partitioned".

For instance, if you are using 3DES as symmetric cipher and SHA-1 for the MAC, the "write keys" are 24-byte long each, the IV are 8-byte long each, and the MAC keys are 20-byte long each. So, a total of 104 bytes. The key generation function repeatedly invokes SHA-1 and MD5 on various elements; each round produces 16 additional bytes (that's the output size of MD5). You need 104 bytes, hence, you will need 7 rounds.

At the first round, you call SHA-1 over the concatenation of 'A' (a single byte of value 65), the master secret, the server random and the client random, in that order ('+' indeed denotes concatenation). This SHA-1 invocation yields 20 bytes. The concatenation of the master secret and the SHA-1 output is then hashed with MD5, which yields 16 bytes. These are the first 16 bytes of the key block.

For the second round, the processing is identical except that you use 'BB' instead of 'A' (two bytes of value 66 each). This produces the next 16 bytes of the key block.

You continue like this. Ultimately, you can potentially do 26 rounds (up to 'ZZZ...Z'; the SSL 3.0 specification does not define how to go beyond that). This would yield a total of 26*16 = 416 bytes. But if you need only the first 104 bytes, there is no need to compute the whole 26 rounds; just compute enough rounds to get the number of bytes you need.

Once you have your key block (104 bytes with 3DES and SHA-1), you split it into the needed key elements. The first 20 bytes go to the client write MAC key, the next 20 bytes for the server write MAC key, then the next 24 bytes for the client write key, and so on.