What does $k^{-1}$ mean?

In the question's formula $S=k^{-1}(\mathrm{hash}+d_A\cdot R)\bmod p$ , the term $k^{-1}$ is a (or the) multiplicative inverse of $k$ modulo $p$. By definition, that is an integer $i$ such that $(i\cdot k)\equiv1\pmod p$ , that is an integer $i$ such that $p$ divides $(i\cdot k)-1$ (or if we want the multiplicative inverse, additionally $i$ must be such that $0<i<p$ ). Which  multiplicative inverse we take does not change the result $S$ .

$k^{-1}$ can be computed using the (half-)extended Euclidean algorithm (see this ); or other methods. Whatever was used, the question has $S$ matching $k$, $\mathrm{hash}$, $d_A$, $R$ and $p$ , and the equation given. But see below why $S$ is wrong.

  Its length seems to be only half of a valid signature

Indeed. That's because the signature is $(R,S)$ per some convention; like concatenation of fixed-length octet strings representing $R$ and $S$ per big-endian convention, perhaps with some prefix.

  Comment on the equation

Oh, I had missed that initially: the question's equation $S=k^{-1}(\mathrm{hash}+d_A\cdot R)\bmod p$ is wrong! There is confusion between the order $p$ of the field (used for coordinates on the elliptic curve secp256k1), and the order $n$ of the point $G$ on the elliptic curve (which for secp256k1 is also the number of points on the elliptic curve, including the point at infinity). The correct equation is $S=k^{-1}(\mathrm{hash}+d_A\cdot R)\bmod n$ . For secp256k1, $n$ is 115792089237316195423570985008687907852837564279074904382605163141518161494337 . That changes $S$ , of course.

  If the equation only gives us $R$, how can we get $S$ ?

We obtain $S$ using the equation $S=k^{-1}(\mathrm{hash}+d_A\cdot R)\bmod n$ starting from $k$, $\mathrm{hash}$, $d_A$, $R$ and $n$ .

We must previously have obtained $R$ by computing $k\times G$ . That's by point multiplication on the elliptic curve secp256k1, using arithmetic modulo $p$ (this is not a typo), keeping the $X$ coordinate, and deducing $R$ . The normative way is to compute $R=X\bmod n$ (after having reduced $X$ modulo $p$ so that $0\le X<p$ ), and redoing from start with another $k$ when $R=0$ . However in practice, if we do no get $0<X<n$ , then the process by which $k$ was chosen and $X$ computed is almost certainly broken, and in all other cases $R=X$ .

Update: I confirm that the question's $R$ matches the question's $k$ . Thus all that remains to do is compute $S$ using the appropriate modulus, and format $(R,S)$ into the signature.


Why is there the option to use NIST P-256 in gnupg?

Because P-256 is the most used elliptic curve and there are no certain reasons to believe it's insecure.
It's the first standardized curve at the 128 bit security level (which is very popular).

The rumors about its backdoor came from 3 factors:

The Snowden's revelations included a generic claim of the NSA trying to backdoor NIST standardized crypto
DualEC DRBG being a NIST standard actually backdoored by the NSA
Daniel J. Bernstein trying to push for his own curve25519

But there is no backdoor connection between DuelEC DRBG and NIST Curves and we have no idea about how to backdoor an elliptic curve. Bernstein and Lange built a site claiming P-256 is not safe. But it actually boils down to the fact that NIST curves, generated in the 90s, lack some of the fancy features of more modern elliptic curves, as the fancy techniques were not known at the time.

To address your questions directly:

For compatibility reasons, since it's the most used elliptic curve.
Yes of course, e.g. TLS.
No, we believe it's secure.


Could randomisation make for a better book cipher?

From the Wikipedia page on Book ciphers:

  Essentially, the code version of a "book cipher" is just like any
  other code, but one in which the trouble of preparing and distributing
  the codebook has been eliminated by using an existing text. However
  this means, as well as being attacked by all the usual means employed
  against other codes or ciphers, partial solutions may help the
  cryptanalyst to guess other codewords, or even to break the code
  completely by identifying the key text. This is, however, not the only
  way a book cipher may be broken. It is still susceptible to other
  methods of cryptanalysis, and as such is quite easily broken, even
  without sophisticated means, without the cryptanalyst having any idea
  what book the cipher is keyed to.

So you would effectively have a very weird book that would be unknown to the attacker, but that isn't enough to make it secure.  In particular, (link)

  If you know 1,000 words, you will be between a functional beginner and
  conversational level in English.  In most of the world’s languages,
  500 words will be more than enough to get you through any tourist
  situations and everyday introductions.

Randomizing the word order wouldn't change the frequency clues.  Not being able to guess the book would add a small amount of additional security, but not enough to give it any meaningful improvement over a traditional book cipher.


Method to verify a signed archive's X.509 CoT

On the Software Developer side:

  Obtain a certificate from a public CA like verisign

Yes, you could use a CA, but you could also host your own CA. You'd of course need your clients to trust this CA.

Obtaining a certificate is probably more economic in the long term though.

  Generate a hash of your archive and then encrypt this string using the private key from your certificate, this is the "signature"

The signature generation in general contains the hashing operation. The hash algorithm is a parameter to the signature generation algorithm. The hash doesn't need to be encrypted, for instance ECDSA is not used for encryption.

Sometimes a hash tree is used instead - the hash over the data is not directly signed, but the hash is included in a structure also containing meta data (e.g. the MIME type of the data), and that structure is signed.

  Host the archive for download, along with a separate file which contains the public key from your certificate + the signature generated in step 2.

No, you'd leave the public key within the certificate. You can used either attached or detached signatures (see below).

On the (user) client side:

  Download and unpack the archive, download the signature + public key file

Right. Except that the public key file would be a certificate.

  Decrypt the downloaded signature using the downloaded public key, save this value

See above, decryption is not always used.

  Iterate through the public root certificates embedded within your operating system. For each root certificate, decrypt the signature value and compare the result to the result in step 2.

The chain is probably longer than two certificates (containing intermediate / server certificates), and certificates helpfully contain one or more "Issuer" fields to look up the higher level certificate. So there is no need to search for the root certificate top-down.

  Once a match is found in 3, you have verified that the author's private key descends from the chain of trust of the CA which you found matched in step 3 Note: This all assumes that the software developer used a CA for which we have an embedded root certificate in our clients OS.

Yes, by verifying the signatures in the certificates, but also validate CRL's for revocation, validate that the certificate is within the validity period, etc. etc.

Questions:

  Is the above method sound, or am I overlooking key details?

Yes, see above.

  Given a blank slate client, if I wanted to combine the public key + signature + archive into a single file that I could make the client understand and parse, are there any widely supported formats to leverage for organizing this data?

For systems using PKIX (Public Key Infrastructure using X5.09 certificates as issued by - for instance -Verisign) the best known container format is probably CMS, the Cryptographic Message Syntax.

There are of course various package managers (or "stores" nowadays) that may describe how software needs to be signed or otherwise managed. It could well be that they in turn use CMS to sign the software, but other protocols may be used as well.


Is an equality test possible when using paillier crypto?

No, you can't let a party test for equality with different keys without also allowing that party to guess and confirm the message contents.

I'll now show that a scheme that allows you to test for equality is trivially insecure against passive eavesdropping adversaries.

Suppose we're in the usual multiple-message eavesdropper game, that is our challenge messages actually are allowed to consist of multiple messages and we get the pair of individual encryptions as our challenge ciphertexts and are not allowed to ask the oracle for encryptions or decryptions.

Select $m_0=(m, m)$ and $m_1=(m, m')$ where $m\neq m'$.
Receive $c_b=(c,c')$ with $b\in\{0,1\}$ being chosen uniformly at random.
Use your special functionality "$=$" to evaluate $c=c'$. If it is true, return $b=0$ and if it is not return $b=1$.
Note that this special functionality may involve choosing a key for the cryptosystem yourself and encrypting $m$ and $m'$ under that key you know and which is unrelated to the key used for $c,c'$.

Obviously, this strategy works with the same probability with which you can detect duplicates, which is $1$ which is non-negligible and as such this scheme cannot be secure against eavesdroppers who can observe multiple messages and make this equality test.

Note that Paillier-Encryption is IND-CPA secure, meaning it is secure in the above scenario even when you'd be given a way to encrypt messages and as such Paillier-Encryption cannot possibly allow for passive equality tests without being given the decryption key.

The best technical solution I could offer for your problem is to let each party encrypt the hash of the contents for the storage provider and then let the provider make the deduplication based on these hashes which only he can read. But this bears the problem that the users can of course lie about the hash because you have no way of verifying it. Alternatively you could run Socialist-Millionaires-Protocols between all pairs of files (well their owners should) and you use the reported results (if they agree) for deduplication which again relies on the honesty of the users.


Is it easy to factorize a number of the form $n = t^{2} \cdotp p$?

Integers of the form $n = p\cdot q^2$, $p$ and $q$ prime, are the basis of a few public-key cryptosystems, including ESIGN, Okamoto-Uchiyama, cryptosystems based around the hardness of finding the class number of quadratic fields. As such, being able to efficiently factor numbers of this form would immediately break a number of cryptosystems. This would be a big deal. Additionally, this is also related to a classic problem in number theory, which would be of independent interest.

As far as concrete factorization algorithms targeting this type of integers, there are various strands:

Peralta and Okamoto slightly optimized ECM against this form, but the result is not significantly superior to regular ECM.
Boneh, Durfee, and Howgrave-Graham used Coppersmith-style root-finding techniques to factor $n$ in approximately $n^{1/9}$ operations when $p$ and $q$ are similarly-sized. While this may sound impressive, it is not better than the number field sieve for numbers of cryptographically-relevant size.
Castagnos, Joux, Laguillaumie, and Nguyen observed that, given some extra information about $n$ it becomes possible to factor $n$ in polynomial time. But this is not the general case and only applies to special cases, like NICE.


Is there an algorithm that allows verification that 2 encrypted or hashed bits of data are the same, given that I may only know half of the key/ salt?

I ran into a situation with a similar requirement, and here's the idea I came up with:

We don't use a conventional 'salted hash', instead to encode a user's password, we first hash it (optionally with the user's id, but without a salt) to form a value $h$, and then you select a random Elliptic Curve point $X$, you compute the point $Y = hX$ (where $hX$ is point multiplication), and then you encode store it as the pair of points $(X, Y)$.  To validate the password that the user enters, you again hash the password the user gave you, and then check if $hX \overset{?}= Y$; if it is, you accept the password.

This encoding is effectively one-way, given $(X, Y)$, it's infeasible to recover the password hash $h$ that would match it (assuming that we use a strong curve); this is the ECDLP problem.

$X$ effectively acts as salt; given a pair of encoded passwords $(X, Y)$ and $(Z, W)$, it is infeasible to determine whether they encode the same password; this is the dECDH problem.

And, finally (here's why it is of interest to you), it's updatable; at any time (be it once a year, or more often if we choose), we can select a random integer $r$, and replace $(X, Y)$ with $(rX, rY)$; effectively changing the salt we use without changing the password it matches.

Depending on your actual requirements, something like this might be adaptable to your situation.


Scheme that encrypt with $n$ pk that any sk of the pks can decrypt?

This is in no way practical, but it's relatively easy to describe a scheme.

If the public key contains (or allow easy derivation of) a unique prime (just has to be unique among the recipients - If every recipient knows the public key of any other recipient, and public keys can be ordered, we can use the first $n$ primes.), say $r_i$, you can use:
$$
C=\prod_{i=1}^n r_i^{\operatorname{enc}_{pk_i}(m)}
$$
(where $\operatorname{enc}$ is the function for encrypting to one recipient).

Then for decryption you "just" need to determine factor $C$ and determine the highest power of $r_i$ that divides it, and put the exponent into the function for decryption to one recipient.

I haven't tried to prove that it isn't easier to break this than to break than to break the scheme it's based on. I can't see why it would be though, and given how impractical this is, I don't think it matters much.


What is the Peer Signing digest on an OpenSSL s_client connection?

Peer Signing Digest is the hash algorithm used by the peer (i.e. the server from the perspective of the client) when signing things during TLS handshake. You will find these places by looking for the term digitally-signed in the TLS RFC.  See for example the details of the ServerKeyExchange message in wireshark:

  .. even with SHA1 hashes disabled on windows

SHA1 is not disabled on Windows in general. It is disabled only for use within the issuers signature of a certificate.


RSA cracking: The same message is sent to two different people problem

$c_1 \equiv m^{e_1} \bmod n$

$c_2 \equiv m^{e_2} \bmod n$

if $\gcd(e_1,e_2)=1$ then $\exists a,b\in\mathbb{Z} : e_1\cdot a + e_2\cdot b = 1$ ($a$ and $b$ can be found by extended euclidean algorithm)

And,

$m\equiv c_1^a\cdot c_2^b \bmod n$

Note: In practice, either $a$ or $b$ will be negative. WLOG, let $b$ be negative. This leads to problems in the above equation. To get around this, use the following computation.

Let $i\equiv c_2^{-1} \bmod n$ (i.e., the modular inverse of $c_2$)

$m\equiv c_1^a\cdot i^{-b} \bmod n$

Update to show details of $m\equiv c_1^a\cdot c_2^b\bmod n$. All math below done modulo $n$.

$$
c_1^a\cdot c_2^b\\
(m^{e_1})^a\cdot (m^{e_2})^b\\
m^{e_1a}\cdot m^{e_2b}\\
m^{e_1a+e_2b}\\
m^1\\
m
$$


How hard is it to generate a partial RSA fingerprint collision?

As far as we know, it is totally infeasible for anyone to create an RSA private key with a public key that has a specific 32 character fingerprint.  This remains true if you give the adversary a budget of a few billion dollars; the best approach for an adversary would be to try to break in and steal (or purchase) the private key (and the second best approach would be to factor the existing RSA key to obtain the private key, rather than trying to create a second one).

SSH uses MD5 to do its fingerprinting; the best way known to find preimages is just to go through a huge number of images, and hope to stumble across one that happens to hash into the value you're looking for; for this to work, we would expect to involve testing about $2^{128}$ images before we get lucky.  We might get lucky earlier than that; however we're more likely to hit the lottery than for this procedure to take less than $2^{100}$ trial images; creating and testing this number of RSA keys is completely unthinkable.

On the other hand, if we're looking for a partial match, for example, the first 4 characters and the last 4 characters (total of 32 bits), this changes entirely.

To attack this, we would need to generate and hash an expected $2^{32}$ RSA keys.  So, the question is "how realistic would such an attempt be for an attacker?"

Well, the answer is surpising; an attacker can probably do this in a few hours even if he has only one cPU at his disposal.

The immediate obvious objection to this is "it takes me quite a while - hundreds of milliseconds - to generate an RSA key; how can an attacker do it so much faster?".

Well, the answer is that the reason it takes you so long to generate a key is that you actually care that the RSA key is hard to factor, and so you spend a lot of time looking for large primes.  Now, it appears likely that an attacker might not actually take so much care that the RSA key he generates is as secure.

Once you stop caring whether the RSA key is actually secure, it becomes a lot faster to generate them; all you need to do is find a bunch of (say) 32 bit primes, and multiply them together in various combinations until he gets a match.  Once he has found an RSA public key that matches the parts of the hash he cares about, he knows the factorization of the RSA modulus, and so he can then generate the RSA private key, and he's good to go.

When you look at the inner-most loop of this procedure, it consists of taking a $N-31$ or $N-32$ bit number (of known factorization), multiplying it be a 32 bit prime, and then hashing that product, along with the $e$ value, and then seeing if that hash is partial match to the target.

I haven't tested it myself; it appears plausible that this multiplication and hashing might take a microsecond; if that guess is approximately close, then an attacker could, with a single CPU, find such a partial collision in a few hours.

So, to answer your clarification question: an attacker can easily find a match over 8 digits; he might (by using several CPUs and/or spending more time for the search) be able to find a match over 10 digits.  To go much beyond that would appear to require a zombie farm, or an array of FPGAs, or something other way of gaining more computing resources than are available to your average script kiddie.


What are the different use cases between an HMAC and digital signature?

Generally a digital signature is created using a private key and verified with the public key of an asymmetric key pair. Public keys can be easily distributed to verify the signatures.

It is however required that the public key can be trusted to be part of the correct key pair; the public key needs to be trusted. For this a public key infrastructure or PKI can be used. Probably the best known PKI is the PKIX infrastructure used by browsers. Here the public keys are part of X.509 certificates where the certificates are part of a trust chain. If such an infrastructure was not present then the attacker may have substituted a public key of his own key pair.

One thing that is not possible with signature generation is to sign with the public key. This is what allows the public key to be publicly distributed.

HMAC (which is just a specific MAC) is used with a single secret key, which is required for both the generation of the authentication tag (the MAC signature) and the verification of the tag. Anybody who has this key can therefore be a verifier and signer. The secret MAC key cannot be part of a PKI because of this.

Due to the issues with key distribution MAC schemes are either used by one party, or by a limited number of parties that have exchanged keys.

A MAC and signature algorithm can both be used for message authentication / integrity or entity authentication. However, due to the differences in how the keys are handled, MAC doesn't scale as well as a signature generation scheme.

On the other hand, symmetric algorithms are much more efficient than asymmetric ciphers, so if there is a choice then a MAC can be used to speed things up. A MAC is generally also more secure than a signature generation algorithm with regard to the key strength and resistance against quantum crypt-analysis.

As an example, in TLS 1.3 for HTTPS, entity authentication of the server is performed using a digital signature where the server has a private key and the client trusts a chain of certificates from a root CA to the certificate of the server.

However, the messages themselves are protected by a fast MAC - nowadays part of an authenticated cipher - after the session keys have been established. These session keys are - as the name implies - only used for the specific connection.


Why does Schnorr's Digital Signature scheme necessitate two prime numbers?

First of all, while Schnorr Signatures are usually described that way, the two primes are not necessary for it to work. In principle, Schnorr works in any cyclic group.

However, to achieve security we need that the discrete logarithm problem in that group is hard.
So the reason for the choice of $q$ (which is the group order) is that DL is believed to be hard in subgroups of prime order $q$ of $\mathbb{Z}_p^*$, where p is a safe prime, i.e. $p=2q+1$. (And also for other values than $2$, but I'm currently not sure what the conditions are.)


Which characters to take into account when calculating unicity distance?

The alphabet size you need to consider, when calculating the unicity distance, is the size of the ciphertext alphabet.  This follows from the definition of unicity distance, as the amount of ciphertext needed to rule out all but one of the keys.*

For a classical cipher that only encrypts letters to letters, and ignores spaces and case distinctions, the alphabet size would be 26 (or possibly less, e.g. if I and J are merged together).
For a cipher that uses exactly the alphabet you described (upper- and lowercase letters and spaces) for both plaintext and ciphertext, the alphabet size would be 2 × 26 + 1 = 53.
For a modern cipher that outputs one 8-bit byte for each plaintext character, the alphabet size would be 256.
For a hypothetical cipher that only outputs 7-bit bytes, the alphabet size would be 128.

Note that, in the formula $U = H_k / D$ for the unicity distance, the per-character redundancy $D$ should really be interpreted as the number of bits of information revealed by one additional ciphertext character.

This can be calculated as the number of bits encoded by one ciphertext character (i.e. as log2(alphabet size), if we assume the ciphertext to have no redundancy), minus the number of bits of entropy per plaintext character, assuming that each ciphertext character decrypts to one plaintext character.  For ciphers where this is not always the case, like the VIC cipher or other fractionating ciphers, things get more complicated.

(Another example of a fractionating cipher would be a modern block cipher in a mode like ECB or CBC that always encrypts or decrypts one full block at a time.  For such ciphers, it's arguably more meaningful to calculate the unicity distance in units of blocks rather than characters.  Of course, you can then convert the result back to, say, bytes, and typically get the same result as if you'd assumed a one-byte block size to begin with.  But you still can't really decrypt a partial block with such a cipher — except by brute force iterating over the missing part of the block, which makes your already slow brute force attack even slower.)

It's also worth noting that the whole concept of a constant "plaintext entropy per character" is somewhat nonsensical, since it's not really fixed — typically, the more plaintext you already have, the easier the next character is to predict (and, thus, the less entropy it carries).  The plaintext entropy also depends strongly on the assumed distribution of plaintexts, and, in practice, on how good the attacker is at recognizing valid plaintexts.  Thus, reasonable estimates for the unicity distance of the same cipher can in fact vary widely, depending what assumptions one makes.

*) In fact, this "casual" definition I gave has a subtle error: for most ciphers, there is no amount of ciphertext that can be guaranteed to rule out all keys but the correct one.  Rather, the usual formula for calculating the unicity distance gives approximately the amount of ciphertext needed to reduce the expected number of false positives (i.e. wrong keys that randomly yield a plausible decryption) to one.

This means that, if you have exactly one unicity distance worth of ciphertext, and try to decrypt it with all keys by brute force, you will, on average, end up with two keys that give a plausible plaintext — one correct key, and, on average, one false positive.  To actually be reasonably sure of getting no false positives at all, you'll need more than one unicity distance of ciphertext.


Could the Enigma algorithm be classified as a Feistel network?

Enigma is not a Feistel cipher. A "Feistel cipher" is a block cipher with a specific structure, namely the whole business with the two halves, the combination of one half with a (one-way) function of the other half and a reversible operation (e.g. XOR), and the swap. See the Wikipedia page which has nice schematics.

So considering Enigma as a kind of Feistel cipher is like considering a salmon as a kind of chicken: yeah, it has no beak, no feathers, no legs and no wings, but could it be a called a chicken ? Strangely enough, I tend to answer no to that. Even though both the salmon and the chicken are edible. But being edible is not sufficient to grant chickenness. Similarly, being a symmetric cipher is not sufficient to grant Feistelness.


AES MixColumns Predefined Lookup 2D Tables and Rcon Predefined Lookup 2D Table


The strength of ECDH public keys with small order

$g$ is a generator and is of order $P$.  Lagrange's theorem says that the order of an element in a group $\mathbb{G}$ divides the order of the group.

In your case, one has $\mathbb{G} = \langle g \rangle$.  Therefore, the order of an element $a = Ag \in \mathbb{G}$ is a divisor of $P$.  If $P$ is a prime, its two divisors are $P$ and $1$.  Hence, either $a$ is of order $P$, either $a$ is of order $1$ (in the latter case, $a$ is the neutral element ---the point at infinity on an elliptic curve given by a Weierstrass equation).


Choice of bilinear group for implementation of BLS signature with NIWI proof?

If you want to try a scheme that is already being used in the industry, you may try EPID.

A paper describing it is on IACR eprint 2009-095.


CTR mode nonce with aggressive key rotation policy

A 6-byte nonce can expect to receive a collision 0.01% of the time after around 240,000 nonce generations (based on a birthday attack). After 100 such rotations (a little under 17 years, based on your 2-month rotation policy), that comes out to a likelihood of just under 1% of experiencing a collision. On the surface, to me that seems like a reasonable margin of security.

If practical, you may also want to consider simply using an autoincrementing counter for your IV. Allow the first byte to be a machine identifier, and then use a mutex to synchronize access to the remaining five bytes. Whenever you need an IV, lock the mutex, read the current value as the IV, increment it by one, save it, and release the mutex. This allows you to encrypt over one trillion messages with a single key before the nonce rolls over, and has zero possibility of collision as long as you detect IV wraparound.


Edwards / Montgomery ECC over binary extension fields

So I had the following questions regarding (twisted) Edwards / Montgomery curves over binary extension fields:

  Do they exist?

Yes[1].  They have the form $$d_1 (x + y) + d_2 (x^2 + y^2) = x y (1 + x) (1 + y)$$ where $d^2 \ne {d_1}^2 + d_1$.  The identity is $(0, 0)$; negation sends $(x, y) \mapsto (y, x)$.  If $d_2 \ne \alpha^2 + \alpha$ for any $\alpha$, then like (nonbinary—represent!) Edwards curves, binary Edwards curves have a relatively simple complete addition law, detailed in the EFD.

  Are they any special, like Curve25519 and Curve448 are (i.e. easy side-channel resistant implementation)?

BBE251[2] is the binary Edwards curve over the field $\mathbb F_2[t]/(t^{251} + t^7 + t^4 + t^2 + 1)$ with coefficients $$d_1 = d_2 = t^{57} + t^{54} + t^{44} + 1.$$  Like Ed448-Goldilocks, BBE251 was chosen to optimize certain performance metrics within this shape, subject to security constraints detailed in the paper; for example, the small Hamming weight and convenient shape of the polynomial $t^{251} + t^7 + t^4 + t^2 + 1$ makes reduction cheaper, and the small degree and Hamming weight of $t^{57} + t^{54} + t^{44} + 1$ makes multiplication cheaper.

The accompanying software computes a batch of thousands of scalar multiplications in somewhat fewer cycles per key on average than contemporary software for elliptic curves over prime fields of similar conjectured security levels.  Even though software doesn't make fast binary field arithmetic easy, the simple complete addition laws make for easy bit slicing in batch computation.

(Side note: There's nothing particularly special about Curve25519 and Curve448 among Montgomery curves over nicely shaped prime fields that makes them encourage side channel resistance.  Their equations $y^2 = x^3 + A x^2 + x$ have small coefficients $A$, which makes for a cheaper ladder, but that's a performance optimization, not a security concern.  Their primes $2^{255} - 19$ and $2^{448} - 2^{224} - 1$ make for fast constant-time reduction algorithms, but it's not clear that there's any security analogy here when the premise is a bit-sliced batch algorithm anyway.)

  Are there standardized curves for them?

Not to my knowledge.

There has been relatively little interest in these curves, it seems, perhaps in part because without a batch advantage they are extremely slow to compute in constant-time software, and perhaps in part because the security of binary field curves seems shakier and not as well-understood—or at least not as confidently understood—as large prime field curves[3].

More recent performance results like [4] are heavily dependent on CPU support for binary field arithmetic, and even then it's not clear that binary Edwards curves are competitive in performance with other alternatives, particularly alternatives that take advantage of fast endomorphisms.


How does future secrecy fail for Signal group messaging?

Note: It seems that future secrecy fails due to the ability to join a group just by knowing its GroupID.

Correct, this seems to be the issue. Since an attacker can join a group by learning some of the session states and thereafter compromise all messages due to being a part of the group, the group protocol lacks future secrecy.

From the paper (page 8 of the pdf): "After adding herself to the group, the confidentiality of future plaintext messages is compromised."

  Assuming that group update messages are properly authenticated, does future secrecy still fail for Signal's group messaging?

Due to the use of the double ratchet, it would retain that property if knowing the session state would not allow joining the group. But details matter in achieving that. It is not sufficient to just authenticate the group update since we are talking about a situation where the keys of one party are compromised.

However, you are right that it seems to be only the group administration that needs to be fixed.


Understanding math behind RSA key derivation

Well, if $e$ is not relatively prime to $\phi(N)$, then there won't be any such $d$; in fact, there generally won't be a unique decryption.

For example, let us consider the toy example $N = 77$ and $e=3$.  Note, that $\phi(N) = 6 \times 10 = 60$ is not relatively prime to $e$.

Then, let us assume that we receive a ciphertext $41$, and we need to find the plaintext $P^3 \equiv 41 \pmod{77}$.  The problem is that there are three; we have $P=13$; as $13^3 \bmod 77 = 41$.  However, we also have $P=24$; as $24^3 \bmod 77 = 41$ as well.  pick a plaintext $P=13$ and compute the corresponding ciphertext $C=13^3 \bmod 77 = 41$.  $P=68$ also works.  So, which is the right one?  The decryptor has no way of knowing.

We avoid this problem if $e$ and $\phi(N)$ are relatively prime.


There are 4294967296 nonces, because it is 32-bit.

Most of the time, none of the nonces will produce a "Golden Block".
If none of the nonces work, the miner must make a new block (with a different Merkle root (256 bits) which means the block has different transactions in it) and try to mine that block instead.

Currently, about 99.999999994% of blocks don't have any valid nonce. That means the miner must try over 15 billion blocks before it finds one that has a nonce.

This is not a problem, because one of the transactions in a block is the one which gives the bitcoins to the miner. The miner can't change other peoples' transactions, but it can add extra unused bytes to its own transaction, which means the block has different transactions in it, and a different Merkle root.


Staying PCI compliant while upgrading encryption

Supplementing RSA-1024 with SHA-256 instead of SHA-1 won't cut it from a PCI-DSS compliance standpoint: RSA-2048 is a minimum for a large class of uses according to PCI-DSS's definition of

  Strong Cryptography: Cryptography based on industry tested and accepted algorithms, along with key lengths that provide a minimum of 112-bits of effective key strength and proper key-management practices (..)
  At the time of publication, examples of industry-tested and accepted standards and algorithms include AES (128 bits and higher), TDES/TDEA (triple-length keys), RSA (2048 bits and higher), ECC (224 bits and higher), and DSA/D-H (2048/224 bits and higher). See the current version of NIST Special Publication 800-57 Part 1 for more guidance on cryptographic key strengths and algorithms.
  Note: The above examples are appropriate for persistent storage of cardholder data. The minimum cryptography requirements for transaction-based operations, as defined in PCI PIN and PTS, are more flexible as there are additional controls in place to reduce the level of exposure.
  It is recommended that all new implementations use a minimum of 128-bits of effective key strength.

Also, just switching from SHA-1 to SHA-256 arguably would not help against real attacks: as a general rule, a security chain can only be as strong as its weakest link; and in many usage patterns, second-preimage (rather than collision) is what matters, making RSA-1024 a weaker link than SHA-1 is.

Addition following comment: SHA-1's collision resistance is weaker than RSA-1024. But in most applications, a successful attack requires breaking the hash's second preimage resistance, and SHA-1 remains extremely strong against that. There are a few exceptions where breaking collision resistance matters, like attacking an hypothetical certification authority still issuing SHA-1 based certificates and using predictable certificate numbers; but notice that from the standpoint a PCI-DSS entity, using a strong hash does not help protect from this hypothetical attack; what matters is that acceptors of certificates reject certificates made with SHA-1 (or reject certificates issued by authorities that do not have a policy stating that when they issue certificates based on SHA-1, they use an unpredictable certificate number).


Total password count, given length and pool size

Possible combinations (permutations) = sequenceOptions to the power of sequenceLength

Assuming a pool of 95 sequence options

sequenceLength 0 = 0 permutations (950)
sequenceLength 1 = 95 permutations (951)
sequenceLength 2 = 9025 permutations (952)
sequenceLength 3 = 857375 permutations (953)
etc

This is not limited to passwords/characters. For example, when a password is put through a key derivation algorithm, it ends up as a string of bits for which there are two options; 0 and 1.  Hence, a 256 bit length key contains 2256 permutations.

More simply, a 4-digit numeric pincode has 10000 (104) possible permutations.

As for the second part of your question, yes; if the sequenceLength were <= 8 then the total number of permutations would be 950 + 951 + 952 + 953 + 954 + 955 + 956 + 957 + 958

Of course, the above assumes that each option in the sequence can appear more than once. If that's not the case then factorials come into play.


What is Identity-Based Encryption (IBE) and why is it "better"?

Conventional public-key cryptosystems require key distribution: in order to encrypt a message destined to Bob, you must know Bob's public key with enough certainty (an attacker could try to substitute his own key there). Various systems have been designed for that, e.g. certificates. In practice, key distribution proves complex.

With IBE, the name (email address) of Bob is his public key, so it is already distributed. To understand it, imagine the following model: there is a trusted central service, to which you send the email; the central service forwards it to Bob, and all communications are encrypted. This is how encrypted communications worked before the invention of RSA, so it is an old model. It has two drawbacks:

the central service must be trusted (it has the power to read all emails);
the central service must have oversized optic fibers and thousands of processors because every message goes through it.

IBE uses high-level mathematics to remove the second issue. With IBE, the "central service" must exist, but it needs not be "online"; its real-time action is replaced with a mathematical pairing.

Another, more mathematical way to say it, is that with IBE, a central authority has a key pair. The central authority can compute the private key corresponding to a given "public key", where public keys can be just any sequence of bits, e.g. email addresses. You cannot do that with RSA: RSA public keys have a strong internal mathematical structure. With IBE users key pairs, not so. The counterpart of that property is that the central authority public key must be involved in the encryption and decryption processes. In a full-fledged IBE system, users obtain their own private key from the central authority; afterwards, no need to talk to the central authority.

Voltage Security sells IBE-based products (Dan Boneh is one of the founders of that company). The practical point of IBE is to "avoid" certificates. See Voltages pages to get some descriptions of IBE; also, the Boneh-Franklin article is a good source of information. Details on the actual computation of Weil and Tate pairings are intricate; Ben Lynn's thesis is a good starting point.


Why do we use XTS over CTR for disk encryption?

Suppose you use the sector number times the number of AES blocks per sector as the initial value for CTR. If you successively store the content $M$ then $M'$ in the same sector $n$ then $E^{CTR}_n(M) \oplus E^{CTR}_n(M') = M \oplus M'$ (where $E^{CTR}_{n}$ is the encryption function with CTR mode and IV started for sector number $n$). CTR mode fails catastrophically when you reuse a counter value, because it's a pure xor stream cipher: xorring two ciphertext blocks that were produced with the same key and counter values cancels out the encryption. For example, if the block started out as all zeroes (which happens pretty often in practice) and an adversary manages to obtain both the initial ciphertext and the updated ciphertext, then the adversary has the confidential plaintext on a platter.

If you use the sector number as the initial counter, it's even worse since the second block of a sector shares a counter with the first block of the next sector and so on. That would enable an adversary to reconstruct a lot of content with even a single snapshot of the disk.

To use CTR safely, you need to generate a fresh counter value each time. You can use the sector number as part of the initial counter value, but there's little value in doing so, because you'll need to store the rest of the counter (some kind of per-block update count, a global counter value, a random value, or any other scheme) anyway.

XTS incorporates the sector number as a tweak. Any change in the plaintext results in a complete change of the content. An adversary who knows the content of a sector at two different times can observe whether the content of the sector has changed, which is unavoidable for deterministic encryption, but if the content has changed, then the adversary obtains no information about the plaintext.

If the only threat is that the disk is stolen, so that an adversary will only ever obtain one version of the ciphertext and no more plaintext will ever be encrypted after that, then I don't think there's any benefit in using XTS over CTR.

If the adversary can observe the ciphertext at different times, XTS does a better job. Not perfect though: you need the extra burden of storing an IV of some kind for that.

If the adversary can modify the ciphertext, then you need to worry about data integrity as well. CTR is extremely malleable: the attacker can flip plaintext bits by simply flipping the corresponding ciphertext bit. XTS is less malleable but still allows the attacker to replace good content with garbage or with older content. Authenticated encryption modes combine encryption with a MAC, and thus provide both confidentiality and authenticity (and if done right, integrity).


Is there any hash function that relies on integer exponentiation instead of XOR?

You can use the discrete log-based hash given by $H(x,y) = g^x h^y$, where $g$ and $h$ are two randomly chosen group elements. If your group has known prime order $p$, then this function is collision-resistant if and only if discrete logarithm is hard in your group. In particular, if you find a collision, $g^x h^y = g^{x'} h^{y'}$, then you get $g^{x-x'} = h^{y'-y}$. This means that $x - x' = \log_g h \cdot (y' - y) \mod p$. Since $p$ is prime and $y \neq y'$, we can invert $y'-y$ modulo $p$ to compute the logarithm.

This is assuming that you want a collision-resistant hash function. If you want something stronger, then this might not be suitable for you. E.g., this obviously has the property that $H(x+1,y) = g \cdot H(x,y)$, which could be really bad in some applications.


Verifying Self-signed SSL Client Certificates

Your problem boils down to the following:

Client shows $v$ (his certificate).
Server wants to know whether $v$ is the same one as previously. He may store $v$ itself, but $v$ is somewhat bulky, so the server would like to store $h(v)$ only, for a hash function $h$.

So can an attacker show up with a value $v'$, distinct from $v$, such that $h(v') = h(v)$ ? If the attacker can, he wins. If he cannot, then storing $h(v)$ is sufficient.

If the hash function is second preimage resistant, then, by definition, the attacker cannot. SHA-256 is believed to be second preimage resistant.

I must also insist that the certificate is only the public part; the server must still extract the public key from the certificate sent by the client, and use it to verify the signature sent by the client as part of the ClientKeyExchange handshake message. Normally, the SSL implementation takes care of that point.

An edge case happens with DSA public keys. A DSA public key contains some parameters (modulus $p$, subgroup order $q$, generator $g$) and the actual user-specific public value ($y$). It is allowed, as per X.509, to omit the parameters from the certificate, keeping only $y$, if the certificate is signed by a CA which also uses DSA with the same parameters. This is parameter's inheritance. This is not compatible with your idea, because the client's public key cannot then be extracted from the user's public key alone; you still need X.509 path validation. But, in practice, this won't happen: nobody really uses DSA certificates, let alone DSA with parameter inheritance.


libsodium x25519 and Ed25519 small order check

Short answer: You don't need to worry about the blacklist or point validation unless you are designing an exotic protocol.

Medium answer:

It depends on what you are trying to do.  There is a short blacklist, and a much larger set of points (too large to list) that may cause you trouble—but only if you are setting yourself up for trouble by using the primitives in an unusual novel protocol and expecting unusual security properties from them.

The ‘blacklisted’ points have low order: each point $P$ has the property that there is a very small number $n$, in this case always a divisor of 8, such that $[n]P = \mathcal O$.  Thus there are only at most 8 different scalar multiples of each of these points.

This significantly reduces the number of possible shared secret values that someone computing a ‘shared secret’ using their private secret scalar $n$ and a malicious peer's ‘public key’ $P$, nearly or completely negating the contribution of the secret scalar $n$ of which there are $2^{251}$ possibilities.  None of the low-order points are actually valid public keys: the standard base point $B = (9, \dots)$ does not generate them.

In sensible protocols, you normally don't need to worry about these points at all:

In an interactive key agreement, (a) a malicious peer is usually out of scope, (b) a MITM should be detected by authenticating the transcript, and (c) you hash the entire transcript of the key exchange including the shared secret and the hapless sap's public key $[n]B$ to produce a session key for a subsequent conversation.
In a signature system, you rely on verification under known public keys; a malicious signer giving one of the ‘blacklisted’ points is out of scope.  Blacklisted points in signatures can't fool verifiers—the signature scheme would be horribly broken if they could.

For more details on validation, see Trevor Perrin's article on point validation in such protocols.

Any other properties, you have to be very careful about, e.g. uniqueness of public keys or signatures—and here the blacklist is not sufficient.  Why is the blacklist not sufficient for some obscure applications requiring obscure security properties?  If $P$ is a point of low order, and $n$ is a legitimate user's secret scalar, then for any point $Q$ generated by the base point $B$, $[n](P + Q) = [n]Q$.  This happens because every legitimate secret scalar is a multiple of 8, the cofactor, and so annihilates $P$, i.e. $[8]P = \mathcal O$ is the identity.  Such incautious design of a novel protocol requiring novel security properties thoroughly flummoxed Monero last year, after a casual comment by Trevor Perrin explaining this.

Long answer:

The groups that X25519 and Ed25519 work in have some nontrivial structure which make the so-called ‘invalid points’ relevant.  I'll focus on X25519.

Every group has an identity element, which we call $\mathcal O$.  Every element $P$ of a finite group (written additively) has a finite order $n = \operatorname{ord}(P)$, the smallest positive number of times that adding it to itself $P + \cdots + P = [n]P$ yields the identity $\mathcal O$.  The order of the identity is 1; all other points have order greater than 1.

X25519 works in the prime field $\mathbb F_p$ where $p = 2^{255} - 19$, also known as $\mathbb Z/(2^{255} - 19)\mathbb Z$.  Specifically, it works on bit string encodings of the $x$ coordinates of points on the curve $$E/\mathbb F_p \colon y^2 = x^3 + 486662 x^2 + x.$$  Every curve point $P$ except the identity $\mathcal O$ has an $x$ coordinate, which we will call $x(P)$.  We additionally define $x_0(P) = x(P)$ when $P \ne \mathcal O$, and $x_0(\mathcal O) = 0$.

It turns out that if $P \in E(\mathbb F_{p^2})$ has $x_0(P) \in \mathbb F_p$, then for every integer $n$, $x_0([n]P) \in \mathbb F_p$, and every $P$ with the same $x_0(P)$ has the same $x_0([n]P)$.  That is, scalar multiplication keeps the $x$ coordinate in the base field $\mathbb F_p$ and not in an extension field, and the $x$ coordinate of the scalar multiple $[n]P$ is uniquely defined by the $x$ coordinate of the base point $P$.  This is Theorem 2.1 of the Curve25519 paper.

You don't need to understand all the details—suffice it to understand that since we work only in encodings of elements of $\mathbb F_p$, the only points we ever have to worry about are those in the group $E(\mathbb F_{p^2})$ with $x$ coordinate in $\mathbb F_p$.  (Why might we have to worry about $\mathbb F_{p^2}$ at all, a quadratic extension of $\mathbb F_p$ that adds fabricated square roots to nonsquare elements of $\mathbb F_p$?  There are some $x$ coordinates for which $x^3 + 486662 x^2 + x$ is nonsquare, so there is no corresponding $y$ coordinate in $\mathbb F_p$, but there is one in $\mathbb F_{p^2}$.)

The group $E(\mathbb F_p)$ of $\mathbb F_p$-rational points, or roughly those whose coordinates are in $\mathbb F_p$ and not an extension field (more precisely, the fixed points of the componentwise action of the automorphism group of $\overline{\mathbb F_p}$ that fixes $\mathbb F_p$; this definition works with projective coordinates too), has $8 p_1$ elements, where $p_1 = 2^{252} + 2774231777737235353585193779088364849$ is prime, and 8 is called the cofactor.  By a standard theorem of group theory, the order of every element of $E(\mathbb F_p)$ divides $8 p_1$.  This means that every element of $E(\mathbb F_p)$ has one of eight possible orders: $\{1, 2, 4, 8, p_1, 2p_1, 4p_1, 8p_1\}$.

The twist group, which is the subgroup of $E(\mathbb F_{p^2})$ with $x$ coordinates in $\mathbb F_p$ and $y$ coordinates not in $\mathbb F_p$, has $4 p_2$ elements, where $p_2 = 2^{253} - 5548463555474470707170387558176729699$ is also prime.  This is the group that we don't ordinarily work with (there is no multiple of the standard base point in this group except the identity), but which about half the possible $x$ coordinates that X25519 can handle will decode to.  Thus, the order of every element in the twist group divides $4 p_2$, and therefore the only eight possible orders are $\{1, 2, 4, p_2, 2p_2, 4p_2\}$.

Legitimate X25519 users choose public keys of the form $x_0([8a]P)$, where $P$ is a standard base point of prime order $p_1$, and shared secrets of the form $x_0([8a]B)$, where $x_0(B)$ is their peer's public key.  The factor 8 means that the public key $x_0(B + Q)$ for a point $Q$ of order 8 (also called an 8-torsion element) yields the same shared secret as the public key $x_0(B)$, because $[8a](B + Q) = [8a]B + [8a]Q = [8a]B + [a][8]Q = [8a]B + [a]\mathcal O = [8a]B$.  A malicious peer could choose such a $B + Q$, which is bitwise distinct from $B$ but always yields the same shared secret.  A malicious peer could choose $B$ not of the form $[8b]P$ at all but rather a point of low order, which would reduce the number of possible shared secrets to 1, 2, 4, or 8.  E.g., they could choose $\mathcal O$; then the ‘shared secret’ would be $x_0(\mathcal O) = 0$—that's where the zero check comes from.

The blacklist is the list of all points that will give zero as the ‘shared secret’.  It does not list all illegitimate public keys—there are too many to list, of the form $B + Q$ where $B$ is a legitimate public key (of which there are $p_1$ possibilities) and $Q$ is on the blacklist.  The only way to detect legitimate public keys is to confirm that $[p_1]B = \mathcal O$.

But for most protocols the threat model that could cause trouble by substituting illegitimate public keys is irrelevant because the same attacker, the same malicious peer, could cause trouble in all sorts of other ways anyway.  For example, in DNSCurve, which was probably the original application of X25519 using static-static DH key agreement, the only problem that a malicious nameserver or user could cause by using an illegitimate public key is to leak the peer's secrets on the wire to an eavesdropper—which they could do anyway.


Why is hybrid encryption more effective than other encryption scheme?

Alice also needs to first decrypt the symmetric key and then decrypt the message. It almost seems like a double work.

Encrypting a short plaintext (i.e. the symmetric key) requires only one asymmetric (e.g. RSA) operation, while encrypting a longer message would in theory require many RSA operations.

Suppose we want to encrypt a 1 MiB message.  Using 2048-bit RSA-OAEP exclusively (i.e. without hybrid encryption) would require over 5500 RSA encrypt operations (leaving aside for now the question of mode of operation), all of which are expensive in terms of performance.  Using hybrid encryption, we can perform a single expensive RSA encrypt operation on a symmetric key, and do all of the remaining work using fast symmetric encryption like AES-GCM.

  Along with sending data here it also needs to [send the] key along.

You're right about this.  Hybrid encryption does make the ciphertext longer in cases where the messages are very short.  However, 2048-bit RSA-OAEP (for example) operates on plaintexts of at most 190 bytes, so the threshold at which hybrid encryption becomes more efficient is fairly low.


How to create the right Blowfish padding?

I use the OpenSSL library for Blowfish encryption in ecb mode. [...] What am I doing wrong?

You're using ECB mode and no authentication.

But as for the question itself.

Your input length is 29+1 bytes, which should get padded to 32 bytes, which should be ceil(32/3*4) = ceil(42.67) = 43 characters when base64-encoded, plus one = to round up to four. The output from the site you linked to seems to be of that length, but the output from your code looks like 48 characters, or 36 bytes. Extra bytes appear to show up from somewhere.

The output is made using this call to base64_encode:

unsigned char *out = (unsigned char *)malloc(OutSize);
base64_encode(out, strlen((char *)out))

The length is determined with strlen. But is the data in the out buffer terminated with a zero byte? I don't see that terminator anywhere, so it may be that strlen and hence base64_encode read past the buffer.
Check what the strlen output is, compared to OutSize.

In any case, the output from the cipher might contain zero bytes too, so I don't think you should be using strlen here at all.

Also, the padding you are using destroys the length of the plaintext. That is, foobar and foobar0 pad to the same string, foobar00 and there's no way to tell them apart. You may want to consider some other method of padding. (Basically, encode the length of the padding in the padding itself, which means you may need to pad a full block.)


What's the proper way of fitting hash digest to encryption scheme?

A universal one-way hash function (or UOWHF), also known as a target-collision-resistant (or TCR) hash function, is a randomized hash function $H_r(m)$ with the following security: If an adversary commits to a message $m$, then upon being challenged with a random $r$, the adversary cannot find a distinct message $m' \ne m$ such that $H_r(m) = H_r(m')$.  (More details, background, history, and references on UOWHF/TCR, particularly in signature applications.)

Any collision-resistant hash function is obviously also TCR, but TCR is a much weaker security property—much all major ‘cryptographic hash functions’ like SHA-256 including broken ones like MD5 are generally conjectured to exhibit TCR in prefix-hash form $H(r \mathbin\| m)$ and in HMAC form $\operatorname{HMAC-\!}H_r(m)$, but in the off chance that they don't (the Merkle–Damgård construction does not necessarily preserve TCR), there's a generic construction called RMX from Halevi and Krawczyk's research program on randomized signatures, which was standardized by NIST in SP 800-106.  If you like more modern flavors, you could use keyed BLAKE2 or KMAC128 too, since TCR—and the slightly stronger eTCR—was an explicit design goal for SHA-3.

If you want a smaller digest, just truncate the hash function; if you want a larger digest, the easiest way is to use an XOF like the SHA-3 function SHAKE128 or like BLAKE2x.  You could also use SHA-256 in ‘CTR mode’, yielding $H(r \mathbin\| m \mathbin\| 0) \mathbin\| H(r \mathbin\| m \mathbin\| 1) \mathbin\| H(r \mathbin\| m \mathbin\| 2) \mathbin\| \dotsb$, provided you make sure to pad it unambiguously, or use a standard (if somewhat more complicated) construction like HKDF-SHA256 or MGF1 of PKCS#1.


is the perfect secrecy of one time pad dependent on the xor randomness preserving property?

(Answering my own question).

One time pad retains perfect secrecy using any operator $\Delta$ showing the following property: for a plaintext $M$ and a key $K$, the cyphetexts $C =  M \Delta K$ is such that there is a the same constant number of $K$s that encrypt $M$ to $C$, for any tuple ($M$, $C$). Specifically, if the length of the key equals to the length of the plaintext, then for each pair ($M$, $C$) there is a single, unique key that encrypts $M$ to $C$.

Therefore, not only xor but also other operators, such as applying Vigenère cipher with a uniformly generated key whose length equals to the message length, are suitable for one time pad.

the "random preserving" property, i.e. the uniform distribution of $C$ given a uniform distribution of $K$ and regardless of the distribution of $M$, is indeed equivalent to the above definition: if $\Delta$ preserves randomness there is necessarily the same number of $K$s for any pair ($M$, $C$) - otherwise, the distribution of $C$ wouldn't have been uniform; and if there is a constant number of keys for any pair then necessarily all cyphetexts are generated with an equal probability.


Why do we require a CSPRNG's output to be indistinguishable from true random?

We simply strive for crypto that's as close as possible to ideal. Indistinguishably is the strongest property we can demand from a PRNG/streamcipher.

It's hard to predict which non ideal properties will lead to problems at some point in the future. For example the non ideal properties that lead to padding oracles, BEAST, CRIME or the RC4 biases were known for years before they were shown to be exploitable.

Many security proofs assume indistinguishability, so if the PRNG is distinguishable, this weakens the proof. If the PRNG is distinguishable under certain conditions, even if it's a seemingly harmless distinguisher, then a proof relying on indistinguishability becomes useless if those conditions are met.

Consider a message encrypted using a block-cipher in CTR mode. This has the property that no blocks in the key stream will be identical (just like Fortuna/Yarrow without re-keying). When the ciphertext contains identical blocks, the attacker knows that the corresponding plaintext blocks were different, because the corresponding key-stream blocks were different as well.
Admittedly that's not a huge leak in most contexts, but it is a leak. It might lead to problems in some contexts, for example if the message only uses a few different values for each block.


Breaking ciphertext using a quantum computer when the public key is not available

You asked:

  Is it possible to crack RSA / ECC on a quantum computer if we only have ciphertext and don't have the public key used to encrypt itself?

Typically not, with a few exceptions; here are the exceptions:

RSA signatures with deterministic padding (eg. PKCS #1.5) and a small to moderate $e$ (e.g. $e = 65537) - with two signatures (and corresponding message), we can recover the public key with a conventional computer (and then use our quantum computer to break it).
ECDSA signatures - with one signature (and corresponding message), we can recover the public key (with a few "false hits") with a conventional computer; we can then use our quantum computer to break it.

Things that likely look immune:

RSA encryption (which always uses random padding), or randomized RSA signatures (e.g. PSS); the relationships between the plaintexts would appear to be too subtle for the attacker to use them.
EdDSA signatures - because of how the public key is stirred in, the key recovery method we used with ECDSA doesn't work (and without the public key, the attacker can't compute $H(R, A, M)$, which you need to know to have a copy of generating a forgery)
ECIES - the ciphertext consists of $rG$ (for some random $r$) and a symmetric ciphertext that is keyed based of $rP$; the attacker could recover the value $r$ with his handy quantum computer, however without knowing $P$, there's not much else he can do (and having multiple ciphertexts wouldn't appear to help).


Last year the paper Factoring as a Service was published, where Amazon EC2 is used to factorize a 512bit RSA modulus in just four hours for $75.
As far as I know, that is currently the fastest/cheapest approach actually used.


Why does Fortuna RNG use double SHA-256?

Ferguson and Schneier define SHAd-256 in their book Practical Cryptography in Chapter 6.3.1 Length Extensions.

  For any hash function SHA-X, where X is 1, 256, 384 or 512 we define SHAd-X as the function that maps m to SHA-X(SHA-X(m)). In particular, SHAd-256 is just the function m ↦ SHA-256(SHA-256(m)).

They clearly defined SHAd-256 to prevent length extension attacks.

I don't know why Ferguson and Schneier also used SHAd-256 when they designed Fortuna, but I assume that they preferred a hash function invulnerable to length extensions over a vulnerable one even if it might not matter for a particular use.


how can I draw from a set of characters using a seed for entropy?

Yes, this strategy works, in the sense that it generates each character with the appropriate distribution, and there is not trivial attack (with the caveat that the formatting used must allow to unambiguously find $S$, $i$ and $c$ from the concatenation $S\|i\|c$; formatting $i$ and $c$ as fixed-width fields will do). However

We do not have a strong security argument: for this we'd need a MAC keyed by $S$, e.g. use $\operatorname{HMAC-SHA256}(S,i\|c)$; the HMAC construction turns a hash into a MAC, with a proof.
There is no entropy-stretching, nor salt, as in standard password-based key derivation; thus a guess of $S$ can be checked with low odds of errors knowing a password and it's $i$; if the seed string $S$ is low-entropy (like a master password), that's a huge problem.
We can obtain the appropriate distribution with far less hashes; see this.

Point 2 is by far the most worrying.


Hardness of elliptic curve discrete logarithm problem?

This depends a bit on your group structure because P0, P1, P2 could lie in small subgroups but if you avoid that you are still trying to solve a hard discrete logarithm problem.


How to salt PBKDF2, when generating both an AES key and a HMAC key for Encrypt then MAC?

I'd use HKDF's "expand" step to generate multiple keys from one masterkey.

Use PBKDF2 to derive that masterkey from the password and salt. i.e. replace the "extract" step of HKDF with PBKDF2.

//Extract
MasterKey = PBKDF2(salt, password, iterations)

//Expand
AES-Key = HMAC(MasterKey, "AES-Key" | 0x01)
MAC-Key = HMAC(MasterKey, "MAC-Key" | 0x01)

(where | denotes concatenation)

Having PBKDF2 output more than its native size is a bad idea IMO. It increases the cost for the defender considerably (multiple key derivations with thousands of iterations) but doesn't increase the cost for the attacker(he can verify correctness of his password guess after one key was derived, he doesn't need both).

If you use a 512 bit hash, such as SHA-512 in PBKDF2 (PBKDF2-HMAC-SHA-512) you can also get away with simply splitting those 512 bits into two parts, using one for encryption and the other for MAC. But IMO the HKDF approach is cleaner.


How can create a proof that we have a sequence of binary digits?

If I understand correctly, you're asking to prove that you have the result of running a secret input through a public process without revealing anything about this result.

For this proof to be an interesting one, you would have to output some value and then prove how it relates to the values you're hiding. If you don't do that, then you're simply proving that you ran any value through a public process. Since anybody can run values through a public process, this wouldn't be interesting. Does that make sense?

In other words, it's important that you figure out what is interesting about your proof. i.e. is there some fixed secret information you would need to have to prove what you're trying to prove?

If you reveal, say, the encryption $c$ of the bit string under a public key $pk$. Then proving that $c$ is the encryption under $pk$ of some bitstring $y$ seems like it could be interesting. You would probably also have to prove that $pk$ was generated honestly. Assuming unique decryption, this combination of proofs will fix the witness $(x,sk)$ which leads to the output $(c,pk)$.

This proof can be framed as an NP language where the value $(c,pk)$ has witness $(x,sk)$. You can then use standard zero-knowledge.


Hash function composition - security level

z(x) is equivalent to f(x) for your use case. MD5 has known collision vulnerabilities, so your overall output will suffer from the same vulnerabilities. Also since the output is 128 bits long it is discarding the additional security margin of having a longer hash output.

Using SHA-512 alone is safer. If length extension attacks are an issue either use SHA-512/256, SHA3, Blake2b, HMAC, or another secure hash function immune to such attacks.


$\mathbb{Z}^*_{13}$ is a group with 12 elements, not 13.

A group is defined by a set of elements, and a "law". The law combines two elements and yields a third one within the set. You get a group if the law fulfils some properties (the law is associative, there is a neutral element, each element has an opposite in the group).

$\mathbb{Z}_{13}$ is a group with 13 elements, using "addition modulo 13" as group law. The neutral element is $0$; the opposite of $4$ is $9$ (because $4 + 9 = 13 = 0 \mod 13$).

$\mathbb{Z}^*_{13}$ is a group that uses "multiplication modulo 13" as group law; it contains all the elements that are invertible modulo 13. Since 13 is prime, these are all elements of $\mathbb{Z}_{13}$ except $0$; so you get 12 elements (the integers $1$, $2$,... $12$ modulo $13$). The neutral element is $1$ (multiplying any element by $1$ leaves it unchanged). The opposite (traditionally called "inverse" since the law is called "multiplication") of $4$ is $10$ (because $4\times 10 = 40 = 1 \mod 13$).

A generator for a group is an element $g$ such that applying the law repeatedly on it ultimately yields all the group elements. In $\mathbb{Z}^*_{13}$, $2$ is a generator for the whole group: if you multiply $2$ by $2$ then you get $4$; if you multiply $4$ by $2$ you get $8$; multiply by $2$ again and you get $3$; then $6$, $12$, $11$, $9$, $5$, $10$, $7$, then $1$. You got all 12 elements. On the other hand, $8$ is not a generator for the whole group since it generates only $8$, $12$, $5$ and $1$.


Computational Complexity of SHA-3 (SHAKE128)

Strictly speaking, computational complexity is certainly not the right term. It is an asymptotic notion, describing the approximate behaviour of the cost for "large enough" inputs. SHAKE is an "extensible output function" (XOF) and its computational complexity is $O(m + n)$ where $m$ is the size of the input, and $n$ the size of the output. I.e., it's "linear". However, this does not apply to your case, where the input size is fixed (100 bits) and I suspect that your output size is also fixed. The "complexity" is when the input size "tends towards infinity", and 100 will never go toward infinity; it's fixed.

Therefore, we have to assume that reviewer of that journal uses the expression "computational complexity" in a loose, technically incorrect sense, to express the notion of "cost". In simple words: if somebody implemented your proposed protocol on some specific hardware (e.g. a PC), and ran it, to what extent would your specific choice of SHAKE would impact overall performance metrics of the system?

To take an example: consider SSL/TLS. That protocol starts with a complicated process call the "handshake", through which a client and server agree on a common shared secret, used thereafter to encrypt data. The bulk of the cost is in the data encryption, which does not use a hash function (if a proper ciphersuite was negotiated). Hash functions are involved in the handshake, but in conjunction with asymmetric cryptographic stuff which is, in practice, a lot more expensive. In the TLS protocol, you can therefore say that the choice of the hash function in the handshake has negligible impact on the performance metrics of bandwidth, CPU usage and latency, as long as you do not use a stupidly slow hash function. On the other hand, for embedded system with strong constraints on, for instance, ROM size, the choice of hash function matters because if you already have an implementation of a hash function somewhere in the system software, then reusing that implementation yields smaller code than including a new one.

My bet is that the reviewer wants something similar to the above analysis.(*)

(*) It's a lie. My real bet is that the reviewer is an unpaid student who did not know what to write in his review, and has only little idea what he is talking about.


Validating file type via magic of an AES encrypted .ts file

For a well-designed block cipher like AES, its output should be indistinguishable from random noise except to someone who knows the key, so this is not possible in the general case.

The larger problem here, however, seems to be that you are trying to use the magic tests to verify file integrity without having any other protections. Confidentiality (as provided by encryption) does not guarantee integrity, and vice versa. You should use an authenticated encryption mode that handles both or find another way to create a system that provides both confidentiality and integrity.


Is factorization modulo a product of primes an NP-hard problem?

Your question has not a unique answer. In general case, finding $a,b$ is very simple. In this state, we can choose an arbitrary $b$(can be a prime number) and find the $a$ as follow:
$$a=c\cdot b^{-1} \pmod n.$$
Unfortunately, if you need that $a$ be prime, your question has no unique answer again. As an example, let $n=33$ and $c=20$. So we have:
$$7\cdot17=23\cdot31=20 \pmod{33}.$$


FHMQV-C \sigma calculation - Full Dual Exponential Challenge Response (FDCR) signature schemes-

Both $\hat{A}$ and $\hat{B}$ are computing the same quantity, $G^{xy+bex+yda+adeb}$, letting $\mod q$ be implicit:

$\sigma_{\hat{A}} = (YB^e)^{s_A} = (YB^e)^{x+da} = (G^y G^{be})^{x+da} = G^{xy+yda} G^{bex + beda} = G^{xy+bex+yda+adeb}$

$\sigma_{\hat{B}} = (XA^d)^{y+eb} = (G^x G^{ad})^{y+eb} = G^{xy + xeb} G^{ady + adeb} = G^{xy+bex+yda+adeb} = \sigma_{\hat{A}}$

As for $d$ and $e$, all that matters is that both $\hat{A}$ and $\hat{B}$ can each calculate $d = \bar{H}(X,Y)$ and $e = \bar{H}(Y,X)$. This is true since $\hat{A}$ sends $X$ to $\hat{B}$ and $\hat{B}$ sends $Y$ back to $\hat{A}$.

Note that $\sigma_{\hat{A}} = \sigma_{\hat{B}} = G^{s_A s_B}$, where $s_A = x + da \mod q$ and $s_B = y + eb \mod q$.


Luby-Rackoff theorem for Generalized Feistel

As you probably saw in the reference linked, there are multiple types of "basic" generalized Feistel networks: Type-1, Type-2 and Type-3. As far as I can tell all of these were introduced at CRYPTO'89 by Zheng, Matsumoto, and Imai in "On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypotheses".

Suppose that your state is split into $k$ blocks, then the above paper does in fact prove  / claim security for these generalized Feistel constructions (with each and every PRF used in all rounds and all state parts of each round being independent):

For Type-1, security is proven for $2k-1$ rounds
For Type-2, security is proven for $k+1$ rounds
For Type-3, security is proven for $k+1$ rounds

The paper also proves / claims that these numbers of rounds are actually minimal.

For everbody's reference, here are the three basic types as a fancy graphic:
image source

As one can somewhat clearly see, the first two types are "special cases" of the third where a certain selections of PRF invocations and XORings is dropped. The paper does provide further analysis on the number of rounds to keep security when dropping these with certain patterns


Calculating distance between two vectors using Paillier homomorphic encryption

I don't see your problem.
10118 is indeed the square of the euclidian distance ~100.5883


You should never keep keystreams. You should keep a key, and store an IV or Nonce with the ciphertext. You first need to think about where to store the key, if you store it in the same location or with the same security as your ciphertext, your scheme is meaningless.

Check this answer I just created on Stackoverflow, and learn about key management. This answer on the Information Security site also seems very on topic for you.


Is it true that in RSA $p^e\equiv p \pmod n$ and $q^e\equiv q \pmod n$?

No, it is not always true (and, for realistic RSA modulii, it is rarely true).  To take an example, if we have $p = 11$, $q = 17$ and $e = 3$, we have $p^e \equiv 22 \not\equiv p$ and $q^e \equiv 51 \not\equiv q$

  (I have to find four examples of $w$: $w^e\equiv w \pmod n$. My candidates are $p,q,-p,-q$.)

Actually, there are always at least nine examples, however those four aren't it.  I'll give you three for free: 0, 1, and $n-1$, all you need is a fourth one...


Yes, no.

  Does it needs to be new for every transmitted message?

Yes, always, otherwise this qualifies as IV reuse, the keystream produced by the stream cipher is the same (since keystream is independent of plaintext) and you end up with the familiar $M_0 \oplus M_1$.

I think you answered your own question here by noting that IV's must never repeat.

  It must be secret? (Is it assumed to be known by an attacker)?

No, it can be made public and is generally transmitted along with the message. It is not a key. If it had to be kept secret, there wouldn't be much point in using one, as it would be equivalent to changing the key.

I should note this is a very common question here and will probably be closed as a duplicate:

Stream Cipher : Never use stream cipher key more than once
Why can't the IV be predictable when its said it doesn't need to be a secret?
Why is the IV passed in the clear when it can be easily encrypted?
What is the main difference between a key, an IV and a nonce?


"Normal" AES implementations and tiny-AES perform the same task.

As stated in the README:

  This is a small and portable implementation of the AES ECB, CTR and CBC encryption algorithms written in C.

It's simply an implementation with low memory usage. The reason for the existance of tiny-aes can be traced back to the initial search for a replacement for DES (which would then become AES). One of these requirements were that they should have low memory usage for implementations suitable for example in SmartCards.

As stated in their paper (Second AES candidate conference, section 5) they performed tests on the different submitted AES candidates, one of which was memory usage.


Does an adversary require the public key to perform operations when RSA or ECC is broken?

TL;DR: yes, no, or maybe. Knowing the public key can only help an attacker. How much? It depends.

Usually, the public key is assumed known to all, hence its name; we'll assume it is not.

The answer depends on a lot of things: the cryptosystem, whether it is randomized or deterministic, if more than the ciphertext or signature is known (for example, if it is known matching plaintext/ciphertext pairs; if the message going with the known signature is also known; in the case of encryption, if something about the plaintext is known, like some redundancy ..). In general, the more is known, the easier it would be for the hypothetical attacker to break the cryptosystem even without the public key.

Also, the ability of the attacker matters: if s/he can break the cryptosystem with the public key, when by design of the cryptosystem s/he should not be able to do so, then perhaps she has resources not taken into account by standard security hypothesis, re-purposable for other tasks which could help towards breaking the cryptosystem without the public key: like a general-purpose quantum computer, or means of observing the internals of a supposedly impenetrable device.

Sometime, we can answer conclusively that the public key (or some other extra information) is required. For textbook RSA encryption $M\to C=M^e\bmod N$, a single ciphertext $C$, and unknown random plaintext $M$, the plaintext $M$ demonstrably can't be recovered from the ciphertext $C$, even by an arbitrarily powerful attacker, and even if s/he knows (a single) one of $N$ or $e$.

If we suppose the attacker has $C$, $N$, and its factorization as $N=p\cdot q$ with $p$ and $q$ odd primes, $p<q$, the set of possible plaintexts $M$ is all the $C^{j^{-1}\bmod\operatorname{lcm}(p-1,q-1)}\bmod N$ for $j$ such that this is well-defined. Typically, there are many such odd $j$ in $[3,\operatorname{lcm}(p-1,q-1)[$, and although some lead to duplicates, the set of possible plaintexts is very large (proof welcome); and the attacker has no way to chose among theses.
Similarly, if we suppose the attacker has $C$ and $e$, the set of possible plaintexts $M$ includes all the $C^{e^{-1}\bmod\operatorname{lcm}(p-1,q-1)}\bmod(p\cdot q)$ for odd primes $p$ and $q$ such that this is well-defined, $p<q$, and $M<p\cdot q<2^n$ where $n$ is the number of bits in the actual $N$. Typically, there are many such $(p,q)$ , and although some lead to duplicates, the set of possible plaintexts is very large (proof welcome); and the attacker has no way to chose among theses.

Sometime, we can answer conclusively that the public key is not required, because the attacker can find it anyway. For textbook RSA encryption restricted to small public exponent $e$ (say $3\le e\le65537$) and modulus $N$ not unusually oversize, given just three known plaintext/ciphertext pairs $(M_i,C_i)$ for arbitrary $M_i$ (much larger than $N^{1/e}$, which is necessary for security), it is quite easy to compute $N$ with high likelihood by computing $\gcd_i({M_i}^e-C_i)$ until that's not 1, for the few candidates $e$ (a classical result, proof welcome). Therefore, an attacker able to break the cryptosystem with the public key can obtain it under the usual assumption of a few known plaintext/ciphertext pairs, then break the cryptosystem.


There are alternatives to an s box.  You might say that they are evolutionary extensions of the traditional s box.  But they are all very much more complex.

As you know, an s box is typically implemented as a RAM based look up table.  So for an 8 bit s box, there are 256 possible inputs and outputs, requiring 256 bytes of storage.  This is 2^8.  If you had a primitive that required a 16 bit s box, you'll need 2^16 or 65,536 lookup values.  So this would be suitable for a 16 bit processor.

If you go wider, the memory required for a look up table becomes onerous for today's processors.  (You might manage a 24 bit lookup table, but processing 24 bit words on  32 bit processor is a PITA.)  You can opt for a real time computed s-box.

Instead of a static lookup table, you perform a computation on the inputs to the real time computed s-box, and output a value determined in accordance with some formula you've devised.  It's usually some form of mini hash.  It allows s boxes of arbitrarily large width.  A good example is  The Diffusion Layer (MR) algorithm of the Whirlpool hash.  That's 256 bits wide and uses clever Galois field theory.  A passive s box would be impossible at this width.  That transformation matrix could easily be widened to 16 * 16 values creating a 512 bit s box and a Whirlpool block size of 2048 bits.  Or even more.

Another form of active s box can be implemented without the clever Galois mathematics using Pearson hashes.  An 8 bit hash output is generated per each pass over the input bits. Using a unique permutation table for each byte means that the active s box can be extended to any size.  I've successfully used this for a 2048 bit box. The penalty is 256 permutation tables, but this is easily within the capacity of a small desktop /tablet.  The security of this technique may be acceptable when used in conjunction with a good permutation and key round functions.

You'll find that any reasonably secure algorithm can be used to compute the outputs of a real time computed s-box.  There's also this question regarding similar active s boxes.  The security of a primitive doesn't just come from an s box.  Indeed Keccak has no real s box but is ostensibly secure at the moment.  And a great deal of security comes from the number of rounds, not just the complexity of the rounds.  The upshot is that it doesn't have to be dead clever to be dead 'ard.  Skein follows this principle.


How to calculate the key size of my cryptographic system

To compute bit length equivalent of your key, you need to compute $\log_2(\Omega)$ where $\Omega$ is the space of possible keys. Now, I have myself been computing the equivalent key sizes of many non-modern cryptosystems so it proved a really interesting exercise.

The formula I'm left with is

$$
\log_2(1147^N \cdot 94^N \cdot 2^N \cdot 2)
$$
where $N$ is the number of rotors.

First, we select the rotors. For $N$ rotors, there are $1147^N$ possible choices. Then, we select their initial state (which were historically distributed by a codebook, different for each day). For each rotor we have $94$ possibilities, therefore for the whole setup there are $94^N$ possibilities. Then, each rotor can have two directions, hence $2^N$. The flow direction, I assume, is global, therefore we finally multiply all of this by $2$.

So, for the calculation, we have

$$
\log_2(1147^N \cdot 94^N \cdot 2^N \cdot 2)\\
= \log_2(1147^N \cdot 94^N \cdot 2^N)  +  \log_2(2)\\
= N \cdot \log_2(1147 \cdot 94 \cdot 2) + \log_2(2)\\
\approx N \cdot 17.718 + 1
$$

You will therefore have over 128-bit keyspace with 8 rotors and you will need 15 of them for 256-bit keyspace.

As previously noted by Adrian K Luis Casillas [edit], it doesn't mean this cryptosystem has this much "bits of security". This notion is much less strict and takes cryptanalysis into account, e.g. a cryptanalyst can find the attack which, after collecting sufficient material, will reduce the effective key space by either a couple of bits or even a large factor, halving it or worse.

Note that if you have any objections for this analysis I will happily discuss this topic further. It has been fun.


As far as I know, some people use the term inversion per byte for the conversion functions of section B1 of the standard, i.e. h2b and b2h, which convert from the unusual (i.e. different than as in SHA1, SHA2 ) NIST bit encoding to Hex bytes.

This is relevant only if you implement the API for hashing bit-string messages
with non-zero bit length mod 8.

The concluding paragraph of the 'Conversion Functions' section of FIPS 202  is: The formal bit-reordering function that was specified in
[12] for the KECCAK submission to the SHA-3 competition gives
equivalent conversions when the message is byte-aligned, i.e.,
when n is a multiple of 8.

If you work with byte messages this whole stuff adds some confusion but is not really necessary (and therefore it is no surprise that is not met often in actual implementations.)


Why Curve25519 for encryption but Ed25519 for signatures?

While it is true that Elliptic Curve Diffie Hellman, Elliptic Curve Signature Generation and Elliptic Curve Signature Verification rely on scalar multiplications, these are usually implemented as different types of scalar multiplication for both security and efficiency reasons.

In fact there are three types of scalar multiplications used in practice for these schemes:

Fixed-Base: when the input point of the scalar multiplication is known at design time
Variable-Base: when the input point of the scalar multiplication is not known in advance
Double-Base: when the protocol actually requires to compute two scalar multiplications and then to add the both results. (e.g. $kP+rB$ )

Variable-Base is what is usually needed in ECDH, as you receive the input point of the scalar multiplication from another peer.

Fixed-Base is used in key generation and signature generation. Here the fixed-base is always the "generator point", which is the point who generates the prime-order subgroup that is provided together with the curve's equation.

Double-Base is used for signature verification (both ECDSA and EdDSA and Schnorr) require to compute something of the form $kP+rB$. Note that unlike ECDH or Signature Generation the Signature Verification doesn't make use of any secret values and therefore there are no requirements for constant time execution.

X25519 provides a very simple, constant time, and fast variable-base scalar multiplication algorithms. This is very good for ECDH and this is why it is used specifically for ECDH.

Ed25519 instead provides a very fast fixed-base and double-base scalar multiplications, thanks to the fast and complete twisted Edwards addition law.
In fact, the fixed-base algorithm of Ed25519 is, on most platform, faster than the variable-base of X25519.

And using X25519 for signature verification is just a bad idea because you need to execute it twice (to compute $kP$ and $rB$) and then to add a new function to perform the full addition of the two resulting points. Furthermore you are using constant-time computation where it's not needed. Instead, you can achieve a much faster implementations using interleaved NAF methods and the twisted Edwards addition law.

Note: for the purpose of this answer I'm not distinguishing between different elliptic curve signature algorithms such as ECDSA and EdDSA.


Second pre-image resistance vs Collision resistance

The difference is in the choice of $m_1$.

In the first case (second preimage resistance), the attacker is handed a fixed $m_1$ to which he has to find a different $m_2$ with equal hash. In particular, he can't choose $m_1$.
In the second case (collision resistance), the attacker can freely choose both messages $m_1$ and $m_2$, with the only requirement that they are different (and hash to the same value).

(From this, it is also obvious that collision resistance implies second preimage resistance: An attacker can just choose an arbitrary $m_1$ and compute a second preimage $m_2$ to obtain a collision.)


How to calculate kinv from the given k value

Just compute the multiplicative inverse $k^{-1}$ of $k$ modulo the prime order $n$ of the base point $G$ (I used the typical notation for the domain parameters of the curve). This can efficiently be done using extended Euclid and should be available in any reasonable big integer library (typically something like modinverse). Thats it.


A set of key pairs and one hash to secure them

What you are proposing in effect means that you use a not-really-random one-time-pad, which is used twice (i.e. a two-times-pad). This is not secure.

Using a single hash to generate a key from a password is a bad idea - especially if the password is short, it is easy to brute-force it (i.e. try lots of passwords).
Using the simple XOR cipher to encrypt a ECDSA key pair, one half of which is public anyway, means that half your key is directly derive-able from the encrypted key pair. (This helps with the brute-forcing in step 1.)
Using a one-time-pad twice means that the attacker can derive $x_1 \oplus x_2$ (i.e. the XOR of the two private keys). I don't know of any way to come from this to $x_1$ and $x_2$ (given also the public keys $g^{x_1}$ and $g^{x_2}$), but I would not wonder if someone would find a way to do this easier than trying all $x_1$.

Instead, use established algorithms:

Use an established key derivation function (Bcrypt, Scrypt, PBKDF2) with an appropriate work factor to derive the key from a password.
Use a secure cipher algorithm (a block or stream cipher) in a secure mode instead of XORing.


You don't have to use any special asymmetric construct. Just give the group keys and encrypt the file with a unique random key and than encrypt the file key many times using the keys of the permitted users.

You can give each user multiple keys some of them shared by relevant groups. To prevent encrypting a file with too many keys. These can even be done ad-hoc, assuming groups repeat themselves. you can create a group key encrypt it with the keys of the members and reuse it if you want to give that group access to another resource later.


Constant Time Multiplication for Cryptography in Pure Software without Hardware Multiplier or Barrel Shifter

Constant-time multiplication in software without constant-time multiplier is easy. In C, this working code to compute $x\cdot y$ for 8-bit inputs is typically¹ constant-time:
unsigned mul(unsigned char x, unsigned char y) {
  unsigned r = x, s = x&-(y&1);
  s += (r += r)&-((y >>= 1)&1);
  s += (r += r)&-((y >>= 1)&1);
  s += (r += r)&-((y >>= 1)&1);
  s += (r += r)&-((y >>= 1)&1);
  s += (r += r)&-((y >>= 1)&1);
  s += (r += r)&-((y >>= 1)&1);
  return ((r+r)&-(y>>1))+s;
}

On a $b$-bit CPU, it is required $O(b)$ instructions, compared to $O(1)$ with a constant-time $b$-bit multiplier. Assembly often makes it possible to do considerably better than the obvious translation of the above code, especially on architectures without built-in 16-bit addition.
It's possible to compute $(x\,y)+z$ where $0\le z<2^b-1$ by the same method. This can be used to perform multiplication of arbitrarily large fixed-size quantities in constant time using the schoolbook algorithm, or others such a Karatsuba, translated to base $2^b$ rather than base $10$, with essentially the same $O(b)$ performance penalty compared to implementation with a constant-time multiplier.
The most serious difficulty is the same as on architectures with a constant-time multiplier: constant-time modular reduction.
I don't get how the lack of barrel shifter is an issue: in the arithmetic used in ECC cryptography, there's typically no computed shift involved, thus no opportunity that the lack of barrel shifter degenerates into a timing dependency. And the natural form of most algorithms uses shifts by one, thus a barrel shifter would not help much anyway.

One thing worth investigation on CPUs without hardware multiplier is Elliptic Curves over $GF(2^m)$, e.g. sect239k1. I know no reason this would be much less secure than secp224k1, and scalar multiplication no longer uses any integer multiplication, so the lack of hardware multiplier has low penalty.

¹ Except if the compiler introduces branches or if some of the instructions involved are not constant-time, but I've ever experienced that.


Does it make any sense to hash parts of a hashing target?

From the practical point of view both approaches have similar resistance to brute-forcing. From the implementation point of view it may be simpler to apply hash only once, without hashing of every single part.
Nevertheless I would suggest you to review your design and consider other options. Suppose somebody has received your message and validation shows, that Items[0].ItemSig and Items[0].Data to not match. This can have two reasons:

Either Items[0].ItemSig was invalid before you signed it (then the signer has faked the signature).
Or the signature was correct, but you have replaced Items[0].Data before signing.
Or Items[0].Data was modified on the way from you to the receiver.

Thus it will be hard to find out where the problem has happened.
That's why I'd suggest other approach. Think of separation of concerns. Don't consider the structure of what are you signing. Sign the whole element Items. Then if somebody receives your message and something is not consistsnet, it will be easy to check: One should just check if your signature matches the Items element. If matches, means there was no modification on the way from you to the receiver, and the problem occurred on the signer of Items[0].Data before you signed.
TLDR: I'd suggest to hash the whole element Items, not the parts of it, and without hashing of every single part of it.


The combination between addition modulo $2^{32}$ (not modulo $32 = 2^5$) - indicated by $\boxplus$ in the diagram - and XOR (i.e. bitwise addition modulo $2$) - indicated by $\oplus$ - makes the algorithm more non-linear.

Each of them for itself is a linear operation, but over different groups (addition in $GF(2^{32})$ vs. addition in $Z/2^{32})$, and the combination is slightly non-linear over both groups.

Why modulo $2^{32}$? This operation is already implemented in many processors (Java's int addition is this, for example), and this makes implementation easy and efficient.

The later Threefish cipher used in Skein takes this to a new level, its nonlinearity depending exclusively on this simple combination, in a really large number of rounds.


For CBC mode, the IV can be generated in any manner where it would be unpredictable to an attacker from one message to the next. In practice that means a random number generator of some kind. Since the block size is 128-bits, the probability of IV repeat before the key expiration is negligible. The CBC IV is visible to an attacker viewing your ciphertext; as you said, it is attached some how.

There does not need to be any agreement on both ends as to the method of generating it. Most implementations I know of prefix the ciphertext with the IV.

For CTR mode it is a different story. The IV is the combination of Nonce and Counter. There needs to be strict agreement on both sides how they are combined and incremented, or the other party will not be able to decrypt. Additionally if the same key is used by both parties, they need to make sure there is no Nonce reuse between the 2. This can be achieved by forcing one party to always have a specific bit of the Nonce set to 0, and the other party set that bit to 1, such as the MSB. The better option is to have 2 different keys. Since CTR mode turns the block cipher into a stream cipher, IV reuse in CTR mode is catastrophic. There is no requirement that the Nonce be unpredictable, and can be a simple message counter.

The nonce is the only part of the CTR IV that is transmitted with the message, and once again it is visible to an attacker. Most implementations I know of prefix the ciphertext with the Nonce, and the block counter for the message starts at 0, except in the case of AES-GCM.


How WhatsApp users authenticate themselves in end-to-end encryption?

Basically the way WhatsApp and many other end-to-end encrypted messaging platforms work is that your device generates a public/private key pair. The public key is uploaded to the server and the private key is maintained. It is typically recommended that you do an "out-of-band" authentication of public keys with anyone you want to communicate with. This is often done by meeting in person. You can display your public key on your device, which they can see what public key they have for you (from the server) and compare. If you both see the same public key, all is well.

The reason and "out-of-band" mechanism is needed is that you cannot trust the WhatsApp channel for security yet, since security is being provided via the crypto. In theory, if you had some other trusted channel, you could use that. But if you already had a trusted channel, why use WhatsApp (or any other application)? This is why "in person" is typically the way this happens. You could do it over a phone call, or maybe even SMS, and feel sufficiently certain that correct public keys were exchanged. The beauty of how these apps work is that they allow you to decide that. That is also the disadvantage. If users don't fully understand the implications, they may be more risky than they would be otherwise.

This public/private key pair is used to sign partial ECDH key exchanges. You upload your half, signed by your private key to the server. The person who wants to communicate with you downloads one of the partial exchanges, verifies it with your public key. Completes the key exchange and uses the resulting key to encrypt the contents of the message. They then upload the other half of the key exchange, signed with their public key, and the encrypted message. Finally, you download all that info and are on your way.