Yarrow and weak cryptographic keys on macOS

A 160-bit seed is plenty for a cryptographically-secure PRNG. We are not going to be able to count to 2160 any time soon, so there is no need to worry that this is a "gaping hole". While in theory Linux's random driver may have a larger keyspace, it's not going to make a difference in real life. Fortuna does have advantages over Yarrow, but a larger key size is not what's important. What really matters is resistance to side-channel attacks and adequate entropy collection at boot time.

By default, Yarrow-160 actually uses 3DES in counter mode to generate the random output, which gives it approximately 112 bits of security. Fortuna uses any other block cipher in counter mode, but typically 128-bit AES. The Linux randomness driver uses ChaCha20. It starts out with 320 bits of secret material (a 256-bit key and a 64-bit nonce). Each reseed updates the 256-bit key. So yes, Linux has a larger keyspace. No, this doesn't matter in practice. Yarrow, Fortuna, and Linux's CRNG are all secure.


Differences between Work Factor and Time Complexity

Work factor is a more appropriate description because time factor is relative to processing power. Time factor, time complexity, computational complexity, and work factor, are used to describe the same thing. When someone says time complexity, they are probably not talking about actual time, but rather computation.

Work factor would be something like "200 trillion iterations of the block cipher", which is constant.

Time factor would be something like "20 years", but if you double the compute power, that is now 10 years. Therefore, time factor is only a good comparison with a fixed level of compute or when you can accurately estimate the amount of computation over a given length of time. Time is easier to explain to someone, and compute power raises at a fairly consistent rate, so using time is acceptable, and thus you can give an expiration date to things like public keys.

That being said, "time complexity" is probably the more common term used to describe computational complexity.


Pseudonymous publication of a series of texts online when a bad guy is expected to join in with fakes: will this approach to PGP verifiability work?

Yes, properly implemented including choice of keys and parameters, what's proposed makes Bob detectable when publishing texts under the pseudonymous identity used by Alice in stage A.

One detail is not made explicit: in step A2 the "signature made using her PGP private key" must be a (detached) signature of at least the text in A1. It is not useful to include in what's signed the PGP public key and fingerprint; but as long as it remains easy to verify the signature and extract the public key and fingerprint, such inclusion does not harm.

In stage B, Alice should I believe try to keep the same signing habits as in stage A, still including her PGP public key and fingerprint, and signing the same elements as she did in stage A. Things still work if the public key is removed (like due to limited publishing space), but including it eases the work of whoever actually try to sort out things, and makes it easier to detect forgeries when Bob chooses the first or second of these strategies:

not including a public key in his messages
including his public key in his messages
including Alice's public key in his messages

Per common practice, the date carried in Alice's signatures should be shortly before the date of the usenet posts or publication; anything else will raise suspicion.


Difference between function $f$ in eval and dec of homomorphic authenticated encryption

The key-word "authenticated" mean that Dec is has not just a decrypting functionality. It should also check the validity of the computation made. that's why it takes as input the function $f$. Read more in details the paragraph "4.4 Authenticity".


Well, at least two representations come to my mind, but I'm afraid you will not find them too useful. In general, S-boxes are designed with the goal in mind that such "mathematical" representations do not help in exposing any more structure than just writing down the table does.

If we are talking about bit strings, i.e., an S-box $S\colon\{0,1\}^n\to\{0,1\}^n$, we can interpret $\{0,1\}^n$ as a finite field $\mathbb F_{2^n}$. Over any field, polynomial interpolation works, thus there exists a unique polynomial of degree at most $2^n$ over $\mathbb F_{2^n}$ that describes the substitution $S$.
Similarly to your permutation matrix example, any map $f\colon A\to B$ of finite sets can be written as a matrix: Let $A=\{a_1,\dots,a_n\}$ and $B=\{b_1,\dots,b_m\}$ (note this fixes an order on the sets), and define $F$ to be the binary $m\times n$ matrix which has $1$ in the entry labelled $i,j$ and only if $f(a_i)=b_j$. Then $F$ applied to the $i$th unit vector gives back the $j$th unit vector, where $b_j=f(a_i)$.

Note how both representations have size exponential in the bit length of the input.


How are objects sold as NFT's ("non-fungible tokens")?

Usually, the NFT has no ties to the physical object. And anecdotally I have heard of many cases where an NFT represented some intellectual property, but did not come with rights, and if the owner of the NFT tried to distribute the corresponding media, then he/she would be in violation of the copyright.
One could potentially sign a contract saying, "whoever legitimately possesses this NFT has these rights," but I have never heard of that being used for a real world object or intellectual property.
Further more, the cryptographic security provided by the block chain is moot because the original creator of the NFT could create arbitrarily many NFTs for a real world object and dishonestly claim that they are the only NFT for the object.
If there is a painting I liked, and someone gave me the choice of either a corresponding NFT or a fancy looking signed certificate that says "whoever owns this certificate is the honorary (but not actual) owner of [the artwork]," I would take the certificate because I could hang it up on my wall and the physical form may give it a higher resale value.


What's a good hash algorithm for hashing a short length (e.g. 256 bytes) buffer, which must be fast and very collision resistant?

First you should check if a cryptographically secure hash such as SHA-2 is fast enough. It is likely it is fast enough, and then the fine details of your weakened collision resistance requirement become irrelevant.
If you really need something fast you may consider CRC-64, but it is obviously not cryptographically secure, It is rather trivial to construct collisions for CRC-64. However if you are trying to protect against random collisions, it may suffice, and with random input data, you may assume CRC-64 won't collide much more then a random function which mean you can use birthday paradox to calculate the chance of having a collision. Essentially you need number_of_messages << 2^(bit_length/2)


Generate a unique 64 bit numeric database key without collisions at $2^{32}$ birthday threshold?

Unfortunately, without some additional assumptions about the strings (e.g. that the first 8 bytes are unique), there is no way to reduce the chance of collision below the usual chance levels.  If you need unique 64-bit ids, the options are:

Do a database lookup when generating keys and pick another key if it is already in use (you state that you want to avoid this).
Ignore duplicate keys, e.g. set things up so that only one of the two entries is kept.  As long as you don't go much above $2^{32}$ entries, the expected number of collisions will be very low, and depending on your task, it may be acceptable to ignore a small fraction of the entries.


Using same encryption key in different schemes

I understand that this could be easily made secure by producing few more keys out of the one key that is provided by, for example, using a stream cipher over predefined plaintexts or by hashing the key with predefined prefixes.

This would be the task of a Key Based Key Derivation Function or KBKDF for short. HKDF is such a KBKDF that quickly has made inroads. It is possible to construct keys using other methods as well, but basically you'd be creating simplified KDFs.

So usually it is better to use a KDF to derive each separate key.

  I am wondering if there are any non-obvious problems with mixing schemes. I suspect there may be, since both ciphertexts together provide more information to an attacker than each ciphertext alone.

As you already found out, it is very easy to create a set of two theoretical ciphers where reusing the key is insecure. You could however take a set of normal ciphers that are very different. In that case you have to find an equation where one cipher leaks information about the other, or you have to retrieve the key from one of the ciphers (i.e. breaking it). Nobody here is going to take two of the final AES candidates and break this scheme.

  On side note, I am aware that same RSA keys should not be used for encryption and authentication. GPG uses separate keys. Feels like a similar issue.

Now you're getting into dangerous waters. Unlike the AES candidates keys for asymmetric ciphers generally have a specific structure that is tied to the algorithm (e.g. RSA). So you can probably only use them for algorithms that are directly related. In that case it might very well be that you leak information and possibly even the key.

The same indeed goes for cipher modes that simply split the key into multiple parts such as SIV of course. You would not want any key reuse for those kind of modes of operation.

Note that besides theoretical issues there may be practical issues as well. Many API's won't allow you to use a key of one specific type as another. Imagine you've got an RSA or AES key in a HSM. You cannot just use that for any other algorithm.


How secure is passing a MAC to Python's random.seed before using random.choice to generate a MAC?

No. It looks like random.seed uses the hash of the argument, which is a 4-byte int.


What is the time complexity of the RC6 encryption?

The time complexity of encryption, decryption and brute forcing a block cipher key are all O(1). This is a fixed problem with no apparent n. If you want to encrypt many blocks using some sane mode (cbc,cfb,ctr,...) the complexity would obviously be O(n).
Cryptographers often misuse assymptotic complexity annotations and write stuff like O(2^128) which is silly as it is still O(1).


PBKDF2 without salt on 16 digit password

TL;DR: If an attacker can gain less than 50k-100k USD from breaking all the "passwords" you're fine, else you could be screwed. (for 10k iterations, using SHA-1 for PBKDF-2)

  How secure would be to use PBKDF2 without salt (or with the same salt
  for all) with a 16 digits passwords that are unique (there can't be
  two identical)?

It would keep medium-scale companies and smaller attackers from getting the passwords, but would fail to do so for larger scale attackers.
The exception being of course an attacker that already has the right scale of infrastructure ready-to-use (first noted by Maarten Bodewes)

The reason for this is documented in the answer to the next (sub-)question.

  How fast someone would be able to identify password using 10000 or
  50000 iterations?

Let's assume you'd use 10,000 iterations (multiply everything with $5$ for 50k). This would mean to search the entire password space you'd have to do 10k SHA-1 iterations per entry. There are $10^{16}$ entries, so that's $10^{20}$ SHA-1 hashes in total.

Now let's have a look at how many SHA-1 hashes a modern GPU (a Nvidia GTX 1070) can calculate per second: 6.3GHashes/s which is $6.3\times 10^9$ hashes per second. Now multiply this with $60^2\times 24$ to get the number of hashes per day: $5.4\times 10^{14}$. So you'd need $10^{20} / (5.4\times 10^{14})\approx 180,000$ days with a single GPU. Now - just for fun -  let's calculate how much 400 GTX 1070 (roughly 500€ a piece) would cost (they'd take roughly 450 days to search the entire key space): $400\times 500\approx 20k$ euro. This is the hardware cost. Additionally you'd need to pay for electricity and other stuff and if you want to be faster you need either FPGAs, better GPUs, ASICs or more GPUs. Now I think with the additional infrastructure, the deployment and the electricity you may end up at 50k-100k USD (and maybe you've bought a few more GPUs ;). So if an attacker can gain this amount of money by breaking your system, you should adapt and if not you're probably fine.

Note that this is an example calculation. An attacker could also very well try and rent high-end GPUs in the cloud, possibly reducing cost and management overhead (first noted by Maarten Bodewes).


Are lookup tables safe when they fit in a cache line?

The typical cache line size of modern x86 machines is 64 bytes.

This might not be true for all processors. You should retrieve that from system if you want to know that. Ideally you should split data further, in your example you can split it to a bit every 16 bytes, so you will support every machine with cache line size of 16 or bigger (and 16bytes is size of SSE register so most machines that come with SSE should have that cache size - so most CPUs in this millennium).

  As far as I can tell, this should be immune to timing attacks, because at no time does secret data determine which cache line is read.

We can only hope.

x86 and x64 processors aren't security devices. They don't come with any guarantees of data access time or any constant time guarantees. In fact, they are known to do anything they can to avoid being constant time, they want to do it faster if possible.

But hopes are (for example OpenSSL RSA relies on that) that this is indeed constant time. There aren't any guarantees from Intel nor AMD. But as far as we understand processors they produced - this is indeed true as of now.

However you should be careful. It isn't hard to introduce timing-attacks into your code - it's very easy to even introduce branch depending on secret if you are using anything but assembly. Best thing you can do is testing if something is indeed constant time on your machine. This doesn't mean it will always take same amount of time. Instead, different secrets shouldn't take different amount of time in long run.


How hard is the Solitaire cipher to crack?

Of course, it strongly depends on what exactly you mean when writing “casual person”. The cipher algorithm works similar to a shift cipher. As long as the attacker does not know the original order of the cards (of one or more decks of cards), then the cipher should be close to being unbreakable for a “casual person” – assuming that that casual person is someone we could call “an average Joe” and not a ”maths, statistics, or cryptanalytics fan”.

As for cryptanalytic security:

It should be noted that there is a chance the algorithm may repeat numbers since there is some bias (as pointed out by people like  Paul Crowley in his Problems with bruce schneier's "solitaire"). While the probability that several numbers will be repeated consistently is rather low, you might want to take a look at his (and related) analysis nevertheless. After all, “having bias” is what broke RC4s neck too. (Yet, RC4 was used in a completely different context where several KBs of data were encrypted with a single key… which added to its bias becoming a weaknes.)
Also, it should not be ignored that if you encrypt with the same deck order and the same keyphrase twice (or more), then both messages can be solved by dragging probable cribs and expanding the solution… without ever attacking the Solitaire key-generation algorithm itself! This practically means Solitaire has the same weaknesses as an OTP system: key-distribution and user-discipline.

On the other hand, we should remember the Solitaire cipher is nothing but a pen-and-paper cipher so we can surely not expect the same security that cryptographic algorithms like AES provide. If you want to hide some personal information from your neighbour, Solitair will do a perfect job. But if you want to protect your country’s top secret information, I would definitely advise to use something else.


what are the benefits/limits of constructing AEAD using Duplex mode with ARX primitive (chacha20 for example)?

It is possible!

The SPARKLE suite is a round 2 family of NIST candidates that uses ARX-based permutations to build sponge-based hash functions (called ESCH) and duplex-based AEAD (called Schwaemm): see their website and the NIST list of candidates.

Some advantages of ARX would be the smaller code size and the speed it allows. A disadvantages would be a harder masking (an implementation technique preventing side-channel attacks).


blake2b length extension attack approach

BLAKE2 is not open-source. BLAKE2 is a specification.

The state is shuffled one last time after having set the final bit, ensuring that a small change, even a single bit, yields a completely different output, that cannot be reverted.

A length extension attack means that knowing M and Hk(M), you may be able to compute Hk(M||E) without knowing the key k.

But with BLAKE2, in order to compute Hk(M) before the finalization, you would need to know the key k. If you somehow know the secret key, you can already forge tags for arbitrary messages.


How do I verify a reset token if the token is hashed in DB?

I was pondering this as well and it was hard to find answers.

My solution: don't hash the token with bcrypt. Instead hash it with e.g. SHA256 with no salt. It will be secure enough if the token is truly random data and long enough.

Then the hash will always be the same, so you can easily find it in the database. No need to iterate over all users or tokens in the database – that would be madness.

Some resources to validate my solution:

How to store the access token / password reset token in the database?
Pre-generating 'secure tokens'
Should password reset tokens be hashed when stored in a database?


Perfect secrecy with some considerartion

I want to prove that $\epsilon$-perfect secrecy holds, when $|K|<|M|$.

I think you are misunderstanding something here. For perfect secrecy as defined, $|K| \geq |M|$ does not imply perfect secrecy. It is the other way around: If perfect secrecy is given, this implies $|K| \geq |M|$.

The implication the other way is impossible to show: Consider $E(m,k) = m$, with some keyspace $K$ larger than the message space $M$ (no need to be more specific). In this case we have $|K| \geq |M|$, but obviously it's not perfectly secret.

And the same goes for your idea: You can not show that something has any kind of secrecy definition, when just the size of the messagespace and keyspace fullfill some equation or inequality. The (almost trivial) counterexample $E(m,k) = m$ with matching key- and message spaces works there as well.


Is a message digest useful with symmetric encryption to check for integrity?

Normally a message authentication code (MAC, for instance HMAC) is used for symmetric integrity and authenticity of the message. In that case a hash can be used with a secret key to protect the message; this is also called a keyed hash. Nowadays authenticated modes of encryption is also used a lot; for example an AEAD cipher such as GCM. AEAD ciphers combine message authentication code with encryption.

Sending encrypt(M) followed by hash(M) is certainly not secure, as the hash leaks information about M. If the message is "Yes" or "No!" then an attacker cannot distinguish between the two when CPA secure encryption is used. However, an attacker can simply test both possibilities by recalculating the hash over the message.

A hash over ciphertext send with the message isn't useful at all, as it would enable the attacker to simply change the ciphertext and then recalculate the hash. Before the hash was sometimes put over the plaintext as well and then encrypted, but that is still not as secure as performing a MAC over the ciphertext, and it may still allow for changing the ciphertext, allowing for instance padding oracle attacks.

With all that said, a hash can be used to secure the integrity / authenticity of a message, be it plaintext or ciphertext. In that case the hash itself must however be trusted. This can for instance be accomplished by putting the hash on a secured website, say apache.org. In that case messages (in this case applications) can be downloaded from mirrors and then compared to the hash, published on apache.org (hopefully over TLS, adding an additional layer of security).

With asymmetric encryption the hash can be trusted because it is verified that the hash was used together with the private key to generate the signature.


OpenSSL - extract hash algorithm from signature data (PKCS#1 v 1.5)

The hash identifier of a given RSASSA-PKCS1-v1_5 signature can only be obtained using the signature's public key¹. It's revealed by performing the signature verification steps 1 and 2/a/b/c (which basically gets the signature as an integer, raises it to the power $e$ modulo $N$ extracted from the public key, and converts back to bytes), then parsing the Encoded Message, which should be as per section 9.2 step 5, that is
$$\text{EM}=\mathtt{00}\mathbin\|\mathtt{01}\mathbin\|\mathtt{FF}\mathbin\|\ldots\|\mathtt{FF}\mathbin\|\mathtt{00}\mathbin\|T$$
where

the left two bytes $\mathtt{00}\mathbin\|\mathtt{01}$ are fixed, and followed by $f\ge8$ bytes at $\mathtt{FF}$ then a $\mathtt{00}$ ($f$ is maximal, that is for a $b$-bit public modulus $N$ the length of $T$ is $\left\lfloor(b-17)/8\right\rfloor-f$ bytes).
$T$ is ASN.1 DER encoded, containing the hash identifier and hash value.

The pragmatic approach to decode $T$ is to look at note 1 (or the table below, which comes from that).

MD2:         30 20 30 0C 06 08 2A 86 48 86 F7 0D 02 02 05 00 04 10 ∥ H
MD5:         30 20 30 0C 06 08 2A 86 48 86 F7 0D 02 05 05 00 04 10 ∥ H
SHA-1:       30 21 30 09 06 05 2B 0E 03 02 1A 05 00 04 14 ∥ H
SHA-224:     30 2D 30 0D 06 09 60 86 48 01 65 03 04 02 04 05 00 04 1C ∥ H
SHA-256:     30 31 30 0D 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20 ∥ H
SHA-384:     30 41 30 0D 06 09 60 86 48 01 65 03 04 02 02 05 00 04 30 ∥ H
SHA-512:     30 51 30 0D 06 09 60 86 48 01 65 03 04 02 03 05 00 04 40 ∥ H
SHA-512/224: 30 2D 30 0D 06 09 60 86 48 01 65 03 04 02 05 05 00 04 1C ∥ H
SHA-512/256: 30 31 30 0D 06 09 60 86 48 01 65 03 04 02 06 05 00 04 20 ∥ H

If we dive into the fine print, this is a DigestInfoValue. For example, the last entry decodes as

30 31   Sequence of 49 bytes

30 0D   Sequence of 13 bytes

06 09   OID of 9 bytes

60 86 48 01 65 03 04 02 06OID 2.16.840.1.101.3.4.2.6 meaning "SHA512-256 algorithm"

05 00   NULL for the Parameters field²

04 20   Octet string of 32 bytes

(the hash H follows as 32 bytes).

See this for how OIDs are encoded, and links to the ASN.1 DER specification. Examples can be thrown at Lapo Luchini's useful ASN.1 decoder.

¹  Given a signature, it's possible to make a new public/private key pair that makes this signature valid with any desired hash identifier and matching any desired known message (not only the the original) when checked with this new public key.

² This field must be present and NULL when encoding and checking $T$ in the context of RSASSA-PKCS1-v1_5. In other contexts a parser must accept that it is missing for the SHA algorithms, see the Exception in appendix B.1 and the two paragraphs above.


Point addition in affine coordinates involves the computation of modular inverses for elements of the underlying finite field. Modular inversion can be done with the extended Euclidean algorithm, although its cost is around 100 times the cost of a single addition or multiplication in the finite field.

Point addition in projective and Jacobian coordinates, however, doesn't require to compute any modular inverse. Hence, the cost of adding two elliptic curve points in projective or Jacobian coordinates is much smaller than in affine representation.

The following is the result of a test I've just run for curve secp256k1, where 'a' means number of additions, 's' number of subtractions, and 'm' number of multiplications, and 'i' number of inversions:

## Addition in affine coordinates ##
{'a': 0, 's': 154, 'm': 299, 'i': 149}

## Addition in Jacobian coordinates ##
{'a': 1, 's': 5, 'm': 17, 'i': 0}

These numbers mean that, for this implementation (which is far from optimized, but serves as an example), addition in affine coordinates is approximately 20 times costlier than in Jacobian.


ElGamal in private set intersection: how to handle negative numbers?

I use the notation introduced in the paper: The parameters of ElGamal are $(G, q, g)$ where $q$ is prime, $G$ is a cyclic
group of order $q$ and $g$ is a generator. In the paper, the authors use "exponential ElGamal" such that they have an additive homomorphism, i.e., the message is
represented as "exponent" of $g$, i.e., as $g^m$. With $h=g^x$
being the public key a ciphertext of a message $m\in Z_q$ is $(c_1,c_2)=(g^y,h^y\cdot g^m)$ and it is clear that by componentwise
multiplication of two ciphertexts for messages $m_1$ and $m_2$, the additive homomorphism gives a ciphertext for $m_1+m_2 \mod q$.

Note that the message space is $Z_q$ and we are working with integers modulo $q$, i.e., the set $\{0,\ldots,q-1\}$.

Now how to handle negative integers $-x$?

There are two ways how you can see this:

If for $-x$ that the absolute value of $x$ is in the set $\{0,\ldots,q-1\}$, i.e., you have that $0\leq |x|<q$.
Then, you can view $-x$ as the additive inverse of $x$ in the group $(Z_q,+)$ which has order $q$. This means $-x$ is an element $a$
for which it holds that $x+a\equiv 0 \pmod q$. Consequently, the value of $a$ is $p-x$.
For example: Let $q=5$ and we want to know $-2$, i.e., the additive inverse of $2$ in $Z_5$, then we have $-2=5-2=3$, since
$2+3\equiv 0 \pmod 5$, so $-2$ is equal to $3$.

Now what if the absolute value of $x$ is not in the set $\{0,\ldots,q-1\}$? For instance, how to handle $-16$ in case of the integers modulo $5$?.

We also can view integers modulo $q$, i.e., the set $\{0,\ldots,q-1\}$, as a set of representatives of the $q$ residue classes modulo $q$.
More precisely, $0$ is a representative for the class $[0]$ of all integers having remainder $0$ when divided by $q$, $1$ a representative for class $[1]$, etc. If you encounter a negative integer as
defined above, then you simply add $q$ until the value lies within the set $\{0,\ldots,q-1\}$ since this will obviously not change the class.

Back to our example, this means that given $-16$ you add $5$ and find that $-16+5=-11$, $-11+5=-6$, $-6+5=-1$ and finally,
$-1+5=4$. Consequently $-16\equiv 4 \pmod 5$ and you can represent $-16$ as $4$.


NIST STS incorrect results for sample files

Don't worry about it :-)

The documentation is "Revised:April2010".  The latest code implementation is (officially) dated July 9, 2014 and commented as "This update has a few minor corrections to the source code. The first change corrects the non-overlapping template test to make it correctly skip bits when a sequence matches.  The second change is to correct the $\pi$ values in the overlapping template test."

The NIST programmers aren't the best, and there might be other later tweaks to the source code.  I don't know how many "few" is, and they don't say.  I haven't gone through all of the individual source files.  Revisioning comments are effectively non existent. Your compiler errors can be ignored, they're only warnings and my (and others) experience of the code is that it works if your samples are large enough. 1 million bits is a good starting size.

A P of 0.534146 is a good result, and shows $\pi$ passing your randomness tests pretty well. The other test files ($\sqrt{2}$ et al) should also give you almost perfect scores but might differ slightly from those documented.

It's just a minor bug fix.


Why are elliptic curves better than cyclic groups?

The first assumption: $E(F_q) \simeq Z_s \times Z_t$ is always true!! (see Handbook of Elliptic and HyperElliptic Curve Cryptography)
It is never said that coordinates of points lie on $Z_s \times Z_t$ which has no sense except if $s=t$.

But the isomorphism is not trivial to compute (it is in fact hard to compute, since it is related to the discrete logarithm for the left-to-right part).

And working only with the representation $Z_s \times Z_t$ will weaken the discrete logarithm so useful for cryptographic purposes.

In brief, if you can exhibit a curve (or demonstrate that there is a NIST curve) for which the computation of the left-to-right part of the isomorphism is easy, then this curve MUST be considered as weak and must never be used for any cryptographic purpose.

Concerning quantum computers, EC-DLOG will be solved as easily as for any cyclic group, since the Shor algorithm can be adapted to solve it, but don't ask me about details, I don't understand them...


LUKS multiple key slots - what's the intuition?

Roughly your password is used to encrypt a MasterSecretKey. Then you use this MasterSecretKey with a symmetric algorithm to encrypt or decrypt your data (the disk sectors).
They eight key slots in LUKS are eight different encryptions of the same MasterSecretKey under eight different passwords.

See also this image:  (original web page: http://auto0.info/secret-messages-download-red-hat-fedora)
(original image http://nnc3.com/LM10/Magazine/Archive/2005/61/065-071_encrypt/images/fig3-partition-header.png is not more available)

Actually LUKS does not encrypt the MasterSecretKey with a password but with a key, generated with a PBKDF.

A similar approach is used by GPG when you send a message to a set of distinct recipients.

This is usally know as KEM/DEM paradigm: Key Encapsulation Method/Data Encapsulation Method and it is the standard method when you use public key to encrypt something.


SPDZ protocol: how expensive is it to generate the multiplicative triples?

The answer to your question can be found in a SPDZ follow up paper; it is described as contribution (2) in the intro (top of page 2).

There is a new version of SPDZ called MASCOT that uses OT instead of somewhat homomorphic encryption, and is supposed to be about 200 times faster. So, I would recommend looking at that as well.


I did also tried to find a good value for the -a flag, in a MacBook Pro Mid14 (i7), trying to login in to a Debian 8.5, I had this results:

-a 1000 Took about ~20s.
-a 100 Varies between ~3.5s to ~6s.
-a 64 (4x default value) ~3 to ~9s.
-a 16 (default) ~2s ~2.5s.

In the end I just stick with the default since I'm not a paranoiac and I don't like to wait, however I did found in my research a value of 100 is not uncommon to choose.


Does AES(x || x) provide secure message authentication when message fits in a single block?

Concatenating two copies of your message is unnecessary and is equivalent to padding out your 64 bit message to the full 128 bits with zeros from a security standpoint (which happens automatically in the encryption process).

  Would they be able to securely authenticate the message?

I assume you mean Authenticated Encryption.  The simple answer is no.  AES on its own only provides provides confidentiality, not Authenticated Encryption (which is defined as confidentiality, integrity, and authenticity).  To get true Authenticated Encryption you would need to use some sort of hash function to create and append a mac, which is validated during the decryption process.

More information on Authenticated Encryption can be found here.

EDIT:  Sorry I was making a few assumptions about other concepts outside the scope of this question.  The reason why simply encrypting one block of AES doesn't give you integrity or authenticity is because it is susceptible to modification by an active attacker.  One way this would work is actually pretty simple, but it assumes you would also use an Initialization Vector (IV).  While not specifically stated in your question, this would be required to make the message resistant to Replay Attacks and is the only way a block cipher is CPA secure.

Assuming CBC mode, the IV is XOR'd over the plain text before encryption.  If you were to XOR what you think is in the plain text (a guess), then XOR what you want to be in the plain text, it will be XOR'd into the plain text before it is encrypted, thus modifying it to whatever the attacker wants.  Other modes could be venerable to attacks like this also.

You could also use this method and the fact that the first 64 bits of the message should match the second 64 bits as a oracle where by you could test one character at a time and watch what response a server gives back to actually decode the message.


Why do 5G, 4G, etc., use non-conventional algorithms?

These decisions are driven by silicon.  Most specifications for hardware are built around a minimally viable CMOS implementation (ex: MPEG-1, lightweight cryptography via NIST 8114).  This is particularly true in commodity parts, such as cell phones.
When you make wireless ICs, you have two clocks in the system at a minimum, which are the carrier frequency and then the baseband frequency.  As an example, for the 900MHz RFID tags that are used for inventory control, you have a 900MHz frequency and then a 1MHz-ish clock (programmable) that handles bit stream generation to  give you about 100kbs of throughput.  When I make RFID tags, I use a feistel cipher in a bit serial mode because I can use the carrier clock run the cipher in a way that I do not have to wait for data to be ready.  By the time that the slow data has been encrypted, it's ready to send.
In the case of AES, I need to fill 128-bits into the register, and then add a buffer to hold the result.  You need to do this with the feistel ciphers as well, but AES is rather large in silicon and slow compared most feistel ciphers in this specific context.   Not using AES allows me to use less silicon, which then helps keep costs down.
update:
Looking at my GDS files for layout and simulations on an ancient process (GF 180nm), SIMON 128/256 was 30% of the area and 50% of the power compared to AES256 for an RFID tag. The sboxs were not done with a lookup table, but explicitly calculated in circuits.  A note, I do not believe that this would scale well due to metals at sub-14nm nodes (sadly, my lectures from Georgia Tech are all no longer online, as I spent a week on this.  Stanford  has some lithography notes.  I'm still looking for a good public facing document).  I would expect the feistel to be a little larger, but AES to scale the same due to colored metals; however, the power should be similar. (I cannot share specific details on modern processes.)


How is information disclosed by modular multiplication?

Can an attacker learn some bits of a using this information?

No.  In the case of multiplication modulo a prime, we have, for any possible value of $a$, there is a unique value of $b$ that makes $a \cdot b \bmod p$ give any particular value of $c$ in the range $(1, p-1)$.

That is, even if we knew all the bits of $c$, no particular value of $a$ are any more likely than any other (assuming we have no information about $b$).  And, in particular, we have no information on any of the bits of $a$ (other than what's implied by $1 \le a < p$, which we already knew).

Any observation in the non-modular case (where this observation does not apply) doesn't apply to the modular case.


Transmit half the bits of the $g^a$ and $g^b$ as MITM countermeasure in DH key exchange?

The question's technique does not prevent a Man in the Middle attack, for the reasons stated in the question. Nothing cryptographic can, under the question's assumption. Pre-existing trusted material allows that, and is used to that effect in authenticated DH.

What the question's technique achieves is

Give more insurance to Alice that the shared secret that she will use can't have been chosen to have certain properties, because the other party's secret exponent $b$ can't be chosen with knowledge of the full $g^a$ chosen by Alice. When doing the normal way (where Alice reveals $g^a$ in full before receiving $g^b$), the party communicating with Alice (no matter who) could chose $b$ such that $(g^a)^b$ has (for example) its low-order 20 bits set to zero, then send the corresponding $g^b$ to Alice; exploring $b$ sequentially, this require only about a million multiplications.
Make it harder or impossible to tell if Alice has chosen a somewhat poor value of $a$ before going as far as the second message sent by Alice, so that analysis of logs of failed connections will have more chance to reveal an attack forcing repeated connections until such poor choice (no answer from Bob on the first message can simply mean that Bob is offline; no answer on the second message, repeatedly, can't have this simple explanation and should raise alarm).
More generally, lessens the asymmetry in timing of information disclosure between the originator that sends the first message, and the other party.

That might guard against some attacks, or make some security proofs possible.

For example, the question's technique might at least partially mitigate an attack where Mallory, actively performing MitM during key exchange, tries to make Alice and Bob compute a common shared secret that Mallory also knows, which then allows Mallory to passively eavesdrop later direct communication between Alice and Bob, encrypted under a symmetric key derived from the shared secret. There's an illustration in the second section.

If additionally the convention exists that the originator sends the high half first, while the other party sends the low half first, then:

Assuming authenticated symmetric encryption from the shared DH secret, this blocks a denial of service by reflection attack where Alice is made to communicate with herself by always sending back to Alice whatever message she sends.
This could have some (hopefully strengthening) effect on protocol attacks that attempt to change originator/target roles.

Half-baked construction where the question's practice mitigates MitM even so slightly.

Start with naive Diffie-Hellman key exchange to establish an encryption key in $\mathbb Z_p^*$ with prime $p$ and $g\in\mathbb Z_p^*$ with $g\ne1$ (perhaps a generator). Normally the protocol goes:

Alice draws random secret $a$ and sends $m_a=g^a\bmod p$ towards Bob
Bob draws random secret $b$ and sends $m_b=g^b\bmod p$ towards Alice
Alice receives alleged $\hat m_b$, computes $s_a={\hat m_b}^a\bmod p$, then $k_a=\operatorname{SHA-256}(s_a)$ used as a secret shared key for a symmetric cryptosystem.
Bob does similarly and ends with $k_b=\operatorname{SHA-256}(s_b={\hat m_a}^b\bmod p)$, which if everything went well is the same as $k_a$.

Mallory playing active attacker could perform a classic MitM (where he plays as Bob to Alice, and as Alice to Bob), and have Alice and Bob use $k'_a$ and $k'_b$ that Mallory knows. But that leads to different $k'_a$ and $k'_b$, and Mallory has to decipher then re-encipher all symmetrically-enciphered messages between Alice and Bob. That's at least a chore for Mallory, and might lead to his active snooping to be detected.

Thus Mallory wants $k'_a=k'_b$. With the basic protocol above, he can achieve this my making $\hat m_a=\hat m_b=1$, $\hat m_a=\hat m_b=p+1$, or $\hat m_a=\hat m_b=p$, which will lead to $s_a=s_b=1$ or $s_a=s_b=0$, hence $k'_a=k'_b$ and known to Mallory. The question's countermeasure won't help against that, but the simpler countermeasure that Alice checks $s_a>1$ will block it. We assume that from now on.

Mallory can still succeed with fairs odds by sending $\hat m_b=p-1$. With odds about 25%, $a$ and $b$ will both be odd, giving $s_a=s_b=p-1$. If $g$ is a generator of $\mathbb Z_p^*$, Mallory can even force Alice to use odd $a$, by having Alice retry until ${m_a}^{(p-1)/2}\bmod p\ne1$ (which insures $a$ odd); same for Bob. The question's technique starts helping, even so little: Mallory can no longer determine the parity of $a$ from what Alice first sends, and must allow the protocol to advance to the second step for Alice before Mallory aborts it, or not.

Note: I tried to find attacks that work even if further it is checked $s_a<p-1$ or something similar intended to block the above, but so far found none. I welcome these (there's an open question), and vaguely conjecture that the question's countermeasure is likely to mitigate such other attack, if any.


Who said "32 round Rijndael" in the third AES Conference

This answer is based on Morris Dworkin's report of the conference, so it ultimately relies on its accuracy (it is probably more reliable than memory, though).

Regarding the question "Except for your proposal for AES, what is your candidate?", the report states (page 15):

  The panelists were asked which algorithm, other than their own, they
  would choose for the AES. Rijmen liked RC6; the other four panelists
  said Rijndael if it was extended to 18 or more rounds.

So this suggests that the representative for Rijndael (Vincent Rijmen) chose RC6.

During his presentation at the conference, Bruce Schneier is reported to have ended with the following suggestions (page 15 as well):

  He [Schneier] recommended  that  NIST choose  either  Rijndael  extended  to  18
  rounds,  Serpent,  or  Twofish  for  the  AES;  he  favored Twofish
  for its efficiency across the board, its unique flexibility, and its
  speed-security tradeoff.

Since he suggested 18 rounds here, it would surprise me if he would argue for 32 rounds later the same day.

So the representative who answered "Rijndael with 32 rounds" was either Shai Halevi (MARS), Ron Rivest (RC6) or Ross Anderson (Serpent).
My personal guess would be Ross Anderson (this would make sense because Serpent has 32 rounds). In fact, on page 16 of the report there is some weak evidence pointing in this direction:

  Anderson  responded  to  a  suggestion  to  transfer  some  of
  Serpent’s rounds to Rijndael by reiterating his support for 32 round
  Serpent with 256 bit keys.


Machine learning to break imperfect randomness

Both cryptography and machine learning are very broad terms. I gather you are wondering if it's possible to use some sort of inference techniques (like support vector machines or deep learning) to exploit a weak PRNG to extract a secret key. If this is possible, it's only true in a very limited manner, and there are probably more effective ways to infer secret material (see, for example, Bleichenbacher’s method for learning about biased nonces).

The only obvious application to me seems to be in the validation of the strength of a PRNG.

If you're willing to consider other kinds of applications of machine learning, you may be able to make some progress. For example, in this paper (unfortunately behind a paywall), the author trains a neural network to carry out a known-plaintext attack against DES and 3DES and infer the plaintext from a given ciphertext. Of course, DES and 3DES are not secure, and the key is not leaked by the method. Furthermore, I don't find this approach any better than just brute-force. Why not?

Machine learning is most useful when it can teach you something about your data. Good cryptosystems publish their designs, so I already know what they will do with the data, so again, I can really only learn about the security of the generation of secret key material: Kerckhoff's Principle in action.

Machine learning may fit into the security landscape in other ways.  Enter adversarial machine learning, which concerns the security of the ML itself. How do you know someone isn't feeding you deliberately-biased training samples to skew your algorithms, for example?

Also, consider the learning with errors problem: given a system of linear equations mod some $q$, solve it assuming some additive random noise is added in. The "random noise" part makes the solution very difficult. In a way, it flips your question on its head: trying to learn about vectors in this system has created a useful hard problem that cryptosystems can be built from!


Wikipedia's double-and-add point multiplication algorithm for elliptical curves

P is an x, y coordinate and so it seems reasonable to assume that 0 is a 0, 0 coordinate

Actually, that's an incorrect assumption; by 0, they really mean the point at infinity (aka the neutral element aka the identity element).  That is, it is a point that doesn't actually correspond to a solution to the cubic equation, but instead is something that needs to be thrown in to make the curve a mathematical group.

As for how it is represented, well, that rather depends on the implementation; there might be implementations that represent it as (0, 0), but (as you point out), that might not work if $x=y=0$ is a valid solution to the equation.


Share encrypted files without giving master key

Yes, it's safe, as you can't calculate the secret key from the HMAC result. HMAC would be useless without this feature
No, Bob will not be able to use his key to calculate the other keys, as long as you use a  reasonable hash function (SHA-2 should fit)
It's the same as 1., Bob doesn't get more information by more derived keys

But when Bob get the key for filename2 and Carlos for filename3, then it's important that Bob nor Carlos are able to affect the filenames.
Otherwise they could create a key for a encrypted file related to another person


NTRU: Possible misunderstending of division and euclidean algorithm for polynomials

I am trying to find GCD of two polynomials

If you are trying to find the GCD, it turns out that trying to perform divisions is the wrong way (the referenced question was talking about computing inverses - a rather different problem).

The first thing you need to ask is "what ring or field are the polynomials defined over?".  If it is, in fact, a field, then it is easy; you can follow this procedure:

GCD( Polynomial P, Polynomial Q ) {
    for (;;) {
        if (deg(P) < deg(Q))
            swap P, Q
        deg_p = deg(P);
        lead_p = P[deg_p];   /* The leading coefficient of P */
        deg_q = deg(Q)'
        lead_q = Q[deg_q];   /* The leading coefficient of Q */
        X := (x ** (deg_p - deg_q); /* A polynomial with the coefficient */
                             /* deg_p-deg_q set */
        (P, Q) := (Q, lead_q*P - lead_p*X*Q);
        if (Q == 0) {        /* If Q is the all-zero polynomial */
            return P;
        }
 }

This function decreases deg(P)+deg(Q) each iteration, and so it is guaranteed to terminate.  In addition, all the operations can be done fairly easily (the computation of X*Q can be done by shifting all the coefficients of Q leftward deg_p-deg_q places).

And, if the polynomial is defined over a field, it can be shown that this always returns a correct value.

On the other hand, sometimes NTRU works in polynomials over the field $\mathbb{Z}_3$, and sometimes in polynomials over the ring $\mathbb{Z}_q$, for $q = 2048$ or $4096$; this ring has noninvertible elements, with muck things up a bit.

Now, if you are working over $\mathbb{Z}_q[X]$, I believe that the above algorithm will return something related to the actual GCD (however, it's not guaranteed that $P$ and $Q$ will both be multiples of the result); depending on what you're doing with the GCD, it might be good enough...


Is it a bad idea to make multiple SHA-* with the same header?

The standard assumption in cryptography is that the adversary knows

methods used
what's physically transmitted (here, I guess payload and the SHA-512 hash);
any data other than the key(s)

Here pincode is clearly a key, and the default assumption would be that unique ID is not. With this hypothesis, a single hash is enough to allow an adversary to find pincode by enumeration, then break the system. Thus multiple hashes are not worrying, but the basic principle is insecure.

Additionally, SHA-512 is vulnerable to a length-extension attack, and with a few hypothesis about what's admissible as payload, that might allow computing the hash for an extension of the payload, without knowledge of unique ID (or even the original payload; only its length is required).

If some other hypothesis applies, please edit the question.


Modes of operation for Public Key Encryption schemes

No, usually you are required to use hybrid cryptography.

ECB, CBC etc. are defined for block ciphers. Although you could possibly apply them to asymmetric cryptosystems, it would make little sense:

performing sequential asymmetric cryptography is not efficient, block ciphers are much more efficient
in general there will be a lot of overhead per block, e.g. due to per-block padding (where block ciphers don't have any overhead per block)
the block size is usually rather large

So in general a symmetric key is generated, which encrypts the plaintext, and then the symmetric (session or data) key is encrypted and send with the ciphertext.

Note that ECB is usually not secure. For asymmetric ciphers, the plaintext (or key) is normally wrapped with random padding before encryption. So ECB is not deterministic for most asymmetric encryption primitives for which such random padding is applied.


Berlekamp-Massey algorithm: case when sequence length is less than double the length of the LFSR

The Berlekamp-Massey algorithm find the shortest LFSR that can produce the given sequence.
Formally, if the sequence has $n$ elements $S_0, S_1, \ldots, S_{n-1}$, then the
algorithm finds $\lambda_1, \lambda_2, \ldots, \lambda_t$ such that for
$i = t, t+1, \ldots, {n-1}$, the following equation holds:
$$
S_{i} +S_{i-1}\lambda_{1} + S_{i-2}\lambda_2 + \cdots + S_{i-t}\lambda_t = 0,
\tag{1}
$$
that is,
$$S_i = -\bigr(S_{i-1}\lambda_{1} + S_{i-2}\lambda_2 + \cdots + S_{i-t}\lambda_t
\bigr).
\tag{2}$$
Note that for $i=t$, we have
$$S_{t} = -\bigr(S_{t-1}\lambda_{1} + S_{t-2}\lambda_2 + \cdots + S_{0}\lambda_t
\bigr)\tag{3}$$
The idea is that the initial loading of the LFSR is $(S_0, S_1, \ldots, S_{t-1})$,
and the weighted sum of the LFSR contents stated in $(3)$ is fed back
into the right end of the shift register as the LFSR contents shift one place
to the left. Thus, the new state of the LFSR is $(S_1, S_2,\ldots, S_{t-1}, S_t)$. In later clock cycles,
the LFSR will contain $(S_{i-t}, S_{i-t+1},\ldots, S_{i-1})$, the feedback
will compute $S_i$ as given in $(2)$ and so the new state of the LFSR
is $(S_{i-t+1}, S_{i-t+2},\ldots, S_{i-1}, S_i)$.  The output of the
LFSR is the symbol falling off the left end and is thus $S_0, S_1, \ldots, S_{n-1}$.

The dsp.SE reader will recognize that if we define polynomials
$$S(z) = S_0 +S_1z + \cdots + S_{n-1}z^{n-1}, ~~
\Lambda(z) = 1 + \lambda_1z + \cdots + \lambda_tz^t,$$
then the left side of $(1)$ is the coefficient of $z^i$ in the
product $S(z)\Lambda(z)$. Thus, the product $S(z)\Lambda(z)$
contains no terms of degree $t, t+1, \ldots, n-1$.

Turning to the problem at hand, if the given sequence can in fact,
generated by a LFSR of length $L$ (where $L$ is the length of the shortest
LFSR capable of generating $S(z)$), and if $n \geq 2L$, then
the Berlekamp-Massey algorithm will find the feedback coefficients
$\lambda_1, \lambda_2, \lambda_L$ of the unknown LFSR as soon
as it has examined the first $2L$ terms $S_0, S_1, \ldots, S_{2L-1}$
of the given sequence. It will then process the remaining terms
$S_{2L}, S_{2L+1}, \ldots, S_{n-1}$ of the sequence, and will discover
that the same LFSR that it has
already found will generate these remaining terms as well.

It is important to remember that the Berlekamp-Massey algorithm
will find the shortest LFSR that will generate
$(S_0, S_1, \ldots, S_{n-1})$, and this LFSR
might not be the same one
that was actually used to generate $(S_0, S_1, \ldots, S_{n-1})$.
Any sequence that can be generated via a LFSR with feedback polynomial
$\Lambda(z)$ can also be generated via a (longer) LFSR with feedback
polynomial $\Lambda(z)\Psi(z)$, and the Berlekamp-Massey algorithm
will find the shortest shift register that works.

What if $L$ is such that $2L > N$, then the Berlekamp-Massey
algorithm will find the shortest LFSR that will generate
$(S_0, S_1, \ldots, S_{n-1})$. The length of this LFSR
will generally not be $L$ and its feedback coefficients will in
general not be the same as those of the actual LFSR
that was used to generate the sequence. If at a later time,
the terms $S_{n}, S_{n+1}, \ldots, S_{2L-1}$ become known,
the algorithm will extend the LFSR and ultimately come up
with the right answer, but for now, it will simply find
the shortest LFSR that will generate
$(S_0, S_1, \ldots, S_{n-1})$.

In broad terms, the Kolmogorov-Chaitin theory of complexity
of a sequence
says that for almost all sequences of length $n$, the shortest
program that can print out the sequence has length $n+c$ where
$c$ is a constant. In other words, for most sequences, one can do
little better than simply store the sequence in memory and print it out: there
are no computational methods that will allow you to generate
the sequence via calculations. Thus, given an arbitrary sequence
of length $n$, the Berlekamp-Massey algorithm will typically
find an LFSR of length $n-1$ that stores the first $n-1$ symbols
and then calculates $S_{n-1}$ via $(2)$ with $t = i = n-1$.

The answer to the OP's question

  "...can the algorithm be used when $2L>N$ and $N$ is "reasonably" close to $2L$?"

is that the algorithm can be used, and it will find the
shortest LFSR
that will generate  $(S_0, S_1, \ldots, S_{n-1})$, but
this LFSR will typically not be of length $L$ and
the feedback polynomial will typically differ from
that of the LFSR of length $L$ that is known to
generate $(S_0, S_1, \ldots, S_{n-1})$.


How to Update Non-Membership Witness upon deletion in RSA Dynamic Universal Accumulator

The updated Non-Membership Witness ($\hat a, \hat d$) upon deleting a member $\hat x$ can be calculated as follows:
$\hat a = a\hat x\mod x$
$r = (a\hat x - \hat a)/x$
$ \hat d = (d\hat c$ -r )$\mod n$
Hope this is useful to future developers trying to deconstruct these equations.


How can I generate large primes for Pedersen commitment?

You can find two algorithms for generating such $p$ and $q$ in Appendix A.1, FIPS-186-4 (digital signature standard).

edited to add: Essentially, the two algorithms generate a pseudorandom prime number $q$ of the desired size first, then generate a pseudorandom random number $p$ (such that $q|(p-1)$) of the desired size, and test whether $p$ is prime. If so return $(p,q)$ pair, otherwise start over again. The difference between the two algorithms is that the one in A1.1 uses probabilistic primality testing thus returns probable prime numbers and the one in A1.2 returns provable prime numbers. The two algorithms use hash functions as pseudorandom generators so that the seed can be provided for people to verify the numbers are generated pseudorandomly from the seed.


Decoding base64 encoded message with a key

That's a simple substitution cipher. Base 64 uses the following alphabet A-Za-z0-9+/. Here A encodes  000000, B encodes 000001 etc. In your case the g encodes 000000, P encodes 000001 etc.

Instead of writing your own decoder for that you can simply take the ciphertext, iterate through the characters of the ciphertext and replace g with A, P with B etc. After that you should be able to use a regular base 64 decoder to do the work for you.

Don't replace multiple characters at a time or you'll run into trouble. Put the characters in a new string instead (if you map g to A while there are still other A characters left then your algorithm will certainly fail).


Can CFB mode of block cipher be used as a commutative encryption?

No, because CFB isn't commutative.

You can see this by looking at the decryption of double-CFB encrypted ciphertext. Even assuming a constant IV (so single-use keys), if you decrypt in the wrong order it cannot work, since the ciphertext is used as input into the block cipher and will differ from what was used with that key when encrypting.

The exception, of course, is single block messages, where CFB effectively reduces to CTR and has similar commutativity and (in)security, with the latter depending on how it is used.


Does DTLS Change_Cipher re-transmission use same epoch as original one or the new one?

The handshake protocol retransmits its messages using the same epoch as it used in the first original transmission.

DTLS1.2 RFC6347 section 4.1 hints about it.
However the text to reuse the  same epoch is not explicit.

  ... some care needs to be taken during the handshake to ensure that retransmitted messages use the right epoch and keying material...

For the situation where ChangeCipherSpec gets lost, it cannot be retransmitted in the new epoch. Doing so will lead the ChangeCipherSpec recipient to a situation where it does not have anyway to decrypt it because its own receive side record layer cipher state has not been updated yet with the keys of new epoch.


No, Lamport signature is a particular one-time signature scheme prescribing a particular method of verifying signatures, generating key pairs, and generating signatures.  You could use that technique to turn a one-time signature scheme such as Lamport's into a tremendously awkward stateful many-time signature scheme.


In BBC Sherlock's The Blind Banker, what type of cryptographic function is used by the Black Lotus?

This sounds like a straight forward book cipher.

Symmetric encryption implies that the knowledge of the key is sufficient for both encryption/decryption.

Asymmetric encryption implies that the ability to perform the encryption/decryption operation is separated into two distinct keys.

  But at the same time, the book is publically accessible so it's not strictly a secret/private key.

Which book is used may be the secret key. Also, which book is used could be public knowledge, but certain subsections of it are the key.

Another way to look at it is that the set of possible bit strings of a given size is public knowledge. But if you select one particular bit string secretly from this publicly known set, it does not mean your secret key is then public information.


You elaborated that your goal is to make it possible to decrypt a message successfully "only when the device is in a specific location".

Great goal, but yeah, well, the particular scheme you describe in your question ain't gonna work. Someone who is not physically at the specific location, but who knows where the specific location is, can still infer the key and decrypt the ciphertext.  This is a fundamental flaw, and it's not something you can fix by sprinkling on a KDF or multiple keys.  It doesn't matter how many keys you have or how you combine them.  Sorry to break it to you, but your scheme is not secure, and it cannot be easily repaired.  You're asking the wrong question: your whole approach is flawed.

There's been academic work on this sort of problem (e.g., by Dorothy Denning), but it's a much harder problem than you seem to realize, and the resulting schemes look very different.  One has to find some source of unpredictable entropy that is visible to anyone who is at the specified location at the specified time, but that is not known or predictable to anyone else.  That's very challenging.

For the state of the art in this area, see the following papers:

Location-Based Authentication: Grounding Cyberspace for Better Security.  Dorothy Denning.  Computer Fraud & Security, Feb. 1996.
On location-restricted services. Eran Gabber and Avishai Wool. IEEE Networks, 13(6):44-52, November/December 1999.

There may be more other work; I recommend that you do a literature search to check.


It seems like a stream cipher will always be one-way, whereas a KDF might not be (see AES or DES key schedules for example).

A KDF has nothing to do with DES or AES key schedules. Key schedules are internal functions of the block cipher, they aren't designed to be KDF's. And KDF's are certainly supposed to be one-way functions.

From SP-800 SP 108 chapter 7.1, Cryptographic Strength:

  The security strength of a key derivation function is measured by the amount of work required to distinguish the output of the KDF from a truly uniformly distributed bit string of the same length, under the assumption that the key derivation key, $K_I$ [ed: the input keying material], is the only unknown input to the KDF.

  So using a KDF might be dangerous if you use it to both derive public and private values.

The output of a KDF should be indistinguishable from random, so this statement is false - which has probably to do with your statement that they may not be one way.

  it takes a SALT parameter. So you can use it several times with the same key, but by varying the parameter you will get different output. If you would do that with a stream cipher you would need to remember a state.

Salts are used to further strengthen the security proof for HKDF. In SP 108 they can be part of the Context and are then called a Nonce (and, given that the salt is large enough, random salts are unique in a computational sense). A random IV would do the same thing for a stream cipher.

Salts are not required for key based KDF's as the input keying material should provide enough entropy.

But I think you are mixing up key based KDF's such as HKDF and password based KDF's such as PBKDF - see below.

  it has a work factor. So with the SALT and that you can use it as a password hashing function. But then we're kind of off track.

A work factor is only needed if the input material is not strong enough. This is basically the case for password-based KDF's such as PBKDF2, bcrypt, scrypt and Argon2. The work factor is used to strengthen the input keying material (somewhat).

Counter mode encryption doesn't explicitly contain any ways of inputting labels, salts or context. A KDF construction makes these explicit.

With regards to the output, a KDF can be used with different info (label / context) to generate different keys, using the same input keying material. This is important if you integrate such a function in e.g. a HSM (security token), where you want to keep the output as key within the token (instead of splitting it up manually in software).

Finally, many KDF's contain not just expand functions to generate enough output keying material, they also contain extract functionality to compress the entropy in the input keying material. Many stream ciphers require keys that are indistinguishable from random and/or a specific length. So they don't provide extract functionality.

A KDF is build from PRF's; a PRF provides the required security to create proofs for the KDF. Actually, counter mode is often used for KDF's, but they employ a PRF instead of a PRP such as a block cipher (of course the PRF may be created out of a block cipher itself). So in the end many KDF's do output a stream of pseudorandom bits.


Why shouldn't cryptocurrency hash algorythms, resist side channel attack?

It is generally assumed that cryptocurrency mining is an "offline" process, that is you take one input from outside, and then after a long while you report back with a result. In particular, it is assumed that an adversary does not see when exactly one search starts and when it ends nor do they see how many tries it took you exactly. This makes timing-based side-channels extremely hard - most likely impossible - to execute, even if you leak "a lot" in terms of traditional timing side channels. Furthermore the input to the hash function - which is what you'd want to recover - is only secret right up until you make your outside communication announcing said input - at which point a more sophisticated recovery of it would be pointless...


Why should I use X.509 Authentication over PKC based Authentication?

In real communications, you often don't reliably know each others' public keys. X.509 certificates provide a way to verify a public key (as the certificate is signed by another key, and that key can be in a certificate signed by a third key, and so on, until we reach a public key that the other person does trust). Certificates are unnecessary when both parties already know each others' public keys through some form of out-of-band communication.


Attacks on elliptic-curve based cryptosystems through solving the Decisional Diffie-Hellman Problem with the Weil Pairing

Proposition  One-wayness of ElGamal encryption holds under the Computational Diffie-Hellman (CDH), and conversely.

CDH Problem (informally) Given $(P, [r]P, [s]P)$ find $[rs]P$.

Let the public key be $Q = [s]P$ where $s$ is the corresponding secret key.  Let also a ciphertext $C = (C_1, C_2)$ with $C_1  = [r]P$ and $C_2 = M + [r]Q$ for a message $M$ (viewed as a point on an elliptic curve).

Proof (of the proposition):

If you can solve the CDH then you can break the one-wayness of the encryption.
Suppose you are given a ciphertext $C = (C_1, C_2)$, the goal is to recover the corresponding plaintext. On input $(P,C_1,Q)$, you first obtain $[rs]P$ by solving the CDH. Next you recover the plaintext as $M = C_2 - [rs]P$.
If you can break the one-wayness of the encryption then you can solve the CDH.
Suppose you are given a DH triple $(P,[r]P,[s]P)$, the goal is to obtain $[rs]P$.  You define the ciphertext $C = (C_1,C_2)$ where $C_1 = [r]P$ and $C_2$ is a random point.  You define the public key as $Q := [s]P$.  You recover the corresponding message $M$ (because you can break the one-wayness) and find $[rs]P$ as $[rs]P = M - C_2$.


Static DH/Static ECDH certificate using OpenSSL

DH: OpenSSL commandline has three options for creating certs, but all of them either selfsign the cert or require a selfsigned CSR, and DH can't do either of those. OpenSSL library called from a program you write can construct an X509 object (cert) containing a DH publickey, subject and other attributes as you specify, signed by an RSA key corresponding to a parent (CA) cert. Look at the code for ca.c or x509.c in x509_certify as a (very approximate) starting point. Remember that if the same parent key/cert was or will be used to issue other certs as well you should keep all serialnumbers unique, perhaps using the same simple file ca and x509 use.
(update) In 1.0.2 this changed; x509 -req -CA[key] now has an option -force_pubkey which allows you to create a CSR with a dummy key that supports signing but issue the cert for the DH key. (I didn't notice right away because the usage message wasn't updated until 1.1.0.)
(added) Plus as Maarten spotted OpenSSL has long used PKCS3 parameter encoding (p,g and optionally subgrouplen but not q) not X9.42 as specified by RFC3279 (p,g,q and optionally cofactor). However in 1.0.2 up X9.42 format is supported under the name DHxparams and is automatically used if the q field is set in the DH struct, which (as well as reading it in) occurs if you convert DSA-format parameters (which always use p,g,q) using DSA_dup_DH, invoked by commandline dhparam -dsaparam (!), or create them using genpkey -genparam -algorithm DH -pkeyopt dh_paramgen_type:{1 or 2} (!!).
ECDH: the same key format is used for ECDH and ECDSA and the cert is distinguished if at all only by whether KeyUsage extension permits keyAgree versus digSign. Therefore with commandline you can generate (in order) EC parameters and an EC keypair, an ECDSA-selfsigned CSR, and a cert signed by a parent key&cert either RSA as you asked or ECDSA, optionally containing a KeyUsage extension as you desire (and other extensions also). The two options and variations are the same as for entity RSA except using an EC keypair -- which is generated using EC parameters (aka curve) where RSA keypair is generated using only a bitsize (which is sometimes defaulted).
protocols: If you intend to use these certs for SSL/TLS, note that OpenSSL does not yet implement the static-DH ciphersuites, even though it has long implemented the primitives needed by those suites -- and DHE and DHanon which are implemented. Apparently for the last 15 years there has been essentially no demand; this suggests that the peer systems you can communicate with using static-DH is probably the empty set. The probably-soon next release 1.0.2 is planned to add them. (update: it did, in Jan. 2015) OTOH static-ECDH has been implemented since EC ciphersuites as a whole were implemented; the code was actually in 0.9.8 but disabled by default, and since 1.0.0 it has been enabled by default except that RedHat packages before late 2013 removed (all) EC due apparently to patent concerns. (update) However 1.1.0 released in Aug. 2016 removed both static-DH and static-ECDH ciphersuites.
curve format: for EC (including ECDH) it is possible to represent some standard and popular EC curves either as a OID that maps to a code set by rfc4492, or as 'explicit' parameters (underlying field prime or polynomial, equation coefficients, base point coordinates, order and cofactor). These produce the same EC computation but are NOT equivalent in SSL/TLS protocol. In particular in some cases libssl will successfully use a cert/key with the 'named' form curve (if agreed by the peer system, of course) but not one with the 'explicit' form of the same curve. Use a standard curve (i.e. don't generate your own) and be sure not to convert the parameters to explicit form. (update 2021-04) I didn't notice right away but OpenSSL 1.1.0l and 1.1.1d up (both in 2019-09) now recognize a cert with explicit-form parameters as matching the named curve.
EDIT 2017-10: belatedly found crossdupe https://security.stackexchange.com/questions/44251/openssl-generate-different-types-of-self-signed-certificate
2019-08: also similar https://security.stackexchange.com/questions/14165/do-you-require-a-special-type-of-certificate-for-using-diffie-hellman-as-the-key

Edit: Additional answer to question(s) in comment by Martin Del Vecchio which initially appeared similarly but is in fact completely different.
This new problem is not DH or even ECDH, it is ECDHE. I'm not sure exactly what you are doing so I'll just start from the beginning and work through.
DH and ECDH are different algorithms. They are based on similar mathematical concepts, but they use completely different data.
Classical or "integer" Diffie-Hellman uses a usually-smaller subgroup of the multiplicative group of integers modulo a large prime.
Elliptic-curve Diffie-Hellman uses a usually-maximal subgroup of the points on an elliptic curve over an underlying field.
A DH key or cert cannot be used for ECDH, and an ECDH key or cert cannot be used for DH.
ECDH and ECDHE are different protocols. SSL/TLS has three main key-exchange mechanisms that use the ECDH algorithm:
"fixed" or "static" ECDH, represented by just ECDH in cipher suite names; "ephemeral" ECDH represented by ECDHE; and "anonymous"
ECDH represented by ECDH_anon in the standard (RFC) names but AECDH in OpenSSL. The first two have variants depending on what
authentication is used; anonymous does no authentication, which in practical use on the internet isn't secure,
and thus is disabled by nearly all implementations including OpenSSL by default.
What Firefox offers: I don't use WebRTC, but for https my Firefox 39.0 offers 11 suites: 6 ECDHE
(3 ECDHE_ECDSA and 3 ECDHE_RSA, almost as you had in your comment except the sixth one should be c012 not a repeat of c013),
2 DHE_RSA suites (that's integer-DH not ECDH), and 3 plain RSA suites (not using any kind of DH).
I find it surprising NSS (which is what FF uses for SSL/TLS) would be different for DTLS than TLS;
perhaps it's because DTLS started at the same time and protocol level as TLS 1.1,
which is well correlated with ECC although it doesn't technically require it.
But even if ECDHE isn't required it's still preferable both in itself (PFS and efficient)
and because FF/NSS offers it in conjunction with GCM for the data cipher.
FF also offers only the 3 most popular "curves" from SECG/NIST: P-256, P-384, P-521. It might support others but it doesn't say so.
What ECDHE requires (any server): to support any ECDHE ciphersuite in SSL/TLS you do NOT need an ECDH cert, much less a DH cert.
You need two things in the server:

a privatekey and cert that allows signing, either RSA with a size acceptable to the client or ECC(ECDSA) on a curve supported by
and acceptable to the client (and the server), with the cert issued by a CA/chain trusted by the client (and not expired or revoked etc.) and any chain cert(s) either supplied by the server or dynamically available or both.
Best practice since the beginning of 2014 is that RSA must be at least 2048 bits, ECC at least 224 bits, and signing hash at least SHA-256. FF apparently doesn't check RSA-2k yet, and it doesn't enforce SHA-256 yet but it does give a warning in its optional console(s), but you should expect it probably will enforce these before very long for "proper" (CA-issued) certs; whether it will do so for selfsigned certs that necessarily must be manually trusted is less clear to me. By choosing the "top 3" ECC curves FF implicitly enforces more than ECC-224.

ECDH parameters -- not a key and definitely not a cert, but only parameters, and not DH parameters either.
ECC parameters are usually called a curve
because that's the interesting part although the actual parameters also include the base point, order and cofactor. The curve used must be supported by and acceptable to the client (and the server).

What OpenSSL server and selfsigned needs is more specifically:

privatekey and cert that allows signing either RSA or ECC (ECDSA). Lots of browsers and clients besides FF like P-256 so if you use EC use P-256 unless you have a strong reason otherwise. As noted in the first part of my answer, make sure you use the "named" form of the curve not the "explicit" form.
If you don't include the KeyUsage extension, it allows signing implicitly;
if you do include KU, the value must have the digitalSignature bit set.
Any selfsigned cert (for any ciphersuite and keyexchange not just ECDHE) will have to be manually trusted in FF.

"temporary" (ephemeral) ECDH parameters. You can:

call SSL_[CTX_]set_tmp_ecdh to set a specific curve
for future sessions (unless changed);

call SSL_[CTX_]set_tmp_ecdh_callback to set a callback function which will
be called for each session to select a curve (unless changed);

or in 1.0.2 (released Jan. 2015) call SSL_[CTX_]set_ecdh_auto
to have libssl automatically choose a curve suitable for each session.
As above use P-256, by calling EC_KEY_new_by_curve_name(NID_X9_62_prime256v1), unless you use auto.
(EC_KEY_new doesn't generate a key; it creates an object containing the curve which will be used to generate the key in libssl.)

SSL_k (and _a) bits cannot be in a cert. They are used only within OpenSSL as attributes of ciphersuites.
There are some different values sometimes used in some certs to represent information related to but different than
the SSL_k and SSL_a bits. But not for SSL_kPSK or SSL_aPSK; those never correspond to anything in a cert, because PSK never uses certs.
I'm not sure what you actually did here, but the above description is what is correct.


Verilog is Turing complete, so you can implement any algorithm in Verilog, if you really want to.


Applicability of IBM's projected 50-qubit quantum computer Q to cryptanalysis?

What would be the applicability of that to cryptanalysis?

It wouldn't appear to have any direct applicability to cryptanalysis, for two reasons:

50 Qbits is just not enough to attack any cryptographical problem; to apply either Shor's or Grover's algorithm against any realistic problem, you'll end up needing thousands.
It doesn't appear that they're addressing the decoherence issue.  That is, in a quantum computer, you'll end up getting random perturbations to the running state.  Cryptographical computations take quite a long time (far longer than we can go without expecting such a random event to occur), and are quite sensitive to such perturbations.  What they'll need to do is run error correction logic (which has multiple physical qbits stand for the one logical one, and has logic to detect such a perturbation on one of the physical qbits, and correct it).

Now, I'm not saying that what IBM is trying to build is useless; for one, it would appear that the computations that Chemical modeling requires fits nicely into what they have.

And, while this isn't immediately useful for cryptography, it is another step towards a Real Quantum Computer (where "Real" means "can actually solve an interesting cryptographical problem).


What's the difficulty of using elliptic curves to design homomorphic encryption protocols?

From my point of view, Homomorphism is a inherent attribute of certain lattice-based scheme.Researchers try every means of solution to enhance the attribute,but not all primitives have this attribute.


What would be the best encryption method[...]?

The standard approach is quite simple. You have a Diffie-Hellman shared secret $K$. Because $K$ is not actually uniformly distributed you run $K$ through a key-based key derivation function (KBKDF) like HKDF (or even a "simple" hash), this is your key $k$ then. Then you use $k$ to symmetrically encrypt (and authenticate) data using a unique nonce for each data packet. You can also derive multiple different keys from the shared secret, e.g. one for each transmission direction.

You may want to note though that your current parameters are a bit on the insecure side being only 12-bit long as opposed to the current standard 2048-bit length.


You can use a standard signature scheme. The user will type in a password, and receive their private key and associated username. Then, to post a message, they sign the message and broadcast the message, username, and signature. Other users will convert the username to a public key and then verify the signature.

This is the same way that bitcoin handles the identity crisis: tying messages to keys instead of real people.


Possible ways to crack simple hand ciphers?

When trying to break an unknown cipher, one first needs to figure out what kind of cipher one it is.  Generally, a good starting point would be to start with the most common and well known classical ciphers, eliminate those that obviously don't fit, and try the remaining ones to see if any of them might work.

An obvious first step is to look at the ciphertext alphabet: does the ciphertext consist of letters (and if so, in what alphabet), numbers, abstract symbols or some combination of those?  If it's letters, does it include spaces, punctuation or case distinctions — and, if it does, do they look like they're also scrambled somehow, or are they perhaps just left as they are in the plaintext?

Compiling a letter (or symbol) frequency table of the ciphertext, and comparing it to the corresponding table of plain English text, can often yield information about the general type of cipher one is dealing with:

If the ciphertext is written in letters, and their frequencies more or less match those of plain English text (the nonsense phrase ETAOIN SHRDLU is handy to remember for this), you're probably dealing with a transposition cipher.  (If the most frequent letters don't quite match, but still look plausible for natural text — mostly vowels and a few simple consonants — it might be a transposition of text in some other language.)
If the rank–frequency distribution looks similar to that for plain English, but the letters are obviously scrambled (e.g. most frequent letters are G, X and Q instead of E, T and A), the cipher is likely to be a monoalphabetic substitution (possibly combined with transposition).
If the frequency distribution is closer to uniform than one would expect for natural language, you're probably looking at a polyalphabetic substitution cipher.  With experience (and enough ciphertext), one may even be able to guess at the most likely cipher just based on the frequency distribution.

Knowing whether the cipher has a key or not, and what form the key takes (word, number, sequence of numbers, etc.) can also help reduce the range of possibilities.  For example, let's say that the ciphertext is uppercase letters with no spaces or punctuation, and that we know it has a key which is a word or a short phrase.  That narrows down the likely choices quite a bit:

If it's a transposition cipher, the obvious thing to try would be columnar transposition and its variants like double transposition.
If it's a monoalphabetic substitution and has a keyword, the keyword cipher described by mikeazo in his answer is the obvious choice.
If it's a polyalphabetic substitution, there are more choices.  The first ciphers I'd try would be Vigenère, autokey and Playfair; if those don't work out, Beaufort, two-square and four-square may be worth trying too.

Since you already know what the key is supposed to be, testing each cipher should be pretty straightforward: just try to decrypt the message with the key and see if the output makes sense.

Note that, in some cases, effort can be shared between ciphers.  For example, the Vigenère and autokey ciphers are identical for the beginning of the message; they only start to behave differently when the end of the keyword is reached.  It may also be a good idea to try simple variants of these ciphers, such as switching the encryption and decryption rules around; some of them work equally well in both directions, and may have been used so.


Is it possible to determine if data was encrypted by a specific public key?

This depends on the scheme that is being used.

In the case of a scheme that behaves like a random oracle: We could assume that the scheme that is used behaves as a random oracle, and that we are to infer by the ciphertext that some specific key was used. This would imply that we could actually get some information about the key, by knowing only the ciphertext (and not the plaintext). Namely if a specific key was used to encrypt the plaintext. This would however violate the assumption that the scheme behaves like a random oracle. So in the case of a random oracle the answer would be no.


Given the choice, it is preferable to use the block encryption operation of AES, since it often faster than block decryption (never slower AFAIK). For this reason, AES-CTR is defined to use the block encryption operation of AES exclusively; that's both for AES-CTR encryption and AES-CTR decryption, which are the same operation except for IV generation/input.

AES block encryption is faster than AES block decryption because:

MixColumns uses a matrix with smaller coefficients than InvMixColumns, thus is simpler to compute (that's particularly true for purely software implementations; hardware implementations sometime use the same number of cycles, including I believe Intel's AES-NI instructions).
during encryption, subkeys are needed in the order they are produced from the key, but during decryption that order is reversed, therefore on implementations (including hardware) that start decryption with the pristine key as input, some preliminary work is necessary before decryption can start (there's no known shortcut).

Here is for example a crypto library performance report (single-thread, software AES) showing speed differences.


Hard-core predicates: should the adversary be given $1^n$?

First note that it is not necessary for $B$ to guess the correct $n$. To see this, you can think of the PPT adversary $A'$ that on input  $(y, 1^{n-1})$ outputs $A(y, 1^n)$. The sole purpose of the input $1^n$ is to allow $A$ to run in polytime in $n$.

However, if the input (i.e., the output of $f$) to $B$ is of size, e.g., a constant $k$, then $B$ can not run an adversary $A$ running in polytime of $n$. But in this case it should not be problem for the following reason.

I assume $U_n$ here roughly means a $n$ uniformly random bits? In that case you have from $f$ being injective and pigeon-hole principle that with high probability (at least $\frac{1}{2}$) $|f(U_n)| \geq n$. I.e., $B$ will be allowed to run in polytime in $n$ at least on these inputs.

EDIT: Note that the above is slight sloppy and simplified argument. You do not strictly need $|f(U_n)| \geq n$, it could be smaller. You just need it to be large enough for $B$ to run in poly time of $n$.


A key point is that for group $G$ and any arbitrary $m \in G$, choosing a uniform $k \in G$ and setting $\hat{k} = k \cdot m$ gives the same distribution for $\hat{k}$ as just choosing it uniformly from $G$.
This is because:
$Pr[\hat{k}=k \cdot m] =Pr[k=\hat{k} \cdot m^{-1}] = {1 \over {|G|}}$
So in the reduction, when $A$ interacts with the challenge $<u=g^y,v=g^z \cdot m>$ for random $z$, $u$ is completely independent of $v$, and so they reveal no information over each other.
Notice that even though it's not a valid encryption scheme (because it's impossible to decrypt), the experiment is still well defined.


Question 2 can be easily answered. Yes, an attacker could easily overload this part of the system.

This may be the first time S sees A's public key. However, S makes sure the signature checks out, and registers A's new state provided that A's previous state is either older or non-existent.

An attacker can easily send their own public key instead of $A$'s key. Then sign with their own private key. The signature will, of course, be valid, so $S$ will accept it. If $S$ ties that key to the identifier for $A$ going forward, then future messages from the real $A$ would be blocked. Also, no $B$ will ever request a message with said key's fingerprint, so it will wait taking space in the message queue, leading to an easy way to fill the queue and stop any new messages from being processable.


Take SSH for an example: The server will always be listening for commands, so anyone who has the public key (easily obtained as I understand (I might be wrong)) can send commands to the server and it would appear as if the correct client had sent them?

You are confused indeed, but you are drawing a strictly correct inference here: the server's public key is of no use for the server to tell authorized clients apart from attackers. But it's not meant to do that; the server public key is meant to provide two things:

Allow the client to authenticate the server (so that an attacker can't impersonate the server);
Allow the client to bootstrap an encrypted channel with the server.

So what follows is that, in addition to its public key, the server needs some other mechanism to authenticate the clients.  The most common ones are familiar:

The server asks the client for a username and password
The user has their own public key registered with their account in the server (in most implementations, in their ~/.ssh/authorized_keys), and the client and server execute a challenge-response protocol to allow the client to prove they possess the corresponding private key.


Is it possible to encrypt the key by sender's private key and again encrypt it with receiver's public key by using RSA algorithm at sender end

It doesn't make much sense to "encrypt" with your private key, I suspect what you want to do is sign with a private key, which for RSA is essentially the same operation.
You definitely can sign a message with your private RSA key and then encrypt it with the recipients RSA public key. This is even common.
Obviously you want to use proper padding (e.g OAEP)

Note you can do this in either order, sign and encrypt or encrypt and sign.
Note public key operations are cheaper computationally compared to private key operations. If you encrypt and sign we can verify cheaply and not waste time decrypting unverified messages. If you sign and encrypt you can hide you identity If this is relevant.


How to show Hash-Then-Encrypt is not AE-secure

first one is simple as ${H_1(m)}$ leaks the information about the message in the ciphertext. So it is not CPA secure.

second one , the scheme will be under CCA. as @SEJPM mentioned attacker can modify the c1 such that new ciphertext c2 will be the result of ${H_2(c1)=c2}$, so ciphertext integrity is not preserved, required in AE.


How is a group element converted into a key?

I don't know the protocol, so I'm not sure.
It is a standard way of converting group elements (e.g. the shared value $g^{ab}$ you get after Diffie-Hellman) to keys. You don't need to worry about the specifics of the group when choosing a hash function, just use a cryptographic hash like SHA256.
It's hard to know what the difference between those two is without more context. You are certainly using the hash function to derive a key, but not all hash functions are also key derivation functions. Usually you talk about 'extractors' in the context of extracting entropy from a value, so in a sense the hash function is also an 'extractor' in that the hash is (probably) shorter than the value being hashed but contains (roughly) the same amount of entropy.


A question regarding next-bit predictors

[SEE UPDATE BELOW] This is a very interesting question. Basically what it means is that if there exists a next-bit predictor, then there is a canonical distinguisher $D$ that outputs the $k$th bit and does nothing else. This is a good distinguisher since the $k$th bit equals 1 with probability that is polynomially bounded away from a random bit. I find this intuitively appealing and was first surprised. However, it does make sense.
As a sanity check, let's see what would happen if on the extreme:
$$
Pr_{X\sim D}[X_k=1 \mid X_1X_2\ldots X_{k-1}] = Pr_{X\sim D}[X_k=0 \mid X_1X_2\ldots X_{k-1}].
$$
This would mean that $X_k$ is actually independent of $X_1,\ldots,X_{k-1}$ and is a random bit. In such a case, it is clear that $A$ could only predict the next bit with probability $\frac12$. As a result, I think that this could be proven in the contrapositive.
I won't do all of this here; there is good value in you working it out. In order to get the direction, I propose that you look at the proof of equivalence of next-bit unpredictability and pseudo randomness. One place to see this is Section 7.3.2 of this chapter on Pseudorandomness by Salil Vadhan.
Let me know if it doesn't work out from here.
==================================
I'm leaving the above for the didactic value, but I'm no longer sure that this is correct. The problem is the conditioning. In particular, once we condition on $X_1,\ldots,X_{k-1}$, then we are completely changing the probability space. (General recommendation - it's really easy to get conditioning wrong so stay away if you can. This was a recommendation given to me by my advisor. You can't always avoid it, but you need to be really careful.) In more detail, it could be that for \emph{many} given $X_1,\ldots,X_{k-1}$, the $k$th bit $X_k$ is polynomially biased away from $1/2$. The problem is that you don't know how to recognize the prefixes where this holds. Of course, this means that it can't happen with high probability (or a non-uniform distinguisher could hold some prefixes as advice). I think part of the confusion is what it even means to sample a full $X$ and then condition on $X_1,\ldots,X_{k-1}$. I think what you mean is that: for every $X_1,\ldots,X_{k-1}$, the probability of $X_k=1$ when the sample of $X$ has the given prefix of $X_1,\ldots,X_{k-1}$ is bounded away from $1/2$. I don't think this would be correct. If you mean something else, then it's worth thinking about.
I guess the important question is what you are trying to show and why, or possibly it's just understanding (which is good within itself).


Change a secret key in an embedded device

What's proposed is unsafe if used more than once: assume $\text{Sk}_1$ is (re-)established this way by sending $\text{RN}_1$; then, after compromise of $\text{Sk}_1$, $\text{Sk}_2$ is re-established this way by sending $\text{RN}_2$. The adversary can find $\text{Sk}_2$ as $\text{Sk}_1\oplus\text{RN}_1\oplus\text{RN}_2$.

Also, $\text{RN}$ does not seem integrity protected, allowing the adversary to play nasty tricks.

A better practice is to send a fresh $\text{Sk}$ protected by authenticated encryption with a dedicated Key Enciphering Key (having the role of $\text{SRN}$ here).


First, the passage you refer to is on page 55, 2nd paragraph. And it would also be great if you'd announce that figure 4.1 is actually in a different document ;-) took me quite a while to figure this out. Now to your question.

So, I assume you understand the paragraph? You have to note that a round here corresponds to $2^{(i-1)h}$ "whole tree rounds". Now, the paragraph only says that every "round" a new node on level $ih$ is not required anymore, every two rounds one at level $ih+1$, and so on. Figure 4.1 is a bad example because the root of a subtree is never stored and hence there is no node on the second internal level of the subtree to discard. However, ignore everything green and red in the picture and assume this tree of height 3 is our exist subtree. Then, in the first round node $n_1$ is not needed anymore. In the second round, node $n_0$ and node $n_{23}$ can be discarded. So, Gustavo was right.

Regarding the $A$... it is simply $a$, I assume this is simply a typo, occured when harmonizing the notation of the different papers. You see, in round $a$ you discarded $a$ pebbles at level $ih$, $\lfloor a/2\rfloor$ pebbles at level $ih+1$, and so on.


Simple example: Suppose you have a hash that is 136 bits but the last 8 bits are always 0.

Clearly it is not more secure than just the first 128 bits.

In practice it will be less obvious but it means that the 136 bit long output will be one of only $2^{128}$ different values.

The extra bits are required to guarantee 128 bit security and cannot be omitted.
To continue the analogy, assume that the 8 extra zero bits are mixed with the rest of the 128 bits. You simply don't know which bits to omit.

To give a possibly more visual, short example consider the following fictitious hash outputs:

$100, 110, 011, 010$

Since there are only 4 possibilities the hash could not have a security level greater than $2^2$. (You could simply attack it by guessing one out of the $2^2$ values.)

However, the output is 3 bits long and you cannot remove any of the bits. If you did you would have less than $2^2$ possibilities left.


Mitigating the effects of server-compromise in an end-to-end encrypted system

Trusted server

That's right.  There are several standard approaches to handling group key management with a trusted server:

Group key: Use a single group key known to everyone in the group.  Anytime someone is removed from the group, change the group key and update everyone who is supposed to still have access.  Use a symmetric key for the group key; this makes encryption and decryption efficient.
Individual keying, with server proxying: Give each person their own individual symmetric key, which is shared only with the server.  Each person has a secure connection with the server, secured with this key, and the server forwards messages (decrypting and re-encrypting).  This is a hub-and-spoke model, with the server responsible for determining who is allowed to see the messages.  When someone is removed from the group, the server will stop forward messages to them.
Signed list of group members: Have the server sign a list of group members, along with a timestamp.  For instance, each group member could be indicated by its public key.  It's important to include a way for the server to prove freshness of the signed list (e.g., include a timestamp in the signed data).  This solution is vaguely similar to what you sketched in your question, except you seem to have overlooked the need for a timestamp and a signature.  Clients will have to periodically poll the server to check for updates to the list of group members.

If you use public-key encryption to encrypt all messages between group membesr, this will be unnecessarily expensive/slow, because it would require all clients to use public-key encryption to encrypt each message, and require $O(n)$ public-key encryptions per message sent.  However, each client could exchange a symmetric key with every other authorized member of the group (using the public key provided by the server), cache this symmetric key, and use it for all subsequent messages, which will be more efficient.

Yes, this is a pain, but it's a necessary pain.

No, your solution isn't secure, for exactly the reason you mentioned: because the list of group members is unsigned, it can be modified by a man-in-the-middle.

All of these solutions require trust in the server.  That is unavoidable: it's part of your problem specification that the server determines who is authorized to be in the group.  Thus, a malicious server can just add himself to the group and read/modify all the traffic.  Once you start from a world where the server is empowered to decide group membership, you must trust the server.  There's no way to avoid trusting the server, if the server is empowered to decide who is part of the group -- in that model, there's no way to build a solution that doesn't involve trust in the server.

Untrusted server

The simplest approach is to have a single group leader who is in charge of group membership, and who has complete control over the list of people in th group.  The most natural model is that the group leader be the first person to create the group -- so the group owner is one of the members of the group, and controls who the other members are.

You can easily support that model, without trust in the server.  Simply take any of the three solutions above, but replace "server" with "the group owner's machine".

There are other approaches one could imagine -- e.g., once someone is in the group they can never be removed (revocation is impossible); or, all members must approve each group member and any member can kick anyone out of the group at any time -- but the usability consequences of those seem horrible, so I can't imagine they are going to be attractive.


Determining message given cipher-text and public key

This is called the common modulus attack.

Bezout's Identity says that there exists $x$ and $y$ such that $ax + by = gcd(a, b)$.

In our case we have $gcd(e_a,e_b) = 1$, so we can find $x$ and $y$ such that $e_{a}x + e_{b}y = 1$ (you can use the extended euclidean algorithm for this).

After solving for $x$ and $y$, you compute:

$C^xC^y\mod N$ to get $M$.

This works because $C^xC^y= M^{e_{a}x}M^{{e_b}y} = M^{e_{a}x + e_{b}y} = M$


Special-purpose witness encryption without multilinear maps

One obvious example would be the factorization problem, with the Rabin encryption system.

One way of stating the factorization decision problem is: given $x, M$, does there exist integers $y, z$ such that $1 < y < x$ and $yz = M$?  The witness would be the values $y, z$.

If we constrain the values of $M$ to be Rabin modulii (product of two prime factors, with both factors $3 \bmod 4$), then Rabin is provably equivalent to the factorization problem.  Hence, if you can decrypt, then you can produce a witness (as you can factor), and if you can produce a witness, then you can decrypt (as you can factor).