Indistinguishable encryptions in the presence of an eavesdropper

Your understanding is correct. There is no particular significance to $m_1$ being all zeroes, it is just a simple and convenient way to ensure that the inputs to $F_k$ will be all distinct, which is what we need in order to produce a pseudorandom string.


When NIST made the call for AES, they were trying to address short comings of DES that had a 56-bit key (64-bits with parity).  I got the following information from NIST while at the NIST 8114 conferences because I was complaining about having to keep 192-bit key compatibility in my SIMON hardware when no one would likely use it.

The summary:

In 1997, the idea was to double the key length (to 128-bits) and then double the key length again (to 256-bits).  The reason that 192 bits was there was because it was thought that an intermediate key length would be good for systems that couldn't handle the complete 256-bit length.  You need to keep in mind that at the time of specifying 128/192/256 bits, and algorithm had not yet been picked.  On 1997 hardware, 192-bits takes more time than 256-bits, and it was hoped that by having a larger key size the life of AES would be more than 20-years, unlike DES.

As mentioned in the comments, retrospectively, the 192-bit requirement was likely not optimal as pretty much no one uses it.  You have to include a 192-bit key option in your hardware cores for complete AES compatibility.  I had a bug in my netlist verification for AES-192 for 10 years, and I only found it recently, which really means... no one every uses AES-192.


Why BouncyCastleAesCbcBytesEncryptor is using a salt and an initialization vector?

In short; salt is used for Key derivation function together with the password. IV is used for CBC which must be unpredictable.

In details;

The document is sparse for the details. One can guess that is is for key derivation from the supplied password and salt instead of a key. So the initial guess was it is used for key derivation from the password. When we look at the source code;

public BouncyCastleAesCbcBytesEncryptor(String password, CharSequence salt,
            BytesKeyGenerator ivGenerator) {
        super(password, salt, ivGenerator);
    }

The super class is BouncyCastleAesBytesEncryptor and there

PBEParametersGenerator keyGenerator = new PKCS5S2ParametersGenerator();
...
keyGenerator.init(pkcs12PasswordBytes, Hex.decode(salt), 1024);

And form the documents;

  Generator for PBE derived keys and ivs as defined by PKCS 5 V2.0 Scheme 2. This generator uses a SHA-1 HMac as the calculation function.


Is there a standard for hashing a list of strings?

There are two ways of going about this:

create a hash tree (or, as it is only one deep, a hash list);
create a canonical representation of the strings;

For the first option you simply hash each string, and then hash all the resulting hashes. As the hashes should not have collisions, you can be certain that the resulting hash doesn't collide either.

In the other option you create a canonical hash. You've got three options:

use escape characters or bytes;
define the structure and size of the elements outside the strings;
a combined approach of the above.

The first approach I won't explain much. It consists of appointing an escape character and use that for structural information. So e.g. a single 00 byte is used to indicate the end of a string and all the existing 00 in the string are doubled. Disadvantage  of this approach is that your string may grow significantly.

As for the second approach: take a look at how ASN.1 would create structures using DER. You would use a "tag" to indicate a set, then the length of the set. Then you would put one or two strings in the set. Each string again has a tag and a length. This structure is completely canonical without requiring any escape characters (as DER is a binary encoding). This will only add a limited amount of overhead.

The combined approach is e.g. applied by Python: you can perfectly distinguish between ['string1', 'string2'], ['string1str', 'ing2'], as well as ['string1string2']. The language is already showing you how to encode lists of string!


What is the best way to encrypt form data from client end javascript and decrypt at server side Java?

If you are not using SSL/TLS on the web server, any man-in-the-middle can tamper with the javascript code as it is pushed from the server to the client. At that point, an attacker can disable any client-side protections you have added. So, without SSL/TLS, anything you do is basically useless.

Now, once you enable SSL/TLS on the server and force users to connect via that secure connection, all information is protected in transit already, so no additional protections are needed.

So, enable SSL/TLS on the server and force all connections to use that and you are good to go.


What does "a 15360-bit RSA key is the equivalent to a 256-bit symmetric key" mean?

The statement

  a 15360-bit RSA key is the equivalent to a 256-bit symmetric key

does not take into account quantum algorithms. In fact, it is based on a specific computation model.

It is just based on the fact that there exist sub-exponential algorithms for factoring and therefore you need longer keys than when using symmetric-key crypto where it is believed that there is no attack that is more efficient than exhaustive search.

I'm not 100% sure, but I think the NIST standard is based on a paper by Lenstra and Verheul (PDF).


AES Decryption followed by Encryption, will it produce the original text?

If you are talking about the AES block cipher acting on a one block message, then yes, with K being the actual 128/192/256 bit-key.  For a given key, the encryption E(message, key) and decryption D(ciphertext, key) functions are perfect inverses of each other.  You will always have both E(D(m,K),K) = m and D(E(m,K),K) = m by construction for any block cipher encryption/decryption functions operating on a one-block message m (for AES one block = 128-bits = 16 bytes).

That said in practice, if you use some well-written tool in a secure mode (like openssl aes-[128|192|256]-cbc) that internally uses AES as the block cipher for encryption/decryption this probably will NOT work, if you simply feed your tool a plain text message and ask it to decrypt said message with your key.

This is because your tool that uses AES as your block cipher will make various assumptions for you and does more than just apply AES to each block.  Specifically:

The tool will likely add proper padding to your message before encrypting it and will fail to decrypt if you are attempting to decrypt something that wasn't properly padded.  (Without proper padding their are attacks against multi-block AES encrypted messages).
On encryption, the tool may prepend the ciphertext with a block of a random initialization vector (IV); on decryption doesn't attempt to decrypt the zero-th block assumed to be an IV.   (Without an initialization vector, an eavesdropper can detect when similar starting messages are being sent and potentially tamper with them).
The tool also may include some sort of MAC to verify the data wasn't tampered with that will fail if you attempt to decrypt a plaintext message (as the plaintext message would not have a valid MAC that allows decryption to proceed).


How to "score" partially decoded ciphertext?

You are looking for a way to measure the similarity between strings, which is usually refered to as string metric. Now in your case one of the strings is the original plaintext and the other is a (more or less) similar string generated by encrypting and decrypting only partially correct. But actually, it doesn't really matter where the other string comes from, you just need to measure how similar they are.

However, there are many string metrics, and it's possible to adapt them to your specific needs. Here are a few common ones:

Hamming distance: Number of mismatching characters
Levenshtein distance: Number of insert/delete/substitute operations

There are countless other ways to measure the similarity between strings, and it has to be determined what is considered similar and what isn't.


How do I classify my RSA encryption strength?

The key length specified for RSA is the length of the modulus $n$ in bits. Thus, if you generate $n=p*q$ and get a 2048 bit modulus, your RSA encryption is 2048 bit.


Is secp256r1 more secure than secp256k1?

The main difference is that secp256k1 is a Koblitz curve, while secp256r1 is not. Koblitz curves are known to be a few bits weaker than other curves, but since we are talking about 256-bit curves, neither is broken in "5-10 years" unless there's a breakthrough.

The other difference is how the parameters have been chosen. In secp256r1 they are supposedly from random numbers, however, it is impossible to prove that's really the case. See e.g. these slides from Bernstein and Lange for an easily understandable treatment.

The Koblitz curve, on the other hand, has had its parameters chosen relatively rigidly. The post runeks linked in the comments has an explanation for why they were chosen.

So rather than saying one is more secure, I would say that the risks are different. If neither curve has backdoors or accidental weaknesses, both are secure. The few extra bits of security secp256r1 has won't matter unless you happen to own e.g. a moderately sized quantum computer that can just manage one but not the other. It would have been easier to backdoor the secp256r1 curve, but on the other hand, Koblitz curves as a class could be completely weak in some way not currently known.

I.e. which to prefer is somewhat subjective. If you don't like Koblitz curves but are afraid secp256r1 is backdoored, there's always the option to use some other curve designed according to criteria you like. (Though you cannot, of course, change what BTC uses.)


What are the randomness requirements for inputs to PBKDF2?

As PBKDF2 is a key derivation function, its primary purpose is to turn a secret, low-entropy value into a higher entropy secret key.
In your use-case, if the key is expected to be secret (I assume it is), then using only publicly known data associated with the user will result in a key that anyone with access to the PBKDF2 parameters can generate.
That said, depending on how you intend to use the keys, if you intend to store them or generate them on the fly, etc. things could potentially change, but you would need to be careful of the fact that the output of PBKDF2 is effectively non-secret if you're solely using non-secret inputs.
The inputs don't necessarily have to be random (most passwords aren't, strictly speaking, random) but it should be secret.  Remember that in general with key derivation functions you are trying to trade off the time you spend generating the key with the time it would take for someone to brute-force all possible candidate inputs for that key.  So if the value is public, and even something directly associated like the username, they're not going to spend much more time figuring it out then you spent generating it.  But if they have to guess every allowable password, the time taken to guess the input (and therefore be able to recreate the key) should hopefully be increased to the point that the resources required of the attacker would make the attack cost-prohibitive for what you're protecting with these keys.
How that cost-benefit analysis works out for your case is up to your risk assessment which should lead into your choice of PBKDF2 parameters, or even decision to use that algorithm at all, and your requirements of what is used as an input (e.g. what types of passwords are allowed to be used).


Securing Data via secret key that must be revealed later

If I understand you correctly,
you want to set up a system such that

Alice stores encrypted data on Ted's servers
Some event occurs that tells Ted to do something.
Sometime before that event, Alice has disappeared and becomes unable to perform any other steps in the protocol.
Everyone wants Bob to recover the plaintext of Alice's data after the event.
Ted is never able to recover the original plaintext. (In other words, this is a "host-proof" protocol. See host-proof for many related questions and answers).
Bob is not able to recover the original plaintext before the event, only after Ted cooperates by doing ... something.
Bob doesn't need to actively communicate with Bob or Ted or even know Alice exists before the event.

It seems clear to me that Bob needs to know (or be able to find out) something that Ted doesn't know. If Ted hypothetically knows everything that Bob knows, then by the time Bob receives a message from Ted and has all the information needed to decrypt the data, Ted has long before that time already has all the information needed to decrypt the data, which means that hypothetical protocol fails to be host-proof.

It also seems clear that we must trust Ted to actually send something to Bob after the event.
If hypothetically both Alice and Ted refuse to communicate after the event, then Bob won't learn anything that he doesn't already know, and therefore either Bob has long before the event already had all the information he needs to recover the plaintext, or else he never is able to recover the plaintext -- both undesired.

Off the top of my head, one possible approach could be:

Ted and Trent: two trusted hosts

For each document, Alice generates a random symmetric key, encrypts the document with that symmetric key, and stores the resulting encrypted document on Ted's server or Trent's server or both.
For each encrypted document, Alice encrypts the (symmetric) key used to encrypt that document using a one-time pad. This splits the key into 2 pieces -- an encrypted symmetric key, and a piece of one-time pad that can later be used to decrypt it. (This is "trivial secret sharing". Any other secure form of secret splitting would also work. Other forms of secret splitting might work even better).
For each encrypted document, Alice stores one piece of the split key on Ted's servers and the other piece on Trent's servers, but never sends all the pieces of the split key to any one person.
After the event, both Ted and Trent send all data they got from Alice to Bob. (In principle, Ted and Trent could send all the encrypted documents to Bob ahead of time, and send either one part of the split key or the other -- but not both -- to Bob ahead of time).
Once Bob receives the encrypted version of a document and all the pieces of a split key for that document, Bob combines the split key to recover the original symmetric key, then uses that symmetric key to recover Alice's plaintext document.

Given the initial constraints, I don't see any way around trusting Ted not to reveal some information to Bob prematurely.
This protocol has the additional weakness of trusting Ted not to (ever) reveal information to Trent, and also vice-versa.


Is exposing a constant IV an easy target to attacks?

To use CBC mode, you'll want to get a new, randomly-generated IV before each message encryption.  As long as you do this, you shouldn't have to worry about issues like how many times the same ciphertext is read with the same IV.


One possible solution is to use base conversion, and use the resulting "digits" of that base as index in the dictionary.

As that's probably a bit too abstract, so let's use some pseudo-code:

words = []
left = hexToNum(hash)
base = size(dictionary)
while (left > 0) {
    wordIndex = left % base
    word = dictionary[wordIndex]
    words += word
    left = left / base

The hash is treated as a positive number. This number is then converted to a number of digits using the size of the dictionary as base. Each "digit" (which is really just another large number between 0 and the dictionary size) is treated as index into the dictionary. Then we just perform a simple lookup and concatenate the words found.

As the left variable has a very big number value, you might have to use a "BigNum" library (a 64 bit integer would be too small). Most language or cryptographic API's will supply one. To speed things up a bit you might want to look for a function that performs divide and remainder in a single step, because that will incur fewer CPU operations than doing the division and remainder calculations separately.

As mentioned in the comments, there is no PRNG required. A PRNG is useful for seed expansion, but that doesn't seem required; only just conversion seems required. As the hash already is well distributed you can use the leftmost bytes of the hash to use fewer words.


How does Permutation and Substitution work?

The concepts here are diffusion and confusion, the goal of diffusion is to spread the influence of one bit over all bits. The job of confusion is to obscure the relationship between input and output.

S-boxes confuse (transform series of bits into different bits), P-boxes diffuse (shuffle bits around).

S-boxes need to have certain properties to be secure, they need to be non-linear to a degree where they can't even be linearly approximated. Given any two possible inputs into the box the difference in input must not correlate with difference in output.

Consider some input going into some number of S-boxes, it has changed drastically. But now consider that input being mixed (XOR) with the key before going to the box, it now changed in a very different way. If all you do is shuffle your entire function is linear and you can just build a matrix to represent it, then it's broken trivially.

In practice you apply shuffling and S-boxes multiple times (rounds) with multiple keys (derived from a master key).


What they are trying to say that an effective way to multiply $a$ and $b$ in $GF(2^8)$ is to first check if either $a$ or $b$ are zero (if either are zero, the result of the multiplication is zero), and if neither are zero, then:

$$a \otimes b = E( L(a) + L(b) \bmod 255 )$$

where $E$ and $L$ are lookups in the ETable, LTable given, and the addition is over the integers (and not addition in the $GF(2^8)$ field).

There are more mathematically elegant ways of expressing it; however this is just about the most efficient way to implement it on a standard CPU.

However, this has doesn't have that much to do with AES; yes, AES does computation within $GF(2^8)$, however it never requires us to multiply two variables.

What the MixCollumn step asks for is multiplication by the fixed values 1, 2 and 3.

Now, computing $1 \otimes x$ is easy; $1 \otimes x = x$

Computing $2 \otimes x$ is only slightly more involved; because AES uses a polynomial representation of $GF(2^8)$, this can be simplified by shifting left by one, and then xor'ing the fixed value $0x1b$ if the original msbit was one; in a C-type notation, $2 \otimes x$ would be the value:

((x<<1) & 0xff) ^ (x & 0x80 ? 0x1b : 0x00)

Once we can compute $2 \otimes x$, computing $3 \otimes x$ is easy; $3 \otimes x = (2 \otimes x) \oplus (1 \otimes x) = (2 \otimes x) \oplus x$


The usual mode for disk encryption is XTS (let's say the mode suggested by the NIST). AEAD cipher seems to be promissing but typically with the GCM you will have also to store an authentication tag per encrypted block which may lead to a complex implementation (but interesting). I believe that regarding at least integrity, there exist "new" file systems which handle this (to be check on linux side).


Can cryptocurrency mining devices be used for cryptanalysis?

Practicality: Using a bitcoin miner for cryptanalysis would at the very least require you to write very low-level custom code. Indeed, depending on the precise hardware/software split used by the miner, it might well require modifying the actual hardware to facilitate your cryptanalytic attack. Anyway, let's suppose someone could 'convert' one. What would this mean?
 Well, if someone could convert a bitcoin ASIC into a viable cryptanalysis box, then you can bet the ASIC companies would just go ahead and produce them directly.

It is probably reasonable to assume that 'groups actively involved in cryptanalytic attacks already use some of the best hardware available, so in practice a converted miner would still probably leave you behind the curve. Anyway, supposing it did, your question would boil down to:

What would happen if the 'effectiveness'$^{[1]}$ of cryptanalytic equipment suddenly advanced by an order of magnitude?

Most good crypto is either believed to be well outside the bounds of brute force (eg see these answers about AES, RSA), even when we make very generous assumptions about an adversaries computational power. As such, even relatively significant improvement in cryptanalytic equipment (which is what your question suggests) will make a negligible difference in these problems.

Notes:

We assume 'effectiveness' has some appropriate meaning for the problem in hand, eg cost/size/speed etc


If you are using the full HKDF each time, you could possibly save time by only using the Extract portion once and Expand once per derived key. That could even halve the total time taken, if you had a worst case situation.

Another speedup possibility within HKDF is to use another hash. Either a faster hash or one that matches the required key length better. For example, if you are generating a 256-bit key you would likely not want to use SHA-1 even though it is faster than SHA-256, because you would need two serial iterations.

Depending on the use case, you might also want to look into using KDF1 or KDF2, which are faster hash-based KDFs. They are defined in ISO18033, but KDF1 is also in RFC 3447 (appendix B.2), under the name MGF1.

However, as explained in the HKDF paper (pdf), the Expand scheme could work with any PRF. That means that for best performance you could roll your own version by replacing HMAC with a block cipher that you have in hardware (e.g. AES-NI on some new CPUs), since secure block ciphers are indistinguishable from a PRF up to the birthday bound.


Using the -k option, you can specify a password. Passwords are not really encryption keys, so OpenSSL uses a key derivation process to turn the password into an encryption key. It turns out by default OpenSSL uses a salt in that derivation process (which is why you see Salted__ in the output, which is a magic to indicate that the next 8 bytes are the randomly generated salt). The ciphertext only starts from byte 16 onwards.

If the salt changes, the encryption key changes. If the encryption key changes, the ciphertext changes. By default OpenSSL generates a new random salt every execution. That is why you are seeing the changing ciphertext.

To turn this off you can add -nosalt. This is fine for testing purposes. As stated in the OpenSSL docs "This option SHOULD NOT be used except for test purposes or compatibility with ancient versions of OpenSSL and SSLeay". Otherwise your ciphertext is deterministic which can lead to cryptanalysis and a broken (i.e., insecure) system.

Alternatively -K lets you directly specify a key value in hexadecimals, skipping the (OpenSSL specific) password key derivation - and therefore the salt generation - entirely. You also need to specify the IV using -iv in that case. The IV should be random to achieve security in CBC mode if the key is reused, but the generation of the IV is left to the user.


How can we encrypt a file to be just readable (and not writable) after decryption?

A "file" is a convenient metaphor for a sequence of bits on a specific file system. Your copy of foo.bar is not the same as my copy of foo.bar, even if they contain the same data. And short of exploiting a bug in my system (illegal in many jurisdictions) there is no way for anyone else to dictate what I do with my copy of files. So in general, no, this is not possible if I have control over the system the file is on. Conversely, if you control the hardware, software and I/O devices of a system you can give me access to look at the contents of the file but not change it in any way.

However, if the goal is to preserve authenticity the solution is readily available: Use a hash-based cryptographic signature and ensure that anyone or anything that reads the resulting file verifies that the signature belongs to the right person.


If you need something that already exists, have a look at the advanced Crypto software collection and specifically cpabe — which implements ciphertext-policy attribute-based encryption scheme that uses C and PBC library for pairings.


Is it possible to use an S-box similar to the one used in DES in AES? How would this work?

DES is a Feistel cipher that doesn't require the $F$ function to be reversible, where the S-Boxes are used. DES has a non-reversible $F$ function in which the 8 S-boxes $S:\{0,1\}^6\to \{0,1\}^4$ is used.
AES is based on Susbstition Permutation Network (SPN) where everything must be reversible. AES is using S-boxes $S:\{0,1\}^8\to \{0,1\}^8$. Therefore it is not possible to use the DES Sboxes in the AES.
Besides the functionality, even if we could interchange them, that would require to analyze, too.


Is it possible to have self-authenticated message?

One solution is to use the choice of which equivalent message you send as a way to encode a MAC value.

Take a "base message", where e.g. each word choice is the alphabetically first one. (Or some other known rule.)
Calculate the MAC for that: MAC(key, message). The MAC should be $m$ bits or less. HMAC, possibly truncated would work fine.
Encode that MAC value in the word choices, so that each bit chooses one of the words.

The recipient would need to know the possible word changes (synonym pairs). They would first use the rule to derive the same base message, then compute the MAC using the shared key, and finally check that the same value is encoded in the word choices.

A similar algorithm would work for public key signatures if you had a sufficiently long message. The recipient would decode the signature value from the word choices and use normal signature verification with the base message and a public key.


Why is the Pedersen commitment computationally binding?

The misunderstanding you have is with the sentence "the sender is able to compute an $r'$..."

Actually, that's not true, and the "information theoretically hiding" bullet point does not state that.  What it does state is that, for every $m'$, there exists an $r'$ that satisfies the relation; however it does not imply that a real sender can find such a value.  In fact, the "computationally binding" bullet point specifically states that a real sender cannot (assuming he is unable to solve Discrete Log problems).

Instead of talking about the senders capabilities, the information theoretically hiding bullet point talks about the receiver; that is, even if the receiver had infinite computing power, he still cannot get any information from the commitment as to what is committed to (because all possible values are equally likely).  Now, the Pedersen commitment scheme is asymmetric in this (because a computationally unbounded sender can change commitments); on the other hand, it turns out that a commitment scheme between two computationally unbounded parties is actually impossible; the Pedersen scheme is as close as we can come.


This can be done with RSA where k1 and k2 are encryption keys and f is  multiplication modulo the totient of the public modulus.
The last property, that knowledge of other pairs $k_2'$ and $k_{new}'$ does not reveal $k_1$ is satisfied by using a different modulus for each pair generated.


What exactly is a quantum key distribution network for?

It seems that the initial diagram is correct.  A QKDN is exactly this:-

and it relies on two pieces of kit, a quantum key generator and an encryptor device. A 256 bit AES key is generated and shared between Alice and Bob via the BB84 protocol running over dedicated fibre optic cable. The key itself is created via a true random number generator (perhaps based on the phase interference of a laser beam).

The keys are then passed to the encryptor devices which operate AES between themselves over conventional channels. So actual business data flows only between the encryptor devices, over common networking technology and not the quantum machines. The thing that ensures the security of the transmitted data is that the AES keys only have a life span of one minute.  They're then replaced.  That's why all that quantum data is transmitted.  AES keys are constantly being replaced before anyone could even attempt to break them. Clearly some of the numbers here are dependant on individual networks and hardware.

And QKDNs are used in anger all over the world including government and commerce. The first was deployed in Switzerland to secure their frequent public votes /elections. And there are some interesting future developments that won't require fibre optics at all, and some that will ensure secure key exchange over infinite distances.

All of this is to be found on YouTube.  Don't laugh.  It's a presentation by Kelly Richdale, head of quantum randomness at ID Quantique, a market leader in QKDNs.   There is also an unbiased and fair summary of QKD from  the European Network and Information Security Agency (ENISA) here.  It's concise but rather dated (Nov 2009), so a lot of the open issues should have been resolved or are in the process of being so.


AES transformation can be viewed as a sequence of invertible transformations each processing only a small part of the state. All these transformations would be even, and so is the entire AES for any key (see also this question).


Cryptanalysis Affine Cipher: Brute-Force Search Vs. Meet-in-the-middle

I don't know what you mean by a 'meet-in-the-middle' attack.  The obvious way to attack this cipher is a known plaintext attack, that is, encrypt any two distinct plaintexts $x_1, x_2$ (and hence two encryptions), getting their encryptions $y_1, y_2$ :

$y_1 = (a x_1 + b) \mod m$

$y_2 = (a x_2 + b) \mod m$

and solve for $a, b$ as:

$a = (y_1 - y_2) (x_1 - x_2) ^ {-1} \mod m$

$b = (x_1y_2 - x_2y_1) (x_1 - x_2) ^ {-1} \mod m$

Now, as for your side question of what $a^{-1}$ means, well, that is the modular inverse of $a$; if we claim that $c = a^{-1}$, this is equivalent to claiming that $a \cdot c = 1 \mod m$

The modular inverse of $a$ can be found efficiently (given a, m) by the Extended Euclidean Method


Seeking key stream as way to reuse a key

To address your bullet point directly, yes this will work for all generic key streams that only produce a sequence dependent solely on a key.
 However these are some real world problems.

Your scheme requires perfect synchronicity between a single pair of sender and receiver.  Otherwise the stream position will get lost as that is not part of the transmission.
You've specifically mentioned attackers.  Receipt of an attackers message will throw out the stream position and you'll never recover it without careful tracking of the number of characters received. Perhaps not even then.
Similarly, anything other that a single pair of sender /receiver will make stream position recovery extremely difficult. In the long term, impossible /impractical.
Salsa20 /ChaCha20 overcome this problem by use of a nonce that resets the key stream to an identifiable position.
If you don't exchange keys, how can new members join the party?

Key exchange is a part of cryptography and is well addressed.  Key stream positioning is the role of a nonce, and well discussed.


Actually, the document talks about Rijndael, not AES.

Aren't Rijndael and AES that same?  Well, not precisely; Rijndael is specified with a set of parameters that AES does not support; how example, how it works with different block sizes.  AES is defined only with a block size of 128; Rijndael supports a set of different block sizes.

That is where your confusing is coming from; the varient shift-rows are used if you have a block size of 256 bits; since AES never has a block size of 256, those shift rows are never used.


As for the algorithm, you have two choices: The quadratic sieve and the general number field sieve.

If you want to implement the factorization yourself you want to use the quadratic sieve, as a good implementation of the GNFS is really hard.

However, if you're willing to use pre-made tools using GGNFS and msieve (together) is your best option. Msieve provides good polynomial selection (first step) and GGNFS provides the efficient second step, while msieve takes over the last step, you may want to refer to this guide for the exact how-to.


Right way to hash elliptic curve points into finite field

For $H_1$ it depends on a bit on what characteristics you require of your hash function. There is a thorough analysis from Brier et. al (https://eprint.iacr.org/2009/340.pdf). Here's the basics:

Method 1: One way to hash from $\{0,1\}^*$ to $E(F_p)$ is to first hash to $Z_p$ and then multiply by the generator. Universal Hash Functions as first described by Carter and Wegman (https://en.wikipedia.org/wiki/Universal_hashing) provide a simple mechanism to obtain an indistinguishable distribution. Given $q \geqslant p$ and random values $a,b \in q$ this can be constructed as:

$$H_{CW_1}(x) = ((a_1x + b_1) \text{ mod } q) \text{ mod } p$$

$$H_u(x) = H_{CW_1}(x)*G$$

$H_u$ hashes from ${\{0,1\}}^*$ to $E(F_p)$. Because $H_{CW}$ is uniform (i.e. the probability of a collision is $1/p$) in $Z_p$ it follows that $H_u$ is uniform in $E(F_p)$. This could be sufficient for some uses, however it should be noted that $H_{CW}$ is the discrete logarithm of $H_u$. If your use of a hash function depends on security of the ECDLP for the result then this is not sufficient.

Method 2: The second method, assuming a short Weierstrass represenation with $p \equiv 2 \text{ mod } 3$ is to use Icart's function to map directly to $x,y$ coordinates which are parametrically constrained to be on the curve $E(F_p)$. Icart's function $f(u) = (x,y) : u \in F_p$ is defined by:

$$v = (3a -u^4)/6u$$
$$x = (v^2 - b - u^6/27)^{1/3} + {u^2}/3$$
$$y = ux + v$$

Extending this to map $\{0,1\}^* \rightarrow E(F_p)$ is as simple as:

$$H_{CW_2}(x) = ((a_2x + b_2) \text{ mod } q) \text{ mod } p$$

$$H_I(x) = f(H_{CW_2}(x))$$

$H_I$ hashes from ${\{0,1\}}^*$ to $E(F_p)$. The derivation $(x,y)$ using Icart's function provides no gain on finding the discrete logarithm of $f(u)$, so it could be sufficient for some applications, however $f$ only maps to a distinct subset (about 5/8) of the points of $E(F_p)$, so it is not sufficient for appilcations which require a uniform/indistinguishable mapping.

(Note: there are alternate implementations to Icart's function explained in Brier et. al. which can be used for other curve equation forms and for $p \neq 2 \text{ mod } 3$)

Method 3: If you want something which is uniform and ECDLP-secure then you can simply combine the above two methods:

$$H_{us}(x) = H_u(x) + H_I(x)$$

For $H_2$ you likely want to securely hash the full string representation of the point (as doing something like using the x coordinate would have a trivial hash collision of $-P$) to $\{0,1\}$ and then reduce that to $F_p$. Something like:

$$H_{CW_3}(x) = ((a_3x + b_3) \text{ mod } q) \text{ mod } p$$

$$H_{Z_p}(P) = H_{CW_3}(SHA256(P_x | P_y))$$

Which will produce a secure, uniform result in $Z_p$


What is the recommended format/notation for crypto design?

TL;DR: Find the most important specification that is of the same type as the one you want to write and use its style for yourself, chances are, other people also have read it.

There is a myriad of ways to specify a crypto protocol / design.

However, there are four things that you really should take into consideration when writing a crypto-related specification.

The most important one first: Fancy pictures. A good picture (as in: a colorful graphic or even ASCII art) says more than a thousand words and can greatly help people quickly understand the essentials of what your protocol is all about. Examples of ASCII art can be found in the actual TLS specification and fancy picture can be found outside of that.
Data Encoding: ASN.1. If you want to submit data with your protocol, you need some structure within it and for notating structured data, nothing beats ASN.1 in terms of being deployed and well-understood. You should really consider using ASN.1 for specifying data structures, to which you only need to apply primitives afterwards (like "sign it!"). Don't forget to define encoding rules (like BER and DER) though. An example for an extensive use of ASN.1 would be CMS, the basis of S/MIME.
Protocol summary: The Handbook of Applied Cryptography (HAC) style. While fancy pictures are valueable, a written out summary is also very valueable and I in my experience the HAC does a really good job at writing them down. It consists of four parts: a) write down the TL;DR of the protocol, e.g. what does it do? b) write down the setup phase of the protocol c) write down the protocol messages as can be seen on the wire (encoding is implicit here, possibly using $\LaTeX$) and d) write down the protocol actions happening between each step. This summary should give everybody a good oversight, of what is done when and the notation also allows you to associate keys, IVs and other things with specific function calls. As a bonus for this method: Many serious cryptographers have read the HAC or have a copy of it very close at all times. Protocol 12.20 is an example for this style (PDF).
The details: The TLS specification style. When you want somebody to review / implement your full specification, this person likely has some experience in doing such things and usually usually has read the TLS specification at some time before, so using its notation is a no-brainer. Additionally, TLS also deals with a bunch of keys and the specification is clear enough to distinguish what to use when, by using things like digitally-signed struct.


Cipher Block Chaining - How do you change the plaintext of all blocks?

If this is all you have, then I think you can't.
You can easily get 1st and 3rd block.
Change the 2nd ciphertext to get the desired result of 3rd block and change IV to get the desired result for first.
But changing a cipher text block means you no longer have the results of the block cipher decryption.

If you have however limited access to a decryption oracle then you will just need to make trial decryption of two blocks. The ciphertext of block 2 which makes the 3rd block what you want. And then given it,  you choose the ciphertext for block 1 which you send to decryption in order to calculate required IV.


I think the adjugate matrix is the transpose of the cofactor matrix.

(Btw, I do not think this is a crypto question.)


Elliptic Curve SSL performance: ECDHE and/or ECDSA?

It is hard to give a precise percentage as you expect because performances depend on the hardware platform. But let's get into the subject.

The only difference between TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA384 and TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384 is the signature algorithm.

Whatever, one will have to generate an ECC key pair on the fly in order to perform an ECDHE. Then, this key pair will be signed using the certificate private key. If the certificate contains a RSA public key, then the generated ECC public key will be signed using RSA. Otherwise (i.e. if it contains an ECDSA public key) it will be signed using ECDSA. Also note that one will have to verify the peer signature on top of generating his own.

So your question is equivalent to comparing RSA to ECDSA, I suggest you to take a look at How do RSA and ECDSA differ in signing performance? and Signatures: RSA compared to ECDSA.


Can I use M1 straight away and get rid of IV in Merkle–Damgård?

TL;DR: A simple reason why we use the IV is to mitigate second preimage attacks.

This is the typical Merkle–Damgård construction: you split your messages in blocs of $k$ bits (input size of the compression function).

    M1         M2 ...     Mn
    |          |          |
    +--|\      +--|\      +--|\
       | \        | \        | \
 IV ---|  |-------|  |-------|  |---  Hash
       +--+       +--+       +--+

your proposal is the following :

    M2         M3 ...     Mn
    |          |          |
    +--|\      +--|\      +--|\
       | \        | \        | \
 M1 ---|  |-------|  |-------|  |---  Hash
       +--+       +--+       +--+

This assumes that the message is longer than $k$ bits! What if the message is shorter ? Well you get the following because you don't have an IV to compress with.

 M1 ---  Hash

Also this idea of using $M_1$ as an $IV$ assumes that the inputs of your compression function have the same size e.g. if you take $f(x,y) \to h$ where:

$\texttt{sizeof}(x) = 128 \texttt{bits}$ and
$\texttt{sizeof}(h) = 160 \texttt{bits}$

This implies that  $\texttt{sizeof}(y) = 160 \texttt{bits}$. Therefore the use of an IV is encouraged unless you want to manage a padding for the first input...

What if we have a fixed last bloc compression ?

Such that:

    M2         M3 ...     Mn ...     LB
    |          |          |          |
    +--|\      +--|\      +--|\      +--|\
       | \        | \        | \        | \
 M1 ---|  |-------|  |-------|  |-------|  |---  Hash
       +--+       +--+       +--+       +--+

And in the case of very short messages:

    LB
    |
    +--|\
       | \
 M1 ---|  |---  Hash
       +--+

In the end don't you agree that this is the same has having a fixed first block, also called an IV ? You still need to save this value. Whether it is at the end or at the beginning, it is needed.

A Second Pre-image attack

Quick reminder:

  Given an input $m_1$ it should be difficult to find another input $m_2$ such that $m_1 \neq m_2$ and $hash(m_1)=hash(m_2)$. Functions that lack this property are vulnerable to second-preimage attacks.

Feeding directly $M_1$ instead of the IV whatever the construction above (with or without a fixed last block) leads to a second-preimage attack:

Let $M_1$ such that $M_1 = a || b || c || d$ where $||$ is the concatenation and $a,b,c,d$ are of the right size. We pose $H(a || b || c || d) = h$.

    b          c          d
    |          |          |
    +--|\      +--|\      +--|\
       | \        | \        | \
  a ---|  |---h'--|  |---h"--|  |---  h
       +--+       +--+       +--+

Notice that we have $h'$ and $h''$ such that $h = H(a||b)$ and $h'' = H(a||b||c)$.

What happen if we compute $H(h'||c||d)$ or $H(h''||d)$ ?

   c         d
   |         |
   +--|\     +--|\
      | \       | \
  h'--|  |------|  |---  h
      +--+      +--+

    d
    |
    +--|\
       | \
 h'' --|  |---  h
       +--+

In both case you will get $h$ which leads to:
$$\begin{align*}
H(a || b || c || d) &= h\\
&= H(h' || c || d)\\
&= H(h''||d)
\end{align*}$$

Thus we have a collision through a second preimage attack (note that the compression function may be perfectly secure!).

How to solve this?

Multiple solutions exists:

Use an IV.
Encode the length of the input in the last block.
add a domain separation encoding at the end of each block.

Solutions has been discussed in the following paper (see section 8:  Implications for sequential hashing).


Is AES + RSA Encryption of individual log entries with the same key but different IVs secure?

Yes that would work; that's exactly what the IV is for. In this case the IV is really required to obtain confidentiality over multiple log entries. Note that public key operations are relatively fast for RSA (but nowhere near so fast as AES encryption, generally).

Mind though that there are many other possible leaks of information: size of ciphertext, time of logging, change of encrypted AES key (i.e. change of run). If those leak any info depends on you.

Also note that encryption by itself does not allow to detect change, duplication, removal etc. So you should make sure that this is acceptable to you as well. Signatures generation and sequence numbers can be part of a solution to create a cryptographically secured, auditable log file.


According to Handbook of Applied Cryptography (15.3.2, ii), ANSI X9.9 (which SEJPM mentioned in the comments but I have no access to) defined CFB-MAC only as a compatible alternative to CBC-MAC:

The X9.9 MAC algorithm may be implemented using either the cipher-block chaining (CBC) or 64-bit cipher feedback (CFB-64) mode, initialized to produce the same result (see Note 15.1).

With a segment size equal to the block size (so 64 bits with DES) and using the first message block as IV, the two are indeed equivalent. So this case of CFB-MAC clearly has all the properties of CBC-MAC.

However, the first definition of CFB MAC seems to be from FIPS 81 (DES Modes of Operation, see Appendix F):

A MAC may be generated using either the CBC or the CFB mode. [...]
In CFB authentication, a message is encrypted in the normal CFB manner except that the cipher text is discarded. After encrypting the final Kbits of data and feeding the resulting cipher text back into the DES inputblock, the DES device is operated one more time and the most significant M bits of the resulting DES output block are used as the MAC.

The example shows 8-bit CFB MAC using an IV, so clearly it was defined for arbitrary CFB modes.

What remains unanswered is how the security compares to that of CBC-MAC when segment size differs from the block size. However, the use of segments is somewhat historical anyway, so it is only a curiosity.


It's generally strongly recommended you use an existing library for your crypto, instead of trying to reimplement it.  One big advantage of a widely used existing library is that it's been improved over time to deal with new threats.  You may be aware of timing attacks as a current weakness, but these libraries have already solved those problems and many others, and fixed them.

OpenSSL is written in C, widely used and trusted, and could meet your needs.  Cryptlib is distributed under the Sleepycat license (sort of compatible with the GPL) and is also written in C, and has a paid support team.  GnuTLS is LGPL, if you really want GPL compatibility.


What is the advantage of using the socialist millionaire protocol to authenticate vs HMACing some random number?

The problem with the HMAC-based solution you drew up is if the shared secret $s$ has low entropy; for example, it's actually a password that could conceivably be in a dictionary.

In this case, someone could listen to the exchange $r_1, \operatorname{HMAC}(C \mathbin\| r_1, s)$, and go through his dictionary of possible values of $s$, and see if any one of them makes the HMAC be the expected value; if so, he can MITM (or just pretend to be either Alice or Bob).

If this is a possibility, it's generally a good approach to use a Password Authenticated Key Exchange; this is a protocol that solves the socialist millionaire problem, and also generates a secret value which is the same on both sides if both sides have the same password.  This secret value is useful because it can be used to derive keying data; then can be used to prevent MITM attacks after the PAKE protocol has completed.

Now, one thing that a PAKE protocol can't prevent is someone making a guess at the shared secret $s$, and attempting to log in using that value -- if his authentication attempt is successful, he knows that he guessed correctly.  What PAKE can do is prevent any more efficent approaches; to test 1000 possible passwords, the attacker would need to attempt 1000 authentication requests.

On the other hand, if you have a strong $s$ which is immune to a dictionary attack (for example, it's a 128 bit random number), and you don't care about Perfect Forward Secrecy (which a PAKE will also provide), then a PAKE is overkill -- your simpler approach using HMAC may be preferable (and, don't forget, you would need to bind the rest of the conversation with the authentication exchange, such as generating a shared key based on $s$).


finding second pseudo preimage faster than brute force

For MD5, it is only known for the first (pseudo) preimage it is given by Yu Sasaki and Kazumaro Aoki in 2009

Finding Preimages in Full MD5 Faster than Exhaustive Search

In this paper, we present the first cryptographic preimage attack on the full MD5 hash function. This attack, with a complexity of $2^{116.9}$, generates a pseudo-preimage of MD5 and, with a complexity of $2^{123.4}$, generates a preimage of MD5.

In the pre-image attack, given a hash function $H$ and a hash value $h$, we try to find $x$ such that $h = H(x)$, In the second preimage attack we are given $H,x,h$ with $h = H(x)$ and we need to find another $x'$ such that $h = H(x')$.
If we can execute a pre-image attack, then we may carry it into a secondary pre-image attack. First, execute a pre-image attack, if we find $y \neq x$ than we are done. If not, continue the search. If brute-forcing, just continue, if a special attack, change the parameters and/or continue to find another.
A similar idea can work for the pseudo secondary preimage attack, too. I've not seen an example on MD5. Usually, the first pseudo preimage attack is extended to secondary pre-image attack. Like done on Gost hash function
A (Second) Preimage Attack on the GOST Hash Function
Note: pseudo-preimage is also called free-start target attack.


Zero-Knowledge proof with the paillier cryptosystem

Found an implementation here: https://paillier.daylightingsociety.org/Paillier_Zero_Knowledge_Proof.pdf


Proving property of Modified Rabin Signature

In short words: when you compute things modulo $n = pq$, you are really computing things simultaneously modulo $p$ and modulo $q$. That's the gist of the Chinese Remainder Theorem. So to prove that $a = b \pmod n$, you just have to prove that $a = b \pmod p$ and $a = b \pmod q$.

Modulo $p$, for any $x$ that is not a multiple of $p$, $x^{p-1} = 1 \pmod p$ (this is Fermat's little theorem). Therefore, $x^{k(p-1)} = 1^k = 1 \pmod p$ for any integer $k$. Now, $p$ and $q$ are big primes, so they are odd. It follows that $q-1$ is even, therefore $(q-1)/2$ is an integer. So $x^{(p-1)(q-1)/2} = 1 \pmod p$. The same holds modulo $q$ for the same reason. By the CRT, you get the result modulo $n$.

Note that while Rabin's cryptosystem is defined with $p = 3 \pmod 4$ and $q = 3 \pmod 4$, these properties are not necessary to demonstrate that $x^{(p-1)(q-1)/2} = 1 \pmod n$. It also works when $p = 1 \pmod 4$ or $q = 1 \pmod 4$. The only requirement is that $x$ is relatively prime to both $p$ and $q$, which is exactly what $\mathrm{gcd}(x,n) = 1$ means.


Cipher text only attacks on deterministic fully homomorphic encryption schemes

Yes, your understanding is correct.

It is well-known that homomorphic encryption schemes are vulnerable to cipher text attacks if they are deterministic. See, for example, the section 2.4 of the paper A Survey of Homomorphic Encryption for Nonspecialists

Consider that the attacker has a value $c_1$ that is known by him to be a encryption of some clear text $m$.

So, if this scheme accepts at most $L$ additions in sequence, the attacker can find the encryption of $L$ multipes of $m$ by adding $c$ to itself:

$c_2 = c_1 + c_1 \Rightarrow dec(c_2) = 2m$

$c_3 = c_1 + c_1 + c_1 \Rightarrow dec(c_3) = 3m$

...

$c_L = c_1 + c_1 + c_1 + ... + c_1 \Rightarrow dec(c_L) = L \cdot m$

Note that the attacker can combine the "intermediate" ciphertexts too (I mean, add the ciphertexts $c_2, c_3, c_4, .., c_{L-1}$ to themselves).

With just this, the attacker can learn a lot of pairs of cleartexts and correspondent ciphertexts. Then, since the scheme is deterministic, he will able to identify a lot of the ciphertext that are being sent.


Can I use Pollard'-Rho even when the order is not a Prime?

If the order is not prime, you first use Pohlig-Hellman to reduce it to several instances where the order is prime, and use rho to solve those.


How to increment the counter value for CTR mode?

Basically there are two ways:

decode the counter to be a big number in some kind of library, increase that number, then encode it back as unsigned, statically sized, big endian value, making sure you left pad with zero valued bytes when necessary;
increase the value of the right-most byte (highest index) as unsigned number, if the resulting value is zero then increase the value of the byte before that, up to the leftmost byte if required (i.e. use a bit of awkward carry-bit detection).

Probably 2 is easier and less error prone; you'd just need a single loop construct, one expression to increase the byte value and an if statement to detect the carry by comparing to 00 afterwards.


RSA signature attack check on lowest 16 bytes - Implementation

if(checkValue.compareTo(resultOfModulus) == 0)

Here's your problem; you're checking if $y^3 = (md5BigInteger \bmod 2^i)$; that's wrong (as $md5BigInteger \bmod 2^i$ won't typically be a cube).

Instead, what you want is to check if $y^3 \equiv md5BigInteger \pmod{2^i}$; or, in other words (thinking less like a mathematician, and more like a programmer) if $(y^3 \bmod 2^i) = (md5BigInteger \bmod 2^i)$

Also, don't forget to check if $md5BigInteger$ is odd (or more generally, $8^k w$ for integer $k$ and odd $w$); if it's not of that form, no such simple cube will exist.


The AES standard specifies the use of 10 rounds with 128-bit keys. Anything other than this is, by definition, not AES. There are no known effective attacks against standard AES-128.


Very short block ciphers for equally-short plaintexts

Why don't you use a stream chiper like RC4? (ok, RC4 is known to be broken, but there are many others). Am I missing something from your question?


If Alice and Bob both use static DH keys, they only have to perform the DH operation once to get their shared secret. The number of messages that are safe to exchange encrypted with something derived from that shared secret is not really a function of the DH problem, except to the extent that the size of the modulus and of the private keys put a limit on the maximum security strength of the shared secret.

However, there are other factors that might entail such a limit, such as whether or not they exchange nonces for the key derivation from the (calculated once) shared secret, which symmetric cipher they use for bulk encryption, which mode of operation is used, etc.

Another thing that might entail such a limit is their confidence in the key management of both Alice's and Bob's private key. If either private key is compromised, this will mean complete loss of confidentiality of all messages sent encrypted with a key derived from a shared secret calculated using that key. Again, this is a key management issue and not a security issue specific to static DH in any way, but it might be mentioned as the reason why there exist various hybrid schemes that mix long term asymmetric keys with ephemeral asymmetric keys.


Is there any recent cryptographic algorithm especially designed for low-level processors?

In the context, one option would be AES in CTR mode with the XOR between ciphertext and keystream on the PC side (saving most of the bandwidth in the PC to Low-level processor direction). CTR mode allows direct access to any portion of the plaintext. AES is easy to implement on an 8-bit CPU, reasonably fast, and low on resources. As a bonus, protecting AES against side-channel attacks is well studied (although the weakest point likely will be different: obtaining the whole plaintext or keystream once, and storing that).

If AES is not fast enough, and about 260 bytes of RAM are available, and the plaintext can be divided into relatively large blocks (like 1024 bytes or more), and we replace recent by tried and tested, there is RC4 with an appropriate key setup (e.g. append 32-byte key to 8-byte block address, use that as the RC4 key, discard the first 256 bytes produced by RC4).

Update: beware that both methods allow the user to change bits of plaintext just by flipping the corresponding bits of ciphertext; see that other answer if the integrity of plaintext is required (this also requires assuming the program on the PC is not altered).


Assuming the hash function is good, and SHA-256 is widely believed to be so, the probability of no collisions in $k$ samples into a range of size $n$ (e.g., obtained by selecting a subset of characters) is upper bounded by $exp(-k^2/2n).$

For you, say $k=2^{21}=2,097,152$ (couple million) and $n=2^{64}$ means that your probability of no collision is roughly

$$exp(-2^{42}/2^{65})=exp(-2^{-21})\approx 1-1.2\times 10^{-7}.$$

If you had 8 times more inputs (16 million plus) this would become

$$ exp(-2^{48}/2^{65})=exp(-2^{-17})\approx 1-7.6\times 10^{-6}$$

so probability of collision would be more than one in a million.


Can stream ciphers (usually) be "run backwards"?

With RC4, the answer is "yes, you can efficiently run the cipher backwards, reconstructing previous states".

For stream ciphers, whether you can reconstruct previous states in not typically considered, however for cryptographically secure random number generators (which are a similar primitive), it does come up; the term I've heard is "Backtracking Resistance".

Now, there is one thing to be careful with "Backtracking Resistance"; if the reason you have backtracking resistance is because the function that transitions between the previous state and the next state acts like a random function, then it becomes easier to fall into a short loop than if the transition function is invertable; this is because the you run into a loop if the next state happens to be any of the previous states you have visited.  In contrast, if you have an invertible next-state function, the only state that you might revisit is the initial state.  Because of this increased tendency to fall into short loops, it's typically considered wise if you (at least) double the size of the internal state beyond what the security strength might indicate you would need.


Collisions of RSA keys should never happen for realistic key sizes and good random number generators.

Assume a 1024 bit RSA key; the primes from which it has been derived are about 512 bit. If we assume every 500ths 512 bit number is a prime, and we assume the most significant bit of the 512 bit number is set, we still get about $2^{500}$ or $10^{150}$ different primes. If you apply the birthday problem to these numbers then you would expect RSA keys to have a prime in common about every $2^{250}$ or $10^{75}$ key generations. Identical RSA keys are even more rare.

This is large enough to never happen in practice. Unfortunately bad PRNGs which cause collisions do happen in practice, but you can't translate this into probabilities.

I've neglected a few small factors within the calculations that should not have a significant impact on the outcome.

GUID collisions are a bit more likely. V4 GUIDs are random, except for 6 reserved bits. So there are $2^{122}$ different V4 GUIDs. It's possible to get collisions if you create huge, but achievable amounts of GUIDs if you have a huge system dedicated to creating random GUIDs. The creation of a collision is  very unlikely to happen in a normally sized system, where GUIDs are only a part of the overall security system.

It shouldn't matter in theory that you create many RSA key pairs at the same time, as long as you seed your PRNG with enough entropy. But if you seed badly - so that there isn't much entropy in addition to the system time - then random extraction at the same moment can be a problem. One of the most common randomness related questions in C# is why two instances of System.Random created in quick succession return the same sequence. If the random sequences used for RSA key pair creation are the same, then the RSA key pair will be identical as well.


RSA factorization for special primes $p$ and $q$

Let $N=p\,q$ be an RSA modulus such that $p>N^\beta$ and $\displaystyle p=\sum_{i=0}^k a_i\,x^i$ such that $\max(a_i)<N^\delta$ and

  $$\delta <\frac{1}{k+1}\bigl(1-(1-\beta)^\frac{k+1}{k}-(k+1)(1-(1-\beta)^\frac{1}{k})(1-\beta)\bigr).$$

Then one can factor $N$ in polynomial time (see here).

In your question $a\ne b$. Let $b=a+c$. So

  $$p=2a^2+2ca+c^2,\ q=2a^2+2c+1.$$

In this case ($q>N^{0.499}$, $k=2$)  we have $a_0=2c+1, a_1=0$ and $a_2=2$ which means that if $2c+1<N^\delta$ then we can factor $N$ in polynomial time.


Can someone randomly guess the key to AES 256 bit encryption?

There are $2^{256}$ different AES keys, the chance that you hit the one right one on first try is thus $2^{-256}=\frac1{2^{256}}$.

To put this into perspective, here's a list of events that is roughly a billion times more likely to all happen (copied from Thomas Pornin's answer on Information Security SE):

  The computer spontaneously catches fire during the key generation process.
  Great Britain is wiped out by a falling asteroid during the very same second.
  A rogue gorilla escaped from a zoo enters your living room and mauls you.
  You win millions of dollars at the lottery three times in a row.

According to his answer, these events have roughly the chances of happening $2^{-45},2^{-50},2^{-60},2^{-71}$ each, which multiplies to $2^{-226}$ if you want all four to happen which is still roughly a billion times more likely than finding a 256-bit key on first try.

Note that this assumes that the key does indeed contain 256-bit of entropy, ie it can indeed take all the $2^{256}$ different values.


I think I figured out the solution.

Assume such G exists (a PRG).

Then G' as described here is a PRG as well.

But applying it on $x\|x$ results in $G'':x\mapsto G\left(x\right)\circ G\left(x\right)$, which is not a PRG (easy to construct a distinguisher that checks if its input $z=z'\|z'$).

It is also possible to use $G′:\left(x\|y\right)↦x\|G\left(y\right)$ instead.


If OWF were to exist, do we know for sure that one of the candidate OWF would indeed be a OWF?

Yes, you are looking for the notion of a universal one-way function.
Rafael Pass/abhi shelat's notes contain a construction on page 49. The construction is "unnatural" in the sense that it involves parsing the input to the OWF $y$ as a pair $\langle M\rangle || x$, where $\langle M\rangle$ is interpreted as the description of a Turing machine. Then you simulate $M(x)$'s executation for a bounded number of steps.
This is fairly typical of "universal" constructions (others exist, namely Levin's universal search). It is far from being feasible in practice though.
The notes mention that a "natural" universal OWF construction is a very open problem (circa 2008-ish).


What you are describing is called output feedback mode, a mode of operation for block ciphers to create a stream cipher. You are discarding the first 996 output blocks and are using the following four ones.

In general, your algorithm (as any algorithm) can't produce randomness, just stretch existing randomness in a way which might look more random.

If there are $N$ possible values for $p_0$ and $M$ possible values for $k_0$, we get at most $N·M$ possible different values for the final key – no algorithm can do better, arguably.

If the key $k_0$ is fixed (or known to the attacker), she can just as well as you calculate the whole series and get the result from $p_0$ (or even, if she had only one block of the output, calculate $p_0$ and the other blocks of the output).

The moral: don't try to invent your own scheme.

For deriving a key from another, already high entropy key (e.g. to use different keys for different uses), use a key derivation function. Those are often based on a MAC or a hash function, use the key and a "personalizer" as input, and create another key.

For deriving a key from a password (i.e. a low-entropy key which a human can memorize), we want a slow key derivation function. These take a password and a salt (different for each use, but doesn't need to be secret), do a lot of work(configurably much), and produce a key. Examples are PBKDF2, bcrypt and scrypt.


These are all fine and the order seems reasonable as well. It is a judgement call which part you think is most likely to fail. I would use your order of preference for the elliptic curve algorithms. GCM vs. CBC is a case of which you find more likely to be badly implemented.

If the requirements are not enforced upon you, I would consider adding in P-256. It should be as strong as 3072-bit RSA, and it at least used to be slightly more widely supported than P-384 – I have not seen recent numbers though.


First of all signing does not equal encrypting. It only works on some crypto systems and even then it is not the whole picture.

Hash algorithms are used for various reasons. One of them is to reduce the size of the signature since the digest is generally a lot smaller than the message itself.

But the main cryptographic reason behind hash functions is to make it so that a possible attacker cannot force the message he wants to forge a signature for, to have a certain property.

It is a bit technical but for example in the ElGamal cryptosystem if you sign the message itself then it is possible for an attacker to produce a valid signature without knowing the secret key. If however you sign the hash of the message  then this is not possible.


Suppose you've let the box encrypt 'AAAAAAAx' for all byte values of x. (It will be the first block of the total output). Then send AAAAAAA and see what the first block is. You know now what last byte is and it's the first one of S. Now you know one byte. Think and iterate.


Creating a license system based on asymmetric encryption (RSA or ECDSA)

Sign the license text.  There's nothing confidential in the license text, so you don't need confidentiality.

If possible, include some kind of customer ID or something in the license that links it to a particular customer.

Standard digital signature schemes can easily sign arbitrary-length messages.  Don't worry about the length of the message.  (Internally, they hash the message with a collision-resistant cryptographic hash, then sign the hash, roughly speaking, which is how they can handle arbitrary-length messages efficiently.  But you shouldn't need to know that, if you are using a standard implementation of a well-vetted crypto algorithm.)

One approach to revocation is to have your client software contact a central server for periodic download of the revocation list.  The alternative is to have your server issue short-lived signed authorizations, and require the client to periodically contact the server when each one expires to get a new one (and the server can withhold providing any new authorizations once you revoke that customer).  In either case, make sure that the client can continue to use your software for some set period while they are offline without destroying their access to the software, or your customers might become very mad at you.

There is no purely offline solution to revocation.  If the customer has no network connectivity, there's no way to revoke their software license early.  If in the absence of revocation their software license would be valid until time $T$, and at time $t<T$ you want to revoke them, you can't.  Consider: from the client's perspective, there is nothing that lets them distinguish between whether they are revoked or not, if they don't have any communication whatsoever with the server or anyone else.  So if you expect clients to be offline, it becomes a tradeoff between "the lifetime of a license" (how long before it expires?) vs "speed of revocation" (how long before revocation takes effect?).  If you issue licenses that are good for one year, then revocation won't take effect until that year is up -- if clients are offline.

What you can do is refuse to provide software upgrades to clients whose software has been upgraded.  This won't prevent them from continuing to use the older version of the software, though, for as long as their license is valid.  Optionally, you could also have the client software try to connect to the Internet whenever possible, and if the client goes for a certain time period without having being able to reach the server, you could have the client disable itself; whether this is acceptable will depend upon how you expect your legitimate customers will use your software.

If your private signing key is stolen, you are hosed.  There's nothing you can do to prevent whoever holds that signing key from generating illegitimate licenses that the existing version of your software will accept as valid.  All you can do is change the public key that's hardcoded into the software, in the next software update (so people won't be able to use that newer version of software using licenses signed by the old stolen key) -- but this won't stop people from using the older version of your software.  So try to not let your signing key get stolen.

Finally, remember that these licensing schemes provide a speedbump, not strong security.  They exist to keep honest people honest, but they will not be effective at deterring or stopping dedicated malicious people from bypassing your copy protection system.  Therefore, whatever you do, try to ensure that your license system doesn't inconvenience honest users too much.  Don't drive them to download pirated copies because they're less annoying than the actual paid-up copy.


Word-based stream ciphers vs "regular" stream ciphers?

A word-based stream-cipher produces the pseudo-random sequence one word (of several bits) at a time. For example RC4 is a word-based stream cipher, with the word size a byte. By contrast, a typical bit-based stream cipher such as one using the ASG produces the pseudo-random sequence one bit at a time.

Word-based stream ciphers may be better suited to fast software implementations than are bit-based stream ciphers, since CPUs typically process one word no slower than one bit.


How is digital signature different from a message authentication code (MAC)?

The main functional difference is that anyone able to verify a Message Authentication Code is also able to forge one, because the same key is used for both tasks; whereas someone with the public key can verify a digital signature, but can't forge one.

Contrary to a MAC, digital signature is thus usable in contexts where the verifier is not trusted, which is of tremendous practical value. There's a price to pay for that: a digital signature is significantly larger, and slower to generate and/or verify, than a MAC is.


Solid summary of what encryption remains strong after recent events

We don't know what NSA (or any other spy agency--the US isn't the only country with code breakers) has broken.  Other than Dual EC DRBG, we are left with everyone making their best guess, just like before.  The NIST elliptic curves and the SHA2 hashes and DSA all came from NSA, but that seems to be the only real reason to suspect anything bad about them.  Neither AES nor SHA3/Keccak have anything at all to do with NSA.


Polynomial representation of the affine part of the AES S-box

Your code is an attempt to implement the function $f$ which is a polynomial representation of the $\text{GF}(2)$ affine part of the S-box of the AES (usually referred to as $A$). Function $f$ is described on page 7 of the paper and your coefficients seems to be OK.

Your code is mapping $\text a$ to $\text q$ such that $\text q=f(\text a)$.
You're however missing a huge part of the AES S-box, that is, the inversion in $\text{GF}(2^8)$. What you actually want is to map $\text a$ to $\text q$ such that $\text q=f(\text a^{-1})$ where the inversion takes place in your ring $\text R$. Note that you must handle the special case $0$ aside...


Zero-Knowledge Proof of a Turing Machine

In principle, any language in NP can be proven in zero knowledge. Furthermore, any language in NP can be proven with a zero knowledge proof of knowledge. Thus, in order to answer your question, the only issue remaining is whether or not the language you have defined is in NP. In order to verify this, one needs to define a relation that can be verified in polynomial time. The way you have formalized the question is such that this is not the case. In particular, you have not included a requirement that the machine run in polynomial time. However, even if you do add this, it has to be done carefully. If you define: $(I,O)\in L$ iff there exists a polynomial time TM $M$ such that $M(I)=O$, then what you are really writing is $(I,O)\in L$ iff there exists a polynomial $q$ and a TM $M$ that runs in time $q(|x|)$ upon input $x$ such that $M(I)=O$. However, in this case there is no fixed polynomial-time upper bound on the running-time of the verifier (since the polynomial $q$ in the witness can be any polynomial). This can be solved by either defining the language $L_q$ to be $(I,O)\in L_q$ iff there exists a TM $M$ running in time $q$ such that $M(I)=O$. Alternatively, one can define $(I,O,1^t)\in L$ iff there exists a TM $M$ such that $M(I)$ outputs $O$ within $t$ steps. Since these languages are in NP, you can prove a zero-knowledge proof of knowledge and get what you want.

I note that in fact any language in $IP=PSPACE$ can be proven in zero knowledge, but then the proof isn't efficient.


Constant time comparison for arrays of different lengths

Assuming the first code extract is translated straightforwardly to machine code (perhaps by blocking some compiler optimizations, or using a relatively dumb compiler) and executed on a CPU that performs no groundbreaking runtime optimization, it it is plausible that execution time has no dependency on the data in the arrays, except perhaps in the final 0 == nonEqual (and that residual timing dependency is a non-issue if the function result is to be used as argument of a conditional operator, as seems likely in the context). It's possible to ascertain this by looking at the generated code and at the characteristics of the CPU, and/or confirm it by careful instrumentation.
But execution time almost certainly depends on the length of the arrays, in several ways:

As noted in another answer, System.Math.Min likely does.
An optimizing compiler is likely to crunch out a lot of the second for loop, since (b[i] ^ ~b[i]) is always ~0. The whole nonEqual |= (b[i] ^ ~b[i]); could be replaced by nonEqual = ~0. It's entirely possible that the full loop is reduced to a test that it runs at least once and a conditional nonEqual = ~0.
Even if somehow the above is  made to not occur, there's no reason to believe each execution of the second loop lasts the same time as the first: the code is not the same; on some architecture the code alignment matters; a data cache or some other CPU optimization is likely to make the two references to b[i] faster than the references to a[i] and b[i]; on some architectures, the ~ has a cost...
When the second loop does not run at all, it's possible the code is not fetched and that it saves some time when the two arrays are exactly the same length.

Can we fix it? Not portably, in C# or in any language I know that targets multiple CPUs.
Does it matter? Perhaps, but only if that's among the smallest timing dependencies on the length of the arrays. Which is unlikely, and hard to assess: there's no portable way to setup an array in time independent of it's size!

Which approach should be taken when comparing arrays of different lengths?

Try to reformulate the problem/method so that the need to perform such comparison in constant time vanishes. E.g. if we want to hide the length of a password, we can turn the password into a hash once in a context where adversaries can't time the hashing operation, then hash the string to be compared and compare the equal-length hashes in constant time. If even that is difficult (a compiler, JIT, or even CPU architecture optimization can optimize the loop in a ConstantTimeCompare into something with a data timing dependency), we can perhaps compare (H)MACs of the hashes computed using the same secret random key.
More generally, demonstrable absence of timing dependency is hard to obtain. It's impossible to obtain from a high level language without exquisite control on the compiler and runtime environment. The best line of action is to reduce to an absolute minimum where in the code that's necessary. Or offload the problem to an environment dedicated to that, like a security CPU, which is designed to prevent timing side channels (including using a CPU having carefully designed and specified timing characteristics making execution time precisely predictable), and other side channels (power analysis, fault injection…).


How can we prove that the following theorem is valid for almost perfect secrecy?

You cannot prove that because it is not true.

Chapter two of the book Introduction to Modern Cryptography explains about perfect secrecy and defines this $\varepsilon$-perfectly secret notion. In exercise 2.12 you are asked exactly to

  [...] Show that $\varepsilon$-perfect secrecy can be achieved with $|K| < |M|$
  when $\varepsilon > 0$.


The original proposal specifies:

  A plaintext $P$, which can have any number of bits between 0 and $2^{39} − 256$.

The NIST SP 800-38D specifies:

  Although GCM is defined on bit strings, the bit lengths of the plaintext, the AAD, and the IV shall all be multiples of 8, so that these values are byte strings.

So there is a clear difference between the original proposal and 38D. I presume that this is because the test vectors almost never contain any tests for plaintext (or AAD, IV and authentication tag) that are not a multiple of 8 bits. In that case it is probably better to leave it out.

So onto your question:

  What is the minimum amount of plaintext data required (after any padding) to appropriately encrypt and authenticate using AES-GCM?

Well, zero bits, obviously. GCM doesn't require any padding of the plaintext before it is used within the algorithm. Steps 4 & 5 in 7.1 of 38D define how the input is padded before it is used. Although the specification is limited to accepting bytes, there is nothing stopping you from creating an implementation that operates on bits.


Pailler encryption of small integers to 32-bit integers

Regardless whether input is small, $n$ must be large enough to avoid factorization. Next, $r$ must be sampled from a large space to avoid decryption by trial-and-error. Some crypto and big-numbers library (bouncycastle, openssl, crypto..) might be handy to implement such an algorithm. It would be safe to choose an implementation rather than write it from scratch.


The second step has nothing to do with the first step. It doesn't matter which hash is used in the first step. For X25519, which operates on an equivalent curve Curve25519, the private key is obtained by randomly generating 32 bytes and the first step of using that key is to apply the bit pruning step (clear bits 0, 1, 2 and 255 and set bit 254).

Clearing bit 255 ensures that the key is in the range $0..2^{255}-1$ where the operations are defined. Setting bit 254 improves performance when operations are implemented in a way that doesn't leak information about the key through timing. Clearing the low-order bits counters attacks that force the use of a weak key.


DES is a Feistel cipher where the round function doesn't need to be invertible. Therefore, when designing a Feistel cipher you will have invertible and non-invertible S-box options.

In contrast, AES is a substitution-permutation network where the structure is completely different. If AES operations are not invertible, you will not be able to decrypt anything. So, the second claim is wrong.


Patterns flaw to sign a counter with public key encryption protocol

Terminology issues:

one does not sign with an encryption protocol, but with a (digital) signature scheme.
secp256k1 is neither of these. It is an elliptic curve.

Thus it is wanted to ask if in modern (asymmetric) (digital) signature schemes, like ECDSA on elliptic curve secp256k1, there is any flaw in signing a counter.

The answer is no, for proper implementation. That would go against the theoretical definition of a signature scheme's security. And there is practical insurance that the scheme does not become insecure when a counter is used as message: in all modern signature schemes with appendix (including ECDSA), the message is hashed, the resulting hash is the only input to the rest of the signature scheme, and the hash of a counter has no remarkable property (for a secure hash).

The only remarkable things are that

The messages are predictable. It allows the signer to prepare the signatures in advance. If either comes with a risk, it is not one specific to the signature scheme.
The messages are heavily constrained, which can only raise the difficulty of signature forgery, compared to other predictable messages.


Actually, a well known result is that, for any cryptosystem that relies on the hardness of the DLog problem (including ECDlog), there is no such reduction in strength if you have $k$ keys.  That is, the problem of "here are $k$ keys, break any one" is essentially as hard as the problem "here is one key, break it".
The proof is straight-forward; first off, we assume that the cryptosystem is based on Dlog, hence breaking the system is equivalent to solving some DLog problem.  Further suppose we did have a method of, given $k$ values $a_1G, a_2G, …, a_kG$, of finding $a_i$ for some $i$, and this takes effort $M$ [1].
Then, given $bG$, we can attempt to recover $b$ by selecting $k$ random values $r_1, r_2, …, r_k$; and compute $r_1(bG), r_2(bG), …, r_k(bG)$.  We then hand this off to our oracle, which gives us the value $c$ s.t. $cG = r_i(bG)$ for some $i$; we then compute $b = cr_i^{-1}$, and thus recovering $b$, at the cost of $M$ plus the time to do $k$ point multiplications (which is quite feasible assuming $k$ isn't ridiculously large).
Similar proofs would apply to DH-based cryptosystems as well.

[1]: I'm using additive notation, mostly because I find it easier to read...


How to implement the Salsa20 hash function?

You are right about the interpretation of the power 10: it's a tenfold iteration. So we apply the function 10 times, starting with $x$, feeding the output as input for the next step. So C-like (I write x for the vector of 16 words $x_0,\ldots,x_{15}$):

y=x;
for (i=0; i< 10; i++){
    y = doubleround(y)
};
return y

The inverse of little-endian is indeed the function that sends a word (32 bits) back to the sequence of 4 bytes in a little endian way, so the least significant byte goes first, and the most significant byte goes last. So it maps $w$ to w & 0xff, (w >> 8) & 0xff, (w >> 16) & 0xff, (w >> 24) & 0xff

Finally, the iteration gives you a vector 16 words, which you add componentwise in the same order with the original input vector. Then you convert them to bytes again, in that same order, and every word in the little-endian fashion described above. (We could also have converted them to bytes first (using the inverse of litleenian) and then done 64 byte additions in order, but this is less efficient, as we then do 64 byte additions instead of 16 word additions).


Elliptic Curve Point at Inifnity in Projective Coordinates

The curve equation for an elliptic curve in Jacobian form is

$$Y^2 = X^3 + aXZ^4+bZ^6.$$

If $Z=0$, then $Y^2=X^3$, and all points satisfying this are of the form $(\lambda^2 :\lambda^3:0)$, where $\lambda$ is in the finite field you are working over. Projectively, these are all equal to $(1 : 1 : 0)$, and therefore the only point on the curve satisfying $Z=0$ is $(1 : 1 : 0)$. This is why we refer to it as the point at infinity, and not a point at infinity (points with $Z=0$ can be thought of as lying at infinity).

Assuming that your points are one the curve, it is therefore enough to check that $Z=0$.


Impact of distinguishing between random text and cipher text?

Patarin's proof isn't about distinguishing ciphertext from "random text", it's about distinguishing a Feistel cipher from a random permutation.  That proof is also in the information theoretic world, which means that the Adversary is computationally unbounded, and as such can deduce everything about the cipher (the 'key', all remaining ciphertexts, etc).

In the more 'practical/useful' sense (i.e. against bounded Adversaries), if the Adversary can efficiently distinguish a cipher from a random permutation then they can usually mount efficient key-recovery attacks against the cipher structure (guessing part of the key in order to 'peel off' rounds, and using the 'wrong-key randomization' hypothesis).  Once you know the key then you can deduce all future ciphertexts.

I should also add that any permutation, whether truly random or pseudorandom, can be distinguished from "random texts" /"random strings" with the following Advantage (probability of success):
$$\mathbf{Adv} \leq \dfrac{n(n-1)}{2^{\ell+1}}$$
Where $n$ is the number of requested chosen plaintexts and $\ell$ is the blocksize of the permutation in bits.  This is because if you select $n$ distinct plaintexts you will always get $n$ distinct ciphertexts if the Oracle is a permutation.  But if the Oracle is returning random strings then there might be a collision in the outputs (and the probability of collision grows with the amount of requested plaintexts, becoming essentially $1$ when around $2^{\ell/2}$ requests have been made).


Shamir Interpolation Problem (Recovering secret with fewer parts than the threshold)

I have picked all combinations $C^p_2$ and $C^p_3$ of $(x, (fx))$ to all polynomials $ a_3x^3 + a_2x^2 + a_1x + a0$ where  $\{a_3, a_2, a_1, a_0\} \in Z_{5}, Z_{7}$ and $a_3 > 0$. I can always recover the secret using less points than the threshold.

From your comments, it sounds like when you say "I can always recover the secret" what you mean is that there is some subset of shares that results in the correct secret. Not that all subsets of shares always reveals the correct secret.

That is the expected behavior. Under the typical usage of Shamir secret sharing, a subset of fewer than the threshold can use their shares to try to recover a secret, but they will have no idea if they are correct, and their probability of being correct is no better than random guessing.

You said in a comment that "if you consider that the Dealer can be malicious". Shamir never claimed (or proved) the scheme to be secure in the presence of a malicious dealer. For that threat model, you would have to use other schemes.


The cryptosystem enciphers plaintext $m$ as ciphertext $c \gets (m\cdot k) \bmod p$ where $k$ is the secret key, and $p$ is a prime. It is (silently) assumed $0<m<p$ and $k\bmod p\ne 0$; otherwise decryption by $m \gets (c\cdot k^{-1}) \bmod p$ is not possible. Not told, and of paramount importance: is $k$ used just once, or reused?

Once: the system is information-theoretically secure, which is the best it can get, but is not a cipher per both the academic and practical definitions of that. It's like a One Time Pad, as inconvenient from the standpoint of transmitting the key, and much less convenient to use afterwards.
Reused: The system is a cipher, but it is trivial to find (a working equivalent $\hat k$ of) $k$ from a single known pair $(m,c)$, per $\hat k \gets (c\cdot m^{-1}) \bmod p$; then decipher the rest. This is below what the expectation for good crypto has been since at least Kerckhoffs.

There's no bad crypto that can't be improved: if we use OAEP padding like in RSA to turn the message into $m$, and undo that on decryption, I believe the combination becomes a provably secure IND-CPA (perhaps IND-CCA2) symmetric cipher. But we have simpler and more efficient ones.


Is there any reason to use RSA or DSA when we have ECC?

There are three use cases where RSA beats common ECC algorithms, such as ECDSA:

Signature with verification frequent or/and by low-power devices. The verification cost of $n$-bit RSA with usual public exponents is $O(n^2)$, but the verification cost of ECC-based signatures is $O(n^3)$ (using usual algorithms). Together with simpler math, that's why RSA can be way over 10 times faster for signature verification at usual security levels, even though it must use a larger $n$ for equivalent security level.
Similarly, encryption by low-power devices or/and with decryption comparatively rare.
Need to minimize the size overhead of adding a signature; using signature with message recovery, that can be 34 bytes for RSA (using SHA-256 hash, ISO 9796-2 mode 3 or the deprecated mode 1, for messages at least 222 bytes before signature at the 2048-bit security level), versus 64 bytes for ECDSA for comparable security.

RSA is thus a good choice (and indeed still the dominant one, I believe) for signing public-key certificates; beside inertia, in the internet domain that's mostly for reason 1 (certificates are verified often), but in the Smart Card and payment industry reason 3 adds up.

Additional arguments for RSA (vs ECC) are

RSA was first there / is the most time-proven, and became an industry standard.
Simplicity. RSA signature verification is much easier to code, and get right, than ECDSA signature verification.
RSA is now clearly patent-free.
Perhaps, slightly more quantum resilience; that is, at comparable level of resistance versus non-quantum attacks, RSA arguably would fall after ECC if it ever emerged quantum computers usable for cryptanalysis; see this other answer and section 5.4 of its source; note that Koblitz and Menezes are not making any strong statement, rather, their intro is (emphasis mine):

  We next examine some conjectures about the NSA’s motives in its PQC announcement (..)
  The NSA believes that RSA-3072 is much more quantum-resistant than ECC-256 and even ECC-384. (..)

Note: this answer does not touch use cases where ECC is preferable, or its virtues.


For two LUKS volumes made with the same password, can stealing the encryption key from one volume allow access to the other?

It should be safe. If the running computer is stolen and memory is read, it's the master key that will be revealed, allowing decryption of only that volume. The password itself is only used transiently when you open the volume to decrypt the master key. The other volume, despite using the same password to decrypt its constituent master key, will have a different master key.

When you use a system like LUKS, you are not encrypting data directly with your password. Rather, a completely random key is generated that is used to encrypt your data. This key is called the master key, sometimes called a data encryption key. This master key is itself encrypted with another key (derived from your password), called the slot key, or key encryption key. The encrypted master key is then stored directly in the encrypted volume. Because each volume will use a different master key, revealing one master key says nothing about the other, nor does it say anything about your password.

An attacker can attempt to brute force your password. This is done by guessing a password, processing it, and seeing if it can successfully decrypt the master key. They will only succeed if your password is very weak due to the processing algorithm LUKS uses, called PBKDF2. This algorithm runs your password through a hash function a huge number of times. It is intended to take approximately one second on a consumer computer. While waiting one second to see if your password is correct won't bother the end-user, it does mean that cracking the password becomes significantly harder.


How does the sponge construction avoid the weaknesses present in Merkle–Damgård hash function?

There's two ways to answer this.  One would be to go over the individual M-D weaknesses you list and show why the sponge construction is resistant to them.  For example, if you consider length extension, the attacker knows:

The permutation $F$, capacity $c$, bitrate $r$ and padding rule used in the sponge instance;
The length of a message $m$ and its hash output $h$, but not the content of $m$.  For simplicity, we'll assume the output length is $r$.

To perform a length extension, the attacker has to guess the content of the $c$ capacity bits, and test each guess against some sort of oracle that will tell them whether they hit the correct $c$-bit combination.

The other, more general way to answer is to remark that the sponge construction is random oracle indifferentiable.  This means that any attack that distinguishes a random oracle from a random sponge can only succeed with negligible probability.  As the sponge functions page puts it:

  One could exhaustively list all the properties that a hash function should resist to and assign them resistance levels. Alternatively, claiming the security of a concrete function with regard to a model means comparing the success probability of an attack on the concrete function against that on the model. This allows compact security claims, which address all the possible properties at once, including future requirements not foreseen in an exhaustive list.


Is the one-time pad secure if the key is computed so the ciphertext will consist only of "A"?

You're missing the goal of a one-time pad: it's a key generated and distributed ahead of message transmission.
When using a one-time pad, the only secure time to exchange the pad is ahead of time. The message itself is encrypted with the pad to make up for the lack of a safe communications channel.
By computing a "one-time pad" such that the ciphertext is a fixed content, you are moving pad generation from "ahead of transmission" (when we have a secure channel) to "at transmission time" (when we do not).
You now need to send your "pad" instead of your "all As" message. This means that you have turned your pad into a message and have no secure channel to send it.


Why are $\{0,1\}$-matrices almost-MDS only when n is 2, 3, or 4?

From the article on page 5;

Theorem 1 Let $A:{GF(2^m)}^n \to {GF(2^m)}^n$ be an $n\times n \{0,1\}$-matrix over $GF(2^m)$. Then the branch number of $A$ is at most $\frac{2n+4}{3}$.

Let $A$ be the almost-MDS matrix. So its branch number is $n$. Using above theorem we have
$$n \leq \frac{2n+4}{3} $$
So $n=2,3$ or $4$.
The size of matrix is a tool for finding upper bound of branch number. The branch number of $n\times n$ matrix is at most $n+1$ and equality occur, when matrix be MDS.
Also matrix $A$ is MDS if determinant of all its sub matrices be not $0$.


No, they aren't, at least if you assume that the Merkle tree has a height of over 1 node, because in that case the "tree" would contain a single node and the two are equivalent. The height and amount of data / number of hashes per node are generally configured beforehand, and specifying 1 doesn't make sense.

A Merkle tree consists of multiple nodes, and each node consist of the hash of the underlying layer. That layer can consist either of other nodes or of data (I've not seen that data and nodes are mixed, and that would be dangerous practice). However, even for a two-height / two-node tree you would have $\text{H}(\text{H}(M))$ instead of just $\text{H}(M)$.

As finding a hash where $\text{H}(\text{H}(M)) = \text{H}(M)$ would amount to a collision, a secure hash will never output the same value for a hash and a Merkle tree.


It is safe to xor parameters into the sponge as long as they are uniquely encoded so that they can't be confused with part of a message.  The same goes for padding: if two distinct messages are treated the same way because you skipped padding, you're in trouble; e.g., if you use a length prefix then no padding at the end is necessary but you need to know the length up front.

This is not like JWT where the adversary can change one part of the JSON like the algorithm tag to control what algorithm the receiver uses to verify the rest of the JSON: you can't recover parameters from a hash anyway if it's worth its salt as a hash, so legitimate users aren't even temped to do that.

Even better, hashing the parameters means that an adversary can't reuse a hash made with one set of parameters for an application that uses another set of parameters—hashing the parameters makes the hashes used by the two applications essentially independent.

As a pathological example of how this could go wrong, imagine a protocol where one part uses $\operatorname{SHA-256}(x)$ as a public identifier for something, and another part uses $\operatorname{SHA-256}(\operatorname{SHA-256}(x))$ as a secret, each of which use is independently essentially fine (except for potential generic issues with $H^2$).  Obviously this combination of uses could be exploited to learn the secret.  Were the number of iterations of SHA-256 hashed into the message, as in $\operatorname{SHA-256}(1 \mathbin\| x)$ and $\operatorname{SHA-256}(2 \mathbin\| \operatorname{SHA-256}(2 \mathbin\| x))$ instead, there would be no such danger.


Are longer passwords really safer against brute force attacks?

If we take two password strings of different length and attempt to bruteforce match them, it is obvious that the longer one will take longer to crack on average.

Actually, that might be obvious to you, but it's not true.

A brute force search is one where an attacker has a long list of passwords, and tries them in succession.  Now, if the attacker is at all intelligent, they'll put passwords that are likely to occur near the front of the list, and unlikely ones near the rear.  That is, the 'goodness' of a password is not its length, but instead how unlikely it is to guess.

In particular, a password of 123456789 is considerably worse than a password of 2u,7J$n even though the latter is two characters shorter.

And, because the entire strength of a password is how unlikely it is to be guessed, a fixed transform (like you suggest) will add no strength.  If the attacker guesses the real password abc, they'll run it through the known transformation, yielding abc0000000 and check that against the underlying password logic; that has the same likelihood to succeed as it would have been if we had not added the 0 characters.


Shamir secret sharing with two types of parties

Let's say your secret is $S$. Split $S$ into 3 parts (say $S_1,S_2,S_3$) such that $S=S_1\oplus S_2\oplus S_3$.

Give each politician a copy of $S_1$, each general a copy of $S_2$, then split $S_3$ using 3-out-of-n Shamir Secret sharing.


Why are recomended RSA key lengths so high?

RSA, and to a somewhat similar extent Diffie-Hellman, bases its security on the difficulty of factoring large numbers into primes. While a scheme like AES can use all 2n numbers, in order to break RSA, you need to guess prime numbers.

As there are far fewer prime numbers and the factors can be better guessed, we need far larger prime numbers than other schemes like AES. So each additional bit doesn't double the difficulty of brute forcing it. If you want to venture into the math, you can check out the Wikipedia page on RSA.

While no one (we know of) has managed to break 1024, it is always important to stay ahead of the curve. And since brute force isn't exactly 2256 times more difficult,we pick higher primes. Who knows what future improvements in mathematics could break 1024-bit keys.