What are the security risks in making a passphrase-encrypted private key public? I have a 4096-bit GnuPG private key.  It currently resides at ~/.gnupg/secring.gpg.

The private key is passphrase protected.

Is it necessary to keep this private key hidden from public access?

Or, for convenience purposes, can I depend on passphrase protection, and put it somewhere that is not very secure (like a Git repository or a drop box) for ease of distribution to my various devices?

From the manual of GnuPG:

  To help safeguard your key, GnuPG does not store your raw private key on disk. Instead it encrypts it using a symmetric encryption algorithm. That is why you need a passphrase to access the key. Thus there are two barriers an attacker must cross to access your private key: (1) he must actually acquire the key, and (2) he must get past the encryption.

  [...]

  The motivation for trying passphrases is that most people choose a passphrase that is easier to guess than a random 128-bit key. If the passphrase is a word, it is much cheaper to try all the words in the dictionaries of the world's languages. Even if the word is permuted, e.g., k3wldood, it is still easier to try dictionary words with a catalog of permutations. The same problem applies to quotations. In general, passphrases based on natural-language utterances are poor passphrases since there is little randomness and lots of redundancy in natural language. You should avoid natural language passphrases if you can.

From here we have

  s2k-cipher-algo

  Name

  s2k-cipher-algo — use a specified algorithm as the symmetric cipher for encrypting private keys

s2k-cipher-algo name

  Description

  Use name as the symmetric cipher algorithm to protect private keys. Running the gpg with the command version yields a list of supported algorithms. The default cipher is Blowfish.

also

?> gpg2 --version
gpg (GnuPG) 2.1.11
libgcrypt 1.7.3-beta
Copyright (C) 2016 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Home: ~/.gnupg
Supported algorithms:
Pubkey: RSA, ELG, DSA, ECDH, ECDSA, EDDSA
Cipher: IDEA, 3DES, CAST5, BLOWFISH, AES, AES192, AES256, TWOFISH,
        CAMELLIA128, CAMELLIA192, CAMELLIA256
Hash: SHA1, RIPEMD160, SHA256, SHA384, SHA512, SHA224
Compression: Uncompressed, ZIP, ZLIB, BZIP2

TL;DR:

Sure, you can distribute your encrypted private key, but this defeat one of the two barriers mentioned in the manual (difficulty of access...)

The cipher used should be strong enough to guarantee the security of your key. However this will require you to use a really strong passphrase in order to avoid brute force and dictionary attacks.

Really TL;DR:

You can do it, but IT IS NOT ADVISED NOR RECOMMENDED. Your security will only rely on the strength of the passphrase that protect your secret key.


Choice of the one-way function (OWF) for Lamport signatures I am studying the Lamport signature scheme, and I found that in many sources (eg: Hash-based Digital Signature Schemes) the input and output bitstring of the OWF and the message digest have the same size, generally 256.

As the minimal requirement for the OWF is to be pre-image resistant, it seems that 128 bits for the output is "sufficient", this is explained in this discussion: Hash collision resistance requirements for Lamport signatures (basically the theoretical security is 119 bits in that case).

Questions

What about the input? Does a 128-bits input keep the security parameter?
If the answer is positive, what could be the most efficient OWF with 128 bits input -> 128 bits output in terms of implementation? Is there a block cipher (AES-128 ?) that would be more efficient than a cryptographic hash function, for the same level of security requirements?

(Q1) Assuming that you talk about the size of the secret key elements which equals the input size of the OWF when you talk about the "input", this should be at least as much as the output size.

Consider a function $f: \{0,1\}^m \rightarrow  \{0,1\}^n$.The thing to worry about when you choose $m < n$ is a brute force search for a preimage, which in this case takes about $2^m$ queries to $f$. The second thing is the collision probability, i.e. the probability of choosing the same value for two different secret key elements. As these are sampled from the uniform distribution, the probability for this is $2^{-m/2}$. Please note that this is a constant probability that an adversary cannot influence, so you are perfectly fine if this is, e.g., $2^{-64}$. Moreover, you can also let your implementation check that this doesn't happen. So, $m = n$ is perfectly fine.

Also, a $128$-bit output is fine as Lamport does only rely on the one-wayness of the "internal" hash function. However, as you mentioned, the hash function used to compress the message still needs collision resistance and hence has to be at least $256$-bit (or you use some kind of randomized hashing).

Summing up: For OWF $f: \{0,1\}^m \rightarrow  \{0,1\}^n$, $m = n = 128$ is fine for classical security (if you want security against quantum attackers you need to make it $256$ bit because of Grover's algorithm).

(Q2) Good question, as proposed in the XMSS paper, you can use AES and  the Matyas-Meyer-Oseas construction to build a $n$ to $n$ bit hash function. This works with any block cipher that has same key and block size. The advantage of AES is the available hardware acceleration on many different platforms, incl. modern general purpose CPUs and many smartcard micro controllers.


PKCS1 signing not recommended? Daniel Roesler's personal page has a live examples table for WebCrypto support.
https://diafygi.github.io/webcrypto-examples/

Without explination he marks several as "Discouraged! Only use for backwards compatibility!". Two of them i am using in my application are RSA-OAEP for encryption, RSASSA-PKCS1-v1_5 for signing. As far as I know they are not broken.

On the other hand ECDSA and HMAC are recommended by him for signing.

Why is no RSA method recommended for encrypting?

So can someone please help me understand the reasoning for marking these methods the way they are?

Is it just that, for example, elliptic curves produce smaller key sizes for the same level of security?

or about potential for missus, or browser implementation?

Well, you are as surprised as I believe most of us are...

AES-CTR and AES-CBC are "obsolete", whilst AES-CTR is used by AES-GCM. Okay, so maybe he recommends authenticated modes (which don't require making your own authentication). But those aren't obsolete, they are just harder to code properly...
DH and all variants of RSA are "obsolete". Only ECDSA and ECDH... There are many  asymmetric algorithms that showed up which are meant to replace RSA, but RSA isn't obsolete and will probably remain huge until quantum computers.
HKDF-CTR is "obsolete". Should we use PBKDF2 which is designed for passwords and not keys?
RSASSA-PKCS1-v1_5 is kind of a problematic choice. Many people still use it, but I believe moving to OAEP and PSS is better in long run. Of course this doesn't mean "obsolete", at most "unrecommended".

All in all, I think "obsolete" isn't correct word. More like: Algorithms that newbies shouldn't use because they aren't obvious what they do. Of course then we should throw in AES-KW and ECDH, because those both are rather not obvious. I think person who created this site wanted to give "best recommendations", but deprecating HKDF-CTR is questionable at least.

TL;DR: This isn't by any means correct, except for SHA-1.


Which is the better way of generating a salt string? Using T-SQL as per the snippets below, which method is superior (or is it a tie)?
 -- method 1: DIY
 SET @Salt = ''
 WHILE LEN(@Salt) < 72
 BEGIN
   SET @Salt = @Salt + CHAR(CONVERT(INT, Floor(RAND() * (126.0 - 33 + 1) + 33)))
 END

 -- method 2: concatenating 2 GUIDs
 SET @Salt = CONVERT(VARCHAR(36), NEWID()) + CONVERT(VARCHAR(36), NEWID())```

Neither. The RAND function in method 1 isn't cryptographically random; the GUID generation is only random with version 4, and isn't guaranteed to be of cryptographic quality.


Could a good PRNG have a long period? I'm thinking about the evaluation of a cipher or separate cipher round as a PRNG. In general, we can encrypt consecutive natural numbers and check them with some randomness test. But PRNGs don't work like this. They use their output like a new input.
Shouldn't it be like that the ciphers should have long periods in such a test? Do they have long periods? If not, they should not be considered good PRNGs, correct?  And is it possible that a cryptographically secure PRNG will have a short period for some inputs?

They use their output like a new input.

That's not correct, generally CS-PRNG's keep a state and use separate bits (or possibly the state run through a PRF) as output.

Shouldn't it be like that the ciphers should have long periods in such a test?

Yes, and the same goes for the CS-PRNG's. Yes, if you can trigger a CS-PRNG to repeat a long enough pattern then something is wrong. There are many other reasons why a PRNG is broken of course. It may be biased or how an attacker could get the state back, for instance. Beware that a cipher is not necessarily a CS-PRNG.

And is it possible that cryptographically secure PRNG will have short period for some inputs?

When correctly seeded they should have unpredictable output. If you can seed according to the specifications and it is still computationally feasible to get into a cycle then no, then it would not be cryptographically secure.
Generally you should not get repeated output as long as the seed is unique. Secure hash functions are often used to accomplish this.


Does having a hash of the plaintext compromise the ciphertext? If I have a SHA512 hash of my plaintext, does it weaken or break the encryption of my ciphertext?

Yes, having a hash of the plaintext available weakens the security of your encryption scheme.

Semantically secure encryption schemes have the guarantee that ciphertexts should be indistinguishible, regardless of what plaintext is encrypted. Clearly hashes do not have this property, since they're deterministic for each plaintext.

Assuming that messages are not randomly chosen, an adversary can guess messages, hash them, and check whether or not the hash is correct in order to learn the plaintext for the ciphertext. With only access to the ciphertext, but not a hash of the plaintext, this would be impossible, since a semantically secure encryption scheme does not allow an attacker to guess the plaintext for a ciphertext, as ciphertexts appear to be completely random with respect to the plaintext. The confidentiality guarantee of your system should only rely on the randomness and size of the key used, and not on the randomness of the plaintext, so this scheme is insecure if a hash is provided.

As for whether or not it allows the attacker to generate the key, that depends on the security guarantees of your encryption. As long as the encryption scheme is CPA secure (which is pretty much the weakest level of security that's "acceptable" for an encryption scheme), then one can't recover the key from plaintext and ciphertext.


Signature with appendix I see sometimes signatures schemes with appendix. This is about signatures schemes in which the message is needed in the verification algorithm, that is, the ouput of the signature algorithm is of the form $(M,s)$

The appendix is referred to the message or the signature ?

Thank you.

In a signature scheme with appendix (such as RSASSA-PSS), the signature $s=\operatorname{Sign}(M,\text{PrivateKey})$ of the message $M$ is usually appended to the unmodified message $M$, forming $(M,s)$ or $M\mathbin\|s$. This is effectively sent, and verified; the signature is an appendix to the message.

Signature scheme with appendix opposes to signature scheme with message recovery (such as ISO/IEC 9796-2). In the later kind, all or some of the message is embedded in the signature. When all of the message is embedded, the verification procedure requires only $s=\operatorname{Sign}(M,\text{PrivateKey})$ as input, and recovers $M$ as a by-product (that's known as total message recovery). Only the signature is sent; it embeds the message.

In the case of RSA, signature schemes with message recovery provide significant bandwidth or space saving for signed messages about the size of the public key used, including public key certificates; that's why they are common in the field of Smart Cards.


CBC-MAC using predictable IV Imagine you have a string of plaintext (a), IV (ai) and the MAC (am) for the plaintext (a).

How can you generate a MAC (bm) for a different string of plaintext (b) - using an IV (ib) of your choice, using the same key - which you don't know and can't retrieve.

You can also assume both plaintexts are the same length.

  Edit: I have found this question which I think provides a clue: CBC-MAC insecure with random IV

  But I'm not sure if I understand correctly. You can also assume your
  plaintexts are one-block plaintexts.

This should prove that cbc-mac with random IV is insecure.

Thank you.

You're saying we're looking at messages of length one block and a variant of CBC-MAC that uses a random IV. (I'm assuming we're looking at CBC-MAC for fixed length messages, i.e. we can ignore padding issues.) Then we have
$$am:=(ai,E(k,a\oplus ai))$$
To forge a MAC for message $b$ we can reuse the second part of the tag if we choose $bi$ such that $$b \oplus bi = a \oplus ai$$$$ \implies bi = a\oplus ai \oplus b$$

I.e., given $a$ and $am=(ai,t)$ simply output $bm=(a\oplus ai \oplus b,t)$.


Encryption with 2 symmetric keys and decryption with one key Here is my use case:
I need to keep encrypted data in Hadoop. The data is encrypted with symmetric key that is being changed every half a year.
When data is retrieved it should be decrypted.

Lets say that data from 1/1/19 until 6/30/19 is encrypted with key1, and data from 7/1/19 until 12/31/19 is encrypted with key2.
The issue is that if I retrieve data from 5/30/19 to 7/30/19 I need to decrypt half of the data with key1 and half of the data with key2.

So I am looking for a solution that, for any query with a year time range, will enable to decrypt with a single key.

One solution I was thinking of is to encrypt the data with 2 keys (key1 AND key2) and decrypt it with any of the keys (key1 OR key2). Is is possible?

One solution I was thinking of is to encrypt the data with 2 keys (key1 AND key2) and decrypt it with any of the keys (key1 OR key2). Is is possible?

The immediately obvious way is, when you want to encrypt a record $M$, you select a random key $r$, and generate $Encr_{key1}(r), Encr_{key2}(r), Encr_r(M)$

The decryption process is obvious, using the $key_i$ you have, you recover $r$, and then use that key to decrypt the actual record.

Is there any reason this scheme doesn't solve your problem?


On the security definition of password-authenticated key exchange I found in all PAKE papers, the security is defined as something like this:

Let $Succ(A)$ be the probability that an attacker $A$ successfully distinguished the session key from a random string. Then the advantage of $A$ is $Adv(A) = 2 \times Succ(A)-1$.
Then a PAKE protocol is secure if $Adv(A) \leq n_{se}/|PW| + neg$. where $n_{se}$ is the number of queries made by the attacker, and $|PW|$ is the size of the password dictionary.

From this definition, it seems that the session key is semantically secure only if $|PW|$ is large enough to make $n_{se}/|PW|$ negligible. Does this contradict the definition of PAKE that supports low-entropy passwords? I mean if |PW| is small, then the session key generated by PAKE is not indistinguishable from a random key, so we cannot use it for encryption and so on, isn't it?

Let's approach the question from this direction.

PAKE tries to solve this problem: Alice has a password $PW_{a}$, and Bob has a password $PW_{b}$; consider a protocol where Alice and Bob exchange messages, and generate encryption keys $E_{a}, E_{b}$ where $E_{a} = E_{b}$ if $PW_a = PW_b$ (and unrelated if $PW_a \ne PW_b$); if they're the same, Alice and Bob can use the common key to protect traffic.

In this scenario, one thing that an attacker Eve can do is pretend to be Alice, create a guess at the password $PW'$, and then run through the protocol with Bob (who knows the real password); if Eve picked the same password as Bob ($PW' = PW_b$), she knows her guess at the password was correct.

This (and the obvious related one where Eve pretends to be Bob) are inherent within the scenario; what a PAKE attempts to do is ensure that there is no significantly better attack; that going through the plausible passwords, and trying them one-by-one is about Eve's best option.

The formalism $Adv(A) \leq n_{se}/|PW| + neg$ attempts to capture this idea in a manner that we can make mathematical statements about; if Eve gets $n_{se}$ attempts, and she knows the size of the dictionary $|PW|$ of possible passwords, she can try $n_{se}$ entries with her attempts, and succeed with probability $n_{se} / |PW|$ (assuming that each entry in the password is equiprobable); the $neg$ term is there because no real protocol can actually achieve this.

What does this mean to you?  If the risk that an attacker might guess the password successfully is too high for you, then yes, a PAKE in not applicable; you'll need to find some other authentication method that relies on something stronger than a low entropy secret.


Limitations of boolean and arithmetic circuits Much of modern cryptography is based around working with boolean or arithmetic circuits. For example in Multi-Party Computation the 'famous' results allow for the secure computation of any function that can be represented as a boolean or arithmetic circuit.

I am wondering what the limits of these circuits are, what are some examples of functions are we not able to compute securely --- that is what functions are not representable as a boolean or arithmetic circuit? And in the real world does this reduce the effectiveness of modern cryptography or are these circuits enough to implement everything we require?

The question should be which functions can we build a small circuit to solve. Any function mapping a fixed number of bits to a fixed output can be represented as a boolean circuit. But it may be very large.
This brings is to a difficult topic with few lower bounds: https://en.m.wikipedia.org/wiki/Circuit_complexity


What is meant by domain separation in the context of KDF? This is a quote from my cryptography notes:

If $h$ is a random function oracle of output length $n$ then also the two KDF constructions:
$K(x) = h([0] \| x) \ldots \| h([L] \| x)$
$K(x) = h(x \| [0] ) \ldots \| h(x \| [L])$
yield random function oracles of otput length $L \cdot n$.

They call this property domain separation. What does this property mean? Can it  be applied to only this setting or is it more general? What about the proof of this quote, is it inmediate?

With KDFs, you need domain separation when you use the same initial key material to generate keys for different purposes like using the same initial key material and nonce to generate encryption and signing keys, you provide the KDF some data about the domain (encryption or signing) so it can generate different (private) keys. eg. for HKDF there is an info parameter that can be used for domain separation, see here.

Domain separation is a broader concept and also applies when the same hash function for hashing different kinds of data in a system, so if you wanted to hash say user id and user account balance using the same hash function, you will use different domain separators like user-id (assuming user-id is numeric) and user-bal. Another common example is hashing leaves and non-leaves in a Merkle tree, see here for more details.


How long would it take to brute force a 32 or 16 bit integer and which type of processor would brute force this in the shortest period of time I was actually wondering... How long would it take to crack/brute force a 32 bit key/encryption and a 16 bit key/encryptions respectively on a 4GHZ and a 2GHZ PC. I know that a 32 bit integer has 4,294,967,296 combinations while a 16 bit number has exactly 65,536 combinations but I don't know how long It'll take. and what processor would be able to brute force this in the shortest period of time

$4,294,967,296ops/4,000,000,000ops/s=1.07s$
$65,535ops/4,000,000,000ops/s=16.4μs$
2GHz twice that.
That's per-core. So 8 cores = 1/8 of a second or so. 64-core/128 thread 2GHz Threadripper = about 16ms.
A GPU will be even faster. It's recommended to brute force the entire 2^32 space for testing various numerical functions, it's fast and catches all the edge cases you might not have thought about. Brute forcing 2^64 values takes a month or so on a fast GPU, easily doable faster on a GPU cluster.
Edit, thanks to kelalaka: a Tesla V100 can run about $2^{47}$ SHA-1 hashes/hour. SO $720hours/month\times2^{47}Hashes/hour\approx2^{56}Hash/month$. That's about 182 months total, but each hash is substantially more work than just incrementing an integer, so a faster operation can likely be brute-forced in a month on such a GPU. Slower operations need a cluster, but such clusters can be rented from various cloud providers.


What is the use of SCRAM-SHA-256 (over SCRAM-SHA-1)? The Salted Challenge Response Authentication Mechanism (SCRAM) specified in RFC 5802 can use arbitrary hash functions to operate. The base version from RFC 5802 uses SHA-1.

From my understanding, SCRAM solely relies on the one-way-ness of the function. It does not need collision resistance. It uses extensive salting and possibly many iterations, as well as a clever nonce-based mechanism to thwart replays.

In a discussion about which SCRAM version to recommend, somebody asked why SCRAM-SHA-256 (RFC 7677) should be used at all (even why it was even specified); aren’t the improved security properties of SHA-256 over SHA-1 irrelevant for the SCRAM use-case? Is this simply future-proofing?

RFC 7677 states in the Security Considerations:

  See [RFC4270] and [RFC6194] for reasons to move from SHA-1 to a
     strong security mechanism like SHA-256.

RFC 6194 has the following:

  3.  SHA-1 Security Considerations

  [collision resistance and pre-image considerations for SHA-1]

  3.3.  HMAC-SHA-1

  As of today, there is no indication that attacks on SHA-1 can be
     extended to HMAC-SHA-1.

Note that SCRAM uses the hash function mostly in an HMAC construct; the only exception is StoredKey := H(ClientKey), but StoredKey is never transmitted over the wire and only used as key in an HMAC round. However, StoredKey is stored on the server. I don’t think that a pre-image to StoredKey would be useful, because in the protocol one needs both StoredKey and ClientKey to form the ClientProof.

RFC 4270 is less specific about the hash functions and talks in more generality about how they are used in the IETF protocols and how the attacks affect those uses.

From what I can tell, we can consider two uses of the hash function in SCRAM-SHA-1: 1. The obfuscation of the password through PBKDF2 with HMAC-SHA-1 as pseudo-random function, 2. challenge/response mechanism using HMAC-SHA-1.

Both uses are not mentioned as problematic in RFC 4270, AFAICT.

So to summarize, from what I have gathered:

SCRAM-SHA-256 uses a more expensive algorithm, without apparent security benefits
migration from SCRAM-SHA-1 to SCRAM-SHA-256 is difficult (requires a password change -> user interaction)

So... From that, the only use for SCRAM-SHA-256 seems to be new deployments and future-proofing, is that right? Is there a conceivable weakness of SCRAM-SHA-1 which outweighs the loss of interoperability when moving to or deploying SCRAM-SHA-256?

Nobody should use a primitive which is known to be broken in any new development or deployment. Anything involving SHA-1 is basically deprecated at this point.

A break in collision-resistance is a crack that might be exploited further by follow-on research; this happened with other hash functions in the past. Attacks only get better, they never get worse.

Besides, SCRAM-SHA-1 really isn’t deployed widely enough  for interoperability to matter.


flaw in perfect secrecy of shift cipher? Why do we say shift cipher is perfectly secure when it is easy to break it (source)?
Let's say I have a plaintext.
"Australia is a big country";
I encrypt it using a shift of 2;
That ciphertext can be broken using brute force search over 26 numbers.

What you're referring to with "using a shift of 2" is in fact called a Caesar cipher and is not secure. You correctly pointed out, that it can easily be broken if you brute force the 26 possibilities.

But what the author is referring to is a so-called one-time pad (as described on page 78). It has the property of information-theoretic security.

The caesar-cipher can easily be brute forced to the original message, but on the other hand, OTP can be decrypted to any message of the same length. If we don't know any information about the message space then all keys are probable.


Converting Ciphertext to a Number in RSA I've been looking into RSA and the attacks against weak implementations of it, such as when $e$ is small and there's no padding. On Wikipedia, the following attack is outlined for small $e$ values:

  When encrypting with low encryption exponents (e.g., $e = 3$) and small values of the $m$, (i.e., $m < n^{1/e}$) the result of $m^e$ is strictly less than the modulus $n$. In this case, ciphertexts can be easily decrypted by taking the $e^\text{th}$ root of the ciphertext over the integers.

What I'm confused about here though is how do you carry out mathematical operations on ciphertext? I'm aware that all characters have numerical values, but what I'm unsure on is do you construct a single number from a whole ciphertext as you would for plain text to be encrypted (ie, convert each character to an integer then construct the number with the rightmost digit being most significant) and then carry out the operation on this number, or do you act on each individual number in the ciphertext? If it's the former, how do you determine to reconstruct the single number into a sequence of numbers that create the original plain text?

The ciphertext of RSA is actually just a number in the range 0..N that has been encoded to an octet string (another name for byte array) of the same size as the minimum modulus N. To be precise, the ciphertext is an unsigned, statically sized, big endian integer.

The PKCS#1 standard defines it this way, both for PKCS#1 as well as OAEP padding:

  Convert the ciphertext representative c to a ciphertext C of
          length k octets (see Section 4.1):

  C = I2OSP (c, k).

Where I2OSP - integer to octet string primitive - is defined here. I2OSP is just a mathematical way of defining how the number is encoded as described in the first section of the answer. Stupid implementations actually perform these kinds of calculations, most implementations require some resizing / reversing (in case little endian is used internally) and smart implementations already keep the numbers in the correct format in memory.

Now for textbook RSA, you can, of course, argue that pointing to the PKCS#1 specification is unfair because textbook RSA is not defined in that standard, and textbook RSA isn't required to follow the conventions specified in it. However, the fact that the ciphertext is just an encoded number remains. Sometimes the minimum length and / or little endian encoding is returned and of course, some implementations will simply return the number without performing encoding at all. However, in all cases, it should be easy to get the numeric value of the ciphertext - which is just the result of modular exponentiation with the public exponent after all.

Note that many languages - notably the C language - unfortunately handle bytes and characters as being the same type; they are not. The bytes generated by encoding a number can have any value and may not be printable. If you need a printable text that contains these bytes you will have to encode the bytes to a string, e.g. base 64 or hexadecimal encoding. Some libraries allow you to specify this as output size, and some bad ones even default to performing an encoding over the ciphertext bytes. To convert those back you need to first decode back into bytes and then perform the bytes-to-number conversion.

Despite the possible output values, you should never ever have to perform calculations on the individual bytes unless you cannot load any kind of library that does this for you and you will have to define your BigNum yourself (and yes, I have been there). Usually the cryptographic libraries themselves contain this kind of library; they need the functionality after all. They are quite often in the "hazmat" part of the library or not directly present in the API however.


Safety of having many passwords hashed with the same salt? I'm working on a web application where passwords must be hashed on the client before it can be send to the server. This is because the user's raw password is used for cryptography purposes and can't be sent anywhere.

My initial thought was to use a SHA algorithm, but then I was wondering if maybe using something like argon2 would be better. Because I have to validate the password on the server without having access to the raw password, I have to use the same salt when using Argon2.

Note that I will properly hash the client-side hashed password on the server again before saving it into the database. But the server will have access to the passwords directly from the client, so in case the server gets hacked and they change the code, they still won't have access to the raw password.

So my questions:

Is having access to many passwords that are hashed with the same salt a security issue?
Is using a SHA algorithm (like SHA-512) better in this case?

To answer your explicit questions:

Hashing many passwords with the same salt is definitely a security issue. The whole point of a salt is to never hash different passwords¹ with the same salt.
When passwords are involved, there is no way that a SHA algorithm can be more suitable than a password hashing algorithm such as Bcrypt or Argon2. Despite the similarity of names, hashing algorithms and password hashing algorithms have very different properties. Recommended background reading: How to securely hash passwords?

Now, on to your system design. It's difficult to tell exactly what you're doing, but there's probably something you need to change in your design. It may not need to be a drastic change, probably just making some changes to how you use the password and what information gets transmitted between the client and the server.

The salt needs to be unique, but it doesn't need to be secret. If the server needs to make a calculation involving the salt, either the salt should be stored in the server's database or the client should send the salt to the server.

  The user's raw password is used for cryptography purposes

A password can't² be directly used for any cryptography purposes, for the same reason a cryptography hash can't be used for passwords. To turn a password into something that can be used for cryptography, such as a key, you need to apply a key stretching algorithm to the password.

Key stretching and password hashing are very similar. In fact, you can take a password hashing function with a suitably long output, split that output in two, and use one half as a key and the other half as a password hash. Knowing one of the halves of the output, you can't find the other half (unless you manage to guess the original password). You need to be very careful not to mix those two halves!

¹  By “different passwords”, I mean passwords for different accounts, or successive passwords for the same account. I'm not referring to whether the passwords happen to be identical character string.
²  “Can't” meaning “your program may work but it will be grossly insecure”.


SPDZ protocol: how expensive is it to generate the multiplicative triples? I am currently reading the full version of the SPDZ protocol. I understand that the online phase does multiplication with computational and communication complexity $O(n)$ by using Beaver's multiplicative triples as explained $\Pi_{Online}$ (Fig 1, page 5). These triples are numbers $a$,$b$ and $c$ such that $ab=c$, where $a$ and $b$ are random. These triples are generated in the preprocessing phase, as explained in protocol $\Pi_{Prep}$ (Fig 7, page 13) which depends on protocol $\Pi_{Reshare}$ (Fig 4, page 12), to decrypt the value of $c$ and distribute its shares among the players.

$\Pi_{Reshare}$ uses $F_{KeyGenDec}$ to decrypt $e_{m+f}$ to obtain $m+f$. $F_x$ in the paper represents some ideal functionality $x$, and typically there is a protocol, $\Pi_x$ that implements that functionality. In Definition 1, on page 10, they mention that such an implementation $\Pi_{KeyGenDec}$ is required for the cryptosystem. However, I was not able to find the implementation of this KeyGenDec functionality in the paper (including appendices).

Where could I find an implementation of KeyGenDec? How long does this protocol take to run? Is this the bottleneck in the time required to generate the triples?

The answer to your question can be found in a SPDZ follow up paper; it is described as contribution (2) in the intro (top of page 2).

There is a new version of SPDZ called MASCOT that uses OT instead of somewhat homomorphic encryption, and is supposed to be about 200 times faster. So, I would recommend looking at that as well.


When would you increment a nonce and when not? K is the shared key for encryption known by _Alice and _Bob. $N_A$ is a nonce created by Alice. The function f is the increment by 1 function.
(1) Alice -> Bob: $E_K(N_A)$
So Alice encrypts a nonce with the shared key and sends it to Bob.
(2) Bob -> Alice: $E_K(f(N_A))$
Bob receives it, I think first he needs to decrypt it, then increment it by 1, encrypts it again and then send it back to Alice.
The question is now, when and why would you use this use-case? What could be the scenario for these two steps?
I have seen these two steps for example in the Needham–Schroeder protocol, but I did not understand why they need these two.
My only idea is that Bob authenticates himself to Alice, because if Alice later decrypts it, Alice will see whether Bob was able to decrypt it. But why would you need to increment the nonce?

UPDATE: As my idea seems to be right according to otus, I have to ask for another use-case I've seen:
(1) Alice -> Bob: $N_A$
Alice sends the plain nonce to Bob.
(2) Bob -> Alice: $E_K(N_A)$
Bob encrypts it with the shared key and sends it back to Alice.
For this second use-case I was pretty sure that my idea for the first use-case would be right -> Just to authenticate Bob. So I thought the use-case with the increment function is for something else.
So are these two use-cases for the same purpose? Just to authenticate Bob to Alice? What is the difference between them? When would you apply which of these two and why?

My only idea is that B authenticates himself to A, because if A later decrypts it, A will see whether B was able to decrypt it. But why would you need to increment the nonce?

Correct, that's the idea.

If B didn't need to increment the nonce and just encrypted the same value, the message sent back would be the same that A sent, so an attacker would be able respond correctly without knowing how to decrypt it.

There are other ways to accomplish the same in other protocols that do not use increments. For example, B could encrypt it with another shared key.

  So are these two use-cases for the same purpose? Just to authenticate Bob to Alice? What is the difference between them? When would you apply which of these two and why?

In terms of authentication there is no real difference. They both prove to Alice that Bob has the correct key.

The one with encryption and increment is slightly less efficient, due to requiring both parties to encrypt and decrypt the values. However, it has the advantage of not allowing an attacker to directly ask for encryptions of chosen plaintexts, with which they could attack other uses of the same key. This is not necessarily a problem if the key is only used for authentication, but in the case of Needham–Schroeder the objective is to establish a session key.


How many primitive cryptography operations are there? Every cipher I've encountered seems to be built from slight variations of only three basic operations: the S-box, the P-box, and the XOR.  I’m just wondering, are there any others?  And if there aren't (keep in mind I'm not counting XNOR here, since it's semantically the same as XOR), is there any way to prove that those three operations are the only ones that have the desired entropy properties needed for cryptography?

Actually the list is large.  You're only describing the old stalwarts that have been around for donkey's years in say DES. Substitution and permutation form what is termed confusion and diffusion. These aren't always required as there are alternatives.  Your sentence regarding entropy as a function is inaccurate as in cryptography the entropy is external to the primitive, eg. in a key or password.

If you consider all primitives and not just ciphers, Keccak hash uses a quite elegant permutation of bits in it's $\pi$ permutation which isn't   like a traditional P box as it does not distribute active bits between multiple S boxes.  Whirlpool hash uses Galois field multiplication to achieve diffusion, as does Rijndael /AES.

Stream ciphers operate differently, and a stream of pseudo random numbers are used.  ISAAC and RC4 are examples that use various array transpositions /indirections and bitwise rotations. I guess if you had a lot of time, Blum Blum Shub could be seeded to product a (slow) cipher stream of pseudo random numbers that is based upon prime multiplication and quadratic residues.

If you then expand the scope to asymmetric techniques, that are all manner of other mathematically hard trap door problems that can be used in things like lattice and elliptic curve cryptography, key exchange etc.

There are even alternatives to XOR, such as modular addition used in Speck. Speck also extensively features the bit rotate operator.

So you see that the list is longer than you thought, and I've only included a few of the operations that underpin cryptography.  I hope that by listing these, it's proved by deduction that S and P boxes and XOR are not the only tools.


Given a SHA-256 message block, is it possible to undo the transformation of the internal state? Consider the transformation described in section 6.2 of RFC4634 ("US Secure Hash Algorithms (SHA and HMAC-SHA)"). Given the message block M(i), and hence the message schedule W, as well as the output of the block function H(i), how hard should I expect computing H(i-1) to be?

Interestingly, the 64 "rounds" are easily reversible for this set of knowns and unknowns, but the final addition makes using this fact not trivial.

No, this 'unappend' operation is effectively infeasible for the SHA-256 hash compression operation; there is no known way that is less expensive than brute force.

Such an 'unappend' operation would reduce the time taken to generate preimages from $2^{256}$ to $2^{129}$ hash compression operations (assuming that the unappend operation is as cheap as the forward hash compression operation).  This would be done via a meet-in-the-middle attack, where in the most straight-forward implementation, you generate one list of $2^{128}$ intermediate states (from $2^{128}$ prefixes), and you generate a second list of $2^{128}$ intermediate states (from $2^{128}$ postfixes; starting from the target hash, you use the unappend operation), and search for a common value in the two lists.


MAC unforgeability and secret key guessing The standard notion security for MACs is usually expressed by means of experiments like the following one (given an attacker A):

$k  \leftarrow \mathsf{KG}(1^\lambda)$
Invoke $A^{\mathsf{TAG}_k(\cdot),\mathsf{VRFY}_k(\cdot,\cdot)}$
Output $1$ if $A$ queried $(m^*,\tau^*)$ to $\mathsf{VRFY}_k(\cdot,\cdot)$ s.t.  $\mathsf{VRFY}_k(m^*,\tau^*) = \mathsf{Accept}$ and $A$ didn't receive $\tau^*$ by querying  $m^*$ to $\mathsf{TAG}_k(\cdot)$

Now consider the following variation to point 3:
Output $1$ if $A$ gives $k'$ s.t. $k=k'$

How could I prove that a MAC unforgeable according to the first game is unforgeable according to the second game too? Is there a specific $\mathsf{MAC}(\mathsf{KG},\mathsf{TAG},\mathsf{VRFY})$ that is unforgeable according to the second game, but not according to the first one?

I was going to make this a comment; however you asked for hint, and these are hints.

Suppose you had an Oracle that solved the second game for you; how could you use that Oracle to solve the first game?

Does that imply that a MAC where the first game is unsolvable imply that the second game is also unsolvable?


Why can we always assume that $Gen$ algorithm choose key uniformly? Disclaimer: This is exercise 2.1 in Katz-Lindell book.

Given a (symmetric) encryption scheme $\Pi=(Gen,Enc,Dec)$ where $Gen$ takes the security parameter $1^n$ as input and generates a key $k$ of length $n$.

Usually we simply assume that $Gen$ chooses key uniformly from $\{0,1\}^n$ but this is not always the case.

Given $Gen$, how would you construct a new generation algorithm $Gen'$ that indeed outputs $k$ uniformly at random?

Are you trying to prove this for a specific encryption scheme or for any scheme?

If you have a specific scheme in mind, you can consider using rejection sampling.
In your case, it would be quite straightforward to use :

Let's say each key $k\in \{0,1\}^n$ is output by $Gen$ with a probability $p(k)$, and $p_{min} \overset{def}{=} \min\limits_{k} p(k)$.
You can then define $GenU(1^n)$ per example like this :

$GenU(1^n):$

1) $k \leftarrow Gen(1^n)$

2) With probability $p_{min}/p(k)$, output $k$, otherwise restart

You can see that an iteration of $GenU$ outputs each $k$ with probability $p_{min}$, and terminates ($ie$ does not restart) with probability $\sum_{k} p_{min} = 2^n\cdot p_{min}$.

Now, this algorithm assumes that you can efficiently compute each $p(k)$. Moreover, if $p_{min}$ is much smaller than the other values of $p(k)$, then $GenU$ may take an impractical amount of time to terminate ($eg$ if $p_{min} = 2^{-2n}$, then an iteration $GenU$ will terminate with probability $2^{-n}$).

For these reasons, if you want to prove your proposition in the general case, you cannot apply this algorithm as it is. Hope it helps though.


Could Diffie-Hellman protocol serve as a zero-knowledge proof of knowledge of discrete logarithm? The Schnorr identification protocol is widely recognized as the simplest ZKPoK of the discrete logarithm (more clearly, Honest-Verifier ZKPoK).

However, I can't figure out why this simple protocol, which is actually just a Diffie-Hellman key establishment protocol, is not an HVZKPoK also
(I understand that if it would be the case, I would see it everywhere in literature as an example of HVZKPoK).

Common input: generator $g$ of group $G$;

Prover's input: secret random $x$, and $y=g^x$;

Verifier's input: $y$;

Verifier is getting proof that the prover knows $x$ so that $y=g^x$ in 2-steps protocol:

Verifier $V$ selects randomly $k$, and sends $v = g^k$ to the prover.
Prover evaluates $r = v^x$ and sends it to the verifier.
Verifier accepts iff $r = y^k$.

Completeness of this protocol is obvious.
Soundness is based on the assumption of hardness of Diffie-Hellman problem.

Honest-verifier zero-knowledgeness seems easy to show: in order to simulate correct transcripts, simulator just selects random $k$, and outputs $(g^k, y^k)$ as a valid transcript.

Could you point me to a mistake in my logic, or assert that this protocol is correct HVZKPoK (in the latter case, why it's not preferred than Schnorr one).

This is an interesting question. In fact, cryptographers have been using this exact protocol on many occasions, and there are two important reasons to prefer Schnorr over this protocol in most situations.

The soundness of the protocol is not based on the Diffie-Hellman problem.

This is probably the most important point to address. What does it mean for this protocol to be sound? Informally, soundness can deal with two types of statements: you might want to prove membership in a language, or (this is stronger) you might want to prove knowledge of a witness. An example of the first statement could be "I claim that $(g,h,u,v)$ is a DDH-tuple", while an example of the second statement can be "I know the discrete logarithm of $y$ in base $g$".

Let's go back to your protocol now: you should be easily convinced that it cannot be expressed as a statement related to membership to some language: this would be a trivial statement (think "$y$ does have a discrete log in base $g$": if $g$ is a generator, this is always trivially true). What you truly care about is showing that the prover does know the discrete log of $y$ in base $g$. Formally, I know a witness is defined in cryptography as the witness can be efficiently learned from me, or more precisely: there exists a polynomial-time extractor that, given the code of the prover, can extract a valid witness from the code.

Now, how would you do that with your protocol? With Schnorr's protocol, it's fairly easy: given the code of the prover, run it to get the first flow $g^r$, then put a breakpoint, fork it, and run it twice on two different challenges $e,e'$ from the verifier. You get back two answers $d,d'$ which satisfy (with non-negligible probability) the verification equation: $y^e\cdot g^r = g^d$ and $y^{e'}\cdot g^r = g^{d'}$. From the two equations, you easily get $g^{(d-d')\cdot (e-e')^{-1}} = y$ (assuming you have a prime order group), hence you've just extracted the witness $x = (d-d')\cdot (e-e')^{-1}$.

I would suggest that you spend a minute or two convincing yourself that there is no clear way to do the same thing with your protocol. Given the code of the prover, it is not clear at all how one would extract $x$.

But now, this is unsatisfying, right? Intuitively, it seems clear that the only way for the prover to answer correctly the challenge of the verifier in your protocol is by knowing $x$. This seems obvious, but we cannot prove it. This issue has been acknowledge long ago in the crypto community - it was first identified by Damgård in this paper, published in 1991. The best cryptographers could do was to formalize this belief in the form of an assumption, which is called the Knowledge-of-Exponent Assumption (KEA). This assumption states exactly that our intuition must be right: "for any polytime algorithm A that successfully replies (with good probability) with $y^k$ given as input $g^k$, there exists a polytime extractor that, given the code of A, outputs $x$ such that $g^x = y$."

Assumptions of this style are now widely used in cryptography - for example, very similar assumptions are at the core of SNARGs and SNARKs, which have gained a widespread attention due to their efficiency and their use in anonymous cryptocurrencies. Still, they are weird assumptions. For one thing, they are not even falsifiable: to break the factorization assumption, just give me a polytime algorithm that factors number, and I can easily check that it works. But for KEA, it's not even clear how one could verify that you have broken the assumption - this cannot just be an efficient algorithm, it has to be somehow an algorithm, together with a convincing argument that no extractor can exist for this algorithm.

Getting back to your protocol, then: it is believed to be sound, but only under the KEA assumption (tautologically). This is a weird and not well understood assumption. It does not even come close to being comparable to the Diffie-Hellman assumption, it's just a strange object in itself. In comparison, note that the soundness of Schnorr's protocol is just unconditional. Not based on a weird assumption, but also not even based on an assumption at all.

The protocol is only HVZK, not ZK, and it is not clear how to make it ZK

Before moving on with this point, a quick digression: a simple modification of your protocol can be used to prove that a tuple is a DDH tuple (meaning: fix generators $(g,h)$, and now the prover wants to demonstrate that some pair $(u,v)$ is of the form $(g^x,h^x)$). Proving DDH relations is widely used in crypto. But unlike your protocol, we can now be happy with a membership proof: in most situations, it suffices to show that the witness $x$ exist (it's a non-trivial relation), no need to show that the prover knows it. So, suppose you modify your protocol as follows:

Verifier: send $g^{k_1}\cdot h^{k_2} = w$

Prover: answer with $z = w^x$

Verifier: check that $u^{k_1}\cdot v^{k_2} = z$

Then, interestingly, the previous issue disappears entirely: although it would still require KEA to prove that the prover must know $x$, it does not require any assumption at all to prove that $x$ exists, and this suffices to show that $(u,v)$ is a DDH tuple! In other words: in appropriate settings, for a slightly different language, a variant of your protocol does actually not have any problem with soundness anymore. So, why do we still not use it often?

This has to do with zero-knowledge. As you correctly pointed out, your protocol (and the variant above) satisfies honest-verifier zero-knowledge (as does Schnorr's protocol), meaning that it is zero-knowledge as long as the verifier is honest.

Sure, but why do we even care about HVZK? In practice, we are not really happy with something being secure only when the opponent is honest, right? The answer is that what we truly care about is indeed full-fledged ZK, but HVZK is often a good first step: we know very general and very efficient transformations that can convert a large class of HVZK protocols into full-fledged ZK protocol. Hence, we can just build HVZK protocols, prove that they satisfy this property, and they can be compiled into real ZK protocols when needed.

What is this large class of HVZK protocols that we can transform efficiently into ZK protocols? They are the so-called public coin protocols: all protocols in which all the randomness used by the verifier is fully revealed to the prover. Take one minute to convince yourself that this property is satisfied by Schnorr's protocol (and by essentially any HVZK protocol in the literature, up to a few exceptions), but not by your protocol. This means that even though your protocol is HVZK, this does not suffice to make it ZK through general techniques!

Of course, there are known methods that can transform your protocol into a ZK protocol, introducing additional rounds and complexity. But then, they end up loosing any clear advantage over Schnorr's protocol in terms of efficiency... So we usually simply stick to Schnorr and its variants :)


How to solve MixColumns I can't really understand MixColumns in Advanced Encryption Standard, can anyone help me how to do this?

I found some topic in the internet about MixColumns, but I still have a lot of question to ask.

ex.

$$
\begin{bmatrix}
\mathtt{d4} \\
\mathtt{bf} \\
\mathtt{5d} \\
\mathtt{30} \\
\end{bmatrix}
\cdot
\begin{bmatrix}
\mathtt{02} & \mathtt{03} & \mathtt{01} & \mathtt{01} \\
\mathtt{01} & \mathtt{02} & \mathtt{03} & \mathtt{01} \\
\mathtt{01} & \mathtt{01} & \mathtt{02} & \mathtt{03} \\
\mathtt{03} & \mathtt{01} & \mathtt{01} & \mathtt{02} \\
\end{bmatrix}
=
\begin{bmatrix}
\mathtt{04} \\
\mathtt{66} \\
\mathtt{81} \\
\mathtt{e5} \\
\end{bmatrix}
$$

Here, the first element is calculated as

$$(\mathtt{d4} \cdot \mathtt{02}) + (\mathtt{bf} \cdot \mathtt{03}) + (\mathtt{5d} \cdot \mathtt{01}) + (\mathtt{30} \cdot \mathtt{01}) = \mathtt{04}$$

First we will try to solve $\mathtt{d4} \cdot \mathtt{02}$.

We will convert $\mathtt{d4}$ to it's binary form, where $\mathtt{d4}_{16} = \mathtt{1101\,0100}_2$.

$$\begin{aligned}
\mathtt{d4} \cdot \mathtt{02}
&= \mathtt{1101\,0100} \ll 1 & \text{(}{\ll}\text{ is left shift, 1 is the number of bits to shift)} \\
&= \mathtt{1010\,1000} \oplus \mathtt{0001\,1011} & \text{(XOR because the leftmost bit is 1 before shift)}\\
&= \mathtt{1011\,0011} & \text{(answer)}
\end{aligned}$$

Calculation:

$$\begin{aligned}
 & \mathtt{1010\,1000} \\
 & \mathtt{0001\,1011}\ \oplus \\
=& \mathtt{1011\,0011}
\end{aligned}$$

The binary value of $\mathtt{d4}$ will be XORed with $\mathtt{0001\,1011}$ after shifting if the left most bit of the binary value of $\mathtt{d4}$ is equal to 1 (before shift).

My question is, what if the left most bit of the binary value is equal to 0, what do I XOR it with then? ex. $\mathtt{01}_{16} = \mathtt{0000\,0001}_2$ ..?

Well, it sounds like you're close.

The multiplications implicit within the MixColumns operation are $GF(2^8)$ multiplication operations, using the same field representation as they use in the inverse within the sbox.

However, because they're multiplying by the fixed constants $\mathtt{1}$, $\mathtt{2}$ and $\mathtt{3}$, it's easier to implement than a general $GF(2^8)$ multiplication.

Multiplying by $\mathtt{1}$ is easy; it's exactly what you'd expect.

Multiplying by $\mathtt{2}$ is what your question is about: it is equivalent to shifting the number left by one, and then exclusiving-or'ing the value 0x1B if the high bit had been one (where, in case you're wondering, the value 0x1B came from the field representation).  And so, that is the answer to the question you asked; if the high bit was a zero, then you don't need to exclusive or anything (or equivalently, you exclusive-or in a 0x00 constant).

And, your next question would likely be "how do a multiply by $\mathtt{3}$"?  Well, you can do that by multiplying by $\mathtt{2}$ (see above), and then exclusive-or-ing that with the original value, since $\mathtt{3} = \mathtt{2} \oplus \mathtt{1}$.  Or, in other words:

$$\mathtt 3 \times x = ( \mathtt{2} \oplus \mathtt{1})\times x = (\mathtt 2 \times x) \oplus x $$

So, once we've gotten the multiplication by 2 operation solved, the multiplication by 3 is solved as well.

Once you've multiplied all the vector elements, then you need to add them.  Now, you might be tempted to add them modulo 256, but that'd be wrong.  This "addition" operation is actually "exclusive-or".  They've written it as $+$ because, in $GF(2^n)$ fields, exclusive-or is considered the addition operation; it acts an awful lot like an addition operation in conjunction with the multiplication operation.

So, if we look at the calculation:

$$(\mathtt{d4} \times \mathtt{02}) + (\mathtt{bf} \times \mathtt{03}) + (\mathtt{5d} \times \mathtt{01}) + (\mathtt{30} \times \mathtt{01})$$

$\mathtt{d4} \times \mathtt{02}$ is $\mathtt{d4} << 1$, exclusive-ored with $\mathtt{1b}$ (because the high bit of $\mathtt{d4}$ is set), giving $\mathtt{b3}$;
$\mathtt{bf} \times \mathtt{03}$ is $\mathtt{bf} << 1$ exclusive-ored with $\mathtt{1b}$ (because the high bit of $\mathtt{bf}$ is set) and $\mathtt{bf}$ (because we're multiplying by $\mathtt{3}$), giving us $\mathtt{da}$;
$\mathtt{5d} \times \mathtt{01}$ is $\mathtt{5d}$, and $\mathtt{30} \times \mathtt{01}$ is $\mathtt{30}$.

Now, we add (rather, exclusive or) $\mathtt{b3}$, $\mathtt{da}$, $\mathtt{5d}$ and $\mathtt{30}$ together, and that gives us $\mathtt{04}$.


What are the major flaws and limitations of this hash-based stream cipher design? K is a 224-bit key.
C is a 32-bit counter; it is publicly known. the same value is never used twice.
plaintext has arbitrary length (up to 64kB).
H is a cryptographic hash function that returns len(plaintext) bits.
^ is the bitwise XOR.
+ is the concatenation.

Encryption:

ciphertext = plaintext  ^ H(K + C)

Decryption:

plaintext  = ciphertext ^ H(K + C)

Are there any fundamental flaws?
Would it make sense to use a longer key?
Under what circumstances would doing H(C + K + C) instead of H(K + C) make the algorithm more secure?
I intend to use Skein, which comes in three flavors of internal state sizes: 256, 512 and 1024 bits. How does the internal state size limit the strength of the whole system? Would it make any sense to use the 512/1024 bit variants, even though len(K+C) = 256?
Is there anything particular about Skein that would make it unsuitable for the job?

edit: Thinking about it, len(K) > internal state size seems pointless. To break the encryption,  an attacker would just need to find a K that produces the same internal state as the real K.

Are there any fundamental flaws?

The construction itself is secure for a good H. It's close to what many stream ciphers use internally. E.g. chacha has an H that hashes a 256-bit key, a 64-bit nonce and a 64-bit counter to get 512 bits of output.

  Would it make sense to use a longer key?

Yes, if you want more brute force resistance, since finding a preimage is not enough to find the key, if it leads to different values for other counter values.

  Under what circumstances would doing H(C + K + C) instead of H(K + C) make the algorithm more secure?

If your H was vulnerable to length extension attack (e.g. SHA-256) and the counter was variable length, H(K + C) would not be secure, but H(C + K + C) might. However, with a constant sized C, I can't think of a reason to use H(C + K + C).

  I intend to use Skein, [...]

Then shouldn't you use the stream cipher construction from the Skein paper (pdf, section 4.10)?


Has there been any cryptanalysis of AES under a non-uniformly distributed key? The standard security property demanded of a blockcipher is that it be a pseudo-random permutation; i.e., given a uniformly random key, the blockcipher should be computationally indistinguishable from a random permutation under a chosen-plaintext or chosen-ciphertext attack.

However, what if the key is randomly selected from a non-uniform distribution? Has there been any research in analyzing the security of AES (or any other well-known blockcipher, for that matter) when the key is instead chosen from some other distribution? Clearly low-entropy distributions would permit brute-force attacks, but it seems there's a pretty big gulf between keys for which brute-force attacks are infeasible and uniformly distributed keys.

My question is motivated by the observation that encryption keys are frequently derived from passwords or other low-entropy sources by hashing them (perhaps with a salt, which itself may or may not fall into the hands of an attacker). The hashing may expand the key to the required length and deter brute-force attacks, but cannot introduce entropy into the result. (Edit: My question isn't about scenario in particular, it's just an example of when a non-uniform key distribution could happen in practice.)

I am aware that there has been work on related-key attacks, but to my knowledge the results aren't directly applicable to this question.

As far as I know, NO, there has not been any cryptanalysis of AES under a non-uniformly distributed key. That holds even if we let the adversary decide what the non-uniform distribution is. Of course we should adjust the expected difficulty of attack according to the entropy remaining per the distribution; but typically, hashing a low-entropy password looses negligibly few entropy.

Further, the scenario that motivates the question has a low-entropy key hashed then the result (known as a derived key) used as the AES key. Indeed that leads to a non-uniform distribution of the AES keys, but that distribution is unrelated to the structure of AES, thus it is highly implausible that an attack on AES can take advantage of that non-uniform distribution.

The closest thing to what's asked is related-key attacks, but (as stated in the question) such attacks do not apply in the scenario that motivates the question. See in particular Alex Biryukov and Dmitry Khovratovich's Related-Key Cryptanalysis of the Full AES-192 and AES-256 (in proceedings of AsiaCrypt 2009). Quoting their adversarial model:

  The related-key attack model is a class of cryptanalytic attacks in which the
  attacker knows or chooses a relation between several keys and is given access to
  encryption/decryption functions with all these keys. The goal of the attacker is
  to find the actual secret keys. The relation between the keys can be an arbitrary
  bijective function R (or even a family of such functions) chosen in advance by
  the attacker.

In the scenario that motivates the question, the best general attack is typically enumerating the low-entropy key (approximately from most likely to least likely), applying the key derivation algorithm (or hash) for each, then testing if this is the right AES key based on known or low-entropy plaintext. That is slowed, to a large (but often insufficient) degree, by using a purposely slow key derivation algorithm, such as scrypt, or the lesser bcrypt or PBKDF2.


Give a simple hash chain example in Java I am looking for a very simple example of cryptography hash chain source code. Could you forward me some examples or link, guys?
For example, https://en.wikipedia.org/wiki/Hash_chain [1].
h(h(h(h(x)))) gives a hash chain of length 4. h=hash, x=password

I'm not a Java programmer, and I didn't compile this, but I modified answer to this question to achieve a hash chain of length equal to four.

byte[] bytesOfMessage = yourString.getBytes("UTF-8");

MessageDigest md = MessageDigest.getInstance("MD5");

byte[] thedigest = md.digest(md.digest(md.digest(md.digest(bytesOfMessage))));

PS. Don't use MD5 for crypto. It's not secure.


Distance between consecutive primes distribution In several prime generation schemes I saw we pick a random number uniformly at random from a wide range and find the next prime after it.

Obviously with such a scheme some primes are more likely than others, a prime is as likely as the distance to the previous prime.

The question is how unbalanced is this? If a friendly alien gave me a list of the top X most likely primes from a much wider range how likely would a random prime from the scheme above be on the list?

First some empirical results,
over the first 1 million primes the to 0.1% will show up 0.65% of the time
the top 1% will occur 4.7% of time and the top 10% will happen 29% of the time.

Looking at visual from https://en.wikipedia.org/wiki/Prime_gap

It doesn't look like it has a heavy tail and seems to decline super linearly. this suggest a small tail will never be a large portion.

For larger numbers the largest ratio between the prime gap and $ln(p)$ is 41 (This ratio is called merit), this is largest known and not an upper bound, but if we take it as an upper bound, and if we take ln(p) as the average distance and 2 as the minimum distance. The most extreme imbalance would be if all gaps were ever maximal or minimal (obviously not the case just for a bound). We mark the ratio of maximal gaps as r. So we will get $ln(p)=r * ln(p)*41+ 2*(1-r)$
which leads to $r=(ln(p)-2)/(41*ln(p)-2)$ for $p=2^{1024}$ this comes out 2.5%, and these would come up 99% of the time. But obviously we can't have many gaps of size 2. We can improve this somewhat but not much.

So we get a huge discrepancy between what we expect and we can prove. If we want a stronger claim then assuming maximal merit things get worse we can bound the gap to be no more than $p^{0.525}$ and if again assume to have a range where gaps are almost entirely either this maximum or very small, we will be able to get a more extreme ratio. Yet even this scenario won't get enough for e.g efficient factorization. If we have a range from $2^{1023}$ to $2^{1024}$ even with maximal gap there are still a lot of primes there. If we would try to factor with trial division we would get no more than a square root speed up over naive trial division which is not competitive with other methods.


Generating random non-repeating numbers from a small group I read this Q&A which gave a clever solution: feed an incrementing index into a block key cipher as a way of producing non-repeating random numbers. The problem is the block size of all the good algorithms is often way too big. What if I just want to iterate through all 16-bit numbers, or all N-bit numbers where N is determined by the problem at hand? Nobody in their right mind would make a 16-bit block cipher, but that's what I would need.

One idea I had to iterate pseudo-randomly through all n-bit numbers was to use a binary field. Randomise the modulus polynomial, $Q$, ensuring it's irreducible. Then take a random starting point, $a$, and multiply repeatedly by a random primitive element, $r$, to generate the pseudorandom series.

$n_i = a r^i \pmod Q$

Something tells me this isn't good enough. Predicting the next elements can be interpreted as a discrete logarithm problem if $i$ is the plaintext which must be found from $n_i$. The discrete logarithm is difficult, but when $n_i$ are all given in order, can the problem of finding $r$ and $Q$ from the sequence still be interpreted as the discrete logarithm problem? Does the problem have a name? How hard is it?

If this method of iteration is no good, I had an idea to make it a lot harder: pad the index $i$ with some random bits before encryption, so if the index is a 16 bit number, encrypt it to 20 bits with four random bits. Would that be enough to ensure an unpredictable pattern? What method of iteration would ensure sufficient difficulty in finding a solution? One downside to this modification is that although the sequence generated is non-repeating, it doesn't cover the entire output domain. Is there a way to cover the entire output domain?

If you are going to generate ALL the numbers in the output domain, an attacker's job of guessing the next number becomes easier the more numbers you use, once you pass the halfway point. I would suggest with whatever method you choose, to never exceed $N/2$ values used, where $N$ is the total number of elements that can be generated using that method, $N=2^{16}$ in your example.

I actually see no problem with using a finite field, but you would need to make it difficult for the attacker to guess the values used to generate it, even if the method was known.

My solution would be to use the same finite field inversion method as was used to generate the AES S-box, but in $GF(2^{16})$ with the APA method. It is a highly nonlinear sequence, and there are simply too many combinations of generator values and reduction polynomials to brute force every option like there are in $GF(2^{8})$.

Essentially, you perform an affine transformation on the input, then find the inverse in the field, and then perform the affine transformation again, with an irreducible polynomial chosen at random from the list of possible polynomials. There are specific combinations of affine generators and vectors within each finite field that generate high quality results useful for S-boxes, but you would not be constrained by the same conditions, giving you more flexibility. The mathematical description of the algorithm would be very simple.

The format preserving option easily allows you to build a Feistel cipher of whatever block size you want since your domain size is an even power of 2, in your case 16-bit, by using another block cipher or PRF as the F-function. You can drop in AES, use the 8-bit block half plus a round counter as an input, and truncate the output to 8-bits. This would be very easy to code and very quick to generate numbers, at the expense of a complex description of the final algorithm. You can also generate 128-bit subkeys in CTR mode, then use these as independent AES keys for each round, at the expense of additional computation.


Proof of work scheme with one and only one correct answer I need a problem that has one and only one solution, such that the solution is hard to find but easy to verify. I need to be able to generate the problem deterministically from a random seed.

So essentially, I want to be able to do this:

A random value is produced.
One can then search for the "correct answer" to the random value.
There is one and only one "correct answer".
That a particular answer is correct can easily be verified.

Ideally, the amount of work required would be tunable. The problem with most proof of work systems is either that they don't ensure that there is one and only one correct answer or they require some entity to generate the problem and withhold the solution.

For example, I could require someone to produce something that HMACs with the random value to a very low result. But then there wouldn't be one and only one correct answer. I could multiply two primes together and the lowest factor could be the correct answer. But I have no agent that can do that multiplication. Steps one and two are set in stone, though I can adjust the size of the random number.

Update: It must not be possible to do all of the work before the random number is generated. Ideally, there would be no significant benefit to any precomputation. The random number being revealed must enable you to do the work.

One obvious approach would be look at a discrete log problem.  That is, you pick an appropriate group of order $n$ (where $n$ is prime) and a generator $G$; for a challenge, you pick a random element $H$, and you ask for the value $0 \le k < n$ such that $H = kG$.

This meets your requirements (1) the value produced is effectively random, requirement (2) one can search for the answer in $O(\sqrt n)$ time, (3) if $G$ is a generator, then there is exactly one such value, and (4) the answer can be verified in $O(\log n)$ time. In addition, the amount of work is tunable (by selecting groups of various sizes).

For this to work, we need to select a group where we can't find discrete logs faster than $O(\sqrt n)$ time; I believe an appropriately sized random Elliptic Curve meets this requirement.

However, the chief difficulty with this suggestion is finding an Elliptic Curve group of the appropriate size; that's nontrivial, and all the precomputed Elliptic Curve groups I know are scaled to make the discrete log problem "infeasible", not "difficult".

Another group that would appear to be suitable is a small subgroup of a larger multiplicative group.  That is, we pick a large prime $p$ and a small prime $q$ where $q | p-1$.  We will then work in the multiplicative subgroup of size $q$ of the group $\mathbb{Z}^*_p$.  To create a random element of this subgroup, we select a random number $1 < x < p$, and compute $H = x^{(p-1)/q}$.  The order of the subgroup is, of course, $q$, and so if the work target is about $2^{32}$ operations, we may select a 1024 bit $p$ and a 64 bit $q$.  The chief advantage of this proposal over the Elliptic Curve idea is that it is much easier to devise a $p$ and $q$ of the appropriate sizes, rather than trying to define an Elliptic Curve.


DES - encrypt 3 times - DES(DES(DES, k), k'), k) - stronger than 2DES with 2 different keys? What if were to use DES in the following way:

For a given plaintext x and key k we will perform: DES(DES(DES, k), k'), k), where k' is the complementary of k.

If an adversary has a small amount of text and their ciphertexts, would he still have to run 3 * 2^56 encryptions: for each key perform DES(DES(DES, k), k'), k) and therefore this encryption is stronger than 2DES with 2 keys (meet in the middle requires 2^57 runs) but less than real 3DES which is much more than 2^57 ?

Or is there a smarter way ?

As pointed out in the comments two key triple DES (without your complementary key condition) already has efficient attacks against it, going back to the 80's. See for example a detailed analysis in Van Oorschot and Wiener here which converts a chosen plaintext attack by Merkle and Hellman to a known plaintext attack.

Since 2 key 3DES is already weak, trying for sophisticated and complicated improvements based on the complementary key condition is likely not worth the effort.


How any attack on a cipher carried out? Are these practical or only theoretical? I have been reading about successful attacks on AES and other ciphers. One such mention is here (see excerpt below):

  AES was published under the name Rijndael in 1998. Refereed
  cryptanalytic papers in the next three years culminated in attacks
  taking time "only" $2^{140}$ to break 7 rounds of 256-bit AES and "only"
  $2^{204}$ (with a huge amount of memory) to break 8 rounds of 256-bit AES.
  Subsequent work made very little progress. (Related-key attacks can
  break more rounds but are not of concern in any properly designed
  cryptographic protocol.)

I want to know:

If any paper mentions attack as $2^{140}$, how the researchers determine this number of operations?
Are these attacks only on paper or practically proven?
Considering super-computers owned by the government, which researchers don't have access, this figure may vary? Are these attacks taking into account super-computers computing power also?

I'll answer your questions in order:

1. If any paper mentions attack as $2^{140}$, how the researchers determine this number of operations?

By examining the mathematical properties of the algorithm and their attack.

2. Are these attacks only on paper or practically proven?

There is no practical way to perform any operation $2^{140}$ times, so they are only on paper. But note that mathematics is one of the few sciences where we can prove things without resorting to experimentation.

3. Considering super-computers owned by the government, which researchers don't have access, this time-frame may vary? Are these attacks taking into account super-computers computing power also?

$2^{140}$ is the number of elementary operations, usually 1 operation takes a constant amount of operations of the underlying primitive, e.g. 1 AES encryption/decryption operation. The number of operations required does not depend on computer speed.

But yes, faster computers will perform the operations faster. This is however of little importance as $2^{140}$ operations together take multiple universes of time and energy to complete. Only very disruptive technology such as quantum computing or breakthroughs in mathematics could make such attacks practical.

There is always the possibility that the attack itself can be improved upon. Attacks get better, never worse.

The results on 256 bit AES with relayed keys are mainly of importance when the block cipher is used within other constructions such as pseudo random number generators. AES encryption is still considered secure.


What is the strength of unpadded RSA? I would like to use unpadded RSA for homomorphic encryption in a toy P2P game, for things like fair coin flips and shuffling.

How many bits of security does unpadded RSA have, in relation to its key size?

None.

When enciphering any small set of values (including a fair coin flip, a byte, even a small password..), unpadded RSA (or RSA with any padding that does not include randomness) is a terminally weak encryption method: the adversary can enumerate the possible plaintext values, encrypt them using the public key, and check against the ciphertext to determine if the candidate plaintext value being enumerated is the right one.


Ring Signature Verification When a receiver is verifying signed message, it has all the public keys of possible senders.

Sender

$S(M)$ denotes signed message $m\in M$, private key $s$, and public key $p$ giving us:

$(m, \ s_i, \ p_1, \ p_2 \ , ... , \ p_n)$

Receiver
Verifies the message using:

$(m, \ p_1, \ p_2, \ ..., \ p_n )$

I am a little bit confused. How are these keys reconciled?

When validating the message, does the receiver try each public key one by one?

If the receiver has to conduct an exhaustive search, does it mean the receiver knows the exact public key used to validate the signed message?

Does knowing the public key mean knowing the owner of the private key?

How can a receiver know who signed the message?

I am a little bit confused. How are these keys reconciled?

Since this question is more or less specific to the ring signature system. I will assume you are talking about ring signatures as proposed by Rivest, Shamir and Tauman in 2001.

I took the liberty to reorder your questions a bit.

  Does knowing the public key mean knowing the owner of the private key?

Rivest et al. use standard RSA or Rabin keys, so every private key has an associated public key, just like in classical public key cryptography.

  How can a receiver know who signed the message?

They cannot know; this is the whole point of ring signatures! The only thing that the receiver learns, is that the signature was crafted by one in the ring: $\{p_1, p_2,\dots, p_n\}$. The receiver can verify that the signature was generated by one of the associated private keys, without figuring out which one it was.

  When validating the message, does the receiver try each public key one
  by one?

  If the receiver has to conduct an exhaustive search, does it mean the
  receiver knows the exact public key used to validate the signed
  message?

The receiver does not try each and every public key once; they combine all public keys in the ring to verify the integrity of the signature.

They get combined in a ring equation:

$$
C_{k,v}(y_1,y_2,\dots,y_n)=v
$$

where $y_i$ is the result of a public key operation with public key $p_i$. This equation is constructed as such, that the signer needs access to at least one private key to make it satisfied.

Let me know if you want me to go more in detail here. I got to this question while studying ring signatures myself :-)


Can one efficiently iterate valid bcrypt hash output values? bcrypt is an intentionally slow hash algorithm. In my last protocol idea, I wanted to use it to expand a password and then only transfer the bcrypt-hashed password.

An efficient attack on this would be an ability to iterate all bcrypt hashes (or only these from passwords in a dictionary, maybe $2^{12}$ ones) without actually bcrypting the passwords.

The output of bcrypt consists of the security parameter (an integer), the used salt (128 bits), and the actual hash (192 bits), which is the result of 64 iterated Blowfish ECB encryptions of the ASCII string "OrpheanBeholderScryDoubt", where the key and s-boxes were expensively created by the (costly) EksBlowfishSetup instead of the normal BlowfishSetup.

Assume we have a quite high security parameter, like 12 (meaning $2^{12}$ iterations in the setup phase).

To make it easier, assume that either the salt is fixed, or we want to enumerate all valid actual hashes for all salts (without paying attention to which salt is used for which hash).

Is there any method of enumerating all the hashes without actually running the bcrypt algorithm, or enumerating the whole 192-bit output space?

What I could see is simply enumerating all possible blowfish states (e.g. subkeys + S-boxes) before doing the 64-times encryption with each such state. But if I understand right, this state consists of a $576$ bit P-array (the subkeys), and $4·265·32=32768$ bits of S-boxes. This is a much larger space than the hash output space ($192$ bits), thus we then simply could assume that every possible hash occurs at least for one such state, and simply enumerate the whole $192$ bit space. Not really a win.

bcrypt uses Blowfish, which is a block cipher (albeit with a much enlarged key schedule). As such, Blowfish implements a permutation of the space of 64-bit blocks; and there should be no way to distinguish Blowfish (using a random key) from a permutation extracted at random, with uniform probability, from the set of permutations over 64-bit blocks (there are $2^{64}!$ such permutations).

The best cryptanalysis result so far, about precisely distinguishing Blowfish from a random permutation, is due to Vaudenay: some Blowfish keys can be detected (and thus making the block cipher distinguished from a random permutation) if the number of rounds is reduced to 14 (from 16 for the "normal" Blowfish). There is no attack on the full Blowfish, and even if there was, it would only be about the weak keys (about one key in $2^{15}$ is weak).

Therefore we cannot guess anything about the Blowfish instance, that would not apply to a randomly chosen permutation. This still allows a small remark: since this is ECB encryption, i.e. encryption of three distinct 64-bit blocks, we know that the hash result must consist of three distinct 64-bit blocks, concatenated together. This implies that the space of possible hash values has size $2^{64}(2^{64}-1)(2^{64}-2)$, which is $2^{192}-3\cdot2^{128}+2\cdot2^{64}$, i.e. very slightly lower than $2^{192}$ (but not by a significant amount).

The trickier part of your question is about bypassing the key schedule. The point of bcrypt is to make processing of a single password as slow as possible for the attacker, but not intolerably slow for the honest systems. The use of Blowfish is a good idea here: the key schedule of Blowfish is optimized for systems which have a few Kbytes of fast RAM, and that's a PC. Implementing Blowfish on, say, a FPGA or ASIC, would be a painful experience; and the RAM requirement is likely to impair performance on GPU as well. This still requires that the key schedule itself is not amenable to hidden optimization, that the attacker may use. To my knowledge, there is no known result on the security of the "expanded key schedule" used in bcrypt.

Note that this algorithm is of the kind which uses self-modifying lookup tables, like MD2 and RC4, which are notoriously difficult to analyze: we do not benefit from the usual tools such as differential or linear cryptanalysis. MD2 and RC4 turned out to have weaknesses, but it took an awful lot of time, and nothing currently suggests that Blowfish could have such weaknesses. We still lack a proper mathematical framework to discuss the security of such constructions. So the absence of published results just means that nobody found an actual break; it does not mean that there are known reasons why such a break may or may not exist. My feeling is that the extended key schedule used in bcrypt is robust for what it is used for (i.e. an unavoidable mass of computations for each password guess).

So my answer to your question ("Is there any method...") is: no.


How Does Progressive Hashing Work? Example: http://jsfiddle.net/KGtUE/

https://code.google.com/p/crypto-js/#Progressive_Hashing

sha256.update("abc");
sha256.update("def");
sha256.update("ghi");

vs

CryptoJS.SHA256("abcdefghi");

How does this work?

I will assume the way my class does it is the same way other classes such as CryptoJS do it.

Quite simply, there is a buffer in the class that absorbs the input until it reaches the hash block length or a multiple thereof, then processes that section of the buffer through the compression function. Whatever is left becomes the start point of the buffer.

How to implement that buffer is up to the programmer.


Whether ramp secret sharing possess additive homomorphism? Ramp secret sharing replaces the random coefficients in original Shamir secret sharing with original data to be shared. In such a case, all the coefficients in the polynomial evaluation will be secrets. If such ramp secret sharing supports additive homomorphism, how these secrets are reconstructed. Can the coefficients other than constant term can be reconstructed through Lagranage interpolation.

It does indeed. I've written a bit about this here with code examples: https://mortendahl.github.io/2017/06/04/secret-sharing-part1/#packed-variant.


AES CBC with unique key per message, but fixed IV I'm working on a project with a scheme in which c[i] = AES-CBC-Encrypt(msg_key[i], IV, msg[i]), and two distinct plaintexts never have identical keys. IV is a string of nulls.

Random IVs are not an option because fully deterministic behavior is essential in this application. The only available sources of entropy (passphrase, id and msg[i]  below) are used in key derivation, so no derived IV would be independent of the key. The value i is used for notational reasons only and is not available for cryptographic use, e.g. as a counter.

Keys are derived as follows:

passphrase = string chosen by user, constant for all messages

uuid = non-secret UUID, constant for all messages

msg[i] = plaintext of message i

root_key = PBKDF2(passphrase || uuid)

signing_key = HKDF(root_key, 0x01) # HKDF with extraction as in RFC 5869, IKM=root_key, salt=0x01, info="", L=chosen AES key length

text_id[i] = HMAC(signing_key, msg[i])

msg_key[i] = HKDF(root_key, text_id[i] || 0x02)

text_id[i] is known to recipients in another scheme beyond the scope of this question. The reason for deriving variable keys with a fixed non-secret IV instead of variable IVs for a fixed secret key is twofold:

Limit the amount of text encrypted with one key
Require knowledge of text_id[i] to decrypt any block of c[i] in addition to the passphrase. (The motivation for this comes from the system this scheme belongs to.)

It seems to me that this scheme addresses the major concerns I have seen raised regarding fixed IVs:

In order to produce an key collision in a chosen-plaintext attack, the adversary must find two messages that produce a collision in the HMAC function.
Two plaintexts with identical prefixes will not generate ciphertexts with matching or similar prefixes with any greater likelihood than two random plaintexts would.

Someone asked a similar question and got an answer that concerns me a bit:
Why should I use an Initialization Vector (IV) when I have unique keys?

  On the other hand, by not using a random IV, in some setups, one gives the adversary the same plaintext block enciphered with different keys (that would be the case if the first block of each plaintext is a known constant); this reduces the number of trial encryptions for exhaustive key search by a factor (at worse) equal to the number of different keys.

If I'm understanding this right, the concern is that if an attacker possesses N ciphertexts and knows that their plaintexts all start with a common prefix P at least one block in length, then the attacker can encrypt P under various keys until they duplicate the first block of one of the ciphertexts, at which point they will have discovered the key for that ciphertext. It seems like N needs to be quite large to make this practical, particularly for a 256-bit key.

But fixed IVs make me feel bad inside, and so I wanted to ask... what dangers might I be overlooking?

What you are describing is related to the synthetic initialization vector or SIV family of authenticated ciphers, where the cipher is a deterministic function of a key and a message without a separate initialization vector or nonce.  Such ciphers cannot conceal repeated messages, but that is the only inherent flaw.

Some ciphers also admit specifying an IV or nonce, and if the nonce is always unique, then they work like standard nonce-based ciphers, but if the nonce is ever repeated, then they fall back to failing to conceal duplicates but nothing else—we call these nonce-misuse-resistant or NMR.

SIV or NMR ciphers are not very popular right now, partly because nobody agrees on which ones to use, and partly because the security bounds or data volume limits on the most common ones like AES-SIV and AES-GCM-SIV are not very good owing to the small block size of AES—indeed, the name ‘AES-GCM-SIV’ has undergone many revisions over the past couple years in attempts to improve the bounds, and its definition is still not standardized.

The general structure of (a) deriving a key or IV as a pseudorandom function of the message, and then (b) applying a standard cipher with the derived key or derived IV, is generally fairly safe as long as everything involved is large enough to have a low collision probability—if we're talking HMAC-SHA256 to derive an AES-256 key, that should be fine.  The main difference between instances of this structure is cost.  (Just make sure you don't reuse keys for multiple purposes.  For example, if elsewhere you reveal the HMAC-SHA256 under signing_key of public messages, you might leak which public message you just encrypted.)  If the cost of HMAC-SHA256 is acceptable to you and to your auditor, great!

What you describe is not exactly an SIV cipher because you derive the key rather than the IV as a pseudorandom function of the message.  With ciphers like AES, this incurs a somewhat high cost per message, because AES has an expensive key schedule, which is why AES-SIV is more popular than a hypothetical ‘AES-SK’ with synthetic keys.  In contrast, ciphers like ChaCha and Salsa20 have zero overhead to changing keys.

  If I'm understanding this right, the concern is that if an attacker possesses N ciphertexts and knows that their plaintexts all start with a common prefix P at least one block in length, then the attacker can encrypt P under various keys until they duplicate the first block of one of the ciphertexts, at which point they will have discovered the key for that ciphertext. It seems like N needs to be quite large to make this practical, particularly for a 256-bit key.

The area*time cost (a good proxy for euros or joules) of a generic attack on a cipher with a $b$-bit key given $n$ ciphertexts is $2^b/n$, using Oechslin's rainbow tables to save hash evaluations, on a $p$-way parallel machine for $p \geq n^2$ to save memory and communication costs, which runs in the time of $2^b/np \leq 2^b/n^3$ sequential AES operations.  This is why, for example, AES-128 should not be considered to provide a ‘128-bit security level’—if a billion users use the application (or, your users in aggregate make a billion ciphertexts under different keys using your synthetic key scheme), the cost of breaking one of them is well below $2^{100}$.

If $b = 256$ as for AES-256, it would take $2^{128}$ different targets before the cost drops below $2^{128}$.  In other words, you don't have to worry about this.  This is why, if you're aiming for a 128-bit security level, you should use ciphers with 256-bit keys like AES-256.

(Actually I don't recommend AES-256 either because it invites timing side channel attacks on software implementations, but if you must use AES you should use AES-256 instead of AES-128 unless you have an overwhelming performance consideration that can be carefully justified within your security goals.)


Use case for extendable-output functions (XOF) such as SHAKE128/SHAKE256 FIPS 202 defines 2 functions, SHAKE128 and SHAKE256, as extendable-output functions (XOFs) that can have variable output length. But in Appendix A.2 marks:

  it is possible to use an XOF as a hash function by
  selecting a fixed output length. However, XOFs have the potential for generating related
  outputs—a property that designers of security applications/protocols/systems may not expect of
  hash functions

Later it describes a theoretical use case (and explicitly discourage such uses):

  For example, a naïve (and non-approved) way
  for two parties to agree to derive a 112-bit Triple DES key from a message designated as keymaterial would be to compute SHAKE128(keymaterial, keylength), where keylength is 112.
  However, if an attacker is able to induce one of the parties to use a different value for keylength, say 168 bits, but the same value for keymaterial

So what is the use case for these functions? Is there any reasonable use case where these functions should be used instead of standard (fixed-size output functions) SHA-3 functions?

As of now I can think of four different applications for XOFs.
Note that some change the padding depending on the requested output size and so the outputs are truly unrelated, Skein does this.

Signature message hashing. Using an XOF you don't have to rely on ad-hoc constructions for hashing the message in signature schemes to the appropriate size. For example, implementing RSA-FDH is trivial with an XOF while it is not so easy with fixed size hashes. As another example the CFRG of the IRTF adopted SHAKE-256 as the internal hash function for the Ed448 signature standard (which needs an 912-bit hash internally).

Stream ciphers. This may be a artificial but you can in fact abuse your XOF as a stream cipher if you don't want to trust the well studied AES-CTR or Salsa constructions. This was indeed proposed in the Skein specification.

Key derivation. Assume for a second that you didn't know HKDF. You trivially replace HKDF with an XOF in most scenarios as you could simply save the state after processing the master secret and then pad it with the context for each key-derivation. Or if you only need one giant block of derived bits, you'd need to call HKDF or a fixed size hash many times but your XOF only once.

Easier instantiation of random oracles. Some security proofs rely on the so-called random oracle model to prove the security of a given scheme. Normally you'd use some artificial construction around a fixed-size hash function to get the desired output size, but with XOFs you can just plug them right in without having to fear any mistakes on your side potentially breaking the proofs (most people don't know / understand in many cases, me included).

TL;DR: Native XOFs aren't necessary and can be emulated using known "ad-hoc" constructions, but they are highly convenient in random oracle based schemes, in signature message hashing and for fast and easy key derivation.


Is there a way to use Shamir Secret Sharing with updatable data? I want to divide a system that maintains these properties, based on Shamir's Secret Sharing:

A secret key is split up to N pieces, where T of them are enough to reconstruct the key.
The original key is then destroyed and doesn't exist anywhere except the N separate pieces.
The information unlocked by the T signatures is updatable - I want to retain some other information that will allow me to update the secret that is accessible by the secret holders.

The use case is a will that contains secret information. I have N people I trust, and I want any group of T of them to be able to read the secret information (hopefully, only after I'm dead). I want to be able to update this secret information from time to time, without the bother of recreating and redistributing another set of keys.

Is there something that answers these requirements?

I think there's a better way to do this, and I'm not sure the existing answers check all your boxes. I suggest using secret splitting together with asymmetric keys so that:

Nobody but you can write data.
Shareholders can come together to read data.
Each shareholder can individually verify, but not read data.
You can read and write data at any time.

Here's how I'd do it:

Create asymmetric (e.g. RSA) key pair "A".
Split the private half of A into $s$ shares, where $s=nx+t$.
Keep $t$ shares for yourself.
Create asymmetric key pair "B".
Give $x$ shares in A and the public half of B to each trusted person.
Secure the public half of A and the private half of B and keep them to yourself.
Create your data, encrypt it using the public half of A, then sign it using the private half of B. Distribute the signed, encrypted data.

Each shareholder can use the public half of B to verify the encrypted data; they may do this alone and at any time. Shareholders may combine their shares to recover the private half of A, which can then decrypt the data.

You, may at any time, use your shares to recover the private half of A and read the data. Also at any time, and as often as you wish, you may create new and/or additional data, encrypt and sign it, and distribute to your trusted people.


Key exchange protocols non-reducible to groups Some questions I have ended up wondering about while reading through many of key-exchange protocols are:

Is there an intrinsic reason, why most key exchange protocols use group-based approaches apart from it being a well-studied area?
Given a key exchange protocol does there always need to be some group or a particular algebraic structure involved?
What about key-exchange with a requirement for perfect forward secrecy?
What would be the least constrained algebraic structure involved for a secure key exchange?
If not can you give some examples of perfect forward secure key exchange protocols not involving group operations?

Is there an intrinsic reason, why most key exchange protocols use
  group-based approaches apart from it being a well-studied area?

No. It just so happens that

Diffie-Hellman was first and heavily used multiplication modulo a prime, which was later generalized to groups. So groups are important for historic reasons.
Groups are easy to understand and "even the average software developer" can probably get a grasp of why this is secure somewhat quickly.
We know efficient ways to create groups which yield fast, small and secure key exchanges, so they are a natural choice.

Beyond that you can build a secure key exchange from any encryption scheme, including e.g. McEliece (by simply encryptingt the shared secret and sending it over).

  Given a key exchange protocol does there always need to be some group
  or a particular algebraic structure involved?

In some sense yes. You can't avoid fields / groups because computer arithmetic fundamentally is working with these, so if you want to actually compute / execute the protcol you'll at some point involve fields and groups.

On a higher level, to agree on a secret over a public channel we need some structure that allows us to publicly show values and blocks passive adversaries from learning the corresponding secrets. Chances are you can always find a relevant mathematical concept / basic idea out of any key exchange. Additionally sometimes these protocols start from things we know how to quickly compute as honest users but know to be hard to break from other fields, so why make an effort to come up with something new (that may be broken in a few days - years) when you can build on a large amount of existing research?

  What about key-exchange with a requirement for perfect forward
  secrecy?

Just about any protocol can be modified / extended to provide forward secrecy, so there's nothing special about this property and groups. It just so happens that with groups the property can be achieved somewhat cheaply.

  What would be the least constrained algebraic structure involved for a secure key exchange?

On an abstract level probably the semi-group which is usually enough for the "group-based" key exchanges we are using, because these don't actually make use of the ability to invert every element nor do they make use of the availability of a neutral element.

Note though that not every semi-group (eg the natural numbers with addition) actually provide cryptographic security. If you are looking for examples of secure semi-group based key exchange look no further than standard ECDH and DH, which use $(E(\mathbb F_p),+_{\text{EC}})$ and $(\mathbb F_p^*,\cdot)$ as their semigroups.

  If not can you give some examples of perfect forward secure key
  exchange protocols not involving group operations?

See above on avoiding groups and using McEliece. You get forward secrecy by throwing the encryption scheme's private / public key away after each key exchange.