How to verify the integrity of RSA encrypted messages? I need to encrypt messages using PublicKeyCrypto and send it to the server, where the message should be decrypted. I'm aware of the Padding Oracle Attack and want to apply a server side integrity check of the incoming cipher messages. In AES there is the so called CCM mode, which performs the integrity checks implicitely. Is there something else for RSA decryption?

I'm using the 'javax.crypto.Cipher' library.

With pure asymmetric encryption there is no way to ensure integrity and authenticity, since anyone who knows your public key can encrypt any message for you. For that you would need either a symmetric key to use for a MAC (in which case you could use it/derivatives for symmetric encryption too) or a signature from the sender. And in the latter case the advice is to sign-then-encrypt, which doesn't help with any padding concerns.

There's no simple way to avoid leaking information through a padding attack, like with encrypt-then-MAC for symmetric encryption, if the padding algorithm is vulnerable to one. Instead, your implementation should not leak information about whether the padding is correct. OAEP is more resistant than older padding algorithms, but even it must be correctly implemented.

However, since you are using a high level cryptographic library, the low level details are not something you should have to worry about. The writers of that library should have taken care of those. Just choose the correct algorithm, i.e. OAEP. (I don't know details about any Java libraries' security record, though.)


Does security under ROM imply exactly what? I'm not sure I understand really the implications of proofs of security in the random oracle model. Does a proof of security in ROM translate to a reduction of security of the crypto-system to the security of the hash function in the standard model? If not, then this would imply that the meaning of the ROM proof in the SM depends on the particular algorithm and it would seem almost impossible to say anything general about implications of proofs like this. However, people seem to put a lot of effort in producing proofs of security in ROM so perhaps these proofs do have some value (I just don't exactly understand what, and it would seem extremely hard to point out any general implications). Textbooks tend to be typically quite vague at explaining this.

A very much related question: Does anyone have any insight to whether there is some general reason why proofs of CCA security are expected to be hard (if they even exist) in SM?

By the way, are random oracles really impossible to have in reality? True randomness could be produced by quantum phenomena, so why not use that?

If you can show a reduction of a security property of your protocol to the security of a hash function is the standard model, you do not need the random oracle assumption. So a proof in the ROM does not have any general (positive) meaning in the SM; hence why it is controversial. About the only general thing you can say is that some (arguably highly contrived) protocols that are secure in the ROM are insecure in the SM with a concrete hash function.

The value of a ROM proof is that it still narrows the range of attacks possible on a protocol. Unlike an unproven protocol where it could break in any number of ways, a ROM protocol will only break if the hash function does not live up our theoretic expectations of it. Further, no "natural" protocol that is secure in the ROM has ever been broken.

There is a good discussion in Katz-Lindell. Basically their conclusions is, a ROM protocol is better than no proof. A SM protocol should be preferred up to a reasonable decrease in efficiency.

A RO needs to return the same output value if queried on the same input. That is essentially why quantum randomness does not work.


Why is the internal chacha20 permutation vulnerable to attacks if used in a sponge construction? The user Forest in here claims that the internal chacha20 permutation is "vulnerable to attacks if it were used in a sponge construction". My question is as follows:

What are these attacks?
Would these attacks still be an issue if we assume that we are using a modified version of the chacha20 that does not have a trivial to find fixed point?

I would have phrased it as not having evidence supporting it as safe to use.

The ChaCha permutation was not designed to be used in a sponge construction. It could be safe, but we don't have evidence of any weight similar to the weight of evidence we have suggesting that the whole ChaCha20 stream cipher is safe.

I'm not aware of any attack on the ChaCha permutation if used as a sponge, unless capacity bits are initialized to zero. ChaCha's trivial fixed point is from zero to zero. If you can force the sponge's state to that value, then you can insert one or more blocks of all zero bits between two message blocks without changing the sponge's state. (Making collision attacks trivial.)

It is (most likely) non-trivial to get the state (capacity) bits to the zero if they aren't already that value. If the capacity bits are non-zero and the number of capacity bits is sufficiently large and the ChaCha permutation would be indifferentiable from a random permutation if not for the one known fixed point, then there might not be a way to exploit the fixed point in practice.

But, again, that third point isn't something that we can assume is true with the same confidence that we have for assuming that the stream cipher algorithm, ChaCha20, is secure. There is a lack of evidence because not enough effort has been put into studying the permutation in isolation.


Basic questions on how asymmetric keys "interact" Have I understood this correctly?

To use a key and lock analogy. With an asymmetric pair of keys (when used to encode) can either key be used to encode the message (close the lock) and only the "pair" be used to decode (open the lock)?
Taking the key analogy further, is it a useful comparison to say that the first key of the pair changes the lock after it is used so that only the "not yet used" key of the asymmetric pair can open the lock?
The description of keys as "public" and "private" is only a convention that relates to their use and not the order in which they are used i.e. can use 3.1 public then private (encoding for one intended recipient) or 3.2 private then public (digital signatures)?

Edit: Wording of point 2 altered following comment by Maarten Bodewes.

To use a key and lock analogy. With an asymmetric pair of keys (when used to encode) can either key be used to encode the message (close the lock) and only the "pair" be used to decode (open the lock)?

No, not in practice. Although some systems work kind-off like that, for instance raw (unpadded) RSA, others do not. Besides that, one key is supposed to be public so anybody could use that key to open the lock. Locks are used to emulate encryption, and encryption is used for confidentiality. If you use the private key to lock then anybody could open the lock. That's not a good way to achieve confidentiality.

The confusion mainly seems to arise from RSA where signature schemes were seen as encrypting a (padded) hash value. Nowadays the specification of secure RSA goes out of the way to make sure this confusion doesn't arise. More information here.

  Taking the key analogy further, is it a useful comparison to say that the first key of the pair changes the lock after it is used so that only the asymmetric key of the pair can open the lock?

Both keys in the key pair are asymmetric to each other. So there is not one asymmetric key, but two (or more). The analogy is already broken, it doesn't make sense to take it further.

  The description of keys as "public" and "private" is only a convention that relates to their use and not the order in which they are used i.e. can use 3.1 public then private (encoding for one intended recipient) or 3.2 private then public (digital signatures)?

Yes, that is right.


Complexity class of an idealised version of Bitcoin's proof-of-work (hashcash)? To formulate this question precisely, I will define an idealized hypothetical "perfect" hash function $H(n)$ which has nice scalability properties, and will formulate a problem PERFECT HASHCASH in terms of that, understanding that practical considerations may end up yielding only an approximation of this ideal.

To keep it simple, we will say that our hash function $H(n)$ takes as input a single natural number $n$. Then we say that $H(n)$ is a perfect hash function iff:

$H:\mathbb N \to \{0,1\}^\infty$; That is, $H$ maps each natural number to an infinite binary sequence, and which the time complexity to compute any initial segment $s$ is polynomial in the size of $n$ and $s$, (making it a sponge function).
For any initial segment of length $d$, the set of all natural numbers $n$ such that $H(n)$ shares that initial segment has natural density $2^{-d}$.

The first thing formalizes the scalability of our function, and the second thing formalizes the idea that we want all hashes to appear roughly "equally often" as an output. Other than that, our perfect hash function is a black box, and we don't care much about exactly how it works, so long as it meets the above properties, as well as the usual desiderata applying to hash functions (easy to compute, hard to invert, hard to find collisions, etc).

Predicated on the assumption that a perfect hash function exists, we can now define the problem PERFECT HASHCASH as follows: PERFECT HASHCASH takes as input a perfect hash function $H$, a natural number $n$, and the zero vector $0^d$ of length $d$, which can be thought of as a unary representation of $d$. A solution to PERFECT HASHCASH consists of an $n$ and $d$ such that $H(n)$ starts with $0^d$.

Given those inputs, it is clear that PERFECT HASHCASH is in the complexity class TFNP, since this is a function problem and a solution is guaranteed to exist.

Can we also identify PERFECT HASHCASH as a member of any complexity class finer than TFNP?

Could it perhaps be in PPP? PPA? PPAD? Something else?

For background, see Complexity class on Wikipedia.

Bitcoin's proof-of-work problem is solved in constant time, since there is no asymptotics. Complexity classes are irrelevant here.


HMAC vs ECDSA for JWT I will be implementing JSON web tokens into my website and have a question about implementing them. I have a choice of using two algorithms, HMAC-SHA256 and ECDSA-SHA256. I have used HMAC-SHA256 in the past for jwt, but now I noticed ECDSA is being added to a lot of jwt libraries. As someone who does not have a strong background in security, I was wondering what the advantages/disadvantages are between these two? Trying to Google HMAC vs ECDSA did not bring up any great results. My areas of concern include:

Speed (Since my server will need to sign many tokens, how do they perform?)
Security (How do they fair against brute force attacks and rainbow tables? This will probably relate to my first concern.)
Stability (Are these algorithms accepted as stable, proven, and reliable?)

The distinction is that ECDSA solves a problem that HMAC does not. If you need that problem solved, then you need to do ECDSA rather than HMAC; if you do not, then HMAC works just as well (and is a lot cheaper).

With HMAC, here is what we have: we have an authenticator that has a secret key.  It takes a message, and gives that (and the secret key) to the HMAC algorithm, and that generates a tag.  We send that tag, along with the message, to the verifier.

The verifier also has the secret key. It takes the received message, and gives that (and the secret key) to the HMAC algorithm, and that generates the tag.  It then checks if the computed tag was precisely the same as what it received; if it is, then it knows that the message is precisely as it was when it was originally sent.

With ECDSA, here is what we have.  we have an authenticator that has a private key.  It takes a message, and gives that (and the secret key) to the ECDSA signing algorithm, and that generates a tag.  We send that tag, along with the message, to the verifier.

The verifier also has the public key (which is not the authenticator's private key). It takes the received message and tag, and gives that (and the public key) to the ECDSA verification algorithm, and it checks whether the tag corresponds to the message.  If it does, then it knows that the message is precisely as it was when it was originally sent.

So, what's different?  With HMAC, both sides share the same key; the verifier could (if it wanted to) generate its own tags to messages of its choice, and those tags would validate just as well.  With ECDSA, this doesn't happen; the key that the verifier has (the public key) allows it to check tags, but it does not allow it to generate tags on its own.

So, is this distinction important in your scenario?  I don't know enough about what you're doing to say.  The question you need to answer is: can you trust the verifier not to generate its own tokens?  Can you trust someone who has access to the verifier's keys not to do so?  If that is not something you are worried about (possibly because the verifier is the only one who cares about tags generated by a specific set of keys), then HMAC works just fine (and, as I mentioned earlier, is a lot cheaper).  If you do care (for example, you distribute the verifier code to lots of people, and you have one set of keys), then it doesn't matter how cheap HMAC is - it doesn't solve your problem - you need to go with something like ECDSA


Creating a share of a random shared secret I am interested to know if there is a solution to the following scenario:
Assuming we have $n$ party members, is there a scheme that at the end of it, every party member $i$, holds a shamir's threshold share, $S_i$, of the secret $a$ where $k$ of $n$ can reconstruct $a$ using the shamir's threshold reconstruction and none of them individually knows the secret itself.

You probably want a stronger requirement, that no individual knows more than his share. Off the top of my head I don't know how to do that.

But the question you asked, only requiring no one to know the full secret is easier.
K participants each pick a random number to be their share, using secure multi-party-computation they compute n-k shares which they distribute.
If n>=2k you compute in groups changing the set of people computing.

This can probably be modified slightly to meet the stronger requirement without using secure multi party computation as a black box.


Does collision resistance stay when extending a hash function to a set domain? Given a Cryptographic hash function $h$ for element $x$, let's extend it to sets via $H(S)=\prod_{x\in{S}}{h(x)}$. I am asking if the new hash $H$ (in domain of set) is still collision resistant?

To be more specific, is it the same difficult to compute $S$ for given $H(S)$, comparing to that of computing $x$ from given $h(x)$?

Also how hard it is to find another $S'$ so that $H(S')=H(S)$? Is it at the same level of difficulty comparing to finding another $x'$ s.t. $h(x)=h(x')$.

If the hash outputs 160-bit integers, and the product operation is integer multiplication, then this is probably not secure, for reasons fgrieu outlines.  For instance, about $1/2^{19}$ of all 160-bit integers are $B$-smooth, if we take $B$ to be the $2^{20}$th prime.  Consequently, after hashing $2^{45}$ different candidate messages, we expect to find about $2^{26}$ smooth hash digests, which I suspect is enough to find a collision; and this computation seems likely to be feasible today.

On the other hand, if you work in a multiplicative group where the discrete log problem is hard, such as $\mathbb{Z}_p^*$, and if the hash function outputs random elements of this multiplicative group, then your scheme is secure.  For instance, if you pick a 2048-bit prime $p$, arrange for your hash function to output numbers that are uniformly distributed between $1$ and $p-1$, and interpret the product as "multiplication modulo $p$", then your scheme should be secure.  However, it might be a bit slow.  See the following papers for technical details and security analysis:

Incremental Multiset Hash Functions and Their Application to Memory Integrity Checking.  Dwaine Clarke, Srinivas Devadas, Marten van Dijk, Blaise Gassend, G. Edward Suh.  Asiacrypt 2003.  See the scheme they call MSet-Mu-Hash.
A new paradigm for collision-free hashing: Incrementality at reduced cost. Mihir Bellare, Daniele Micciancio.  Eurocrypt 1997.  See the scheme they call MuHash.


Is there an asymmetric scheme where keys form a graph and a message can only be decrypted across a certain degree of separation? Consider a network of trust, where each user u specifies some other set of users whom u "trusts". This forms a graph with users as nodes and declarations of trust as directed edges.

Each user may push encrypted data out to the network along with a maximum "degree of decryption", e.g. if the degree is 2, only direct friends (degree 1) and friends of friends (degree 2) should be able to decrypt the message.

Ideally this restriction could be implemented in the encryption scheme itself. The scheme would have the following properties:

Ability to encrypt a message M = c || d

where c is the message content and d is the max degree

The ability to generate a new key from another private key which can still decipher M (this corresponds to an edge on the graph of trust)
A generated key can only decipher M if it is less than d levels of derivation away from the original key used to create M
No key can be easily derived from a generated key

To spell it out more plainly, when user A trusts user B, A derives a new key from her private key and shares it with B, so B can now decrypt her messages of d >= 1. B does the same and generates a new key from A's shared key, which B shares with C. Now C can read messages from A of degree d >= 2. And so on. (Actually, when B decides he trusts C, he would pass on to C generated keys for every person B trusts.)

I'm wondering if anything like this exists, or if anyone can point me in that direction, or can provide intuitions as to whether this is even feasible. I am new to cryptography and can't even tell whether this is likely to be already done, doable, or impossible.

This looks like a new research to be done. I believe this is doable starting from graph characteristic polynomial as introduced at iacr 2008/363 and CECC 2009 (shameless). "Trusted" relationship would mean knowing secrets associated with neighbor nodes. Having secrets of trusted network of neighbors, sender would produce characteristic polynomial such that any trusted node can divide, that is, produce zero remainder polynomial. There might be a variant of ElGamal encryption designed from probabilistic test (Schwartz-Zippel) for zero remainder condition, which would likely complete this design. Considering (verifying) characteristic polynomials over a ring modulo random linear polynomial (no such ring at 363 preprint yet) might be a practical solution. Welcome.


what are the security benefits of LUKS? Aremed with only basic crypto knowledge, I'm trying to understand the security benefits of LUKS over plain-mode dm-crypt. Hopefully this is a good place to ask.

Given the LUKS header contains information describing how the payload is encrypted, would it not be more secure to use plain dm-crypt instead?

I'm thinking that a plain device will just look like random data and won't have a label attached that tells all that it's encrypted data and what the cipher and other details are. Plain mode allows plausible deniability where as LUKS doesn't.

The LUKS header not only contains the master key (albeit it stretched and encrypted) but it also contains up to eight attack vectors that can be used to get the master key. Yet, underlying all this, the same dm-crypt engine is used to encrypt both the plain and luks payloads.

Therefore, attacking a plain or luks payload could be done directly (however impractical that may be), but LUKS throws in some additional ways to crack the data whereas plain-mode gives nothing away.

I guess it may boil down to the fact that a user of plain mode will need to have the actual key and may not store it securely or use a pass-phrase that is only hashed simplistically, whereas a user of LUKS mode will never have the actual key but will use a pass-phrase that is put through a salted iterative key derivation function.

So, is LUKS less secure than plain dm-crypt ?

I think it is often considered a principle in evaluating the quality of a cryptographic setup to start with the assumption that the opponent is aware of the algorithm and the only variable unknown is the key. Given this, there are not many cryptographically motivated security benefits/differences, given you use the same cipher (+ block chaining mode of operation).
Arguably for the human eye, the LUKS header gives away information to the attacker and it feels wrong to do so. I expect we are misled in thinking that because of the perceived amount of information about the specifics of the encryption it is a human emotion to feel bad since one whole point of encryption is to avoid giving away information in the first place.
Yet by using dm-crypt directly I fear most of what is achieved is some additional security through obscurity, something many people are rather skeptical about. Maybe this is because its effect can hardly be estimated. To some extent for instance you might be coerced into using a safe encryption scheme either way and since such a trusted cipher (block-chaining-mode+) does not exist in that great abundance, chances are high that you will use AES 256 CBC or alike. If you were to use some other cipher you maybe might gain potentially some better protection against cryptanalysis that attempts to abuse AES specific weak points. On the other side, not using AES for this inestimable safety might lead you to a cipher XXX that is not as tested and hardened against standard cryptoanalytic attacks.
After all in bullet-point style (things to consider):

LUKS header will defeat much plausible deniability, while dm-crypt pseudo-random hard drive "better" (this is of course not a cryptographic attribute, and would more be focused on http://security.stackexchange.com )
LUKS will use some random data source (I think it is /dev/random even) to create the master key for encrypting the hard drive/partition, which might be considered more entropic than a key derived from a passphrase (if that was the way you provide dm-crypt with a key).
Then again, LUKS will generate key slots that use key derivation functions to accept keys for unlocking the master key.

Consider also that security is a context-dependent concept. For instance, it can be said a LUKS setup is more secure as it protects you from losing the encryption master key since after all it is stored (again encrypted) in the LUKS header. You still can lose access to your data by way of forgetting the passphrase.
Also, LUKS gives some security to lose the information about which cipher was used, as it is directly stored in the header, while that would be something that you need to secure your dm-setup against (you need to remember what you did).


Is This method of generating Initialisation Vector for Cipher Block Chaining secure? I have worries about security defined in BACnet protocol (ASHRAE/ANSI Standard 135, ISO 16484-5). Full text of security is here: http://bacnet.org/Addenda/Add-135-2008g.pdf and here is my summary:

In my message I have header containing unique message ID and timestamp (along with some other data) and payload. I sign whole message using HMAC with first key and MD5 or SHA-256 as hash algorythm. Then i use first 16 bytes of signature as IV for encrypting payload with CBC AES with second key. I attach signature to the message.

Is My IV unpredictable enough? Is signing a plain payload making my security vulnerable?

I have not looked in detail at the standard you linked to, but in general, applying a PRF (such as HMAC) to the plaintext (plus associated data and/or a nonce, if any) to derive a message authentication tag, and then using the same authentication tag as the IV to a conventional IND\$-secure length-preserving IV-based encryption scheme, is an instance of the "SIV construction" (Rogaway & Shrimpton 2007, pp. 6–9).  Thus, if the assumptions of Rogaway & Shrimpton's proof are met, this construction yields a secure deterministic authenticated encryption scheme (if used without a nonce) or a misuse-resistant authenticated encryption scheme (if used with a nonce) in the sense defined in the paper.

However, a notable issue in applying the SIV proof to the BACnet scheme (as you describe it) is that basic CBC mode (without ciphertext stealing) is not length-preserving.  In particular, the scheme you describe appears potentially vulnerable to the CBC padding oracle attack if an attacker can distinguish a CBC padding error from an HMAC mismatch.  Even if the recipient is specified to return the exact same error in both cases, it might still be possible to distinguish the two cases by timing how long it takes the recipient to reject the message.

A simple solution to this issue would be to replace CBC with a length-preserving encryption mode, such as CTR, CFB or even CBC with ciphertext stealing.

Ps. I thought this question seems vaguely familiar, and while searching for references I stumbled across an earlier very similar question about HMAC + CBC in an SIV-like construction that I'd previously answered:

Is this method of deterministically using CBC secure?

Also, for general information about the security of the MAC-and-encrypt structure of SIV mode, see the following question:

Why is synthetic IV (SIV) mode considered deterministic authenticated encryption (DAE)?

as well as the paper "Reconsidering Generic Composition" by Namprempre, Rogaway and Shrimpton (Cryptology ePrint Archive, Report 2014/206, 2014) which I cite in my answer there.


Security of this scheme I am developing a software and I am not sure if it is completely secure.

I have 22 Mb of data to encrypt used multiple times,
random IV (generated using RAND_bytes from OpenSSL lib)
and password which is $key = SHA3_{256}(PBKDF2(salt, password, 256000, SHA2-256))$.

SHA3_256 from Qt QCryptographicHash, PBKDF2 and SHA_256 from OpenSSL, salt is also generated from RAND_BYTE and 256 bits long.

Now I would like to know your opinion if this scheme is secure:

XOR key and IV together:

$$
encryptionKey = IV \oplus key\\
$$

encrypting IV:

$$
firstBlock=E_{AES-EBC-256}(key, IV)
$$

encrypting data:

$$
secondBlock = E_{AES-GCM-256}(encryptionKey, IV, data)
$$

and then:

$$
output << firstBlock\\
output << secondBlock
$$

I am not sure especially about this part $E_{AES-GCM-256}(IV \oplus key, IV, data)$.

I would really appreciate your opinion about it.

It's rather hard to answer the full question, but I'll try and answer as best as possible.

You try to derive a data encryption key using the IV, because you think the IV may be overused.

NIST SP 800-38D section 8.3 states (for a probability of non-repeation of $2^{-32}$ ):

  The total number of invocations of the authenticated encryption function shall not exceed
  $2^{32}$, including all IV lengths and all instances of the authenticated encryption function with
  the given key.

Great, so unless you invoke GCM more than 4 billion times (short-scale), then you should be OK, and you may not need any special constructs.

Let's assume you don't want to limit the amount of GCM calls. In that case you to derive a key for each encryption. You can use a Key Based Key Derivation Function or KBKDF. Probably the best one you can use is HKDF. HKDF accepts a salt as well, and is able to generate as many bits from the input as needed. So you could use the following construct:

$salt = random()$
$seed = PBKDF2(salt, password, 256000, SHA2-256)$
$key = HKDF(seed, \text{"key"})$
$iv = HKDF(seed, \text{"iv"})$
$(ct, tag) = E_{AES-GCM-256}(key, iv, data)$
$output = encode(salt, (ct, tag))$

now say you don't want to perform those 256000 iterations for each file, and you want to encrypt/decrypt multiple files at a time, then you can do the following:

$salt = random()$
$seed = PBKDF2(salt, password, 256000, SHA2-256)$
$salt_2 = random()$
$key = HKDF(seed, salt_2, \text{"key"})$
$iv = HKDF(seed, salt_2, \text{"iv"})$
$(ct, tag) = E_{AES-GCM-256}(key, iv, data)$
$output = encode(salt, salt_2, (ct, tag))$

as HKDF can also use a salt. For each file, repeat steps 3 to 6.

A trick is to use just HKDF-expand and generate 512 bits for key and IV. Other, more simple KDF's such as KDF1 or KDF2 may also be used if HKDF is not available.

As for your scheme, I see some drawbacks.

the additional call to SHA-3 is spurious;
the IV of GCM is best set to 96 bits (12 bytes), but the XOR and encryption of the IV seems to suggest an IV of 128 bits;
the XOR'ing of key and IV is not a secure key derivation function;
the key length is now limited to the size of the IV or introduce additional complexities;
reusing the derived key for different, related algorithms is not recommended.

Here the combination of 3 and 5 is the biggest issue; you'd have to prove that the insecure key derivation doesn't hamper the security of the GCM algorithm. This is not something you should want to do.

As always, it may be advisable to use an existing protocol and library though; there are plenty secure ones available.


In a secret image sharing scheme, what are the advantages of Galois field $\mathrm{GF}(p^m)$ over finite field $ F_p$? Shamir's Secret Sharing Scheme uses arithmetic in a finite field of prime order.
In a secret image sharing scheme, what are the advantages of Galois field $\mathrm{GF}(p^m)$ over finite field $ F_p$?

In a secret image sharing scheme, what are the advantages of Galois field $\mathrm{GF}(p^m)$ over finite field $ F_p$?

Well, Shamir Secret Sharing works over any finite field $GF(p^m)$, where $p$ is any prime, and $m$ is any integer $m \ge 1$ (N.B. the finite field $GF(p)$ (with $m=1$) is another name for $F_p$).  Any selection of $p$ and $m$ is perfectly secure (assuming we select the polynomial randomly; this is a practical concern, but doesn't really depend on $p$ and $m$), with the only provisos is that the number of shares we can distribute is limited to $p^m-1$, and the value of the shared secret $s$ is in the range $[0, p^m)$.

So, any $p^m$ that is sufficiently large will work and meets the security goals; we then turn to practical considerations.

One strong practical consideration is the size of the shares.  Each share is a value in the range $[0, p^m)$, for $p=2$, this can be conveniently expressed as $m$ bits; for $p>2$, this is a bit larger.  This is not a huge difference; however it is generally viewed the only other practical difference, which is the familiarity we might have with math in $F_p$.

Here is one slightly contrived example to high-light the difference: suppose that we want to share a secret, and we have decided to split up the secret into bytes, and share each byte separately (if each polynomial is selected independently, this is fine).  And, we do not have any need to generate more than 255 shares.  In this scenario, we have two obvious options; we could use $GF(257)$; that makes the math fairly easy; however because each share is a value between 0 and 256, it doesn't fit into a byte; hence the obvious way to encode shares would be twice as long as the original secret.  The other option would be to use $GF(256)$; the math is less obvious (however, with log and antilog tables, it isn't that bad), and each share turns out to be exactly as long as the original secret.


repeating-key xor and hamming distance I read that to break repeating-key xor you can do the following: try a keysize $n$ and compute the hamming distance between the first $n$ bits of the encrypted string and the bits $n+1$ to $2n$ of the encrypted string and normalize by keysize.

The true keysize probably minimizes this. Why?

It also suggests to average a couple of the near minimal values computed in this way. But why should keysizes that are not correct help compute the true keysize?

Yes, you are remembering correctly.  Yes, this is a reasonable method to find the key length.

The reason why this works is because, typically, the plaintext is not uniformly random.  For instance, rather than a random bit-string, the plaintext might be some English text, encoded in ASCII.  If $X,Y$ represent two random English letters, encoded in ASCII, then the expected value of the Hamming distance $\text{wt}(X \oplus Y)$ is maybe 2-3 bits.  In contrast, if $U,V$ are two random 8-bit bytes, then the expected value of the Hamming distance $\text{wt}(U \oplus V)$ is 4 bits, significantly larger.  If you look at sequences of multiple characters, rather than a single letter at a time, the difference becomes even larger.

How does this apply to your situation?

Well, if you have correctly guessed the key length, then your ciphertext consists of $X\oplus K$ and $Y\oplus K$ (as Dilip Sarwate explains), where $X,Y$ come from the plaintext distribution.  Now notice that the Hamming distance between these two is the same as the Hamming distance between $X$ and $Y$, namely, it is $\text{wt}(X \oplus Y)$.  As we explained before, you can expect this might be maybe 2-3 bits times the length of $X$ measured in bytes.
In contrast, if you guessed the key length incorrectly, then you're looking at ciphertexts of the form $X \oplus K$ and $Y \oplus K'$.  The Hamming distance between the two basically boils down to the Hamming distance between $U$ and $V$, where $U$ and $V$ are uniformly randomly distributed (since $K,K'$ are uniformly randomly distributed), and thus is $\text{wt}(U \oplus V)$.  As explained before, you can expect this should be approximately 4 bits times the length of $X$ measured in bytes.

So, as you can see, the Hamming distance is significantly less when you've guessed the key length correctly.

For a vaguely similar method, read about the Index of coincidence; you can expect it to be more effective in some cases, and less effective in others.


Determining message given cipher-text and public key Consider the following scenario:

  Suppose A and B have set up their RSA public keys, namely $(e_a, n)$
  and $(e_b, n)$, where the n-value is the same. Also, it happens that
  the $\gcd (e_a, e_b) = 1$. Suppose C wants to send both A and B a
  message $M$ that is coprime with $n$. Thus, C encrypts $M$ using A and
  B's public keys, producing the cipher text, $C_a$ and $C_b$.

I was told by my instructor, that suppose if there is someone who obtains the values of both $C_a$ and $C_b$, that particular person can determine the message $M$ using the public keys of $A$ and $B$, without knowing their private keys. Why is it necessarily true? Any help would be highly appreciated!

This is called the common modulus attack.

Bezout's Identity says that there exists $x$ and $y$ such that $ax + by = gcd(a, b)$.

In our case we have $gcd(e_a,e_b) = 1$, so we can find $x$ and $y$ such that $e_{a}x + e_{b}y = 1$ (you can use the extended euclidean algorithm for this).

After solving for $x$ and $y$, you compute:

$C^xC^y\mod N$ to get $M$.

This works because $C^xC^y= M^{e_{a}x}M^{{e_b}y} = M^{e_{a}x + e_{b}y} = M$


Could a C25519/ED25519 cryptographic module be FIPS certified? NIST algorithms include ECDH and ECDSA. NIST also specifies curves. Is the use of NIST curves required for FIPS certification or could other curves theoretically be certified if someone were willing to do the work?

Could a C25519/ED25519 cryptographic module be FIPS certified?

Likely yes in the near future—although ‘near’ is measured relative to the pace of a US federal government bureaucracy.

On 2019-10-31, NIST submitted a request for comments to the Federal Register on drafts for FIPS 186-5 and NIST SP 800-186 that include the Montgomery and Edwards curve shapes; the particular curves Curve25519, Curve448, edwards25519, and edwards448; and the EdDSA signature scheme instantiated with them, as defined in RFC 7748 and RFC 8032.  Comments are due by 2020-01-20.

(The updates do not cover the X25519/X448 DH functions, but NIST's late 2017 announcement of the upcoming changes also mentioned future updates to NIST SP 800-56A, which covers key agreement.)


AES 5-round Square attack, how to choose plaintexts? I know that we need to generate a delta-set (with 256 plaintexts).

During the attack, we guess 4 bytes of round 5 key and 1 bytes of round 4 key, which allows us the byte at one position of the state at the end of round 3. If that position is balanced, then the 4-byte prediction is valid, but there are a lot of false-positives.

My problem is that there are too many false positives. No matter what delta-set I generate, all remaining 4-byte combination result in a false-positives.

How can I generate the input plaintexts to eliminate these false positives? I can't find a single implementaion of AES Square attack online, so if anyone can show me, I'd be very grateful.

Thank you.

Edit: nevermind. On average 5 delta-sets or less is needed. I just had a data-type bug (char -> unsigned int) that make the program fail to eliminate delta-set

In statistical attacks (such as square), if we can reduce the key space, it will be considered successful. Here, as you pointed, there are false-positives and they should be considered as correct key candidates. But the point is that the distinguisher has removed some incorrect keys and has reduced the key search space. After finding candidates for the correct key, you should do exhaustive search among them or try other attacks to even reduce the key space further!
Here, choosing the plaintexts does not have that much effect on the false positive, since different keys will change the chosen set differently.


CBC-MAC: is it secure to authenticate a fixed length ciphertext? Suppose I have a fixed-length arbitrary ciphertext.

To authenticate such ciphertext:

I generate a random AES Key $K_{auth}$.
Then I compute the CBC-MAC Tag of the ciphertext with $K_{auth}$.
Finally, I store the ciphertext and the associated Tag in my database.

For decryption process:

I get the ciphertext and the associated tag from my database.
Then I check the ciphertext length and if it match as expected, compute the tag with $K_{auth}$.
Finally, if tags matches, I process the cipertext.

In my case the database should be considered untrusted, as an adversary may edit both ciphertext and tag. However, as keys remain private, is such Encrypt-then-Mac approach secure (even if the tag is not itself encrypted) ?

Yes, if your encryption algorithm is reasonable secure.

Given fixed length messages (in your case the ciphertext), CBC-MAC is a secure MAC scheme, meaning that an attacker, without knowing the key, cannot produce a valid message-tag pair with non-negligible probability. Furthermore, according to this paper, Encrypt-then-MAC is the best procedure, while MAC-then-Encrypt and MAC-and-Encrypt are vulnerable to chosen-ciphertext attacks, the latter may even weaken the security of the encryption scheme itself. Thus the security of your system depends solely on the encryption algorithm you use. The ciphertexts it produces should be indistinguishable under chosen-plaintext attacks (IND-CPA). In other words, an attacker who sends two messages to an oracle and gets one ciphertext in return won't know which one of the two messages were encrypted.

AES in CBC mode with an initialization vector chosen randomly each time you encrypt a message is assumed to have this property.


Chosen Ciphertext Attack with a theoretical decryption machine Say we have an encryption algorithm that encrypts data blocks of 128 bits size, and makes them cipher blocks $C = E(P)$ without chaining.

Also assume there is a linearity rule for XOR: For every pair of plaintext blocks $P_1$, $P_2$ there is: $E(P_1 \oplus P_2) = E(P_1) \oplus E(P_2)$ for all patterns. Encryption is done using a specific secret key.

Now assume the attacker has a decryption machine, and can do Chosen Cipertext Attacks:
He can pick a set of 128 cipher blocks say ${C_j}$, and the decryption machine gives him the matching ${P_j}$ Plaintext blocks.

I am wondering, how to prove that he can decipher ANY cipher block without knowledge of the secret key?

Well, one obvious way he can decrypt ANY cipher block is just give it to his Decryption machine; that machine will give him the matching plaintext block, which is precisely what he is looking for.

Now, normally when we give an attacker a decryption oracle, and give him a challenge "decrypt this specific message", we put a limitation on the oracle that it won't decrypt that specific message; let us assume that there is such a limitation (even though it was not specifically listed).

So, we know that the encryption algorithm obeys $E(P_1 \oplus P_2) = E(P_1) \oplus E(P_2)$.

First question: does this imply that $D(C_1 \oplus C_2) = D(C_1) \oplus D(C_2)$ (where $D$ is the inverse of $E$)?  How would you show that?

Next question: if $D(C_1 \oplus C_2) = D(C_1) \oplus D(C_2)$, how would you select a set of ciphertexts $\{C_1, C_2, ..., C_n\}$ such that any ciphertext can be expressed as the exclusive-or of some subset of $C_i$?  How can you use this observation to decrypt this arbitrary ciphertext?

Bonus question (which goes beyond what they asked): how can you extend this observation if you were given a set of random plaintexts and their encryption?


Parameter choice Supersingular Isogeny DH In “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies” by DeFeo, Jao and Plut (PDF), the public parameters are defined as:

Supersingular curve $E$, and
bases $P, Q$ generating the torsion subgroup $E[l]$ respectively for Alice and Bob.

The parameters for the key exchange generated by Alice would be:

Random elements $m, n$.
The isogeny with kernel $K := \langle[m]P + [n]P\rangle$.
Some other stuff beyond this question…

So the question is:

Why does it not suffice to generate the torsion subgroup (respectively the isogeny, defined by kernel) with just one point $P$? Taken the subgroup $\langle P\rangle = E[x]$ i could also generate an isogeny. Also the final isogeny could be generated by Bob using only $\mathit{Alice}'$ resulting curve $E_{\mathit{Alice}}$ and the image of the the point $P_{\mathit{Alice}}$ as well as Bobs secret parameters.

Found the answer:

The $l$-torsion subgroup is isomorphic to a direct sum of two quotient groups:
$E[l] \simeq \mathbb{Z}_n \oplus \mathbb{Z}_n$, hence the basis requires two points and the elements of $E[l]$ are represented by linear combinations of such a basis.
[Reference: Elliptic Curves, Washington, section 3.1]


What exactly does Keyspace $K^3$ mean? This is from Dan Boneh's book
4.5 Constructing block ciphers from PRFs
Let F be a PRF, defined over $(K, X, X)$, where $X = \{0, 1\}^n$. We describe a block cipher $\varepsilon = (E, D)$ whose key space is $K^3$, and whose data block space is $X^2$.
Given a key $(k1, k2, k3) \in K^3$ and a data block $(u, v) \in X^2$, the encryption algorithm E runs as follows:
(snipped)

What exactly is  $K^3$ & $X^2$ here? Why has the KeySpace been cubed & the datablock space been squared?

What exactly are $K^3$ and $X^2$ here?

The notation $K^3$ where $K$ is the set of keys $k$ stands for $K\times K\times K$, that is the set of triplets $(k_1,k_2,k_3)$ with $k_1\in K$, $k_2\in K$, $k_3\in K$. When $K=\{0,1\}^n$ (the set of $n$-bit bitsrings), we can assimilate $K^3$ to $\{0,1\}^{3n}$ (mathematicians do this when there's a trivial bijection between two sets; here that's concatenation of bitstrings in one direction, and splitting into 3 equaly-sized bitstrings in the other).
Similarly the notation $X^2$ where $X$ is the set of blocks $x$ stands for $X\times X$, that is the set of pairs $(x_1,x_2)$ with $x_1\in X$, $x_2\in X$. When $X=\{0,1\}^b$, we can assimilate $X^2$ to $\{0,1\}^{2n}$.

Why has the key space been cubed and the block space been squared?

That must be the objective of the skipped construction. Increasing the keyspace is easy and there's one common example: 3DES cubes or squares the keyspace, leaving the blockspace unchanged. Increasing the blockspace is slightly trickier.
The cardinality of the key space is cubed: it goes from $2^n$ to $2^{3n}=\left(2^n\right)^3$. The cardinality of the block space is squared: it goes from $2^b$ to $2^{2b}=\left(2^b\right)^2$.


is there a problem with the following private set intersection protocol Say Alice has the following set:  $\{A_1,A_2,\ldots,An\}$
and Bob has the following set:  $\{B_1,B_2,\ldots,B_m\}$

Alice creates a key $a$ and bob creates a key $b$
these keys should be commutative (eg: use RSA)

Alice encrypts each element of her set with $a$ to create $\{A_{1'},A_{2'}, \ldots,A_{n'}\}$
and similarly Bob makes $\{B_{1'},B_{2'},\ldots,B_{m'}\}$ with $b$

Alice sends her set to Bob and Bob sends his to Alice.
Alice encrypts each element of $\{B_{1'},B_{2'},\ldots,B_{m'}\}$ with a to make $\{B_{1"},B_{2"},\ldots,B_{m"}\}$ and similarly Bob makes $\{A_{1"},A_{2"},\ldots,A_{n"}\}$

Now Alice sends $\{B_{1"},B_{2"},\ldots,B_{m"}\}$ to Bob and Bob sends $\{A_{1"},A_{2"},\ldots,A_{n"}\}$ to Alice.

Because the keys commute, if $Bi=Aj$ for some $i$ and $j$, then $Bi" = Aj"$
Thus Alice and Bob can each identify which elements they have in common.

Also this protocol only requires encrypting and communicating each element twice so it has $O(n+m)$ run time.

I have not been able to find this protocol anywhere and it seems very simple so I thought there must be a problem with it.

This is very similar to a well-known protocol that dates back to the following work.

  Catherine Meadows. A More Efficient Cryptographic Matchmaking Protocol for Use in the Absence of a Continuously Available Third Party. In IEEE Symposium on Security and Privacy. 1986

  Bernardo A. Huberman, Matt Franklin, and Tad Hogg. Enhancing Privacy and Trust in Electronic Communities. In ACM Conference on Electronic Commerce. 1999

It uses the commutative property, namely that $(x^a)^b = (x^b)^a$. This PSI protocol is usually used with the following modifications:

Usually Diffie-Hellman cyclic groups are used rather than RSA. This allows you to send around compact elliptic curve elements (e.g., 256 bits) instead of RSA group elements (e.g., 2048 bits). Diffie-Hellman groups clearly give you the commutative property that this protocol requires.

Also, RSA is commutative only when using the same modulus. In this setting, who chooses the modulus? Probably neither party should know the factorization.
It is not secure to exponentiate the raw items. Instead, they should be hashed under a random oracle first.

Consider if Alice holds items $x, x^2, x^3, \ldots$ and Bob only holds item $x$. Then Bob will eventually learn $x^{ab}, (x^2)^{ab}, (x^3)^{ab}, \ldots$. He will recognize $x^{ab}$ because he has item $x$ (this is what we expect). But he can also recognize the other values as $(x^{ab})^2, (x^{ab})^3, \ldots$, and conclude which of $x^2, x^3, \ldots$ Alice holds. Clearly this is a violation of privacy.

The parties should compute $H(x)^{ab}, H(x^2)^{ab}, H(x^3)^{ab}, \ldots$,  where $H$ is a random oracle. $H$ breaks the algebraic relations among the items, so that knowing $H(x)^{ab}$ doesn't help you predict $H(x^2)^{ab}$.
The RSA assumption and CDH assumptions give you the following property: "given $H(x_1)^{ab}, \ldots, H(x_n)^{ab}$ for random/secret $a$, it is hard to compute $H(x^*)^{ab}$ for $x^* \not\in\{x_1, \ldots, x_n\}$." This is not quite enough for security of the PSI protocol. We in fact need $H(x^*)^{ab}$ to be pseudorandom given $H(x_1)^{ab}, \ldots, H(x_n)^{ab}$ (not just hard to compute). This can be achieved by assuming DDH rather than CDH, or by applying an additional random oracle, so that Alice sends values of the form $H'(H(x)^{ab})$.


Difference between secure function evaluation and private function evaluation? Yao's garbled circuit is used to compute multiparty computation. I know that secure function evaluation is used to hide users input and circuit from each other.

Can any body tell me what is private function evaluation? and how is it different from secure function evaluation?

You will find similar terminology interchanged a lot in this field. So, secure multiparty computation can take the acronym MPC, SFE, SMC and so on. In general, you should look at each paper closely to see what they mean in their definition. However, pretty much secure function evaluation is just another term for secure computation. In contrast private function evaluation can refer to the case where the function itself is private and is not revealed. Note that these are completely orthogonal to the number of parties involved.


Re-using parts of a one time pad to encrypt a new one? The main problem with OTP's is the fact that they can only be used once.

Would it be possible to use a random number that's, say, 512 digits, then use 256 of those for the (non-random) message, the 256 remaining ones to send half of the new pad (to be able to send a message back), then re-use those last 256 to send the second half?

As far as I can see, the clear text is obviously obscured (exactly the same as a standard OTP), and the re-used part is also secure because of the fact that the encrypted information is random as well.

The big difference from a two / many time pad is that the re-used part never comes into contact with any predictable data; it's an entirely different part of the message. So, as far as I can see, you could say the OTP encrypts the 256 digits, just as well as the 256 digits encrypt the OTP (both are completely random). Therefore, there should be no difference between the security of this and the regular way of using OTP's. If you were to re-use the part of the pad that encrypted the plain text, you would be vulnerable with regards to a known plain text attack.

Of course, it's not that efficient, because if the random number that encrypted the first message is discovered, all future numbers can be discovered. But other than that it could be pretty fun.

Let me get this straight; if you are sending a 256 bit message, and get a 256 bit reply, the obvious way using OTP would be the message to use up 256 bits of pad, and the reply to use up a separate 256 bits of pad, using a total of 512 bits.

Instead, you propose to use a total of 512 bits to send the message (and a temporary pad), the reply will then be encrypted using the temporary pad); this uses a total of ... 512 bits of pad.

Well, I don't see any reasons why this would be insecure (however, you appear to think you have a way to extend this to multiple messages; exactly how that would work is not obvious), however I also don't see any specific advantage over normal OTP; in both cases, you're using 512 bits of pad to transmit a total of 512 bits of message.


In the Linux Kernel 4.8+, does the CSPRNG update the entropy pool? My understanding of how /dev/urandom works is that the kernel collects true randomness from a variety of sources, and mixes them together to remove statistical bias. It does this at regular intervals to refresh the entropy pool.

The CSPRNG then takes a subset of these bits to generate random bits for consumption.

My question: in the course of dipping into the entropy pool, does the CSPRNG also update the entropy pool or is that done only by the OS?

The CSPRNG is updated from the input pool from time to time (at most every 5 minutes by default). It does not feed back into the input pool since it is derived entirely from it in the first place.

Prior to 4.8, the input pool would periodically feed into the blocking pool and non-blocking pool at long enough intervals to provide a "catastrophic reseed" that mixes in enough entropy that it could not be brute forced even given knowledge of the prior state. These two pools were identical, with the exception that the blocking pool would track entropy estimates and block if the estimate drops too low. Since 4.8, the non-blocking pool has been replaced by a CSPRNG based on the ChaCha20 stream cipher.

From Documentation and Analysis of the Linux Random Number Generator, version 2.5


Is it possible in PGP to provide verification/verify the ownership of a public key? I am new to PGP/GPG and I am somewhat confused by the idea of the Web of Trust (WoT). Isn't signing a public key with its private key enough to prove the ownership of it? if it is so, why don't key servers just do that before storing the keys instead of relying on users to trust each other?

In short, it is not about proving that you have any key, it is proving that this key is bound to a specific entity. The identity of the person submitting the key must be established.

The server doesn't know which keys to trust. It can sign any key, but what would be the point of that? The idea is that users can verify by other means that the key is trusted and belongs to the person submitting the request. Verification over the phone (using the key fingerprint) or even receiving expected messages at a particular time could do that. Otherwise an adversary can inject a public key belonging to their own key pair, using your identity information.

If you start just signing keys - without making sure that you can trust that the key belongs to a person - then you're actually poisoning the server. It is important to keep that in mind and give your friends / colleagues a call if you suspect anything is wrong. Certainly do verify that keys belong to the right entity when they have not yet been sufficiently verified by others.


Protect the original message of a hash from brute force My apologies for the somewhat inaccurate terminology.

Basically I have some simple messages (entropy ~50 bits) the user will use for registration. The messages should remain private, and I don't plan to keep that in my database. However, I do need to keep a hash so that I know when the same message is used again. (this is quite similar to ProtonMail registration)

Using simple hash it would be trivial to run through all possible messages to find the original messages from the hash, even if a really slow algorithm is used. Besides, a random salt probably can't be used as I need to check if the hash against all previous hashes.

Besides encrypting the database, I am thinking if an HMAC construct would help here. I assume the attacker cannot find the original message from the hash, if she couldn't find the key (where the key is not distributed, locally stored), and finding the key would be computationally infeasible if only the hash table is leaked. Is this correct? Is there a better solution?

First of all, even the entropy is 50-bit, it is not easy to list all possible string to execute an attack on the data set.

Using hash function can hide the data itself due to pre-image resistance, however, the same data can have the same hash since the hash functions are deterministic. Therefore, it can reveal information, especially there is also side frequency information about the data. This is a modern frequency attack[*] and also applies the ECB block cipher mode [‡] of operation. Also, collisions in hash functions are inevitable due to the pigeonhole principle, to reduce the birthday attack probability use SHA3-512 so that the probability will be so small $\mathcal{O}(2^{256})$ for finding a collision with %50 probability. Of course in the adversaries advantage, 50% is too big. This is not a problem for 512-bit hash output, however, one must consider it in the other cases.

In the case that you have only 50-bit space (not 50-bit entropy), it is quite possible to build a rainbow table to attack your hash values, i.e. finding pre-images. If you consider that the bitcoin miner calculates $2^{67}$ double SHA-256 hash values in a second, then 50-bit space is quite accessible. The mitigation against the rainbow table attack (The rainbow tables are dead) is using salt, however, that you want to avoid.

You should use HMAC-SHA3 so that you will have a keyed hash that also provides unforgeability. Since HMAC requires a key, the attackers cannot find the original message or forge a new one, that we expect computationally infeasible. The rainbow table doesn't apply since the attackers don't know the key.

However, even with HMAC, frequency attack condition still applies if the same data occurs multiple times that can leak information. Meaningful possible mitigation is using salt that prevents you from directly comparing the values, or in another term separating the domains of the user.

In short, yes use HMAC-SHA3 or HMAC-Blake2.

update per comment:

  Can I assume the data be secure if the key is not leaked?

HMAC is not encryption, it is a keyed hash function for message authentication. The real security issue for message authentication is unforgeability. No, the attackers cannot find. Even if, they are able to find out out one to forge, it doesn't mean that they found your message, actually they need to find another one to forge because there is already one.

[*] Read from this question How can frequency analysis be applied to modern ciphers? or the below articles.

Inference Attacks on Property-Preserving Encrypted Databases, by Naveed et. al. Applied frequency attack on electronic medical records.
On the Difficulty of Securing Web Applications using CryptDB, by Akın and Sunar, example how to infer the data form Hospital records.

[‡] One might not even call it a block cipher mode of operation.


How to generate a non periodical, theoretically infinite, sequence of numbers from a secret alphanumeric key Are there algorithms that enable the creation of a non periodical, theoretically unlimited, sequence of numbers based on an alphanumeric secret key? The idea is to produce always the same unique sequence from a secret alphanumeric key, where the sequence doesn't leak information about the used key, and looks random enough from a cryptographic stance. If the key changes just one bit, the pattern is completely different. Is there a known secure way to produce this?

There are quite a few options here as you can basically use any algorithm with a single key input and configurable amount of output:

a DRBG (or CSPRNG) such as Hash_DRBG or CTR_DRBG;
a stream cipher or block cipher in streaming mode such as Salsa20 or AES in counter mode;
a KBKDF such as HKDF;
a XOF such as SHAKE256 (SHA-3).

In principle a DRBG - deterministic random bit generator - may seem to be the best option. A DRBG basically turns a seed into a stream of random bytes. It may however request reseeding, which may be a problem. To resolve this, just keep feeding it the same value or zero bytes at the same point in the stream and you should be OK. Furthermore, the DRBG needs to be well defined; some programming API's make changes in the algorithm without notification. This may mean that there are few implementations available - if any, as most of them are simply designed to return unpredictable random numbers. Note that a DRBG is also known as a CSPRNG - a Cryptographically Secure Pseudo Random Number Generator or sometimes just as a PRNG.

A stream cipher takes a symmetric key (and possibly an IV) and turns it into a pseudo random key stream consisting of a virtually unlimited amount bytes. This is completely deterministic and doesn't require reseeding. Note that this key stream was created for encryption rather than randomness. One of the weird properties of counter (CTR or SIC) mode encryption is that it never repeats a block, which distinguishes it from a random stream of bytes. The chance of randomly creating e.g. two identical 128 bit blocks is however infinitely small, so that should not pose a problem.

A KBKDF - Key Based Key Derivation Function - such as HKDF generally can be seen to have an extract and expand phase. First during extraction the entropy in your initial key is put into the state. This state is then used to generate a virtually unlimited amount of bytes. This is called the expansion phase. Problem with this approach is that most of the KDF's expect the output size to be defined in advance.

A XOF - eXtendable-Output Function - can be used by using the key as input for the XOF and defining the random stream as output of the XOF. This is probably the easiest function to use. The input doesn't have to be a particular size and the function was defined to stream out information. The main known XOF's, SHAKE128 and SHAKE256 are however part of the SHA-3 specification and may not be available for all runtimes.

To use your alphanumeric key you first need to convert it into a key that is acceptable to the function that you decide to use. First of all, you'd convert it to binary using character encoding such as ASCII (or UTF-8, which amounts to the same thing).

You may need to use a KDF or hash to generate a key of the right size, in case your DRBG or cipher expects a key of a specific size. In general the leftmost bytes of a hash would also suffice.

In general all of the above are one-way functions so you cannot convert them back to your alphanumeric key apart from brute forcing the alphanumeric key. They all use deterministic (and therefore repeatable) algorithms to generate streams of bytes.

The XOF functions seems to be the main contenders as they are designed for streaming and accepts any size of input data.

AES in counter mode + hash as KDF to create the key - is a very good contender if simply for the reason that it is almost universally available, it's definitely impossible to retrieve the secret key and the output is likely good enough.


Is it possible to construct a compression function that works exactly as MD5's CF but is much easier to compute? Is there any chance that MD5's compression function can be represented in a completely different way so that it's much easier to compute/reverse it?

Not that we know of.

Although we have no proof, there is still a strong belief that MD5 represents a one-way hash. It is broken, but that doesn't mean we can reverse it (or the compression function that it is based on).

Similarly, we don't know a faster way to compute it (in the algorithmic sense) but we cannot proof that there isn't a faster "representation".

One of the things to consider here is P versus NP. As long as this remains unsolved we don't know if P = NP could hold, which would have interesting consequences.


Can I dynamically calculate an appropriate number of iterations for PBKDF2 based on the system time, rather than using a fixed value? Could you choose the number of PBKDF2 iterations based upon the system time?

I've heard a few people recommend that the number of iterations for PBKDF2 should be doubled every two years (starting with the recommended 1000 iterations in the year 2000 when PKCS #5 was released).

Theoretically at least, you could determine the ideal iterations through an equation based upon the current time. Perhaps something like:

year = <current time in years>
exponent = (year - 2000) / 2
iterations = 1000 x (2 ^ exponent)

Which would give a value of about 115,196 iterations at the time of writing.

Assuming that:

The system clock can be trusted.
The number of iterations is stored with the hash, so that hash verification is still possible.
Safeguards are in place to stop the system attempting to hash with a ludicrous number of iterations.
You continue to monitor the actual time taken to hash passwords on your specific hardware.
You regularly upgrade hardware to keep up with the increasing performance requirements.
You choose an appropriate underlying hash algorithm.

Would such a system be safe and practical?

Of course you can - but as to whether or not it's a practical or advisable idea, I don't think so.  It's not really prudent to implement crypto systems/protocols and assume that they'll be fine in 10 years.

Cryptography is a dynamic field that changes rapidly; algorithms get broken, hardware improves, governments try to undermine the field, and attacks only ever become more sophisticated.  The only way to ensure the security of your system is to stay abreast of what's happening in the crypto/security world, and to adjust your system/protocol accordingly.  For example, despite the recommendation of doubling PBKDF2 rounds periodically, many people in the community now recommend a memory-hard PBKDF like Scrypt instead, making PBKDF2 more or less redundant (although not quite, as it's used internally in Scrypt, and in systems where memory is not available).

Your proposal does have an upside though: a vast majority of security/crypto protocols get implemented and forgotten about.  Look at the linked-in fiasco for example - at the time of designing the system, the architect may have (however erroneously) thought that a saltless sha1 hash of the user's password would be sufficient security.  These days, the idea of a prominent website doing this is unthinkable (hopefully).  So in this sense, your proposal does at least attempt to stay up-to-date, which in lieu of a static system, is better than nothing.  However, I think that continuous scrutiny and a more "hands on" approach is preferable.


How to use salt when there is only one user I am encrypting files for storage in an untrusted location, using a custom Java program to do that. There is only one user, but there are many files.
I am using AES in CBC mode with PKCS5 padding, and the key is created from a single passphrase using PBKDF2.

Question: Would it increase security if I used a different salt for encrypting each file, or would that only make sense if I also used a different passphrase for each file?

The posts I could find deal with a multi-user scenario, where of course you need per-user salts. But I have only 1 user and 1 passphrase, so creating a new key for each file feels wrong to me.

In a scenario such as yours, where there is only one password/passphrase, but it is used as key material for the encryption of multiple CBC encrypted files, you will (as you noted yourself) obviously not make it any harder for an attacker to compute your password, should you use a salt.

However, using a salt would mean that the encryption of each file is independently keyed, which might increase resistance against collisions in the CBC chaining state, should you use the same password for encrypting a very large number of very large files. Since you are using AES-CBC and AES has a 128 bit block size, you would have to encrypt billions of GB sized files to get close to a 0.5 probability there would be just one such collision (in two 128 bit blocks somewhere), but depending on your security requirements, even such a small risk might be unacceptable. An alternative to using salts, would in such case be to use a cipher with a 256 bit block size instead of AES.

A third alternative would be to use random keys for each file, and only encrypt that file specific key using the key you derived from your password. If you put those encrypted keys together in a separate index file, you will get two additional benefits:

Changing the passphrase will become much cheaper, in particular if you have a large number of files or very large files. Changing the passphrase might, or might not, be something that improves your security. Obviously, if an adversary at some point in time gets hold of all of your files and is able to compute the passphrase you were using at that point in time, you gain nothing by later changing the passphrase. The file specific keys (for the files that existed at that point in time) will already be compromised.
However, using random file specific keys, will make it possible for you to put together index files for other users, containing only the keys of the files those users are supposed to get access to.


Structure for an introductory course on cryptography? Many introductory courses on cryptography have their treatment of secret-key crypto start with OTP, then block ciphers, and for public-key cryptography revolve around RSA with no notion of padding (some even have matching exercises showcasing insecure practices, beyond using artificially small parameters). It is all too common that after such introductory course, students will happily consider the OTP as a useful cipher, or tell (and try to perform) things like encrypt with private key, and believe (perhaps rightly) that's what they have been taught.

I ask what would be a better roadmap for a short introductory course on cryptography, aimed at students with an inclination towards engineering and IT, that

gives the audience a fair grasp at the basic functions modern cryptography performs routinely (signature, authentication, key exchange, encryption..), and how they differ in goal;
illustrates some of these functions with concrete methods, not requiring much more advanced math than RSA does, and implementable (with artificially small parameters) on about anything that can compute, including spreadsheet formulas;
not touching formal definitions of security, much less game proofs, advanced cryptanalysis..

I realize that an actual course content will depend considerably on the time allocation, math background of the audience, and the (widely varying) organization and goals of the learning environment. I wish these things are left out inasmuch as possible, to concentrate on what cryptographic techniques should be in a coherent exposition of cryptography, so that this question can hopefully be considered on-topic.

I recently read Understanding Cryptography: A Textbook For Students And Practitioners by Christof Paar & Jan Pelzl. I can say without a doubt that it addresses all your bullets and in the meantime it's easy and fun to read.

I have an MSc in Information Security so everything I read I already knew but some of the concepts were so well put that I felt I got a better grasp on how some things work.

As I was a reading it I thought to myself that if I ever teach a introductory course in Cryptography I'll follow this book. You can give it a shot, see if its format suits your needs as a roadmap.


Is MCrypt's 8-bit OFB mode secure? I just stumbled across a Stack Overflow post which points out that the libmcrypt library (notably used in PHP) implements a somewhat unusual set of block cipher modes: it calls the usual CFB and OFB modes, with full-block feedback, "nCFB" and "nOFB" respectively, and implements the CFB-8 mode as just "CFB".

Besides the somewhat unconventional (and potentially confusing) naming convention, there's nothing novel there.  However, it turns out that libmcrypt also features an 8-bit shift register variant of OFB mode, called simply "OFB", which is described rather curiously in the documentation:

  "OFB: The Output-Feedback Mode (in 8bit). This is a synchronous stream cipher implemented from a block cipher. It is intended for use in noisy lines, because corrupted ciphertext blocks do not corrupt the plaintext blocks that follow. Insecure (because used in 8bit mode) so it is recommended not to use it. Added just for completeness."

Ignoring the weirdness of a library supporting an encryption mode that its own developers describe as "insecure" and recommend "not to use it", I started wondering — is it really insecure?

It's well known that OFB mode keystream generation is equivalent to encrypting an all-zero message in CFB mode.  Thus, if CFB-8 mode is IND-CPA secure (and it is, at least when used with a random IV), so that, in particular, the encryption of an all-zero message cannot be distinguished from a random bitstring, then neither can the XOR of this ciphertext with an arbitrary message.  Doesn't that imply that this "OFB-8" mode is IND-CPA secure, too?

Actually, I think I found the answer to my question while writing it, but I'll post it anyway, since it might be interesting to others:

Yes, OFB mode is secure even with 8-bit feedback, at least as long as IVs are chosen randomly.

Specifically, in the paper "New proof for old modes" (IACR Cryptology ePrint Archive, 2008), which I've cited earlier here, Mark Wooding proves the IND-CPA security (and, in fact, a somewhat stronger security property termed ROG-CPA, for "real or garbage" indistinguishability) of both CFB-$n$ and OFB-$n$ modes for any number of feedback bits $n$, provided that either:

the IVs are chosen randomly,
the IVs are generated by encrypting a deterministic sequence (a "generalized counter") using the block cipher, or
the IVs are directly chosen according to a deterministic sequence, and $n$ is no less than the block size of the block cipher used.

(The extra limitation on the feedback size $n$ in the case of a deterministic IV sequence is due to that fact that CFB and OFB modes using less than one cipher block of feedback have some rare "weak IVs" that can produce a low-period keystream.  Presumably, a deterministic IV sequence chosen to deliberately avoid such IVs would also be safe.)


Is MD5 second-preimage resistant when used only on FIXED length messages? I fully realize that MD5 should not be used in any new project, but in my particular situation I have severe CPU performance issues, so MD5 is convenient.
I have read a lot about MD5 security for this project, and I know it is broken in several ways: extending a file while having the same MD5 hash, and generating two different files with the same MD5 hash, for instance.

In my particular instance, I have a Merkle tree. The root is validated with SHA256, but for performance reasons the internal nodes use MD5. The key point  is that in my application the MD5 hashing is done over fixed length blocks.
For instance, leaf nodes are MD5 over a 4096 bytes block. Internal nodes are MD5 over a 16384 bytes block.

So, my question is: Given a known block and its MD5 hash, is there an attack to generate a different block of the same length with the same MD5 hash?

I don't want to generate two 4096 bytes blocks with the same hash. I want to know if, when given a 4096 bytes block, can one replace it with a different 4096 bytes block with the same MD5.

Right now, the best published attack against MD5's preimage resistance (first preimage, actually, but it applies to second preimage resistance as well) finds preimages in cost $2^{123.4}$ average cost, which is slightly better than the generic attack (average cost of $2^{128}$), but still way beyond the technologically feasible. The attack rebuilds the preimage as a two-block value (128 bytes) and can be adjusted to any larger length.

Therefore:

There is no practical attack against your 4096-byte hash tree nodes yet.
But the fact that they have a fixed 4096-byte length does not appear to improve the situation.

Still, the foundation of the security of MD5 appears somewhat flimsy, so it is not recommended (at all) for new systems. If you have severe CPU constraints, then you might want to consider the SHA-3 candidates. The 14 "round 2" candidate functions have been quite thoroughly investigated, and no break has been found in any of them; in that respect, they are all stronger than MD5, and arguably stronger than SHA-1, which has a known collision attack (but no known preimage attack). Some of them are quite fast, and competitive with MD5. Depending on your architecture (8-bit CPU, small 32-bit ARM, big modern 64-bit PC with AES-NI opcodes...), you would be most interested in BMW, ECHO, Shabal and Skein. "The" SHA-3 (Keccak) is not as fast as these (except on dedicated FPGA / ASIC).

It is usually best, for public relations, if you use a standard, recommended function. However, if you decide otherwise, using a function which has survived some scrutiny by cryptographers with no known weakness is arguably better than using a function with big weaknesses.


Reduced message expansion in NTRU In the original NTRU proposal from 1998, it says on page 16:

It may be worth mentioning, though, that there is a simple. masking technique that can be used to significantly reduce message expansion. With this approach, Alice sends a pair of polynomials $(e_1, e_2)$. The first polynomial is the encryption $e_1 =r_1 \cdot h+r_2 \mod q$, where $r_2$ is a randomly chosen polynomial with all coefficients equal to -1, 0 and 1. The second polynomial is $e_2 =r_2 \cdot h+ m' \mod q$, where $m'$ is the plaintext message in a suitable digital envelope modulo $q$.
Since Bob can decrypt $e_1$ to recover $r_2$, he is able to recover $m' \mod q$. In other words, at the cost of doubling the length of the encrypted message to $2 n \log_2 q$ bits, Alice is able to send to Bob a $n \log_2 q$ bits of information. In principle, this reduces message expansion to 2-to-1, although the use of a digital envelope will naturally
increase message expansion.

Is this still possible in the current instantiation of NTRU?

I work for Security Innovation, which owns the NTRU algorithms. Glad to see this interest!

You can look on this approach as two separate encryptions: one public-key encryption to transport $r_2$, and one symmetric encryption using $r_2$ as the key to encrypt $m$. This makes it look much more like standard practice in asymmetric crypto, where you typically use a public key crypto algorithm to agree a key and then use a symmetric algorithm to encrypt the data.

So the question is, is using $r_2*h + m$ a good symmetric encryption scheme? And the answer is no, it isn't really. For example:

It's not secure against chosen plaintext attacks. Consider an attacker who knows one of the messages 00000... and 11111... has been encrypted. She takes the ciphertext and multiplies by $h^{-1}$. If the result has the form of $r$, she knows the message was 00000... . If it doesn't, she knows the message was 11111... .
It's not authenticated. An attacker who knows I'm sending the message "pay \$200" can easily change it to "pay \$999".
It's not clear how best to encrypt multi-block messages. You can come up with ad hoc constructions such as CBC of course, but this would need to be defined.

You can address all of these problems, but at the cost of additional processing time. Probably, although the raw encryption mechanism is very fast, if you do it securely it won't be any faster than using a standard symmetric algorithm. So we would recommend just using NTRUEncrypt for key transport or for encrypting small messages, and if you have more data to encrypt, doing it with a strong symmetric algorithm.


How can uniformity of hash functions (e.g. SHA-256) be proved? In reading about the Bitcoin protocol I noticed how much its proofs-of-work apparently depend on uniformity of the SHA-256 hash function. And so  presumably do many other applications.

How do researchers go about proving uniformity of proposed hash functions? Is it just an empirical matter of running many inputs through the function and observing the distribution of outputs, or can one formally prove the property? Where could one (non-crypto-expert) learn about how such proofs are constructed and look one up e.g. for the case of SHA-256?

Uniformity is a tricky one. SHA-256 (as well as SHA-3 for that matter) follows a heuristic approach. That is, the design is not based on a hardness assumption (for example, the factoring or discrete-log assumption) but on criteria that have only been verified empirically. As such, also the study of uniformity is an empirical study. The development of SHA-1/SHA-2 was not a public process (it was developed by the NSA and NIST) and no rationale as to design choices were given. What you usually do in this case is to run statistical tests and see if any of them indicate any weaknesses. For example, a simple test would check that every single output bit is set to 1 with probability 0.5. A suite of statistical tests that, I believe, was used in the evaluation of AES was published by NIST (http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html).

If you want to go into more detail I would have a look at the SHA-3 competetion. Here, every candidate had to provide an elaborate and convincing case for why this candidate is a good pseudorandom function. You can find the documents for Keccak (the new SHA-3) on http://keccak.noekeon.org/files.html. The Keccak reference has a whole section on the analysis of Keccak as a pseudorandom function.


Safety of using GPG's libgcrypt prime generation for generating ephemeral Diffie-Hellman primes? My company wants to generate new primes for every Diffie-Hellman key exchange.  We are thinking of using the prime generation scheme in GPG’s libgcrypt library.

The code documentation says that the scheme that libgcrypt uses is based on a paper from Crypto 97.  It is entitled, ”A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroup”  and is by Lim and Lee.

Is this Prime Generation scheme by Lim and Lee still considered secure?  Is the libgcrypt code the only implementation of this scheme?

The Lim-Lee Prime Generation Algorithm you reference has been used in GPG’s libgcrypt for almost 20 years.  As long as the bit length of the smallest prime (other than 2) dividing the prime (p) is greater than or equal to twice the desired bit security the Lim-Lee prime generation produces sufficiently strong primes for use in Diffie-Hellman key exchanges.  For instance, if one wished for 128-bits of classical security, the smallest prime (other than 2) dividing p-1 should be at least 256 bits in length.

Using the Lim-Lee algorithm to generate a prime p gives all of the prime factors of p-1.  These factors can be used to prove the primality of p using an extension of Pocklington’s theorem.  If you were to use the Lim-Lee algorithm for generation of ephemeral primes for a Diffie-Hellman key exchange you should consider using deterministic RNG for the Lim-Lee algorithm.  If you sent the seed for the deterministic RNG to the other side of the key exchange, they could  re-run the Lim-Lee algorithm, produce the prime p, the factors of p-1 and check that p is indeed prime and that all of the prime factors of p-1 are suitably large.  Sending a seed rather than the prime and all its prime factors is more bandwidth efficient.

Given the widespread use of GPG in the world, I would assume that if there were some major weakness in the Lim-Lee algorithm someone would have published a criticism of the algorithm by now.  I have never run across such a criticism.  Therefore, I believe that the Lim-Lee generation scheme is fit for the purpose you describe.


What is a good way to demonstrate elliptic curve cryptography? For school (high school) I am writing an essay on elliptic curve cryptography. The assignment needs to include a practical part, so I decided to write a Python class for elliptic curves. This class is capable of performing elliptic curve arithmetic and can encrypt files using MV-ElGamal (although it is horribly slow).

The problem is that I need to present my research, including the practical part, to fellow high school students. I considered writing a chat app or something similar, with a connection secured by elliptic curve diffie-hellmann+AES256 and elliptic curve digital signatures, however, I'm not sure how easy that is. What would you suggest? I am looking for something simple, with the focus on the cryptography as much as possible, since that is what my essay is about. I also don't want something too ambitious since I am still only a beginner when it comes to programming (I am more into the math side). Keep in mind that my audience is not particularly interested in mathematics nor programming though.

An encrypted chat application by itself will not really demonstrate anything, since from the users' point of view it will not (if done properly) be any different from an unencrypted one. To demonstrate the encryption, you would need to also use Wireshark or something similar to sniff packets on the network and see that they are encrypted. But if simply showing a ciphertext and saying "this is encrypted" is enough, you can just encrypt a file, which apparently you can already do.


Generate $J_0$ for GCM cipher when $\operatorname{len}(IV) \neq 96$ bits I have the following questions about the construction of J0 when is not equal to 96 bits, $s= 128\big\lceil \operatorname{len}(\text{IV})/128\big\rceil-\operatorname{len}(\text{IV})$

For example if my IV is equal to 1, Calculating with Len would be 8-bit result, If we subtract, $\operatorname{len}(IV) / 128$ and calculating the result is 1 subtracted by 8 would be 7, Real number 1 or it is taken as 8-bit byte, and it would be and the rest would be 0?

And the 128 which is outside what is the function, multiply? And read the steps, but reading the explanation of the document and reading the formulas confuses me.

If $\operatorname{len}(\text{IV}) ≠ 96$, then let
$s= 128\big\lceil \operatorname{len}(\text{IV})/128 \big\rceil-\operatorname{len}(\text{IV})$, and let
$J_0=\operatorname{GHASH}(\text{IV}||0s+64||[\operatorname{len}(\text{IV})]64)$.

Yes, the initial 128 is multiplication and it is performed before the subtraction.

OK, so if $\operatorname{len}(IV) = 1$ in bits then $$s= 128\big\lceil\operatorname{len}(IV)/128\big\rceil-\operatorname{len}(IV)$$ would be $$s= 128 \cdot 1 - 1 = 128 - 1 = 127$$

However, if you encode it as a single byte then $$s= 128 \cdot 1 - 8 = 128 - 8 = 120$$.

Note that any IV size between 0 exclusive and 128 inclusive will let $\big\lceil \operatorname{len}(IV)/128\big\rceil$ evaluate to 1, as the division result is in between 0 exclusive and 1 inclusive.

The IV is generally delivered as byte array as implementations generally do not operate on bits, even if the speficiation does specify the algorithm in bits. So generally delivering just one bit is not possible. This means that the most significant (leftmost bits) of the byte or bytes are included in the calculation even if they set to 0. The IV is handled as a string of bits, not as a number within the specification. So lets assume a single byte with value 00000001 in bits.

For the second part of the scheme to calculate $J_0$ we have $$J_0=\operatorname{GHASH}_H(IV||0^{s+64}||\big[\operatorname{len}(IV)\big]_{64})$$ which means the $\operatorname{GHASH}$ using $H$ over the one byte IV concatenated by $s + 64$ bits (184 bits or 23 bytes) set to zero and then the length of the IV created as static, big endian unsigned encoding of 8 bytes. If you combine the sizes of the fields you'll get a nice 32 bytes: $1 + 23 + 8 = 32$, which is handled perfectly well by GHASH that requires 128 bit / 16 byte block size.

The result will be, the GHASH over (in hexadecimals, two characers per byte):

01_000000_00000000 00000000_00000000 00000000_00000000 00000000_00000001


Interpretation of (NIST) Non Overlapping Template Matching Test Regarding the Non-Overlapping Template test, this test normally gives us a bunch of p-values (148 values). I would like to ask that how do we interpret those values into a single p-value for presenting in an academic report. I have seen many papers illustrate as only a single p-value. For example,

Cao et.al, Phys.Rev X 6, 2016

In this work the p-value of Non-Overlapping Template test is shown as a single value. I have tried using fisher method to combine all of the p-values but by it's characteristic, the p-value after a combination drops exponentially.
Is there any simple way to interpret ?

Thank you in advance.

First, Fisher's method is a way to combine several independent statistical tests with known distributions under the null hypothesis into a single statistical test with a known distribution under the null hypothesis.  If you would have raised an alarm for certain outcomes of the individual statistical tests with a known false alarm rate, then you can use the same criteria to raise an alarm for the composite test with a known false alarm rate.

Another way to look at this is: Fisher's method is a way to combine several independent d20 rolls into a single d20 roll, so that if you're given a black box that prints d20 outcomes, you can't tell whether a gremlin inside is doing several statistical tests and applying Fisher's method to them and rounding the result, or just rolling a d20.

If you would have raised an alarm when one of the statistical d20 tests rolled a 1 for the standard false alarm rate of 0.05, then you can raise an alarm when the Fisher composite statistical d20 rolls a 1 for the standard false alarm rate of 0.05.
Another way to look at this is:

With one statistical test, you lay out the possible test outcomes ($p$-values) uniformly on a line segment from $[0,1]$ and raise an alarm for any data that gives a $p$-value in $[0, 0.05]$.
With two statistical tests, you have a grid of outcomes on the unit square $[0,1] \times [0,1]$.  On what subspace of the unit square do you raise an alarm?

Fisher's method is a particular choice of which subspace of the unit square raises alarms.  There's some good illustrations of this—and comparisons to an alternative method of combining $p$-values—in the answers to a question about Fisher's method on stats.se.

There are other methods too for combining a collection of $n$ values $\{p_i\}_{i=1}^n$ into a single test statistic with a known distribution:

The arithmetic mean $\sum_i p_i/n$, as discussed in the stats.se answers, and known as Edgington's method.
The root-mean-square, $\sqrt{\sum_i p_i^2/n}$.
The geometric mean $\prod_i {p_i}^{1/n}$, which turns out to be tantamount to Fisher's method—just take the log.
Pearson's complementary geometric mean, $1 - \prod_i (1 - p_i)^{1/n}$.
The minimum $\min_i p_i$.
$p_1$, ignoring $p_2, p_3, \dots, p_n$ altogether.

Why should you prefer one of these over the others?  They all give rise to statistical tests that have any prescribed false alarm rate you want, so they must all be good, right?  Well, there's an elephant in the room.

Why raise an alarm when you roll a 1, rather than, say, a 7, on your d20—i.e., why do we care about $p < 0.05$?  What's really interesting is the alternative hypotheses.  The null hypothesis is that the device is working correctly as intended (and perhaps that working correctly means a perfect uniform distribution).  But the test is valuable insofar as it raises alarms at a substantially higher rate for plausible deviations from the null hypothesis—for instance, a significantly higher number of one bits than zero bits, which can happen in samples under the null hypothesis but only with low probability.  What plausible deviations might there be?

Study the physics or engineering of the system—don't just discard them as waste byproducts of the process that led you to a good NIST test result.

What do you know about the physics that might let you predict the result better than flipping a coin?
What manufacturing flaws and failure modes could the engineered system have that might change the distribution?

Many of these deviations or failure modes will not be detected by generic statistical tests.  As an extreme case, if your device chooses $k$ uniformly at random and produces $\operatorname{AES}_k(0) \mathbin\| \operatorname{AES}_k(1) \mathbin\| \operatorname{AES}_k(2) \mathbin\| \cdots$, except when it's broken and always chooses $k = 0$, generic statistical tests will never detect that broken case.

What matters for security is showing that the smartest, best-funded physicists in the world can't do better than a certain advantage at predicting what the outcome is, and that if the device fails in some way then you will detect that failure and stop relying on it.

The $p$-values of NIST statistical tests on samples you took during development?  These are more like the waste byproducts of a process that led you to a good hardware RNG.


Is cypher.js secure for sensitive data? Is this library secure? Link to github repo
Here's his explanation:

Cypher does not encrypt through allocation based on mapping patterns. Cypher encryption process is completely mathematical and therefore, no pattern can be observed in the encrypted data result. Furthermore, Cypher encryption process result is not persistent, which means that encrypting a particular object with a particular key multiple times is highly unlikely to result in the same data - see demonstration below.

let data = "Cypher AAA", key = "_b7gBiG1oo";

console.log(data.encrypt(key)); // Possible OUTPUT: x%7~(yo~6}103V3I'Iv
console.log(data.encrypt(key)); // Possible OUTPUT: xMeqv|D~~21c1Z'oOw
console.log(data.encrypt(key)); // Possible OUTPUT: tmu~4~v|l^&X"~1I'|

I'm no expert in this field, but based on his description is seems like it can't be reversed or cracked.

No. It is not secure. This is very simple substitution algorithm. It shows patterns clearly. If the encrypted message is long enough or if you have many short encrypted messages, you can crack it using simple frequency analysis. You don't need any complex technique to crack it.
Example:
let data = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
let key = "12345";
console.log(data.encrypt(key));
console.log(data.encrypt(key));
console.log(data.encrypt(key));

Result:
dopqrsopqrsopqrsopqrsopqrso~1}11pqrsopqrsopqrsopqrsopqrsb
dopqrsopqrsopq}33rsopqrsopqrso~3pqrsopqrsopqrsopqrsopqrsq
Nqrsopqrs}38opqrsopqrsopqrsopqrsopqrsopqrsopqrsopqrs~0opv

You see patterns clearly.


Digital signature that is only verifiable by one specific person I would like to digitally sign a message in such a way that the signature can only be verified by one specific person. Simply encrypting the signature will not work, because that person could then decrypt and publish the signature and everyone else would be able to verify it.

Does anyone know of a scheme to accomplish this? Or any other advice?

In my situation, the person verifying the signature has an incentive not to publish their private keys.

What you seem to be looking for is deniable authentication.

This is actually a somewhat stronger property than what you're asking for: it guarantees that the recipient (let's call him Bob) cannot cryptographically convince anyone else that the sender (let's call her Alice) signed the message, even if he discloses all his private keys, simply because the protocol guarantees that knowing Bob's (and/or Alice's) private key is both necessary to verify the signature and sufficient to forge it.  So Bob, seeing a message with a valid signature and knowing that he didn't create it himself, can be confident that Alice must have sent it — but he cannot use the signature to convince anyone else of that, since he could've just as well created the signature himself.

The simplest way to achieve this kind of authenticated but repudiable communication between two parties is to use a symmetric-key authenticated encryption scheme (or, if message privacy is for some reason not required or desired, just a plain MAC).  With these schemes, Alice and Bob know the same secret key that is used both to authenticate the messages and to verify their authenticity.  Thus, trivially, anything Alice can do (such as to create a valid authenticated message claiming to be from Alice to Bob) Bob — or anyone else who knows the secret key — can do as well.

The main drawbacks of such symmetric-key schemes are that they require a separate secret key for each pair of communicating parties (which could become cumbersome if there are potentially many such parties) and that the secret keys must somehow be securely shared between each pair of parties.  This would be easy if we had an encrypted and authenticated secure channel between each pair of parties, but since that's exactly what we're trying to set up here, that creates a kind of a chicken-and-egg problem.

One way around these issues is to use public-key encryption to share the secret keys.  In particular, we can use the Diffie–Hellman key exchange to establish a shared secret between any two parties, as long as they know each other's public keys (and, of course, their own corresponding private keys).

The Diffie–Hellman key exchange is often illustrated as an interactive protocol, but actually the only interaction it needs is for each party to send their public key to the other (which they may do in advance, e.g. by publishing them on some semi-trusted central key server).  After that, any time one party (say, again, Alice) wants to send a message to another party (say, Bob), she can just combine her private key with Bob's public key to obtain a secret value known only to her and Bob, and then use this secret (possibly after feeding it through a suitable KDF) as the symmetric secret key for an authenticated encryption scheme as described above.

Anyway, for practical use, you don't actually need to implement any of this yourself, since there are plenty of existing implementations of such schemes.  For example, the NaCl library (and its various derivatives, such as libsodium) provides the crypto_secretbox function for symmetric-key authenticated encryption and the crypto_box function for repudiable authenticated public-key encryption.  If you don't particularly need to roll your own encryption scheme, I would encourage you to use those, or some other similar established and well studied implementation.

(One possible reason why you might want to do that is for nonce misuse resistance.  The NaCl functions described above require you to assign each message a unique nonce, and its security can be badly compromised if you ever reuse the same nonce for two distinct messages encrypted with the same secret key.  There are authenticated encryption schemes based on the SIV construction that are much more resistant to such nonce misuse, such as AES-SIV, AES-GCM-SIV or even HS1-SIV, but NaCl crypto_box does not currently support them.  If you wanted, you could reimplement the "hashed Diffie–Hellman" part of crypto_box using crypto_scalarmult and use the resulting key with some SIV-style symmetric encryption scheme, but that requires a lot more effort and care than just using crypto_box as it is.)

Ps. On a slight tangent, note that Diffie–Hellman alone doesn't entirely solve the key distribution problem, since it still relies on the parties being able to share their public keys without anyone tampering with them.  In particular, if Alice and Bob are trying to exchange public keys over a channel controlled by a middle-man Mallory, he can just replace Alice's and Bob's public keys with his own, and thereafter intercept any messages encrypted with those keys, decrypting and re-encrypting each message before passing it on.

(Of course, if Mallory ever stops doing that, Alice and Bob will find themselves unable to communicate until and unless they re-exchange public keys.  But to Alice and Bob, that just looks as if someone just started attacking their communications by intercepting their messages and replacing them with invalid forgeries.  Without some alternative communications channel, there's no way for Alice or Bob to know whether an attack just started or whether one just stopped.  And even if they do somehow figure it out, it may be too late.)

One way to try to solve this problem is to set up some kind of a public key infrastructure where third parties can sign Alice and Bob's public keys in order to vouch for their correctness.  But setting up a reliable PKI is far from a trivial task, since at some point you still need to trust someone.