Why do different applications of hash functions demand different properties of the hash function? A strong cryptographic hash function in general must guarantee several properties, including: Preimage resistance, second preimage resistance and collision resistance. It turns out, however, that certain applications only require a subset of the properties while others require all of them. The table below gives a summary of which applications require which properties (from Stalling's book). Can someone give an explanation for the properties required by each application? For example, it makes sense that one-way passwords require preimage resistance since we don't want a person to compute the password from the hash. But I would not understand why one-way passwords do not require collision resistance (i.e., if two different passwords give the same hash, then an impostor could more easily break in). Anyone with an explanation for the different properties? The table is from an authoritative textbook in the area (Stalling's book).

Hash + digital signature

If the hash is not collision resistant, the attacker can produce two messages having the same hash. They'll request a signature on the first and present the signature on the second, a forgery.

When second pre-image resistance is violated, this attack becomes much more severe, since now the attacker doesn't need control over both messages, they can simply use any (signature, message) pair they observed.

First pre-image resistance is not directly required, since signatures make no promise about hiding the message, But for common definitions first pre-image resistance is implied by second pre-image resistance.

IDS / virus detection

If second-pre-image resistance is violated an attacker can give their malware the same hash as an existing benign software, preventing blacklisting of the malware without the collateral damage of also blacklisting the benign software.

If collision resistance is violated an attacker can create one benign and one malicious piece of software. That's probably not a big deal, since the blacklisting will only affect the decoy software and not software somebody else developed. Still I'd strongly recommend using a collision resistant hash so you have a clear 1-to-1 mapping between hashes and executables, preventing confusion and misunderstandings.

Password hashing

Clearly the attacker must not learn anything about the password input, which is closely related to first pre-image resistance.

Lack of collision resistance only allows the attacker to construct two different but equivalent passwords which are valid for their own account. Second pre-image resistance requires knowledge of the correct password, and is thus harmless as well. The popular PBKDF2 password hash suffers from certain trivial collisions and second pre-images.

MAC

A MAC is keyed, a normal hash is not. So you need to specify how you construct a MAC from the hash. The standard choice is HMAC, which does not require collision resistance. As an example, HMAC-MD5 is still secure as MAC/PRF while the collision resistance of MD5 is utterly broken.

Key recovery is related to first pre-images, so you probably need that property. You also don't want any key independent collisions, but those are much harder to construct that plain collisions.

For a detailed description of sufficient conditions for HMAC security you can consult the HMAC proof of security.

Hash + symmetric encryption

If you want both integrity and confidentiality, we use authenticated encryption. The standard approach is first encrypting the message and then computing a MAC over the ciphertext. This is known as Encrypt-then-MAC and requires the same security properties as the MAC above.

Encrypting a hash of the message is insecure for many popular encryption algorithms, no matter how strong the hash. Don't do that, unless you really know what you're doing.


How is HMAC(message,key) more secure than Hash(key1+message+key2) I understand how for hash functions which are vulnerable to length extension attacks (such as SHA1 and SHA2) it is safer to use a HMAC construction.

What I don't understand is, how or why is $\operatorname{HMAC\_SHA256}_\mathrm{key}(\mathrm{message})$ safer (in terms of resistant against certain attacks) than $\operatorname{SHA256}(\mathrm{key}_1 \mathbin\| \mathrm{message} \mathbin\| \mathrm{key}_2)$, assuming that all key strings are sufficient in length and entropy?

The construction you are proposing is called the "envelope" or "sandwich" MAC, it predates HMAC, and it is in fact secure—provided the key and message are appropriately padded. That is,

$$
\text{SHA256}(k \parallel m \parallel 1 \parallel 0^{b - 1 - (|m| \bmod b)} \parallel k)
$$

is secure, as long as $k$ is the underlying hash function's block length $b$ ($b = 512$ in the case of SHA256), or is padded to that effect. Note that the padding after the message is crucial: without making sure the second key is in its own block the security of the envelope MAC is lower than that of HMAC. This was proved by Yasuda, and later Koblitz and Menezes (§6) argue that there is no sound theoretical reason to prefer HMAC over (correctly padded) envelope-MAC, beyond the former's more established nature.


AES: How to create the S-box with Sage The $Sage$ code for the AES $S-box$ is below and a link is here: Polynomial representation of the affine part of the AES S-box. An online version of $Sage$ to test this is here.

I understand most of it but I cannot understand where the polynomials for $a$ to $h$ come from. Can anyone give a simple example? Even for just one of the polynomials if this will suffice.

This might be a bit off-topic, but I can not yet add a comment:

Note that you can also use the SBox object, included in recent Sage versions (from >= 8.2, I think):

sage: from sage.crypto.sboxes import AES
sage: AES
...

This offers you methods for cryptanalysis etc.


Why is Vigenère Autokey self-synchronizing? According to the Wikipedia, and to several of our school study materials, Vigenère autokey ciphers are considered to be self-synchronizing stream ciphers.
If I understand it correctly, the main idea of self-synchronizing ciphers is that they should re-sync in an event of missing characters in the ciphertext because the key only depends on previous N characters.
But, as far as I understand, in Vigenère autokey, every character depends on all the previous characters being in the right order, isn't that so? So, in an event of a character loss, the rest of the ciphertext after the lost character will never be deciphered correctly.
So, what am I missing? Do I misunderstand self-synchronizing ciphers, or am I missing something about the Vigenère autokey cipher?

"Autokey" refers to an encryption method that uses the plaintext itself to generate the ciphertext. "Self-synchronization" of a stream cipher is not an encryption method. It is a modern (from 1946) process for a stream cipher to update its state based on the previous ciphertext.
Is Vigenère's Autokey Cipher an example of a self-synchronizing stream cipher?  No, but it could be coded, one supposes, to be self-synchronizing for certain methods of transmission and reception.
Background
Girolamo Cardano (1501-1576), a prolific writer and mathematician from Milan, came up with the first autokey cipher in 1550, but he designed it very poorly. As David Kahn explains in The Codebreakers (Macmillan, 1967), "He employed the plaintext as a key to encipher itself, starting the key over from the beginning with each new plaintext word." (Kahn, p.144).
Blaise de Vigenère improved on Cardano's work when he "did not recommence his key with each plaintext word, which was his [Cardano's] weakness, but kept it running continuously." (Kahn, p. 147). This innovation was "entirely forgotten" until the latter part of the nineteenth century. Vigenere's autokey is stronger than the famous "Vigenère Cipher" that was later mistakenly attributed to him, but it is a relic of the past.  Picture pen and paper, or even better, quill pen and parchment.
This idea of an autokey cipher that does not repeat the keyword has been used in some more modern cryptographic methods--rotor machines, for example--and the principle is still relevant. So, autokey is a symmetric encryption method with a curious history and many variations (also see Bellaso's method from 1564; Kahn, p. 144). On the other hand, self-synchronization of a stream cipher means maintaining its correct state.


Can homomorphic encryption offer program integrity and program obfuscation? By program integrity, I mean the (encrypted) result I receive is indeed the expected result and not, say, an intermediate result or a result affected by an adversary. Can homomorphic encryption defend against active attacks?

By program obfuscation, I mean the adversary not being able to infer what operations are performed (data access patterns aside).

If the homomorphic evaluation procedure is deterministic, as is usually the case, the program integrity requirement is trivially fulfilled: given a function $f$, the input ciphertext $C$ and the output ciphertext $C'$, anyone can publicly evaluate $f$ on $C$ (homomorphically) and check that the result is indeed $C'$. However, this conflicts with a standard other requirement, where one wants the output $C'$ to be distributed as an encryption with uniformly random coins.

When the output ciphertext is randomized, to ensure program integrity, the usual strategy is to use a zero-knowledge proof system. Namely, given a function $f$, the input ciphertext $C$ and the output ciphertext $C'$, the homomorphic evaluator will prove in zero-knowledge that $C'$ was obtained as the result of homomorphically evaluating $f$ on $C$ (and randomizing the output). Many solutions exist to implement this, depending on the other constraints (e.g. if we want this verification to be less expensive than performing the entire homomorphic evaluation, on can use succinct zero-knowledge proofs).

Regarding your 'program obfuscation' requirement, this sounds like what is usually called circuit privacy (i.e., when evaluating $f$ on $C$ homomorphically and getting an output $C'$, seeing $(C,C')$ should leak nothing about $f$). Any 'partially homomorphic' encryption scheme we know of (Paillier, ElGamal, Goldwasser-Micali, and the like) is re-randomizable (given a ciphertext $C$, anyone can publicly construct a ciphertext $C'$ encrypting the same value with uniformly distributed random coins), hence can be trivially made circuit-private. For fully homomorphic encryption, it's a bit more complex, but there are also well-established techniques, such as using noise flooding, or some more advanced strategies such as this one.


When it comes to linear cryptanalysis, is there always a key that could work for every possible input/output? Until now every tutorial I've seen about linear cryptanalysis, is written on the basis that we have all possible inputs/outputs. Is that a condition? And if not, how many should we have as a minimum?

I also noticed that the idea is to find a key that would work for every possible combination. So, when it comes to block ciphers that could be cracked using linear cryptanalysis, is there always a key that could work for every possible input/output?

Regarding your first question, we assume (for known plaintext attacks such as Linear cryptanalysis) that we can obtain a large number of inputs and the corresponding outputs under the unknown key. The goal of designing a good linear attack is to find a biased linear approximation to the cipher to minimize how many input/output pairs we need. But we shouldn't need all input/output pairs, since that would turn into a brute force codebook(dictionary) attack. Matsui's Linear cryptanalysis attack on DES needs only $\approx 2^{42}$ of the $2^{64}$ possible input output pairs.

Addressing your second question "..when it comes to block ciphers that could be cracked using linear cryptanalysis, is there always a key that could work for every possible input/output?":

Any block cipher defines a unique invertible mapping between the input and output spaces, say both are $\{0,1\}^n,$ given any fixed key, so the answer is yes, absolutely.


SRP and compromised verifier Let's assume that attacker knows the verifier so now the attacker can commit a Man-in-the-Middle (MitM) attack:

Client sends A to server;
MitM takes it and sends B to client.

As the MitM knows the verifier it is also possible compute the secret key. So every message from client encrypted by that key is not safe. How to deal with this situation?

As pointed by the question, in SRP an attacker knowing the verifier can impersonate the server. That's not against the security objectives of SRP.

To carry the attack, the attacker also needs to know the salt, but it is public and can be obtained from the server. With both verifier and salt, the attacker then behaves with respect to the client just as the server does.

The problem of authenticating the server can be solved by https and a server certificate, inasmuch as you trust certificates (certificates only checked by a common web browsers/OS should be only marginally trusted: governmental and other well-founded adversaries can easily obtain a forged certificate with any CN field they wish, and certificate chain, that pass this test). It is still reasonable to use SRP on top of https with a server certificate: at least, if the certificate is subverted, the password does not leak, and the user can't be impersonated to the server (the main goal of SRP), contrary to what would happen with the password sent over https.


RSA: Should the generation of random data used for primes include zero When generating random data that is later tested for primality, should the random data include the value 0x0?

I would have thought that primes that do not include zero's are a subset of the set of primes that do - and therefore make keys generated with no zero's easier to brute force?

However my colleges are of the opinion that having zero in the prime data makes the key operations consume less time / and or power, and thus make these keys more vulnerable to a DPA / timing based attack. They have also seen open source code that removes zeros from the random data.

Which is more of a concern? Attack, or a subset of primes?

When generating random data that is later tested for primality, should the random data include the value 0x0?

I'm reading this as: should the hexadecimal expression of the primes include the hexadecimal digit 0?

With hight likelihood yes. But that needs not/should not be tested. Common wisdom is that except for the few high-order bits (constrained by range considerations) and the low-order bit (which is set), all bit sequences much shorter than the prime itself should be random-like, thus about 1/16 of hexadecimal digits other than the low-order and high-order are expected to contain the hexadecimal digit 0x0.

  (Aren't) keys generated with no zero's easier to brute force?

Not sizably. Indeed, preventing the hexadecimal digit 0x0 to appear would reduces the possible primes. However, there remains so many that trying to factor an RSA public modulus by enumerating the candidate primes (roughly $2^{510\cdot15/16}/\log(2^{512})>2^{469}$ for 512-bit primes suitable for 1024-bit keys of FIPS 186-4 format) remains  hopeless anyway. And we know no efficient factorization algorithm that can take advantage of the special form of these primes.

  (..) my colleagues are of the opinion that having zero in the prime data makes the key operations consume less time / and or power, and thus make these keys more vulnerable to a DPA / timing based attack. They have also seen open source code that removes zeros from the random data.

To my knowledge, there is no evidence that accidentally having zeroes in the hexadecimal expression of the primes has sizable chance to enable a DPA / timing based attack. Arguments: long sequences of zeroes will be statistically rare; if there's data-dependent timing variation or potential for DPA attack in an implementation, that must be mitigated anyway; we could make the same argument for 0xF; on the contrary, knowing that there are not zero could conceivably speed-up some side-channel attack.

I do not know an open source RSA key generation code purposely weeding out primes with an excess of zeroes. And I'm reasonably confident that no public standard (from ANSI, BSI, ETSI, IEC, IETF, ISO, NIST, or the company formerly known as RSA security) asks for that. Do the person(s) with this recollection also remember what open source code does that, so that said recollection can be cross-checked, and perhaps a rationale found from comments or a reference?


How to construct encrypted functions (with either public or private data)? Homomorphic encryption is often touted for its ability to

Compute on encrypted data with public functions
Compute an encrypted function on public (or private) data

I feel I have a good grasp of #1 as most of the papers I've come across on homomorphic encryption (both partially and fully) seem to deal with this type of problem, but #2 I haven't been able to wrap my head around.

So, to whittle this down to the simplest case, given a fully homomorphic encryption scheme, let the public input be $a,b,c,d$ (each is a single bit for simplicity). How would I construct a function to compute $(a\vee b) \wedge (c\vee\neg d)$ such that whoever I give it to will not know what the actual function is (granted this is such a simple example they could easily create a brute-force lookup table)?

I'm not looking for an exact function, but how this would be done in general. How does it change if I make it that $a,b,c,d$ are private (to the function creator)? Is the process similar for partially homomorphic (where only the $\wedge$ or $\vee$ operations are possible)?

Theoretically, with fully-homomorphic encryption (like with Gentry's scheme), you could make a circuit (with memory) which computes over encrypted data and outputs encrypted results. The circuit could be a general-purpose CPU, and the encrypted data the code which is to be executed (reading this again, I think this is what @ByteCoin suggests).

Since this method requires doing some pretty heavy stuff for every gate in the circuit (including every gate which is used for RAM in our custom CPU) and for every clock cycle as well, the cost would be tremendous (polynomial, yes, but with a hell of an exponent).

Now this would work over encrypted data, and produce encrypted results. If you want an encrypted function which runs over public input data and produces a public output, then the party who holds the decrypting key must be involved at some point. Without such a party, I don't think it is known whether it is doable.


What are good sources for properly learning cryptography for a mathematician? I'm a pure mathematics student(currently in a Msc program) looking to get into cryptography. I imagine most "regular" introductory books on cryptography would avoid being too heavy on mathematical details due to the target audience. So I'd like to ask, if someone is perhaps able to recommend good books that provide an introduction to cryptography for someone rather unfamiliar with it, but having all the neccessary mathematical background to understand full details and justifications of the algorithms etc.

Edit: I'm aware that I can't possibly know  every theorem etc. involved, but I think it's safe to assume that I should be able to lookup any such additional details in reasonable time, while going through the book.

Reference requests are off-topic here, so your question will likely be closed. Nevertheless, here are three pretty good introductory books that don't skimp on mathematical details. They're all intended for grad students with a good amount of mathematical maturity.

Foundations of Cryptography volume 1, by Goldreich. This is the classic book in what I sometimes think of as "complexity-theoretic crypto", which starts with one-way functions (OWFs) and builds more complex primitives like pseudorandom generators and zero-knowledge proofs from OWFs. Another (soon-to-be-published) book of this type is Pass and shelat's "A Course in Cryptography"; you can google around for the most recent version.
Introduction to Modern Cryptography by Katz and Lindell. This is a newer book that covers what most people consider "applied cryptography" - that is, how do you build an encryption scheme that you would really implement to protect some data. Books in this genre generally start with the one-time pad instead of OWFs. Covers the basics of symmetric- and public-key cryptography well, but does not cover zero-knowledge proofs.
A Graduate Course in Applied Cryptography, by Boneh and Shoup. A draft of a not-yet-complete book on applied cryptography. The finished chapters cover a fairly large subset of what Katz/Lindell does, and some subjects (e.g. constructing PRFs) in more detail. Also has a lot of nice exercises and neat "case studies" on topics like side channels.

Because someone suggested it in a comment: I would avoid more specialty texts that only cover the mathematics of public-key crypto, at least for your first text. This includes Hoffstein et al.'s "...mathematical cryptography" and Koblitz's books. These are good books, but they'll only teach you enough modern cryptography (i.e. security reductions and definitions) to be dangerous. Learn how to do a proof by reduction and understand security definitions before you get into the deep mathematics of public-key cryptography.


Advantages of HS1-SIV over ChaCha20-Poly1305-SIV? What advantages does HS1-SIV have over ChaCha20-Poly1305-SIV?

I know that both use the ChaCha stream cipher, but I am trying to understand why HS1-Hash is a better MAC.

Edit: To hide the Poly1305 result I would use of the ChaCha20 core, a.k.a. HChaCha20, as a nonce-free but keyed PRF.  This works because ChaCha20 is really a keyed hash in counter mode, and can also be used as a PRF directly.  In fact, this is what XSalsa20 does with Salsa20 – it uses the Salsa20 core as a PRF to generate a 256 bit subkey from a 256 bit key and 128 bit nonce, the other 64 bits being used as the nonce for the subkey.  Since HChaCha20 is a strong PRF (ChaCha20 is broken otherwise), I can just use it as a keyed 128->128 bit PRF, by discarding the top 128 bits.

ChaCha20-Poly1305-SIV is not well defined, and does not have the advantages of SIV-mode if you do define it.

The SIV mode is essentially MAC-then-encrypt, with the MAC reused as nonce. The MAC in ChaCha20-Poly1305 requires a nonce, because it uses ChaCha20 to encrypt the Poly1305 authenticator (you cannot reveal the raw authenticator). So you cannot use it to derive a nonce without already having a nonce.

You can use a version of SIV where a nonce is included in the MAC calculation, but then you do not gain any nonce-reuse resistance – the MAC is broken with nonce-reuse. You also have the problem (not insurmountable) of defining how the 128-bit MAC is used as a nonce to an encryption algorithm that only takes a 96-bit nonce.

Essentially, then, there is no advantage of using the SIV mode over just using ChaCha20-Poly1305, and the clear disadvantages of performance and complexity. HS1-SIV solves this by generating new keys using a hash of the message instead. This means that nonce misuse is not the end of the world.

With the updated question, where the MAC is Poly1305 and a PRF applied to it, the requirement of a strong nonce is lessened. However, unless you do include a nonce, you get worse bounds so you would still want a nonce (also to make it non-deterministic, if you want that).

In that case the advantages of HS1-SIV are not so clear. However, it is hopefully a somewhat better analyzed construction – or will be if it does well in CAESAR. It also offers different parameter options, the highest of which uses a hash larger than the 128-bits you are limited to with Poly1305. That means a lower probability of collision, and a higher number of messages before running into the birthday bound.

Again, you would still need to define how a 128-bit nonce will be used in ChaCha20, how or if associated data is authenticated, etc., but it seems like a reasonable option to HS1-SIV's middle set of parameters. The main advantage of HS1-Hash, then, is its flexibility.

(I do not know if it has performance advantages, but it seems possible that especially with short messages it would have an advantage over using an extra ChaCha call as a PRF.)


Communication cost of Oblivious Transfer and OT Extension? Suppose there exist fixed K set of N-bit strings.
Here, sender and receiver perform 1-out-of-K OT either once or many times.
In the latter case, we may use OT Extension.

What is the order of the communication cost of Single base-OT and OT Extension??

If we do a single 1-out-of-$K$ OT, is the communication cost $O(N)$ or $O(KN)$?
If we do OT extension to invoke  $m$ independent 1-out-of-K OTs, is the communication cost $O(mN)$ or $O(mKN)$?

Best,

With the most standard approaches, the cost of performing $m$ $1$-out-of-$n$ oblivious transfers of strings of length $\ell$ with security parameter $\lambda$ is $O(m(\lambda + n\ell))$ (see e.g. this paper, Section 5.3). Use $m=1$ above to have the asymptotic cost for a singe OT. Note that this can be improved in various settings - e.g., it can be typically much less if all you need is are random OTs (where the selection bits and the transmitted strings are random). We can also get some savings when $\ell$ is very small (constant) and $n$ is not too big as well - for example, $1$-out-of-$2$ OT of length-$1$ secrets can be done with communication $O(\lambda/\log \lambda)$ with the same paper.

One can further improve this cost, at least in theory. Typically, it is theoretically feasible to perform $m$ $1$-out-of-$n$ oblivious transfers of strings of length $\ell$ with security parameter $\lambda$ using communication $O(m n\ell)$, under standard assumptions (e.g. under the DDH assumption, with a constant $4+o(1)$ in the $O()$ when $m$ is sufficiently large, using this paper - note although that this is not concretely practical)


AES/GCM/PKCS5Padding giving issues while AES/CBC/PKCS5Padding works fine for my use case I have a requirement to read-encypt-save plus its reverse i.e. read-decypt-save files through chunk/block mechanism (single operation not feasible because of huge(GBs) file sizes).
So essentially the two functionalities should work as below :

loop (read-plain-text-block-from-external-source -> encrypt -> save-encrypted-text-block-to-external-target)
loop (read-encrypted-text-block-from-external-source -> decrypt -> save-plain-text-block-to-external-target)

Also requirement is to have flexibility to use different chunk/block sizes while encryption / decryption. so either party (Encrypter or Decrypter) does not know other's size at all.
Now we have successfully implemented this functionality using AES/CBC/PKCS5Padding but we are facing issues while trying the same using AES/GCM/PKCS5Padding. Decryption was returning blank plain chunks and we finally received aggregated plain chunks at loop completion. this stops us from saving individual decrypted-chunks to external target during single iteration of the loop.
Any idea if AES/GCM/PKCS5Padding is even an option for our use case ? what must be causing above issue ?

AES-GCM uses AES-CTR to create confidentiality internally. Counter mode turns AES into a stream cipher, where the plaintext is XOR'ed with a generated key stream. This key stream can be applied bit by bit or - practically speaking - byte by byte (with the leftover key stream bytes after encrypting the last counter simply being discarded). Specifying any padding at all is a waste of effort for a stream cipher. Instead you should be using "AES/GCM/NoPadding" for Java.
I would not bet that other implementations allow GCM with PKCS#5 padding. Furthermore, it is the question if that mode would always be using no padding (as it isn't required), 1 byte of padding (since a stream cipher works with "blocks" of a single byte) or up to 16 bytes of padding (because the block size of AES is 16 bytes).
GMAC, the internal MAC operation of GCM also requires padding as it operates on 128 bit values. But as common with MAC algorithms, only one particular padding is used, so it doesn't need to be specified - it is not a configuration option.


Hashing into a supersingular elliptic curve Is there any way to hash from a string
$\in \{0,1\}^{*}$ into a supersingular elliptic curve $E(F_p)$ such that the hash function behaves(provably) like a random oracle, and is efficient?

Using Maurer's indifferentiability framework 1, one can prove that a cryptosystem using a random oracle is secure if the random oracle is replaced by an "indifferentiable" hash function. Brier et. al. 2 prove the conditions for a hash function to be indifferentiable from a random oracle, i.e. to put it simply, the hash function has to use an "admissable encoding" of elliptic curve points. They also provide a construction based on Icart's function that appears to work only on ordinary elliptic curves.

My question is, does there exist similar such constructions for supersingular elliptic curves? The Boneh-Franklin IBE requires the use of a hash function to a supersingular elliptic curve. They construct a hash function and prove that their IBE scheme is secure using the new construction. However, they do not prove that this construction is "indifferentiable" from a random oracle, or that this construction can be used in any other cryptographic scheme without altering its security.

Elligator works just fine for any (including supersingular) elliptic curve with a point of order $2$, with the sole exception of $j=1728$. The latter special case can also be done; see Section 4.2 here.

(The requirement that the curve has a point of order $2$ is trivially fulfilled for supersingular $E/\mathbb F_p$ where $p>3$ is prime, since this implies $\#E(\mathbb F_p)=p+1$ which is always even.)


Can I remove newlines in a public key? Can I remove new lines from the RSA public key file to get a one line string? So the question is if the key looks like this

AAA
BBB
CCC

or

AAA\n\rBBB\n\rCCC\n\r

is this the same as

AAABBBCCC

I'm assuming you mean a base 64 encoded key file, since removing the newlines from a binary file would obviously break things.

The RSA standards (e.g. RFC 2459) only define a binary representation for keys. In practice, like OpenPGP keys (RFC 4880), they are often encoded in base 64 using the otherwise obsolete PEM standards (RFC 1421).

The PEM printable encoding section says:

  To represent the encapsulated text of a PEM message, the encoding
     function's output is delimited into text lines (using local
     conventions), with each line except the last containing exactly 64
     printable characters and the final line containing 64 or fewer
     printable characters.

The OpenPGP radix 64 section says:

  The encoded output stream must be represented in lines of no more than 76 characters each.

For SSH, on the other hand, RFC 4716 Section 3:

  A key file is a text file, containing a sequence of lines.  Each line
     in the file MUST NOT be longer than 72 8-bit bytes excluding line
     termination characters.

Do implementations in practice accept longer lines? I would expect many to do so. However, while no information is lost, it's technically nonconforming to use such encodings.


minimal overhead of ChaCha20 + ECC What we want?

Encrypt plaintext with ChaCha20 + ECC on curve 25519 (hybrid cryptography) the result would be a data stracture X.

Input: public key on Curve 25519

No authentication required (no AEAD)

What is the minimal storage ovehead of producing a data stracture X as compared to the plaintext.
What are the required steps, and what are the elements of X.

The resulting data structure X should be decryptable by requiring only the corresponding private key.

If we were to cut on storage ovehead even further, at the cost of security (change curve Curve 25519 to something else? idea?)

32 Bytes (+16 for the tag)
Let data be your data, let || denote concatenation and let pkD be the "data's public key" (that is a Curve25519 public key which has exactly 32 bytes) and tag be the Poly-1305 authentication tag (16 bytes long).
Because pkD and tag have a fixed size, you don't need to encode their lengths and you can literally store this as pkD||data||tag. For decoding, you just grab the first 32 bytes as the data's public key and the last 16 bytes as the authentication tag.
Encryption would go like this:

Run a standard Diffie-Hellman key agreement against the recipient's public key. The public key you would normally send over the wire is pkD and will be stored for decryption.
Feed the shared secret into a key-based key derivation function to get an IV, a key for the symmetric cipher and a key for the MAC.
Encrypt the data using the symmetric keying material and append the authentication tag.
Delete all keys and the data.

If it is not of concern that an attacker can flip bits in targeted attacks with bit-level accuracy (that is, he can modify any known plaintext-ciphertext pairs to say whatever he wants), then you can omit the authentication algorithm and the MAC tag.


Standard format to encode AES cipher and random IV As far as I understood, a secret key (same length as CBC block size) and an initialization vector (IV) are needed to decrypt a AES-256-CBC encrypted string. As the IV should better be random, it has be distributed in plaintext along with the encrypted text.

Is there a standard or at least "commonly used" format to format the result?

E.g. /usr/bin/openssl seems to concatenate "Salted___" + IV + cyphertext and then base64 encode everything. Would this be a recommended way? I want to store the encrypted text and still be able to decrypt it in 10 years with any PHP/Python/Java library.

Is there a standard or at least "commonly used" format to format the result?

PKCS #7 (and CMS which is a further development) describes a standard format for encrypted data. While it's mainly meant for public key encrypted data, it also has options for symmetric keys. It's rather complex due to all the features it supports, however, so unless you can find a library that does all the encoding and parsing for you, you may want to do something simpler if you only need the format for your own use.

Another "format" that's probably quite commonly used is simply to concatenate the IV and the encrypted message (and then MAC, if applicable). However, that's not very discoverable.

  E.g. /usr/bin/openssl seems to concatenate "Salted___" + IV + cyphertext and then base64 encode everything. Would this be a recommended way?

Actually, "Salted___" in OpenSSL indicates password-based encryption, and the value that follows is not an IV for the cipher, but a salt for deriving the key and IV from a password. If you are using a key directly, rather than a password, you shouldn't reuse that format, or it'll just cause confusion.

  I want to store the encrypted text and still be able to decrypt it in 10 years with any PHP/Python/Java library.

Other than PKCS #7 or CMS, I would suggest using just plain ASCII to describe the format, cipher and mode and then concatenating the binary IV + data. It will expand the data, but space if usually cheap, and ASCII will always be readable.


RSA: What would happen if you chose n to be a prime? If Alice were to choose n to be a prime, instead of the product of two primes, what exactly would go wrong in the RSA cryptosystem? How would Bob decrypt her message?

How would Bob decrypt her message?

That'd be easy, all we would need to assume that Bob has the public key.  If $n$ is a prime, he is able to compute $d = e^{-1} \bmod{\lambda(n)}$, because $\lambda(n) = n - 1$.  He can then raise the ciphertext to the $d$th power modulo $n$, and that's the padded plaintext.

Since anyone with the public key can do this, RSA based on a prime modulus is insecure.


Is there any correlation in between two AES with a key differ only by one bit? (ECB mode) Given two AES (128bit, ECB mode) with almost equal keys $k_1,k_2$: 127 of the 128 key bits are equal. Is there any correlation in between the ciphers they build?
$$AES_1(m_i) = c_i$$
$$AES_2(m_i) = d_i$$
Would it be different to two keys differ by 64bit? by 128bit? Or the same key but shifted by $n$ bit?
E.g. An adversary found some correlation in between the target AES mapping and another he knows the key of. Does this help him anything for deriving the key of the target AES?

This is called a related-key attack. There are many types of related-key attacks and the AES key schedule is vulnerable to some of them, but not the one you describe. From the linked answer:

The key owner can somehow be persuaded to compute three other keys $K_B$, $K_C$ and $K_D$, from $K_A$, using a specific derivation algorithm ($K_B$ is equal to $K_A$ XORed with a constant that the attacker chooses; $K_C$ and $K_D$ use a more complex but equally deterministic derivation algorithm).

There are some ciphers which would be vulnerable to such a trivial related-key attack as the one you describe. The TEA block cipher has equivalent keys. Each key has two others which select the same permutation. The RC4 stream cipher is even more vulnerable. When used multiple times with keys which differ by a small number of bits, it becomes possible to calculate the key.
Even though AES is not vulnerable to such a trivial related-key attack, it is still a good idea to re-key it with independent keys (e.g. by passing a master key through HKDF), for two primary reasons:

So the security of your scheme is not dependent on the particular cipher being used.
To protect from future attacks against AES' relatively simple key schedule.


Thoughts on This Encryption Method, Please? I'm very much an amateur programmer, and 90+% of the math of true encryption is way over my head. That said, I did write an encryption program once upon a time and I'd appreciate your thoughts on it.  It was written in C++ as a command line executable that accepted a filename and a password as input. To encrypt, you would enter 'N-Crypt filename password'.  What it did was almost ludicrously simple. It opened the file it was to encrypt, looked at each byte in order and converted it to a value from 0 to 256 value based on the password you specified, using each successive ASCII character value of the password in order and cycling back to the first character when it reached the end. It also alternated between adding and subtracting the character value  So, for example, if the password was 'God' and the first byte of the file had a value of 30, it would add the ASCII value of 'G' which is 71 to the 30 and return 101. If the resulting value was greater than 255, it would cycle around, so 256 would become 0. If the second byte of the file was 220, it would subtract the ASCII value of 'o', which is 111, and the result would be 109, and so on until the entire file was encrypted, then it would overwrite the original file with the encrypted version.

Ludicrously simple, yes?  But here's where I think it got interesting - you could cycle the file encryption through as many different passwords as you wanted, and there was no limit on how long the password could be (except whatever limits the command line structure had).  So, say you started with a jpeg file, and cycled it through three encryptions using three different passwords.  To decrypt the file, you had to reverse the process with the D-Crypt command line program, using the original passwords in reverse order. If you didn't get any part of the passwords correct, the decryption process would fail, producing a file of gibberish. The only way anyone could know they'd successfully decrypted the file is it come out as whatever the file originally was.

So, my question is this.  If your a highly paid NSA cryptologist and you are handed a mystery file encrypted in this manner, what are your chances of successfully decrypting it?  What methods would be useful given the encryption scheme? Some of the first issues you face include 1. Not knowing the encryption scheme. 2. Not knowing the passwords. 3. Not knowing how many passwords were used. How would your chance of decryption improve if you also had copies of the encryption and decryption programs (you still would be facing issues 2 and 3)? To my non-cryptologist's brain, my scheme seems pretty secure, but you hear about decryption methods that border on the miraculous, so I really have no clue how secure it really is.

Thank you for any reply you care to give.

That looks like a (polyalphabetic) substitution cipher, with a less-straightforward method of entering the key. As already mentioned in the comments, close to the Vigenère cipher, which is rather well known. IIRC ciphers like that were used (and broken) in times before WWI (or WWII?), The Code Book by Simon Singh has material about historical ciphers, among other books, if you are interested.

As for not knowing the algorithm, it's usually taken as granted as the algorithm will be known (Kerckhoffs's principle), as it's hard to keep it hidden if the system is used widely enough and there is sufficient interest in it. Either the algorithm is widely available and can be bought, or it will be found out by old-fashioned spying, or in case of a single criminal using it, law-enforcement will be happy to read the software off your computer... (Since you need to have an unencrypted copy of the encryption program anyway.)

As for the system, consider that using words as keys isn't that unpredictable, passwords are attacked with dictionaries daily, and the range of 26 letters out of 256 values is also quite small (if mostly lower-case letters.) Also, this isn't strictly true:

  To decrypt the file, you had to reverse the process [...], using the original passwords in reverse order.

The algorithm has a property that makes the order of the keys irrelevant. Perhaps you can find it?


How can my application make sure the right symmetric key is used for decryption? I am developing an Encryption/Decryption Utility using Adobe AIR. I have chosen the AES algorithm and currently use the as3crypto library for this. My query is in what practical ways can I detect if the password provided at the time of decryption valid or not.

As of now I thought of encrypting a constant string with the password and storing the encrypted string in the header of my encrypted file. For decryption, I can check if the correct password is provided by decrypting this string.

This is a temporary work around as storing a ciphertext of a known plaintext (The string is hard coded as a constant inside my application) is not a proper way as I know.

Since I don't have much experience, I am looking for a proper and safe way to accomplish this. My application will be a standalone desktop application without a server.

First of all, you should definitely be using some sort of an authenticated encryption solution. If you can't use AES-GCM or some other mode designed specifically for authenticated encryption, you should probably pick AES-CTR and HMAC-SHA256.

Next, you should encrypt the actual data with a completely random key you have generated and store this key encrypted to the password (using a password based key derivation function, such as PBKDF2). If you want to be really proper, using a standard key-wrapping algorithm for this would be best, but using authenticated encryption works. Do not encrypt the key without authenticating it.

This gives you two benefits:

You can change the passphrase to a file without re-encrypting it fully
You can detect if the passphrase was typed wrong

And included the standard disclaimer: if this isn't for a hobby project - please don't. There's no need to reinvent the wheel - you can implement standard OpenPGP symmetric encryption, for example. And even if you do use a standard - cryptography is hard to implement correctly and it takes a long time to build confidence in an implementation.


How does the zuc algorithm complete the synchronization? I have already read the following documents:

Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3. Document 1: 128-EEA3 and 128-EIA3 Specification

Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3. Document 2: ZUC Specification

Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3. Document 3: Implementor’s Test Data

Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3. Document 4: Design and Evaluation Report

and I know the ZUC algorithm use the iv to synchronize for the frame, but I still don't understand how iv synchronization is implemented in real applications. Is the method for implementing synchronization similar to that in the WEP algorithm as show below?

In the WEP algorithm the output of the process is a message containing the IV and ciphertext, is the output of the ZUC algorithm also a concatenation of IV and ciphertext ( IV || ciphertext )?

frame counter (32 bit)

you find it in  last paragraph of page 14 in Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3. Document 4: Design and Evaluation Report.


How to perform AES MixColumns as matrix multiplication in GF(2) (boolean values)? AES MixColumns is done by multiplying a $4 \times 4$ matrix and a column of the AES state (a vector). Addition and multiplication are done in $\operatorname{GF}(2^8)$.

In the paper White-box AES, the authors use $32 \times 32$ matrix $\mathit{MC}$ times a $32 \times 1$ vector over $\operatorname{GF}(2)$.

My question is how this $32 \times 32$ matrix is constructed? Or more generally, how matrix multiplication in $\operatorname{GF}(2^8)$ is mapped to multiplication in $\operatorname{GF}(2)$?

Assume that we have to compute $M\times x$, where $M$ is a $n\times n$ matrix, and $x$ is a $n\times 1$ vector, all entries of $M$ and $x$ are in $GF(2^8)$.

We have:

$$
M\times x = M \times \left( \begin{matrix} x_0 \\ x_1 \\ \vdots \\x_{n-1}\end{matrix}\right)
= M \times \left( \begin{matrix} x_0 \\ 0\\ \vdots \\ 0\end{matrix}\right)
\oplus M \times \left( \begin{matrix} 0 \\ x_1 \\ \vdots \\ 0\end{matrix}\right)
\oplus M \times \left( \begin{matrix} 0 \\ 0 \\ \vdots \\x_{n-1}\end{matrix}\right)
$$

Write each $x_i$ in polynomial format: $x_i = x_{i, 0} x^0 + x_{i, 1} x ^ 1 + \ldots x_{i, 7} x ^ 7, x_{i,j} \in \lbrace 0, 1 \rbrace$, which is equivalent to binary form: $x_i = x_{i,0}x_{i,1}\ldots x_{i,7}$ (little endian notation). We have:

$$
M \times \left( \begin{matrix} 0 \\ \vdots \\ x_i \\ \vdots \\ 0\end{matrix}\right)
= M \times \left( \begin{matrix} 0 \\ \vdots \\
\left(\begin{matrix}
x_{i, 0} \\ \vdots \\ x_{i,7}
\end{matrix} \right)
\\ \vdots \\ 0\end{matrix}\right)  \\
= M \times \left( \begin{matrix} 0 \\ \vdots \\
    \left(\begin{matrix}
    x_{i, 0} \\ 0 \\ \vdots \\ 0
    \end{matrix} \right)
 \\ \vdots \\ 0\end{matrix}\right) \oplus
M \times \left( \begin{matrix} 0 \\ \vdots \\
   \left(\begin{matrix}
   0 \\ x_{i,1} \\ \vdots \\ 0
  \end{matrix} \right)
\\ \vdots \\ 0\end{matrix}\right) \oplus \ldots \oplus
M \times \left( \begin{matrix} 0 \\ \vdots \\
  \left(\begin{matrix}
  0 \\ 0 \\ \vdots \\ x_{i,7}
\end{matrix} \right)
\\ \vdots \\ 0\end{matrix}\right)
$$
(Note that $\left(0, , \ldots x_{i,j} \ldots, 0 \right)^T $ is still interpreted as a byte.)

Now, as $x_{i,j} \in \{0, 1\}$, we can check that:
$$
M \times \left( \begin{matrix} 0 \\ \vdots \\
  \left(\begin{matrix}
  0 \\ \vdots \\ x_{i,j} \\ \vdots \\ 0
\end{matrix} \right)
\\ \vdots \\ 0\end{matrix}\right) =
x_{i, j} \times M \times \left( \begin{matrix} 0 \\ \vdots \\
  \left(\begin{matrix}
  0 \\ \vdots \\ 1 \\ \vdots \\ 0
\end{matrix} \right)
\\ \vdots \\ 0\end{matrix}\right) = x_{i, j} \times V_{i,j}
$$

Hence:
$$
M \times x = \bigoplus_{0\leq i \leq n, 0\leq j \leq 7} x_{i, j} V_{i, j}
$$
$V_{i,j}$ is a $n\times 1$ vector, its entries are in $GF(2^8)$. We can check that writing $V_{i, j}$ in $8n\times 1$ binary format (let's call that $V'_{i,j}$) does not change the result. So we have:
$$
M \times x \mbox{ is equivalent to } \bigoplus_{0\leq i \leq n, 0\leq j \leq 7} x_{i, j} V'_{i, j} \\
= (V'_{0, 0}|| V'_{0, 1} || \ldots || V'_{n, 7}) (x_{0, 0}, x_{0, 1}, \ldots x_{n, 7})^T
$$
Let $MC = (V'_{0, 0}|| V'_{0, 1} || \ldots || V'_{n, 7})$, which is a $8n\times 8n$ matrix formed from $8n\times 1$ vectors, we have:
$$
M \times x \mbox{ is equivalent to } MC \times (x_{0, 0}, x_{0, 1}, \ldots x_{n, 7})^T
$$

Thus, we have transformed a matrix multiplication in $GF(2^8)$ to matrix multiplication in $GF(2)$.

Thanks my supervisor for this answer.


Using ECB as RSA encryption mode when encrypted messages are unique? As I understand, ECB should not be used as encryption mode unless you are encrypting single blocks of data which are always unique and only are encrypted once.

I have a collection of ids represented by integers that I encrypt and transmit (individually) with the same public key using RSA/ECB/PKCS1PADDING. Sometimes the same ids are encrypted and transmitted multiple times but as far as I can tell the ciphertext is never the same.

Can anyone tell me how this is possible? As far as I understand, this would not be an acceptable scenario to use ECB, but why are the encrypted messages never the same even though the key and plaintext messages are?

The Java algorithm string "RSA/ECB/PKCS1Padding", as you already found out, does not implement ECB; it only encrypts/decrypts a single block. The Bouncy Castle cryptographic security provider has a better named algorithm string, "RSA/None/PKCS1Padding", which better indicates that no mode of operation is used. It is likely that "/ECB" was just included to mimic the cipher string for  block ciphers. So you would have to call the cipher "RSA/ECB/PKCS1Padding" multiple times to implement ECB.
"PKCS1Padding" indicates RSA with PKCS#1 v1.5 padding for encryption. This padding is indeterministic - i.e. it uses a random number generator. This explains why each ciphertext block will be different.

To make RSA secure it is required to use a secure padding scheme. If PKCS#1 v1.5 padding is used then there is a significant (11 byte) overhead for each block of plaintext. The padding consists of at least eight bytes of positive random values which explains why the ciphertext is always different even if the same plaintext block is encrypted. If you would use RSA in ECB mode then you would end up losing the padding overhead for each block. That means that the ciphertext would be significantly larger than the plaintext.
Furthermore, RSA operations require a lot of CPU resources. The RSA encryption/decryption operations are based on modular exponentiation with extremely large numbers. Using RSA operations on many blocks will therefore use a lot of CPU time. This is especially true for decryption; encryption has the advantage that the public exponent is generally relatively small. But even RSA encryption will be a lot more CPU-expensive than any symmetric cipher.
To encrypt larger messages you should be using a hybrid cryptosystem where asymmetric (RSA) encryption is paired with a fast, efficient symmetric cipher such as AES. In your case where you encrypt a large amount of numbers it is better to aggregate them in a structure, encrypt the structure using AES and then encrypt the AES key using your RSA public key.

Notes:

OAEP is more secure than PKCS#1 padding. If you choose OAEP then the padding overhead is even larger, making ECB even less efficient;
It is also possible to use RSA-KEM or any other technique to establish the symmetric key - those techniques are however not present in the Java JCA library as of now;
For block ciphers ECB performs the block cipher operation for each block in the plaintext. This is not secure in most situations, independent of the padding used. It is however useful as a lower level operation such as key wrapping of a symmetric key;
Instead of designing your own protocol you could be using container formats such as the Cryptographic Message Syntax (CMS) or Pretty Good Privacy (PGP); both formats already implement a hybrid cryptosystem;
Increasing the key size only to support larger messages is generally not recommended: it would require a huge increase of CPU time during encryption and decryption, only dwarfed by the time it takes to generate the larger RSA key pair;
You may want to sign the message before encryption for additional security (sometimes it makes more sense to sign afterwards, it depends on the use case);
Using all possible bytes for PKCS#1 v1.5 padding comes with a downside: the random padding is only ~64 bits so there is a possibility of a collision with an earlier padding due to the birthday bound - it is better to use an overhead of 19 bytes instead of 11 bytes and have ~128 bits of padding.


Are libhydrogen's Gimli permutations production ready? I've recently had a situation in which a recommendation for an easy-to-use, hard-to-misuse cryptographic library for Java was required. The first choice was Google's Tink, since it was designed specifically for that purpose. Given it's association with Google, the customer was not too thrilled and asked for alternatives.
libhydrogen came to mind, which had a Java wrapper called Hydride, and was also designed to be easy-to-use and hard-to-misuse. However, libhydrogen only supports NORX v3.0 AEAD as the algorithm for secret-key encryption, which is based on Gimli permutations. Hashes and HMACs offered by libhydrogen are based on Gimli hash functions as well.
I have to admit, I've never heard of Gimli permutations, and I am not nearly skilled enough in cryptography to perform cryptoanalysis myself. As such, I hesitate to fully recommend libhydrogen as alternative to Tink. Can libhydrogen and its Gimli permutations be considered production-ready?

If you consider a feature being enabled by default as meaning the feature is production ready, then yes Gimli is production ready. However, it's still fairly new and hydrogen allows you to switch a compile time flag to use NORX/Keccak-p at the cost of being slightly slow.


How much entropy is lost if 1 character is fixed in HMAC SHA-512? We have an entropy source called “Entropy”. We encode this entropy with HMAC-SHA512 using a “Key”. The Key is public, but the Entropy is secret. We are then testing for the HMAC-SHA512 output in order to start with 1.

So, how much entropy is lost in the process, by encoding the secret Entropy with a public Key, and making sure that the output starts with 1?

For example:

Entropy     = random 132 bit integer
Public Key  = Test
HMAC-SHA512 = 1f042a41f2a940c38e64146823abd7926acb9d26cf02ee50f637dd5fb37c60c4d582603abe789138fa51a0496a6840b6e03e9b38d886e6bc6fd337f284a1052f

In our case we would search for a random integer until the HMAC-SHA512 output of it encoded with Test will start with 1 like 1f042a41f…

So in our case the final "not so random number" is:

467315884026680443925332907127019473008

How much entropy is lost in this process?

I'll assume the hash function is "good", i.e., equidistributed and partial-preimage-resistant.

If the input length $n$ is fixed and you fix $k$ bits of the output hash, you're losing roughly $k$ bits of information-theoretical entropy. This is easy to see: Without constraining the output, the entropy is $n$ bits, but forcing the value of $k$ bits means throwing away (on average) all but one out of $2^k$ of those preimages, therefore the resulting value is really sampled from (roughly) $2^{n-k}$ inputs rather than $2^n$.

However, computationally, this doesn't matter: Unless the hash function is severely broken, an attacker trying to recover your secret cannot "carve out" the subset of inputs whose hash values satisfy a specific constraint. (Note: If this were possible, they could just do it for any instance, not just one where you brute-forced those bits!)
Thus, the computational search space for an attacker is still $2^n$ instead of $2^{n-k}$, since they have to use basically the same method as you did.

These considerations are related to the conjecture that Bitcoin works and an indication that vanity keys such as Facebook's Tor Hidden Service address facebookcorewwwi.onion are not insecure even though their private key contains (information-theoretically) less entropy than other keys.


Sha-512 understanding padding problem I don't understand how to append the length of 128 bits exactly? First, we pad bits to make the length ($n*1024-128$) but then I need to append 128 bit of the plain text length. I find the problem to append 128 bits.

NIST FIPS 180-4 on page 13 defines the padding scheme for SHA-512 as;

  Suppose that the length of the message, $M$, is $\ell$
  bits.  Append the bit 1 to the end of the message, followed by $k$ zero bits, where $k$ is the smallest, non-negative solution to the equation
  $$\ell + 1 + k \equiv  896 \bmod 1024$$

So you first append 1, then calculate the number of the zeroes by the formula, append the zeroes, then append the 128-bit binary-encoded length.

For example: If your message size is $\ell =49$ than

$$49 + 1 + k \equiv  896 \bmod 1024$$ solving for minimal $k = 896-49-1 = 846$. Therefore the padded message is

$$ \text{padded message } = \overbrace{M}^{49-bit} \mathbin\| \overbrace{1}^{1-bit} \mathbin\| \overbrace{000\cdots 000}^{846-bit\; 0s} \mathbin\| \overbrace{00000000\cdots00110001}^{128-\text{bit binary encoded length } \ell} $$

Like all uniquely removable padding schemes this padding scheme also uniquely removable, usually called unpad. Get the last 128-bit, then remove all trailing zeros and the first 1 from the end. The rest will be the message and check the message size to ensure that it matches.

The length encoding in the NIST standard sets an upper limit for the size of the message to be hashed. One can hash at most $2^{128}$-bit-sized input messages. Before the upper limit, one has limited by the current technology.

SHA512, like all Merkle–Damgård constructions SHA512 has also vulnerable to length extension attack. Instead of SHA512 using SHA3 or Blake2 series are preferable. After SHA3, the stripped versions SHA512-384 and SHA512-256 are designed to have resistance to length extension attack. They have also different initial values that provide the domain separation from SHA512.


Security equivalent to Diffie–Hellman problem? I've been doing the security proof for one of my Theorem. Basically, given
$g^a$, $g^b$, $g^{cb}$, $g$ and $c$ as known values. Is the problem of computing $g^{acb^{-1}}$ equivalent to the Diffie Hellman-problem? In other words, is this easy to compute that?

My feeling is that its similar to the harder problem of the original Diffie-Hellman, which is given $g^a$, $g^b$, $g^c$ and to compute $g^{abc}$. But I couldn't come up with a reasonable proof. Could you please help?

Thanks,

It is equivalent to the computational Diffie-Hellman problem; if you can one of the two problems, you can solve the other (with a polynomial number of queries to the oracle which solves the other).

If you can solve the Diffie-Hellman problem, you can solve your problem: this can be seen by first noting that, with a Diffie-Hellman solver, given $g^b$, you can compute $g^{b^{-1}}$; this is done by computing $g^{b^k}$ (which can be done with $O(\log k)$ queries to the DH oracle) with $k=q-1$ (where $q$ is the order of the group).  Once you have that, you can do another query with $g^{b^{-1}}$ and $g^a$ to obtain $g^{ab^{-1}}$, and once you have that, you can then compute $g^{acb^{-1}}$ directly (as you know the value of $c$).

If you can solve your problem, then you can solve the computational Diffie-Hellman problem with two queries; given $g^a$ and $g^b$, you can first do a query with $g^1$, $g^b$ and $c=1$ (to compute $g^{b^{-1}}$), and then with $g^a$ and $g^{b^{-1}}$ and $c=1$ to compute $g^{ab}$


Is there a metric (term) for work required to decrypt a public key? Any public key decryption can be decrypted given enough time and computing power. Is there a metric or term for this? Something like

it would require on average 2^43 1024 bit hashes to find private key 'I' based on public key 'U'?

Is there a term that would sum up this average amount of work?

There are multiple metrics for work or effort needed:

Amount of operations it takes (one operations is, for instance, one invocation of hash function or number of modular multiplication operations)
Amount of money it takes
Amount of memory it takes
Amount of time it takes
Strength in bits

Amount of operations

Usually, if amount of operations is large enough so that it cannot be done with all the energy in the solar system even if single operation consumed just one electron, it looks safe enough.

Brute forcing AES-256 bit key is too expensive in amount of operations

Amount of money

If it costs too much to build device for breaking encryption, people assume it cannot be done, or that it is prohibitingly expensive.

Excellent paper of PBKDF algorithms, including cost of breaking a key in a year.

Amount of memory

Sometimes it would be feasible for large organizations to break algorithm according to how long it takes to break it (in number of operations), but it may be that breaking the algorithm takes so much temporary space that it cannot be done, because that temporary space is no where to be found.

Question on duration for attacking Two-Key Triple-DES using all RAM ever built.

Amount of time

Various parties like Prof Arjen Lenstra make estimates how long various kinds of keys take to break, based on the best attacks currently known. These are equations based on algorithm and key length.

These estimates can be found on www.keylength.com, along side other estimates.

Strength in bits

Some parties like NIST estimate algorithm strength in bits. This is: amount of bits symmetric encryption algorithm of equivalent strength against attempt to break would have.

These estimates are based on previous, especially number of operations required.

NIST SP 800-57 Part1: Recommendation for Key Management – Part 1: General contains necessary information to convert various algorithms to bits of strength to make it easier to compare algorithms in apples-to-apples manner.

How strong algorithms we should use then?

Algorithms with strength around 56-64 bits have been typically broken. (Like RSA 768. => Don't use.)
Algorithms with strength around 80 bits typically have not been broken, but are "on edge" and therefore their use is no more recommended. (Like RSA 1024. => Avoid.).
Algorithms with strength 112 bits (like RSA 2048) or more are considered to be safe (according to NIST), until beyond 2030, as long as they are used properly (single key has life time of about 1-2 years etc.)

More exact estimate on cracking RSA can be found here: How to estimate the time needed to crack RSA encryption?. The amount of time to crack other public key crypto will be different. However, if you use key sizes which are currently recommended, as far as public knowledge on cryptography goes, work required is infeasible.


Can it ever be impossible to invert a PRNG? I've read about the possibility of inverting the Mersenne Twister after 624 numbers of output.  624 matches the state size of my implementation of the Twister.  Coincidence?  If the generator only output 623 numbers, i.e. less than the state size, might inversion still be possible with really clever maths?  Or is this mathematically and logically impossible?

This leads me to think about a general case.  I got this embryonic analogy from solving simultaneous equations.  Consider each member within the state array as a degree of freedom.  And consider each number output as a degree of freedom.  And if (for some generator) there is a group operation over the whole state such as an addition of all of the elements, this acts as a constraint. Can the following be true?

Let,

$F_o$ = degrees of freedom output,
$F_s$ = degrees of freedom within state,
$C_n$ = number of constraints on the state.

Is the random number generator “impossible to uniquely invert” if $F_o < F_s - C_n$?

I've read about the possibility of inverting the Mersenne Twister after 624 numbers of output. 624 matches the state size of my implementation of the Twister. Coincidence? If the generator only output 623 numbers, i.e. less than the state size, might inversion still be possible with really clever maths? Or is this mathematically and logically impossible?

No, it's not a coincidence. The period is related to the state size, and a smaller sample cannot allow unique inversion due to the fact that every shorter number sequence appears in the total output of MT (with equal frequency to boot).

In general the same does not have to be true. A PRNG can use its state "wastefully" in such a manner that not every state is possible and inversion can happen much earlier than state size. Or it can have correlations that break it even without inversion. Contrarily, an actual cryptographically secure PRNG is expected to produce much more output than the state size without ever being invertible.

So I doubt your equation holds without additional assumptions.


Diffie-Hellman: *assumed* largest prime factor of order of $g$? I've read in several places:

some of my confusions about DDH assumption - comment by Thomas Pornin on his own post
Is there a key length definition for DH or DHE? - the answer by Tom Leek

that somehow the largest prime factor $q$ of $|g|$ (order of $g$) is assumed to be large enough without actually knowing $q$. How do they do that?

The only method I'm aware of is to start with a large enough prime $q$ and search for prime $p=nq+1$, then compute $g=a^{(p-1)/q}\pmod{p}$ for some random $a$. So the order of $g$ is $q$ if $g\neq 1$.

I've read in several places that somehow the largest prime factor $q$ of $|g|$ (order of $g$) is assumed to be large enough without actually knowing $q$. How do they do that?

Actually, both references talk about the behavior of the TLS client when negotiating a DHE-based ciphersuite.  The server proposes $p$ and $g$ as a part of the exchange, and hence the client doesn't know $q$.  This doesn't mean that $q$ is unknown, only that the client must trust that the server generated the group properly (which isn't totally unreasonable, as the client needs to trust the server to do other things properly as well).  Now, it would have been reasonable for the server to include the value $q$ as well (so a paranoid client could check it); they didn't include that in the protocol.

  The only method I'm aware of is to start with a large enough prime $q$ and search for prime $p=nq+1$...

That is certainly one method which is used in practice.  An alternative method would be to search for a Sophie-Germaine prime, that is, two values $p$ and $q = (p-1)/2$ which are prime simultaneously; in this case, any quadratic residue (other than 1, of course) would work as a generator.  This takes a bit of more work than the method you listed; however if you're generating a group once, this is irrelevant.


Question about discrete logarithm problem DSA and ECDSA both are based on discrete logarithm problem (and elliptic curve based DLP)

And ECDSA protocols resembles DSA.

My question is,

Can every protocol based on DLP be changed (substituted) to a protocol that is based on ECDLP?

To convert every protocol based on DPL to ECDPL based protocol there is a limitation as EC uses generators from a very large prime(or binary) fields. For an instance consider ECDSA which is an EC analogy of DSA, in ECDSA there is a Generator G (used in calculating public key) is from a large prime subgroup of EC where as in DSA the private key (x) is just a random number such that  0 < x < q where q is N-bit prime number.


Would this be considered secure? Assume an algorithm that encrypts each letter in a string into a different one, using a key, but in such a way that if you were to change a single letter from the clean text, the encrypted text would look completely different.

Also assuming each letter doesn't get encrypted to the same letter.

Here is an example (not generated by an actual algorithm)

Clean:

  Foo Bar Foo Bar

Encrypted:

  GjhetvbawmgYerujkgry

And another example

  Foe Bar Foo Bar

Encrypted, looks completely different from changing just one letter (and maybe even has a different length):

  HjengaieyHgnAuYehkawTGn

Would that be considered a strong algorithm?

My thoughts:

Statistical analysis can't happen (right?) because there is no symmetry in the encryption (for example, the two "o"s in "Foo" turn into different letters).

So how would a cryptanalyst find the key from such an algorithm?

(To clarify, I'm not asking if an algorithm is powerful, just how a cryptanalyst would look at it, assuming he knows the algorithm (and knows the key length) and has the ciphertext)

As a previous commenter pointed out, you're describing the avalanche effect.  In a block cipher, every output bit should be dependent on every input bit.  Changing a single bit of the key or a block of plaintext should, on average, cause half of the bits in the ciphertext block to change.

A cipher that exhibits the avalanche effect is not necessarily secure.  It can still have statistical biases or be vulnerable to attacks such as differential or linear cryptanalysis.


Hypothetical DES weakness: dual encryption identical to single encryption with specific keys If there always existed a $k_3$ such that $\operatorname{DES}(k_2, \operatorname{DES}(k_1, M)) = \operatorname{DES}(k_3, M)$,  how would that affect the security of the DES block cipher?

I will take this to mean that it's possible to efficiently find a $k_3$ so that

$$E(k_2,E(k_1,M))=E(k_3,M)$$

which would mean the cipher $E$ has too much structure and given a keylength $n,$ a double encryption like above is as weak as a single encryption and brute force key search would take $O(2^n)$ encryptions at worst.

Mind you, a meet in the middle attack on double encryption for an arbitrary cipher $E$ can break it in time $O(2^n)$ and a few plaintext/ciphertext pairs $(M,C)$ if
memory of size $O(2^{(n+\log n)})$ is also available. First form a hash-sorted list of $$\{(k_2,E(k_1,M)):k_1 \in \{0,1\}^n\}$$ sorted on the second coordinate
and then keep computing $E^{-1}(k_2,C)$ as $k_2$ ranges over $\{0,1\}^n,$ and looking up to see if it is in the table.

If you find a hit, then try with another P/C pair to confirm the guess is not spurious. This is because the composite permutation may have fixed points.

Edit:. I didn't originally want to make this too abstract, but as pointed out in the comments, what you're asking is whether $E$ forms a group, which it most certainly does not when $E$ is DES.


Is $F'_k(x) = F_k(x) \oplus k$ a pseudo random function? Let $F_k$ be a pseudo random function.
Is $F'_k(x) = F_k(x) \oplus k$ necessarily a pseudo random function?

I think that it is a PRF, but I just can't find a reduction that works with it.

You won't be able to find a reduction since you need somehow to XOR $k$ with the output you would get from oracle queries to the PRF, and you can't do this. In fact, the answer is that this is not necessarily a PRF, meaning that I can build a (convoluted) PRF $F$ such that $F'$ is not a PRF.

Specifically, let $\tilde F$ be any PRF and define $F_k(x) = \tilde F_k(x)$ for every $x\neq \tilde F_k(0)\oplus k$, and define $F_k(x) = 0$ for $x = \tilde F_k(0)\oplus k$. I argue that if $\tilde F$ is a PRF then so is $F$. This is because the probability that the adversary $\cal A$ will be able to query $F$ on $\tilde F_k(0)\oplus k$ is negligible. Formally you can show this by constructing a distinguisher $D$ who has oracle access to either $\tilde F$ or a random $f$ and runs $\cal A$. Then, $D$ queries its oracle on $0$ and gets back a value (if it has $\tilde F$ then it will get back $z=\tilde F_k(0)$). Then, for every query $y$ that is made by $\cal A$, distinguisher $D$ computes $k' = y \oplus z$ and locally checks if this defines the function it has oracle access to. If it has $\tilde F$ and $\cal A$ makes this query, then $D$ will know it has $\tilde F$.

Now, given the above, observe that if we construct $F'$ from this $F$, then we can query $F'$ with $0$ and get back $y=\tilde F_k(0)\oplus k$. We can then query $F'$ again with $y$ and we will get back $F'_k(y) = F_k(\tilde F_k(0)\oplus k)) \oplus k = 0 \oplus k = k$, and so we have the key.


What would happen to AES if we replaced MixColumns with ShiftColumns? I have this as a question in an assignment and I guess I don't fully understand the steps.
I understand that if we omit MixColumns, then every byte of the ciphertext would not depend on every byte of the plaintext. But if we insert a new operation, ShiftColumns, which is like ShiftRows, but operates on columns, wouldn't this, combined with ShiftRows, provide a solution?

If MixColumns is omitted, the following happens:

The cipher essentially becomes a group of 8-bit block ciphers, that work only by subkey addition and s-box transformation. After every 3 rounds, the original bytes will shift back to their original locations, in the following pattern:

Original state
a b c d
e f g h
i j l k
m n o p

After round 1
a g i o
f k n d
l m c e
p b h j

After round 2
a n l h
k e b o
c p i f
j g d m

After round 3
a b c d
e f g h
i j k l
m n o p

With AES-128, 10 rounds would equal a single round shift, and with AES-256, 14 rounds would equal a double round shift. An optimized version of the cipher would exist where only the final byte repositioning occurs, and the subkeys themselves get the shifts during the key schedule.

The entire cipher can then be re-described as 16 8-bit block ciphers, all with different key schedules that do not use every bit of key material for each round, and a final position change. The 8-bit ciphers will not be secure. Only a maximum of 16 times the data should be required to attack it compared to an 8-bit cipher, which recovers the entire code page for that key.

Key recovery is substantially more likely with a chosen plaintext attack due to the way the key schedule is broken up across each 8-bit group than would be with a pure 8-bit cipher, and the fact that you have 16 of them to work with.


collisions on hash functions Why do we say that collision-resistance is a "harder" property than second pre-image for hash functions whereas if you have an attack on the second pre-image then you find a collision ?
Moreover, a collision has a good probability to be found in $O(\sqrt{N})$ where $N$ is the size of the hash function outputs, whereas second pre-image needs $O(N)$ ...

It's harder for the designer to make a hash function collision-resistant than second-preimage-resistant, because it's harder for the adversary to find a second preimage than to find a collision.


Elliptic curve parameter generation I am curious of the details of how one would go about generating elliptic curve parameters. (I know standardized parameters exist, but I'm trying to understand both how they were generated and the general case.)

Let's also assume we want to work in a prime-order subgroup of size $O(2^n)$.
For simplicity, let's work over a prime-order field $F_p$.

As I understand it, the basic idea is
(1) generate a random elliptic curve $E$ over $F_p$;
(2) use a point-counting algorithm to count the number of points $N = |E(F_p)|$; finally,
(3) check that $N$ is divisible by an $n$-bit prime

I am confused about the 3rd step: how is it implemented efficiently without using a general-purpose factoring algorithm? Also, how many iterations are required (in expectation) before finding a curve $E$ whose order $N$ is divisible by an $n$-bit prime? Finally, given $n$, how should we best choose $p$? (This is related to the question of what co-factor one should be looking for.)

First of all, for elliptic curves based on a prime field $F_p$, we always work with a prime $p$ that is the same size as our target subgroup.

The reason is quite simple: we could work in a proper subgroup based on a larger curve, but what would that buy us?  It becomes more costly (as all our internal computations are modulo $p$, and if $p$ is larger, those operations are more expensive), and it doesn't make it any more secure; the best attack still involves $O(2^{n/2})$ operations.

A side effect of this decision is to make step 3 quite simple.

$N$ will always be in the "Hasse interval"; $p - 2 \sqrt{p} + 1 \le N \le p + 2 \sqrt{p} + 1$, or in other words $N \approx p$. Since $p$ is an n-bit number, that means that if $N$ were to have an n-bit factor, well, $N$ would have to be that n-bit factor (there is a possibility is that $p = 2^{n} - \epsilon$, where $\epsilon < 2 \sqrt{p}$; in that case $N \ge 2^n$ is possible; I'll ignore that corner case)

So, step 3 is effectively "test $N$ for primality"; that can be implemented quite efficiently.

As for your other questions:

The number of curves you'd expect to go through: if the probability of a curve order being prime is approximately the probability of a random number in the Hasse interval being prime, then we'd have an expected $\log{p}$ iterations.  However, I'm not certain about true that assumption is; I expect it is close.
What size of $p$ do we want?  As above, we pick a cofactor of 1, with $p$ being an $n$-bit prime; again, we could use a larger prime, but there doesn't appear to be any benefit from doing so.


Security of (cryptographic) padding compared to other methods for blockcompletion for block ciphers As said in the heading, I want to know how the security of different padding methods, e.g. ANSI X.923, ISO 10126 and PKCS7, is compared to other methods to reach the needed block size, like ciphertext stealing or residual block termination. And what is about the counter mode of operation?

I heard that oracle attacks are possible if padding was applied, but have the other methods also disadvantages (except a higher complexity)? Or are there any possible ways for the problem that I forgot, that are more recommended?

The security of these schemes is all comparable, as far as I am aware.  In all cases, you need to use authentication (e.g., Encrypt-then-MAC).  Padding attacks are just one way that security can fail if you omit the authentication, but all of these schemes will have serious security problems if you omit the authentication.  So, don't forget the authentication.

Bottom line: I don't know of any compelling security reason to choose one of these methods over any other, assuming that you are using the crypto correctly.  You can choose on other grounds, e.g., interoperability, performance, ease of implementation, etc.


Why do crypto tools display key components in such an unusual format? openssl x509 (v1.0.1f) displays public key moduli as arrays of hex-encoded bytes, 15 columns wide, starting with a leading 00::

    Subject Public Key Info:
        Public Key Algorithm: rsaEncryption
            Public-Key: (1024 bit)
            Modulus:
                00:b0:d0:f4:33:a8:b2:93:06:65:27:72:94:57:92:
                bd:c7:ca:d4:08:e7:06:b9:4e:5e:d4:4a:ff:cc:f3:
                4f:4a:fc:92:75:46:4f:ce:fc:18:4a:d1:30:f2:64:
                31:94:4d:13:0d:91:ef:a4:34:59:71:b4:a1:cd:4e:
                fe:8f:e4:57:71:55:6a:d5:47:db:12:db:aa:df:20:
                6a:36:d1:5d:8c:68:db:ef:63:87:56:df:79:71:50:
                69:8d:b8:67:32:e7:51:17:26:21:fd:20:c7:1d:d2:
                dc:78:d7:fe:98:42:d0:24:8c:6a:df:12:cd:da:a9:
                81:fb:60:8b:ba:c9:12:d3:a9
            Exponent: 65537 (0x10001)

GnuTLS's certtool -i shows the bytes in an array of 16 columns, which seems less surprising, but again starting with a leading 00::

Subject Public Key Algorithm: RSA
Certificate Security Level: Weak
    Modulus (bits 1024):
        00:b0:d0:f4:33:a8:b2:93:06:65:27:72:94:57:92:bd
        c7:ca:d4:08:e7:06:b9:4e:5e:d4:4a:ff:cc:f3:4f:4a
        fc:92:75:46:4f:ce:fc:18:4a:d1:30:f2:64:31:94:4d
        13:0d:91:ef:a4:34:59:71:b4:a1:cd:4e:fe:8f:e4:57
        71:55:6a:d5:47:db:12:db:aa:df:20:6a:36:d1:5d:8c
        68:db:ef:63:87:56:df:79:71:50:69:8d:b8:67:32:e7
        51:17:26:21:fd:20:c7:1d:d2:dc:78:d7:fe:98:42:d0
        24:8c:6a:df:12:cd:da:a9:81:fb:60:8b:ba:c9:12:d3
        a9
    Exponent (bits 24):
        01:00:01

When it comes to private keys, however, both openssl rsa and certtool -i -k show all the private key components in arrays of bytes 15 columns wide. They both show leading 00: for some components of the private keys but not others.

This display format seems unusual because the quantities in question are generally sized in powers of 2 (e.g. 1024 bits == 2^10), but the binary data is shown in rows of 15 columns. The leading zeros are surprising as well.

So… is there a good reason for this unusual display format?

As for the leading zero, I believe the tools are just displaying what's in the ASN.1 as is; the BER/DER encoding rules will insist on a leading 00 byte in some cases.

Specifically, if you encode a positive integer, the msbit of the value stored must be 0 (if it is a 1, the encoded value is assumed to be negative); if the msbyte of the value you want to store has a 1 msbit, then you must prefix a 00 byte byte to the stored value; this 00 byte does not change the value (obviously), but it does make the msbit 0.  In both case you have, the most significant nonzero byte has an msbit of 1; hence, they have a 00 prefix.

Now, you state that other components within the private key do not have a 00 prefix; I expect that, if you examine them, the first byte of those values will be somewhere in the 01-7f range, and so don't need a 00 prefix.


Given an elliptic curve, how do I calculate the order of the points manually, when we don't know about the curve's points? So basically all I can do is

use Lagrange's Theorem and figure which factors of the group order are in line, then
start trying each of these using the Double-and-Add-Algorithm until I get $\mathcal{O}$?

This takes forever if I do it by hand. Is there any easier way to find the order of all points? or find all the points on the curve?

Okay after some research: There is no shortcut. If you do it manually you need to proceed as suggested above. Realistically this is possible only for very small curves because of the complexity.


Authentication and encryption using a simplex communication channel Is it possible to authenticate a client with encryption on a simplex communication channel without the use of authoritative root certs?

Sure. For instance:

Use PKI, register client public key (or self signed certificate) on the server and consider any registered public keys as trusted. You should understand also all drawbacks that it has, like dealing with validity period (how are you going to check if some PKs are still valid / trusted or not and should you remove them from your server PK store or not?), dealing with compromized private keys (instead of revocation list of CA), etc.
Use shared secret. Again, be prepared to the drawbacks. For instance, in such case not only the user, but also you on the server side will be responsible for keeping user authentication material safe.
One time passwords.


Probabilistic verification of signature schemes like RSA? I was wondering if there were any verification algorithm in the literature that enables a "probabilistic" verification of well-known signature schemes?

For RSA signature verification for example, is there any way to verify $s^e = H(m) \mod N$ in a fast way but with a certain "error" probability ?

If not for RSA, for any other schemes ?

Every signature scheme has some nonzero forgery probability: if there are $n$ distinct possible signatures, this forgery probability is always at least $1/n$, because a forger could just try signatures uniformly at random.  But sometimes $n$ is so large that $1/n$ is smaller than it needs to be for confidence, say $1/2^{2048}$ when all you really need is $1/2^{100}$, and we can exploit this to trade off forgery probability for performance.  Here's an example of how, with RSA.

Suppose a signature is not an integer $s$ such that $s^e \equiv H(m) \pmod N$, but rather a pair of integers $(s, k)$ with $s < N$ and $k < N^{e - 1}$ such that $$s^e = H(m) + kN.$$  Then the verifier can verify this equation modulo a secret uniform random $v$-bit prime $r$, $$s^e \equiv H(m) + kN \pmod r.$$  There are $\pi(2^v) - \pi(2^{v-1})$ such primes, and $s^e - h - kN$ has at most $\lceil(\log_2 N^e)/v\rceil$ $v$-bit prime factors, so the probability that $r \mid s^e - h - kN$ is at most $$\frac{\lceil(\log_2 N^e)/v\rceil}{\pi(2^v) - \pi(2^{v-1})}$$ for any fixed $(s, k)$, $h$, and $N$ unless $s^e = h + kN$.  Of course, while the forger can try about $t$ messages to find one whose hash $h$ has a desired property occurring with probability $1/t$, only about $1/2^{2048}$ of them satisfy $s^e = h + kN$ if $N \approx 2^{2048}$, so the forger has no hope of finding those.

For $v = 128$, we have $$\pi(2^v) - \pi(2^{v - 1}) \approx \frac{2^{128}}{\log 2^{128}} - \frac{2^{127}}{\log 2^{127}} \approx 2^{120},$$ and for $e = 3$ and $N \approx 2^{2048}$, we have $\lceil(\log_2 N^e)/v\rceil = 48$, so the forgery probability is at most about $1/2^{114}$.

Obviously, the verifier can choose independent primes $r_1, r_2, r_3, \dots$ to lower the forgery probability further; the verifier can also reuse the primes for multiple verifications to save effort, as long as they remain secret.

This scheme is not particularly attractive unless $e$ is very small: even for $e = 3$, it triples the size of the signature.  It is most attractive for Rabin-type signatures with $e = 2$, which are, of course, qualitatively different from RSA-type signatures (and largely better all around except in being deployed anywhere!).

To my knowledge, this idea was first published by Bernstein in 1997, and is mentioned in his summary paper on modular root signature schemes discussing many variations on the themes of RSA and Rabin–Williams signatures.


AES MixColumns what do I xor with I'm trying to understand the MixColumns operation in AES but I have a question that I just can't figure out (it's probably something very simple but I can't find the answer).

The textbook explains that if you want to do a multiplication by 2 that can be implemented as a 1-bit left shift followed by an XOR.

How do I know what I XOR with?

Thanks!

It's 0x11B. Basically, you shift left by 1 bit, and if the upper bit is 1 (and only in that case), you XOR the value with 0x11B. In C terms, it will look like this:

static inline unsigned
mul2(unsigned x)
{
    x <<= 1;
    if (x & 0x100) {
        x ^= 0x11B;
    }
    return x;
}

Now this can be done without a conditional (which, on some architectures, will result into a conditional jump) with some trickeries like this:

static inline unsigned
mul2(unsigned x)
{
    x <<= 1;
    x ^= (-(x >> 8)) & 0x11B;
    return x;
}

This relies on the fact that -1, cast into an unsigned type, yields an all-ones pattern.

It really pays off, in these matters, to take the time to understand what is going on at an algebraic level. What really happens here is that we work in the finite field $GF(256)$. A value is a polynomial of degree at most 8 with coefficients in $GF(2)$. For instance, 0xB2 (in binary 10110010) really represents:

$$ v = X^7 + X^5 + X^4 + X $$

The coefficients are always 0 or 1. Addition is done for each coefficient independently, and in $GF(2)$, so $1 + 1 = 0$. In practice, this means that addition of two elements in $GF(256)$ really is bitwise XOR.

For multiplication, this is again done with polynomials, and a modular reduction, using a specific degree-8 polynomial, which happens (in the case of AES) to be:

$$ P = X^8 + X^4 + X^3 + X + 1 $$

which corresponds to 0x11B (100011011 in binary). This is defined in section 4.2 of FIPS-197. Thus, multiplication by 2 (0x02, i.e. 00000010 in binary) really is multiplication by the polynomial $X$, followed by reduction modulo $P$. If we take our value $v$ above (0xB2), then multiplication by $X$ "bumps up" the monomials:

$$ v\times X = (X^7 + X^5 + X^4 + X)X = X^8 + X^6 + X^5 + X^2 $$

In the binary representation, this is a left-shift by 1. However, the result must be reduced modulo polynomial $P$. In this specific case, $v\times X$ is a degree-8 polynomial, which is one too many (since $P$ has degree 8, all polynomials modulo $P$ must have degree 7 or less). Modular reduction really is subtracting a multiple of $P$ such that the result will have degree 7 or less (note that subtraction and addition are the same thing: a bitwise XOR). In this case, it suffices to subtract $P$ once:

$$ \begin{eqnarray*}
v\times X \pmod P &=& (X^8 + X^6 + X^5 + X^2) + (X^8 + X^4 + X^3 + X + 1) \\
 &=& X^6 + X^5 + X^4 + X^3 + X^2 + X + 1
\end{eqnarray*} $$

so the result will be 01111111 in binary, 0x7F in hexadecimal. You can check that, indeed, left-shifting 0xB2 by 1 yields 0x164, and XORing that with 0x11B results in 0x07F.

Multiplication by 3 in $GF(256)$ is polynomial multiplication by $X + 1$, followed by modular reduction. To implement that easily, reuse the multiplication by 2:

static inline unsigned
mul3(unsigned x)
{
    return mul2(x) ^ x;
}

because for a polynomial $Q$, you have $(X + 1)Q = XQ + Q$, so really it is "multiply by $X$ (i.e. "2") then add (XOR) the operand one more time".

Similarly, multiplication by 9 will be:

static inline unsigned
mul9(unsigned x)
{
    return x ^ mul2(mul2(mul2(x)));
}

because "9" is really $X^3 + 1$ so that is "multiply by $X$ three times, and add once more the operand".

This whole polynomial business, and in particular the "addition is XOR", takes some effort wrapping your mind around it; but once you get it, the rest is "easy".


What is the role played by cache misses in memory-hard password hashing? I experiment with argon2 and build a web application. In browser, I use one threaded hashing with not too much memory. I want to protect my short length input data from parallel brute-force attack.

I understand, using large memory (1GB or greater) prevent parallelism, because of the cost. I would like to support mobile and older browsers, so I use 16MB or 32MB memory maximum.

I thought argon2 indexing function generate large amount of cache miss, while randomly access the shared memory and a cores waiting a lot. Consequently parallelism increase the cache miss count and slowing down the hashing. I was benchmarked in parallel, but it is not affected, parallelism worked.

Is it because my benchmarks wrong or is not generate a lot cache misses I thought or cache misses not affects like the processing?

Cache misses wrong for memory-hardness, because the waiting cores might compute a missing memory faster then the waiting time, aka time-memory tradeoff?

edit1
What is the relationship between used memory and memory bandwidth and speed?

I understand, using large memory (1GB or greater) prevent parallelism, because of the cost. I would like to support mobile and older browsers, so I use 16MB or 32MB memory maximum.

This is true, but 32mb memory is fairly safely OK for most applications.

  Is it because my benchmarks wrong or is not generate a lot cache misses I thought or cache misses not affects like the processing?

Problem of password cracking isn't mere 16 threads that a CPU can pull off. CPU is fairly complex thing and even if it can't cache whatever you throw at it, it has multiple channels of high-speed ram with capacities reaching into terabytes for powerful servers.

Problem starts when everyone has thousands of processors in their computer. This is case right now with GPUs. GPUs make use of massive parallelism. This makes some tradeoffs, for example every thread has tiny amount of memory and no cache. Common GPU programming technique require that data to be accessed next is fetched earlier and saved in that reduced space. This obviously can't happen with 32mb table, which is further limited by huge performance cost of accessing global GPU memory (and you have thousands on threads all accessing some random informations). And you don't even have enough memory in GPU to run 1000 threads at once.

Argon also tries to combat all kind of premade chips to break it quickly by using a lot of memory quickly: your can't just invest into a lot of quickly-hashing chips because they will need megabytes or more per one chip.

So if you were running your benchmarks with CPUs this is expected that it will run this algorithm fairly well. After all argon2 was made so that it runs efficiently on multiprocessor CPU, but not on GPU or ASIC.


Supersingular Isogeny Key Exchange Software Are there any optimised implementations of the Supersingular Isogeny Key Exchange by Defeo, Jao, and Plut.  It seems like this would be a great drop-in replacement for Diffie-Hellman in both OpenSSL and GPG.  I'm wondering if that code is available or if someone is working on it.

The inventors of the Supersingular Isogeny Key Exchange, Defeo, Jao and Plut have posted some code on GITHUB at:

https://github.com/defeo/ss-isogeny-software/

There is also a paper on implementation of this key exchange by some people from the University of Waterloo.  Their paper is "Efficient Implementations of A Quantum-Resistant Key-Exchange Protocol on Embedded systems" and can be found:

http://cacr.uwaterloo.ca/techreports/2014/cacr2014-20.pdf

I would also like to note that while Lattice Based Cryptography (as suggested by the other answer) is more efficient than the Isogeny based key exchange it has not received significantly more analysis than the Isogeny based scheme.  In particular the work of Galbraith and Delfs from 2013 is an independent assessment of the difficulty of solving the underlying hard problem in the case of the Isogeny problem.

Many of the lattice schemes are designed and analyzed by the same small group of researchers who base their research on each others previous research.  Of course research on the Isogeny key exchange is not immune from that.  A more recent paper by Biasse and Jao on the difficulty of finding isogenies includes one of the inventors (Jao) as an author.  Nevertheless, the Isogeny key exchange builds on almost two decades of intense research on elliptic curves.  Until recently the only lattice based scheme under active scrutiny was NTRU and there the findings were historically problematic.  Of course if efficiency is what you need, the lattice based schemes are indeed superior to the Isogeny based key exchange.  I hope this helps.

You might want to write to Fishein, Jao, and Azarderakhsh to see if they posted their software anywhere.  They claim to have software that is significantly more officient that the original code.


Is a one-time pad secure if the encryption method is not? (The following situation is hypothetical.)

I need to communicate something securely and I have decided to use one-time pads.

I am going to be using human genes as the source of the OTP data (this is important).

If I were to use (for example) a weak kind of encryption, in this case a variation of XOR 'encryption', would the fact I am using OTPs offset the weakness of XOR 'encryption' or would it be a complete waste of time because XOR is still inherantly weak?

If it matters, before being XOR 'encrypted' the messages will be plaintext in an unspecified human language (English, Japanese et cetera - the language is irrelevant other than being a known, well spoken human language).

Disclaimer:
I won't be offended if I'm told that this is a horrible idea - It's not my idea.

OTP requires a completely random key. That's next to impossible, and human genes are certainly not completely random. This is why OTP's are mainly theoretical constructs.

XOR is the normal way of encrypting using an OTP. XOR is not weak encryption if the key stream is strong. And if the key stream is perfectly secure then XOR encryption is completely secure (for confidentiality anyway).

And no, the messages do not matter. A secure cipher should be secure against known plaintext attacks. That is, different messages or other parts of the message should remain confidential even if part of the message is known.

It's good that you're not offended, because it certainly is a horrible idea.


RSA signature attack check on lowest 16 bytes - Implementation I am referring to solution given in this question

I need help to implement Poncho hint in this comment:

As the first question i have an RSA signature of 1024 bit applied on an hash (MD5) of the message.

I am trying to get a valid result coding it in Java but i don't get any result from my iterations.

Can someone help me to find out why i don't get results as mentioned by @Poncho?

Example of hash: 0xCC844F9AF903BCB3CB0A7F0433AF70D3
Decimal representation: 271849508914011436342484527734062018771

Thanks a lot.

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

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

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

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


Statistics on the frequency of usage of RSA key public exponents Are there any publicly available stats regarding how often are specific public exponents used for RSA keys?

Presumably, 65537 is the most commonly used of them, but I'd like to get some notion of which other values one should care about when testing for compatibility.

I couldn't find any references to any statistics, however:

All Fermat primes $${3, 5, 17, 257, 65537, 4294967297, 18446744073709551617, … }$$ could be used while regarding the use a proper padding scheme. There is no known weakness for any short or long public exponent for RSA, as long as the public exponent is "correct" (i.e. relatively prime to p-1 for all primes p which divide the modulus).

So why is $ e = 65537$ used most commonly?

Using $e=65537$ (or higher) in RSA is an extra precaution against a variety of attacks that are possible when bad message padding is used. But it's not too large so that it would greatly impact performance speed ($e = 3$ is around 8x faster than $e = 65537$).

So in short: $e = 65537$ is most commonly used as a comprimise, because it's reasonably fast and secure.

Related answers for more details:

Impacts of not using RSA exponent of 65537, answer by fgrieu
Should RSA public exponent be only in {3, 5, 17, 257 or 65537} due to security considerations?, answer by Thomas Pornin