Enigma message decode errors, and protocols to prevent them

On page 5 of the document you linked in the comment it says the following in section 22:

  Satzzeichen

  Es werden ausgedrückt:

  Punkt durch x, Doppelpunkt durch xx, Fragezeichen durch ud, Komma durch y, Trennungsstrich, Bruchstrich, Bindestrich durch yy, Klammer durch kk. Satzzeichen sind im allgemeinen nicht entbehrlich, Schlusspunkt ist nicht einzusetzen. Da Satzzeichen im Interesse der Kürzung des Spruches gestrichen werden, ist im Wortlaut auf Unmissverständlichkeit sorgfältig zu prüfen.

(My) Translation to English:

  Punctuation

  To express are:

  Dot by x, colon by xx, question mark by ud, Comma by y, hyphen, line break, hyphen in words by yy, bracket by kk. Punctuation marks are generally not dispensable, the final dot is not to be used. The punctuation marks shall be deleted in the interest of shortening the sentence, the wording shall be carefully checked for unambiguity.

In section 28 there's also a short overview:

  \begin{array}{|c|c|}
\hline
j - j & Highlighting \ signs \\ \hline
x & Dot \\ \hline
y & Comma \\ \hline
ud & Question \ mark \\ \hline
xx & Colon \\ \hline
kk - kk & Bracket \\ \hline
qu & Square \\ \hline
grqu & Big \ square \\ \hline
fpkt & Time \\ \hline
sm & nautical \ mile \\ \hline
yy & Hyphen, \space Line \ break, \space Hyphen \ in \ words \\ \hline
\end{array}

So, as we can see, there's no special procedure to prevent vague messages. I would even argue that this could have been done intentionally, because the German language can have (very) long words and if you know the length of certain words it might be easier to decrypt a message.

Edit:

Handwritten text on pages 23 & 25:

??? = The parts I can't quite read

  Gestrichen ??? Ergänzende Anweisung [Befehlsnummer / Datum] gef.  / gez. [Unterschrift]

English:

  Discarded ??? Additional instruction [Number of command / Date] private / signed [Signature]

I guess there was a command released that these instructions are not to be followed as written in this book. The soldier then crossed these pages out and signed it. "gef." is probably an abbreviation for "gefreiter" and is a rank in the military that can be compared to the English rank of private or soldier.

It could also be that it's "gez." (instead of "gef.") which would mean "signed" followed by the soldier's signature.


I will attempt to answer some parts of my own question.

Short answer: All of them.

We define curves over Fields which have size n. We then operate in some subgroup of it, which has size/order r.

The cofactor is calculated by doing n/r . if the cofactor is equal to 1, then it means that n = r and the subgroup is equal to the whole field.

I would like to say by intuition that this means that since the co-factor is an integer. If n is prime, then the co-factor is either n or 1. The case where the co-factor is n means that the subgroup has one element. Could this be the empty set? or just the neutral element?

The case where the co-factor is one would be the only logical or useful case, which means that the subgroup is equal to the order of the field. My intuition tells me that every prime field would therefore creator subgroups that are equal to it's size.

If n is not prime, then this means that there are other numbers that it can divide by. 8 and 4 seem to be special numbers.

I would like to say that we the 8 and 4, or any multiple of two, pops up because these curves normally have orders of 2^m.

h = 2^m / r => r must be even and so must h. Does this imply that h must be a multiple of 2?

Yes. h*r = 2^m => that h and r must be multiples of 2.

I've not seen curves with odd primes, however I do not see any reason for there to not be any.

  I have seen a Twisted Edwards Curve with prime order, but also had a
  co-factor, was I mistaken?

From my deduced understanding, it must have had a order that was 2^m.

  I read that non-primes only have co-factors, but Edwards have a
  co-factor and it is defined over Fp s.t. P = 2^255 -19 which is prime
  right?

A quick google search would have shown that this number ended in 6 and so is even.

  Am I right in saying that P256 for example, has no co-factor because
  it is of prime order?

Co-factor is one.

  How is the co-factor created, some have co-factor 4 and some have
  co-factor 8?

I explained this part above where they have an order of 2^m

I'm not quite clear on how to find a G s.t. it has a small subgroup and I am not sure how multiplying a point by the co-factor "puts it in the subgroup" . Will open another question for this.


How to attack RSA-CRT with large public exponent?

There is a paper by Daniel Bleichenbacher and Alexander May called "New attacks on RSA with small secret CRT-Exponents" (you can find it under http://www.cits.rub.de/imperia/md/content/may/paper/crt.pdf). They are not quite able to break the RSA under your assumptions. I'm not aware of better results, but I didn't look at the list of articles citing this paper.


Formal security of recycled random blinding in a Paillier scheme

You have to worry not just about a pair of blinding values being equal, but more complex relationships between them.  Thus, finding a proof of security for this approach looks non-trivial to me.

Let me elaborate.  Suppose $R_j$ is the $j$th blinding variable you use.  If $R_i = R_j$, that's a problem, but as you say, that can be made very unlikely.  However, that's not the only potential problem.  If there exist indices $a,b,c,d$ such that $R_a R_b = R_c R_d$, then you might also have a problem, and this happens with higher problem.  At least, this will be a difficulty for a proof of security, as this relationship is detectable by an adversary and allows some kinds of distinguishing attacks.  If you make $k$ and $n$ large enough, you can rule out even this kind of multiplicative relationship, but you might still have to worry about higher-order multiplicative relationships, and it's not entirely clear to me how you'd address this challenge.

Perhaps you can deal with this somehow and prove something with some additional insights, but I think the above phenomenom will be a non-trivial complication.

You subsequently revised the question to propose a proof strategy.  Your revised proof strategy won't work.  It requires showing that there's unlikely to be a collision between products of the $R$'s.  However,  you won't be able to show that, because it's not true: if you consider products of very large size, it's overwhelmingly likely that some such collision does exist.  You can't avoid that by choosing $k$ and $n$ to be larger.  So, the proof strategy you suggest in the revised question isn't going to work.  This is more delicate than you might have realized, and it's not clear to me how to prove that your idea is secure (or whether a proof is possible).


Security of the shared secret key for a smart meter (Linky)

In addition to the other answer

Using asymmetric cryptography in the meters would have some benefits:

it can make passive eavesdropping of meter/server communication useless, even to a party holding or able to use the server's private key; something not achieved with secret-key cryptography.
it can ensure that any central key leak can not compromise the capability to authenticate messages from the meters.

But that's about all I see. In particular, even a full blown asymmetric public key mechanism can not solve the most serious problem that if the central system is hacked, and the hacker can communicate with the meters as the central system does, then all the capabilities the central system has (including reading any meter, or/and making any parametrization of the meters) are available to the hacker. A complete hacking of the central system is thus a disaster, no matter what.

That's why such central systems should be designed with multiple layers of security. In particular, they should hold secret keys, and the server's private key if some asymmetric cryptography is used, within devices intended to never leak such secrets, like HSMs or Smart Cards. That way, penetration of the outer layer (e.g. server's OS) simply can't leak secret or private keys (only, at worst, allow their use). After an attack, restoring the integrity of the server can hopefully restore security and functionality (unless the hacker managed to change the highest-level individual meter keys).


RSA: How to get ciphertext in decimal from an encrypted base64?

Base 64 is an encoding of bytes, not numbers. Of course, bytes can be used to represent a number. The output of RSA encryption consists of bytes (or octets, the term used in the RSA PKCS#1 stancard). So the base 64 decoding has come after RSA encryption in your protocol. This all means that the conversion is a two step process.

How to decode base 64 to bytes is not a question we're going to answer here, there are plenty of libraries that will do this for you.

Before the conversion happens it is important to validate that the value is precisely as long as the modulus (the key size), when encoded to a minimal number of unsigned byte. The real second operation, both for RSA that uses OAEP- and RSA v1.5 padding, is the conversion from bytes to the integer. This operation has a name: OS2IP, or the Octet String to (2, gedit?) Integer primitive. Very basically, this interprets the bytes as an unsigned, big endian integer.

    a.  Convert the ciphertext C to an integer ciphertext
        representative c (see Section 4.2):

         c = OS2IP (C).

This points to the following text in Section 4.2 of PKCS#1 v2.2:

  OS2IP converts an octet string to a nonnegative integer.

   OS2IP (X)

   Input:  X octet string to be converted

   Output:  x corresponding nonnegative integer

   Steps:

      1.  Let X_1 X_2 ... X_xLen be the octets of X from first to last,
          and let x_(xLen-i) be the integer value of the octet X_i for 1
          <= i <= xLen.

      2.  Let x = x_(xLen-1) 256^(xLen-1) + x_(xLen-2) 256^(xLen-2) +
          ...  + x_1 256 + x_0.

      3.  Output x.

Do not try and implement this as a mathematical function using multiplication and calculating things to the power of two; it is just a mathematical description of the decoding of an unsigned integer.

After the trick is to find a good big integer library for your language and use the right method to convert or at least interpret. In Java it is simply new BigInteger(1, <the byte array>) where the 1 is the sign bit, which is of course always positive (or zero). Java copies the value represented by the bytes to the internal interpretation but other languages may leave the number where it is and simply reference it as an unsigned big integer.

Beware that other languages such as C# are commonly little endian. You may need to find the right method that explicitly mentions the endianess. Otherwise you may need to reverse the location of the bytes within the representation before parsing the bytes that now represent a little endian integer.


What parts of AES encryption result are safe to pass on the network

IVs and salts are public, so they are safe to pass with the ciphertext. They should be authenticated along with the ciphertext though.


Substitution Cipher vs. Permutation Cipher

Substitution Ciphers

Substitution ciphers replace units of plaintext with units of ciphertext.

A simple example is the Caesar cipher, which specifies the substitution of each plaintext letter with the letter which is found some fixed number of places away in the alphabet. The Caesar cipher is easily broken by trying all possible offset values, where the number of offset values is equal to the alphabet size.

For example, if the offset value is $s = 3$, then the plaintext $caesar$ will be encoded as the ciphertext $fdhvdu$.

The class of cipher's to which the Caesar cipher belongs is the monoalphabetic substitution ciphers.

Another class of substitution cipher are polyalphabetic substitution ciphers. The Vigenère cipher is a simple example which substitutes plaintext values for ciphertext values using a series of Caesar ciphers which are defined by a keyword.

The keyspace $|K| \approx 2^{88}$ mentioned in your question can be derived from a Vigenère cipher with a 26 character alphabet and a keyword $k \in K$ which is 26 characters long. The calculation is $26!$ which tells us the number of different configurations in which we can arrange 26 characters.

This brings us to the concept of brute force complexity. Brute force complexity is a measure of the computational effort which is required exhaustively find a solution to a problem. In order for brute force complexity to be meaningful in a cryptographic context it is necessary that there aren't any shortcuts which can be taken to reduce the space which must be searched.

The Vigenère cipher does not usually meet this requirement. If the length of the plaintext is greater than 26 characters, or the same keyword is used to encrypt multiple messages, then an attacker can use frequency analysis techniques to recover information about the encrypted messages.

Both of these constructions are very old. Claude Shannon's information theory and it's application to cryptographic systems as information-theoretic security is sometimes credited with transforming cryptography from an art into a science and is an important foundation in modern cryptography.

Essentially Shannon sought to quantify information leakage in the context of cryptography, and proved that the one-time-pad satisfied a property known as perfect secrecy - it cannot be broken by any adversary, even one given unlimited computational power and time.

Permutation Ciphers

Permutation ciphers attempt to hide information from an adversary by rearranging the plaintext so that it can no longer be recognised. A simple example is the rail fence cipher which transposes a plaintext by arranging it diagonally into a number of rails. In practice this is highly insecure since the number of rails is small and can be attacked by brute force.

Modern Block Ciphers

Some modern Ciphers such as AES apply both substitution and permutation repeatedly in rounds by applying a construction known as a substitution-permutation network (SPN). AES is much more secure than any of the ciphers mentioned above, and is not vulnerable to frequency analysis in the same way as alphabetic ciphers are. For a better understanding of AES I recommend reading: A Stick Figure Guide to the Advanced Encryption Standard (AES)


Does length-prepending stop length-extension attacks?

Yes, if the length is formatted in a constant-size value (e.g. 64-bit field) or in an otherwise uniquely decodable manner.

With such a length field, no hash input can be the the prefix of another valid input. Thus there is no length-extension attack.

(Assumptions include that you reveal no intermediate values, of course.)


No, your values for $e$ and primes are fine (well, at least for a toy example); $e$ is relatively prime to both $p-1$ and $q-1$, and that's the only hard requirement (not counting the security related ones, of course).

I get $d=905$, as $5 \times 905 \equiv 1 \pmod{ \operatorname{lcm}((53-1),(59-1))}$; alternatively, you might get $d=2413$, if you do the computation $\bmod (53-1) \cdot (59-1)$.

I can only suspect that you're doing Extended Euclidean wrong; however without knowing exactly what you did, I really can't say exactly where you erred.


Does knowing multiple hash of the same content make it more likely to generate original plain text?

No, there is no security decrease in this case. While there could be some hypothetical constructions that might leak the preimage if two images are known, this is definitely not the case for existing hash functions, which are all quite different from each other.

An example of such a weak pair of hash functions could be two versions of MD5: one with 63 rounds, and another one with 64 rounds. Then the two hashes would reveal partial information about the preimage.


Merkle tree H(RBIT(X) ⊕ Y) instead of H(X || Y)

The problems mentioned in Can XOR be used in a Merkle Tree instead of concatenation? are just special cases of a fundamental problem: the construction is not second-preimage resistant. In fact, it is even worse in the sense that you can find a preimage with any $X$ value you like (similarly any $Y$ value you like).

You can open a Merkle-tree node $H( X \oplus Y)$ to any other values $X'$ and $Y'$ as long as $X \oplus Y = X' \oplus Y'$. If you can do this, then you can open a Merkle-tree leaf to literally any value. Flipping/inverting some bits (and indeed, any linear operation) won't make this attack any harder.


Does hashing PII in logs provide any real security?

Will this setup provide any real security if the logs are leaked?

One issue is the fixed salt.  With that, the translation of email to hash is fixed; that is, if the attacker sees two identical hashes, he knows that they were the same email address; he might not know what the email address is, but he knows that the two emails were to/from the same person.  And conversely, if the hashes were different, then they referred to two different email addresses.
One possibility would be to include a 'per-hash' salt (salt1), which is randomly selected each time you generate a hash [1], and so the email address would be replaced by salt1 + sha3-256( salt + salt1 + email ) (where + is string concatenation).

[1]: You could generate the per-hash salt sequentially if the order you generated the hashes didn't need to be secret; this would allow the per-hash salt to be shorter without worrying about duplications.


I know of no software that lets you visualize an arbitrary SPN network; however, many of us on the semiconductor side of things have their verification tools output visualizations based on the bit states.  We used these to compare the SPICE output to the software simulated.  My Simon Cipher and AES verification tools print out bit grids.  My AES tools are async, but the simontool program gives synchronous outputs and will give you an example of how to generate these types of bit grids if you dig into the code.  As a tractable example using the SIMON32/64 test vector:

simontool -e -b 32 -k 64 -s 1918111009080100 -t 65656877 -l log.e.32.64.txt -x simon-e-32-64

That dynamically creates a LaTeX file that contains a bit grid based on the input vector.


What's the probable usage of Interlock Protocol

The interlock protocol still relies on an external verification mechanism, otherwise the eavesdropper can replace the challenge with his own challenge.  In the example in the paper, they mention recognizing the voice of the person reading you half the challenge.  That's the external verification.  Without a pre-shared piece of information, a computer network or protocol has no external frame of reference, and can't "challenge the challenge."

Thus, we still need entities like certificate authorities (only better.)


What is a good way to handle longer strings using FPE?

FE1 has no inherent maximum length; that limit is imposed by the implementation.  The first obvious suggestion would be to use an alternate implementation without that limitation.

Now, lets assume that's not a viable option; that you have to use this particular FE1 implementation.

Now, the problem with chopping up the plaintext into fragments and encrypting those separately is that if someone modifies just one of those encrypted fragments, they'll modify part of the decrypted plaintext, but not all.

I'll suggest a way around that, using the "tweak" that FE1 also provides.  This "tweak" value is another input into the FE1 algorithm that modifies how it encrypts data; it is not assumed to be secret, but not be presented to both the encryption and the decryption.  What it is intended to do is bind the ciphertext to a particular context (so that the ciphertext cannot be used in any other context).

The idea is to split up the plaintext, and encrypt each one separately; however we use the rest of the message as a tweak.  For example, if we split up the plaintext into three sections $P_1, P_2, P_3$, we generate the ciphertext as:

$$C_1 = FE1_k( P_1, 0 || P_2 || P_3 )$$
$$C_2 = FE1_k( P_2, 1 || C_1 || P_3 )$$
$$C_3 = FE1_k( P_3, 2 || C_1 || C_2 )$$

(where $FE1_k(A, B)$ means "the $FE1$ encryption of $A$, using key $k$, with tweak $B$).

In general, ciphertext $C_i$ is defined as $C_i = FE1_k( P_i, i || C_1 || C_2 || ... || C_{i-1} || P_{i+1} || P_{i+2} || ... || P_n )$

To decrypt, you just do things in the opposite order:

$$P_3 = FE1^{-1}_k( C_3, 2 || C_1 || C_2 )$$
$$P_2 = FE1^{-1}_k( C_2, 1 || C_1 || P_3 )$$
$$P_1 = FE1^{-1}_k( C_1, 0 || P_2 || P_3 )$$

By binding each ciphertext block to both the previous and subsequent blocks, you prevent anyone from modifying part of the message without affecting everything.  This does assume that your FE1 implementation allows long tweaks.


What is a good AES mode to use on file encryption?

Since you zip the directory before encryption, we can assume that the compressed directory now is random file. You can use CBC mode or CTR mode. However, these modes are not providing any authentication.

You should use authenticated encryption mode as AES-GCM.

There is another issue waits for you. How do you derive cryptographic keys from the user's password? The common method is using a KDF function as PBKDF2 or Argon2.

You generate a random AES key and encrypt the zip file with it. After the encryption, encrypt the AES key with the key derived from the user's passwords with KDF and store it together with the encrypted file.

For the random bytes generation, at least, you should use urandom.

Python has AES-GCM and PBKDF2. You can find the example codes as here and here


Well, with CFB mode, the encryption process is "take the most recent ciphertext block, pass it through the block cipher, and then exclusive-or that with the plaintext block to generate the next ciphertext block".  As for the IV, that's used as "the most recent ciphertext block" when encrypting the first plaintext block (where you don't have a most recent ciphertext block yet).

Now, the advantage that CFB brings to the table is error recovery, including errors that add or delete ciphertext blocks.  That is, is a ciphertext block is garbled (or a block is inserted or removed), the corresponding decrypted plaintext block and the one after that is also garbled; however, after that, the decryption process resyncs, and then it decrypts the rest of the text correctly.  Now, CBC also has this same property in regards to entire blocks; however, if you take the last 128 bits of ciphertext, encrypt that, and then use (say) only 8 bits of each AES block output, and exclusive-or that is 8 bits of plaintext to form the next 8 bits of ciphertext, well, now you have something that is resilient against changes that inserts or removes individual bytes from the ciphertext (at the cost of having to run the block cipher N times to encrypt N bytes).  Nowadays, this is not considered relevent (we generally want to encrypt and MAC entire messages, and if anything was changed, we reject the entire message); historically, this was considered a nice feature if (say) you were encrypting data going over an RS-232 interface (which really could add/drop individual bytes).

The other advantage that CFB mode has (over, say, CBC) is that the decryption process also uses the block cipher in encryption mode; depending on how different the block cipher encryption and decryption is, this can be convienent.

Now, as for your questions:

As to the relationship between CBC and CFB; well, they both perform the same general process, they both take iteratively exclusive-or in the next block of plaintext, and then run that through the block cipher.  How they differ is where they pull the ciphertext from; CBC pulls it after we run the internal state through the block cipher, CFB pulls it after we compute the exclusive-or.
Is it OK to use with AES?  Why, yes, AES works perfectly well with CFB.  As for your statement that "the plaintext message should enter AES algorithm to encrypt the plaintext message", why, that's not at all true; in Counter mode, the plaintext message doesn't go through the AES algorithm at all.  For CFB mode, for the very first ciphertext, yes, the plaintext doesn't enter the AES algorithm; however, for any other ciphertext block, we send the previous ciphertext block through it, and the previous plaintext blocks were used to compute the previous ciphertext block.


Exact communication of the IPS compiler?

They do not specifically assume a bit-OT… but at least in the semi-honest case, it seems that having an ideal bit-OT is indeed sufficient.

If you are wondering about the fact that they do not specify which kind of OT they use: their purpose was to focus on a black box use of the primitive; bit OT and string OT can be easily reduced in black box to each other.

And if you are wondering about the fact that the communication is only $O(s)$: the costs of the OTs are not counted, as they are replaced by an ideal primitive to which all the players have access.


Computational indistinguishability: are function parameters known?

You're right: If you know the setup, calculating the next output from any given $x$ is fully deterministic and you know everything already.

Even if you don't know $a$ and $b$, those are easy to calculate from three consecutive $x_i$. If $n$ is not known, its calculation is still pretty easy, given a few consecutive $x_i$.

Anyway, LCGs are very unsuitable for cryptographic tasks. That's why in pretty much every standard library you find a warning not to use the standard Random class for cryptographic protocols (at least for Java and Python I know those warnings are there).

Usually not the entire output is used, but only a part of it, because otherwise two consecutive numbers can't be equal (and ever change again afterwards). Such an RNG is good enough for almost all non-security-related context, where randomness is needed (it is good enough for a little randomness. But e.g. in simulations, where a lot of random numbers are needed, you want "better" randomness, e.g. from the Mersenne Twister). Anyway, predictable PRNGs (without the CS) based on any such construction is not suited for cryptography. For CSPRNGs, you can find a couple of designs on wikipedia.


Why is knowing M not enough to break Blum Blum Shub?

Knowing $M$ is not enough to break Blum Blum Shub because the internal state of the random number generator, $x_i$, should never be revealed. Therefore, while you are correct that knowing the current state allows you to know the next (and all subsequent) states, a secure implementation of BBS should not reveal the internal state.

For provable security, only one bit should be revealed at each iteration. That said, you shouldn't be using BBS in practical applications at all.


No.
Any adversary could simply perform the hash themselves and so you are providing them with no additional resources.


How is the inter and the intra distance of a PUF calculated?

I believe Roel Maes gives a very good answer to your question in his PhD thesis, pages 20-23.

In essence, ideally, you need to calculate an array of the Hamming Distance between every pair of responses to the same challenge. Those pairs correspond to either the same chip or different chips depending on if you are looking at intra- or inter- distance.

Both metrics and various statistics based on them are, in principle, characterising the performance of the whole PUF construction. For example, the maximum intra-distance would give an idea of the worst case ('least reliable') response that could be expected. As a result, $n$ should be equal to the maximum number of challenge-response pairs (CRPs) offered by the PUF.

Of course, reading out all the CRPs negates the purpose of the PUF in some scenarios. In practice, one would get hold of a number of instances of the same chip and run some characterisation experiments to get the metrics. After establishing a certain confidence in those metrics a different set of chip instances would be deployed in production.

The whole thesis (with a lot more details and formulas) is freely available at https://lirias.kuleuven.be/handle/123456789/353455


I invented SIDH and can surely answer any technical questions about it. Proofs of $E_{ab} \cong E_{ba}$ are given in several places, though rarely in official Theorem / Proof form, because this result is just an application of well-established theory on elliptic curves rather than any sort of new mathematical result that merits formal statement as a theorem. See for example the original paper (Section 3.2, in particular the (unique) displayed equation in that section), or De Feo's survey article (page 34), or Martindale and Panny's cryptanalysis summary (page 4, paragraph "Key exchange").

If you have a more specific question, please ask away.


Why do we use 1024 / 160 bit primes in DSA?

There are two ways to solve a discrete log problem over $Z^*/p$, that is, given $g$ and $h$, find $x$ with $h \equiv g^x \bmod p$:

If the point $g$ generates a subgroup of size $q$, use a general Discrete Log algorithm (such as Pollard Rho) to recover $x$ in $O( \sqrt{q})$ time.
Use the Number Field Sieve algorithm to attack the discrete log problem in $Z^*/p$.  NFS is typically seen as a way to attack the factorization problem; it can also be applied (with some additional complexity) to compute discrete logs.

Because of this second possible method, using $p \approx 2^{160}$ would be a serious weakness.


How can one protect against a Man In The Middle attack during key exchange without using certificates?

Any shared secret can be used. Securely distributed passwords and symmetric keys, for example.  Alternatively, you can use asymmetric cryptography, such as public keys.

For one example, SSH has for years authenticated servers using public key cryptography and users typically using either public keys or passwords. Only recently had SSH added support for certificates.


Are there any attacks on the key exchange when the client and the server are using the same private key?

No, there shouldn't be any weaknesses. The server key and client key don't interact within the protocol in such a way that relationships between the two matter.

Key exchange is done either using the server key (EG:TLS_(server key algo)_WITH_(cipher suite) modes) with the client encrypting a secret which only the server key can decrypt. Or with ephemeral keys (EG:TLS_(DHE/ECDHE)_(server key algo)_(cipher suite)). In both cases, relationships between the server and client keys do not matter.

Client certificate authentication is done separately from key exchange(step 5). The client signs a digest created from messages previously sent in the protocol.

An attacker with access to a client cannot get the client to perform the private operation on arbitrary data. They only control messages which contribute to the hash which the client signs.
An attacker with access to a server cannot use the server as a decryption oracle. They can submit arbitrary encrypted messages to the server as an "encrypted session key" the server will perform the private operation and attempt to use the result to derive a session key. The intermediate result, the result of the private operation is not accessible to the attacker in any useful way.
If TLS is configured to use an ephemeral key exchange, the client authentication is the same but the server is completely useless to an attacker since it just signs an ephemeral public key which the attacker does not influence.

In all cases, the keys never interact in the way you worry about (EG:DH mixing)

SSH is similarly immune. It uses ephemeral keys and client and server keys are used differently so that the client cannot hand back the signature supplied by the server.


Send content to owner of gpg public key, nested content symmetric encryption

If you encrypt a text file with the GPG utility, it randomly chooses a symmetric key, encrypts the file using that key, then encrypts the symmetric key using an asymmetric algorithm, and embeds the encrypted symmetric key in the file. There is a format that GPG uses and expects, but it is not easy to work with.

There is an RFC that describes the OpenPGP file format. It's not fun reading, but with a lot of hex dumps and a lot of time with the GPG source, I did figure out the basics of a GPG-encrypted file.

I did take the openssh project and carve out the sftp piece to build a package that encrypts the files when it puts them on the remote server and decrypts them when it reads from the remote server. The format of the files is GPG-compatible, without using the GPG utility. You might find some useful code in there for generating GPG-readable files, mostly in the iron subdirectory. IronCoreLabs/ironssh GitHub project


What restrictions exist for publishing on strong encryption in USA?

My experience is from my time working in the State of Georgia, and firstly, how true that you want to stick to this depends on your funding source, and your end goals.

For software, the truth is probably nothing needs to be done in a practical sense due to Bernstein v. USA, but it's legally more complicated, and the details are here.
By the letter of the law: If your keys are greater than 64-bits, each time the cryptographic functionality of the source code is updated or modified you have to notify NSA and the U.S. Department of Commerce Bureau of Industry and Security (BIS).  If there are changes, you will need the specifics to notify BIS and NSA.  I also explicitly keep embargoed countries and people from accessing the files because I only distribute them on request.  This means that you can do whatever, and then publish the source code if you notify BIS.  I also send them updates every 3 months to say "nothing has changed" because if not, they ask.

For hardware, it's much more complicated because it is much more inconvenient.  I cannot fab anything without the proper forms in place, and the fabs enforce this as well.  I need a product ECCN.  Another annoyance is that I always end up making "hardware for export" for conferences.  For example, I have a power attack for SIMON128/256, but I've only shown the SIMON32/64 attack publicly because there's no way to guarantee who's in the audience.

The biggest issue of why to care is the funding source.  If you get USA money, you want them to feel like you are playing by their rules.  I've put up with the bureaucracy so I've been able to get repeat funding for semiconductors, and those aren't cheap.


Does there exist the method of projective coordinates for the computation of scalar multiplication for Koblitz curve?

Koblitz curves are still (convertible to) elliptic curves with a short Weierstrass equation.

Therefore you can use the standard projective / Jacobian coordinate systems as you'd use for more generic curves, though I think (variants of) Jacobian coordinates tend to perform best. All of these coordinate systems only require a single modular inversion at the end of the scalar multiplication, in an operation often called "rescaling".

If your curve is additionally of the form $y^2=x^3+b$ further optimizations seem to be possible using a special case of Jacobian coordinates.


There's no advantage to padding short passwords with a (non-secret) constant.

It doesn't make the password hashes any harder to crack by brute force guesswork: if an attacker can program a computer to try common passwords like abc, 123, swordfish, etc. (and they can, with very little effort), they can also just as easily make it try abcAnyConstantToMakePasswordBigger, 123AnyConstantToMakePasswordBigger, swordfishAnyConstantToMakePasswordBigger and so on.
It doesn't make the hashing algorithm (PBKDF2-HMAC-SHA1, according to CodesInChaos) any harder to break (not that anyone knows how to break it anyway).

In fact, technically, the HMAC-SHA1 algorithm does internally pad the password to 512 bits (= 64 bytes); it just happens to pad it with null bytes (and then XOR each byte with 0x36 for the inner hash calculation, and 0x5C for the outer one).  Note that, given the way SHA-1 and pretty much any other modern cryptographic hashes work, padding with null bytes is no more or less secure than any other fixed padding.

Padding the password with a secret constant (often called "pepper"), however, can improve security in some scenarios — specifically, if an attacker gains access to the password database (e.g. through an SQL injection vulnerability), but not to wherever the secret constant is stored.  However, if you want to do this, you should add the pepper to all passwords, not just to short ones.


Cracking pdf file with arabic password using hashcat

If you cannot get things to work with the application you can try and use the source code instead. A lot of these tools are open source. Then you can specify the character set directly and/or use an Arabic dictionary.

The password itself is not stored when a password is hashed. That means that the precise encoding details are lost - the password hashing algorithms themselves process bytes, not characters usually. Nowadays a lot of password hashes and applications default to UTF-8 though, which can encode any character set. UTF-16 and UTF-16LE can also be tried, with and without BOM header.

However, to find out which character set is used just from the hash (instead of, say, a protocol specification) you can only try.


There are three main issues with 3DES that an application needs to be aware of:

Small block size – 3DES has a small 64-bit block size. When encrypting non-negligible amounts of data with a single key, a small block size makes the Sweet32 attack possible.

Meet-in-the-middle attack – Due to its construction, the effective strength is reduced from 168 bits to 112 bits by virtue of a generic attack called meet-in-the-middle.

Inefficiency – DES itself is not very fast, and 3DES is three times slower.

When encrypting a very small amount of data, 3DES is sufficiently secure if one does not need a high performance cipher or a security level above 112 bits. Its use in smart cards is not an issue. Some smart cards use much weaker ciphers, or ciphers with even smaller block sizes (e.g. Simon32/64).

To answer your individual questions:

How susceptible is it to brute force

It provides a 2168 security against naïve brute force, and 2112 against brute force augmented with a meet-in-the-middle attack. This is generally sufficient.

dictionary

The key is not derived from a human-generated passphrase, so dictionary attacks do not apply.

or collision attacks?

Collision attacks are usually an issue with hash functions, not block ciphers, although the Sweet32 attack can be considered a type of collision attack. The small block size does make collision attacks possible, but only if a large amount of data is encrypted with a given key.


Cryptographically secure PRBGs and the previous-bit test

If you only have a subsequence of the output that does not include the first bit, then the bits of your subsequence can be labeled $b_0$, $b_1$, $\dots$. The bits of the overall sequence from which they are taken would then be labeled $\dots$, $b_{-1}$, $b_0$, $b_1$, $\dots$.
In other words, you're not necessarily starting the labeling of the bits at the beginning of the generator output, but rather at some later point. In that case there is a previous bit, and the previous-bit test applies.


What makes RSA secure by using prime numbers?

In order to generate a RSA key pair, you are to find a public exponent $e$ and a private exponent $d$ such that, for all $m \in \mathbb Z_n^*$, i.e. $m$ is relatively prime to $n$, $(m^e)^d \equiv m \pmod n$. It is a consequence of Euler's theorem that if $e, d$ satisfy the equation $ed \equiv 1 \pmod {\phi(n)}$, they are such a valid public/private exponent pair.

The fundamental theorem of arithmetic says that every integer has a factorization into powers of prime numbers that is unique to the integer, save for the order of the factors.

The definition of Euler's $\phi$ function is that $\phi(n)$ equals the number of integers less than $n$ and relatively prime to $n$. In order to determine this number, you have to know the factorization of $n$.

Consequently, if you select a number $n = pq$ where $p, q$ are both prime, you will have selected a number you can factor, but, if it is large enough, no one else can factor. The reason for this is because, using known factorization algorithms for arbitrary integers, the running time of such algorithms depends on the relative size of the second largest prime factor of the input. This means that given the public exponent $e$ only you can determine the private exponent $d$.

(Note: The hardness of performing the RSA private key operation $m \equiv c^d \mod n$ given only the public key $e, n$ as above, is known as the RSA problem, which hasn't been proved to be as hard as factoring the modulus. The best known method is however by factoring the modulus $n$ in order to determine $d$ given $e$.)

It also means that if you were to select $p, q$ just as odd integers, you would make it harder for yourself to find $\phi(n)$, while at the same time decreasing the relative size of the second largest prime factor, and thereby making it easier for everyone else to factor $n$. In fact, it would be as hard for you to factor $n$ as it would be for everyone else, so you would completely loose the trapdoor component of your scheme (if not making it completely infeasible to find a pair $e, d$).

Regarding your second question, for large $x$, the number of primes less than $x$ equals $\pi(x) \approx \frac x {log(x)}$. Hence, the number of primes roughly equal to $\sqrt n$ is, for large $n = pq$, large enough to make factorization algorithms faster than a brute force search. Besides, by the arithmetic theorem above, the adversary is really only interested in prime numbers anyway, so the question is moot.


Why don't PyCrypto and M2Crypto produce the same result as OpenSSL here (AES-128 ECB)

Commandline openssl enc normally does Password Based Encryption which derives the actual key, and IV (although IV is ignored for ECB), from the password or passphrase you enter, using a variant of PBKDF1. To get "raw" encryption you must specify the key in hex with -K (uppercase), in which case -nosalt is irrelevant (because it applies only to PBKDF). Except for the most recent releases of OpenSSL (and my test system has an older one) with -K you must also specify an -iv in hex even when the cipher/mode used doesn't need it, like ECB.

lin04:~ $ echo -n YELLOW SUBMARINE |od -tx1 |awk '$1="";gsub(/ /,"")'
59454c4c4f57205355424d4152494e45
lin04:~ $ echo -n 0123456789abcdef |openssl aes-128-ecb -nopad \
-K 59454c4c4f57205355424d4152494e45 -iv 00 |od -tx1
0000000 20 1e 80 2f 7b 6a ce 6f 6c d0 a7 43 ba 78 ae ad
0000020

Out of scope of your question, but I hope you know that using ECB is in most cases
a very bad idea. I've seen probably dozens of questions and answers here and
security.SE about that. As the most glaring fairly recent example, see the Adobe
password breach, which allowed many many passwords to be broken due to using ECB.


Yes, there is a practical attack.  Leaking those (or even just one of those) allows us to factor the modulus quite efficiently.

Suppose the attacker knows the values $n$, $e$ (the public exponent) and the value of $d \bmod (p-1)$ (which we will call $dp$).

Then, the attacker selects a value $m$, and then computes:

$gcd( n, m ^ {e \cdot dp-1} - 1 \bmod n)$

To see why this is likely to give us a nontrivial factor of $n$, let us consider the value of $m ^ {e \cdot dp-1} \bmod p$ (which we can do, even if we don't know the value of p).  We see that this is:

$m ^ {e \cdot dp-1} \bmod p = 1$

This is because $e \cdot dp = 1 \mod (p-1)$ (and Fermat's Little Theorem).

In contrast, this same value modulo q is (with high probability, assuming $m$ was selected randomly) not 1, and so $m ^ {e \cdot dp-1} - 1 \bmod n$ will have $p$ as a factor, but not $q$.  And thus,

$gcd( n, m ^ {e \cdot dp-1} - 1 \bmod n) = p$

with high probability.


The point is that even though $p - 1 = tq$ may be large, the discrete log security of $(\mathbb Z/p\mathbb Z)^\times$ against Pohlig–Hellman depends on the size of $q$, not on the (possibly much larger) size of $p$ or $tq$.  If $q$ is the largest prime factor, then the cost of computing discrete logs modulo $p$ is essentially at most the cost of computing order-$q$ discrete logs in Pohlig–Hellman.  This is why, e.g., Schnorr groups are chosen to have an order with a large prime factor.


How can I create an RSA modulus for which no one knows the factors?

One practical method: use a Java Card Smart Card. Load a trivial Java applet, made with the free Java Card Classic Development Kit, that generates an RSA key, and outputs the public modulus. Then either destroy the Smart Card, or zeroize it.

The applet will be so simple that it can be convincingly audited, either from source or from the tiny, well documented Java Card bytecode (RSA key generation itself is a few bytes in that, invoking the method built into the Java Card runtime supplied by the card/micromodule manufacturer, possibly calling a library supplied by the chip manufacturer). Some Java Card models are security-certified with similar usage and security demonstration in mind (though it might be hard to purchase these certified models in small quantities, and next to impossible to obtain their full documentation).

A difficult problem: convince oneself/the audience that what's loaded in the Java Card is really the audited applet, and more generally of the integrity of the gear handling the Java Card and the result it produces. In key ceremonies for Smart Cards where the integrity of the gear is paramount, it is common to install a bare OS to a virgin PC without network access from original optical media in front of the customer, but the Smart Card readers might not be scrutinized, even though that equally matters.

Also, there still is a risk that the card developers goofed at writing the RSA key generator. There are precedents:

section 6.1.1 in Petr Švenda, Matúš Nemec, Peter Sekan, Rudolf Kvašňovský, David Formánek, David Komárek, Vashek Matyáš: The Million-Key Question — Investigating the Origins of RSA Public Keys, best paper of Usenix Security Forum 2016. This one is a Java Card (but not an audited one that I could identify from its traceability data, which I obtained from the lead author).
Daniel J. Bernstein, Yun-An Chang, Chen-Mou Cheng, Li-Ping Chou, Nadia Heninger, Tanja Lange, Nicko van Someren: Factoring RSA keys from certified smart cards: Coppersmith in the wild, in proceedings of AsiaCrypt 2014. Some part of it appears to be FIPS 140-2 certified, but likely the certification was abused so badly as to become meaningless.

Ah, and of course, it is hard to convince others that the number you exhibit was produced in that way. Not such a good answer..


I think I'm trying to find the C in an RSA cipher to find the key for an aes_128_ecb cipher, can anyone tell me if I'm on the right track?

I think you should review how RSA encryption and decryption work.

You are given all the elements you need:

$P = C^d \mod N$

You know $d$, you know $p$, $q$, and thus $pq = N$. Usually people use $e$ to the encryption exponent and $d$ for the decryption exponent, but from what you said, $d$ is being used to encrypt.

You can recover $C$ with $P^u \mod N$, where $u$ solves:

$ud = 1 \mod (p-1)(q-1)$

Can you figure it out from there? (Hint: The Extended Euclidean algorithm will help.)


Is there any encryption method (theoretical) that could process instructions on encrypted code?

Yes.  It's called Fully Homomorphic Encryption.


RSA exhibits symmetrical properties — is it possible to form a cryptanalytic attack?

The first observation in the question boils down to: in textbook RSA, the encryption of $N-M$ instead of $M$ yields $N-C$ instead of $C$.

This is a special case of a more general property of textbook RSA, that the encryption of $M\cdot M'\bmod N$ yield $C\cdot C'\bmod N$, whenever enciphering $M$ yields $C$ and enciphering $M'$ yields $C'$; combined with the elementary fact that enciphering $M'=N-1$ yields $C'=N-1$.

These properties are the basis of numerous attacks on textbook RSA, including some of these (and of attacks on real RSA signature schemes with ad-hoc padding, such as on ISO/IEC 9796-2 scheme 1). This is why textbook RSA should not be directly used for anything else than random messages, or messages sufficiently close to that.

A second observation in the question considers the case of $N=P\cdot Q$ with $P-1$ smooth.

The worst thing if that happens is that it is easy to factor such $N$, using Pollard's p-1 factoring algorithm (giving a total break, making the considerations in the question of secondary importance). However this is not a serious weakness of RSA, for the odds of accidentally selecting such a $P$ are vanishingly small for usual order of magnitude of $P$; see the Dickman function for a numerical estimate.

Further, we can avoid such $P$ with relative ease; this remains standard practice at least for $P$ up to 512 bits (see appendix B.3 in FIPS 186-4, and in particular the requirement in B.3.1 A: "p and q with lengths of 512 bits shall be generated using the conditions based on auxiliary primes"). The only case when this might matter (there is not quite a consensus here) is when one generates ziiillions of keys, with $\log_2P$ below or close to 512, and a marginal risk that even one public key is vulnerable to Pollard's p-1 factoring is unacceptable (the adversary's best use of CPU time might be to attack each key with Pollard's p-1, rather than a few keys with other factoring methods).


Can Web Cryptography API's native key object be reverse engineered in any way?

The Web Crypto API isn't intended to stop users from getting their own keys, or guaranteeing that to web pages. The Web Crypto API allows web pages to create and use private keys that the web page (and future versions of the web page) can not access; the API is about protecting web pages' keys from themselves.


There are serious errors in the fragment quoted in the question, which is (an appendix of) the paper: Josep Domingo-Ferrer, Qianhong Wu, Alberto Blanco-Justicia, Flexible and Robust Privacy-Preserving Implicit Authentication (in ICT Systems Security and Privacy Protection, Volume 455 of the series IFIP Advances in Information and Communication Technology pp 18-34; also in arXiv:1503.00454).

We are invited to use the technique in [7]: James Demmel and Plamen Koev, The Accurate and Efficient Solution of a Totally Positive Generalized Vandermonde Linear System, in SIAM J. Matrix Anal. Appl. 27 (2005). But in that reference [7] the unknowns $a_i$ are real variables, and the critical issue is numerical stability; when the unknowns in the context are integers, and the system of equations to solve is $\bmod n$ (or at least modular). I'm thus inclined to believe reference [7] can't be directly applied. That might have to do with why reference [7] was not used; quoting section 6 of the paper

  we used straightforward Gaussian elimination which takes
  time $O(s^3)$, although, as mentioned above, specific methods like [7] exist for generalized Vandermonde matrices that can run in $O(s^3)$ (such specific methods could be leveraged in case of smartphones with low computational power).

Even with Gaussian elimination, I am left puzzled at the description of how the authors proceed in the setup phase. My best guess is that their $\log$ really is discrete logarithm to base $g$ in the multiplicative group $\bmod n^2$ (where $g$ is some generator, possibly the same as in the public key); but in that case, the linear system obtained won't be $\bmod n$ as written: an appropriate modulus $m$ would be one with $g^m\equiv1\pmod{n^2}$, and there is no reason that $g^n\equiv1\pmod{n^2}$. I'm cautiously optimistic that using $m=\lambda(n^2)=p\cdot q\cdot\operatorname{lcm}(p-1,q-1)$ would be a step towards reason (note: $\lambda$ is the Carmichael function).

But I see another issue: computing discrete logarithm to base $g$ is computationally involved in the general case even with factorization of $n$ known, we have not been told in appendix B to choose $p$ and $q$ making that operation easier, thus I do not see how we could (as told in section 4.1, Set-up item 4)

  randomly choose $R'\in\mathbb Z_{n^2}$. Find $r'_0,\dots,r'_s\in\mathbb Z_{n^2}$ such..

as to match the system of equations in the question, by the reduction to a linear problem that (my reinterpretation of) the paper suggests.

My best idea to reach the goal of Set-up item 4 is to assume that we can write $R'=g^u\bmod n^2$ and $r'_i=g^{v_i}\bmod n^2$ for $0\le i\le s$, and choose random $u$ and $v_0$ (yielding random-enough $R'$ and ${r'_0}$ with known logarithm). Having done this, $\log(R'/r_0)$ becomes the chosen $u-v_0$, $\log(r_i)$ is the unknown $v_i$ for $1\le i\le s$, and indeed if we can solve the linear system of $s$ equations $\bmod\lambda(n^2)$ with $s$ unknowns $v_i$ for $1\le i\le s$, then that solution yields what's wanted in Set-up item 4.

I find the paper lacking on many more points than exposed above; among such pitfalls:

No argument is given that what's disclosed at Set-up item 5 does not allow factoring $n$ or finding information about the user's profile, which is essential to the stated goal; the closest thing being an assertion without proof (made quite moot by what I emphasized)

  If both parties are honest, then the carrier learns $|X\cap Y|$ but obtains no information about the elements in $X$ or $Y$.

There are striking similarities with earlier work blinding set operations (including counting the intersection) using the Paillier cryptosystem; at least the seminal reference [9] (Michael J. Freedman, Kobbi Nissim, Benny Pinkas, Efficient private matching and set intersection, in proceedings of Eurocrypt 2004) is in the bibliography, but the text makes no reference to it.
We are given benchmarks of the setup phase, but no way to reproduce or analyze these, and not even a clear description (hence the question);
The performance numbers are given for a CPU only specified as "Intel i7", which leaves performance unspecified by a wide factor, given the variety of processors sold under this label;
In appendix B, the decryption for the Paillier cryptosystem has a number of small issues, and two serious ones:

the final formula uses the wrong modulus $n^2$, rather than $n$;
it is missing the critical Euclidian division by $n$ step!


Recovering a secret that has been blinded several times

If all we know are the blinded values $y_i$ (and the modulus $p$), and if the blinding factors $r_i$ are indeed sampled randomly from the multiplicative group modulo $p$, I don't see any way to recover the secret $x$.

This is because, for any list of blinded values $y_i$ and any candidate $x$ value, we can compute a unique list of blinding values $r_i \equiv y_i \cdot x^{-1} \pmod p$ that, when multiplied by $x$ modulo $p$, will yield exactly those blinded values.  Given that the $r_i$ values are chosen randomly, this particular list of blinding values is exactly as likely as any other.  Thus, this blinding scheme appears to be unconditionally secure.

(Also, the knowledge that the $r_i$ values cannot repeat won't help, since all it implies is that the $y_i$ values won't repeat either.  If we did observe repeated $y_i$ values for the same secret $x$, we would know that the corresponding $r_i$ values must be the same, but would still gain no further knowledge about $x$.)


How to prove to a third-party that a given response came from a specific domain?

No, at least for standard ciphersuites, TLS/https does not allow proving to a third party that an https payload was received from a certain domain.

Problem is, the initial TLS handshake leads to symmetric keys known by both parties, used to secure the rest of the exchange. Thus each party can forge messages and pretend the other side sent them.


What is customizable in ECDSA signature and verification?

Theoretically which things should be known to both modules:

Padding scheme for message

As mentioned in the comments, the 'padding scheme' for ECDSA is either fixed or arguably nonexistent.  You take the hash value, zero extend it if it's smaller than the group size, you take it modulo $q$ if it's bigger than the group size, and then fit that integer into the ECDSA equations.

Hashing function

Yes, bare ECDSA signatures and public keys have no way of indicating what hash function is used.  IMHO, it should be listed in the public key; it isn't (at least in my experience)

Scheme for combining message and signature

Well, you appear to be under the impression that we always attach the signature to the message.  Sometimes this is true, as in PGP. However sometimes this isn't true at all, for example, if we are using signatures to authenticate IKE; there, the value we sign is actually derived from the contents of a previous packet, hence we can't say that the message and the signature are combined at all.
What I've seen in practice is that we separate out the protocol level stuff (how are messages and signatures transported; there are a lot of varients used in practice) and the crypto stuff (how to do ECDSA); for example, on the verification side, there is some upper layer that somehow obtains the message and the signature, and then presents them both to the verifier.

Something else?

Apart from the public and private keys that you mentioned:

The actual curve being used; that is far from irrelevant to the crypto module.

The format of the signature; I've seen two variants; one is to just paste the $r$ and $s$ integers together (using a fixed length for both); the other is to ASN.1 encode it as a sequence of the two integers.  Now, it's possible that the protocol-level logic that I mentioned before would standardize that...


Encode ASN.1 PKCS#8 Private Key with Public Key and attributes

This is more about representation and manipulation of data in a computer program than cryptography. Questions about Dart or the use of libraries in Dart, are better asked on Stackoverflow.
The [0] and [1] are context-specific tags; more exactly they are tags that are not universal (because then the number-type mapping would be fixed and known) with a class that is not specified and thus defaults to context-specific.
Because they are IMPLICIT, the top-level ASN.1 type of their contents is not encoded, and cannot be shown by a generic decoder like the one you link -- see a page earlier, above the table of universal types.
[0] is Attributes which in rfc5958 (and many other places) is SET OF Attribute (with infoset constraint) where CMS-style Attribute is SEQUENCE { attrType OBJECT IDENTIFIER, attrValue SET OF ANY --DEFINED BY type-- } in the old ASN.1 notation, or with attrValue defined by an infoset in the new notation. Thus the decode of [0] shows the one SEQUENCE of OID plus SET containing UTF8STRING.
On the other hand, [1] is PublicKey ::= BIT STRING which has no internal structure, so it is shown as raw data -- including the prefixed value octet for unused_bits = 00, so the real value of the publickey is the remaining 32 octets.


A Lightweight Matrix Suggestion for MixColumns State of AES

I'm not sure to what paper you reference with "30th paper from FSE 2018" because in this list the 30. paper is not about implementing MDS matrices. As the 31. paper is, I assume you refer to this, entitled "Shorter Linear Straight-Line Programs for MDS matrices".

When you take the XOR count as a metric for efficiency, you can just compute this for your matrix and end up with an naive XOR count of 144, an optimized XOR count of 103 when using the SLP heuristics from the above paper. While the 144 XORs for the naive implementation are better than 152 XORs we would need for a naive implementation of the AES MC matrix, the later can also be optimized with SLPs and this will give you an implementation with only 97 XORs.
So, when only using the XOR count metric, it appears that your matrix is not more efficient than the AES matrix.

Of course it also depends a lot what application you have, if you only need to encrypt stuff (e.g. using AES in CTR mode), looking only at the "normal" matrices is fine, but when you also need decryption and thus the inverse matrices, these have to be implemented as well.


How do salt and initialization vector differ?

The term salt and IV are indeed largely used to provide the same functionality. They differ mainly for the type of algorithm. Both are used to ensure that the output is not purely determined by the input.
IV's or salts don't necessarily have to be random, they may just be unique. In that case the functions output is pseudo-random; the randomness is taken from the entropy in the key material (or password) instead. The requirements (the output size, if they need to be randomized or not) for the salt and IV depend on the algorithm used.
The term IV - Initialization Vector - is generally associated with block cipher modes of operation. Most of these modes use some kind of chaining of operations. As the name implies the IV is just the "first vector". This can be most easily shown by looking at CBC-mode of operation: here every plaintext block is XOR'ed with the previous ciphertext  block (the vector) before it is fed into the block cipher, but the first plaintext block is XOR'ed with the IV instead.
Salt is a more generic term which is often used in combination with KDF and KDF-related algorithms. You'll often see the term mentioned in combination with password hashing (i.e. a PBKDF) and password based encryption (PBE). The salt is then used to derive unique key material. You may also see the term salt used for other pseudo-random functions such as MGF1 which is used for modern RSA encryption (RSA-OAEP) and signature generation (RSA-PSS).


We already know that $P$ $ \subseteq $ $BPP$ $\subseteq $ $BQP$. So, since the problems involved in the reductions are "hard", at first glance, such a LWE solver might have some impact on the following famous questions:

Is $P$ equal to $NP$?
Is $NP$ contained in $BQP$ ?

But analyzing it more carefully, we see that the first one is not really related to that setting, because, by Regev's results, given a quantum algorithm to LWE, we have a quantum algorithm to the lattice problems. But both $P$ and $NP$ are defined with respect to "classical" algorithms.

The second question makes more sense because because at least it involves quantum algorithms: if we had a quantum polynomial-time algorithm for LWE and some $NP$-Hard problem that reduces to LWE, then we would have a quantum polynomial-time algorithm for any $NP$ problem (therefore, $NP$ would be a subset of $BQP$).

However, the detail now is that the lattice problems involved in Regev's quantum reduction are not known to be NP-Hard.

That occurs because, roughly speaking, Regev's reduction states that a quantum solver for LWE with parameters $n$, $q$, and $\alpha$, where $0 < \alpha < 1$, gives us a quantum solver for the approximate GapSVP and SIVP over lattices of dimension $n$ with approximation factor $\gamma \approx \frac{n}{\alpha} $.

So, even if the LWE solver worked for $\alpha$ arbitrarily close to $1$, the approximation factor would still be greater than $n$. But we are far away from proving that those lattice problems are NP-Hard for linear approximation factors. And there are even negative results for the hardness of those approximate problems for $\gamma \ge \sqrt{n}$.

Therefore, with the current reductions we know, a quantum polynomial-time algorithm for LWE would (obviously) put LWE inside $BQP$, but would not impact questions 1 and 2.

Of course, from a practical point of view, that is a huge breakthrough.  On one hand those approximate versions of the lattice problems are not known to be NP-Hard, on the other hand, we don't know efficient algorithms to solve them.


Combine two sha512 hashes to a single hash

Most standard-use iterative hash functions (including SHA-512) are build in a way that these types of operation are not possible (without breaking the hash function).

They work generally in this way:

The message is split in same-size blocks (usually with some padding at the end to fill the last block): $pad(M) = M_0 || M_1 || M_2 ... || M_n$.
There is some internal "state" $S$, initialized to a fixed value $S_0$ at the start
For each block, some internal function $C$ (usually called a "compression function") is applied to the old state and a message block to produce a new state: $S_{i+1} = C(S_i, M_i)$
At the end, either the last state is output directly, or (in more modern hash functions) another function $O$ is applied on that state to produce the final hash output: $h(M) = O(S_{n+1})$

So for example with a 4-block message (after padding) we have $$h(M) =  O(C(C(C(C(S_0, M_0), M_1), M_2), M_3)).$$

The compression functions are usually build in a way that even a minor change in one of the inputs produces a totally different output, and such that there is no easy way to go back from the output to the input. (This is usually formalized as "$C$ is a one-way function".) (Sometimes parts of the state are treated specially and can be easily tracked back, like in Skein, where they contain a counter. This is not the case for SHA-256, and also in Skein this doesn't hurt anything, as the output doesn't include them.)

Even assuming there is no padding, O is the identity and our fragments have both the size of only one block, we get $h(F_1) = C(S_0, F_1)$, $h(F_2) = C(S_0, F_2)$ and
$h(F_1||F_2)) = C(C(S_0, F_1), F_2)$.
While we can write the latter also as $h(F_1||F_2)) = C(h(F1), F_2)$, the one-way property of the compression function doesn't allow us to get any information about this from $C(S_0, F_2)$.

But if you have $F_2$ actually given, not just its hash, you can use this to create the hash of $F_1||F_2$, even without knowing $F_1$. This is known as the length-extension property of iterative hashes with the identity as its output transformation.
In reality it is complicated by the presence of a padding, but you still get to create the hash for something like $F_1 || P || F_2$, where you know $h(F_1)$ (but not $F_1$ itself), $P$ is some padding depending on the length of $F_1$ (and not actually needed to be known by you), and $F_2$ is a string chosen by you).

Using a non-trivial output transformation blocks this – possible ways are to apply some simple truncation (like SHA-384, which is essentially SHA-512 with a different initial state and a truncation of the result), or some other compression-function-like transformation. Or simply apply the whole hash function again on the result (this is used e.g. as SHA-256d in the Bitcoin protocol).

On the other hand, there are hash functions which are specifically designed to allow stuff like that: hashing two (or more) parts of the message separately and create the final hash from the partial hashes.

Have a look at the Merkle tree article in Wikipedia, it explains the basic principles. When used as a simple message hash algorithm (and not a complex structure), for it to have a deterministic result, the size of $F_1$ needs to be one of some few specific values (e.g. powers of two), so the limit between $F_1$ and $F_2$ falls exactly on a border between two subtrees.


How relevant are hardware implementations of crypto algorithms?

Hardware implementations are common, and likely to become more common as security needs increase, rather than less common.  One place they're used is in the digital signature of messages, such as messages going to/coming from a Smart Card used for banking.  Those are tiny, slow, limited processors, and a hardware implementation has the potential to improve their performance.  Americans aren't used to the slowness that Chip and PIN will bring to the checkout experience, so anything that speeds up that process is going to be of great value.

Security is also becoming more critical for other embedded devices.  Smart homes use secure communications to tell door locks to unlatch, and alarms to disarm.  And in any battery operated device, such as an alarm sensor, power efficiency is often the top requirement.  If a hardware implementation saves a few milliwatts, that could extend the life of a battery in an alarm sensor by a month, which is a huge benefit to the homeowner.

With all the talk of cyber-terror attacks on Industrial Control Systems, the individual controlling hardware devices may soon need to validate signatures on each instruction they receive.  They need extremely fast response times to perform real time controls of manufacturing equipment, and must be able to quickly process an emergency shutdown request.  Encryption and authentication is always a bottleneck, so a high speed hardware implementation could help maintain near-real-time response times.  Look for those algorithms to be baked into the communications chips.

At the other end of the computing spectrum, giant web servers use HSMs to perform the encryption and decryption of thousands of https: sessions per second.  Dedicated hardware implementations make such devices far more efficient than general purpose CPUs.

In the middle, you have PCs and laptops, where encryption on the CPU is fast enough for the end users, and the performance benefits of hardware implementations is negligible.  But they're also the most subject to malware like viruses, and embedding the security features in a chip could prevent malware from accessing sensitive data like private keys.  (If TPM wasn't all about enforcing DRM and other forms of rights restrictions, it might have been useful for actual security functions.)


I don't think that's possible, at least not without the kind of intrusive mechanisms you'd need for reliable DRM.

Basically, if the user gets a key that lets them decrypt the files, what's to stop them from just decrypting them all and keeping the decrypted versions?

The only way this could possibly work if you only allowed access to the files through a program you control, which would present them to the user in a way that makes them hard to copy (like rendering video directly to the screen).  Then you'd need to prevent the user from modifying the program or running it under a debugger, or finding some way to copy the data anyway as it's presented (e.g. through the "analog hole").

All that's easier said than done — and once you've done it (as well as you can), you may find out that it still won't stop a clever and determined user from copying the data, but that it will piss off ordinary users because all the restrictions make them feel like they're working in a straitjacket.


Can I generate same random number given same entropy value?

Yes, of course you can do that hypothetically. By definition random numbers are generated based on the entropy together with known values and algorithms. It would of course be necessary to know those constants and algorithms though. Quite often this is possible as the source code for the random number generator is often known in some way or other (open source or research program).

Usually runtimes make use of the random generator of the operating system, and the Microsoft algorithm is pretty complex and may change for different versions of the operating system. However, good random number generation has been known to be complicated on VM's.

Nowadays it may well be that the OS mixes in values of the hardware based RNG on Intel and AMD processors or a TPM module on the motherboard, making it nigh impossible to guess the entropy used to seed the OS PRNG.

TL;DR is it possible? Yes, if you truly know all the entropy - which usually is a questionable assumption. But even then it requires a lot of practical knowledge and a lot of effort.


How can hashes be unique if they are limited in number?

how can for example SHA-256 be unique if there is only a limited number of them?!

Where your issue occurs is that they're not unique.  It's just very improbable that they'll reoccur.      Unique in this context is not a mathematical definition, it's a humanist one.

In terms of human numbers, $ 2^{256} $ = 115792089237316195423570985008687907853269984665640564039457584007913129639936 which is 0.1% of the number of atoms in the visible universe. So that's a lot of them.

There's a better  answer @ Why haven't any SHA-256 collisions been found yet?, but you should get the gist from the lengthy 116 quattuorvigintillion number.


Yes, this is possible. You can create a symmetric key per entry. You can then wrap that key with any key (of any person) you want and store the wrapped keys with each entry.

I strongly suspect that doing so within keypass is not possible.


The Montgomery Powering Ladder for computing the scalar product of a point P on an elliptic curve (or in every other abelian group) only needs the x-coordinate of P.

It is used widely since it is believed to be secure against side channel attacks, which is not true in all cases-- for example, see this.

For further details concerning the Montgomery Powering Ladder, see the subsection "Montgomery's ladder technique" in this article

To compute $d\cdot P, P\in E(K)$ we have the following formulas which are used in MPL:

Let $P_{1}, P_{2}, P_{3}, P'_{3} \in E(K): y^{2} = x^{3} + Ax + B$

$P_{3} = P_{1} + P_{2}$

$P'_{3} = P_{1} - P_{2} = \left(x'_{3}, y'_{3}\right)$

$x_{3} = \dfrac{2\left(x_{1} + x_{2}\right)\left(x_{1}x_{2} + A\right) + 4B}{\left(x_{1} - x_{2}\right)^{2}} - x'_{3}$

As you see, the y-coordinate of P is not needed in this computation.

I hope my answer satisfies your need!


What are some hashes that do not exhibit the avalanche effect?

In general, most hashing methods do not exhibit the avalanche effect:

most hash functions -- unless they were specifically designed to be cryptographically secure -- accidentally fail the avalanche test -- all cyclic redundancy checks (CRCs), all error correcting codes, nearly all checksums,  etc.
A few hash functions -- such as Locality-sensitive hashing and the way feature hashing summarizes a document as a short vector of integers -- deliberately fail the avalanche test, because they are designed to have certain features that are incompatible with the avalanche effect.

In cryptography, my understanding is that failing the avalanche test makes a hash function vulnerable to many attacks that every cryptographic hash function is specifically designed to prevent. So every cryptographic hash function either exhibits the avalanche effect or is considered broken.

Are you looking for an example of a broken hash function to show students why this is such a bad thing? Or (what I would find more interesting) are you designing a system where this property would be useful in some way?
I'd like to learn more about what you are trying to do.


Implementing AES MixColumns with fewest XOR gates

many thanks to everyone. When I was reading originally the FIPS 197 document I made one big mistake: I assumed that the appendix C had only the cipher portion, similar to the appendix B, and missed the uncipher portions.

Answering my own question, yes, translation of the variable temp to the one I proposed initially was correct. However, my error come from another part: For ciphering, you can save directly the results in the state array, but for the decryption you need 3 auxiliary variables more.

I'll clean the code a little more and try to suggest an update to the Contiki repository with my part.

Again, many thanks to everyone by guiding this misled soul


Should the seed of CSPRNG produce the same random number?

The seed is the source of entropy for any CSPRNG. A CSPRNG is a pseudo random number generator. The "pseudo" part in the name explicitly means that it solely depends on entropy delivered from outside the algorithm using one or more seeds. So a CSPRNG, by definition, cannot be designed to produce "different numbers", as the outcome solely depends on the seeding of the algorithm.

Maybe the term "deterministic random bit generator" or DRBG better catches this meaning - most CSPRNG implementations do also primarily output pseudo-random bits rather than pseudo-random (ranged) numbers.

Now CSPRNG implementations in many runtimes depend on seeding by the operating system. Such seeding may even take place if a user provides a seed themselves. Basically such systems treat the seed as an additional source of entropy, making the next retrieved values depend on both the entropy sources, by mixing them into the state.

Furthermore, CSPRNG algorithms or algorithm implementations may be configured (explicitly or implicitly) to perform re-seeding after a certain amount of bits or calls. In that case the CSPRNG performs a callback to the system that provides the (initial) seed to retrieve additional seeds, which are then mixed into the state. A user may usually also call a method to add seeds or fire a request to re-seeding.

Often CSPRNG's are not explicitly required to return the same random bits if the amount of bits are different between calls. Even if the CSPRNG is in the same state, asking for 8 bits and then 16 bits may result in different values than asking for 16 bits and then 8 bits.

CSPRNG's may also change their implementation slightly, for instance they may generate numbers in a range using several different methods.

All this makes using a CSPRNG of a runtime system very dangerous if you expect to having it generate the same sequence for the same seed, and using a CSPRNG for such purposes it a huge red flag within any design - unless the CSPRNG is explicitly designed for such purpose.

If you do need a predictable stream then you are better off using a KDF (for relatively small output), a XOF such as SHAKE-128 or SHAKE-256 or indeed a stream cipher. Beware though that crypto-systems such as EC may also use the bits in different ways, so if those systems change implementation, you'd still get different results.

Generally, however, a well seeded CSPRNG is all you need to implement a cryptosystem that requires randomness.


Is a subset of a random set still random?

Already answered here: https://stackoverflow.com/questions/471157/is-a-subset-of-a-random-sequence-also-random , take a look at all the answers.

But, saying in other words:

If you have a list of random bytes, any selection you make in that list will be random as well, according to your selection criteria.

Examples:

if you choose every 3rd element, you'll end up with another random
list;
if you pick up all the elements that are smaller than any
value, you'll end up with a list with random elements smaller than
your criteria;
if you choose to pick up the first 10 elements, you
have 10 random values;
... and so on.


Why can't they just fix SHA-1 if it's broken?

I have 3 answers: We can't fix SHA-1, we shouldn't fix SHA-1 and we already did fix SHA-1.
SHA-1 is a hash standard; many different people can and have implemented it and they all get the same results. SHA-1 is broken. We have to replace it and convince everybody to move on to a new standard. A fixed SHA-1 wouldn't be SHA-1.
We shouldn't try a minimal fix; we should build the best (fastest, most secure) hash algorithm we can. A minimal fix will keep us with the problematic basic structure of SHA-1. If are switching, we want something which will be secure for many years to come. And be as efficient as possible.

That said, we already fixed it. It's called hardened SHA-1; it is immune to the known and similar collision attacks and it is even backwards compatible with SHA-1, sort of. It detects patterns which will occur in a collision attack and are very rare in random data. Hardened SHA-1 is identical to SHA-1 on almost any input, yet won't be the same and an infinitesimally small portion of inputs we see in collision attacks of the class published.

However though there are no currently known attacks on hardened SHA-1 and it isn't much slower. Nobody has the illusion SHA-1 has competitive security with SHA-2 or SHA-3.
Even if you need to truncate to 160 bits, these are probably safer options.  If you must have backwards compatibility as a quick fix, Hardened SHA-1 is a great trick but you should make plans to switch to SHA-3


Can 2 bit commitment protocols be secure when sent together with the same bit

It is certainly safe for any commitment scheme we would want to use.  However, I believe that we can make a stronger statement; we can show that if there is such a method, then either C1 or C2 is not computationally hiding.

Suppose we have an oracle $\theta( C_1^x, C_2^y )$ that would take a commitment in C1 to the bit $x$ and a commitment in C2 to the bit $y$, and if those two commitments were to the same bit ($x=y$), it would output that common value; if they were to different bits, then the behavior is unspecified.

Then, suppose we were given a commitment $C_1^b$ in scheme C1 to a bit $b$.  When we could do is generate two commitments in C2, namely $C_2^0$ and $C_2^1$, and evaluate both $\theta(C_1^b, C_2^0)$ and $\theta(C_1^b, C_2^1)$.  Now, if $b=0$, we know that $\theta(C_1^b, C_2^0)$ must evaluate to zero (by the definition of the oracle); and so if the behavior of $\theta(C_1^b, C_2^1)$ was anything other than evaluating to one with high probability, we would be able to deduce that $b=0$.  Similarly, if $b=1$, then we see that $\theta(C_1^b, C_2^0)$ must evaluate to zero with high probability.

Hence, for C1 to be hiding, we must have $\theta(C_1^b, C_2^x) = x$ almost all the time.

This gives us a computationally efficient method to evaluate C2 commitments, that is, C2 is not hiding.


Should DES be avoided when developing new systems?

Yes. DES is no longer considered an approved algorithm by NIST, and breaking a 56-bit key can be done quickly - in 1998 the EFF DES Cracker managed to break a DES key in 56 hours. The average time it required to break any DES key was 4½ days. You could use triple DES instead, which is still considered secure, but it's very slow (in software, even single DES is slower than AES), and a time-memory tradeoff described by Martin Hellman in 1980 shows how to break 3DES with a 168 bit key in $2^{112}$ time. In addition the 64 bit block size is a major practical problem if using 3DES in some modes, as described by Thomas in his answer.


RSA Decryption with Private Key but no public exponent

There's nothing inherent in the RSA decryption operation that requires the public exponent; it's just:

  $P = C^d \mod N$

(or a slightly more complex version involving the CRT parameters)

So, strictly speaking, OpenSSL doesn't have to insist on it.

On the other hand, there are some protections against side channel attacks that involve the public modulus:

If they blind the message before performing RSA, the standard way to do this is to break this up into these operations:

Select a random $r$ and $r^{-1} \bmod N$
Compute $C_{blind} = r^e C \bmod N$
Compute $P_{blind} = C_{blind} ^ d \bmod N$
Compute $P = r^{-1} P_{blind} \bmod N$

To protect against differential fault analysis attacks (where they deliberately attempt to induce an error, and attempt to deduce information from the erroneous result); the standard way to protect against this is:

Compute $P = C^d \bmod N$
Compute $C_2 = P^e \bmod N$
Check if $C = C_2$; if not, discard the result and signal error.

Both of the above use the public exponent $e$ in their computations; hence they need to know it.

OpenSSL is able to do message blinding; I suspect that's why they always insist on it.


Why public key has two parts in my secure messaging client similar to signal

The answer to this question is simple. In simple words, in elliptic curve cryptography, the public key is calculated by multiplying the private key value $s$ with the base point $G$, which results a point on the elliptic curve point: $W = s \cdot G$. This point consists of has two values on the x-axis and one on y-axis if the curve is considered to be within a 2D coordinate system.

Here is a link which gives a good idea of it: ECC with Diffie-Hellman.


What does it means the security parameter K for cryptographic signatures schemes

The security parameter (usually denoted $k,\lambda$ or $\kappa$) is the input to the algorithms of a cryptosystem against which we measure security. That is it should have no effect on correctness of the scheme but only its security against attacks.

Formally the only requirement for this parameter is that attacks grow in time super-polynomial in this parameter and the time for legitimate applications of the scheme grows polynomially in this parameter.

Practically one also often encounters security parameters to make comparisons between parameter sets across schemes. For example a 384-bit elliptic curve has 192-bit security, AES-192 has 192-bit security and 3072-bit RSA has 128 bit security. So if you are asked for a security parameter independent of the scheme it usually is the "x-bit security" parameter, but when asked for a concrete scheme it usually is the "x-bit $Scheme" parameter. For all practical purposes a general security level / parameter of 128-bit is sufficient.


Is this problem with anti-circulant matrices hard?

No, this problem is not hard. Here is algebraic reformulation which leads to efficient key recovery.
Ring representation
Let $R = \mathbb{F}_p[X]/(X^4-1)$. We identify any $a \in S$ with an element of $R$ as follows:
$$
R(a) = a_0 + a_1X+a_2X^2+a_3X^3.
$$
From now on assume that we work with elements of $R$.
Let $rev$ denote the polynomial reciprocal function:
$$
rev(R(a)) = a_3 + a_2X+a_1X^2+a_0X^3.
$$
Then, it is easy to verify that for any $a,b \in R$
$$
rev(a\cdot b) = X\cdot rev(a) \cdot rev(b)
$$
and that
$$
f(a,b) = rev(a\cdot rev(b)) = X \cdot rev(a) \cdot b.
$$
Using the simple fact that $rev(X^i a)=X^{-i}rev(a)$, we can reduce the result of any sequence of operations of $f$ to the form
$$
s_i(k_1,k_2) = X^j \cdot k_1^x\cdot  rev(k_1)^y\cdot  k_2^z\cdot rev(k_2)^w,
$$
where $i,j,x,y,z,w$ are known integers (depending on the number of iterations $i$).
Note that we are given two such values $s_i, s_{i+1}$.
This settles simple (up to $rev$) algebraic formulation of the problem.
Clearly, without $rev$ we would be given a pair $(k_1^xk_2^y, k_1^zk_2^w)$ and it would be easy to recover $k_1,k_2$, excluding corner cases when the matrix
$$
\pmatrix{x & y \\ z & w}
$$
is not invertible modulo $p-1$, in which case we'll have to deal with factorization of $p-1$.
Recovering linear components
Observe that $X^4-1 = (X-1)(X+1)(X^2+1)$. We will consider $s_i \in R$ modulo each of the linear factors and two cases for the last factor depending on whether it splits or not.
Case of $X-1$
Reduction modulo $(X-1)$ is equivalent to computing the trace of the vector: $tr(a) = a_0+a_1+a_2+a_3$. It is easy to see (e.g. by plugging $X=1$ in the polynomial form of $a,b$) that
$$
tr(f(a,b)) = tr(a)\cdot tr(b).
$$
As a result,
$$
tr(s_i) = tr(k_1)^{F_{i-1}}tr(k_2)^{F_i},
$$
where $F_{-1},F_0,F_1,F_2,\ldots = 1,0,1,1,2,\ldots$ are the Fibonacci numbers.
Given $s_i, s_{i+1}$, we can "undo" the iterations via divisions like
$$
tr(s_{i-1})=tr(s_{i+1})/tr(s_i)
$$
and recover
$$
tr(k_1), tr(k_2).
$$
This amounts to inverting the matrix described above
$$
\pmatrix{x' & y' \\ z' & w'} = \pmatrix{x & y \\ z & w}^{-1}
$$
and computing
$$
tr(k_1) = tr(s_i)^{x'}tr(s_{i+1})^{y'},
tr(k_2) = tr(s_i)^{z'}tr(s_{i+1})^{w'}.
$$
Case of $X+1$
Similarly, let $tr'(a) = a_0 - a_1 + a_2 - a_3$. Then we also have
$$
tr'(f(a,b)) = tr'(a)\cdot tr'(b).
$$
The recovery of $tr'(k_1), tr'(k_2)$ is analogous to the case of $tr$, except that we have to track the sign, since $tr'(X) =-1$.
Case when $X^2+1$ splits ($p=4k+1$)
If $p=4k+1$, then $X^2+1$ splits into $(X-i)(X+i)$ (thanks @Mark).
However, reduction modulo $(X-i)$ or $(X+i)$ does not behave very well with respect to $rev$. Let $a = a_0 + a_1X + a_2X^2 + a_3X^3$. Then,
$$
a \mod (X-i) = (a_0 - a_2) + i(a_1 - a_3),
$$
$$
rev(a)\cdot i \mod (X-i) = (a_0 - a_2) - i(a_1 - a_3).
$$
We see that $a$ and $rev(a)\cdot i$ are "complex conjugates" of each other (note that $i$ is actually not imaginary but lies in $\mathbb{F}_p$).
The problem with previous approach is that $a$ and $rev(a)$ are not related by a constant multiplication and so each $s_i$ has 4 variables (whereas previously $k_1$ and $rev(k_1)$ collapsed into one variable).
Now,
$$
a \mod (X+i) = (a_0 - a_2) - i(a_1 - a_3),
$$
$$
rev(a)\cdot (-i) \mod (X+i) = (a_0 - a_2) + i(a_1 - a_3).
$$
Observe that the four expressions $a \mod (X+i), rev(a) \mod (X+i), a \mod (X-i), rev(a) \mod (X-i)$ contain only 2 unique variables. Therefore, $s_i \mod (X-i), s_i \mod (X+i), s_{i+1} \mod (X-i), s_{i+1} \mod (X+i)$ give four equations on the exponents of four variables (a pair of "conjugates" for each of $k_1,k_2$). Therefore, we can invert the respective 4x4 matrix and recover $k_1,k_2$ modulo $(X-i)$ and $(X+i)$.
Now that we have the solution modulo each linear factor, we can reconstruct the keys using the Chinese Remainder Theorem (CRT). This is a complete break for the case $p=4k+1$.
See SageMath implementation of the attack.
Case when $X^2+1$ does not split ($p=4k+3$)
In this case apply the same technique to recover the complex norm of $k_1,k_2$ modulo $X^2+1$, which is multiplicative.
Further, we reuse the previously noted fact that
$$
X\cdot rev(a) \mod{X^2+1}
$$
is the complex conjugate of $a \mod {X^2+1}$. In particular,
$$
X\cdot rev(a) \cdot a \mod{X^2+1} = norm_{X^2+1}(a)
$$
Recall that we have values of the form
$$
s_i(k_1,k_2) = X^j \cdot k_1^x\cdot  rev(k_1)^y\cdot  k_2^z\cdot rev(k_2)^w.
$$
Working modulo $X^2+1$, we can replace $rev(k_1)$ by $norm_{X^2+1}(k_1)/X/k_1$. Similarly with $k_2$. Since the norm is recovered,
we end up with equations of the form
$$
u_1 = k_1^{x'}\cdot  k_2^{y'}
$$
$$
u_2 = k_1^{z'}\cdot  k_2^{w'},
$$
where $u_1,u_2,x',z',y',w'$ are known. This is completely similar to previous attacks, and so we recover $k_1$ and $k_2$ modulo $X^2+1$.
After combining the components using CRT, we recover $k_1,k_2$ completely.
The scheme is broken.
UPD: I just realized that I was recovering $k_1,k_2$ from $s_i, s_{i+1}$ which is trivial to do in any representation by inverting each step. However, for $r_1=f(s_i,k_1), r_2=f(s_{i+1},k_2)$ the attack still works by inversion of the relevant exponent matrix $[[x,y],[z,w]]$ modulo element order of the multiplicative group of the ring (which is $p-1$ for $p=4k+1$ and $p^2-1$ for $p=4k+3$). The only caveat is that in the latter case the matrix is not always invertible modulo each factor of the order. I suppose that the solution is not unique in such cases.


Are there attacks on AES with 16-bit keys?

There is no such thing as a 16 bit AES key. AES is a block cipher with a block size of 128 bits and a key size of 128, 192 or 256 bits. As a block cipher, AES can only encrypt 16 bytes (128) bits at a time. AES in itsef is not (CPA) secure as repetition of the plaintext would lead to repetitions of the ciphertext.

To encrypt larger amounts of data, AES needs to be used as primitive in a block cipher mode of operation. Although block cipher mode of operations of course depend on the (high) security of AES, they have their own security boundaries. ECB is not secure at all, CBC needs a randomized IV, CTR needs a unique nonce and has limitations on the size of the input.

The practicalities of establishing the mode and parameters such as the IV depend on the protocol. You would have to examine the protocol, mode and cipher to establish if your use case is secure or not. This would also depend on the attacks you're willing to allow. For instance, just using AES in CBC mode of operation does not protect against man-in-the-middle attacks at all.


Calculating the point on the curve during ECDSA signature verification

To obtain (62, 4) you just add points $\textbf{but on elliptic curves}$.
This is different from a "regular" addition, since the result must be a point of the curve (or a point said to be at infinity, I'm not explaining I try to keep things simple) .
Addition is defined and to do so either you use the heavy addition formulas (If you have seen groups theory), either you do as explain in the coindesk article :
let $P$ and $Q$ be two points on the curve
to do  $(P) + (Q)$ you trace the line passing by both $(P)$ and $(Q)$.
This line will intersect the curve on a third point, call it $(R')$, then $(P) + (Q) = (-R')$  and you have your result,
i.e. if $(R') = (x, y)$ then $(-R') = (x, -y)$. (In the coindesk article $(-R') = (R)$)
This is an $\textbf{incomplete}$ explanation but you should catch the thing, I didn't discuss the special points (when the last coordinate's member is $0$), inflexion points (when $P = Q = R$), or why there is another point on both the line and the curve.
If you want to double a point $(P)$ you trace the tangent passing by $(P)$, and this tangent will pass by a second point on the curve and you take the opposite point.
Personally I never use the explicite formulas (I didn't write them here) , which are too heavy in my opinion, I just do it with the last method.
For the first part you just break $76G$ in additions and doubles of $G$. Then you replace $G$ by its coordinates $(2, 22)$ and you just double or add.
For example: $2.(2, 22) = (2, 22) + (2, 22) = (52, 7)$ using your curve.
To check your results, or to get it easily, you can use : http://christelbach.com/ECCalculator.aspx an online calculator for elliptical curves.
You just have to set the parameters of your curve ($mod p = 67$, $A = 0$, $B = 7$) and you will get the correct answer (I checked).


After having read the "paper", which is probably just a "publication" the relevant student had to tick off, I'm pretty sure that a standard probabilistic encoding of messages to curve points was used, which is usually attributed to Koblitz. Written algorithmically:

Pick a message $m$ of 1 decimal digit length.
Set $i\gets 0$
Construct $x=m\cdot 10+i$. If $i\geq 10$ return with an error, this has probability around $2^{-10}$.
Compute $y=\sqrt{x^3+ax+b}\bmod p$ where $\sqrt\cdot$ is a modular square root, ie $(\sqrt x\cdot \sqrt x)\bmod p=x$. If no such $y$ exists, set $i\gets i+1$ and go to 3.
return $(x,y)$

Decoding a curve point can then be achieved by finding the decimal representation and cutting the last digit off.


Creating a small number from a random octet string

The method given in this other answer is correct: to choose a uniformly random integer in range $[0,k-1]$ given a string of uniformly random integers in range $[0,n-1]$ with $1<k≤n$, get one integer $x$ from the string until $x<⌊n/k⌋⋅k$, then output $y=x\bmod k$. If we have $k≤n<2k$ (as in the question where $k=201$, $n=256$), that simplifies to: get one integer $x$ from the string until $x<k$, then output $x$.

However, that's not the best method, as asked: it consumes more from the input string than strictly needed. Otherwise said, when the input string is of limited length, odds that the algorithm fails are higher than needed. If there are $m$ values in the input string, odds of failure are $(1-⌊n/k⌋⋅k/n)^m$. For $k=201$, $n=256$, $m=3$, that's nearly $1\%$. It can get much worse: for $k=129$, $n=256$, $m=3$, odds of failure are over $12\%$.

We can modify the algorithm to improve on that; and also remove the $k≤n$ requirement.

Set $r←0$, $s←1$.
Get one new $x$ from the random string, set $r←r⋅n+x$ and $s←s⋅n$.
If $r≥⌊s/k⌋⋅k$, set $r←r-⌊s/k⌋\cdot k$ and $s←s-⌊s/k⌋⋅k$, and proceed to step 2.
Output $y=r\bmod k$, and stop.

Sketch of proof of correctness: by induction, before step 2 and before step 3, $r$ is a uniformly random integer with $0≤r<s$.

The integers $r$ and $s$ never exceed $(k-1)⋅n$, and thus the algorithm does not require arbitrary-precision arithmetic. It minimize odds of failure for a given input string of length $m$, to the bare minimum possible for exactly uniform output: $(n^m\bmod k)/n^m$; that is $≈0.0009\%$ (rather than $≈1\%$) for $k=201$, $n=256$, $m=3$; or $≈0.0007\%$ (rather than $≈12\%$) for $k=129$, $n=256$, $m=3$.

The algorithm works if the input string contains bits, or dice rolls with any number of faces, including variable (just change $n$ at step 2 according to the $x$ extracted from the input string).

If we need to generate more than one output $y$, there are several options:

The easiest is to start over; but that's clearly sub-optimal, especially when $n≫k$.
We can change "stop" at step 4 to: "set $r←⌊r/k⌋$, set $s←⌊s/k⌋$ (then, if desired, change $k$ for the next output); and proceed to step 3". The resulting algorithm still produce uniformly distributed output (the recurrence in the proof sketch holds), drastically reduce the consumption from the input string when $n≫k$, but I'm uncertain about optimality is not optimal (that's blatant for $k=2$, $n=3$).
If we know the number $j$ of desired outputs $y$ in advance, we can set $\hat k=k^j$, generate one $\hat y$ uniform in $[0,\hat k-1]$ using the optimal algorithm, then split $\hat y$ into $j$ outputs by expressing $\hat y$ as a $j$-digit number in base $k$. That's back to optimal, but is not a sequential algorithm, and requires arbitrary precision arithmetic when $j$ grows, with $O(j)$ extra memory.
We can generate any number of outputs using several batches of $j$ as in the previous tweak, but using the suboptimal sequential algorithm described above. That allows using bounded extra memory, and becomes close to optimality as $\hat k=k^j$ grows. However this is not a sequential algorithm.

I now lean towards belief that any optimum algorithm is bound to require $O(\log m)$ extra memory in some worst case. However it is possible to make a sequential algorithm using bounded extra memory, much less than above, and closer to optimality. I plan to detail such an algorithm (if someone else finds a reference, or otherwise has a suitable algorithm, please tell us!).


For public-key encryption, why does COA resistance imply CPA resistance?

I was/am assuming that for public key encryption, COA means "other than the public key, ciphertext only".  Otherwise, any secure symmetric cipher with the key published becomes a "COA resistant" PKE scheme.  With that in mind, access to an encryption oracle cannot possibly help an attacker, since the attacker can already encrypt any plaintext using the public key. $\:$ Therefore, COA resistance implies CPA resistance. $\:$ (for public-key encryption, with my assumption on the definition of COA)