The non-interactive proof of verifiable computation: Pinocchio I am reading the Pinocchio paper. The paper says, in paragraph "polynomial asymptotics" of section 4.2.1, a worker, in order to include $h(s)$ into the proof, has to interpolate $p(x)$, and then divide it with $t(x)$ to get $h(x)$, then calculate $h(s)$.

As a worker, I would calculate $p(s)$, then $t(s)$, and let $h(s)=p(s)*(t(s))^{-1}$. Suppose this $h(s)$ is good, this approach is much less complicated, compared to the approach described in the paper, which dictates at least $O(n (log(n))^2)$ complexity.

I am wondering why this simpler approach to get $h(s)$ for the worker does not work. Any help is appreciated.

The worker does not know $s, t(s), v_k(s), w_k(s), y_k(s)$, the workers knows only the content of the public evaluation key and the public verification key. That's to say, the worker knows only $g^s, g^{t(s)}, g^{v_k(s)}$ etc.


Can a KEM shared secret be used directly as a symmetric key? As an example, both Classic-McEliece and Kyber KEMs produce 32 byte shared secrets. How convenient since that's exactly the size I need for an AES-256 key!
Is this safe to do? My question can be formalized into these (I believe) equivalent questions about the definition of KEMs (I'm mostly interested in NIST Round 3 PQC KEMs, but more general answers are ok too)

Does an $X$-bit KEM shared secret contain $X$ bits of entropy?
Are the bits of a KEM shared secret guaranteed to be IID?
Can a KEM shared secret be used directly as a symmetric key?

Background to explain how I arrived at this question; not actually part of the question.
I am expecting the answer to be "No, you need to run the SS though a KDF", but I'm looking for citations to back that up. That would align with this answer that @poncho gave about ECDH, which would also be true of DH, but maybe those are not formally KEMs?:

Can a raw ECDH shared secret be used directly for encryption?

The algorithms you mentioned use a secure hash function to derive this convenient 32-byte shared secret, but it is not necessarily true that all KEMs will do so. The answer to your three general questions would thus be all "it depends on the actual algorithm". In general, they use KDFs.
The Kyber KEM submission, for example, uses SHAKE-256:

As a modification in round-2, we decided to derive the final key using SHAKE-256 instead of SHA3-256. This is an advantage for protocols that need keys of more than 256 bits. Instead of first requesting a 256-bit key from Kyber and then expanding it, they can pass an additional key-length parameter to Kyber and obtain a key of the desired length. This feature is not supported by the NIST API, so in our implementations we set the keylength to a fixed length of 32 bytes in api.h.

The McEliece submission uses the same hash function:

3.1 Parameter set kem/mceliece348864
KEM with $m = 12$, $n = 3488$, $t = 64$, $\ell = 256$.
Field polynomial $f(z) = z^{12} + z^3 + 1$.
Hash function: SHAKE256 with 32-byte output.
This parameter set is proposed and implemented in this submission.


What is the NTRU parameter equivalent to security level 112, 128 and 192? I came across this paper which mentions this table, which states that NTRU 347 is equivalent to 112 bit security level

However, in this paper, Choosing parameters for NTRU mentions that NTRU-401 is equivalent to 112 bit security

Thus, I would like to ask what parameter of NTRU is equivalent to 112, 128, 192 bit security level

The answer is not easy. There is an estimator by  John Schanck. You can use this estimator to derive according to your requirements.
For example

NTRU
Core-SVP (tuple Sieving)
Hybrid

443
~93
~89

743
~176
~172

I've omitted the variant of the Core-SVP, for example, the core belongs to the Tuple lattice sieving. They are both used in the Core-SVP and in the Hybrid.


Computational Diffie-Hellman problem over the group of quadratic residues Suppose that $N=pq$ where $p$ and $q$ are safe primes. $\mathbb{QR}_N$ is the group of quadratic residues which is a cyclic group with order $\frac{\phi(N)}{4}$. Let $g$ be the generator of $\mathbb{QR}_N$.

The computational Diffie-Hellman problem is defined as : given $U=g^u\in\mathbb{QR}_N$ and $V=g^v\in\mathbb{QR}_N$ where $u,v$ are chosen uniformly at random from $\mathbb{Z}_{\frac{\phi(N)}{4}}$, compute $CDH(U,V)=g^{uv}$.

Now, if $N$  can be efficiently factored, then computing  $CDH(U,V)=g^{uv}$ is still hard ?

That depends entirely on the size of $p$ and $q$.

Given a factorization of $N = pq$, an attacker can compute $g^u \bmod p$ and $g^v \bmod p$, and then attempt to solve the CDH problem modulo $p$, giving him $g^{uv} \bmod p$.

Then, he can then compute $g^u \bmod q$ and $g^v \bmod q$, and then attempt to solve the CDH problem modulo $q$, giving him $g^{uv} \bmod q$.

Then, he can combine them to form $g^{uv} \bmod pq$.

The only parts that might not be straightforward is the CDH problem modulo $p$ and $q$ -- if one if the two primes is large enough to make this infeasible, then he cannot do that (and conversely, if he cannot solve the CDH problem modulo $p$, he obviously cannot solve it modulo $pq$.


What is a Key Derivation Function? From Wikipedia:

  In cryptography, a key derivation function (or KDF) derives one or more secret keys from a secret value such as a master key or other known information such as a password or passphrase using a pseudo-random function.

Is there a more formal security definition for what they are and what properties they are trying to guarantee, like ind-cpa security for encryption schemes, or collision resistance for hash functions?

This is a summary of the indicated section of Cryptographic Extraction and Key Derivation: The HKDF Scheme from user4982's comment.

Because this is in the context of an academic paper describing a HMAC based KDF, the terminology can be a bit excessive. I have tried to trim it down in this summary.

Definition of a KDF:

A KDF takes four inputs: a key source value, an output length, a salt, and a context variable. The last two are optional. The security and quality of the KDF depends on the properties of the key source value.

Definition of a key source:

A source comprises two values, the key source material and auxiliary knowledge about it, created using an algorithm with sufficient statistical entropy to be considered random. (The auxiliary knowledge can be the distribution from a statistical entropy source, or the non-secret values of a DH key exchange, or any other related, but not secret data about the key source material)

Definition of the security of a KDF:

A KDF is secure if an attacker knowing the auxiliary data and salt value has little chance of deriving the key source material and context variable from repeated attempts at using the KDF with the auxiliary data, salt, and random key source materials and context variables (a.k.a brute forcing the KDF).


Using a SHA512 hash to encrypt data How can I judge the level of security with the following algorithm:

I create a 64 byte hash using SHA512 via some input. I use this hash to iterate over the plaintext, byte by byte, and similarly iterate over the hash byte by byte XORing each byte of the plaintext with a respective byte from the hash like this (in C#):

for (int i = 0; i < data.Length; i++)
{
  if (j == key.Length) j = 0;
  data[i] = (byte)(data[i] ^ key[j++]);

}

where key is a byte array containing the hash. Issues of how the code acquires the key aside, is this secure? (Apologies if I am not framing this with the proper terminology). I am not using a salt. The input which is used to create the hash can be of any length (up to being reasonable; i.e., not a huge block of text).

No it's not. It is really bad.

Basically, this is a stream cipher, where your keystream is $key | key| key|key....$. This is really bad, similar to the level of "using OTP twice". As If you take a block of size keylength, and XOR two such blocks, then you get the XOR of the plaintexts. Depending on the nature of the plaintext, this can be really easy to guess.

If you want an easy encryption scheme, like XOR the plaintext with a keystream, use a stream cipher or a block cipher in OFB mode of operation. If you want a construction with SHA512, that is also possible, see e.g.

Is it feasible to build a stream cipher from a cryptographic hash function?
Can I use HMAC-SHA1 in counter mode to make a stream cipher?

However, since hash functions have different security properties than stream ciphers, it might be better to use a construction which is actually intended to be used this way. In a similar context, Bruce Schneier wrote (about ciphers based on hash functions):

  While these constructions can be secure, they depend on the choice of the underlying one-way hash function. A good one-way hash function does not necessarily make a secure encryption algorithm. Cryptographic requirements are different. For example, linear cryptanalysis is not a viable attack against one-way hash functions, but works against encryption algorithms. A one-way hash function such as SHA could have linear characteristics which, while not affecting its security as a one-way hash function, could make it insecure in an encryption algorithm such as MDC. I know of no cryptanalytic analysis of particular one-way hash functions as block ciphers; wait for such analysis before you trust any of them.


How can I edit or build an app to encrypt data, and build a decryption key? I'm curious how I could make an app or add a function to an app that will encrypt the data, then a key that will decrypt it. Specifically, I am wanting to be able to add a "button" or setting on the camera app on my phone that will encrypt the image (I imagine encryption via altering the pixels of the image for cool effects, but that may not be logically efficient), then a setting on my gallery that will do the reverse and decrypt it. My main reasoning is to be able to do really cool transformations to images via algorithms (cause that kind of thing is really fun for me), but as a bonus I'll be able to keep my images more secure. I don't know if this is the place to ask, but I'm interested in cryptography (though I'm familiar with the concept, new to the practice), and I thought here may be good. Thank you in advance for any help you can give.

For added details, I'm looking to do this on an iPhone 7+ and galaxy Note 5 so the encrypt/decrypt can work on both, together or separately. This part isn't entirely necessary, but pertains to the specific case I have.

Generally speaking, it is not up to you to design and implement your own encryption algorithm. The time period where you could do that and maybe get away with it has long since past. Nowadays, we have standardized cipher algorithms such as AES, which are efficient on modern CPUs and believed to be secure against all currently known attacks.

So basically, your question is/should be, "how do I select an algorithm and generate a key for using it?".

My answer is, unless you can cite a specific reason to not use AES, then AES is probably what you should be using. So now that the algorithm has been selected, you need to find an implementation. This is a language dependent issue and you will have to find an appropriate library for the language your program will be in.

Do not just implement AES yourself (for production use; it's fine for fun). There are some "extra" implementation details that can influence the security of the implementation, and these things may be non obvious to those who don't know what to look for.

Key generation is simple: to generate a key, use the key generation function provided by the library that implements AES, or use the OS urandom/CryptGenRandom functions (for UNIX/Windows). A good library should disallow you from using inappropriate key sizes; For AES, 128, 196, and 256 bits are appropriate key lengths.

If you're on multiple platforms, you may want to find a cross platform crypto library to ease the implementation. An easier implementation can lead to less bugs, which can influence security.

Regarding "I imagine encryption via altering the pixels of the image for cool effects, but that may not be logically efficient" - you're going to want to forget about this idea. After successful encryption, any file data will look like noise/scrambled data - if it does not look this way, then you have a problem.

Lastly, unrelated to the crypto: adding a button to the native camera apps on your phone may be more complicated then writing say, a python script to encrypt the contents of the folder where the images are saved. The latter would not require modification of multiple, different, already compiled apps.

Alternative Ciphers

There do exist alternative designs that are both efficient and believed to be secure. If you really do want a different algorithm, this article might be interesting to you. Assuming the alternatives that are suggested are equally secure for practical use, you might implement each and measure which is most efficient for your specific application and platform.


In what cases might PRESENT be implemented as encryption-only? In the paper, under section 4.1 Goals and environment of use we read:

In applications that demand the most efficient use of space, the block cipher will often only be implemented as encryption-only.

I presume this is NOT the same as one-way encryption (perhaps I should say hash?) as used for passwords.

So in what cases might we need only encryption but not decryption? It seems strange we would encrypt something that does not need decrypting at some point.

Furthermore, the quote above continues with ...

In this way it can be used in challenge-response authentication protocols and, with some careful management, it could be used for both encryption and decryption ...

This just added to my confusion.

It seems PRESENT can decrypt a ciphertext by running it in reverse. So why the need for some careful management for PRESENT to be used for both encryption and decryption?

So in what cases might we need only encryption but not decryption? It seems strange we would encrypt something that does not need decrypting at some point.

For example, the CTR mode uses only Encryption, and CFB, OFB.

  It seems PRESENT can decrypt a ciphertext by running it in reverse. So why the need for some careful management for PRESENT to be used for both encryption and decryption?

The correct sentence is

  In this way it can be used within challenge-response authentication protocols and, with some careful state management.

All about the hardware implementation of PRESENT.

This paragraph from the article;

  Encryption and decryption with present have roughly the same physical requirements. Opting to support both encryption and decryption will result in a lightweight block cipher implementation that is still smaller than an encryption-only AES. Opting to implement an encryption only present will give an ultra-lightweight solution. The encryption subkeys can be computed on-the-fly.

So they compare their encryption and decryption supported hardware implementation to encryption-only AES claiming that PRESENT has smaller requirements.


Dynamic accumulator with only non-membership witness Goal: Construct a dynamic accumulator which can add elements and provide non-membership witnesses. I wanted to know if my construction is correct.

Consider a group $Z_p$ where $p$ is prime number. Consider the set $S=\{c_1, c_2,\cdots, c_m\}$ where $c_i\in Primes(Z_p)$. Consider the following accumulator:
$$
A = \left(\prod_{c_i \in S} c_i\right) \text{mod } p.
$$

Addition: To add a new element $c \in Primes(Z_p)$,
$$
A \longleftarrow \left(A\times c\right) \text{mod } p.
$$

Non-Memerbship witness $(x,y)$: To show $c \not\in S$, we use the fact that $c$ is co-prime with all the elements in $S$. We use Bezout coefficient $(x,y)$ to show that
$$
cx+Ay=1 \text{ mod } p.
$$

Security: $\forall c\in S$, there exists no algorithm $\mathcal{A}$ such that

$$
(x,y) \leftarrow \mathcal{A}(c,S),\; cx+Ay=1 \text{ mod } p.
$$

This is not a correct dynamic accumulator scheme.

Your scheme assumes that the following holds: if $a,b$ are primes and  $0< a,b < p$, then $$(a,b)=1 \implies (ab\mod p,a)\neq1. $$ If this is true, then your scheme is correct, however this is not the case.

Toy example: $p=11,a=5,b=7$. Since $ab \mod 11=35 \mod 11=2,$ therefore $A=2$. Now, it is clear that security does not hold, since one could prove false non-membership statements. The reason for that is: $(a,A)=1=(b,A)$. Meaning one can prove that $a$ and $b$ are not accumulated however they were indeed added to the accumulator. For instance $(2,1)$ is a a non-membership witness for $5$, when $A=2$, since $5*2+2*1 \mod 11 = 1$.


CBC-R when IV unknown I've read the CBC-R description from Rizzo & Duong but am having trouble understanding the sequence of steps that would be taken when the IV is unknown and is not included with the ciphertext.

Suppose I want to send a two-block ciphertext such that block 1 decrypts to garbage and block 2 decrypts to my desired plaintext. Would the following work? If so, why not?

Pick a desired plaintext, call this P
Create a random block, call this R1
Send the random block to a padding oracle decryption routine, call the result D1
XOR D1 with P, and make this block 1
Use R1 as block 2

Since the IV is unknown the first block becomes garbage, but the during decryption the next block should decrypt R1, yielding D1, then XOR it with my block 1 to get back to my desired plaintext. Am I looking at this correctly?

Side question: I assume plaintext (step 1) should include any padding sequence that the server expects, e.g. PKCS#7. Or should this be somehow applied during step 5?

Yes, you are correct. For padding - there's no way to fix it at step 5, you need to make correct padding at step 1.


HMAC with public-private key I need a way to protect my data.

More then encryption I need a way to guarantee integrity and authenticity but I also need to be the only one that can understand integrity and authenticity.

I found HMAC to be a good way for integrity and authenticity but it is based on a single key that I should share within my software and I don't like it.

Is there a something like HMAC but with public-private key so that I can share only one key?

Consider the following system involving a message authentication code like HMAC-SHA256:

Alice generates a key and shares it with Bob, and Bob alone.
Alice authenticates a message with the key.
Bob acts on the message only if it can be verified with the key.

Of course, Alice can verify messages too, and Bob can forge messages too.  Indeed, anyone who has the key can verify or forge messages: the key necessarily grants the power to do both.  Consequently, Alice can't present a cryptographic proof to a third party that a message came from Bob, because Alice could have forged the message; and vice versa.  Thus this system has ‘deniability’, or lacks third-party verifiability.

Consider the following system involving a digital signature scheme like RSASSA-PSS or Ed25519:

Alice generates a key pair and shares the public key with Bob, and Bob alone.
Alice signs a message with her private key.
Bob acts on the message only if it can be verified with Alice's public key.

Only Alice can sign messages; anyone with the public key can verify them but not sign them.  You asked that only Bob be able to verify messages.  Can the public key be kept secret so that Bob alone can verify them?

The standard for signature security is existential unforgeability under adaptive chosen-message attack, or EUF-CMA, which means that an adversary who can query an oracle for the signature of any message of their choice nevertheless can't forge a signature for any message they didn't query the oracle for.  Nothing prevents an EUF-CMA signature scheme from simply including a copy of the public key in the signature itself, so that won't keep Alice's public key secret.

There's a nonstandard property of some public-key cryptosystems called key privacy—formalized for public-key encryption schemes, it means that given two public keys and a ciphertext the adversary can't tell which public key the ciphertext corresponds to.  Of course, this doesn't carry over naturally to signatures because if you had the public keys and message you could just verify the signature.

There's a related notion of anonymous signature schemes, where an adversary presented with two public keys and a signature but not the message can't tell which public key made it, which typical RSA-based signature schemes fail by the German tank problem to the chagrin of the Australian Department of Human Services who hoped it provided privacy it didn't.  Schnorr-type signature schemes in a standard group like Ed25519 do tend to provide anonymity in this sense.

There's another related notion of key indistinguishability (paywall-free) where an adversary presented with two public keys and a signing oracle can't tell whether the public keys have the same private key, but this is in an exotic context where a set of many users can sign messages with their respective private keys, but only one party can distinguish signatures made by the users.

Which of these do you want?  I don't know—it's not clear to me what you're trying to accomplish at a higher level, so it's hard to give more specific advice.


Does AES 256 really make sense in hybrid crypto systems when the PKI is the bottleneck? AES 256 is used widely in hybrid crypto systems (e.g. SSL/TLS). According to keylength.com a 2048 bit public key corresponds to 112 bits of security.

Does it make sense to use AES 256 in this context?
If yes, how it improves security in comparison with AES 128?

It's possible to use much larger key sizes than 2048 bit RSA for TLS. So the argument that 256 bit RSA provides much more security than 2048 bits RSA may not apply.

If used with a 2048 bit RSA key then using AES-256 may not make too much sense. But don't forget that AES-256 will be used to encrypt large amounts of plaintext, and that attacks on AES will be quite different from attacks on RSA. Furthermore, AES-256 is not that much slower than AES-128 - and certainly not twice as slow as you may expect.

In general using AES-128 or AES-256 won't make much of a difference. Using EDH for perfect forward secrecy or the application of strong(er) authentication will arguably have more of an impact on security.


what is the difference of Pretty Good Privacy and Gnu Privacy Guard i want to know about the difference. of this two. because as far as i know  many cryptocurrency users.  use this for  more secure  transactions specially when the amount is huge.. to prevent identity while having a discussion about the transaction.

Both PGP and GPG are software implementations of the OpenPGP protocol. Typically when people say "PGP" they refer to the OpenPGP protocol.

OpenPGP itself specifies the formats for messages and keys. Both the PGP software and GPG are implementations which produce OpenPGP messages and keys.


Is it possible to derive the recipient's public key from libsodium's crypto_box? Libsodium has "crypto_box_seal" which according to the documentation is used to "anonymously send messages to a recipient given its public key.", which hides the sender.

But Is it possible for Eve to know/confirm the exact public key of the recipient from a message made from crypto_box/crypto_box_seal, assuming that Eve already has a list of public keys that it could be?

You are given $E_{H([ab]P)}(n, m)$ and $[b]P$, where

$E$ is an authenticated encryption function,
$H$ is a hash function,
$a$ is the recipient's secret key and $[a]P$ is the recipient's public key,
$b$ is the sender's secret key and $[b]P$ is the sender's public key,
$P$ is the standard base point on the standard curve,
$n$ is a nonce, and
$m$ is a message.

Your task, as stated, is to find which of $[a_1]P, [a_2]P, \ldots, [a_k]P$ is $[a]P$.  Let's assume you already know $n$ and $m$; if you don't—if your knowledge about them has total min-entropy $e$ bits—then you'll probably have to iterate this process $2^e$ times.  Let's simplify it a little bit and say you only want to tell whether $[a]P = [a_1]P$ or not; you can repeat it $k$ times to find which key among the choices, if any.

Suppose you have a random algorithm $A(Q, R, c)$ that returns 1 with high probability for $A([a]P, [b]P, E_{H([ab]P)}(n, m))$ and returns 0 with high probability for any other inputs.  Then I can define an algorithm $A'(Q, R, S) = A(Q, R, E_{H(S)}(n, m))$ that serves as a distinguisher for the decisional Diffie–Hellman problem in the group generated by $P$, because it returns 1 for $A'([a]P, [b]P, [ab]P)$ with high probability and returns 0 for any other inputs with high probability.

So the answer is: No, Eve cannot even confirm the recipient just by examining the ciphertext.  This property is sometimes called key privacy or anonymity.  (The formulation in the paper is slightly different, but I think it is equivalent; if not, adapting the proof to the formulation in the paper is left as an exercise for the reader, since most DH-based schemes naturally exhibit key privacy, unlike RSA-based schemes.)


What NIST protocol was allegedly backdoored by NSA in 2006? From a recent NY Times article:

  Cryptographers have long suspected that the agency planted
  vulnerabilities in a standard adopted in 2006 by the National
  Institute of Standards and Technology and later by the International
  Organization for Standardization, which has 163 countries as members.

  Classified N.S.A. memos appear to confirm that the fatal weakness,
  discovered by two Microsoft cryptographers in 2007, was engineered by
  the agency. The N.S.A. wrote the standard and aggressively pushed it
  on the international group, privately calling the effort “a challenge
  in finesse.”

  “Eventually, N.S.A. became the sole editor,” the memo says.

What protocol was adopted by NIST in 2006, then subsequently broken by MS employees in 2007?

The standard in question was the Dual Elliptic Curve Deterministic Random Bit Generator (Dual_EC_DRBG), standardized in NIST Special Publication 800-90. In this case, it was not a protocol, but instead a random number generator. It wasn't exactly "broken"; instead, it was proven that there existed a "master key", if you will, that would allow someone to predict the stream of "random" bits. (That is, the PRNG isn't really random if you happen to know the proper numbers.)

Despite that the cryptography community has been aware of this for some time now, this discovery has resurfaced in the recent media firestorm surrounding the Snowden leaks. Note that we aren't really sure if the NSA really constructed the backdoor, or if they have the backdoor "key", although recent events seem to suggest that they do.

You can find some more information at these links:

Who uses Dual_EC_DRBG?, a recent question on this site
The Strange Story of Dual_EC_DRBG, a blog post by Schneier on the matter (from 2007, mind you!)

and of course, the citations at the bottom of the above-linked Wikipedia article are always nice to look at.


How did LinkedIn "salt" all their passwords? First, just to make sure I understand "salting" correctly:
You randomly generate a string to append to the password before hashing it, so as to increase its length and make precomputed tables much less useful in cracking them.

Assuming my understanding is correct, then I'm having trouble how LinkedIn salted their passwords:

  One of our major initiatives was the transition from a password database system that hashed passwords [...] to a system that both hashed and salted the passwords [...] That transition was completed prior to news of the password theft breaking on Wednesday.

Doesn't salting require you to have the plaintext password? How can you salt a hashed password?

Basically, salting a password means that you compute a hash value which depends on the password and on a salt (a non-secret random value of sufficient length, e.g, 64 bits). Remember that salting a password allows to better resist attacks such as dictionnary attacks or time-memory tradeoffs (e.g., rainbow tables), i.e., attacks involving an offline pre-computation step, but not brute-force attacks.

If we denote by $H(.)$ the hash function ($\mathrm{SHA1}$ for LinkedIn), by $p$ the password and by $s$ a salt value, LinkedIn might find themselves in the situation where they have a database of values $h_i = H(p_i)$, for $1 \leq i \leq \ell$, where $\ell$ denotes the number of accounts. Thus, one could imagine that they compute $h^\prime_i = H(s_i||h_i) = H(s_i||H(p_i))$ ($||$ denoting a concatenation) and that they store the pairs $(s_i, h^\prime_i)$ in the database. Note that they don't need to know the passwords to perform this operation.

Another possibility would consist in resetting all the accounts, force the users to setup a new password, and hash them according to a better scheme, but this a bit less customer-friendly...


Secret Sharing 1 Required Devise a scheme so that a message M can be shared among X, Y and Z in such a say that the only way of recovering the message is when X is present with either Y or Z. When X isn't present or each is alone, they will not be able to recover the shared secret.

Additionally, generalize the above to devise a scheme so that a M can be shared among 5 entities such that the only way of recovering the secret is when either X and Y are both present or when C, D, E are all present together.

I have no idea how to create a hierarchy such as what is being proposed. Any ideas?

This is actually a fairly trivial case of secret sharing:

In the first case, we select a random value $R$, we give $X$ the value $R \oplus M$, and we give both Y and Z the value $R$.  Obviously, $X$ alone, nor $Y$ and $Z$ together cannot reconstruct $R$.

In the second case, we select random values $R_1$, $R_2$ and $R_3$, we give:

$R_1 \oplus M$ to $X$
$R_1$ to $Y$
$R_2 \oplus R_3 \oplus M$ to $C$
$R_2$ to $D$
$R_3$ to $E$

Shamir Secret Sharing is a neat trick; however sometimes problems can be solved by simpler methods.


What's the difference between a hash chain, transaction chain and a blockchain? Can anyone explain to me what the difference is between a hash chain, transaction chain and a blockchain?

A hash chain is a sequence of hashes of blocks. Each block consists of the hash of the previous block, and (optionally) some data. These can be seen a special case of a Merkle Tree, that is one with only a single branch.
A transaction chain is a hash chain with the data being lists of transactions, instead of arbitrary data.
A blockchain is a Merkle Tree with a consensus algorithm to determine which branch is the "correct" one. Typically other branches get discarded, but not always. E.G. git uses a Merkle Tree internally to verify the directed acyclic graph of commits, with a specially named branch (usually master or main) maintained by some user as the cannonical chain.
Cryptographically they're all identical, unless the consensus algorithm of a blockchain involves cryptography. Not all of them do, eg permissioned blockchains simply require authorization by the chain administrator to add a block.


Why aren't Diffie Hellman public keys used for authentication? So I have been reading about Diffie Hellman and specifically the MitM attacks that it is vulnerable to.

I am aware that these are solved currently in ssl for instance by using rsa signatures to authenticate dh public keys (as in the $g^a$ mod n bit) to prevent a middle man from compromising the connection.

I also am aware that the public key of the server that is used in the RSA authentication is provided by a CA which is how the browser knows it is valid.

I am also aware that DH as used in ssl is ECDH, but regardless I think my question still applies and I would be interested in an answer in reference to either ECDH or just normal DH.

What I don't understand however is why the certification authority (CA) can't simply give out the servers $g^a$ mod n (public DH key) instead of their public RSA key, as to avoid having to use RSA.

I know that one reason this is not used is because of forward secrecy which can only be gained with session based DH keys, but why has this never been implemented (from what I can tell, it hasn't) even though non forward secret RSA used to be used for this purpose?

Would having a persistent DH public key introduce a mathematical vulnerability or is there another reason why this hasn't been done?

Thanks you

This is called static DH. It can be done directly by using OpenSSL, but not many clients will support it. There is no mathematical vulnerability to using DH in this way, but it never really took off. Infrastructure for RSA signatures were already in place, so there was no need to switch to another algorithm.


Hash algorithm for converting n-bit number into another n-bit number So I'm new to this area of Stack Exchange, and to cryptography in general, but I just wanted to ask this question here to see if I could get any advice. I don't understand a lot of the technical jargon used around here, so go easy on me.

I'm programming something where I need to use a hash algorithm to convert a 96-bit number into another 96-bit number. No, it's not for passwords, and it doesn't really need to be super secure. Actually, it's just for generating a unique UUID for each level a player creates in a game. The original 96-bit number contains the user's MAC address, the timestamp when the level was created, and a pseudorandomly generated number. To me it seems a bit weird to have a level's UUID traceable back to the timestamp and the creator's MAC address (and possibly a minor security risk for the latter, from what I get at), so I decided on using a hash function to obscure that information.

However, most hash functions take an input of indefinite length and return an output of predetermined length, which in most cases is not 96 bits. I need a hash function where I can specify the length of the output. Preferably, the function would require an input of that same length. Why is that? Well, however rare they may be, the possibility of hash collisions is a given for functions that take an input of indefinite length. If my function were to take an input with a length of 96 bits and return an output with a length of 96 bits, a one-to-one mapping could be created between the inputs and outputs. Again, I don't know a huge deal about cryptography, so I have no idea if creating a function like this that is completely immune to hash collisions is even possible, but I would like to try to avoid them as much as I can because of my requirement for uniqueness.

Thanks in advance for the help.

What you're asking for is basically a 96-bit block cipher (pseudorandom permutation) that does not have an easily computable inverse.  On the contrary, your permutation should instead be resistant to preimage attacks.

Alas, I'm not familiar with any such cryptographic primitive, or any construction that would allow one to be constructed from standard components.  (If anybody does know such a construction, I'd be quite interested to learn about it.)

In practice, I'd recommend just using a standard hash function (like SHA-256) and truncating its output to 96 bits.  In practice, you're not likely to see any collisions before the number of hashed inputs starts to approach the "birthday bound", i.e. the square root of the number of possible outputs, in your case $\sqrt{2^{96}} = 2^{48}$.  It seems very unlikely that your game would ever end up with anywhere near that many players, considering that there are less than $2^{33}$ people living on Earth.

If you want even more certainty than that, just don't truncate the hash.


Why should one model an entropy source in order to build a TRNG? Some  assert that a theoretical model of the unconditioned source must be created when building any TRNG. It's believed to be a fundamental requirement.  So a few related questions arise:-

What is a "model"? For example, are we talking a simple histogram of the raw output distribution, or something like $ \sigma^2_{quantum} = \frac{\gamma}{\gamma + 1} \langle V(t)^2 \rangle $ thus $ \sim H_{Shannon}  $ in laser phase interference?
More generally, do they mean   a posteriori (empirical summary statistics, probability density function, $V_{RMS}$ , $\delta^2_{signal}$)  , or a priori (predictive) modelling like the $ V \sim -C_1(1 - e^{-\frac{t - t_a}{C_2}})  $ capacitive charge curve that governs the shape of Zener diode breakdown and the earlier laser equation? The major difference being that an empirical/a posteriori model is agnostic to any physics. Yet underlying physical processes are often mentioned.
Is there any original theoretical work justifying this modelling requirement? I'm asking about any works underpinning or justifying what one might read in a NIST/BSI AIS document.
What to do if the empirically measured entropy rate does not agree with a priori (predictive) modelling? Say a very significant error. A measured noise signal can easily increase 100% between two generic component types from different manufacturers (eg. BZX85C24 Zener diode).

Update:

There is now a hot network question - Is a model fitted to data or is data fitted to a model?
 Currently answers are leaning towards the empirical data taking priority over the theory. So you'd start with the oscilloscope and work upstream to the physicsing[sic]. As a philosophical empiricist, this seems more intuitive to me but there does seem to be a portion of members here that give precedence to   math over  measurement. It's a Plato v Aristotle question and I'm trying to be  open minded on this one.

Why use a model?
The utility of a scientific model is the ability to make predictions. An example of a simple model is one describing the motion of projectiles based on Newton's laws of motion and gravity.
You could use two strategies on a battlefield to make a cannonball land where you want it to.
You could point the cannon in the general direction of a castle and fire. If the projectile flies over the target you try again, aiming lower. If it still overshoots the castle you aim a little lower again. (Or if it falls short aim a little higher.) You try and make adjustments until you get the result you want.
Alternatively you could determine the distance between you and the target, how much higher the target is than the cannon, the initial speed of the cannonball. You model the cannonball as a point mass. You ignore the effect of drag. (It might be fine depending on how dense the cannonball is, how thin the atmosphere, how far it needs to travel.) In such an environment, a consequence of Newton's laws is that the relative position of a projectile can be determined from its initial velocity. You use the numbers and formulas to determine where to aim. Not your eyes.
The first method does not use a formal model. It is not preferable because it will waste resources and because any mistakes will put you in danger. The second method (potentially) enables you to hit your target on the first try.
Science is full of models. You want to find one that is sufficiently accurate in order to have confidence that things will work out right. You want a simple enough model for it to be practical. The Newtonian cannonball model does not describe exactly how the real world works. It simplifies things while remaining useful. For some applications you need something more complex. All models are like that.

Example
If you want to build an RNG that uses radioactive decay as it's source of unpredictability, then first you model the process of decay using the half life model. It lets you treat the physical phenomenon as a clean mathematical abstraction.
Next we figure out how much of the material you have and what fraction of the decay events we can detect. Then we use our knowledge that the half life decay model can be described as a Poisson process to create a statistical model.
The model will tell use how likely we are to detect an event in any given time slice of a certain length. If the half life is long enough and we have enough material this probability should remain accurate for a long time.
Now we have a Bernoulli process. The samples are binary (detection or non-detection), independent, and will have effectively constant probabilities.
We can look at the probabilities of the two possible outcomes. From that we can easily determine the min entropy. That number can tell us how many samples we need to take to ensure we have sufficient entropy. (And therefore also a lower limit on how long we need to wait to generate a key.)
Multiply the number of samples you need by 2 or 2000 just be conservative and paranoid. Now you know how many samples to process through a cryptographic hash before you can use the output to generate a key.
We could have stopped once we knew we could model detection as a Poisson process and not calculate probabilities. Two non-overlapping time slices are statistically independent in a Poisson process model. We could use von-Neumann's debiasing algorithm for that reason without needing to know the detection probability because (assuming the hardware is working correctly) the kind of samples we have are independent and identically distributed.
But calculating the probability gives us the opportunity to test if things are working as intended. (Use a better model to build a safer HWRNG.) If the CPU sees detections far more frequently than expected, then maybe someone is using another radioactive source to try to bias our RNG. If we see too few detections or too many identical consecutive samples then maybe a circuit has been damaged.
Note: I'm confident that I don't know how every real world radioactivity-based HWRNGs work with 100% accuracy. There could be different designs with different design justifications. Physics is not something I plan on studying further. And I'm definitely not going to bother with reverse engineering proprietary things.

Other questions
Use a histogram?
No. Don't use a histogram. Use a probability mass function.
Creating a histogram requires sampling. A histogram can only be used to estimate probabilities. If you don't know what to look for then you definitely can't tell the difference between a working system and a broken one.
You also don't want to calibrate the system based only on empirical results. It's important to know how likely components are to fail, to know whether or not aging of components will render the calibration invalid.
Calibrating to lab conditions is dangerous because the characteristics of the entropy source you use might be different at different temperatures, in different environments, as the components age, when exposed to different strengths and frequencies of electromagnetic noise, on different power supplies.
It's a better idea to use a design based on knowledge of a physical process that will be robust enough to still be unpredictable (and predictably unpredictable) in the future under different conditions.
Theoretical necessity?
Theories for why you don't need theories? Maybe. I don't know how many theoretical researchers have an interest in that niche.
Results don't match theory?
You're model is wrong or your hardware is broken. If a device isn't working the way it's expected to and there are any safety implications if it's broken, then why not fix it or use a different device? If your model is wrong and your hardware is fine, then why not find a model that does explain things?
50% error?
I don't know what metric you're using. That sounds really high.


What if OT breaks in Yao's garbled circuit? Two semi-honest parties are computing F with Yao's garbled circuit. Sender garbles it with his inputs baked in then sends it to the receiver. At this point the receiver must use OT to get his keys. What happens if OT breaks and the receiver gets both keys for every wire? It's not clear to me that this would break the sender's input privacy.

The problem is because sender has provided the receiver with a garbled circuit in which the sender's inputs are hard coded (or has provided keys for those inputs, which is morally the same).  If the receiver has both keys for each input wire then it is trivial to narrow down the possible values of the sender's input.

Consider a concrete example, the millioniar's problem.  In this problem the sender constructs a circuit that returns $1$ if the resulting value is less than or equal to the sender's wealth.  If the receiver has the circuit and all input keys then it effectively has a function $f : Z_n \rightarrow Z_2$.  Through trial and error we can find the sender's wealth, $X \in Z_n$ where $f(X) = 1 \wedge f(X+1) = 0$.


How to create a private key using $n,e,d,p,q$ where $n$ is prime Someone has incorrectly created a public/private key pair where $N$ (modulus) is a prime number.

This makes $p$ and $q$ trivial as they they are $n$ and $1$.

$d$ is solved from
$d \cdot e =  \bmod (p-1)(q-1)$ which becomes $d \cdot e =  \bmod (n-1)$

I want to create the private key knowing this information but no PEM generators I've found correctly handle $p$ or $q$ being $1$ because when you need to find  $e_1$ or $e_2$ you are looking for $d \bmod (p-1)$ and $(p-1)$ [or $q-1$] would be zero and it crashes.

I've tried python's RSA.construct and attempted to make a asn1.cnf but I am unable to calculated $e_1/e_2$.

I am confident it can be cracked though because RSA decrypt is just ciphertext to the $d$-power, $\bmod n$.

You already stated the answer yourself: You know $N$ (which is prime by your assumption) and from the public key $e$ you can compute $d = e^{-1} \bmod N-1$, e.g. using the EEA.

With this $d$ you can then decrypt any ciphertext $c$ into the corresponding $m = c^d \bmod N$.


AES 128 GCM - dynamic key with static IV/nonce I'm working on a project to upgrade an existing system that currently uses RC4 to encrypt a payload with a random session key. The session key is then encrypted with asymmetric public key encryption (RSA PKCS#1 OAEP). The encrypted pair are then transmitted over insecure channels as a token.

I'm looking to replace the RC4 part with AES-128-GCM. This is an interim solution on the way to using a standardised authenticated public key message exchange framework, such as OpenPGP or JOSE JWE.

To reduce the amount of work required to implement AES-128-GCM by keeping the message syntax the same, I was thinking of using a static IV/nonce shared by sender and recipient. As the session key is unique, I understand that this is as secure as using a random IV with a static key.

Is this an acceptable solution?

Yes.  You can even use the nonce 0, and skip sharing state between the sender and receiver.  While you're at it, consider using AES-256-GCM instead of AES-128-GCM to limit the danger of multi-target attacks.

And stop there; don't waste your time with the painfully archaic OpenPGP or hopelessly dwimmy JOSE.  If you really want to switch to an existing library, consider instead using NaCl/libsodium crypto_box with a random nonce or libsodium crypto_box_seal (which has no nonce, and, as you describe, generates a session key independently at random for each message).


Key Reuse in this simple cipher Consider the following very simple cipher, where, to send length $n$ bit-strings, we randomly correspond the numbers $1, 2, 3, ..., N$ with $n$ bits, so the key is the correspondence between each integer and the bit value it maps to.  Then, to share a bit-string, Alice will send Bob a permutation of the integers $1, 2, ..., N$.

Obviously this cipher is not good for use, but I am wondering the following: am I correct in assuming that so long as the adversary does not obtain any plaintext/ciphertext pairs, Alice and Bob can share multiple messages with the same key, as each new message, to the adversary, is just a permutation of the numbers $1, 2, ..., N$?

so long as the adversary does not obtain any plaintext/ciphertext pairs, Alice and Bob can share multiple messages with the same key

Even if Alice and Bob do not explicitly disclose plaintext/ciphertext pairs, if they care for confidentiality, they must not use this cipher, except maybe for essentially random plaintext and when leaking the Hamming weight of plaintext is no issue (e.g in re-encryption).

Problem is, the more ciphertext, the easier it is to reconstruct all or part of the permutation given some model of plaintext redundancy. For example, if the plaintext is known to be ASCII restricted to uppercase and space, then groups of 7 bits where one is rarely 1 and the others 6 are always 0 when that occurs must belong to the same character, and the rare 1 is the bit set in a space, coded 00100000 in binary (while letters are 010xxxxx). The bit among the remaining 6 that is 1 in all letters is identified by this characteristic. Then frequency analysis reveals the mapping of the remaining 5 bits, and the corresponding letters. Then all that remains from the cipher is a fixed substitution of symbols.

Even with a single block of $n$ bits, if we know that the plaintext is restricted to a small set (e.g. names as written on the class roll), the Hamming weight might allow decryption, and will likely narrow the possible names.


How does reusing IV for OFB mode breaks the scheme Consider a Plaintext P1 and Ciphertext P2, which is known to the attacker. If the attacker knows that the IV used in encrypting P1 in OFB mode is the same used to encrypt another plaintext P2, how can he find out the content of P2 given the ciphertext C2?

Will the attacker have greater limitation if it is encrypted in CFB mode instead?

OFB converts a block cipher to a stream cipher (As does CTR mode). The plain text or any derivitive from it never enters the block cipher. The key stream is unrelated to what is being encrypted. The final ciphertext is just a xor of the plain text with the key stream and the key stream depends only on secret key and IV. reuse both and you get the same key stream. It is the same as reusing a one time pad. It's bad even without knowing a cipher text plain text pair. If you do, it becomes trivial to decrypt any message reusing the same key+IV.


Why are digital signatures used when performing DH? Suppose the server has a public key which everyone knows is associated with it, maybe it's hardcoded into the browser or signed by some CA.

At no point do you need the server to sign anything with it, the client generates an ephemeral key pair, performs DH with the server's public key and sends his ephemeral public key followed by a symmetrically encrypted message.

Only the server and client now have a shared secret. The client can reject any reply that does not contain something encrypted with the symmetric key.

If forward secrecy is required the server's ephemeral key can be contained inside the encrypted message when it replies. So why do all the schemes use digital signatures in key exchange?

tldr: If you are able to verify a signature you have a public key to work with, if you have that then why not just do DH with it?

In principle, if the server has a long-term secret exponent $s$, and a long-term public point $S = g^s$ that the client is willing to believe, then that's enough for the client to send a confidential authenticated message to the server: client picks $c$ at random, computes $C = g^s$, computes $k = H(S^c) = H(g^{sc})$, and uses $k$ as the key for symmetric authenticated encryption.

Unlike a signature, there's no third-party verifiability; anyone who can verify the conversation's authenticators can also forge them.  If you want fast key erasure, then you can use this authenticated channel to perform an ephemeral Diffie–Hellman key agreement, as, e.g., the Signal protocol (technical documentation) does.

Why didn't we do this in, e.g., SSH and TLS?
Mainly for hysterical raisins, I expect.  The use of signatures in TLS goes back to the original SSL, where I'd guess it was derived from the use of signatures in x.400 email with x.509 certificates.

For a certificate chain, you need a signature because you need third-party verifiability, and when you already have an authentication hammer, why bother devising another public-key authentication mechanism?  Symmetric authenticators, i.e. MACs, as needed by a public-key authenticator using DH, were not really popular until the mid-nineties when HMAC was developed, even though the concept was first published in 1974.

Why don't we do this now in, e.g., SSH and TLS, using the public keys in certificates that are already deployed?
Many of them are RSA keys that are fit only for signature or (nonephemeral) key agreement, as in RSA key agreement, not for ephemeral Diffie–Hellman key agreement.*  There technically are standards for x.509 certificates for static Diffie–Hellman public keys, but these are seldom used.

Why don't we use this in any protocols?
Well, we do.  Public-key authentication without nonrepudiation didn't become popular until OTR in 2004, though proposals for it to replace email signatures date back to 2000.  The dnscurve protocol was designed around fitting a server's long-term X25519 public key in a tagged DNS label so that you can compatibly fit it into a standard NS record.  The Signal protocol uses long-term DH keys for authentication extensively.  The Noise protocol framework doesn't use signatures at all at the moment; all authentication is via long-term DH keys.

Why don't we retroactively use it for protocols that already have Ed25519 keys deployed for signatures?
We could, e.g. using XEdDSA, but someone would need to implement it to make it happen.  I can't speak for all protocols out there!  Will you send the patch to OpenSSH to implement public-key authenticators using XEdDSA for deployed X25519 keys, and argue on the mailing list to justify the additional complexity, when signatures already work?  When you design a new protocol, will you use long-term DH keys for authenticators instead of signatures?

Note, of course, that merely using long-term DH keys for authentication doesn't allow key erasure because the keys are, well, long-term.  So for fast key erasure, you still have to compose it with ephemeral DH keys, as I summarized in a recent post on an idealization of how WhatsApp works.

* Here ephemeral means that the keys can be erased after a session and all its resumption tokens have been erased, so compromise of the server's long-term identity key doesn't enable retroactive decryption of past sessions.  This property is sometimes called forward secrecy, a term that glibly obscures when the erasure happens, which is particularly important to take care of with TLS resumption tokens.


Is it secure to encrypt random key with block cipher in ECB mode? If we have a random key $K$ which is 256-bit, and have a block cipher $C$ which has a block size of 128-bit. Is it safe to encrypt $K$ with $C$ in ECB mode?

This problem can be generalized to given a block cipher $C_0$ which has a block size of $k$-bit and a random bit string $S$ whose length is $n \cdot k$ where $n$ is a positive integer; in such settings, what would the security risks be to encrypt $S$ with $C_0$ in ECB mode?

I've read this thread Is it safe to encrypt random data using ECB mode?, which gives a good answer to a more generalized question. But in this case, $n$ is (assumedly) generally small, and the benefit to use a simple mode like ECB without op mode parameters (IVs, nonces, etc.) over more advanced modes like CTR is significant enough. Also although not mentioned in the link above, this specific setting doesn't involve padding, which makes the situation even simpler.

In general, this is a bad idea. I won't give you any concrete attacks, but will try to explain why you shouldn't do this. In general, if you want to encrypt a key then you should do it using a secure mode for this purpose. (One is the SIV mode of operation. Another is just to use GCM or CCM.) First, I want to stress that you should always use an authenticated encryption mode, by default. Next, the problem of encrypting with ECB is that it has ramifications that can be problematic. In order to see this, denote by $(c_1,c_2)$ the two blocks encrypting the key $k$ which is 256 bits long. Denote $k=k_1\|k_2$ where each $k_1,k_2$ is 128 bits long (Thus $c_1$ is an encryption of $k_1$ and $c_2$ is an encryption of $k_2$.) Now, given $(c_1,c_2)$, it is possible to replace the two blocks of the encrypted key with $(c_1,c_1)$ or with $(c_2,c_2)$. If an attacker can get some plaintext/ciphertext pairs with $(c_1,c_1)$, then it can learn $k_1$ in time $2^{128}$. It can then do the same with $(c_2,c_2)$ and the result is that the entire 256-bit key can be learned in time $2^{129}$. Now, $2^{128}$ is beyond the capabilities of what can be done. However, if you are using a 256-bit key, then you clearly think that $2^{128}$ is not enough of a margin. By using ECB, you have reduced the security down to $2^{128}$. Beyond this, if you can get encryptions under this key, then you can play around to get encryptions under $k_1\|k_2$, $k_2\|k_1$, $k_1\|k_1$ and $k_2\|k_2$. These are all related keys and there are weaknesses to AES under related key attacks. Even if we don't have a concrete attack on this, it is certainly a threat that should not be ignored.

Bottom line, there is no reason to encrypt with ECB so don't do it. If you do, you certainly run the risk of significantly reducing the complexity of the attack. Make sure that you use an authenticated encryption mode (if you encrypt with CTR then you can flip bits and once again get a related-key attack).


What are the specifics behind MD5 being weak against collisions? One thing I see a lot on InfoSec Exchange is this phrase -

MD5 is weak against collisions

but what I am failing to understand is why.
Why specifically is MD5 weak to collisions? I understand the concept of a collision attack (at least I think I do) so perhaps this question appears stupid in that case, but what is it specifically which makes MD5 so prone to collisions? Are there any other "common" hashing functions which suffer from the same issue? And to what extent do they suffer this issue?
Would I be correct in assuming speed has something to do with this?

TL;DR: On an overview / high-level, how do the collision attacks against MD5 work and why don't they apply to other algorithms?

We know techniques for cheaply computing collisions in MD2, MD4, SHA-0, and, of course, MD5.

The first cheaper-than-generic technique for computing MD5 collisions was published by Hans Dobbertin in 1996; then a collision in MD5, computed in a few hours on an IBM p690, was published by Xiaoyun Wang, Dengguo Feng, Xuejia Lai and Hongbo Yu in 2004, and the technique explained in a followup paper in 2005 (some details on the history); an independently developed technique was used in an international incident of industrial sabotage by the United States and Israel against Iran; and the techniques for computing MD5 collisions have since improved nearly to the point of being a parlor trick.

We also know a technique for computing collisions in SHA-1 much more cheaply than a generic collision search on a 160-bit hash function.  It is nowhere near as cheap as MD5—it cost about $2^{64}$ evaluations of SHA-1, whereas a generic collision search costs $2^{80}$ evaluations of the hash function, and the current best known MD5 collision search by Tao Xie, Fanbao Liu, and Dengguo Feng costs only $2^{18}$ MD5 evaluations.  But it has been executed to find SHA-1 collisions, and for Merkle–Dåmgard hash functions like MD5 and SHA-1, one collision of equal-length messages can be trivially extended into many, so knowing one SHA-1 collision is enough to get you in trouble!

We don't know any techniques for finding collisions with reasonable cost in SHA-2, SHA-3, any of the SHA-3 finalists, BLAKE2, or various hash functions of lesser import.

Many crypanalysts have tried, and failed, to figure out techniques for finding collisions in these.  Any hash function widely used by many applications, especially financial or political applications, will be subjected to scrutiny because of its high value.  It's possible that a spook or crook who found an attack might choose not to publish it, of course!  The SHA-3 competition subjected a number of candidates to years of scrutiny by the world's top public academic cryptanalysts, compiled at the SHA-3 zoo, so that we have some confidence in them to resist collisions.

We also don't consider any hash functions with small outputs, e.g. less than (say) 192-bit, to be collision-resistant because the cost of generic collision searches, counted in number of evaluations of the hash function, is small enough to be within the realm of feasibility for humanity to execute.

To put the number in perspective, the Bitcoin network today performs about $30 \times 10^{18}$ SHA-256 computations every second, about $2^{64}$ per second or $2^{90}$ per year.  A generic collision search on a 192-bit hash function would cost an expected $2^{96}$ evaluations.  That's not cheap, but it's imaginable.


Inverse of a function $f_k(x) := f (x ⊕ k) ⊕ k$ $f : \{0, 1\}^4 → \{0, 1\}^4$

Given a function $f_k(x) := f (x ⊕ k) ⊕ k$, what is the inverse function $f_k^{-1}$?

I could not figure out how this would be done. Thanks.

Assuming $f^{-1}$ exists (i.e., that $f$ is injective), then $$f_k^{-1}(y) = f^{-1}(y \oplus k) \oplus k.$$ To see why consider an $x \in \{0,1\}^4$ so that $f_k(x) = y$. Then you have that $$y \oplus k = f (x \oplus k).$$ Now by applying $f^{-1}$ on both sides of that equation you have $$f^{-1}(y \oplus k) = x \oplus k.$$ And finally by XOR'ing $k$ on both sides you get the above result.


Revealing vote after time Imagine we have 5 different parties, all of these parties test if a particular thing is true or false over the course of 24 hours. The network needs to come to a consensus about the majority outcome of these parties votes.

The 5 different parties need to submit their votes onto a blockchain, however if within the 24 hour time-frame one of the parties submits their vote early there comes potential for one of the other party members to look at the early submitted vote and copy that vote skewing the real result.

What is the way to prevent copying in this situation, can a hash time locked contract be opened that collects the encrypted votes from each party and then after the 24 hours reveal the result to the network?

Or is there something simple im missing, the basic idea is I want to cryptographicaly hide something and then reveal it at a certain block height?

Based on @Cort Ammon suggestion and some additional consultation i think the below will work

  Each of the 5 parties could publish Hash(vote || random bytes), because of the random bytes it would not be possible to find the vote by hashing guesses. Then after all commitments are published or 24 hours has passed each party would publish the plaintext = (vote || random bytes), and all other parties could hash that to verify that it is equal to the original commitment.


Authentication by hardcoding public key in client software It would seem to me that mobile applications could reduce network traffic by hardcoding the server's public key into the app.

The idea being that they could then encipher a secret to share with the API using the public key.

We then would seemingly not need to validate the server-side identity, because only the private key holder should be able to decrypt the message.

The conversation could then switch to symmetric encryption immediately, since both sides have knowledge of the key.

Apart from key management issues, in the event of an unrelated private key compromise, is this otherwise secure? What weaknesses, if any, are there for this scheme vs. traditional TLS handshake?

Yes, the basic idea of hardcoding a public key is secure. It is sometimes recommended as an alternative to the complexity TLS and PKI bring – otherwise it can be easy to skip a crucial step and end up with little or no security.

However, the "encrypt a secret for server" scheme has some weaknesses compared to TLS. The clearest is lack of forward secrecy (which admittedly some TLS suites also lack). If an attacker breaks the public key encryption or gets the private server key, they can decrypt all sessions past and future.

A slightly more complex protocol would fix that issue. You could e.g. hardcode a signing key and authenticate an ephemeral Diffie–Hellman key exchange.

(You also miss out on using the available implementations of TLS, needing to write your own code risking mistakes. That is harder to quantify. And like you said, key management may be more of an issue.)


Can I discard a specific X509 signature from file? I'm writing a program to sign files using X.509 certificates and .NET framework classes. My users can sign the same file more than once without any problem (like a revision process). So, a file may contain one or more signatures.

I'm using the CMSSigner class and I don't encrypt the file. I just sign it.

But now a user asked me the following: "By mistake I signed a file and I would like to take off my signature from that file. Can I do this?"

I see no problem when the file has only that one user's signature (only one X509 certificate within). But I'm not sure if I can unsign the file if it has many signatures there. The routine that I use to strip a signature from a file picks the original data and, in that case, I lose all of its signatures.

So, using .NET classes (X509Certificate2), can I just delete the user's signature from that file, without loss the other certificates there?

Thanks for any help.

Cryptographically speaking, a digital signature provides the property of non-repudiation -- the signer cannot deny signing once signed. So, you either have to keep the unsigned version if you can't strip the signature from the document, or sign another document invalidating the previous signature if the previous document has been released.


Why use complex encryption algorithms? I have recently gotten interested in cryptography, so I looked some things up.

I thought, why even use AES or DES or any other complex way for encrypting data when there are far simpler ways, like just generating a random (pseudorandom) bitstream, and XOR'ing it with the data or secret message? The point is, if you have a random enough bitstream, you can just XOR the data.

Of course, you're the only one who will know the stream.

So why use all sorts of encryption if you have these simpler, easier ways of doing things? I'm new to cryptography, so this question may sound a bit naive.

We use more complex encryption algorithms than XOR  with a random or pseudo-random keystream for a number of reasons:

In order to get a short secret key in symmetric encryption. XOR with a true random stream (One Time Pad) requires storing or/and transfering a secret keystream the size of the data to encipher, which is utterly impractical. Replacing the keystram with a pseudo-random stream (as outlined in the question) solves that key size problem, but see below.
In order to construct Cryptographically Secure Pseudo-Random Number Generators then used as suggested in the question. A weakness in a PRNG could become a weakness in the encryption scheme using its keystream, especially if that's by XOR. We know several demonstrably secure ways to turn a secure block cipher into a CSPRNG, that are reasonably efficient, and (thus) popular.
In order to get direct access to encrypted data. Imagine a large movie stored encrypted as proposed in the question. In order to start viewing it in the middle, we have to run the pseudo-random generator from the start of the file. That's solved by encryption using a block cipher (such as AES) in most common modes, including CTR/CBC/OFB/CFB. For example, AES-CTR does as in the question, with the pseudo-random stream obtained by enciphering a counter (starting from an Initial Value usually stored at start of file), so that we can produce the keystream for any position by adding the IV and the (appropriately scaled) file index, and enciphering the counter values startign from there with AES, yielding the keystream, which allows decryption starting at the desired point.
In order to also get assurance of data integrity and origin, which often turns out to be at least as needed as data confidentiality. Even if we assume a large secret keystream, we need something slightly more complex than XOR with the keystream (e.g. universal hashing) in order to ensure that an adversary did not mess-up with the data (e.g. change "pay \$100" to "pay \$900").
In order to get asymmetric encryption, that is the capability to encipher without needing anything secret (beyond the data to encipher) on the side that enciphers.


Why exactly is Blowfish faster than AES? I've not been able to understand exactly the reason behind Blowfish being faster than AES. Is it dependent on the block size? Or is it processor dependent? (if Yes, then lets assume that AES accelerators are not used) I'd like to know the exact reason behind it. Thanks.

Blowfish has strong points regarding speed because bulk encryption (and decryption) reduce to an alternation of: a 8->32-bit table lookup, and one or two 32-bit operations (addition or XOR). That structure is very well suited to 32-bit CPUs with a short pipeline and a fast cache of at least 4 kByte; and is well suited for a straight C implementation, which generates code that often is very near optimum.

For each byte enciphered, and unless I miscount:

Blowfish performs on average 8 table lookups and 10.25 straight 32-bit operations.
AES-128 performs on average 10 table lookups and 7.75 10.25 straight 32-bit operations (when using a common optimization also requiring 4 kByte of tables).

Table lookups are much more expensive than straight 32-bit operations (most of these come almost for free in practice), and dominate the cost. Thus yes, Blowfish can be a little faster than AES implemented in software; especially if the AES implementation is not optimized to the max, or is AES-256.

Other than that, Blowfish and AES are not playing in the same league, and AES often wins without battle:

Blowfish is a 64-bit block cipher, while AES is a 128-bit block cipher; this is a serious issue in a growing number of applications.
Blowfish key setup is a slow process that produces 4 kByte of table per instance, in RAM. By contrast AES can be implemented efficiently (at least in hardware) with no RAM, and (for encryption, which is the most used) no pre-computation at all (decryption requires a tiny pre-computation).
The 4 kByte table (or 1 kByte, 512 bytes, or even 256 bytes with speed trade-of) used for fast software AES implementation can be shared between instances (or in ROM/flash), it can't in Blowfish.

That makes Blowfish a terrible algorithm when 64-bit block is an issue (e.g. CBC mode with gigabytes of data); or when key agility matters (on occasions the relative slowness of Blowfish's key setup is an asset, see bcrypt); or for hardware implementation; or when 4 kByte is a lot of RAM (e.g. some embedded systems, or a server handling many simultaneous connections).

Also: as rightly pointed in cherio's comment, AES has hardware implementation on many modern CPUs, and that more than offset any speed advantage Blowfish may have (but the question states "AES accelerators are not used").


Do ciphers with a key size of 64 bits still have use under very limited attack models? If we have a very performance critical interactive session, like a video game, running on a trusted platform (video game console).
If our goal is to prevent exfiltration of up to date information (enemy locations, health etc) and malicious commands sent to server in a small time frame (aim botting), say ~1000ms through 1h, to prevent MITM cheating, it seems that 128 bits of protection is excessive for our threat model.
Also are there any decent, modern ciphers with a key size of 64 bits that might actually be faster than AES-NI?

I believe that ciphers of low bitwidth still have a place for sensor data and likely, video game data.  Mainly, this is due to the nature of the data.  In the case of a sensor, cryptography generally buys you very little in the practical sense outside of verifying a message, and the same is true in video games.  Your data is "stale" in a matter of seconds, and as long as the scheme takes minutes to brute force, you are likely to be fine.

If you have access of AES-NI, or an equivalent instruction set, you will not be able to make anything faster.  Let's make the assumption that you are not worried about side-channel attacks, do not have cryptographic hardware on your CPU, and just are interested in speed.

I use SIMON in my embedded hardware, and SPECK in software when I cannot get something else to fit in the space.  SPECK is about as fast as you get on an IC without explicit cryptographic hardware.  The cryptographic community while give you a difficult time for these ciphers as the NSA created them, but I know of nothing better.   SPECK64/96 has 26 rounds, on a MIPS 32-bit MIPS core, it takes me 51 instructions (after I expand the keys) to encrypt the block.


Subscript R notation for the finite fields I'm trying to understand the notation used in the literature for Pairing-based cryptography.
I know (and I hope I've understood it well) from Wikipedia that $\mathbb{Z}_p$ is the finite field of prime order $p$, where

$p$ is the order of the field
$q$ and the characteristic of the field and $q=p^n$

I came across this notation here and there while researching the Identity-Based Encryption (Boneh-Franklin): $$s \in_R\mathbb{Z}^*_q$$
The $\mathbb{Z}^*$ means that the finite field is provided with the multiplication operation.
But the $_R$ confuses me, as I can't find its meaning on the web.
Could somebody explain it?
PS: are the following notations equivalent? $GF(p)$, $\mathbb{Z}_p$, $\mathbb{Z}/p\mathbb{Z}$ and $\mathbb{F}_p$

To quote yyyyyyy from the comments:

  The $_R$ has nothing to do with the field — it is associated to $\in$!
  To quote your first link: "For a set $S$, by $a\in_R S$, we mean that
  $a$ is randomly chosen from $S$."

and to quote SEJPM from the comments:

  If $p\in \mathbb P$ (with $\mathbb P$ being the set of all primes)
  then the notations $GF(p);\mathbb Z_p;\mathbb Z/p\mathbb Z;\mathbb
 F_p$ are equivalent.


Can one build a one-way function from AES? We change the AES block cipher encryption:

we delete the key schedule algorithm
the user now provides a string of 1408 bits
we divide the string to 11 sub keys, and use them directly in the encryption part of AES as the round keys.

We call the resulting function $AES' : \mathbb Z_2^{1408} \times \mathbb Z_2^{128} \to \mathbb Z_2^{128}$.

Then we use this function $AES'$ as cryptographic compression function in the following way:

Given text $M$, we divide it to blocks $M_1, \dots M_n$ of size 1408 bits each. Then define $g_i \in \mathbb Z_2^{128}$ as

$g_0=0$
$g_i = AES'(M_i,g_{i-1})\quad$   (Each $M_i$ is used as the round keys in one AES encryption.)

Then the hash function $h : \mathbb Z_2^{n·1408} \to \mathbb Z_2^{128}$ is defined as follows : $h(M)=g_n$

Is $h$ a one way function? If not, how could an attack reveal $M$, given $h(M)$?

(I don't want you to solve, I just want some hints to solve this problem.)

As Mike asked, it's not clear if you're asking about onewayness, or collision resistance (as you call the function a 'cryptographic compression function').

Assuming you're asking about onewayness, well, given a single 128 bit value $h(M)$, we obviously cannot uniquely deduce the 1408 bit value $M$.  However (hint), let us assume that we can ask for the value $h(M \oplus \Delta)$, for 1408 bit values $\Delta$ that we pick; how can we use that to recover $M$?  How can we extend this observation to cases where the length of $M$ is a multiple of 1408 bits?

Assuming you're asking about collision resistance, well, how can we pick a value $M$ so that $h(M)$ is a predetermined value?  Hint: look at how the AES uses the last round subkeys.


Is the seed block in Argon2 (H0) 64-bit or 64-byte? Is the H0 block in Argon2 64-bits, or 64-bytes? The RFC says bits:

  Establish H0 as the 64-bit value as shown below.

But then it attempts to generate 64-bytes using Blake2

Background

I'm trying to implement Argon2, and the original specs paper, and RFC are not a very friendly to implementors.

I'm stuck on the first step of the Argon2 pseudo-code:

  Establish H0 as the 64-bit value as shown below.

H_0 = H^(64)(LE32(p), LE32(T), LE32(m), LE32(t), LE32(v), LE32(y), LE32(length(P)), P, LE32(length(S)), S, LE32(length(K)), K, LE32(length(X)), X)

There's a lot going on in there, but we can clean it up:

  Establish H0 as the 64-bit value as shown below.

  H0 = H^(64)( [stuff to hash] )

It would seem to indicate that the H^(64)(...) is going to return 64-bits (because of the phrase "...as the 64-bit value...".

But now we go hunting what H^ is, which brings us to the preamble of Section 3.2 in the RFC:

  Argon2 uses an internal hash function H^x(). Here H^x() applied to string a is the BLAKE2b [RFC7693](a,|a|,0,x) hash function

Now we know that: H^(x)(a) = Blake2b(a, |a|, 0, x).

That brings us to RFC 7693 - The BLAKE2 Cryptographic Hash and Message Authentication Code (MAC), in order to figure out what the four paramters are (especially the final paramter x):

The following procedure processes the padded data blocks into an
"nn"-byte final hash value.  See Section 2 for a description of
various variables and constants used.

   FUNCTION BLAKE2( d[0..dd-1], ll, kk, nn )
   |
   ...snip...
   |
   END FUNCTION.

That's a little hard for implementors to read; we can make it a bit more understandable:

Function Blake2(DataToHash, OriginalMessageLength, KeyLength, DigestLength)
   Inputs:
      DataToHash:            Bytes    //array of bytes to be hashed
      OriginalMessageLength: Integer  //length of message in bytes
      KeyLength:             Integer  //length of secret key in bytes (0..64)
      DigestLength:          Integer  //length of desired digest in bytes (1..64)
   Output:
      Digest:                Bytes    //digest that is DigestLength long

   ...snip...

The final parameter to Blake2 (nn in RFC's parlance) is bytes (not bits):

|             | BLAKE2b          |
|-------------|------------------|
|Bits in word | w = 64           |
|Rounds in F  | r = 12           |
|Block bytes  | bb = 128         |
|Hash bytes   | 1 <= nn <= 64    |
|Key bytes    | 0 <= kk <= 64    |
|Input bytes  | 0 <= ll < 2**128 |

Back to Argon

We're looking at Argon2, which says:

H^x() = BLAKE2b(a,|a|,0,x)

So in our case:

  H0 = H^(64)( [stuff to hash] )
  H0 = Blake2b([stuff to hash], |[stuff to hash]|, 0, 64)

Which means that 64 is a number of bytes (not bits), which means that the very first line of the algorithm description should be:

  Establish H0 as the 64-byte value as shown below.

Where am I going wrong? How big is H0? H1?

Bonus

I assume it's a typo when the RFC says:

  Here H^x() applied to string a is the BLAKE2b(a,|a|,0,x) hash function

and that it should read:

  Here H^(x)(a) applied to string a is the BLAKE2b(a,|a|,0,x) hash function

Because later it uses the second syntax:

  H^(64)( [stuff to hash] )

In core.h of the Argon2 reference implementation, we can see that ARGON2_PREHASH_DIGEST_LENGTH = 64.  In core.c, we can see that ARGON2_PREHASH_DIGEST_LENGTH and ARGON2_PREHASH_SEED_LENGTH are used as numbers of bytes (to allocate a buffer in bytes and to specify the size in bytes of a BLAKE2b hash).

We can also reason that it makes no sense for the password, salt, optional secret key, and associated data to figure into the hash only via a 64-bit intermediate quantity—that would open it to preimage attacks on the intermediate quantity.

Please send email to the authors of the internet-draft identifying the incorrect ‘64-bit’ units!

Update: The November 22, 2018 revision of the Argon2 internet-draft, draft-irtf-cfrg-argon2-04, corrects the typo:

  Establish H_0 as the 64-byte value as shown below.

  —draft-irtf-cfrg-argon2-04, §3.2 ‘Argon2 Operation’


need to develop CSPRNG. can i use ANSI X9.31 generator need to create secure PRNG. can i use ANSI X9.31 generator and modify its entropy rather using DT use something else >?

Yes, you can use any generator from NIST SP 800-90A rev.1 (PDF) as SEJPM indicated in the initial comment above.

Adding entropy is called seeding a random number generator. Seeding a PRNG with just date/time is sinful at best. Using a nano-second precision clock is only somewhat better; generally anybody can guess the value of the time so date / time itself is not random enough for secure random number generators.

Yes, you can seed using /dev/urandom which itself is a PRNG, seeded by the operating system. You could also use /dev/random (without the u) to retrieve a seed more directly from the entropy pool of the operating system. However, using /dev/random may cause performance issues and /dev/random may block as well. In general using /dev/urandom should be preferred.

If you use at least 128 bits of randomness from the /dev/urandom then your qualified PRNG should be at least as secure as using /dev/urandom directly. The security of /dev/urandom of course relies on the implementation, configuration and indeed the quality of the entropy it relies on. You may also seed the date / time in addition to the 128 bits of entropy, but date / time brings so little benefit that you might as well skip that part.


What are the actual anonymity features of ZCash? I have looked at their FAQ but I didn't find the answer to this.

Having looked at their whitepaper, it seems to me that the main feature of ZCash is that you can't trace where the money came from, because of zero-knowledge proofs.

My question is, does ZCash also feature anonymity the other way – not being able to trace who the money was paid TO, after it has been paid?

In other words, someone lost X amount, someone gained X amount, and we can't prove who paid whom. But what about simply finding all the people in that block who either gained or lost X? Zcash says it "does not: ... protect against correlations made with public transaction" but what about internal transaction?

As a short answer, yes you can have a transaction that does not allow others to trace who the money was paid.

Zcash supports four kinds of transactions that are categorized as follows,

Public-address to Public-address (like as the ones in Bitcoin)
Public-address to Private-address (they call it shielded transactions)
Private-address to Public-address (they call it deshielded transactions)
Private-address to Private-address (they call it shielded pool transactions)

For transactions in Shielded Pool, origin, amount and destination are anonymous, but in deshielded or shielded transactions only one side is hidden. Recently there was an empirical analysis of anonymity in Zcash that has some very interesting result. I highlight some of them here,

Only 0.3% of Zcash transactions are done in shielded pools (the transactions that are completely anonymous) and only 14.96% of transactions do interact with shielded pools.
73.5% of Zcash users only use public transactions that already exist in Bitcoin and are shown to be linkable.
Only 25% of visible addresses have a non-zero balance, and more surprisingly the top 1% hold 78% of all Zcash coins (ZEC).
Founders of Zcash behavior with quite obvious patterns that make easy to trace their transactions. e. g. analysis show that 14 addresses of founders had been used regularly  to deposit coins to the pools.

You may read more details on https://arxiv.org/abs/1805.03180


Understanding fail-stop subliminal channels It has long been known that randomness can be used to create subliminal channels (see Simmons' "Prisoner's problem" in 1983) and that preventing such subliminal channels is hard.

For the case at hand, Simmons proposed a protocol for preventing subliminal channels within the random numbers generated during the creation of DSA signatures in his "An Introduction to the Mathematics of Trust in Security Protocols" paper in 1993. In Simmons' modification to DSA, the signer Alice (A) tries to communicate a subliminal bit b to Bob (B), communicating through a warden (W) who tries to prevent subliminal channels. The approach to prevent it is basically forcing A to incorporate some randomness that W provides A before A generates the final signature. The rationale of subliminal-freeness being that A can no longer choose the random number on her own.

However, it was later shown by Desmedt in "Simmons' protocol is not free of subliminal channels" that even in that case, there exists a specific type of subliminal channel, which I've seen sometimes referred to as fail-stop subliminal channel. This type of channel works as follows in the DSA case: since A has access to W's randomness before producing the final signature, she can (a) halt the signing process if the last bit of the signature after having incorporated W's randomness does not match b; or (b) complete the process if, after having incorporated W's randomness, the resulting signature's last bit matches b. There may of course be more convoluted ways to decide whether or not to keep going, but that seems to be the overall idea.

My doubt comes at this point. After this reasoning, Desmedt argues that, in order to show whether or not a channel is subliminal-free (i.e., no subliminal channel can be created within it), only the case in which A does not stop should be considered, as in the case in which she stops, W detects that some suspicious behavior is taking place and thus no subliminal exchange can occur (because W detects it, which directly contradicts the principle of subliminal communications). So, following this argument, a system with a fail-stop subliminal channel would (assuming uniformity of the bits to transmit in a subliminal manner) be detectable 1/2 of the executions.

But then, this subliminal channel is of little use in general: if I have a device/software that fails 1/2 of the times, I would, in the best case, assume it is a quite useless device/software and would change it for another different device/software, so no subliminal communication would be possible any longer (and probably, I would think that something weird is happening in that device/software).

Main question: Is this the way in which fail-stop subliminal channels are expected to work, or have I misunderstood something?

Follow up question: If this is indeed the way they do work, when does this type of subliminal channels make sense in practice and how can they be used? (Note: I am not asking in what kind of real-world scenario would a fail-stop channel be applicable, although that can of course help. Rather, I am interested in how could a fail-stop channel be used without the warden detecting/highly suspecting that subliminal communications are taking place and deciding to discard the involved software/device.)

Answer to main question: Yes, it is indeed the way they work. Specifically, the rationale that in order to demonstrate whether or not a channel is subliminal-free, one needs to focus only on the instances in which A does not stop, is quite logical. Consider that, if A stops, then W realizes that a subliminal communication is taking place and the channel is not subliminal-free. But similarly, for the cases in which A does not stop, W still needs to decide if there is a subliminal channel. This is more clearly explained in "A Progress Report on Subliminal-Free Channels." (Check specifically Definition 3, although the prevoius sections help understanding the thought process of the authors.)

Answer to follow up question: TLDR; a fail-stop subliminal channel is  practical roughly when only one subliminal bit needs to be transmitted. Thus, it may make sense only in very restricted cases. The example by Desmedt is that in D day, it would have been enough to transmit a subliminal bit of "landing would not take place at Calais." When more bits need to be transmitted, it is very probably not practical, as its probability of going undetected goes down exponentially (and its capacity drops to $0$ just as quickly).

It can be naturally argued that the practicality of a subliminal channel is determined by its capacity, when the subliminal communication goes undetected.
The maximum capacity of a channel (in the absence of communication errors), is determined by its entropy. And given the previous answer, we know that a fail-stop subliminal channel is undetected as long as A does not halt, so we can use conditional entropy.

The condition making A halt may be defined arbitrarily, but for the sake of simplicity, I stick to Desmedt's example (the following calculations are actually sketched in Desmedt's paper, although a bit succinctly...). In Desmedt's example, A stops if the last bit of the r value of the DSA signature matches $b \oplus c$, where $b$ is a secret (uniformly sampled) bit shared by A and B, and c is the subliminal bit to be transmitted. The event in which A does not stop implies that W sees a perfectly valid DSA signature that has been generated according to the protocol. Thus, he cannot differentiate it from a completely legitimate run. This is denoted with $\{w = 0\}$ (i.e., W ouputs "no subliminal information").

Lets generalize and assume that A wants to transmit u bits. I denote the bitstring to transmit subliminally with $c_i$, for every $i \in [0,2^u-1]$.
Then, the capacity of one single execution of the protocol is:

$H(c_u|w = 0) = -\sum_{i\in[0,2^u-1]} p(c_i,w=0) \log \frac{p(c_i,w=0)}{p(w=0)} = -\sum_{i\in[0,2^u-1]} 2^{-2u} \log \frac{2^{-2u}}{2^{-u}}=u2^{-u}$

[Note that $p(c_i,w=0)$ is the event in which $c_i$ equals the $u$ least significant bits of $r$. Then, $p(c_i,w=0)=2^{-u} \cdot 2^{-u}$, as $c_i$ and $w=0$ are independent random variables, given that $b$ is chosen uniformly at random, and $r=(g^{k' \cdot k''} \bmod p) \bmod q$ is also drawn uniformly at random (because $k''$, chosen by W, is.)]

Now, the function $f(u)=u2^{-u}$ has a maximum at $1/\ln2$ and therefore the maximum capacity is $1/\ln2 \cdot 2^{-1/\ln2}=0.5307$.

Note that, if we want to analyze the case in which A tries to transmit t different signatures (restricting to the fail-stop strategy), each including $u$ bits of subliminal information, it is equivalent to having A try to transmit $tu$ bits in a single signature, which is again maximal when $tu = 1/\ln2$.


Is verification of ring signature always linear in the amount of members? To me it seems that maybe we can prove that verification of a ring signature  must be linear in the number of members, since we need to make sure each members component is correct and the ring is formed correctly.

Is there any proof of this statement, or a refutation?

In the most common definition of ring signatures, the verification algorithm obtains the list of public keys (the ring) and thus already requires linear time to read this input.

However, there are constructions based on accumulators (Dodis et al. EUROCRYPT'04, Libert et al. EUROCRYPT 2016, Derler et al. PQCRYPTO'18) which allow amortized sublinear verification costs. In patricular, there is some constant size representation of the ring (the accumulator), where on the first verification one checks if it represents the correct ring (linear time) and after that, verifications with respect to the same ring can take the accumulator instead of the ring and the computation depends only on the complexity of membership proofs in the accumulator (constant for the RSA accumulator in the first link and logarithmic in the ring size for the latter two).


Is it possible to find the product of two numbers without knowing the two numbers? I'm doing a thought experiment:

Alice chooses a number $a$ and Bob $b$. They send $A(a)$ and $B(b)$ to Charlie. He performs $C(A(a), B(b))$ and gets $ab$.

Do there exist not easily reversible functions $A, B, C$ for which the above is true?

I'm a beginner so I'd be all the more grateful if somebody knows :)

Thank you!

In the way you setup the problem the answer is No.

As Charlie can perform $C(A(1),B(b))$.


Why do "nothing up my sleeve numbers" have low entropy? As a preface, forgive me for some of the links being from Wikipedia.  I realize that academia frowns upon this.

I came across this article about "nothing up my sleeve numbers".  In it, it says:

  In cryptography, nothing up my sleeve numbers are any numbers which, by their construction, are above suspicion of hidden properties.  [...]  Such numbers can be viewed as the opposite extreme of Chaitin–Kolmogorov random numbers in that they appear random but have very low information entropy.

In looking for an example of one of these numbers, I came across this Crypto Beta Q&A, where the answerer says:

  [M]athematical constants like binary expansions of irrational numbers like 2√ (or roots of other numbers), e, π can be used, to show that one didn't select the numbers to create a back door.

This is what Wikipedia has to say about information entropy:

  Entropy is typically measured in bits, nats, or bans.  Shannon entropy is the average unpredictability in a random variable, which is equivalent to its information content. Shannon entropy provides an absolute limit on the best possible lossless encoding or compression of any communication, assuming that the communication may be represented as a sequence of independent and identically distributed random variables.

Based on this, I don't see why these numbers (or any possible number) can have low entropy.  It seems like all numbers have equal likelihood of being generated as a "random variable" as long as that number is within the generated range (e.g., if the number is 1564631 [assumed to be one of these kinds of numbers], and I'm looking for number between 1 and 2000000, it has an equal likelihood of being generated, regardless).

Can anyone explain this concept?  I looked at the definition of entropy, but I admit that the math is a little over my head.  I'm not sure how someone would use a number without these properties to "create a backdoor."

You're absolutely correct: numbers (or a given binary string) don't have entropy. However, a number can be sampled from a distribution that has entropy. In other words, the entropy is a property of the process used to generate a number, not of the number itself.

So if I just give you the number 4, and assure you that I picked this number uniformly at random from between 1 and 6, you have no way of knowing if I'm telling the truth. Depending on the scenario, maybe I had an ulterior motive for picking 4, rather than choosing a number at random.

The issue comes up in cryptography because when it comes time to choose the constants for an algorithm (such as SHA1, or any of the other examples in the Wikipedia article you linked), there might be mathematical arguments suggesting, "If the constants are chosen at random, then with high probability, no attacker will be able to break it." But cryptographers, being a paranoid lot, are skeptical when someone says, "Let's use this set of constants. I picked them at random, I swear." So as a compromise, they'll use constants like, say, the binary expansion of π. While we no longer have the mathematical benefit of having chosen them at random from some large pool of numbers, we can at least be more confident there was no sabotage.

These nothing-up-my-sleeve constants have low entropy because the process of choosing them didn't involve very many random choices --- compare the number of "reasonable" nothing-up-my-sleeve numbers to the number of, say, 128-bit strings they are used to produce. This is by design. If there were a large number of nothing-up-my-sleeve numbers to choose from, then it would be easier for a malicious algorithm designer to find some that suited his agenda.

A very recent and very alarming case of someone not using nothing-up-my-sleeve numbers to create a backdoor is the Dual EC DRBG standard, which is used to generate random numbers. This algorithm included two constants, P and Q, and would be secure if no one could compute f(P, Q), for a specific function f.
Given randomly chosen P and Q, this would be hard. However, if you get to choose P and Q, then you could choose P, decide what you wanted f(P, Q) to be, and then solve for Q rather easily. Now you have a backdoor.