Shouldn't a signature using ECDSA be exactly 96 bytes, not 102 or 103?

1) If I'm using it to sign a hash that I've already created (HMAC-SHA-384-192, specifically)

  a) why must I specify another hash algorithm?

HMAC is not a hash algorithm. It's a MAC, a message authentication code, or keyed hash. As the private key is used to create the signature there should not be any need for the secret key used to create a HMAC value. The hash itself is a integral part of ECDSA.

  b) What algorithm is consistent with the one in the HMAC and ECDSA-384?

You'd expect something like SHA-384, not HMAC-SHA-384-192.

  2) Why does the signature size vary between 102 and 103, instead of being exactly 96?

The signature consists of two integers. The format of X9.62 creates two ASN.1 INTEGER values for these and puts them within a SEQUENCE. The integer values are encoded as big endian signed values. So if the integers are 9, 17 or 25 bits smaller than the key size then the resulting encoding will be smaller.

Take for instance this 100(!) byte $r$ and $s$ value encoding for a 384 bit curve:

3062022e52884531f76504d28c0a60771025bce8881d33377fce5d62566d7d9a47da55066784b21b4bfcabd105dbe127ea6f0230560212a2b3078c55157842b92476dfaea7b6a58f2e4047d374de53b98629607b70e2ee06a1263c25db66f45572759c2d

decodes to

SEQUENCE(2 elem)
  INTEGER(367 bit) 1938306347072450679876740861736525521572671793660053577404161377925729…
  INTEGER(383 bit) 1323785767677292921898744777970756602439423500858315154875512504309946…

In principle they could also be slightly larger as a leading 00byte needs to be added for positive values where the very first bit is 1. This is because the initial bit is the sign bit, so if the first bit is set then the value would be interpreted as negative. The order of the curve however could well prevent this from happening.

  3) If I'm supposed to append a binary signature onto a potentially binary message (UDP), how is the recipient going to figure out where a message of unspecified length ends and a signed digest of unspecified length begins?

If you just concatenate both then you may not have a deterministic method of doing so. So basically you have to include a length of your message or signature.

You could also convert the signature to a signature that does contain two statically sized integers of course. The encoding of both "Plain Format" integers and "X9.62 Format" signatures is discussed in TR-03111 of the German BSI, section 5.2. You may want to reencode them back to ASN.1 DER format after the message is received and parsed of course, in case your API doesn't support Plain Format signatures.

In that case the signature size will be 96 bytes.


A quantum computer solves the discrete logarithm problem for both finite fields and elliptic curves. Being able to efficiently calculate discrete logarithms implies being able to break Diffie-Hellman, so Diffie-Hellman on either of them is not secure against an adversary who owns a large quantum computer.

There might be other groups in which DL problem is hard even against a quantum computer, but I've never heard of such a group.


Definition related to homomorphic encryption

I believe you are talking about the accumulative noise associated with performing gate operations on encrypted bits.

When looking at FHE over the integers (without modular reduction), it is easy to track the noise associated with operations.

In the 'AND' operation :
$$\begin{align*}
    c_i\cdot c_j =&\left(p\cdot q_i + 2\cdot n_i + b_i\right)\cdot\left(p\cdot q_j + 2\cdot n_j + b_j\right)\\
    =&p\cdot\hat{q} + 2\cdot\hat{n} + \left(b_i\cdot b_j\right)\\\\
{\#bits(\hat{n})} < & \#bits(\frac{p}{2})
  \end{align*} \\
$$

If this noise constraint isn't preserved, then the decrypt operation no longer holds.
$$Dec(c_k) = b_k = \left[p\cdot q_k + 2\cdot n_k + b_k\right]_p(mod\;2)$$

The introduction of different 'Recrypt' strategies are used to increase the depth of a circuit by reducing accumulated noise.


Formal Information-Theoretic Key Expansion Definition

NIST SP-800 108 seems to have a semi-formal definition in chapter 5.0:

Section 1:

  A key derivation function iterates a pseudorandom function (ed: PRF) $n$ times and concatenates the outputs until $L$ bits of keying material are generated, where $n = ⎡L/h⎤$.

Section 2:

  For each of the iterations of the PRF, the key derivation key $K_I$ is used as the key, and the input data consists of an iteration variable and a string of fixed input data.

But I must admit that this seems more a description of the inner workings of the described KDF's than a formal definition of one, if such a thing exists.

As about any KDF actually works this way it remains to be seen if this isn't enough of a formal description.

The original HKDF paper has this more formal definition:

  Definition 5: A key derivation function (KDF) accepts as input four arguments:

  a value $\sigma$ sampled from a source of keying material (Def. 6),
  a length value $l$,

  and two additional arguments,

  a salt
  value $r$ defined over a set of possible salt values
  and a context variable $c$,

  both of which are optional, i.e., can be set to the null string or to a constant. The KDF output is a string of $l$ bits.


User-specified PBKDF2 password, salt, and iterations limits

In other words, because none are ever stored by the implementation, can standard login authentication guidelines also with a 4-digit PIN be enforced to produce theoretically uncrackable combinations where the login username & password are substituted for the PBKDF2 password & salt or vice versa, and the PIN is the number of iterations no less than 1,000?

I see no good reason to make the iteration count configurable, at least within just 1000-9999. Attackers can check all the hashes with the different iteration counts in similar time as only the 9999 one, if they know know the hash and salt.

If you leave the iteration count configurable, it would need to have a significantly larger range of allowed values before it had much of an effect on how an attacker should try to look for a matching password. I.e. several orders of magnitude. That would mean someone willing to wait, say ten seconds every login (tens of millions of iterations) would get some extra buffer.

The standard specifies which of the parameters is meant to be the password (the one used as HMAC key) and which the salt, and while using them in the opposite order may not be insecure, that's what you should use to be safe. I.e. the secret password/passphrase as the PBKDF2 password and the (possibly public) username as the salt.

  If the standard username/password rules should not be implemented, why, and what minimums, by any measure such as length or quantity and/or variety of special characters, should be placed upon the PBKDF2 password/salt combination?

Well, pretty much no heuristics can stop a user using a poor passwords like "pa$$w0rd". However, the purpose of KDFs like PBKDF2 is to make the cost of cracking a password higher for an attacker. You can basically subtract ~10 bits from desired attack complexity due to your 1000 iterations.

For example, NIST recommends 80 bits for most secure passwords. You might get away with 70 for a comparable strength. That would mean 12 random base 64 characters (~numbers and upper and lower case letters), but a user-chosen 12 character password would probably have much lower entropy, even if it contained lower-, uppercase and numbers.

As an aside: if you want to guide users to choose good passwords, I would rather not set any limits (especially maximum length or minimum character set) and point users towards something like Diceware or password managers.


iSeries (AS/400) Database File: password encryption

Wikipedia has a list of cryptographic hash functions, together with their output size. 16 bytes are 128 bits. From the list, the following ones could be candidates:

MD2, MD4, MD5
RIPEMD / RIPEMD-128
HAVAL-128

The most probable one would be MD5, so start with this.


Is this pairing-based signature scheme secure?

The proposed digital signature scheme is not secure! More precisely, it is not existentially unforgeable under an adaptive chosen-message attack.
Let's consider the following efficient adversary $\mathcal{A}$: it queries the $\mathsf{Sign}_{sk}(\cdot)$ oracle for the digital signatures on $m_1,m_2$, where $m_2:=m_1+1$. The received signatures are $\sigma_1=g_1^{x_1m_1+x_2}$ and $\sigma_2=g_1^{x_1m_2+x_2}$. Now, $\mathcal{A}$ computes $\frac{\sigma_2}{\sigma_1}=\frac{g_1^{x_1m_2+x_2}}{g_1^{x_1m_1+x_2}}=g_1^{x_1(m_2-m_1)}=g_1^{x_1}$. Once $g_1^{x_1}$ is recovered, $\mathcal{A}$ can also compute $g_1^{x_2}=\frac{\sigma_1}{(g_1^{x_1})^{m_1}}$.
The knowledge of these $2$ points ($g_1^{x_1}$ and $g_1^{x_2}$) enables now $\mathcal{A}$ to forge signatures on any message of their choice. Namely, given any message $m$, $g_1^{x_1}$ and $g_1^{x_2}$, the valid signature on $m$ can be computed as $\sigma=(g_1^{x_1})^{m}g_1^{x_2}=g_1^{x_1m+x_2}$. The adversary $\mathcal{A}$ outputs $(m,\sigma)$ as a valid forgery and wins the security game.
This means, that the adversary can win the existential unforgeability security game with probability $1$ already after $2$ signature queries.


7zip : Why does encrypting the same file with AES-256 not give the same output?

This is expected behavior since 7zip uses Cipher Block Chaining (CBC) mode for encryption. For which you need the Initialization Vector (IV) to be unique and unpredictable.
It was using 64-bit IV but fortunately, that was changed to 128;

Encryption strength for 7z archives was increased: the size of random initialization vector was increased from 64-bit to 128-bit,
and the pseudo-random number generator was improved.

If the encryption of the same file results in the same ciphertext then we will be thought that there is a problem with the IV generation. Hopefully, from here we see that there is not.
Note 1: 7zip uses $2^{19}$-times iterated SHA256 to derive the AES-256 key from passwords. This is not safe from massive parallelization. A password with high entropy like diceware is recommended.
Note 2: The first comment under question claims that CBC mode of operations has IND-CCA actually it can't, it has IND-CPA. See the seminal work of Rogaway on modes Evaluation of Some Blockcipher Modes of Operation


Since these bytes are sent in clear text, what is the relevance of
  them being random?

They are a guarantee that the other party with whom you wish to communicate is actually interactively there and you're not just seeing a recorded session that is being replayed to you, potentially impersonating somebody else.
The randomness helps in this to prevent attackers from simulating a bunch of sessions beforehand and then picking the the relevant one for you.

  Also, what exactly are these random bytes used for?

Their actual usage is limited to being additional input to the key based key derivation function that transforms the pre-master secret into the master secret (section 8.1 RFC 5246).


The difference between MACs vs. HMACs vs. PRFs

A PRF or pseudorandom function family is a family of functions $F_k\colon \{0,1\}^n \to \{0,1\}^m$ such that if $k$ is uniformly distributed, then $F_k$ appears to be uniformly distributed among all functions $G\colon \{0,1\}^n \to \{0,1\}^m$.  A PRF $F_k$ is secure if an adversary who does not know the key $k$ can't distinguish $F_k$ from a uniform random choice of function $G\colon \{0,1\}^n \to \{0,1\}^m$ with more than negligible probability of success beyond flipping a coin—the adversary's only strategy is to correctly guess the key $k$ which is usually drawn uniformly from a space of usually $2^{128}$ or $2^{256}$ possibilities, which no adversary will ever stumble upon by chance.

The existence of PRFs remains a conjecture, related to P = NP; at best we conjecture that function families are PRFs, and sometimes find counterexamples to the conjectures.  Some PRFs have long or variable-length inputs, e.g. keyed BLAKE2b; some PRFs have short inputs, e.g. ChaCha or the compression function inside MD5.

A MAC or message authentication code is a family of functions $M_k\colon \{0,1\}^* \to \{0,1\}^T$ with which one can construct and verify a $T$-bit tag $t = M_k(m)$ on a message $m$ with a secret key $k$.  A MAC is secure if an adversary, upon seeing some number of past (possibly adaptively) chosen messages and tags $(m_i, t_i)$ with $t_i = M_k(m_i)$, can't forge a tag $t' = M_k(m')$ for a message $m'$ not previously seen with better than negligible probability.

Many MACs are one-time authenticators, meaning the secret key can be used for only one message, such as Poly1305 and GHASH (of AES-GCM).  One-time authenticators are useful because they can be extremely fast and can come with an unconditional information-theoretic security proof of forgery probabilities, and it is easy to use a PRF with a nonce to create a new OTA key for each message.

A long-input PRF $F_k$ can also serve as a MAC, because an adversary having seen $\{F_k(m_i)\}_i$ can't even distinguish that from $\{G(m_i)\}_i$ for a uniform random choice of $G$, so the best strategy the adversary has is to pick some $k'$ uniformly at random, try forging $t' = M_{k'}(m')$ for some message $m'$, and hope that $k = k'$, whose success probability is bounded by the probability that $M_{k'}(m')$ happens to coincide with $M_k(m')$ or that $k = k'$, which are both negligible.

$\newcommand{\concat}{\mathop{\Vert}}$HMAC is a specific construction of a long-input PRF out of a short-input PRF chained in a Merkle-Damgård construction $H$, such as MD5 or SHA-256.  Naively using the function $$F_k\colon m \mapsto H(k \concat m)$$ for uniform random key $k$ does not give a PRF when $H$ is either MD5, SHA-1, SHA-256, or SHA-512, because even if I don't know $k$, knowing $F_k(m)$ enables me to easily compute $F_k(m \concat p \concat m')$ for some padding $p$ and an arbitrary suffix $m'$.  This is called a length extension attack.  HMAC works around this for an MD hash function $H$ by using $$F_k\colon m \mapsto H\bigl((\mathrm{opad} \oplus k) \concat H\bigl((\mathrm{ipad} \oplus k) \concat m\bigr)\bigr),$$ where $\mathrm{opad}$ and $\mathrm{ipad}$ are constant strings defined in the standard.

(The full details are finicky, e.g. if $k$ is not exactly the length of one block of the short-input PRF underlying $H$.  You can also use HMAC on non-MD functions such as SHA-3, but the usual reference for an HMAC security reduction relies on MD.  The security reduction story for HMAC is complicated, and there has been some more recent work on it; however, the strategy for modern designs like SHA-3 and BLAKE2 is to just make prefix-keyed $F_k\colon m \mapsto H(k \concat m)$ work as a PRF without the contortions of HMAC, and to define a standard domain-separated keyed PRF variant of the function.)

Since for certain fixed hash functions $H$, HMAC-$H$ is conjectured to be a PRF, and since a PRF always makes a MAC, you can use HMAC-$H$ to make a (rather slow) MAC.

Is your construction an HMAC for some fixed hash function $H$?  No.

Is your construction a PRF?  No: if an adversary can control $\mathrm{handshake\_messages}$, then they can almost certainly find a collision in $$\operatorname{MD5}(\mathrm{handshake\_messages} \concat \mathrm{Sender} \concat \mathrm{master\_secret} \concat \mathrm{pad}_1),$$ which would enable them to distinguish $F_k$ (your construction) from a uniform random $G\colon \{0,1\}^\ell \to \{0,1\}^T$ without knowing $k$ ($\mathrm{master\_secret}$) by simply evaluating it on the colliding messages and seeing whether it's the same, which for the overwhelming majority of functions $G$ will not be the case.

Is your construction a MAC?  Again, no, because if the adversary can find a colliding pair of handshake message sets, then they can ask you to make a tag on one of them, and then they can use the same tag to produce a forgery on the other one.

Does this mean you can immediately attack a system in practice that works this way?  Maybe, maybe not.  What it means is that the crypto is not engineered out of reliable well-understood parts that could give confidence in the security of the whole system.  Thus to understand the security of the whole system you cannot simply (a) assess the security of the parts, and (b) assess the security of how they are wired; you must assess the whole thing as a giant unit ball of hair.  And most cryptographers and auditors don't want to bother doing that because it's a lot more work than well-done crypto engineering.


Pohlig-Hellman and Shanks algorithm on ECC

Although I was not able to run the scripts (perhaps my fault, my Python skills are mediocre at best), let me try to elaborate (slightly) on fkraiem's comment.

You are indeed right that the complexity of Pohlig-Hellman is lower than the complexity of BSGS (for a curve of smooth order). However, your parameters are relatively small. Looking at the definition of the big-$O$ notation, we see that this line of reasoning will ignore some constants. That is, roughly, the complexity $O(\sqrt{x})$ means that there is some constant $c$ such that for large parameters the complexity will be $\leq c\sqrt{x}$. This is however only a statement about large parameter values, and does not have much meaning for specifically chosen (small) parameters. For example a situation where an algorithm with complexity $O(t)$ is slower than an algorithm with complexity $O(t^2)$ for a specific instance is easily possible. Note that the definitions of small and large here depend very much on context.

Having said that, I am not sure whether that is actually the problem here. Iirc Pohlig-Hellman does not behave very poorly for small parameters, nor does BSGS. Perhaps you should be careful how you are measuring your complexity. Is it running time, number of curve operations, number of field multiplications, etc.? It could be that there is some overhead unrelated to the algorithm which affects the complexity.

Edit:
Okay, there are some confusing parts in your question. Let's get the details straight. We are assuming a curve $E:y^2=x^3+521x+1331$ over the field $\mathbb{F}_{26596586063}$. As you say, the points on this curve form a group of order $N=2*853*3593*4339$, with some generator $G$. Suppose there is some $H\in E$ such that $H=\ell G$ for $\ell\in[1,..,N]$. I deliberately name the scalar $\ell$ as opposed to $x$ to avoid confusion with the curve variable $x$. Let's compare the two ways in which we can solve this DLP (with a bit of abuse of notation):

BSGS: Doing BSGS on a group of order $N$ has complexity $O(\sqrt{N})$ and will give us $\ell\pmod{N}$.
Pohlig-Hellman:  Doing PH will cut the DLP up into four parts. We solve four smaller DLP's with respective complexities $O(\sqrt{2})$, $O(\sqrt{853})$, $O(\sqrt{3593})$ and $O(\sqrt{4339})$ (these are your $ni$'s), to get $\ell\pmod{2}$, $\ell\pmod{853}$, $\ell\pmod{3593}$ and $\ell\pmod{4339}$. We then use the CRT to recover $\ell\pmod{N}$. Hence we have complexity $O(\sqrt{2}+\sqrt{853}+\sqrt{3593}+\sqrt{4339})$ for the small DLP's. Note that we are forgetting about the cost to actually reduce to these small-order DLP's.

What we conclude is that for BSGS we have a complexity of around $\sqrt{N}\approx 163085$ while for Pohlig-Hellman we only have a complexity of around $\sqrt{2}+\sqrt{853}+\sqrt{3593}+\sqrt{4339}\approx 156$.


Real time video stream AES encryption with authentication

updated per comments;
Currently Netflix Uses AES-GCM

I am now studying the AES encryption for real-time video stream. It seems that Netflix uses the AES-GCM (or CBC + MAC) mode for real-time video encryption and authentication.

With MAC authentication, client can only get the MAC message after the> whole video is encrypted and authenticated. After that, the client can only get the MAC message after the whole video is encrypted and authenticated.

This blog post, posted on Aug 8, 2016 by Netflix, mentions that;

Cipher Evaluation
We evaluated available and applicable ciphers and
decided to primarily use the Advanced Encryption Standard (AES) cipher
in Galois/Counter Mode (GCM), available starting in TLS 1.2.
We chose AES-GCM over the Cipher Block Chaining (CBC) method, which comes at a
higher computational cost. The AES-GCM cipher algorithm encrypts and
authenticates the message simultaneously — as opposed to AES-CBC,
which requires an additional pass over the data to generate keyed-hash
message authentication code (HMAC). CBC can still be used as a
fallback for clients that cannot support the preferred method.
We needed to determine the best implementation of AES-GCM with the
AES-NI instruction set, so we investigated alternatives to OpenSSL,
including BoringSSL and the Intel Intelligent Storage Acceleration
Library (ISA-L).

How AES-GCM enables immediate playing

However, if the client wants to play the video immediately (without receiving and decrypting the whole video), how can the client verify the MAC message?

AES-GCM mode requires the receiver to verify the tag before using the plaintext. Since Netflix uses SSL/TLS there is a limit of a record in SSL/TLS, see RFC-5246 section-6.2.1. The amount is given as $2^{14}$ bytes or less. $2^{14}$ bytes is just ~16 kB. This amount is easy to verify the tag and decrypt the data even the user jumps on the movie.

Server Side

I am not sure whether my guess is right. Can anyone give any advise? How does the real video provider's server do this kind of secure video stream transmission?

Netflix used AES-CBC now AES-GCM. As mentioned in the blog, AES-CBC mode of operation requires an additional pass to generate the HMAC. AES-GCM, however, can perform encryptions and authentication the message simultaneously. This is good for the server-side for reducing the data access.  With the usual numbering of the data, the server can feed the client with many records at once.
On the server-side they use AES-NI, ISA-L, and BoringSSL
Note that; they developed a special TLS;

To retain the benefits of the sendfile model while adding TLS
functionality, we designed a hybrid TLS scheme whereby session
management stays in the application space, but the bulk encryption is
inserted into the sendfile data pipeline in the kernel. This extends
sendfile to support encrypting data for TLS/SSL connections.

see the two technical articles from Netflix developers;

Optimizing TLS for High–Bandwidth Applications in FreeBSD
Improving High–Bandwidth TLS in the FreeBSD kernel.

Parameters

If my guess is right, what is the typical size of video slices, or it is dynamic?

The Netflix articles don't exactly mention this. This paragraph from the article 1;

When the keys were ready, have the TLS library
send them to the kernel and let the kernel do the encryption
part, while all the other parts of TLS would continue to be
executed by the TLS library. The TLS library would continue
to frame its messages and submit framed but un-encrypted
messages to the kernel.

implicitly implies that they are bound to TLS record size, $2^{14}$ bytes.


ADLY is the order those letters appear in the alphabet, so A=1, D=2, L=3, Y=4.

But I've never seen such a substitution in a Vigenere cipher, and it's dumb, since it makes a weak algorithm even weaker. Normally you just identify A with 0 or 1 and then assign increasing numbers to subsequent letters. A=0, B=1, C=2, ... Z=25, so LADY would map to 11,0,3,24 (or 12,1,4,25 if you start with A=1 and end with Z=26=0).


Can I combine two of SHA-3 candidates cryptography hash functions and obtain more secure Algorithm?

The basic problem with combining primitives in a hashing or encryption function is that when doing so, you have to be sure that the combination doesn't expose some weakness. When talking about hashing, the three main desirable qualities are one-way transformation (absolutely critical), even distribution (after hashing a sufficiently large number of messages and plotting a histogram of the hash values, you would expect all buckets of the histogram to be equal), and high avalanche effect (related to randomness, adding or changing a single bit in the message should produce a massive and theoretically unpredictable change to the hash value).

When coming up with a hash algorithm, designers combine primitives in such a way that they can mathematically or empirically demonstrate the relative level of strength in these three areas. Conversely, third parties can demonstrate weaknesses in these areas. For a simple example, take the original FNV-1 checksum hash; for each byte of input, the working hash is multiplied by the FNV prime and then XORed with the input byte. People using it found that while it worked well for checksums, if these two operations were reversed, the algorithm exhibited much better avalanche characteristics and more even distribution, leading to the commonly-used "FNV-1a" variant described in the whitepaper.

By combining hash algorithms in a particular order, you may or may not create a stronger algorithm. You may increase the one-wayness of the algorithm, but conversely you may at the same time reduce the set of possible hashes (either by hashing a hash into a lower-bit output or reducing the distribution of hash values within an absolute range). The same applies to performing primitives of a hashing function in differing order, as evidenced by the above example.

Lastly, the combination of primitives you chose may induce a weakness; neither FNV-1 nor 1a are crypto hashes for many reasons, one of them being that regardless of which way you perform the primitives, the least significant byte is always the XOR of all input bytes each XORed with 1. That reduces the set of all possible collisions with a particular hash by half; a cracking algorithm could very quickly spin through this "carry XOR (lsb XOR 1)" sequence to determine that a candidate message won't work. By doing so you effectively reduce the complexity of brute-forcing a collision with the given hash by a power of 2, thus breaking "strong collision resistance". If a crypto hash had this weakness it would be considered broken.

If you want a secure hash, consider bcrypt. First off, bcrypts are relatively small to store as strings since they're Base64-encoded (60 chars/bytes, vs 64 for a hex-encoded 256-bit hash), but they store as much entropy as a 256-bit hash. Second, not only is bcrypt slow, it's configurably slow, by increasing the number of steps for a key initial stage of hash generation by powers of two. Thus, the algorithm can easily be adapted to keep up with Moore's law; every year and a half, you just increment the complexity of the hash and presto, it takes twice as long to brute-force the hash, offsetting the empirical doubling of processing power during that time.


Does the One-Time Hash-based Signature Scheme render Ring Signatures useless?

I see several misunderstandings in your question. Let me provide some clarification:

One-time addresses don't provide privacy at satisfiable level. At first glance, it's impossible to associate some one-time address with some identity (person).
But analysis of the graph of transactions could reveal relations between one-time addresses. E.g., despite the fact you use one-time addresses to receive payments, then, to spend this money (buy a car) you would need to
aggregate all the addresses in a single transaction. This will reveal all you wanted to hide. Even if you try to make a confusing chain of transfers between one-time addresses, someone like Sherlock Holmes is able to unravel a tangle step-by-step.
One-time signatures (OTS) is not a feature, but a restriction.
You cannon say that OTS "more powerful than other types of signature schemes". Vice-versa, they are limited/hard to use.
Ring signatures, at least in original cryptographic meaning (https://en.wikipedia.org/wiki/Ring_signature), don't provide privacy by itself. They could be used just as a building block of a complex cryptosystem like Cryptonote/Monero. But if you use the term "ring signature" as the cryptosystem provided by Monero, you're right - its goal is a privacy, including unlinking senders and receivers of transaction and impossibility to associate relations between addresses.
There're several definitions of privacy in payments, several levels of privacy. And several solutions, the most noted are: 1) Cryptonote/Monero, 2) Bitcoin confidential transactions, ZkSNARKs based solutions of 3) Zcash and 4) Ethereum, 5)Bulletproof-based solutions for Bitcoin.
For example, Bitcoin Confidential Transactions provides only confidentiality of amounts of a transaction but doesn't hide senders and receivers. So, different systems achieve different aspects/levels of privacy. It's even so except bugs/attacks.

So, answering your question, OTS doesn't make Ring signatures useless in any sense, since:

one-time addresses doesn't provide privacy, while solutions based on ring-signatures (such as Monero) do;
OTS and one-time addresses are difficult/inconvenient to use, comparing to multi-time ones; e.g., in order to receive recurring payments, you constantly need to inform your payers with fresh addresses.


Difference between using Schnorr Protocol and just compare hash function to prove knowing something?

The question does not correctly describe the Schnorr protocol. Here it is (with restriction to a multiplicative subgroup of $\Bbb Z_p^*$, because that's in the question).

It is chosen a large prime $q$ (e.g. $>\approx 2^{512}$) and a larger prime $p$ (e.g. $>\approx 2^{8192}$) with $p=2\,a\,q+1$ for some integer $a\ge1$ (with $p$ not of a special form facilitating SNFS), and an integer $g$ of order $q$, that is with $g^q\bmod p=1$ and $g\bmod p\ne1$ (one such $g$ is $4^a\bmod p$). Parameters $p$, $q$, $g$ are public.

A random secret $x\in[0,q)$ is known to a Prover, who publishes $h=g^x\bmod p$. The above choice of parameters $p$, $q$, $g$ is such that the Discrete Logarithm Problem of finding $x$ given $h$ is believed hard.

The protocol's goal is that a verifier gets rightly convinced that a party knowing $x$ with $h=g^x\bmod p$ participates in the protocol, without revealing $x$ to the prover or to adversaries, including active (in particular, adversaries are able to impersonate the prover w.r.t. the verifier, and vice versa). Towards this:

Prover draws a random value $r\in[0,q)$ and sends commitment $c=g^r\bmod p$
Verifier draws a random value $t\in[0,q)$ and sends that challenge to prover.
Prover computes and sends response $s=r+t\,x\bmod q$
Verifier is content that prover knows $x$ iff $g^s\bmod p=c\,h^t\bmod p$

That equality normally holds because $s=r+t\,x\bmod q$ implies that $\exists k,\ s+k\,q=r+t\,x$ therefore $g^s\equiv g^{r+t\,x-k\,q}\equiv g^r\,g^{t\,x}\,g^{-k\,q}\equiv c\,(g^x)^t\,(g^q)^{-k}\equiv c\,h^t\,1^{-k}\equiv c\,h^t\pmod p$.

It can be shown that breaking this protocol is equivalent to solving the DLP.

  What is the difference if I store a hashed value for example $h=\operatorname{SHA-512}(x)$ to a public place, and if prover wants to prove he knows secret $x$, he just need to send $h'$ to verifier and verifier compare if $h=h'$ stands.

The proposed protocol fails to prove to the verifier that another party knowing $x$ participates in the protocol. Argument: since $h$ is in a public place, an adversary not knowing $x$ can get $h$, send that as $h'$ like the prover knowing $x$ is supposed to do, and thus pass the verifier's test.

If prover and verifier both know $x$, a solution is possible using $\operatorname{SHA-512}$ in a challenge-response protocol: verifier draws and sends random $t$, prover computes and sends $s=\operatorname{SHA-512}(t\mathbin\|x)$, verifier checks $s=\operatorname{SHA-512}(t\mathbin\|x)$.

The advantage of Schnorr's protocol is to achieve the same goal without requiring the verifier to know $x$. In particular, in the MAC-based protocol, the verifier must keep $x$ secret, which is hard even for an honest verifier, and is not necessary with Schnorr's protocol.


The non-interactive proof of verifiable computation: Pinocchio

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


Where is the "Letter to NBS, October 22, 1975"

This letter, among other letters of the time, can be found in the Stanford digital repository of Hellman's papers.
This October 22 1975 letter, in particular, is here.


Yes, a Merkle–Damgård hash can be one-way. Even MD5 hasn't been broken in that way.

Target collision resistance (TCR) is a notion similar to second preimage resistance (but for keyed functions). Preimage resistance, i.e. one-wayness, does not imply second preimage resistance, so a hash function can be one-way without even having second preimage resistance.

Normal collision resistance, which Bellare and Rogaway call any collision resistance (ACR) in that paper implies target collision resistance, so if the function is collision resistant, it is also TCR. With Merkle–Damgård a collision resistant compression function gives you a collision resistant hash function. Likewise, a preimage resistant compression function gives a preimage resistant hash function.

So what's the point of their result?

They show that TCR of the compression function does not imply TCR of the keyed hash function, meaning that e.g. a 128-bit MD hash does not necessarily have 128-bit TCR.


Why can't the commitment schemes have both information theoretic hiding and binding properties?

It's impossible. In order to be perfectly hiding, it must be the case that two different messages can produce the same commitment string. But then that commitment can be opened in two ways (by an unbounded committer), so the scheme is not perfectly binding.


What are some different cryptography methods?

All mathematical groups can be used to perform an ElGamal encryption, so that is a first kind of math. That's where elliptic curves are useful: they have a group structure. If you find a group, you can build a cryptosystem out of it. However, as @poncho pointed out, different groups have different properties with regards to security. For instance, elliptic curves are better than modular groups because they do not have a specific structure which can be leveraged to solve the discrete logarithm problem (see http://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm for an example of algorithm working only in modular groups).

You also have cryptosystems based on lattice related problems. In particular, lattices have been used to create the first fully homomorphic cryptosystem (see the references in http://en.wikipedia.org/wiki/Homomorphic_encryption).

A system which turned out to be very bad was built from the knap sack problem (see the Naccache–Stern knapsack cryptosystem on wikipedia).

For symmetric crypto, the theory of boolean functions can explain how the functions inside Feistel Networks or substitution permutation network are chosen. This yields connexions with coding theory and of course with finite fields of size $2^n$.


Using Lattice-based cryptography for TLS\SSL

Feasible? Sure, there are lattice algorithms that are competitive in performance with RSA.

However, there are drawbacks, like:

They've been studied less than RSA or ECC, especially the individual algorithms.
The most well studied system, NTRU, is patented.
No generic proof that I know of that there isn't a quantum algorithm to solve them.

The first one is why I doubt TLS will quickly move to lattices at least unless there's significant evidence that a quantum computer capable of breaking current crypto is practical. The third means that even then another public key system might be better, if such can be found.


SHA3 hexadecimal paddig odd length string

The bid padding of KECCAK family
Actually, the padding is defined bit based in section 5.2 for the general case;
Algorithm 9: pad10*1(x, m)

Input:
positive integer x;
non-negative integer m.

Output:
string P such that m + len(P) is a positive multiple of x.

Steps:
    1. Let j = (– m – 2) mod x.
    2. Return P = 1 || 0^j|| 1.

and also noted as
Therefore this at least a 2-bit padding. If the message size $m \bmod r = \{0,-1\}$ then a new block will be required.
The $x$ is set as $x = r (rate)$

The suffix and padding for $\operatorname{SHA3-224}$
The Keccak uses domain separation for SHA3, rawShake, and Shake series. For SHA3-x the message is first suffixed with 01 then the padding is applied (section 6.1);
$$M||\underbrace{01}_{suffix}||\underbrace{10^*1}_{padding bits}$$
$$\operatorname{SHA3-224}(M) = \operatorname{KECCAK}[448] (M || 01, 224);$$
In this case, the minimum added bits is 4, 2 from the suffix, and at least 2 from the padding.
byte padding fix for odd hex numbered messages.

but to do a bit of padding I first need to convert the input from hex to binary. To do so I could use Algorithm 10 in section B1 but this works only with hex string of even length so it cannot be used so that's why I'm asking for detail about the hex padding

Since the encoding trans $\texttt{abc||060*80}$ to $[80\ ..\ 00\ 06\ c0\ ab]$ the obvious solutions is using $\texttt{ab6c||0*80}$ and this will be translate to $[80\ ..\ 00\ 00\ 6c\ ab]$ as required.
The confusion come from the fact that the NIST defines the message as

message A bit string of any length that is the input to a SHA-3 function.

So the bit padding is naturally applied to a bit string. For the hex valued string, it must be converted Algorithm 10: h2b(H, n) but the document implicitly defines the byte padding as before the conversion. after the conversion it is still the bit padding.

Note: the $\phantom{a}^*$ represents the Kleene star simply means zero or more.


How to go about decrypting a cipher with known input and output?

Block size 8 symbols because repetitions. it is not caesar or vigenere because next symbol (B instead of A) in input doesnt mean next symbol in output(j instead of i). It is primitive cipher because 1 letter input makes 1 letter output. Closest thing is likely enigma, the world war 2 cipher machine. To decode think about it as 8 substitute ciphers. Symbol in positions 1+8n, where n=0,1,2,3,4... uses first substitution cipher. symbol in position 2+8n, where n=0,1,2,3,4... uses second substitution cipher.
How to test if im right: enter BA in input. Output will be Di.
How to recreate it: write down substitution alphabet for symbol 1 by entering in input A, then B, then C... and writing down the output. You will get a table that says 'if A then X'. Repeat for the second position, it will give you second substitution alphabet. In total you will get 8 substitution alphabets. Then you can turn letters into numbers. Im almost certain that author was lazy enough to code this substitution with math, and not actual alphabets. Seeing letters in substitution alphabets in a form of numbers you can make equations. A=1, B=2, C=3, ... X=26, A multiply 5+21=X, 1 multiply 5+21=26. Once you figured out the math for each symbol position, you can figure out math for going from symbol 1 to symbol 2, likely the same operation as converting a symbol from input to output. At this point you will have a compact representation of author's algorithm.


Is it possible to use crib drag on base64 cipher text?

Yes, it is possible to use crib dragging. It is easy to prove this: you could just search for the base 64 encoded version of the crib. This would work even if you would simply use search for a recurrence of the crib every 4 characters because that's the amount of base 64 characters that are needed to encode 4 bytes. So the chance of success would be diminished, but it is still possible.

It is also possible to perform crib dragging over byte boundaries in base 64, but then you may need to check for multiple possibilities that could be valid. So the chance of success is much lower if you start in the middle of a base 64 character.

You can of course guess the characters before the crib itself as well, so the extended crib can still be moved across the boundaries. You'd need to guess up to 3 characters though.


How to verify the claim of entropy available made by Linux 4.5?

You can't, and you're not the only consumer. The operating system rips you off. It uses true randomness to prevent attacks by shoving code into random places. And randomly sequencing it's network traffic. But here's the thing...

“We have to remember that what we observe is not nature in itself but nature exposed to our method of questioning.”

-Werner Heisenberg
and that's compounded with the concept of the observer effect.
Essentially what the kernel does is quantize various external events via a made up second order differential algorithm. There's a write up in Documentation and Analysis
of the Linux Random Number
Generator but essentially it comes down to temporal quantization of hardware events as :-

And so,

It seems therefore that Linux 4.5 underestimates its amount of entropy

Yes.  That's the conclusion of all of the academic works I've seen on /dev/random. It's essentially the least signification digit of system time when something happens. But, the problem is that it shouldn't take 160 PDF pages to convince us of randomness. My concept of Open Entropy dictates that it should be screaming right up in your face without funky science.
With delicacy, what's your real question?

Nothing in this post relates to Micro$oft operating systems.

If this is important to you, build your own entropy source. It's not difficult considering the 2nd law of thermodynamics. Get a diode.

There's a dangerous and hugely misunderstood  meme out there that suggests /dev/random = /dev/urandom without appreciating the role of time. $(\epsilon, \tau)$ and the left over hash lemma  is everything.


Is MAC-then-encrypt with stream ciphers secure?

As correctly pointed out in a comment, the authenticated encryption model assumes that

the attacker knows the algorithm;
the attacker can query the encryption oracle with any plaintext $P$ (and a unique nonce $N$) and get MAC-then-Encrypt ciphertext $C$;
the attacker can query the decryption oracle with any string $C$ pretending to be a ciphertext.

No other data is available to the attacker. The assumption you made that the MAC alone is available is too strong.


Why is CBC with predictable IV considered insecure against chosen-plaintext attack?

The CBC IV attack does more than that.

If I guess the plaintext corresponding to any ciphertext block I've seen before, and can predict a future IV, I can verify my guess by submitting a suitable message to be encrypted with that IV.  Obviously, that could be bad if, say, I knew the plaintext to be either "yes" or "no", and only needed to find out which one it is.

More concretely, the BEAST attack for example allows the recovery of cookies sent by a web browser over HTTPS.  The way it works is (more or less) that you first convince the browser to send an HTTPS request where a block boundary falls just after the first unknown byte in the cookie (e.g. by adjusting the length of the requested URL) and intercept the ciphertext.

So now you have a ciphertext block that you know corresponds to, say, the string Cookie: secret=X, where X is an unknown byte.  Now you use the CBC IV attack to test all possible values of X and find the right one.  Then you repeat the process with a URL that's one byte shorter, so that you get a ciphertext block corresponding to ookie: secret=XY, where you now know X but don't yet know Y.  Then just keep repeating the process until you've recovered the entire cookie, byte by byte.

See this answer to a related question for more details.


TL;DR: The public key is not a point, it is the $x$-coordinate of the point.

The base point of the curve has been chosen to be the point $G = (9,y_0)$ with $y_0>0$, and the curve Curve25519 is used in its Montgomery form given by the equation
$$
y^2 = x^3 + 486662x^2 + x.
$$
The main operation on elliptic curves is the scalar multiplication, and in this case, it is computed with the Montgomery ladder algorithm with formulas that use only the $x$-coordinate of the input point, and output the $x$-coordinate.

For one valid $x$-coordinate of a point $P$, there are two possible points, $P$ or $-P$, so if Alice private key is $a$, then her public key is $x([a]G)$ (the $x$-coordinate of the point $[a]G = G + G + \cdots + G$, the output of $\operatorname{Curve25519}(a,9)$). Since the $y$-coordinate is not used, then it corresponds either to the point $[a]G$ or $-[a]G$, then Bob can compute easily $x([ba]G)$, which corresponds to either $[ab]G$ or $-[ab]G$.

Basically, the $y$-coordinate is not useful to get a shared secret, and not useful for the computation since the formulas that do not use it on Montgomery curves are pretty efficient.


Is there a recommended cryptoperiod for HMAC hashing keys?

Theoretically as pointed out by @CodesInChaos there is no need to rotate keys as long as they remain secret.

Also as @CodesInChaos points out, you need to architect the system for key rotation in the event of key compromise.

The best way to do that is to build key rotation into the app and operational tooling, and then put procedures in place to rotate keys regularly. That way you know key rotation will actually work when you really need it.

During the Heartbleed incident there were banks that were unable to re-key many of their certificates for several months despite regulator requirements that they be changed immediately. Rekeying was an infrequent manual process on their varied and ancient systems; some had never been re-keyed and nobody in house knew how to do it. It simply couldn't be done in a timely manner.

Regular exercise of key rotation prevents this sort of problem. Automation makes it easy. Think of it as DR planning and testing for your crypto keys.


Long-term data protection, storage of old encrypted traffic and quantum cryptocalipse

I can't agree with bullet 3. of the question stating quantum computers are getting stronger with a good pace (82-qbit computer last year, 512-qbit computer this year), at least in a context of cryptanalysis.

Even the marketing people praising the device alluded to do not pretend that it is of a kind useful for cryptanalysis: they state about it:

  The types of problems the quantum computer is designed to solve are called discrete combinatorial optimization problems. The most cited example of this kind of problem is the “traveling salesman problem”.

Importantly, there is no claim of exactly solving almost all TSP of a given size, which would be a big breakthrough with potential applications to cryptanalysis. This marketing text proceeds to describe how better solving the traveling salesman problem as applied to US trucking could be of economic and ecological significance, without giving any evidence that today's TSP solvers can't handle that task satisfactorily.

In a recent scientific pre-publication linked here, the term " quantum annealing processor " is used to describe the device. Entanglement of only 8 qubit is claimed (a single out of 8x8 arrays of 8 qubit). Even if these 8 qubit where a quantum computer, and if all 64 arrays where functional, 64 arrays of 8 qubit would not make a 512-qubit quantum computer.

Enough expressing my strong doubts about the usefulness of Quantum Computers for cryptanalysis in a foreseeable future, let's get positive.

To protect against hypothetical Quantum Computers of a kind and size useful for cryptanalysis, using twice larger keys for symmetric algorithms is ample; AES-128 is safe today against key search, I bet AES-256 will remain resistant (in practice, to all but side-channel attacks) even with quantum computers, for decades (the most forward-looking may want to use Rinjdael in its 256-bit mode with perhaps an even wider key).

Now there's the problem of asymmetric algorithms (used when we want a private key not shared with anyone else). The mainstream asymmetric algorithms (RSA, ECDSA, DH, ECDH..) with today's key size are conceivably not secure against said hypothetical QC. Update: and, contrary to what I initially wrote, forward secrecy can't fix that. Protocols with forward secrecy, like some options of TLS or IPSec, can prevent past intercepts to be broken in the event of future leakage of private keys, including by use of future QC. But we do not know practical means (wich excludes Quantum Key Distribution) to fully protect us against intercepts made today, and analyzed in the future using an hypothetical Quantum Computer of a kind and size useful for cryptanalysis, and able to break the step of a key exchange protocol that built an ephemeral/session symmetric key, using typically some variant of DH or ECDH. Towards that, we need better/stronger asymmetric algorithms; I'm incompetent about it. In the meantime, we can use large asymmetric keys (particularly for the scheme building an ephemeral/session symmetric key); that's arguably at least of some use against QC.

And we should care, a lot, about much more mundane things than QC; like compromise of our computing platform, side-channel attacks, bad TRNGs, implementation goofs, and traffic analysis.


Does such a cryptographic protocol exist?

How about the following, not practical, but proof of viability with lot's of usage of Secure-Multi-Party-Computation) :

A,B,C generate using secure multi-party-computation: a joint private/public key, none of them have the private key individually only together. Also a simple symmetric key shared between them (each with one shard).

The initial balance sheet is encrypted with the shared symmetrical key.

When someone wants to give money to someone, they sign a statement saying so with their own personal private key, and then encrypt the signed transfer order with the shared public key.
When this encrypted transfer order is presented, together they may apply secure multi party computation, to verify it, verify balance, approve/reject the order and produce new encrypted balance(Possibly also provide ZKP of correctness of the process).


Pick your favorite $b$-bit block cipher $E_k$, say AES-256.  Let $k$ be the seed and let the $i^\text{th}$ output be the $b$-bit string $x_i = E_k(i)$.  Then $i = E_k^{-1}(x_i)$.  Given $k$ and $x_i$, this is widely considered to be ‘easy’, for most block ciphers including AES-256.  Note that every possible $b$-bit string has an index.

$\newcommand{\Z}{\mathbb{Z}}$Pick your favorite 2048-bit safe prime $p$, say $2^{2048} - 1942289$, and your favorite nonzero generator $a$ of $(\Z/p\Z)^\times$, say $5$.  Let $x_0 \in (\Z/p\Z)^\times$ be the seed and let the $i^\text{th}$ output be $$x_i = a x_{i - 1} = a^i x_0.$$  Then $a^i = x_i x_0^{-1}$, so that $i = \log_a x_i x_0^{-1}$.  This is widely considered to be ‘hard’, for sufficiently large safe primes including $2^{2048} - 1942289$.  Note that every possible element of $(\Z/p\Z)^\times$ has an index.

Defining ‘easy’ and ‘hard’ is left as an easy exercise for the reader.  Deciding whether to encode $i$ as little-endian or big-endian for $E_k$ is left as a hard exercise for the reader.

This does not address any security of these PRNGs.  One of these is fit for use in cryptography; the other is emphatically not.  Since you didn't mention any security requirements in your question, I didn't mention any security properties in my answer.  Figuring out which one is which is also left as an exercise for the reader.  (I hope you're taking notes, because there'll be a quiz on Thursday next week about all these exercises!)


Using the same RSA key for verifying a website and digital signature

tl;dr: send to the server $enc(random) \times theHash$, and divide the value that you get back by $random$. That is your forged signature for $theHash$.

Your setup can be summarized as follows: with have a Server S with an RSA private key $(N; d)$, a Client C with the corresponding public key $(N;e)$. Furthermore the client as a value $h$ for which (s)he wishes to get a valid signature under the private key of the server, namely the client wants $h^d \mod N$. Finally the server authenticates itself by proving the knowledge of $d$(i.e computes $q^d \mod N$ where $q$ is possibly an encrypted nonce.

Observations: 1. We can assume that the server somehow checks that none of the queries is $h$, and refuses to decrypt any such query otherwise game over.
2. I wrote possibly because the client in fact doesn't need to send and encrypted query. He could send any value to the server as long as it's an element of $Z/Z_N$.

The attack: the client selects a random value $s$ such that $gcd(N, s) = 1$, and sends to the server the value $q = h\times s^e \mod N$. This is indeed a valid query. Next, the servers send back $\sigma = r^d \mod N = h^d \times s \mod N$. Finally the client computes the signature as $sig = \sigma \times s^{-1} \mod N = h^d \mod N$. So we have the signature that we wanted.


Now I noticed that no matter which generator I use, when I use power-mod such that g^(q-1) mod q the result always 1

Congratulations, you just rediscovered Fermat's Little Theorem which says that for all primes $p$ and all non-zero integers $a$ which are not multiples of $p$, it holds that $a^{p-1}\bmod p=1$.

So if I have the group order set to 8009 minus one can is 8008, because 1 + 8008 mod 8009 = 0.

Indeed, this is how it works for plain addition $\bmod 8009$, however it seems you're not actually doing that and are actually using lifted ElGamal, i.e. encrypting as $(g^k \bmod p,g^m\cdot y^k\bmod p)$ (because standard ElGamal only has a multiplicative homomorphism).
But at that point you're no longer adding $m+m'$ but you're instead adding $g^m\cdot g^{m'}=g^{m+m'}$ and as it turns out, these exponents don't operate in the group $\mathbb Z_p$ (i.e. $\bmod p$) but instead in the group $\mathbb Z_{\operatorname{ord}(g)}$, where $\operatorname{ord}(g)$ is the smallest non-zero integer $q$ such that $g^q\bmod p=1$. If you are using a safe prime $p$, i.e. a prime $p$ such that $(p-1)/2=q$ is also prime, then $\operatorname{ord}(g)$ can take exactly 4 values: $1,2,q,2q$ (by Lagrange's theorem and the multiplicative order being $p-1$ for a prime).


You can never actually prove that it was generated randomly or pseudorandomly. You can only prove with high probability that it wasn't. Calculating the number of heads and tails is one way. Another is calculating runs of consecutive heads or tails. There is a suite of statistical tests from NIST in their FIPS 140-2 document which is a good place to start.

Having said that, for cryptographic purposes you really need to be sure that you are using a secure random number generator and there aren't any tests you can apply to the data itself to sufficiently guarantee that it is secure enough.


In RSA, is it possible to compute the private key if one knows one of the primes used to generate n?

I'll read the problem as stating we have $c$, $e$ and $p$ from some encryption $c=m^e\bmod(pq)$. But for some reason we do not have $n$ (even thought it is part of the public key, which is assumed public).

We know the order of magnitude of $q$, which likely is little above $\log_2(c)-\log_2(p)$-bit. But that's a far cry from $q$.

We can compute $d_p=e^{-1}\bmod p$, then $m_p=c^{d_p}\bmod p$ which is $m\bmod p$. Depending on context, that might let us guess $m$. For textbook RSA encryption and a narrow message (bit size of $m$ less or comparable to the bitsize of $p$), we will have $m=m_p$ or $m=m_p+k\,p$ for some small $k$, revealing $m$ or allowing to guess $k$ and $m$ if $m$ has some redundancy.

If we somewhat get the full $m$, we can compute $a=(m^e-c)/p$ and that's a multiple of $q$. If we are lucky, $a$ can be fully factored, revealing $q$. That's not entirely impossible for very small $e$ when using ECM to try to pull the factors of $a$.

If we can similarly find the full $m'$ for another $c'$, then we can compute $a'=(m'^e-c')/p$ and then compute $\gcd(a,a')$. That's a multiple of $q$, and has an excellent chance to be easy to fully factor, revealing $q$.

With $p$ and $q$, we can compute a working private key per any of the usual methods in RSA.


Can a file encrypted with one tool be decrypted with different tool?

As mentioned in the comments what the receiver needs to know is effectively: Formats, Algorithms and Keys.

Now this may be a bit of an unsatisfying answer to most people, so I'll go into more detail.

Formats

The sender and the receiver have to agree on a format on how to actually read the data and how to interpret it. If I give anyone a chunk of Word document data without any format specification he will have a really hard time figuring out what field means what. So in your scenario you have to think of some specification on how to transmit your files, this may be as simple as the following, but must be done in order to ensure compatibility.

Example: RSA encrypted file

Offset        | Size | Type | Name |Description
0             | 4    | bytes| Magic| A constant magic value to identify this packet
4             | 4    | bytes| Ver  | A little-endian (LE) 32-bit integer denoting the format's version
68            | 64   | bytes| Cert | A SHA-512 hash of the certificate used to encrypt the key
72            | 4    | int  | KeyLe| A LE 4-byte integer holding the size of the ciphertext
76            | 8    | int  | Size | Size of the actual encrypted data
84            | 12   | byte | Nonce| A random nonce used for GCM
96            | KeyLe| int  | KEM  | An encrypted random number
96+KeyLe      | Size | byte | Data | The encrypted file
96+KeyLe+Size | 16   | byte | Tag  | The GCM tag on the data

So far for the format, now for the

Algorithms

Only knowing how to read in the data doesn't help you alot. You also need to know how to interpret it. This is where the algorithms come into play. For the above example you need to know that f.ex. Header Version 1 would be to use AES-256-GCM to encrypt the data using the nonce and outputting / verifying the appended tag along with authenticating the header as associated data (AD). Furthermore you'd have to know that this version requires you to use HKDF (salt=empty, no additional info) to derive the key from the RSA decryption of the Key value using the certificate with the hash matching the Cert entry. You'd also need to know that you select a key by randomly choosing a number smaller than the RSA modulus and by encrypting this number with RSA (=Key) and using the HKDF of the secret integer as the AES key.

Keys

The keys aren't all that interesting at this point. You'd need to somehow trust the authenticity of the public key (using certificates?). But that's basically it with key management with this example. Of course you also have to consider things like key revocation, key expiration and key erasure but those are different problems...

To finally answer your first question whether the programming language matters. It doesn't if both systems use the same Formats, Algorithms and the right keys, because you wouldn't be able to distinguish the results of a C# from a Python from a C++ implementation then.


How to compare the efficiency of public key cryptosystems, i.e., RSA vs El Gamal?

Since you are approaching this from the point of view of mathematics, I think the most fruitful avenue would be to look at asymptotic performance and security of the problems that the cryptosystems are based on.

For example, with RSA you need a modular exponentiation for every message you encrypt or sign. The time that takes depends on the length of the modulus as well as the exponent. The most efficient general purpose algorithm for breaking RSA is GNFS which also takes time dependent on the size of the modulus.

Find out the same for the other algorithms you are interested in and you can compare them and see e.g. whether one will asymptotically become more efficient at equal security.

This will allow you to steer clear of the various practical issues of how the different constants compare and what platform some performance measures might be relevant for.


Is stretching hash several times basically the same as bcrypt?

bcrypt operates using the Blowfish block cypher. It does not use any kind of message digest function (such as MD5, SHA1, SHA-256, etc.) internally.

Of course, I think what you really wanted to ask was, "would using a traditional message digest function with some amount of stretching give similar security to bcrypt?", and the answer to that question is probably "no". However, we can't answer that because we don't really know how you would accomplish the stretching. It's probably reasonable to say that stretching in some way would achieve similar security, but you would need to account for what bcrypt was designed to do.

bcrypt does have the advantage that it's "slower" than the message digest algorithms, but that's not it's main goal. bcrypt was designed not only to be slow, but to scale poorly on FPGA and GPU architectures. As you mentioned, modern FPGAs have gotten quite a bit better and serve as reasonable means to break bcrypt, which is why scrypt was invented in the first place.

It should be noted that what you describe with the stretching is essentially PBKDF2, which has been shown to be less secure than bcrypt.


Can you help me understand indistinguishably as described in the CPA security definition?

Yes, your intuition is completely right (assuming a polynomial-time adversary and a super-polynomial message space, which is the usual setting). If the scheme were deterministic, then the adversary could simply use the oracle to distinguish which message was encrypted. Therefore, no deterministic encryption can be CPA-secure. This is a well-known implication of the definition of CPA-security.


Are there better alternatives to CRC32 for distributed download components hash calculation?

I'll assume we want a cryptographic hash giving security in the Random Oracle Model; collision-resistance and preimage-resistance follows. Collision-resistance alone rules out CRC, regardless of size.

The standard technique would be to split the file into blocks, distribute them with index to the participants, which hash each of their blocks; then hash the hashes concatenated in order of increasing indexes, or use a Merkle tree, to form the hash of the whole file. However, with blocks distributed in haphazard manner (as in the question), most block hashes need to be exchanged, which can get sizable; and the distributed computation of the final hash is slightly hard to organize.

Rather, we can group the block hashes (made dependent of their index) using an order-independent hash, used by each participant over all the hashes of the blocks s/he is responsible for, then again to obtain the final hash. This simplifies the organization, and saves bandwidth when there more than a few blocks per participant: like 8 in the following simple example using $\Bbb Z_p^*$, but I conjecture that the overhead can be made negligible down to 1 block per participant using an Elliptic Curve Group instead.

For a 256-bit hash, marginally more costly than a regular one for large files, we'll use:

Some 512-bit hash $H$, e.g. $H=\operatorname{SHA-512}$.
Some 2048-bit prime $p$ making the Discrete Logarithm Problem in $\mathbb Z_p^*$ (conjecturally) hard; see final section.
Some public block size $b$ multiple of $2^{12}$ bit (512 bytes), e.g. $b=2^{23}$ for blocks of 1 MiB.
Implicit conversion from integer to bitstring and back, per big-endian convention.

To hash a file of $s$ bits (with $s\le2^{62}b$, which is more than ample):

Split the file into $\lceil s/b\rceil$ blocks $B_i$ of size $b$-bit, except for the last which may be smaller (but non-empty), with $0\le i<\lceil s/b\rceil$. Distribute the blocks $B_i$ and indexes $i$, such that each participant $j$ is assigned a block only once.
Have each participant $j$ perform:

$f_j\gets1$
For each block $B_i$ assigned to participant $j$

$h_i\gets H(B_i)$. That's a 512-bit bitstring characteristic of $B_i$.
$g_i\gets H(h_i\mathbin\|\widetilde{4i})\mathbin\|H(h_i\mathbin\|\widetilde{4i+1})\|H(h_i\mathbin\|\widetilde{4i+2})\|H(h_i\mathbin\|\widetilde{4i+3})$ where $\widetilde{\;n\;}$ is the representation of integer $n$ as a 64-bit bitstring.
Since function $H$ returns 512 bits, the concatenation of the 4 hashes makes $g_i$ a 2048-bit bitstring, characteristic of $B_i$ and $i$.
$f_j\gets f_j\cdot g_i\bmod p$.

$f_j$ is a 2048-bit bitstring characteristic of the $B_i$ and $i$ assigned to participant $j$.
If $j\ne 0$, transmit that $f_j$ to participant $0$.

Participant $0$ performs:

$f\gets f_o$
When receiving $f_j$ with $j\ne 0$

$f\gets f\cdot f_j\bmod p$.

$h\gets H(f)$ truncated to it's first 256 bits, where $f$ is represented as a 2048-bit bitstring when applying $H$.
Send $h$ to all participants.

Absent message alteration or loss, $h$ is independent of how the blocks have been distributed. That is a 256-bit bitstring characteristic of the whole file, computed in a largely distributed manner. The computation of $f$ and $h$ could be distributed too, at a small extra cost in message exchange.

The order-independent hash is borrowed from the multiplicative one in Dwaine Clarke, Srinivas Devadas, Marten van Dijk, Blaise Gassend, G. Edward Suh, Incremental Multiset Hash Functions and Their Application to Memory Integrity Checking, in proceedings of AsiaCrypt 2013, which is given a security reduction in appendix C. The security of the whole construction should follow.

On choice of $p$: our requirement is hardness of the DLP in $\Bbb Z_p^*$, as in classic Diffie-Hellman key exchange. We need a 2048-bit safe prime, with no special form $p=2^k\pm s$ that could make SNFS easier. Customarily, it is used a nothing-up-my-sleeves number based on the bits of some transcendental mathematical constant, as a good-enough assurance that $p$ is of no special form.

That can be $p=\lfloor2^{2046}\pi\rfloor+3617739$. The construction uses the first 2048 bits of the binary representation of $\pi$, then increments until hitting a safe prime. Hexadecimal value:

c90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca18217c32905e462e36ce3be39e772c180e86039b2783a2ec07a28fb5c55df06f4c52c9de2bcbf6955817183995497cea956ae515d2261898fa051015728e5a8aaac42dad33170d04507a33a85521abdf53ee2f

As pointed by Sqeamish Ossifrage in comment, we could use the 2048-bit MODP proposed by RFC 3526: $p=2^{2048}-2^{1984}-1+2^{64}\cdot\lfloor2^{1918}\pi+124476\rfloor$. That similarly uses as many of the first bits of the binary representation of $\pi$ as possible, but by construction has the 66 high-order bits (including two from $\pi\approx 3$) and 64 low-order bits set. The high-order bits simplify choice of dividend limbs in Euclidean division by the classical method, while the low-order simplify Montgomery reduction. This is believed few enough forced bits to not allow a huge speedup of the DLP.

ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca18217c32905e462e36ce3be39e772c180e86039b2783a2ec07a28fb5c55df06f4c52c9de2bcbf6955817183995497cea956ae515d2261898fa051015728e5a8aacaa68ffffffffffffffff


The one time pad can be used to provide perfectly secure encryption, given fully random key stream. Of course this key stream needs to be kept perfectly secure for it to be considered fully random.

Nether RSA nor AES can be used to protect a one time pad, because the one time pad would rely on RSA and AES to be secure. Neither RSA nor AES are perfectly secure, and neither can even be proven to be secure - as far as we know.

This prohibits distributing a one time pad with either RSA or AES; you are better off just using RSA / AES directly, for instance using a hybrid cryptosystem with AES in counter mode or any authenticated mode.


Can the statistical width of the avalanche effect be calculated?

Q. Is there a calculable mathematical relationship between the standard deviation and the block size, or must it always be determined empirically?

This is a well studied problem in probability.

If we consider each output bit as an independent random variable (and if they're not independent, your hash function is broken), each such random variable has a standard deviation of $0.5$ (if $0$ and $1$ have equal probabilities; again, if this is not true, your hash function is broken).  The sum of $N$ such independent samples will have a standard deviation of $0.5 \sqrt{N}$.  In your case, $N=512$; this gives us a standard deviation of $11.3137...$, which is just what you see.


What is the difference between SHA256WITHRSA and SHA256WITHRSAENCRYPTION digest algorithms?

It seems that djigzo uses bouncycastle and if you look in the source at the DefaultSignatureAlgorithmIdentifierFinder, e.g., here, then you find:

algorithms.put("SHA256WITHRSAENCRYPTION", PKCSObjectIdentifiers.sha256WithRSAEncryption);
algorithms.put("SHA256WITHRSA", PKCSObjectIdentifiers.sha256WithRSAEncryption);

Thus, it seems that both refer to sha256WithRSAEncryption, which means RSA with SHA-256 and PKCS #1 v1.5 padding.


does using an HMAC protect against hash table DoS attacks?

but if there are N buckets and N is not super large, simply generating random data will still produce a hit approximately once every N tries.

Changing the hash function won't change this fact. There should be other mitigations to a user adding a bunch of random data, such as rate limiting or changing your data structure.

How do you plan on obtaining the key for the HMAC? If it's the same for everything, then hash collisions in the underlying hash function translate to hmac collisions. If it's derived from the data, then the attacker's job is just marginally more difficult; they have to effectively compute three hashes per calculation (one for the key derivation, two for the hmac) instead of one. If it's random, how will you be able to retrieve data from the table?

As you mention in the comments, we don't care about hash collisions but rather hash collisions mod N. In this scenario, an HMAC would sufficiently stop an attacker from being able to calculate data that would hash to the same bucket. If the HMAC construction is too expensive for your application, you should be able to get away with something lighter weight like H(key||message).


Backdoorable hash function in password database

You can simply handle password verification on login and escrow independently:

Store a salted password hash (e.g. bcrypt) together with its salt. You can use this to verify logins, just like what you'd use if you had no escrow.
Also store the password encrypted with asymmetric encryption (e.g. RSA-OAEP, ECIES).

Since these are randomized, they are not vulnerable to attacks where the attacker guesses a password and checks if the encryption matches the ciphertext.

You might need to add some padding, to avoid leaking the length of the password.

The Makwa password hash has a built-in backdoor, but since this problem can be solved generically, I don't consider that a good reason for using Makwa over another hash.


Let $a$ and $b$ be the numbers emited rsp. by person A and person B. $E(x)$ means encoded form of $x$.

$E(a)$ and $E(b)$ are publicly known, right?

Note that if person A knows $a$, $E(a)$, $E(b)$ and person B knows $b$, $E(a)$, $E(b)$ and it is possible to calculate $a+b$ from $E(a)$ and $E(b)$ (that is what you want to do, right? So it must be possible) person A can calculate $a+b$ from the data he has. He also knows $a$ and calculating $b$ given $a+b$ and $a$ is trivial. Now person A knows the secret number of person B and person B can calculate the secret number of A same way.

I don't know what is this system going to be used for, but even if A and B trust each other there are still some security risks here.


The first scheme is similar to what's called Encrypt-and-MAC. It is not ideal, but it is not fatally broken, and it is still used by the SSH protocol securely. You need to include a counter or other unique value in the data being MACed to maintain IND-CPA security (i.e. identical plaintexts don't have identical MACs).

The second scheme you present doesn't really make sense. I can't see what benefit it would provide. Generally, you would want to use Encrypt-then-MAC, or EtM, a scheme where the plaintext is encrypted, the MAC is computed over the ciphertext and appended directly to it. EtM is a better scheme because it gives away no information about the plaintext, even if the MAC is broken. It also gives you the benefit of allowing you to discard a forged message without needing to decrypt it first, to prevent some attacks.

See also Should we MAC-then-encrypt or encrypt-then-MAC?

On a side-note, you should use AEAD instead. For AES, that means selecting an authenticated mode like GCM, which is both fast and secure. Although HMAC can be used safely, AEAD is usually better.


Choice of public modulus $p$

Using for $p$ a large safe prime (that is, a prime $p=2q+1$ with $q$ also prime) is the way to go for the Pohlig-Hellman cipher, because that

simplifies the choice of encryption key $k$: a random odd $k$ in range $[1,q-2]$ will do, because that ensures that $\gcd(k,p-1)=1$ (the condition for validity of an exponent in the Pohlig-Hellman cipher);
makes recovering $k$ from sample plaintext/ciphertext pairs $(m,c=m^k\bmod p)$ conjecturally hard, and in particular avoids the case where $p-1$ would be smooth, allowing to find $k$ quickly by the Pohlig-Hellman Discrete Logarithm algorithm.

To guard against the Discrete Logarithm variant of the SNFS algorithm, it is also recommendable that $p$ is not of the special form $r^e\pm s$ for small $r,s$.

Provided this, there is consensus that, baring apparition of Quantum Computers usable for cryptanalysis or spectacular algorithmic progress, a 3072-bit $p$ is most likely fine for some decades (say, comfortable 128-bit security), and 2048-bit likely fine .

Because the requirements for $p$ are the same as for Diffie-Hellman key exchange, there are ready-made, unobjectionable $p$. The $p=2^{3072}-2^{3008}-1+2^{64}\cdot(\lfloor2^{2942}\pi\rfloor+1690314)$ of the 3072-bit MODP Group of RFC 3526 is suitable (hex value below)

FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C354E4ABC9804F1746C08CA18217C32905E462E36CE3BE39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9DE2BCBF6955817183995497CEA956AE515D2261898FA051015728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6BF12FFA06D98A0864D87602733EC86A64521F2B18177B200CBBE117577A615D6C770988C0BAD946E208E24FA074E5AB3143DB5BFCE0FD108E4B82D120A93AD2CAFFFFFFFFFFFFFFFF

Intentionally, for this $p$ and its 1536 to 8192-bit analogs:

leftmost 66 bits are ones, which simplifies quotient estimation in classical modular reduction;
rightmost 64 bits are ones, which similarly eases Montgomery arithmetic;
most center bits are borrowed from $\pi$, and the few-digits constant is minimal to reach a safe prime, so these are nothing-up-my-sleeves numbers.

Choice of encryption key $k$ and decryption key $k'$

The requirement is that $k$ is a secret coprime with $p-1$; that is, with our choice of $p=2q+1$ with $q$ prime, that $k$ is odd and not a multiple of $q$. This ensures there exists a matching decryption key $k'$ with $k\cdot k'\equiv1\pmod{p-1}$, which in turn insures (by a straightforward application  of Fermat's little theorem) that for any message representative $m$ with $0\le m<p$, ${(p^k\bmod p)}^{k'}\bmod p=m$ ; that is, encryption of $m$ with $k$ followed by decryption with $k'$ will get back to $m$.

It is enough to choose $k$ as a truly random odd integer in range $[1,(p-3)/2]$, or some sub-range of that (with a bare minimum of about $2^{2b}$ possible values for $b$-bit security, with no constructive proof that's enough). For example, if $p$ is $n$-bit, it is fine to draw $n-4$ random bits, append a one bit on the left and on the right to form an $(n-2)$-bit odd integer (that works regardless of endianness). What's critical is that the generator uses some unguessable entropy, and that the key $k$ (and matching $k'$ ) are kept secret, including during use. Protection against side channels is going to be a serious issue.

The decryption key $k'=k^{-1}\bmod(p-1)$ can be computed with the (half) extended Euclidean algorithm. Another method giving $k'$ is computing $k^{q-2}\bmod q$ and adding $q$ when the result is even.

Note: as stated in the question, constructing the message representative $m$ from the actual data to transmit should be done with care. A safe option would be to reuse the OAEP construction of RSA.


Related to Curve25519

Curve25519 seems to be secure so far. Yet, you have to remind yourself that Dr. Bernstein specified Curve25519 for key-exchange. Meaning: key-generation, transaction signing, and verification are somewhat different beasts – you might want to cross-check on that before jumping toward Curve25519. Sure, Curve25519-java supports signing… but I’m not aware of a thorough, well-vetted cryptanalysis of the signing side of things. There might be issues with it, which have yet to be checked for to be found.

Related to Curve25519-java

NxtCoins.NL reports that BCT user named Jesse James, also known as DoctorEvil, reviewed the Java implementation and he seems to think it is safe. Quoting his publication: “Crypto Review of Curve25519.java & Crypto.java”, last modified on 2014-03-14:

  Crypto Review of Curve25519.java & Crypto.java

  By DoctorEvil on Nextcoin.org
  Sponsored by MSIN on BitcoinTalk.org

  TL;DR

  NXT's Crypto.java and Curve25519.java look kosher aside from a signing bug that is currently being worked around.

  General Methodology

  Reviewed the primary/secondary literature on Curve25519 and EC-KCDSA to evaluate them vis-a-vis the NXT use-case.
  Re-implemented these primitives from scratch in Python (differently than the Java version).
  Scoured every line of the Crypto.java/Curve25519.java.
  Ran tests to uncover output discrepancies between my implementation and the Java version.

  Choice of Algorithm

  Curve25519+EC-KCDSA are theoretically defensible choices for NXT's use-case.  However, since cryptocurrency applications are dominated by signature verification, Ed25519 would have arguably been a slightly better pick (although no high quality Java implementations of it exist so NXT's choice is understandable).

  Signing Bug

  As I (and others) have noted before, the Curve25519.sign function has a legitimate flaw that causes it to occasionally produce invalid signatures. This flaw may have arisen because the original C code the Java was ported from used unsigned primitive integral types underlying its representation of big numbers whereas the Java port is restricted to signed types.

  BloodyRookie's proposed patch is essentially sound, although it can be simplified and made constant-time.  Here is a fixed sign function inspired by his changes:

  (Java sourcecode)

public static final boolean sign(byte[] v, byte[] h, byte[] x, byte[] s) {
    // v = (x - h) s  mod q
    int w, i;
    byte[] h1 = new byte[32], x1 = new byte[32];
    byte[] tmp1 = new byte[64];
    byte[] tmp2 = new byte[64];
    // Don't clobber the arguments, be nice!
    cpy32(h1, h);
    cpy32(x1, x);
    // Reduce modulo group order
    byte[] tmp3=new byte[32];
    divmod(tmp3, h1, 32, ORDER, 32);
    divmod(tmp3, x1, 32, ORDER, 32);
    // v = x1 - h1
    // If v is negative, add the group order to it to become positive.
    // If v was already positive we don't have to worry about overflow
    // when adding the order because v < ORDER and 2*ORDER < 2^256
    mula_small(v, x1, 0, h1, 32, -1);
    mula_small(v, v , 0, ORDER, 32, 1);
    // tmp1 = (x-h)*s mod q
    mula32(tmp1, v, s, 32, 1);
    divmod(tmp2, tmp1, 64, ORDER, 32);
    for (w = 0, i = 0; i < 32; i++)
        w |= v[i] = tmp1[i];
    return w != 0;
 }

  I have tested this patch with over 100,000 random keys/messages.

  Non-standard Algorithm Tweaks

  EC-KCDSA as implemented by Crypto/Curve25519.java does not exactly match the specification per IEEE P1363a.  In particular:

  It modifies EC-KCDSA to be deterministic.  IMHO, this is good change.  However, the implementation uses a non-standard deterministic signature nonce generation scheme; RFC6979's or Ed25519's scheme would arguably have been better choices on the basis of having been more looked at.  That said, I couldn't find anything obviously wrong with the scheme used.

  The implementation also deviates from the standard with regard to the computation of w, instead computing it as H(H(m) + x1) (using the terminology of Guide to Elliptic Curve Cryptography ).  That said, I couldn't find anything obviously wrong with this deviation; it appears sound.

  The implementation's EC-KCDSA key generation is also non-standard due to complications of Curve25519 using x-coordinate only representation.  While this ambiguous representation is not problematic in the context of Diffie-Hellman key agreement (for which Curve25519 was specifically designed), it is inconvienent for naïve EC-KCDSA.  The implementation uses a workaround during key generation to address this issue.  While I couldn't find any reference to anyone else using the specific workaround, it appears to me to be sound.

  Curve25519.verify uses a variant of a Montgomery ladder differential addition chain to calculate the curve point (vP + hG).  I can't find any reference to this variant in the literature and this is easily the most optimization-obfuscated part of the implementation.  That being said, nothing about it stands out as wrong and I can understand the performance motivation of using the variant.

  Signature Malleability and Signature Canonicalization

  It's worth noting that Daniel Bernstein, the primary designer of Curve25519, explicitly states in his paper on the related Ed25519 signature scheme that he does not consider signature malleability a part of the threat model when designing signature schemes.  This should give pause to those who think they will be able to define canonicalization conventions to eliminate all sources of malleability.  It may be possible to achieve using such conventions but it is not safe to assume without formal, peer-reviewed proof.

  As far as I can tell, NXT's fix in response to the attack I reported earlier, makes it immune to signature malleability.

  One malleability-related observation: public keys are EC x-coordinates over a field of order 2^255-19.  This means every public key has two 32-byte representations.  While an interesting sidenote, I don't see how this opens up any avenues for attack in the context of NXT.

  I'd also like to make one correction to my earlier vulnerability report.  The GROUP_ORDER constant in Curve25519 I reported as 2^252+2^124 (from misreading of a code comment) but is actually defined as 7237005577332262213973186563042994240857116359379907606001950938285454250989.  My exploit code worked anyway simply because it used the constant as defined.

  Side Channel Attacks

  The implementation leaks a small amount (up to 2 bits?) of private key information via timing during signing in Crypto.sign because this function recomputes the signing key from the passphrase each invocation (Curve25519.keygen is not timing attack resistant when used to generate EC-KCDSA keys).  I don't see any way to exploit this in the context of NXT.   However, precomputing the signing key once at user login and passing it into the sign function would be appropriate if NXT were to ever have a code path where an external observer could cause a target to sign anything on-demand and observe it's timing (e.g. like some interactive authentication protocol).

  Alternative Implementation

  As part of my analysis I developed an alternative Python implementation of the crypto primitives.  As noted, my code is pedagogical (slow and not timing-attack resistant).  However, since it uses fundamentally different EC arithmetic (affine XY coordinates vs projective XZ coordinates), it serves as a useful sanity check of the Java version's math (as well as makes for a more understandable exposition of the underlying algorithms).

  In a test with 1024 signers, it produced the same signature outputs and had the same verification results as the (patched) Java implementation.

  Other Checks

  The Curve25519 committed into NXT's repository (as of the publication of this report) exactly matches the port distributed by Dmitry Skiba. Not hugely notable, but thought this was worth checking for the sake of the tin-foil-hat crowd.

  EC-KCDSA with ECDH

  A formal proof of security that they are compatible was out of scope of this review. However, my preliminary investigations lead me to believe it is OK for NXT to re-use EC-KCDSA keys for ECDH key agreement (something which NXT currently does not do but which is implied by road mapped features).


How does the simulator of the special-honest verifier zero-knowledge property works?

Even following your edits, there's still some confusion about honest verifier zero knowledge and plain-old (i.e., "possibly malicious verifier") zero knowledge, which is a much stronger property.

Your description of HVZK is essentially correct, but with the following clarifications:

  A 3-move protocol between a prover P and a verifier V for a language $L$ is said to be honest verifier zero-knowledge if there exists a polynomial-time simulator $M$, which on any input $x$ in the language $L$, outputs a transcript $(a,e,z)$ having the same probability distribution as a conversation between the honest $P,V$ on input $x$.

A key point here is that the simulator's transcript must look like a real conversation between the honest prover and verifier.  Typically, this makes simulation very straightforward, because in most protocols the honest verifier is defined to make a uniformly random challenge $e$ that is independent of the prover's initial message $a$.  So the simulator does not need "black box" access to $V$ or its random tape, nor does it need to rewind $V$, because we know exactly how the honest $V$ operates.  Instead, a typical simulator for proving HVZK will just first choose the challenge $e$ uniformly at random, then generate the prover's messages $a,z$ in a manner consistent with that challenge, and output the transcript straightaway (no rewinding).  It's usually easy to prove that $(a,e,z)$ has the appropriate distribution, thanks to the independence of $a$ and $e$ in the real protocol.

By contrast, the strategy presented in steps 1-2(b) represents a typical (black-box) simulator for proving plain-old ("possibly malicious verifier") ZK.  Here we don't know the verifier $V^*$'s strategy for choosing its challenge $e^*$; in particular, it might choose $e^*$ non-uniformly, or in a way that depends on the prover's first message.  So we usually define a simulator $M$ that first "guesses" an $e$ in advance and prepares $a,z$ to work for that value of $e$, then sends $a$ to $V^*$ to receive some $e^*$, and checks whether $e=e^*$.  If so, $M$ finishes the transcript successfully, otherwise it throws everything away and starts over.

To answer your first question, the reason $M$ starts over from scratch is that we don't know how $V^*$ chooses its $e^*$ -- maybe $e^*$ has some crazy dependence on the prover's first message $a$.  In such a case, changing $a$ could lead to an entirely different challenge $e^*$ (even if $V^*$'s coins remain fixed).

To answer your second question, one can typically design $M$ so that when $x \in L$, the value $a$ that $M$ gives to $V^*$ reveals no information about which challenge $M$ is prepared to answer.  So if, e.g., $e$ is a uniformly random bit, the probability that $e^*=e$ is exactly 1/2, and so $M$ succeeds after 2 attempts in expectation.  This means that its expected runtime is polynomial.  (Alternatively, one get a truly polynomial-time simulator that outputs a transcript that is statistically close to a real one between $P$ and $V^*$ -- the difference being that in the negligibly small chance that $M$ fails after many attempts, it just outputs a junk transcript.)


Are Anonymity and Authentication possible together?

First, authentication is not really “proving that someone is who they say they are”, but linking an action, message or situation with an identity. If I show my passport to prove who I am, what I am really doing is linking my physical presence with the identity conferred to me by the state of which I am a national.

A person may well have multiple identities. For example, people with dual citizenship have two passports and what they do with one is somewhat decoupled with what they do with the other.

Multiple identities are the basis of anonymity. Indeed, as soon as you interact with anyone else in any way, this creates an identity: you're the person who did this thing at that time. Anonymity is not a lack of identity, but a lack of a link between a certain identity and any other identity that you may have.

Coming back to authentication, it is a link between two identities: the person who did that thing at this time is the same person who owns these credentials. Phrased this way, authentication is exactly contradictory with anonymity. However, there are many situations where it is useful to have partial authentication or partial anonymity.

An obvious solution to partial anonymity is to have a trusted third party as an intermediary. I'm using one right now: you know me by my Stack Exchange account, and you can use this identity to authenticate my Stack Exchange activity. Stack Exchange knows me by an identity with an OpenID provider, but isn't telling you. My OpenID provider in turn knows some things about me, but they only know the name on my passport if I've been telling them. There is a chain of links between identities (which could be traced all the way to, say, my home address via ISP logs), but you need the collaboration of multiple parties to resolve the chain.

How satisfactory such situations are depends on how the identification linkage chain is set up and what parties you're prepared to trust. Having identification linkage chains that are practically impossible to trace is the basis of anonymity systems such as TOR.

Going in another direction, authentication is very often used for authorization. I may use this account because I am the account owner. I may enter this building because I am an employee. An authorization system can be set up to decouple the action that is being authorized from the identity that led to the authorization. A well-known example is voting systems: they have both strong authorization requirements (only registered voters may vote, and only once per election) and strong anonymity requirements (even I cannot prove who I voted for, at least not if I want my vote to be counted). In traditional voting systems, anonymity is ensured by stepping into a booth to put a standardized piece of paper in an opaque envelope. Anonymity is ensured by observers who control that everyone steps into the booth and by rules that make non-anonymous ballots void.

Reference: https://security.stackexchange.com/questions/47913/is-the-concept-of-authenticated-anonymity-possible


How to change the policy value of a CA identity in apple keychain?

In Keychain Access.app highlight the certificate, then "Get Info" ( ⌘ i ):

  Under "Trust" select "Code Signing" > "Always Trust"


Signal-to-noise ratio in differential cryptanalysis

The point of differential cryptanalysis is to find a differential characteristic with sufficiently high probability.  You go through plaintexts until you find pairs that give you "enough" of a difference.  You know only plaintext and ciphertext difference and you do not know difference between individual rounds, because cipher is a black box.  (this is called filtration btw)

You use these pairs as a start for "key-recovery" by exploring the probabilities into possible subkeys in order to try to correlate the pairs.  Every pair suggests several subkeys.  Good pair suggests exactly one good subkey and few
wrong subkeys. How many times the correct subkey is more frequent than other subkeys is signal to noise (S/N) ratio.

There's a paper that I read (which currently eludes me) that had a nice description of this where they used about 2GiB of data an javascript to extract the keys from TLS.  You basically will want to look at the cipher of interest, and do a literature review to see how much data you'll need, unless you want to go into the mathematics yourself.


What is a good way to demonstrate elliptic curve cryptography?

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


How can one construct the weakest S-box ever?

Any affine function will do. Let your Sbox be $$S(x)=Mx\oplus c$$ where $M$ is an $n\times n$ binary matrix and $c$ is an $n-$bit constant vector.

The output difference for this Sbox is, for any nonzero $a$
$$
S(x \oplus a)\oplus S(x)=(M(x\oplus a)\oplus c )\oplus Mx\oplus c= M a\oplus c
$$
which is a constant for fixed $a$ so all the output differences for that input difference take on the same value.

For nontriviality pick either $c$ nonzero or $M$ a non identity matrix. The matrix must be invertible (over $GF(2)$) for the Sbox to be invertible, i.e., a proper substitution.

AES with this type of Sbox can be trivially broken.

Edit: See the answer to this question for details.


How to crack unknown 8-bit encryption algorithm?

Assuming that there are no collisions and there exists a 1 to 1 bijection between input and output, you could construct and store a table of assignments on a single round of encryption for all 256 possible bytes regardless of the key size. From there you can extend this to subsequent rounds by simply XORing the result of the previous round to the next 8 bit block, and plugging this result into your table.


CTR works by taking a counter, concatenating it with a nonce, and encrypting the result

Not quite. CTR works by taking a value that is unique per block encrypted with the same key and encrypting it. How this value (the counter block) is constructed is not standardized, and all that matters for security is its uniqueness (and independence of the encryption key).
One way to use CTR mode is to keep a count of blocks (a number: 0, 1, 2,  …) that are encrypted with that key, and use a representation of that number as the counter block: typically base 256 big-endian or base 256 little-endian, if you see the counter block as an array of 8-bit bytes. That works when there is a single entity using that key, it only ever encrypts one message at a time, and it remembers where it left off between blocks.
This simple approach breaks down if multiple entities want to encrypt, or if even one entity wants to encrypt multiple messages in parallel, since there's no practical way to both keep counter values consecutive within a single message (without that, you'd need to save all the counter values with the message and not just the initial value) and avoid repeating counter values (which would break security).
The best solution is to never encrypt two messages with the same key, and instead do two steps to encrypt a message: first derive a key from a per-message nonce, then use that single-use key to encrypt the message. You would then send the derivation nonce with the message, and you wouldn't need to send the initial counter value since you can simply always start at 0.
If you want to encrypt multiple messages with the same key, you need a way to have disjoints sets of counter values per message. A common way to do this is to break the counter block into two parts: a per-message nonce, and an in-message counter. This limits the possible length of messages to the number of blocks that can be represented with the in-message counter, for example a 32-bit in-message counter means a maximum of $2^32$ blocks (so $2^{36}$ bytes for ciphers such as AES with a 128-bit block size). The per-message nonce needs to be unique per message, for example a counter of messages sent.
Another common approach that avoids saving state (such as the number of messages sent) is to start each message with a random counter value and increment it throughout the message. This is fine as long as you don't send too much data with the same key, where "too much data" means you mustn't get close to the birthday bound, i.e. the square root of the number of possible blocks. For a 128-bit block size, this means don't get close to $2^{64}\,\text{blocks} = 2^{68}\,\text{bytes}$ of data.
Xoring a per-message nonce with the in-message counter may or may not work depending on how the nonce is generated. For example, if the nonce is a count of messages sent, it's horribly bad, because it leads to repeated counter block values. In base 2, and just representing the last three bits of the counter blocks, you'd have:

First message: first counter block $000 \oplus 000 = 000$, second counter block $000 \oplus 001 = 001$, …
Second message: first counter block $001 \oplus 000 = 001$, second counter block $001 \oplus 001 = 000$, …

As you can see, counter blocks are repeated, and that defeats the security completely.
If your nonce is a random 128-bit value, it's similar to the common method of starting with a random 128-bit value and incrementing it, but with an order of enumerating counter blocks that depends on the per-message initial counter value. I think this has the same statistical properties, but I haven't done the math. It complicates the implementation very slightly. I don't see any particular benefit.


Generating AES-256 Private Key from user string

Using a key derived from a password hash means someone could brute force this using either a known list of passwords or dictionary.

Since SHA-256 is quite fast, it's very easy to do with a moderate amount of computational power.

To better protect the key from such an attack, it is suggested to use a password derived from a key derivation function.

Some examples of these include: PBKDF2, scrypt and argon2.