Have affine ciphers actually been used in practice? I have been been studying some basic ciphers, and learnt about the affine cipher where the encryption function is given by $ax+b \pmod{26}$ for an alphabet with 26 characters. This is a very insecure cipher, so if it was used it must have been a long time ago. I am aware that the Caesar cipher and the Atbash cipher are special cases of the affine cipher (with $a=1$ and $a=b=25$, respectively). However, when these two ciphers were used, the encryption was not performed mathematically using the affine function, but with a shifted alphabet.

So, my question is: Has the affine cipher ever been used in practice (with $a\ne1$ and $a\ne b\ne25$), where the encryption was performed mathematically using the affine function?

While it's hard to prove that something has not been done, I'm fairly confident in asserting that affine ciphers (with $a \not\equiv \pm1$) are purely educational toys and have never been used for serious encryption (i.e. something not deliberately designed to be broken), except perhaps arguably as parts of a more complex cipher.
For one thing, affine ciphers of this type aren't really particularly good for anything in practice.  Their keyspace is not that much larger than that of simple Caesar shift ciphers, and in any case they are just as vulnerable to attacks via frequency analysis as any other simple monoalphabetic substitution cipher.
As hand ciphers, affine ciphers are too complex to be practically applied without the aid of an explicit lookup table.  And while one could indeed construct an encryption table using an affine map, doing so would not seem to offer any particular advantage over e.g. the various keyword-based methods actually used in practice.
Meanwhile, for a machine cipher, affine maps offer no obvious advantage over the combination of shifts and (fixed) non-linear permutations, as used e.g. famously by the Enigma machines, and they have the obvious disadvantage that modular multiplication is far harder to implement mechanically than simple shifting.
That's not to say that it could not be done, as exemplified e.g. by Weisner & Hill's patented mechanical implementation of the Hill cipher.  That said, it's worth keeping in mind that, although proposed as (a component of) a practical real-world cryptosystem, the Hill cipher was never really adopted as such, is large part due to its cumbersomeness.  Presumably, any attempts to employ affine ciphers via mechanical means would have encountered similar difficulties.

I tried to see if I could determine when and where the concept of affine ciphers was first introduced, but I'm not sure if I've really found it.  In any case, the earliest mention of the term "affine cipher" that I could find in the literature is from 1983, in a book chapter titled "Elements of Cryptology" by M. Davio and J.-M. Goethals, included in the book Secure Digital Communications by G. Longo (ed).
However, while the chapter indeed briefly discusses classical monoalphabetic substitution ciphers (of which affine ciphers as you define them are a subset) on page 3, the phrase "affine cipher" only occurs on page 14, in the context of block ciphers, and only as an example of an insecure class of ciphers to be avoided:

2.4 Combining building blocks.
Individually, each of the above building blocks [i.e. bit permutations, translations, linear transformations, addition mod $2^n$ and substitutions (S-boxes)] is a poor cipher. However, by combining them (as suggested by Shannon) in a product cipher, we may obtain much stronger ciphers.
Some of the combinations, however, are weak. For example, by combining translations and linear transformations we obtain an affine cipher: $$m \to Am + b$$ which can be broken in much the same way as a linear cipher. Thus affine substitutions should be avoided.

(emphasis original; [editorial note] mine)
In particular, in the context where the quote above appears, $m$ in fact denotes a block of $n$ bits, $A$ is an $n \times n$ matrix over GF(2), and the operator $+$ (which really should have been written as $\oplus$, to stay consistent with the usage on the previous page) clearly denotes bitwise XOR.  Thus, while the "affine cipher" described in this text is indeed clearly an affine transformation, the elements being transformed in this case are $n$-bit vectors over GF(2) rather than integers modulo 26 (or any other modulus).

Meanwhile, the earlier mention that I could find of the "educational" form of the affine cipher you describe above is from Douglas R. Stinson's book Cryptography: Theory and Practice, first published in 1995:

1.1.3 The Affine Cipher
The Shift Cipher is a special case of the Substitution Cipher which includes only 26 of the 26! possible permutations of 26 elements. Another special case of the Substitution Cipher is the Affine Cipher, which we describe now. In the Affine Cipher, we restrict the encryption functions to functions
of the form $$e(x) = ax + b \bmod 26,$$ $a, b \in \mathbb Z_{26}$. These functions are called affine functions, hence the name Affine Cipher. (Observe
that when $a = 1$, we have a Shift Cipher.)

There's no mention in the rest of Stinson's book of any historical usage of affine ciphers, and indeed the text seems to present them merely as a particular mathematically interesting class of simple ciphers.  If a historical source for affine ciphers existed, one would expect it to be mentioned in section 1.3 ("Notes"), which e.g. cites Lester S. Hill's original 1929 paper on his eponymous cipher, as well as David Kahn's The Codebreakers for general history of cryptography (with a special mention of the historical misattribution of what's nowadays known as the Vigenère cipher to Blaise de Vigenère rather than to its actual author, Giovan Battista Bellaso).  But no such reference is given there, or anywhere else as far as I can tell.
It thus seems possible that Stinson may have invented the affine cipher in its modern form, perhaps inspired by earlier uses of the term in contexts like Davio's & Goethal's mention of affine block ciphers.  However, without additional sources, I cannot be sure of this.  Perhaps someone ought to contact him and ask.


Is power of non-negligible function non-negligible? If I have a probability which is > negl(n), i.e., non-negligible, will be this probability raised to the power of n also non-negligible?

No and yes, depending on what do you mean by $n$.

Take $f(x)=1/2$ for example. It is a non-negligible function, but $g(x)=(f(x))^x=(1/2)^{x}$ is negligible, i.e. for every positive integer $c$, there exists an integer $N_c$ such that for all $x > N_c$,

$$|g(x)|<{\frac {1}{x^{c}}}.$$

If you mean a constant $n$, then $g(x)=(f(x))^n=(1/2)^n$ is non-negligible.


Allowing the user to choose the hashing formula at the registration I was thinking of a potential new way to increase someone's account security.

The idea was allowing the user to choose one of the hash formulas available in the software (example: "MD5", "SHA512" and "Whirlpool"), decreasing the chances of any intruder to find out the hashing system used in case passwords are — for some reason — leaked increasing a potential required time of brute-force or dictionary attacks.

Would that be a good idea?

This doesn't sound like a good idea. As CodeInChaos already pointed out, choose one good password hashing scheme like scrypt or bcrypt and go with that

The reason why what you proposed isn't so great is that you'll give the user the choice between a few good password hashing options and the work of an attacker is at best multiplied by the number of options you proposed.

By doing that it's also unlikely that a bad password hashing will make its way into the list and the users picking that one will be at the attacker's mercy.
Lastly I don't think it's a good design to leave security relevant choices up to the user.

How should an average user know better than the designer of the system what's good for him ?


Client side encryption / hashing of "person ID's" with password? What we're looking for

A solution where data is stored and retrieved (!) from a server using a person ID that can only be known at the client (form of anonymization). Furthermore, the client should be able to calculate the original person ID back from a data record.

Storing certificates on the client is not an option, asking the user for a password is.

My original idea

PBKDF2 + AES (CCM) on the client. However, because we need to be able to retrieve records later, I had to keep the IV (and salt) constant. For what I've read, this could be a problem (but I'm not sure, especially if the person ID is always smaller than the key?).

My alternative idea

PBKDF2 + AES (CCM) on the client, now with random IV. This can now only be used for calculating the person ID from a data record. For data retrieval we would add a separate column, containing a client-calculated hash of the person ID. To prevent against an attack that hashes all valid person ID's and works back from there, I was thinking to salt with the same user supplied password as we used for encryption (since this can be expected to never leave the client).

I could really use some thoughts on this challenge (and the two ideas described above).

Because of the requirement that the secret be decryptable, it has to be encrypted, rather than simply hashed. Because of the requirement that a record be retrievable by the secret, it should be encrypted deterministically, so it can be reproduced. Finally, no keys or salts can be stored by the client, complicating the matter.

This suggests that the client should encrypt the secret person ID using e.g. AES-SIV, which requires no IV. The encryption key can be derived from a password and a constant salt (per client, rather than per record) which does not need to be secret or random (but can be for some extra protection against the server).

Possible key derivation functions include e.g. PBKDF2, bcrypt, scrypt or argon2. I would prefer the later ones, but any of them are acceptable if the password is good.

(Note that AES SIV used without a nonce, like any deterministic encryption, leaks the equality of person IDs (by design), so they should all be unique for this to work.)


Understanding pseudo-random functions (used in a Oblivious Transfer Protocol) Given a family of pseudo-random functions

$$\{F_K:\{0,1\}^m\mapsto \{0,1\}^m | K \in \{0,1\}^t \}.$$

I want to understand how the elements behave.

Lets say we take some $F_{K_1}$ and evaluate at $x=(0,\dots,0)\in\{0,1\}^m$, is it true that the evaluation of $F_{K_1}$ at $x$ always yields the same result? Why property does make this set so special? I tried to understand the definition from wikipedia, but failed to do so..

I am asking this questions and trying to understand PRF because I am studying a paper about generalized OT protocols which can be found here ( page 5).

Yes, if you take an instance out of the function family (e.g. $F_{K_1}$), then the evaluation of this function at $x$ always yields the same result. You can think of it like that:

If you fix a key $K$, then your PRF is basically a look-up-table. For every possible input $x \in \{0,1,\cdots,2^m-1\}$ there is an entry in the look-up-table for the output $F_{K_1}(x)$. For each key, there exist a different look-up-table.

So why is called pseudo random? Well imagine some bad guy who sends different $x$ to a black box and gets back some value. Inside the black box, there is either a $F_{K}$ with a key $K$ chosen uniformly at random or a function $f: \{0,1\}^m \rightarrow \{0,1\}^m$ that is chosen uniformly at random from the set of all possible functions from $\{0,1\}^m$ to $\{0,1\}^m$. If the bad guy cannot tell wether he is talking to $F_K$ or $f$, then $F$ a good PRF, because the output looks totally random to him in either cases.

There is a possbile way to distinguish both functions, if the bad guy accidentally finds two distinct values $x_1, x_2$, that yields the same output $f(x_1) = f(x_2)$. Then he knows, that he's talking to $f$. But if $m$ is suffienciently large, the probability of a collision is very low.


Acceptable assumptions when proving security Considering the output of a cryptographic primitive, like an encryption scheme (CBC, ...), a hash function or even the output of any schemes based on number theoretic assumptions, is it reasonable (acceptable) to assume that these outputs are random when proving the security of a protocol/algorithm which relies on the use of such a primitive? Is this a good starting point?

The answer is "it depends". There are two fairly commonly used sets of assumptions, the so-called standard model, and the random oracle model. In the standard model, hash functions are one-way functions. In the random oracle model they are random oracles. The random oracle model isn't actually true, but it is useful and many protocols inspired by it are in fact secure as no one has been known to attack them.

For ciphers the usual model is PRP, pseudo-random permutation, although the ideal cipher model is also used, but generally PRP is realistic and strong enough to prove things secure.

Number theoretic primitives do not output random strings. For instance DH never produces all zeros. You should use hashing to make this truer.

For protocols usually a game is designed where an adversary tries to get bad things to happen. Showing that the game is lost if the cipher is a PRP implies that a real version will be secure if the cipher behaves like a PRP, and so is generally considered a proof of security. However, the constants involved matter: if you haven't read DJB "Non-uniform cracks in the concrete" you should before embarking on any sort of provable security work.


Why R value in signatures have to be 'calculated' values and not just a random numbers? This document (page 27) says that:

  The only significant difference between ECDSA and DSA is in the generation of $r$.

ECDSA $r = (kG)_x \bmod n$ and,
DSA:  $r=g^k \bmod p$

Why is it necessary to have a function that takes a random number $k$? Why do we cannot use the random $k$ directly as our $r$ value in the signatures?

The DSA signing algorithm involves the value $k$ not only at the step $r=g^k$, but also when calculating $s = k^{-1} (H(m)+rx)$.

So if you assign $r$ randomly, then you would need to calculate $k$ for the calculation of $s$, which is the dlog of $r$ to base $g$.

The argument of Biv's answer is of course valid too: If you choose $r$ randomly, you can't be sure that it is actually in the subgroup generated by $g$. In the verification process you need this fact, so that different powers of $g$ cancel each other out.

Considering ECDSA: Actually, it is exactly the same algorithm, just the additive notation instead of multiplicative. And of course, that the actual addition in elliptic curves have their own unique definition. For example, to calculate modular exponentiations, usually square-and-multiply is used. In additive notation, this is just called "double-and-add", as noted in the Wiki article as well.


How do I safely encrypt a file for transport and storage? So I need to encrypt a file server-side for transport from server to client and storage on client-side. I'm quite confused as to what I have to watch out for, as it seems like it's insanely easy to screw up really bad.
The files I need to encrypt

Are binary
Sometimes contain big areas of null bytes.
Are of medium size, usually < 1gb.
Usually start with the same or similar header, so plaintext will often be the same.
Dont need to be encrypted often, but decrypted often, as they will not be stored decrypted.
Should remain very secure for a long time.

What I thought I could do is to use AES-256 in OCB3 mode, as it seems to provide both authentication and encryption.
I'm however not very sure about how I would go about generating a suitable key from a password.
Is using a simple hash function like SHA-256 secure?
I'm assuming I'll have to store the IV along with the file. Is that correct?
Would AES-256 in OCB3 mode be suitable for this sort of task or is there a better way of doing this?
By the way, I am aware that it's quite easy to read the decrypted file from memory when it's decrypted at client-side, but I'm afraid there's not much I can do about it.
Edit: Both server and client programs are written in c++. I also want to be able to encrypt and decrypt the files just in memory at runtime, so a lot of file encryption tools don't really fit the task.

I'm however not very sure about how I would go about generating a suitable key from a password. Is using a simple hash function like SHA-256 secure?

No, you'd generally use a Password Based Key Derivation Function such as a secure version of Argon2. But preferably, you'd not use a password at all. It is only one factor that's required and passwords generally do not contain enough entropy for long term storage.
One trick is to use a public key for hybrid encryption, and store the private key on a separate device that is only connected when the file needs to be decrypted. That private key in turn can be encrypted.
If you use a password, I'd use a password manager with a very large password.

I'm assuming I'll have to store the IV along with the file. Is that correct?

Not necessarily. The input of a PBKDF always contains a salt value to protect against rainbow tables. From the password and salt (as well as the work factor) the output keying material can be calculated. It is possible to retrieve both a key from the output bits and the IV from other output bits.
Of course, now you'd have to store the salt value.
Full file names are also unique and could be used for a mode of operation by hashing the filename. However, that means that the file cannot be copied to another location, so generally we would try and avoid such brittle constructions.
There is of course nothing particularly wrong by storing a (random) IV, as long as it is unique with a high probability.

Would AES-256 in OCB3 mode be suitable for this sort of task or is there a better way of doing this?

It's not better or worse than any other AEAD cipher I suppose.

By the way, I am aware that it's quite easy to read the decrypted file from memory when it's decrypted at client-side, but I'm afraid there's not much I can do about it.

Well, you should harden your clients to the best of your ability. But yeah, in the end you need to access the data, and it is too large to fit into any kind of secure enclave in all likelihood.

Edit: Both server and client programs are written in c++. I also want to be able to encrypt and decrypt the files just in memory at runtime, so a lot of file encryption tools don't really fit the task.

Tools: possibly not. Higher level encryption libraries are however certainly available, and libsodium has already been mentioned.


Correct method to encrypt data so that it can be decrypted only by Alice and Bob I need to build a system that stores encrypted transactions. Transaction involves always two parties. Payer and payee. Both must be able to download encrypted transaction from server and decrypt it using their own private key. And likewise issuing transaction must be possible by either one just by knowing both's public keys.

Is it safe to encrypt exactly same message twice (using different public keys), first by Alices public key and then by Bobs public key?(and make both 'versions' available) That way Alice can decrypt the first one and Bob the second one using their private keys. If attacker knows that two encrypted messages are actually the same, can that information help him crack the encryption?

Or is there a smarter way? And what algorithm do you recommend? I was thinking of RSA

The traditional way to go about this would be to generate a symmetric key and use AES to encrypt the transaction using that symmetric key. You would then encrypt that symmetric key with Alice's public key and publish that. Then encrypt the symmetric key with Bob's public key and publish that. You also publish the AES encrypted version of the transaction.

I say that is the traditional way is you could, theoretically encrypt the transaction directly with RSA (though it is typically not recommended). The transaction would have to fit size constraints (see my comment).

Now, there is one additonal requirement that you might not be aware of. I'm assuming that you wouldn't want anyone to be able to modify any of these messages that will be uploaded to a server without being detected (think a hacker breaking into the server). Therefore, you will have to digitally sign the copies of the encrypted symmetric keys and compute a MAC on the AES encrypted transaction. The MAC could be a traditional HMAC or by using an authenticated encryption mode such as GCM.


One time Key Encapsulation Mechanism? For KEM's, do you only exchange a private key once via the public key encryption and then do all further encryption with this private key, or is a fresh private key sent out with each message?  The latter seems inefficient, but I could also see issues in having to store private keys for everyone.

In general you simply create a new symmetric secret key for each message. You wrap this using a trusted public key for the person holding the private key. In general you use KEM just because you don't want to encrypt/decrypt the entire message with the asymmetric key pair. Using a hybrid cryptosystem is much more efficient.

If you need to create a transport protocol you could also use KEM to establish session keys. You'd need to store those session keys for the duration of the session. Keys don't generally take a lot of resources, but you would have to keep them relatively secure, yes (at least as secure as the data you're sending during the session anyway).

In the case of a transport protocol with sessions you'd probably be better of by using an authenticated key agreement protocol though. In that case you may not need KEM.

For symmetric systems it is better to use the term "secret key" than "private key". This helps to distinguish symmetric keys from private keys that are part of an asymmetric key pair.


Derive operations from an arbitrary number I don't really know how to phrase this question, so I'll just mention the idea. This is partially reminiscent (at least in spirit to white box crypto): Can one derive arithmetic operations from a number? Is there a formula to do that?

So, the simplest example would be:

a = 4
ops = get_operations(a)
print(ops)

/* output:
*
* b = 2
* c = 2
* return b + c
*/

The idea is to simply have a way to "derive" a mathematical operation from a value. There are obviously more than "one" operation that could be derived from the above example. The system does not have to be complete.

The flow of such a "derivation" algorithm in my head is as such:

Get input (k)
Randomly choose an arithmetic operand (P) where y = k (P) x and store the operand (P)
Pick a random number (x) and store its value
Solve for (y) and store its value
Now, we have a combination of (P), (x), and (y) that, when solved, would yield the correct input (k).

My question is this: did someone research this and make a way better algorithm that what I could muster up here?

Is there a formula to do that?

Your example looks like a problem about Partitions to me. A partition is a way of representing a positive number as a sum of $n$ positive integers, for example:

The partitions of the number $5$ are:

$5 \space (+0)$
$4 + 1$
$3 + 2$
$3 + 1 + 1$
$2 + 2 + 1$
$2 + 1 + 1 + 1$
$1 + 1 + 1 + 1 + 1$

Since partitions consider every possibility valid, the number for possible ways of any integer $n$ can grow very fast, i.e. the number of possible partitions of the number $100$ is $190,569,292$.

There exist some formulas (some more complicated or faster than others and some are only approximations).

In your example you only have an operator once, so here $4 + 1$ and $3 + 2$ would be a possiblity.

Since you mentioned "more than one operation", a possibility would also be to represent numbers as their prime factors, for example:

The prime factorization of the number 22 is:

$2 \times 11$

There's always only one possiblity to represent a number as it's prime factors (if you don't care about the way you write it ($2 \times 11$ is the same as $11 \times 2$)).

There are a lot of factoring algorithms, since this is still a unsolved problem (Does P = NP ?) and this problem is important for cryptography.

I assume that a problem occurs if you'd try to do this with the operators of division and subtraction, for example:

There are infinite possibilities to represent a number as a subtraction, for example:

For the number $5$:

$6 - 1$
$7 - 2$
$8 - 3$
$9 - 4$
$\ldots$


Will non-ECC algorithms like RSA eventually become too inefficient? The strength of symmetric and asymmetric encryption schemes scales with the key length, but there is a difference between symmetric algorithms like AES and asymmetric algorithms like RSA.

For example, according to some sources, 128 bit symmetric keys are equivalent to 3072-4096 bit asymmetric keys; but to get 256-bit equivalent security, asymmetric keys need to be more than 15000 bits long.
Elliptic curve keys, however, are often stated to be comparable to symmetric encryption keys (with a constant factor of about $1/2$).

Is there an exponential relation between the key length for symmetric/ECC and asymmetric encryption schemes, and what are the theoretical and practical implications of that? Will there be a point in time where using RSA and DH/DSA will be impossible because of the huge key sizes and the resulting computations?

How does this relate to the notion of computational security, especially the security parameter of an algorithm – is the security parameter exactly the key length, or can the key length be a (polynomial? exponential?) function of the security parameter?

RSA will never become "impractical" until it gets broken. (in polynomial-time)

As the best current algorithm to break RSA is sub-exponential (general number field sieve / GNFS). According to Moore's law computing power grows exponentially however. So simply increasing key size will always be an option.

Beyond 256-bit security EC crypto just is significantly faster than "classic" crypto. For example, for 512bits, EC crypto is 64 times faster than classic crypto (compared to private key operations using RSA).

If you are interested in key sizes you should read this paper.


DES: Computing the output of S-Box 1? If the 48-bit input to the S-box is 0xAAAAAAAAAAAA, what are the first four bits emitted by S-box 1?

Answer: 0110

I know that an S-Box takes n inputs and give m outputs and that n != m, but I really don't see how they got that answer.

Since a S-Box takes 3 bits and maps it to 2 bits how can you predict what AAA will be?

DES has a total of 8 s-boxes which takes 6-bit input (say $b_1b_2 ... b_6$) and produces 4-bit output. The s-boxes are the 2-dimensional array of size 4x16.
The bits $b_1b_6$ determine the row of the s-box and bits $b_2b_3b_4b_5$ determine the column. The value of 6-bit input is substituted with the value at cell $S_i[b_1b_6][b_2b_3b_4b_5]$.

In your given question the output of 1st s-box will be the value of $S_1[3][15]$

For reference, you can Cryptography: Theory and Practice, Third Edition (Discrete Mathematics and Its Applications) page 97.


One time pad key exchange If two parties want to communicate with securely using OTP , how is the key ( that is lengthy as plain text) shared with other party for decryption ?

That's a well-known disadvantage of using OTP. Like in the ancient times, you could e.g. employ a trusted courier for that transfer.


The length extension attack and security on length shortening of a hashed message by one byte MD5, SHA1, SHA2 are vulnerable to length extension attacks Wikipedia:Length extension attack.
Could is also be possible to generate $H(\text{message}[1..n-1])$ from $H(\text{message}[1..n])$ if I know the last byte?
It's essentially the same question as md5: is reverse length-extension attack possible?
Might it become possible, when I just want to shorten the message by just one byte in any of MD5, SHA1 or SHA2? Or could I at least reduce the computational cost of a brute force attack?

Could is also be possible to generate $H(\text{message}[1..n-1])$ from $H(\text{message}[1..n])$ if I know the last byte?

No, the length extension attacks are not working exactly like that. Let see how MD5 operates;
MD5 divides a message into 512-bit blocks to operate1 in Merkle–Damgård fashion way. Every message is padded. The messages are padded with 1 and following many zeroes so that the padded message size is multiple of 512 with the message length appended at the end represented in 64 bits. In a minimum way with always 1 is added the number of zeroes can be zero.
More formally, add bit 1 than add as many as required bit 0 until message length in bits $\equiv 448 \pmod{512}$ then add the message length in 64 bits. This also limits the file size that can be hashed with MD5.
So the $message[1..n-1]$ is calculated with $message[1..n-1] \mathbin\| padding$. After the padded message one can execute the length extension attack. The extended message with padding is;
$$\text{message}[1..n-1] \mathbin\| \text{padding} \mathbin\| \text{extension}\mathbin\|\text{padding}$$
To execute a length extension attack, one replaces the initial value of the target hash function with the hash. After this calculate the extended hash as usual hashing. Formally

let $\text{MD5}'(m,\text{MD5IV}) = \text{MD5}(m)$. I.e. $\text{MD5}'$ enables to control of the IV of the MD5.
let $h = MD5(m)$ of a message $m$.
then $h' = MD5'(m', h) = MD5(m\mathbin\|pad_1\mathbin\|m'\mathbin\|pad_2)$ where the $pad_1$ is the padding of $m$ when hashed with MD5 and $pad_2$ is the padding of $m\mathbin\|pad_1\mathbin\|m'$

The $h'$ is the length extended hash.

Might it become possible, when I just want to shorten the message by just one byte in any of MD5, SHA1 or SHA2? Or could I at least reduce the computational cost of a brute force attack?

After SHA3, there are variants of SHA2 like SHA512-256 that calculates a hash of output size 512 bits then truncates to 256. That almost eradicate the length extension attack's possibility. The SHA512-256 has a different initial value from SHA512-512 that separates the domains. In other words, they are different random oracles.
Of course, the pre-image resistance and secondary pre-image resistance and the collision resistance are weakened by $2^8$, $2^8$, and $\sqrt{2^8}$, respectively.

1The dividing is not specific to MD5 and diving size may change with each hash function like SHA512 uses 1024 bit block sizes


Is it wise to use HOTP (raw bytes) as a key for HMAC? Assume I have client and server applications with a shared master secret KEY_SECRET already in place. Also assume that the client and server have an implicit shared counter CTR initialized on the same value.

Is it wise to sign the data sent from the client to the server in a following way:

KEY_SIGN = HOTP(KEY_SECRET, CTR)
SIGNATURE = HMAC_SHA256(DATA, KEY_SIGN)

Client is technically able to compute the signature and server is able to validate it but I am wondering if this could have some hidden security / crypto / math side-effects.

Note: I assume "raw" HOTP format (4 bytes) here, not the decimalized version with the final "modulo D" that gives away the D-digit numeric code.

Note 2 (edit): As suggested in the comments below, using simply KEY_SIGN = HMAC_SHA1(KEY_SECRET, CTR) would gain much better key entropy.

As mentioned by SEJPM in the comments, four bytes is much too short for an HMAC key.

Since KEY_SECRET is already in place, you could just use it directly as a MAC key, but then you need to make sure that DATA cannot collide with any counter value. You could do this by prefixing DATA with enough constant values to make it longer than the counter.

For example: MAC = HMAC(KEY_SECRET, 0x01 * 9 || DATA, where nine 1-bytes are prepended to make it longer than the eight-byte counter of HOTP.


Curve25519 over Ed25519 for key exchange? Why? I've been reading up on the Signal Protocol (in this PDF) and it seems to be using Curve25519 for ECDH and EdDSA (with Ed25519) for signatures.

My question is why not use only Ed25519?

This implementation supports Ed25519 and key exchange so what is Curve25519 needed for?

Are there any security considerations where it beats Ed25519 key exchange?

This question from CryptoSE answered why to use Ed25519 over Curve25519 for signatures but why not to use Ed25519 for key exchange?

There's a few different related parts here, and the nomenclature of the library you've cited is a little confusing.

Curve25519 is an elliptic curve over the finite field $\mathbb F_p$, where $p = 2^{255} - 19$, whence came the 25519 part of the name.  Specifically, it is the Montgomery curve $y^2 = x^3 + 486662 x^2 + x$, but you don't need to know the details other than that it was designed to admit fast computation of $x([n]P)$ given $n$ and $x(P)$ which is useful for Diffie–Hellman key agreement.

(Side note: Sometimes the Montgomery form is written with the letters $u$ and $v$ as in $v^2 = u^3 + 486662 u^2 + u$, especially when drawing a contrast to another form like Weierstrass or Edwards.)
X25519 is a Diffie–Hellman function built out of Curve25519.  An X25519 public key is the encoding of the $x$ coordinate of a point on Curve25519, hence the name X25519.

(Historical note: Originally, X25519 was called Curve25519, but now Curve25519 just means the elliptic curve and X25519 means the cryptosystem.)
Edwards25519 is an elliptic curve over the same field, with a different shape, the twisted Edwards shape $-x^2 + y^2 = 1 - (121665/121666) x^2 y^2$, which admits fast computation of $P + Q$ given the $x$ and $y$ coordinates of $P$ and $Q$.  It is related to Curve25519 by a birational map, so most points on Curve25519 can be mapped to edwards25519 and vice versa.
Ed25519 is a public-key signature scheme built out of edwards25519, using the EdDSA construction.  An Ed25519 public key is the encoding of the $x$ and $y$ coordinates of a point on edwards25519.

Curve25519 and X25519 were developed first; then Harold Edwards came along and blew the minds of Dan Bernstein and Tanja Lange by inventing Edwards curves which let you compute $P + Q$ in constant time faster than any other curve shapes and competitively with variable-time (i.e., leaky) formulas for other curve shapes.  Fortuitously, it turned out that Curve25519 was birationally equivalent to a (twisted) Edwards curve, leading to Ed25519.  Under the birational equivalence of Curve25519 and edwards25519, each X25519 public key corresponds to two possible Ed25519 public keys.  As Ruggero explained, Curve25519 admits faster variable-base scalar multiplication, while edwards25519 admits faster fixed-base scalar multiplication and double-base scalar multiplication.

So what do you do if you want to use the same key material for key agreement and signature?  There are a few options:

The library you cited uses edwards25519 points as public keys, and converts them on the fly to Curve25519 $x$ coordinates for key agreement.  This is simple and works if you have full control over the public key format and can choose to use edwards25519 points.  It's confusing to call the function ed25519_key_exchange, but such is life.
XEd25519 as used by Signal uses Curve25519 $x$ coordinates as public keys, and for signatures, always chooses the ‘positive’ point on edwards25519 as a corresponding Ed25519 public key.  This is useful if you already have a lot of public keys deployed and you really don't want to redeploy them just to determine which ones are positive and which ones are negative.
The signature scheme qDSA, following an idea used in Mike Hamburg's Strobe, uses Curve25519 $x$ coordinates as public keys, and uses a variant of the EdDSA signature equation to take advantage of the Montgomery ladder and avoid the Edwards shape and point addition altogether.  This is useful if you want very small code like on a microcontroller, where there is a high cost to having several different scalar multiplication routines, e.g. for fixed-base vs. double-base.


Why is Ring-LWE more efficient compared to LWE? Can someone please tell me why is the Ring-LWE more efficient?
By introducing polynomials in place of matrices, what kind of optimizations do we introduce that make Ring-LWE more efficient?

If you're using LWE for cryptography, then you'll need a system of $n$ linear equations with errors (mod some $q$). So for those $n$ equations, your key size will have $O(n^2)$ coefficients. In Ring-LWE, you only need $n$ coefficients (see Oded Regev's survey, page 5).
Because you're dealing with polynomials now, you can use the Fast Fourier Transform or (even better for finite fields) the number theoretic transform to multiply them.


Require x of y possible passwords to decrypt Is there a way to set up encryption so that a certian number (x) out of a total (y) number of users/passwords are required to do the decryption?

Background: This is mostly a thought experiment, and I don't have a realisitic real world application for it, although they may exist. I recall first getting the idea from an interview with Edward Snowden (Neil deGrasse Tysons podcast I beleive), but cannot find any follow information about the concept.

Hypothetical example 1: There are 3 "leaders" to a finctional technologically country. In order to start a war, 2 of them must agree and provide their crypto keys to decrypt the required commands/codes.

Hypotheical example 2: There are 435 congressmen in the USA. Sometime in the future, bills must be passed using cryptographic methods. 50% of them must provide their key/password in order to get the master key and pass a law.

Trivial Solution: For each combination users, encrypt the master decryption key in order (alphabetical by username). For the first example, there are only 3 combinations, and it is trivial to just encrypt the master key 3 different ways. Unfortunately this does not scale well. For the second example, 218 out of 435 gives us ~3*10^129. (For reference, there are 10^80 atoms in the universe.)

Is their a more programatic way to perform this type of encryption? The more I learn about crypto, the more I see amazing applications for reletively straightforward mathematical algorithms.

This is a well studied problem in cryptography; what you're looking for is known as a Secret Sharing Scheme.  This is a scheme where we take a master secret, and from that generate $N$ shares, and with any collection of $T$ shares, we can reconstruct the master secret (and we can't with $T-1$ of them).  We can make $N$ and $T$ as large as we like, and so it works in the "any 218 out of 435" case.

See this article for more details, as well as pointers to practical ways to implement it.


How do hashes really ensure uniqueness? This might seem an impractical and unnecessary conversation, but I feel it's something I need to clarify. Especially, as I just got my first developer job in a blockchain startup.

So hashes are said to generate the same thing for any information it sees, and it's only a one-way interaction.

As far as I understand, hashes are just long alphanumeric strings. If one computes hashes across all documents, keys, information, files, etc, over and over again- it's simply a matter of time until the same combination comes up again for different information (applying it across all possible contexts)? This might be an impractical test given size and possibility, yes, but is it this that makes hashes powerful, that it's practically impossible to recreate a hash that for any foreseeable endeavor it's fine, or is there some element that I'm missing that reduces even that extremely low probability to zero?
Is there any design constraint that prevents a very powerful computer to back-calculate the original data from a hash? Or is it simply that the design is so complex that it's simply a futile exercise to dream of such a large computer required for this task?
What's stopping a hacker or malicious middle man to hack open the software program or library that creates this "hash" and then use that library to create hashes of his/her own or mislabel some target company's hash with his/her own pointing to their version of the file? Especially since many applications, languages, and developers use hashing independently. Whichever is most weakly secured, we can use that to take on the rest?

Any resources are also appreciated.

The simple answer is that hashes don't ensure uniqueness. Very broadly, hashes behave like "deterministic random numbers" – deterministic in the sense that hashing the same data always gives the same answer; random in the sense that the value of the hash is basically unpredictable without actually computing it. And sufficiently unpredictable that, for a good cryptographic hash, we don't know any way of finding a string with a particular hash, except for trial and error.

In particular, cryptographic hash values are close enough to truly random that the birthday paradox applies. That is, if there are $k$ different values the hash can take and they're all equally likely, you have to hash roughly $\sqrt{k}$ documents before the probability of finding two with the same hash is greater than a half.  So, if you're using a 256-bit hash, you'd need to look at about $\sqrt{2^{256}}=2^{128}\approx 3\times 10^{38}$ documents to even have a 50/50 chance of finding two with the same hash. For comparison, that's about 200 documents for every nanogram of mass in the Earth.


Avoiding collisions by combining MD5 and SHA-2 It is often suggested that hashing of long character columns can be used for indexing in databases, but the possibility of collisions is an issue for Unique indexes. Whilst I know that both MD5 and SHA-256 can (rarely) produce collisions, I was wondering what the possibility of them both clashing at the same point with the same input? In other words, if I produce a Unique key by running both MD5 and SHA-2 against the same character field and combining them to make the Unique key, is this collision free.

Currently no collisions are known for SHA-256 and it can be used safely to hash long texts and you can be confident you won't happen to get a collision by chance.
Generally speaking if we have two different hash functions and $f$ and $g$ and you hash some input $x$ with both and use the concatenation $f(x)||g(x)$ the collision resistance of this will be better than either function individually and in some cases much better.  If the functions are unrelated and you are only worried about chance collision the likelihood of a collision will be the product of the likelihood of collision in each function individually. However this last statement will not hold in face of an attacker exploiting weakness in these function. It's still harder that either individually but may not be noticeably harder to find a collision than finding a collision in just one of the two.
Other techniques of combining the functions such as $f(g(x))$ are ill advised and won't add security, since any collision of $g$ is also a collision in the composition.


What is security of stream cipher against chosen plaintext attack? I have been looking for image encryption after compression using Ax+e, where A is a random matrix, x is plaintext and b is a bitstream generated using a stream cipher. Suppose choosing plaintext as all zeroes (dark image), will reveal many keystream bits. With the sufficiently large amount of known keystream bits, it is possible to obtain the original key. Is there any upper bound on the number of known keystream bits for a stream ciphers that can guarantee a sufficient resistance against attacks? For example, if the sequence has been generated by an LFSR of length n, then the Berlekamp-Massey algorithm is guaranteed to find this LFSR after examining no more than 2n bits of the sequence.

Is it possible to make above system cryptographically secure against chosen plaintext attack?

Is changing the initiation vector frequently so that attacker can get the limited amount of keystream bits only solution?

How to use initialization vector in such scenario?

Is one-time permutation after obtaining keystream bits proper solution?

Suppose choosing plaintext as all zeroes (dark image), will reveal many keystream bits.

It doesn't matter. When using proper cryptographic cipher the bits revealed should not tell anything about the key or previous / next bits.

  With the sufficiently large amount of known keystream bits, it is possible to obtain the original key.

And this is where the term cryptographic comes to the game. The stream ciphers are designed to resist revealing its internal state so even possessing the complete amount of stream bits (used to encrypt the plaintext) it should be hard to derive the key and next bits.

Indeed the LFSR is very open to produce its internal state is not to be used as a stream cipher.

We already had a discussion on this forum. When using simple LFSR (such as common Random implementations with random seed) it is often enought to have very little of the ouput (in some cases 2 numbers) to reveal big part of the internal state and the rest is feasible to guess.

  Is it possible to make above system cryptographically secure against chosen plaintext attack?

Just use proper cryptographic cipher () and you should be ok (assuming you use keys with high entropy and unique iv).

  Is changing the initiation vector frequently so that attacker can get the limited amount of keystream bits only solution?
  How to use initialization vector in such scenario?

You don't need to change IV often. E.g. Salsa has internal state of 512 bits (key size of 256 bits) so it is prettty much enough to encrypt all you need.

It is more important the IV is unique (or random/unpredictable if you want to play safe) for each key reuse. The stream cipher will take care of mixing IV into its output.

  Is one-time permutation after obtaining keystream bits proper solution?

IMHO it is not necessary. When using simple permutations, it doesn't add any security (from the cryptographic point of view)


Is it possible to determine or estimate the period for Blum-Micali PRG? The Blum-Micali is a cryptographically secure pseudorandom number generator.

The construction (from wikipedia):

Let $p$ be an odd prime, and let $g$ be a primitive root modulo $p$.
Let $x_0$ be a seed, and let $x_{i+1} = g^{x_i}\ \bmod{\ p}$.
The $i$-th output of the algorithm is 1 if
$x_i < \frac{p-1}{2}$. Otherwise the output is 0.

I have toyed with small values of $p$ and have noticed that cycles occur if there's a fixed point, that is $x_{i+1} = x_i = g^{x_i}$.

For example when $g=3$ and $p=7$ (from wikipedia primitive root example), there are two fixed points where $3^4 = 4 \bmod 7$ and $3^5 = 5 \bmod 7$. This would be problematic for Blum-Micali generator since it would cycle and repeatedly output the same bit.

Is there a relationship with the size of $p$ and the period which is based on the likelihood of a fixed point?

Under the question's hypothesis, $x\mapsto g^x\bmod p$ is a permutation of $\mathbb Z_p^*$, that has some characteristics of being random.

If we take a random permutation of a set of size $s$, the length of the cycle iterating that permutation from a random point has length $l$ with probability exactly $1/s$, independent of integer $l$ with $1\le l\le s$. It follows that the cycle has length $l$ or less with probability exactly $l/s$.

This forms an heuristic argument (obvious, as pointed by Thomas in comment) that perhaps it is $\epsilon$-rare that the cycle length of the question's generator is much less than $\epsilon\,p$.

This is however very far from a proof or even a convincing argument. In particular, because $x\mapsto g^x\bmod p$ belongs to a very small and special subset of the permutations of $\mathbb Z_p^*$, with that subset having $(p-1)/2$ elements out of $(p-1)!$ permutations.

By contrast, D.W.'s argument is a valid proof that the cycle length is too large to be found when $p$ is such that the discrete logarithm problem is hard. However that gives a considerably looser safe estimate of the cycle length; perhaps likely at least $2^{100}$ for $2048$-bit randomly-seeded $p$, when the above heuristic argument suggests likely at least $2^{2040}$.


Any case that can require to encrypt a certificate revocation list before distribution As far as we know certificate revocation lists (CRLs) include public information so they do not have to be encrypted before distribution.

Is there a case that can require to encrypt it before distribution? A case in which eavesdroppers can capture some information from the CRL and use it to perform an attack?

No. A CRL is as public as the certificate it revokes; it has to be signed to guarantee authenticity, but not encrypted. There are no optional confidentiality requirements for CRL distribution in RFC 5280. It is not even common practice to use anything other than plain http for the CRL distribution points. The whole idea with CRLs is to get them out there to as many as possible, as fast as possible, with as little performance overhead as possible, without sacrificing authenticity.

That said, it might be worth pointing out that an attacker who has compromised the private key corresponding to a certificate, might have an interest in preventing clients to download any CRL revoking that certificate. One way to counter an attacker that both controls the network and has compromised the private key, is for the client to explicitly check the status of a specific server certificate, prior to connecting to the server. Combining CRL distribution with OCSP over https MAY be one way to prevent certain attacks.


Prime numbers in RSA encryption I'm studying how the selection of prime numbers in RSA encryption may affect the security of the encryption in regards to the public key.

Essentially, are there any specific types of prime numbers that render the most secure public key? (meaning that someone cannot backtrack the public key and figure out the private key)

Or do the prime numbers just have to be 'sufficiently' large?

Thanks for helping out :)

As long as the two primes are large and random, and ideally approximately the same size, they will be suitable for a secure implementation of RSA. For an $n$-bit RSA key, it's generally safe to generate two $n/2$-bit random primes. As long as the two primes are generated randomly using a cryptographically-secure random number generator, they can be used securely. The difficulty comes in quickly and accurately determining whether or not an integer is prime, but luckily there are probabilistic algorithms like the Miller-Rabin primality test which are quite effective when run a sufficient number of times.

The most common method of generating random primes involves generating a large, random odd integer and checking if it is prime. If it is not, then it is incremented by two and checked again. This repeats until it is prime. Note that this method does not find perfectly-distributed primes. It is biased towards primes with large gaps between it and the previous prime. However, there are no known ways to exploit this bias and it is believed that none exist. The alternate, slightly slower method of finding primes is to generate a random odd integer and check it for primality. If it is not prime, then rather than adding two and checking again, a new independent integer is generated and checked for primality.

If you want to use a standard for prime generation, consider FIPS 186-4, which should be safe.


Simple digital signature example that one could compute without a computer? I am working on a document to explain Bitcoin to students. But I am having a hard time translating the principle described in §2 of the Bitcoin whitepaper in layman's terms.

There is a great question (Is there a simple hash function that one can compute without a computer?) with a great answer, which helps to understand hashing in cryptography better. I am looking for a similar answer like the question above received, but related to Bitcoin… more specifically, the digital signatures (public key & private key) used by the Bitcoin protocol.

I'm trying to understand how a verification works in the image below:

The goal is to simplify the signature generation and verification algorithm in a way that I can make it understandable for students that are not familiar with digital signatures or elliptic curve cryptography at all. So, what I am looking for is a pseudo/toy-algorithm (something like the Caesar cipher) that the students can use to understand how public and private keys work in an extremely simplified way.

Does any such digital signature example exist that one could compute without a computer? Or could you give me a helping hand coming up with an example that I could provide to my students?

The main difference between what you want an example for (digital signatures) and secure communication is this: the roles of the public and private keys are reversed.

Also, the content being encrypted is different. For secure communication, the entire message is encrypted. For digital signatures, the message format is irrelevant; you are trying to prove authenticity, not protect message content. Rather, it is a digest, hash, or checksum of the message that is encrypted.

The signature algorithm computes the digest, encrypts it with the private key (known only to the sender), and includes this encrypted digest (the signature) along with the message, to prove its authenticity.

The verification algorithm takes the public key (known to everyone) and uses it to decrypt the signature, as well as computing the hash or digest of the message itself. It then compares its computed hash of the message to the decrypted signature. If they are identical, verification was successful. If not, verification fails.

This is in contrast to security usage, protecting the content of a message. In this case, the message is encrypted using the public key of the recipient, and thus can only be decrypted by that intended recipient who has the matching private key.

So if you have an existing pen and paper example for security purposes, you could just use that same example, reversing the roles of the private and public keys. It's just a matter of understanding the differences in the process.

The only additional piece is the digest or hash. You can choose any mathematical function for this; a checksum or simple equation would be fairly easy to compute by hand. A checksum for example could be used to make a digest this way:

Message: HELLO

We can make it simple: A = 1, B = 2, etc. So we have

  H = 8
  E = 5
  L = 12
  L = 12
  O = 15

The checksum is then computed by multiplying the position of each letter by its value, and summing them all up. So now we have

checksum(HELLO) = (8*1)+(5*2)+(12*3)+(12*4)+(15*5)=8+10+36+48+75=177

Now we encrypt 177. If our encryption method is xor (to simplify things on paper) and our private key is 915, the xor result is

177^915

Simplify using place values:

=(1^9)*100+(7^1)*10+(7^5)

Simplify again using binary:

=(0001^1001) | (111^001) | (111^101)

Now we can easily compute the binary xor operations and add the results:

=1000 | 110 | 010

Back to decimal:

=8*100+6*10+2=862

So we send the message HELLO862 probably along with some way to specify the message length. In most cases the signature might not be distinguishable from the message itself without knowing in advance how long the message is.

Then take 862, the signature, back through the decryption process. In our case we used xor which is a symmetric encryption, so it sort of defeats the purpose, but when using RSA, your private key and public key are two different numbers.


Authentication scheme to protect against fake devices I want two embedded devices (call them master and slave) to communicate with each other. For intellectual property protection, the master must reject fake slave devices (the other way around is a pre but not a requirement).

I'm having no luck finding a scheme that satisfies the following requirements:

Authenticated: For each message received by the slave, only if the slave is genuine it knows how to interpret the message
Replay-resistant: Can't record a conversation with genuine slaves and replay it later with fake slaves,
Autonomous: No third party involved (trusted or not),
Fast: Slave has a slow processor so any number-field theoretic ciphers are out of the question, even for key-exchange

Also:

No confidentiality required, messages are not secret,
Messages are short; never in excess of 16 bytes,
Slaves have a unique serial number that the master receives in plain,
Only slaves can have a secret embedded in it, not the master (and can be unique for each slave),
Only master can generate entropy / secure random data,
Without secure co-processors, SIM or SAM modules.

Even though the messages are not secret, they must probably be encrypted nonetheless. If the adversary obtains fake slaves and generates fake commands (i.e. fake master) then they might as well buy everything from the competition. We (as a company) thrive on the broad feature set of the master that interlinks many kinds of slaves.

My attempts at thinking of a solution:

Public-key cryptography or Key-exchange schemes: Too computationally heavy for the slave.
Slave is an encryption-oracle and master knows one (or more) legal plain/ciphertext combinations: Replay attack.
A commutative cipher $E_{k1}(E_{k2}(P)) = E_{k2}(E_{k1}(P))$ such that when $E_{k1}(E_{k2}(P))$, $E_{k1}(P)$ and $E_{k2}(P)$ are all known to an evesdropper, $P$ can't feasibly be retrieved. (i.e. CTR mode is out of the question). I have yet to find such a cipher.

I tried to be as thorough as possible, but let me know if I missed some requirements.

[edit] Removed an optional requirement that allowed listen-only fake slaves to co-exist with a real slave.

There is no cryptographic solution, that is one secure under the assumption that keys are the only secrets.

The requirement Authenticated and Replay-resistant imply that fake slaves can't interpret commands intended for genuine ones; hence the use of encryption. Since the master is assumed unable to hold any secret, only public key cryptography with a private key in the slave could secure that encryption, or its key establishment. And the slaves are hypothesized not powerful enough for that.

This is not changed even if we relax the requirements to allow:

Random number generation in the slave (which often is possible, especially in a device with a secret; e.g. by enciphering a counter held in EEPROM memory, or careful accumulation of entropy from analog sources, including clock drift and timing of external stimulus).
Public-key cryptography in the slave limited to the public-key side (a PIC18F24Q10 costing less than a dollar can do the public-key side of RSA in a fraction of a second, and that might be needed only once the first time an instance of the master establish connection).

For something with cryptographic security, we need at least one of:

Public-key cryptography with a private key in the slave; that rules out RSA, perhaps not ECC (depends on hardware, power budget..).
Some secret in the master (see final section)

Cryptography can help on one thing: the serial number of each genuine slave can come with a static cryptographic signature written at factory and checked by the master. That won't prevent cloning genuine slaves with their serial number and signature, but will make it impossible to manufacture a larger quantity of clones with distinct serial numbers than one has managed to gather signatures; it might also allow to blacklist clones according to serial number (e.g. in new releases of the master).

On the slave side that requires only persistent storage and transmission of about 64 bytes with EdDSA, for 128-bit security (and slightly more compact signatures exist). The master checks the signature against a public key that it embeds (we must assume integrity of the master). The private key is used only for production of genuine slave devices.

White-box cryptography (our tag white-box) could allow a secret in the master. Even though it typically fails under determined attack, that's the closest thing to a satisfactory solution. Sketch:

slave is asked and gives its serial number;
master uses white-box crypto to encipher that serial number using a master key implemented by the white box, and that gives the slave's diversified secret that was written in the slave at fabrication time;
master and slave now have a shared secret and use (authenticated) symmetric encryption like AES-GCM (though if the genuine slave is to be protected against replay, it neeeds a RNG or a persitent storage).

Refinements:

white-box crypto is used in the master beyond computation of the slave's diversified secret;
use of a session key for the authenticated symmetric encryption;
the slave contains several secrets, and selects which it uses according to a key version given by the master (that allows to recover from extraction of the master key from the white box; slave clones made using that will stop to work with new releases of the master, which can use improved white-box crypto);
use of a static cryptographic signature (see second section), best transmitted only encrypted by the slaves to make their collection slightly harder.


Why are password database breaches bad if cryptographic hashes can't be reversed? If companies such as Facebook store our passwords as hashes, when they are leaked how can this be a threat to the users? I thought of it because nowadays we do not have computational power to break those hashes, so how can a criminal use those hashes against the users?

Users have a habit of choosing passwords badly so that they can be guessed much more easily than cryptographic keys, requiring (say) only a trillion ($10^{12} \approx 2^{40}$) guesses on average instead of a duodecillion ($10^{39} \approx 2^{128}$, or thousand sextillion in the long scale) guesses on average.  Users also have a habit of reusing passwords from site to site, like using the same password for Facebook and Gmail.

Suppose I'm trying to break into your Gmail.  There's only a limited rate at which I can test guesses for your password.  Even if I can narrow your likely passwords down to a trillion possibilities, I can't try more than a few passwords every second at Gmail—even if I had a colossal botnet around the world to avoid IP-based rate limits, and even if I did it in bulk to many targets to avoid account-based rate limits, I'd still be limited by network bandwidth.

But if Facebook's password database gets breached—even if they do everything right like using salts to thwart rainbow tables, using argon2id to raise the computational cost of testing a guess, using OPAQUE to thwart adversaries on the network—then I can try guesses without using the network.  No more rate limits to work around.  No more network bandwidth to worry about.  No more botnet to manage.  I can try guesses offline using my supercomputer cluster tucked away in my evil lair built into the simmering underbelly of a volcano powering my machinations with geothermal heat while sipping at my martini and cackling evilly.

And once I have confirmed a guess for your Facebook password I can try it at Gmail.

There are some mistakes that Facebook could do to make it worse:

Facebook could fail to salt their password hashes uniquely per user.

Then I can search for one of many passwords given their hashes even faster using multi-target attacks like rainbow tables[1] in parallel[2]; if the cost to find one password given its hash is $C$, the cost to find the first of $t$ passwords given their hashes is $C/t$, and the time to find them can be as little as $C/tp$, as long as my volcano supercomputer lair is parallelized $p \geq t^2$ ways.
Facebook could fail to use a costly password hash like argon2id, and instead use MD5.

Then the offline computational cost to test a single guess is as cheap as computing MD5, which costs a few hundred cycles on a typical CPU and negligible memory, in contrast to argon2id which can be scaled to cost billions of cycles and gigabytes of RAM and multiple CPUs in parallel according to the legitimate user's available resources.  This lowers the cost $C$ to find one password and the cost $C/t$ to find the first of $t$ passwords.

In practice, Facebook probably doesn't offload the password hash to the user's computer, so they probably won't use argon2id with billions of cycles of CPU time and gigabytes of RAM and multiple CPUs in parallel, but they will probably use something more expensive to compute than MD5.
Facebook could use a hash that fails to have preimage resistance.

This one is a stretch because essentially no major hash function with advertised preimage resistance has ever been broken[3] (archived).  But if Facebook—for some inexplicable reason—used 2-pass Snefru to hash passwords, then in principle there may be a shortcut to finding a password given its hash more cheaply than just trying passwords until one works[4].
Facebook could just accidentally log their passwords in cleartext.

Well, this one actually happened[5], but Facebook swears that the logs were visible only inside Facebook and that nobody breached Facebook and that nobody inside Facebook would ever dream of abusing insider information like that[6] (archived 2019-06-19), and disclosed it on a night of big news of a long-awaited drama in United States national politics[7].


Variable length variable output encryption with out any padding? I would like to know if there is any encryption algorithm with variable input variable output with out any padding? For example if I give 16(17,18,67,117,..any size) bit plaintext, my ciphertext is also 16(17,18,67,117,..any size) bits.

It is important to understand that secure encryption - by the standard notion of security - must be probabilistic. This is so that the same value encrypted twice will look completely different. Otherwise, it is possible to compute statistics and learn a lot of information. The easy fact based on this is that secure encryption must increase the size (the ciphertext has to be bigger than the plaintext).

It is possible to also assume state. For example, if the encryptor and decryptor can keep track of a unique nonce (e.g., a counter), then it is possible to still get secure encryption. (For example, use CTR mode.)

If you don't have either of these, then you are in trouble. This doesn't mean that you can't do anything reasonable, but we don't have enough information about your application to help. Just encrypting using format-preserving encryption can be very problematic, depending on what you want to do. I refer to a recent paper by Seny Kamara and others that will appear at ACM CCS 2015 that presents attacks on databases encrypted using deterministic encryption.


Are Authenticated Encryption ciphersuites supported in legacy TLS versions older than TLS 1.2? I have read in a paper that Authenticated Encryption (by this I mean those that support GCM mode or ChaCha20 ciphers) are not supported in versions older than TLS 1.2?

I could not confirm this as the paper does not provide a reference. Can any expert confirm this information?

Pretty sure AES GCM is only defined for TLS 1.2.  If you look at RFC 5288, it's titled "AES Galois Counter Mode (GCM) Cipher Suites for TLS" and it only defines suites for TLS 1.2:

  The following cipher suites use the new authenticated encryption
     modes defined in TLS 1.2 with AES in Galois Counter Mode (GCM)

Later on it says

  These cipher suites make use of the authenticated encryption with
     additional data defined in TLS 1.2 [RFC5246].  They MUST NOT be
     negotiated in older versions of TLS.  Clients MUST NOT offer these
     cipher suites if they do not offer TLS 1.2 or later.  Servers that
     select an earlier version of TLS MUST NOT select one of these cipher
     suites.

While this doesn't mean that a different, particularly a later, RFC couldn't have defined them, I can't see why one would have done so.


How can a hash have a fixed length? I am very new to cryptography, I apologize if my question is so basic.

I do not understand how a hash can have a fixed length, because you can have infinite inputs to a hash function. With a fixed length you would have limited possibilities of hash outputs. So a hash can have different messages with the exact same output?

So a hash can have different messages with the exact same output?

Yes; that's true of any function with inputs longer than the output.

What collision resistance of a hash function doesn't mean that there aren't two messages $X$ and $Y$ that hash to the same value; instead, it means that it's hard to find them.


how does https key get shared? I am only a beginner and doesn't know much about https. I have heard that they uses somekind of a key and is shared between them. If an attacker wishes to attack could he be able to capturebthe key and attack?

No, an attacker listening to the SSL connection is unable to get a copy of the keys.

This is actually a fairly fundamental property of SSL (or any other protocol that encrypts traffic); we're encrypting the traffic because someone might be listening in, and we want to prevent them from being able to understand the traffic.  We do this by having the two side share keys, and using those keys to encrypt the traffic.  If the guy in the middle could recover the keys, they could listen in.  Hence, any encryption protocol must have some story why someone in the middle cannot recover the keys.

Actually, SSL can do it a number of ways, depending how what the two sides agree on (the "ciphersuite").  I'll describe the most common method.

This method (which I believe is used when, say, you're doing a connection with Amazon) depends on the magic of Public Key Cryptography.  What this allows us to do is have one side (the Server) generate two related keys, the "public key" and the "private key".  Someone can encrypt a message with the "public key"; however the public key does not allow you to decrypt; in essence, it acts as a "one-way" box.  However, someone with the private key can decrypt messages.

So, here is a simplified summary of it works: you (the client) ask the Server for a copy of its public key; it gives it to you.  Then, you pick a random value (the "premaster secret"; at your level, you can think of it as the session key), and encrypt that with the servers public key, and send that.  The server then receives the encrypted value, and then decrypts it.  At this point, both sides share the same premaster secret (the client because it originally picked it, the server because he just decrypted it), and so can use that value to come up with the session keys.

Now, here is what someone in the middle hears:

The Server's public key.
The random value encrypted with the public key.

Now, the Server's public key does not allow him to decrypt the random value (remember, the public key allows only encryption), and so he cannot learn the value that was shared.

Now, if you think about this, one thing may occur to you: how does the client know that the public key he got was actually the Server's public key; couldn't someone who can modify messages in the middle substitute his own public key and pretend to be the server?  Well, SSL does have defenses against that; however, that involves more Public Key Cryptography, and so I'll leave that out for another day.


Can md5 be used for encrypting data? I know that md5 shouldn't be used for password hashing because of collisions and possibility of making dictionary attacks e.g. using rainbow tables. But what about other uses? Can I use md5 for encrypting data?

Say, attacker gains access to database where sensitive data was stored using md5. He wants to know just this data that was hashed, not another data that gives this hash. Can he do it?

I know that there are better cryptographic hash functions so don't suggest to use them if md5 is enough.

If the question is "if I just had MD5 as my sole cryptographical primitive, could I use it to encrypt", well, the answer is yes, you can.  Then are a number of standard block cipher modes that don't assume invertability of the block cipher, and hence would work just find if you plopped MD5 (or rather, a keyed MD5, where you ask MD5 to hash both the input block and some keying data) right there.  Examples of such modes are CFB, OFB and Counter mode.  We don't do this in practice, both because MD5 hasn't been studied in such a mode (because the assumptions we're making on MD5 aren't the standard assumptions of hash functions, but ones concerning a large number of hashes from related images), so no one could say that it is secure), and because it would be rather slow.

On the other hand, your question would appear to be "if I have a database that includes an MD5 hash of some data, could I reconstruct what the original data was".  Well, we don't normally call that "encryption" (because there's no way to undo that operation).  And, if that is your question, the answer is no (unless you can guess what that data is, and verify it by doing an MD5 on your guess).  Even if the original data was short enough that there is unlikely to be another string that short that hashes to the same value, there is no known way (other than brute force) to find MD5 preimages, much less a specific MD5 preimage.


I'll assume that $p$ and $q$ are prime.

Here's one approach to recover them

Step 1: recover $l = d^{-1} \bmod n$
Step 2: select a random $x$ and compute $y = x^l \bmod n$

Here's why such a $y$ is interesting.

We have $y \equiv 1 \pmod q$ (because $l$ is a multiple of $q-1$); similarly, we have $y \equiv 1 \pmod p$.  However, if we consider $y \bmod p^2$, the group order of $\mathbb{Z}^*_{p^2}$ is $p(p-1)$; $l$ is unlikely to be a multiple of that (and will never be if $p$ and $q$ are the same size), and so we have (with great likelihood) $y \not\equiv 1 \pmod{p^2}$

Step 3: compute $z = \gcd(y-1, n)$

$y-1$ is a multiple of $pq$, but not a multiple of $p^2q$, hence $z$ will be $pq$.

Then, it's trivial, $p = n/z$ and $q = z/p$

Now, the above might not work if the prime values $p$ and $q$ were deliberately selected to have $y \equiv 1 \pmod n$ consistently.  However, we have another method:

Step 2': set $l_0, k$ such that $l_0 = l / 2^k$ is odd
Step 3': select a random $x$ and compute $y_0 = x^{l_0} \bmod n$
Step 4': for $i := 0 .. k-1$

Check if $x_i = 1$; if so, fail (and go back to step 3' and select a different x)

Check if $\gcd(x_i - 1, n) \neq 1$; if so, that gives you a nontrivial factor of $n$ (and return success; completing the factorization should be straight-forward)

Otherwise, compute $x_{i+1} = x_i^2 \bmod n$

Here's how the above works; we know that we'll have $x_k = x^l \bmod n = 1$, and so $x_i \bmod p$ and $x_i \bmod q$ will both become 1 at some point in the computation; however it is likely that they'll become 1 at different points in the process; that is, one of them will become 1 first (and if so, the gcd will catch it)


How to get exact number of slots in HElib? Such as 256, 4096 In the Homomorphic Encryption Library, HElib (https://github.com/homenc/HElib), we set up a set of parameters before generating the ciphertext.
For example:
m = 20191, p = 47, phi(m) = 19800
  ord(p) = 66
  normBnd = 1.62077
  polyNormBnd = 4.92719
  factors = [61 331]
  generator 2 has order (== Z_m^*) of 60
  generator 985 has order (== Z_m^*) of 5
r = 1
nslots = 300
hwt = 0
ctxtPrimes = [6,7,8,9,10,11,12,13,14]
specialPrimes = [15,16,17,18,19]
number of bits = 778

security level = 77.9265

Finally, we get the ciphertext with 300 slots. But I want to get ciphertext with 256 slots.
When I use the function findM(/*k=*/80, /*nBits=*/500, /*c=*/2, /*p=*/47, /*d=*/1, /*s=*/256, /*chosen_m=*/0, /*verbose=*/true);, cannot get the proper parameter m to generate 256 slots.
So how should I select the parameters to get 80/120-bit security, ciphertext with 256/4096 slots.

The number of slots is $\varphi(m)/\text{ord}(p)$, where $\varphi(m)$ is the totient of $m$ and $\text{ord}(p)$ is the multiplicative order of $p$ mod $m$ (and hence divides $\varphi(m)$).
In order for the number of slots to be 256, it must be the case that $\varphi(m)$ is divisible by 256. Recall that $\varphi(m)$ is the product of the totients of all the maximal prime powers that divide $m$, i.e., $\varphi(m) = \prod_i (p_i-1)p_i^{e_i-1}$ where $m=\prod p_i^{e_i}$ is the factorization of $m$ into powers of distinct primes $p_i$.
To make $\varphi(m)$ divisible by $256=2^8$, observe that for odd $p_i$, the corresponding term $(p_i-1)$ in $\varphi(m)$ is divisible by some power of two, and these powers combine across the primes. However, higher powers of such primes don’t give us any high powers of two (nor do they hurt). Alternatively, if one of the $p_i=2$, then it contributes a factor of $2^{e_i-1}$ to the totient. As an extreme example, we could take $m=512$ and immediately get $\varphi(m)=256$.
The divisibility condition is necessary but not sufficient; we also need to choose a prime modulus $p$ whose order is $\varphi(m)/256$, i.e., the cyclic subgroup of $\mathbb{Z}_m^*$ generated by $p$ should have that order. This is a bit more subtle. One method that can work is to use the Chinese Remainder Theorem: we know that $\mathbb{Z}_m^*$ is isomorphic to the product of the groups $\mathbb{Z}_{p_i^{e_i}}^*$, so we can find a suitable condition in each component and then use CRT to find a suitable prime $p$.
An extreme example is when $m=512$ (so $\varphi(m)=256$). Then it is necessary and sufficient to take a prime $p$ of order 1, i.e., $p=1 \pmod m$. More generally, for odd $p_i$ the component $\mathbb{Z}_{p_i^{e_i}}^*$ is cyclic, so we can find an element $g_i$ of any order that divides the order of the component, and we want the product of these orders (of the $g_i$) to be 256. Finally, then, we can seek a prime $p$ that is congruent to $g_i \pmod{p_i^{e_i}}$ for all $i$. This may give us what we want overall, but beware that the order of $p$ may not be the product of its orders in each CRT component,
so some trial and error may be needed.


Reasoning about WebCrypto ECDSA choices: P-256/384/521, SHA-1/256/384/512? When implementing EC signing/verification in Javascript, the only options available via the WebCrypto API are:

Curves: P-256, P-384, or P-521

Hashes: SHA-1, SHA-256, SHA-384, or SHA-512

If I was not constrained by these choices, I'd choose Ed25519. Would ECDSA with P-256 and SHA-256 provide an equivalent level of security (assuming I trust the NIST curves)?

How should I reason about the WebCrypto choices available to me?

Don't use SHA-1.

There's unlikely to be a substantive difference between the other choices, as far as you're concerned, except performance:

SHA-256 is might be cheaper on 32-bit CPUs; SHA-384 and SHA-512 are cheaper on 64-bit CPUs.
NIST P-256 is likely to be cheaper than NIST P-384 which is likely to be cheaper than NIST P-521.

All of these choices provide at least a 128-bit security level.

ECDSA is generally dangerous, of course, because implementations tend to require an entropy source when making signatures, with a catastrophic failure mode, unless you can positively confirm that your implementation uses RFC 6979 deterministic signatures.


How do SignRecover and VerifyRecover work? In PKCS#11, there are the SignRecover and VerifyRecover methods,

where the data can be recovered from the signature. How do these methods work?

Can I implement signrecover and verifyrecover with openssl?

TL;DR: they might not.
PKCS#11 is a standard for the software interface to cryptographic tokens (such as HSMs or Smart Cards), aiming at compatibility between implementations made by different token vendors. It also allows the same API to use various cryptographic mechanisms performing similar tasks by changing only a few values, mostly the Mechanisms parameter (an integer with a standard-assigned value) and some sizes.
PKCS#11 was written under supervision of RSA Security, and archives of that period are linked from EMC's PKCS#11 page. PKCS#11 moved to OASIS, which turned these into (in particular) Base Standard v2.40c01 (2014-12-23) and Current Mechanisms v2.40c01 (2014-12-23); these are scheduled for approval on 2015-04-15 with minor changes.
PKCS#11 has an API for signature schemes with (total) message recovery; that is, a kind of signature scheme where the (whole) message being signed is conveyed in the cryptogram of the signature, and is an output of the signature verification, rather than an input (as in the case in a signature scheme with appendix, e.g. RSASSA-PKCS1-V1_5 or RSASSA-PSS of PKCS#1).
For signature production, C_SignRecoverInit and C_SignRecover are to signature schemes with (total) message recovery what C_SignInit and C_Sign are to signature schemes with appendix, with exactly the same interface. For signature verification, C_VerifyRecoverInit and C_VerifyRecover are to signature schemes with message recovery what C_VerifyInit and C_Verify are to signature schemes with appendix, with a difference in the interface of C_VerifyRecover: it produces as output the recovered message (nominally identical to the message passed on input to C_SignRecover), when C_Verify receives as input the message to verify (nominally identical to the message passed on input to C_Sign).
Reference: Definition of C_VerifyRecover, and my memory.

CKM_RSA_X_509 is the simplest Mechanism that may be supported with C_SignRecoverInit, C_SignRecover, C_VerifyRecoverInit, C_VerifyRecover. Basically that's textbook RSA.
For the CKM_RSA_X_509 Mechanism, ignoring checks pertaining to the session state:

C_SignRecover perform just as C_Sign; that is:

checks that the size of the message to sign is at most $k$ bytes where $256^{k-1}\le N<256^k$ and $N$ is the RSA public modulus
converts it to integer $m$ by big-endian conventions
checks $m<N$
produces $s=m^d\pmod N$ where $d$ is the RSA private exponent
converts $s$ to $k$ bytes by big-endian conventions, and output it.

C_VerifyRecover

checks that the size of the signature is exactly $k$ bytes
converts it to integer $s$ by big-endian conventions
checks $s<N$
produces $m=s^e\pmod N$ where $e$ is the RSA public exponent
converts $m$ to $k$ bytes by big-endian conventions, and outputs it.

Reference: Definition of the CKM_RSA_X_509 Mechanism; its table of sizes of inputs and outputs (where £ is to be read as ≤); and my memory.

Cautionary notes:
The CKM_RSA_X_509 Mechanism should only be used as a building block, because textbook RSA is unsafe.
The CKM_RSA_9796 Mechanism, used as example of signature schemes with message recovery in PKCS#11, should not be used, and is not secure under chosen-message attack, even though that was among its design goals. It is (a slight variant of) ISO/IEC 9796:1991 (perhaps on sale here), but withdrawn and next to forgotten (it was planned to be rechristened ISO/IEC 9796-1 but suffered fatal wounds before the ceremony formal approval: forgery is possible from the signature of 3 chosen messages).
The CKM_RSA_PKCS Mechanism (which may support signature with message recovery) should not be used to sign a message under direct control of the adversary, because it is not secure under chosen-message attack (it was not intended to be; variants that hash the message as required by RSASSA-PKCS1-V1_5, such as CKM_SHA256_RSA_PKCS, are stronger, but still are not recommendable except for compatibility with existing systems).
PKCS#11 does not have an API for signature schemes with partial message recovery, and does not support ISO/IEC 9796-2 (any scheme), which is often how message recovery is used (e.g. in Smart Cards for EMV banking, European Digital Tachograph certificates); ISO/IEC 9796-2 with PKCS#11 is thus typically implemented on top of PKCS#11 with CKM_RSA_X_509, or as a proprietary extension, or perhaps as an internal component of a (possibly standard) Mechanism such as CKM_CMS_SIG, rather than by PKCS#11.
Profiles v2.40c01 (2014-12-23), which lists features of PKCS#11 which support is required for conformance, is mum about message recovery; draw your own conclusions about the level of support it has among tokens found in the field. I have seen an implementation which documentation plain omits the SR/VR column in the all-important matrix of Mechanism vs Function support (yet dutifully mentions C_SignRecoverInit, C_SignRecover, C_VerifyRecoverInit, C_VerifyRecover has no limitation).


Is a Qualified Digital Certificate backward compatible with existing certificate code? I'm trying to determine if our digital signature generation code will work without change using a European Qualified Digital Certificate in place of the RSA signing certificate that we normally use.

It seems like the structure of the qualified certificate is the same as any other signing certificate, but has special rules around how it is generated. If this is the case, then I suppose existing certificate handling code should continue to work. But I haven't found actual confirmation of this theory, and I don't have a QDC in hand to try it.

The code in question is a Windows-based C++ application using the Microsoft Cryptography API functions. I also asked the question with code example on stackoverflow.com.

Anybody have experience with this?

TLDR: yes.

Qualified Digital Certificate is not a specification aiming at insuring interoperability. It purposely does not even specify a precise cryptosystem (see comment). Thus in principle there is no sure answer to that question.

However Qualified Digital Certificate only requires common X.509 features, modern Microsoft Cryptography API is flexible in what it accepts, and because it is common certificate issuers typically take care of going by whatever requirement it sets. Thus my bets are on: likely yes, and I'd be surprised if a little care in parametrization at key generation and procurement of the certificate did not make it possible.

Note: Qualified Digital Certificates does not imply Qualified Digital Signature, and there is a long way from the former to the later.


anything obviously wrong with my custom password hash scheme? i sha2-256 hash the password, then i base64 encode the hash (per RFC 2045) , resulting in a 44 bytes string looking like LPJNul+wow4m6DsqxbninhsWHlwfp0JecwQzYpOLmCQ= , then i bcrypt ...crypt() that (using a securely generated salt), and i get something like $2b$10$HyPnAMyB2l1onzLjxEeRHuSioZ/X31I/XP6oHa.SPHA7KxJbR9Jq.

anything obviously wrong/bad with that scheme?

and if you're wondering why i'm doing it like this:
bcrypt crypt() (at least the implementation i'm using) has 2 annoyances, most importantly, it can't handle NULL bytes,
it thinks "\x00foo" is the same as "\x00bar". secondly, it only considers the first 72 bytes of the input password. sha2-256 don't have the NULL issue, nor the length issue, but the resulting hash can contain NULL bytes, and base64 encoded data never contains NULL bytes, and i thought the resulting 44 bytes string would be a great key for bcrypt...?

I am hesitant to say that this is "okay" because it probably is from a strictly cryptographic point of view, because if I do you will stop reading and go with your solution. Some thoughts:

In the word "password" there's the word "word". Passwords are meant to be typed in by humans, therefore they must at least be printable, therefore ASCII control characters are to be avoided.

If you need automatic accounts to log in (legitimate "bots") then they should not have passwords, instead you should provide an authentication API with an access token and a secret key, that the bot can use to make API calls to do whatever it needs to do on your application. This is the industry standard and you would do well to follow it instead of creating ad-hoc binary password schemes.

Generally it is good practice to separate human users and automated scripts/bots, even if just for auditing purposes.

So, in short:

don't give automatic accounts passwords, give them API keys that can easily be tracked and revoked; bots are not humans, they do not behave like humans, and they cannot be treated as humans; treating them the same in your authentication logic is a severe category error;
do validate passwords entered by the user, and accept general UTF-8 characters, but reject obviously invalid characters (control characters), for anything else let users sort themselves out with the "forgot password" feature if they mess up;
in the future, don't work around ridiculous implementation bugs (such as your bcrypt function not accepting null bytes) by modifying your fundamental design and core application assumptions; fix your implementation instead!!


Is this zero knowledge protocol for honest verifiers? Assume the zero knowledge protocol where the prover knows a $x$ such that: $g^x = h \pmod{p}$.

The prover chooses a random $t \in \mathbb{Z}^*_m$ and sends $y = g^t \pmod{p}$
The verifier sends random $c \in \mathbb{Z}^*_m$ and sends it
The prover calculates $s = t + c + x$ and sends it
The verifier accepts if and only if $g^s = yg^ch \pmod{p}$

Is this for honest verifiers?
Attempt:
The real transcript is $(t, g^t \pmod{p}, c, t +c+x)$, but I cannot find a simulated transcript $(t, \cdot, c, \cdot)$ that has the the same distribution as the real one. Can you give me some hints?

Can you give me some hints?

It's not a proof of knowledge, as someone without knowledge of $x$ can complete this protocol successfully with an honest verifier.
Hint: what happens if the ignorant prover sends $y = h^{-1}$?


Is it problematic to use PBKDF2-HMAC-SHA256 to derive a 512-bit XTS key? PBKDF2 should only be used to generate a larger output than the hash function it uses if the output is used in such a way that it has a flat keyspace. As far as I am aware, XTS does not have a flat keyspace, and the first half of the input is far more sensitive than the second half, which is only the tweak key. Am I correct in assuming that disk encryption utilities which use PBKDF-HMAC-SHA256 to derive a 512-bit key for a 256-bit cipher in XTS mode are in error?

If so, what can they do instead? Can they derive the cipher key and master key directly from the 256-bit output of the KDF, e.g. $K_1 = H(D \mathbin\| 0)$ and $K_2 = H(D \mathbin\| 1)$ for PBKDF2 digest $D$?

Background.
PBKDF2 has a stupid design where generating two blocks of output costs the legitimate user twice as much as generating one block of output, without necessarily putting additional cost on the adversary's task of confirming a password guess.  This is because each block of PBKDF2 output is generated by iterating the PRF on distinct initial inputs, which prevents sharing the work to generate each block: $$\operatorname{PBKDF2}(F, s, p, n, b) = \Bigl[\bigoplus_{i=1}^n {F_p}^i(s \mathbin\Vert 1)\Bigr] \mathbin\Vert \cdots \mathbin\Vert \Bigl[\bigoplus_{i=1}^n {F_p}^i(s \mathbin\Vert b)\Bigr].$$  Here ${F_p}^i$ is the $i$-fold iteration of the PRF $F$: ${F_p}^0(\sigma) = \sigma$, ${F_p}^{i+1}(\sigma) = {F_p}^i(F_p(\sigma))$.

It would have been more sensible to separate the computation into two stages like HKDF does (for a different but related purpose) with HKDF-Extract and HKDF-Expand: a costly computation to generate a master secret once, and then a collection of cheap computations to generate each block of output.  But PBKDF2 did not do this.

In general, PBKDF2's stupid design hurts security: if the legitimate user can afford to compute $n$ iterations of the PRF, and needs $b$ blocks of output, the number of iterations that the legitimate user can spend on each block independently is at most $n/b$.  If the adversary has a cheap way to confirm a password guess given any one of the blocks of output, e.g. in a password hash, then it is as if the legitimate user had a budget for only $n/b$ iterations and not $n$ iterations of the PRF.

Does this hurt in the case of XTS?
XTS is the tweakable 128-bit block cipher defined on tweak $(i, j)$ in terms of the block cipher $E$ by $$\operatorname{XTS}_{k_1,k_2}(P, i, j) = E_{k_1}(P + T_{ij}) + T_{ij}, \quad\text{where}\quad T_{ij} = E_{k_2}(i) \cdot x^j.$$  Here arithmetic is in $\operatorname{GF}(2^{128})$ represented by the irreducible polynomial $x^{128} + x^7 + x^2 + x + 1$, with your favorite choice of identification of $\{0,1\}^{128}$ with $\operatorname{GF}(2^{128})$, e.g. little-endian.  (Details of ciphertext stealing are omitted because we use sensible block sizes for everything.)

Suppose you use XTS to encrypt your laptop, and the adversary, a thief, has stolen your laptop.  They have a candidate guess for a password, for which they have spent the cost to compute either $k_1$ or $k_2$, but not the other.  How expensive is it to use this partial information to confirm a password guess, vs. spending the additional cost to compute the remaining $k_2$ or $k_1$ and confirm a password guess with full candidate key information?  Assume that $P$, $i$, and $j$ are fixed and known to the adversary.

The adversary has a candidate $k_1$ but not $k_2$.  The question is whether the function $$\phi\colon k_2 \mapsto E_{k_1}(P + E_{k_2}(i) \cdot x^j) + E_{k_2}(i) \cdot x^j$$ is a pseudorandom generator.  Define $f\colon \sigma \mapsto E_{k_1}(P + \sigma \cdot x^j) + \sigma \cdot x^j$, so that $\phi(k_2) = f(E_{k_2}(i))$.  Let $A$ be a putative distinguisher for $\phi$.  Define $A_0(\mathcal O) = A(f(\mathcal O(i)))$ as a putative PRP-distinguisher for $E$.  Note that $$A(\phi(k_2)) = A(f(E_{k_2}(i))) = A_0(E_{k_2}),$$ so that
\begin{align*}
  \operatorname{Adv}^{\operatorname{PRP}}_E(A_0)
    &= \left|\Pr[A_0(E_{k_2}) = 1] - \Pr[A_0(\pi) = 1]\right| \\
    &= \left|\Pr[A(\phi(k_2)) = 1] - \Pr[A(f(\pi(i))) = 1]\right|,
\end{align*}
where $\pi$ is a uniform random permutation.  Then, if $U$ is a uniform random 128-bit string,
\begin{align*}
  \operatorname{Adv}^{\operatorname{PRG}}_\phi(A)
    &= \left|\Pr[A(\phi(k_2)) = 1] - \Pr[A(U) = 1]\right| \\
    &\leq \left|\Pr[A(\phi(k_2)) = 1] - \Pr[A(f(\pi(i))) = 1]\right| \\
    &\quad + \left|\Pr[A(f(\pi(i))) = 1] - \Pr[A(U) = 1]\right| \\
    &= \operatorname{Adv}^{\operatorname{PRF}}_E(A_0)
       + \operatorname{Adv}^{\operatorname{PRG}}_f(A).
\end{align*}
Thus, it effectively reduces to the question of whether $f$ is a PRG.  This is close to the question of whether $\sigma \mapsto \pi(\sigma) + \sigma$ is a PRG, if we model $E_{k_1}$ by a uniform random permutation $\pi$, which is essentially the Matyas–Meyer–Oseas construction as studied by Black, Rogaway, and Shrimpton in 2002.  By a wing-waving argument, I assert that this seems like a reasonable model for most block ciphers (note related-key attacks are not relevant), and I conjecture the answer is no, the adversary can't effectively confirm a guess knowing only $k_1$ without computing $k_2$ unless they've broken $E$.
The adversary has a candidate $k_2$, but not $k_1$.  The question is whether $$\psi\colon k_1 \mapsto E_{k_1}(P + E_{k_2}(i) \cdot x^j) + E_{k_2}(i) \cdot x^j$$ is a pseudorandom generator.  This straightforwardly reduces to the PRP-security of $E$.  Given a PRG-distinguisher $A$, define the PRP-distinguisher
\begin{align*}
  A_1(\mathcal O)
    &= A(\mathcal O(P + E_{k_2}(i) \cdot x^j) + E_{k_2}(i) \cdot x^j) \\
    &= A(\alpha(\mathcal O(\alpha(P))))
\end{align*}
where $\alpha\colon \sigma \mapsto \sigma + E_{k_2}(i)\cdot x^j$ is a permutation, so $A_1(E_{k_1}) = A(\psi(k_1))$, and
\begin{align*}
  \operatorname{Adv}^{\operatorname{PRP}}_E(A_1)
    &= \left|\Pr[A_1(E_{k_1}) = 1] - \Pr[A_1(\pi) = 1]\right| \\
    &= \left|\Pr[A(\psi(k_1)) = 1] - \Pr[A(\alpha(\pi(\alpha(P)))) = 1]\right|,
\end{align*}
where $\pi$ is a uniform random permutation.  Clearly since $\alpha$ is a permutation, $\alpha(\pi(\alpha(P)))$ has uniform distribution, so
\begin{align*}
  \operatorname{Adv}^{\operatorname{PRG}}_\psi(A)
    &= \left|\Pr[A(\psi(k_1)) = 1] - \Pr[A(U) = 1]\right| \\
    &\leq \left|\Pr[A(\psi(k_1)) = 1] - \Pr[A(\alpha(\pi(\alpha(P)))) = 1]\right| \\
    &\quad + \left|\Pr[A(\alpha(\pi(\alpha(P)))) = 1] - \Pr[A(U) = 1]\right| \\
    &= \left|\Pr[A(\psi(k_1)) = 1] - \Pr[A(\alpha(\pi(\alpha(P)))) = 1]\right| \\
    &= \operatorname{Adv}^{\operatorname{PRP}}_E(A_1).
\end{align*}
The answer is no, the adversary cannot effectively confirm a guess knowing only $k_2$ and not $k_1$ unless they've broken $E$.

Why couldn't we just make $k_2$ public like an IV?
If we did that, the following chosen-plaintext distinguisher would trivially break it: Submit $(P, i, j)$ and $(P + \delta, i, j')$ for the challenge, where $j \ne j'$ and $\delta = E_{k_2}(i) \cdot x^{j'} - E_{k_2}(i) \cdot x^j$, and test whether their ciphertexts differ by $\delta$.

While this justifies keeping $k_2$ secret in the cryptosystem in general, it's not clear that this power of the adversary is relevant to password-guessing for stolen laptop disk encryption: for every password they guess, the thief who stole your laptop would have to submit to you a chosen plaintext to encrypt in order for them to confirm that password.  It's hard to imagine how this could happen unless you're willing to help me recover a large sum of money from a Nigerian prince I know.

But laptop disk encryption is not the only application of disk encryption.  You might use iSCSI over the network, and the adversary might have compromised the iSCSI storage server without your knowledge, and may be able to control blocks of data written by the iSCSI client.  In that case, the adversary may be able to submit a chosen plaintext derived from the value of $k_2$ for every password they guess, and use the client as an oracle to confirm the password at lower cost than evaluating PBKDF2 again to compute $k_1$.

Conclusion.
In the case of laptop disk encryption with AES-XTS, the stupid design of PBKDF2 does not appear to hurt the way that it might generically.  But that took a lot more work to prove (and there's some gaps: e.g., does it make a difference if the adversary has many blocks of output to confirm a guess?—rewrite $\phi$ and $\psi$ as PRFs of $(P, i, j)$).  And it's possible I posed the wrong question, or made a mistake answering the questions I posed: this is, after all, a pseudonymous internet fowl talking feathery nonsense at you, not a bespectacled cryptographer writing in a respectable peer-reviewed journal.  And there are imaginable applications of disk encryption for which this use of PBKDF2 does hurt security.  It would have been safer to derive a master key with PBKDF2 and then derive subkeys from it with HKDF.

P.S.  You should use scrypt or argon2, not PBKDF2.  They make a much bigger difference than this quibbling!  They also don't have this stupid design.  That, or just generate your passwords uniformly at random from ${\geq}2^{128}$ possibilities.