Is Computational Indistinguishability quantifiable?

The answer is yes.
Formally, when a scheme is proven secure (relatively to a specific security game), a theorem states that no adversary $\mathcal{A}$ couldn't win the security game except with a probability $f(\lambda, m_1, m_2, \dots)$.
With $f$ a function in $[0; 1]$, $\lambda$ a parameter called the security parameter (in general when $\lambda$ increases $f$ decreases as the efficiency (in time and space) of your protocol) and $m_1, \dots m_n$ which determines (or just upper bound) the power capability of the adversary: For example $m_1$ could be the number of messages seen by the adversary. And $m_2$ could be the number of generic group operation (if we are in the generic group model).
You have first to determine $m_i$ (id est: If your adversary is your nephew, the NSA, your nephew in 2050, the NSA in 3850, etc). Then you choose lambda which verifies:
$f(\lambda, m_1, m_2, \dots) <\frac{1}{2^{128}}$.
Particular case: Some result contain terms like $\texttt{ADV}^P(\lambda)$, with $P$ a well known computational problem (RSA, DH, LWE, etc). Then you have to check in the literature the best known attack to evaluate this term (or more simply which lambda is recommended).


Order of subgroups formed by Elliptic Curves with a Cofactor

The answer indicates that the order of all points on the curve over the finite field $2^{255} - 19$ is 8 times the size of the subgroup formed by $G$.

Obviously, this is incorrect, and Samuel never claims it.

This curve defines a group with $8q$ elements (with $q = 2^{252} + 27742317777372353535851937790883648493$ prime), and the factorization of $8q = 2 \times 2 \times 2 \times q$.  Hence, the possible orders of points are $1, 2, 4, 8, q, 2q, 4q, 8q$.  In addition, this curve happens to be a cycle curve (not all elliptic curve groups are), and so for each possible order, there are in factor at least one group element with that order.

$G$ happens to be one of the points of order $q$ (actually, it didn't just 'happen', a point of that order was deliberately selected to be $G$).

  How do we know the other points not inside 1, form a variety of small order groups?

Because we know the complete factorization of the number of points on the curve ($8q$).  If there is a subgroup of size $\lambda$, that would imply that $\lambda$ was a factor of $8q$.  We know all the values that are a factor of $8q$, and there are none between 8 and $q$; hence, there cannot be any subgroups with a size between 8 and $q$.

Group theory is your friend.


How to compute the output length of randomized encoding (or garbling)?

The size of the randomized encoding (or garbled circuit) produced by a given construction will be specific to that construction. (Indeed, there are major efficiency improvements to GCs/REs that are still being discovered every year.) So, to answer your (own) question, it would require focusing on a particular construction's details to answer fully.

However -- Yes -- it must be the case that any garbled-circuit / RE that is output by any probabilistic polynomial-time $\mathsf{Garble}$ or $\mathsf{Encode}$ procedure has size at most $\mathsf{poly}(1^\lambda, C).$ For the procedure to output something significantly larger, e.g. exponential in $1^\lambda$ and $|C|$, is impossible (in prob. poly time). Moreover, the typical constructions that come to mind -- e.g. Yao's Garbled Circuits and Applebaum-Ishai-Kushilevitz's randomizing polynomials -- have size approximately $O(\lambda\cdot |C|).$ (It's likely that whatever you're looking at is 'loosely in this range,' though schemes close to the state-of-the-art will have various fine-grained differences..)


Calculating the number of rounds required for block cipher with known differential

I think that you typed the probability of two rounds incorrect and it should be $2^{-7}$. By assuming that, you should choose the numbers of rounds in a way that the number of (chosen plaintexts, chosen ciphertext), exceeds of the number of  (plaintext, ciphertext) that are available(for example with today's computational devices is bounded). As you told the probability for two rounds, if you choose 15 rounds, the number of (chosen plaintexts, chosen Ciphertexts) will be about $15 \times 7 = 105$, that we can use it as a bound for this. You should be considered that it is a theoretical bound and choosing the number of rounds based on 2 rounds estimation is somehow not precious.


How does bit-wise operation work for encrypting grayscale images?

I have solved it.

The main reason was that I'm supposed to use LOGICAL operations instead of BITWISE operations.

The new results: https://imgur.com/a/NLa5Q8J

my function:

def logical_xor(message, key, op):
    message = np.asarray(message)
    key = np.asarray(key)
    new_image = []
    row=0
    col=0
    while row < len(message):
        new_row = []
        col = 0
        while col < len(message[row]):
            if op == 'and':
                new_row.append(message[row, col] and key[row, col]) # and instead of &
            elif op == 'or':
                new_row.append(message[row, col] or key[row, col])
            else:
                new_row.append(message[row, col] !=  key[row, col]) # xor
            col += 1
        new_image.append(new_row)
        row+=1
    return new_image

but before using this function, I had to do this:

from PIL import Image
m = Image.open("test_image.jpg") # message
m = m.convert("1") # converts to boolean?


If you mean exactly as likely, no, because the number of possible hashes is not a multiple of $100$.  This is assuming all the hashes are exactly equally likely.  You can come very close just by taking $SHA256 hash \pmod {100}$  This will be within one part in $\frac {2^{256}}{100}$, which is a very small number.  If you want truly equal, check that the hash is in the range $[0,100\lfloor \frac {2^{256}}{100}\rfloor)$ and take it $\pmod {100}$  If it is above that, hash something else and try again.  Your odds of failing the check are very small, and your odds of failing twice are very small.
In the general case: if one wants a result in the range $0..n\text{-}1$ then use $\bmod n$ and discard if the output  $>n\lfloor  \frac {2^{256}}{n}\rfloor$ and try another input. This is called the discarding technique; it is commonly used to extract a number in a range from a (pseudo) random number generator.


I want forgery ECDSA when prime p is form of 2*n+1, n is order of Elliptic curve

Hasse's theorem on elliptic curves tells us that, using your notation:
$|n-p+1|\le2\sqrt{p} \Rightarrow |n-(2n+1)+1)|\le2\sqrt{2n+1}\Rightarrow n\le2\sqrt{2n+1}$ which doesn't hold for $n>8$.

So either your curve is so small you can solve the ECDLP by hand or you are not defining an elliptic curve.

Could it be that the order of the curve is $2n$ but you are just working in the large prime order group (of order $n$)?
Because in that case $n$ divides $p-1=2n$ and you can mount a MOV attack.


Do test vectors ensure a cipher is free of backdoors?

can we say that it is fully conforming to the specification, and must have been implemented correctly?

No.

  Is it possible to backdoor a cipher (or hash function, I suppose) in such a way that it still appears to be correct and is compatible with different implementations of the same cipher?

Certainly.

Say I have an function AES(k,m)=c where variables k and m are the key and the message respectively and c is the resulting ciphertext.

Now I could write my own AES as follows:

def mikeazo_AES(k,m):
    if k==0x12abed347816981812abed3478169818:
        return m
    else:
        return AES(k,m)

Thus, given a specific key, it will simply return the plaintext. Since that key is not part of the test vectors, they will all pass.

This will be compatible with all other implementations unless that key is hit. Since they are randomly generated, the probability of that happening is slim. This may not seem super useful at first glance, but as an attacker you could add in some sort of trigger mechanism to force keys to be the special key. You can presumably do this as you have already got your software on their system.

There are better back doors that could be inserted. See example in comments from CodesInChaos.


How much extra security does key wrapping provide?

It all depends on the key wrapping used. Key wrapping is little more than encryption of a key with another key. Although key wrapping schemes certainly exist (and are considered rather secure in general) other key schemes may use common methods of encryption, both symmetric and asymmetric. And in the end, how strong the encryption is depends on the method used.

I've seen AES keys being encrypted using AES-CBC, which is perfectly fine for AES-128 and AES-256 keys. Wrapping an AES-192 key that way could already make it vulnerable padding oracle attacks. Encrypting a structured RSA key using CBC and an IV of zero bytes (as used by many HSM's) may even passively leak information to adversaries.

Encryption itself is already a chicken egg problem. You've got this data you want to keep confidential. Now you can encrypt it, but you'd need to secure the key now.

So why is encryption or wrapping useful? Well, not all keys have the same properties. Some keys such as public key for asymmetric systems can be distributed using a public key infrastructure, but they can perfectly use to wrap AES keys to perform key establishment. Other keys are distributed in advance, taking advantage of the moment in time that the key can be established. Yet others take advantage of hardware protection in HSMs or smart cards. So key wrapping is an important tool to perform key management. Note that one wrapping key can be used to wrap many other keys.

As for your examples: yes, a key can be transported over TLS. However, TLS is point to point transport security. After TLS is stripped you'd just have the key. It is much more secure to wrap the key and provide end-to-end security. With a bit of luck the key may be unwrapped directly within a HSM and never even appear in memory. Note that earlier forms of TLS, the TLS_RSA ciphersuites, actually perform a form of key wrapping to establish the master secret to derive the session keys from.

A password protected store can be used. Often the keys in those key stored can be protected separately as well. PKCS#8 could be seen as a high level form of key wrapping, for instance.

However, such key stores are not always useful. For instance, you may want to wrap a key in a HSM to sync it with another HSM. In that case you'll need a wrapping key in both devices. Generally HSM's cannot simply create a password protected key store for that.

Similarly, a device can offload wrapped keys if the memory is limited. This is a common method within TPM modules in PC's: instead of having a high end smart card chip, keys are wrapped with a TPM specific key and stored on the system's drive. When they are needed they are simply put back and used. This way the keys can be secure both at rest and when in use, even though they are not stored in the hardware device.

Wrapping / unwrapping a single symmetric key with another symmetric key that has the same access level probably doesn't make too much sense. But for key management key wrapping is a very important - if not essential - tool.


Is this a good choice of a digital signature scheme?

Rabin-Williams signature verification with 3072 bit keys is much faster than EdDSA signature verification of comparable security (when done in software). How much depends on care of coding, hardware, EdDSA parameters. Two data points:

in the eBATS benchmarks for a skylake CPU, ronald3072 signature verification (RSA with $e=3$ as an OpenSSL wrapper, by Bernstein) is nearly twice as fast as ed25519 (archetypal EdDSA carefully optimized by Bernstein); I'm too lazy to see if/when Montgomery arithmetic (which does not pay in the context) is used by OpenSSL RSA signature verification; but since there are at least two modular multiplications in that, versus one in RW, the later can only be faster.
in the Crypto++ benchmarks, RW 3072 verification can be extrapolated from RW 2048 verification times 2.25 (erring on the safe side), and is over 15 times faster than the fastest ECDSA signature verification (with pre-computation) quoted.

Even for an implementation using a $32\times32\to64$ multiplier, and classical algorithms, the modular multiplication dominating (properly coded) RW signature verification with 3072 bits key uses $k=96$ words, and about $2k^2$ (less than 20000) multiply-and-add. That can't be very long if coded carefully!

I think the theoretical principle of the scheme is right. Some details (like exactly what Full-Domain-Hashing is used, and perhaps additional constraints on primes) needs to be ironed out. And of course, the principle of rolling one's crypto is debatable (or just should be summarily rejected, in many real-life contexts).

As of implementation: the signature verification is reasonably easy to get right (as long as the correct number of redundancy bytes are checked), and is inherently immune to timing and other side-channel leakage (excluding fault injection), since nothing secret is involved. However lots of things can go wrong in signature generation, including side-channel (timing, power analysis..) and fault-injection attacks (against the later, at the very least, the signature should be verified independently of what generated it before being released).


Name for identical operations for encryption and decryption

A cryptographic algorithm where the operations for encryption and decryption are identical is called a reciprocal cipher.
As dfaranha mentioned, this is mathematically an involution.

Most mechanical cipher machines use a reciprocal cipher, so it wouldn't need a seperate "encode mode" and "decode mode".

Some of the more famous reciprocal ciphers are:

The Enigma machine was a reciprocal cipher machine
ROT13
Beaufort cipher
Kama-sutra ciphers
XOR-based stream ciphers
One Time Pads (both XOR and Beaufort cipher versions)

Many modern single-block ciphers are built with a Feistel network structure that, in each round, cascades a reciprocal permutation P ("swap the left and right half of the block") and a keyed reciprocal substitution cipher S, to build a non-reciprocal bijective encryption function E(x) == P(S(X)) != D(X) = S(P(X). It is widely believed that practically any non-linear function can give adequate security if it is iterated over enough rounds.
While the overall cipher is not reciprocal, the parts that are reciprocal allow such ciphers to share parts between the encryption and decryption, so implementations use significantly less space (less code or less hard-wired ASIC area) than they would if they implemented encryption and decryption completely independently.

There are variants of the one-time pad that are not reciprocal (for example, using the Vigenère algorithm), but they are no more secure.


Does a hash function necessarily need to allow arbitrary length input?

Is it necessary for a hash function to allow arbitrary length inputs or not?

Of course not.  SHA-256 is limited to inputs of 18,446,744,073,709,551,615 bits or less; it is not defined for larger inputs; SHA-256 is not disqualified from being considered a hash function because of this limitation.


Note: Until told otherwise this answer will assume the following things:

The "Master-Key" is secure. (unextractable, 128-bit+ entropy)
Ephermal (EC-) Diffie-Hellman is available and secure (keys unextractable, 2048 bit DH / 256 bit ECDH available)
The random number generator used is secure. (i.e. not just relies on the time, e.g. it's a cryptographically secure RNG, which should be available and used by a good TLS implementation)

Now the answer:

You don't have to renew keys if the above points apply.
If the assumptions apply all keys will be unbreakable (for at least a decade).

Well it looks like you want to have forward secrecy and to get this you may want to renew session keys every now and then. If possible I'd suggest renewing the session key after each time some sort of "action" is finished.If you don't have something like this "action" or "large chunk" you may want to renew keys at regular intervals. If the above assumptions apply rekeying at static intervals shouldn't be a problem. As Interval I'd suggest: "As often as possible" which may translate to something in between an hour and a day.

For completely renewing the session key TLS does have a feature called "renegotiation". You can trigger such a handshake whenever you need a new key.

Concerning the renewal of the master-key:

If the above assumptions apply you don't have to renew the keys. Renewing the keys is of interested if you believe that the key might be extracted. Depending on how easy that is you may want to re-new rather often than less. If you're Device is tamper-proofed or you're encrypting the key using ephermal data I'd say that once in a year up to once a decade is ok. If you're device is planned to be used for more than 50 years you may want to consider using 192-bit keys.


I am wondering if I can remove/reduce any field to save space, is there a way to save overhead in ESP packages?

Well, there was an old IETF draft here to address this very problem; however it didn't get enough traction in the IPsecME working group (for the complexity it has, it doesn't save that much space) and thus was abandoned.
Sticking to standard IPsec, well, you could remove the space used by the nonce by using RFC8750; that saves 8-16 bytes (depending on what transform you were previously considering)
And, you could decide not to use an authentication transform (thus eliminating that overhead).  On the other hand, that could bring up the possibility of active attacks; I can't recommend it.
And, as you are probably aware (but I'll mention it anyways) if you're protecting traffic between two endpoint devices, transport mode will allow you to not include an IP header in the payload data (thus saving you another 20-40 bytes).


How does SafeNet MobilePASS generate passwords?

So I was finally able to work this out. The pin code isn't important and is simply used to decrypt the activation code locally (not sure why our server asks for it in that case).

The activation code is a base32 encoding of a seed where every fifth character acts as a checksum for the previous four.

The seed is then passed through KDF1 to generate the shared secret.

That is then in turn used as part of the HOTP algorithm.

You can see my reimplementation in python here: https://github.com/datr/MobilePASSER/blob/python/mobilepass.py


can a key be applied to half the cipher text

Stream ciphers or Block Cipher with CTR mode can do so.

  how much time would it take to encrypt a 1.6 mb file with an average encryption algorthm. in seconds or miliseconds. like half a second?

It depends on hardware (CPU, speed of the driver, etc), software (OS, the programming language, etc) and the algorithm; but 1.6M Bytes should not take 0.5 seconds.

For example:

With the AES-NI, AES(ECB) can encrypt 2G+ Bytes/s with G4500 using Java, Windows 7;
without it, AES(ECB) encrypts around 120M Bytes/s with G2020 using Java, Windows 7.
Twofish encrypts around 110M Bytes/s with G2020 using Java, Windows 7.
Idea encrypts around 65M Bytes/s with G2020 using Java, Windows 7.


Can schnorr-signatures be used to ensure public keys are of the correct form (namely $Y= x \cdot G$)?

As long as the public key is in the elliptic curve group, there is no such thing as being "of the correct form" or not. For any point $P$ in the group, there exists a value $x$ such that $P=x\cdot G$. Thus, all that is necessary is to check that $P$ is indeed in the group. This is carried out by checking (1) that $P=(x,y)$ is on the elliptic curve itself (i.e., it fulfills the equation), (2) that $P$ is not the identity (i.e., the point at infinity, or zero), and (3) that $q \cdot P = 1$, where $q$ is the order of the Elliptic curve group that you are working in. (The third check is needed when the number of points on the Elliptic curve is greater than the size of the subgroup you are working in.)
A completely separate question is whether or not the public-key owner can prove that he knows the associated private-key. That is, do they actually know $x$ such that $P=x\cdot G$. This can be done using a zero-knowledge proof, but actually a Schnorr signature is exactly a zero-knowledge proof of this fact. Indeed, providing an ECDSA signature would also work. However, you need to make sure that this can't be used to extract a meaningful signature that they never meant to sign...


What exactly is "Plausible Deniability in Internet Protocols"?

The Latin word plausibilis means "deserving applause, acceptable", and this morphed into our English word plausible with the meaning, "having the appearance of truth", first used around 1560.

Merriam-Webster defines plausible as:

superficially fair, reasonable, or valuable but often specious
superficially pleasing or persuasive
appearing worthy of belief

"Plausible deniability" is often used in intelligence work: in false flag operations, active measures, offensive cyber ops, anti-terrorism in denied countries--we did not do it, and my boss especially does not know anything about it.

In cryptography it can mean deception about the presence of a message--while having a reasonable explanation. Alice can deceive you about a chunk of data, and you will not know for sure whether plaintext is or is not there--it will take work to figure out the truth, but even after you prove that Alice deceived you, she can still make a case that is believable... or say  I did not know....

"Plausible deniability" can also apply to hiding an encrypted volume in a storage device and then denying its existence.  Veracrypt is a good example of a product that can offer plausible deniability:  this USB does not contain a hidden, highly encrypted volume, enciphered with a cascade of TWOFISH/AES256 hashed with Whirlpool.

With internet protocols it means that two parties can deny having taken part in key exchange.  This might seem to be an odd virtue in key exchange.  In fact, this kind of deniability is an important feature.

You can read more about this last topic here.


If you want to reduce integers modulo that specific prime (and I assume you have checked whether $p = 2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1$ is prime or not), I would suggest you don't use the Solinas algorithms, but instead a different one geared towards modulii of the form $2^n - c$ for small $c$.

The identity underlying this operation is actually fairly simple:

$$a 2^n + b \equiv ac + b \pmod{2^n-c}$$

For you, $n=256$ and $c = 2^{32} + 2^9 + 2^8 + 2^7 + 2^6 + 2^4 + 1$

Here is how this would work; you take your 512 bit number $a2^n + b$ (and if you do the modulus operation immediately after each internal multiply, you never have to deal with an integer larger than 512 bits), and you compute:

$a'2^n + b' = ac + b$

This operation takes the successive words of $a$ (scanning from the lsword towards the msword), multiples each word by the 33 bit constant $c$, and adds in the corresponding word of $b$.  You call the first 256 bits of this operation $b'$ (remember, this generates results starting at the lsword), and the last 33 bits of the result $a'$.

You then do it again, taking $a'$, multiplying it by $c$ (which results in at most a 66 bit value), and adding it to $b'$.

The result of that has a small probability of being greater than $p$; check if so, and subtract $p$ if necessary.

There, you're done.  This would work fairly well on a 64 bit processor; it's less convenient on a 32 bit processor (because $c$ doesn't fit in a 32 bit word).


Who's talking to who encryption - does this concept work?

Like @StephenTouset said

  You appear to be reinventing the concept of onion routing.

For a practical example, check the Tor Project (based on the Onion Routing program) which enables online anonymity and directs internet traffic through a worldwide network consisting of thousands of relays to conceal a user's location… which would cover most of what you need.

But there are other implementations out there too; most of them handling encrypted, anonymous data (voice, text, binary) transfers using random node allocations and bridging.

Besides that, it is worth diving into mixnets too.

For more, the anonymity bibliography might come handy as an orientation for further research.


Why are multiple rounds with generated subkeys used?

It's true that a badly designed key schedule weakens the cipher.

However the main point is to "stretch" the randomness across all subkeys by using diffusion techniques, while using only $k$ bits of randomness for the key instead of $kr$ bits of randomness if all round keys were independently chosen.

This is doable. AES is a good example where the components of the cipher are used in the key schedule.

More theoretically, James Massey (and one of his students whose name escapes me now) has proved that a construction called perfect local randomiser can extract random looking $k-$tuples (subkey bits) from a uniformly distributed $n-$tuple (randomly uniformly chosen master key) such that these $k-$tuples are locally uniformly distributed. The construction uses orthogonal arrays which can be obtained from certain MDS codes under certain conditions. MDS codes are intimately related to the branch number of AES MixColumns operation, see, e.g. The answer to this question.

Edit: Also, a one round cipher will not have enough diffusion for linear and differential probabilities to drop to safely low levels, as it happens through multiple rounds.


Authentication by hardcoding public key in client software

Yes, the basic idea of hardcoding a public key is secure. It is sometimes recommended as an alternative to the complexity TLS and PKI bring – otherwise it can be easy to skip a crucial step and end up with little or no security.

However, the "encrypt a secret for server" scheme has some weaknesses compared to TLS. The clearest is lack of forward secrecy (which admittedly some TLS suites also lack). If an attacker breaks the public key encryption or gets the private server key, they can decrypt all sessions past and future.

A slightly more complex protocol would fix that issue. You could e.g. hardcode a signing key and authenticate an ephemeral Diffie–Hellman key exchange.

(You also miss out on using the available implementations of TLS, needing to write your own code risking mistakes. That is harder to quantify. And like you said, key management may be more of an issue.)


What does the "Type 1 query" model on Miles, Sahai, and Zhandry's paper?

Based on the author's presentation at CRYPTO 2016 (available on youtube), we see that the Type 1 query is really modeling the attacker's ability of multiplying the zero-testing parameter by the values it has.

The point is that this abstract query is conservative in the sense that it gives to the attacker more power than it would have (a priori) in practical in multilinear maps setting. Also, this query is modeled like that because it is likely that if an attacker can get the expressions I described as the expected ones, than she/he can also get the ones returned by the queries (for instance, by recovering $g$ and dividing the value $ p_k $ she/he has to get $ p_k / g $).


Proper way of doing encryption and authentication (PBKDF2 + AES)

PBKDF2 can produce output of arbitrary length. With HMAC/SHA-512 it does so in 512-bit chunks, but it is not restricted to 512 bits. If you need more bits then you can have more.

If you want to use the same password for authentication and for encryption, then the proper way is to "isolate" them from each other. I suggest the following: for the user password and salt (salt is on the server, and sent back when any client asks for it), the client computes PBKDF2 and obtains at least 256 bits. The first 128 bits will be used for authentication; the other 128 bits for encryption. Presumably, knowing the first half of the PBKDF2 yields no clue about the second half, and vice versa, except if the source password is guessed through exhaustive search (we are expecting PBKDF2 to behave like a Pseudorandom Function Family, the salt selecting the function in the PRF).

For authentication, use SRP indeed. For encryption, use GCM or EAX. GCM and EAX are nice encryption modes for AES (or other block ciphers, but primarily AES) which handle both symmetric encryption and a MAC, and can do so with relaxed requirements on the IV: these modes just need a non-repeating IV, not necessarily a random IV. You don't have to derive the IV from the password, and indeed you should not do it in case you want to encrypt several files with the same password, because then all the files will get the same IV, which is known to be a problem. Just encode the IV (counter, random... whatever floats your boat, depending on the encryption mode) in the file header.

It is not scientifically needed to use more than 128 bits for encryption or for authentication. Some people find psychological comfort in having huge keys, though.

It shall be noted that since the client first requires the salt from the server, an attacker impersonating the server could feed the client with a fake salt. Forcing the client to use a specific salt might allow for precomputations (aka "rainbow tables"). However, the SRP protocol ends with a pair of verification messages which validate that "everything went well" (when using SRP with TLS, the TLS Finished messages play that role). In the envisioned case, these messages not only guarantee to the client that it talked to the expected server, but also that the salt value was the right one, not one provided by an attacker.


Is there an advantage to storing keys split between several hashes?

Lets take your idea to the extreme to see its weakness. For simplicity I'll scale things down. Let's assume an 8 bit key chosen randomly. Call this key $k$. If I break into your database and get $d=H(k,s)$ along with $s$ (where $H$ is a hash function and $s$ is the salt), it would take on average $2^{8-1}=2^7=128$ computations (or calls to $H$) to find $k$.

Now, using your idea, lets say the server instead splits $k$ into $(b_1,b_2,\cdots,b_8)$ (i.e., bits) and then computes $d_i=H(k_i,s_i)$ (so there is a different salt for each bit of the key). Now, the attacker who breaks into your database and steals the pairs $(d_i, s_i)$ needs to crack all $8$ hashes. More difficult? No.

The reason is, how much work does it take to break $d_1$? Well, the attacker only need compute $H(1,s_1)$ and $H(0,s_1)$ to find $b_1$. That is only two operations (one on average though since half of the time the attacker will get the right value on the first try). Do this for all $8$ bits and the attacker has to make a maximum of $16$ hash function calls to break the key $k$. The average number of hash function calls would be $12$. This is much, much less than in the normal case above.

Asymptotically speaking, the first system (which hashes the entire password) is something like $O(2^n)$ where $n$ is the number of bits in the key and the second system (your proposal) is $O(n)$.


RSA hybrid decryption via PKCS#11 - unwrap or decrypt?

The AES is just used to protect the data. And although keeping the AES key in the HSM is more secure, you need to remember that there is little reason to protect it any better than the data itself.

However, if you don't need the speed, why not go for the HSM option? At least you'd be reasonably sure that the key is secure, that there are no side channel attacks and that the algorithm will operate as designed (e.g. with regards to random generation of the IV, self tests, destruction of the key etc.).

So use AES in software if you require the speed, HSM resources or low latency. Otherwise use the AES key in the HSM if you don't require it.


Here's a simple example for addition which can be extended to other operations as well.

Suppose there $X$ number of children in a classroom and everyone has a score ranging from 0 to 100. We want to calculate the average of the scores of all students without the teacher or the other students knowing what their classmates have scored.

Here's how we can achieve this.

Step 1 :

Make them each right down the score that they have got on a piece of paper and make sure no one is colluding. This only works if everyone does it honestly.

Step 2:

Tell each student to select $X$ numbers and write them down preferably on small bits of paper since there are $X$ number of students such that these numbers will add up to the score they want to keep secret. The range can be from $-∞$ to $+∞$.

Step 3 :
Tell each student to distribute $ X-1$ bits to every other student so that each students ends up with $X$ bits in the end.

Step 4 : Now that each student has $X$ bits of paper , tell them to add up all numbers they have in front of them and write the value they got on the board.

Step 5: Add all these numbers and you will get average of the scores of each student.

You could calculate the average without anyone knowing what their score was.

You can cross verify by taking the average of the actual scores.


How does table size impact table lookup speed?

To answer a specific question:

Are benchmarks simply being run in a vacuum and not in production?

Well, yes, pretty much.  If you are running a serious performance test on a specific routine, you deliberately don't run anything else (because whatever else the computer is doing at the time will jitter the timing of the routine you'll looking at, making the results less reliable).  And, yes, this gives an advantage to solutions which use a large amount of shared resources (such as cache space), over how they would perform in a more realistic environment.


Does ECC's cofactor affects ECC's private key selection?

Diffie-Hellman on Curve25519 and Curve448 is specified on RFC 7748 and the algorithm clearly mentions that the scalar must be a multiple of the cofactor (by setting the 2 or 3 least significant bits to zero depending of the curve).

If you choose a key with least significant bits not all zeros, then it depends of the implementation. An correct implementation following the RFC will make sure the least significant bits are set to zero before the scalar multiplication (whether when the key is imported in the program, or just before the scalar multiplication).

Now, you can eventually make an implementation that does not clear the least significant bits, the algorithm will give you something, but then it is vulnerable to small subgroup attack.

If someone sends you a small order point (let's say $4$), then by getting rid of the least significant bits of your private key, the result of the algorithm will give $0$ which is consider invalid and the small order point will be automatically detected.


Zero knowledge / proof of knowledge sudoku solution

Rough scetch, assuming Bob is standing next to you in the same room:

Prepare cards with the correct numbers on them
Lay down the cards according to the setup, face up
Lay down the remaining cards with the correct solution, face down, so that Bob can't see them.

Now you let Bob choose one column, row or sector.

You pick up the cards in that row, column or sector, still not showing them to Bob (turn around face-up cards if there are any), and start shuffling them.
Hand them to Bob, who can see if the cards have the correct numbers (1-9 in the standard game).

After shuffling, Bob can't see any more which card was in which position, he just knows that the set of cards is the correct one. If the face down solution is correct, this will always work out correctly. If you don't know the actual solution, there is a nonnegligible probability to be caught cheating. The chance for catching cheating is quite low tho, so you need to do many repetitions of this to achieve an overall acceptable probability.

All of the processes can be done cryptographically, e.g. face down cards can realized by commitments, shuffling is known from MPC, mix nets, etc.

Edit:
Alternative solution from this blog:
Apply a permutation to the numbers, then you don't need shuffling. However, then you need to prove that the solution actually fits the setup of fixed numbers under that permutation. Therefore, Victor can also choose to see the permuted original puzzle.


Hide the presence of a key in a key-value storage

Suppose you have a set of key-value pairs $(k_1, v_1), (k_2,v_2), \ldots$. You can store the coefficients of a polynomial $P$ that satisfies $P(k_i)=v_i$. The polynomial can be evaluated at any point to give a plausible output.
The degree of the polynomial leaks the number of key-value pairs, but if the $v_i$'s are uniform then the polynomial leaks nothing about the $k_i$'s. This is because for every way of fixing distinct $k_i$'s, the polynomial's coefficients are an invertible linear function of the $v_i$'s, so the coefficients are uniform if the $v_i$'s are uniform.
The only real downside is that polynomial evaluation is a bit slow: if there are $n$ key-value pairs then probing this data structure costs $\Theta(n)$.
However, there are alternatives to polynomials that have the security properties you need, with cheaper $O(\kappa)$ access time (for security parameter $\kappa$).
They have slightly higher storage overhead, whereas polynomials are optimal in size (exactly $n$ space to store $n$ key-value pairs).
The best reference for these data structures is actually an upcoming paper of mine, which will be on eprint in the next few weeks. I can post an update here when it's available.
In the meantime, the "best" publicly available oblivious key-value store is the probe-and-XOR-of-strings data structure that we propose in ia.cr/2020/193.
It has $O(\kappa)$ access time and $\sim 2.5n$ size to store $n$ key-value pairs.


In addition to the works that fgrieu cited, there is also Edward Eaton's paper analyzing LMS in the Quantum Oracle model.


It makes no sense since its nonsense. Let me explain why. Consider an attacker who captures a message of the form $(IV,c)$ for a plaintext $m$ that is not known to the attacker. The aim of the attacker is to "push" the message $m\oplus\Delta$ (e.g., the attacker wishes to flip some bits of $m$. Then, since CRC is linear, the attacker can compute $c'=c \oplus(\Delta,CRC(\Delta))$ and "push" the message $IV,c'$ which will decrypt to $m\oplus\Delta$.

Technically, one could argue that the text is just arguing that you can't push a message with an unknown IV and here I am reusing the IV. However, who cares if the attacker reuses or not; the recipient will accept reused IVs so the attack works.


The columns of the state are considered as polynomials over $\operatorname{GF}(2^8)$

Bytes are values in $\operatorname{GF}(2^8)$. Thus a column composed as the 4 bytes $a_0,a_1,a_2,a_3$ represent the polynomial  $a_0 x^0 + a_1 x^1 + a_2 x^2 + a_3 x^3$ (notice the ordering with respect to the power!).

Now we have:

\begin{array}{cccccccccccccccc}
(a_3 x^3 &+& a_2 x^2 &+& a_1 x^1 &+& a_0 x^0) &\cdot&\\
& & (\texttt{03}x^3 &+& \texttt{01}x^2 &+& \texttt{01}x^1 &+& \texttt{02}x^0) = \\
\texttt{03}a_3 x^6&+& \texttt{01}a_3 x^5 &+& \texttt{01}a_3 x^4 &+& \texttt{02}a_3 x^3 &+& \\
& & \texttt{03}a_2 x^5&+& \texttt{01}a_2 x^4 &+& \texttt{01}a_2 x^3 &+& \texttt{02}a_2 x^2 &+& \\
& & & & \texttt{03}a_1 x^4&+& \texttt{01}a_1 x^3 &+& \texttt{01}a_1 x^2 &+& \texttt{02}a_1 x^1 &+& \\
& & & & & & \texttt{03}a_0 x^3&+& \texttt{01}a_0 x^2 &+& \texttt{01}a_0 x^1 &+& \texttt{02}a_0 x^0)
\end{array}

If we apply $\mod (x^4 + 1)\ $ we have:
\begin{array}{cccccccccccccccc}
(a_3 x^3 &+& a_2 x^2 &+& a_1 x^1 &+& a_0 x^0) &\cdot&\\
& & (\texttt{03}x^3 &+& \texttt{01}x^2 &+& \texttt{01}x^1 &+& \texttt{02}x^0) = \\
\texttt{02}a_3 x^3 &+& \texttt{03}a_3 x^2 &+& \texttt{01}a_3 x^1 &+& \texttt{01}a_3 x^0 &+& \\
\texttt{01}a_2 x^3 &+& \texttt{02}a_2 x^2 &+& \texttt{03}a_2 x^1 &+& \texttt{01}a_2 x^0 &+& \\
\texttt{01}a_1 x^3 &+& \texttt{01}a_1 x^2 &+& \texttt{02}a_1 x^1 &+& \texttt{03}a_1 x^0 &+& \\
\texttt{03}a_0 x^3 &+& \texttt{01}a_0 x^2 &+& \texttt{01}a_0 x^1 &+& \texttt{02}a_0 x^0 &= \\
b_3 x^3 &+& b_2 x^2 &+& b_1 x^1 &+& b_0 x^0
\end{array}

Thus by reading the colunns:

\begin{array}{cccccccccccccccc}
b_3 = \texttt{02}a_3 + \texttt{01}a_2 + \texttt{01}a_1 + \texttt{03}a_0\\
b_2 = \texttt{03}a_3 + \texttt{02}a_2 + \texttt{01}a_1 + \texttt{01}a_0\\
b_1 = \texttt{01}a_3 + \texttt{03}a_2 + \texttt{02}a_1 + \texttt{01}a_0\\
b_0 = \texttt{01}a_3 + \texttt{01}a_2 + \texttt{03}a_1 + \texttt{02}a_0\\
\end{array}

by reordering over $b$:

\begin{array}{cccccccccccccccc}
b_0 = \texttt{01}a_3 + \texttt{01}a_2 + \texttt{03}a_1 + \texttt{02}a_0\\
b_1 = \texttt{01}a_3 + \texttt{03}a_2 + \texttt{02}a_1 + \texttt{01}a_0\\
b_2 = \texttt{03}a_3 + \texttt{02}a_2 + \texttt{01}a_1 + \texttt{01}a_0\\
b_3 = \texttt{02}a_3 + \texttt{01}a_2 + \texttt{01}a_1 + \texttt{03}a_0\\
\end{array}

by reordering over $a$:

\begin{array}{cccccccccccccccc}
b_0 = \texttt{02}a_0 +  \texttt{03}a_1 + \texttt{01}a_2 + \texttt{01}a_3\\
b_1 = \texttt{01}a_0 +  \texttt{02}a_1 + \texttt{03}a_2 + \texttt{01}a_3\\
b_2 = \texttt{01}a_0 +  \texttt{01}a_1 + \texttt{02}a_2 + \texttt{03}a_3\\
b_3 = \texttt{03}a_0 +  \texttt{01}a_1 + \texttt{01}a_2 + \texttt{02}a_3\\
\end{array}

Which is exactly the matrix multiplication:

\begin{array}{cccccccccccccccc}
\begin{bmatrix}
b_0\\
b_1\\
b_2\\
b_3
\end{bmatrix}
=
\begin{bmatrix}
\texttt{02} & \texttt{03} & \texttt{01}& \texttt{01}\\
\texttt{01} & \texttt{02} & \texttt{03}& \texttt{01}\\
\texttt{01} & \texttt{01} & \texttt{02}& \texttt{03}\\
\texttt{03} & \texttt{01} & \texttt{01}& \texttt{02}
\end{bmatrix}
\times
\begin{bmatrix}
a_0\\
a_1\\
a_2\\
a_3
\end{bmatrix}
\end{array}


How are Predicate Encryption algorithms implemented?

At first, your syntax (Setup,GenKey,Encrypt,Query) seems to be the syntax of public-key encryption with keyword-search (PKES). In the case of predicate-based encryption, we use Decrypt rather than Query.

The Sahai-Waters Fuzzy IBE

I recommend Sahai and Waters: Fuzzy identity-based encryption (EUROCRYPT 2005) as a first step. I assume you know the basic of pairing-based cryptography and secret sharing.

In Fuzzy IBE, a ciphertext and secret key is associated with attributes sets, $X$ and $Y$, respectively. If $X$ and $Y$ shares at least $t$ elements, one can decrypt the  ciphertext $c_X$ using $sk_Y$.
The syntax is as follows:

$\mathsf{Setup}(1^{\kappa},n,t)$ outputs $msk$ and $pk$, where $\kappa$ is the security parameter, $n$ is the size of universe, and $t$ is a threshold parameter.
$\mathsf{GenKey}(msk,Y)$ outputs $sk_Y$, where $Y \subseteq \{1,\dots,n\}$.
$\mathsf{Encrypt}(pk,X,m)$ outputs a ciphertxt $c_X$, where $X \subseteq \{1,\dots,n\}$.
$\mathsf{Dec}(sk_Y,c_X)$ outputs $m$ if $X$ and $Y$ share at least $t$ elements.

They design the scheme as follows (I omit enc and dec):

Setup: the master secret key is $\alpha,t_1,\dots,t_n \in \mathbb{Z}_q$ and the master public key is $e(g,g)^{\alpha}$ and $T_i = g^{t_i}$.
GenKey: The master generates shares $s_1,\dots,s_n$ of $\alpha$ by using $(n,t)$ secret sharing scheme, computes $D_i = g^{s_i/t_i}$ for each $i$, and returns $D_i$ for $i \in Y$.

Other schemes

Predicate-based encryption schemes based on the paring groups often employ this structure. Intuitively speaking, they hide/share the master secret into user secret keys as Sahai and Waters did.

If you need examples of implementations, we can find (proof-of-concept) implementations of more complex predicate-based encryption schemes in cryptographic libraries:

PBC and jPBC
Charm


If a cipher has key length shorter than plaintext, then it is not perfectly secure

Here's a more "down to earth" example. The following cryptosystem with plaintext space $\mathcal{M} = \{a,b,c,d\}$, keyspace $\mathcal{K} = \{1,2,3,4\}$ and ciphertext space $\mathcal{C} = \{A,B,C,D\}$ has perfect secrecy:

$$\begin{array}{c|c c c c}
& 1 & 2 & 3 & 4 \\
\hline
a & A & B & C & D \\
b & B & C & D & A \\
c & C & D & A & B \\
d & D & A & B & C
\end{array}$$

if the key is chosen uniformly at random independently of the plaintext (the table should be read as saying that, for example, encryption of the plaintext $a$ with the key $3$ yields the ciphertext $C$). The perfect secrecy means that an attacker who obtains a ciphertext has no "hint" about what the plaintext may be: for example if an attacker obtains the ciphertext $C$, it could be the result of encrypting the plaintext $a$ with the key $3$, or the plaintext $b$ with the key $2$, or the plaintext $c$ with the key $1$, or the plaintext $d$ with the key $4$, and all those cases will occur with probability $1/4$. By comparison, the following cryptosystem:

$$\begin{array}{c|c c c c}
& 1 & 2 & 3 & 4 \\
\hline
a & A & A & C & D \\
b & B & C & D & A \\
c & C & D & A & B \\
d & D & B & B & C
\end{array}$$

does not have perfect secrecy because if an attacker obtains the ciphertext $A$, he knows that the plaintext is not $d$, and it is also more likely that the plaintext is $a$ (which is the case with probability $1/2$) than $b$ or $c$ (probability $1/4$ each).

On the other hand, with the following cryptosystem with keyspace $\mathcal{K}' = \{1,2,3\}$:

$$\begin{array}{c|c c c c}
& 1 & 2 & 3 \\
\hline
a & A & B & C \\
b & B & C & D \\
c & C & D & A \\
d & D & A & B
\end{array}$$

an attacker obtaining the ciphertext $A$ knows that the plaintext is not $b$, so this system does not have perfect secrecy either, and it is easily seen that any cryptosystem with fewer keys than plaintexts will have the same problem.


The problem you described is addressed and solved in different way by the Broadcast Encryption: roughly the problem is how to encrypt a message intended to more than one recipient.
You described a naive approach to the problem, your solution is, indeed, probably the simplest one.

The Broadcast Encryption concept was formalized and defined by Fiat and Naor in their seminal paper Broadcast Encryption. Their solution is based on a binary tree where recipient are leafs of this tree and owns a key for every node from them to the root ($2^n$ leafs, $n-1$ keys per user): a ciphertext is encrypted using the minimal set of nodes covering the set of intended recipient.

Other solutions have been published, using both public and symmetric key cryptography. These attack different deficiencies of solutions to the problem: size of the ciphertext, size of the user keyring, revocation without re-keying, privacy preserving schemes, ...

Two kinds of broadcast encryption exist: one where you name the intended recipients and the other one where you ban a subset of all potential recipients. This first is similar to pay TV (you pay so you can decrypt the broadcast), the second to DVD encryption (all players can play a DVD unless they are banned). The Fiat and Naor solution is of the first kind.

Note that usually public-key encryption is used with the KEM/DEM paradigm, so the plaintext to be encrypted to multiple recipients is a random key for a symmetric algorithm.


Encrypt a file once with 50 characters password or twice with 25 characters?

Layering encryption doesn't effectively concatenate the keys (despite what intuition may suggest). The attacker can still attack the two passwords separately, such as by using a meet-in-the-middle attack. This means the effective key space (that is, the number of possibilities for the combined password that the attacker must try) is much lower for the double-layer scheme.

Because the keys can be attacked separately, two half-length passwords do not offer as many effective combinations as one full-length password. If each character in the password has $n$ possibilities (for example, a standard keyboard might offer 26 uppercase + 26 lowercase + 10 numeric + 30 symbols = 92 characters), the 50-character password has $n^{50}$ possibilities, whereas the two 25-character passwords only provide security equivalent to $2 × n^{25}$ possibilities. Using our example numbers, that's $90^{50}$ for the single long password vs $2 \times 90^{25}$ for the two shorter ones.

For perspective, the 50-character password has about the square of the number of possibilities for two 25-character passwords. It's a lot more.


That is right, but is it possible that the victim send me his encrypted symmetric key and I will send the decrypted key back?

I have not personally written any ransonware, nor have I examined how they operation; however if I were to, that is what I would do - once the victim has paid up, they would send a copy of the encrypted symmetric key, decrypt it, and send it back to them (so that the various files could be decrypted and restored).
Since we would never send the private key to the victim, they could not share it (and hence the concern the article you reference would not apply).


Hashing entropy generator output with SHA256

Generally seeds for PRNG's should be mixed in with the internal state using a hash function, and the output should be at least a hash away from the internal state. You could take some hints from the implementation of SHA1PRNG in the Sun JCE or from other hash based PRNG's on how to do this.

You do not want to forget the internal state, because in that case the output is fully dependent on the seed. If there is any problem with a seed, you would have predictable output.


What is ADH? Where is it standardized?

ADH stands for Anonymous Diffie-Hellman, ie unauthenticated Diffie-Hellman, also called "opportunistic encryption". It has been part of the SSL/TLS standards at least since SSLv3. It was also extended to ECDHE in RFC4492.

  The listed MAC algorithms are hash functions. Is it using HMAC?

Yes indeed.

  What does "Au" mean?

It most likely means something like Authentication mechanism. This clearly covers with the given ciphersuites as ADH suites have none there, RSA key-transport and DHE+RSA suites have RSA there (server authenticated via RSA signature), DHE+DSS suites have DSS there (server authenticated via DSA) and suites using static DH ones have DH there (server authenticated via his static DH public key).


Validating individual letters of a password reduces complexity of guessing that password by trying all possible variants, so I would suggest avoiding such a design.

PCP (probabilistic checkable proofs) is a well-known case of validating just a small portion of the "witness" (defined in that context), with focus on algorithm complexity.

Regarding "1st Edit": pass/fail response to "simplified" query is exactly how complexity is reduced. Random selection of letters requested might be considered a challenge/response scheme, on condition it can not be affected. Worst case would be repeated or single-letter queries.


Current mathematics theory used in cryptography/coding theory

Finite fields - which is a branch of algebra - is a must. It is, in some way, used in almost all types of cryptographic algorithms.

Also, you need some sort of basic programming ability since you will need to calculate time and space complexity of cryptographic algorithms. An "Algorithms" course  taken from a CS  department would be very useful.

My advice is, you can read the  first 2-3 chapters of Rudolf Lidl' s Finite Fields book. You don't need to understand every little detail in the book, just read that part and get the general idea, and that would be enough for the beginning.

But the bible for the beginners in cryptography is definitely, "Introduction to Cryptography" by Washington and Trappe. It is the most basic book amongst all in addition to being very  comprehensive. It  has a solution manual and nice exercises that you will enjoy solving. I personally learned a lot from it. Trappe covers almost every basic thing that you need to know as a beginner.


Insecurity in Needham and Schroeder protocol?

Maybe this question relate to public-key version of protocol.
In this case, adversary could start two synchronous exchanges with Alice and Bob, and use Alice responses to convince Bob, that he communicating with Alice. More information


Ok, here is one possible sketch of a brute-force style attack against OCB, which doesn't assume you know the nonce.  It takes 512 trial decryptions for every key tested, so it's a bit more expensive than, say, a brute-force attack on CBC, but only by a constant factor.

Let us assume that:

you have an encrypted message that is $16n+15$ bytes long
that you know the last 15 bytes of the plaintext
and there's another block $P_n$ that you have enough information that you can recognize it if we decrypt it properly.

If we look at the OCB processing of the last 15 bytes, we have:

$C_{last} = P_{last} \oplus Trunc( E(K, \Delta_{last} ))$

where $Trunc$ is a function that chops off the last byte.  So, we know the first 15 bytes of $E(K, \Delta_{last})$, namely $C_{last} \oplus P_{last}$.

To test a value of $K$, we iterate through all 256 possible values of the last byte $B$, and compute

$\Delta_{last} = D(K, (C_{last} \oplus P_{last}) || B)$

From each $\Delta_{last}$ value, we compute the corresponding $\Delta_{n}$ value (which is a $GF(2^{128})$ multiplication, so that's easy), and then compute:

$P_n = \Delta_{n} \oplus D(K, C_n \oplus \Delta_n)$

and check if that is a plausible plaintext value.

Once we have a plausible values for $K$ and $\Delta_i$, we can check the authentication tag to validate the decryption.

Once we have all that, we can also recover the nonce that was used to encrypt the message; this may be useful if related nonces were used to encrypt other messages with the same key.

Now, obviously this attack can be improved if we can get a plaintext message which is $128n+127$ bits long; that is unlikely in practice.


Significance of rotation constants in SHA-512?

The SHA-2 family is built from a block cipher in a Davies-Meyer construction, where the message is considered they key, and the current hash value the plaintext. The 2nd set of constants in the SHA-512 round function is 14, 18, and 41. Rotations are also performed in the message expansion (key schedule), and are also important.

The block cipher at the center of the compression function must behave in a secure manner, and the rotational constants were chosen in such a way that the block cipher is resistant to standard cryptographic attacks. The round count was then fixed to meet the security requirement of the hash digest, plus some wiggle room for new attacks.

SHA-2 was developed in secret at the NSA, so the above is partly speculative, however we do have good examples of how improper choice of rotational constants can weaken a hash function. During the SHA-3 competition, the Skein hash function was successfully attacked using rotational cryptanalysis, and a change in the rotational constants was made to prevent the attack. The attack with the old rotational constants was 22 rounds more effective than the best attack on Skein with the new constants; that is 30% of the full round count, which is substantial.

The attack seemed to exploit the specific combination of rotations and modular addition, both of which are heavily used in the SHA-2 compression functions. The continued lack of highly effective attacks on SHA-2 implies that its rotational constants were chosen well. The way that rotations are used in SHA-2 and Skein differ, but poor constants would still have prevented proper diffusion within the round, or in the key schedule. The best attacks are still reduced round differential and biclique attacks, and are not practical.


Fuzzy Extractor constructor for sequence reconciliation

Hamming distance based reconciliation for close secrets as maintained in famous paper by Dodis et.al on Fuzzy Extraction for close/noisy bio-metric data


Can we do modulus switching for number theoretic encryption?

Security goals like confidentiality is the reason to ask for encryption.
Modulus is chosen (for particular group types) on the grounds of hard problems associated with that groups; encryption strength is defined by level of hardness of that problems.

It would be nice to discover a hard problem related to some change of modulus, comparable to indistinguishability of Diffie-Hellman tuples of 4 group elements for ElGamal or $n$-th roots for Paillier with modulus $n^2$.


Reuse of TLS client key/certificate in challenge-response protocol

No, there are no problems (which I could see) with re-using the signature key in this scenario.

There are two potential concerns:

It may be possible to learn something about the private key using the challenge-response protocol
It may be possible to re-use the signature of a run of the challenge-response protocol for TLS

The first concern is clearly invalid, as any decent signature won't allow you to learn anything about the private key just be asking for signatures of (chosen) messages (this is the standard security notion for signature schemes). The same argument holds for TLS' client authentication.

The second concern is also invalid as an attacker can't control the messages being signed in neither TLS nor the challenge-response protocol. In TLS, the client signs the complete transcript being exchanged yet, including the client's random and the server's random value, which the attacker can't control both. The same argument holds for this scheme. While the attacker can control $r_B$, he can't control $r_A$ and thereby he would have to hope that the random values repeat in the protocol (extremely unlikely) or that the hash to be signed is the same in TLS, which would imply a collision on the hash function, which is extremely unlikely if the hash function is chosen somewhat decently (like SHA-256).


Constructing of 16x16 Involutory Binary Matrices of Branch Number 7

I guess you can construct those matrices simply with M1h and M2h with a double and add algorithm.

Clearly, $M_{4h} = M_{2h} \cdot M_{2h}$ and $M_{Fh} = ((((M_{2h} \oplus M_{1h}) \cdot M_{2h}) \oplus M_{1h}) \cdot M_{2h}) \oplus M_{1h} $. From this you can deduce how to construct all the remaining matrices.


About Primitive roots mod n in Diffie-Hellman

The problem you want to make hard in Diffie-Hellman type groups is taking discrete logarithms, whereas you want exponentiation to be easy. Now when you pick a subgroup $G$ of $\mathbb Z^*_n$, the cost of exponentiation will be roughly proportional to $n$ whereas the cost of taking discrete logs will be proportional to $\sqrt{k}$ where $k$ is the order of the largest subgroup in a decomposition of $G$. (Actually, for the number field sieve the formula is more complicated and less than $\sqrt{k}$, but it is still an expression in $k$.) So you want to have $k$ big to get your security up and once you've decided on $k$ you want $n$ to be as small as possible to make the whole thing efficient. In other words, you want to minimise the computation cost to security level ratio $n/k$.

The best possible choice is to let $n = p$ a large prime: if $n$ were not a prime and had nontrivial factors, then $k$ couldn't be larger than the largest of these factors, and all other factors are just slowing things down without adding any security. Since $\mathbb Z^*_p$ has $p-1$ elements which will be an even number, there's always a subgroup of order $2$ and the best possible choice of group order is $q = (p-1)/2$ again a prime (in which case $p$ is a "strong prime"). For such a choice, $k = q$ as it doesn't have any nontrivial factors, so the computation cost/security level ratio is $n/k = p/q$ is approximately $2$, the smallest possible. And in this case any generator is automatically a primitive root.


Is it possible to execute elliptic curve encryption on small sensor-tags CC2650?

The CC2650 is a Cortex M3 with 128KB flash memory and 20KB SRAM.

This is definitely not enough for RELIC or OpenSSL.

TinyECC fits, but even if this is only for signatures, some symmetric cryptography will be needed in addition to it.

Better options would be Cifra, libhydrogen, tweetNaCl or a minimal BearSSL build. They all fit in about 20 KB flash memory and require little stack to run.


What is the probability of breaking the AES algorithm?

Of course it is technically possible to crack AES. The method for doing this is to guess the correct key. Assuming you know something about the plaintext, you can easily verify that the key you guessed resulted in the correct decryption.

The probability of breaking AES using this method? AES has 128, 192 and 256 bit key variants. Thus if there are $n$ bits in the key, the probability that your guess is correct is $\frac{1}{2^n}$.

What is the role of increasing the rounds and does this make it harder to break? In general, more rounds are required to diffuse bits. That is why you see more rounds with the larger key sizes. In the specific case of guessing the key, it only slows down decryption. It does not change the probability of a break. There are other articles on this site on increasing rounds. I'll try to find them and add links.

What is the contribution of each round towards enhancing the security? This is hard if not impossible to say. If you modified AES to have only 1 round, it would be trivial to break. Up it to 10 rounds for AES-128 and we can't break it. Up that to 1 million rounds and the cipher isn't really much more secure but takes so long to encrypt or decrypt that no one will use it (a kind of dimishing returns). See fgrieu's comment for additional information.


It all boils down to the amount of entropy in the second string.

How is that second string generated?

If a human generates it, you can be pretty sure that most of the time it will be easy to figure it out. If a computer generates it using a cryptographically strong random number generator, and the string has sufficient length (say more than 80 bits), it will not be feasible for an attacker to guess it.


Counting the number of binary solutions of quadratic system

Actually, it would appear that a standard breadth-first search works for this specific problem.

The algorithm tracks all the solutions that satisfy the equation up to bit $n$, and for each such solution, it considers all possible extensions to bit $n+1$ (there are four), and whether they satisfy the condition on $c_{n+1}$.

If you use this algorithm on the standard factorization problem, it fails miserably (as the number of intermediate solutions approximately doubles at each step until you hit the half-way point); this happens because each extension satisfies the next condition with probability 0.5.  However, for this problem, the condition that needs to be satisfied is $\sum_{i+j=k}p_iq_j = c_k$, which for large $k$ has a considerably smaller probability of holding for an incorrect solution, and hence incorrect solutions are pruned much faster.

I threw together an implementation, and it showed promise; given the arbitrarily product $314159 \times 271829$, such a state search gave a maximum of 22 intermediate solutions (11, really, as I counted solutions with swapped $p$ and $q$ separately), and this was after processing bit 11.

This finds all the solutions fast enough that you should be able to use this to obtain a count.


Does AES-128 have the same strength as AES-256 with a padded key?

In this scenario, it is better to use AES-128 than AES-256 if you are to 0-pad a 128-bit key to 256 bits.

If you 0-pad, the round key for round 1 is all 0s, and round 3 is effectively worthless as well. So now you are down to 12 effective rounds vs 10 for AES-128.

Then you need to look at the effectiveness of the remaining keys. Here are some example key schedules for AES-256 (0-padded 128-bit key) and AES-128:

00  a1b625fe 019e24c8 0a7f661b 9ad9d51c    00  a1b625fe 019e24c8 0a7f661b 9ad9d51c
01  00000000 00000000 00000000 00000000
02  c2d5469c c34b6254 c934044f 53edd153    01  3d0e10fc 3c903434 36ef522f ac368733
03  ed553eed ed553eed ed553eed ed553eed
04  9780ba2c 54cbd878 9dffdc37 ce120d64    02  fe9f15e9 c20f21dd f4e073f2 58d6f4c1
05  669ce9ae 8bc9d743 669ce9ae 8bc9d743
06  8dbd6726 d976bf5e 44896369 8a9b6e0d    03  86f5e352 44fac28f b01ab17d e8cc45bc
07  18887679 9341a13a f5dd4894 7e149fd7    04  e36ea834 a7946abb 178edbc6 ff429e7a
08  834e9df5 5a3822ab 1eb141c2 942a2fcf    05  3978842f 9eecee94 89623552 7620ab28
09  3a6d63f3 a92cc2c9 5cf18a5d 22e5158a    06  0d40336d 93acddf9 1acee8ab 6cee4383
10  fddd44bc a7e56617 b95427d5 2d7e081a    07  e1101b37 72bcc6ce 68722e65 049c6de6
11  e29e5351 4bb29198 17431bc5 35a60e4f    08  6fe2c58b 1d5e0345 752c2d20 71b040c6
12  794b6037 deae0620 67fa21f5 4a8429ef    09  db412299 c61f21dc b3330cfc c2834c3a
13  34c1f68e 7f736716 68307cd3 5d96729c    10  5b64ce86 9d7bef5a 2e48e3a6 eccbaf9c
14  a707f037 79a9f617 1e53d7e2 54d7fe0d

Round 5 is effectively 64-bits instead of 128, and while you cannot see it with this example, rounds 2 and 4 are also very linear with respect to subkey 0, and only at round 6 do we see a level of acceptable nonlinearity (we get this at round 3 with the 128-bit key schedule). Further nonlinear expansion is also slower, I would suggest the final round keys are similarly linear to the original key for both key schedules.

It is probable that even with the extra 4 rounds, the full AES-256 cipher with the padded key will be weaker than AES-128 against a variety of attacks, while taking 40% more time to encrypt. As CodesInChaos suggested, expanding a 128-bit key to 256-bits using a cryptographic hash will result in a stronger cipher than AES-128 while still only having an effective key size of 128-bits. I would not recommend duplication of the key to expand to 256-bits, round key linearity is still high, and it is probable existing attacks will be more effective.


Is the nonce in GCM mode used as key for HMAC? And how to send it?

Is the nonce used to generate a "probabilistic ciphertext", as with IV in CBC mode? Is the nonce also used as key to generate the HMAC for the ciphertext? And therefore only specifying this one I would already obtain an authenticated ciphertext (without having to specify the AAD data)?

Yes, it provides probabilistic ciphertext.

Contrary to you mentioning HMAC, GCM does use a MAC construction but it is called GMAC. The GMAC tag value is encrypted using the initial counter value, so the authentication tag - the MAC value generated by GMAC - does rely on the IV.

  Or is the AAD data the one used to generate the HMAC for the ciphertext (I'm pretty sure it's not)? And if not, what is the AAD used for? "To provide an additional context HMAC to accompany the ciphertext"? Could somebody provide an example of this?

AAD - the additional authenticated data - is included in the authentication, but it isn't responsible for creating the authentication tag. Actually, it is often empty. It can be used for any data that needs to be authenticated, but doesn't need to be confidential.

For instance the header data of a mail message or IP packet could be AAD data. It might be useful to authenticate it so the receiver address isn't altered, but of course the data to route the package to the right address needs to be readable by the routers in between.

  ALSO.., independently of which element is used as key to generate the HMAC for the ciphertext.. How must this one be protected? As far as I know, the nonce does not have to be random, it can be a numeric sequence like 1, 2, 3.. for each encrypted message. This seems pretty guessable by an attacker. So isn't it dangerous to use a guessable nonce, or even send it in clear with the cyphertext?

The authentication tag is protected by the same key (and for GCM, indeed, the same cipher / mode of operation) as used to keep the data confidential. So with most AEAD modes you just need one key (SIV mode cheats on this: it requires a double size key and then just splits it in half). And yes, for GCM mode you just require a unique IV/nonce, but remember that it breaks almost completely if you reuse the IV even once.

Please do not look at the Wikipedia pages to understand GCM, instead check section 7.1 of NIST. Note step 6: 6. Let $T=\operatorname{MSB}_t(\mathit{GCTR}_K(J_0,S))$ where $S$ is the outcome of GHASH and $J_0$ is directly derived from the IV ($T$ is the tag, $t$ the tag size and MSB the most significant - leftmost - bits, to be complete). Note that the hash is not secure without this block encrypt.

So the authentication tag is always dependent on the IV value. Note that a unique IV is required even if no data is being encrypted by GCM mode. The GMAC relies on the uniqueness of the IV, as this answer by poncho explains.


In context of interactive proof systems (including zero-knowledge proofs) completeness means the same as the term correctness as used for many other (interactive) cryptographic schemes or protocols. I guess that's mainly due to historical reasons (there are even some people that use correctness instead of completeness in context of zero-knowledge proofs).

Basically, both things say that if everything happens honestly, then it works out as it is supposed to be. Note that completeness as well as correctness may not be perfect. For instance, zero-knowledge proofs may have a completeness error, i.e., even if the statement to be proven is true and both - the prover and the verifier - behave honest, the verification may only work with some probability (close to one). Similarly, for public key encryption schemes the correctness may also only hold with a probability close to one, i.e., that decrypting a ciphertext for a message may lead to some different message (even under some honestly generated keys).


Which attacks are possible against raw/textbook NTRU encryption?

Without a well-designed padding system it may be possible to craft a ciphertext that the decryptor may or may not be able to decrypt properly. Whether the decryptor is able to do so will depend on the private key. The concern is that an attacker may be able to craft a string of ciphertexts, listen in to whether they decrypt properly, and finally deduce the private key from the bits denoting the success/failures.

To review how raw NTRU encryption works: select a message $M$ (as a polynomial), select a random lightweight polynomial $R$ and then compute the ciphertext $C = RH + M$ (where $H$ is from the public key).

To decrypt it is required to compute the plaintext $P = CF$ (where $F$ is from the private key), computing everything $\bmod q$.  Because of how $F$ and $H$ are related, this is $pRG + FM$; the next step is to evaluate this polynomial $\bmod p$; assuming that no wrap around (modulo $q$ has occurred). T his strips off the $pRG$ term, giving $FM \bmod p$; from that, it is possible to recover $M$. However, if some coefficient does wrap, then the decryptor will recover an incorrect value for $FM \bmod p$; this will give the wrong $M$.

So, what can cause a wrap?  Well, wraps will occur if a coefficient of the polynomial $RG$ is too large. It is too large when it is outside the range $(-q/2, q/2)$ (not considering the implicit $\bmod q$ operation). $R$ is a value that the encryptor (who may be the attacker) selects, while $G$ is a value that can be used to calculate the private key from the public key. By artfully selecting $R$ values, an attacker could probe $G$ and - over time - recover it. Note that the $FM$ term can also contribute to the wrap; the attacker can account for this by selecting $M=0$.

There are guidelines on how an honest encryption should select $R$ values so that decryption failures don't leak information. An attacker will however ignore these guidelines. NAEP prevents the key recovery attack by making the polynomial $R$ a deterministic function of $M$ (and some random bits that are included in the message). So after the decryptor recovers $M$ (and those random bits) we can recompute what $R$ should have been. We can then compares it to the $R$ that was actually used. If they're different then that also results in a decryption failure. An attacker can therefore not use a value of $R$ that is outside the guidelines.


How Can I decrypt this VNC Authentication handshake?

challenge":"318E90D502A379A7B1583C35DB772138"}
{"id":"handshake","authentication-response":"1D214EF554123712A0DC9BCF003C27F4"}
{"id":"handshake","authentication-passed":true}

Ok, I got it.  Just answering for anyone else who stumbles here.  While not documented, RFB mirrors each bit.  Using the key of all B's, I was able to get my result, as B is a palindrome.


Why does LastPass use exactly 100100 PBKDF2 rounds

LastPass uses PBKDF2 with SHA256. The number of iterations (also called count) in PBKDF2(PRF=SHA256, Password, Salt, iterations, dkLen) is used against the password crackers. With the increase of the computation power, the developers change the number of iterations from 5000 to 100100 and there is nothing special about it other than being large. Having different numbers from others only can be considered a pre-countermeasure that may be helpful in the future. You can still adjust the iteration number to any value that you want.

The salt, on the other hand, is used as a countermeasure against Rainbow Tables. Actually the salt simply killed the Rainbow Tables. They are no longer helpful if the sites use a salt-based password hashing.

With a good PBKDF function with properly used salt, the only way to break is the brute-forcing the possible password and combinations. The number of iterations linearly increases the cost of brute-force. That is, if you double, the attacker with the same system need double time.

Keep in mind that there is an old saying inside the US National Security Agency (NSA):

$$\texttt{Attacks always get better; they never get worse}$$


MixColumns implements a matrix multiplication, so InvMixColumns is the multiplication by the inverse of that matrix. Thus, it boils down to computing the inverse of the matrix. It can be tedious to do by hand, but it involves only straightforward computations. Alternatively, look up the AES standard itself (FIPS 197): the inverse matrix is spelled out explicitly in section 5.3.3.

More generally, FIPS 197 is quite readable (as standards go) and if you want to know how AES works, it is recommended to read it through (and in particular section 4, that gives some details on the underlying mathematics).


Does encryption of data/information take place in peer to peer networks like Gnutella, Bittorrent?

BitTorrent, when encryption is used (optional in most clients), uses the Diffie-Hellman protocol for key exchange and RC4 for confidentiality. It also drops the first 1kb of data from the RC4 output as part of the specification.

There is no authentication, not really enforceable anyway due to the nature of peer-to-peer sharing networks. Standard theory applies; man in the middle is possible, but a passive attacker, only able to observe traffic, cannot see the content of the messages being sent.

The idea is to stop people from figuring out specifically what data is being sent, but bandwidth analysis will clearly reveal the use of peer-to-peer technology. Other factors, such as popularity (peer count) and total bandwidth may help in identifying the specific files being downloaded.


This is useful to know in general.

Given the Sbox map, generate the truth tables for the bits of the map.
From the truth tables, obtain the algebraic normal form, via the Mobius transform.

So, given an $n-$bit truth table, say $$T=[f(x): x \in \mathbb{F}_2^n]$$

where $$x=(x_1,\ldots,x_n)$$ ranges over the vector space $\mathbb{F}_2^n$ in standard order, the function has an anf representation given by
$$
f(x)=\sum_{y \in \mathbb{F}_2^n} a_y \prod_{1\leq i\leq n~:~y_i=1} x_i
$$
which means the variable $x_i$ is included in the monomial product corresponding to the coefficient $a_y$ if and only if $i$ is in the support of the vector $y.$

So if we had $y=(y_1,y_2,y_3,y_4)=(1,0,1,0),$ for $n=4,$ the coefficient $a_y$ multiplies the monomial $x_1 x_3$.

The transform computes the coefficients $a_y$ by the sum
$$
a_y=\sum_{x\preccurlyeq y} f(x) ~(mod~2),
$$
where $x \preccurlyeq y$ means the support of $x$ is a subset of the support of $y.$

The complexity is $N \log N$ where $N=2^n,$ so this is a fast transform.


Reducing the XOR's in Implementation Cost

Yes. I have a solution with 5 $\oplus$.

Hint 1: That would not work with $*$ (ordinary multiplication, or even multiplication in $\Bbb Z^*_p$) where there is $\oplus$, because we must use a property of $\oplus$ that $*$ does not have.

Hint 2: The right path is greedy.

Hint 3: It's key to compute $y_3$ late, with just one extra step.


How to generally define it

Modern applied cryptography usually defines the (unbounded) message space as:
$$\mathcal M=\{0,1\}^*$$
where the star denotes you can have arbitrary lengths. Formally, $A^*:=\bigcup_{n\geq0}A^n, A^0=\varepsilon,A^{n+1}=A^n\cdot A,n\in\mathbb N$ where $\cdot$ denotes concatenation.

If you ask somebody who's really into the theory of programming languages, they're gonna basically say you the same, but will probably replace the $\{0,1\}$ with an arbitrary alphabet $A$.

Now to the formula you asked about:
$$\{\forall c\in A\}$$

This is not only syntactically wrong (a quantor always needs an accompanying statement), but also makes no sense at all. After all, you're saying that "the set consisting of 'for all c in A' " which is at most a set of syntactically wrong logical formulae. However if we were to leave the $\forall$ away, you basically wouldn't have gained anything over a plain use of $A$, as the set consisting of all elements in A basically is just A.
If $A$ is assumed to be an alphabet, you'd indeed need a length qualifier, something like the star in the above notation or a concrete instance where you'd fix the length to some (arbitrary) value $n$.


Randomized functions cannot increase statistical distance

Second question:

$\Delta$ is defined on distributions so the distributions of $f(X)$ and $f(Y)$ are the same, since $X,Y$ are both uniform. The supremum definition makes this clearer.

First question:

Unless the map is one to one, hence a bijective,  when equality holds, the probability that $f(X)=f(Y)$ can only increase compared to the probability that $X=Y$. Prove this for binary distributions and then subpartition and use induction to conclude the general case by using conditional probabilities.


End to end encrypted web chat app with stored messages in database

Just keep all user-associated information encrypted using the user's password. Be sure to use a secure password-based key-derivation function (PBKDF2 seems to come to mind but personally I prefer Argon2) because passwords make terrible encryption keys. Here is an example of how it might be done:

User generates random encryption key (master key or MK) on the client-side (not based on a password, actually random)
User generates a key-encryption-key (KEK) from their password
User encrypts MK using the key KEK
User uses MK to encrypt their data, within their browser.

This way, if a user is to change their password they can simply re-encrypt MK with a new KEK. Or, they have the option to change their MK and KEK if they think their MK has been compromised. You don't need anything more, since the encryption does the work. Everything else can be done as if client-side storage is available, since it's secured with MK.
This sounds mostly like what you're doing, but it doesn't sound like you're using a KEK or key-derivation function, both of which should be the case if the system is to be secure and scalable.

A key pair is created and the private key is encrypted symmetrically using the entered password.

Encrypt with MK, not the password

Y's message is encrypted in his browser two times

Because there are two versions of the message stored in the database, a potential attacker could have an easier job of brute forcing the original content. Though, this might be prevented by signing both messages with some userspecific value, i.e. the username

This doesn't affect security, assuming you do it right. Each message should be encrypted with a random IV for this to work. Make sure it's random, and unique to each message. This will double the amount of information you need to encrypt, but anything else is insecure. The IV can be known by the server, without compromising security, and as such, needs not be encrypted.

Keeping "raw" password in browser as a key for symmetric encryption/decryption maybe a concern.

This is correct. Definitely derive the key from the password.

Passwords are limited in length, and may not provide crytographic high strength if used as symmetric key directly. One option could be to derive the key from it

Definitely do this! Use a function specifically designed to derive encryption keys from passwords.

var key = crypto.createCipher('aes-128-cbc', 'secret password');

This is a bad idea (sorry, but it is). AES isn't a key-derivation function. Please don't use AES to derive keys! use PBKDF2 or Argon2; they're specifically made for exactly that purpose.

This approach wont allow server-side search on the chat messages. Client side search can be implemented on a limited text loaded into UI component.

That is correct. However, if I were the one using the service I'd expect that; I'd automatically distrust anything that allowed server-side search.

The server does not have to decrypt and re-encrypt all messages when a user changes their password

This can only be done if you use the MK-KEK scheme I described. I should also add, the client should do the encrypting and re-encrypting, not the server.
Changing the password means you have to at least re-encrypt something. Also, if the MK is compromised you still have to re-encrypt everything. Be ready for that, or risk sacrificing security (which to me is an unforgivable sin).


Invalid challenge-ciphertext in IND-CPA and IND-CCA games

$A$ outputs a bit depending on whether it thinks you gave it an encryption of $m_0$ or $m_1$.

If you cheat and give it something completely different it has no usable information but still needs to output a bit.

If your PKE scheme has invalid ciphertexts $A$ might be able to detect that or not depending on the specifics.

So if you want to exchange your encryption of $m_0$ or $m_1$ for something else in a proof you have to show that $A$ cannot distinguish between these two situations.

Intuitively you can think about it this way:
If $A$ had some way to distinguish between the real security game and your simulation it means that your simulation looks different. So how do you know that whatever $A$ did to attack the original game will work on your simulation if it doesn't look the same to $A$?


How to avoid a chicken and egg scenario with encrypting passwords?

As fgrieu notes, the problem as specified is unsolvable: if the server alone should not be able to decrypt the files, then there must be something (in this case, the password) possessed by the user but not the server which is needed to decrypt them.  If the user loses this extra information, there's no way the server can provide them access to the files — if it could, it could also provide itself with access.

However, let's step back and think about what a "password reset" really accomplishes.  Basically, it's a mechanism that allows users to prove their identity and access their data using some proof of identity other than their usual password.  For example, in the case of a password reset e-mail, the proof of identity is effectively access to a predesignated e-mail account, to which the password reset code is sent.

(There are various fundamental security concerns with that, as with most "password reset" schemes, but I'll ignore those for now and assume that having a password reset mechanism has been found necessary and desirable, and that the only issue is how to implement it.  I do strongly recommend that the user should be able to opt out of any such mechanism in advance, if they wish to do so in order to minimize the attack surface for their account.)

So, instead of having the server send the user a single-use password reset code after the user has forgotten their password (which is impossible in this case), you could allow the user to request one in advance, to be saved in case they need it later.  Indeed, you could even send one automatically (unless the user explicitly opts out) as part of the signup process, and resend a new one whenever the previous one has been used.

In effect, you'd be allowing your users save a back-up key to their account.  I should note that this is not a new idea: for a recent example, the Firefox Sync service does something quite similar.

What should this back-up key contain, then?  Well, obviously it needs to allow the server to access the user's internal key, just like a normal password would.  It probably should not be the user's normal password, though, or anything related to it, just to avoid concerns about password reuse.  Also, if you want the back-up key to be single-use, it should not simply be a copy of the internal key either.

One simple solution would be to just generate a random password (of sufficient length), encrypt the internal key with the password, save the encrypted key at the server and send the password to the user as their back-up key.  Then the only difference between this back-up key and the user's normal password would be the actions the server takes when the user logs in with the back-up key (typically, request a new password, generate and send a new back-up key, and replace the old ones so that they can't be used again).


Indistinguishability versus semantic security?

The definition of semantic security has its origins in the definition of perfect security, where the adversary's information about the message is the same after seeing the ciphertext. Semantic security is exactly the same thing in a computational setting: the adversary's "practically available" information about the message is the same after seeing the ciphertext.

This is formalised by simplifying the problem: the adversary chooses an "interesting" predicate $f$ on the message space and a way to choose messages such that the predicate holds with probability $1/2$. Then we must prove that the adversary cannot determine the value of the predicate with probability significantly different from $1/2$. (You can define a variant of perfect security in exactly the same way.)

Then it turns out that there is a simpler notion - indistinguishability - that is equivalent to semantic security. This notion is easier to work with, so everyone uses that one, to the extent that semantic security is often identified with indistinguishability.


Is there a deterministic number generator that allows me to share some (not all) numbers I've generated using a smallish seed?

A really basic insecure example would be to use sha256(seed + n) where n starts at 0 and increases for each number. You would share the seed plus all the n values you want to share. Obviously this means people could generate the numbers I don't want them to by filling in the missing n values.

You could extend that idea and use $\operatorname{sha256}(seed || n || r_i)$, where $r_i$ are smaller random numbers. By using 32-bit seeds to produce 256-bit random numbers, you would save almost 90% of the transmission and storage costs.
However, anyone could tell an unrevealed number was one of the $2^{32}$ that could be created with that seed and n.

If that's not acceptable, you could build hash trees, where you start from one seed and at each level derive two seeds from one, eventually ending in the random numbers desired. (There would be one hash tree for "left" and one for "right" values in the pairs.)
Then you could reveal any seeds for which the whole subtree should be revealed. On average this could save almost a third of the data.

As a special case of the above, if you just used a new seed every other left/right value (i.e. left of the first two pairs would be derived from a single seed), you could save exactly 25% of the data on average with simpler logic than a whole hash tree requires.


Examples of Weak Cryptography being exploited in the wild by cybercriminals?

I would also be interested in attacks against primitives that are known to be weak, provided they were against some notable company (where "notable" essentially means "something an average person may have heard of").

The first example that comes to mind in TJX's use of WEP 5 years after the break was announced; that lead to millions of credit cards being stolen.


How 2 rounds in AES achieve full diffusion?

AES diffusion is taking cared of by 3 main functions:

SubBytes
Shift Rows
Mix Columns

SubBytes works as a 8-bit S-box. Thus if one bit change, the 8 bits of the byte are likely to change. With this step, each bit of a byte depend of each other.

This modification on the byte is then translated through the state via Shift Rows (still 1 byte affected) and then through the column (we moved from 1 byte affected to 4 bytes affected).

With one round, we therefore impacted on 4 bytes.

By doing it once again we will be affecting $4 \times 4$ bytes or the full state due to the nice coverage provided by Shift Rows and Mix columns.

Thus after 2 rounds, each bit has an influence on the full state.

This could be summarized by the following image where $\star$ represent a modification of a bit (and then byte).


It is possible to do, but depending on the performed operation, it may not be useful at all, so you have to choose the operation carefully.

The ultimate goal of FHE is to perform generic computations over encrypted data. That is, you have a generic function $f$ and you want to be able to compute it using encrypted inputs, so that:

\begin{equation}
f(\mathsf{Enc}(x), \mathsf{Enc}(y)) = \mathsf{Enc}(f(x,y))
\end{equation}

If you encrypt the AES key, and perform generic computations on the encrypted key and some other encrypted input, then, thanks to the homomorphism of the FHE scheme, you will obtain after decryption the computation over the key and the other input to the function. Therefore, depending on the computation (i.e., the function $f$), this could produce a different AES key, and the AES encrypted data cannot be retrieved with the resulting key.

However, that does not mean that what you suggest is not useful at all. A possible scenario is that the operation you perform over the encrypted data does not modify the original value, for example, when FHE is used for implementing a proxy re-encryption functionality. In this case, the original message would be the AES key encrypted under some public key $pk_1$, and the homomorphic function is actually decrypting the AES key under $pk_1$ and encrypting it again under $pk_2$. This way, when someone uses $sk_2$ to decrypt the result, he will obtain the original AES key.

Suppose that you have your AES key, $K$, encrypted under $pk_1$, that is, $\mathsf{Enc}_{pk_1}(K)$. You also have a FHE scheme so that $f(\mathsf{Enc}_{pk_2}(x), \mathsf{Enc}_{pk_2}(y)) = \mathsf{Enc_{pk_2}}(f(x,y))$, for some other public key $pk_2$. Now simply set $x = sk_1$, and $y = \mathsf{Enc}_{pk_1}(K)$, so:

\begin{equation}
f(\mathsf{Enc}_{pk_2}(sk_1), \mathsf{Enc}_{pk_2}(\mathsf{Enc}_{pk_1}(K))) = \mathsf{Enc_{pk_2}}(f(sk_1,\mathsf{Enc}_{pk_1}(K)))
\end{equation}

As you can see, if $f$ is designed to decrypt ciphertexts using the corresponding secret key, that is, $f(sk_1,\mathsf{Enc}_{pk_1}(K)) = K$, you are implementing a proxy re-encryption scheme that transforms ciphertexts from one public key to another, without altering the original message:

\begin{equation}
f(\mathsf{Enc}_{pk_2}(sk_1), \mathsf{Enc}_{pk_2}(\mathsf{Enc}_{pk_1}(K))) = \mathsf{Enc_{pk_2}}(K)
\end{equation}

There are other types of use cases; see for example the ones in mikeazo's answer.


How to build disk encryption system using forward permutations like Gimli?

Disclaimer: I'm one of the authors of the said permutation.

Gimli does not aim to be used as a block cipher (in the traditional sense of it: $x \to (\sigma \circ K_{\mathit{add}})^{\mathit{nb}_{\mathit{rounds}}}$ with a block size of 384 bits or similar constructions); it is better to use it with a sponge construction such a Monkey-Duplex/Monkey-Wrap or Farfalle.
An example of such a construction would be the design of Ketje Sr.
No Idea.

  Imagine there's no blockciphers, it's easy if you try :-)

  Joan Daemen at FSE 2017 [abstract] [slides]

(I really advise you to have a look at the slides.)

The idea is here is to have a unique permutation (Gimli? :D) on which you can derive the rest (hash functions, CPRNG, etc.). Sure you can use a Davies–Mayer or Even–Mansour with Merkle–Damgård construction to build a hash function from a blockcipher. But using a sponge construction is more elegant and efficient: you only have one code for the permutation and the design is easier to read (thus understand and verify).


Can hashes be used to generate larger random numbers?

No, actually your 32-bytes would only be a representation of the 8-bytes random (or pseudorandom) number. In this case if I want to attack you system (eg. by brute force) I need only to perform 2^8 attempts instead of 2^32 as someone could expect. This occurs because the 32 hash is only a deterministic representation of a very small 2^8 number.


Multiparty key exchange for end-to-end encryption

Well There are many options to do so. One of them and the most easy to implement and naive one is to do one of the following:

Each participant sends its own temporary symmetric secret key to others via pairwize secure channels. Every time each participant receives a message is reiceived from him/her/it uses this key to decrypt it. (I think WhatApp does this using Signal's Sender Keys)
The rooms initator owner (The one who wants to talk) sets up pairwize key generation with the one who participates and sends the common room/chat key.

An another Option (and the most efficient one) is to use a Group Key Agreement protocol like ART or the (n+1)sec uses.

The only Difference is when you use Diffie Hellman in each protocol modify it to use the variety of Diffie hellman that uses Eliptic Curves or even Deniable Group Agreemens Such as 3XDH like signal does.


Is frequency analysis the only attack on a simple substitution cipher?

Yes, there are many. Here are the few that I know:

Brute-Force: Simply trying all possible keys.
Kasiski examination: Exploiting the repeated words in the ciphertext to figure out the key length in Vigenere Cipher.
Friedman test aka Kappa Test: Measures the unevenness of the cipher letter frequencies to break the Vigenere cipher.
Key elimination: Eleminate the key by XORing two plaintexts with the same key.


True random numbers generated by sensors

Tl;dr: In theory, yes, if you do it carefully.  But in practice, it is better to use SecRandomCopyBytes().

Breaking it down a bit first, we step into a definition.  "True" random numbers of the kind you are discussing are those that are truly unpredictable, where the preceding data has absolutely no relationship to the next data.  This measure of unpredictability is called "entropy" by the random number crowd.

You are asking "are physical sensors good sources of entropy?"  The answer is "they can be", but it depends largely on what they're measuring and how often they're sampling it.

An accelerometer in an iPhone is a poor source of entropy if the phone is lying on your desk, because if I measure a string of values and they're all equal, the chances are pretty good the next one is equal as well.  It's also not a good source if you're simply reading it while the owner is performing a rhythmic activity, such as walking.  The motion of an accelerometer during walking is so predictable that smart pedometers (such as the fitbit) have an acceleration profile that can tell the difference between walking with it and just shaking it.

That is driven by the sampling rate.  If you are reading samples 60 times per second, that walking profile curve is going to be very visible.  But if you're sampling only once every ten minutes, even a marching band member is unlikely to yield predictable values over that duration.  Of course, sampling infrequently produces less usable entropy over time than does rapid sampling.

If you can recognize events with the accelerometer, such as a "walking step" or a motion reversal, you can measure the time between events using a high precision timer or a CPU cycle counter.  Repetitive human motion is precise only to a certain degree, such as a tenth of a millisecond.  Any measurements taken with a much more finely grained clock, such as nanoseconds, will be influenced by random biological variances between them.  If you take nanosecond timings (or CPU cycle counts) between two accelerometer events and keep only the bottom 8 bits, they'll all be unpredictable.

Most secure random number generators have an "entropy gathering service" continually running on a machine.  It's job is to harvest entropy from multiple sources over time.  Measuring user keypress timings and mouse movements using the high precision clock or the CPU cycle counter, the number of processes running at a given time, the total number of memory bytes allocated, network connection timings, hard drive seek times, all these things that the engineers "hope" are unpredictable are each measured just a few bits at a time, and those bits are mixed into and stored in an entropy pool.  The values in the pool are generally "stretched" by feeding them into a cryptographic algorithm (such as a stream cipher or block cipher) to produce a larger sequence of unpredictable numbers from a smaller input.  I believe Microsoft's CryptoAPI draws something like 512 bits from the pool and uses them as seeds to fill a buffer of random bytes.  Whenever a random number is requested, data is immediately returned from this buffer.   The buffer holds no more than 128 kb of random bytes, after which the random number generator returns to the pool for more seed bits and refills the buffer.

An accelerometer would be a good contributor to the pool if you were careful to recognize a stationary sensor and not harvest the bits generated when it's not moving, and use extraordinarily precise timings between events instead of directly sampling the raw values generated during the events.


Should a tweak value be secret like a key or visible like an IV?

The way it is defined in the paper "Tweakable Block Ciphers" by Moses Liskov, Ronald L. Rivest and David Wagner:

  A tweakable block cipher should also be secure, meaning that even if an
  adversary has control of the tweak input, we want the tweakable block cipher
  to remain secure.

Furthermore:

  For this operator, we call the new (second) input a tweak" rather than a nonce" or initialization vector," but the intent is similar.

so it is intended to be similar to an IV or nonce, not to be similar to a secret key.

Although a higher level mode of operation could still define the tweak to be secret, it certainly isn't intended to be, and it is unclear what the advantage would be, given that the block cipher itself doesn't depend on it.

So the only reason why the tweak would need to be kept secret is that it itself contains information that needs to be kept secret for other uses.