Could symmetric keys be of sizes other than 2^x or 2^x + 2^y? Is this an issue for, perhaps, RSA? I wonder if a key could be any other size, say 261 bits.

Modern CPUs are typically 64-bit. This gives us a very good performance incentive to design symmetric cryptography with block size as a multiple of this.
There is a lesser (IMHO) drive for using $2^x$ bits, many parts especially in hardware will require ceil(log(length)) time/depth/gates by using $2^x$ we get more efficient implementations.
Obviously we could build a less efficient (bytes/second or bytes/$) cipher with arbitrary block size.


Does AugPake not require key stretching? I was reading the AugPAKE rfc and noticed that there is no mention of key stretching anywhere. The protocol does mention use of a hash function, and the hash function that is provided as an example is SHA2.

It appears the protocol does not utilize computationally expensive key stretching anywhere. I would like to ask how the protocol can remain secure with regards to low entropy passwords. What prevents an attacker from brute forcing the weakest link in the chain?

It seems like there must be some form of rate limiting in order to slow down the search through such a limited set of possibilities. The only mention of this I saw was the standard recommendation of only allowing X incorrect password attempts per unit time.

Could it improve security to use a key stretching algorithm such as pbkdf2/bcrypt/scrypt/argon2 on the password, or would that defeat the purpose/efficiency of the protocol?

It seems like there must be some form of rate limiting in order to
  slow down the search through such a limited set of possibilities.

There is. Due to the nature of AugPAKE an attacker can only try a single password per connection attempt with the server, meaning offline attacks against the handshake transcript are not possible. Thus if the connection-rate is limited, the search speed is limited accordingly as well, protecting even weak passwords, if something like 10 attempts per second and further penalties for bursts are implemented.

The fact that you can't guess anything from a passive view of the transcript is documented (and proven) in section 3.2.
Section 3.3 in turn talks about what active attacks can do and argues that even an active attacker can do no better than an on-line dictionary attack, which means one password attempt per connection.

  Could it improve security to use a key stretching algorithm such as
  pbkdf2/bcrypt/scrypt/argon2 on the password, or would that defeat the
  purpose/efficiency of the protocol?

It would certainly improve the security of the protocol to use a strong password-based key derivation function (PBKDF) in so far as it hardens the server's password database in the sense that a leak of the database isn't directly equal to "many, easy-to-break real-life password hashes". However this would also impose high loads on the clients of such a connection, which may be unfavourable, especially as there's no one-size-fits-all for password hashing given how different desktop computers and smartphones are, where the former needs maybe 100ms for something the latter needs 3s. This is very likely the reason why there's no such strong PBKDF in place here, as the designers decided that speed is more important than "security in case of database leaks".

This is also part of the security discussion of the document (section 3.5) which says that a protocol is secure against server compromise as long an attacker can do no better than running off-line dictionary attacks on the database.

  What prevents an attacker from brute forcing the weakest link in the
  chain?

The weakest link in the chain is the password database (which is secured using standard access control) or by the nature of the protocol, making guesses really slow and controllable.


Where I can find a list of certified software / hardware RNGs compliant to NIST SP 800-22? I need to use NIST SP 800-22 approved software / hardware to generate RSA key pair.

Where I can find a list of certified software / hardware RNGs compliant to NIST SP 800-22?

And how is the SP 800-22 related to FIPS 186-x? If I generate RSA key pair with approved software compliant to FIPS 186-x, does it mean that it is also compliant to SP 800-22?

Please refer the document at NIST site pointing to the document (800-22-rev 1a ) updated on April 2010  (http://csrc.nist.gov/publications/nistpubs/800-22-rev1a/SP800-22rev1a.pdf).

The list of special published (SP) documents are available at (http://csrc.nist.gov/publications/PubsSPs.html)

It involves some reading, but should get your answers. Since it will keep changing wouldn't paste an answer here.


Which algorithm can be performed by humans? Suppose I want my grandmother to perform encryption without any help from a computer, and she must encrypt the word 'HELLO' for me.

I could ask her to instead of typing the real keys, that she always hits the key thats on the right side of the real key. So that instead that she types HELLO, she types JR;;P. On my side I just look what JR;;P means, and I can decrypt that she said HELLO.

I am sure that she can do this. Is there an improvement possible to the scheme I just proposed, or is this the best the average human can do?

Every classical cipher can be used without a computer's assistance; while simple mechanical ciphers can fall into the "classical cipher" category, in general classical ciphers are pen-and-paper ciphers, almost all of which are more secure than your "press the key to the right of the real one." Vigenere, for instance, has flaws; however, it is much more secure than "press the key to the right of the real one," because the latter is a special case of a monoalphabetic substitution cipher (the whole class was broken in the 9th century CE), while the former is a polyalphabetic substitution cipher which was broken in the 19th century.

More recently, you have some newer schemes that can be done without the aid of a computer. Neal Stephenson's book Cryptonomicon featured as a plot point the Solitaire scheme, which requires only a deck of playing cards to implement. Solitaire has some weaknesses, but is likely better than Vigenere or other previous ciphers. More secure than Solitaire is RC4; this could be implemented by hand, but would be complicated (to ease matters, you could probably have a reduced-security version that could also use a deck of cards for the state).

Anything that's truly highly secure will probably be not realistic to implement by hand (except an OTP, but that's really hard to pull off the preconditions), because they are designed to be easy for a computer to do, and computers are good at different things than people. But there are certainly options better than monoalphabetic substitution.


Generate shared secrets using RSA Before explaining my question, please let me introduce the scenario:

There are 2 type of actors: 1 server and N clients
Each actor has a RSA 2048 bit private/public key
The server knows all the clients public keys
The clients know the public key of the server

The desired goals are the following:

Clients must authenticate themselves to the server
Integrity must be guaranteed for all exchanged messages
Secrecy is a plus but not mandatory

A solution that came to my mind is to share a secret between all server-client pairs and then proceed by sending the messages concatenated to the MAC

Server ---- M | MAC(M) ----> Client
Client <--- M | MAC(M) ----- Server

Then on top of this, a challenge-response protocol is used to guarantee the authenticity of the clients.

However, by searching online I was not able to find a "standard" way to generate a shared secret using RSA. I was only able to find DH or ECC protocols for this.

There is a well-defined scheme based on RSA to obtain a shared secret or the aforementioned goals?

What you want to do is establish a shared, authenticity guaranteeing channel assuming both sides know a fixed public key (either RSA or ECDH based) of each other.

Transport Layer Security (TLS) can do that and really should be used if possible, given that it also takes care of things like state management and replay-prevention for you. If you need a list of embedded-friendly TLS libraries have a look here and also note that TLS does offer cipher suites which only perform authentication and no encryption if the cost of encryption is unbearable to you (though many implementations don't actually have them).

Alternatively if TLS is really not an option and you have the replay-protection figured out, you can also just use RSA signatures (not to be confused with the integrity guarantees provided by RSA encryption!). This can be done either by using RSA-PSS (preferred these days) or by using RSA-PKCSv15 signatures, both of which are supported by LibTomCrypt (your currently preferred library) and guarantee that the signed message actually came from the owner of the associated public / private key and was not altered and can be verified just using the public key.

But now to the question you asked (but probably didn't mean to ask):

  There is a well defined scheme based on RSA to obtain a shared secret
  or the aforementioned goals?

The standard way to do this (and the way TLS does it) is that one side of the exchange picks a random number (e.g. 64 bytes long) and then encrypts it with the other side's public RSA key (and e.g. RSA-OAEP).

If you also want to ensure that the sender is actually who they claim to be, simply sign the resulting ciphertext and enforce signature-checking on the receiver-side.

  In addition to this how can I avoid reply attacks?

If there is a a relieable clock on the devices one could e.g. send nonce+timestamp pairs and clean nonces from the cache after e.g. an hour (assuming the nonces are covered in the signed data). Alternatively one could have the recipient send a fresh nonce and the next message must use that nonce so that only one nonce needs to be stored.

That means the first approach would mean this message format:

$$\text{Timestamp}\parallel \text{SenderNonce}\parallel M\parallel \operatorname{Sign}(\text{Timestamp}\parallel \text{FreshSenderChosenNonce}\parallel M)$$

and discard nonces from memory after one hour. Or alternatively

$$\text{ReceiverNonce}\parallel \text{SenderNonce}\parallel M\parallel \operatorname{Sign}(\text{ReceiverNonce}\parallel \text{SenderNonce}\parallel M)$$

where ReceiverNonce was transmitted as the nonce to be used on the next transmission from the receiver to the sender.


Generate one-time-pad with pre-shared key and public randomness I know very little about cryptography, so I apologize if the question does not make sense.

Let's say we design a function $F(P, X) \rightarrow K$ that takes in a pre-shared private key $P$ and a publicly available source of randomness (say a server that generates true random numbers) $X$. The output $K$ of this function is a new key that we use as a one-time-pad to encrypt and decrypt a message.

The sender pre-share the key $P$, the function $F$ and the source of randomness to the receiver before their communication. For every new message $M$, the sender collects the random information $X$, generates a one-time-pad $K$ using the function $F$ and encrypts the message with $K$. The receiver generates the same $K$ and decrypts the message.

My questions are

This scheme is not information theoretic secure, right? because AFAIK, the one-time-pad cannot be reused in any way, but in this case, we are reusing $P$ for every message, which can be considered as part of the one-time-pad $K$
Is this scheme viable? Is it more secure than simply encrypting/decrypting with the pre-shared key $P$?

You can relate your construction to the approach of using a pesudo-random function (PRF) in order to extend the key-length on the one-time-pad construction (in fact, it is more typicall to use a pseudo-random generator (PRG), but since this can be obtained from a PRF, and since your construction resembles more a PRF as well, I prefer to present it like this).

A PRF is a family of functions that resemble random functions, in a very precise way.
We say that a family of functions $\{F_s\}_{s\in \{0,1\}^\ell}$ is pseudo-random, where $F_s:\{0,1\}^n\to\{0,1\}^m$, if a function sampled at random from this set (which is done by sampling a random $s\in\{0,1\}^\ell$) is indistinguishable from a totally random function $f:\{0,1\}^n\to\{0,1\}^m$ (i.e. one were the image of each $x\in\{0,1\}^n$ is a uniformly random string in $\{0,1\}^m$).
If you have such a family of functions then you can build an "extension" of the OTP by simply using the pre-shared secret key $s$ as a seed to get a random function $F_s$, and using $F_s(0)\|F_s(1)\|\cdots\|F_s(N)$ as a (much longer) OTP key.

Now, if you think about it, when you consider your function $F(P,X)\to K$ you're sort of using this idea: you are using some shared secret randomness to expand it to a longer, perhaps not totally uniform key.
So, to answer your questions, your scheme is not information-theoretic secure but not really because you're reusing the key, but because the PRF is not really information-theoretic secure.

Remarks

Notice that, in particular, the source of randomness you call $P$ doesn't even need to be random! It only needs to ensure that the same value of $P$ is not reused among several different encryptions, and this can be achieved via a counter as I illustrate above. There is some randomness involved of course, but this is coming from the shared key.


RSA: How to compute plaintexts knowing ciphertexts, public key and relation between plaintexts I'm trying to solve an exercise where you have to compute two plaintexts $p_1$ and $p_2$, knowing the corresponding ciphertexts $c_1$ and $c_2$ and the public key, of which $e=3$, and $n$ is a large number.
Also given is a relation between $p_1$ and $p_2$. $p_2 = c_1 \cdot p_1 + c_2$. Where $c_1$ and $c_2$ are constants.

I'm guessing I should use the fact that $e$ is a low number (3) since RSA is unsafe in this case. I'm not sure where to start, how should I go about solving this exercise?

Since this is an exercise, I'll provide the links of the articles as a hint;

The linearity of the messages  is first studied when $e=3$

Low-Exponent RSA with Related Messages by Don Coppersmith, Matthew Franklin, Jacques Patarin, Michael Reitert, EUROCRYPT 1996: Advances in Cryptology — EUROCRYPT ’96 pp 1-9

A more general case, where $e$ is not limited to 3 and the relation is linear is studied in

A New Related Message Attack on RSA Oded Yacobi and Yacov Yacobi, PKC 2005: Public Key Cryptography - PKC 2005 pp 1-8.

It is quite clear that these attacks are related to textbook RSA and it must not be used in practice.

For encryption, RSA has used either PKCS#1.5 padding or OAEP. Actually, we don't use RSA for encryption. We prefer it in digital signatures and that requires PSS padding or for Key Encapsulation, RSA-KEM.


Which MAC scheme is quantum resistant? will HMAC survive Grover algorithm ? if not then which MAC scheme provide post-quantum security ?

Yes, HMAC with a sufficiently long key will survive Grover's algorithm.  Grover's algorithm breaks a cryptosystem with a $n$-bit key using $2^{n/2}$ (quantum) steps of computation.  Therefore, in practice, a 128-bit key is likely to survive Grover's algorithm, and a 160-bit key almost surely will.

So, HMAC with a 160-bit key is safe against Grover's algorithm, and HMAC with a 128-bit key is almost certainly safe enough against Grover's algorithm for most purposes -- even assuming someone figures out how to build a working quantum computer.


Sensible usecase for restricting special characters in passwords? Please See Why Not Allow Special Characters In a Password on Security.

Several websites I've come across limit the allowed special characters for a password. My thought was, it should all be hashed anyway so why does it matter?

Is there an actual security reason to restrict this?

Example error:

The password needs to be at least 4 characters.
Valid characters are: letters, numbers and the following symbols: #$%&!?@.

Summary of comments, not to take credit.

Answer so far is: cryptographically no. But it's practical for usability.

Restricting control characters is useful for different interfaces/input methods.
Restricting non-ASCII characters is useful for avoiding bugs with different encodings.
Restricting characters that are not on every keyboard adds to the user-friendly experience (preventing the user from locking themselves out on a different device).
Restricting characters that are in different locations on different keyboards prevents 'habit-mistakes' on different keyboards.
When a password is easier to remember it's less likely to be written down (in theory) see: XKCD #936: Short complex password, or long dictionary passphrase?


Does the signatures generated by a revoked member before revocation remains valid in VLR group signatures Group signatures allow any member of the group sign the message on behalf of the group anonymously using his own secret-key. Only group manager can reveal the identity of the signer.
Verifier Local Revocation (VLR) is an efficient approach of membership revocation.

In VLR group signatures, revocation-token is generated for each user and is placed in Revocation List (RL) whenever the user is revoked. VLR group signature schemes consist of three algorithms: KeyGen, Sign and Verify

KeyGen algorithm outputs public-key, secret-key for each user and revocation-token for each user

Sign algorithm generates the signature on a message using the secret-key of a group member.

Verify algorithm returns 1 if it is a valid signature that is signer is valid group member and he is not revoked. Otherwise, returns 0.

If a group member "i" is revoked then its revocation token in placed RL. Therefore, he cannot generate a valid signature.
But, the verify algorithm returns invalid for all the signatures generated by user "i" before revocation if we verify the signatures using the RL where revocation-token of user "i" is placed. Is my understanding correct?

I think it depends on the implementation of the scheme. A naive implementation might do what you've described and invalidate every previous signature of the revoked member.

However, the scheme proposed here: http://www.scitepress.org/Papers/2012/40175/40175.pdf takes a respective time $period$ into account.

Here the verification algorithm is defined as:

$Verify(gpk, j, RL_{j}, m , \sigma)$:

  This  algorithm,  run  by  a verifier takes as input a message $m$,  its signature $\sigma$, a  period $j$,  the  corresponding  Revocation  List $RL_{j}$ and the public parameters $gpk$.  It checks if the message has been signed by an unrevoked group member, without revealing the signer’s identity.  The possible outputs are valid and invalid.

As you can see, the verification check depends on a certain time period here. In this case, all signatures in previous periods would remain valid. This is especially useful because it enables to unrevoke members in a later period without having to generate a new key for that user.

So to answer your question: I think it depends on the implementation.


Changing a bit Changes Hash I am very curious on the fact that SHA, MD5 and all related Hash Functions change the output even by changing one bit in input Message. Why is that?

This is called the diffusion property, and hash functions are explicitly designed to have this property. The reason you want this property is because it makes it harder to find patterns between similar plaintexts and their hashes.

Something like SHA-1 is based on a block cipher. This essentially means that hashing involves iterating some operations over a block of data many times. Each iteration, the bits get scrambled and effect the subsequent iterations. This way, one small change at the beginning makes a large difference 80 iterations later (SHA-1 does 80 iterations)


RC2, RC4, RC5 key length While reading the Wiki page on RC4 I noticed that the key size must be in the range of 40–2,048 bits. So should I understand like this, that I can have a key that has length of, lets say 333 bits? (any decimal number between 40-2048?) How about inputs length?

Imagine that I can ask a user to give me an input length (for example, 1027) and keylength (lets say, 359) and I can use them?

Same question about RC2 - the key size must be in the range of 8-128 [bits] and RC5 - the key size must be in the range 0 - 2040 [bits].

Can I use any key length which is in the given range? Even the exotic one, like, I dont know, 879 or 123 bits as the length of the key?

Yes, you can have a key of any length of that range (as long as it is an integral number of bytes), but really, why?  There is absolutely no reason to.

If the key is uniformly distributed, anything over 256 bits is total overkill and completely pointless.
If the key is not uniformly distributed (maybe it's a passphrase or something), you should not be using it directly as the RC4 key.  Instead, you should hash it first (preferably using a slow hash like PBKDF2) and use the result as the RC4 key; and the output of the hash will be something like 128 bits or 256 bits, so again, the range doesn't matter.

Bottom line: If you need to ask about the exact range of key lengths, you're probably using RC4 incorrectly.  Instead, stick to a key that is 128-256 bits long and is uniformly distributed and generated using a cryptographic-quality pseudorandom number generator or using a suitable hash/KDF function.

Update: apparently RC2 does allow arbitrary bit lengths for its keys, per a comment from Henno Brandsma (thanks!).  However, that doesn't change the bottom line.  I would not recommend using unusual length keys.  Stick to ordinary lengths, like 128 bits or 256 bits.


Square roots, prime factorization I´m stuck in my homework and since its homework, I would rather get some hints than full solution. The problem goes:

factorize n = 88416763 in case that you know that the square roots of
51733469 (mod 88416763)
are 50224876, 38191887, 22222, 88394541.

Following CodesInChaos request to turn the hint into a full solution, here's a full solution. Let $x$ and $y$ be square roots of $51733469$ modulo $n$. It follows that

$$0\equiv x^2-y^2=(x+y)(x-y)\,(\textrm{mod }n).$$

If we choose $x\not\equiv \pm y\, (\textrm{mod }n)$, then $x-y$ and $x+y$ are not divisible by $n$. On the other hand, $n\mid (x+y)(x-y)$, so $\gcd(x+y,n)\neq 1\neq \gcd(x-y,n)$. Choosing for instance $x = 38191887$ and $y=22222$ gives

$$\gcd(x-y,n) = 8887,\;\; \gcd(x+y,n)=9949.$$

A direct computation shows that $n=88416763 = 8887\times 9949$. It's easy to use the Sieve of Eratosthenes to calculate all primes smaller than $100$ and then check if any of them divide either factor, which will show that $8887$ and $9949$ are both prime.


Fast reduction in $GF(2^{128})$ using x86 `PCLMULQDQ` Modern x86 CPUs support the PCLMULQDQ instruction, which does an XOR-multiply of two 64-bit numbers instead of an add-multiply (i.e. typical arithmetic multiplication).  This makes XOR-multiplication for $GF(2^{128})$ significantly faster.

However, it's only one half of multiplication in $GF(2^{128})$: after the XOR-multiply, you get a 256-bit result, which then needs to be reduced by the modulus (0x100000000000000000000000000000087 for Galois/Counter Mode).

How does one do XOR-division when the CPU's hardware acceleration is only for XOR-multiplication?  I thought of using the CRC32 instruction for doing the XOR-division step, but sadly, CRC32 hardwires the modulus as 0x11EDC6F41.

Basically, to (naïvely) implement modular reduction by M = (1 << 128) + 0x87, you need to:

take the upper 128 bits $x_H$ of the 256-bit (actually, 255-bit, since the high bit can never be set) PCLMULQDQ result $x = x_H \| x_L$,
shift them down by 128 bits,
XOR-multiply them by 0x87,
XOR the result with the lower 128 bits $x_L$ of the 256-bit result, and
repeat (see note below).

Step 3 could be implemented with PCLMULQDQ, but since one of the multiplicands is a small constant, it's probably more efficient to just implement it with discrete shifts and XORs.

Note that the result of step 3 (and thus of step 4) can be longer than 128 bits — up to 6 bits longer, in this case — and may thus need to be reduced a second time.  In this second reduction, $x_H$ is at most 6 bits long (and thus the result of step 3 is at most 13 bits long), so this pass is simpler to implement, and guaranteed not to overflow and require a third pass.

(Also, if you can be sure that one of the original multiplicands is at most 122 bits long, then $x_H$ is at most 121 bits long, and so step 3 cannot overflow 128 bits.  This can simplify the implementation, and in particular, makes the second reduction pass unnecessary.)

What we're really doing here, in steps 2–4, is calculating x' = x - M * x_H, where x_H = x >> 128 and the multiplication and the subtraction are both carryless.  Of course, carryless binary subtraction is just the same as carryless binary addition, i.e. XOR.  Treating it as subtraction here generalizes better, though, and also more clearly explains why this method works: we're effectively just subtracting multiples of M from the result so as to clear the upper half of it.

I have not looked at the Intel paper linked by fgrieu in detail, but I suspect they're doing something smarter and faster than this naïve reduction.  I'll let him summarize the paper, if and when he has more time. :)


Efficiently map $2^n$ unique 64-bit vectors to $2^n$ $n$-bit vectors where $n < 64$? Is there an efficient way to map $2^n$ unique 64-bit vectors to $2^n$ $n$-bit vectors where $n < 64$?

In general, no. There are:
$$ {2^{64} \choose 2^n} = \frac{2^{64}!}{2^{n}!(2^{64}-2^n)!} $$
possible ways of selecting $2^n$ distinct 64-bit vectors. This is a huge number; using Stirling's approximation of factorials, when $2^{n}$ is substantially smaller than $2^{64}$ (i.e. when $n$ is smaller than $55$ or so), this number of combinations is approximately equal to:
$$ \sqrt{\frac{1}{2\pi}} 2^{-n/2} 2^{(64-n)2^n} $$
Therefore, any generic method for doing the mapping you seek must, necessarily, use enough memory on average to accommodate that many possible combinations. For instance, if $n = 32$, then you will need a minimum of 137 gigabytes. In fact, the naive method of storing all $2^{32}$ 64-bit vectors in a sorted array, using a binary search to locate the index of a given value, will use twice as much, but if the values are sorted and more or less uniformly spread over the space of 64-bit vectors, then the difference between two successive vectors will fit in less bits (a bit more than 32) so you could, realistically, do your mapping with 160 gigabytes or so.

Of course, the argument above is for generic methods. If you know how the $2^n$ 64-bit vectors are generated, then a more efficient method may be possible. As an extreme case, if the 64-bit vectors all end with 32 bits of value 0, then simple truncation will work for your mapping.


One-way function with combination sets as output / image One-way functions generally operate on bit strings, for the input and the output.

Are there any examples of one-way functions that produce a combination set in output? Let's call this function $f$. The function would take one bit string in input, of size $p$, and would produce a combination ($k$ elements among $n$). $n$ is a power of $2$.

Concrete example of combinations set: 64 elements among 256. The size of this set is 1.9E+61 (204 bits)

I have an algorithm to generate a combination through a hash function: the hash function is used to generate a pseudo random bit string, then the bit string is split into sub-strings of size $\log_2(n)$ whose value represents the position of the element in the set of size $n$. If the value was already selected, to check the next value. If the hash function has good properties the loop will stop after some iterations.

I would like to know whether there are constructions considered as primitives for this problem.

From what I know, there's a prior art here.

The random oracle / hash function used in BLISS signature scheme hashes a certain bit string into a sparse vector (see section 4.4). And the way they do it, is similar to what you just described.

I've got an old code sample lying around you can reference, I've incorporated a few later improvements.


Is there any benefit from using SHA-512 over SHA-256 when AES just truncates it anyway? I am still not very clear on how AES-256-CBC can use SHA-512 bit keys, but I assume that it just truncates the 512bit hash down to 256bit.
In software like GnuPG and OpenPGP, is there any real benefit using a SHA-512 key over a SHA-256 key with the AES-256-CBC block cipher?

SHA-512 has both a larger internal state and a higher number of rounds than SHA-256 - which means that it provides a higher bit strength. Somewhat surprisingly it may also outperform SHA-256, as it uses 64 bit word size, which works best on 64 bit processors. You can see a good comparison table on Wikipedia

If less bits are required from SHA-512 then they are generally just taken from the left of the output (it doesn't matter which bits are used, this is just convention). There are also specialized constructs such as SHA-512/256 that use different initial values. This should be used in case the leakage of a partial hash is a problem within the specific protocol.

That said there are no attacks on SHA-256 that come close to breaking that particular algorithm, so it can still be used with some kind of confidence.

There is no such thing as a SHA-256 or SHA-512 key. SHA-2 may be used to derive keys though, for instance using HKDF. For key derivation it is best to use the hash as part of a HMAC function to create a PRF.

As deviantfan commented, CBC requires an IV. The additional output of the SHA-512 function could be used to deliver those additional 128 bits.

For GPG specifically, RFC 4880: OpenPGP Message Format specifies in section 3.7.1.1: Simple S2K:

  If the hash size is greater than the session key size, the high-order (leftmost) octets of the hash are used as the key.

This is also the method used for Salted S2K and Iterated and Salted S2K as those expand the Simple S2K function.

Note that there is a specialized SHA-512 version called SHA-512/256 standardized by NIST, which let you use a version of SHA-512 with reduced output. It uses different constants which could fend of some attacks as the start of a hash may tell an attacker something about the full hash. Obviously it therefore produces different output than (the leftmost bytes of) SHA-512. SHA-512/256 should be used instead of SHA-512 in new protocols if your target platforms support it.


X509 Cert exploit CA check Assumptions

Let's theoretically assume that a browser skips the check that a certificate it receives belongs to the stated CA (that's an exercise).

How could I exploit this in order to impersonate to a server?
In other words, if some client requests site A, and I have MitM capabilities, can I redirect the user to my evil site?

My idea

I thought about forging a certificate for my evil site, and then sign the forged certificate with another forged one of a CA that I also forge, which signs the initial certificate for me (in other words: I sign for myself).

In the forged cert, I'd state that I am site A, attach my public key and in then (hash and) sign the cert with my own made up sign key $K_s$ (let's say RSA but it doesnt actually matter).

Now I'd put $K_v$ which is the public validation key as the public key of the CA cert I forge, and attach this CA cert to the server cert.

Now, when the user requests site A, I return him my evil site with the two certs I fogred.

The browser then skips the CA check and just validates the signature with the previous CA cert public key (extracting the hash and then comparing the hashes), and it's OK.
I also assume here that the Trust Anchor check is also skipped, thanks to the base assumption.

Is my idea correct?

When you connect to a secure site the certificate validation happens. Certificate validation failure can happen when:

Fields CN or SAN dont't match the site's domains. That means that the certificate was issued for a different domain.
Invalid digital signature. Certificate has been altered.
Unknown certificate issuer, thus unknown intermediate CA or root CA.
Other common errors such expiration, revocation etc

Notice that an error here will warn the end-user via the browser. So the end-user has the power to trust a forged certificate if possible.

Now, in the case that you suggest, if the browser skips the root CA validation, it will only validate the digital signature in the certificate chain validation process, so it stops when reaching the CA Root. This means that the end-user will only validate digital signatures according to the certificate's Issuer public key until you hit the root CA, then process stops here without checking the key ring/trusted anchors.

This has happened in some crypto libraries among non-browser applications allowing an attacker to MITM a TLS session with forged certificates. Take a look at https://www.cs.utexas.edu/~shmat/shmat_ccs12.pdf


1 Billion Bit Encryption? So, browsing through YouTube, I stumbled on this video interview of John Draper (Captain Crunch), one of the first "hackers". He talks for about 3 minutes (until 27:48) about his home rolled encryption method that will use 1 billion bit keys that randomly change every 5 seconds.

My first thought is, is this guy full of crap? But, more specifically, if we have the capability to use 1 billion bit encryption (he claims an overhead of only 250kb to transport keys), why don't we see keys much longer than 4096? Other than the fact that it seems like an insane overkill.

Examining his claims about "Thundercloud":

You can use it with "any existing software, operating system, or device" (a massive amount of effort---by whom?)
Has its "own cryptographic language that is completely independent of any existing security technology" (this is a negative thing: abandoning the entire knowledge base of cryptography is incredibly stupid)
Its strength is "built within [its] proprietary design of the public and private cryptographic keys" (proprietary design is not a strength)
Those keys are 1 billion bits (125 megabytes!!!)
Those keys are "rotated randomly every 5 seconds" (a generation rate of 200 megabits per second)
Those keys are "controlled entirely by the user" (how they can generate 200 megabits per second is beyond me)
"No information is ever stored... the size of our standard encryption key is in excess of a terabyte data block" (???)
However, the above is what makes their technology so exciting---since it's transferred in the space of 200 kilobytes! (what?)
Will conform to any existing method of data storage or communication without any overhead
"Most security keys range from 128-bit to 4096-bit" (I guess the range includes both symmetric and asymmetric encryption!)
Since "most" security keys are so small, "cracking security keys in this size is fairly easy with enough computational power" (of course this is true---by definition, "enough" computational power will break computational security; that's kind of the point)
Current cryptographic technology is no longer safe: even RSA crypto was discovered to have "back doors" (yes, recently a blog post circulated showing that RSA can be backdoored if you let someone else control key generation, but that is practically a non-issue)
The system is designed from the ground-up to be impossible to breach
Every supercomputer in the world in tandem can't break it! (Neither can they break ChaCha20 with its 256-bit key, though, either......)
Adding tracking elements to Thundercloud is "technically impossible"

Needless to say, I am very skeptical. He certainly uses many technical terms, but there's very little substance. Sporting massive key sizes are a telltale sign of bullshit.

Answering your question directly: 128-bit encryption is generally considered very sufficient. Maybe it is not very sufficient: then you can pick 256-bit, whose breaking by exhaustive search is "totally out of reach of Mankind".

If exhaustive search of a 256-bit keyspace is totally out of reach of Mankind, why should you use 1 billion bit keys? Even if you built a system that could, is the massive overhead of trying to use a 1-billion-bit key really worth it? I wouldn't say so: not when 256-bit keys suffice.

Some schemes can be broken much faster than by doing an exhaustive search. For example, to get "256 bits of security," you need 15360 bits for RSA, so there's an example of needing a really, really, really large key to attain a certain security level. (Also, notice that I'm saying 15Kbits is really, really, really large. Imagine how I must feel about a gigabit!)

(Almost?) all practical cryptosystems might be broken in the near future, so we can't say that 256-bit encryption with, say, ChaCha20 gives you ironclad, unstoppable security. At the same time, though, if we somehow extended ChaCha to use a gigabit key, there's no guarantee that a new attack would necessarily be thwarted by such a large key, either. So, I don't view excessively large keys as great "insurance" against future cryptanalytic attacks.

As an update for anyone curious, today (2015 July 04) was labeled as "internet independence day" in the linked video - supposedly the launch date of "Thundercloud." The Thundercloud website (warning: autoplaying video) has not been updated, and the Thundercloud Twitter account has gone dark, so at this point, the software probably classifies as vaporware.


Proof by reduction clarification If I execute a proof by reduction using a given adversary A as a subroutine to A'. How do I know that using adversary A which can solve a given hard subproblem, is the most efficient subroutine to use to solve the larger problem that A' solves?

Thanks in advance.

in reduction you have two problems A and B, A$\leq$B means that if you can solve problem B then you can solve problem A , now in most reductions ,the level of efficiently for the solver for A that you construct is the same as B unless you add more steps. so this means you cant know if its the most efficient , it may be and it may not.


Why is this signature independent of the message? Assume that we have the following signature scheme CL Signature:

Choose a cyclic group $G = \langle g \rangle$ of order $q$.
Uniformly and randomly choose two elements $x,y \in \mathbb{Z}_q$, and compute $X = g^x$ and $Y = g^y$.
The secret key is $sk = (x,y)$, while the public key is $pk = (q, G, g, X, Y)$.
On input a message $m \in \mathbb{Z}_q$, secret key $sk$ and public key $pk$, choose a random $a \in G$ and output the signature: $$\sigma = (a, a^y, a^{x + xym}).$$

In the same paper, they ensure that $\sigma$ is NOT information-theoretically independent of the message $m$ being signed and propose an alternative that achieves this independent notion $$\sigma = (a, a^z, a^y, a^{zy}, a^{x + xy(m + zr)}),$$ where $z,r \in \mathbb{Z}_q$ are another uniformly random elements such that $Z = g^z$ is also part of the public key $pk$.
Several questions arises on that:

What exactly means to be information-theoretically independent?
Why it is not achieved by the first scheme?
What happens if we change $a^{x + xy(m + zr)}$ with $a^{x + xy(m + r)}$?

Intuitively, I think that being information-theoretically independent means that the signature reveals no information about the message $m$. Then, why the first one reveals something about the message $m$?

Note that in the first variant given a signature and knowing the public key, the message $m$ is uniquely determined. Information-theoretically dependent means what you assume it means. An unbounded adversary who can compute all discrete logs, can thus easily figure out the unique $m$ in the first scheme.
In the second variant, the message is information-theoretically hidden (even for unbounded adversaries). Note that $m+zr$ is basically „an encryption“ with a secret key $r$ (and $r$ does not appear anywhere else). So for $v=m+zr$ you can always find a suitable $r‘$ for any possible choice of $m‘$. This information-theoretically hides the message.
The problem with your modification is as follows. In the second variant a message is $(m,r)$. If you modify it to $a^{x+xy(m+r)}$ then you can open your signature to any message $m‘$ by computing $r‘=(m+r)-m‘$ and providing $(m‘,r‘)$ as the new message. This clearly will verify. Thus, your modification does not yield an unforgeable signature scheme. For the second variant of the CL signatures, however, the scheme can be shown to be unforgeable as $z$ basically commits you to the $r$ value.


How to calculate entropy of output of a PRNG Suppose the entropy of seed key is $H(n)$ which is $n$-bit long and random and the output bit length of the PRNG is $2^n$, which will be used as a long running key. Though it is obvious in that case, as output key sequence of PRNG is derived from input seed key, so entropy of output key sequence of PRNG never exceeds the entropy of the seed key. $H(2^n) \le H(n)$ in this scenario but how to prove it?

TL;DR: The applied thought process was wrong. Entropy is a function of random variables and not of arbitrary integers. The fact that the PRNG doesn't increase entropy follows from the fact that the input space is limited and there's no other input to the algorithm and thereby entropy can't be increased.

First, let's recall the formal definition of "entropy" (as can be found in the Handbook of Applied Cryptography, chapter 2.2, PDF):

  Definition The entropy or uncertainity of $X$ is defined to be $H(X)=-\sum_{i=1}^np_i\lg p_i=\sum_{i=1}^np_i\lg (\frac{1}{p_i})$ where, by convention, $p_i\cdot \lg p_i=p_i\cdot \lg (\frac{1}{p_i})=0$ if $p_i=0$.

Notation: $\lg a$ is the binary logarithm of $a$. $X$ is a random variable that takes each value $x_i$ (from a finite set if size $n$) with the correspdoning probability $p_i$.

Now let's model the $m$-bit string as the random variable $X$. The $m$-bit string can take $n_X=2^m$ values, each of which has the probability $p_i=\frac{1}{n_X}=2^{-m}$. Thereby the entropy $H(X)$ is $$H(X)=\sum_{i=1}^np_i\lg (\frac{1}{p_i})=\sum_{i=1}^{2^m}2^{-m}\lg (2^m)=2^m\cdot(2^{-m}m)=m$$ as expected.

The next step is to properly model the "PRNG". I will model it as a pseudo random generator (PRG), because I assume that's how you meant it.

  In short: A pseudo random generator (PRG) is a deterministic algorithm that takes a fixed length input and returns a longer output.

(not a full formal definition and the usual definition would restrict to polynomially sized outputs, but we don't need one here)

By this we can model our PRG $\mathcal G: \{0,1\}^m\rightarrow \{0,1\}^{2^m}$. As $\{0,1\}^m$ can only take $2^m$ states and this is the only input to the function, we know that there can be at most $2^m$ different outputs of the PRG.

If we model the PRG output as a random variable $Y$, we know that (in "best case") $p_i=2^{-m}$ for $2^m$ different $y_i$ and $n_Y=2^{2^m}$. We further know that for the remaining $2^{2^{m}}-2^m$ possible values $y_i$, $p_i=0$ holds. With this information, we can compute the upper bound of the entropy of the PRG:

$$H(Y)=\sum_{i=1}^np_i\lg (\frac{1}{p_i})=\sum_{i=1}^{2^m}2^{-m}\lg (2^m)+\sum^{2^{2^m}-2^m}_{i=1}0\cdot\lg(\frac{1}{0})=2^m\cdot(2^{-m}m)+(2^{2^m}-2^m)\cdot 0=m$$

Note that $0\cdot \lg(\frac{1}{0})$ is, by convention, $0$.

As we have modeled $Y$ using as an optimal "PRG", it may be very well the case that there aren't $2^m$ different outputs. So we can conclude with $$H(X)\geq H(Y)$$ as expected and thereby that the PR(N)G doesn't increase entropy by itself.


How is the key shared in symmetric key cryptography? Symmetric key cryptography is an encryption system in which the sender and receiver of a message share a single, common key that is used to encrypt and decrypt the message.

Is the key public or it is secret? How can the sender and the receiver both know the key?

Handing keys, in general, is known as key management.

Symmetric keys should be kept secret from other parties than the participants in the scheme. The term "secret key" is often used as a synonym for the symmetric key. The private keys for asymmetric schemes are not shared, but are of course also kept secret, as privacy implies secrecy.

The establishment of symmetric keys between parties can be performed in several ways:

(Authenticated) Key Agreement (KA)
Sending of an (authenticated) encrypted key, also known as key wrapping
Derivation from a base key using a Key Derivation Function (KDF), using other data as input, for instance, a unique number. If the derivation is performed so the resulting keys can be used in different schemes it is often called key diversification. If keys are derived in an iteration we talk about a key ratchet.
Any kind of "out of band" procedure (after random key generation),

by a previous telephone call
sending a letter
meeting in a pub (handing over a USB stick or other data carrier)

Creating a key from key parts held by different persons (key sharing schemes)
Quantum key distribution

There are other methods for establishing symmetric keys, but these are some of the most commonly used ones. The security of these schemes depends of course on the implementation.


In which situation is HMAC mandatory rather than signature? I’ve seen that the question has been asked already but this is still confusing to me.

In a digital signature, Alice sends a message M and the hash(M) which is signed by her private key. Bob recomputes hash(M) (that he retrieves with Alice’s public key) and ensures that he finds the same hash value as Alice.
Therefore he knows that the message M is coming from Alice and that M has not been tampered with during the transit. So, it looks like we get both authentication and integrity.

In the HMAC construction (or more generally MAC this is not the subject here), a shared key between Alice and Bob is appended to the hash of data. I agree that it provides also both message authentication and integrity but what does it provide more? In other words, in which situation is HMAC absolutely required?

In principle, a signature can always be used in lieu of a MAC. You use a MAC when you want the legitimate recipient of a message to be able to verify its authenticity. With a signature, everyone, including of course the legitimate recipient, can verify the authenticity of a message.

The reason we use MACs at all, instead of just using signatures all the time, is of course that MAC constructions are more efficient. Thus an answer to the question could be: when a signature is not efficient enough for your purposes.


Use of PBKDF2 when no access to HKDF? I would like to use a unique encryption key and authKey for each payload that I encrypt and authenticate via AES256 CBC with HMAC-SHA256.  I'm considering the following:

Salt = 32 random bytes, unique to each payload, stored out in the open.
MasterKey = 32  random bytes, chosen once ever, stored securely
EncKey||AuthKey = PBKDF2(MasterKey, Salt, iterations)

Where EncKey will be 32 bytes used as the encryption key to AES256CBC and AuthKey will be 64 bytes used as the hashKey for HMAC-SHA256.

From my reading on crypto.stackexchange.com I understand that HKDF is probably a better function to use for deriving EncKey and AuthKey then PBKDF2 but in the development environment I'm in (.Net) I don't have access to HKDF from an authoritative source.

Is it ok to use PBKDF2 for this purpose?  And if so, is it better to use a high iteration count (like 100,000) or a low iteration count like 1?

From my reading on crypto.stackexchange.com I understand that HKDF is probably a better function to use for deriving EncKey and AuthKey then PBKDF2 but in the development environment I'm in (.Net) I don't have access to HKDF from an authoritative source.

Discretion is the better part of valor, so more often than not it makes sense to try and use algorithms your environment provides over having to implement your own.  In this case, however, I think we have a reasonable exception; if your environment provides PBKDF2, and thus presumably HMAC, I think HKDF is simple enough that I'd say just write your own implementation of it.  The most useful source is the RFC:

https://tools.ietf.org/html/rfc5869

In particular, if your MasterKey is already uniformly distributed, section 3.3 tells you that you can skip the HKDF-Extract function (section 2.2) and implement just the HKDF-Expand (section 2.3), which is little more than a fairly straightforward chain of HMAC calls:

HKDF-Expand(PRK, info, L) -> OKM

Options:
   Hash     a hash function; HashLen denotes the length of the
            hash function output in octets
Inputs:
   PRK      a pseudorandom key of at least HashLen octets
            (usually, the output from the extract step)
   info     optional context and application specific information
            (can be a zero-length string)
   L        length of output keying material in octets
            (<= 255*HashLen)

Output:
   OKM      output keying material (of L octets)

The output OKM is calculated as follows:

N = ceil(L/HashLen)
T = T(1) | T(2) | T(3) | ... | T(N)
OKM = first L octets of T

where:
T(0) = empty string (zero length)
T(1) = HMAC-Hash(PRK, T(0) | info | 0x01)
T(2) = HMAC-Hash(PRK, T(1) | info | 0x02)
T(3) = HMAC-Hash(PRK, T(2) | info | 0x03)
...

(where the constant concatenated to the end of each T(n) is a
single octet.)


Malleable version of Schnorr signature Given an elliptic curve defined in $\mathbb{F}_{q}$ with a generator $G$ and a hash function $H_{q}(x)$ which maps $x$ to $\mathbb{F}_{q}$. A Schnorr signature variation for a data block $B$ such as:

$SigGen(s, B)$:

$m = H_{q}(s||B)$, $M = m \times G$
$c = H_{q}(P||M||B)$
$p = m + c \cdot s$
Outputs $\sigma = (M, p)$

$\text{Verify}(P, B, \sigma)$:

$c = H_{q}(P||M||B)$
Check if $ p \times G \stackrel{?}{=} M + c \times P$

What would be the implications of changing $c = H_{q}(P||B)$, removing the dependency on $M$?

The only thing I can see is that there exists one $M^{*}$ such that $\sigma = (M, p) = (M^{*}, p)$ is equally valid. But an acceptable compromise in my point of view, if one actually needs to construct a scheme that maintains a deterministic value for $c$ given $B$.

Are there any other drawbacks?

OK, I found my own answer.
A catastrophic drawback is $M = p \times G - c \times P$, by changing $c$ to any desired data block.


Why hash the message before signing it with RSA? The diagram below illustrates the process of digitally signing a message with RSA:

As diagram shows, the message is first hashed, and the signature is then computed on the hash, rather than on the full message.

Why hash the data before signing it? Why not sign the whole message? Of course, it'll save time if you sign just the hash value, but I've heard there are also security issues with directly signing the full message. If so, what are they?

In addition to the performance problems poncho already mentioned when using RSA signatures without hashing I just want to add on the security warning of poncho:
Reordering
If you have a message $m>N$ with $N$ being the RSA modulus, then you have to perform at least 2 RSA signatures as $m$ does not longer fit into $Z_N$. Let us assume that it requires $k$ such signatures and write the message $m=(m_1,\ldots,m_k)$ and the overall signature will be $\sigma=(\sigma_1,\ldots,\sigma_k)$, i.e., $k$ RSA signatures. Now without any additional measures, anyone getting to hold $(m,\sigma)$ can manipulate the message and adopt the signature by 1) swapping any pair of sub-message $m_i$, $1\leq i\leq k$ and corresponding sub-signature $\sigma_i$ or 2) dropping a sub-message and corresponding sub-signature.
As an example for swapping lets say we have $m=(m_1,m_2,m_3)$ and thus $\sigma=(\sigma_1,\sigma_2,\sigma_3)$, i.e., 3 indepenendet RSA signatures for a message consisting of 3 blocks, then an adversary who gets $(m,\sigma)$ can simply swap, for instance to $m'=(m_2,m_3,m_1)$ and $\sigma'=(\sigma_2,\sigma_3,\sigma_1)$, which is a forgery, as it clearly is a valid signature.
Existential forgery
If you do not use a redundancy scheme for messages prior to signing within RSA (textbook RSA signatures), they are susceptible to existential forgeries. Let $(e,N)$ be the public signature verification key of RSA, then one can randomly choose a signature $\sigma \in Z_N$ and compute the corresponding message as $m\equiv \sigma^e \pmod N$.
Note that given an RSA signature $\sigma$, a message $m$ and a public verification key $(e,N)$, the signature verification for the textbook RSA signature will be to check: $m\stackrel{?}{\equiv} \sigma^e \pmod N$.
Clearly, this check will hold for the forgery by construction. Observe, however, that the adversary can not control what the message $m$ will exactly be. In particular, it will be a random element of $Z_N$. However, this may be sufficient in some applications, e.g., when only signing random numbers when issuing some tokens. Applying a redundancy scheme to messages, i.e., hashing and padding prior to signing renders so computed forged signatures useless in practice.
Final Remarks
Consequently, textbook RSA signatures must not be used and instead standardized padding methods for RSA involving hashing and padding the message must be used. Then, RSA signatures provide strong security guarantees (UF-CMA security).


How can we generate a shared key from two key pairs for an ECC implementation? This is the diagram of an ecc implementation here that needs to generate the shared key, how can it be done?

The diagram leaves out something (rather assumes it implicitly), which is that you and the recipient have agreed upon curve parameters / a standardized curve with which to perform key exchange. We can derive the shared key as follows once we agree upon parameters (this method is basically elliptic curve Diffie Hellman):

Use the RNG to generate an integer $d \in \mathbb{Z}_q$ where $q$ is the order of the generator point $G$ of the curve (technically $d$ can be arbitrarily large but there's no advantage to this).
Your ECC key pair is then $(d, Q)$ where $Q = d*G$. $d$ is the private key, $Q$ is the public key. Note that $Q$ is a point on the curve.
Given the recipients public key $R$ (also a point on the curve) compute $S = d * R$. $S$ is the shared secret. (Note that if $e$ is the recipients private key that means $R = e * G$, and thus $S = d * e * G$, meaning if we send the recipient our public key $Q$ they can also derive the secret $S = e * Q = e * d * G$).

Now we have shared key material we can pass into a KDF to derive symmetric keys.


How do I find $g$ given $g^r \bmod p$ How can $g$ be derived from $c = g^r \bmod p$ ?

$g$ and $r$ are not known, but $c$ and $p$ is. And oracle can provide many $c$ but the $r$ and $p$ is always random.

I think this is somewhat related to Decisional Diffie Hellman but I am not sure where to go from there, as the $p$ is always random.

Here's a solution:

If we assume many pairs $(c_i,p_i)$, and all the $p_i$ are primes (because  often the letter $p$ is used when talking about primes, and you relate to the DLOG problem in your question where the modulus is also prime), then we can use this method:

We ignore all the $c_i$. For every $p_i$ we find one generator $g_i$ of the entire group. And then we use the Chinese Remainder Theorem to find $g$, which fullfills $g = g_i \mod p_i$ for every $p_i$. Now $g$ is a generator for every subgroup, and therefore for every $p_i$ there exists some $r_i$, s.t. $c_i = g^{r_i}$. This has nothing to do with the DLOG problem, it is just finding a generator for several groups.

But if we assume any random $p_i$, then we also need a closes look at the numbers, and we need to consider all the $c_i$ as well:

First, we need to check which $c_i$ are not coprime to their respective $p_i$. If $ggt(c_i,p_i) = a$, then we already know that $a$ is a prime factor of $g$, which is like the equation $g  = 0 \mod a$ in the CRT.
Then, instead of looking at the individual $p_i$, we look at all the prime factors of all $p_i$ instead, which are coprime to $g$. And we need to take the prime powers of those factors into account, but it's quite straight forward as well.


One-Time MAC's data block length and q When 128-bit long data blocks are unavailable for one-time MAC:

Could 64 bits be used instead?
Should $q$ then be >=64 bits? E.g. $2^{64}+5$
Can this be scaled even further downwards to 32, 16, … bits? (block size and $q$)

The few theory sources I found:

https://www.youtube.com/watch?v=OMDDvINZNnE
http://www.crypto-it.net/eng/theory/mac.html

Could 64 bits be used instead?

Yes, but it reduces the security.

Assuming that the message length is $L$ blocks, then given a valid message, tag pair, the attacker can generate a second message/tag pair that would authenticate with probability $L/q$ (assuming, of course, that $L \le q$).  By reducing the value of $q$, you're increasing the probability that the attacker would succeed.

Now, you could run it several times in parallel (using distinct random values for $k_1, k_2$ for each instance; lets example how it works.

For example, if you use a single 128 bit $q$, and your message length is $\ell$ bytes (and hence we have $L = \ell/16$), that means that the attacker can succeed with probability $2^{-132} \ell$.

In contrast, if you have a 64 bit $q$, and run it twice in parallel, and your message length is $\ell$ bytes (and so $L = \ell/8$), this means that the attacker can succeed with probability $2^{-134} \ell^2$ (note, this is always larger, even with the smaller constant factor, as we assumed that $\ell$ is a multiple number of blocks, and so $\ell \ge 16$).

Because the second case reduced security as a square of the message length, it degrades significantly faster if long messages were possible.  Whether it degrades too fast would depend on a) how much forgery probability is tolerable, and b) how long your messages are anyways.

  Can this be scaled even further downwards to 32, 16, … bits? (block size and $q$)

Yes, but you run into even faster degradation based on message length.


Are pseudorandom permutation really permutation in mathematical sense? In security, and specifically Block Cipher (AES, DES, etc), when we talk about pseudo random permutations, is the term "permutation" refer to the same meaning as in discrete mathematics. That is, the random shuffling of elements?

So let's the input of DES has n 1s and m 0s, is the output gonna be n 1s and m 0s as well?

Formally, a block cipher is a family of permutations, indexed by the key.  More specifically, let $P$ be the set of all permutations (shufflings of elements as you put it) on the set of $n$ bit strings, i.e. the Symmetric Group $Sym(\{0,1\}^n)$.  The $n$-bit block cipher $B$ is a subset of $P$.  The key specifies which element of the subset $B$ is to be used in the encryption/decryption process.

As CodesInChaos points out in a comment, you are confusing the idea of transposition of the $n$ individual bits of the input with a permutation over the set of $n$-bit strings.  Think of DES as being like a monoalphabetic substitution cipher, except instead of having an alphabet of 26 letters it has an alphabet of all $2^{64}$ 64-bit strings.  More precisely (following the formal definition above), DES is a family of $2^{56}$ different monoalphabetic ciphers, and the 56 bit key specifies which monoalphabetic cipher will be used for encryption/decryption.


Elliptic curve with non-prime generator? Suppose we need a special Elliptic curve on prime field $Fp$, for some reason, that the order of the generator must be $6*q$, where q could be a big prime, does this weak the ECC encryption? What's the possible attack vector towards this kind of curves?

I'm just a beginner in ECC, so hope this is not a silly question.

The question is a bit broad. Generating secure elliptic curves is highly non-trivial, see for example this question, which contains references to this and this paper.

Considering a black box group, the fact that it has order $6\cdot q$ does not break the DLP. What happens is that the DLP can easily be reduced to a group of order $q$ by eliminating the cofactor 6. So being a multiple of 6 does not break DLP, nor does it help.

However, an elliptic-curve group is of course not black box. In some particular cases we can use properties that reduce the ECDLP to simpler DLP's, for example in the case of supersingular or anomalous curves. These are criteria which have to be taken into consideration when choosing the curve, to make sure the corresponding ECDLP is hard.

However, cryptographic protocols rely on assumptions which are similar, but not exactly the same as the ECDLP. For example, the Diffie-Hellman assumption does not reduce to ECDLP. Therefore, we also have to choose curves in such a way that attacks on our particular protocol are avoided. There are many attacks which target an elliptic-curve-based protocols by using properties of the underlying curve. Important examples are small-subgroup attacks (very relevant here!) and twist attacks. There are many more examples.

In conclusion, having order $h\cdot q$ for a large prime $q$ and some integer $h$ is necessary to build secure elliptic-curve-based protocols. It is however not sufficient. Obtaining a secure elliptic curve of order $6\cdot q$ is possible, but you'll want to take many more properties into account before deciding to use it. This is very non-trivial, so generate your own curves with care.


AES oracle with bad S-box Say you run in to a messed up AES (128) implementation which has the s-box configured as [0x0, 0x1, ..., 0xFE, 0xFF] and where you can query a few plaintexts to get the corresponding ciphertexts.
How many queries would one need to be able to deduce the key, and how would one go about it?
This would be a chosen plaintext attack, but I fail to see how it would be done.
Thanks a lot.

Linear ciphers

If the s-box is the identity mapping, then the remaining cipher is linear.

If the cipher is linear (over $GF(2)$), then the expression for any given bit will be equal to: $$c_i = m_i \oplus m_j \oplus m_k \oplus \dots \oplus k_a \oplus k_b \oplus k_c \oplus \dots$$

For some varying quantity of and values of $a, b, c, j, k, \dots$ per ciphertext bit.

Basically, each ciphertext bit is equal to a xor of plaintext bits and key bits (and any round constants, as applicable).

Chosen plaintext attack

A linear cipher can be broken with 1 chosen plaintext attack.

Submit a block of all 0 bits as the plaintext to the encryption oracle.

Since the plaintext has no influence on the key schedule, the key bits that influence each ciphertext bit do not vary between invocations on different plaintexts. When the message is all 0 bits, then the equation for any given ciphertext bit is simply $$k_a \oplus k_b \oplus k_c \oplus \dots$$

Where the quantity and values of $a, b, c, \dots$ vary for any given ciphertext bit (round constants omitted for simplicity).

The resultant ciphertext will be equivalent to an encryption/decryption key.

It may/will not be the key that was used to evaluate the cipher, but it will work to recover the plaintext from a ciphertext, or vice versa.

To do so, simply XOR the equivalent key with a ciphertext, then run the "AES"* decryption routine without the addRoundKey step.

Proof of concept located here

*"AES" is in quotes, because AES is a standard. Once it is modified (e.g. by changing the s-box), it is not AES anymore.


Can curve25519 keys be used with ed25519 keys? Can curve25519 keys be used with ed25519?

I'd prefer to use ed25519, but there isn't a fast java version.  For my application, I'd like to use curve25519 until I can get a faster ed25519 for java.

At the very least can the curve25519 keys be restricted if some can be converted ed25519?

Trevor Perrin wrote a library doing exactly that. Explanation can be found on in the curves mailing list archives.

To convert a Curve25519 public key $x_C$ into an Ed25519 public key $y_E$, with a Ed25519 sign bit of $0$:
$$y_E = \frac{x_C - 1}{x_C + 1} \mod 2^{255}-19$$
The Ed25519 private key may need to be adjusted to match the sign bit of $0$: if
multiplying the Curve25519 private key by the Ed25519 base point
yields a “negative” Ed25519 x-coordinate, then the private key must be negated modulo the order of the base point: $a_E = q - a_C$.

See Trevor Perrin's email and the ensuing thread  for a security analysis.


Famous ideal lattices I am wondering if there exist some special rings $R$ that gives us, under the canonical embedding, some special lattices, like the root lattices, Barnes-Wall lattices, Leech lattices, ...
In more details, is there some rings $R$ such that $\sigma(R)=D_n, \,  A_n, \, BW^n ...$?

Yes, there are. The following table is taken from this paper of Ducas and van Woerden, although the results are not derived there (in the below, $p$ is an odd prime, and $n, m$ are coprime).
\begin{align*}
\mathbb{Z}[\zeta_{2^k}]&\cong \mathbb{Z}^{2^{k-1}}\\
\mathbb{Z}[\zeta_p] &\cong A_{p-1}^*\\
\mathbb{Z}[\zeta_{p^k}]&\cong \bigoplus_{i = 1}^{p^k-1}\mathbb{Z}[\zeta_p]\cong I_{p^k\times p^k}\otimes \mathbb{Z}[\zeta_p]\\
\mathbb{Z}[\zeta_{nm}]&\cong \mathbb{Z}[\zeta_n]\otimes \mathbb{Z}[\zeta_n]
\end{align*}
Conway and Sloane's book Sphere Packings, Lattices, and Groups is the canonical reference on the topic of lattices. Chapter 8 discusses "algebraic" constructions of lattices. This means two things:

Constructions of lattices as $R$-modules of a certain rank for $R\neq\mathbb{Z}$
Constructions of lattices as ideals within (the ring of integers of) an algebraic number field

Note that these things are slightly different. For example, an ideal lattice has rank at most the degree of the underlying number field (as it is a sublattice of $\mathcal{O}_K$), but there is no such restriction on the first case.
Anyway, chapter 8, section 7.3 gives a general equation for the lattice $\mathbb{Z}[\zeta_m]$, in particular its Gram matrix $A$ has $(j, k)$ entry:
$$A_{j, k} = \frac{\mu(d)\varphi(m)}{\varphi(d)},\quad d = \frac{m}{(m, k-j)}$$
They then summarize constructions of $E_6$ as an ideal of $\mathbb{Z}[\zeta_9]$,
the Leech lattice as an ideal of $\mathbb{Z}[\zeta_{39}]$ (note that $\varphi(39) = 24$).
There are a few other constructions given as well, but those are the "biggest names".
Edit:
One can further realize Craig's Lattices as ideals (again within the ring of integers of a cyclotomic number field).
Craig's Lattices are a family of lattices $A_n^{(m)}$ obtained by starting with $A_n^{(0)} = \mathbb{Z}^{n+1}$, and performing a "repeated differencing" operation.
I will not define the construction here, but notably:

$A_n^{(1)}=  A_n$ is the (primal) $A_n$ root lattice.
According to Conway and Sloane, Craig's lattices are the densest packings known for dimension $148 \leq n \leq 3000$. I do not know how/if this knowledge has changed in the last 20 years.

One can then obtain $A_{p-1}^{(m)}$ as the ideal $(1-\zeta_p)^m$ within the ring of integers of $\mathbb{Z}[\zeta_p]$. The minimal norm (which I believe Conway and Sloane uses to denote the squared norm) is not explicitly known, but can be lower-bounded (in the case that $n = p-1$, and $m < n/2$) by $2m$.
See chapter 8 section 6 of Conway and Sloane, or Proposition 5.4.7 of Martinet's Perfect Lattices in Euclidean Space.


Group for which computing inverse is hard Is there any group in which not only discrete logarithm and finding square root are believed to be hard, but also finding the inverse of a given element?

Thank you.

Not to my knowledge. However, there are braid group and other nonabelian group based cryptosystems proposed where the difficult problem is the conjugacy problem in a nonabelian group $G$, i.e., given $g$ and $h$ in $G$, determine whether they are conjugate. This means finding an $x$ in $G$ such that $$g=xhx^{-1}.$$

Clearly inverses play a key part in these systems. You can search eprint.iacr.org for some papers. One notable paper in this field is the one below:

Cheon, J. H., & Jun, B: A polynomial time algorithm for the braid Diffie-Hellman conjugacy problem, CRYPTO 2003.

None of these systems have been widely adopted, however. One of their attraction is resistance to quantum computing based attacks.


What are the implications of XORing ciphertext with plaintext? I was intrigued by this question: Does adding complexity mean a more secure cipher?
And it led me to wonder: What are the implications (if any) of XORing a ciphertext with the original plaintext message? So:

$$C=(E_k(m)\oplus m)$$

My first impression was: "That sounds like a bad idea.", but is it necessarily? Seems like something similar is being used for Propagating Cipher Block Chaining.

  "In PCBC mode, each block of plaintext is XORed with both the previous plaintext block and the previous ciphertext block before being encrypted."

This is not a correct encryption scheme because it cannot be properly decrypted. Consider $E_k$ to be the one-time pad (OTP), the key being all zeroes. Then, for any message, you have:

$$C = E_{0^{|m|}}(m) \oplus m = (m \oplus 0^{|m|}) \oplus m = m \oplus m = 0^{|m|}$$

Or consider encrypting some random string $r$, then you have:

$$C = E_k(r) \oplus r$$

Which is basically the OTP. How would you expect to decrypt that?

The PCBC mode also does not output this construct as part of the ciphertext but feeds it as input to the block cipher encryption XORed with a plaintext block.


How to adjust scrypt parameters for Moore's Law? I have been examining the scrypt paper, and I noted the claims in table 1.

  For 10 random ASCII characters, the cost at that time for scrypt set to $(2^{14}, 8, 1)$ is estimated to be $175T/yr.

Can formulae for equivalent year cost be constructed to determine the parameters as functions of time since those tests were performed?

Can formulae for equivalent year cost be constructed to determine the parameters as functions of time since those tests were performed?

Yes, but you have to make a lot of assumptions. First, though, note that the paper says:

  We caution again that these values are very approximate [...] Nevertheless, we believe that the estimates presented here are useful for the
  purpose of comparing different key derivation functions.

The estimates are not necessarily very accurate as absolute values, but only in relation to each other. They are based on numbers from 2002.

That said, there are three parameters to tweak in scrypt: $N$, $r$ and $p$. Increasing $p$ increases only the computational cost. Increasing $r$ or $N$ also increases memory use. The effect of $p$ is easiest to estimate:

Doubling $p$ doubles the time taken per try, so the attacker needs twice as many devices to calculate the same number of hashes in a year, so the attack cost doubles.

Now how much cheaper has computing power become since 2002?

A 2002 Northwood P4 had 55 million transistors while a 2014 Haswell i7 has 1.4 billion. That's about a 25x increase.
The 2002 130nm process could put about 0.38 million transistors on a square mm, while the 2014 22nm process can put 7.9 million. That's about a 20x increase.
The "doubles every two years" version of Moore's law implies a 64x increase.

Conservatively, then, you could increase $p$ from 1 to e.g. 64 to account for the increased performance/\$ potential, but that would likely increase the time it takes significantly, at least unless your implementation is parallelized (for $p>1$ the different SMix invocations can be calculated in parallel).

Increasing $N$ would be even better, because of the increased memory use – not only would the attacker need twice as many devices, but each of those would be more expensive as well. However, the effect of that is more difficult to estimate. Additionally, that may not be doable in a low memory environment, like mobile or in the browser.

In practice, I think a better approach is to set a target time and find the highest numbers you can use and still make a target time.


Is there such a thing as a hash function with a fixed size input? That seems like it would be a useful primitive. Using it in place of a block cipher in the Merkle–Damgård construction would give a variable-length hash, maybe without the tricky business with related keys? Using it to hash a key+nonce+position would give you a stream cipher. Though maybe the collision resistance we need from hashes is wasteful for a cipher?

Relatedly, why is it that block ciphers seem to be the low-level building block of choice for hashes and stream ciphers? Especially when the decryption operation doesn't seem to get used very often.

Such a category of functions is not generally used as is, but compression functions, which are close to what you describe, are (as you describe) used to build (variable length) hash functions. For example, Merkle–Damgård hashes like SHA-2 have a compression function that takes an IV (or previous block output) and a fixed size data block to generate a smaller fixed-size output.

If you want to use a compression function as a cipher you can. If you use the key as the data block input, you get a block cipher that in the case of SHA-1 and SHA-256 is called SHACAL-1 and SHACAL-2. You can then construct a stream cipher from these using CTR mode.

However, Merkle Damgård does not require a block cipher, and Damgård suggested several number theoretical problems for the compression function in A Design Principle for Hash Functions.

  Relatedly, why is it that block ciphers seem to be the low-level building block of choice for hashes and stream ciphers?

Many hashes and stream ciphers are built from something else, like Salsa20 or SHA-3.

However, it is true that block ciphers have been used a lot. Partially because everyone was looking for ways to use DES (and later AES) which was standardized by NIST. Partially because the design of block ciphers is well understood.


Security of Salsa20 with some known plaintext? Basic question- if I'm encoding a bunch of known filetypes with salsa20, will it still be secure if the plaintext header is known?

Assume that a different IV and Key are generated before each file is encrypted (or at least, it's statistically impossible for an attacker to know whether or not different files were encrypted with the same IV or key, and it's very unlikely that 2 in fact were)

I.e. the attacker will precisely know the first 64 bytes or so of the plaintext file, not the remaining mega/gigabytes, and does not have a comparison file which was likely to be encrypted with the same IV and Key

Yes, because there are no known weaknesses in (full) Salsa20.

http://www.researchgate.net/publication/226808260_The_Salsa20_Family_of_Stream_Ciphers


Order of subgroups formed by Elliptic Curves with a Cofactor In this question:

Why are the lower 3 bits of curve25519/ed25519 secret keys cleared during creation?

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

i.e. the subgroup size is
1=2^252+27742317777372353535851937790883648493 whereas the number of points in the curve itself is 8(1).

The answer then states: "This means that there are a few remaining points that have small order."

However, as stated in the answer the few remaining points are in fact 8 times the number of points in the cyclic subgroup G.

So how can one conclude that the remaining points form small order groups?

Isn't there scope for a group within the set of remaining points to be bigger than 1?

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

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

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

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

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

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

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

Group theory is your friend.


Does there exist equivalent hash function? Is it possible to find equivalent hash function? Under equivalent, i assume same input produce same output, but they have different initial integer values and/or different set of bitwise operators. Or in other words, does there exist another algorithm of hash function, but having same input->output mapping. If exist, how to find or construct such algorithm, if not exist, do we have some proof of it? For example, we have different search algorithms, they have same input->output mapping, but different properties, for example complexity. Does this analogy work for hash function?

If a hash function can be described using boolean algebra, you can transform it into an equivalent function using distributivity, commutativity, associativity, De Morgan laws, absorption, etc... Two functions will be equivalent if you can find a serie of transformations that will lead to one another while preserving the equivalence.

See:
https://en.wikipedia.org/wiki/Logical_equivalence

If you need a more complex function with flow control, whether two Turing machines are equivalent is undecidable in the general case. You might construct two functions with the same input/output mapping without being able to prove it except by testing all possible inputs, which hashing functions are designed to prevent. However, yes, you can always construct an equivalent function by yourself, by replacing subparts which are provably equivalent ($y+y+y$ becomes $y*3$) or reorder instructions when the order is commutative.


Big-Omega and small-Omega question I found this on page 538 (resp. 576) of Introduction to Modern Cryptography 2nd (resp 3rd) edition by Katz and Lindell. The third bullet point under Example A.6 says:
$$\begin{array}{l}\text{Let }f(n)=n^4+3n+500.\text{ Then:}\\
\quad\text{(…)}\\
•\;\; f(n) = Ω(n^3 \log n).\text{ In fact, }f(n) = ω(n^3 \log n).\end{array}$$
I am just looking for a high level explanation, not a mathematical proof or something, about what this means.

The first line in the quote now in the question defines a function $f$ of variable $n$. The last line is about how fast (the output of) that function grows when $n$ grows towards $+\infty$.
Both statements $f(n) = Ω(n^3 \log n)$ and $f(n) = ω(n^3 \log n)$ are about how fast $f(n)$ grows relative the function $g$ defined by $g(n)=n^3\log n$. The first statement roughly tells that $f(n)$ grows no slower than $g(n)$, while the second tells that $f(n)$ grows faster. Both statement are true, and easily shown so when we look at the definition of $f$ and $g$.
Update following comment:

The statement is strictly about the value taken by $f(n)$, not about the difficulty or cost to compute $f$. What that value represents is not stated by the notation. It's state by what defines what $f$ represents. That could be time, or effort, or memory, or the value of an integer, like an RSA public modulus; we can't tell.
"grows faster" is not really the same as "greater". Sorry, to be precise, we need the mathematical definition.

That's using a so-called (Bachmann-)Landau notation, which makes an unusual use of the $=$ sign: equality usually features transitivity. It takes some time to get used to it.
Anything more specific won't meet the "high level explanation" requirement in the question. But if we read a few lines above the question's quote in the book, or about (Bachmann-)Landau notation, the definitions are given.
It can be shown $f(n) = ω(g(n))\;\implies\;f(n) = Ω(g(n))$. That's why the sentence has $\text{in fact}$, often used to introduce a stronger or more precise statement, like: That's good. In fact, it's delicious.


Why do the non-leaf Nodes of Merkle tree need to be hashed? Given the standard Merkle Tree as shown Wikipedia. I am having a hard time understanding why Hash(Hash(Leaf A)|| Hash(Leaf B)) at the parent of A and B is advantageous over just Hash(Leaf A) || Hash(Leaf B). I understand that a hash can't be any more collision resistant than it's input, so why can't we just return the concatenation as opposed to double hashing again? Is it just to make the result a fixed size again?

The benefit of the Merkle Tree is that you store only one element, the top hash. You don't need to store any other elements to verify the data. The hash of each element is in the chain to the top hash.

In your proposal, if one needs to get A, then you return Hash(Leaf A) || Hash(Leaf B). But, wait; how one can verify it by the top hash. To verify we need to store Hash(Leaf A) || Hash(Leaf B). So there will be many elements to store. Thus, if you stick the Merkles' idea you will have the benefit.

For the comments;

The layer of hashing is necessary since we can store only one element the top hash and we can return only the intended element since the elements are on the leaf level we only need to transfer the requested leaf and path the root hash.
Some purposes: Memory verifications against fault attacks. Also, storing files on the cloud. This will prevent the rollback attack, i.e. an attacker replaces the old version of a file. The Merkle Tree enables detection with negligible false acceptance.


What's the GCM-SHA 256 of a TLS protocol? If we read the Google line information about how the cypher the https communication, it reads:

TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256

I understand it's using ECDHE to exchange keys, using ECDSA as digital signature and making the symmetric encryption with AES algorithm, using 128 bit keys. I don't know though what the GCM_SHA256 means. What is that?

I'll quickly decompose this cipher suite.

TLS - standard starting point
ECDHE - elliptic curve version of the Diffie-Hellman key-exchange using ephemeral keys (/exponents), other values for this position include RSA, DH and DHE
ECDSA - signature algorithm, used to sign the key-exchange parameters, omitted for RSA, other values include RSA
AES_128 - AES with a 128-bit key, AES_256 would denote a 256-bit key, with GCM, only AES, CAMELLIA and ARIA are possible, with AES being clearly the most popular and widely deployed choice.
GCM - Galois/Counter Mode, a modern authenticated encryption with associated data (AEAD) mode of operation for blockciphers with 128-bit blocks.
SHA256 - Secure Hash Algorithm (SHA)-256, the hash-function used as a basis for key-derivation from the master secret in the TLS protocol, as well as for authentication of the finished message. See Maarten's answer for more details.


Would requiring reciprocal signatures create a stronger Web of Trust? In this post on Cryptome it's noted that a person called Michael Vario is willy-nilly signing people's public key's and uploading those signatures. He is effectively forging a web of trust. I'm sure this kind of thing has been done before.

It occurred to me that if the public key servers could be asked to return public keys with only those signatures that are reciprocal we would perhaps have a more realistic picture of who trusts who. With this feature enabled Vario's signatures wouldn't appear in any of the keys that he's signed and his effort would be for naught.

Would this key server feature be useful?

Would we also need some additional options/messages in GnuPG to make it clear when you might be looking at an "unauthenticated" signature?

Would we also need some additional options/messages in GnuPG to make it clear when you might be looking at an "unauthenticated" signature?

Hopefully I'm not stating the obvious.

OpenPGP does not trust keys simply because lots of people have signed them. You must "set ownertrust" for the keys you have before they will be used in Web of Trust calculations.

This related answer has some good information about how the Web of Trust is calculated.

  He is effectively forging a web of trust.

Nope.

If you haven't trusted Michael Vario's key, then you have nothing to worry about. It's just spam.

If somebody you know is verifying a key by any method other than Web or Trust or verifying the fingerprint with the owner, they are using PGP wrong. End of story.

  It occurred to me that if the public key servers could be asked to return public keys with only those signatures that are reciprocal we would perhaps have a more realistic picture of who trusts who.

Perhaps this would be useful, but I personally see it as unnecessary. PGP is complex enough as it is :)

Sidenote: If you trust a key enough for the purposes you are using it for but you don't trust it enough to "put your name on", you can perform a "local signing" that will be considered for Web of Trust calculations that won't be exported to any keyservers.


Which one these alternatives using authentication and encryption will solve this multiple-user database problem? Which one these alternatives using authentication and encryption will solve this multiple-user database problem?

I'm trying to understand the field of cryptography, so I've started reading a textbook on the subject.

An exercise at the end of a chapter of authenticity asks the following:

I've got a strong feeling that the second alternative is not safe under the security policy / threat-model, but I'm not sure.

Can someone help me justify this, or give an argument on which one of the two alternatives fails?

The first one looks more complicated, but it is wrong. What you should see is that a man in the middle attack by user $B$ can replace it by $E_{pk_D}(R), S_{sk_B}(E_{pk_D}(R)), B$. Now the server will happily verify the signature, decrypt the request, and return the data to $B$ instead of $A$.

This is why in general you cannot trust that available data was only signed by one entity, and this is why in general we use sign-then-encrypt for asymmetric schemes while we tend to use encrypt-then-mac for symmetric schemes. You would not have trouble if you'd only accept signatures from one entity or from fully trusted entities, but that's clearly not the case here.


How to use cryptography to assure data integrity? I only understand assurance of integrity using a hash function. How to use cryptograpy to assure data integrity?

If I want to ask a potentially compromised server to remember a file that I don't have room to store myself, I can pick and remember a 256-bit secret uniformly at random, and compute a short—say, 128-bit—authenticator (or MAC, message authentication code) for the file under the secret key.  I keep the key on my person; I affix the authenticator to the file.

Standard MAC algorithms include Poly1305, which is very fast but can handle only one file per secret key, and HMAC-SHA256, which is much slower but can handle many files per secret key.

If, when I ask the server to retrieve my file, the server tries to fool me into accepting a file that is different from the one I stored, I can recompute the authenticator using the secret key, and compare it to the one that was stored alongside the file.  If they match, then it is almost certainly the file I stored.  If they don't match, then the file was modified.

The technical property that a MAC has is existential unforgeability under chosen-message attack: we conjecture, or prove in the case of one-time authenticators like Poly1305, that an adversary who can learn the authenticator for one or many messages of their choice has only negligible probability of finding the true authenticator themselves for any other message.  That is, we consider a game where the adversary can query you, the bearer of the secret key, for the authenticator for one or many messages of their choice; then the adversary wins if they can find, without asking you, the correct authenticator on any other message.

What if I want someone else to be able to verify integrity, without their being able to forge the messages?  For example, I want to make a promise in a contract, and publish the contract so that anyone can read it, but I don't want to let anyone else alter the contract.  I first share a public key with everyone, and then use the corresponding private key to digitally sign the contract.  Anyone can use the public key to verify the signature.  Only I, with secret knowledge of the private key, can make a signature that will pass verification.  So anyone can verify, but only I can sign.

Standard signature algorithms include RSASSA-PSS, which is based on the mathematical magic of the RSA trapdoor permutation $m \mapsto m^3 \bmod n$ for $n = pq$ a product of large randomly chosen primes, and Ed25519, which is based on arithmetic in the scalar ring of the twisted Edwards elliptic curve $-x^2 + y^2 = 1 - \frac{121665}{121666} x^2 y^2$ over the finite field $\mathbb Z/(2^{255} - 19)\mathbb Z$.

The technical property that a digital signature scheme has is also called existential unforgeability under chosen-message attack, but in the public-key setting where the adversary also has access to the public key in addition to being able to query you for the signature on any message of their choice.


Alternatives to sbox's for diffusion? Are there any other alternatives to Sbox's or SP networks to provide diffusion preferably more basic alternatives which still provide a good degree of security?

There are alternatives to an s box.  You might say that they are evolutionary extensions of the traditional s box.  But they are all very much more complex.

As you know, an s box is typically implemented as a RAM based look up table.  So for an 8 bit s box, there are 256 possible inputs and outputs, requiring 256 bytes of storage.  This is 2^8.  If you had a primitive that required a 16 bit s box, you'll need 2^16 or 65,536 lookup values.  So this would be suitable for a 16 bit processor.

If you go wider, the memory required for a look up table becomes onerous for today's processors.  (You might manage a 24 bit lookup table, but processing 24 bit words on  32 bit processor is a PITA.)  You can opt for a real time computed s-box.

Instead of a static lookup table, you perform a computation on the inputs to the real time computed s-box, and output a value determined in accordance with some formula you've devised.  It's usually some form of mini hash.  It allows s boxes of arbitrarily large width.  A good example is  The Diffusion Layer (MR) algorithm of the Whirlpool hash.  That's 256 bits wide and uses clever Galois field theory.  A passive s box would be impossible at this width.  That transformation matrix could easily be widened to 16 * 16 values creating a 512 bit s box and a Whirlpool block size of 2048 bits.  Or even more.

Another form of active s box can be implemented without the clever Galois mathematics using Pearson hashes.  An 8 bit hash output is generated per each pass over the input bits. Using a unique permutation table for each byte means that the active s box can be extended to any size.  I've successfully used this for a 2048 bit box. The penalty is 256 permutation tables, but this is easily within the capacity of a small desktop /tablet.  The security of this technique may be acceptable when used in conjunction with a good permutation and key round functions.

You'll find that any reasonably secure algorithm can be used to compute the outputs of a real time computed s-box.  There's also this question regarding similar active s boxes.  The security of a primitive doesn't just come from an s box.  Indeed Keccak has no real s box but is ostensibly secure at the moment.  And a great deal of security comes from the number of rounds, not just the complexity of the rounds.  The upshot is that it doesn't have to be dead clever to be dead 'ard.  Skein follows this principle.


For a hashing function like MD5, how similar can two plaintext strings be and still generate the same hash? When I say similar, I'm referring to the Hamming distance, the Levenshtein distance, or a similar string distance metric that measures how similar or dissimilar two strings are.

For instance, are there two plaintext strings with a Levenshtein distance of 1 which share the same MD5 hash? If not, do we know the smallest Levenshtein distance possible for a pair of strings which share the same MD5 hash? Is it even possible to determine this with certainty?

I'm asking about MD5 since it's a well-known and simplistic hash. But I'd love to know how this applies to SHA-2, bcrypt, or other common hash functions.

There's a similar question which is looking for the shortest length strings that can generate a collision, but I'm looking for the smallest string distance to generate a collision. The actual length of the source strings isn't important.

(Asking purely out of curiosity; I don't have a real-world use for this)

This answer is based on the work by AleksanderRas, although my conclusion is different.

First, to lay out a definition, a hash is a function that takes an arbitrary length input to a fixed length output. For example, MD5 takes any input and produces a 128 bit output.

A cryptographic hash is a hash function which has certain additional security properties.

Because a hash function takes an arbitrary length input and produces a fixed length output, it is guaranteed that there are some inputs which produce the same outputs. These are collisions.

Finally, the Hamming distance is the number of bits by which two inputs of the same length differ.

For any hash function, whether or not it is a cryptographic hash function, there are inputs with a Hamming distance of 2 which collide. This can also be shown by the pigeonhole principle:

Suppose that the hash function returns an n bit output.
There are 2n possible outputs.
Consider a string B which is 2n + 1 bits long.
Consider then the set of all strings which differ from B in exactly one bit. There are 2n + 1 such strings.
The Hamming distance between any two different strings in this set is 2: a 1 bit change to get back to B and a second 1 bit change to get to the other string in the set.
Because there are more strings in this set than there are possible output hashes, at least two strings must share a hash.
Therefore the hash function has a 2 bit difference collision.

It is possible to construct a hash function which does not have any collisions between strings with Hamming distance of 1. This can be shown as follows:

Consider a string B
Consider a string C which has Hamming distance of 1 from B.
The parity of B must be different from the parity of C. That is, if there are an odd number of bits set in B, there must be an even number in C and vice versa.
Therefore any hash function which directly encodes the parity of the input, such as regular MD5 with the parity bit appended, will have a minimum Hamming distance of 2.

There are less trivial hash functions than the parity one which have a minimum collision hamming distance of 2. For example, CBC-MAC is a family of algorithms which encrypts a bitstring with a fixed key under CBC mode, and returns the last block. This meets the definition of a hash function: it takes an arbitrary length input and returns an output fixed at the size of the block. Although (like all hash functions) CBC-MAC is vulnerable to collisions, it cannot have a collision if all changes occur within a single block. (This property comes from the fact that it is an encryption function and therefore a permutation, but further elaboration would be off topic) Since a hamming distance of 1 corresponds to a single bit change, and that single bit change is necessarily in just one block, it cannot cause a collision.

This should not be taken to mean that the smallest Hamming distance between collision inputs for every hash function is 2. There are functions with a minimum Hamming distance of 1: for example, the trivial hash function truncate. That is, given an n bit hash function which simply drops all but the first n bits, varying bit n+1 will (because it is ignored by the algorithm) give a collision.

So, when it comes to particular hash functions, the answer could be 1 or 2.

Others have argued that for MD5 and other standard cryptographic hash functions it will probably be 1. This is a purely probabilistic argument, but in the absence of evidence to the contrary it is a reasonable to use probability with hash functions which are designed to behave randomly.


Can anyone elaborate why KP-ABE is better than CP-ABE for television program broadcasting? I know the difference between KP-ABE and CP-ABE. I am not able to understand why   KP-ABE is better for broadcasting than CP-ABE ?

Let's say if we want to encrypt a cartoon musical movie, and it can be watched by children users:

In KP-ABE, we can encrypt the movie with attribute cartoon and musical, and then generate a secret key with attribute structure cartoon AND musical for children users.

In CP-ABE, we have to think in the way that only users attributed with cartoon AND musical can decrypt, and then generate the secret key with attribute cartoon and musical for children users.

Although both encryption works, KP-ABE is more intuitive for broadcasters, because we only need to encrypt the movie with its types during production. Besides, it is also more flexible because we can add new users with personalized types without re-encrypting the video.