Shamir's Secret Sharing - Impersonating the Dealer

Yeah, as stated, that's an unsolvable problem.

Basically, if you assume that the dealer loses everything that would let the shareholders (or anyone else) distinguish them from some random stranger, then there's nothing they can do that some random stranger couldn't also do.

The typical real world solution is to let the shareholders identify you by some physical means, such as by your fingerprints, iris patterns, DNA or just general familiarity with your physical appearance and personality.  Such biometric IDs are hard to accidentally lose (especially if there's some redundancy) and even harder for someone else to copy (at least in a way that would fool a careful human inspector; unfortunately automatic checks are often quite a bit easier to trick).


Should I add randomness at the end before AES?

I want to make it harder to decrypt AES I send.

Fundamentally, the thing you are trying to do is completely unnecessary. If AES does ever become broken, the scenarios in which this makes any measurable difference are exceedingly unlikely. If AES isn't broken, then doing this was wasted effort in the first place.

There is zero plausible reason why your idea would make AES harder to decrypt in any scenario.

Virtually any other use of your time would be better spent. AES, when used correctly (e.g., a well-regarded mode like GCM, non-repeating nonces, and a cryptographically random key or strong password with suitable PBKDF), is going to be the strongest part of your cryptosystem by multiple orders of magnitude. Focusing extra time on this part of the problem is, to paraphrase Bruce Schneier, like protecting your house by planting a single stake into the ground and hoping the attacker runs into it, instead of building the rest of the fence.

Edit: Upon rereading your question, it appears you're gravely misusing CBC mode by using a static (or no) initialization vector (IV). An initialization vector should never be reused between encryptions with the same key. Additionally, CBC IVs have the requirement of being unpredictable to an adversary. Your encryption library should have a function to set the initialization vector before encrypting any plaintext, and before decrypting any ciphertext. Generate one with a cryptographically secure random number generator, pass it to your encryption library, and then send the IV alongside the ciphertext so the receiver can decrypt it.


How to encrypt 1-to-1 chat application for dummies

There are two solutions which vary in their integration complexity but also in their feature-set.
Solution 1: The Signal Protocol
The Signal Protocol is, well, the protocol used by the famous Signal-Messenger and which was also adapted in quite a few other popular messengers such as WhatsApp. It is designed to perform best in the situation you're in: asynchronous chat applications. As such it ensures forward secrecy and allows to confirm other parties at any point. As a bonus there's the famous libsignal which should greatly ease implementation.
If you can this is absolutely the solution you should take.
Solution 2: E-Mail Encryption methods
If however integration of the Signal Protocol proves impossible for your deployment, the usage of standard E-Mail encryption methods should still work. Basically you let each party generate public-private keypair(s) and then use your favourite PGP encryption and signing library to sign and encrypt the message as if they were emails or you could use your favourite S/MIME library to do the same. However this doesn't provide forward secrecy and gives non-repudiation to the messages (ie "everyone" can verify that X send the message Y). Key confirmation can be solved by your provider (for when the users trust you) and by comparing key hashes by the users if they meet in person.
This is the second best solution which you should implement if the Signal Protocol really isn't an option.


$$O=(A\cdot I_1)+I_2$$
Take $\mod A$ of the equation.
$$O \bmod A=\left( ( A\cdot I_1)+I_2 \right) \bmod A = I_2 \bmod A$$
So we get the $I_2$. the rest is substructing the $I_2$
$$O - I_2 = A\cdot I_1$$ and the final is simply dividing by A.
$$I_1 = \frac{O - I_2}{A} $$
The given $h_1$ and $h_2$ are not used! One may argue to use the hashes to identify the multiple solutions, however, the Euclidean division says they are unique since $A$ is a 1024-bit number and $I_i$'s are 512-bit numbers.


How long does it take to crack RSA 1024 with a PC?

RSA-768 took 2000 years of 2.2Ghz single-core Opteron from the year 2009.

DJB et al wrote in 2013 (see page 30) (see also: 29C3: FactHacks (EN); slide 87/112; about 10 minutes) that RSA-1024 would take $2^{70}$ differences with $2^{24}$ per machine per second in 2009, so 2 million years. Hardware improved since then, and GNFS can use GPUs, so maybe better, but about a million years I guess.

Absolutely the computation can be parallelized to use many devices, for example to use a botnet, which is what DJB recommends. Whether one can have a botnet with a million devices with strong CPU/GPU that uses up a lot of power and not get noticed for a year, is another matter entirely.


Any point to AES on password with hardcoded key?

Obviously it would be easy to decrypt the password for any serious attacker, but it might help deter casual attackers. Instead of opening the config file in a text editor and finding the password they would have to decompile and decrypt it, or snoop the memory while it's running. It might also help to stop automated tools that may be searching the filesystem for documents containing things like "password=xxx".


Establish a secure connection between a Bluetooth Low Energy device and an Android App using ECDH

With this protocol, I see three issues right now.

In step 2 both devices just send their public keys. Now an attacker could go ahead, intercept the keys from either part, pretend to be the other one and relay all the trafic over himself. This is a classic man-in-the-middle attack against Diffie-Hellman.
You use "AES-CBC with integrity". This does look very bad for a mode of operation. It seems to be (from a quick glance) $E_K(m)=E_K^{CBC}(m\parallel H(m))$ at best which is also called hash-then-encrypt, which is highly nonstandard and potentially dangerous. Upon further inspection of the source code (thanks to Isaac Potoczny-Jones in the comments) it turns out to actually be an HMAC-SHA256 applied on the ciphertext which is standard encrypt-then-authenticate.
You use sect163k1 which is a Binary Koblitz curve over a field of size $\approx 2^{160}$, thus a brute-force attack would take $\approx 2^{80}$ operations which is considered dangerously weak these days. If you have to (perfomance-wise) you can do it, but it's certainly not the robust 128-bit security level you normally expect.

As for mitigations, I strongly recommend you to use a more standard secure channel protocol (like TLS). If your platform does not natively support it, it may be time to either require an upgrade or bring your own library.


Super-simple encryption of short strings

It seems you want some sort of anonymization, and you already jump to a conclusion with encrypting symbols. Maybe you should step away of that for a moment, and ask yourself what your actual goal is.

Encryption is useful, if you want to be able to reverse that process. If you don't hashing is a better choice in general.
Your set is small enough that you can just create a lookup table on the fly with a random number generator of your choice, as fgrieu already pointed out.

Instead of focusing on how to anonymize the initials, you might want to have a closer look on the anonymization of the actual data, if there is more than a single measurement for each participant. Aggregation of data can reveal information, that you wouldn't have imagined before. Simple pseudonymization might only work for those with common features and expose those with rare combinations. E.g. gender + age in a group with mostly men will give some anonymity to the men, while women of a certain ag can be identified much easier.

In general, I would say it is a bad idea to publish the raw data from any experiment with real people, and don't rely on pseudonyms as anonymization. Only publish the final aggregated data, which shows what you want to state.


How can you extract individual characters of an encrypted string such as a password?

Most financial services companies that I've come across who make use of this kind of system are encrypting the password using a Hardware Security Module ("HSM").

In this kind of system the password is symetrically encrypted with a key held in the HSM, and then stored on disk.  The application will then pass the encrypted password and the individual characters into the HSM which will decrypt the password, make the comparison with the supplied characters and return a true/false answer to the application.

The security of this kind of system relies on the intended properties of the HSM which should be resistent to tampering and which run a very limited number of functions to reduce attack surface.

Also in this kind of situation key management is obviously very important as compromise of the key would allow for easy access to all customer passwords. This tends to lead to split authority and key parts being stored in safes, as a backup for the HSM.


Security of deterministic encryption that uses CBC mode and plaintext as iv

No, you should not do that. Any time you encrypt a message with CBC you should use a new, random IV and send it together with the ciphertext. Don't encrypt the IV after usage.

The IV for CBC mode has to be unpredictable. That means you can't reuse an IV and you should not take any already used value from elsewhere. That was the problem of TLS with the BEAST attack, you maybe have heard of it. As soon as an attacker can make any statements about the IV there could be a serious security problem with your scheme.

IVs are also used to make the encryption more random - with your scheme, your IV only depends on your message, so the ciphertext is always the same when the message is the same. We mostly don't want that because it would show an attacker that we are sending the same message again.


MAC unforgeability and secret key guessing

I was going to make this a comment; however you asked for hint, and these are hints.

Suppose you had an Oracle that solved the second game for you; how could you use that Oracle to solve the first game?

Does that imply that a MAC where the first game is unsolvable imply that the second game is also unsolvable?


RSA: given (N,e,dP), is it possible to find d?

is it possible to recover $d$?

Yes, with $N, e, d_P$, you can factor $N$ (and from there, recover $d$)

If we select an arbitrary $r$, $r^{e \cdot d_P} - r \bmod n$ will have $p$ as a  factor. This is because $r^{e \cdot d_P} = r \bmod p$ (as $e$ and $d_P = d \bmod (p-1)$ are inverses of each other modulo $p-1$).

In contrast, $r^{e \cdot d_P} - r$ is unlikely to have $q$ as a factor.

So, if we select a random $r$, and compute $\gcd( n, r^{e \cdot d_P} - r\bmod n )$, we will (with high probability) recover $p$, and from there, factoring $n$ and reconstructing $d$ is straight-forward.


The user94293's answer is correct, If you look at the equation you will see that the result will be zero if you add the number itself. It is designed for the points $P$ and $Q$ such that $P\neq Q$. If you want to calculate the $P+P$ that is called point doubling and it is written as $[2]P$. There are always special formulas for doubling since it adds the point itself.
The addition formula is optimized and cannot be used for $2[p]$. From your questions and comments, I understand that you are trying to find the scalar multiplication by just adding;
Scalar Multiplication
The scalar multiplication $[k]P$ this actually means adding $P$, $k$-time itself. More formally;
let $k \in \mathbb{N}\backslash\{ 0\}$
\begin{align}
[k]:& E \to E\\
&P\mapsto [k]P=\underbrace{P+P+\cdots+P}_{\text{$k$ times}}.\end{align}
Double-and-Add
To use these formulas correctly, you need the double-and-add algorithm
#Returns [k]G, where p is modulus
#and c is the constant of the Generalized Hessian Curve
doubleAndAdd(G, k , p ,c)
  N = P
  Q = 0
  for i in bits(k)
     if i = 1 then
         Q = point_add(Q, N)
     N = point_double(N)
  return Q

Where the bits convert the $k$ into binary form and started from LSB.

Updates on implementation
I've found a problem during the calculation of the order an element, later figured out the cause. One can reach the codes and explanations on the Q/A from the StackOverflow
The order of $(4,2,6)$ is $77400$ i.e. $[77400](4,2,6) = \mathcal{O}$ and the order factors into $2,2,2,3,3,5,5,43$. Not a good curve.
To run better, the order of the curve must be calculated before and so that one can use $[k]P = [k \bmod order]P$ equality.
Smart's Sample Curve
N.Smart wrote an article titled  The Hessian Form of an Elliptic Curve. In this work first, a curve over $\operatorname{GF}(2^{191})$ on the form $$E': y^2 +xy = x^3 + x^2 + b$$ $$b =  \texttt{0x4DE3965E00F2A1C6C9750156A6FEFBE5EEF780BF3EF20E48}$$ is given, and that then transferred to a Hessian form.
$$x^3 + y^3 + z^3 = Dxyz$$
$$D = \texttt{0x16A4C7C2030FAD1380ABF8C2D47DC3E0C20AF62F6EDD06A7}$$
A point of order $q$ on $C$ is also given by $(x, y, z)$, where
$$x = \texttt{0x52FD0CE78D0651B4F66D2F4E12E170CA3E429F6A06433B22}$$
$$y = \texttt{0x1BECA50368403F3D13173968082B035397C77830A9D90E5D}$$
$$z = \texttt{0x2B08F7C0CCAC86151AA6FECABDD2D052BD60924F28A6A78E}$$
That is not generalized, however, your $c=1$ make is in this case. You can benefit from this curve.


Compact ROM with space only for EdDSA. How to fit a key exchange algorithm inside?

A bit of nomenclature first: “Ed25519” is defined to refer to the EdDSA signature algorithm over the edwards25519 curve. What you appear to actually mean is whether you can reuse your edwards25519 code for Elliptic Curve Diffie–Hellman (ECDH).
There is no inherent reason that you can't use edwards25519 for ECDH. We've been doing ECDH with all kinds of curves for ages already, and edwards25519 works just fine as any other. You need to take the same precautions as for X25519, too: multiply by the cofactor $h=8$ or check against a blacklist of bad points (but the encoding of those points will differ between compressed edwards25519 points as for Ed25519 and X25519).
Since you say you're looking at a constrained-memory system, it is likely that you've first built signature verification (which not require constant-time code). If you're going to reuse this code for key exchanges, make sure all curve code and field arithmetic code (except the routines only used signature verification) are made to be constant-time.
A key exchange protocol requires more than just a curve, however, so you may want to look into e. g. the Noise protocol patterns.


Is Guillou-Quisquater existentially unforgeable against adaptive message attack under a random oracle model?

Guillo-Quisquater scheme uses the Fiat-Shamir trick to convert a proof of knowledge into a signature. There is a paper out there about the security of such schemes in the random oracle model here which seems to give what you want.


Possible password search space = $36^5$ = 6.05 million possible combinations or ~$2^{26}$.  If the passwords were randomly generated it would be 26 bits of entropy which isn't just weak it is pointless.

To put that into perspective the throughput on modern GPUs is on the order 1 billion SHA-256 hashes per second.  So the exhaustive search time to break an account would be 60ms.  An attacker could break about 60,000 accounts per hour.

Rainbow tables are a non issue as you are using per record random salt.  It is too short to be fully effective but given how weak it is generating the rainbow tables would take far longer than just breaking all the accounts.


I need to know number of encryption/decryption operations?

I'm not sure you understand the purpose of EDE. EDE only specifies the order of operations of the DES primitive in 3DES is Encrypt-Decrypt-Encrypt. It does not specify the amount of key material. That's determined by the key option.

In 3DES, key option 1 uses three independent keys for a total of 168 bits, meaning a brute force attack requires 2^168 attempts. Note that in this case using EDE results in the same amount of work and protection as EEE would.

Key option 2 uses two keys for a total of 112 bits, or 2^112 attempts. They are used in a 1-2-1 pattern, helping protect against a meet-in-the-middle attack.

Key option 3 means the same 56-bit key is used for all three DES operations - the EDE causes the second pass to decrypt the first pass, yielding the plaintext to be reencrypted by the third pass. It's backwards compatible with single DES. This is the reason EDE was created, to serve old 56-bit applications back when they were trying to upgrade from DES.

So that's why EDED doesn't actually make much sense. There is no backwards compatibility it would preserve, so EEEE would be a less complex choice. However, going forward with the idea that 4DES is a decision someone would make over AES-256 (which would probably be a bad idea), I would assume they would do so with four independent keys, for a total strength of 224 bits, or 2^224 attempts.

Note that all these answers are excluding any benefits in performance gained by cryptanalysis of the algorithms.


What is the advantage of a probabilistic PKC over a traditional PKC?

Every secure public key cryptosystem must have a probabilistic encryption algorithm.

Suppose this was not the case and consider the usual IND-CPA game.
An attacker can now win this game with probability 1 as follows:

He chooses two distinct messages $m_1,m_2$ at his liking and submits them to the challenger.
The challenger chooses a bit $b\in\{0,1\}$ uniformly at random and answers with $c'=c_b=E_{pk}(m_b)$.
The adversary computes $c_0=E_{pk}(m_0)$, if $c_0=c'$ he outputs 0, otherwise 1.
As the encryption algorithm is non-probabilistic, ie deterministic his choice for $b$ is right 100% of the time because he can be sure to always to the same value as the challenger.


What is the difference between static and dynamic tokens?

Software tokens are software that generate tokens for you. For example the Google Authenticator App or Authy on your smartphone, while hardware tokens are actual hardware that are only made for generating those tokens without doing anything else, such as RSA SecurID.

A static token would be a token that is always the same, for example a password stored on a Yubikey that is entered each time you press a button on the token.
A dynamic token is a token that varies, like Google Authenticator two-factor tokens that change each 10 or whatever seconds.


Adding a Random component to CBC MAC in order to enlarge the tag space

First, don't roll your own crypto.

Second, why would you want to use CBC-MAC, if you have GMAC (GCM-mode) and CMAC and even better HMAC? (all of which are better than CBC-MAC)

Third, don't try to fix problems that have been fixed. (see second)

Fourth, I'm not aware of this construction being standardized and I'd doubt it has been. (see points 1 to 3)

Fifth, in fact there's a proposal that is similar to yours. Look here


Maximum value of negligible probability?

It depends on context.

In a theoretical context, baring other definition, a probability is negligible if it decreases exponentially (or: faster than any polynomial of fixed degree) with some security parameter $k$, often a number of bits in the key; while the computational effort to use the system grows no faster than some polynomial of $k$.

In a practical context, if the probability is for one try of the adversary, and more tries will increase that probability about linearly, something like $2^{-80}$ used to be considered adequate, $2^{-128}$ is considered adequate for a decade or two baring hypothetical future quantum computers usable for cryptanalysis, $2^{-192}$ and $2^{-256}$ are sometime specified (because of security classification levels, and because that improves confidence when considering said quantum computers). Lower values will do, of course. Higher values (like $2^{-64}$) wight still make sense if the stakes are low and lowering that probability was costly, or forbidden by law.

In a practical context, if the probability is with all the parameters influencing it (effort of the adversary, number of users, size of plaintext..) set to credible values maximizing the probability, then $2^{-10}$ to $2^{-40}$ is reasonable, depending on how damaging the low-probability event would be. Lower values will do, of course.


What is "electronic" in electronic codebook (ECB)?

In a paper codebook, plaintext words (perhaps arranged alphabetically like in a dictionary) lead to a replacement word.

Cipher for Telegraphic Correspondence — a code book used by Union General Joseph Hooker’s code clerk. Source: wikipedia.

A block cipher implemented using electronic circuitry (as DES was initially) does the equivalent, with block instead of word, and new key instead of new book. That's thus an electronic codebook. The operating mode based solely only this feature is Electronic CodeBook.

It would be possible to implement a block cipher using non-electronic means, e.g. mechanic of even manual; and operate it in ECB mode. Fact is, this was not done on a large scale. Before DES, mechanical ciphers tended to operate on a letter-by-letter basis, not something wide comparable to a word.


Is symmetric key encrypted with server's public key secure

The first part of the protocol – e.g. alice choosing a random secret key and sending it public-key-encrypted to Bob – is in essence the same as the usual RSA key exchange used in SSL/TLS.

As you mentioned, Mallory can't read the key, but can start her own connection to Bob pretending to be Alice, so this part only provides authentication of Bob for Alice, not the other way around. (This is okay for the common use case of HTTPS, where we have one trusted server and lots of untrusted clients).
But (assuming your symmetric encryption also includes some kind of MAC and you have some protocol measures against replay attacks, like message numbers) Bob knows that he speaks with the same entity during the whole conversation.

Mallory might be able to send messages in Alice's name (and receive the responses to these messages), but can't read messages sent by Alice or read the responses to these messages (if they arrive at Bob).

To add authentication for Alice, you add a second authentication step over the now encrypted channel. This can be whatever wanted, from a plain password to another public key signature from Alice. Both schemes are commonly used in SSH, by the way.

This looks secure, but there might be some details hidden in the details of your protocol.

As mentioned by Ricky Demer, when Bob's private key is revealed/broken for some reason, all the previous connections (which an Mallory might have recorded) can now be read by Mallory. (This is called the non-forward-secrecy.)

Using Diffie-Hellman (together with some kind of authentication, like signatures from both parties) or SRP solves this by making the session key unrecoverable from just the transcript and the long-term secrets. This is incorporated in both SSL and SSH protocols, too.

In general I would recommend to use an existing (and evaluated) protocol like SSL or SSH as the base of your communication. (You don't have to implement all options.)


Cryptographic limit to total accounts in secp256k1

The upper limit really depends on your risk. The birthday attack's 50% probability is a too big risk to rely on. Let's look at some numbers assuming that the total of the points is $2^{256}$ which is not bu very close*. Assuming the keys are constructed uniform randomly like a coin toss.
We will use the fact that the probability of collision among uniform randomly selected $k$ elements in the set of $n$ element can be approximated by $(2^{k})^2/2^{n}/2=2^{2k-n-1}$

Consider $2^{100}$ private keys, that has a probability of collision
$$(2^{100})^2/2^{256}/2 = 2^{200 - 256 - 1} = 1/2^{57}.$$ Not going to happen  $\times 2^{-40}$ ans still very low proabaility to execute an attack.

Consider $2^{90}$ private keys, that has a probability of collision
$$(2^{90})^2/2^{256}/2 = 2^{180 - 256 - 1} = 1/2^{77}.$$ Not going to happen $\times 2^{-20}$

Consider $2^{80}$ private keys, that has a probability of collision
$$(2^{80})^2/2^{256}/2 = 2^{160 - 256 - 1} = 1/2^{97}.$$ Not going to happen

Consider $2^{70}$ private keys, that has a probability of collision
$$(2^{70})^2/2^{256}/2 = 2^{140 - 256 - 1} = 1/2^{117}.$$ Not going to happen $\times 2^{20}$

Consider $2^{60}$ private keys, that has a probability of collision
$$(2^{60})^2/2^{256}/2 = 2^{120 - 256 - 1} = 1/2^{137}.$$ Not going to happen $\times 2^{40}$

Consider $2^{50}$ private keys, that has a probability of collision
$$(2^{50})^2/2^{256}/2 = 2^{100 - 256 - 1} = 1/2^{157}.$$ Not going to happen $\times 2^{60}$

Consider $2^{40}$ private keys, that has a probability of collision
$$(2^{40})^2/2^{256}/2 = 2^{80 - 256 - 1} = 1/2^{177}.$$ Not going to happen $\times 2^{80}$

Actually, there is no need to look lower than $2^{70}$ since the probability is already is so tiny to happen. When it is around $1/2^{100}$ we simply say that it is not going to happen. Similarly, there is no need to look over $2^{80}$ since normally, that amount of users is not going to be needed. This also shows that if an entity tries to randomly guess the private keys, will fail.
In the case that one entity decides to attack all $t$ targets than the cost to find the first of $t$ target is not cheaper than the DLOG.
* the order of the base point is = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141


Efficient Incremental Updates to Large Merkle Tree

Yes, you should be able to handle this situation readily.  There are many optimizations available.

One key observation is that if you're going to go to disk, then you might as well read lots of data: it takes just as long to read an entire block of data as to read 1 byte.  So, I suggest you store the data on disk in 4096-byte blocks, and do a Merkle tree over these blocks.  In particular, you will have one leaf per 4096-byte block.  Then you can store the Merkle tree in memory.

Second, there's no need to use SHA224.  A 160-bit hash is sufficient, so you could use SHA1 (or SHA224/SHA256) truncated to 160 bits.  This way, each hash will be 20 bytes long.

How will this perform?  Each 4096-byte block on disk can store about 200 hashes.  Therefore, you'll have about 1.5 million blocks.  Treating the hash of each block as a leaf, we have a Merkle tree with 1.5 million leaves.  Such a Merkle tree has 3 million nodes in total, which you can store in memory using just 60 MB of RAM.

Every 5 minutes, 4000 random entries will be modified.  This requires you to read 4000 blocks from disk, update them, recompute their hashes, and update the Merkle tree.  To read the 4000 blocks, update them, and write them back out to disk will involve reading 16 MB of data and writing 16 MB of data; no problem.  Hashing all of this data will take about 40 ms, since you can hash a 4096-byte block in about 10 microseconds.  Then, you'll need to update about 8000 nodes in the Merkle tree.  This involves computing 8000 hashes on short inputs, which will take about 4 ms, since it takes about 0.5 microseconds per hash of a short input.  Overall, the performance impact on your system should be very low.  (These numbers are on one particular machine I happened to have laying around, using SHA1.  Your numbers may vary by a constant factor, but probably not by an order of magnitude.)

Overall, this solution should perform extremely well, both in memory consumption as well as in CPU usage.

If you want to squeeze out every last byte of RAM, there are other tricks available.  You can save up to a factor of 2x in memory usage if you use a tree with a much higher branching factor, rather than a binary tree (though this will cost you a little bit in CPU utilization).

Also, you can safely truncate the size of the hash down to about 80 bits (10 bytes), if you use a UOWHF.  One way to do this is to pick a secret 128-bit key $K$, and then the hash of the data $X$ is $H(X || K)$ (i.e., append $K$ to the data before hashing), truncated to 80 bits.  The use of the key $K$ (i.e., the use of a UOWHF) eliminates the opportunity for birthday attacks, so in this situation, 80 bits is enough.  This can save you another 2x in memory usage.


The $KeyHandle$ is not the public key, it's a value used to identify the public key that's been registered.  Essentially, it's an identifier of a specific pairing of that device with that server, with its own unique private/public key pair.

From the page you linked to, the $KeyHandle$ is not a sum but both values, the nonce and the MAC of the AppID and the generated private key.  When it's registered, it sends the $KeyHandle$ and public key to the server.

When authenticating, the server sends that $KeyHandle$ back, so the device simply uses the nonce to regenerate the private key, verifies it with the MAC, then uses that to prove it knows the private key corresponding to the public key sent during registration.

The hash is just a large number.   ECDSA is used in UAF. When using modular exponentiation systems, the public key is often of the form $g^x mod$  $N$ where x is the private key, EC is similar in form.


You're trying to compare authenticated encryption with disk encryption. GCM is used to solve 2 security problems at once: encryption and authentication. GCM is designed such that only someone knowing the key can modify ciphertext without raising alarms. This requires additional data to use as an authentication tag.
XTS, on the other hand, only partially hold this property. The benefit of XTS, however, is you don't need to store additional data for an authentication tag. XTS also has (some) resistance to tampering, since any change made to the ciphertext yields random and meaningless plaintext. However, this is not considered sufficient for authentication, since an attacker can still make changes without the changes being noticed. This is undesirable in any case where an attacker may intercept encrypted communication (ex. network protocols).
For full-disk encryption (FDE) authenticated encryption becomes impractical, since you would need to store a lot of extra data to verify integrity (with a mode like GCM). Unless you have so much disk space you don't mind losing half of it, this isn't a reasonable option. You could also store a separate hash (HMAC) but this still requires reading the entire contents of the disk to verify (which takes a long time), and will likely cause the hashes to mismatch simply due to normal wear and tear on the drive... Effectively creating a game of Russian Roulette; except instead of getting shot you lose data.
As such, unauthenticated encryption becomes the only rational way to encrypt an entire drive. Since an attacker cannot control the result of changes in XTS it's better than modes like CBC (where an attacker can rewrite the drive to whatever they want simply by being decently clever) or CTR (where cleverness isn't even a prerequisite to tamper with data), and XTS isn't vulnerable to statistical analysis like ECB. Therefore it's a not-ridiculous trade-off for cases where authentication can't be reasonably performed.


ECDSA: with knowledge of private key, can we make signatures with partially chosen content?

If the attacker has the ability of choosing the private key, then he can create a valid signature $(r,s)$ with a target value for $s$ for any message $m$. The attack works in the following way:
The attacker choose its target $s$, generates a random ephemeral key $k$ and computes the hash of the message $e = H(m)$.
Then the attacker computes the scalar multiplication $kG$ and takes $r$ as the x-coordinate of the result modulo $n$.
Then he computes the private key $d$ as:
$d = \frac{s - k^{-1}e}{k^{-1}r}$.
In this way $s$, when computed in the standard way: $s = k^{-1}(e+rd)$ will match the desired $s$.
In case the attacker can't choose the private key then I don't see how he can achieve his goal because in $k^{-1}(e+rd)$ he can control only $k^{-1}$ but that will pseudo-randomly influence the value of $r$.


find master key given all but last decryption round keys

Unless you have a non-standard version of AES decryption, the decryption round keys should just be the encryption round keys in reverse order. In the notation of the wikipedia article, it sounds like you have $W_4,\ldots,W_{59}$ and you want to know $W_0,\ldots, W_7$ ($W_4,\ldots W_7$ represent the penultimate decryption round key; $W_8,\ldots W_{11}$ represent the antepenultimate decryption round key and so forth).
$W_4,\ldots W_7$ can be read off directly and (per the linked article) we have
$$W_8=W_0\oplus S(\mathrm{LeftShift}(W_7)\oplus 1\iff W_0=W_8\oplus S(\mathrm{LeftShift}(W_7))\oplus 1$$
and
$$W_9=W_1\oplus W_8\iff W_1=W_9\oplus W_8$$
$$W_{10}=W_2\oplus W_9\iff W_2=W_{10}\oplus W_9$$
$$W_{11}=W_3\oplus W_{10}\iff W_3=W_{11}\oplus W_{10}$$
which allows us to recover $W_0,\ldots,W_7$ which is the same as $K_0,\ldots, K_7$.
Note that the LeftShift function rotates the 32-bit word left by 8 bits and that the $S$-box is the same as used in AES encryption.
ETA if you are using the "T-table" implementation of AES (which is suggested by your MixCol remark), then yes, you will need to apply MixCol to the 32-bit words to get the $W_i$. If you use the standard AES MixCol() then no S-box adjustment is needed; if you use the T-table combined MixCol(Subbytes()) then you'll also need to apply the Inverse S-box as well.


Why isn't the alternating step generator used more often?

A stream cipher, RSA, or whatever you designate by the expression "discrete logarithm system", are not "one-way functions". In particular, asymmetric encryption algorithms and digital signature algorithms provide functionality which is not doable (or not with the same usability) with only the "scrambling" techniques of symmetric cryptography. Let's not confuse things.
ASG is a stream cipher: it produces a key-dependent sequence of pseudo-random bits, which can be combined with some data (bitwise XOR) to encrypt or decrypt it. This is symmetric encryption. As a symmetric encryption engine, it is rather lousy:

Linear Feedback Shift Registers are inefficient in software. They used to be popular in the 70s and 80s because a LFSR is inexpensive, in terms of silicon area, when implemented in a custom ASIC. However, the World has evolved since, and has gone more and more software-based. As of 2011, extreme silicon efficiency is relevant only to very small platforms (RFID tags). For all others, ASG is just slow.

ASG is wasteful of its state. For n-bit security, it requires three LFSR of size at least n bits. Compare it with A5/1: A5/1, with m bits of state, has a security equivalent to 22m/3. The original A5/1 state size is only 64 bits, so its security is in the realm of the highly breakable and open to many kinds of optimizations with precomputations; but the structure of A5/1 could be extended to longer registers, and yield adequate security. For instance, with three LFSR with a total size of 192 bits, you could get with an A5/1-like cipher about 128 bits of security, which is, in simple terms, "totally unbreakable for the foreseeable future". To get the same security level with ASG, you need 384 bits of state, i.e. twice as much.

There is more to a stream cipher than simply spouting out bits. A complete specification should define how the key is transformed into the initial state, preferably along with an Initialization Vector, so that one could encrypt several messages with the same key (exactly what RC4 lacks, and it proved to be an endless source of vulnerable implementations). Weaknesses often hide in those steps. Without such a specification, ASG is like a car engine: regardless of its power, it will not get you far unless you add wheels.

As @Marsh points out, ASG has been patented. This alone is enough to explain that it is not widely used. There is no shortage of good stream ciphers, that we do not know how to break; why would anybody use yet another one, of questionable efficiency and subject to usage conditions and assorted royalties ? In cryptography, a patent is often a way to make sure that a given algorithm will not get used.


Is it safe to generate GCM/GMAC intermediate tags?

Can xor`ed tags info be useful for any kind of attack?

Yup; by using the same IV for multiple generated tags, the attacker can effectively recover the internal GCM value $H$, and with that, generate tags for any arbitrary data.

(You stated that xor'ing the two tags discarded $H$; unless you are using the notation $H$ to mean something other than the secret value that the GMAC polynomial is evaluated at, this is not correct.  It does discard the $Encr(IV)$ value that is exclusive-or'ed with the polynomial evaluation.

GMAC works this way: it takes a ciphertext (and AAD), formats them into a polynomial, and evaluates that polynomial at a point H.  Then, it adds (xors) in a value that depends on the IV.  So, to attack this, the attacker would take the two ciphertexts (and AADs), format them into the polynomials (with the tags as the constant coefficient), and then subtract (xor) those two polynomials. What he ends up with is a polynomial that he knows that evaluates to 0 at $H$; all he needs to do is find a zero of that polynomial.

That turns out to be a feasible task; in fact, with a second polynomial (which requires a third GMAC tag evaluated with the same IV), it becomes easy (the Euclidean Method over polynomials works).

This attack relies on the fact that the same IV is used for every tag; if a different IV is used (say, incrementing the IV whenever you generate a tag), this doesn't work, and it turns out to be secure.


Question on the remote coin flipping problem

Is the definition of 'box' i gave wrong? What is the correct definition?

It is incorrect.

The analogous description of a commitment scheme would be that it is a box that contains only one choice (for example, "heads" or "tails"), Alice can place either, and Bob can't tell (by looking at the box) which is in it.

Later, Alice can open the box; Bob can then tell what's in it and (here's the key point) Alice can't change her mind what's in the box.

With this definition, this is a secure coin flip protocol (except that when Alice learns Bob's choice, she can walk away without opening the box; that needs to be handled somehow).

The easiest way to implement a commitment scheme is with a cryptographical hash function; Alice picks the secret value she's putting into the commitment and a long random nonce, she hashes them both together:

$$Commitment = Hash( Secret || Nonce )$$

She then sends the hash to Bob.  Bob, by looking at the hash, can't recover the commitment (because of the random nonce).  Then, Alice opens the commitment by revealing the secret and the nonce; Bob verifies the secret by hashing the revealed secret and nonce together to recompute the original commitment.  If the Hash used is collision resistant (that is, we can't find two distinct values that hash to the same value), then Alice can't have a single commitment that can open to two different value (because that would imply two different $Secret || Nonce$ values that hash to the same thing, and we assume Alice can't find such a pair).


Does the security of RSA come from just the carries in multiplication?

might have the terminology wrong when I say "GF(2) polynomial multiplication"

You are thinking of multiplication in the ring of binary polynomials, that is polynomials with coefficients in the Galois Field with 2 elements. That set is noted $GF(2)[x]$. It's addition reduces to XOR of the coefficients of equal weight. It's multiplication is called "carryless multiplication" in computing. It supports an analog to Euclidean division, and modular arithmetic.

It's my understanding that if you calculate $N=pq$ using (this) multiplication rather than ordinary multiplication, it is easy to factor $N$.

Yes. There are efficient algorithms for factoring binary polynomials into irreducible polynomials (which are analogs to primes in the ring of binary polynomials).

Does it mean that the security of RSA comes entirely from the addition carries that happen during ordinary multiplication?

True, RSA is not secure if we remove the carries (in the additions within it's multiplication by the schoolbook algorithm). I can't agree with "security .. comes entirely". Analogy: a chain is insecure if one removes it's last link, yet it's security does not come entirely from that link.


You are correct about the graphical representation. A line in the finite field $\mathbb{F}_p$ is not $y=ax+b$ but "informally" $y \equiv ax+b \pmod p$, so the line "repeats" itself. For the tangent, you refer to the algebraic formula to trace the line.
Have a look at the third figure here.


On the fly signatures and zero-knowledge

Actually, it has not really to do with zero-knowledge.

From any public-coin three move identification scheme you can derive a secure signature scheme (in the random oracle model) using what is called the Fiat-Shamir heuristic. Many of these protocols represent honest-verifier zero-knowledge proofs (like the Schnorr, GQ etc. protocols). Now, every such scheme has basically the same structure (choose randomness, compute commitment, compute hash, etc.) and thus is a candidate for the precomputation of the first two steps as you describe it for the Schnorr signature.


Assuming you are talking TLS_PSK without DH or RSA (which are an option), if an attacker compromises the PSK and watches the nonces go past in the clear, yes the attacker can easily compute the master secret.

Section 2 of RFC4279 details how the premaster secret is computed. Without DH or RSA, there is no, indeed can be no*, additional entropy added.

The master secret is a function of the premaster secret and two nonces sent in the clear at the beginning of the handshake. So if the handshake is captured, so are the nonces. So all the inputs to compute the master secret are known.

* Any additional entropy that could be added must be shared. TLS_PSK assumes that the PSK is the only shared secret value between the two parties.


How does forking lemma work in regard to Digital signatures produced by GPV hash and sign algorithm based on lattices?

While, as Chris said, GPV does not rely on the forking lemma, here is a cute metaphore for it.

Imagine a video game, with n level. The game is tough, and at each level, you have a probability 1/2 to die. If you die you have to restart from scratch. It's running on a very old game console, and you can not save your game. So, you'll need an average of $2^n$ trials before you win the whole game.

The game remains fully deterministic though, and the only source of randomness is your limited skill to reproduce exactly the same sequence of keystrokes on your gamepad.

The forking lemma can been thought as a small device in between your gamepad and the console, that can record your keystroke and replay them. So, if you were lucky enough to succeed level 1, but fail level 2, you can replay exactly the winning sequence of keystrokes for level 1, and therefore directly replay level 2, to try a sequence of keystroke there. With such a strategy, you can win the game playing on average $2n$ levels.

Back to the crypto-world, the deterministic console is the attacker, and the  sequence of keystrokes of each level are the responses of the random oracle to each hash queries. Using the forking lemma strategy, you can try several response for a given request, without having to rerandomize all the previous responses. This way, you can somehow trick your attacker to get to a particular situation much more efficiently than hoping a random set of $n$ response will get him there.


What is the exact meaning of revocationWarning and revocationNotification in RFC 3161?

According to a discussion on the PKIX mailing list, it means the TSU (Time Stamping unit) certificate which signs the time stamp responses.


When I use --verbose --list-packets on an export of a secret key it displays all the fields in the secret key (sub)packets. At least it looks like it is complete.

It does not open key encryption, so I have to export the key with a empty passphrase (unfortunatelly there is no export option for that anymore so I had to edit the key).

In this case it uses a named curve, the curve parameters are publically known and not exported.

> gpg.exe --verbose --list-keys
pub   brainpoolP384r1 2017-12-09 [SC]
      971D76C158AFD6D6AC53205327C195C6F0FB0EDA
uid        [ ultimativ ] Bernd Eckenfels (test) <ecki@zusammenkunft.net>
sub   brainpoolP384r1 2017-12-09 [E]

> gpg.exe --export-secret-key > secret.pgp

> gpg.exe" --verbose --list-packets secret.pgp
...
# off=0 ctb=94 tag=5 hlen=2 plen=168
:secret key packet:
        version 4, algo 19, created 1512840291, expires 0
        pkey[0]: 092B240303020801010B brainpoolP384r1 (1.3.36.3.3.2.8.1.1.11)
        pkey[1]: 042B9980A50F01AE91CA7B5A6ABDD350B3FE6BB8E7F44E561FDCB45354BA0D721DA4D9E3DB9B8CD96E248F2099E643E0073649E6D97DB9FCF67B1060F8F36EE0F12F3CEAC68F0D7DAC811DA290693F7620640F87A398901E6D2BDBEA6D4A7251E4
        skey[2]: 40223083F5447B9C109A2F063EAF45FFA7D3DDC48AF71F061B4E95CA475775CF488095D4EDE4109B9539DFD036AE4DB7
        checksum: 1872
        keyid: 27C195C6F0FB0EDA
...
# off=397 ctb=9c tag=7 hlen=2 plen=172
:secret sub key packet:
        version 4, algo 18, created 1512840291, expires 0
        pkey[0]: 092B240303020801010B brainpoolP384r1 (1.3.36.3.3.2.8.1.1.11)
        pkey[1]: 0467F588651ACAB96B80CA052030B3337E8374586C86B3D4386D5569D6C548C0D76662EB112438300B73275FB81809CE6642D3B1878292729B1F3FD1AE2C246AE7064A7B9464446E7A4E0C16B25FD933556371271862C6EEFDFE01087BEEB3CFF9
        pkey[2]: 03010909
        skey[3]: 15FCB0053B11FD8E4E907E9E7ED937F0E226AE0DF4D79D333ED18BF396191628E8A82241BF26B1C1FBD9F5984636A495
        checksum: 19cb
        keyid: 80C1909634D5FC1B

18  ECDH public key algorithm   [RFC6637]
19  ECDSA public key algorithm  [RFC6637]

pkey[0] is the curve OID. Parameters of the curve are public known and not part of the key format.

pkey[1] is the public point (uncompressed format starting with 04 and then two 384bit scalar integers as coordinates).

According to RFC 6637 there is only a single secret algorithm specific parameter for ECDH and ECDSA keys: a MPI scalar. The above example lists them as skey[2] for ECDSA main key. In my case is a 0x017f bit long scalar (48bytes).

BTW: If exported with password protected keys, it looks like:

# off=0 ctb=94 tag=5 hlen=2 plen=214
:secret key packet:
        version 4, algo 19, created 1512840291, expires 0
        pkey[0]: 092B240303020801010B brainpoolP384r1 (1.3.36.3.3.2.8.1.1.11)
        pkey[1]: 042B9980A50F01AE91CA7B5A6ABDD350B3FE6BB8E7F44E561FDCB45354BA0D721DA4D9E3DB9B8CD96E248F2099E643E0073649E6D97DB9FCF67B1060F8F36EE0F12F3CEAC68F0D7DAC811DA290693F7620640F87A398901E6D2BDBEA6D4A7251E4
        iter+salt S2K, algo: 7, SHA1 protection, hash: 2, salt: 70B08AE0E115EFEE
        protect count: 1507328 (167)
        protect IV:  98 be 19 56 65 43 7c 32 0a ff 4f 21 5b eb 47 af
        skey[2]: [v4 protected]
        keyid: 27C195C6F0FB0EDA

The examples have been created with win64 gpg 2.3.2 (libcrypt 1.8.1).

Here is the test key: https://gist.github.com/ecki/8adb287fa64347bfba218a6fd9e21d0f and details.


Non interactive zero knowledge proof with common reference string

A NIZK in the CRS model consists of algorithms $(\operatorname{Setup}, \operatorname{Prove}, \operatorname{Verify})$ where
$$\operatorname{Setup}(1^\lambda)\rightarrow (\sigma, \tau)$$
generates a public CRS $\sigma$ and a verification state $\tau$. The proving algorithm $$\operatorname{Prove}(\sigma, x, w)\rightarrow \pi$$ uses the CRS, a statement and a witness to produce a proof $\pi$, which the verifier can check using the verification state
$$\operatorname{Verify}(\tau, x, \pi) \rightarrow 0/1.$$

Such NIZK systems exist for virtually any statement you could be interested in, namely for any $\textbf{NP}$ relation. You can find an implementation of a NIZK for Boolean circuit satisfiability here: https://github.com/scipr-lab/libsnark


How should verification work? - JWT documentation are your friend.
Should I look at the JWT's signature section and verify with the private key each time? - https://scotch.io/tutorials/the-anatomy-of-a-json-web-token
should I store the token in a No-SQL? - NO, there's no need if you are able to decode the token that mean the token is valid.
secret key be? it's depends the bigger the key the slower your api so its a trade off (remember you need to decode the token on every request)
Is RSA with the HMAC SHA256...? Most people using HS256,

I'm recommending for you to check out this url

Hope it helps,


zero knowledge proof for complete new user authentication

No, you can not.

You assume:

$B$ does not know anything about $A$.
You need to know if $A$ is actually called Alice.

Well, that does not work. There is no possible proof that $A$ is actually called Alice. That is unless you verify some other credentials, e.g. an ID card. But trust can not be generated out of nothing. That is simply impossible.

For example, if there is no way to verify a persons name, then no one in the world can decide if he is actually talking to the real Alice or to Eve who is just calling herself Alice.

The question has nothing to do with zero knowledge - that is just impossible in general.


Elliptic Curve Encryption Ciphertext Size

Ok, I sum it up.

In ECIES, which is a hybrid encryption scheme, the ciphertext size is one point of the curve + the size of the encrypted message (size of the message + small overhead of padding for the symmetric cipher) + the tag length of the used MAC. As CodesInChaos pointed out, if you work on a 256 bit curve (giving 128 bit security), then using point compression this will amount to 32 byte (and 64 otherwise) for the elliptic curve point and as he mentioned in addition to the ciphertext and the MAC some little overhead for the format.

A Note on ElGamal (as in the original Question):
ElGamal is not really useful for larger messages and when using ElGamal in the elliptic curve setting hashed ElGamal should be your choice (as you avoid cumbersome mapping of messages to points on the curve). You could also use a hybrid version of ElGamal to achieve a hybrid cryptosystem like ECIES does.

But ECIES is standardized and provides better security (IND-CCA) as the ElGamal versions (only IND-CPA).


What is a simple 8-bit cryptographic hash function that I can use in a quantum simulation of Grover's algorithm?

Your requirement that it not be trivially crackable is already violated by the premise of an 8-bit hash function: for a uniform random 8-bit function it takes an expected 128 trials to find a preimage, and the time for an expected ${\sim}256/n^3$ trials to find the first preimage among $n$ targets if parallelized $n^2$ ways.  But maybe you meant there are no better-than-generic attacks on it.  (Similarly, it takes an expected ~20 trials to find a collision, although it's not clear that collisions are relevant to your application.)

You could use a Keccak sponge with 1-bit words for a total 25-bit state, 12 rounds, and an 8-bit capacity.  I don't know 25-bit Keccak admits better-than-generic attacks—I wouldn't be surprised if it did—but it is structurally the same as the Keccak permutation used in SHA-3, with 64-bit words, 1600-bit state, 24 rounds, and either $4\lambda$- or $2\lambda$-bit capacity (respectively, for the fixed-size hashes like SHA3-256, or for the extendable-output functions like SHAKE128) for $\lambda$-bit collision resistance and $2\lambda$-bit preimage resistance.

Right now, the best collision attacks on 1600-bit Keccak[1][2] seem to be limited to 6 rounds, which justified the use of 12 rounds for KangarooTwelve.  There are newer attacks on other aspects of Keccak, but 12 seems like a reasonable margin—and it's not clear that those attacks would be cheaper than Grover.  If all you want is preimage resistance, a $\lambda$-bit capacity should suffice for $\lambda$-bit preimage resistance.

One nice thing about a permutation-based sponge like Keccak is that the fixed permutation is, well, a permutation, so it will require no ancillary qubits to implement; the only need for ancillary qubits will arise from xoring the message into the state to hash it.


Zero Knowledge and Computational Indistinguishability

Suppose in some protocol Alice is supposed to send an encryption of her special secret $s$ under a public key $pk$. She is sampling from the distribution of encryptions of $s$.

Bob can choose a random plaintext $r$ and encrypt it under $pk$. He is sampling from the distribution of encryptions of random plaintexts.

Even though Bob doesn't know Alice's special secret $s$, these two distributions are computationally indistinguishable (that's the basic definition of security for the encryption scheme). So this message (Alice's encryption of $s$) is zero-knowledge.

In a real example, you would have to simulate the entire exchange of all messages (called the transcript). It doesn't really work to simulate just one at a time, you have to capture correlations along messages if there are many rounds in the protocol.

Imagine Alice wants to prove to Bob that she is a good archer. The protocol to convince him is for Bob to paint a target on the wall, then Alice will fire an arrow into the bullseye. The "transcript" (the information that Bob leaves with) is a target painted on a wall with an arrow in the bullseye.

But Bob can generate the same distribution of transcripts without Alice's help! He can just put an arrow into the wall first and then paint a target around it. Hence, the protocol is "zero-knowledge."


You can use different key pairs for this. You can give both Bob and Cesar two public keys that they can use to encrypt documents with. Those public keys are part of a key pair that is shared with Bob and Cesar - one for Bob and one for Cesar.

Bob or Cesar encrypt the document by first encrypting a two random symmetric keys with the public keys (one each) and using the result of XOR-ing the two random values as another symmetric (data) key. Then either of them needs to encrypt the document with the symmetric data key. To decrypt they both need to decrypt both symmetric keys, combine them and then decrypt the document. They can do this in any order, as long as the two symmetric keys become available at the same time.

This is a fairly basic secret sharing scheme with an asymmetric component.

Undoubtedly there are better schemes that have additional properties. Having some kind of signing or authentication should be high on your wish list as well.


How are messages from server secured when using SSL certificate

You are missing the entire TLS protocol. The TLS protocol first establishes session keys. These can be randomly created at the client and send encrypted to the server. After that the session keys can be used to protect the data for confidentiality, integrity and authenticity. Encryption and authentication is performed in both directions.

The TLS protocol is however gravitating towards authenticated ephemeral Diffie-Hellman, which is a key agreement protocol. Ephemeral DH provides forward security, meaning that the session keys (and thus the data) stay secret even if the private key gets factored afterwards. In that case the private key is only used for signature generation to perform authentication.


Why do we use (pseudo) random permutations and not (pseudo) random functions for en- and decryption?

We do use PRFs for encryption and decryption!  We use them as stream ciphers to generate one-time pads.

For example, with the ChaCha20 stream cipher, the encryption of the $n^{\mathit{th}}$ message $m$ in a conversation is

\begin{equation*}
  \operatorname{ChaCha20-Encrypt}_{\;k}(n, m) = m \oplus p,
\end{equation*}
where $\oplus$ is xor, and the pad $p$ is generated by
\begin{equation*}
  p = \operatorname{ChaCha20}_{\,k}(n \mathbin\Vert 0)
                \mathbin\Vert
                \operatorname{ChaCha20}_{\,k}(n \mathbin\Vert 1)
                \mathbin\Vert
                \dots.
\end{equation*}

$\operatorname{ChaCha20}_{\,k}$ is the ChaCha20 core PRF under the key $k$.

Likewise for the AES-CTR stream cipher, but we use the PRP $\operatorname{AES256}_k$ approximating a PRF instead of the PRF $\operatorname{ChaCha20}_{\,k}$ to generate each block of the one-time pad.  In all cases with this pattern, decryption conveniently turns out to be exactly the same procedure—which is a bonus for AES, because $\operatorname{AES256}_k$ is usually faster to compute than ${\operatorname{AES256}_k}^{-1}$, the latter of which is unnecessary to use in AES-CTR.

N.B.: If you're thinking about doing this in practice, please use it responsibly in an authenticated encryption scheme like crypto_secretbox_xsalsa20poly1305 or AES-GCM, not alone, unless you're very carefully designing an exotic protocol.


Why does UMAC encrypt the output of universal hash function?

What would go wrong if I skipped the encryption step?

It's be easy for someone getting some message/UHASH pairs get enough information about the key to produce further message/UHASH pairs himself.  If he receives enough pairs (and it wouldn't take that much), he can fully recover the entire key (and then generate a UHASH for any message of his choosing).

To take a simple example, suppose the attacker receives the UHASH for two messages that differ in a single block.  If we call the data from the block that differs from one message $(A, B)$, the UHASH for the first message is $(k_1 - A) \cdot (k_2 - B) + M$ (where $M$ is the contribution from the rest of the message, and $k_1, k_2$ is the UHASH keying data for that block); if the data from the second message is $(C, D)$, then the UHASH for that second message is $(k_1 - C) \cdot (k_2 - D) + M$ (with $M$ being the same, as we assumed that the rest of the message is the same).

If we substract these two, the attacker can recover the value $(k_1 - A) \cdot (k_2 - B) - (k_1 - C) \cdot (k_2 - D) = AB+CD - (B+D)k_1 - (A+C)k_2$

He has a nontrivial probability of being able to recover $k_1, k_2$ just from this; if not, a third message that differs in only this block will make the recovery unique.

This observation is not difficult to extend to sets of messages that differ in multiple blocks.

  In case I have to skip the encryption step, what properties would be required from the universal hash function to make the scheme secure?

I can't add much to what Ricky Demer has already said; if you need a function that can be used as a MAC, it needs to have the security properties of a MAC


How do I create a cryptographic signature and commitment scheme with accountable evidence?

I, personally, did not know of any scheme with such properties yet so I took the challenge of creating one and succeeded. After that, I was really unsure on whether to post it or not since it SHOULD NOT BE USED. I decided to do so for the mere point of showing that such schemes are probably possible.

Given an elliptic curve with a generator $G$ of order $q$ and a hash function $H_q(x)$ which maps $x$ to $[1, q]$:

$\operatorname{GenKey}():$

$s_k \leftarrow Z_q$
$P_k := s_kG$
$D_k := H_q(1||s_k)G$

$\operatorname{Sign}(s_k, B):$

$m = H_q(2||s_k||B)$, $M = mG$
$c = H_q(P_k||M||B)$
$p = m+c*s_k$
$\sigma = (M, p)$

$\operatorname{Verify}(P_k, B, \sigma):$

$c = H_q(P_k || M || B)$
Check if $M+cP_k = pG$

So far, this is a variation of the Schnorr signature scheme which uses the hash-function to generate the private masking key, like it's done in EdDSA instead of randomly picking one. Please note that I highly discourage anyone from using this scheme already since it hasn't gone through formal research.

Based one the rationale that this masking key private, we can use it to create a derivation key to $D_k$.

$\operatorname{GenX}(s_k, B):$

$x = H_q(1||s_k)-H_q(2||s_k||B)$

$\operatorname{DeriveD_k}(\sigma, x):$

$D_k = M + xG$

Let's discuss the properties of this scheme:

Obviously, there is an $X_i$ for each $B_i$ which can be computed easily if you know $s_k$.
Also, each $(\sigma, x)$ tuple should lead to the same $D_k$.
Computing any $\sigma$ should require $s_k$. Calculating $x$ from any $\sigma$ requires knowledge of $s_k$ as well.
Even if you know $D_k$ and a $\sigma$, finding $x$ is as hard as solving the discrete logarithm of $D_k-M$.
Even if you know $D_k$, and choose a $x \leftarrow Z_q$, you would need to forge a signature.
Let's discuss the privacy of the signer by assuming one would compute the challenge by $H_q(M || B)$ and someone knows $\sigma$. He could then compute $P = c^{-1}(pG - M)$. This is circumvented by incorporating the public key into the challenge.
Given a dishonest signer, he could chose a random $y \leftarrow Z_q$ and use it as private key for $D_k$ instead of $H_q(1||s_k)$ or could create commitments which do not lead to $D_k$.

Again, I do not recommend using this scheme since it has not undergone any research at all instead of my two hours.


How do we reduce the multiplications in the AES mix column layer using $x^4 +1$

The $x^4+1$ is implicit in the matrix.

What you are doing is that you consider formal sums $z_0 + z_1 \alpha + z_2 \alpha^2 + z_3 \alpha^3$ for $z_i$ elements of the field $\mathbb{F}_{256}$, and a formal value $\alpha$ which is not in $\mathbb{F}_{256}$, but is such that $\alpha^4+1 = 0$. You can add and multiply such elements, always keeping the result in the same set by applying the rule that $\alpha^4 + 1 = 0$. If you set:
\begin{eqnarray}
y &=& y_0 + y_1\alpha + y_2\alpha^2 + y_3\alpha^3 \\
z &=& z_0 + z_1\alpha + z_2\alpha^2 + z_3\alpha^3 \\
\end{eqnarray}
then you have:
\begin{eqnarray}
yz &=& (y_0 z_0 + y_1 z_3 + y_2 z_2 + y_3 z_1) \\
&+& (y_0 z_1 + y_1 z_0 + y_2 z_3 + y_3 z_2) \alpha \\
&+& (y_0 z_2 + y_1 z_1 + y_2 z_0 + y_3 z_3) \alpha^2 \\
&+& (y_0 z_3 + y_1 z_2 + y_2 z_1 + y_3 z_0) \alpha^3 \\
\end{eqnarray}

This equation can be expressed as a matrix multiplication. The example in your question really is the multiplication of $z = D4+BF\alpha+5D\alpha^2+30\alpha^3$ by $y = 02+01\alpha+01\alpha^2+03\alpha^3$. By writing it as a multiplication by that specific matrix, you "hide" the polynomial $\alpha^4+1 = 0$ into the matrix (specifically, the matrix columns are $y$, $y\alpha$, $y\alpha^2$ and $y\alpha^3$).

Note: The set of formal sums $z_0 + z_1 \alpha + z_2 \alpha^2 + z_3 \alpha^3$ is actually the ring $\mathbb{F}_{256}[x]/(x^4+1)$, i.e. the ring of polynomials with coefficients in $\mathbb{F}_{256}$ and taken modulo the polynomial $x^4+1$. It shall be noted that this ring is not a field, because $x^4+1$ is not irreducible over $\mathbb{F}_{256}$; indeed, in that field, $x^4+1 = (x+1)^4$ (it's a binary field, addition is XOR, thus $2=0$). The ring not being a field does not prevent the operation from being computed, but it means that there are couple of values $(y,z)$ such that $y\neq 0$, $z\neq 0$, but $yz = 0$. However, the $y$ value used in AES ($02+01\alpha+01\alpha^2+03\alpha^3$) is invertible in that ring, which is a blessing because it means that multiplication by $y$ is a bijection; otherwise, decryption would not always be possible.


How secure is this logarithmic encryption algorithm?

I'll assume R is secret, and is the key; and the ciphertext is given as a list of values x in decimal, as in the example given x = 0.559425856.

This is totally insecure: even without knowledge of R, it is trivial to reduce candidate plaintext letters to almost nothing, just by knowing the corresponding x. e.g. if we assume R is an integer in range [2..127], and x = 0.559425856, the only pair (R,M) possible is (13,98). That can be seen by tabulating x by increasing values as follows

 x               R        M
0.557913767     10       62
0.558189871     13       99
0.558248536     14      113
0.558830625      9       51
0.558890092     11       73
0.559030886     15      127
0.559300193     14      112
0.559329667     12       85
0.559425856     13       98
0.559944654     15      126
0.559957234      8       41
0.560120590     10       61
0.560365305     14      111
0.560680089     13       97
0.560692653     11       72
0.560823605     12       84
0.560868731     15      125
0.561444177     14      110

The problem can NOT be fully fixed by giving just enough decimals of x to allows decryption (here, x = 0.559 would do if we round to the nearest), for that still allows to reduce the possibilities in the plaintext a lot.

A lesser problem is that if the plaintext gets known, it is trivial to find R. Hence R can not be reused for different plaintexts. Hence this is not a cipher by the modern definition of that, which requires that there's a key reusable for several messages. That also makes use of the system impractical, as the OTP is; but at least that one is secure.

Also, the ciphertext is larger than the plaintext; another problem that the OTP does not have.


I think why this assumption is hard is that in the prime field $F_p$, you can't find directly $a$ from $g^a \bmod p$ , where $g$ is generator.
So if prime is too large it takes a lot of time to find $a$, because you need to try all the elements in $1..p$.

that is based on DLP(Discrete Logarithm Problem).


How can I calculate non-linearity of an s-box element wise?

I'm not sure if I fully understand your question.

"tell me how to trasform the s-box which is in binary form into decimal form?": Changing numbers between binary and hexadecimal (or decimal, if you would really want to) is not different for numbers that are used with S-boxes compared to any other numbers.
"Also how i calculate the non linearity of certain element of that s-box.":  As far as I am aware, nonlinearity is defined for functions from $\mathbb{F}_2^n$ to $\mathbb{F}_2^m$. In the context of S-boxes, we typically consider the nonlinearity of a full S-box, and not of a single element.

Having said that, let $S : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^m$ be our S-box. Then the nonlinearity $\mathcal{N}$ of $S$ is usually defined in terms of the linearity $\mathcal{L}$ of $S$,  which is usually defined in terms of the $bias$ $\mathcal{E}$ of Boolean functions. Here is the full definition, where $S_b$ considers Boolean component functions of $S$ and $\varphi_a$ does $x \mapsto ax$:
$\mathcal{N}(S) = 2^{n-1} - \frac{1}{2}\mathcal{L}(S) = 2^{n-1} - \frac{1}{2} \max_{a,b \in \mathbb{F}_2^{m*}} \left|\mathcal{E}(S_b + \varphi_a)\right|$.
In this answer, I elaborated on how to compute this bias $\mathcal{E}(S_b + \varphi_a)$ to compute the values in the linear approximation table of $S$, including a fully worked out example. I'll try to avoid repeating that here.
Once all values in the linear approximation table are computed, the largest absolute number (ignoring the trivial case of $a=b=0$) is called the linearity. Using the definition, it is then straightforward to calculate the nonlinearity.


No, it's not safe to seed a PRNG with the hash of a password, then generate a key from that PRNG. That is especially bad with DSA and shared parameters $(p,q,g)$, and only slightly less unsafe for RSA, or DSA with per-key parameters $(p,q,g)$. Two essentials things are missing: some slow step, and salt.
If the proposed procedure was applied, all there is to do to test (with high confidence) if a given password is the right password boils down to Check(password):

Hash the input password.
Seed the PRNG with that hash.
Generate a key using that PRNG, as per the normal key generation procedure.
Return true if the public part of the key generated in step 3 matches the known public key; else return false (for symmetric cryptography, use the key generated in step 3 to decipher a portion of ciphertext, test if the result matches known-plaintext; or, lacking sizable known plaintext, the test that byte distribution in the candidate plaintext is uneven according to a chi-squared test, deciphering more plaintext in case of doubt).

None of these steps is compute-intensive; that's the first problem. An adversary can enumerate likely passwords until it steps on the right one. A password cracker's basic function is to test passwords, approximately from most likely to least likely, using the above Check(password) procedure, until it returns true; at which point it is trivial to recover any non-public part of the key, and any plaintext.
If we assume that the actual password has been chosen randomly, or that the password cracker is good at ordering the passwords tested from most likely to least likely, then the expected cost of finding a password with $N$ bits of entropy is $C\cdot2^{N-1}$, where $C$ is the average cost of the Check(password) procedure above. Costs can be expressed in monetary or energy units; or in core·time, in which case the expected duration of the attack is its cost divided by the average number of cores.
In the particular case of DSA with shared parameters $(p,q,g)$, step 3 boils down to generating $x$ with $0<x<q$ (the private part of the key) by a straight invocation of the PRNG, then computing $y=g^x\bmod p$ (the characteristic part of the public key). That modular exponentiation, if performed naively, is the bottleneck of Check(password). It is not unrealistic to test $10^4$ passwords per core per second even with this straightforward algorithm; and there's an easy time-memory trade-off to speed that exponentiation by I guess a factor of 10 or more, by pre-computing $g^u\bmod p$ for $u$ of the form $u=v·2^{j·w}$ and $0≤v<2^w$, which allows reducing the number of modular multiplications by a factor of ${3\over2}·w$ compared to straight modular exponentiation. I'll thus assume a cost of $10^{-5}$ core·second (perhaps that requires dedicated CPU instructions for the hash and block cipher used by the PRNG, but that's increasingly common).
XKCD's estimate for the entropy in a 4-word password is $N=44$ bits; let's use that, even though it seems more than common practice. We get an expected $2^{44-1}·10^{-5}/3600/24≈10^3$ core. days to find the password. Using rented CPU time at $\\\$0.2$ per core·day (based on EC2 spot price), the expected monetary cost is $\\\$200$ plus adapting an existing password cracker. For Sequoia and its 1572864 cores, that's $2^{44-1}·10^{-5}/1572864/60≈1$ minute.
With RSA, or DSA with per-key parameters, testing a password is perhaps two decimal orders of magnitude more costly (because step 3 is much more complex), and that will make the scheme correspondingly less insecure; but that's an artifact, and still very insecure.
Also, only step 4 in that Check(password) procedure depends on the key; that's the second problem. This fact allows the attacker to amortize all other costs against the keys of several users. All there is to do is replace step 4 by If the public part of the key generated in step 3 matches any of the known public keys, return an identifier of that key; else return not_found; that change introduces negligible extra cost (for each password tested: little more than a single indexed memory accesses into little more memory than needed to store the public keys). That trivial change reduces the expected cost of attack proportionally to the number of users, which is a disaster for security. As a related issue, a rainbow table can be computed once for only a few times the cost or delay that would be necessary for finding the password for one particular key; after that initial effort, most keys are breakable with no sizable cost or delay.
Add that the password with the worse entropy is often what matters to the attacker (e.g. when restricting or accounting for use of a resource shared among several users) and that a sizable fraction of users choose poor passwords, and you'll find that a practical attack is feasible at low cost with a high probability of success using only commodity hardware.

The right technique if it is wanted to generate a key from a password is to replace the hashing (and optionally the PRNG) by stretching of the password (and if at all possible a per-user salt) into pseudo-random bits, using an appropriately parameterized Password-Based Key Derivation Function. A typical PBKDF is a public, deterministic, computable function accepting as input a password (assumed secret), salt (possibly public), and some parameter(s) controlling the cost of its evaluation (and typically, the size of the output). That PBKDF shall behave like a Pseudo-Random Function of (at least) its password and salt inputs.
The PBKDF transforms the password and salt (or something derived from them) iteratively, a high and parameterizable number of times. The transformation is such that it is unlikely that a shortcut requiring fewer iterations is feasible. The number of iterations should be chosen as high as tolerable for legitimate use. That dramatically raises the attacker's cost, since it must evaluate the PBKDF in step 1 of Check(password). Most importantly, optimization of later steps (like PRNG, key generation including modular exponentiation, primality test..) no longer helps the attacker significantly.
The minimum common PBKDF is PBKDF2, based on iterated hashing; a very serious drawback is that it is very susceptible to hardware-assisted acceleration, using ASICs or GPUs. A better one is Bcrypt also known as Eksblowfish, which by using 4kiB RAM makes such acceleration less economical. The state of the art is scrypt: it offers larger and parameterizable RAM usage (in turn raising cost of attack significantly and in a relatively precisely predictable manner); has a structural safeguard against massive hardware acceleration by virtue of using Salsa20/8; can use multiple cores (if available) to reduce the time penalty perceived by a legitimate user, and comes with convincing security argument.
The salt can be a (say) 128-bit random (that's the best when it is possible); or just a unique identifier (like the email of user concatenated with a value common to all users of a given server). It is enough that the salt is different for each public key to ensure that a password cracker must evaluate the PBKDF for each password·key combination tested, rather than for each password tested; and salt comes almost for free in most practical applications. Further, if the salt is unpredictable, the adversary can't start an attack before getting the salt.
Using a salted PBKDF, the expected cost to test a password becomes a parameter that can be adjusted, as a compromise between security and cost of legitimate use. Parameterize script to require 0.5 seconds on a 4-cores machine with a gigabyte of RAM per core (a fair desktop PC; that may translate to 3 seconds on a lost-cost dual-core portable PC); use the email address associated with the key and an arbitrary fixed string as salt; and you can have fair confidence that today's supercomputer would take weeks per XKCD-class password guessed (ignoring the hard-to-estimate difference between one of Sequoia's 1572864 cores and one in that desktop PC, the expected duration of the attack is $2^{44-1}·0.5·4/1572864/3600/24>129$ days, thus odds that an attack succeeds in less than 2 weeks are less than one in 36). Adjust the parameters every odd year (when you force users to change password and key), and you have decent long term security.
Caveat: it is highly recommendable to have in addition the key-dependent on something secret beyond the password, made part of the salt. That's a practical necessity when users are allowed to choose their password and have no incentive to choose a good one.

In addition: it is customary to allow users to change passwords while keeping the same public key. One simple technique is:

Generate a true-random seed S, e.g. 256-bit, that will remain unchanged as long as the user keeps the same asymmetric key.
Stretch password and salt into a symmetric key K, e.g. 256-bit, using an appropriately parameterized PBKDF.
Store the exclusive-OR of S and K; that will be used to recompute S from the password, and will be adjusted to change the password without changing S.
Seed PRNG with S.
Generate asymmetric key (public and private) using PRNG.

An often-used, slighting more complex technique towards the same goal is to symmetrically encipher the asymmetric key using K; that avoids re-generation of the asymmetric key each time the password is entered, and most importantly allows interoperability of various generation algorithms and PRNGs.

It is further asked:

If there was a strict requirement to derive a key from a few bits as possible (if you need salt at some point, it counts against those bits), would seeding a PRNG from N bits be acceptable, or is there a better method in terms of security level per bit to input?

If salt is counted as input the same way as a secret password (despite salt being usually assumed public and coming for free, e.g. the name or email of the key holder), then one is best with no salt.
Again, and in summary, if the input entropy is low, it is bad to feed that precious little to a PRNG (be it directly or through a standard hash) then use the PRNG to establish a key (be it asymmetric, or for a fast symmetric algorithm). Somewhere in the chain between the input and anything the attacker can observe (public key or ciphertext), there must be an inherently costly process, that is a PBKDF. Its salt input should be different for each user, if at all possible without reducing the entropy in what's secret. If a user must remember the whole secret input, not using a PBKDF amount to gross negligence; same for not salting that PBKDF if any characteristic of the user is available.


Deriving Keys for Symmetric Encryption and Authentication

Yes, this is a fine approach.  This sort of technique is known as "key separation".

Since your master key is a cryptographically secure key, you do not need to use a large iteration count.  Also, you could use any PRF, in place of PBKDF2.  (The iteration count is normally used if you are applying PBKDF2 to a passphrase, instead of a cryptographically secure key; but that is inherently problematic from a security perspective, so what you are doing is much better.)

For instance, you could use HKDF or AES-CMAC as your PRF.  HKDF produces an arbitrary-length output, so you can use it as a plug-in replacement for PBKDF2: Derivation = HKDF(MasterKey) and then continue as you described.  A standard way to use AES-CMAC would be to use MasterKey as the CMAC key, and use different message-inputs for each value you want to derive: e.g., CipherKey = CMAC(MasterKey, 0), AuthKey = CMAC(MasterKey, 1), IV = random() (or IV = CMAC(MasterKey, 2)).

(For more on key separation, the tag wiki for key-derivation has a very brief set of keywords that might help you find more.)

Credits: Thanks to @CodesInChaos for suggesting HKDF as one reasonable way to do it.


if I use $e=7$ (or another coprime like $11$) I can't compute $d$

You can use $e=7$. When $n$ is squarefree, a private exponent $d$ will work if (not: only if) $e\;d\equiv1\pmod{\phi(n)}$, that is by definition when $e\;d-1$ is divisible by $\phi(n)$. There are solutions to that if and only if $e$ is coprime with $\phi(n)$. The textbook systematic way to find such $d$ is the Extended Euclidean Algorithm. See there for a more efficient and easier to implement variant; or there for a "binary" variant.

Note: When $n$ is squarefree, the necessary and sufficient condition for $d$ to work in RSA is: $e\;d\equiv1\pmod{\lambda(n)}$ (where $\lambda$ is the Carmichael function). That simplifies computation of $d$, and typically leads to a smaller one. $d=e^{-1}\bmod\lambda(n)$ is required by some RSA standards including FIPS 186-4. When $n$ is the product of distinct primes $p$ and $q$, $\lambda(n)$ can be computed as
$$\begin{align}\lambda(n)&=\operatorname{lcm}(p-1,q-1)\\&=\frac{(p-1)(q-1)}{\gcd(p-1,q-1)}\end{align}$$

  Can I pick $e=3$, even if it isn't coprime with $\phi(n)$?

No. It is required that $e$ is coprime with $\phi(n)$ [equivalently: that $\gcd(e,p-1)=1=\gcd(e,q-1)$ ] in order to insure unique decryption of ciphertexts. Otherwise, there will be multiple plaintexts $m\in[0,n)$ leading to the same ciphertext $m^e\bmod n$. In your case $(n,e)=(77,3)$, for example, $m=4$ and $m=15$ would lead to the same ciphertext $64$.

  Picking $e=p$ or $q$ seams wrong

For large $n$, it would be bad to choose $e$ equal to a factor of $n$ (or with any other approximate relation between $e$ and a factor of $n$) since that would allow factoring $n$. But when one deliberately illustrates RSA with a toy $n$ such as $n=77$ which is trivial to factor, choosing $e$ equal to one of the factors is a non-issue. Still, one could use $e=13$ to avoid that special case.

  What is the largest integer that can be encrypted?

In textbook RSA, plaintext and ciphertext space is the integer interval $[0,n)$. The largest integer that can be encrypted (and decrypts correctly) is thus $n-1$. Notice that it is always encrypted to itself, thus trivial to decipher. More generally, textbook RSA is insecure when directly used to encipher data. It is conjectured secure when $p$ and $q$ are large random secret primes, and a random $x$ in the plaintext space $[0,n)$ is enciphered.


Building multiple keys from the same input using a KDF

Assuming you aren't using a completely broken hash function (speaking of which, what hash and iteration counts are you using? Are they dynamically selected, and if so how?), what you're doing should work.

More specifically, assuming user 1 knows K1 (their own derived key), salt1 (the salt used to derive K1), and salt2 (user 2's salt), but doesn't know S or K2, they should not be able to derive K2 (or S, which would let them get K2 if they know salt2).

With that said, I can't really recommend this approach; it's not really the way KDFs are specifically meant to be used, and adapting cryptographic functions to new uses is often dangerous. Their security properties are not always what you intuitively think they are.

For example, to a naïve understanding of hash functions, knowing the digest of some blob B (without knowing B), and knowing the suffix X that gets appended to B, should not be enough for you to know the digest of concat(B, X). That is, people usually assume that if you don't know the entire input to a hash function, you can't possibly predict the output... even if you know the output of a different input, and know what change was made to that output (in this case, concatenating a suffix). However, due to length extension attacks, it sometimes can be possible to know what the digest will be after appending a known suffix, even if you don't know the original message.

I don't know that anything similar applies to PBKDF2 (or any other KDFs) but I'm still leery of using them in an unusual way. The purpose of the salt is so that, even if two users unknowingly use the same password, you can't tell it's the same password because the derived keys will be different. If you know from the start that the passwords are the same, I don't believe the function is known to guarantee that no additional information could be derived. Maybe it does, maybe it only does with certain hashes, maybe it doesn't... but I don't know, and I don't know if anybody has studied it.


Entropy estimation by Linux Kernel when adding entropy from TRNG

When you are adding entropy from outside the kernel, the kernel's entropy estimation functions are not used. Instead the entropy count is either not updated (e.g. if you just write data to /dev/random) or is updated according to the entropy count given to the kernel (e.g. through the RNDADDENTROPY ioctl).

Since you are using rngd, it will run some tests and assuming they pass ask the kernel to credit the entropy count with the full size of the data that was mixed in. I.e. 160 bits if you had 160 bits of data from the TRNG.


Do I need to use HMAC in this crypto wallet backup application?

No, I don't think that a HMAC is necessary here. However, you may want to consider what happens if the QR code is indeed wrong. For instance, it was found that a system that used passive RFID tags was vulnerable against buffer overrun attacks: all the attacker had to do was to increase the size of the ID represented by the tag.

Ultimately you want simply to keep the private key value secret. The validation of the private key can be handled by performing an action on the wallet. If such an action is not possible on its own or if the verification of the private key solely rests on the decryption of that key then you may be in trouble: you need some way of verification that the decryption result is OK. Padding in that case cannot be trusted enough to be worth the cost (and if you can pad then you can also not pad and store a authentication tag (MAC value).

Having a MAC over the ciphertext makes it much easier to prove security. Note that you can derive the IV from the salt and the pass phrase using scrypt or scrypt and a KDF/PRF (such as, funny enough, HMAC), so you could replace that with an authentication tag. Using SIV mode is also possible, then the IV would double as authentication tag.

The scrypt parameters could be represented by a single protocol version byte representing hard coded parameters.


How is the Swiss post e-voting system supposed to work, and how was it wrong?

In the Swiss Post electronic voting protocol, after voters submit ballots, they are scrambled individually and shuffled together so that they cannot be traced back to voters to find who voted for whom—variously called ballot secrecy, privacy, or anonymity—before they are tallied.

But since the ballots are bits in an electronic system, not physical artifacts, it would be easy to fabricate shuffled ballots inside the magic vibrating silicon crystals in the computer that implements the shuffler.  So the shuffler must also print a receipt that anyone in the world can use to verify that it is just a shuffling and not any other kind of alteration—part of universal verifiability of the election—while still keeping it secret who voted for whom.

The method of universal verifiability in the Swiss Post protocol, as in any electronic voting protocol with ballot secrecy, involves a lot of complicated math.  And it turns out that the way the math was designed enables the vote shuffler to trivially forge a receipt for a fraudulent ‘shuffle’ that changes the outcome of the election.

How does it work?

Let $m_1, m_2, \dots, m_n$ represent filled-out ballots in an election.  We want to keep the ballots secret, but compute the vote tally, and let the public verify the vote tally.

The poll workers see who submitted each ballot $m_i$, so we first encrypt the ballot as $c_i = E_k(m_i, \rho_i)$ to conceal it from the poll worker who puts it in the pile of ballots, where $E_k(m, \rho)$ is a randomized public-key encryption scheme with randomization $\rho$.  Randomization means the poll worker can't just check whether $c_i = E_k(b)$ for each possible ballot $b$ to recover what $m_i$ is.
The vote counter, who knows the secret key, then takes the pile of encrypted ballots, decrypts them, and tallies the results.

Since the poll worker could pass along who voted in which order, we enlist the aid of a vote shuffler to shuffle the votes into the order $c_{\pi(1)}, c_{\pi(2)}, \dots, c_{\pi(n)}$ for a secret permutation $\pi$.*
Since the vote counter could eyeball $c_{\pi(i)}$ to discern whether it is the same as $c_j$ and thereby recover what $\pi$ is, we also ask the vote shuffler to scramble each vote without changing the ballot it conceals.

If $E_k$ is homomorphic in the message and randomization, meaning $$E_k(m_1 m_2, \rho_1 + \rho_2) = E_k(m_1, \rho_1) \cdot E_k(m_2, \rho_2),$$ then we can scramble the votes by $$c'_i = c_{\pi(i)} \cdot E_k(1, \rho'_i) = E_k(m_{\pi(i)}, \rho_{\pi(i)} + \rho'_i)$$ for secret randomization $\rho'_i$.*  Then we pass $c'_1, c'_2, \dots, c'_n$ on to the vote counter.

Members of the public only have their own receipts $c_i$, which without the private key are indistinguishable from one another and from the $c'_i$.  To have confidence that the vote counter or vote shuffler isn't fraudulently changing the outcome of the election by replacing $m_i$ by some malicious $\hat m_i$, the system must be verifiable to members of the public.†

The canonical example of a homomorphic randomized public-key encryption scheme is Elgamal encryption $E_k(m, \rho) := (g^\rho, k^\rho \cdot m)$ where $g, k, m \in G$ are elements of a group $G$ in which discrete logs are hard, and the secret key for $k$ is the exponent $x$ such that $k = g^x$.  Here multiplication of ciphertexts $(a, b) \cdot (c, d)$ is elementwise, $(a \cdot c, b \cdot d)$.

There have been many systems over the years, of varying degrees of efficiency, to prove that what the vote shuffler sends to the vote counter to tally is, in fact, the set of $c_{\pi(i)} \cdot E_k(1, \rho'_i)$.‡  One of them is Bayer–Groth (full paper).  There's a lot of cryptidigitation building on decades of work to make an efficient non-interactive zero-knowledge proof—a receipt that any member of the public can use offline to verify that the $c'_i$ are in fact the $c_{\pi(i)} \cdot E_k(1, \rho'_i)$, without learning what $\pi$ or the $\rho'_i$ are.

The key part in question is the use of Pedersen commitments to commit to exponents $a_1, a_2, \dots, a_n$ with randomization $r$ by sharing the commitment $$\operatorname{commit}_r(a_1, a_2, \dots, a_n) := g_1^{a_1} g_2^{a_2} \cdots g_n^{a_n} h^r,$$ where the group elements $g_1, g_2, \dots, g_n, h \in G$ are independently chosen uniformly at random.

The commitment itself gives no information about $(a_1, a_2, \dots, a_n)$ without $r$ because all commitments are equiprobable if $r$ is uniform—that is, Pedersen commitments are information-theoretically hiding.  But the commitment and randomization $r$ enable anyone to verify the equation for any putative $(a'_1, a'_2, \dots, a'_n)$ to get confidence that they are the $(a_1, a_2, \dots, a_n)$ used to create the commitment in the first place: if you could find a distinct sequence $(a'_1, a'_2, \dots, a'_n) \ne (a_1, a_2, \dots, a_n)$ and randomization $r'$ for which $$\operatorname{commit}_r(a_1, a_2, \dots, a_n) = \operatorname{commit}_{r'}(a'_1, a'_2, \dots, a'_n),$$ then you could compute discrete logs of $h$ and $g_i$ with respect to one another—a pithy summary of which is that Pedersen commitments are computationally binding under the discrete log assumption.  (Proof: If $g_1^{a_1} h^r = g_1^{a'_1} h^{r'}$, then $\log_{g_1} h = \frac{a'_1 - a_1}{r - r'}$.)

The Bayer–Groth shuffler uses Pedersen commitments to commit to one $\pi$ and to the randomization values $\rho'_i$ in the receipt that the public can use to verify the set of votes submitted to the vote counter.  If the vote shuffler could lie and claim to use a permutation $\pi$, while they actually use a function that repeats some votes and discards others, then they could fraudulently change the outcome of the election.  The Lewis–Pereira–Teague paper goes into some details of how this works.

One way to look at this reliance on Pedersen commitments is that the discrete logarithm problem seems hard, so we just have to choose the commitment bases $g_1, \dots, g_n, h$ independently uniformly at random.

The obvious method to pick group elements independently uniformly at random is to pick exponents $e_1, \dots, e_n, f$ independently uniformly at random and set $g_1 := g^{e_1}, \dots, g_n := g^{e_n}, h := g^f$.  This is what the Scytl/Swiss Post system did.
Another way to look at this is holy shit, the exponents $e_1, \dots, e_n, f$ are a secret back door, knowledge of which would enable the vote shuffler to commit essentially arbitrary vote fraud—just like the Dual_EC_DRBG base points.

The election authority could mitigate this by choosing commitment bases using another method, like FIPS 186-4 Appendix A.2.3, which probably makes it difficult to learn the back door exponents, and which can be verified; this is allegedly what Scytl has elected to do to fix the issue, although I have no idea whether they have published the hash preimages necessary to conduct the verification.

This may sound like a trivial mistake: oops, we forgot to zero a secret.  But it illustrates a deeper problem.

The commitment bases $g_1, \dots, g_n, h$ serve as a common reference string in a standard technique (paywall-free) for converting an interactive zero-knowledge proof system into a non-interactive zero-knowledge proof receipt like the vote shuffler is supposed to print out.

In an interactive proof system, the verifier might choose an unpredictable challenge—like which tunnel to come out of in the story of Ali Baba and the 40 thieves—which the prover must answer correctly.  What if we want to make a non-interactive proof receipt that we can publish on a web site for anyone in the public to download and verify?

In some protocols, like signature schemes such as Schnorr's derived using the Fiat–Shamir heuristic, the challenges can be replaced by a random oracle: a random function that the prover can evaluate on the transcript so far to imitate an unpredictable challenge that the verifier might have submitted, but that the prover has no control over.  To instantiate such protocols, we choose a hash function like SHAKE128 that we hope has no useful properties the prover can exploit to forge fraudulent proofs.

Addendum: This post was getting too long already, but two weeks after the flaw detailed here was reported, the same researchers reported another fraud-enabling flaw in the misuse of the Fiat–Shamir heuristic—the designers neglected to feed in the entire transcript of committed values into the hash function (‘random oracle’), which is crucial to the security of the Fiat–Shamir heuristic.  That flaw also appeared in the New South Wales Electoral Commission's iVote system based on Scytl's software, despite the NSWEC's public claims to be unaffected (archived).
Similarly, in some protocols like Bayer–Groth we can use a common reference string: a predetermined bit string chosen randomly and known in advance to the verifier and prover.  To instantiate such protocols, we need a system to pick a random string in advance with negligible probability that the prover can exploit properties of, like we get with FIPS 186-4 Appendix A.2.3.  If the prover can influence the common reference string, the proof means nothing.

This is part of the security contract of a cryptosystem.  To get any security out of AES-GCM, your obligation is to choose the key uniformly at random and keep it secret and never reuse it with the same nonce.  To get any security out of a Bayer–Groth vote shuffler, the verifier and prover must agree in advance on a common reference string that the prover has no control over.  In the Scytl system, the prover chose the common reference string.  Not only did this violate the security contract, but it demonstrated a profound failure to understand the basic premises of the non-interactive zero-knowledge proof system they used.

The public evidence is unclear about whether the authors knew this would serve as a back door, and the Lewis–Pereira–Teague paper cautions that this could be a product of incompetence rather than malice—the technical nature of the flaw was known internally since 2017 (archived) but it's unclear the whether consequences were understood.  It could have been incompetence on the part of NIST that they adopted Dual_EC_DRBG—NIST recognized early on that there was something fishy about the base points and was told not to discuss it by NSA.

The first order of business is not to argue about whether the software vendor Scytl was malicious or incompetent, but to be taken seriously enough by election authorities to demand real scrutiny on designs, not a sham bug bounty hampered by an NDA just before deployment, and to review the process of how we got here to ensure that designs with back doors like this must never even come close to being deployed in real elections because they enable extremely cheap arbitrarily massive unverifiable vote fraud.

(One can argue whether the larger problems arise from undetectable centralized fraud in electronic voting; distributed fraud in voting by mail; or voter suppression by gerrymandering, felony disenfranchisement, and closure of polling stations.  One can argue about other IT issues, about the importance of paper trails and mandatory risk-limiting audits, etc. Such arguments should be had, but this question is not the forum for them—consider volunteering as an election worker instead or talking to your parliament!  This question is specifically about the technical nature of the misapplication of cryptography, whether negligent or malicious, by Scytl and Swiss Post.)

* We assume that there is an omniscient mass surveillance regime monitoring the every action of the vote shuffler to ensure they do not collude with anyone else to reveal secret ballots.  The omniscient mass surveillance regime is also honest and would never dream of colluding with anyone themselves—not wittingly.

† We assume that the public consists entirely of people with PhDs in cryptography, like the country of Switzerland.

‡ The vote counter must also be able to prove that the tally it returns is the sum of the plaintexts of the encrypted ballots that are fed to it, which we will not address here—the specific back door under discussion here is in the vote shuffler.


Is there such thing as an order independent, updatable hash?

The answer largely depends on what security properties you want.

The scheme I would use here is to hash all of the individual parts, then take some Diffie-Hellman group, and then raise the generator of that group to the power of the product of the individual hashes. That is,

$ H(a_1, ..., a_n) = g^{\operatorname{SHA256}(a_1) * ... * \operatorname{SHA256}(a_n)} \bmod p $

for $ * $ being multiplication and $ g $, $ p $ being the generator and modulus of the Diffie-Hellman group. (This could also be done with an elliptic curve group to the same effect).

This provides a number of properties:

It is secure given a reasonable Diffie-Hellman group (if you're using Diffie-Hellman based on modular arithmetic, then $ g $ needs to be reasonably large, or $ g^{a} $ may not be larger than $ n $), and reasonable assumptions similar to DDH
It is communitive; that is, the hash value is independent of the order of the hash (and it can be updated after it's computed by raising the computed hash to the power of a new block)
It is reasonably fast

You may also want to consider using a block chain; it's faster, although it isn't communitive, which is one of the properties you asked for. (I also initially considered using XOR in place of exponentiation in a group, but I quickly realized that can be defeated with Gaussian Elimination. It's possible I'm missing something there, though).