secure embedded/microcontroller crypto using AES-ctr with hmac-sha2

Fgrieu has already posted a good answer, which I won't try to repeat.  However, here are a few additional observations:

For an embedded system, you may want to consider using CMAC-AES instead of HMAC, since you can reuse your AES implementation, and don't need a separate hash function.
Further consider using SIV mode (RFC 5297).  It's very similar to CTR+CMAC, but provides additional protection against accidental nonce reuse, and also removes the need for separate cipher and MAC keys.
Do be careful about nonce reuse, especially if you don't use SIV.  (But please use SIV, if possible!)  Saving the nonce to flash after every message is generally not a good idea, so the usual approach is to write, say, nonce + 1024 to flash before each block of 1024 messages.  On reboot, just resume from the last nonce value in flash, which should be greater than the last nonce actually used.  (Also, make sure that nothing breaks even if power is lost during a write; there are standard techniques for handling this, but they're not really specific to crypto.)
Consider including a timestamp and/or a sequence number in your messages to protect against replay attacks.  If you're potentially using the same keys in both directions, or over multiple channels, also tag your messages with sender and receiver IDs.  (These may be in plaintext, but they do need to be included in the MAC.  For SIV, you can include these as "associated data".)


Is it correct that Alice sends the ciphertext $CT=E_K(IV,AAD,D)$ to Bob together a timestamp $t$ like $CT||t$

That doesn't work; here, GCM doesn't protect $t$; the attacker can easily change it to anything he wants, and GCM will never notice.

Now, you could expand the AAD to include the value $t$; , that is, we have $CT=E_K(IV,AAD || t,D)$.  With that change, this is safe.  What this does is cryptographically bind the value $t$ to the ciphertext (the GCM tag), if the attacker modifies it, then the tag would not validate.

  or encrypt the timestamp in the ciphertext (and in this case the plaintext $D$ becomes $D||t$)

That also works; in this case, $t$ is cryptographically bound to the ciphertext, and hence cannot be modified.

The main difference between the two is whether the timestamp is in the clear or not.


ECDH Public Key Recovery - Determine if valid key exists from just signature and message

"My question is if there is a fast way of determining whether P exists, without doing the full expensive calculations to determine P."

I believe that you could check whether $r$ is a valid nonzero $x$ coordinate; that is, whether it is a part of a solution to curve equation (e.g. if your curve is in Weierstrass form with characteristic > 3, you'd check whether $x^3 + ax + b$ is a Quadratic Residue).

If it is (and if it is nonzero), then yes, you could perform the operations to recover $P$, and it would come up with two valid points, and so that's your answer.


Which is stronger: Threefish 1024-bit, SHACAL-2 512-bit, or AES-256?

Neither SHACAL-2 nor Threefish are "more" secure than AES because it's a case of "meh cannot break" with all of them.

All three ciphers are unbroken and all three use keys larger than 128-bit* meaning the bigger numbers in the key size have no value except to impress people with being bigger and with the company being able to waste computation time. Also note that in the most rares cases it is actually the crypto (and especially unlikely the block cipher) that is broken but rather the implementation and especially the data handling implementation.

Now for a bit of discussion on each cipher:

SHACAL-2. It is based on SHA-2's compression function and from what I can tell turning it into a block cipher was a case of "we did it because we could". It's practical deployment is absolutely negligible and cryptanalysis results are sparse, so I wouldn't trust it more than AES.
Threefish. Threefish was the block cipher underlying the Skein submission to the SHA-3 competition. It has some well-reputed names behind it and is a very useful tool block-cipher with a large block size that is especially hardened against related-key attacks and side-channel attacks. I would actually prefer Threefish over AES if you don't have a well-hardened implementation of AES available and you are on a 64-bit platform and you don't have hardware-accelerated AES available. This is because Threefish only uses additions, rotates and XORs (ARX) which makes it quite easy to implement securely and with solid performance. Analysis-wise it has seen quite a bit during the SHA-3 competition and a bit afterwards, but as Skein wasn't selected it hasn't seen much analysis since.
AES. AES is an excellent block cipher which has with-stood nearly two decades of intense cryptanalysis. Not only hasn't it been broken in this time, but we have also figured out how to implement it securely and it has wide hardware support these days, making it the performance- and security-wise best choice if available. If not, using a more modern ARX based cipher is also appropriate, but especially on a modern phone secure AES implementations should be available.

On this topic, also see the mandatory blog post by Matthew Green.

* If you believe that large-scale quantum computers will exist at some point, you need 256-bit symmetric keys to force $2^{128}$ quantum operations (thanks to Grover's Algorithm) which all three cipher support.


How long would it take to brute force an AES-128 key?

I wrote a similar answer in the past, where the assumption was half the key is known. Since then, the bitcoin hashrate almost tripled (it's used in the estimation, as below). The estimation for half the known key would therefore be $~3.6$ seconds.

But to brute force a $128$ bit key, we get this estimate:

Let's assume we can test as many keys as the current hashrate of the bitcoin network. There special purpose hardware is used and it's for SHA-256, this makes it not directly usable, but it should be close. That means we could test approximately $5 \cdot 10^{18} \approx 2^{62.117}$ encryptions per second. Regarding the type of hardware: For some years now bitcoins are mined mostly with ASICs, which are faster and more efficient than all of those options you listed. That's special purpose hardware, which can't be programmed to do anything else - but it's the best we can do for speed.

That means, for the full key we need $\approx 2^{128} / 2^{62.117} = 2^{65.883}$ seconds. This is approximately:

$68 \cdot 10^{18}$ seconds
$18.9 \cdot 10^{15}$ hours
$2.158 \cdot 10^{12}$ years. Written as integer: $2,158,000,000,000$

Since that number is still slightly hard to grasp, this is the age of the universe: $13.799 \cdot 10^9 = 13,799,000,000$

So a rough estimation would be $156.4$ times the age of the universe for testing all keys. You can divide that number by $2$ to get the average time to find the correct key.

Related question: How much would it cost in U.S. dollars to brute force a 256 bit key in a year?


What does the $e$ operation mean in cryptography research papers?

It's the pairing function. This bilinear map which takes as Input the set $\mathbb{G}\times\hat{\mathbb{G}}$ (in the common case, eliptic curves), and output a group element in $\mathbb{G}_T$ the group target.
In the symmetric case (Type 1), because $e$ is bilinear, you can deduce that $$e(g_1, g_n)^t= e(g, g)^{x_1x_nt}$$
with $x_1,x_n$ respectively be the discrete logarithms of $g_1, g_n$ in base $g$.
For more details check:
https://en.wikipedia.org/wiki/Pairing-based_cryptography


AES 128 GCM - dynamic key with static IV/nonce

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

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


Is there an encryption algorithm that only adds minimal (if any) size compared to the size of the unencrypted data?

A steam cipher does not increase the size of the plaintext, but you need an IV (which then does increase the size) or different key each time, so effectively this doesn’t help. You can get a relatively small increase of size by using AES-GCM with a tag size of 10 bytes and IV of size 12 bytes.  So this increases by 22 bytes overall.

If this is too much, then it depends if you can guarantee that the same plaintext never repeats. If yes, then you could use AES-GCM-SIV with a fixed IV and save the IV bytes. Alternatively, if you don’t need authentication, then you can use XTS but this is far from ideal.

In general, an additional 22 bytes for about 1KB is only about 2% overhead so it’s not significant and your best using a full blown authenticated encryption mode.


can I use PBKDF2 instead of hmac as a hashing tool for sensitive data

So in my case is it safe to use PBKDF2 as hashing tool - to hash any thing like (timestamp+sensitive_info+extra_info) with a SECRET_KEY just similar to hmac?

The reason that a Password Based Key Derivation Function or password hash is used is because passwords are generally not considered secure enough. The iterations or work factor of such a PBKDF makes it harder for attackers to use dictionary attacks and the like to retrieve the password value and any derived key from it.

However, if you already have a secure secret key then there is no need to perform PBKDF2. It doesn't depend on the sensitivity of the protected data at all. So if you have a secret key and you just need integrity and authenticity, then you can just use a normal MAC - such as HMAC. If you also need confidentiality then an authenticated cipher such as GCM makes more sense.

Beware that HMAC doesn't have a salt; you may need a nonce or IV value to make your message / ciphertext secure (but this depends on the threat model for your particular use case). If you use a timestamp then this may be part of providing message uniqueness (although timing information is always a bit dangerous due to precision and reset issues).


is using secp256k1 curve for ECIES considered safe?

How much Unsafe is using secp256k1 for ECIES and what dangers/weakness it exposes /what attack it makes possible?

Let's have a look through the "failures" that secp256k1 achieves according to SafeCurves.

ECDLP: "disc": This means that the curve has a specific value to be small. As the website indicates this is not inherently bad or exploitable, it just means a (minor?) speedup is possible for the brute-force search. Because a large value is "safer" here a curve has to achieve that.
ECC: "ladder": This means that a naturally fast and side-channel resistant scalar multiplication algorithm isn't possible for this curve. However side-channel resistant implementation is still possible (though it requires a bit more care).
ECC: "complete": This means you have to do a case-distinction if you want to add two points $P,Q$ (in theory making side-channel resistant implementations harder). However this is irrelevant in practise given that the case distinction for secp256k1 is "$Q=-P$" or "$Q=P$" or "$Q\neq \pm P$" and for any sane scalar multiplication algorithm we can in fact predict which case will happen at any point with 100% accurcacy, so the fact that there is a case distinction doesn't matter.
ECC: "ind": This means that if you are given a string you can efficiently decide whether you're looking at a random string or a random point on the curve. This most likely won't matter to you unless you have some super fancy protocol that relies on this property, but things like ECDSA and ECDH / ECIES are not included in this.

  Should I avoid secp256k1 completely or I can use in some circumstances?

For "standard" use-cases, i.e. ECDH / ECIES / ECDSA and similar "simple" applications you can use secp256k1 just like Curve25519 assuming you have a secure implementation. The only place where you can't is when you need the indistinguishability property, but that seems to not be the case here.

  What cures are safe for ECIES (since Curve25519 is only implemented for ECDSA)?

Curve25519 should be usable for ECIES given that ECIES is essentially "do a ECDH key exchange with a fixed public key and then hash to shared secret to be used as a symmetric key" and the standardized version of Curve25519 for Diffie-Hellman is also sometimes called X25519.


What paradigm does ABE, KP-ABE and CP-ABE fall into

This is an interesting question. ABAC itself is an access control model, and (at least should be) agnostic to how it is enforced (see some ABAC links below).   ABE-schemes, on the other hand, are cryptographic schemes, where only the terminology links them to attributes (which are, in fact, algebraic group elements mapped into real-life attributes. This mapping is scheme-dependent, and sometimes non-trivial).

However, it seems evident that the designers of ABE-schemes had the ABAC paradigm in the back of their mind, as there are many parallels. I investigated this connection more closely in my dissertation (see the last link below) in connection with RBAC (in some sense, a subset of ABAC).

Currently ABE schemes have difficulties enforcing some RBAC-standardized features, such as role hierarchy and dynamic separation of duty. Thus their support for full ABAC seems dubious. Additionally, ABAC depends on environmental attributes, and obtaining cryptographically verifiable and reliable environmental references is difficult. For example, imagine that a document is allowed to be decrypted only in a certain country. How can the encryptor control the decryption location reliably?

In summary: ABE-schemes represent an independent dimension (an enforcement paradigm) to that of access control models. Yet the current capability to support full RBAC or ABAC features is not there. Core RBAC could, in theory, be supported, though.

Links for ABAC:

NIST guide: "Guide to attribute based access control (ABAC) definition and considerations, NIST SP 800-162", http://dx.doi.org/10.6028/NIST.SP.800-162.
An ABAC dissertation: Jin, X.: "Attribute-based access control models and implementation in cloud infrastructure as a service" (University of Texas at San Antonio Dissertations), https://pdfs.semanticscholar.org/c342/d13a011460df3392815ab74fd6252187d15b.pdf

Link for a RBAC-ABE dissertation

Kiviharju M: Enforcing Role-Based Access Control with Attribute-Based Cryptography for Environments with Multi-Level Security Requirements
http://urn.fi/URN:ISBN:978-952-60-6774-2


Do RSA keys contain a checksum mechanism?

No, there is no checksum built-in to the RSA keys per se. There is no need for that.

  Does this breaks the key ? Or changes the key internally, without
  breaking it ?

[EDIT] It was rightfully pointed out to me that at least one of the statements I typed (in haste) was plain wrong. Now that the answer has served its initial purpose, I've removed my badly worded and therefore wrong statements and just duplicating here the link to a much better explanation of things (which I really liked):
Why does my SSH private key still work after changing some bytes in the file?


However, in some protocols descriptions, like TLS 1.3, I find them say
  the client sends "hello message includes Diffie-Hellman public values
  for the client's preferred groups". What is "group" refers to??

The term group is a mathematical concept that guarantees that a specific operation doesn't leave a set, that it is associative, that there is a neutral element and that there's an inverse element for each element.

Diffie-Hellman generally operates in such groups.
Just view it like this: Your set is defined by $p$, e.g. for all integers $x$ in the group $0\leq x <p$. You then take an element $g$ from it and apply the group operation (multiplication modulo $p$) a certain number of times to it (whatever your exponent tells you).

Now every choice of $p$ describes its own group and additionally you can choose groups with an entirely different structure such as the points of elliptic curves over prime fields (which makes this ECDH)


Encrypt the hash using the public key of the avatar server with ECC. This has a space overhead of 32 bytes (43 Base64 characters). A modern CPU should be able to decrypt about 10000 messages per second per core. If a website uses a fixed key for all the avatars both sides can cache the shared key, so they don't have to pay the cost of the key exchange all the time.

While this solves the "everybody can do an offline search to guess the email matching a hash" problem gravatar suffers from, it doesn't solve all its privacy problems. In particular the avatar service can track users, and the picture data itself allows correlation across sites, even if the hash differs.


What signature aggregation schemes support valid single signature is exist in aggregation signature?

If $A,B,C$ are the three strings, then one could let

$$f(A,B,C) = Hash(A)\,||\,Hash(B)\,||\,Hash(C)$$

where $Hash$ is a publicly known one way permutation.  Then, one can compute $Hash(B)$ and check if it is equal to one of the blocks of $f(A,B,C)$.  Since $Hash$ is one way, knowing $B$ and $f(A,B,C)$ does not leak information about $A$ and $C$.


I'd advise the result of Daemen and Rijmen on the matter called the wide-trail design strategy that has been used to construct the current AES.
Shortly you want s-boxes that have:

High algebraic degree

If you have the ANF of the Boolean function induced by your permutation which is a polynomial $\mathbb{F}_2[x_0,...,x_{n-1}]/(x_0^2 - x_0,..., x_{n-1}^2 - x_{n-1})$ then the algebraic degree is the number of variables in the largest product term of the function’s ANF having a non-zero coefficient.

Balancedness

Let $F$ be a function from $\mathbb{F}_n^2$ into $\mathbb{F}_n^2$. $F$ is balanced if it takes every value of the range exactly once.

High Nonlinearity

The aggregated nonlinearity of your S-box is the minimum nonlinearity of all of it's component functions which you can get with the Walsh-Hadamard transform

Low Differential uniformity

Define the difference distribution of any a function with respect to $a$ and $b$ elements from $\mathbb{F}_2^n$ as $DF(a,b) = \{x∈F_2^n:F(x)⊕F(x⊕a) =b\}.$
Then the differential uniformity is the maximum value got with this function using any pair of $a$ and $b$.

High differential branch number

this is calculated by $min_{x\neq y}wt(x⊕y) +wt(F(x)⊕F(y))$ where $wt$ is the hamming weight.

Note that these are still a subset of all tricks used in literature used to argue about s-boxes but the wide-trail strategy is currently still a good pivot point.
There are very useful tools in the SageMath library to easily check these properties: http://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/sbox.html


Solve the congruence using Pohlig-Hellman algorithm

You are correct in the procedure.
You need to express $x$ as $x = 2^0x_0+2^1x_1+2^2x_2+...+2^{15}x_{15}$
Where the $x_i$ are in $GF(2)$

First compute:
$3^{(0*(p-1)/2)} \pmod p \equiv 1$
$3^{(1*(p-1)/2)} \pmod p \equiv 65536$

So that when you'll compute
$2^{65536/2^{i+1}} \pmod p$ you'll get either 1 (corresponding to $x_{i} = 0$) or 65536 (corresponding to $x_{i} = 1$)

For the first values of $i$ you will get only $x_i=0$, but then for $i=11$: $2^{65536/2^{12}} \pmod p\equiv 65536$ which corresponds to $x_{11}=1$

Then you need to proceed... but I just wanted to show that you don't get 0 for all $x_i$


Does Encryption add difficulties to File Recovery?

It depends on the circumstances, whether encryption will cause difficulty while recovering files. If you have your physical drive damaged then chances of recovering the data in the first place (encrypted or not) are bleak depending upon the extend of damage.
First let's think of this hypothetical situation when using file system level crypto on the contents (files) of a drive: If I have an algorithm (that does not use chaining) that uses encryption  with authentication to encrypt the contents of a drive. Say, my drive got physically damaged, but the damage was to a small extend. It so happend that the "error bits" were on a JPEG image. If I decrypt that content from my hard drive, my software would give me an error stating that, the file / content has been damaged and its integrity can never be trusted and would refuse to decrypt it. But If I know the algorithm and the key and I make a custom software to decrypt the contents of the file no matter what, I might get a decrypted JPEG that may be partially viewable/cluttered at some places. But still in essence the data is tampered and the whole purpose of "authentication" has been compromised!
But the above situation is practical if we are using file system level encryption/ decryption and that is why it is more recommended to use it than FDE (full disk encryption), at least you can view parts of the image / file.  But still the algorithm itself opens up difficulties
if I used AES CBC with HMAC to encrypt my file then the block where the error bit occurs, the decryption becomes cluttered and meaningless, and also alters the output of the decryption of the adjacent block but if I used a stream cipher like XChaCha20-Poly1305 the error byte will be meaningless, but I get the rest and in both cases the authentication tags will not match as a result of the errors in the data in the first place.
Secondly, if I used chaining algorithms AES CBC to do FDE full disk encryption, then the error propagates, from the block where the error occurs and also affects the bytes of the next block getting decrypted . It is mostly due to the fact that the encryption function themselves have an avalanche effect when their input bits are changed giving totally different outputs !
At most if you use chaining you loose blocksize*2 bytes of data for blocksize bytes error in a block. For AES this block size is 16 bytes.
Therefore it depends on the algorithm that you use and also the circumstances in which they are applied.
In practice we use AES XTS as the defacto standard for full disk encryption:
See:
Disk encryption theory

AES XTS

Hope you understand what I wanted to convey...


What's the difference between PBKDF2 and HMAC-SHA256 in security?

HMAC is still very efficient. It's used in PBKDF2 not for the lower efficiency (that's handled by iterating it many times) because of the fact that it takes two inputs. That lets the password and other data be combined in a safe manner, invlunerable to some of the issues that just using SHA256 alone could create.

PBKDF2 isn't doing H(H(H(...H(Pwd + salt))...), it's doing HMAC(Pwd, HMAC(Pwd, ... HMAC(Pwd, Salt + number)...), where + denotes concatenation and the number is a block index. So the iterations use the password as the key for the HMAC in each stage, and stages other than the first are HMACing the output of the previous stage. This mixes the password in to every iteration of the result, instead of just the first iteration.

Hopefully that explains both why HMAC alone isn't enough and the obvious follow-up question of why HMAC instead of just SHA-256.


Recovering key length from transposition block cipher ciphertext

It really depends on the key schedule.  IE, how is the key operated on to find the permutation to be used?

Absent that knowledge, really the only way to know is to launch searches in parallel at different key lengths, and the one that finds the answer first had the right key length.  Unfortunately anything more clever than that will utterly depend on how the key is used to generate a permutation.

Just a note:  As described, this cipher is terribly insecure; the attack is called parallel anagramming, and is not really more difficult than a crossword puzzle.  It breaks the instant the opponent has more than one block, assuming the same permutation is used for multiple blocks.

Permutation ciphers also fall to even a single block of known plaintext.


Is there a bulletproof way to know a file has been successfully decrypted?

From the application designer's perspective: Yes, by using an authenticated cipher like AES-GCM or crypto_secretbox_xsalsa20poly1305, which you should do anyway.  See the scrypt tool for an example of an application that does just that: encrypts a single file using a key derived from a password using an authenticated cipher—specifically, the tool uses AES-CTR and HMAC-SHA256 in encrypt-then-MAC composition, but these days it is almost always simpler to reach for AES-GCM or crypto_secretbox_xsalsa20poly1305.

From the adversary's perspective: Can't say without more information about the plaintext in your particular case.

In most applications in practice, the plaintext has some identifiable pattern even if the application foolishly didn't use authenticated encryption.  For example, an HTML document will usually begin with <html> or <!DOCTYPE; an email will usually have a header and be limited to 7-bit US-ASCII.

In general, we consider a cipher to be secure for confidentiality (in the formal sense of IND-CPA) only if an adversary can't distinguish patterns in the plaintext given ciphertext even when the adversary can choose the pattern.  Of course, a 3-letter password admits a very short brute force attack, so we don't consider that to provide any meaningful security.

  I use brute force to decrypt it, but two different passwords lead to a file that contains English intelligible text. Is there a way for me to know which one is the original one?

Again from the adversary's perspective, let's suppose there's no authenticator to verify a decryption, and the pattern you're looking for is that the text is all 7-bit US-ASCII.  Actually you're probably looking for a pattern that is much sparser in the set of all bit strings, but this one is easy to quantify.

We can reasonably model each byte of a wrong decryption as independent uniform random, so there's a $1/2$ chance each byte in a wrong decryption is 7-bit US-ASCII independently, and if your file is $n$ bytes long, there's a $1/2^n$ chance that all bytes in a wrong decryption are 7-bit US-ASCII.

In cryptography we generally consider an event ‘not gonna happen’ when its probability is well below $1/2^{100}$.  If there are $2^t$ keys chosen uniformly at random (say, $2^{256}$ for AES-256 or Salsa20), all it takes is a bit more than $100 + t$ bytes in this model before you stop worrying about any false positives from wrong decryptions—that is, when the probability of a false positive from this pattern is at most the probability of a false positive from a cryptographic authenticator like Poly1305.

But if you do somehow find yourself confronted with two candidate plaintexts that both meet all your criteria, well, there's nothing in cryptography to help discriminate between them, and you'll have to use outside information to help you decide.

This model assumes that the key is substantially smaller than the message and the cryptosystem is not hopelessly broken by related-key attacks; for example, it breaks down when the key is a one-time pad, but it is a reasonable model for, say, AES-CTR or Salsa20.  Specifically, let $K$ be the event of guessing the key correctly, and let $A$ be the event that the ciphertext decrypts under the candidate key to US-ASCII.  The hypothesis is that that $P(A \mid K) = 1$ meaning that the true plaintext is known to be US-ASCII.  By Bayes' rule,

\begin{align*}
  P(K \mid A)
  &= P(K) \frac{P(A \mid K)}{P(A)} \\
  &= P(K)
     \frac{P(A \mid K)}
          {P(A \mid K) P(K) + P(A \mid \lnot K) P(\lnot K)} \\
  &= \frac{P(K)}{P(K) + P(A \mid \lnot K) (1 - P(K))} \\
  &= \frac{1}{1 + P(A \mid \lnot K) (1/P(K) - 1)}.
\end{align*}

The additional modeling assumption about the cipher is that $P(A \mid \lnot K) = 1/2^n$.  If we suppose the key is uniformly distributed among $2^t$ possibilities (e.g., $t = 256$ for Salsa20 or AES256-CTR) so that $P(K) = 1/2^t$, then this reduces to

\begin{equation*}
  P(K \mid A)
    = \frac{1}{1 + 2^{-n} (2^t - 1)}.
\end{equation*}

When $n < t$, meaning the key is underdetermined, this is about $2^n\!/2^t$.  For example, if you have a 100-byte text and a 256-bit key, $P(K \mid A) \approx 1/2^{156}$.  However, when $n > t$ so that $2^n \gg 2^t - 1$, this is about $1 - 2^{-n}$ and rapidly converges to 1 as $n$ increases and overdetermines the key with more bytes of plaintext that must match the pattern.


How important is the size of the public key (for a given security level)?

Larger public keys (in the same scheme) lead to

larger signatures
larger certificates
slower signature computation
much slower key generation

All of these might be a problem, especially for embedded devices, as you already mentioned.
As for your last question: Yes, there are a lot of protocols which transfer a public key, usually in the form of a (X.509) certificate. A TLS handshake is just the most prominent example.


Don't use ECB mode. ECB mode is fundamentally unsound except in very specific use-cases.
IVs have different requirements depending on the mode. In CBC mode, the requirement is "unpredictability", which is typically construed to mean "cryptographically random". CTR mode only requires that the IV be a nonce (e.g., is guaranteed to be unique).
A new IV must be used for each and every use of a key for an encryption operation.
IVs do not need to be kept secret. They are considered public information.
SHA-256(rand) is not a cryptographically strong random number generator. Hash functions evenly distribute existing entropy. If your underlying random source is predictable (e.g., has low entropy), hashing it does not improve that. Use a real CSPRNG.
In almost all contexts, you want to use authenticated encryption. GCM mode, EAX mode, and CCM mode satisfy this requirement. Non-authenticated encryption modes can allow attackers to modify ciphertexts in ways that have well-defined effects on the underlying plaintext.

If you want to generate hard-to-guess symmetric keys, just use a cryptographically-strong source of random numbers. If you need to establish these keys over an insecure channel, use something like the Diffie-Hellman key exchange.

You appear to be very new to cryptography. In general, I would strongly caution against working with ciphers at this low a level – the details are extremely important, and they are very difficult for amateurs to get right. The fact that you have already made multiple serious mistakes in fewer than 20 lines of code should give you an indication of just how difficult it actually is.

Unfortunately, I am not personally familiar with any higher-level abstractions for this sort of stuff for Common Lisp.


Why can ECDSA public keys be sent over an insecure network, while ECDSA is used to sign ECDH public keys to securely be transported over the network?

The attack that we're trying to prevent is a Man-in-the-Middle attack; this is one where an attacker (who is assumed to be able to modify messages) can step into a negotiation.  In effect, when Alice tries to negotiate with Bob, Mallet steps in, and so Alice actually negotiates with Mallet.  Mallet can then negotiate with Bob (posing as Alice), and then, forward any traffic he gets from Alice to Bob, and any traffic he gets from Bob to Alice.  As far as Alice and Bob are concerned, it looks like they have a secure connection (but Mallet can listen in to all their traffic, and also modify it at will).

To prevent this from being a possibility, Alice and Bob need to be able to do something that Mallet cannot.  There are a couple of possible ways, including:

Alice already knows Bob's public key, and Bob already has Alice's public key.
Alice and Bob both have a certificate from a trusted certificate authority.

There are other possibilities; hwoever these two are relevant to your question.

  However, most solutions seem to simply send the ECDSA public key over an insecure channel.

I would certainly hope not; as you can see, Mallet can generate his own ECDSA public key, and so this would do nothing to prevent a MITM attack.

What these solutions do is actually have Alice and Bob have certificates.  What a certificate is is essentially a message "Alice's public key is [this], signed Trent" (where Trent is the friendly neighborhood CA).  Trent gives Alice her certificate (based on Alice's public key) before negotiation ever happens, and Trent also gives Alice his public key.  During negotiation, Alice gives Bob her certificate; Bob can then verify that a) the identity listed in the certificate is the perform Bob thinks he's talking to, and b) it actually is signed by Trent.  If both are true, Bob then knows Alice's public key, and that can be used in the protocol.  Mallet cannot generate such a certificate; Trent won't give a certificate to Mallet that lists Alice as the owner; Mallet cannot reuse Alice's certificate (as he doesn't know Alice's private key); Mallet cannot generate his own certificate (as he doesn't know Trent's private key).

So, once Bob knows Alice's public key (and similarly, Alice knows Bob's), they can then use the each other's public key to authenticate the ECDH exchange, and all is well.

One other thing I want to bring up:

  In my implementation, I wanted to hardcode a static key pair into both sides

If you're not actually using a certificate authority, then you could have both sides generate a long term ECDH key pair, and just install Alice's public key on Bob, and Bob's public key on Alice.  This would also foil a MITM attack (as Mallet can't replace the public keys with his own).  There is an issue about updating the keys (we never want an immortal key; every key ought to have an expiry date), and there's no obvious way to update keys here.

Of course, if that's what you're doing, and you're happy with it, then it's not clear why you actually need to bring public key crypto onto the table.  If Alice and Bob both share a Message Authentication Code (MAC) key, then during negotation, Alice and Bob can exchange nonces, and then both compute $\text{MAC}_{key}( Nonce_{Alice} | Nonce_{Bob} )$; that's a shared secret that's a whole lot faster and easier than ECDH.

The other concern is a potential device compromise attack (which may or may not be relevant to you).  In this attack, we assume Mallet breaks into Alice, and learns all her secrets.  Now, going forward, Mallet can then pretend to be Alice (and there's nothing we can do about that).  However, with the ECDH preconfigured private keys (or the shared MAC key), what Mallet can do is go back and decrypt previously recorded communicates by Alice (because Mallet now keys Alice's private key).  In contrast, in an ECDSA/ECDH scenario (where Alice and Bob select the ECDH keys randomly each time), he cannot (assuming Alice zeroizes all her keying material when she's done with it).

Now, obviously, and ECDSA/ECDH protocol will be more complicated then one just using ECDH.  Is the extra complication warranted in your case?  That, you have to decide for yourself.


Consequences of AES without any one of its operations

As poncho notes in the comments above, viewing the input block as a 128-element vector over ${\rm GF}(2)$, the AES ShiftRows and MixColumns operations are both linear transformations, and AddRoundKey is just vector addition.

Both linear transformations and addition of a constant are kinds of affine transformations, and since the composition of any two affine transformations is itself an affine transformation, it follows that, if the non-affine SubBytes step is removed from AES, the whole cipher becomes affine.

In particular, every affine transformation can be represented in the form $c = Ap + k$, where $p$ is the plaintext input (a vector of 128 bits), $c$ is the corresponding ciphertext output, $k$ is a constant vector and $A$ is a 128 × 128 bit matrix.  Furthermore, the inverse of this transformation is then simply $p = A^{-1}(c - k)$, where $A^{-1}$ is the matrix inverse of $A$, and (for vectors over ${\rm GF}(2)$) both vector addition "$+$" and subtraction "$-$" simply mean bitwise XOR.

The constant $k$ obviously depends on the key, but the matrix $A$ actually does not — it is fully determined by the ShiftRows and MixColumns steps, neither of which are key-dependent.  Thus, you can precalculate it e.g. by implementing this affine AES variant yourself, leaving out the AddRoundKey step as well to make it linear, and using this to encrypt (or decrypt) all the 128 blocks with a single bit set to one and all other bits zero, which will directly give you the columns of $A$ (or of its inverse $A^{-1}$).

Once you've precalculated $A$, even just a single known plaintext/ciphertext block pair $(p,c)$ encrypted using the actual affine cipher will let you determine the key-dependent the additive constant $k = c - Ap$.  Knowing $A$ and $k$ will then let you encrypt (or decrypt, using $A^{-1}$) any arbitrary plaintext (or ciphertext) block.


Is forward secrecy overhyped or necessary?

Since I am at the source of the original quote, I might as well respond...

Technically, forward secrecy is overhyped because it is recommended almost everywhere. In some contexts it makes sense and is a valuable property. In many other contexts it makes less sense and, while harmless from a security point of view, it may induce performance-related issues.

Suppose that you have two systems that want to exchange confidential data over an insecure network. This is the context of the TLS protocol. At some point, the data is encrypted with a secret key derived from the key exchange protocol used in the TLS handshake. Forward secrecy is a property that says, basically, that once the exchange is over, the involved parties do not keep around all the secret information that allows decryption: the data has been encrypted on the sender side, and decrypted by the recipient, and nobody (except the attacker, of course!) needs to decrypt it again, so the encryption key can be dropped. If the TLS client and server use the RSA key exchange, then the protocol is not forward secure, because the RSA decryption key is the server's long-term key, the one corresponding to the public key in its certificate, and these will live for as long as the certificate itself, usually months or years.

In that kind of situation, a non-forward secure key exchange can be exploited by an attacker if that attacker records the encrypted session, then later on manages to compromise the server to obtain the decryption key. This assumes that the attacker can somehow predict that he will be able to compromise the server at a later date, making it worthwhile to record encrypted sessions. This is not plausible in many situations involving for instance Web browsers talking to Web servers: the attacker simply does not know when or if he will get access to the server, and if the goal is to obtain (for instance) credit card numbers, the attacker won't bother to record previous sessions; he will simply plunder the server-side database, to which he will have good access once the server itself is compromised.

Notwithstanding, there are real-life contexts where forward secrecy is very useful; one of them is typically end-to-end encrypted messaging systems. A number of characteristics make forward secrecy highly desirable for such systems:

The total amount of encrypted data is much smaller than typical Web-browsing sessions (let's face it, today's Web is fat). Moreover, in some messaging systems, encrypted messages are already recording by servers that manage the transport, for asynchronous delivery.
Past conversations are interesting to attackers, and not necessarily made available to them by virtue of compromising one device (it depends on the system's strategy with regards to caching).
Group conversations imply group management, and, in particular, ability to exclude a former group member from subsequent discussions; this inherently calls for some sort of forward secrecy ("ratcheting", in modern parlance).

My point, though, is that the blanket recommendation for forward secrecy everywhere is "a bit overhyped", because it is, indeed, a blanket, universal recommendation, marketed as an unavoidable requirement in all cases, while many situations don't need it.

On the negative side, here is a performance issue that arises from the universal forward secrecy requirement. In TLS 1.3, forward secrecy is systematically enforced. Suppose that some small embedded device must talk to a server with mutual, certificate-based authentication. Suppose also that elliptic curve cryptography is used. The following will happen:

The client generates a new ECDH key pair, i.e. a random integer a, and the curve point aG (for the conventional generator G).
The server also generates a new ECDH key pair (b, bG).
The server signs its public part bG; the signature will use ECDSA or EdDSA, and involves computing a multiplication of the generator G with a new scalar.
The client verifies the signature. This requires performing two point multiplications, one of these points being the generator G, the other one being the server's public key. There are tricks to somehow mutualize some operations in these two point multiplications, but they need extra RAM, always a scarce resource in embedded systems.
The client terminates the ECDH key exchange by multiplying the received bG with a.
The server also terminates the ECDH key exchange by multiplying the received aG with b.
The client must itself compute a signature with its own long-term key, so that the server knows that it talks to the right client.

In total, the client will need to compute five point multiplications, three of which being on the conventional generator G (since that generator is known in advance, this allows some optimizations, so multiplications of G are a bit less expensive than multiplications by a freshly received point). The cost on the server is similar.

Now, compare that with TLS 1.2. With TLS 1.2, all of the above can be done in about the same way (encoding of messages differs, but the cryptographic result will be the same); this would use an "ECDHE_ECDSA" cipher suite (ECDHE key exchange, signed by the server with its ECDSA private key). However, TLS 1.2 also offers "ECDH_ECDSA" cipher suites, without the final "E" of ECDHE (the one that means "ephemeral"). In the ideal case, what happens is the following:

The server has a long-term EC key pair (b, bG). The public part (bG) is in its certificate, i.e. has been computed at key generation time.
The client also has a long-term EC key pair (a, aG), with aG encoded in its certificate, again a key generation time.
The client and the server send to each other their certificates.
The client computes a(bG) as the premaster secret for the TLS connection (the actual encryption keys will be derived from the premaster secret with some HMAC-based function that also includes the random values exchanged during the handshake).
The server computes b(aG) as the premaster secret for the TLS connection.

And that's it. The client and server now have to compute a single point multiplication each. This is called the "static-static Diffie-Hellman".

The static-static Diffie-Hellman key exchange is not allowed in TLS 1.3, because it is not forward secure. Modern implementations of elliptic curve cryptography are fast, and any decent server can certainly compute five point multiplications for each client without breaking a sweat; a decent x86 CPU can do 30000 point multiplications per second with a single core! However, on the client side, things may differ: a very small embedded system, e.g. an ARM Cortex M0+ clocked at 5 MHz or less (to save power), would need close to one second for each point multiplication. For such a client, a multiplication of the cost by five is certainly not negligible, and can be the difference between "a non-forward secure connection" and "no encryption at all because the forward-secure exchange is too expensive". Regardless of how much indispensable you think forward security is, lack of encryption is certainly not an improvement over non-forward-secure encryption.

In that sense, TLS 1.3 is more hostile to small embedded systems than TLS 1.2, and this is for the sake of mandatory forward security, even in cases where it does not bring any actual advantage. This is what I call "a bit overhyped".


Let $G$ be the public key matrix. With Gaussian elimination, you can find a Matrix $G'$ with $G = (E_k | G')$, where $E_k$ is the identity matrix with dimension $k$. Then, you only have to store $G'$. And $G'$ has the dimension $(n-k) \times k$.

Source: German Wikipedia (https://de.wikipedia.org/wiki/McEliece-Kryptosystem)


If you take an Sbox and two different inputs $x_1,x_2$ (binary vectors of length 6) the exclusive or ("sum") of the two inputs is does not propagate to the output. So
$$S(x_1)\oplus S(x_2) \neq S(x_1\oplus x_2)$$
in general. This means that there is no shortcut allowing one to predict outputs "bit by bit" and build efficient search tables, by just considering the list of outputs

$S(100000),S(010000),S(001000),S(000100),S(000010),S(000001)$$

and obtaining

$$S(a_1~a_2~a_3~a_4~a_5~a_6)=a_1 S(100000)+a_2 S(010000)+\cdots+a_6 S(000001).$$

by linearity. This would lead to very efficient attacks when applied to all 8 Sboxes.


Unique decoding Radius in Reed Solomon Codes

Let the linear block code $C$ with the minimum distance of $d_{min}$ which this amount is either odd or even so for each integer $t$ we can define the below inequality:
\begin{equation}
2t+1 \leq d_{min} \leq 2t+2
\end{equation}
Suppose $W$ is all code-words in code $C$ except $V$ which is the original code-word along with the channel and $r$ is the received code-word. Therefore, the below inequality according to one of the famous Lemma is satisfied.
\begin{equation}
d(V,r)+d(r,W) \geq d(V,W)
\end{equation}
Since $V$, $W$ $\in$ $C$,
\begin{equation}
d(V,W) \geq d_{min} \geq 2t+1
\end{equation}
Now, suppose the number of error between $V$ and $r$ is $l$ i.e. $d(V,r)=l$.
So
\begin{equation}
d(r,w) \geq 2t+1-l
\end{equation}
If $l$ $\leq$ $t$ then
\begin{equation}
d(r,w) \geq t
\end{equation}

In other words, if the number of errors between the transmitted and the received code-words be less than $t$ so the code-word $V$ is the closest code-word to $r$ than all other code-words in code $C$. i.e.
\begin{equation}
d(V,r) < \frac{d_{min}-1}{2}
\end{equation}

We can generalize this bound for all linear block codes such as Reed Solomon codes. The $d_{min}$ for RS codes is $n-k+1$ so we can conclude:
\begin{equation}
d(V,r) < \frac{n-k+1-1}{2}=n\frac{1-\frac{k}{n}}{2}
\end{equation}
So
\begin{equation}
\delta < \frac{1-\rho}{2}
\end{equation}

It is exactly the bound for the RS codes to obtain uniquely the original code-word.


You can think of crypto_box_curve25519xsalsa20poly1305 as some composition of X25519, a key agreement scheme; XSalsa20, a symmetric-key stream cipher; and Poly1305, a one-time polynomial evaluation message authentication code.  But that's not the best way to think about it when you're engineering something out of it—partly because there are many ways you could compose those, but mainly because it doesn't help you to figure out how it fits into your application.

Instead, you should think of it as a contract, with obligations on your part and security services on the part of crypto_box_curve25519xsalsa20poly1305:

Your obligations to crypto_box_curve25519xsalsa20poly1305.

(a) You must generate a secret key uniformly at random.

(b) You must choose a distinct nonce for every public key and message you use that secret key with.  You may generate them uniformly at random if you like.
Security provided by crypto_box_curve25519xsalsa20poly1305, even in the face of an adversary who can intercept every box on the wire and persuade the legitimate users to create boxes for arbitrary messages of their choice adaptively.

(a) Anyone who does not know one of the two secrets keys for a sender and receiver cannot open boxes whose contents did not already know.

(b) Anyone who does not know one of the two secret keys for a sender and receiver cannot forge a box not created by the sender or receiver.

crypto_box_curve25519xsalsa20poly1305 does not provide third-party verifiability, also known in some circles as nonrepudiation: if Alice sends a box to Bob, Bob can't cryptographically persuade Charlie that Alice sent him that message without also demonstrating to Charlie the ability to forge Alice$\rightarrow$Bob messages.

This is spelled out in slightly more academic detail in the NaCl crypto_box documentation under ‘Security model’.

Attack costs.
crypto_box_curve25519xsalsa20poly1305 is designed to target a ‘128-bit security level’, which means that the area*time cost—area on a silicon die times amount of time you spend powering it—of the best known attacks is around that of $2^{128}$ bit operations, which is more than we can imagine anyone ever carrying out.

The secret keys of crypto_box_curve25519xsalsa20poly1305 are indeed 256 bits long, but there is enough mathematical structure in X25519 to admit an attack cheaper than simply enumerating and trying all possible secret keys—so much cheaper that the best you can hope to get for an elliptic curve over a field of 256 bits is a 128-bit security level.  You can find highly technical references about these attacks at SafeCurves under ‘ECDLP security’.

The secret keys of crypto_secretbox_xsalsa20poly1305, an operation out of which crypto_box_curve25519xsalsa20poly1305 is built, are also 256 bits long, but the nature of the kind of object that a secretbox is allows multi-target attacks, where the best known area*time cost of breaking at least one of a set of $n$ target $k$-bit keys with nonnegligible probability is significantly less than $2^k$.  Using a 256-bit key for crypto_secretbox guarantees that even for an unimaginably large set of $2^{128}$ targets, the best known area*time cost of breaking at least one of those targets with nonnegligible probability still exceeds that of $2^{128}$ bit operations.


Does Hinek and Lam's Paper prove that Common Modulus Attacks is possible with non-coprime public exponents?

The first common modulus attack is described by G. J. Simmons

1983 A ‘weak’ privacy protocol using the RSA crypto algorithm

and if there is a common modulus and the public exponents are relatively prime (i.e. $\gcd(e_1,e_2)=1$) then recovering the message is easy ( no factoring).
As pointed in section 5 of your linked article;

Howgrave-Graham and Seifert’s small private exponent attack on common modulus RSA [1] improves upon Guo’s attack in several ways. In particular, the attack can be mounted with only two instances of RSA (although it gets stronger with more), the problems associated with relatively prime quantities are not a concern and, most importantly, the attack (even with only two instances) is much stronger.

So your understanding is correct.


Do I need to provide entropy to secp256k1_ecdsa_sign() ?

Question1: Where is randomness coming from? The default secp256k1_nonce_function, when i pass in NULL is nonce_function_rfc6979.

Obviously, there is no randomness involved when RFC 6979 is used. The title of that RFC is "Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)". In this case identical messages will generate the same signature value.

As the RFC reads: "Even slight biases in that process may be turned into attacks on the signature schemes." So the deterministic signature scheme makes sure that the replacement of the random value doesn't have any bias. Fortunately, this is exactly what a pseudo-random-generator (PRG) is able to generate when the hash over the message is used as key. In the RFC a HMAC algorithm is used as PRG. So the true random value is replaced by a pseudo random value that depends on the message.

  Question2: Did I do something wrong? Can my private-keys be derived from my signed messages?

No, as long as the security considerations in section 4 of the RFC holds you should be fine.

Notes:

Generating the same signature value for message input is not necessarily a problem and it is not a generic requirement for signature schemes. For instance, the PKCS#1 v1.5 signature scheme is fully deterministic. However, for ECDSA, it is possible to calculate the private key value using simple mathematical equations if no (pseudo-)random value is present.
You should consider if deterministic signature generation is OK for your specific protocol. For instance, if sign-and-encrypt is used then a deterministic signature may give information about the plaintext message, breaking the confidentiality requirement (although if the signature is verifiable, this is already  the case if the signature and public key is available to an adversary).
Other API's may choose to use some kind of default secure random generator instead of deterministic signature generation. For instance, Java will use the highest priority secure random generator if no specific random generator is explicitly indicated during initialization of signature generation algorithm;


Combining cascaded encryption keys into one key

For a crypto algorithm that acts like a group, the first thing that comes to mind is Pohlig-Hellman.  In this method, we have a large prime $p$, and define:

$$E_A(Data) = Data^A \bmod p$$

(with $A$ relatively prime to $p-1$)

This has the property that $E_B(E_A(Data)) = E_{A \times B \bmod p-1}(Data)$; however it has the security properties you're looking for; for example, given lots of $X, E_A(X)$ pairs, you can't recover $A$.

Now, this is a symmetric system (given $A$ and $E_A(Data)$, you can recover $Data$).  If you insist on an asymmetrical system, you might want to do this modulo a composite of secret factorization; only some who knows the factorization can then decrypt.  That version might be somewhat related to a better known asymmetric scheme...


What is CCM -- Counter Mode Cipher Block Chaining Message Authentication Code Protocol

CCM puts together two different modes of operation (at least in the
  name). Does it mean data is encrypted using counter mode and then
  encrypted using CBC; kind of a double encryption?

Yes, kinda.
With the CCM mode of operation, you authenticate your data first using CBC-MAC which is, well, basically CBC on the data to be authenticated.

Now on the combination of ciphertext and tag you apply the CTR mode to conceal the contents. While you do "double-encryption" here, you only send the full result of the CTR mode and only the very last block from the CBC mode (encrypted using CTR). The latter one is the tag with which the recipient can verify the integrity of the message.


Is matrix elliptic curve discrete logarithm problem quantum-safe?

Reasoned it through just now. Given the ultimate generator of the elliptic curve group $G'$

Shor $G$ element-wise to obtain an MI $H$ such that $G=H * (G')$, where $*$ is element-wise multiplication.

Shor $P$ element-wise against $(G')$ to obtain an MI $J$

Calculate $J\over H$ using Gaussian elimination to obtain $v$

Yeah! I defeated myself in a cryptanalysis challenge.


Some information about zero knowledge proofs

This depends a bit on your background and what you are interested in. Philosophically speaking, zero-knowledge proofs are easy to understand (correctness, soundness and zero-knowledge), while the technical details often can be very complex. See https://en.wikipedia.org/wiki/Zero-knowledge_proof for a nice intro and non-cryptographic examples.
I think the ZKProof Community Reference (https://docs.zkproof.org/reference.pdf) gives a good intro to zero-knowledge proofs, but maybe the best (cryptographic) example is Schnorr signatures, which you can think of as a zero-knowledge proof of knowledge of the secret key corresponding to the public signing key (see e.g. https://datatracker.ietf.org/doc/html/rfc8235 or https://web.stanford.edu/class/cs259c/lectures/schnorr.pdf). This is a fundamental protocol, and many other zero-knowledge protocols (often called Sigma-protocols, see https://docs.zkproof.org/pages/standards/accepted-workshop4/proposal-sigma.pdf or https://www.cs.au.dk/~ivan/Sigma.pdf) builds upon the same structure. Finally, I can recommend this talk by Dan Boneh: https://www.youtube.com/watch?v=wB3DlND7KEw.


Is RSA provably secure in the sense of Douglas Stinson's ``provable security''?

Every cryptosystem is "provably secure" under at least one hardness assumption: the assumption that it cannot be broken. Hence, the only question which matters is whether a cryptosystem is provably secure under a well-known and well-studied assumption.

This is kind of the case for RSA, but in a somewhat unsatisfying way: the IND-CPA security of RSA with appropriate padding can be reduced to the RSA problem (extracting $e$-th roots mod $n$), which is a well-studied assumption... But only because this is the one underlying the RSA cryptosystem, and we have been using the cryptosystem a lot in the past decades.

Something much more satisfying would be to reduce it to a problem which had long been studied before, in different context; the most natural such candidate is indeed factoring. Unfortunately, we do not know of a reduction from RSA to the hardness of factoring integers - in fact, we even have proofs that it will be hard to find such a reduction (in a well defined sense).

We have, however, many other cryptosystems which can be reduced to factoring; the earliest example of this kind is the cryptosystem of Rabin.


How does recovering the public key from an ECDSA signature work?

Actually, it is not possible to uniquely recover the public key from an ECDSA signature $(r,s)$.  This remains true even if we also assume you know the curve, the hash function used, and you also have the message that was signed.

However, with the signature and the message that was signed, and the knowledge of the curve, it is possible to generate two public keys; one of which will be the public key corresponding to the private key used.

Here's how that works:

First, you find the two points $R$, $R'$ which have the value $r$ as the x-coordinate $r$.
You also compute $r^{-1}$, which is the multiplicative inverse of the value $r$ from the signature (modulo the order of the generator of the curve).
Then, you compute $z$ which is the lowest $n$ bits of the hash of the message (where $n$ is the bit size of the curve).

Then, the two public keys are $r^{-1}(sR - zG)$ and $r^{-1}(sR' - zG)$

It is easy to verify that if you plug either of these values in the ECDSA signature routines as the public keys, the signature validates.


Cryptographic hash with ability to ignore specific bits based on a hidden pattern?

Suppose you had such a hash. Then anyone who knew some value for which the condition matched could find out the full pattern/mask:

You know some environment for which mask(hash( environment ), encryptedPattern ) == encryptedCondition.
You can flip one bit at a time, compute the masked hash, and see if you still get a match. If you do, that bit was masked out in the (unencrypted) mask pattern.

So possibly what you want is impossible. However, if you only need the pattern to remain hidden from those who do not know any matches, it may be possible using homomorphic encryption.

Take a suitable homomorphic encryption system that allows computing ANDs and verifying the results*. Encrypt the mask m = E(pattern) and the condition c = E(requirement).
The user encrypts a value E(environment), ANDs with the mask and compares to the condition: E(environment) & m == c.

* The system must be deterministic and have E(x) & E(y) = E(x&y).

(Note: the use of deterministic encryption means that a user can guess and test values against pattern and requirement. This is quite weak, but conceivably there could be applications.)


By definition you cannot encrypt values greater than the modulus in RSA, because the plaintext is immediately reduced modulo $n$ which loses information. This is because textbook RSA works in the $\mathbb{Z}/n\mathbb{Z}$ congruence ring, so from RSA's point of view, as long as two values have the same remainder modulo $n$, they are effectively equivalent. So with your $n = 77$ example, RSA will not distinguish plaintexts of $10$ and $87$ since they both leave a remainder of $10$ when divided by $77$, i.e. they are equal in $\mathbb{Z}/n\mathbb{Z}$. They will produce the same ciphertext, and hence decrypt to the same value ($10$).

Put differently, RSA does not care what your plaintext is, all it cares about is its remainder when divided by your modulus. Anything else is irrelevant, all that matters is the remainder (hence everything being done modulo $n$).

You will notice "z" (90) decrypts to 13 which just so happens to be the remainder of 90 when divided by 77, as $90 = 1 \times 77 + 13$. Similarly, "h" (104) decrypts to 27, and sure enough, $104 = 1 \times 77 + 27$. And again, "u" (107) decrypts to 30... you guessed it, $107 = 1 \times 77 + 30$. Coincidence? Not at all, it is a direct consequence of the first paragraph.

Another way to think of it is that since RSA can only output values between $0$ and $n - 1$ (because the ciphertext is taken modulo $n$), then there can only be $n$ possible plaintext inputs (pigeonhole principle). It then becomes clear encrypting values above $n - 1$ is not useful.

You'll need to use a bigger modulus, or work with a different charset e.g. a = 0, b = 1, etc... instead of using the ASCII one, since in ASCII most small values are unfortunately taken up by control characters. If you want all basic characters to work properly, try this keypair:

$\left ( ~ p = 13, ~ q = 29, ~ n = 377, ~ e = 17, ~ d = 257 ~ \right )$

This should work - but do remember this is only for learning purposes.

Fun fact: this small RSA keypair is very interesting in that its encryption and decryption exponents are both prime fermat numbers, this is amazingly rare and quite surprising. Just thought I'd mention it.


How did LinkedIn "salt" all their passwords?

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

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

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


No.  Entropy does not depend upon time.  Entropy is a purely mathematical, probability-based concept.

The entropy of a distribution is some particular function of the distribution.  The entropy of a random variable is the entropy of its distribution.  Formally speaking, it does not make sense to speak of the entropy of a particular value; but we can talk about the entropy of a random process.  For example: suppose I roll a fair 6-sided die, and get 3.  It doesn't make sense to talk about the entropy of the number 3, but I can ask what is the entropy of this random process (the process of rolling a fair 6-sided die to get a random number from 1 to 6) -- it has $\lg 6$ bits of entropy, in particular.  The entropy of a process is the entropy of the distribution on the possible outputs from that process.

Notice how nothing here changes with time.  If I roll a fair 6-sided die today, the entropy of the result is $\lg 6$ bits.  If I roll it tomorrow, the entropy of that will also be $\lg 6$ bits.  If I roll a fair 6-sided die today, write down the answer, and then a decade from now look at what I wrote down and ask about its entropy, the answer will still be $\lg 6$ bits.  The entropy of this random process remains $\lg 6$ bits no matter how long we wait, because its entropy depends upon the distribution of possible outputs from the random process, and that distribution is whatever it is -- it does not depend upon time.

Now in some cases it might be true that, if you use a random secret key, then the longer you use the same key, the greater the chances that an attacker can recover the key.  That might be true.  But it has nothing to do with entropy.  The entropy doesn't change or degrade with time; the entropy of that key is what it is.  All that changes is, the longer you use the key, the more chances the attacker has to try to break it.  For the same amount of entropy, the more times the attacker can try to break it, the better the attacker's odds will be.  So that's one sense in which the attacker's success probability (or the security of the system) might depend upon how long the system is used for -- even though the entropy of the crypto key does not depend upon that.


Message space when using the group of QR's for El Gamal Encryption

If this is true, how would one solve this in practice?

Actually, in practice, what we generally do is not use El Gamal at all, but instead use Integrated Encryption Scheme (IES), which solves the same problem based on the same hard problem, but where one doesn't worry about Quadratic Residues (or the homomorphic properties, or the need to compute inverses, which is doable but annoying).

Now, if we have to use El Gamal (e.g. because we need to take advantage of the homomorphic properties), well, one way to avoid the QR problem is to simply square the plaintext before encryption (and hence the plaintext that we encrypt is always a QR).  Then, on decryption, we would compute the square root (and take the smaller of the two possible values).  This implies that the plaintext is limited to the range $(0, (p-1)/2)$, but any value in that range can be encrypted.


Is it possible to derive a constant value from different signatures of a private key?

I understand the question to mean: is there a function $F$ whose domain is signatures under a public-key signature scheme such that, given a signature $s_1$ made with a key $k_1$ and a signature $s_2$ made with a key $k_2$, $F(s_1) = f(s_2)$ if and only if $k_1 = k_2$? Or in simple terms: can you tell who made a signature by looking at it?
You aren't going to find a generic proof of impossibility because it is possible to build signature schemes for which $F$ exists. In fact, any signature scheme can be adjusted to make $F$ possible. Given a signature scheme whose signature function is $S$, define a new scheme whose signature function is $S'(k_{\mathrm{priv}}, x) = (S'(k_{\mathsf{priv}}, x), k_{\mathsf{pub}})$ where $k_{\mathsf{pub}}$ is the public key associated with $k_{\mathsf{priv}}$. In simple terms: attach the public key to the signature. This new scheme is just as secure as the original since the new signature function doesn't reveal any more information than the original and doesn't have equality cases that the original doesn't have.
For ECDSA, given a curve with the generator $G$, its order $n$, and two key pairs on this curve $(d_1, Q_1)$ and $(d_2, Q_2)$, here's a way to construct signatures that are valid with both keys. Note that they are signatures of different messages. Given a nonce $k$ and a message $m_1$, the signature under the first key is $(r, s)$ where $r$ is the x-coordinate of $k G$ modulo $n$ and $s = k^{-1} (H(m_1) + r d_1)$. Let $e_2 = k s - r d_2$. If there exists $m_2$ such that $H(m_2) = e_2$ then $(r,s)$ is the signature of $m_2$ under the second key. Hash functions are not necessarily surjective, so $m_2$ might not exist, but if $H$ is sufficiently indistinguishable from a random oracle, the proportion of values of $k$ such that $m_2$ exists is the size of the image of $H$ among bit-strings of the appropriate length, so many values of $k$ are suitable.
Note that this is a (sketch of a) proof of existence. Finding actual examples (at least with this method) is infeasible since it requires calculating a pre-image under the hash function.
I haven't worked out the math for RSA. I think that due to the longer signatures, it is not the case in general that given two key pairs, there exists a pair of messages such that the signature of the first message with the first key is equal to the signature of the second message with the second key. I expect that this is true with high probability when the hash is sufficiently longer than half the key and false with high probability when the hash is sufficiently smaller than half the key.
Note that if you require the signatures to be of the same message, the answer is completely different. With a known message, ECDSA allows key recovery. This is not true for RSA.
A more interesting version of this question in practice is, given a signature, or more generally a set of signatures made with the same key, and a collection of public keys, is it possible to tell with a non-negligible probability which key made this or these signature? This is the problem of key privacy for signature. RSA does not have key privacy. Ed25519 looks like it might have key privacy.


Why is it that researchers prefer finding secure software solutions over secure hardware solutions?

I think this question is setting up a false dichotomy.

It's not that a researcher has an opinion as to whether they prefer software or hardware implementations. The choice of implementation depends on the requirements of the specific cryptosystem you're building.

For example, if you're designing a system to encrypt voice traffic on a mobile phone network, then clearly that's going to favour hardware based solutions.

Alternatively, if you're building an open-source program that handles file-encryption, this is going to strongly favour a software based solution.

Some requirements drive hybrid solutions. Two factor authentication systems such as Yubikey or RSA's Securid use a blend of hardware and software.

It's worth pointing out that all software requires hardware at some level. At what point does the software solution become a hybrid solution?

These days, the lines are becoming more blurred. Modern processors now contain hardware RNGs and instructions that implement the core operations in AES.

So even applications that appear on the surface to be composed entirely of software could utilise these instructions if they were available.

To summarise, I think the distinction between drawn in the question is false and that all cryptography uses a blend of hardware and software. The precise blend is controlled by the requirements of the system. Over time, more of the crypto is finding its way in to hardware due to better standardisation.


Are there any downsides to key stretching an already high quality entropic key?

Even with perfectly random input, if your final key size is 32 bytes, you cannot have more than 32 bytes of entropy in it.

But it seems pretty useless to use key stretching if you already have more random bytes than your key length, you could just use 32 bytes of your 'perfect' source as an AES key. You just expose yourself to possible weakness in the key stretching algorithm without any benefit.


What math should I learn to get in depth with Elliptic Curve Cryptography research?

An Introduction to the Theory of Elliptic Curves (Brown University)

Elliptic Curve Cryptography (Wikipedia)

Performance analysis of identity management in the Session Initiation Protocol (SIP) (IEEE)

Overview of Elliptic Curve Cryptosystems. (RSA.com)

Lecture by Dan Boneh (Youtube)


Given plain text of given cipher text, can AES key be uncovered?

It is not possible to find an AES key from a known plaintext / ciphertext pair. If that was the case then AES would either have to be:

vulnerable with regard to the key size or;
vulnerable against attacks that invalidate the cipher.

AES has a security close to the key size (of 128 bits, in your question). Brute force or more intricate attacks against the key itself are therefore infeasible.

And, as indicated by the text above, the cipher has certainly not been broken in a sense that you can (easily) recalculate the key. Allowing an attacker to find the full key is as broken as a cipher can get; in general it is assumed that an attacker knows parts of the plaintext.

The mode of operation and IV are inconsequential to the security of the key as the key is only used as input of the block cipher - both in CBC and GCM mode. The key is therefore protected by the block cipher itself.


How is the AddRoundKey operation performed in AES-256?

how do you add an 256 bit round key?

Actually, each round key is 128 bits, and so XORing them into the state matrix is easy.

What the AES key expansion process does is take the 256 bit AES key, and generate 15 round keys (one more than the number of AES rounds).  Now, for AES256, the first two round keys are, in fact, 256 bits taken directly from the AES key.  After that, it computed the next round key based on a simple function of the previous two round keys (plus a per round constant).


If you consider symmetric encryption schemes instead of just stream ciphers, you're looking for "key-homomorphic encryption". There has been some work on lattice-based fully key homomorphic encryption schemes (see here).


Does SipHash have 64 bit (second) preimage security?

SipHash is a MAC (aka Pseudo Random Function Family) with 64-bit output and 128-bit key, rather than a hash (aka random public member of a Pseudo Random Function Family). It is explicitly designed to be used with a secret random key. Quoting Jean-Philippe Aumasson and Daniel J. Bernstein's SipHash: a fast short-input PRF (in proceedings of Indocrypt 2012):

  the standard PRF and MAC security goals allow the attacker access to the output of SipHash on messages chosen adaptively by the attacker. However, they do not allow access to any "leaked" information such as bits of the key or the internal state. They also do not allow "related keys", "known keys", "chosen keys", etc.

Thus you are without endorsement of the creators if using SipHash as a hash function and expecting 64-bit second preimage resistance when the key has gone public (as you would legitimately for a 64-bit hash function).

This does not answer the question of if preimage resistance of that SipHash-turned-hash can be broken much better than by brute force (expected $2^{64}$ evaluations of SipHash, which is not much); I simply do not know, and find it nontrivial to make an opinion other than: uncertain.


Would data be secure if a cryptographically secure PRNG was used for encryption?

A PRNG with a seed $S$ whose output is combined with the plaintext is called a stream cipher with the key $S$. So assuming that the details are filled in correctly, what you're describing is a stream cipher algorithm with two session keys, one used in each direction. Each seed/key must be unique, and the combination must ensure that each output bit has a $1/2$ probability of being flipped (xor is common, but addition of bytes would work too).

If you have an encrypted communication channel, then it's already using a stream cipher, which may be built on AES. (Note that AES is not a stream cipher — it's a family (128, 192, 256) of pairs (encrypt, decrypt) of algorithms that operate on blocks of exactly 128 bits. There are ciphers built on top of AES with a mode of operation, which result in a block cipher or stream cipher.) For example, AES-CTR is a popular stream cipher. AES-CTR is also a popular PRNG, for exactly the same reason.

Combining your scheme with another cipher would mean, in fact, chaining two ciphers. This is hardly ever useful, but is at least as strong as the weakest cipher if the ciphers are not correlated. (Possibly not as strong as the strongest cipher, because the weakest cipher may leak information.) Correlation can lead to catastrophic failures — for example, if you encrypt twice with the same stream cipher with the same key, you get the original stream.

A stream cipher only ensures confidentiality, not integrity or authenticity. For example, AES-CTR is trivial to modify: flipping a bit of ciphertext results in the same flipped bit in the plaintext (this applies to any stream cipher that uses xor as the combination function). HMAC or some other form of MAC can ensure integrity and authenticity. Alternatively, you may use a mode of operation that performs authenticated encryption, such as CCM or EAX which are CTR combined with CBC-MAC or CMAC.

Further reading: Is modern encryption needlessly complicated?

 I'm only rehashing what's been said in comments really, just so that this question is answered.


Are there asymmetric cryptographic algorithms that are not based on integer factorization and discrete logarithm?

Yes there are other hard problems you can base asymmetric cryptography on.

Lattices. The NTRU systems is based on the shortest vector problem in ideal lattices. Lattice-based cryptography is of much interest these days for two reasons: (1) unlike factorization and discrete logarithms, there isn't an efficient algorithm for breaking these problems on a (still theoretic but should happen within our lifetime) quantum computer; (2) you can use lattice-based systems to do arbitrary operations on data while it is still encrypted (not with NTRU though but other lattice-based systems).

Coding Theory. The McEliece system is based on decoding linear codes. It is a very old system but recently has seen renewed interest for the same post-quantum reasons as lattice-systems.

Misc. There are other more obscure (research-level) cryptosystems based on things like learning parity with noise, learning with error (related to SVP in lattices), subset sum problem (including a famous broken example), solving multivariate or diophantine equations, etc.

In response to your second question, is it that hard to find alternatives, the answer is it is reasonably hard. For most cryptographic primitives, you need to find examples of functions that are hard to invert, and for asymmetric encryption specifically, you are generally interested in functions that have a specific value that allow them to be inverted (but only if you know that value). See trapdoor functions. It is difficult to find new candidates for trapdoor functions and to establish they are suitably hard.


Is there only one formula for the statistical difference between a pair of distribution ensembles?

What we call "statistical distance" in cryptography is called total variation distance by statisticians. So it certainly exists outside of cryptography.

I can't speak to its applications within statistics. But it certainly is the most natural metric for cryptography because it has an equivalent formulation in terms of distinguishing two source distributions given a sample, which is how we state many security properties. Restricting the distinguisher to be polynomial-time leads to natural and useful generalizations.


$\pi$ is the transcendental number 3.1415926...

It's there in the formula to show this specific number was not chosen with a specific cryptographical backdoor in mind; it seems unlikely that anyone was able to select the value of $\pi$ (unless Carl Sagan was correct, of course :-)


Interleaving bytes to make an effectively larger block size

Alternative 1, Interleave = ShiftRows

Use a KDF for extending and splitting the input key into three keys $K_1, K_2, K_3$.
Split the input into $A_0 = a_0..a_{15}, A_1 = a_{16}..a_{31},...,A_{16} = a_{240}..a_{255}$
AES-ECB encrypt using key $K_0$ so that $E_{K_0}(A_i) = B_i = b_{16i+0}..b_{16i+15}$
Interleave so that $c_{16i+j} = b_{16(i+j)+j \bmod 256}$

The problem here is that if $A_i = A_j$ for all $0 \le i, j \lt 16$, then $C_i = C_j$ for all $0 \le i, j \lt 16$. This equality will propagate through all three rounds, making it easy to distinguish your 2048-bit composite function from a random 2048-bit permutation with only a single query.

Clearly, if $A_i = A_j$, then $E_{K_0}(A_i) = E_{K_0}(A_j) = B_i = B_j$. This means that $b_{16i+k} = b_{16j+k}$ for all $0 \le k \lt 16$. If this relation holds for all $0 \le i, j \lt 16$ then, for each $0 \le k \lt 16$, $b_{16i + k} = b_{16j + k}$ for all $0 \le i,j \lt 16$.

In particular, $b_{16i+j} = b_{16(i+j)+j \bmod 256}$.

In other words, if $A_i = A_j$ for all $0 \le i, j \lt 16$, then the interleave step will be the identity function. The composite function will for such inputs only consist of three consecutive AES-ECB operations.

Alternative 2, Interleave = Transpose

Use a KDF for extending and splitting the input key into three keys $K_1, K_2, K_3$.
Split the input into $A_0 = a_0..a_{15}, A_1 = a_{16}..a_{31},...,A_{16} = a_{240}..a_{255}$
Round = 0
AES-ECB encrypt using key $K_0$ so that $E_{K_0}(A_i) = B_i = b_{16i+0}..b_{16i+15}$
If round = 2, exit
Interleave so that $c_{16i+j} = b_{16j+i}$
round = round + 1, $A = C$ jump to step 4.

In this case, if $A_i = A_j$ for all $0 \le i,j \lt 16$, then, in the first round = 0, $c_{16i+j} = c_{16i + k}$ for all $0 \le i,j,k \lt 16$. This means that after the second round = 1, there are only $2^8$ different values for the $B_i$ blocks.

Hence, find two 128 bit values $A$ and $A'$ such that $E_{K_0}(A) = b_0..b_{15}$ and $E_{K_0}(A') = b'_0..b'_{15}$ differ only in a single byte $b_i \neq b'_i$, and such that $E_{K_1}(b_i..b_i) = c_0..c_{15}$ and $E_{K_1}(b'_i..b'_i) = c'_0..c'_{15}$ are equal in two different byte positions $c_j = c'_j$ and $c_k = c'_k$. If this happens, the two inputs to the composite function that consist in sequences of $A$ and $A'$ respectively, will result in two output, such that both the $j$th blocks and the $k$th blocks are identical. The probability two random 128 bit blocks will have this relation is $\frac{16}{2^{8\times15}}\times\frac{16\times15}{2^{8\times2}}$, which is significantly greater than the probability that you would get the same relation between the corresponding outputs of a 2048 bit pseudo random permutation, and great enough to expect to get such a relation after only $2^{64}$ attempts.


What is the functional role of CKY-I and CKY-R in ISAKMP (IKEv1)?

What is the functional role they play?

They exist to identify the SA.  That is, when an IKE implementation receives an IKE packet, it is able to use the cookies to identify the SA that the packet corresponds to.

  Why not simply use an SPI value like IPsec does?

Why do you think there is some fundamental difference between the cookies that IKE uses, and the SPI that IPSec uses?  They are essentially the same; they are an arbitrary identifier that the allows the implementation to correlate incoming packets with SAs.  Now, there are some minor differences; most notably that an IKE packet contains the identifiers from both sides, while an IPSec packet only contains the identifier from the receiving side; however that difference doesn't change what those identifiers signify.

  how are they created?

Actually, the RFCs do not specify how the implementation selects its cookies, and for a good reason; that is something for the implementation to decide, and if the implementation can (for example) speed up the lookup by selecting nonrandom values, it is free to do so.

Now, there is a minor glitch for IKE cookies that do not reply to IPSec SPIs; since both the initiator and the responder cookies are in the IKE packet, then if both sides select nonrandom cookies (and use the same strategy), then there is a possibility for the implementation to get confused (as it won't know apriori which cookie is his, at least if the implementation can be both an initiator and a responder.  This possibility also exists if the cookies are selected randomly; however the cookies that sufficiently long that such a collision is, in practice, improbable.


modular reduction algorithm over $F_{2^m}$ doesn't seem to work when order of polynomial being reduced is small

In the for loop $i$ is going from the $2m - 2$'th bit (more specifically, the coefficient of $x^i$) downto the $m$'th, where $m$ is the order of the reduction polynomial ($128$). So you never actually get to $x^{127}$ and so nothing is ever added to $C\{j\}$ and thus the return value is $0$.

Actually, $C$ starts off initialized to the input polynomial $c(z)$, and so by not adding anything, the final $C$ value is precisely the initial value, which is the correct answer.

They could have written the algorithm clearer by explicitly stating that, and using the same case for $C$ consistently...


How long must be the key of a stream cipher?

So if the plaintext is N-bits long...the key has to also be N-bits long?

Let's explain this point-by-point:

The key stream has to be N-bits long for a stream cipher;
For an OTP the key is basically the key stream;
For a stream cipher or block cipher (in stream mode such as counter mode) the key is generally between 128 and 256 bits to be considered secure;
For these ciphers the key is used to generate the key stream.

I've skipped "plaintext aware" stream ciphers as they don't use XOR (directly) to calculate the ciphertext from the key and plaintext.

If the answer is no and it can be an arbitrary number...wouldn't that be a block cipher?

A block cipher is a cipher that permutes one  block of plaintext to a block of ciphertext (and vice versa) - using the key to select the permutation. You can have block ciphers and stream ciphers with about any size of key. The key size doesn't define if something is a stream cipher or block cipher.

If the answer is yes, does the sending and receiver end have to agree on the quantity of bits to be transmitted beforehand?

The answer is no, so that makes this question invalid. Nevertheless: for an OTP you'd have to make sure that you know the location within the key stream and of course that you have shared enough key bits. For a stream or block cipher you don't need to know the quantity of bits to be transmitted beforehand. However, you should be using a unique IV or nonce for each message.

If this is random (ie. unknown beforehand), how can they know what key to use to encrypt and unencrypt if it has to be as long as the plaintext?

They use a complex technique called "keeping count" :) And yes, it is a problem if the index gets out of sync, e.g. because of lost messages.


How is multiplication in field $GF(2^{8})$ done?

Consider we want to obtain $\mathtt{0x57} \cdot \mathtt{0x02}$. First we see this one by polynomial method
$$
\begin{array}{lcl}\tag{3}
\mathtt{0x57} \cdot \mathtt{0x02}&=&(01010111)_2 \cdot (00000010)_2\\
&=&({x}^{6}+{x}^{4}+{x}^{2}+x+1)\cdot x\\
&=&{x}^{7}+{x}^{5}+{x}^{3}+x^2+x \\
&=& (10101110)_2\\
&=& \mathtt{0xAE}
\end{array}
$$
The relation $(3)$ means that when an element of $\alpha \in\operatorname{GF}(2^8)$ multiplied by an element $\mathtt{0x02}$ we shift the binary mode of $\alpha$ in the left side.

Now, if the first bit (from left) of $\alpha$ is  $1$ we should $\operatorname{XOR}$ the results with $\mathtt{0x1B}= (00011011)_2$ since when the first bit is  $1$, it means we have $x^7$ in the representation of $\alpha$ and by multiplying by $x$ we get $x^8$ and we use the polynomial $x^4+x^3+x+1$ instead of $x^8$ in our calculation.

We call this operation x_time(). For instance, let we want to get $\mathtt{0x57} \cdot \mathtt{0x04}$. The element $\mathtt{0x04}=(00000100)_2$ is equal to $x^2$. Therefor to obtain $\mathtt{0x57} \cdot \mathtt{0x04}$ we use the function x_time() two times. In $(3)$ we got $\mathtt{0x57} \cdot \mathtt{0x02}=\mathtt{0xAE}$.

In the rest, to obtain $\mathtt{0xAE} \cdot \mathtt{0x02}$, first we shift the binary mode of $\mathtt{0xAE}=(10101110)_2$ in the left side that implying that $$
(10101110)_2 \stackrel{shift\, to\, left}{\Longrightarrow} (01011100)_2 \tag{4}
$$
The first bit of $\mathtt{0xAE}=(10101110)_2$ is $1$ and hence we $\operatorname{XOR}$ the result obtained in $(4)$, with $(00011011)_2$ as follows
$$
 (01011100)_2 \quad \operatorname{XOR}\quad (00011011)_2=(01000111)_2=71=\mathtt{0x47}
$$
I suggest you to obtain other cases as an exercise.


Does this implementation of a function operate in constant time?

Would implementing a function this way run in constant time?

This is not an implementation, it is an abstract description of the algorithm.

You need an implementation of the function in an actual programming language (or actual hardware) to determine whether or not it executes in constant time. You can't determine this by the description of the abstract algorithm, as there are (usually) many different possible ways to compute it.

An example of an implementation of the function would be some C code. Note how there are no operators or instructions in your description - an implementation would have a difficult time producing results without processing a series of instructions.

Additionally, the actual platform that you execute the algorithm on can influence whether or not the operation takes a constant amount of time. Even the programming language that you use can make implementing constant-time anything challenging.

Note also: Constant time in regards to cryptography means "time taken is independent of any secret data", as opposed to "takes the same amount of time to execute on all possible inputs".

If you branch on data that is supposed to be secret, you will probably leak information about it via how long it takes the operation to be performed.


Probability of a prime number of points on an elliptic curve over a prime field

It is known, that as in your setting, when $p$ is prime every possible integer in the Hasse-interval $\mathcal{H}_p$ arises as group order of an elliptic curve $E/\mathbb{F}_p$. For arbitrary prime powers $q = p^f$
this is not generally true: there are often not enough supersingular curves to cover the cases $N \equiv 1 \mod p$.

Galbraith and McKee gives a formula for the probability that a randomly
chosen elliptic curve over a finite field has a prime number of points. The conjecture is the following: Let $P_1$ be the probability that a number within $\mathcal{H}_p$ is prime. Let $C_2\approx0.6601$ be the Hardy-Littlewood twin primes constant. Then the probability that an elliptic curve over $\mathbb{F}_p$ has a prime number of points is asymptotic to $c_pP_1$ as $p\to  \infty$, where

$$c_p=\frac{3}{2}C_2\prod_{l\vert p-1,l>2}\Big(1+\frac{1}{(l+1)(l-2)}\Big) .$$

One might say that $P_1\approx\frac{1}{\log p}$, however this estiamte might not be precise in short intervals.

If all numbers of points in $\mathcal{H}_p$ were equally likely, then we would have $c_p = 1$. The expression given for $c_p$ lies between
about $0.44$ and $0.62$, indicating the phenomenon that prime numbers of
points are disfavoured.

Even though prime numbers of points are seem to be disfavoured by nature, you can efficiently generate such curves in poly-time, ie. in $\mathcal{O}(\log^{3} p)$.


Block cipher mode of operation with beyond-birthday-bound security

It is not a standard mode of operation and I do not know if anyone uses it in practice, but one option is double encryption using counter mode and a non-repeating counter. That is, doing $E_{k_1}(i) \oplus E_{k_2}(i) \oplus p$. The sum of two PRPs is a PRF with better bounds than one. The bound is basically $O(2^{2n/3})$  rather than $O(2^{n/2})$. See The Sum of Two PRPs is a secure PRF.

For example, with a 64-bit block size that means something like going from encrypting 32 gigabytes before attacker advantage to encrypting 32 terabytes instead.


Are hardware encryption chips safer than their software counterparts for desktop apps?

‘Hardware encryption chips’ could mean a couple different things: it could mean

hardware that simply computes cryptographic operations with keys fed in by software, like Intel's AES-NI CPU instructions; or
hardware that stores keys and computes cryptographic operations in them with defensive measures to prevent anyone from ever extracting the keys, like a YubiKey USB device or an HSM.

What I was addressing in the earlier post was only the first type.

If you can take advantage of your CPU's (say) AES and GHASH hardware, then it is probably faster and less vulnerable to timing side channel attacks than software AES.

But it's a lot of engineering work to audit the entire software stack in all instantiations that might arise to ensure that you really are taking advantage of the hardware—because,

for compatibility, software stacks usually have software fallbacks; and
for performance except in sensible software like BearSSL, software fallbacks are usually faster but leaky by default; and
timing side channels are usually silent meaning you won't ever notice the problem until someone on the other side of the planet steals your money through a leak in your Bitcoin wallet software.

Of course, you can get almost the same performance and essentially the same side channel resistance just by using ChaCha and Poly1305 instead, and then you don't have to do all that engineering and auditing work because the widely available ChaCha and Poly1305 software tends to resist timing side channels already, and you get a better security margin because ChaCha is a better design, and your software will be usable securely on a wider variety of platforms.

So, if you're choosing a cipher for a new protocol, then this argument favors ChaCha or XSalsa20 and Poly1305 over AES-GCM in order to avoid needing hardware for fast security.  But if you're choosing an implementation when your protocol has already chosen AES-GCM, then it's safer to use AES-NI or similar to compute it if you can.

As for hardware devices that store keys, well, it's great if you can do that because then malicious apps on your phone/laptop/exobrain/advertisementIVdrip can't steal the keys.

But it also means someone can't just use your awesome app with a one-click install from the app store; instead they may have to carry around a physical device, or you may have to deal with vagaries of platforms like TPM in laptops and SE in iPhones and so on.

So it's more engineering work and usability hurdles.  Which may be worth the security benefit!  It's up to you as an engineer to make informed decisions about these tradeoffs, using particular information about your intended audience, usage, etc.


How can we distribute Shamir's secret sharing scheme shares without a dealer?

Here is the setup I am assuming, in the beginning you have a dealer who distributes $k$ shares from a $k$ out of $n$ secret sharing (e.g., Shamir) to the $k$ parties currently present.

What you would like is that if at some point in the future the $k$ parties want to add an additional party, they can do so, without requiring the dealer to cooperate at that moment in time.

As you mention, one way to do this would be with a general MPC. Another way to do this, would be, if the dealer agrees at the start that some additional shares should be available so that if the $k$ parties want to let another person in, they can, the dealer can generate a few additional shares right off the bat (say $k+t$ instead of just $k$ shares). Distribute $k$ shares to the $k$ parties, then secret share the remaining $t$ shares with the $k$ parties. That way, each of the $k$ parties has their own share, and shares of the remaining $t$ shares. If they want to give someone else a share, they send them a share of one of the $t$ shares. That party reconstructs to get a share of the original secret.

This allows the $k$ original parties to keep their original shares, while giving a new share to a new party. The dealer can also set thresholds on how many of the $k$ parties need to come together to pass out additional shares (it doesn't have to be all $k$).

As I mentioned in my comment, if you remove the requirement that the original $k$ parties can keep their original shares, i.e., you allow them to get a fresh share at the same time that you are generating a new share for the incoming party, Desmedt and Jadjodia's paper on redistributing secret shares is the way to go (malicious model variants have been proposed if necessary).


One approach is to sign $H(m)$ where $H(\cdot)$ is collision resistant, but this approach only has security level of $n/2$ because of birthday attack.

I would argue that this is not susceptible to the birthday attack but requires a second preimage attack. The adversary may be able to use the birthday attack to find two messages such that $H(m_1) = H(m_2)$ but this is not sufficient to break a digital signature. The adversary must also know the corresponding signature for either $m_1$ or $m_2$, and if it can generate these for arbitrary messages (as would be required for the birthday attack) then using a collision to forge a signature is moot (it can already generate arbitrary signatures).

Thus a reasonable assumption is the adversary can only intercept valid message / signature pairs (which is generally a fair model to use) and has to be able to find a collision for a fixed message (i.e. the message that was intercepted), which would require a second preimage attack. So I would argue that $H(m)$ is fine in this context (note that this is what schemes like ECDSA do).