What to do when crib dragging does not work in OTP (One-time pad) ciphers?

I'm going to assume this isn't homework because otherwise reading this answer would count as cheating. If it is homework please tell me so I can delete this answer.

Crib dragging does work, you just need to be more persistent. I wrote a script (available via GitHub) that answers your question:

#Use this tool to solve multi-time pads
#Written on 4th march 2016
#Took me a good 30 minutes
#How this tool works:
#Suppose you guess a crib " the "
#We have n messages each of length k
#For each of the n messages and at each position k we want to guess the crib
#However, we can make our lives vastly easier if we guess the other way round:
#Instead of guessing each message separately, we guess at the same position for all the messages at the same time
#This will make it easier to spot when crib for message m at position k produces the wrong output for any other message
#Therefore, what this program does is to guess for each combination of message and position the crib for all messages at position k
#Suppose at message m position k the plaintext is " the ", then we can derive the key at position k with the length of our crib
#Once we have derived that part of the key we then apply it to the rest of the messages to see if we get a sensible output
#Therefore for any crib there are n * k outputs where n is the number of ciphertexts and k is the length of each ciphertext
#Each output is n strings of characters representing the "decoded" portion of each message at position k

#Todo: Use a dictionary to automate this.

from itertools import combinations
a="7ECC555AB95BF6EC605E5F22B772D2B34FF4636340D32FABC29B"
b="73CB4855BE44F6EC60594C2BB47997B60EEE303049CD3CABC29B"
c="64C6401BAF45F6A930435F3DF875C4E102F8742A45C824AFCA9B"
d="72C24A52B550B3B8624D4F22F86BD2B30ABD642C498122A1D29B"
e="73CC5457BF17E7A4750C5423B178D0A44FFF756355C03CABC28A"
f="74CC0155B443B3A8795F4224AA7E97B507F2632606CF3FA0D59B"
crib = " the ".encode("hex")
#data = [line.strip() for line in open("20k.txt", 'r')]

binary_a = a.decode("hex")
binary_b = b.decode("hex")
binary_c = c.decode("hex")
binary_d = d.decode("hex")
binary_e = e.decode("hex")
binary_f = f.decode("hex")
L1=[binary_a,binary_b,binary_c,binary_d,binary_e,binary_f]

def xor_strings(xs, ys,i=0):
    return "".join(chr(ord(x) ^ ord(y)) for x, y in zip(xs[i:], ys))

def initial_drag(crib):
    '''for combo in combinations(L1, 2):
        xored= xor_strings(combo[0], combo[1]).encode("hex")
        print combo[0].encode("hex"), combo[1].encode("hex")
        print xored
        for i in range(27):
            print xor_strings(xored.decode("hex"),the2.decode("hex"),i)'''
    for cipher in L1:
        for position in range(len(cipher)-len(crib)):
            key = xor_strings(cipher,crib.decode("hex"),position).encode("hex") #when we XOR our crib with the ciphertext, we should get back the key
            for c in L1:
                print xor_strings(c,key.decode("hex"),position), cipher.encode("hex"),position #we then XOR the key we got back with the other ciphertexts
            print ""

def crib_drag(crib,ciphertext,position):
    key = xor_strings(ciphertext,crib.decode("hex"),position).encode("hex")
    for c in L1:
        print xor_strings(c,key.decode("hex"),position), c.encode("hex"),position #we then XOR the key we got back with the other ciphertexts

# Step 1. Do an initial crib drag through all possible key fragments for your crib.
initial_drag(crib)

# Step 2. Once you have found a valid key fragment, expand on that fragment. I did this manually in the interpreter.
crib_drag(" the ".encode("hex"),L1[4],5)
crib_drag("ble pr".encode("hex"),L1[0],4)
crib_drag("able pr".encode("hex"),L1[0],3)
crib_drag("able pri".encode("hex"),L1[0],3)
crib_drag("nese puzzle".encode("hex"),L1[1],3)
crib_drag("chinese puzzle ".encode("hex"),L1[1],0)
crib_drag("notable prisoner ".encode("hex"),L1[0],0)
crib_drag("do not disturb those ".encode("hex"),L1[5],0)
crib_drag("notable prisoner is freed ".encode("hex"),L1[0],0)

The difference between the method I used and the one posted elsewhere is that I drag the crib over all ciphertexts at the same time, whereas the one posted in the blog only compared a pair of ciphertexts at a time, making it much more prone to false positives compared to my method.

If you start with crib dragging using the as the crib then you will find

le pr
se pu
ree o
 clea
g tra
 the
t dis

When you assume that the 5th position of 73cc5457bf17e7a4750c5423b178d0a44fff756355c03cabc28a begins with the. This stands out because almost all the other results you get will have weird symbols or obviously nonsensical combinations of letters whereas this one looks like a possible fragment of a grammatically correct English sentence. From there onwards you just keep lengthening the crib to get the rest of the key.


Let $g(x)$ be a length-preserving one-way function. Then $f(b||x)=1||g(x)$ (where $b$ is one bit of input) is a length-preserving one-way function and $\text{hc}(b||x)=b$ is a hard-core predicate for $f$. But $G(b||x)=f(b||x)\|\text{hc}(b||x)$ is not a pseudorandom generator.

So the answer to the problem is no.

edit: My original answer did not prove that the counterexample $f$ actually had a hard-core predicate.


Checksum for bailing early on first corrupt byte in stream?

..how others have dealt with (bailing early if any of the deciphered bytes are wrong)

A relatively common practice with this side effect is to restrict bytes in the plaintext to a certain discrete subset (e.g. Base64 characters, or those with an odd number of bits set) and stop at the first decoded byte that does not belong to this subset. Don't do this, for two reasons:

If the adversary can detect when the receiver aborts (which is common and should be the default assumption), it often opens to padding oracle attacks which compromise message secrecy.
It is not secure against adversarial modifications, to a degree varying with the cipher. The worst case is stream ciphers, including CTR and OFB, where the ciphertext can be trivially altered to escape this detection method, often even if the original plaintext is not known. It does not work well either in most other modes, especially when some plaintext is known.

  Any advice?

There is a compromise between immediately detecting individual byte corruption and lost bandwidth. By a counting argument, for residual probability $\epsilon$ of not immediately detecting corruption over $n$ bits, we need to sacrifice $\log_2(1/\epsilon)$ bits for each $n$ bits. The only way to keep the relative overhead $1/(n/\log_2(1/\epsilon)+1)$ low with low residual odds of not immediately detecting an alteration is to increase the block size $n$ to more than a byte.

TLS has the functionality of authenticating individual enciphered blocks, and I'm confident that whatever it does in its modern ciphersuites is fine, and could be reused with some care. But I do not know what method(s) it uses.

A recommendable method is to use multiple independent blocks of information each individually enciphered and authenticated with an authenticated encryption mode, with some measure to prevent substitution of blocks. The simplest is numbering them using an explicit incremental block number. But we want to minimize lost bandwidth:

The block numbers can come for free: we include them in the authenticated payload, but neither encipher nor transmit them. AES-GCM supports that.
The IVs/Nonce of the authenticated mode can come for free: they can be derived from a CSPRNG seeded with an extra key (with perhaps that key and the encryption key derived from the main key).

We might additionally want to use a short authentication tag for intermediary blocks in order to conserve bandwidth, but maximize odds that a previous alteration that went undetected because of that is detected later. I know no standard method, but it is possible to improvise one if computational efficiency is not an issue: we can include a MAC (made with an independent key, e.g. derived) of the previous block (including its authenticated data) in the next block's authenticated and implicit data. Further, we can use a hash rather than a MAC if the authenticated encryption is such that passing it's integrity test does not compromise the confidentiality of authenticated data when that's implicit (which is the case at least if that integrity is checked using a MAC).

If we use a large authentication tag for the last block only, there must be some safe way to recognize that block, and that's not to be taken lightly. A safe method is to make it of a recognizable length and use a different derived key for that block.


In RSA, the keys do not consist of a single value; they consist of multiple values:

the public key consists of the modulus and the public exponent;
the private key consists of the modulus and the private exponent.

So there are two exponents: one for the public and one for the private key. You perform modular exponentiation with the public exponent for encryption or verification and modular exponentiation with the private exponent for decryption or signature generation.

The public exponent is deliberately kept small to have more efficient public key operations. Generally it is just set to the fifth prime of Fermat, called F4. It only has two bits set to 1 to further optimize the calculations.

It might be that the more efficient Chinese Remainder Theorem (CRT) parameters are included in the private key. These are basically the parameters from which the modulus and exponents are derived such as the prime numbers P and Q. It is possible to speed up RSA private key calculations using these parameters. To speed calculations even more it may be that more than two prime numbers are used, resulting in multi-prime RSA.

Your posted RSA PRIVATE KEY is a private key whose format is specified in PKCS#1, which is the RSA standard used in most applications:

RSAPrivateKey ::= SEQUENCE {
       version           Version,
       modulus           INTEGER,  -- n
       publicExponent    INTEGER,  -- e
       privateExponent   INTEGER,  -- d
       prime1            INTEGER,  -- p
       prime2            INTEGER,  -- q
       exponent1         INTEGER,  -- d mod (p-1)
       exponent2         INTEGER,  -- d mod (q-1)
       coefficient       INTEGER,  -- (inverse of q) mod p
       otherPrimeInfos   OtherPrimeInfos OPTIONAL
   }

You can see its contents here. Alternatively you can view it using the command line openssl asn1parse:

    0:d=0  hl=4 l=1188 cons: SEQUENCE
    4:d=1  hl=2 l=   1 prim: INTEGER           :00
    7:d=1  hl=4 l= 257 prim: INTEGER           :D75430BE504D406163BD9C496689A5488A596B85897375040DA621E7200F091A040B95499B8F4CB195348215CD3639EFE3426396EE9686F42860F454BAAEEEA3B274C753C519D76C869D77E7B3FA8EDAF9EBB7B401C40DD65828B5BE068158D3101E78AB87149FBC3F5DB8BCBB5B2200CB6594995B64D5C5570A53F3805B1888F4A829D6D8D3449DFA6E09C3799078A56DA2AB92E8AC2CF0DC67A158F8F453F99F71CEC2FAEA3736378DF7128E6518738DA6E4F2B0B686711A49E639E8B80D04018E1B6F608FE5E86072B2F27E4FD4BD2788F998B320762F8654B5EF9D7ACAD5F71AD8F64C46330932F45C4DF5FD2E932DE6A36786A7C82F5B755F4F7C4C08B3
  268:d=1  hl=2 l=   3 prim: INTEGER           :010001
  273:d=1  hl=4 l= 256 prim: INTEGER           :3ABBC81FE11F71341F5494D0A09B62EE0A6EA19967088B1E73EAA0CCBE3DDBA9B0F8C7DBB006C2509DF6189581C80CBD962B81A6A5A581620FB18273AA081527A98198ED0C9223E48243697555EE3E1114A26B153A7613A027A3D30EE60F59FF1822779FB1D4BA4D4AAB71BC690E4E9410E6C045A45C38C2FF1EDE0F492F8FDD2B54749B5403F17C25153F6B347AB7DFC034623EF7A94BD2907C31A833596FFD3C3D32788822D97C4403911DE89040CC6A96FD91C5172E853AE39A189645A1EA077E40B64CD203EF55542202C458E8016BDA31FE7B767B1EDC1304A1427450D58E605D08C297D6D50866B8BE51D04A567D8F77D4A6293CEF2C6C60D9DB272821
  533:d=1  hl=3 l= 129 prim: INTEGER           :F35A0E03E3A004A0E42A9FD1CC470492E0227654DB00B734EE45525866587C3F97948D7102B72CDCBFF2C68292423A23ADB75BFB0A7DF61C37B93EFF18664A0ADFA24353FFBF5E9E1BE03E766A87E7F0B50C19A94CE870A3E40B7CBDDDD091A7D940D181F3493F0876DBEAD275EFA27EE60C69A76599566B35FF14B95CDEF1BF
  665:d=1  hl=3 l= 129 prim: INTEGER           :E285460B8B85C62534B7DD312603555549723219E1541C250A81D3AA4A107B3B9A4DA9F3D0BD6A068E76F8674A20196B43D8BBE1ABEF886BA9E655D3C164D5985C4A03EBC0EE88C29A37F4DF6E2DD3CA286CFB13ECE0E9EA64734269BA50A46358238844DD6B42C15537C2CF62491005461B1B9E21A8D61EFA81802BF9F2BE0D
  797:d=1  hl=3 l= 129 prim: INTEGER           :DC25E3F7F0BC9A7352F69C8E9756C7F4777FB5BD1E428F7AFAF30B839D52FF542834E3A010ECD550FEF50A50A52FF498C256D6874CFE96DF002A3DAB58CF70BC5583DD94E8109FF03917AC6A44059EF64B531F03E1E785BF3E56860ADDD8096CE7459443136C77F198556B21EA3F57A9A5442570A2A10D64FFFC3B2B55B0FAD1
  929:d=1  hl=3 l= 128 prim: INTEGER           :78E68F2B2C4DBB23328F0C04E67812FC9155DCFDC9315E503ADA6E41CE841B72057A7C4240E0480DB5CE33E8D53C6AB4C0A2962CEDDACC2242AD4893DBFDD8AF185AFCDAC0BFCFC8A60D45AA5721289016A18C24E76268170D842327512527884A8BB478A50151C0E49DFD6138E12C26D473357B6215BE2B0CA33FE8B8E061A5
 1060:d=1  hl=3 l= 129 prim: INTEGER           :88EE8B43C85D95C6B0DA7E574D3DEA4769521535E41F2FC24883850164238AF30DB07D826829452345740B1D7CB1C689729A04A95FEAF5DD32AC1847148FC7BC503ED43DA2378F82B3A06D877972ADC01CB32B99F2504EF78759EE1A5D5E4776CFA4B2D2FE7957F7C6F60ED2683DBBCAEC55A296AA41832D38DFECEA61484102

As it is quite tricky to parse these kind of formats, it is best to use a library that already contains an encoder. Implementing a full ASN.1 decoder requires knowledge about compilers, parsers and code generation. It's interesting enough, but it is hard to do as well.

Note that PKCS#1 specifies a structure. This structure is encoded using BER / DER, the basic or distinguished encoding rules. These are however binary encodings. What you've specified is obviously text. This text is called PEM for privacy enhanced mail. Mail is a text format, so it cannot deal with binary. For that reason the binary is base 64 encoded and a header and footer line are added so that the type of key is known. OpenSSL uses this as default format for keys.


How to encrypt a symmetric key with a shared secret?

How is the shared secret asymmetric if the "shared secret" is used to
  both encrypt and decrypt?

By its way of creation you can call it asymmetric. There are asymmetric public keys involved in agreeing on the shared secret, so it's asymmetric. You could also call it asymmetric as the knowledge of the shared secret is asymmetric. Only the endpoints know the shared (private) secret while everybody else (in the middle, like ISPs) only knows the public keys.

  How exactly do i encrypt an AES key with the "shared secret" key?

Usually, you don't. You feed the shared secret into something called a "key-based key derivation function" (KBKDF), which will accept your shared secret (a large number) and generate cryptographic keys (for use with AES for example) from that.

  Is it not possible to directly create a symmetric AES key with the DH
  key exchange?

You could do it. However, AES accepts at most 256-bit long keys. If you end on a 256-bit shared DH secret, then the group parameters are really weak and it's easy to find the shared secret just given the public keys.


Is 512 bits a more secure hashing than 256 bits?

When there is no known weakness in the hash function we talk about their generic1 resistances

Pre-image resistant: given a hash value $h$ find a message $m$ such that $h=Hash(m)$. E.g., consider storing the hashes of passwords on the server. An attacker will try to find a valid password to your account.

Second Pre-image resistant: given a message $m_1$ is should be computationally infeasible to find another message $m_2$ such that $m_1 \neq m_2$ and $Hash(m_1)=Hash(m_2)$, e.g., producing a forgery of a given message.

Collision resistance : it is hard to find two distinct inputs, $a$ and $b$, that hash to the same output $a$ and $b$, i.e., $H(a)= H(b)$ and $a \neq b.$

A hash function with output size $n$ is expected to have $\mathcal{O}(2^n)$ pre-image resistance and secondary image resistance and $\mathcal{O}(\sqrt{2^n)} = \mathcal{O}(2^{n/2})$ collision resisance. The collision resistance is less due to the birthday paradox (attack).
If we plug 256 and 512 into those equations you will see that

256 has $\mathcal{O}(2^{256})$ pre and secondary and $\mathcal{O}(2^{128})$ collision resistance, whereas
512 has $\mathcal{O}(2^{512})$ pre and secondary and $\mathcal{O}(2^{256})$ collision resistances.

As a result, as long as there is no specific weakness in the (unspecified) hash function the larger the output the better the resistance they will have.
When the hash function is specified then one can talk about their resistance in all directions. For example;

Standard Merkle–Damgård constructions (MD) (MD5, SHA-1, SHA-2) are vulnerable to length extension attacks, however, sponge constructions (SHA3) and HAIFA based (e.g. BLAKE(2)) are not. Note that after SHA3, there are variants of SHA-2 that have resistance against length extension attack like SHA512-256,

Herding attack for MD constructions is introduced by Kelsey and Kohno in 2005 and applied to MD5 Finding Preimages in Full MD5 Faster Than Exhaustive Search with Chosen Target Forced Prefix Pre-image resistance

Chosen-prefix collision on SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust, 2020. List of attacks on SHA-1 can be found 1,2

The relations of the generic resistances are, in simple terms,

Collision resistance implies 2nd-preimage resistance of hash functions, see a detailed work on our site

2nd-preimage resistance implies preimage resistance, see the proof on this site.

The formal definitions of the resistance and modern cryptographic deal of the above facts and more provided in the novel article; Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance by P. Rogaway and T. Shrimpton on 2009.

1 The term generic is used when a resistance ( or the attacks) applies all of the hash functions. This term similarly used in other cryptographic contexts, too.


Summary: no, this does not hold for all curves. It does hold for all Barreto-Naehrig curves, though; however, there are some subtleties.

First, some definitions. In order to define the question with all due precision, I must recall some known results.

Let $\mathbb{F}_q$ be a finite field of characteristic neither $2$ or $3$; that is, $q = p^f$ for some prime $p \geq 5$ and some integer $f \geq 1$. We consider curves $E$ over $\mathbb{F}_q$ with short Weierstraß equation $y^2 = x^3 + Ax + B$ for two constants $A$ and $B$ such that $4A^3 + 27B^2 \neq 0$ (if that last property is not fulfilled, there is a singular point with no tangent, hence which cannot be added to itself in a meaningful way, and the curve is not, stricto sensu, a curve).

Curve isomorphisms correspond to affine changes of variables; these are the transforms of the plane that map lines to lines, and therefore conserve point additions. It can be shown that the only possible changes of variables between two curves with short Weierstraß equations are $(x,y) \mapsto (e^2 x, e^3 y)$ for any $e \neq 0$ in $\mathbb{F}_q$. Such a change of variable transforms the curve equation into: $y^2 = x^3 + Ae^{-4}x + Be^{-6}$. We can thus to a large extent "normalize" either $A$ or $B$ to a small set of possible values.

The $j$-invariant of the curve is the field element:
$$ j = 1728 \frac{4A^3}{4A^3 + 27B^2} $$
Each element of $\mathbb{F}_q$ is a possible value for the $j$-invariant. When two curves have the same $j$-invariant, then either they are isomorphic to each other (in the sense explained above), or they are called twists of each other. When two curves are twists, then this means that they are isomorphic in a field extension; that is, there is a degree $k > 1$ such that, lifted into $\mathbb{F}_{q^k}$, the two curve equations become two isomorphic definitions of the same curve (and this then holds also in the algebraic closure of $\mathbb{F}_q$). The twist is called quadratic if $k = 2$, cubic if $k = 3$, and so on.

In the general case, when the $j$-invariant is distinct from $0$ and from $1728$, the curve admits a single twist (up to isomorphism) and it is quadratic. Namely, let $d$ be a non-quadratic-residue in $\mathbb{F}_q$ (i.e. an element with no square root); an equation of the twist is then: $y^2 = x^3 + Ad^2x + Bd^3$. It can be seen that if we "invent" a square root $e$ of $d$, then this yields the isomorphism which was described above. $e$ does not exist, by construction, in $\mathbb{F}_q$; therefore, adjoining $e$ to $\mathbb{F}_q$ yields $\mathbb{F}_{q^2}$, a degree-2 extension (in the usual definition of field extensions with polynomials, we are using the irreducible polynomial $X^2 - d$, and call $e$ one of its roots in the field extension).

It can be shown that if the curve $E(\mathbb{F}_q)$ has cardinal $q+1-t$ (with $t$ being the trace of Frobenius, bounded by Hasse's theorem: $t^2 \leq 4q$), then the twist has cardinal $q+1+t$, i.e. the trace is simply negated. The elementary proof consists in enumerating elements $x$ in $\mathbb{F}_q$:

If $x$ is such that $x^3 + Ax + B$ is the square of $y \neq 0$, then there are two points $(x,y)$ and $(x,-y)$ on $E$. But then, $(dx)^3 + Ad^2(dx) + Bd^3 = d^3 y^2$, and since $d$ is not a square in $\mathbb{F}_q$, this last value is not a square, and there is no point $(dx,y')$ on the twist $E'$.
Conversely, if $x^3 + Ax + B$ is not a square in $\mathbb{F}_q$, then there is no point $(x,y)$ on $E$, but there will be two points $(dx,y')$ on $E'$.
If $x^3 + Ax + B = 0$, then $(x,0)$ is a point on $E$, and $(dx,0)$ is a point on $E'$.

Thus, by enumerating the $q$ possible values of $x$, we obtain always two points: either two on $E$, or two on $E'$, or one of each of $E$ and $E'$. This covers all points of $E$ and $E'$ except the point-at-infinity, which does not have coordinates per se, and is part of both curves. Therefore, $\#E + \#E' = 2q + 2$, from which the result is obtained.

Note that, from the $j$-invariant, a matching curve equation is obtained as:
$$ y^2 = x^3 + \frac{3j}{1728 - j} x + \frac{2j}{1728 - j} $$

If the $j$-invariant is zero, then this corresponds to curves of equation $y^2 = x^3 + B$ (i.e. $A = 0$). There are only six curves with such an equation, up to isomorphisms (i.e. there are exactly six isomorphism classes); moreover, they are all twists of each other. Some of these will be quadratic twists, some will be cubic twists, and some will be sextic twists.

If $q = 2 \bmod 3$ (this may happen only if the characteristic $p$ is itself equal to $2$ modulo $3$, and $q = p^f$ for an odd integer $f$), then every element of $\mathbb{F}_q$ has a single cube root; therefore, for every $y \in \mathbb{F}_q$, there is a single $x$ such that $x^3 = y^2 - B$. It follows that the curve order is $q + 1$, and the curve is supersingular, and the embedding degree of the curve is $2$, and you don't want that for your pairings. Supersingular curves have a bunch of special properties, which I won't detail here.

I now suppose that $q = 1 \bmod 3$. Since $q$ is odd (it is a power of the characteristic, which we supposed was not equal to $2$, and is prime, and therefore odd), it follows that $q = 1 \bmod 6$. This implies that there are non-trivial sixth roots of unity, and that there are elements $\xi$ such that $X^6 - \xi$ is irreducible (there's a short proof of it given in the Barreto-Naehrig article, on page 6). We obtain all curve classes by enumerating the equations:
$$ y^2 = x^3 + \frac{B}{\xi^i} $$
for all $i$ from $0$ to $5$.

With $\xi^0$, we have the curve $E$ itself. With $\xi^3$, we get a quadratic twist of $E$. With $\xi^2$ and $\xi^4$, we obtain two cubic twists of $E$. With $\xi$ and $\xi^5$, we get two sextic twists of $E$.

Now for the group orders. When a curve has $j$-invariant zero, then its group order can only take six values (corresponding to the six isomorphism classes). Consider the integer $4q - t^2$: as indicated above, by Hasse's theorem, this integer is nonnegative. You can make it square-free by removing all prime factors with an even exponent; i.e. you can write:
$$ 4q - t^2 = Dv^2 $$
for integers $D$ and $v$, where $D$ is square-free (i.e. there is no prime integer $z$ such that $z^2$ divides $D$). By unicity of the factorization of integers, $D$ is uniquely defined. For curves of $j$-invariant zero, it so happens that $D = 3$, always; and this also works in the other way: if $D = 3$, then the curve MUST have $j$-invariant zero (this comes from complex multiplication theory, which is, indeed, rather complicated). From the value $v$, we can obtain the orders of the twists of curve $E$. We recall that $\#E(\mathbb{F}_q) = q + 1 - t$; then:

Quadratic twists of $E$ have order $q + 1 + t$.
Cubic twists of $E$ have order $q + 1 - (3v-t)/2$ or $q + 1 - (-3v-t)/2$.
Sextic twists of $E$ have order $q + 1 - (-3v+t)/2$ or $q + 1 - (3v+t)/2$.

For a demonstration and pointers, see The Eta Pairing Revisited, section 4.

The third case is when the $j$-invariant is equal to $1728$. This corresponds to curve equations $y^2 = x^3 + Ax$, i.e. $B = 0$. If $q = 3 \bmod 4$, then this defines a supersingular curve. If $q = 1 \bmod 4$, then you get four isomorphism classes, all twist of each other; such a curve accepts one quadratic twist and two quartic twists (extension degree 4). I won't detail that one, but see the Hess-Smart-Vercauteren article for details.

Another useful result is that, given a curve $E$ defined over field $\mathbb{F}_q$, with order $\#E(\mathbb{F}_q) = q + 1 - t$, the order of $E$ over field extensions can be computed as follows:
$$ \#E(\mathbb{F}_{q^n} = q^n + 1 - (\alpha^n + \overline{\alpha}^n) $$
for all integers $n \geq 1$, where $\alpha$ and $\overline{\alpha}$ are the two (complex) roots of polynomial $X^2 - tX + q$. There is a nice recurrence relation:

$\alpha^0 + \overline{\alpha}^0 = 2$
$\alpha^1 + \overline{\alpha}^1 = t$
$\alpha^{n+1} + \overline{\alpha}^{n+1} = t(\alpha^n + \overline{\alpha}^n) - q(\alpha^{n-1} + \overline{\alpha}^{n-1})$

In particular, $\alpha^2 + \overline{\alpha}^2 = t^2 - 2q$

All of this being stated, let's see your specific problem.

You have a prime $p = 1 \bmod 3$. A curve is defined over $E(\mathbb{F}_p)$, with equation $y^2 = x^3 + B$; this is a curve of $j$-invariant zero. Its order is denoted $r$. This curve has a trace $s$, which is such that $r = p + 1 - s$. In BN curves, $r$ is also prime, but this does not matter here.

You then lift the curve into $\mathbb{F}_{p^2}$. I write $q = p^2$: you are interested in twists of $E$ as defined over $\mathbb{F}_q$, not twists of $E$ as defined over $\mathbb{F}_p$. It is important to be precise about such things; this is the reason why I used $q$ and not $p$ in all the treatment above.

With the results above, you can compute:
$$ \#E(\mathbb{F}_q) = q + 1 - (s^2 - 2p) $$
i.e. the trace of the curve over $\mathbb{F}_q$ is $t = s^2 - 2p$.

Since this is a curve of $j$-invariant zero, it admits 5 twists, two of which being sextic, with orders:
\begin{eqnarray*}
    o_1 &=& q + 1 - \frac{3v + t}{2} \\
    o_2 &=& q + 1 - \frac{-3v + t}{2} \\
\end{eqnarray*}
where $v$ is such that $4q - t^2 = 3v^2$.

The question is then: is it guaranteed that one of these two sextic twists has order exactly $r(2p-r) = (p+1-s)(p-1+s)$?

The answer is: no. Here is a counterexample:

Let $p = 31$. The curve $y^2 = x^3 + 3$ has order $r = 43$, i.e. its trace is $s = -11$. The quadratic extension is $q = 961$; over $\mathbb{F}_q$, the curve $E$ has trace $t = s^2 - 2p = 59$. We note that $4q - t^2 = 363 = 3(11^2)$, thus $v = 11$. The orders of the two sextic twists are then $o_1 = 916$ and $o_2 = 949$. However, $(p+1-s)(p-1+s) = 817$, which is distinct from both $o_1$ and $o_2$.

However, for BN curves, this works. Recall that a BN curve is parameterized by an integer $u$, and:

$p = 36u^4 + 36u^3 + 24u^2 + 6u + 1$
$s = 6u^2 + 1$

The integer $u$ is chosen so that $p$ is prime, and the curve order $r = p+1-s$ is also prime. Under such conditions, one can notice that:
$$ 4p - s^2 = 3(6u^2 + 4u + 1)^2 $$
Hence $s$ is the trace for some curve over $\mathbb{F}_p$ with $j$-invariant zero. We can then lift that curve into $\mathbb{F}_q$ with $q = p^2$, and that one will have two sextic twists.

This choice of $p$ and $s$ implies that $r$ divides $p^{12}-1$, which means that the embedding degree (the crucial property for defining pairings) will be at most $12$, hence the curve will be "pairing-friendly".

With these parameters, you get:

$q = p^2$
$t = -36u^4 - 72u^3 - 36u^2 - 12u - 1$
$4q - t^2 = 3v^2$ with $v = (6u^2+4u+1)(6u^2+1)$

And thus, the two sextic twist orders are:
\begin{eqnarray*}
    o_1 &=& 1296u^8 + 2592u^7 + 3024u^6 + 2160u^5 + 1044u^4 + 360u^3 + 84u^2 + 12u + 1 \\
    o_2 &=& 1296u^8 + 2592u^7 + 3024u^6 + 2160u^5 + 1152u^4 + 432u^3 + 120u^2 + 24u + 4 \\
\end{eqnarray*}

If you compute the expression for $(p+1-s)(p-1+s)$, you will find that you get exactly the same polynomial as $o_1$. Therefore, for any BN curve, it is guaranteed that one of the sextic twists $E'$ of $E$ (over $\mathbb{F}_q$) will have order $(p+1-s)(p-1+s) = r(2p-r)$.

Note: there still are two sextic twists. When you choose your $\xi$ such that $X^6-\xi$ is irreducible over $\mathbb{F}_q$, you might be unlucky and obtain the wrong one. The other twist can be obtained by using $\xi^5$ instead (or you could try again with another $\xi$, since you want one that makes computations easiest to do).


Not sure if I am correct about this, but let me give it my best.

I do get that encoding numbers from 0 to 9999 you get 10000 possible encodings, what I don't get is that how to you get 20 digit encodings? As far as I understand with FPE you always get the same length so if you encode numbers from 0 to 9999 you'd get ciphers between the same values.

It seems that the problem assumes that all numbers are written as 20-digit nature numbers. So for the number 45 you might have '00000000000000000045'. This keeps all of your numbers in the same size and format. It also means that the output space is quite large (10^20).

The exercise asks what is the probability of an attacker to generate a valid cupon?

Well, the attacker doesn't know the values of the input numbers (and the input coupon numbers don't necessarily need to be 0 through 9,999, rather, they can be any 10,000 numbers in the space. So that means that the attacker will likely have to try a random input number and then check with the server if the coupon has value. As there are 10,000 valid coupons (10^4) and a space of 10^20, we can simply divide to get 10^4/10^20. So 1/10^16 chance of hitting a valid coupon code.

Hope that answers your questions.


Cryptographic hash functions by design cannot be collision-free since they operate on arbitrary-sized input to fixed-sized outputs like 256 for SHA-256 and 512 for SHA-512. $$H:\{0,1\}^* \to \{0,1\}^b$$ where $b$ is the $H$'s output size.
By the pigeonhole principle, collisions are inevitable. Simply consider 100 holes and 101 pigeons. With this condition when the pigeon placed on the hole, there must be at least one hole more than one pigeon.
This doesn't mean that one can find a collision very easily. For SHA-256 you need around $2^{128}$ inputs to see at least one colliding pair with 50% probability. For SHA-512 that is $2^{256}$. This is due to the generic birthday attack that has cost $\mathcal{O}(2^{n/2})$ with 50% for $n$-bit output hash function. Those numbers are huge to be considered. For example, the collective power of the Bitcoin Miners can reach $~2^{93}$ SHA-1 hashes per year. This means that they need 2^{37} years to find one with 50%.
We don't try to make them collision-free, we live with it by knowing the boundaries.
Currently, neither for SHA-256 nor SHA-512 there is a collision attack better than the generic collision attack. There are attacks on the reduced rounds, however, this simply indicates that better than generic is hard! We will be surprised that one can find two inputs colliding. This happened on MD4 even randomly. MD5 collisions are trivial and SHA-1 has been shattered. Don't confuse that those are not secure hash functions even in the early 2010s.

What are the chances that 2 different strings/URLs produce the same hash when used SHA-256 or SHA-512?

If we model the SHA-256 uniform random then $1/2^{256}$. This is a simple probability; the first element can get any position then the second element has $1/2^{256}$  probability to hit the first one.

Question-2: Assuming that the system saves 30billion URLs their hashes in database, what is a recommended hashing function, if not SHA-2? Please note that a requirement of the system is it should be highly available, meaning: hash computation should not take very long.

30 billion URL ($\approx 2^{32.48}$ URL ) have the probability of collision;
$$(2^{32.48})^2/2^{256}/2 = 2^{69.6 - 256-1} \approx 1/2^{187.4}$$
We call an event is-not-gonna-happen if it has probability $<\frac{1}{2^{100}}$. You can use any 512-bit cryptographic hash function like SHA-512, SHA3-512, and BLAKE2b without fear of collision.  You may look at BLAKE2b quite fast compared to alternatives and its parallel version BLAKE3.

Are SHA-256 and SHA-512 collision resistant?

Yes, currently as of 2021 and in the near future, yes.


Is it possible to spoof an identity cert modulus?

I'm not sure exactly what you are asking. In the scenario, there are two certificates: Romeo's FOAF certificate and Juliet's SSL certificate. However Romeo's certificate is used in two different ways: once to authenticate (over mutually authenticated SSL) and once as posted on a domain he controls.

I believe your question may be, if an active adversary saw Juliet request the certificate information from Romeo's domain (as specified in the cert's alt name), could the adversary modify the response to match a bogus FOAF certificate it provided? The answer is yes, since this connection is not over SSL!

The real question is what happens in step 6? Does Juliet look in her friends databases for the URL or for the public key? If it is the former, there seems to be a security vulnerability. If it is the latter, it is ok, since an adversary has to substitute their own public key to form the HTTPS connection (which requires them to know the corresponding private key).

I once experimented with FOAF but don't know anything about FOAF+SSL beyond this article.


What is the linear complexity of a modified LFSR sequence with a fixed length of zeroes inserted between every pair of successive terms

There are no general lower/upper bounds that are not combinatorial in nature.
If you have a sequence $S=(s_0,s_1,\ldots,s_{N-1})$ which has period $N$ over a finite field $\mathbb{F}_q$ there are two related formalisations of the linear complexity $L(S)$ of the sequence. The first one is the classical
$$L(S)=N-\deg(\gcd(S^N(x),x^N-1)),\tag{1}$$
where $S^N(x)=s_0+s_1x+\cdots+s_{N-1} x^{N-1}.$
Now, for $q=2,$ which is what we are interested in, $x^N-1$ has a canonical factorisation as
$$
x^N-1=\prod_{t=1}^h f_t(x)\quad with\quad f_t(x)=\prod_{j \in C_t} (x-\alpha^j)
$$
where $\alpha$ is an element of order $N$ in $\mathbb{F}_{q'}$ which is defined to be the smallest extension field containing an element of that order. Then the degree of the gcd  in (1) can be written as a sum of cardinalities of cyclotomic cosets modulo $N.$
If you insert $k-1$ zeroes between each symbol, for $k\geq 2,$ to obtain a new sequence $S'$ of period $kN,$ it is straightforward to see that the new linear complexity is
$$L(S')=kN-\deg(\gcd(S^N(x^k),x^{kN}-1))\tag{1}$$
A related characterisation can be made using a finite field valued (not complex-valued) DFT. Firstly you need enough points in the finite field $GF(q')$ over which you will define the DFT to make it one-to-one, thus $q'\geq N$ is needed. For the arithmetic operations leading to the DFT to make sense, $\mathbb{F}_q$ must be a subfield of $\mathbb{F}_{q'}.$
If you can find $\mathbb{F}_{q'}$ such that $\gcd(q',N)=1,$ you can define the DFT vector of the sequence $S$ as
$$
A=[a_0,\ldots,a_{N-1}]
$$
where
$$
a_j=\sum_{i=0}^{N-1} s_j \alpha^{ij},\quad j=0,\ldots,N-1
$$
and all arithmetic is in $\mathbb{F}_{q'}.$
A relationship called Blahut's Theorem in coding theory literature states that the Linear Complexity $L(S)$ is equal to the Hamming Weight (over $\mathbb{F}_{q'}$) of the DFT vector $A.$
Note: Some of the algebraic details of this answer can be found for example in Lidl and Niederreiter's Introduction to Finite Fields book.


Which is the most secure steganography technique?

Steganography is in general impossible, and most "practical" schemes do not work. If you are really interested in the area, however, there was some work done about a decade ago on provably secure steganography. It relies on an understanding of the distribution of the messages, which is what makes it very problematic in practice.

Here are a couple of works to get you started:
https://www.cs.cmu.edu/~biglou/PSS.pdf and
http://cs.brown.edu/~anna/papers/lysmey06.pdf.

I stress, however, once again: practical steganography schemes are broken. They can typically be easily distinguished using basic machine learning tools.


Dieharder input file with a sequence of only binary numbers

You can generate an example of the ascii input by running:

dieharder -o -f example.input -t 10

It will basically be something like:

#==================================================================
# generator mt19937  seed = 3865342443
#==================================================================
type: d
count: 10
numbit: 32

However note, that dieharder will expect that each line of ascii file is either integers in the range 0  to  2^31-1 or decimal with at least ten significant digits (details are here). So maybe in your case, it's easier to produce raw binary files.

Btw, you'll need about 20GB or even more (for raw file) for proper testing. Otherwise, it's hard to say if test failed due to PRNG or too many rewounds (last tests require lots of data and even with 20GB in the standard mode, dieharder will rewound file multiple times).


In general, the high-level idea behind the Digital signatures is what you mention (Convincing the verifier about owning the secret key). We have to be careful in the Encryption schemes we care about the confidentiality and the message keeps secure against the malicious users while in the Signature schemes the authenticity matters and the message is public.

Let show what is the difference between the RSA encryption scheme and the RSA signature scheme.

  RSA encryption scheme:

Setup:

Selects two large prime number $p$ and $q$.
Compute $n=pq$ and $\phi=(q-1)(p-1)$.
Selects $1<e<\phi$ such that $\gcd(e,\phi)=1$.
Calculate $d$ such that, $d\cdot e = 1 \mod(\phi)$.
Then the pair of public keys are $(n,e)$ while the secret key is $d$.

Encryption:

For a message $m$ compute $c=m^e \mod(n)$.

Decryption:

For a given ciphertext $c$ a valid receiver who owns secret key $d$ can compute $m=c^d \mod(n)$.

  RSA Signature scheme:

Setup:

Selects two large prime number $p$ and $q$.
Compute $n=pq$ and $\phi=(q-1)(p-1)$.
Selects $1<e<\phi$ such that $\gcd(e,\phi)=1$.
Calculate $d$ such that, $d\cdot e = 1 \mod(\phi)$.
Then the pair of public keys are $(n,e)$ while the secret key is $d$.

Signing:

For a message $m$ compute $sig=m^d \mod(n)$ and issue $(m,sig)$.

Verification:

For a given pair of message and signature, a verifier by taking the pair of public keys can check $sig^e \mod(n)\stackrel{?}{=}m$.

As you can see, both approaches follow the same idea but in signature schemes, we use keys conversely. But we never use the term of Encryption with a secret key for the Digital signatures because the main point for the encryption is confidentiality of the message while in the signature the message has to publish with the signature.

The RSA signature is just an example while we know this scheme is forgeable if the adversary owns two valid signatures and multiplying them to get a third valid signature.


Would $\mathrm{LLL}$ give us a hint to solve the $\mathrm{SIS}$ problem?

As mentioned by 111 in the comments, solving SIS comes down to finding a short vector in the underlying lattice of some prescribed norm $\beta$ or less. Lattice basis reduction methods like LLL help in the sense that they can reduce a basis with long lattice vectors to a basis with shorter, more orthogonal lattice vectors.

If the reduction is strong enough (LLL, or BKZ with large enough block size) then you expect that the first basis vector of the reduced basis is a solution to SIS. (How strong your basis reduction should be to find a solution depends on $n, m, q$ and on the required length of the short lattice vector, $\beta$.)

So to answer your overall question: LLL can solve the easiest SIS instances (with large $\beta$), and can assist in solving harder SIS instances (with small $\beta$) by finding a shorter basis, which makes finding even shorter lattice vectors a bit easier.


How to quickly detect incorrect password in encrypted file without compromising security?

This is a perfect job for a Key Based Key Derivation Function or KBKDF. Generate two keys from the input (salt and password). One is stored directly in front of the ciphertext and one is used as encryption key. Because the KBKDF is based on PRF it cannot be reverted, so the keys are not related as far as an attacker is concerned.

Currently the best KDF is arguably HKDF. It contains both an extract functionality (to handle long passwords) and can take a salt and OtherInfo structure as input. The OtherInfo can be used for inserting an ASCII string identifying the key, e.g. "KCV" (key check value) and "ENC" (encryption). It is possible to derive the IV by using "IV" of course, in case the salt is already random for each encryption. You may want to perform only one extract and three expands of HKDF.

I would strongly recommend authenticated encryption. Make sure you use a fresh salt for each encryption procedure.


Understanding Diffie-Hellman - Choosing a bad g

There are two tricks that Evan could have played in selecting the $g$:

She could have selected a $g$ that has a small order; that is, $g^x$ could take on a small number of possible values.
She could have selected a $g$ that has a large but smooth order; that is, $g^x$ could take on a number of possible values, but that total number is a product of small primes.

Here's why Evan could take advantage of this second point: if the order $g$ has a prime factor $r$, then given $g^x$, it's possible to determine $x \bmod r$ in $O(\sqrt{r})$ time.  Hence, if the order of $g$ consists only of small factors, then Eve can compute $x \bmod r$ for all the small prime factors, and from that, reconstruct $x$.

In either case, the question is: what's the order of the value $g$ that Evan picked?  Well, one important thing that helps us determine that value; the order is always a factor of $p-1$.  So, the very first step is factoring $p-1$.  Then, you can go through all the prime factors of $p-1$, and use this fact: if $r$ is a factor of $p-1$, the order of $g$ is a multiple of $r$ if $g^{(p-1)/r} \ne 1$.  That should let you determine the order of $g$ without a huge amount of pain.


Nobody has publicly announced that they've broken 1024-bit RSA (other than via implementation defects that can happen with any key size), but it's not out of the question. I can't find a recent estimate, but when RSA-768 was broken in 2009, the researchers estimated that RSA-1024 would be “about a thousand times harder” and that there was “little doubt about the feasibility by the year 2020 of a matrix required for a 1024-bit NFS factorization”. So 1024-bit RSA should certainly not be used to encrypt confidential data or to authenticate arbitrary entities.

However, DKIM is somewhat less demanding than most cryptography applications. Your adversary is not NSA, it's spammers and scammers. On the scale of how much money they make, the cost of breaking 1024-bit RSA would be totally prohibitive. Furthermore, the impact of a broken key is detectable and correctable: if someone manages to break a legitimate key and makes use of that, there will be emails bearing those traces. This may cause temporary harm, but the key can be revoked. In practice, it's a lot more likely that an adversary would impersonate a legitimate participant by exploiting some misconfiguration of the server than by breaking the cryptography.

So 1024-bit RSA is fine for DKIM at the moment. However, attacks only ever get better. It's possible than an improvement to factoring techniques will make it slightly easier to break RSA, and will bring 1024-bit RSA from “NSA can break it if they really want” to “$10k on AWS”. So you should have an upgrade path ready, which you should always have when it comes to cryptography anyway. You should make sure that your system accepts 2048-bit keys, but it's ok to use a 1024-bit key for now.


Is key size the only barrier to the adoption of the McEliece cryptosystem, or is it considered broken/potentially vulnerable?

The huge key is definitely an issue. Another is the lack of standardization or recommendations. Should you use OAEP with McEliece, or some other padding? What parameters are actually secure? And so on.

Part of the problem is that, while it has been around since the 70s, it was not considered particularly interesting until quite recently—so it probably hasn't had that many research years spent on its security properties. And so far as I know, it's never been deployed in the real world.

Other potential candidates for post-quantum crypto include NTRU and HFEv-, which are fast and have small keys. Unfortunately, both are patented. If you're interested in post-quantum cryptography, I would highly recommend picking up Post-Quantum Cryptography by Bernstein, et al, which is a good survey text.


Argon2 for both password storage and key derivation

Should the secret data be encrypted with Alice's raw password?

As a general rule of thumb:
A password should only ever be fed into a password hashing scheme (PHS) such as Argon2, scrypt or bcrypt, never into anything else!

There are multiple reasons for this:

Passwords need special processing in the form of complexity parameters.
Passwords need external (high-entropy) sources of uniqueness / randomness to be mixed in.
Passwords should be allowed to be long and variable-length, most cryptographic primitives have very specific expectations on key lengths.
Passwords usually aren't randomly uniformly distributed bit strings (eg the highest bit is rarely set), which most encryption algorithms assume for their keys.

  Should her data to be encrypted with a random key encrypted with [...] a key derived from her password?

Yes. Another good rule of thumb is:
Only ever perform one password hashing per user, but give it all the resources you can spare.

The idea behind this is:

If you chain derivations and an attacker can validate whether they got the correct value for an intermediate stage, they only need to compute the last stages once, instead of once for all passwords.
If you don't expose intermediate values, you effectively created a new composite hashing scheme.
If you perform two independent derivations, you are likely to lower the resources required for each individual one and it is sufficient for the adversary to only break the weakest one and get the other one(s) "for free".

The rest is similar to smrt28's answer:

Encrypting a high-entropy key with a password-derived key allows your users to change the password without you having to re-encrypt the entire data, which may be costly in terms of CPU-time and I/O-time if you have a lot of data.

Additionally, if you use authenticated encryption (AE) using the derived key for the high-entropy key, you essentially get secure password confirmation "for free", as the scheme will very clearly report an error if the password and thus the derived key is wrong. Additionally, you can cryptographically bind derivation parameters like salt and iteration count to successful decryption using the associated data input of most AE schemes.
So in formulas: $\text{derKey} = \operatorname{Argon2}(\text{password}, \text{salt}, \text{iteration}), c=\operatorname{AE}_{\text{derKey}}(\text{MK})$ and now if one tries to decrypt with the wrong password, the AE-scheme will report an authentication failure as the key is wrong and if it is right, it will just return the correct master-key.


Understanding Diffie-Hellman Key Exchange

$p$ must be a prime number to construct a cyclic group with $p-1$ valid private exponents. Using a composite number might impose security issues and possibly performance penalties.
The size of $p$ dictates the security as it forms the size of the field. The larger the field, the more private exponents to try. The more effort you have to find the used one.
A generator is a group element that has order $\phi(p)=p-1$, so the following equation must hold for a generator $g^t\equiv 1 $ $(mod$ $p)$ where $t$ is the least interger such that this equation holds. This least integer must be $p-1$. Also look at this question to understand why a generator is required.
It would be pointless to choose a private exponent larger than $p$ as one would be again at the bare generator for $g^p\equiv g$ and hence one can save these cycles.
$"mod"$ is the binary operation that outputs the remainder of integer division. For example$7$ $mod$ $3 = 1$ as $7=2*3+1$, mathematicans also write $7\equiv 1 (mod$ $3)$.
This is called "asymmetric cryptography" and number theory is usually the tool used by cryptographers to construct such schemes.

For further understanding, reading one of the established books does help. (like the Handbook of Applied Cryptography as proposed in the comments)


How to calculate time needed for decryption of 64-bit key

If you measure the number of keys you can guess per second (as suggested in the comments) you can calculate from there. As a frame of reference, if you can calculate 1,000,000,000,000 (1 trillion) keys per second, the time to break a 64-bit key would we an average of 15.25 weeks (106.75 days), with the longest possible time to break being 30.5 weeks (213.5 days).
You need to benchmark the number of keys per second on your own system to know the time it would take for you. If you can calculate half the keys, it takes twice as long. If your system calculates 10 trillion keys/sec it would take only $\frac1{10}$ the time (10.675 days average, 21.35 days max). I think you get the picture.


Why is the function $f$ one of the inputs of the verification algorithm in homomorphic signature?

The function $f$ is part of the input to $\mathsf{Verify}$, because the goal of homomorphic signatures is to compute authenticated functions on signed messages.
In particular, given a message $z$ and a signature $\sigma_z$, we want to not only verify that $\sigma_z$ is a valid signature for $z$, but moreover that $z$ is the output of some function $f$ applied to some inputs signed under some tag $\tau$.

To take an example from this paper, you can think of the tag $\tau$ as being "grades" and a list $(m_i, \sigma_i)$ being a bunch of individual grades separately signed under tag $\tau$. Homomorphic signatures now enable the owner of these signed individual grades to compute a signature $\sigma_z$ that attests that some value $z$ is indeed the average of the grades $m_i$.

This authenticity requirement is in stark contrast to (fully) homomorphic encryption, where you only want the ability to alter ciphertexts, but make no requirements on the authenticity of the produced encryption.

A notion that may be closer to what you are looking for are so called Malleable Signatures (see Def. 3.1), which are defined by the algorithms $\mathsf{Keygen}, \mathsf{Sign}, \mathsf{Verify}, \mathsf{SigEval}$, where the first three algorithms are defined exactly as in any standard signature scheme.
The algorithm $\mathsf{SigEval}$ takes as input $(\mathsf{pk}, f, \vec{m}, \vec{\sigma})$, where $\mathsf{pk}$ is a public key, $f$ is a function, $\vec{m}$ is a vector of messages, and $\vec{\sigma}$ is the vector of corresponding signatures.
It outputs a new signature $\sigma'$ such that $\mathsf{Verify}(\mathsf{pk}, f(\vec{m}), \sigma') = 1$.

Note that if you do not want to authenticate the computed function, then it may also not be necessary to use tags in the definition of your signature scheme.


First (just to be sure): $(g^r, g^2h^r)$ is not an encryption of $2$ but of $g^2$ (because decryption in general will only give you $g^2$, then you are left solving the DLOG.
I'll assume this is not a problem in your scheme (e.g,. there are only polynomially many valid values that may ever be encrypted).

Second: it is unclear what you mean by "non-negative integer". All exponents of $g$ can be interpreted as a non-negative integers. So what would ne negative integer be? I'll assume you have some range of numbers inside $\mathbb{Z}_{|\mathbb{G}|}$ that you interpret as "non-negative". I won't mess with your desired range proof, just give you an idea for the ElGamal part.

I'll call the integer you want to range-proof $z$ and your ciphertext $(x,y) := (g^r, g^zh^r)$ (in your example, $z = 2$).
You commit to $z$ with whatever commitment your range proof needs. Send the commitment and the ciphertext to the verifier.
Then you should prove (e.g., with a Schnorr-like protocol, see Construction 2.5 here) that there exists a secret key $a$ (the ElGamal secret key) and that you know $z$ such that:

$h = g^a$ (i.e. $a$ is indeed the ElGamal key)
$(x^{-1})^a\cdot y = g^z$ (the ciphertext decrypts to $z$)
that your commitment opens to $z$.

Then, using the commitment to $z$, you run your range proof.

Another route may be to omit the extra commitment and just integrate the range proof into the same Sigma protocol, where $z$ is already a part of. My guess is that the range proofs you found only require you to commit to the value so that the statement is nontrivial ("I know some integer in this range" is not a particularly interesting statement by itself), but can probably be used in conjunction with other statements in the same protocol without an extra commitment (effectively, the ElGamal ciphertext would be your commitment to $z$).


I work for Security Innovation, which owns the NTRU patents. All NTRU-related patents are freely usable under GPL 2.0 and 3.0 -- in other words, they should fit in with your license requirement as given above. If you have specific license requirements beyond GPL please let me know and we'll accommodate them if we can.

There's an open-source C and Java implementation available from https://github.com/NTRUOpenSourceProject/ntru-crypto that you're welcome to use; it includes protection against CCA2 attacks and some features that reduce timing variability, so it's probably better to use that implementation than roll your own.

License statement about GPL is at https://github.com/NTRUOpenSourceProject/ntru-crypto/blob/master/LICENSE.md. The GPL licensing of NTRU is an irrevocable grant by Security Innovation, Inc. and cannot be withdrawn by Security Innovation, Inc, and/or any future owners of the Patented NTRU Algorithms.

List of covered patents (which is all the NTRU-related patents) is at https://github.com/NTRUOpenSourceProject/ntru-crypto/blob/master/PATENTS.md.

Hope this helps, and I'd be glad to help if you had any other questions about it.


Store hashed email and compare hash values

With normal cryptographic hash functions, two different ones, or the same hash function with different salts (which in effect are different hash functions too, for each salt) are supposed to be independent of each other, i.e. there should be no way (other than brute-forcing the message) to know from the results if they have the same input.

There are some special constructions of "different" hash functions which do not quite behave that way, but when there are independent salts, you even then have no chance.

As you used the homomorphic-encryption tag on your question, this might be a way to go. For example, with modular exponentiation modulo a prime (or analogously in a elliptic curve group), each sender would have to convert the mail address to a number $x$ (everyone using the same method for this), then calculate $f_i(x) = g_i^x$, where $g_i = g^i$ is a number assigned to each sender (and you know the $i$).

To compare the results $f_i(x)$ and $f_j(y)$, you calculate $f_i(x)^j$ and $f_j(y)^i$. If they match, then we have $(g_i^x)^j = (g_j^y)^i$, i.e. $(g^x)^{i·j} = (g^y)^{i·j}$, which usually means that $x = y$.  (This is a variation of the Diffie-Hellman key exchange.)

The $i$ works as a kind of salt here, so for listeners who don't know $i$, the mail addresses of different systems are not comparable. But I don't see how we could incorporate some kind of sender-chosen random salt for each message.


Actually, it's not a hare-brained idea at all; you certainly can do integrity checking using a one-time pad.  However, I believe that you'll need to use the one-time pad bits a bit faster than you'd expect, to achieve a forgery probability of at most $2^{-32}$, I believe you'll need at least 64 pad bits per packet (assuming informational theoretical security - that is, we don't include any computational problems that are too difficult for the attacker to solve).

One way to do this would be do a polynomial hash over $GF(2^{32})$; that is, you use 32 bits of the pad as a value $H$, and compute the value $V = X_i H^i + X_{i-1} H^{i-1} + ... + X_1 H^1 + R$ (where the message is $(X_i, X_{i-1}, ..., X_1$, and $R$ is 32 other bits from your pad, and where the computation is done within $GF(2^{32})$; the value $V$ is your tag that you send with the packet.  This provably has a forgery probability of a modified packet of at most $i 2^{-32}$ and a blind forgery probability of $2^{-32}$.  You'd need to implement a $GF(2^{32})$ multiply routine; assuming you don't need extreme speed, that's not that difficult.

That being said, might I suggest a totally different approach: how about using Speck in a Davies-Meyer construction with a key?  Speck is a block cipher that can be evaluated with minimal memory, and a Davies-Meyer construction would't require much memory.  You'd start the construction with a secret state; assuming that you don't use the block size of 128, you'd also want to end the hash with hashing some other secret data).  The advantages of this approach: you can reuse the same secret data (keying material) for every packet (and so there's no possibility of running out); you don't need to worry about packet drops (as this construction is stateless), and it should fit within your restrictions.


Recommended password complexity for SSH key encryption using AES-256-CBC

Both the AES key size and the RSA key size matter, because it's no use adding security beyond the weakest link. Here the weakest link is 2048-bit RSA, which is considered roughly equivalent in security to 100-128-bit symmetric keys (depending on who you ask). So having a password with much more than 100 bits of entropy would be fairly useless.

In practice, it depends on how much you value your security. 80 bits is enough to be secure against most, but a large adversary like NSA might be able to crack it if they put enough resources to it. 100 bits should be secure against anyone for several decades at least.

For what that means in practice, some examples:

80-bit password: 14 random alphanumeric characters (upper and lowercase).
80-bit passphrase: six diceware words.
100-bit password: 17 random alphanumeric characters.
100-bit passphrase: eight diceware words.

However, there's one important fact missing here: key derivation. The AES-256 key must be derived from the password, and with a good password hashing function this effectively adds "computational entropy" to your password choice. Unfortunately, the default for SSH is still, as far as I can tell, a non-iterated KDF that adds nothing.

If you choose to use the stronger (PBKDF2-based) format (Google should help you), you can add 10-20 bits to the password security, depending on the number of iterations. That means you can skimp a bit on password length or just accept the extra security.


Will the contents of a password protected Zip 2.0 file be safe for a week

I just stumbled on http://www.tomshardware.com/reviews/password-recovery-gpu,2945-5.html. Although it's a bit old, it does give me some perspective. It mentions ~30 million password tries per second on a Zip 2.0 file. So if someone had a that can perform 10 times as much tries per second, they would need (6^5)^5 / 300 000 000 = ~94767626766 seconds = ~3000 years. I don't think anyone will be spending time and money on a 200000 node cluster to bring this down to ~5 days.

@SEJPM, thanks for your comment that gave further thought to my own question. I was wondering, how did you come up with 2^44.8? If I calculate (6^5)^5 / 7 / 24 / 3600 I get 2^45.4. Is there a something I'm overlooking?


Key Derivation from random salted seed, HMAC and HMAC based KDF

If you have plenty entropy in your "seed" then just use a KBKDF such as HKDF. If you have somewhat less, use a PBKDF such as PBKDF2. Both HKDF and PBKDF2 can take a salt as input parameter and are already using a HMAC internally.

There is no need to perform a HMAC beforehand. If you do, you would have to specify what data is used as key for the HMAC primitive.

If you just need a random key, use a well seeded CSPRNG (possibly just the one that the runtime supplies, the OS usually has most access to entropy sources).


fixing WEP by treating all messages as one long stream

Well, WEP uses RC4 to encrypt, and RC4 can be used to generate a long keystream to encrypt multiple messages.  The key would be negotiated when the connection starts; both sides would hand over the negotiated session key to the RC4 algorithm, and RC4 then generates a long keystream that can be used to encryption.  In fact, when SSL uses RC4, it does exactly this.

However, when it comes to WEP, there is a significant practical problem that doesn't arise with SSL; message reliability.  With SSL, the protocol assumes that the protocol is run over a reliable transport (generally TCP); the transport protocol will ensure that the receiver will get every message the sender sends, and in the correct order (and if it can't ensure that, it raises an error condition that shuts down the connection.

This is important for RC4; it generates a separate part of the keystream for every message.  For, if we encrypt two 100 byte messages, bytes 0 through 99 of the keystream will be used to encrypt message 1, and bytes 100 through 199 of the keystream will be used to encrypt message 2.  When the receiver gets the encrypted message 1, he can use his copy of the RC4 keystream generator to create bytes 0 through 99 of the keystream, and decrypt message 1.

The problem comes in if the receiver never receives message 1, and instead receives message 2.  If he were to ask RC4 for the next 100 bytes of the keystream, he'd get bytes 0 through 99, which won't decrypt message 2 properly at all.

With SSL, this situation never comes up; the underlying TCP protocol will ensure that message 1 will always arrive first (unless there's some man-in-the-middle attacker; yes, he can cause the connection to shut down; there's other protections in place that ensure he can't do anything else).

However, WEP is designed to protect wireless connections; the messages that it protects are datagrams transmitted over the radio.  In practice, it is quite common for messages to not be received correctly (because of interference).  Because of this, WEP cannot assume that all transmitted messages will be received, and so WEP cannot use a long-standing RC4 key.

A cryptographic protocol needs to meet multiple goals; they ought to be secure; however, they also need to work well with the overall system design.  WEP, as designed, does the latter reasonably well; it's just the former they missed a bit.


If the block chain is ever growing chain, doesn't it run out of
  storage? Can't this chain be removed permanently?

No, the whole point of a blockchain is that everybody has to store a copy of the blockchain. That's what makes it decentralized, so there's no authority that stores the blockchain and "watches" over it.

The current bitcoin blockchain (as of 9th April 2019) is $\approx 211$ GBs large.

  Does the validation require all peers to agree that the chain is valid
  or only the majority? What if a malicious peer joins the group and
  gives false validation that a valid block is invalid? Does this break
  the entire chain?

Individuals always agree on the longest blockchain, since that is the one with the most work behind it. If a malicious person wants to create a longer and different blockchain he would have to outcompute everybody else who is working together honestly and that is not very feasible. The malicious person needs to have more than $50\%$ of the total computing power to fool everybody.

It could actually be possible, that a fork happens if two miners create a new block. If that happens then you just wait to see which one of the forks gets more blocks attached to it. This would then be the longest block and you then agree on this fork. The other fork can be discarded.

If you still have some questions, then I would recommend to watch this video from the YouTube channel 3Blue1Brown, it explains it quite well.


The correct answer depends on the way the towering is done (if any towering was done). I used the following towering:

$\mathbb{F}_{p^{2}}/(i^2+1)$

$\mathbb{F}_{p^{6}}/(y^3+\xi)$ with $\xi \in \mathbb{F}_{p^{2}}$

$\mathbb{F}_{p^{12}}/(x^2+\xi)$ with $\xi \in \mathbb{F}_{p^{2}}$

For this towering, $\mu^2=y$ and $\mu^3=x$.


AES key schedule. Does it use a KDF to generate the round keys?

No, it uses a specific type of algorithm called a key schedule. Unlike a KDF, it is not designed to be slow (in the case of a password-based KDF) or to be irreversible. The requirements of a key schedule are quite simple. Whereas a KDF might need to expand a key into a number of keys such that knowledge of any one key does not reveal knowledge of the master key or any other derived keys, that is not always true for a key schedule. If you have any round key for 128-bit AES, you can derive all other round keys.


Difference between a Polynomial Opening & a Polynomial Commitment

A Polynomial Commitment is a cryptographic object that binds a party, typically the prover, to a single polynomial. This object could be

an elliptic curve point, such as in KZG or Bulletproofs
en element of a group of unknown order, such as in DARK
the root of a Merkle tree of a Reed-Solomon codeword, such as in FRI.

The point is that underlying this cryptographic object there is a polynomial $f(X)$ that cannot be changed.
A Polynomial Opening of a commitment is the raw polynomial that the commitment represents, together with any auxiliary information needed to verify that the commitment is well formed and indeed a commitment to the given polynomial. The auxiliary information could be a randomizer in the case of semantically secure commitments, or information that is specific to the mechanics and mathematics of the commitment scheme.
The notions Polynomial Commitment and Polynomial Opening suffice to define the desired security property: Binding. Informally, it states that no realistic adversary can produce one commitment with two openings to different polynomials. More formally, for all probabilistic polynomial time adversaries $\mathcal{A}$, the probability that $\mathcal{A}$ outputs $(C, f_1(X), \mathit{aux}_1, f_2(X), \mathit{aux}_2)$ such that $f_1(X) \neq f_2(X)$ and $\mathsf{Verify}(C, f_1(X), \mathit{aux}_1) = \mathsf{True}$ and $\mathsf{Verify}(C, f_2(X), \mathit{aux}_2) = \mathsf{True}$, is negligible as a function of the security parameter.
Polynomial commitment schemes are only interesting when they come with an Evaluation Proof, which is a proof system that establishes that the value of the polynomial $f(X)$ in a point $z$ equals $y$, i.e., $f(z)=y$, where $f(X)$ is the polynomial that the given commitment $C$ commits to. Note that the verifier in this proof system does not need to know a full description of $f(X)$. In fact, polynomial commitment schemes are used precisely in a context where it would be too expensive for the verifier to read $f(X)$ from a complete description, let alone verify $f(z) = y$ directly.


Multiple NTRU public keys for the same private key?

According to current knowledge, handing out multiple public keys (with independent numerators) for the same private key $f$ is not insecure, as long as the parameters are instantiated appropriately.  There is some small loss in concrete security, but nothing like an efficient attack is known.

The standard NTRU lattice for just one public key $h$ is \begin{equation} L_h = \{ (u,v) : u \cdot h = v \pmod{q} \}, \end{equation} and $(f,g) \in L_h$ is a lattice vector that is "unusually short" relative to what the Gaussian heuristic predicts for a "random" $2n$-dimensional lattice having the same determinant $q^n$ as $L_h$.  Essentially, this gap controls how hard it is to find the secret key using lattice reduction (smaller gap means harder to break).

With multiple public keys $h_i = g_i \cdot f^{-1} \pmod{q}$ that share a private key $f$, we can define a similar lattice
\begin{equation} L = \{ (u, v_1, \ldots, v_t) : u \cdot h_i = v_i \pmod{q} \}.
\end{equation}
This $(t+1)n$-dimensional lattice has determinant $q^{tn}$, so the Gaussian heuristic predicts a minimum distance of $\approx q^{t/(t+1)}$, yet
 $(f,g_1, g_2, \ldots, g_t)$ is an "unusually short" lattice vector in $L$.  The gap is typically larger than in the single-key case, making it concretely somewhat easier to find the secret key.  But as long as the gap is not huge (e.g., polynomial in $n$) and the dimension is large enough, algorithms like LLL/BKZ won't be able to find the secret key in any feasible amount of time.

Another reason is that, informally, from one public key $h$ we can generate many public keys $h_i$ having the same secret key, by multiplying $h$ by random small $g_i$.  The resulting public keys won't be distributed like "true" keys, nor will they be independent, but this at least give some intuition why it's hard to find the secret key from many public keys.

It's worth remarking that there's a close similarity here to LWE, where one can get an unbounded number of noisy random inner products with a secret vectors, and the number of such samples does not have a major effect on hardness (though it does have some).


Best way to generate a IV for AES-CBC when encrypting files?

Generate a random IV (with a cryptographically secure random generator of course) and prepend the IV to the ciphertext.

Some modes of encryption don't require a random IV, but you can never go wrong with a random IV as long as your RNG works fine. An IV does not need to be secret (it's a matter of terminology — if it had to be secret it woulnd't be called an IV).

In the case of CBC, a non-random IV is safe if the key is only ever used for a single message. Your key is apparently derived from a user password and a salt, which makes it unique for this password-salt combination — but are you always going to generate a new salt when you encrypt a new version of the file? Even if you currently do this, are you sure that version 3 of your program isn't going to do things differently and encrypt several files with the same key?

Use a random IV, generated independently from the salt. The maintenance cost is negligible and arguably negative (it's one line of code, less long than the comment explaining why it would be safe to use a non-random IV), the performance cost is negligible.

Don't forget that CBC only ensures confidentiality, it doesn't protect the file against modification. Strongly consider using an authenticated encryption mode instead, which protects both the confidentiality and the authenticity of the data.

Finally, or rather firstly, there are already plenty of libraries and plugins to do this out there — do you really need to reinvent the wheel?


PRNG taking advantage of very large seed

The PRNG proposed by Barak and Halevi should be able to meet your needs and provide sufficient security.

Their PRNG has an API of next and refresh. refresh takes an arbitrarily long string and uses it to update the internal state of the PRNG. next returns some number of random bytes (if more is needed, one can simply call next in succession).

They prove some very nice properties of their PRNG (which together define robustness of a PRNG), and give a concrete implementation.

The entire paper is definitely worth a read.


It is helpful to first define what a perfectly secure block cipher is. In the ideal case there are n different keys where each key uniquitely indexes one of the permutations mapping {0,1}^k to {0,1}^k. In this case we have n=(2^k)! Possible permutations/keys.

Perfect security typically means that no information is revealed at all. Not even against an adversary that is computationally unbounded (ie brute force) .

Given such an ideal block cipher (random permutation), can you think of a situation where information is leaked after seeing more than one message. Keep in mind, brute force attacks are allowed here.

Hint, this is why we have block cipher modes.


The hand-waving argument goes thus: when you accumulate $n$ hash outputs, you are actually producing $n^3/6$ triplets, each of them having probability $t^{-2}$ to be a three-way collision (where $t = |T|$, i.e. the size of the output space). So you should expect the first three-way collision to appear when $n^3/6 = t^2$, i.e. $n = 6·t^{2/3}$. For a perfect hash function with 128-bit output, this means that you would need about $2^{88}$ hash function invocations.

Now that's just an approximation which does not give the exact result because the triplets are not exactly independent of each other; but it yields the proper order of magnitude.

More importantly, this assumes a perfect hash function. For a concrete hash function, even a "secure" one, you could get multicollisions much faster. As shown by Joux in 2004, an "iterated hash function" (e.g. MD5 or SHA-256) with an internal state of $s$ bits, you only need to produce $k$ "simple" collisions (of indidivual cost $2^{s/2}$) to deduce a $2^k$ multicollision. When $s$ is equal to the output size (that's called a "narrow pipe design", as @Codes says), this is much lower than the cost above; even if MD5 was not broken, it would still allow a four-way collision with cost $2^{65}$, an eight-way collision with cost $2^{66}$, and so on... The usual security property of "resistance to collisions up to $2^{s/2}$" is not incompatible with "beyond $2^{s/2}$ there may be an orgy of easy multicollisions".


2DES vs. two-key triple encryption, with no decryption step

The meet-in-the-middle attack still applies; instead of attack effort $2^{57}$ DES invocations, you just increased it by $2^{56}$ extra DES block encryptions, i.e. up to about $2^{57.6}$ in total: a mere +50% increase. On the other hand, you also made the overall block cipher (your two-key triple encryption) 50% more expensive to use, so the overall security has not changed at all: attacker and defender have been slowed by the same amount.

What would make the construction much stronger is what is down with the true Triple-DES in two-key mode: $E_{k1}(D_{k2}(E_{k1}(m)))$. With the keys used alternately, the meet-in-the-middle is effectively prevented.

You could replace the middle decryption with an encryption: $E_{k1}(E_{k2}(E_{k1}(m)))$. This would still be secure, but no longer backward compatible with "plain DES", for no obvious gain (DES encryption and decryption are identical, save for the ordering of the sub-keys, so converting a decryption block to an encryption block does not seem to imply any implementation advantage).


$GF(2^{128})$ is a finite field with $2^n$ elements. There are a number of ways to represent this field. For example, a binary vector of length 128, or polynomials of degree 127 where the coefficients are 0 or 1. You could even choose to represent them as integers between $0$ and $2^{128}-1$. These are the elements of the finite field. In addition to the elements you need two operations, call them $\boxplus$ and $\boxdot$ (we often call them addition and multiplication). To be a field, the elements must be closed under both operations, associative under both operations, commutative under both operations, there must exist an additive and multiplicative identity, there must exist additive and multiplicative inverses for every element, and multiplication must distribute over addition (see this for additional details).

So for a given representation, you must specify what $\boxplus$ and $\boxdot$ mean and show that the properties I just listed hold.

It is very tempting to want to think of $GF(2^{128})$ as simply the integers modulo $2^{128}$ ($\mathbb{Z}_{2^{128}}$). Part of this probably comes from the fact that $\mathbb{Z}_p$ where $p$ is prime, is in fact a finite field. It turns out that $\mathbb{Z}_{2^{128}}$ is not a finite field. In other words, using integer addition and multiplication modulo $2^{128}$ does not get us all the properties listed above.

So, $\alpha^j\neq 1<<j\ \%\ 128$. You could represent $\alpha$ as a 128 bit integer, but the operations to compute $\alpha^j$ would be very different from simple integer arithmetic. I'd suggest using a finite field library. For more details on the arithmetic, see the other question you asked.


How does chosen ciphertext attack on Elgamal work?

Assuming you don't use counter-measures against this kind of an attack, a chosen-ciphertext attack works as follows:

Variables: $p$ is field prime, $\alpha$ is the chosen generator, $a$ is the private key, $\alpha^a=\beta$ is the public key. $k'$ and $m'$ are chosen at random.

Note: all the following equations are $(mod$ $p)$.

Suppose you want to decrypt the ciphertext $C=(\gamma,\delta)=(\alpha^k,m*\beta^k)$
Now calculate $C'=(\gamma*\alpha^{k'},\delta*\beta^{k'}*(m'))$
Now give $C'$ to the decryption oracle, you'll get $m''$ in return.
Finally calculate $m=m''*(m')^{-1}$

Why does this work?

Observe that $\gamma'=\gamma*\alpha^{k'}=\alpha^k*\alpha^{k'}=\alpha^{k+k'}=\alpha^{k''}$.
Further observe that $\delta'=\delta*\beta^{k'}*(m')=m*\beta^k*\beta^{k'}*(m')=(m*m')*\beta^{k+k'}=(m'')*\beta^{k''}$

If you let this pair get decrypted, you'll get $m''=m' * m$ in return an hence $m=m''*(m')^{-1}$ holds.


Is it Ok in practice to rely only on the first 64 bits of a scrypt hash in this scenario?

No, you cannot assume that no collisions can be found if there is a chance of $1 \over 2^{32}$ per try. That's too high a risk for almost any kind of cryptographic scheme, especially if parallel attacks are possible. This is true by definition for scrypt as you can simply try multiple passwords at the same time. That kind of parallelization cannot be avoided even if you modify scrypt.


Which Cryptographic Standard ensures cryptographic agility and good adapotion

All but NaCl allow you to specify algorithms, but none of them would allow you to specify an algorithm that is part of the Post Quantum Cryptography initiatives yet (which, although unmentioned in the question, would be a very good reason to have crypto-agility).
For classic cryptography and a relatively high resistance against quantum computers, all those allow for RSA key encapsulation (including RSA-OAEP) and 256 bit AES as primitives. So using an RSA key pair of, say 4096 bits, will allow you to have a pretty good resistance against anything but a full featured quantum computer with more than 8192 logical qubits.
Otherwise I'd make sure that I would use a standard that is practical for you, that has a mature, well maintained library and is checked for e.g. side channel attacks. That's also something that's a good property of CMS; it may be old, but there is little wrong with maturity when it comes to choosing a library.


There is a one-to-one correspondence between the value of the second share and the value of the secret: each of the $2^8$ possible values of the second share will give a (distinct) value of the secret among the $2^8$ possible values for it, and vice versa. Hence, guessing the second share is exactly the same thing as guessing the secret.


How does SSL secure the initial handshake?

The cornerstone of the handshake security is that the Finished messages, sent under the protection of the newly exchanged key (for encryption and MAC), contain hash values computed over all the handshake messages exchanged so far, including the list of cipher suites and all other parameters. As long as client and server don't negotiate the use of a cipher suite which can be broken instantaneously, these Finished messages reliably detect foul play.


What does 2-flat mean when discussing APN permutations?

In the context of Boolean functions, "flat" is usually used as a synonym for "affine subspace of $\mathbb{F}_2^n$". More generally, an $n$-flat in a vector space $V$ (which may be considered as an affine space) is an $n$-dimensional affine subspace of $V$.

Note that a 2-flat of a vector space $V$ over $\mathbb{F}_2$ is then any set of the form

$$A = \{a, a + b, a + c, a + b + c\}$$

with $a, b, c \in V$ distinct. Remark that $\sum_{x \in A} x = 0$ and conversely, any four distinct elements in $V$ that sum to zero form a 2-flat.


Elliptic Curves - Proving that the group is not cyclic

Can anyone explain or push me in the right direction on how to show/answer this?

The first obvious thing to ponder is "what does it mean that a 'group is cyclic'?  What properties does a cyclic group have, that noncyclic groups do not?"

(Broader hint: a cyclic group has a generator; noncyclic (finite) groups do not)

  I understand that points of order two (from the hint) follow the formula: 2P = 0 but I'm not sure how this relates.

It relates quite a bit, actually.  Can a cyclic group have two different elements of order 2?

Update: since Dexter has solved the problem, I'll lay out the proof I was originally trying to suggest.

One fundamental property of all finite groups is that, if $n$ is the number of group elements, we have $xP = (x \bmod n)P$ (for any integer $x$ and any element $P$).

In addition, a finite group is cyclic if it has a generator, that is, an element $G$ for which all elements can be expressed as $xG$ (for some $x$).  In addition, for any $P$, we always have $xG = P$ for some $0 \le x < n$.  In particular, $xG \ne 0$ for any $0 < x < n$.

Now, for the group in question, we have two distinct elements $P_1$ and $P_2$, both of order two (actually, we have three, we only need two).  That is, $P_1 \ne P_2 \ne 0$, and $2P_1 = 2P_2 = 0$.

Now, suppose the group is cyclic; if so, we have a generator $G$.  We know $P_1$ can be expressed as $P_1 = x_1G$ for some $0 \le x_1 < n$.  We also have $2P_1 = 0$, that is, $2 (x_1 G) = (2 x_1)G = 0$.  We know that $(2x_1)G = (2x_1 \bmod n)G$, and if that is the neutral element, we must have $2x_1 \bmod n = 0$.  The only value $0 < x_1 < n$ that can satisfy that is $x_1 = n/2$ (which implies that $n$ must be even).

However, by the same reasoning, if we have $P_2 = x_2G$, we have $x_2 = n/2$, but that would mean that $P_1 = (n/2)G = P_2$, and so the two points of order two were the same, but we know they aren't.

Hence, there cannot be a generator, and hence the group cannot be cyclic.

This proof may sound a bit lengthy, however, that's mostly because I spelled out the logic quite explicitly, listing the various assumed properties of groups.  Once you get more acquainted with group theory, this logic would be more natural.


1st answer:

I was writing a longer answer about proving the claim directly, with the cardinalities of the message space, ciphertext space and keyspace. Basically for a random message, not all ciphertexts are possible, thus for a random challenge, not both messages might be valid decryptions. If you assume that the attacker can try out all valid keys, just one of the messages might be a valid preimage for the challenge ciphertext. In that case, the attacker can find $b$. With randomly chosen messages, this results in a probability different than $1/2$.

2nd answer:

Actually, the proof of the statement is more elegant (in my opinion) with a contraposition ($A \rightarrow B$ is logically equivalent to $\neg B \rightarrow \neg A$) of the following statement:

Perfect secrecy requires $|K|\geq |M|$. If expressed in logic terms, we can say:

Perfect secrecy  $\rightarrow$ $|K|\geq |M|$.

Perfect secrecy means, the attacker has a probability of $1/2$. If the probability is anything else, it isn't perfect secrecy. Keep in mind, that an attacker with probability $< 1/2$ is equivlant to an attacker with probability $>1/2$, by simply flipping the output bit.

Perfect secrecy means basically: $\forall \mathcal{A}: Pr_{\mathcal{A}} = 1/2$. The inverse is: $\exists \mathcal{A}: Pr_{\mathcal{A}} \neq 1/2$
Inverting the statement $|K|\geq |M|$ is quite easy: $|K| < |M|$.

Therefore we get:

$|K| < |M|$ implies $\exists \mathcal{A}: Pr_{\mathcal{A}} \neq 1/2$

This is already quite close in what you tried to prove.


This is the Shamir Three Pass protocol; it turns out the attacker can deduce some information about $m$; whether that information is meaningful depends on exactly what you are sensitive to.

Exactly what information is leaked turns out to depend on the factorization of $p-1$ (assuming, of course, that $p$ is large enough to make solving the discete problem infeasible); if $p-1$ has a factor $q$, the attacker can deduce the value of $m^{(p-1)/q}$ with $O(\sqrt{q})$ effort.  If $p$ is a strong prime, that is, if $(p-1)/2$ is also prime, then the only thing that is leaked is the value of $m^{(p-1)/2}$, that is, whether $m$ is a quadratic residue modulo $p$.

As for sending multiple messages $m_1, m_2, ..., m_t$ using the same private keys, well, if the messages are independent, we can show that there cannot be a weakness that reveals even one of the messages (the proof goes as follows: if there were something where, given $t$ independent exchanges $m_1, m_2, ..., m_t$, it has a nontrivial probability of giving us $m_i$ for some $i$; then we can take a single exchange and blind it $t$ times to generate $t$ independent looking exchanges; if our multi-exchanged weakness revealed one of the blinded messages, we can translate that back to the original message).  However, this proof technique relies on the messages being independent; if the messages had relationships between them, it is possible that the attacker could deduce that relationship (however, they still wouldn't be able to reconstruct the messages).


Is a die implemented in a physics engine truly random?

No, that would not be a true RNG, because these physics engines would just repeat the exact same calculation and thus repeat the whole sequence of random numbers - like a PRNG. The starting conditions are the seed of this PRNG.

Dice are truly random in the real world. Well, are they? If we ignore quantum effects, we could measure all relevant values of the environment and then calculate the next value of the die - at least in theory. In practice the calculations are much too difficult, and the quantum effects destroy even the theoretical possibility to calculate the result.

The physics engines mostly calculate only the important parts of the calculation: the collision with other objects and the gravity. But in the real world, we got air movement (wind, breathing of a human), fluctuation in the temperature, very small movement of the earth, difference in the gravitational field of Earth, or even the vibrations of the heart, wear and tear of the dice or just contamination in the material.

Even if the engine could calculate all this in an acceptable time period, it would have to introduce a RNG itself to simulate the quantum effects. If the engine does this (like mentioned by mikeazo in a comment), then why use the engine and not the RNG directly? If the output of the engine is bigger than the input from the intern RNG, it can't be a true random number generator anymore. It would have to stretch the random numbers. Maybe it's still secure, but using AES in CTR mode would do the same with surely much better properties.

Fun fact: There's the Dice-o-matic which again and again rolls many dice to determine random numbers. It's used to get random numbers for an online game platform. Well, that could be the closest you will come to get true random numbers from a machine with dice.


Modifying Mix Mode Modular Arithmetic in IDEA Cipher

If replacing IDEA's multiplication modulo $2^{16}+1$ by multiplication modulo $2^{16}$ (and dropping the replacement of $0$ by $2^{16}$ on input, and vice versa on output), then

For the cipher to be reversible, we need to use odd subkeys for these that enter a multiplier ($k_1$, $k_4$, $k_5$, $k_6$ of rounds, and half rounds for the first two). This follows from the fact that $x\mapsto k\cdot x\bmod m$ for $0\le x<m$ is reversible if and only if $k$ is coprime with $m$; that is, when $k$ is odd for $m$ a power of two.
There is no longer any operation in the modified IDEA that diffuses a bit flip to the right within a 16-bit word. This is a complete disaster. For example, it allows a trivial distinguisher: randomly changing the high order byte of 16-bit words of input has no action on the low-order bytes of the 16-bit words of the ciphertext output! And I guess key recovery (perhaps of an equivalent key) is feasible by attacking the cipher and sub-keys bit-by-bit within 16-bit words.


Rabin encryption when M is not Disjoint to n

The definition of the Rabin cryptosystem in the question likely is similar to:

Setup:

choose $p$ and $q$ large distinct primes with $p\equiv q\equiv 3\pmod 4$ ;
compute and publish public modulus $n=p\;q$, and publish it as the public key;
the private key is $p,q$ .

Encryption of message (representative) $M$ with $0\le M<n$ :

compute ciphertext $C=M^2\bmod n$ [implying by definition $0\le C<n$ ]

Decryption of ciphertext $C$ :

compute $M_p=C^{(p+1)/4}\bmod p$ and $M_q=C^{(q+1)/4}\bmod q$ ;
deduce that $M\equiv\pm M_p\pmod p$ and $M\equiv\pm M_q\pmod q$ [see proof at end];
noticing that $\gcd(p,q)=1$ by construction, use the Chinese Remainder Theorem to find the set $\mathcal M$ of possible $M$ as follows:

compute $q_\text{inv}=q^{-1}\bmod p$ [this value can be reused for multiple $C$ ];
compute these 4 values:
$$\begin{align}
M_0&=(q((q_\text{inv}(M_p-M_q))\bmod p)+M_q)\bmod n\\
M_1&=-M_0\bmod n\\
M_2&=(q((q_\text{inv}(M_p+M_q))\bmod p)-M_q)\bmod n\\
M_3&=-M_2\bmod n
\end{align}$$
the set $\mathcal M$ is $\{M_0,M_1,M_2,M_3\}$ ;

select $M$ as the message in $\mathcal M$ that pass some consistency check.

Further, it is commonly restricted to $p\ne q\pmod8$ at setup, yielding $n\equiv5\pmod8$; and $M\equiv4\pmod8$ [or some other value $\pmod8$ ], which then is enough to always allow recognition of which element of the set $\mathcal M$ is $M$.

Depending on $M$ or $C$, the set $\mathcal M$ will have one, two or four distinct elements. One element only occurs for $M=0$ ($M_p=M_q=0$); two elements occur when otherwise $\gcd(M,n)\ne1$ [equivalently, when a single of  $M_p=0$ (x)or $M_q=0$ holds; or in other words, when $M\ne0$ is not disjoint to $n$ ; ]; four elements occurs otherwise, that is for overwhelmingly most $M$.

The original reference on the Rabin encryption scheme is: Michael O. Rabin; Digitized Signatures and Public Key Functions as Intractable a Factorization, MIT-LCS-TR-212 (1979). It defines $C=M(M+b)\bmod n$ for some public $b$ with $0\le b<n$, which makes the cryptosystem somewhat less malleable; also, it is not restricted to $p\equiv q\equiv 3\pmod 4$.

Proof that for all $M$, it holds $C^{(p+1)/4}\equiv\pm M\pmod p$ [same for $q$ rather than $p$ ]

By construction, $C=M^2\bmod n$, and $p$ divides $n$; therefore $C\equiv M^2\pmod p$
$p\equiv3\pmod4$ therefore $(p+1)/4$ is an integer, and we can raise the above to that power, giving
$$\begin{align}
C^{(p+1)/4}&\equiv(M^2)^{(p+1)/4}&&\pmod p\\
C^{(p+1)/4}&\equiv M^{(p+1)/2}&&\pmod p\\
C^{(p+1)/4}&\equiv M\cdot M^{(p-1)/2}&&\pmod p&&(1)
\end{align}$$
If $M\equiv0\pmod p$ :

by Fermat's little theorem, and since $p$ is prime, $M^{p-1}\equiv1\pmod p$ holds;
define $X=M^{(p-1)/2}\bmod p$ [implying by definition $0\le X<p$ ]; the above becomes $X^2\equiv1\pmod p$, that is $(X+1)(X-1)\equiv0\pmod p$, which  has exactly two solutions $X=1$ and $X=p-1$ ;
therefore $M\cdot M^{(p-1)/2}\equiv\pm M\pmod p$ ;

Otherwise [ that is, when $M\equiv0\pmod p$ ]

$M\cdot M^{(p-1)/2}\equiv\pm M\pmod p$ holds [both sides are $0\pmod p$ ];

Replacing in $(1)$, it comes $C^{(p+1)/4}\equiv\pm M\pmod p$ for both cases.


Collisions in Diffie-Hellman private keys

In DHKE, Alice and Bob chooses random $x$ and $y$, $1 \leq x,y < n$, respectively.

For simplicity assume that $x$ is a product of two primes $x = r \cdot s$

Then set $ x' = r \neq x$ and $y' = s  \cdot y \neq x$ then $g^{x'y'} = g^{rsy}=g^{xy}$ will be another pair.

if $x$ and $y$ are primes then there are two cases $xy < \varphi(P)$ and $xy > \varphi(P)$ that will result in the same equation that need to be solved.

$$xy \equiv x' y' \mod \varphi{(P)}\;\;, 1 \leq x',y < n$$


What does Modification Detection Code (MDC) in OpenPGP do?

What does MDC do exactly in OpenPGP ?

MDC stands for Modification Detection Code. It's a field of cryptograms aiming at detecting that an encrypted message has been partially tampered with.

Why partially? Because that's the best achievable goal in asymmetric encryption, where it is always possible that an adversary changes a message in its entirety (since encryption requires no secret, only the recipient's public key).

So why does it matter to detect partial tampering if we can't detect total tampering? As illustration, if an adversary knew that a message will be like

connect with password nebulaergpaaelia to the website https://acme.com

and could change it to

connect with password nebulaergpaaelia to the website https://acne.com

then the adversary having registered the domain acne.com stands a chance to intercept the password thru what the recipient will do. Hence the need of an MDC.

OpenPGP has (for most ciphers and all recent ones) a provision for an effective MDC. Problems are:

There are legacy encryption modes without MDC. Thus if a decryption tool allows these legacy ciphers, it must accept to work without MDC.
OpenPGP encryption modes with MDC (that I know) detect message alteration only at the end of the message¹. But decryption tools often can be used as a pipe, spitting the deciphered message before the MDC check. That is per the common Unix design pattern of piping, and is useful for efficiency.
Often a piece of code using OpenPGP acts on the deciphered message irrespective of the later MDC check made later. For example, when the ciphertext is html with embedded URLs, the mere tentative to display it can trigger actions that an adversary can observe, and this allows attacks.

How the MDC is implemented (or not) in OpenPGP depends on the algorithm. None is mentioned in the question, thus I won't dive into the specifics.

  how to force GnuPG to stop on error when the MDC is not checked?

Modern versions (2.2.8 and higher, according to the source code) fail by default. It should suppress file output if the MDC check fails (but can't if output goes thru stdout). All that should be necessary for safety when using GPG thru a command line or thru a well-designed GUI is to

refrain from explicitly disabling MDC check (beware that --ignore-mdc-error can be made a permanent options in a variety of files set up manually or by GUI).
and make decryption output to a named file (rather than using > outputfile or piping) OR avoid using the deciphered output before ensuring that the tool's return code is 0.

¹ Conceivably, an encryption mode could split large messages into blocks of some maximum size each with an MDC, so that a decrypting program using bounded intermediary storage could release a deciphered block only after checking an MDC demonstrating that this block has not been altered and is in proper sequence. That would be safer, but more complex, and would increase ciphertext size to some degree. I do not know that it is used in OpenPGP.


SHA1 no longer considered secure for SSL Certificates -- what about Cipher Suites?

The main thing that makes HMAC secure in typical use even with MD5 is that it is used with a secret key. That means only preimage attacks are really relevant, since finding a collision is always an online attack if you don't know the key. With known attacks the preimage resistance of both MD5 and SHA-1 is > 100 bits. Additionally, HMAC may be secure even with some insecure hash functions.

However, not all cipher suites just use HMAC for message authentication. Older SSL cipher suites (before SSLv3) use plain hash functions for that. Hash functions are also used in many suites as message digests for public key signatures. Is that secure?

Well, yes. Probably. Again, only preimage attacks should apply to the ways they are used in SSL/TLS. A collision attack would require generating a large number of messages to find a pair with equal hash values. That is only a concern whenever the attacker can both predict the data to be signed and influence some of it. E.g. signatures are used for key exchange, where they are used to sign random keys, which the attacker cannot know much less influence.

Still, attacks only get better. Where using more modern algorithms is possible, you should do that.


Even if $q_H$ and $q_{Sign}$ are $\mathsf{poly}(n)$, the security guarantees turn out meaningless since the loss is exponential in $q_{Sign}$. As the author points out in the paragraph (Page 18) following the proof of the theorem, $q_{Sign}$ has to be restricted to $o(n)$ so that security can be based on sub-exponential hardness of the underlying lattice problem.


If we know the pre-shared key of an IPSec tunnel, can PFS help us to stay encrypted?

No, knowledge of the IKE preshared key will not allow anyone to listen into the IPsec traffic (either with PFS or without).

IKE always performs a Diffie-Hellman exchange to generate the initial keying material; knowledge of the preshared keys does not tell the attacker either the Diffie-Hellman private values, or the shared secret.  The encryption keys are derived from the shared secret; hence they are secure as long as the DH exchange is.

The preshared key is present to act as a 'proof-of-identity'; what knowledge of the preshared key would do is allow you to act as an active man-in-the-middle (because to either side, the attacker is indistinguishable from the other side).  The attacker would perform an IKE negotiation with both sides, generate traffic keys, and then be able to decrypt traffic from one side, read it, and then reencrypt it to send to the other side.