Can PBKDF2 be used to create an XOR cipher key to encrypt random plaintext? I want to encrypt a truly random plaintext (a key file) based on a user password. I'll use PBKDF2-HMAC-SHA256 to generate an encryption key from the password, but I'm wondering if I even need to bother with AES or some other cipher: can I expect good security if I just use PBKDF2 to generate a key equal in length to the plaintext, and XOR them together?

I would use an encryption method designed for the purpose, such as AES Key Wrap.

That said, PBKDF2 uses a PRF internally, so if you specify an iteration count of 1, your suggestion would effectively amount to using a PRF in CTR mode. Since you put the question that way, then, yes, it would be good enough, in the sense that the weakest link would probably be the password and not the encryption scheme.

Edit: Using the PBKDF derived key as a key stream, rather than as a key for a proper symmetric cipher, would obviously require you to treat the Salt value as a nonce (i.e. it has to be different each time you perform the encryption operation). This is not strictly necessary if you use AES in a secure mode of operation - in such case you would get away with leaving the Salt unchanged, but you would OTOH, depending on which mode of operation you use, might have to set the initial state of the mode of operation to a Nonce value. If you use AES Key Wrap, the initial state is a default constant, but for e.g. CTR mode it would be essential to set the initial counter to a nonce.


Understanding Pseudo Random Generators I've been taking a crypto course online. I have a good idea how PRG's and Stream Ciphers work, but I'd love to get some input to help visualize what is actually happening. I understand a seed is used, then expanded into a keyspace. Is this correct?

So: $G: \{0,1\}^s \to \{0,1\}^n , n \verb|>>| s$

From what I understand.. For a generator (function $G$) a random seed from all $s$ bit seedspace is mapped to an $n$ bit string.

I'm having trouble conceptualizing is the "mapping" of the random seed to the key (I might be totally incorrect with the way I'm phrasing this). Is this process laid out in the actual cipher (e.g., CSS, Salsa20) or there something else going on?

The way I picture it, a pseudorandom number generator (PRNG) has a box of bytes called "internal state".

Seeding the PRNG sets that box of bytes to some deterministic function of the seed.

Every time you ask the PRNG for another number,
the PRNG "stirs the pot" to some new state -- using a deterministic function of the previous state.
The PRNG also generates an output integer that is some function of one or more bytes in the box of internal state.

I'm not sure where you are getting the "n" in your question -- every PRNG I've ever encountered will continue to produce numbers indefinitely, no matter how many numbers it has already generated since you seeded the PRNG.

The size of the box, the specific deterministic functions used by some PRNG, etc. are generally spelled out in detail in the description of that PRNG.

You may be interested in CipherSaber, Salsa20, Fortuna, etc.


Understanding ransomware – What makes plain-text-attacks or brute-forcing so hard? Say I have four files. Two are completely unencrypted, while the other two are the exact same files other than that they have been encrypted with (apparently) the same public key (via a ransomware virus). Is it possible to deduce the key from these files, so I can apply it to other files also encrypted with the same key?

Edit

Sorry, after searching through the questions related to my tags, I see the simple answer is no, because although the public key is easily discovered, it's probably a private key I'm looking for, which would be hosted elsewhere.

But to modify the question:

Does the length of the public key imply the length of the private key, or can they be unrelated?
Also, wouldn't more plaintext information provide a brute-force program a starting point to speed the process?

I don't understand why, given that all the files would be decrypted using the same key, we can't deduce said key by comparing encrypted files to unencrypted ones.

Does the length of the public key imply the length of the private key, or can they be unrelated?

Yes.

The sizes of public and private keys depend on the cryptosystem. Usually they are related somehow, but not necessarily. For example, you can store a short value as a private key, which is then used as a PRNG seed to generate the private key used in the actual algorithms.

In RSA a private key file typically includes a lot more information than a public key - in addition to those modulus and public exponent that the public key contains, it includes the private exponent, as well as usually the original primes and some CRT values.

However, raw RSA keys only need to contain the modulus and the private or public exponent, so they can be the same size.

  Also, wouldn't more plaintext information provide a brute-force program a starting point to speed the process?

No, typically not. An encryption algorithm where this is true (at least for values smaller than other attacks) is considered broken. Because of the below.

  I don't understand why, given that all the files would be decrypted using the same key, we can't deduce said key by comparing encrypted files to unencrypted ones.

If you could do that, then the public key system would not be very useful would it? Anyone who has the public key can encrypt any number of files they want. Thus, they have any number of plaintext-ciphertext pairs they could want. If this made the algorithm weak, it would be completely useless (except maybe as a replacement for a symmetric, i.e. secret key algorithm).

You might find questions such as this helpful: Is there an intuitive explanation as to why only the private key can decrypt a message encrypted with the public key?


Why do we need to go through multiple cycles in block cipher According to Computer Networking: a top down approach, Chapter 8 (6th edition), block ciphers involves breaking the input message into blocks of size k, where generally k = 64. However since k = 64 implies that we need to create a table of input size 2k or 264 in our case, therefore we simulate randomly permuted tables. To simulate, we use the following process. The function first breaks a 64-bit block into 8 chunks, with each chunk consisting of 8 bits. Each 8-bit chunk is processed by an 8-bit to 8-bit table, which is of manageable size. For example, the first chunk is processed by the table denoted by T 1 . Next, the 8 output chunks are reassembled into a 64-bit block. The positions of the 64 bits in the block are then scrambled (permuted) to produce a 64-bit output. This output is fed back to the 64-bit input, where another cycle begins. After n such cycles, the function provides a 64-bit block of ciphertext.

Here is the question: Why do we need to process the text through n such cycles? The book states that

  The purpose of the rounds is to make each input bit affect most (if not all) of the final output bits. (If only one round were used, a given input bit would effect only 8 of the 64 output bits.)

The key for this block cipher algorithm would be the eight
permutation tables (assuming the scramble function is publicly known).

*Personal Comment -
However, if the input text has gone through even a single cycle still all the inputs would have been affected since each block went through a mapping based on the corresponding table Tj table. Hence we shouldn't be required to cycle it through n cycles.

First of all, I wouldn't rely on that book for information about modern cryptography.  It might be a fine reference for networking in general, however based on the example they gave, it would appear that they really don't know their crypto.  The example cipher they gave feels like something from the '90s.

Modern block ciphers use $k=128$; the issue with $k=32$ is that you tend to leak information about the plaintext after encrypting a few gigabytes with the same key; with modern networks, you can hit a few gigabytes easily.  In addition, key dependent sboxes have gone out of fashion; they are a bit expensive in hardware, they tend to leak timing data in software (due to caching), and the sboxes are sometimes not particularly strong against differential or linear cryptanalysis.

As for your question:

  Why do we need to process the text through n such cycles?

Consider the case where $n=1$, and you have two different plaintexts that differ in a single bit.  Then, if you look at the two parallel encryptions, the inputs for seven of the sboxes are precisely the same (because they only depend on inputs that have not changed), and so only one sbox (say, $T_0$) has its output changed.  That sbox has 8 output bits, and so when you go through the 64-bit scrambler, then you have 56 output bits that would always be the same, and 8 that are potentially changed.  This is far short of 'any input bit can potentially affect any output bit'.

There are more sophisticated things we can do for larger $n$; this simple reasoning shows that the $n=1$ case just doesn't cut it...


Determining average number of hash calls to get a hash that begins with X I have been attempting to find an answer to a self-study question:

  If I have a hash algorithm that outputs 256 binary bits, on average, how many times would I have to call the hash function so that the output begins with 15 zeros?

I am absolutely lost, but bear with me here - each bit has two possible values and assuming an uniformly random output, there are $2^{256}$ (or 1.1579209e+77) possible outputs from the hash function.

So approximately, how many calls to the hash function ($H$) would be required to get an ouput value that begins with those 15 zeros?  Note that I am not looking for the probability of finding such a value (although that could be useful to know as well).

Assuming the output is uniformly random, the probability of any given bit being 0 is $\frac{1}{2}$. So the probability that $b_0,b_1,b_2...b_{14} = 0$ is ${(\frac{1}{2}})^{15}$.

On average, it will require $2^{15}$ calls to find a hash where the first 15 bits are 0.


What is the functional role of CKY-I and CKY-R in ISAKMP (IKEv1)? According to RFC 2409:

  CKY-I and CKY-R are the Initiator's cookie and the Responder's cookie, respectively, from the ISAKMP header.

Each CKY is a 64 bit value that is included in each ISAKMP Header in the Phase1 and Phase2 negotiation, and future ISAKMP informational exchanges.  And they are also used in the math for key generation.

Also in the ISAKMP RFC, I see that the Cookies are used to Identify the ISAKMP Security Association (SA):

  Per the base ISAKMP document, the ISAKMP SA is identified by the Initiator's cookie followed by the Responder's cookie

(although I'm not sure what "base ISAKMP document" they are referring to)

Given all these describe what the CKY-I and CKY-R values are, I am curious to understand why they exist.  Effectively, what is the functional role they play?

If they solely exist to identify the SA, why not simply use an SPI value like IPsec does?  Or, why not simply pick a random arbitrary value to use and not include it in all the key material calculation?

Bonus question:  “How” are they created? I imagine they are random values, but I couldn't find any confirmation related to that in the RFCs.

What is the functional role they play?

They exist to identify the SA.  That is, when an IKE implementation receives an IKE packet, it is able to use the cookies to identify the SA that the packet corresponds to.

  Why not simply use an SPI value like IPsec does?

Why do you think there is some fundamental difference between the cookies that IKE uses, and the SPI that IPSec uses?  They are essentially the same; they are an arbitrary identifier that the allows the implementation to correlate incoming packets with SAs.  Now, there are some minor differences; most notably that an IKE packet contains the identifiers from both sides, while an IPSec packet only contains the identifier from the receiving side; however that difference doesn't change what those identifiers signify.

  how are they created?

Actually, the RFCs do not specify how the implementation selects its cookies, and for a good reason; that is something for the implementation to decide, and if the implementation can (for example) speed up the lookup by selecting nonrandom values, it is free to do so.

Now, there is a minor glitch for IKE cookies that do not reply to IPSec SPIs; since both the initiator and the responder cookies are in the IKE packet, then if both sides select nonrandom cookies (and use the same strategy), then there is a possibility for the implementation to get confused (as it won't know apriori which cookie is his, at least if the implementation can be both an initiator and a responder.  This possibility also exists if the cookies are selected randomly; however the cookies that sufficiently long that such a collision is, in practice, improbable.


If the PSK is known, is it possible to decrypt traffic from other clients in a WPA2 wlan network? If in a public WLAN WPA2-PSK is used, but the PSK is more or less publicly available, does this mean that an attacker with that PSK can easily decrypt wlan traffic from/to other clients of that WLAN?

Or does WPA2 negotiate sort of a per-client encryption key, so that while an intruder can access the WLAN, he's still not able to decrypt the other clients' traffic?

Curiously, the answer is »Yes« to both questions.

Each client (STA) establishes a different pairwise transient key (PTK) with the access point (AP) for each session, but this PTK is derived from the pairwise master key (PMK). And if you are using a pre-shared key (PSK, usually derived from a password entered by the users), this PSK is used as the PMK.

The derivation of the PTK uses a pair of nonce values sent by both STA and AP in clear text as the first two steps of a 4-way handshake, as well as their MAC addresses (which are public anyway) and the PMK (all hashed together with a hash function).

So, listening on those first two handshake messages and knowing the PSK allows an attacker to listen to any messages between AP and STA, as well as impersonate one or both to do a man-in-the-middle attack.

The standard IEEE 802.11-2007 contains a note about this (page 190, in the PDF on page 239):

  NOTE—When an ESS uses PSKs, STAs negotiate a pairwise cipher. However, any STA
  in the ESS can derive the pairwise keys of any other that uses the same PSK by
  capturing the first two messages of the 4-Way Handshake. This provides malicious
  insiders with the ability to eavesdrop as well as the ability to establish a
  man-in-the-middle attack.


In SRP, is the client protected from server impersonation? Assume use of SRP over an otherwise insecure unauthenticated channel where

the user running the client side has chosen a password,
the user only uses that password with a trusted SRP client software, and with the intention to login to the legitimate server (then communicate securely with that server using the SRP-negotiated session key),
there was no attack at enrollment time,
the server keeps the enrollment data confidential,
the password is good enough that odds are negligible that it could be guessed in a thousand attempts, and neither the server nor user would tolerate that many unsuccessful login attempts.

Does that protect the user from logging to another server?

Motivation: see that question.

So far, I have determined that such protection is not in SRP's advertised features:

  It solves the problem of authenticating clients to servers securely, in cases where the user of the client software must memorize a small secret (like a password) and carries no other secret information, and where the server carries a verifier for each user, which allows it to authenticate the client but which, if compromised, would not allow the attacker to impersonate the client. In addition, SRP exchanges a cryptographically-strong secret as a byproduct of successful authentication, which enables the two parties to communicate securely.

Yes (and it is an explicit goal of SRP; perhaps not as advertised as such)

The only attack that SRP allows is for the faux server to take a guess at the password, and then attempt to allow the client to login based on that guess (and if the client thinks he succeeds, the guess was correct).

Given that we assume that the password was strong enough to make that unlikely, you're safe.


Could a key derivation function be used to encrypt data with a weaker key? To allow the key to be more easily remembered.

Example:
To encrypt a hard drive without having a remember a key with 128 bits of entropy.

From what I find they seem mostly used to hash passwords so the password database is more resistant to brute force in the case it's compromised. (compared to using a regular hash function)

So I'm not sure that the use case that I mentioned would be safe.

Yes, with caveats.

Yes, because this is the entire stated point of password-based key derivation functions (e.g., PBKDF2 or scrypt). The caveat is that more iterations only get you so much; 100,000 iterations is only enough to increase "effective" entropy by a little over 16 bits ($100,000 \approx 2^{16}$) — to match a real 128-bit key, you'd need a password with 112 bits of entropy, which is an impractical 19-character alphanumeric password.

One approach without this caveat is to use a PBKDF to derive an actual encryption key from a key and password; this has the benefits of both systems. There's a real 128-bit (or 256-bit) secret that protects the data, which is typically invisible to a user, but you require a password to access and use that key.


Create key for AES-256 in Node.JS I'm trying to create a strong key for encrypting some data using AES-256 for fun and practice.  For my own practice, I want to make this as strong as possible, I don't care how long it takes to complete.

I got some advice from 1Password white paper and therefore I want to use 2 secret keys.  The master password and a random generated 32-byte string.  The master password and the secret key will always be kept on the client side and never transferred to the server. Let me know how I can make this stronger.

The steps go like this:

1) Create a 32-byte salt.

2) Create a 32-byte secret key

3) Using PBKDF2-HMAC-SHA512 with 100,000 iterations, create a key using the password and the salt.

4) XOR the key and the secret key to create the key to be used to encrypt using AES-256.

 crypto.randomBytes(32, function(err, salt) {
  crypto.randomBytes(32, function(err, secretKey) {
    crypto.pbkdf2(password, salt, 100000, 32, "sha512", (err, derivedKey) => {
      var a = derivedKey;
      var b = secretKey;

      if (!Buffer.isBuffer(a)) a = new Buffer(a)
      if (!Buffer.isBuffer(b)) b = new Buffer(b)
      var res = []
      if (a.length > b.length) {
        for (var i = 0; i < b.length; i++) {
          res.push(a[i] ^ b[i])
        }
      } else {
      for (var i = 0; i < a.length; i++) {
        res.push(a[i] ^ b[i])
        }
      }

      var aes256Key = new Buffer(res).toString('hex');
    });
  });
});

This is going to be client-side Javascript, run inside a React-Native application.

I just want it to be looked over to make sure I'm using strong methods as well as correct key lengths for AES 256.

This is largely a reasonable strategy given the tools at hand.  The salt need only be 16 bytes to thwart multi-target attacks, though using a 32-byte salt doesn't hurt.  You will presumably want to store the secret and the salt separately, so that it requires both of them to confirm a guess about the password; otherwise there's no sense in having a separate secret.

Rather than use PBKDF2-HMAC-SHA512 with exactly 100 000 iterations, you should estimate how long you are willing to wait on the slowest device you care about, and use as many iterations as that device can compute in that time.  Even better, if you have a large memory available and access to scrypt or argon2, you should use one of those to exploit the memory available in order to raise the attacker's costs in a different dimension.

The more time you spend, the more joules of energy the attacker must spend to try each guess.  But the attacker can try guesses in parallel.  The more memory you spend, the more die area the attacker must spend on memory instead of parallelism.

N.B.: This is only about the cryptography.  I am not commenting on the quality of your JavaScript code; there is CodeReview.SE for code reviews.


What is an accurate definition for a 'Monoalphabetic substitution cipher' and why does it provide a poor level of security From my research online, I am confused about the difference between a 'monoalphabetic cipher' and 'monoalphabetic substitution cipher'. However, I have got my answer from the websites Kifanga and Cornell.edu for reference:

The following is my answer:

A monoalphabetic substitution cipher is a cipher in which each occurrence of a plaintext symbol is replaced by a corresponding ciphertext symbol to generate ciphertext. The key for such a cipher is a table of the correspondence or a function from which the correspondence is computed.

Monalphabetic substitution ciphers are easy to break using a decryption method called letter frequency analysis. This is done by studying the text in the language of the cipher, and the frequency of each letter can be determined. For example, in the English language, the most frequent letter is E followed by T. By substituting the most frequent letter in the ciphertext with the letter E the second most frequent with the letter T and so on I will end up with the original plaintext.

Are my definition and description accurate? If not, what is an accurate description and why does it then provide a poor level of security?

A monoalphabetic substitution cipher uses a fixed permutation of an alphabet $A$ namely $$\pi:A\rightarrow A,$$ to encrypt a plaintext $P=(P_1,\ldots P_n)\in A^n$ of length $n$ into the ciphertext $C=(C_1,\ldots,C_n) \in A^n$ via $$C_i=\pi(P_i),\quad i=1,\ldots,n.$$

For a natural language, the letter frequencies are non-uniform. Thus, given a long  enough ciphertext, the original text can be easily recovered.

The length of plaintext required for unique recovery of the ciphertext is called the unicity distance, see here defined by Shannon, and is related to the redundancy in English, which is a result of the non uniform letter distribution. Most models of English give a unicity distance of around 30 letters.

Edit: To see how easy it is to attack monoalphabetic substitution, consider the letter frequencies of English, say as shown here. The four most common letters (E,T,A,O) have a total probability of around $0.38$. Thus if we have a 30 letter ciphertext (in a ciphertext only attack), the number of occurences of the letters in the set $$\mathrm{U}=\{\sigma(E),\sigma(T),\sigma(A),\sigma(O)\}$$ is highly likely to be the four most common ciphertext letters, and on average about $0.38 \times 30 \approx 11$ letters will belong to this set. There are only $4!=24$ permutations of this set and trying all will likely expose some English like fragments, helping in the cryptanalysis.

The probability that less than, say $t=8$, ciphertext letters belong to $\mathrm{U}$ can also easily be evaluated using the binomial distribution $\mathrm{Bin}(40,0.38).$

This attack can be further strengthened by considering common digrams (two consecutive letters), trigrams etc. and forming hypotheses on those, not only is the letter $\sf{T}$ very common, the digram $\sf{TH}$ is very common in English, etc.

One good countermeasure to protect this encryption to some extend is to use a Homophonic substitution, i.e., a new alphabet of larger cardinality and splitting the letters of English more or less uniformly, where each common letter is mapped to more than one new ciphertext symbol pseudorandomly.
Simon Singh's website describes this rather well here. However by no means does this countermeasure provide modern cryptographic strength against computer based attacks.


What is the difference between a PRF and a PRP, and are cryptographic hash functions the same as HMAC (PRFs or PRPS)? I read one answer to a similar question that put forth that a hash function is distinct from a PRF, however I've also found materials purporting that cryptographic hash functions are PRFs, and I'm not sure now. Also, is HMAC a PRP because of being keyed? I thought that a cryptographic hash function being keyed (i.e., with a constant prepended/appended to the input) was what determined whether it was a PRF or a PRP, however upon searching more I've become increasingly confused. Right now I think that a hash function is a PRF and that an HMAC is a PRP, and that this is because HMAC is keyed.

I read one answer to a similar question that put forth that a hash function is distinct from a PRF, however I've also found materials purporting that cryptographic hash functions are PRFs, and I'm not sure now.

Those latter materials are wrong.

Random function

A mathematical function (i.e. a "pure" function) whose output values depend only on its inputs, but whose outputs are random.  Think of it as a (potentially infinite) table with two columns:

The first column lists every possible input exactly once;
The second column has been filled-in ahead of time with values selected uniformly at random from the function's range.

A random function is an ideal object—something we know can't practically exist at the sizes we're interested.

Pseudorandom function family (PRF)

A deterministic computer algorithm such that it:

Takes a secret key and a (not necessarily secret) input;
Runs in polynomial time;
Has the property that if you choose the key secretly and at random, an adversary would find it so difficult to crack that they wouldn't even be able to tell it apart from a random function in any practical amount of time, even if they know the algorithm and can choose the non-key input to it.

Note that a PRF is intended to act as a practical aspiration—something that cryptographers hope that a practical computer algorithm can achieve.  Note that there isn't actually hard proof that it's possible to implement a PRF in real lie—the existence of PRFs is a conjecture.

Note also that I boldfaced secret over and over—that's an important little detail here.

Random oracle model

A type of cryptographic security proof where a hash function is modeled as a random oracle—a public random function that is accessible both to honest parties and adversaries.

Note that just like I boldfaced secret above, here I boldfaced public, because that's a key difference.  A PRF takes a secret key that the honest party must choose at random, and thus a PRF is supposed to behave like a random function that only that party is able to evaluate. Whereas crypto hash functions like SHA-256 are designed to resist attacks in scenarios where there's no secret key. For example, an adversary isn't supposed to be able to find two SHA-256 inputs that collide in any practical amount of time, even though no secret about the algorithm or computation is kept from them. So ideally, hash functions should behave like random functions that are known to every party.

Note that another confusion you'll come across often is people who use the term "random oracle" to mean random function.  I like to think of it with this analogy: being a random oracle is like being the President of the United States.  You have to be a natural born citizen and 35 years or older, but what makes them President isn't that they fulfill those two requirements, but rather the role they play in the political system.

Likewise, a random oracle must be a random function, but what makes that function a random oracle isn't just the fact that it's random, but rather the role it plays in some scenario.

Now, the rest of your questions:

  Also, is HMAC a PRP because of being keyed?

HMAC is routinely conjectured to be a PRF. It's not a permutation because there must exist multiple inputs that produce the same output. And thus it cannot be a PRP, which is a subtype of PRFs with the additional stipulation that for each key, the algorithm must implement a one-to-one function (a.k.a. a permutation).

  I thought that a cryptographic hash function being keyed (i.e., with a constant prepended/appended to the input) was what determined whether it was a PRF or a PRP, however upon searching more I've become increasingly confused.

Your mistake here is thinking that being "keyed" is a contextual property of how you choose to use the function in one scenario, but you really need to look at it as an intrinsic property of the function itself, or otherwise you'll indeed get confused.  SHA-256 has just one input, and that input is for a message that the function doesn't demand that you keep secret. So no, SHA-256 definitely isn't secret keyed function.

If you need a PRF, however, one way to build one is HMAC-SHA-256, a construction that defines a function that does take a separate key (that it demands that you choose secretly at random) and message.  Then, under the hood, HMAC-SHA-256 combines those two inputs in a specific way and hands them to SHA-256.

But the fact that HMAC-SHA-256 is a keyed function that's built out of SHA-256 doesn't mean that SHA-256 is "sometimes a keyed function"—it just means that you can build keyed functions out of unkeyed building blocks.  Again, "keyed" should be understood as a fixed, intrinsic property of how the function is defined, not a variable contextual fact about how it's used in some scenarios.


Chosen plaintext vs Chosen ciphertext What is the difference between chosen plaintext and chosen ciphertext attack?
In both of these adversary has access to paintext-ciphertext pairs.Then where lies the difference?

The difference is how the plaintext-ciphertext pairs that the attacker has access to are generated.

In a chosen plaintext attack, the attacker chooses some plaintext and is handed the corresponding ciphertext.
In other words, the attacker may encrypt arbitrary messages.
In a chosen ciphertext attack, the attacker can additionally (a chosen ciphertext attack is usually understood to subsume a chosen plaintext attack) choose some ciphertext and is handed the corresponding plaintext.
In other words, the attacker may encrypt and decrypt arbitrary messages.

(Note: usually, additional restrictions on the permitted messages are posed in a particular security game to make it "fair", since some notions of security are vacuous if the attacker can query really arbitrary messages.)


Decrypting a substitution cipher, but with symbols instead of letters I'm trying to decipher a message encrypted by a substitution cipher (probably a monosubstitution). But the problem is, that we have symbols instead of letters (letters were substituted for random symbols). What would be the best way to decrypt such a message?

Thanks

Frequency analysis is the way to go. If your plaintext is in English then the letter "e" would (probably) be the most common letter in the text. A good technique would also be to look for repeated symbols. In the English language (and probably all other languages as well) there are many words with double letters (i.e. "kill", "hello", "symmetry"), so you can narrow it down what the word with the repeated symbol would be.


Modular Addition in RC5 is linear or not? So, far my understanding was Modular addition is non linear function which is mainly used in ARX based ciphers.
While I was glancing through RC5 paper (https://link.springer.com/content/pdf/10.1007/3-540-60590-8_7.pdf) the author has mentioned that the only non-linear operation is "data dependent left-rotation", even though it has modulo 2^n addition.
In the given paper, the author, has not mentioned about finite field details, so it is assumed that the addition operation is happening on n-bit register.
I am attaching the image for the reference and also note the last 3 lines.

Consider $f: x\mapsto f(x)=\underbrace{x+x\ldots x}_{a\text{ times}}+b\bmod 2^{32}$ in the the ring $(\mathbb Z_{2^{32}},+,\times)$, where $a$ and $b$ are constants.
Per one meaning, $f$ is linear, that is of the form $x\mapsto a\times x+b$, for constants $a$ and $b$. Per another meaning, $f$ is not (in general) a linear boolean function. $f$ is also not linear in the field $(\mathbb F_{2^{32}},\oplus,\otimes)$, where $\otimes$ is polynomial multiplication modulo an irreducible polynomial of degree $32$.
To make «the rotations are the only non-linear operator in RC5» true, we can craft a meaning of «linear» that allows any of the above definitions.
Without rotations, RC5 would be trivially breakable no matter the number of rounds, for lack of propagation from high-order to low-order bits of the four 32-bit sub-blocks.
It's harder to prove the (true) assertion that with only fixed rotations, and baring much more rounds, RC5 would be breakable. That's because it would be too linear, in some sense that I fail to exactly define.


Identify Keccak Algorithm I need to analyse a binary code and check if Keccak is used in this code.
I can identify AES, by using Rijndael S-box. Is there a similiar box for Keccak?

I just found the "round constants" which hopefully are sufficiently unique to allow identification of the algorithm.


Regarding Key Strength with DES and Blowfish I had a small discussion with my friend on combining two encryption algorithms based on 64-bit keys.

Say I have a plain text of 64 bits which I want to encrypt. My Key size is 128 bits. I will use the standard DES algorithm with the first 64 bits of the key to encrypt plaintext. With the remaining 64 bits of key, I will apply the Blowfish algorithm on ciphertext that DES produces. Assume this is my “encryption algorithm”.

Now, what I want to know is: will key size is considered as 120 bits (56-bit for DES + 64 bit for Blowfish), or will it be considered as 2 individual key sizes (56 bit and 64 bit) with two different encryption algorithms? As 64 bit keys based algorithms are weak with current computational environments, can cryptanalysis attack or break the security easily?

Personally I believe double-encryption algorithms provide more security on the plain text. But somehow I am not able to convince my friend that combining two weak 64-bit algorithms will provide a double key strength. Please share your thoughts to help me understand.

I won't say someone would be able to break it 'easily'; however it won't be anywhere as difficult as with a true 128 bit cipher (or even 120 bit cipher; your construction ignores 8 of the key bits).

Here's an outline of how the attack would work: we assume we know the plaintext and the ciphertext, and are trying to recover the key.  When we do is encrypt the plaintext with all $2^{56}$ possible DES keys, and put them in a huge list.  Then, we decrypt the ciphertext will all $2^{64}$ possible Blowfish keys, and put them in another huge list.  Then, we go through the lists, and look for a match; when we find a DES-encrypted ciphertext that matches a Blowfish-decrypted plaintext, that gives us both the DES key and the Blowfish key.

Now, the first obvious objection to this is "if the attacker already knows the plaintext, why does he need the key".  Well, one answer is that this sort of attack can work even if the attacker has a guess of part of the plaintext; if he can just encrypt that region, that is enough to make the attack work.

The second objection is "there's no way anyone has enough memory for lists that big".  While this is true, this attack can be modified to use less memory (at the expense of more computation); in general, if you have $O(2^m)$ memory, this attack can be done in $O(2^{120-m})$ time (for $m \le 56$); this means that if the attacker has a few Terabytes ($2^{40}$ bytes) sitting around, he could do this in $O(2^{80})$ time; that's a bit too close to practical for me


A method to receive payments at obscured addresses The background:

We assume that coin ownership and payments are recorded on a public ledger.
Suppose Alice wants to publish some information to let her receive coins from anyone.
But she does not want to receive coins at a publicly known fixed address.
Instead, she wants the payer to generate a unique destination address each time.
The payer must not know the private key for the address; only Alice will know it.

I want to know if the following algorithm will achieve these goals. This combines Diffie-Hellman key exchange plus any digital signature algorithm. Are there subtle flaws that I am missing?

Suppose we use an elliptic curve for Diffie-Hellman, and $G$ is a publicly agreed base point.
Alice chooses a secret integer $a$.
Alice computes the public point. $A = a×G$
Alice publishes the statement "Alice will receive payments derived from the number $A$".
Alice will not change this statement for a long time (years, many payments).
Bob wants to pay Alice, so he retrieves Alice's value $A$ and will derive a new public key.
Bob chooses a secret integer $b$.
Bob computes the public point $B = b×G$.
Bob computes the shared secret integer $s = \text{hash}(b × A) = \text{hash}(b × a × G)$.
Bob computes the public key $K = A + s×G = a×G + s×G = (a + s) × G$.
Bob sends his payment to the address $K$, and also mentions the point $B$ within the payment message (recorded on the public ledger).
Bob tells Alice out of band, without using the public ledger, about the payment info $(K, B)$. This step doesn't need to be secure, but should be kept off the permanent public record.
Alice computes the shared secret integer $s = \text{hash}(a × B) = \text{hash}(a × b × G)$.
Alice computes the private key $k = a + s$, which corresponds to the public key $K$.
Now Alice can spend the payment she received from Bob, by creating a signature using $k$.

Your algorithm should be secure since it's basicly the same as the "one-time-address"-algorithm in the CryptoNote protocol, which is described as following:

Alice generates two secret keys $a$ and $b$ and publishes $A = aG$ and $B=bG$.
Bob, who wants to send a coin to Alice generates a random $r$ and publishes $R = rG$ and $P = H(rA)G+B$.
Alice (or any party knowing $a$) can check weather a payment belongs to Alice by checking whether $H(aR)G+B = P$. Note that this does not require $b$, so Alice can let any other party check for payment by sharing $a$ without risking them to spend her coins.
When Alice want's to spend the coin, she calculates $x = H(rA)+b$, which is the private key for $P$ since $P = xG = (H(rA)+b)G=H(rA)G+bG=H(rA)G+B$.

Your scheme is a variation of this algorithm with $a = b$ so that $A = B$. This leads to Bob calculation $P = H(rA)G + A$, a check can be performed with $H(aR)G+A = P$ and the secret key being $x = H(aR)+a$, so you can assume it being as secure as the CryptoNote's algorithm (which is pretty secure AFAIK), however you lose the ability to share a view key to let others search for transaction for Alice.


Indeed, this is a threshold issue, but the real threshold is $2^{32}$, not $2^{36}$ as documented. You can verify this with the following test:
SetVerbose("FFLog", 2);
repeat p := 2 * (2^32-5) * RandomPrime(10) + 1; until IsPrime(p);
Log(PrimitiveElement(GF(p)), PrimitiveElement(GF(p))^Random(p));
repeat p := 2 * (2^32+15) * RandomPrime(10) + 1; until IsPrime(p);
Log(PrimitiveElement(GF(p)), PrimitiveElement(GF(p))^Random(p));

Unfortunately there does not appear to be a way to call Pohlig-Hellman directly, or at least disable index calculus.


Why should I use X.509 Authentication over PKC based Authentication? So I have two examples and I don't understand why one would be chosen over the other.

Example 1.
A sends EPUb[r1] to B (asks B to prove knowledge of PRb)
B replies with r1, EPUa[r2] (asks A to prove knowledge of PRa)
A replies with r2 to prove it

Example 2.
A sends r1 to B (asks B to prove knowledge of PRb)
B replies with r2, EPRb[h(r1)], CertB (provides B with signature and certificate and own challenge)
A replies with EPRa[h(r2)], CertA

Why would example 2 be better than example 1? Are there any security loopholes I'm not seeing in example 1 than example 2 fixes?

I'm studying for my cryptography exam tomorrow and been stumped by this example. Fast responses would greatly appreciated.

From what I can pick up on these two examples. Example 2, you provide each other with your public keys and you know the origin is trustworthy after you verify the certificates. When communicating you can then use each others public keys for encryption or you could establish a symmetric key which eliminates the man in the middle attack possibility.

In Example 1 all I can think of is that without the certificate they can't be sure the other entity is who they claim to be but then again to know each others public keys there must be some form of trust between them. Is example 2 better just because you can be MORE sure that the other entity is who they claim to be?

In real communications, you often don't reliably know each others' public keys. X.509 certificates provide a way to verify a public key (as the certificate is signed by another key, and that key can be in a certificate signed by a third key, and so on, until we reach a public key that the other person does trust). Certificates are unnecessary when both parties already know each others' public keys through some form of out-of-band communication.


Does size matter in case of attack on LUKS partition? Does the size of the LUKS partition affect the difficulty of a brute force attack, or would it not make difference? For example, would a 100MB partition be easier to attack than a 100GB partition?

No, the size does not matter. No matter which algorithm you use, the attack with the best chance of success is to guess the passphrase, unless the passphrase is a long, random, unmemorizable one (i.e. a keyfile in practice).

Attacks against the passphrase are not helped by a larger amount of ciphertext. They work by generating the key corresponding to the passphrase, and then attempting to decrypt with the resulting key. A few bytes of ciphertext are enough to validate the guess.

If the algorithm is the limiting factor, then finding the 128-bit key using the fastest known techniques requires very close to $2^127$ attempts on average ($127$ and not $128$ because on average the key is found after exploring half the search space). Knowing a lot of plaintext-ciphertext pairs does not help to find the key or to decrypt other ciphertexts: cryptographic algorithms are designed to resist such attacks.


Validating that a hash is over a specific value for two hashes with additional (known but different) input $M$ (not public) is hashed with a hash function $\text{H}$ that includes a variable $T_1$ (public), giving $C_1$ (public). The same $M$ (not public) is hashed with the same hash function with another variable $T_2$ (public), giving $C_2$ (public).

Knowing the variables, $C_2$ can be verified to be from the same data as $C_1$.

Is there a hash function $\text{H}(M + T_1) = C_1$ that relates to $\text{H}(M + T_2) = C_2$ in such a way that, knowing $T_1, T_2, C_1, C_2$, and with no knowledge of $M$, it can be verified whether both use the same $M$?

This is not probably what you had in mind; but this is easy to achieve with a slight expansion.

Let us assume we have a private, public pair, with private key $P$, and public $K$. We basically consider $P$ to your $M$, and take $K$ to be part of the public knowledge of the verification of the hash.

Then $H(M+X)$ is defined to be $\textrm{Sign}(P,\textrm{Hash}(X))$ for any desired hash algorithm. Let $C_i=\textrm{Sign}(P, \textrm{Hash}(T_i))$. Given the public $K$, one can then verify the legality of each $C_i$ (and of course, for publicly known hash-function, one can also calculate the hash of $T_i$ directly).


Would SHA1 be broken by sheer brute force, even if it had no weaknesses of its own? It is well-known that SHA1 is broken.  Collisions have already been achieved.

Current algorithms for finding collisions leave a “fingerprint” in the collision files, which can easily be detected.  It is claimed that brute-force would not be practical, since that would require $2^{80}$ time.

However, I am not so sure if $2^{80}$ time is that impractical.  My understanding is that the Bitcoin mining network together generates about $7*2^{89}$ hashes per year.  That is enough to break any system with 80 bits of security by sheer brute force.  I know that it uses dedicated hardware that cannot be repurposed.  But creating such hardware would be well within the capabilities of a nation state.  And cryptosystems are supposed to be secure against such adversaries.  Furthermore, there are other cryptosystems with 80 bits of security, and some are still being proposed today (!)

Just how feasable is this attack?

Yes, it is now conceivable to find a SHA-1 collision by brute force.

The general method is outlined in Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, 1999; free earlier version available from the first author's website; expands on an article presented at CACM 1994). It uses local search iterating hashing; when a distinguished value (say with a certain number of zeroes in low-order bits) is found, it is reported to a central location; enough findings lead to a collision. It is expected that less than $2^{82}$ hashes (and comparatively little extra work) are required to find a collision.

By May 2018, the bitcoin mining aggregate hash rate is reportedly $30\cdot10^{18}$ SHA-256d per second ($2^{81.1}$ per day), where SHA-256d uses two SHA-256, and SHA-256 is roughly as costly as SHA-1. The ASICs predominantly used for that can not be directly repurposed for a SHA-1 collision search: they use SHA-256d, not SHA-1; and as an aside they hash incremental values, rather than iterated ones. However the technology is there.

Thus the energy spent in a day of bitcoin mining is enough to find a SHA-1 collision by brute force, hypothesizing the same technology is used. The collision found would be a random one, with chosen prefix decided at start of attack, and could not be detected.

And it might well be that significantly less work would be enough to find a collision that evades detection using the current "fingerprint" method, by using specially crafted (but less efficient) differentials than used to find the first collision reported.


Why is it a bad idea to use a UTF-8 derived symmetric key? Given a cryptographically secure series of octets, it is often useful to display this information or store it in a database in a textual format such as hexadecimal.

Why would it be incorrect to take this hexadecimal and encode it with UTF-8 to derive a symmetric key rather than converting from hexadecimal back to the original byte array?

My thought is that it reduces the key space and presents a bias toward where hexadecimal characters fall in the UTF-8 encoding scheme. Perhaps someone can clarify this for me.

The strength of a symmetric key is determined by the amount of entropy. In that sense your scheme would not increase or decrease the security by much. However, you would be specifying a higher key size than actually used. For instance your AES-256 bit key would have the same entropy as an AES-128 bit one. You'd use a slightly different key schedule and number of rounds as well of course.

Besides that you may run into problems when somebody decides to use a different encoding (hex encoding in UTF-8 is the same as just using ASCII though) or a byte order mark. It could also be possible to mix up uppercase and lowercase characters.

In the end you're only fooling yourself and possibly others if you'd use this kind of scheme. It is very bad practice. If you have to store the key as hexadecimals then pretty please with sugar on top, convert it back to the original form.

In general though you should never ever have to store a key in a string in the first place. Note that strings may be very hard to delete from memory. Instead store them in a key store such as PKCS#12 or preferably in a hardware device.


Is secure lattice based cryptography in future? Lattice cryptography is a post quantum cryptography that work on two NP-hard problem in below:

Find shortest nonzero vector from origin and
Find minimum distance of a arbitrary point out of lattice from origin.

At the moment lattice cryptography system is broken with key space of dimension 300. On the other hand we use dimension 400 in this cryptosystem. Can we use this cryptosystem in future?

How we can distinguish between this cryptosystem with others?

With math and computational advances, for protecting systems we should increase key size. We know that recommended key size for lattice based systems such as the NTRU is approximately $3slog(s)+1000$ bit, which $s$ is a desired security level.Today $s=80$, but with the advances of math, $s$ is increasing. $s=96$ is believed to provide protection until $2020$. So if we use lattice in future we should increase its dimensions.

For more detail about other cryptographic Schemes complexity you can see "Cryptographic Schemes
Based on Isogenies" and also
"Yearly report on algorithms and key sizes".


Proving I can solve an equation without disclosing the solution (zero-knowledge proof) Given a (potentially multivariable) equation $f(x)=0$, Peggy wants to prove to Victor that she knows a solution $x^\star$ to it without actually disclosing anything information about the value of $x^\star$.
Is there a slick way to pull off this zero-knowledge proof?
If possible, I want a solution

in the continuous context where $x\in\mathbb{R}^n$ (and, if necessary, $f$ is well-behaved and infinitely differentiable.)
in the discrete context, where $x\in GF(p)$ (i.e. modulo a large prime $p$).

For a continuous example: $f(x) = [ x_1 \cdot x_2 - 2 , x_1^3 - x_2 + 1] = [0, 0]$. A solution is $x^\star = (1, 2)$.
For a discrete example: $f(x) \equiv 2^{x_1} + 3^{x_2} - x_1 \equiv 0 \pmod{5}$. A solution is $x^\star=(1,2)$.
In both cases, we want to show we have that solution without disclosing the value.
Edit: You can absolutely assume that $f$ can be efficiently evaluated, making the problem in NP.
Edit 2: I in particular want a slick solution that doesn't involve just considering the boolean computation circuit. Something more akin to the zero-knowledge proof that one knows of a Hamiltonian path by considering providing it on an isomorphic graph.

For the discrete case, you can just use any zk-SNARK that generalizes over arithmetic circuits.
There is no direct way to do a zero-knowledge proof over the reals. However, you can map linear operations over real numbers to operations in the field you are working in by first proving an upper bound on your inputs. Since the circuit is public the verifier can independently check if the upper bound leads to overflow.


Public key crypto instead of hashing passwords in a database Suppose I want to keep a client's password database secure (not in plaintext), while still having access to the plaintext password.

Now I generates a public/private keypair. Then I send the public key to all servers, while keeping the private key on a heavy-secured, airgapped computer. Now, instead of salting and hashing the passwords, I salt it and then encrypt it with the public key, and store it in the database.

The method to store the password is Encrypt(password+salt). The encryption algorithm is deterministic. (If the input is the same, the output is the same.

If the bad guys now hack my server, they won't be able to get the passwords, since they don't have the private key to decrypt them.

If I ever need the passwords, I can just copy the database to my airgapped machine and decrypt the passwords in the database.

What are the disadvantages of doing so?

This is a really bad (and somewhat pointless) idea (if you do it on your own), because it provides less security than standard hashing and should only be considered if password escrow is a necessary feature.
If you don't need the password escrow (= recover the password using the heavily secured airgapped private key) you can simply password-hash the password using a modern scheme such as Argon2 which won the Password Hashing Competition.
If you really need the escrow functionality you should use Thomas Pornin's (who's here around sometimes) Makwa password hashing scheme which has been recommended by the Password Hashing Competition (PHC) for special use cases (as yours).

Now for the obvious approach and why it is bad.

I'd assume you would implement this by applying straight, raw RSA to your passwords and compare the results.

Now, if you just do $E_S(PW)$ without any randomness, you're basically creating a one-way hash function (with a backdoor and without compression) which is unsalted and doesn't use stretching (like for example raw MD5 password hashes). As your update reveals you indeed planned on using salting so it's not completely bad, but still far from optimal.
The second issue is that you won't get a compression. Meaning any password will occupy 256 bytes in your database as opposed to the standard 16 or 32 because you need the whole RSA encryption for key escrow.
The next issue is that you could add a salt, but because it's RSA you need to use a big salt, because there is an attack with run-time $O(\sqrt{m})$ meaning you need at least another 32 bytes salt, which further increases storage penalty.
Now you can also quite fastly compute the RSA encryption, meaning brute-force attacks won't be slowed down. This would mean you'd have to apply RSA multiple times are do some intense pre- or postprocessing without loosing information which is quite not easy.

I presume you didn't think of all these issues (yet), so better go with Argon2 or Makwa.


Is encrypt-and-MAC secure for AES-CTR + UMAC? OpenSSH will (especially in older versions) use AES-CTR plus a MAC in encrypt-and-MAC.  This is not secure in general (meaning that there exist secure ciphers and secure MACs such that using them in encrypt-and-MAC is insecure).

However, as I understand it AES-CTR + MAC as used in SSH is secure, at least for the MAC choices actually in use, because:

The MACs used (HMAC and UMAC/VMAC + encrypt the MAC tag) are
privacy-preserving: the MAC tag does not leak any information about
the plaintext, at least for one who does not know the MAC key.  In the
case of HMAC, I believe that this follows from HMAC being a strong PRF;
in the case of UMAC/VMAC, the security of the MAC depends entirely on
encrypting the MAC before transmission, and the encryption of the MAC
also ensures that no information about the plaintext is leaked.
No encoding is done between encryption and authentication.  The data
that is encrypted and the data that is authenticated are one and the
same.
The cipher in question uses CTR mode – in other words, it is a stream
cipher.  Thus, any change to the ciphertext will cause a 1-to-1 change
in the plaintext – integrity of plaintext thus implies integrity of
ciphertexts.

My conclusion is that these cipher suites are actually secure, due to the specifics of the protocol.

Is my reasoning correct?  More importantly, is my conclusion correct?  I am not a cryptographer and have zero trust that I did not make a foolish error.

Encrypt-and-MAC does not preserve confidentiality because two encryptions of the same message will have the same mac tag, revealing the fact that the messages are equal.

Ssh includes a counter in the data the mac tag is computed over, so it never computes the mac tag for the same message twice (even if identical data is transmitted twice), so this particular weakness is not an issue.

This is not an endorsement of encrypt-and-MAC, however. Do not use it.

(If you have a strange MAC, encrypt-and-MAC can leak even more than equality, but few reasonable MACs are strange.)


My RSA decryption doesnt match answer Break the RSA code whose key is $(n, e) = (8369428283, 1234567)$.

Find the deciphering key and then decipher the message under the assumption that the plaintext consists of 7-letter blocks in the alphabet, converted to an integer between 0 and 26^(7) −1 in the usual way, and the ciphertext consists of 8-letter blocks in the same alphabet.

The given answer was CLAIMYOURPRIZE, but this doesn't match the one I got.

I converted the first 7-Letter block in CLAIMYOURPRIZE and I also got the first 8-letter block of the encrypted message. Then in order for them to match the value of the private key (d) must be 2 and that is not possible

$n = 8369428283 = 81799×102317$ (2 distinct prime factors by Wolfram Alpha)

The $d$ can be found in two ways;

if Euler's totient function $\varphi(n)= (p-1)(q-1) = 8369244168$ is used then

$d = 5788687615 = e^{-1} \bmod 8369244168$

If Carmichael Function $\lambda(n) = \text{LCM}(p-1,q-1) = 4184622084$ is used then

$d=1604065531 = e^{-1}  \bmod 4184622084$

Carmichael Function $\lambda$ provides us the smallest $d$  (lcm versus phi in RSA) and this can be helpful for reducing the timing of decrypting and signing. Here, $d$ calculated with $\lambda(n)$ is two-bit less than $d$ calculated with $\varphi(n)$.

I've encrypted end decrypted both parts by $\varphi(n)$ and $\lambda$ successfully.

[ C =  2 ][ L = 11 ][ A =  0 ][ I =  8 ][ M = 12 ][ Y = 24 ][ O = 14 ]
plaintext       =     CLAIMYO
plaintext int   =   748676046

ciphertext int  =  1773907495
ciphertext char =    AFTHVVNJ
plaintext char  =     CLAIMYO

[ U = 20 ][ R = 17 ][ P = 15 ][ R = 17 ][ I =  8 ][ Z = 25 ][ E =  4 ]
plaintext       =     URPRIZE
plaintext int   =  6387458406

ciphertext int  =  5283907511
ciphertext char =    ARCSTZFZ
plaintext char  =     URPRIZE

note: the A in the ciphertext means 0 as an integer.


Are cryptographic hash functions quantum secure? I was reading a paper related to post quantum cryptography. It says that RSA, ECC and ElGamal encryption schemes would be obsolete with the advent of quantum computers. But the hash functions can still be secure. I don't understand how one can unilaterally claim this security when hash functions themselves are not based on any hard problems. (I do have the knowledge of Merkel-Damgård and Keccak construction).

Are there hash functions considered secure just because nobody has come up with a quantum algorithm to solve it? Or are there any reduction to any well known hard problem? It there is please explain the reduction.

It is a bit dubious to claim that hash functions "are not based on any hard problem": inverting a standard hash function, or finding a collision, is itself a very hard problem.

The point of a reduction is to gather the cryptanalytic effort on a smaller number of hypothesis. The fact that RSA-OAEP is CCA secure under the RSA assumption is not a proof that it is secure, simply an indication that to study its security, it suffices to study the security of the RSA problem. As many other cryptographic primitives can be reduced to the RSA assumption, it saves a considerable cryptanalytic effort.

Now, such reductions usually rely on some nice algebraic properties of mathematical hypothesis, exploiting group structure, self-randomizability, and so on. These properties are common in asymmetric cryptography, because such additional structure is already necessary in the primitives it involves. But in symmetric crypto, on the other hand, such structure is typically avoided. A consequence of that is that you need way smaller primitives (in terms of bit size) and much less computationally expensive operations to achieve a (conjectured) given security level, but you loose the possibility of reducing many symmetric primitives to a small number of hypothesis.

Still, for the most widely deployed block ciphers and hash functions, the cryptanalytic effort that has been invested on studying their security easily matches the effort invested on "generic hypothesis" such as the discrete logarithm or the factorisation, because they are widely used in practice. Therefore, there is no reason to believe that, due to the lack of reductions, inverting SHA256 should be any easier than breaking RSA. In fact, because RSA has so much structure, most experts would probably be way more surprised by an attack that inverts SHA256 than by an attack that breaks RSA. Therefore, the fact that ElGamal and the kind enjoy "reductions" does absolutely not make them more secure - it only establishes links between hardness of different primitives.

That being said, quantum computers are not magical. We cannot say anything for sure about what we can or what we cannot break with them - for all we know, it could be that $P=NP$, and that all of cryptography can be broken using a classical computer. But our current knowledge gives us some intuition on the additional power they give over classical computers. And this intuition can be summed up as follow: it seems to give some additional power, but to still fall short on solving very hard problems (say, NP-complete problems) in reasonable time.

Some problems with a special structure (factorization, discrete log) typically fall in the category of problem for which quantum computers would give a very strong speedup, because they can be reduced to the task of finding the period of some function, which seems hard to do with a classical computer, but not with a quantum one. For unstructured problems, quantum computers seem to provide some non-trivial quadratic speedup, via the use of the Grover algorithm. But a quadratic speedup does not give an attack, it simply indicates that the size of the keys should be increased by a factor two to compensate for this speedup.

Hash functions are rather unstructured, so we currently do not see how to get more than a quadratic speedup over a classical computer to attack one. Therefore, we currently conjecture that a hash function with 256 bits of classical security would still have 128 bits of quantum security. For collision resistance, quantum computers provide an even less impressive speedup: the birthday attack gives a $O(\sqrt{n})$ attack, and it's quantum version seems only to make this attack $O(n^{1/3})$.


zkSnarks - why isn't PCD more widely used? I've been reading the paper Scalable Zero Knowledge from Cycles of Elliptic Curves, which elegantly solves (what seems to me) the main problem with zkSnarks; namely that performing non-trivial computations requires building enormous arithmetic circuits. The authors do this by showing how to compose verified computations via circuits that verify the proofs generated by other circuits.

My question is why this technique doesn't appear to be getting much use. Is the overhead from the proof-verifying circuit the main reason? I understand that vnTinyRam (the verifiable simulated CPU they introduce in the paper referenced) executes instructions very slowly, but is this because of the generality of the simulated CPU or is the overhead inherent in the PCD approach?

There are two types of overhead in PCD systems:

Overhead of proof verification: Computing the pairings necessary to verify prior proofs is expensive, and adds overhead unrelated to the statement you're trying to prove.
Overhead of predicates: In the Scalable SNARKs paper, each recursion level verifies the execution of the vnTimyRAM CPU. This involves verifying the CPU execution itself, as well as authenticating that the memory accessed during this step is correct. Checking CPU execution is cheap; it requires roughly a thousand gates. Memory checking, however, is very expensive; each access requires verifying a Merkle tree path. While the authors try to mitigate via the efficient Ajtai hash function, the overhead due to this check is still the largest in the circuit.

Together, these overheads are much more expensive per cycle than other approaches for verifying RAM computations; the primary reason to use recursive SNARKs is for the lower memory consumption.


Is AES in OFB mode with same IV more robust than ECB mode? I am looking at implementing AES128 bit encryption of a data stream. Since AES128 is a block cipher, which is inherently less robust than a stream cipher, I have considered configuring AES128 as a stream cipher in OFB mode as shown here. If I use the same IV, will it be more robust than standard ECB (block) mode?

OFB with an IV re-use is a different kind of completely broken than ECB.

In ECB mode, the problem is the fact that you can recognize blocks. That is if the same block appears twice you will notice that and know the underlying message-blocks were the same.

In OFB mode, the problem is the re-use of the key-stream. That is for any two ciphertexts under the same IV/key pair, you can compute the XOR of the underlying messages. Note that if you know (parts of) either message this allows you to recover (parts of) the other message.

So with ECB mode it's hard to actually infer the precise contents of the message but you can detect patterns in the ciphertext, whereas OFB hides patterns in a single ciphertexts, but leaks a lot of information with two ciphertexts.


Key Derivation from random salted seed, HMAC and HMAC based KDF I would like to generate a key which would be good enough to be used for encryption with AES in a mobile environment. My idea is to use as a seed ''random attributes'' from a mobile device. Is hashing first this seed using HMAC construction (with some salt which is also random but public) and then use a HMAC-based Key Derivation function secure and efficient?

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

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

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


Modular Inverse as a Problem Given a modulus $N$ and a number $a$, a multiplicative inverse exists for $a$ if $a$ and $N$ are coprime. Why isn’t there a cryptosystem that uses this as a computational problem?

Example

Alice and Bob agree on a public modulus $N$ and a public number $p$ such that $p$ and $N$ are not coprime. Then Alice sends Bob $a \cdot p \bmod N$ and Bob sends Alice $b \cdot p \bmod N$. Where $a$ and $b$ can be any number. Then they compute the shared secret: $a (b \cdot p) \bmod N \equiv b (a\cdot p) \bmod N$.

This doesn't work, because it is easy to compute $a$ from $ap \bmod N$ given $p$ and $N$. More precisely, it is easy to compute some $a'$ such that $a'p \equiv ap \pmod N$; $a'$ will not necessarily equal $a$, but that doesn't matter since $a'(bp) \equiv b(a'p) \equiv b(ap) \pmod N$, so the secret is correctly recovered.

In other words, this is Diffie-Hellman in the additive group mod $N$, and it doesn't work because discrete logs are easy to compute in such groups.


How much do we trust KEA1 Assumption? Let $$(g,h=g^s,q)$$ be a tuple such that $g$ is a generator for a group $\mathbb{G}$ of ord $q$ and $s$ is uniformly random in $\mathbb{Z}_q$.

The knowledge of exponent (KEA1) assumption says that for any adversary $\mathcal{A}(g,h,q)$ that outputs a value $(C,Y)$ such that $C^s \equiv Y$ then there exists a extractor $\mathcal{B}$ that on the same input outputs a value $x$ such that $g^x \equiv C$.

The assumption, roughly speaking, says that the only way to compute the tuple $(C,Y)$ is, actually, by knowing the exponent $x$.

This assumption was first proposed by Ivan Damgård in the paper "Towards Practical Public Key Systems Secure Against Chosen Ciphertext Attacks" in the '91.

My question is, how much do we trust this assumption? Is it reducible to something else?

I'm not sure how to answer the question about "trust" in the assumption. I suppose that is a matter of personal belief more than science. We don't know the truthfulness about any cryptographic assumptions, although obviously some have received more scrutiny than others. I'd say that the KEA assumptions have received relatively little attention, and so should be avoided if possible. However, I suspect that if you're asking the question, then it's not possible to avoid it.

As to the reducibility question, it's not reducible to anything that one might call a "standard" assumption. This is in fact by design. Standard assumptions, such as the RSA assumption or the DDH assumption, are "falsifiable" in the sense that if the assumption is false, then it is (in principle) easy to show a counterexample. In the case of RSA or DDH, the counterexample would be an algorithm A that successfully breaks the hard problems. Even if you have no idea how A works, it'd be pretty easy to verify that A is in fact a valid attacker just by sampling RSA composites/DDH tuples at random and seeing how often A succeeds.

By contrast, the knowledge of exponent assumption is one of the few non-falsifiable assumptions that cryptographers use. (The most common non-falsifiable "assumption" would be the concept of a random oracle, although that's not really an assumption per se.) It's possible that KEA1 is false, but it's not possible for me to prove to you that it's false just by showing you some simple witness to this claim.


How to securely map messages to points on an elliptic curve I'm implementing a demonstration hybrid cryptosystem in Python (FinCrypt, I know the name is bad) and I'm migrating over from my Weierstrass curve implementation, which was based off of this, to one based on Edward's curves from here.

However, I'm at a loss when it comes to mapping a message onto an element of the elliptic curve, and I noticed that the implementation I'm currently using doesn't require the message to be mapped, at least to my knowledge.

I was wondering three things:

Do I have to map a message, or is it possible to do something like I've already got going with Edward's curves
Is my current implementation of the ElGamal part insecure because it doesn't map messages and instead takes an integer?
If I do have to implement a mapping for security, how would you reccomend I map message values to points, and how should I figure out the maximum message size based on my curve?

If I do have to implement a mapping for security, how would you
  reccomend I map message values to points, and how should I figure out
  the maximum message size based on my curve?

The default strategy for encoding an integer message as curve point is to define a value $k$ smaller than $\log_2 p$ (with $p$ being the field prime), such that for every valid message length $m$, $m+k< \log_2 p$ holds. You would then encode the message as the $m$ high bits of the x coordinate and start counting up on the $k$ low bits until you reach an $x$ that has an $y$ on the curve (which you find using the curve equation). This usually has probability $2^{-k}$ of failing to encode a message. For decoding you simply throw away the $k$ low bits and take the rest as your message.

  Is my current implementation of the ElGamal part insecure because it
  doesn't map messages and instead takes an integer?

Yes, the scheme as given is insecure because you can easily distinguish an encryption of $1$ from an encryption of $2^{1024}$ because the former will be about as long as the curve's prime and the latter will be more than 1024-bit long, which formally breaks the IND-CPA security of the scheme.

Note that in order to use proper ElGamal you need to encode your message as a curve point $M$ and then compute $c_1=[k]\beta+M, c_2=[k]G$ all as operations on the curve. Also note that I'm fairly confident that simply replacing the unbounded integer addition with integer addition $\bmod p$ will not yield security either because curve point coordinates are not uniformly chosen integers (for starters because some $x$ values simply do not occur).

  Do I have to map a message, or is it possible to do something like
  I've already got going with Edward's curves

I see no reason to make any changes to your code, because currently it doesn't actually use ElGamal (see above). If you were to use proper ElGamal, the same strategy that worked for Weierstrass should also work for Edwards (see the first part).


Finding collisions in SHA1 I am trying to find two collisions in SHA1 for the 50 least significant bits.  I was wondering if there was a way to efficiently do this without having to brute force all of the possible hash outputs?

It seems like trying to look for two same hash outputs is easier than trying to find a message that hashes and matches to a hash output I already have.  (i.e. trying to break preimage resistance rather than second preimage resistance)  But this still seems like I would need to brute force all the possibilities

The easiest way to find a collision in 50 bits is to hash distinct values (random, incrementing, however's convienent), and put the results in a hash table, based on the 50 bits you're interested in.  When you insert a value into the hash table, and there's already an entry there, you've found a collision.

With 50 bits, you expect to have to hash around $2^{25}$ values, or about 30 million or so; if you're unlucky, you might run into 50 or 100 million before hitting a collision. That many entries easily fits into memory, and so this works out fairly well.


When does a feedback shift register count as non-linear? It seems that a feedback shift register is counted as a linear feedback shift register whenever it only includes XOR operations. This leads me to believe that a non-linear feedback shift register is any feedback shift register that does not just use XOR operations and would include the use of S-boxes, AND operations, permutations, and so forth. Am I correct?

Yes, you're right.

XOR is considered a linear function in this case. So the feedback into the registers is linear.  A non linear feedback shift register is a more generalised example where the feedback function can be anything. You can also call them generalised linear feedback shift registers GLFSR).
S-boxes, AND operations, permutations, and so forth are all good.  So the re-entrant bit is more than just a simple XOR operation of register bits. This frees you from the rigidity of Galois, Fibonacci and other predefined taps.  But then you'd have to make sure that lockup doesn't occur and the registers do not settle into some sort of funky stable pattern.

A picture showing a not so complex non linear feedback function f, but it could be anything as you suggest:-

This immediately brings up the interesting possibility of a secure hash function being f.  Or would that just be too much..?


What are the differences between collision attack and birthday attack? From my understanding both types of attack, collision and birthday, are based on the principle of two randomly/pseudo-randomly chosen plaintext to hash to the same value. I don't want to launch any biased supposition, but aren't they the same?

From Collision attack wikipedia article I learned that  every cryptographic hash function is inherently vulnerable to collisions using a birthday attack but in the Birthday attack article it is stated that the attack depends on the higher likelihood of collisions found between random attack attempts and a fixed degree of permutations, thus birthday attack only has this permutation plus?

Collision attacks are attacks where success is obtained when two values obtained by some process are identical. The term is often used in the context of hashes, since collision-resistance is one of their desirable property.

Birthday attacks are collision attacks that work by the effect of chance, with the colliding values obtained by some roughly random process (as in the birthday problem).

Marc Stevens's Single-block collision for MD5 (2012) is an example of collision attack that is not a birthday attack.


Can CTR mode be used with public key cryptography? Can counter mode be used in some way in public key cryptography? Can we decrypt when counter mode is used if 1. we have the key and 2. we have the cipher text? Is there any other mode in which this is possible?

I interpret your question to be asking "Can we directly use public key encryption algorithms with a CTR-like mode?", as opposed to "is it possible to perform a key exchange via RSA and use AES-CTR?" (which is obviously possible).

Let's define a "block cipher" as a deterministic algorithm that produces a permutation (the
"cipher" part) on a fixed-length block of bits (the "block" part). Non-randomized RSA meets this definition, though there are technically variants with different block sizes, determined by the modulus size.

The question then becomes "Can we apply textbook RSA to a public stream of incrementing numbers?", which is obviously a yes. However, doing so will not be secure. Non-randomized RSA is understood to be insecure. More importantly here, you will also be sending the nonce, and the adversary is assumed to possess your public key. Thus, nothing will prevent an adversary from applying $E(seed, public\ key)$ and generating the key stream himself.

"Randomizing" the above construction by using a random nonce will not work - if you are sending the nonce alongside the ciphertext, and the adversary has the key, the adversary can trivially recover the message.

So a secure CTR-mode using deterministic public key encryption such as RSA appears to be doomed.

Can we decrypt when counter mode is used if 1. we have the key and 2. we have the cipher text?

No, CTR mode generates a key stream by encrypting a counter, and adds the key stream to the message. Thus, if you do not have the seed for the key stream, you will not be able to regenerate the key stream and recover the message (assuming you do not resort to cryptanalysis to recover the message, anyways). While not sending the seed will disallow an adversary from recovering the message, it will also disallow the intended recipient from recovering the message, as both of them possess identical keys.


How to prove that a SKE scheme is IND-CPA secure There's an IND-CPA SKE scheme 1 $(\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})$. Scheme 2 is defined as $(\mathsf{Gen}', \mathsf{Enc}', \mathsf{Dec}')$, where $\mathsf{Gen}' = \mathsf{Gen}$, $\mathsf{Enc}'(k, m) = 0||\mathsf{Enc}(k, m)$ if $m\ne k$ and $1||k$ if $m=k$,
$\mathsf{Dec}'(k, 0||c) = \mathsf{Dec}(k, c)$ and $\mathsf{Dec}'(k, 1||c) = c$. How do I go about proving that the scheme 2 is IND-CPA secure?

I'm also having trouble understanding if the adversary can guess the correct bit on a chosen plaintext pair given the ciphertext, given that when $m = k$ the ciphertext always starts with $1$, but for the scheme to be IND-CPA secure I know that the adversary should only be able to guess with negligible probability. What am I missing here?

A CPA on the second scheme is exactly the same thing as a CPA on the first one, provided that the attacker never calls the encryption oracle on a message which equals the key. But the latter can happen only with negligible probability, otherwise the first scheme would not be CPA-secure since it has the same key generation algorithm.

Thus, for any CPA attack against the second scheme, the exact same CPA attack will succeed with almost the same probability on the first scheme after accounting for the negligible possibility that the attack calls the encryption oracle on a message quich equals the key.


What does "G2" mean when used with X509 certficates and certificate authorities? For example "Google Internet Authority G2"?. I thought it was another way of specifying Class 2 (for organizations, for which proof of identity is required) but then see certificates such as "VeriSign Class 3 Public Primary CA - G2".

It couldn't be something so simple such as Generation 2 could it? Hope someone who woks for a CA can explain these naming conventions. Thanks in advance.

Yes, G stands for "Generation". When CA needs to get a new chain they just increment the generation number.

For example GoDaddy's signatures:

G3 - sha256WithRSAEncryption
G4 - ecdsa-with-SHA384


A general definition for cryptocurrencies I am trying to find the definitions to several terms related to digital currencies. Unfortunately, I am always ending up on Bitcoin-oriented pages and websites which only take Bitcoin itself into consideration. So far, I managed to understand (actually, “guess” would be more appropriate) the following:

Digital currencies is the generic term for a currency which exists only as a sequence of zeros and ones on a digital support.
Electronic money is a way to realize a digital currency, it introduces a system where there is a central authority of trust in charge of managing the wallets of users and certifying all the transactions. Cryptography is only used to secure the communications between the users (buyers/sellers) and the central authority.
Cryptocurrency is another way to implement a digital currency, it defines a way to perform secured transactions and to control the creation of new units with the help of cryptographic schemes and protocols.

Now, lets venture a bit further and try to list the security properties that must (or may) be implemented by a cryptocurrency:

Unfalsifiability: The creation of new legitimate (or not) cryptocoins must be under strict control of the system.
No double spending: Once cryptocoins have been spent for a transaction, they must not be reusable by the original owner in another transaction.
Centralized/Distributed: The transactions using the cryptocurrency is done in centralized/distributed manner.
Anonymity (Optional): A transaction may be anonymous, meaning that the previous owner of a cryptocoin should not be easy to find.
Fraud tracing (Optional): A fraudulent transaction may lead to the unveiling of the original fraudster.

I guess that there might be dozens of optional properties to add… but, lets stop here.

So, my question is: are my definitions valid, or did I forget something (maybe some properties)?

I write here a partial answer to my own question (but it is only partial, feel free to write an answer of your own).

In the book "Introduction to Cryptography with Coding Theory" (2nd edition), by Wadde Trappe and Lawrence C. Washington, chapter 11, Digital Cash, p.288, we can find the following list of properties coined by T. Okamoto and K. Ohta:

  The cash can be sent securely through computer networks.
  The cash cannot be copied and reused.
  The spender of the cash can remain anonymous. If the coin is spent legitimately, neither of the recipient nor the bank can identify the spender.
  The transaction can be done offline, meaning no communication with the central bank is needed during the transaction.
  The cash can be transferred to others.
  A piece of cash can be divided into smaller amounts.

In the article "Blind Signatures for Untraceable Payments", by David Chaum, the digital cash holds the following properties:

  Inability of third parties to determine payee, time or amount of payments made by an individual.
  Ability of individuals to provide a proof of payment, or to determine the identity of the payee under exceptional circumstances.
  Ability to stop use of payments media reported stolen.

From all theses definitions, the definition I would find the most suitable is the following (I obviously forgot to speak about the security of each transaction):

Security of Transactions: Transactions between several participants must
be secured and non-repudiable. It must not be possible to pretend to
be someone else during or after a transaction or to spend more
cryptocoins that we really have.
Unfalsifiability: The creation of new legitimate (or not)
cryptocoins must be under strict control of the system.
No double spending: Once cryptocoins have been spent for a
transaction, they must not be reusable by the original owner in
another transaction.
Centralized/Distributed (Altnerative): The transactions using
the cryptocurrency is done in a centralized/distributed manner.

Then, comes optional properties:

Anonymity (Optional): A transaction may be anonymous, meaning
that the previous owner of a cryptocoin should not be easy to find.
Fraud tracing (Optional): A fraudulent transaction may lead
to the unveiling of the original fraudster.


AES mode for file encryption I'm working on software that should eventually result in a crypto file system similar to encfs. So far, i have a user password that goes through PBKDF2 using

PKCS5_PBKDF2_HMAC

with SHA-512 and a couple of thousand rounds to generate the Key Encryption Key. The Data Encryption Key and IV are random on a per-file basis with

RAND_bytes

DEK encrypted with KEK and the IV are written to the file header. So far so good.

For file encryption, I use a configurable block size of 512, 1024, ... 4096 bytes to split write requests into chunks and encrypt each chunk with AES. The mode however depends on various parameters and is not the same all the time. Right now I'm using CBC mode to maintain backwards compatibility, but esp. for random writes, CBC is somewhat ''clumsy'' to handle, so I want to switch to a different mode like GCM. Before I start coding, I have two questions:

Because GCM also offers AEAD, I want to keep the 512, 1024, .. blocks and use a per-block AAD and store the tag in the file. This allows me to fail early during decryption. What should I use for the AAD?
My per-block IVs (nonces for GCM) are generated using ESSIV: IV_n = AES(sha-512(DEK), block number) with Key = DEK and IV = per--file IV for AES, truncated to whatever IV size is used. Is that OK?

Hope I'm not completely off track ...

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


Does OpenSSL apply ASN1 encoding to the hash before signing using ECDSA? I read on stack overflow  that OpenSSL performs ASN1 encoding to the hash before signing it for, for ECDSA.

In other words, OpenSSL performs the following steps when for an Elliptic curve key -sign is called:

Calculate $H = Hash(M)$
Encode $H$ into ASN1 standard $H’$
Sign $H’$

If the above is true then in order to avoid applying step 1. it's necessary to first calculate the digest, and then sign the digest using raw signing -pkeyutl for elliptic curver keys.

However when I run BOTH -sign and -dgst + -pkeyutl I am able to verify the signature using -verify in both cases. This implies that ASN1 encoding is NOT being applied to the hash.

Can anyone throw some light on this topic? I was not able to find information in the OpenSSL documentation.

No, you do not add the ASN.1 encoding to the hash when generating an ECDSA signature.

There are two reasons for this:

The first is that there is no room, if we select a curve and a hash with equal security.  To be secure against attacks that take $O(2^N)$ time, a curve needs to have a prime that's at least $2N$ bits; to be secure against collision attacks that take $O(2^N)$ time, the hash needs an output that's at least $2N$ bits.  That means that, if we don't add any encoding, the hash just fits into the curve. If we were to add an ASN.1 encoding to the hash, that's mean we'd need to make the curve larger than necessary for security purposes.  Alternatively, we could modulo the result by the curve order to make it fit, however that is effectively the same as adding a constant (which depends on the curve and the hash function) to the hash, which appears a bit pointless.
The second is that there is no reason.  In RSA, the verifier recovers the padded hash value; he could then try to parse the ASN.1 encoding to determine the hash used (and then use that hash to hash the message being verified).  For ECDSA, the verifier doesn't actually recover the padding hash value; instead, he needs to generate the hashed (and padded, if padding is being used) message before he learns anything from the signature.  Hence, the potential gain we get from ASN.1 encoding the hash in RSA isn't there for ECDSA.

In addition, the original stack overflow question doesn't mention ECDSA at all; it strictly talks about RSA.  In the the question you pointed to, it's the question that assumes that ECDSA uses padding; the answer doesn't address that.


Why Smart's attack doesn't work on this ECDLP? The Problem is as follows:

sage: p=235322474717419
sage: a=0
sage: b=8856682
sage: E = EllipticCurve(GF(p), [a, b])
sage: P = E(200673830421813, 57025307876612)
sage: Q = E(40345734829479, 211738132651297)
sage: P.order() == p
True

As we can see, P.order() is equal to p, so obviously we can use Smart's attack to calculate the value of k, so i implement the Smart's attack according to the paper Weak Curves In Elliptic Curve Cryptography.

And when we use this kind of attack we will get k = 9762415993955:

sage: SmartAttack(P,Q,p,8)
9762415993955

But actually the correct value of k is 152675955744921:

sage: P*152675955744921 == Q
True

So my question is:

  Why Smart's attack doesn't work on this ECDLP?

P.S. The implement of Smart's attack is correct cuz it can calculate the correct value of k in some former CTF games.

The reason the attack does not work is because you are hitting a special case—the canonical lift. This is the case where the lifted curve over $\mathbb{Q}_p$ is isomorphic to the curve over $\mathbb{F}_p$, in which case no additional information can be extracted from it. The journal version of Smart's paper mentions this case.

The solution is simple: if we are hitting a special lift, randomize the lift! We can do this by lifting to the $\mathbb{Q}_p$ curve $y^2 = x^3 + (p\cdot a')x + (8856682 + p\cdot b')$, for some arbitrary $a'$ and $b'$, which reduces all the same modulo $p$, but will be unlikely to hit the same issue. So we can easily rewrite the attack as

def SmartAttack(P,Q,p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break

    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp

    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()

    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)

which now succeeds:

sage: p=235322474717419
sage: a=0
sage: b=8856682
sage: E = EllipticCurve(GF(p), [a, b])
sage: P = E(200673830421813, 57025307876612)
sage: Q = E(40345734829479, 211738132651297)
sage: assert(P.order() == p)
sage: n = SmartAttack(P, Q, p)
sage: assert(n*P == Q)
sage: n
152675955744921


Is a password cyphered by itself as secure as hash? My Question(s)

I am wondering if I have a password (long enough) and I cypher it by itself (let's ignore the salt) in this way:

cy_hash(mypassword)=cypher(text=mypassword,key=mypassword)

Then, is cy_hash as secure as md5, sha1, sha512, etc?

Also:

Is there any theoretical comparison between these methods?
Has this method ever been used in practice? If not, why?
Is there any research on this hash?

My research efforts

As for my research efforts, I have looked around and found the following Q&As:

Is it safe to encrypt a string using same string as key?
 (at StackOverflow)
how much is secure to encrypt a password using itself (as encryption key) for storing it on a unsecure media? (at Crypto.StackExchange)

but those Q&As do not answer my question. You can safely skip linking to them.

There is an important misconception on your part: in general cryptographic hashes such as MD5, SHA-1 or SHA-512 should not be used to directly hash a password. A password hash or PBKDF should be used. Examples are PBKDF2, bcrypt, scrypt and Argon2. These functions also take a salt and work factor to provide additional protection.

There are a few problems with your idea:

as noted in the comments, a cipher generally takes a key with one or more specific, pre-defined sizes;
a cipher would output a size as large or larger than the input which would leak the password size (and require VARBINARY in databases, larger buffer allocation etc.);
it is missing additional parameters such as a salt or iteration count to make it a password hash;
it would have almost the same performance as just hashing the password (it would offer no advantages, in other words).

No, there is likely little to no research as it would be dismissed out of hand. There was however a password hash competition quite recently where it could have been entered (and immediately dismissed).

Note that MD5 and SHA-1 have been broken and should generally not be used anymore.


Condition on Vector Boolean Function to be Bijective Suppose the vector boolean function be

$$\begin{align}
f:F^n_2 \longrightarrow F_2^n \\
(x_1,\dots ,x_n) \longrightarrow (x_2,\dots x_n,g) \\  \\
g:F^n_2 \longrightarrow F_2 \\
(x_1,\dots ,x_n) \longrightarrow \{0,1\}
\end{align}$$

What should be the condition on the Boolean function $g$ so that $f$ becomes bijective i.e. 1-1 and Onto?

The condition is that:

$$g(0, x_2, x_3, ..., x_n) \ne g(1, x_2, x_3, ..., x_n)$$

for all $x_2, x_3, ..., x_n$

This can easily be derived from the condition that implies bijectivity of $f$; that is,  $f(x_1, x_2, ..., x_n) = f(y_1, y_2, ..., y_n)$ implies that $x_1 = y_1$, $x_2 = y_2$, ..., $x_n = y_n$


Why are the random exponents so much bigger in the Socialist Millionaire protocol versus Diffie-Hellman key exchange? Section 8, Security considerations, of RFC3526, which defines groups used for Diffie-Hellman has a table recommending some random exponent sizes. In particular, it says:

The strength of a key exchanged using the 1536 bit group has

about 90 bits strength for a 180 bit random exponent
about 120 bits of strength for a 240 bit random exponent

On the other hand, the Off-the-Record protocol spec, which uses that 1536 bit DH group, says:

  The random exponents are 1536-bit numbers.

I'm not adhering to the OTR spec, because I'm just using the SMP part of it. But I'm interested to find out:

What is the reason to use these comparatively huge random exponents, when a DH key exchange gets what I would call "enough" strength at far lower exponent sizes? I'm interested because 240 bit random numbers make the authentication go a lot quicker.

As a bonus: how does SMP using the 2048, or 4096 bit groups with smaller random exponents compare to using the 1536 bit group with large random exponents?

For Diffie-Hellman, adequate security is achieved provided that:

we work modulo a prime $p$ big enough to resist discrete logarithm (1536 bits are sufficient);
the order of the subgroup generated by $g$ is a multiple of a big-enough prime integer $q$ ($q$ should have length $2n$ bits to achieve $2^n$ security);
the private exponents are randomly chosen in a big enough range ($2n$-bit exponents to reach $2^n$ security).

The first two conditions are necessary for the discrete logarithm to be hard. But having hard discrete logarithm is not necessarily sufficient for the security of the cryptographic algorithm which uses that group. Diffie-Hellman appears to be reasonably secure with the conditions above. However, other protocols require a bit more. A prime example is DSA. With DSA, you work in a subgroup of size $q$ (a prime integer) generated by a conventional value $g$ modulo a big prime $p$; whenever you sign, you select a random $k$ modulo $q$ (that's a "secret exponent"). $k$ must be chosen uniformly in the $[1...q-1)]$ range; simply choosing a "big enough" $k$ is not sufficient: any bias in the selection of $k$ can be exploited to rebuild the private key from the observation of several signatures (many signatures, if the bias is slight).

So your question is: is SMP more like Diffie-Hellman, i.e. tolerates that private exponents be chosen in a subrange, or more like DSA, for which uniform selection in the whole range is necessary ? Barring any explicit indication to the contrary, it is safer to assume that uniform selection in the whole range should be used. In particular, it seems to me that non-uniform selection may imply exploitable biases in the zero-knowledge proofs which are sent along the SMP values.


How many recursive md5 hashes are needed to always get same string If we start with a set of possible input values, and apply the md5 algorithm to all elements of this set and then filter out the unique results (a.k.a. filter out collision), we are left with a smaller set. Consider this small piece of pseudo code:

Set<String> inputs = ALL_UNIQUE_INPUTS;
while (inputs.length > 1) {
    Set<String> newInputs;
    foreach (String input : inputs) {
        newInputs.add(md5(input));
    }
    inputs = newInputs;
}

I believe that most iterations of the while loop will decrease the size of inputs, untill it reaches 1. Is this true?

Furthermore, can we somehow determine how many iterations this would take for a given input space?

Note: I am aware that you should not attempt to increase the computational complexity of password hashing in this manner, but use salts, reapply those and other neat tricks to make the process more computationally complex whilst not increasing the chance of collisions.

After about $2^{n/2}=2^{64}$ iterations an input will enter a cycle (of length approximately $2^{n/2}=2^{64}$). If inputs didn't collide by the time they enter a cycle, they never will.

If you have more than about $2^{n/4}=2^{32}$ inputs, you'll get collisions after $2^{n/2}=2^{64}$ iterations, as per birthday-problem. But of course you won't have the patience to wait that long.


What is wrong in the following algorithm for computing a hash function using RSA? I'm studying for a cryto exam and have run across this question which has stumped me.

What is wrong in the following algorithm for computing a hash function?

Take a message $M$,
generate a random private RSA key $K$.
Encrypt $M$ with $K$ and
take the first 240 bits of the result as a hash of $M$

Hash functions must be public, so if you want to use RSA as a hash function you should fix $K$. Now let $n$ be the RSA modulus and $H$ denote an RSA hash function. We have

$$H(M)=H(M+n)$$

so this function is not second preimage and collision resistant.
Also, this system is not first preimage resistant (with known public and private key):
Let $M^k=h \pmod n$ and $h_t$ denote the first $t$ bit of $h$, so $H(M)=h_{240}$.
Now suppose $e$ is the public key and $M'={h_{240}}^e \pmod n$. We have:

$$H(M')=h_{240}$$

So we found an inverse for this hash function and this is not preimage resistant.