How can cryptographic signatures be somehow linked to a physical signature?

The short answer is that there's no link between your physical signature and any cryptographic signature. Indeed, from the high-level description of how DocuSign works and their security manifesto there's no reason to believe that any cryptography goes into the signature process itself.

Note that “signature” is an overloaded word. In this post, I will refer to three different concepts that can be called “signature”:

Your physical signature — a scrawling on paper.
A cryptographic signature which mathematically authenticates a message as having been validated by the owner of a key. (There are actually two meanings here: the process of generating a signed message from a key and a bare message, and the bytes that encode the authenticity information in the signed message. But this distinction won't matter in important ways here.)
A validation assertion: a statement that a message has been approved by a certain party.

Physical signatures play a dual role.

They're often used as an authentication factor, because they're supposedly hard to reproduce. But as an authentication factor, they're very broken: not only they're not that hard to reproduce in a way that will fool most people, but mostly because in most cases they can easily be copied and grafted onto a different document. With a scanned signature, grafting it onto any document is trivial.
Physical signatures are also used as a validation assertion. Signing a legal document indicates that you agree to abide by it. Historically, this is the reason they've been used on contracts — even people who couldn't read had the contract read to them and then made a cross at the bottom to signify that they accepted it.

Uploading your physical signature to DocuSign's servers doesn't provide any security. Anybody could find some document that you signed and upload your signature. What it does is partly to provide an illusion of security (we need to demonstrate visible security measures, so let's do something visible and say it's for security), and partly to add a bit of friction and ceremony so that you can't later claim “oh, I must have clicked by mistake, I know nothing about this”. Because your signature is personal to you, you can't claim that it was uploaded by mistake — it had to be you or someone with the intent to commit fraud.

With or without your signature, what DocuSign can attest is:

There is someone with access to an account which has your name and other personal information attached to it. Hopefully they verify that this person has (or at least has had) access to the email account attached to the DocuSign account.
That person made a conscious decision to validate a certain document at a certain time.

Still no crypto so far, except for the trivial (in engineering terms) aspect of using TLS to communicate with their servers.

What can cryptography bring to the table? At this point, nothing, really. DocuSign may well generate a cryptographic key that's specific to your account, and produce a version of the document that's cryptographically signed with your key. That would be a validation assertion for the document on your behalf. They don't need cryptography for that, though: they could put up a web page on their server that states “Rahul approved this document”, and it would serve just as well.

Where cryptography adds something is that a cryptographic signature remains valid in any context. A web page that states “Rahul approved this document” is only useful if you access it on DocuSign's website, because anybody could write that on their own website and it wouldn't have any importance. On the other hand, nobody but the holder of the private key can produce a cryptographically signed document, so the authenticity of that document can be verified offline.

It would be sufficient for that purpose for DocuSign to have a single key and use it to sign all documents. The downside of this approach is that if the key was ever leaked or used in an unauthorized way, it would throw suspicion on all of DocuSign's validation assertion. Using separate keys per user allows the keys to be repudiated separately. For example, if your account is breached because someone hijacked your browser, you could arrange to repudiate signatures made with your key after the breach, which would be a lot less disruptive than repudiating signatures made by all DocuSign customers.

If DocuSign does use a cryptographic signature, it isn't part of the security of the validation assertion, and nothing ties it to your physical signature other than the integrity of your account information on DocuSign's servers. This is the same thing that guarantees the relation between you (via your account, and in particular via your account's credentials) and the validation assertions on your behalf.

You'll note that DocuSign's security page includes a lot of hype, assertions about encryption (which does make sense to improve data confidentiality in case backups are stolen), and assertions about physical security (which makes sense as well, since a breach of their servers would compromise the system) and availability, as well as assertions about following religious regulatory processes. Nothing firm about signing.

As long as the signing key is on DocuSign's servers, the advantage of cryptography is to make the validation assertions easier to use, not to make them harder to forge (i.e. no added security). What if the signing key was only held only on your client? That would reduce the trust that you need to put in DocuSign, since they would not be able to generate arbitrary signatures as you. You would still have to worry about the security of your client environment(s). That would also have practical disadvantages because people use multiple client machines, don't back them up, etc. DocuSign's approach requires no technical competence from the user and no setup on the client side. People who are technical enough to manage signing keys are probably using PGP already anyway.


Is it a requirement to understand mathematics when implementing (or breaking) cryptography?

I would say there are three general areas of necessary expertise for most crypto-related jobs:

Knowledge of primitives and their use cases.
Knowledge of protocols and understanding how to reason about their security.
Deep and abiding understanding of how incredibly stupid people are, including oneself.

The most that knowing the math is going to do for you practically, unless you are in academia/the NSA designing algorithms, is tell you "time to stop using RSA" on the day that you hear that there is a polynomial time factoring algorithm.


Quantum Resistance Characteristics - why symmetric?

I have heard that public key cryptography may be “totally broken” by Quantum computers running Shor’s algorithm

Cryptosystems based on discrete logarithms and factoring are vulnerable to Shor's algorithm.

These cryptosystems do not comprise the entirety of "public-key cryptography", because "public-key cryptography" includes digital signatures, not just public-key encryption and key agreement.

The following types of cryptosystems are not completely broken by quantum algorithms:

Hash-based digital signatures
Code-based systems (e.g. McEliece)
Lattice-based schemes
Multivariate schemes

So "public key cryptography is totally broken by quantum computers" is too broad of a conclusion.

It is more accurate to say "The most common schemes such as RSA, DH, and ECC are broken again quantum computers, but there are more schemes in existence then just those three."

  ...while symmetric key ciphers are safe, but Grover’s algorithm may require twice as many bits in the keys.

This is more or less accurate. There is some debate whether or not an actual doubling of key sizes is strictly necessary. And it should be noted that Grover's algorithm also influences hash functions.

  Can someone please elaborate on what exactly is going on underneath, to say these things? What exactly does Shor’s algorithm do and how bad is it?

What does it do

Shor's algorithm uses a combination of a classical computation algorithm and the quantum fourier transform to factor numbers.

The problem of integer factorization is hard when the product to be factored consists of large prime numbers. A typical RSA modulus consists of two large prime numbers multiplied together $N = p * q$.

Shor's algorithm uses the quantum fourier transform to find how long it takes $f(x) = a^x \bmod N$ to cycle through all the possible outputs back to the beginning. So it looks for an $r$ such that $a^{x + r} \bmod N \equiv a^x \bmod N$, with the additional condition that $r$ is even so that $r/2$ can be obtained. The rest of the algorithm actually uses classical computation, finding the value of $r$ is the hard problem that the quantum algorithm solves. Finally, $gcd(a^{r/2} + 1, N)$ and $gcd(a^{r/2} - 1, N)$ are both nontrivial factors of $N$. (Where "nontrivial" means "not counting $1, N, -1, -N$", because those aren't helpful). The complete algorithm can be found in the wikipedia article about Shor's algorithm.

You can also use Shor's algorithm to compute discrete logarithms, which breaks Diffie-Hellman type cryptosystems. I don't understand the details of how to do so, so I will refrain from going into details.

How bad is it?

  On a quantum computer, to factor an integer $N$, Shor's algorithm runs in polynomial time (the time taken is polynomial in $log\ N$, which is the size of the input)

It's bad. We really need the best attack to take exponential or at least sub-exponential time in order to have security with reasonable and practical sized values. A polynomial time algorithm for solving a problem basically makes that problem not useful for cryptography. Of course, you can technically try to use (much) larger parameters to make up for the difference... but that's not nearly as practical or graceful as we would like.

How exactly are symmetric key ciphers not susceptible to this?

The ability to find the period of a function is not necessarily useful for breaking a symmetric cipher. In order to do anything, you would need access to (at least) an encryption oracle. There is a paper about using Simon's algorithm to break symmetric modes of operation, but the attack model they use is pretty powerful: The adversary must prepare a superposition of all possible plaintext-ciphertext pairs, which is not trivial.

Basically, symmetric block ciphers and stream ciphers tend to use highly non-linear components which destroy any useful relations between inputs/outputs. Asymmetric designs tend to rely on such relations in order to achieve their goals. This means that asymmetric designs tend to incorporate more structure, and the structure can be exploited as a weakness.

How do we know we can’t do better than Grover’s algorithm later, making ALL ciphers susceptible?

Because it has been proven that:

  ...any quantum solution to the problem needs to evaluate the function $Ω(\sqrt{N})$ times, so Grover's algorithm is asymptotically optimal.

What are the measures taken by the latest public key ciphers submitted to NIST that purport to overcome these problems?

They are built on problems that are not known to be vulnerable to quantum algorithms. Using non-abelian groups seems to be helpful in regards to resisting quantum algorithms.

Note that "not known to be vulnerable" does not mean "It is proven that there cannot exist a quantum algorithm that solves the problem", it just means that there is no publicly known quantum algorithm for solving these types of problems.


initial value for RSA and SHA-256 signature encoding

Digging the RFC 8017

9.2.  EMSA-PKCS1-v1_5
For the nine hash functions mentioned in Appendix B.1, the DER encoding T of the DigestInfo value is equal to the following:

and

A.2.4.  RSASSA-PKCS-v1_5
The object identifier for RSASSA-PKCS1-v1_5 SHALL be one of the
following.

Both combined below;
Hash algorithm   OID                           the DER encoding T of the DigestInfo
------------------------------------------------------------------------------------------
MD2              md2WithRSAEncryption          (0x)30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 02 05 00 04 10 || H.
MD5              md5WithRSAEncryption          (0x)30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 05 05 00 04 10 || H.
SHA-1            sha1WithRSAEncryption         (0x)30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14 || H.
SHA-224          sha224WithRSAEncryption       (0x)30 2d 30 0d 06 09 60 86 48 01 65 03 04 02 04 05 00 04 1c || H.
SHA-256          sha256WithRSAEncryption       (0x)30 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20 || H.
SHA-384          sha384WithRSAEncryption       (0x)30 41 30 0d 06 09 60 86 48 01 65 03 04 02 02 05 00 04 30 || H.
SHA-512          sha512WithRSAEncryption       (0x)30 51 30 0d 06 09 60 86 48 01 65 03 04 02 03 05 00 04 40 || H.
SHA-512/224      sha512-224WithRSAEncryption   (0x)30 2d 30 0d 06 09 60 86 48 01 65 03 04 02 05 05 00 04 1c || H.
SHA-512/256      sha512-256WithRSAEncryption   (0x)30 31 30 0d 06 09 60 86 48 01 65 03 04 02 06 05 00 04 20 || H.

and in

B.1.  Hash Functions
The object identifiers id-md2, id-md5, id-sha1, id-sha224, id-sha256,
id-sha384, id-sha512, id-sha512/224, and id-sha512/256 identify the
respective hash functions:
   id-md2      OBJECT IDENTIFIER ::= {
       iso (1) member-body (2) us (840) rsadsi (113549)
       digestAlgorithm (2) 2
   }

   id-md5      OBJECT IDENTIFIER ::= {
       iso (1) member-body (2) us (840) rsadsi (113549)
       digestAlgorithm (2) 5
   }
   ...

Therefore it is the DER encoding of the above object identifiers. See example on A Layman's Guide to a Subset of ASN.1, BER, and DER (5.9)


Yes.  Just prove that such information doesn't exist.

(For example, that can be used to prove that one

doesn't know a boolean value x such that  x and not x .)

For P/poly provers, if such proofs exist then UNSAT has a usually-correct promiseMA protocol.

However, if public-coin collision-resistant hash families exist, then

a common random string is enough for arguments of non-knowledge.

For example, to argue that one does not know a string

such that  Hcommon_random_string(0||x) = y ,  argue that one

does know a string x such that  Hcommon_random_string(1||x) = y .


Why is there no 'ECDSA' version of 'DHE-RSA-CHACHA20-POLY1305'?

The original cipher suites involving ECDH and ECDSA were all introduced together in RFC 4492.  They corresponded to existing cipher suites:

\begin{equation}
\begin{array}{rcl}
  \text{DH_DSS} &\longmapsto& \text{ECDH_ECDSA} \\
  \text{DHE_DSS} &\longmapsto& \text{ECDHE_ECDSA} \\
  \text{DH_RSA} &\longmapsto& \text{ECDH_RSA} \\
  \text{DHE_RSA} &\longmapsto& \text{ECDHE_RSA} \\
  \text{DH_anon} &\longmapsto& \text{ECDH_anon}
\end{array}
\end{equation}

One might infer that the thinking was if you were going to take the plunge into the world of elliptic curves—recall in 2006 elliptic curve cryptography had (and to some extent still has) an undeserved reputation for being new and poorly understood in contrast to modular exponentiation systems in finite (quasi-)fields—then you might as well use ECDH key agreement, while you might keep your long-term RSA certificate because it was costly to buy a new one.  Doing it the other way around—buying an ECDSA certificate but using finite-field DH key agreement—would just be silly.

(Recall that this was also perhaps the heyday of the HTTPS certificate authority protection racket, before the browsers collectively imposed any semblance of regulation on it by the CAB Forum and long before Let's Encrypt rendered it obsolete.)

One might further infer that nobody bothered to break this pattern, because why would you want to do any more finite-field DH key agreement in this day and age anyway?


Sending a big block of data to be then used as initialization vectors is secure (assuming it is transferred encrypted and authenticated), but kind of defeats the purpose of "keeping the message size down".

The requirements for an initialization vector depend on the mode of operation, not on the underlying cipher (AES in your case).

For CBC mode, the initialization vector for each message should be at least not predictable by an attacker before the message is known (otherwise there are some chosen-plaintext attacks which allow decrypting your message).
Old versions of SSL used the last block of the previous message, and were thus vulnerable to this attack – newer versions send an IV with each message.

One way to go here would be to use part of your 1024 bit shared secret as the seed for a CSPRNG (on both sides), and use the output of this as IVs. (Use separate generators for both directions.)

For CTR mode, the initialization vector can either be random (see above), or be simply counted up from the last counter value of the last package, and if this is decided in the protocol, you don't need to send it along with the message.

(Of course, in both cases this only holds if your messages are protected from reordering by some other mechanism – e.g. if this is done over TCP.)

Your MAC (you have a MAC, don't you?) should include the initialization vector, even if it is not sent.

There are other modes of operation, including most AEAD modes, which only require the nonce-property of the initialization vector, i.e. that it is not repeated. Then you can use a simple counter, or use an existing message number (maybe together with an identifier of the sending side).

Also note that the streams in both directions should use different keys, not the same one.


Is there an input length range for SHAKE128 hash function?

The quoted paragraph talks about the testing of SHAKE128. As usual, for the 128-bit security achievement, you need to think about the generic attacks on hash functions.

For preimage resistance, you need 128-bit digest size. However, due to the birthday attack, you need 256-bit digest size to achieve 128-bit collision resistance. That is $\sqrt{2^{256}} = 2^{256/2} = 2^{128}$.

For the input length; if the input space is small, it can easily brute-forced or a special rainbow table can be implemented to find the preimage of the hash values. For 128-bit preimage resistance, you need your input space to be around 128-bit.


How does padding oracle attack work with bytes larger than possible length?

For a CBC mode cipher, which is what POODLE applies to, you don't encrypt or decrypt individual bytes, but rather blocks, formed by adding padding to the actual data bytes. For encryption in general every byte can be any value 0 to 255, and the SSL spec allows the padding_length byte to be almost any value, but most if not all implementations only use 0 to L-1. (Not 1 to L; a different common padding scheme, PKCS#5/7, does use 1 to L.) SSL/TLS uses MAC-then-encrypt (see a hundred other questions why this turned out to be not the best choice) so actually user-data plus HMAC is padded and then CBC-encrypted, as shown by the line you posted: user data consisting of POST /path cookies etc, then (20-byte) MAC, then padding.

CBC mode encrypts a block at a time after XORing the plaintext block with the previous ciphertext block, or for the first block with the IV. Similarly when decrypting it XORs the decrypted block with the previous ciphertext block or IV to produce the plaintext. The diagram in Wikipedia shows this in detail.

HOW POODLE BITES. You omitted most of the paper's explanation:

  The attacker controls both the request path and the request body, and
  thus can induce requests such that the following two conditions hold:
  ● The padding fills an entire block (encrypted into Cn). ● The
  cookies’ first as-of-yet unknown byte appears as the final byte in an
  earlier block (encrypted into Ci). The attacker then replaces Cn by Ci
  and forwards this modified SSL record to the server. Usually, the
  server will reject this record, and the attacker will simply try again
  with a new request. Occasionally (on average, once in 256 requests),
  the server will accept the modified record, and the attacker will
  conclude that DK(Ci)[15] ⊕ Cn-1 [15] = 15, and thus that Pi[15] = 15 ⊕
  Cn-1 [15] ⊕ Ci-1 [15]. This reveals the cookies’ first previously
  unknown byte. The attacker proceeds to the next byte by changing the
  sizes of request path and body simultaneously such that the request
  size stays the same but the position of the headers is shifted ,
  continuing until it has decrypted as much of the cookies as desired.
  The expected overall effort is 256 SSL 3.0 requests per byte.

When Cn is replaced by Ci satisfying the two stated conditions, the receiver first decrypts, and unpads, the received message. There are two possibilities:

If the result of CBC decryption has anything other than 15 in the last byte, the unpadding either fails entirely or yields a result that fails MAC verification (with overwhelming probability), producing an error alert that the attacker can observe.
If the result of CBC decryption does have 15 in the last byte, the receiver doesn't detect any error and continues with the session. The attacker now knows that the last byte from the previous ciphertext block (Cn-1[15]) XORed with byte 15 of the block that was encrypted to form Pi (Dk(Ci)[15]) is 15 and also knows that Dk(Ci)[15] was computed as Pi[15] XOR Ci-1[15]. Combining these allows the attacker to compute Pi[15] with the formula shown.

Replace 16 and 15 by 8 and 7 for an 8-byte block cipher, which for SSLv3 was triple-DES, DES, RC2 or IDEA. But almost nobody implemented IDEA and RC2, and DES has been insecure and deprecated or prohibited for over a decade.

The attacker now knows a cookie byte (or bite?); rinse and repeat, or as a classic snack advertisement had it, "munch all you want, we'll make more".
EDIT: Specifically, to get the second cookie byte, the attacker adjusts the URL path that it causes the browser to request, so that the second cookie byte now falls at Pi[15], satisfying the second assumption. It repeatedly requests this URL until it gets the Pn'[15]=15 case for the second cookie byte. Then it adjusts the path so that the third cookie byte falls at Pi[15] and is recovered, then the fourth, and so on. Remember the browser sends the same cookie(s) on all requests to the same origin across multiple connections, until directed to change it(them), typically when the user logs-out or after a long period of time like an hour; this attack likely takes less than 50*128*0.1sec = 10 minutes. This does assume that the other data in the request headers like user-agent: and accept-language: etc don't vary in length (or vary only by a multiple of the blocksize 16, less likely); in practice on most browsers these are fixed except for Host: and that is fixed by the attack. It doesn't matter the key (and IV) changes on each connection, because we don't try to recover any of those keys, only an unchanging part of the plaintexts.


what is contained in a public key certificate

You actually don't trust the certificate by itself. A certificate is like a diploma that a company (or a domain, e.g. www.crypto.com) obtained from some trusted party, called CA, or Certificate Authority. This diploma states that www.crypto.com is allowed to communicate with you using the public key written in the diploma.

But, as you mentioned, www.crypto.com could generate that diploma to itself, then why should you believe them that the public key written in that diploma is realy theirs and not belongs to some man-in-the-middle attacker?

Here comes the signature part in the diploma. The CA attaches to that diploma a digital signature on www.crypto.com's public key, and you, as their client, verify that indeed, the signature is valid (you do so by applying the CA's verification key on the signature). By definition, nobody can forge that signature and trick you, i.e. to make a valid CA's signature on a fake www.crypto.com's public key.

A crucial key point here is that there exists a 'chain of trust', i.e. you'll believe www.crypto.com only if some CA that you trust tells you to believe it. By default, every browser (and operating systems) is bundled with a list of trusted CAs.


Is there any practical use of reduced rounds of AES

There is not much use for reduced-round AES as a block cipher per se. AES has been carefully designed to provide appropriate security margins and 20 years of cryptanalysis show that they are just right - reducing the number of rounds would make it potentially susceptible to attacks.

On the other hand, the single round function is a very useful transformation that provides good mixing and other provable properties. Moreover, widespread hardware support for the round function (like AES-NI instructions and similar) makes it attractive from the performance point of view.

A good example is a lightweight hash Haraka designed for short-input hashing that uses AES round function.


SHA-256, as part of the Secure Hash Standard or SHS is defined to operate on bits, to be precise in Section 6.2: SHA-256:

  SHA-256 may be used to hash a message, $M$, having a length of $l$ bits, where $0 \leq l < 2^{64}$.

That said, you won't easily find an implementation that does precisely that; usually only bytes (or, by another name) octets are taken.

This is not just true of SHA-256 but also for many other algorithms such as the derived HMAC algorithm, block cipher modes of encryption, RSA (as specified in PKCS#1), etc..

In some sense 8 bit bytes are the atoms of computers. You can still split them up into bits (protons, neutrons and electrons), but the result is difficult to handle. So almost all cryptographic API's are defined on bytes instead of bits, while the algorithm is usually described using bits.

To handle any other data you need to encode the data as bytes. The reason to use SHA-256 is to generate a semi-unique value for a large input that cannot be converted back to the original value.

This means that the encoding of the data should be unique as well; this is called a canonical encoding. One example of this is ASN.1/DER, which is used to sign the X5.09 certificates used in your web browser.

Alphanumeric data can be converted to bytes using a character-encoding such as ASCII or UTF-8. Of course the encoding should be known in advance or you might get different values for the same string, e.g. if one is encoded using Windows-1252 and the other in UTF-16LE, to name just two random other character-encodings.

Note that some runtime environments contain SHA-2 implementations that implicitly convert characters to bytes. A platform itself may also have a default character representation (e.g. PHP).

Furthermore, the output of SHA-2 may also be converted to a hexadecimal string or something similar. This is however a decision by the runtime/API designer and not of the SHA-2 algorithm; the SHA-2 algorithm is defined to operate on bits.


What would the Internet be like without public-key cryptography?

You can create a public key cryptosystem from any trapdoor function, and you need some form of trapdoor to design a public key cryptosystem. Do you mean "those trapdoor functions, which are currently USED in Internet standards"? The most prominent ones are discrete log of integers, factorization and discrete log in elliptic curves.

If so: Yes, it might be possible to set up new protocols, based on other hard problems, although I can just think of lattice problems atm (SVP,CVP,LWE,etc) and McEliece(based on linear codes). It is easy to use these instead of any factorization-based public key cryptosystem. However, the discrete log problem is a different matter: The group structure does not depend on a specific private key and several (pk,sk) key pairs can operate on the same group. This is required for several primitives, e.g. DH key exchange. I can't think of any hard problem with this, other than discrete log on integers and elliptic curves.

If you want to disallow all known public key cryptosystems (in the sense of all protocols based on trapdoor function)... it would be VERY different. While you could communicate over secure channels with symmetric key crypto, there is no way to exchange a key. If you want to use a key for symmetric encryption, both sides have to know it previously or send it plain.

In this case, some parts of the Internet still would work: You could store a secret key for every single party, with whom you interacted. Based on this key, you can set up a new secure connection again. Authentication might still work with hash functions, etc.

But assuming, you want to visit a website and interact over a secure channel: You have no known secret and have to agree on something. Whatever you send, the routers between you and the website will know. If you can trust ALL of them, you are okay. But any of them could just listen in your secret channel

To sum it up: If the Internet was based on trustworthy infrastructure (providers, exchange points, etc.), it would be similar. However, that would not be the Internet we have today. The current Internet would just not work.


Safety when disclosing hashes of secrets used to calculate other secrets

The security concern is that the result of that operation will be guessable without the secret number, since the later part of that answer explains why it also applies to SHA-256.

(Also, $\:$ SHA256(A+"") = SHA256(A)$\:$.)

The random number should be long enough to make brute-force highly infeasible.

If it is and you publish HMAC(A,"") and present them with the values of HMAC(A,B),

then the result of those operations should not be guessable for non-empty strings B.


Predicting Java's PRNG using partial output

Assuming this generator is well-seeded, you probably can't learn much about the next output.  You observe two outputs, so 32 bits in total.  The state of the generator is 48 bits.  Thus, there will probably be about $2^{16}$ states of the generator that are compatible with your two observations.  This means that most of the 16-bit values for the next output are (heuristically) likely to be possible.

Thus, your best bet might be to look at how the generator is seeded.  I have a vague recollection that Java's PRNG is poorly seeded, using a seed that has less than 48 bits of entropy.  If this is the case, then it might be possible to predict the next output, by enumerating candidates for the initial seed and seeing which ones are consistent with the outputs you've observed.

If you need to enumerate which values for the next output are possible, here is a way to do it.

The naive way is to enumerate all $2^{32}$ possible values of seed[i] (you know its top 16 bits, thanks to your knowledge of R[i], so you just need to enumerate all possibilities for its low 32 bits), then test which ones are compatible with the observed value of R[i+1], and for each one that survives, compute the resulting value of R[i+2].  This takes about $2^{32}$ steps of computation, so you can probably make it run in a few seconds or tens of seconds of computation power.

With a little bit of cleverness, you can make this run a lot faster.  Since we know the value of R[i+1], we know the range of possible values for seed[i+1]: in particular, we know that 2^32 * R[i+1] <= seed[i+1] <= 2^32 * R[i+1] + 2^32 - 1.  Also, we know that seed[i+1] = 0x5DEECE66D * seed[i] + 11 - c * 2^48 for some c in the range 0x5DEEC * R[i] <= c <= 0x5DEED * (R[i]+1).  Moreover, we know the top 16 bits of seed[i], so we can write seed[i] = 2^32 * R[i] + x, for some integer x satisfying 0 <= x <= 2^32 - 1.

Combining all of this, it follows that

2^32 * R[i+1] <= 0x5DEECE66D * 2^32 * R[i] + 0x5DEECE66D * x + 11 - c * 2^48 <= 2^32 * R[i+1] + 2^32 - 1

or equivalently,

(2^32 * R[i+1] - 0x5DEECE66D00000000 * R[i] - 11 - c * 2^48)/0x5DEECE66D <= x <= (2^32 * R[i+1] - 0x5DEECE66D00000000 * R[i] + 2^{32} - 12 - c * 2^48)/0x5DEECE66D

This range is of width less than 1, so if you know the left-hand-side and the right-hand-side, you can immediately infer x.

Thus, if we know c, then the value of x is determined, which reveals seed[i] and thus the next output of the generator.  Finally, there are only about 0x5DEED$\approx 380,000$ possible values of c.

This gives an algorithm that enumerates all possible values for the next output, using about $380,000$ steps of computation.  We enumerate over all $380,000$ possible values of c; for each possible value of c, we round (2^32 * R[i+1] - 0x5DEECE66D00000000 * R[i] + 2^{32} - 12 - c * 2^48)/0x5DEECE66D down to the nearest integer, call it x, and then we infer the value of seed[i] (namely, seed[i] = 2^32 * R[i] + x) and run the generator for two steps to observe the implied next output.  We collect all possible next outputs of the generator.  This gives us the set of all possible values for the next output.  Each iteration uses just a few simple arithmetic operations, and we do $380,000$ iterations, so this procedure should run extremely fast: in milliseconds or less.


Diffie-Hellman Key Exchange with Authentication: Man-in-the-Middle query

Firstly, PKI makes use of a private key and a public key. The private key is known only to the user, while the public key is communicated securely via the use of certificates. To provide authentication and non-repudiation, users may sign a message with their private keys and obtain a digital signature. Any other users can verify that the signed signature is authentic by "decrypting" it with the claimed user's public keys.

So to answer your questions:

Mallory is unable to intercept the negotiated session key due to the Diffie–Hellman problem whereby it is hard to compute $g^{ab}$ given $g^a$ and $g^b$. He is unable to impersonate Bob if he does not prossess Bob's private keys.
Yes, your are correct. Mallory can only eavesdrop the encrypted ciphertext and is unable to learn its contents.
No, Mallory is unable to obtain the session key (of the communication between Alice and Bob) even if he has knowledge of Bob's private keys due to the Diffie–Hellman problem. Mallory is able to impersonate Bob when communicating to Alice but unable to impersonate Alice with communicating to Bob. However, if Mallory has access to both Alice and Bob's private keys then a MiTM attack is possible.
No, Bob has to change his public-private key pair including his certificate unless there is 2-factor authentication in place (e.g. via voice/text message or tokens).

Hope this helps.


Paillier cryptosystem, small integers and range of values

With version 1, you are essentially using an additively homomorphic substitution cipher. I understand that the database is quite large, but the number of different values small. This (typically) means that statistical analysis can be used to derive a lot of information, especially if the attacker has some auxiliary information which is often the case. This is a very bad idea.

Version 3 is like version 1, but it's a bit harder to do the statistics. The problem is that the database is so big, that this may also be easy. Of course, it's very hard for me to judge how easy it is to do statistics without knowing the application and without knowing what auxiliary information is available.

Having said the above, your actual question is whether it helps the attacker to actually decrypt (say, with no auxiliary information whatsoever). The answer is no. In order to see why this is the case, consider a game whereby the attacker either receives encryptions of 0 to 50, or 51 encryptions of 0. It is easy to see that the adversary can guess which is the case with probability only negligibly greater than 1/2 (e.g., this is the multiple encryption experiment). Now, an adversary in this game can emulate the database assuming it has encryptions of 0 to 50 and can see what the adversary for the database can learn. If it can learn something, then it must be that the encryption adversary received encryptions of 0 to 50 (since encryptions of zeroes only reveals nothing).

In any case, please do not interpret the above as "approval" for version 1. I think that it's a VERY BAD idea, and strongly advocate for version 2.


Value of “counter” when decrypting AES in CTR mode?

With a 4 byte counter, it is a representation of a 32-bit unsigned integer. Since the counter increments from 0, there is no need to store it on a per message basis. This then becomes an implementation issue.

A smart AES-CTR implementation would accept ANY initial counter/nonce value, and simply 0-pad it to the desired length. If we supply the cipher only 12 bytes, it would be starting with an initial counter of 0. If we supply 16 bytes, the last 4 would be the start counter (which could be 0).

For storage and transmission of the data stream is outside the scope of the cipher, and the length of IV is up to the implementer. Applications that require a new key for each message may not even store the nonce, and instead start from an all 0 IV every time. 4 bytes is not a lot, so if storage is available, storing the entire 16B counter/nonce value would probably make the most sense. I would assume the majority of applications looking for compatibility would store the whole thing, while those that use a fixed nonce length and do not require compatibility store only the nonce.

Any application that stores the counter along with the nonce would store it in a manner where it would be correct for the first ciphertext block (block 0), it would not store the last counter used during encryption (block n). Hence the term, initial value. During decryption, the keystream generation is seekable by supplying the required block number as the initial counter of the IV.


First, 40 = 3*13 + 1

So, we have found 1 in the first step.
Then I can write 1 as following:

1 = 40 - 3*13 and this is equivalent to

1 = 40 - 13*3. 40 is equivalent to 0 mod40.

1 = -13*3. Here we get the inverse of 3 as -13 which is equivalent to 27.


RSA How to find the private key to a given public key when n doesn't consist of two primes?

I also know $\phi(n)=(p-1)(q-1)$

This actually only holds if $n=pq$ and if $p$ and $q$ are both primes.

When $n$ doesn't factor as nicely you'll need the more general definition of $\phi(n)$ which can be computed from the following three axioms (given the prime factorization of $n$):

If $\gcd(n,m)=1$ for any $n,m$ then $\phi(n\cdot m)=\phi(n)\phi(m)$
If $p$ is prime and $k\geq 1$ then $\phi(p^k)=p^{k-1}(p-1)$

So in your case $$\phi(120)=\phi(2^3\cdot 3\cdot 5)=\phi(2^3)\phi(3)\phi(5)=(2^2\cdot1)\cdot2\cdot4=32$$

  does multi-prime RSA make any sense in practical use?

Yes, using more than two primes can make sense if you use the chinese remainder theorem (CRT) which yields a speed-up of $k^2/4$ for $k$ primes compared to using only $k=2$. See fgrieu's excellent answer for a discussion of why one wants that and what one has to look out for when actually deploying multi-prime RSA and the table in DW's answer to the same question for an overview of how many primes to use for each modulus size.


Forget the Mersenne Twister and xorshift; maybe CryptMT is secure but it has received very little scrutiny since it was rejected from the eSTREAM portfolio a decade ago.  Cryptography is rife with good pseudorandom number generators, like ChaCha: if you pick the seed uniformly at random, the attacker has no hope of distinguishing the output from uniform random, and the world has high confidence in this state of affairs because it has been subjected to heavy scrutiny and there are trillions of euros of economic value protected by ChaCha in HTTPS around the world.

If you have measured performance, and you have profiled, and you have confirmed that a lot of time is spent in ChaCha, and you are confident that this will never be security-relevant—in particular, if you can quantify the statistical tests you need to defeat and argue that smarter statistical tests will never be relevant—then maybe you will have a reason to look elsewhere.  But the first thing you can do with ChaCha is tune down the number of rounds from the default ChaCha20 to the cheaper ChaCha12 or even cheaper ChaCha8.

Update, for question's addendum:

If the adversary can control the seed, then even if you used a random oracle for the PRNG (which is the strongest possible model—not attained by ChaCha but a reasonable model for, say, SHAKE128), the adversary can spend an expected $t$ trials finding a seed with a property that occurs only $1/t$ of the time, like $t = 2^n$ trials to find a seed under which the first $n$ bits of output are all zero.  No amount of cryptography can help you against this.

But if the adversary can't control the seed, the property you want—nonsingular matrices with high probability—is essentially guaranteed with any cryptographic PRNG.  If it weren't, then the putative cryptographic PRNG would be astonishingly bad, because a very simple test—generate a matrix and test whether it's nonsingular—would serve as an attack against the PRNG that breaks it without even knowing how the PRNG is designed!


Is a known plaintext, ciphertext, and public-key a viable attack on RSA?

No matter how bad a protocol built on top of RSA is, there is no known risk that a private key leaks from valid plaintext/ciphertext pairs, even if the adversary chooses plaintext or ciphertext; that's one of RSA's virtues. Thus to the question is it possible with this information for Cindy to find $pri_A$ we can answer: as far as we know, no; and more, Cindy can not find an equivalent to  $pri_A$.

More precisely: even with access to an oracle accepting any $x$ and answering with $x^d\bmod N$, a computationally bound adversary can not (as far as we know):

factor $N$;
or otherwise compute any of the several equivalent private exponents $d$ or private keys;
or compute $x^d\bmod N$ for some random $x$ submitted to the adversary after access to the oracle has been denied.

That does not answer if Cindy can decrypt message 2 or otherwise find $n_A$ (which was not asked :-).

It is now asked if Cindy can find $n_A$. The answer is yes, at least in some setup matching the question. To justify that claim, I'll explain one such a setup, and how Cindy proceeds.

Assume that:

$En_{pub}$ and $En_{pri}$ are the public (encryption) and private (decryption) operations of textbook RSA;
the modulus in the public keys of Alice and Bob have the same bit size $m$;
the random $n_A$ and $n_B$ have (at most) fixed bit size $r$, with $2\cdot r<m$;
at step 2., $n_B,n_A$ designates the integer corresponding to the concatenation of the $r$-bit strings representing $n_B$ and $n_A$, using little-endian convention;
Bob verifies that applying $En_{priv_B}$ to the cryptogram he obtained at step 1. yields an alleged $n_A$ of at most $r$ bits, which he proceeds to use during step 2.;
Alice verifies that applying $En_{priv_A}$ to the cryptogram she obtained at step 2. yields an alleged $n_B,n_A$ of at most $2\cdot r$ bits, from which she extracts $n_B$ that she proceeds to use during step 3.;
Cindy can play the role of Bob with respect to Alice, and of Alice with respect to Bob, and further Cindy can persuade Bob to engage in a protocol where Bob acts just as Alice does (e.g. because Alice and Bob use the same program and parameters save for the value of their public key pairs, and Cindy persuades Bob to use his program to establish a session key with Alice in the manner Alice uses her program to establish a session key with Bob).

Cindy does the following:

Impersonating as Bob to Alice in a protocol initiated by Alice, Cindy gets the cryptogram $En_{pub_B}(n_A)$ generated by Alice at step 1;
Impersonating as Alice to Bob in another protocol this time initiated by Bob, she gets (and ignores) the cryptogram generated by Bob at step 1, then passes the aforementioned $En_{pub_B}(n_A)$ as the cryptogram allegedly generated by Alice for Bob at step 2. of that other protocol;
In preparation of step 3. of that other protocol, Bob applies $En_{priv_B}$ to that cryptogram, yielding $n_A$;
that $n_A$ is just the same as $n_A,0$ that Bob would legitimately receive at that step should he have chosen his random number as $0$ in the first step of that other protocol (which he likely did not);
as nothing in the protocol asks Bob to check that the random he has chosen appears in what he obtained, Bob dutifully compute $En_{priv_B}(n_A)$, and sends it to what he believes is Alice, and in reality is Cindy;
Cindy persuades Bob to start over, this time in a protocol where Bob acts as Alice expects Bob to act;
Cindy passes $En_{pub_B}(n_A)$ to Bob as the cryptogram of the first step of that new protocol, as if it was from Alice (which it was in the original protocol started by Alice, which meanwhile is still waiting for Bob);
from then on, Cindy let Bob and Alice communicate normally;
Cindy has $En_{priv_B}(n_A)$ (obtained from Bob at step 3 of the fake instance of the protocol), applies $En_{pub_B}$ to that, and now has $n_A$ in the protocol now being used by Alice and Bob;
Cindy has $En_{priv_A}(n_B)$ (obtained from Alice at step 3 of the real instance of the protocol), and as noted in the question applies $En_{pub_A}$ to that, obtaining $n_B$ in the protocol now being used by Alice and Bob;
Cindy can thus obtain the session key $n_A\oplus n_B$.

That attack can sometime be adapted to big-endian conventions (unless I err, at least when the public exponent $e$ is such that $3^e<2^r$; thus with $m=2048$, $r=512$, $e=257$ or less).

Towards turning that protocol into something safe, we are missing:

A check before step 3. by Alice (and every legitimate party performing her role), that the random $n_A$ she generated in step 1. is found by deciphering with her private key the cryptogram received in step 2., allegedly from Bob;
An additional step 4. where Bob (and every legitimate party performing his role) checks that the random $n_B$ he generated in step 2. is indeed found by verifying, with Alice's public key, the cryptogram received in step 3., allegedly from her;
Forward secrecy, that is insurance that past session keys do not leak should one of Alice's or Bob's private key leak at some point in time. One technique towards that goal, which more generally avoids that the authentication step 3. turns into a decryption oracle (that's how the above attack could be outlined), is to split $n_A$ and $n_B$ into two parts: one used only to build the session key, another used for authentication purposes.
A proper encryption at steps 1. and 2., rather than textbook RSA;
A proper signature (possibly with message recovery) at step 3, rather than textbook RSA.

It is left as an exercise to the reader to exhibit attacks working with the first two tweaks alone (that's trivial unless $r\cdot e\gg m$ holds, but I fear there could be other cases).


I believe that the purpose of performing key evolution after the public key exchange and authenticated encryption is to provide forward secrecy. While generating and exchanging keys there are two security objectives. First, partial send deniability, which is provided by the public key exchange and authenticated encryption. Second, the forward and backward secrecy, provided by the key evolution.


Your calculation is broken.

First as pointed out correctly the expected run-time of GNFS (general number field sieve) is: $$\text{O}\left(\exp\left[\left(\sqrt[3]{64/9}+\text{O}\left(1\right)\right)\cdot \sqrt[3]{\ln n}\cdot (\ln \ln n)^{2/3}\right]\right).$$

So next you can't just set these $\text{O}$s equal, as $\text{O}\left(f\left(x\right)\right)$ means $\text{O}\left(f\left(x\right)\right)< kf\left(x\right)$ which means this is an asymptotic upper bound meaning you need some reference point to find out the "$k$".

Now you'd need some way of comparing the "strengths" of the algorithms. In the paper of Lenstra and Verheul this is done using a reasonable recent attack on the cryptosystems, yielding the information that 1024 / 512 bit RSA takes needs X MIPS-Years and breaking 128-bit ECC takes Y MIPS-Years. Now as you know the growth functions you can calculate how the effort grows to obtain the effort you want to meet. This effort can be set equal to get a complex relation, which can only be solved numerically.

First data point: 512-bit number needs $10^4$ MIPS-Years.
Second data point: 108-bit attacked in $8\cdot 10^6$ MIPS-Years.

Formulas:

\begin{array}{lcr}
E_{\text{RSA}}\left[2^{512}\right]={10}^4 & \Longrightarrow & \frac{E_{\text{RSA}}\left[2^x\right]}{E_{\text{RSA}}\left[2^{512}\right]}=\frac{X}{{10}^4} \\
E_{\text{ECC}}\left[2^{{108}}\right]=8 \cdot {10}^6 & \Longrightarrow & \frac{E_{\text{ECC}}[2^y]}{E_{\text{ECC}}[2^{108}]}= \frac{X}{(8\cdot {10}^6)} \\
\end{array}

Solving this for $X$ yields
$$\frac{(8\cdot {10}^6)\cdot E_{\text{ECC}}\left[2^y\right]}{E_{\text{ECC}}\left[2^{108}\right]}=\frac{10^4 E_{\text{RSA}}\left[2^x\right]}{E_{\text{RSA}}\left[2^{512}\right]},$$
where $E_X\left[Y\right]$ denotes the effort required to attack the number $Y$ of scheme $X$ in MIPS-Years.

For $E_{\text{ECC}}\left[2^x\right]$ this is defined: $E_{\text{ECC}}\left[2^x\right]=2^{x/2}$ and for RSA on simply inserts $2^y$ into the formula of paragraph 2 (without the $\text{O}$).

My calculations yielded a 168-bit EC-key for 2048-bit RSA key, which is correct according to the Lenstra and Verheul paper if you want to compare now. They also consider comparing with "cryptanalytic progress for ECC enabled" yielding ~200 bits.


defaultCiphers = ['RC4'] - is this acceptable? I've heard that RC4 is broken.

About RC4 vulnerabilities in general, see e.g. Google is using RC4, but isn't RC4 considered unsafe?

RC4 can be secure when you discard (enough of) the beginning of the keystream or use a new key each session. Since node.js calls into OpenSSL, I don't think it does the former and can't see it done in secure-peer either.

From a look at the secure-peer source, it seems like they use Diffie-Hellman to get a shared secret and use that to derive the RC4 key and IV. That is should be safe, but I could be reading it wrong.

To test, you could try printing secret before this line:

var encrypt = crypto.createCipher(cipher, secret);

If it's different each time (for the same pair of peers), it's probably fine. Otherwise, there may be cause for concern.

  Are my example RSA keys flawed?

They certainly are now that you published them :)

But, no, probably not. RSA keys are stored in one of several formats that have some leading and trailing data that is similar for keys made using the same implementation.

The keys have format and version tags.
They may have information regarding whether the key is stored encrypted and with what algorithm, presumably the same.
The public key exponent is usually chosen as e.g. 65537 for all keys.


Construct IND-CPA secure encryption scheme by combining two given schemes

The first remark is that the cryptosystems are used with independent keys. This is important, otherwise it is usually very hard to prove anything.

The simple solution

Now, the simple solution is, as is mentioned in the comment and the linked question, is to secret-share your message into two shares and encrypt each share separately. The final ciphertext consists of these two ciphertexts. (This can also be phrased in terms of a "one-time-pad" encryption, but it is better to think about it as a secret sharing, since it is then trivial to generalize to the case where you have more than two cryptosystems.)

The proof strategy is straight-forward. In order to learn anything about the message, an adversary needs (the same parts of) both shares. If at least one of the cryptosystems are IND-CPA-secure, the adversary can learn nothing about at least one of the shares. IND-CPA-security follows.

A proof based on games would probably first use real-or-random (RoR-CPA, equivalent to IND-CPA) for the secure encryption scheme to encrypt a random string instead of the secret share. Once this is done, the properties of the secret sharing guarantees that the adversary cannot learn anything about the message.

As for secret sharing, the simplest is usually the best. If your message is $m$, choose a random string $r$ of the same length. The random string is your first share. Then compute the xor of $m$ and $r$, this is the second share. (This generalizes to more shares in the obvious way by choosing more random strings.)

Composition

A more complicated thing happens if you try to compose the cryptosystems in the sense that you first encrypt the message with one system, and then encrypt the resulting ciphertext with the other system.

If you encrypt with the secure system first (the importance of being first!), everything is ok. Anything the second encryption does, an adversary could have done, so the second encryption cannot destroy the secure inner encryption.

What about if you encrypt with an insecure system first? The intuition is that the outer system (which is now secure) should hide the insecure ciphertext, which would then make the composition secure. But this is not true, and the problem with your intuition is that a cryptosystem hides the message only up to message length. What can happen is that the insecure cryptosystem produces ciphertexts whose length depends on the message. That length (which contains information about the message) can leak through the secure cryptosystem and result in an insecure construction.

However, if you restrict your attention to some sort of "length-preserving" cryptosystems, where the ciphertext length is a function of the message length only, not on the exact content of the message, then your intution should work again.


Given occasional LFSR samples can the next sample be computed?

It is very easy to predict and should not be used as a main cryptographic component on its own.

Firstly, many $k-$decimations $s_{kt}$ of LFSR sequences (those with $gcd(k,2^n-1)=1$) are shifted LFSR sequences themselves so this can be used for prediction.

If you can find a template $T=\{0,t_1,\ldots,t_{n-1}\}$ (with $0<t_1<t_2<\cdots<t_{n-1}$ such that the samples you have of the LFSR sequence $(s_t)$ cover $n+1$ shifts of this template you can set up a linear system and solve for the recurrence. In fact assuming $n=3$ one can (Berlekamp Massey is more efficient of course, this would need Gaussian elimination) set up the system

$$c_0 x_t + c_1 x_{t+1} + c_2 x_{t+2}=x_{t+3}\\
c_0 x_{t+1} + c_1 x_{t+2} + c_2 x_{t+3}=x_{t+4}\\
c_0 x_{t+2} + c_1 x_{t+3} + c_2 x_{t+4}=x_{t+5}$$

and solve for the LFSR coefficients $c_i$. For the template I mentioned, a similar system needs to be solved. This case is the template $T=\{0,1,2\}$ with shifts also $\{0,1,2\}.$


Matsui's paper on Linear Cryptanalysis of DES

Confusion is from notation differences between standard DES notation and Matsui's notation. After reading this: Matsui's Linear attack on DES P box
and make some rearrangements I can find the solution.


Differences between NewHope-CPA-KEM and NewHope-CCA-KEM

Well, it turns out that a straight-forward implementation of LWE key exchanges is vulnerable to chosen ciphertext attacks, in the case that one side reuses the same private value $a$ multiple times.

In this straight-forward implementation, Alice generates a private vector $a$, and sends his key share $a M + \epsilon$.  Then, when Bob receives this key share, he generates a private vector $b$ and sends his key share $b M + \epsilon'$ and a reconciliation vector.  This reconciliation vector is needed because the vectors that both sides compute won't be precisely the same (because of the error vectors $\epsilon, \epsilon'$), and advise Alice how to do the rounding.

The best known attack involves the attacker sending incorrect bits in the reconciliation vector, which (over a number of exchanges) can yield individual values from the $a$ vector.

In the CPA version, they assume that you'll never reuse the same public value over multiple exchanges, and so this attack is irrelevant.

In the CCA version, they can't make this assumption.  What NewHope team has decided to do is to use to have Bob generate his key share from a seed in a deterministic way and encrypt that seed as a part of the ciphertext, and so when Alice gets it, she can decrypt the seed and then regenerate what Bob's key share should be (based on the seed), and see if that's the value she got; this prevents attacks (like the above) which are based on sending illegitimate keyshares.

Of course, all this extra checking slows things down; that's why the CCA version is slower.


Is there a way to do fair exchange between two parties who don't trust each other?

I think what you want to look at is "fair exchange".  There's a giant catalog of protocols for fair exchange.  They've been designed for doing exactly what (I think) you want.

See, e.g.,

https://en.wikipedia.org/wiki/Multi_party_fair_exchange_protocol
Alice trusts Bob only when Bob trusts Alice

Some fair exchange protocols require a third party who Alice and Bob trust, and involve the third party in the protocol.  Others (called optimistic fair exchange) require that there be a trusted third party, but normally the third party does not have to be involved in any way -- the third party only gets involved to settle disputes, if something goes wrong.  Still others try to avoid any third party (e.g., gradual fair exchange); they're not perfect, but they try to ensure that if Alice can learn Bob's message with some amount of effort, then Bob can learn Alice's messages with not too much more effort.

To learn more about fair exchange, do a literature search on fair exchange.  There are lots of research papers on this topic.


Does Format Preserving Encryption have significant advantages over a randomly generated lookup table?

any other considerations?

Yes.

In many common use cases the mapping table needs to be retained. That map changes each time a number is added; that's a backup / continuity of service headache.
The map is security-sensitive: it contains all the clear phone numbers, and information which (combined with other information) allows getting back to users.
The map can be large (at least about twice as large as the numbers themselves); that's a (perhaps minor) storage issue.
When the table grows large, there will be collisions in the mapping table, that's a special case which must be handled, and tested.
Timing attack on the map search code has the potential to leak information (that's also true of some FPE implementations, but proper FPE is less likely to leak something meaningful; in particular FPE won't leak if the creation of the entry was recent, which can happen with a map).
FPE's performance is predictable, when some map implementation have no specified worst-case performance.
FPE allows efficient implementation of direct and reverse map, when not all map implementations allow that.

Bottom line: encryption is desirable there. FPE is useful only if size or interoperability is a concern.


Clarification

  I'm wondering whether there exists an encoding/hashing/encryption scheme whereby the original string can always be derived in its entirety given the entire encoded/hashed/encrypted string, and nothing else (no key/password). But also, no portion of the original string can be derived given any portion of the encoded/hashed/encrypted string.

I am assuming that "no portion of the original string can be derived given any portion of the encoded/hashed/encrypted string" means "no portion of the original string can be derived given anything less than the entire encoded/hashed/encrypted string", otherwise the question would be self-contradictory.

Answer

It sounds like you are looking for a permutation. A permutation is an invertible transformation on a fixed-size set of blocks. If your input is larger, the/an All-Or-Nothing Transform may be useful. The OAEP mentioned by @DannyNiu is an example of an AONT.

For example, many block ciphers are built by interleaving applications of a permutation with the addition of secret key material. The permutation provides diffusion, which ensures that if you modify any part of the output then attempt to invert it, you end up back at a completely different input.

If you simply strip the key addition portion from a block cipher, it should also do what you're asking. For example, AES consists of subBytes, mixColumns, shiftRows, and addRoundKey. If you were to omit the addRoundkey operation, you would be left with a fixed permutation that provides the required avalanche effect and some degree of unpredictability. Another example of a permutation is keccak-f, which does the mixing for the SHA3 algorithm.

A key-less permutation does not provide encryption

Note that such a construction with no key is no longer providing encryption, as it is not possible to provide confidentiality of the message without some kind of secrecy, which is what the key provides. If anyone who has an input message can compute an output "ciphertext", or anyone who has an output "ciphertext" can invert it to the input message, then clearly confidentiality of the input cannot be achieved.

You tagged this question with "encoding", so perhaps confidentiality is not required in your use case. You would need to establish what you need this construction for and whether or not this is an issue.


Enumerating the bias of NIST and Pearson randomness extractors

If $M$ is a uniform random $l \times k$ matrix, then the random function $H\colon x \mapsto M \cdot x$ is a 2-universal hash family[1] (paywall-free: (a), (b)).  This means that for any $l$-bit strings $x$ and $y$, $\Pr[H(x) = H(y)] \leq 1/2^k$.

If $H\colon \{0,1\}^l \to \{0,1\}^k$ is a 2-universal hash family and the random variable $X \in \{0,1\}^l$ has min-entropy $H_\infty[X] = s\cdot l$, then $H(X)$ has total variation distance at most $\epsilon$ from the uniform distribution on $k$ bits, where $\epsilon = 2^{-(s l - k)/2}$.  This is the leftover hash lemma.  (Sometimes it is phrased instead as: if you want TVD $\epsilon$ from uniform, then you must pick $k \leq s\cdot l - \log(1/\epsilon^2)$.)

The total variation distance between two discrete random variables $R$ and $S$ is $$\frac 1 2 \sum_x |\Pr[R = x] - \Pr[S = x]|.$$

What does this all mean?

We are considering a probabilistic model.  This is a model of an uncertain state of knowledge, such as the adversary's, about the specific values of $H$ and $X$ in this model, but we can quantify the uncertainty of this knowledge by giving numeric weights to each of the possible values:

$H$ has a probability distribution on $l \cdot k$ matrices that is uniform.

This means for any specific value $h$ that $H$ could take on, $\Pr[H = h] = 1/(l \cdot k)$, since there are $l \cdot k$ distinct $l \times k$ matrices.

One possible matrix is the matrix that returns the first $k$ bits of an $l$-bit string.  For this particular choice of matrix, the min-entropy of the result depends entirely on the first $k$ bits of the input and not at all on the last $l - k$ bits.
Another possible matrix is the all-zero matrix, in which case $H(x) = 0$ for all $x$.  For this particular choice of matrix, the min-entropy of the result is always exactly zero!  But it is only with probability $1/2^{l \cdot k}$ that $H$ is the all-zero matrix.
The point is that no particular matrix makes a randomness extractor; it is rather a probability distribution on matrices that does.

You could pick a value for $H$ by flipping a coin $l \cdot k$ times and filling in the matrix entries with the outcomes.
$H$ is not uniformly distributed in all functions from $l$-bit strings to $k$-bit strings: there are many functions that $H$ cannot be, namely those that do not have matrix representations.  For example, $H$ cannot be SHAKE128.

$X$ has a probability distribution that has min-entropy $s \cdot l$.

This means that the maximum probability of any specific value that $X$ could be is $2^{-s\cdot l}$; that is, $-\max_x \log_2 \Pr[X = x] = s \cdot l$.

Given this state of knowledge about $H$ and $X$, the two theorems let us conclude that our state of knowledge about the output $H(X)$, a $k$-bit string, is a probability distribution with at most $\epsilon$ in total variation distance from the uniform distribution.  That is, $$\frac{1}{2}\sum_y \bigl|\Pr[H(X) = y] - 1/2^k\bigr| \leq 2^{-(s l - k)/2}.$$

The total variation distance between two random variables $R$ and $S$ is relevant to usual theorems in cryptography because it turns out to be a bound on the advantage of a random algorithm $A$ at distinguishing them, $|\Pr[A(R)] - \Pr[A(S)]|$.  (There are other metrics of probability distributions too, such as KL divergence (or symmetrized KL divergence to get a proper metric), Hellinger distance, etc.  Which one you use depends on what your needs are.)  So this almost says something useful for cryptography.

But what if the adversary knows $H$?  Then the conclusion goes out the window!  In the paper you cited, the matrix $M$ is a pregenerated constant.  So either,

by Kerckhoffs' principle, you should assume that the adversary knows $M$, i.e. $M$ is public, so it cannot satisfy the conditions of the leftover hash lemma and it is meaningless to use with a randomness extractor; or
you already have a sufficiently large uniform random secret, namely $M$, that you can use with a standard cryptography like ChaCha or SHA-3 to expand into as many keys as you need; or
you don't believe in cryptography, but then you probably wouldn't be hanging around here.

In other words, as this paper applies randomness extractors, either it fails to satisfy the premises of the theorem ($H$ is secret), or it does satisfy the premises of the theorem which makes the conclusion unnecessary for cryptography.

On to the specific questions you asked:

A: What if we choose $H$ to be a fixed function, yet instead of choosing a fixed matrix we choose a fixed ‘cryptographic hash function’ like SHAKE128?  It is hard to say, because unlike universal hash families, cryptographic hash functions are designed not to have any interesting properties like linearity of matrix multiplication.

Suppose we model it as a uniform random function from $l$-bit strings to $k$-bit strings.  For every distinct input $x$, the output $H(x)$ is an independent uniform random $k$-bit string—every possible output is equiprobable.  This model is much stronger than a randomness extractor in some sense even though the adversary has access to it as a public oracle, and this model, like all models, is wrong, but some models are useful.

Suppose $X$ has $s \cdot l$ bits of min-entropy.  What is the expected min-entropy of $H(X)$, over uniform random choice of $H$?  To make a conservative estimate of this, let's say $X$ is really just a uniform random $\lambda = \lfloor s \cdot l \rfloor$-bit string.  For any fixed function $h$, the min-entropy of $h(X)$ is $-\max_y \log_2 \Pr[h(X) = y]$.  Note that $\Pr[h(X) = y] \leq (C(h) + 1)/2^k$, where $C(h)$ is the number of possible $k$-bit strings that $h$ does not reach, since in the worst case of min-entropy, there is a single output that is reached $C(h) + 1$ times instead.  Consequently, $$-\max_y \log_2 \Pr[h(X) = y] \geq -\log_2 (C(h) + 1)/2^k = k - \log_2 (C(h) + 1).$$  $\log_2$ is concave, so $E[\log_2 (C(H) + 1)] \leq \log_2 (E[C(H)] + 1)$.  What's $E[C(H)]$?  First, the probability that we do not reach a particular output $y$ is

\begin{align*}
 \Pr[\lnot\exists x. H(x) = y]
 &= \Pr[\forall x. H(x) \ne y] \\
 &= \prod_x \Pr[H(x) \ne y] \\
 &= \prod_x (1 - \Pr[H(x) = y]) \\
 &= \prod_x (1 - 1/2^k) \\
 &= (1 - 1/2^k)^{2^\lambda}.
   \end{align*}

By linearity of expectations, this is also the expected fraction of unreachable outputs, so the expected number of unreachable outputs is $E[C(H)] = 2^k (1 - 1/2^k)^{2^\lambda}$.  When $\lambda \leq k$ this puts an unsatisfying bound on the min-entropy, which happens because to set a hard bound we made an extremely conservative estimate of a colossal collision of all inputs with any collisions into a single output that feels very abused right now.

But $E[C(H)]$ rapidly goes to zero as $\lambda$ increases.  Specifically, for $k \geq 1$, we have $1 - 1/2^k \leq e^{-1/2^k}$, so $$E[C(H)] \leq 2^k e^{-2^\lambda/2^k} = 2^k e^{-2^{\lambda - k}} \leq 2^{k - 2^{\lambda - k}}.$$  Consequently, as long as $\lambda \geq k + \log_2 k$, $E[C(H)] \leq 1$, so the min-entropy is at least $k - \log_2 (E[C(H)] + 1) \geq k - 1$.

For a distribution on $k$-bit strings with min-entropy $k - \delta$, where $\delta = \log_2 (E[C(H)] + 1)$, can we set an upper bound on the total variation distance from uniform?  Suppose for simplicity that $N = 2^{k - \delta}$ is an integer; the greatest TVD is attained by assigning probability $1/N$ to $N$ of the $k$-bit strings, and probability $0$ to the remaining $2^k - N$, so that the TVD is bounded by

\begin{multline}
 \varepsilon
 = \frac 1 2 N \biggl|\frac{1}N - \frac{1}{2^k}\biggr| + \frac 1 2 (2^k - N) \biggl|0 - \frac{1}{2^k}\biggr| \\
 = \frac 1 2 N \frac{2^k - N}{N 2^k} + \frac 1 2 \cdot \frac{2^k - N}{2^k}
 = \frac 1 2 \cdot \frac{2^k - N}{2^k} + \frac 1 2 \cdot \frac{2^k - N}{2^k} \\
 = \frac{2^k - N}{2^k}
 = \frac{2^k - 2^{k - \delta}}{2^k}
 = 1 - 2^{-\delta}.
   \end{multline}

For $\delta = 1$, the the TVD is bounded by $\varepsilon = 1 - 2^{-1} = 1/2$, but the bound $\varepsilon = 1 - 2^{-\delta}$ rapidly approaches zero as $\delta \to 0$.

A more practical way to put it is: The security conjecture of, e.g., SHAKE128 is that there is no better attack at guessing $X$ given $\operatorname{SHAKE128-}\!k(X)$ than a generic search through all possible values of $X$, whose expected cost is at least $2^{H_\infty[X]}/2$ trials, or $2^k/2$, or $2^{256}/2$, whichever is smaller.

(Of course, if there are $n$ targets $X_1, X_2, \dots, X_n$, the cost to find at least one of them given $\operatorname{SHAKE128-}\!k(X_1),$ $\operatorname{SHAKE128-}\!k(X_2),$ $\dots,$ $\operatorname{SHAKE128-}\!k(X_n)$ is $2^{\min\{256, H_\infty[X_1], \dots\}}/(2n)$ instead, i.e. there is a standard factor of $n$ cost reduction for an $n$-way multi-target attack.  This is why it is a good idea either to use 256-bit seeds $X_i$, or to use a globally unique per-seed salt.)
B: What if we choose $H$ to be a Pearson hash, i.e. CBC mode of a uniform random permutation?  By the standard CBC theorem, algorithm limited to $q$ queries on inputs up to $m$ $b$-bit blocks can't attain better advantage than $mq(mq - 1)/2^{b+1}$ at distinguishing $H$ from a uniform random function, and any algorithm to distinguish the output from uniform random bit strings would serve as an algorithm to distinguish the hash from a uniform random function, so the ‘bias’ (here meaning distinguishing advantage) of the resulting distribution is bounded by $mq(mq - 1)/2^{b + 1}$.

Of course, you need at least about $2^b b - 2^b \log_2 e$ bits to store such a permutation, which rapidly becomes impractical as $b$ exceeds 8, the typical size for what gets called a Pearson hash.  You could accommodate a much larger block $b$ by choosing the permutation to be $\operatorname{AES}_k$ for a uniform random key $k$.  But that's only a minor setback.  Much worse: The whole premise is nonsensical, because however you do this, you need a secret permutation to begin with, which is back to begging the question with a randomness extractor: If you already had a long enough secret, you wouldn't need a randomness extractor or a Pearson hash; if you don't have a long enough secret, you can't use a randomness extractor or a Pearson hash and get anything meaningful out of the use.


Is it possible to break the crypto-system deterministically with the given complexity, or we must allow some error probability?

If we model DES as a random permutation, there is always some probability of either deriving the wrong key, or finding multiple ones.

If we have $n$ plaintext/ciphertext pairs, there is a nonzero probability that there exists a second spurious key that just happens to map each plaintext to the corresponding ciphertext.  If our brute force search stops at the first key it finds, it might stop at the wrong one.  If our brute force search keeps on going after the first key it finds, it'll find the second one (and hence report multiple).

Now, the actual probability of this happening is tiny; if $n=2$, then the probability in your example would be about $2^{-8}$ (which is small, but not neglicable), however if $n=3$ (which the term "moderate" would appear that we have at least this many), the probability drops to about $2^{-72}$.

In addition, attackers typically aren't that concerned about a small probability of failure.  When we protect data, we want to succeed (in this case, be secure) with overwhelming probability; but that's not the case for the attacker...


Dan Boneh's Cryptography lecture - problem with 802.11b

...wouldn't key still get repeated every few hours or so - i.e. you come to the end of the PRG(K)...

This is where you are mistaken. Modern cryptographic PRGs simply do no repeat within any conceivable time frame. That is, starting from a seed, a well-constructed PRG (and this is true even when they are not so well constructed, like RC4) will simply never "come to an end" within our life time. You will have to run it for such a long time that the universe will probably have grown dark before you see it cycling back. Hence, for all practical purposes, cryptographic PRGs never repeat.

However, as noted in the video, this only holds true starting from some initial seed which is held fixed throughout the process. Note that the problem with WEP was that they reused the input (i.e. the seed) to the PRG, it was not because the output cycled around! Once you reuse the seed to a PRG then you will of course see the same output stream.


How to prove that the Permutation cipher is not CPA secure?

If $a_i = c$ for all $i$, then clearly $a_{\pi(i)} = c$ for all $i$ as well, regardless of the permutation $\pi$.

Thus, you can choose your two messages $a$ and $b$ such that, say, $a_i = 0$ and $b_i = 1$ for all $i$.  This will then also be true for their encryptions under any permutation cipher, allowing you to trivially distinguish the encrypted messages with 100% certainty.


Computationaly efficient distinguisher for a PRP generator

a distinguisher is possible with 3 queries if we disregard efficiency. But how can we build an efficient distinguisher?

I'm not sure exactly what you mean by efficient (since $n \approx 2^{27}$ is a small number), but here is a sketch of a possible constructive attack. I'll let you tell me whether this satisfies your idea of efficiency. I figure that if you have enough time to accept a long ($n$ items) output from the oracle, you have time to do the attack I have in mind. To keep notation cleaner, I won't explicitly write the modular reductions in $R[ \alpha \bmod n ]$.

Query twice, to obtain (assuming oracle #2): $V_1[i] = R[ P[1] + Q[j] ]$ and $V_2[i] = R[ P[2] + Q[j] ]$.
Let $\Delta = P[2] - P[1] \bmod n$, which is unknown to the attacker. Still, if $V_1[i] = R[\alpha]$ then $V_2[i] = R[\alpha + \Delta]$. So the function $F$ that maps all $V_1[i]$ to $V_2[i]$ (which the attacker can compute) is a function that maps all $R[\alpha]$ to $R[\alpha + \Delta]$.

I think the cycle structure of $F$ already leads to an attack! For example, if $n$ is prime then $F$ must be a simple cycle. This is because the sequence $\alpha, \alpha+\Delta, \alpha+2\Delta, \ldots$ generates all numbers mod $n$ before repeating (so $F$ visits all positions in $R$ before repeating). But I would guess that under oracle #1, the attacker would get $F$ to be a random involution. So this already gives an attack with reasonable bias, with just 2 queries.

In general, all cycles in $F$ must have cycle length that divides $n$ (in the presence of oracle #2). Again, this seems much less likely to happen in the presence of oracle #1.

OK, but suppose that reasoning doesn't work out for some reason. In that case, make another query. The attacker can compute a new $F$ again now using $\{V_2,V_3\}$ this time instead of $\{V_1, V_2\}$. If we got lucky, and $P[3]-P[2] = \Delta$ (which happens with probability $1/n$), then the attacker will obtain the same $F$ as before! Again I have not worked out the probabilities, but in the presence of oracle #1 this event seems much less likely than probability $1/n$.


Difference between semi-honest and malicious adversary using Ideal Real Model Paradigm

Would you please explain to me why in the security definition of ideal/real model paradigm which is described in the efficient secure two-party protocol book(Hazay, Lindell), the simulator tries to simulate inputs and outputs of a party(in the semi-honest model), but the simulator just tries to simulate outputs and not inputs in the malicious model?

As mentioned in the above comments, the inputs do not need to be simulated because they are given to both the simulator (i.e., the adversary in the ideal world) and the adversary (in the real world).

  Would you please explain the difference between the security definition of idea/real model in the semi-honest and malicious model which is described in that book(page 21 and 25)?

In the semi-honest setting, the parties have to follow the exact prespecified protocol in the real world, which implies that they cannot change their inputs or outputs. Therefore, the simulators only need to generate an indistinguishable view for each party, given the semi-honest party's input and output.

In the malicious setting, each corrupted party can deviate from the protocol, e.g., changing the inputs and outputs, aborting the protocol, etc. To define its security, intuitively we also want to simulate the adversary's view, but such a view cannot be defined in the same way as in the semi-honest setting anymore. In particular, the view depends on the real-world adversary which can change the given inputs and generate whatever outputs. Therefore, the secure two-party computation is defined as the indistinguishability between the outputs (which could be anything, like the adversary's view) of the simulator and the adversary.

FYI, I think Lindell's tutorial is very helpful.


If you have a nonrepeating (but possibly predictable) value, you can convert that into an unpredictable CBC-mode IV at fairly minimal cost.  Here's how:

Prepend the 128 bit nonrepeating value to the message
CBC mode encrypt the (value, message), using any IV that's not correlated to the nonrepeating value (all 0's work)
Use the first 16 bytes of the resulting ciphertext as the 'IV', and the rest of the message as the 'message'; don't send the all 0's IV you actually used.

Surprisingly enough, this works, both in the sense that normal CBC-mode decryption will decrypt the message you sent into the original message, and in the sense that the IV you use is completely unpredictable to anyone who doesn't know the AES key.

CBC mode processes the first block as:

$$C_0 = E_k(IV \oplus P_0)$$

In this case, we have $P_0$ being the nonrepeating value; this remains unrepeated after we xor in the all-0's IV value.  The AES encryption of a value that hasn't been seen before is unpredictable; since $C_0$ is the value we use as our effective IV, we meet the goal.

CBC mode then processes the second block as:

$$C_1 = E_k(C_0 \oplus P_1)$$

Now, $C_0$ is the value we sent as the IV; $P_1$ is the first block of the plaintext message we want to send; this matches up exactly to what we would normally do in CBC mode.

If we continue in the rest of the message, we find that it also matches what normal CBC mode encryption processing would be.


How to measure brute force speed of a computer for a give cipher with given number of keys for second for a given key space

Your question is too broad. What algorithm you mean? Brute-forcing DES is different from brute-forcing AES-256 GCM.

Also if you have some scheme where password is derived using Argon2, then password derivation itself can be essentially slower than the actual encryption.

It depends also on implementation of brute-forcing. Less skilled attacker can try every possible key and will perform the whole sequence of the algorithm that is being brute-forced. Where as skilled attacker will be aware about known attacks on particular algorithm and will implement brute-forcing more efficiently; depending on algorithm this can be a few bits, can be also much more.

Try to formulate your question more precisely. Then you will get more precise answers.


How hard is the DLP in that simple group?

That group embeds in  $F_{\hspace{-0.02 in}p}[i\hspace{.02 in}]$$^{\hspace{.02 in}*}$  via the Möbius transformation given by

$f(x) = \dfrac{x+i}{x-i}$  (and  $\hspace{.04 in}f(\infty) = 1$ ),  and that embedding has a left-inverse

(that is not injective and is not necessarily a homomorphism) which is the

Möbius transformation given by $\;\;\; g(z) \: = \: \dfrac{z+1}{z-1} \cdot i \;\;\;$ (and  $g(1) = \infty$ ).

Their partial-inverse-ness can be used to find the range of that embedding

(namely, that range is the set of fixed-points of that embedding composed with $g$);

solving reveals that it's exactly the points $z$ such that $g(z)$ is in the embedding's domain.

Further solving then gives that for all elements $c$ and $d$ of $F_{\hspace{-0.02 in}p}$,

$g(c\hspace{-0.03 in}+\hspace{-0.03 in}(d\hspace{-0.06 in}\cdot \hspace{-0.05 in}i\hspace{.02 in}))$  is in that embedding's domain if and only if $\;\;\; c^{\hspace{.02 in}2}\hspace{-0.04 in}+d^{\hspace{.02 in}2} \: = \: 1 \;\;\;$.

Therefore your group is efficiently-equivalent to the mod-p circle group.

The latter is an efficiently-decidable subgroup of the multiplicative group of an efficient field,

and that efficient field is a simple quotient of the Gaussian integers,

which is a Unique Factorization Domain whose number of units is small.

Thus, by trying to find the discrete log of both inputs in the subgroup with

respect to the same generator of the whole multiplicative group, one should be

able to attack the subgroup's Discrete Logarithm Problem with index calculus,

using $i$ and non-associate Gaussian primes as the factor base.

For that reason, although I don't know how GNFS works, I'd imagine the hardness of

your group's DLP is at most not much more than for the standard DLP mod primes.

I'm not aware of any faster-than-SNFS DLP algorithms for any

[subgroups whose order has a large prime factor] of multiplicative groups of an efficient field, so in particular, I'm also not aware of any such algorithms for your group.

On the other hand, I also don't know how SNFS works.


Yes it is. It can be formally reduced to the hardness of the decisional square Diffie-Hellman assumption, which states that distinguishing $(g,g^a,g^{a^2})$ from random is hard (this is a well established assumption).
It follows in a relatively simple way from the answer I wrote here to a related question. I can let you work out the details in case you want to play a bit with these reductions. In case you cannot figure out the formal reduction, just ask in the comment and I will elaborate.


Does OpenSSL apply ASN1 encoding to the hash before signing using ECDSA?

No, you do not add the ASN.1 encoding to the hash when generating an ECDSA signature.

There are two reasons for this:

The first is that there is no room, if we select a curve and a hash with equal security.  To be secure against attacks that take $O(2^N)$ time, a curve needs to have a prime that's at least $2N$ bits; to be secure against collision attacks that take $O(2^N)$ time, the hash needs an output that's at least $2N$ bits.  That means that, if we don't add any encoding, the hash just fits into the curve. If we were to add an ASN.1 encoding to the hash, that's mean we'd need to make the curve larger than necessary for security purposes.  Alternatively, we could modulo the result by the curve order to make it fit, however that is effectively the same as adding a constant (which depends on the curve and the hash function) to the hash, which appears a bit pointless.
The second is that there is no reason.  In RSA, the verifier recovers the padded hash value; he could then try to parse the ASN.1 encoding to determine the hash used (and then use that hash to hash the message being verified).  For ECDSA, the verifier doesn't actually recover the padding hash value; instead, he needs to generate the hashed (and padded, if padding is being used) message before he learns anything from the signature.  Hence, the potential gain we get from ASN.1 encoding the hash in RSA isn't there for ECDSA.

In addition, the original stack overflow question doesn't mention ECDSA at all; it strictly talks about RSA.  In the the question you pointed to, it's the question that assumes that ECDSA uses padding; the answer doesn't address that.


Can Bitcoin HD public keys be used for symmetric encryption?

Is this (cryptographically) secure?

That is hard to say without knowing the exact details of the bitcoin protocol (which I would like to understand better, but don't have the time at the moment). Looking at the document you linked to, the public child key is created as $\text{HMAC-SHA512}(Key = c_{par}, Data = ser_P(K_{par}) || ser_{32}(i))$. This value is split in half. One half is turned into a point. That point, plus $K_{par}$ is returned as the public key. The other half is returned as the chain node. Is this the index of which you speak?

The process looks good, but it is hard to say whether or not it is cryptographically secure without knowing details of how the input parameters are chosen. It all comes down to the entropy of those. If they are high entropy, then the output should be high entropy and so it should be "secure" (you haven't actually defined secure, but I'm assuming you mean that an outsider could not guess/figure out the key).

I would strongly recommend, once you have formally specified your protocol, that you work on a security proof. This will likely be done by reducing the security of your protocol to some other (related) protocol. This would be done by assuming an attacker breaks your protocol then showing some horrible impact this would have on the other protocol. The other protocol could be the HD wallet protocols. That would establish that breaking your protocol is at least as hard as breaking HD wallet.

  Would it be better to hash the public keys before using them as an encryption key?

As the public key is a point on an elliptic curve, I would say yes. In particular, owlstead's recommendation of a key derivation function is on the right track.

  Are there any resources about doing something similar I can use for research?

Not that I am aware of.

  Anything blindingly obvious that I'm missing?

Well, if there is, I am missing it too. The best way to find out about this at this point would be to write up a short white paper on the idea and present it to people familiar with the areas (both bitcoin and cryptography). You could do this by sending it directly to researchers and getting their thoughts, publishing it in a workshop of some sort, etc. Also, make it available online somewhere (e.g., ePrint) and comment on here with a link (I'll definitely take a look). Your white paper should review enough of the basics of the bitcoin protocol and the HD wallet protocol so as to be self-sufficient. This should be a good exercise as I saw on your profile that you are a graduate student.


Benefit of capitalization when using Diceware passphrases?

Yes, randomly choosing whether or not to capitalize the first word in the passphrase doubles the number of possible passphrases, and thus also doubles the average time needed for a brute force attacker to guess the correct passphrase.

Note that doubling the average time needed to crack the passphrase is equivalent to increasing the entropy of the passphrase by one bit.  In comparison, adding one more word to your Diceware passphrase will increase its entropy by 5 log2(6) ≈ 12.9 bits, multiplying the average time needed to crack it by 65 = 7776.

Of course, there are several other capitalization choices one could more or less reasonably make, such as:

all lower case,
ALL UPPER CASE,
Title Case (First Letter Of Every Word Capitalized),
LeEt CaSe (EvErY sEcOnD lEtTeR cApItAlIzEd),
reversE titlE caseE,
tITLE cASE wITH cAPS lOCK oN,
Only first letter capitalized,
oNLY FIRST LETTER IN LOWER CASE, etc.

Choosing randomly from among, say, the eight capitalization options above would make the passphrase eight times harder to guess, increasing its entropy by log2(8) = 3 bits.  You could also randomly decide e.g. whether or not to use spaces between the words in your passphrase, again doubling the average time to guess it and increasing the entropy by one bit.  And including the possibility of using, say, hyphens or periods or underscores instead of the spaces would add a bit or two more entropy yet.

That's still a lot less than just making the passphrase one word longer, though.  To achieve a comparable increase in entropy, you've have to literally choose the capitalization and punctuation of your passphrase randomly from among almost eight thousand options.  Good luck remembering that!


Is it safe to use a random numbers instead of a counter in ChaCha20?

I am using here the description and terminology from RFC 7539.

ChaCha20 is meant to process messages, each message being a sequence of bytes; ChaCha20 produces pseudorandom blocks of 64 bytes each, which are XORed with the data to encrypted or decrypt. The crucial security property is that all invocations of the ChaCha20 block function for a given key use distinct values for what is injected in state words 12 to 15.

In the description of RFC 7539, state word 12 receives a counter value, which is over 32 bits and incremented for each block, while state words 13 to 15 receive a 96-bit "nonce" which is fixed for a given message, but different for each message. The idea is that, for a given key:

Each message works over a new nonce value (96 bits), such that no two messages share the same nonce.
Within a message, different blocks use the same nonce but a different counter values.
No message may contain more than $2^{32}$ blocks (i.e. close to 275 gigabytes, which "ought to be enough").

Nonce values themselves can be generated in any way that offers the unicity guarantee with sufficient probability. If you generate nonce values randomly (with a uniform generator), then the risk of reuse is low as long as you do not produce too many messages; with $n$ messages, probability of reuse is about $n^2/2^{96}$. In other words, if you do not send more than 8 billion messages with random 96-bit nonces and the same key, then the risk of reusing the same nonce is less than one in a billion.

Take care that all of the above is for reusing a nonce value with the same key. If two messages use the same nonce+counter but with different keys, then there is no security issue.

In a P2P network, conceptually, messages are encrypted with keys derived from some sort of key exchange (e.g. ECDH), and each node must remember the key to use for each of its neighbours; it should not be too much a hassle to remember a counter value along with each such key, in particular if these keys are ephemeral, i.e. only in RAM.


How small are we talking about when defining the small public/private key exponent

Exponentiation by squaring takes time approximately proportional to the number of bits in the exponent. 3 has been used but allows attacks on some weak padding schemes. 65537 ($=2^{16}+1$) is the one used widely in practice.

Cf. Impacts of not using RSA exponent of 65537


The following appears in the linked wikipedia article (emphasis mine):

  The Hierocrypt ciphers use a nested substitution-permutation network (SPN) structure. Each round consists of parallel applications of a transformation called the XS-box, followed by a linear diffusion operation. The final half-round replaces the diffusion with a simple post-whitening. The XS-box, which is shared by the two algorithms, is itself an SPN, consisting of a subkey XOR, an S-box lookup, a linear diffusion, another subkey XOR, and another S-box lookup. The diffusion operations use two MDS matrices, and there is a single 8×8-bit S-box.

So the final round operates differently, opting to replace the diffusion step with an add-key step.

It is not uncommon for block ciphers to skip the final linear diffusion operation, because it does not appear to improve security to include it. For example, AES skips the final diffusion step also. But they don't refer to it as a half round.

Salsa20

Salsa20 (and ChaCha) both use a double-round, which is counted as 1 round. So half-rounds appear again here in this context (scroll to FAQ), due to how the rounds are structured and counted.


What is the Bilinear-map accumulator disadvantage

I will list two disadvantages that come to mind.

A bilinear accumulator requires a public parameter which is linear in size, which means you need to have an upper bound on the number of data elements you would commit to the accumulator. The RSA accumulator requires a public parameter which is constant-sized.
A bilinear accumulator does not allow dynamic updates. If you have an accumulated digest $$A = g_1^{\prod\limits_{i=1}^N (s+d_i)}\;\;\; (s = \text{ the trapdoor}) $$ and need to insert a new element $d$, you would need to update the accumulated digest to $A^{s+d} = A^s*A^d$. But in order to compute $A^s$ without the trapdoor, you would need to know the coefficients of the polynomial $f(X):=\prod\limits_{i=1}^N (X+d_i)$. You would then compute the coefficients of $Xf(X)$ and use those to compute $A^s$. Thus, inserting a single element has a run time of $O(N)$.


An interactive or non-interactive protocol is said to be sound for a language $\mathcal{L}$ if it is "hard" for a (malicious) prover $\textsf{P}$ to convince a verifier $\textsf{V}$ of a statement $I\not\in\mathcal{L}$. Depending on how "hard" it actually is for $\textsf{P}$ to cheat, we either get a (interactive or non-interactive) proof system (when $\textsf{P}$ is computationally unbounded) or an argument system (when $\textsf{P}$ is computationally bounded).
The Fiat-Shamir transform compiles an interactive protocol into a non-interactive protocol by, roughly-speaking, replacing the verifier $\textsf{V}$ with a hash function $H$. To be more precise, the prover computes -- by itself -- the $i$-th verifier message $\beta_i$ by hashing the transcript so far (which consists of the statement $I$, the prover messages $\alpha_i$s from the previous rounds and the previous values of $\beta_i$s): see the figure below (which is taken from here). In the random oracle model (ROM), the hash function $H$ is modelled as a random oracle, i.e., a random function accesible to all parties via an oracle.

The Fiat-Shamir transform is said to be "sound", if it "preserves" the soundness of the interactive protocol being applied to. That is, the non-interactive protocol $(\textsf{P}_{FS},\textsf{V}_{FS})$ that results by applying the Fiat-Shamir transform to a interactive protocol $(\textsf{P},\textsf{V})$ is also sound. We say that the Fiat-Shamir transform is sound in the ROM if the above holds when $H$ is modelled as a random oracle.
When is the Fiat-Shamir transform sound? It is known to be sound in the ROM when applied to constant-round interactive proof systems [PS00]. In particular, we end up with a non-interactive argument system. One of the most common examples of this is the Schnorr signature scheme, which is obtained by applying the Fiat-Shamir transfom to the Schnorr identification scheme.
On the other hand, we know of certain counterexamples where the transform is "unsound" even in the ROM. I'd finish by adding that there has been a lot of exciting recent works that have aimed at proving the soundness of the Fiat-Shamir transform in the standard model (i.e., without random oracles): see [C+19,PS19] and reference related to them.
[C+19]: Canetti et al. Fiat-Shamir from Simpler Assumptions, STOC'19
[PS00]: Pointcheval and Stern, Security arguments for digital signatures and blind signatures, JoC, 2000.
[PS19]: Peikert and Sheihan Non-Interactive Zero Knowledge for NP from (Plain) LWE., Crypto'19


Both options for the 3-cipher cascade are equally safe.

All three algorithms are strong with no known issues.  Veracrypt uses them in well-studied modes that also have no known issues.

If you were worried about one of the algorithm implementations being vulnerable to some sort of side channel attack, then I would use that one as the last to be applied.  But in the context of most Veracrypt usage, someone who can mount a side channel attack, will probably just install a keystroke logger and steal the password directly.

So bottom line:  There is no real difference, and you can arbitrarily choose one with no real impact.

You also ask for an opinion about what the community would choose, so I'll offer mine:  The real threat is bad passwords or implementation bugs not weak algorithms, so I'd go with the highest performance single-pass algorithm.  A three cascaded cipher implementation is overkill.