Should we use IANA groups 14 (MODP), 25, and 26 (ECP)? By looking at SonicWall Knowledge Base article Key exchange (DH) Groups Supported - Site to Site VPN:

It appears that our firewall supports DH group 25, and 26. Almost everywhere I've seen, they've recommended DH group 20-24 (we don't have DH group 24).

Should we use these groups? I don't understand how the ID of the DH group could be higher - using the same elliptical curve primitive - but use a 224-bit algorithm compared to our current 521-bit algorithm for DH group 21.

DH group 21 is also "only" a 512 bit algorithm compared to DH group 14, which is a 2048 bit algorithm. However I read that DH group 21 is still better than 14, because it uses elliptical curve.

EDIT: I've had a technical response vs a mathematical one below. It's appreciated, but a technical one helps me understand more given that we're configuring firewalls. The response is

"This group number is decided or is given by the IANA (Internet Assigned Numbers Authority).

The reason for these lower bit ECP groups to have the higher DH group number is that, the practical implementation (using a software code or a hardware chip) of the key creation and exchange mechanism was only available (or working) for 256, 384, 521 bit sizes. and that's why they were implemented  first (in-order group 19, 20 and 21).

with improvements in technology and the methods with which we write the software code or create hardware chips, it allowed us to have working models for 192 and 224 bit  Random ECP DH group and hence these were assigned a DH group number later.

Security wise, the 521 bit Random ECP group (DH Group-21) would still be on a higher side compared to 192 or 224 bit ECP group."

It appears that our firewall supports DH group 25, and 26. Almost
  everywhere I've seen, they've recommended DH group 20-24 (we don't
  have DH group 24).

  Should we use these groups?

NO, stick to groups 19-21 if possible!

According to the linked resource, DH group 25 is a prime-based 192-bit elliptic curve and group 26 is a prime-based 224-bit elliptic curve. These provide a security level of 96 and 112-bit respectively, that is the best known attack will require about $2^{96}$ or $2^{112}$ curve operations. I suppose these curves were standardized as enough people complained they can't computationally or by bandwidth or storage afford to use group 19 and the probably did so after 19-21 were standardized.

Now compare this to the groups 19, 20 and 21 which use 256-, 384- and 512- bit elliptic curves which respectively offer 128, 192 and 256-bit security. This is much better at a minor cost of performance. If you really can't afford to use these groups for performance reasons, then the 224-bit group should be fine, as its security is comparable to 2048-bit classic DH / RSA and the 192-bit group is risky as its security could be broken by a sufficiently determined attacker with sufficient funding, usually this is attributed to nation-state attackers.

  DH group 21 is also "only" a 512 bit algorithm compared to DH group
  14, which is a 2048 bit algorithm. However I read that DH group 21 is
  still better than 14, because it uses elliptical curve.

Group 14 uses classic finite-field diffie-hellman, i.e. $g^x\bmod p$ for a 2048-bit prime $p$. Because this operation exposes so much structure, there are attacks that are more efficient than the generic ones, which is all that works against elliptic curves. These attacks are so good, that a 2048-bit prime modulus for DH has roughly a 112-bit security level, which roughly corresponds to a 224-bit elliptic curve, e.g. group 26.

Also note that due to these more scalable attacks, group 1 is actually breakable, even by academics and group 2 which has a 80-bit security level due to its 1024-bit modulus has a decent chance of being breakable by a determined attack with sufficient funding. Also due to the nature of these attacks, it is sufficient if the attacker once does one big pre-computation for the parameter set and can then break individual DH instances very easily, think 1 week of pre-computation to solve each instance in 90 seconds afterwards.


Use cases for “online” authenticated encryption? What is the the point of an "online" mode for an authenticated cipher?

I understand what "online" means in this context. However, I have trouble coming up with applications that would benefit from such a feature.

Usually, the "messages" that are encrypted and authenticated are not too long and I think that this is due to people not wanting to decrypt "big messages" completely only to throw them away if the tag is finally invalid. So, at least for network protocols, it seems like a very good idea to insert authentication tags more frequently.

But this strategy makes the "online" feature of some AE implementation seem irrelevant especially since support for online modes makes the implementation more complicated.

The usefulness of online AE (locally):
Assume you wrote a program that encrypt arbitrary files. Now further assume the user wants to view a movie, encrypted with this tool. The tool can now use the online-property to stream the movie in real-time as it uses online-encryption.

The usefulness of online AE (programatically):
Assume you want to process sensitive data. If your cipher supports online AE it can wipe the data after having written / read it an thus presents less attack surface.

The usefulness of online AE (network related):
Assume you stream a movie. You can now use the online AE feature to minimize the RAM needed (and thus give more RAM to the video decoder) and you can present the user with better loading times.

All in all:
Online-AE reduces memory usage and latency for applictions.


SIV - Synthetic IV - S2V Construction? Benefits over a MAC or Hash? Looking at the SIV construction in rfc-5297 - https://tools.ietf.org/html/rfc5297

With regards to the generation of the SIV, using S2V construction, I am struggling to find the benefits of the chosen method of combining MAC codes together and has some questions I am struggling with:

What benefits does the doubling and xor provide over say a modern MAC and/or Hash function?
For example, if you used the following, how does the security differ?

$MAC( MAC($x$0), ... MAC($X$i)) $
instead of

dbl_Xor( MAC($x$0), ... MAC($X$i))
Where xi represents of your header inputs for 0 < i < blocksize-1.
Looking at the choice of a MAC, the proof works if its a secure-PRF. The authors choose CMAC and list that alternative could be used under different circumstances. There are many discussions on this forum on cipher versus non cipher based MACs and the differences mostly come down reducing the number of components you need to trust. Given this, for a SIV construction could you use a modern hash for the MAC instead of CMAC? say SHA3 or Skein-MAC (which is based off a tweakable cipher as well). ?

Thanks and regards

Rogways's paper on the algorithm goes deeper into detail: http://web.cs.ucdavis.edu/~rogaway/papers/keywrap.pdf and discusses more about design rationale and provides proof (more than the RFC).

I find a lot of benefits in SIV and S2V. For me, the most important is that it can be used without nonce. The second most important is that the mode builds on widely available modes of operation, but on the other hand just using single 128-bit cipher (typically AES, just the forward cipher function). If the implementor has some SW crypto library or FIPS 140-2 validated cryptographic module available, chances are that those have AES-CTR algorithm and AES-CMAC algorithm (if they have AES-CBCMAC or AES-CBC then AES-CMAC can be built easily).

But the question was not about these benefits. So I address the questions:

Answering the first question

The operations doubling and xor in S2V construct are primarily intended to be easy to implement yet sufficiently secure. Thus,

$MAC( MAC($x$0), ... MAC($X$i)) $

instead of

dbl_Xor( MAC($x$0), ... MAC($X$i))

invokes the MAC function one more time. For typical amounts of segments in S2V this is for many implementations a slow down.

The most typical amounts of input strings to S2V include:

Plaintext or authenticated data without nonce
Plaintext or authenticated data with nonce; or plaintext with additional authenticated data without nonce
Plaintext and additional authenticated data with nonce

Because the designers wanted a function that can easily handle any of these cases, they designed S2V, which can handle any of these cases and more. It is common that additional authenticated data is factually combination of multiple separate fields and thus it can be seen as nice convenience that it can be fed to S2V as multiple separate fields rather than needing to specify format that combines the fields.

Answering the second question

The SIV mode generates 128-bit IV for AES-CTR and authentication tag with the S2V algorithm. Therefore, perhaps the most prominent benefit of alternative MAC algorithms, larger tag size, would not be realized with SIV mode. Currently many modes of additional authenticated encryption aim at simplicity to have their design depend on as few underlying ciphers and other components as possible. Using separate algorithm for MAC would go against that goal.
Additionally, similar pre-existing algorithms like AES-CCM (not cipher misuse resistant, but otherwise for many of same uses than SIV-AES) already require just one 128-bit block cipher and use only forward function.


Why doesn't the formula work when checking two ECDSA signatures? There are two generated ECDSA signatures

X - Private key

S  = ((Z  + (X * R)) / K) mod n

S` = ((Z` + (X * R`)) / K`) mod n

G - Base point, of order n;

R  = K  * G
R` = K` * G

Why is this formula not working?

C = K - K`

R = R` + (C * G)

Where exactly do I make a mistake?

In ECDSA, the R value in the signature is not the elliptic curve point $kG$, but instead only its x-coordinate, that is, an integer.

So, what do you mean by R' + (C*G)?  In particular, what do you mean by the operator +?

If you mean "the + is an integer modular addition, that is, we take the x-coordinate of the point $CG$, and then add it (modulo $n$) to $R'$", well, that'll give you an integer that's unrelated to $R$ (as $R$ and $R'$ are related as elliptic curve points not integers, and integer addition and elliptic curve operations have little to do with each other)

If you mean "the + is an elliptic curve addition, that is, we find one of the points with x-coordinate $R'$, and add it (using the elliptic curve addition operation) to the point $C\cdot G$), well, that'll work half the time; there are (usually) two elliptic curve points with x-coordinate $R'$, and it'll work if the one you pick just happens to be the original $R'$ point.


RFC3447 OBJECT IDENTIFIER semantic http://tools.ietf.org/html/rfc3447#appendix-B.1

id-sha256    OBJECT IDENTIFIER ::= {
      joint-iso-itu-t(2) country(16) us(840) organization(1)
      gov(101) csor(3) nistalgorithm(4) hashalgs(2) 1
  }

How to read this definition? In another word, how to convert this into a bit stream? Thanks.

Check out the notes of paragraph 9.2 of that document, it lists all the encodings in hexadecimal values. It does so for PKCS#1 v1.5 padding for signature generation, but it certainly contains the OID's internally - 06 LL { OID } where LL species the length of the BER encoded OID:

For the six hash functions mentioned in Appendix B.1, the DER
encoding T of the DigestInfo value is equal to the following:

  MD2:     (0x) 30 20  30 0c  06 08 2a 86 48 86 f7 0d 02 02  05 00  04 10 || H.
  MD5:     (0x) 30 20  30 0c  06 08 2a 86 48 86 f7 0d 02 05  05 00  04 10 || H.
  SHA-1:   (0x) 30 21  30 09  06 05 2b 0e 03 02 1a 05 00  04 14 || H.
  SHA-256: (0x) 30 31  30 0d  06 09 60 86 48 01 65 03 04 02 01  05 00 04  20 || H.
  SHA-384: (0x) 30 41  30 0d  06 09 60 86 48 01 65 03 04 02 02  05 00 04  30 || H.
  SHA-512: (0x) 30 51  30 0d  06 09 60 86 48 01 65 03 04 02 03  05 00 04  40 || H.

I'll add SHA-224:
  SHA-224: (0x) 30 2D 30 0D 06 09 60 86 48 01 65 03 04 02 04 05 00 04 1C || H.

where || is concatenation and H is the hash value.

The ASN.1 syntax is officially defined in

ISO/IEC 8824: Information technology - Abstract Syntax Notation One (ASN.1): Information object specification

and the BER/DER method of encoding that is applied is specified in

ISO/IEC 8825-1:  Information technology - ASN.1 encoding rules: Specification of Basic Encoding Rules (BER), Canonical Encoding Rules (CER) and Distinguished Encoding Rules (DER)

And the OID encoding is in paragraph 8.19 for the 2010 version of that document (an errata exists). How to actually encode it is explained in this answer on StackOverflow


Favor hash size or field size when systems are disparate? I'm working on an implementation of Krawczyk's Hashed MQV (HMQV). I'm using Crypto++, which is a C++ library.

C++ has some features where classes that represent the crypto objects can be combined even if they don't have matching security levels. As an extreme example, imagine a P-160 curve is coupled with SHA-512. Or imagine B-571 coupled with MD5.

In the case where the field size and hash size are disjoint, which should I prefer when implementing the protocol? Should everything be based on the field (and field elements) sizes effectively using truncated hashes? Or should it be vice-versa? Vice-versa would include the field size being larger than the hash, with the values being 0-filled at the MSB as required.

I should also qualify the question with: there is no standardization of the protocol, and there is no reference implementation. The protocol is often only described in a paper. This issue shows up more often than it should. Its one of the differences between theoretical and practical crypto.

MQV has been standardized by IEEE P1363 (specified in P1363 2000, and amended in P1363a 2004), but it does not involve hashing, and therefore can't provide an answer to the OP's question. HMQV standardization proposal has been submitted to IEEE, but it does not contain the specific details that @jww is asking for. I went through the relevant P1363 docs and have not found answers to the @jww's questions. If you think that those details (acceptable hash functions for HMQV, mapping between them and the allowed curves, method of conflict resolution if hash output size is greater or smaller than L) are provided there (and I just missed them) - please be so kind and post the exact reference (document name/number and the page number) here.

Now, since I did want to find the answer, and since Hugo Krawchyk is the author of HMQV, it seemed best to ask him directly. Here's what Hugo replied:

  I assume the question refers to the hashing that results in the values d and e.

  Let L denote log_2(q) where q is the order of the group.

  There are two choices for the length of d and e.
  They may be of full length L in which case I would take the output of the hash  and reduce it mod q (resolving the issue of longer hash values, but truncation to L bits would also work).
  Or, you can follow the optimization used in the HMQV paper where e and d are of length L/2, in this case the hash value is to be truncated to L/2 bits.

  I would note that this L/2 optimization does not buy you anything if you optimize the multi-exponentiation to compute sigma in HMQV. Such optimized multi-exponentiation will cost the equivalent of 1.16 exponentiations even with a full size (i.e., L) values d and e. In this case I would not recommend using L/2 length for d and e but rather the full size L.

  If the length of the hash is less than L but more than L/2 you can just use the output as is for the values d and e. But I would not recommend to use a hash function with less than L bits of output and definitely not one with less than L/2.

  Hope this answers the question.

From the above I conclude:

In your C++ code use the field element size (or rather the order of the group) as the decisive factor, and match/measure the supplied hash function against it.
If the hash output size that your caller provided is at least as big as L, use it and truncate its output if/when needed.
If the hash output size is less that L, probably still allow it (maybe the caller did know what he's doing) as long as it is greater than L/2.
If the supplied hash is smaller than (or equal to) L/2, refuse to instantiate the object and throw an exception.

This approach should apply to FHMQV as well.


Generation of random data for EME-OAEP I'm using my own code to communicate with another party that's specified PKCS#1 V2.1 EME-OAEP encoding, with SHA-1 as the hash function.

There are two places where random data is used in encoding a message:

A 20-byte seed which is passed to Mask Generation Function.
A variable amount of random data which left-pads the message, when the message is shorter than the block.

For these uses, is it OK to use an operating system rand function, which is probably a weak LCG; or should I use a CSPRNG such as ISAAC (which will have been seeded from the weak LCG)?

Use HKDF to generate your random data with inputs of your private key, the message being signed, and whatever entropy you do have available (such as a real-time clock value or other time stamp).

This way all random values you produce will be completely unpredictable to anyone without your private key, and will change with each message even if you have zero effective bits of additional entropy available.

Also, move away from SHA-1 if you can; it provides <70 bits of effective security when used in signatures, and you'll have interoperability issues in the near future without SHA-256 if you're also using any standardized protocols such as TLS.


Ensuring CSRNG integrity in reduced range I recently answered a question on Code Review: Resizing a discrete uniform CSRNG distribution and I was challenged to offer a proof for one of my suggestions, and I can't find one, possibly because I don't know how best to describe my suggestion.

As background, there is an (assumed) CSRNG RNGCryptoServiceProvider available that returns random bytes in the range [0, 256).

The objective is to return random values in a limited range [0, limit) where limit <= 256.

My suggestion is to:

- allocate a variable to store the previous value generated
- add a random value to it (from the CSRNG)
- modulo the result by the limit
- store the result to be used in the next request
- return the result

In my words, this returns a series of integer values where the differences between each is guaranteed (to the limits of the base CSRNG) to be uniformly distributed. Any modulo bias in the result is only relative to the previous result (not relative to 0).

In code (C#), I proposed:

private static IEnumerable<int> RandomWrap(int chunkSize, int limit)
{
    int prev = 0;
    foreach (byte b in RandomBytes(chunkSize))
    {
        prev = (prev + b) % limit;
        yield return prev;
    }

}

Does this code preserve the integrity of the CSRNG source? Can I prove it? Is there a reference I can use?

There are two cases to distinguish:

Either the limit (let me call it $\ell$) divides 256. In this case, your method gives indeed random numbers in the appropriate range, but one can do better: simply pick a random byte $b$ and return $b\bmod \ell$.
Either $\ell$ does not divide 256, and you have an issue.

Let me develop a bit on this issue. Your assumption was that using your method, each value would be biased, but with a bias depending of the previous value, which you assumed to be uniform. However, this does not quite work, for two reasons. First, your previous value is not uniform, as your first value is 0, so you cannot assume that the bias will be "uniformly spread". But even more, assume your previous value is uniform; then it does not solve the issue at all. Indeed, what you want from your random-looking sequence is that each value looks random even given the previous values. This is very important, it is fairly trivial to generate a long sequence of integers so that each integer taken independently look random, but the sequence is clearly not a random-looking sequence.

So, by adding the previous value to your byte before reducing modulo $\ell$, you do not solve the problem: there is a bias, which depends on the previous value, which you should assume is available to the adversary.

Let me restate the classical solutions that provably work:

You can take $b$, and if it is lower than $\ell$, keep it, otherwise drop it and take the next byte. This is the rejection sampling.
You can take a sequence of, say, 9 random bytes, parse them as a random 72-bit integer $n$, and compute your output as $n \bmod \ell$. This gives you a distribution statistically close to uniform over $[0, \ell-1]$, with a bias bounded by $2^{-64}$, as $\ell$ is lower than $2^8$.


Why is AES resistant to known-plaintext attacks? At least it's my understanding that AES isn't affected by known-plaintext. Is it immune to such an attack, or just resistant? Does this vary for chosen-plaintext?

A known-plaintext attack (i.e. knowing a pair of corresponding plaintext and ciphertext) always allows a brute-force attack on a cipher:

Simply try all keys, decrypt the ciphertext and see if it matches the plaintext.

This always works for every cipher, and will give you the matching key. (For very short plaintext-ciphertext pairs, you might get multiple matching keys. Then you need to try more pairs to eliminate the wrong ones).

If you have no known plaintext, only the ciphertext, you can do it similarly, but you also need a function which says whether what you decrypted is a plausible plaintext.

The problem with try all keys is that for every modern cipher (i.e. key sizes of 128 bit or more) the key space is that large that you need much more time than the remaining lifetime of the universe to check a significant portion of all keys.

So, the question is, are there any attacks which are faster than brute-force?

For now, there seem to be some attacks which are slightly faster (like needing only $2^{125}$ steps instead of $2^{127}$ for brute-force, a bit better for the 256-bit-key version) and needing either a really large amount of chosen plain- or ciphertexts (and knowing the result), or even larger amounts of known plaintexts. These are still not practically doable in our world.

There are no proofs that AES (or any block cipher) is really secure, only the heuristic "many smart people tried to break it and until now, nobody was successful" (or at least, nobody who succeeded told the public).


Fault attack on RSA-CRT I am trying to understand fault attack on RSA-CRT, and I found some example, which I don't know how to solve it.

I know public modulus $N$, public exponent $e$, a value of faulty signature (where one of the two partial signatures was incorrect) and the value of correct signature. The message $m$ is signed by RSASSA-PKCS1-v1_5 (signature transformation is RSASP1).

I have already read the documentation of RSASSA and RSASP1, and I have also read some articles about how to attack this problem. However, I don't understand how to get a message which I need for calculating $p$, because I should get $p = \operatorname{gcd}(\text{faultySignature}^{exponent} - m, N)$

Could someone help me?

In order to have a successful fault attack on RSA-CRT, you need to work with known values of $e, N$ and of the message $m$, but you should be knowing them already, since you cannot verify the signature without knowing these values.

So, at first you should be knowing the public key of the signer: $(e,N)$. Then the signer signs a message $m$, which you should know in order to verify it. But if the signer instead issues a faulty signature, you can try and recover its private key as you said using the following method.

You can first recover the value $p$ as you mentioned using
 $$p = \operatorname{gcd}(\text{faultySignature}^{e} - m, N)$$
once this is done, you can get the second prime $q$ by dividing $N$ by $p$:
$$q=\frac{N}{p}$$
and you can finally compute the value $d$ by computing $\phi(N)=(p-1)(q-1)$ (assuming we are working with a 2 prime factors RSA modulus) and by finally computing $$d=e^{-1}\mod{\phi(N)}$$

Now, when using RSASSA-PKCS1-v1_5, what you are signing is not directly the message, to avoid the malleability issues and such, but instead the padded hash thereof. You can see the exact process of deriving the signed hash from the message in RFC3447 section 8.2.1 and following. But basically, what you need to do is to:

Convert the message M into its encoded form of length k octets EM = EMSA-PKCS1-V1_5-ENCODE (M, k).
Convert the encoded message EM to an integer which can be used with RSA: m = OS2IP (EM)
Use this integer value m as being your value $m$ in your computations.


Encrypting a short phrase into two keys. both with length of 32letters It doesn't need to be crazy secure. I wanted to figure out if there's a popular practice when encrypting a short phrase (less than 32 letter long) into two keys (two strings 32 length). Doesn't need to be complicated. It's for a hobby project.

For example:

Key 1: JFHEL1J2J1KD1FK4J4K3LA5D7EKSJX323
Key 2: 1HFK6SJDHG2JEK3DHG5NRJG9HE5K3GJEH
Combined result: Hello World!

So in other words, if two keys get combined, it reveals a sentence. I suppose a simple mod/hash could work, but do you guys know of anything fancy?

As Ricky Demer mentioned, the Shamir Secret Sharing Scheme is information-theoretically secure ("crazy secure") and also, for the "trivial case" of "all shares are necessary to recover the secret", very simple.

We add all the shares together with "non-carrying addition", and the sum is decoded into the decrypted message.
There are a huge variety of ways to "add" the shares, all of which are information-theoretically secure.
The most popular seem to be

non-carrying base 26 sum, aka Vigenère cipher variant Beaufort
non-carrying base ten sum
non-carrying base 2 sum, aka XOR, aka Vernam cipher

One example: Sum three shares using using Vigenere sum, with A:=0, B:=1, C:=2, D:=3, etc.:

ymunl buxee -- share 1 from Alice
htous qrgph -- share 2 from Bob
czdel fdoss -- share 3 from Trent
-----------
HELLO WORLD -- total

(If your phrase was less than 32 letters long, perhaps you could pad it out to 32 characters with Xs or Zs).

Another example: Sum three shares using non-carrying base sixteen, with A:=ten, B:=eleven, etc.:
(using /dev/urandom and some other random number generator)

f 8 1 2  6 4 4 0  0 2 9 7  d 7 1 6  9 a e b  6 5 5 e -- share 1 from Alice
0 1 2 3  4 5 6 7  8 9 9 9  9 9 9 9  9 9 9 9  9 9 9 9 -- share 2 from Bob
5 f 3 0  c 3 c 5  e 4 0 0  f 7 c 0  5 f f 8  7 6 4 a -- share 3 from Trent
----------------------------------------------------
4 8 6 5  6 c 6 c  6 f 2 0  5 7 6 f  7 2 6 c  6 4 2 1 -- total

48  65   6c  6c   6f  20   57  6f   72  6c   64  21 (paired up)
 H   e    l   l    o        W   o    r   l    d   ! (decoded using ASCII)

(If your phrase was less than 16 characters long, perhaps you could pad it out to 16 characters with 0x20 space characters or 0x00 null characters, giving 32 character shares).

EDIT: Oh, you're making physical objects, rather than sending text messages?

When making physical objects to encrypt some short phrase,
I think that visual cryptography is a lot more fun.

The visual cryptography system described by Dirk Rijmenants
can be done with ink on normal transparency paper, or holes drilled through metal,
to do the XOR operation.
(Is there a way to make the leftover "random background" less distracting ?).

The visual cryptography system used in the "amulets" of Henry Segerman
uses linearly polarizing filters to to do the XOR operation.

Perhaps a tiny bitmap font would be useful.
a b c d e f g h i k


Use MDC to provide origin authentication for public key encryption? Why can't we use an MDC (“Manipulation Detection Code”, as also handled in this Q&A) to provide origin authentication when using public-key encryption?

Public key encryption uses a public key of the receiver; anybody can encrypt. So origin authentication would only work if you'd also have a shared secret key (in which case the whole public key encryption becomes kind of useless) or a private key (in which case you'd probably use a signature or an authenticated key agreement protocol).


Deterministic nonces in CTR mode I want to encrypt a file with AES in CTR mode. I have a 256 bit master key and the file. Given these, the encryption must be deterministic, so I can't use a random nonce in the usual way. Fortunately the master key will be unique¹.

My original plan was to simply set the nonce to 0. Assuming no collision happens when deriving the 128 bit AES key from the master key, this should as secure as conventional CTR, where the nonce is prepended to the message.

An alternative plan is to also derive the nonce from the master-key. This seems to offer two advantages:

It makes key-nonce pair reuse more unlikely, since now they have 256 bits and not just 128
It prevents some kinds of known-plaintext attacks, since the attacker now doesn't know the content of the counter-stream, effectively turning the nonce into some kind of secondary key.

Is there a problem with either scheme? Is the second scheme better than the first?

¹ assuming the 256 bit hashfunction I use is collision free

Assuming that you can indeed guarantee that the keys will never be reused, both schemes should be secure.

The only requirement for the nonce in CTR mode is that it must be unique (and, if used directly as the initial counter value, not equal to any intermediate counter value used in the past or in the future).  If you're only encrypting one message with a given key, the nonce $0$ is as unique as any other.

As you correctly note, your second scheme provides somewhat less information to an attacker who can guess some of the plaintext.  (Reading between the lines in your question, I'm assuming you're not planning to store the nonce along with the ciphertext, but to re-derive it from the master key on decryption.)  Whether it's "better" is hard to say — it only makes a difference if the cipher you're using is broken, and at that point it will depend on just how it's broken — but it's at least unlikely to be worse.


Can I compress $192$ byte key into $16$ or $32$ bytes which can be later used in KDF to recover full key I have a key $k$ which is $192$ bytes long. Is there a secure way to first compress this key into $16$ or $32$ bytes, but in such a way that later given those $16$ ($32$) bytes I can use a key derivation function in order to recover the full $192$ bytes $k$?

No, there is no way (secure or otherwise) to compress a random $192$ byte value into something smaller; it is impossible to encode $2^{8 \times 192}$ bit possible settings in only 32 bytes (or $191$ bytes, for that matter...)
Some exceptions:

If those 192 bytes were nonrandom, that is, the vast majority of those 192 bit settings were impossible, you may be able to encode which possible setting into 32 bytes; this would imply that, out of the $2^{1536}$ possible values of those 192 bytes, only $2^{256}$ were possible, then you could do it.  The only plausible way I can think of where this might happen is if the 192 bytes were some sort of public or private key, derived from a much smaller 32 byte seed (and you just store the 32 byte seed, and rederive as necessary).

If you don't mind a large probability of failure; if you don't mind a failure $99.6\%$ of the time, you could trim it down to $191$ bytes.  However, this really doesn't scale to getting things down to the $32$ byte level you're interested in.

If you don't care about the specific value of the $192$ bytes key (only that it was generated 'securely'), then what you can do is pick a $32$ byte secret seed, and use a KDF to expand it into the full $192$ bytes.  This would work; however from your question, it doesn't sound like that's what you're asking about.

BTW: if you ask about a 'secure' method, you need to define what you mean by that.  What operation(s) to do need to be difficult for an adversary?  In this case, there is no method (and so the question is moot), however in other contexts, it would matter.


What are the requirements of a nonce? Sometimes I read that a nonce has to be a random number but I disagree. A nonce just can't repeat itself. You could increase in by 1 every time if you are sure it would never repeat.

Yes, a nonce is a number not used more than once. In its purest sense there should be no other requirements than this, i.e. randomness or unpredictability should not be necessary.

However, in certain settings stronger requirements are put on the nonces; like for instance in the CBC-mode of operation for block ciphers the IV (nonce) needs to be unpredictable (a requirement, when not followed, actually have led to real-life problems in the SSL/TLS-protocol:  Why is CBC with predictable IV considered insecure against chosen-plaintext attack?).

See also: What is the main difference between a key, an IV and a nonce? for a more comprehensive discussion of the properties of nonces and IV's.


Decoding base64 encoded message with a key I am pentesting a database that where I found data which was base64 encoded. I tried the usual method of decoding base64, which didn't work.

Later, I found in database a field called base64_custom_key. How do I decrypt a base64 encoded message with a key?

For eg.
The key looks like gP9jOzA75VyIW6FRuHZimQcLB1rCTKpGN8hdEXw0eY3kMx+/JDUntsob4a2qfSv and the value generated looks like ucaUCo4NmA88Tws8BoQsKAXdBcDn

That's a simple substitution cipher. Base 64 uses the following alphabet A-Za-z0-9+/. Here A encodes  000000, B encodes 000001 etc. In your case the g encodes 000000, P encodes 000001 etc.

Instead of writing your own decoder for that you can simply take the ciphertext, iterate through the characters of the ciphertext and replace g with A, P with B etc. After that you should be able to use a regular base 64 decoder to do the work for you.

Don't replace multiple characters at a time or you'll run into trouble. Put the characters in a new string instead (if you map g to A while there are still other A characters left then your algorithm will certainly fail).


Asymmetric CSPRNG where the public key only works backward Is there an asymmetric cryptographically secure pseudo random number generator in which the public key only goes backward? For example, I'd like to generate 5,000 digits, then provide the public key and RNG state to another party. Then they'd generate the same digits backward from 5,000 to 1. The second party should not be able to calculate the digits from 5,001 onward.

Edit: Here's a working demo of DannyNiu's RSA approach.

Disclaimer: I've not verified the security of my proposal.

You can achieve that in two ways: one pre-quantum, using RSA-like scheme, another post-quantum, using multivariate system.

The RSA version.

Generate an RSA key pair, keep the private key $(N,d)$ to yourself, give the public key $(N,e)$ to the second party.

To generating new numbers, calculate $x_{i+1} = x_i^d \pmod N$. This way, the second party can go backwards from known $x_i$ by calculating $x_{i-1} = x_i^e \pmod N$

The multivariate version.

This version is significantly more heavy-weight than the RSA version. Although there are several multivariate signature schemes in the NIST PQC "Competition" (it seems difficult to build secure encryption scheme using MV), many of them uses exotic methods to compress the public key, which may be optional depending on your use-case.

In its simple form, you have a public multivariate system $P$ which is the composition of private components $S \circ F \circ T$ where $F$ is a easily solvable quadratic system, and $S$ and $T$ are linear.

To generate new random numbers,

Calculate $u = S^{-1}(x_i)$
Solve $u = F(v)$ and choose arbitrary $v$
Calculate $x_{i+1} = T^{-1}(v)$

The second party can reverse it with $x_{i-1} = P(x_i)$

As mentioned by poncho in the comment, the solved $v$ may not be a unique solution, but that's not a problem because any generated $x_{i+1}$ satisfies $x_i = P(x_{i+1})$.

Edit

It seems you're not quite familiar with the notations.

In $x_{i\pm1}$, the $i\pm1$ is the subscript, so in terms familiar to programmers, it's x[i+1] or x[i-1].

$x_i$ is the current state of the PRNG. Since that is the output of some arithmetic operations, its bit pattern is not fully uniformly random (i.e. may fail some sophisticated statistic tests), so you may need to truncate it and/or hash it, to obtain some quality random bits - hashing is also done by the TLS protocol for the same reason.

And yes, it's an iterative generator, but I'm not sure what you mean by "algebraic", and why you believe it'd be inefficient in the second comment.


What Are Secure Limits to Truncate the Authentication Tag (Mac) for Short Messages? I have messages with the following fixed lengths:

4 byte
8 byte
16 byte

I want to encrypted them and prevent modification by appending an authentication tag using a MAC algorithm of my choosing (e.g. using Encrypt-then-Mac schema). Additionally I want the cipher output message to be as short as possible.

Let's say the normal MAC output size would be 16 byte (e.g CMAC with AES). Can I truncate the MAC with a short message like 4 byte to get similar security assurances?

According to various NIST standards, minimum lengths of MAC from 64 bit (CMAC) to 96 bit (GMAC) are recommended.

Cryptographic strength of an authentication tag strongly depends on the tag size and you shouldn't use a tag less than 64-bits for any application. 64-bits is really the minimum you should use.

Such a short tag is acceptable for online protocols, where the intent is just to authenticate a packet that has been received. Since 64-bits will not be collusion resistant, previous tags will be reused before ~2^30 messages. To mitigate this, you might need to rotate key frequently.

You can consider using SipHash function which is optimized for short inputs and has an output of 64-bits.

https://eprint.iacr.org/2012/351


Key cracking: Prefer many small texts over one large text? If an attackers sets out to crack the symmetric key of e.g. AES-CTR, would they prefer to have access to many small cryptotexts or one large cryptotext? I.e. is it more interesting for the attacker to see cryptotexts of many IVs than of a single IV?

Does the answer change if also the plaintexts (many small, possibly similar, plaintexts or one large) are available to the cracker?

Does the answer differ per (approved) crypto algorithm and mode?

I assume perfect implementations, IVs etc. but assume nothing about the properties of the plaintext, except that the attacker does not get to choose it.

If these are too many questions, requiring too long an answer, focus on the first.

Assuming perfect implementations and good block ciphers, it doesn't matter (for any of your questions).

As long as the underlying block cipher is good and has a long enough block length (e.g., 128 bits, as all versions of AES have), any good mode of operation has a security theorem guaranteeing security against chosen plaintext attack for a total of about $2^{b/2}$ blocks of data, where $b$ is the block length. For $b=128$, that's $2^{64}$ blocks, which is more than anyone could ever have time to generate or encrypt (or store).

All this applies to CPA security, which is an even stronger property than resistance to key cracking.


Authentication mechanism for low memory, low computing power device I am looking for an authentication mechanism that works best with low memory, low computing power devices. I came across a paper "A Practical Zero-Knowledge Protocol Fitted to Security Microprocessor Minimizing Both Transmission and Memory" which is released in 1988.

Couldnt find any recent papers. Is it the best one or am I missing some ?

UPDATE:

I have a case where I have few processors connected to a gateway processors. I can send upto 64 bits of data at a time. Computing power is low in the sense that I cant employ something like AES-128 algorithm in all chips. I also need to minimize the number of bits of data send for authentication

SRP doesn't require very much memory, has a low transmission cost (4 packets), and its CPU usage isn't very high (less than 1 second on a low-end 32-bit CPU, but higher on something like an 8-bit CPU).

http://en.wikipedia.org/wiki/Secure_Remote_Password_protocol


Can prepending "junk" be equivalent to an IV when encrypting using CBC? We are encrypting a small positive integer (1-1000) with a constant key using AES256 encryption.  We are considering two approaches to make this secure; use an initial vector (which we then need to store as well), or just prepend some junk to the integer before encryption (possibly 6 characters, this is the plaintext we might encrypt to store 123: "fI8cW3123").

The second approach seems better to us, (we only store a single value, and "discover" the IV while decrypting), but we aren't cryptography experts.  Is this dangerous or less secure?

If you know that the integer is fixed in size (always in the range 1-1000), then the second approach is fine.  Effectively, you still have a random nonce (what you are calling the "junk"); you concatenate the nonce and the integer, then encrypt the result with AES-ECB.  This works.

Do make sure that you choose a large enough random nonce.  I recommend making it as large as possible, i.e., filling the full remaining width of the block.  For instance, if your value is always in the range 1-1000, then it will fit in 10 bits.  So dedicate 10 bits to hold the value, and use the other 118 bits for the random nonce (i.e., to encrypt, you generate a random 118-bit nonce, concatenate it with the value, and then encrypt using AES-ECB).  At a minimum, you probably want your nonce to be at least 80 bits long, and a bit longer might be a bit better.

Also, make sure that you use a cryptographic-strength PRNG to generate the random nonce.


Associative standard cryptographic hash function I am looking for a standard hash function which satisfies the following property:

A hash function $H(a,b) = F(h(a),h(b))$ with $h$ (within $F$) any standard cryptographic hash function and $F$ an associative function.

Is there any standard hash function(e.g. RIPEMD-160, SHA1) for which I can easily implement the associative function (like xor-ing or something similar)?

If you don't need $H$ to be collision-resistant, you can use

$$H(a,b) = h(a) \times h(b) \bmod p$$

where $p$ is a large prime such that $p-1$ has a large divisor (and in particular, the discrete log problem modulo $p$ is hard), and with $h:\{0,1\}^* \to \mathbb{Z}/p\mathbb{Z}$ a hash function that outputs numbers in the range $[0,p-1]$.

If $h$ is a cryptographic-strength hash function, this will be one-way (preimage-resistant) in the random oracle model.  As poncho explains, it won't be collision-resistant, because $H(a,b)=H(b,a)$.

You could also consider

$$H(a,b) = h_0(a) \times h_1(b) \bmod p$$

where $h_0,h_1$ are two separate cryptographic hash functions (e.g., $h_b(x) = h(b,x)$).  This will be one-way and collision-resistant.  I don't know whether it will meet your needs, though, because it's not exactly of the form you mention.

See also MuHash, as described here: Does collision resistance stay when extending a hash function to a set domain?

You might also consider a generalization of this that provides associativity but not commutativity.  Let $\mathbb{G}$ be any non-commutative group.  Then one candidate construction is

$$H(a,b) = h(a) \times h(b) \bmod p$$

where $h:\{0,1\}^* \to \mathbb{G}$ a hash function that outputs group elements.

This gives a candidate construction for each non-commutative group.  Will it be secure?  I don't know, but I expect that will depend upon $\mathbb{G}$.  It seems plausible that with a suitable choice of $\mathbb{G}$, you might be able to design a hash function $H$ that is secure, i.e., one-way and collision-resistant (at least when we model $h$ as a random oracle).

I haven't tried to come up with a specific candidate, but one plausible choice might be letting $\mathbb{G}$ be a suitable set of $2 \times 2$ matrices over a some finite field $\mathbb{F}$, so that $\mathbb{G} = SL_2(\mathbb{F})$.  See, e.g., hashing with SL2: Non-commutitive and nonassociative algebraic structures in cryptography for a related scheme.  I haven't worked out all the details, but this might give you enough ideas to come up with a candidate scheme that meets all of your requirements.


Combining Shamir's schemes I am learning about Shamir's secret sharing scheme and I've come across this problem:

Let's suppose we have a combination of a (3, 6) and (1, 2) Shamir's schemes, where participants $P_1$ and $P_2$ get shares in both schemes and others in the first scheme only. The shared secret is the sum of the two shared secrets. Is such a scheme perfect? My guess is that it is, because I can't see how some unprivileged group would learn anything about the secret.

It depends on the access structure.
It is perfect for the structure on $\{P_1, P_2\}$.
However no subsets of players from $Q=\{P_3,..,P_6\}$ have any information on the secret since they only now one part of the sum.


Why are ephemeral/session/temporary keys useful? One reason that communication protocols use ephemeral keys is to help with implementing Perfect Forward Security.

They're also used in SSL to go from using RSA to using a faster symmetric encryption.

Why else are ephemeral keys used? In particular, if I don't care about Perfect Forward Security, and I already have two machines that have a shared symmetric key, is there any reason to use ephemeral keys?

In AES-GCM, is a 96-bit IV sufficient to not require temporary keys?

Why else are ephemeral keys used?

Ephemeral keys are not a specific form of keys, they are just short lived keys within a key establishment protocol. Usually they are not directly trusted as they are generated on the fly.

ECIES may also use an ephemeral private key, to name a single other usage.

  In particular, if I don't care about Perfect Forward Security, and I already have two machines that have a shared symmetric key, is there any reason to use ephemeral keys?

You may want to generate symmetric session keys that can only be used for a specific session. Ephemeral-ephemeral DH key agreement would work fine for that, although other schemes are also possible. You may also want to use separate keys for different senders and for different purposes (such as encryption and MAC).

Otherwise you could for instance replay messages encrypted with the masterkey. Again, there would be other methods that protect against such a situation, but establishing session keys is a common way to do this.

  In AES-GCM, is a 96-bit IV sufficient to not require temporary keys?

Unless you define ephemeral simply as short lived keys the AES keys themselves are not really ephemeral. They are generally used for multiple messages, not just during key establishment.

AES-GCM can, within reasonable bounds, be used with one key for multiple messages. And yes, the nonce can help with that. The bounds have been defined in NIST SP800-38D which specifies the GCM mode for use in US Federal Agencies.

There are good reasons to use session keys within a transport protocol regardless of the security of the cipher, as already mentioned in the second paragraph.


What's wrong with an iterative (with counter) hashed salted KDF? It seems like the brain-dead simplest KDF would have a key-stretching structure that is not substantially different from $\text{hash}(S | P | S | P |\dots|S|P)$, where $S$ is a salt and $P$ is a password. Other protocols generally require lots of hashes-of-hashes-of-hashes; this one builds up one big string to hash. This naive version has some obvious problems with timing (longer passwords require longer to verify), but it also might be easier to parallelize because the structure is perfectly repetitive, and it might "fall into a fixed point" of the hash function's compression-function, whereby further repetitions do not increase security.

The obvious thing to do, then, involves pre-hashing the password and incorporating a counter. Just to make this question 100% unambiguous, one implementation of this idea in Node.js would be:

function createKDF(work_factor, output_length, hash_algorithm) {
    var crypto = require('crypto'), hash_length, output_blocks;
    function hash(string) {
        var context = crypto.createHash(hash_algorithm);
        context.update(string, 'utf8');
        return context.digest();
    }
    hash_length = hash("").length;
    // needed to support arbitrary output lengths
    output_blocks = Math.ceil(output_length / hash_length);
    function output_transform(bin_data) {
        var buff = new Buffer(hash_length * output_blocks), i, bstring;
        bstring = bin_data.toString('hex');
        for (i = 0; i < output_blocks; i += 1) {
            hash(i + ':' + bstring).copy(buff, i * hash_length);
        }
        return buff.slice(0, output_length).toString('hex');
    }
    return {
        createSalt: function () {
            return crypto.randomBytes(hash_length - 4).toString('hex');
        },
        kdf: function (pass, salt) {
            var hpass = hash('nodejs-passwords-0:' + work_factor + ':' + output_length + ':' + pass),
                salt_buff = new Buffer(salt, 'hex'),
                buff = new Buffer(2 * hash_length),
                hash_state = crypto.createHash(hash_algorithm),
                round;
            assert(salt_buff.length + 4 == hash_length);
            // buffer: [32-bit counter][(N - 32)-bit fixed salt][N-bit hpass]:
            salt.copy(buff, 4);
            hpass.copy(buff, hash_length);
            for (round = 0; round < work_factor; round += 1) {
                buff.writeUInt32LE(round, 0);
                hash_state.update(buff);
            }
            return output_transform(hash_state.digest());
        }
    };
}

The reason I ask is that this approach seems simple enough that, if it is secure, the common advice of "don't roll your own crypto" is somewhat wrong: there are a variety of implementations of $$\text{key} = h_1(0|S|h_2(P)|1|S|h_2(P)|2|S|h_2(P)\dots)$$which you can easily program to create a password-storage system which suits your particular application, if something like PBKDF2 or bcrypt or scrypt is not available in your programming environment.

(Of course Node.js has PBKDF2, so the above implementation is more to clarify the question of "what's wrong with this general approach?" rather than it is to be useful to a JS programmer.)

TL;DR: You put less of a burden an any attacker trying to brute-force this.

And please note: Implementing PBKDF2 shouldn't be much harder than implementing your approach.

Now let's head over to the explanation why "your" scheme is really bad for password-hashing.

The scheme you propose is that each try cost you exactly two hash-function evaluations. One for the first hashing of the password and another for the evaluation of the outer hash.

From a theoretical point of view this is bad because you don't require a certain amount calls to a given function that has a "lower bound" on speed. Memory operations XOR and similar don't count usually. So you have only two evaluations and can only tweak something that doesn't really make a difference.

The last point is that "your" scheme ignores the way how hash-functions work. Hash-functions tend to get faster (measured in bytes / cycle) the more data is fed into the function. So your scheme requires one large invocation with small workload per byte, hence you'd have to feed in much more data (10-1000x) to reach the same workload. PBKDF2 needs less because hash-functions are inefficient for small amounts of data.

To concern your question what would be the disadvantages against PBKDF2 and co.
PBKDF2 is standardized ("your" scheme isn't) and widely accepted for usage (although generally considered the worst option).
bcrypt is generally considered a good choice as it puts a burden on the minimal memory ("you" don't) and is hard to compute on GPUs ("your" scheme seems very GPU-friendly, like PBKDF2)
scrypt is generally considered a very good choice as it puts even more of a burden on the memory side and protects quite good against FPGAs and ASICs ("your" scheme doesn't).


Security analysis of a matrix multiplication protocol Suppose Alice would like to obtain the product of two mXm matrices i.e. A and B. Alice has A, whereas Bob has B.

Since Alice does not want to reveal A to Bob, she chooses a mXm random invertable matrix R. She sends R*A to Bob over a secure channel.

Bob obtains R*A, and calculates R*A*B, and sends it to Alice over a secure channel.

Alice obtains A*B by inverting R i.e. (R^-1)*R*A*B.

R is only utilized once.

Any ideas on how to proceed with the security analysis of the above protocol?

Specifically is H(A|RA) = H(A)

Why over a secure channel? Wouldn't this work pretty well if you take A and B not invertible also in the presence of an eavesdropper? Then Bob could use a similar trick to get AB by sending BS to Alice (where S is invertible) and then recover AB from ABS that Alice sends back. This seems extremely inefficient though.

In any case, Bob knows quite a lot about A. Row-reducing RA should give the same reduced row-echelon form as A has. The rank of RA is the same as the rank of A and so on.


difference between leveled FHE and normal FHE scheme What is/are difference/s between leveled Fully Homomorphic Encryption
  and normal Fully Homomorphic Encryption?

FHE should be able to evaluate any circuit. Leveled FHE can evaluate circuits which have a bounded depth.

BGV was, I believe, the first to offer leveled FHE. The gain was in performance. By restricting to only certain depths (where the depth is calculated by looking at multiplication gates), they were able to remove the bootstrapping operation of Gentry's construction (which was very expensive) or at least spread out the bootstrapping.

Another benefit for leveled schemes is that you can remove the assumption of circular security, i.e., that you can safely encrypt your private key with your public key. We don't know (as far as I remember) how safe this is. Note that we can convert a leveled-FHE to an FHE scheme if we assume circular security though (see footnote 1 in the BGV paper).


How to choose the reduction function in rainbow tables? I have a question regarding Reduction Functions in Rainbow Tables.

If the hashing function is MD5 or SHA-1 etc then should the reduction functions also be MD5 or SHA-1? That is, should the Reduction Function be the same as the Hashing Function but of course with a different set of rules/constraints for  input and output parameters?

So, basically should the reduction function algorithms be same/similar as the Hashing Function algorithm but just differ in terms of rules/constraints for input and output parameters?

No, the way to define the reduction functions isn't related with the hash function used.

Let's consider that we want to recover a password $pwd$ knowing $hsh = H(pwd)$ where $H$ is a hash function. So we will compute a rainbow table for a certain set of passwords $\mathcal{P}$. Note that when the hash chains are computed, at each step $i$ we apply the hash function $H$ and a reduction function $R_i$ (note that several reduction functions are used to avoid collision problems).

A distinction must be made between the hash function $H$ and the reduction functions $R_i$. The reduction functions are used to map hash values produced by $H$ back into values in $\mathcal{P}$.

So the way to define the reduction functions $R_i$ depends on how you chose the set $\mathcal{P}$. For example $R$ can be the decomposition in base $n$ where $n$ is the size of $\mathcal{P}$ (the incrementation functions $R_i$ can be simply defined by incrementing the input of $i$ and then apply the decomposition).

The Wikipedia page also gives an example:

  An example for a reduction function: Given a 32 bit hash, get the last
  6 characters in the hash.


Can CMAC be used as a 128bit Key Derivation Function? I want to derive a key a number of times for a deterministic scenario, where I can get n keys from a single one.

The logic looks something like this:

masterKey = random 128-bit
For i from 0 to n:
    let key[i] = CMAC(masterKey, i)

Is this a proper way to generate a number of keys or does this have a flaw?

CMAC(masterKey, i) should generally suffice, yes. Note that you would need to specify an encoding for i (e.g. octet string consisting of the big endian encoding of i, left-padded with zero valued octets up to 4 octets).

It's probably better to implement one of the schemes defined in NIST SP 800-108: "Recommendation for Key Derivation Using Pseudorandom Functions" though. Note that CMAC is a Pseudorandom Function (PRF) and is mentioned explicitly in this standard.

I'd recommend the NIST SP 800-108 counter mode (section 5.1), which is relatively commonplace and easy to implement. Note that the counter i in the standard is different from your definition of i. The i in the standard is used to derive more keying material for a single key than can be generated by the PRF (i.e. more than 128 bits in the case of AES-CMAC). Your i should be encoded in the Context variable if you follow the standard to the letter.


NIZK Proof of knowledge N of M discrete logarithms (threshold) It is well known how to produce a NIZK that curvepoints $aG$ and $aP$ have the same discrete logarithm $a$ with respect to the curvepoints they are multiplied by. There is also a way to prove that a curve point $aG$ has the same discrete logarithm as one of $b_1P$, ..., $b_nP$. I think this is due to Cramer but I first encountered it in Traceable Ring Signatures.

My question is: is there a threshold version of this? That is, given a set of $M$ discrete logarithms, can I prove that I know $N$ of them?

A straightforward way to prove this when you can prove AND as well as OR statements about discrete logarithms is to take all the $K=\binom{M}{N}$ subsets $A_i=\{A_{i_1},\ldots,A_{i_N}\}$ with $N$ elements of points from the set of your $M$ points and prove the statement
$$PK\{(\alpha_1,\ldots,\alpha_N): \bigvee_{j\in K} \big( \bigwedge_{A_{j_i}\in A_j} A_{j_i}=\alpha_i P \big) \}.$$

If this proof verifies, then you convince the verifier that you know all $N$ discrete logarithms in one of the $K$ subsets of $N$ elements of all your $M$ discrete logarithms without revealing which one.

The idea of proving OR statements is due to Cramer et al.. Moreover, their result holds for arbitrary monotone access structures.

Non interactivity can be added as usual by using Fiat-Shamir and living with random oracles. This recent approach shows how you can use a related transform which does no longer requires programmable random oracles.


Proof by reduction for for digital signature scheme $S_2((sk_0,sk_1), m):=(S(sk_0,m), S(sk_1,m))$ Let  $(Gen,S,V)$  be  a  secure  signature  scheme  (existentially  unforgeable  under  a  chosen  message  attack)  with  message  space${\{0,1\}}^n$.   Generate  two  signing/verification  key  pairs $(pk_0,sk_0)\gets Gen$ and $(pk_1,sk_1)\gets Gen$.  Is the following a secure signature scheme? Show an attack or explain why the scheme is secure, that is, explain why an attack on the scheme leads to an attack on $(Gen,S,V)$.
The new scheme is :
$$ S_2((sk_0,sk_1), m):=(S(sk_0,m), S(sk_1,m))$$
\begin{align}&V_2((pk_0,pk_1), m,(\sigma_0,\sigma_1))= \text{'accept'}\\\iff&V(pk_0,m,\sigma_0) = \text{'accept'}\quad  \text{or}\quad V(pk_1,m,\sigma_1) = \text{'accept'}
\end{align}
I do not know how to give a formal proof (probably proof by reduction) that the scheme is secure. (Maybe by showing if there is an attacker for scheme $S_2$ we can use it to attack $S$ and calculating new attacker advantage and showing that it's not negligible.)

So this is a solution I came up with based on this chat with @Maeher.
We use proof by reduction to show if there exists an attacker $A$ with non-negligible advantage for $S_2$ we can use it to construct an attacker $B$ for $S$ with non-negligible advantage. If
$$\Pr[vrfy(pk_0,m,\sigma_0)  \;\; and \;\; vrfy(pk_1,m,\sigma_1)]$$
be non-negligible then easily we can construct $B$ to give us a forgery for $S$. So we assume this probability is negligible and without loss of generality assumes the above probability is equal to $0$. now suppose the non-negligible advantage of $A$ is
$$ adv2 = \Pr[vrfy(pk_0,m,\sigma_0)] + \Pr[vrfy(pk_1,m,\sigma_1)] = p_0 + p_1 $$.
attacker $B$ take as input public key $pk$ and call $Gen$ algorithm to have $(pk_1,sk_1) ,( pk_0,sk_0) $ then it uniformly choose bit $b$ form $\{0,1\}$ and pass $(pk,pk_b)$ to the $A$. then $A$ return $(m,(\sigma,\sigma_b))$ and $B$ choose $(m,\sigma)$
as it's forgery. advantage of $B$ will be equal to $adv$ which
$$adv \geq \frac{1}{2}(adv2 - p_0) + \frac{1}{2}(adv2 - p_1) = \frac{1}{2} adv2 $$
so $adv$ is non-negligible.


What if the CSR is intercepted in transit while sending it to CA? I was studying PKI the other day and I had a serious thinking about the following question.
What is CSR?  - It is a block of encoded text that is given to the CA when applying for an SSL certificate which validates the identity of the requesting party. The process to construct a CSR is,

A Certificate Request Info value(plain-text) containing Distinguished name has to be filled. i.e. Common Name, Organization, OU, City, State, Email Address and Public Key.
The above Certificate Request Info value is signed with the subject entity's private key. i.e. Digitally signed.
The Certificate Request Info value, a signature algorithm identifier, and the entity's digital signature are collected together into a CSR.

So, basically the CSR contains Digitally signed plain-text info about the requesting party, the plain text-info and the Signature Algorithm.
My question is What if the Man-in-the-Middle alters the Email Address in the CSR but actually kept the public key intact?
This way when the CSR reaches the CA, the CA will fetch the public key from the plain-text info and decrypts the signed info thereby assuming that no tampering was done. So, Is there a way to prevent this interception or my understanding is incorrect?

Normally CSR does not need to be secret. CSR is signed by the applicants private key. If an attacker intercepts a CSR, changes email address and sends CSR on CA, CA will reject it, because the signature will not match the content of the CSR. If the attacker signs the changed CSR with attackers private key, the signature will still be invalid, because it cannot be verifyed by the public key contained in the CSR.
Here is a good short explanation of the verification process: How does RSA signature verification work?.
To sign the CSR with the changed email, a private key of the applicant is needed. If the applicant keeps the private key properly, then the attacker cannot get it and cannot create a valid CSR with another email.
TLDR
CA will consider the changed CSR as invalid because the attacker cannot create a valid signature.


I don't want to store passwords, can I use them as an encryption key for another field? I'm not a 'cryptographic' anything, so if this is a super-dumb question please let me know (politely).

So here's the deal, say I don't want to store passwords because that opens me up to all sorts of failures (see: Facebook). Instead, I want to use the passwords as a key for something else.

Let's assume our process is:

User enters a password, we use 2FA, so we use that password to DECRYPT (via some KDF + et. al.) the Phone Number or Email (whatever the 2FA calls for here), and start the 2FA process;
User passes 2FA, we log them in;

Now, my thought is that this should be an acceptable process, but I'm not a cryptographic expert on anything, so I'm curious on whether this is an adequate method of storing the password + 2FA component. It seems reasonable, after all, we're no longer actually storing the password, and with a sufficiently-strong KDF we add another layer of security by not using the raw password in the encryption process, meaning if someone manages to break it (let's say we use something like AES-256, or whatever the de-facto standard is) and extract the key, they have the KDF-transformed key, not the raw key.

Additionally, my thought here is that this solves the following problems:

Storing the password in plain-text (obviously);
Abusing the MFA components (as a certain, nameless, company has starting using that Phone Number for marketing purposes);

Does this make sense? Am I talking about something the world / experts have decided is a terrible idea?

It kind of makes sense, but there are some hairy details.

To use a password as a key you need a password based key derivation function or PBKDF, not just any KDF. Otherwise the adversary can try and guess the password and try to decrypt anything you encrypted with it. Generally that would take just one additional block decrypt, so that's generally a fast operation. So you need a work factor (or, for specific PBKDF's, iteration count) to make it harder to guess the password. Just like when storing a password hash, for the same reason you will probably also want to a salt. The salt / random may also be required to stop replay attacks.

This does however mean that the user suddenly has to perform the work factor; generally password hashes are calculated server side. This might be an issue if the client has limited computing facilities - or battery life / heat dissipation issues, etc.. More importantly, if the attacker learns the key from your DB, then the attacker can simply skip the calculation altogether.

Generally we don't encrypt known / public data. It may be easy to slightly alter the data by adversaries, which in turn may result in surprising attacks. Generally we use a MAC such as HMAC over the data instead. That way you can verify if the key is correct by simply validating the MAC.

There are many other ways to verify passwords. For instance, you could have a look at PAKE protocols or SRP.

You haven't really indicated why simply storing a password hash is not sufficient either. Currently you are making your life more difficult without making your protocol more secure.


CBC mode works well for input greater than "b" bits. What is that "b" bits? This post on geeksforgeeks.org about block cipher modes of operation, says that one of the advantages of the CBC is that it works well for input greater than b bits. I also saw that in the book "cryptography and network security by William Stallings". But neither of them said what exactly is that b bits. Can anyone explain? thanks.

There the $b$ bits mean the block size of the Encryption and that is 64 for DES and 128 for AES.
Therefore you may need more than one block for the encryption of your plaintext (message). If your message size is $\ell$ than you need $$\lfloor \frac{\ell}{b} \rfloor + 1$$ blocks to encrypt.
The block nature of the CBC mode like any other, not like CTR, requires padding to fill the empty bits of the last block. Usually, the PKCS#7 padding is used for this.  PKCS#7  can increase the number of blocks by one if $b|m$.
Note that if the CBC mode is used with servers like in TLS, then it is vulnerable to padding oracle attacks that work like decryption oracle. In this case, you may need to get rid of the CBC as TLS 1.3 did and use paddles mode like CTR. The better is using authenticated encryption modes like AES-GCM which internally uses the CTR mode and provides integrity and authentication with GMAC.
Keep in mind that, Wikipedia is the first source to look at those, not any other site.
If you really want to use CBC mode then
Your obligations

You must Generate a uniform random 256-bit secret key, and keep it secret all the time;
For each message that is going to be encrypted under the same key choose an Initialization Vector (IV) that must be unique and unpredictable. You can send the IV prepended to the ciphertext
Make sure that the message size is multiple of 128 with proper padding.
The message size must not exceed $2^{60}$.
The key must not be used more than $2^{45}$ due to the IV collision due to the birthday attack. This will produce $$(2^{45})^2/2^{128}/2 = 2^{90 - 128-1} = 1/2^{39}$$ probability of collision instead of $1/2$ probability of $2^{64}$

In return : CBC guarantees

CPA security; that is the adversary cannot distinguish two ciphertexts with the same length, and thus cannot read the message sent.
That is all you get from the CBC mode if used properly. To achieve authenticated encryption use HMAC with CBC in encrypt-than-MAC as a recommendation.


Disadvantages of the Feistel network I have read about Feistel network and so far only advantages have been listed. Are there any disadvantages to the design? Please could you explain in fairly basic terms?

Well, what are we comparing Feistel networks to? The other major design paradigm is SPN: https://en.wikipedia.org/wiki/Substitution-permutation_network. In comparison to SPN, the cons are:

Not a direct implementation of confusion and diffusion. Feistel networks have more structure that has no clear justification. (Some point to the security proof but if you assume a cryptographically secure round function, how wrong can things go? A better question is: "if your round function is weak, what does the Feistel network add?").
Parallelism is about half of an equivalent SPN, which is a disadvantage for hardware implementations.


Testing if a password for an eCryptfs mount is valid I'm using "eCryptfs" on several directories on my dedicated Debian server. I mount them manually via

mount -t ecryptfs [dir] [mountpoint]

But after some weeks being mounted it's not easy to remember the exact passwords for each directory. I want to make sure that I got the right passwords before unmounting them or rebooting the server.

I thought of generating an "eCryptfs" signature and comparing it with the directory's "eCryptfs" signature. Which parameters do I need to know and what is the algorithm for the "eCryptfs" signature? And is this the right way to verify my password?

You can use the ecryptfs-add-passphrase command to add a passphrase to your kernel keyring, which will also print the signatures (hashes) to standard out.

Once you've added a passphrase to the keyring, you might want to clear it, using the keyctl command.

eCryptfs uses a PBKDF2-like, key strengthening algorithm of 65536 rounds of SHA512.

(Disclosure: I am one of the authors and maintainers of eCryptfs.)


How simple hash provide message authentication? This structure provides message authentication. My question is if someone finds the key he can simply change the message and compute new hash according new message and send it to the receiver. If so, how can hashing provide message authentication? This scheme totally depends on encryption algorithm than why do we add hash in this?

As indicated by Dave in the comments, hash-then-encrypt may not provide authentication, so the scheme in the picture you provided may not be secure at all.

Let's assume for this answer that the encryption scheme used is such that hash-then-encrypt is secure. It could for instance be mapped to AES-GCM which uses GHASH, or Poly1305 correctly paired with a block cipher.

The idea of authenticated encryption is not to provide security against leaking information about the key. If the key gets known to the adversary then all protection is lost.

Authenticated encryption provides message integrity - protection against changes of the ciphertext. These changes may be deliberate, i.e.  changes of the ciphertext during transport by an adversary or non-intentional such as data loss by lower levels in the transmission.

If you don't provide message integrity then an adversary may change the ciphertext and thereby alter the decrypted plaintext message without this being detected. It could also trigger the availability of a plaintext oracle that may even compromise confidentiality of the message. Note that hash-then-encrypt may not provide protection against padding oracles if CBC mode encryption is used, as the padding is (commonly) removed before the hash is verified.

Besides that, it provides message authenticity: proof that the plaintext as encrypted by an entity holding the secret key. Nobody else would be able to encrypt a valid hash after all.

In short, the hash is there to protect the message, it doesn't protect the key.


Can you find the salt if you have the original password in plaintext and the hashed version? Suppose that I have a password in plaintext. I also have the hashed version of the password. Say it uses MD5. Is it possible to find out what the salt is given the above information? I'm guessing not?

No. It's impossible to find the salt if you don't already have it unless something is seriously broken or unusual.

You may already have the salt because it's common practice to store the hash together with the salt. Many password hashing interfaces even output a hash string which contains the “real” hash, the salt, and additional metadata identifying the algorithm and the iteration count. For example, the output of the Unix crypt() function looks like $5$salt$hash where 5 identifies the hash algorithm, salt is the salt encoded in Base64 and hash is the output of the underlying function also in Base64. The PHC string format, promoted by the Password Hashing Competition, has a very similar format.

But if all you have is the hash itself, then for anything remotely resembling a proper password hash and even for most things that aren't, the only way to find the salt is by trying every possibly salt until you find the right one, just like the only way to find the password is by trying every possible password until you find the right one. Even something broken like MD5(password + salt) (broken as a password hash because it's far too fast) makes it impossible to find the salt without guessing it. That's preimage resistance, and even hashes like MD4 and MD5 that are badly broken with respect to collision resistance still have preimage resistance.

With the password, guessing is a real risk: most users choose passwords that are at best a slightly modified dictionary word, which can be guessed in seconds of computer time with a broken hash like MD5 and may still be barely manageable but slow with a properly slow hash. But the salt is not chosen by a human. It's usually generated randomly so brute force among all possibilities is the only way. And it's usually long enough that brute force is not feasible. You'll only realistically be able to find the salt if either it wasn't generated randomly (or with a non-cryptographic random generator, or with a badly seeded generator), or if it's too short for comfort.


Given $S:F_2^n\rightarrow F_2^n$, define the (generalized) walsh transform coefficient as $$\hat{S}(a,b)=\sum_{x\in F_2^n} (-1)^{a \cdot x + b \cdot S(x)}.$$

Looking at your array, $b=0$ which gives  $$\hat{S}(a,b)=\sum_{x\in F_2^n} (-1)^{a \cdot x}=0,$$ should result in a zero sum for all $a\neq 0$ and a sum of $2^n=2^4=16$ giving a row or column with 15 $0$s and one $16.$ You have omitted one column, which I shall assume corresponds to $a=0.$

Otherwise, what is observed from your array is that the multiset of absolute values for nontrivial linear selections of the sbox bits ($b\neq 0$),i.e., the multisets
$$
M_b=\{|\hat{S}(a,b)|: a \in F_2^n\}
$$ where we count frequencies of occurence of distinct transform values are invariant with respect to different values of $a,$ which is a kind of uniformity. I wouldn't call it "minimal redundancy" without a definition of what that term might mean. Moreover, due to the absolute value, this is equivalent to the following multisets
$$
M_b=\{|\hat{S}(a,b)|^2: a \in F_2^n\}
$$
begin invariant. In general, from Parseval, we would have
$$
\sum_{a \in F_2^n}|\hat{S}(a,b)|^2,
$$
be a constant, and maybe the maximum redundancy would correspond to these magnitudes all being the same, i.e., $\pm 2^{n/2}$ which could occur only with $n$ even. In any case from Parseval we can deduce that the omitted values in the other rows are $$\sqrt{2^{8}-2\times 8^2-8\times 4^2}=0$$ which could also been directly inferred but this means that your other values are admissible as walsh coefficients so it's useful.
But I fail to see why the multiset of values you exhibit (including the missing one)
$$
\{8(2~times),4(8~times),0(6~times)\}
$$
are in some sense minimally redundant, without some kind of result on divisibility properties (by some $2^i$) for walsh coefficients of Sboxes (which I assume are permutations). Such properties are usually deeply algebraic in nature.


What does trust mean in cryptography? Terms like "trustless protocol", "trusted third party", "trusted platform", "trusted server", etc. require a notion of trust. I already wrote

  The term trust when used in the context of cryptography does not refer to personal confidence in whether a person is reliable or has good intentions but instead describes whether an entity can be assumed to always behave according to protocol within the given model.

and went looking for a source to back this claim up. Unfortunately, I wasn't able to find one, nor was I able to find one to say that my notion of what "trust" means in cryptography is wrong.

So what does this term refer to formally?

A most common use of "trusted" in cryptography is to state that what's qualified as "trusted", by hypothesis, behaves/works/performs per a certain precise set of rules (which depends on context), and will perform no less and no more. That's the case in trusted third party, and trusted server.

A special case is "trusted" applied to data, e.g. trusted key. There, trusted means that the data is assumed to possess some property, which depends on context. Typically, having been generated by a certain party in a certain way and not having been altered by any adversary; or/and being unknown to any adversary. Data can become trusted after having passed a cryptographic check, e.g. a digital signature or Message Authentication Code verification; or be initially trusted (e.g. a Root Certification Authority public key).

In marketing talk like trusted platform module or trusted computing, "trusted" means intended for implementation of something trusted in the above cryptographic sense. Experience often shows otherwise, but confusion between intent and fact is the lesser of the many kinds of lies in marketing (which also has plain lies, damned lies, and statistics).

"Trustless" means not requiring something "trusted". For a protocol, that's not requiring a trusted arbitrator, typically replacing that with users that still are expected to largely play by some rule, because they have no long-term interest in doing otherwise (perhaps, unless enough users band together to rip the others).


OpenSSL ECDH key exchange mechanism I am using FIPS based OpenSSL module for encryption of sensitive data for my desktop socket server and client applications. I am using ECDH for key agreement.The keys public and private pair is generated for server and client on same curve NID_secp521r1. Now I want to exchange the public key between client and server and has following questions.

The generated private key is same for both client and server is it true? Client send its public key first or Server? The public key should be send plain or it should be signed? If signed then what will be the mechanism? I want to reuse my public/private key on server where I store that keys in application exe? PEM file? Any other options?

The generated private key is same for both client and server is it true?

No, that's not true. The key pairs and thus the private keys will be different. They will only be the same if the random number generator creates 521 identical bits for both the server and the client when the key pairs are generated.

  Client send its public key first or Server?

That doesn't matter, whatever is more efficient.

  The public key should be send plain or it should be signed?

Plain will do, if you perform authentication afterwards. TLS signs and verifies all the packets send, after the key agreement. You do need to check if the public key represents a valid point on the curve though.

  If signed then what will be the mechanism?

Depends on the protocol. Anything that can perform signing or MAC authentication really.

  I want to reuse my public/private key on server where I store that keys in application exe?

Whereever they are most secure. If you use them in software then for OpenSSL the PKCS#12 format probably makes the most sense. It doesn't matter if the PKCS#12 key store is stored as PEM or DER format.

Unless you need an ultra lightweight protocol using TLS itself makes an awful lot of sense. If you really must design your own protocol, then first learn and understand TLS.


Slow one-way pseudo-random permutation? I'm looking for a slow one-way pseudo-random permutation; or in other words a block cipher $E_K: P\in\{0,1\}^b\mapsto C\in\{0,1\}^b$ with moderate block size $b\approx 64$ bits, wide key $K$, indistinguishable from a random permutation for one not knowing $K$, and additional characteristics:

encryption $E_K$ is controllably slow according to a parameter $c$, similar to the iteration count parameter in PBKDF2; an additional memory size parameter $m$ as in Scrypt would be nice;
there is no efficient decryption method even knowing $K$, ideally so that the least costly method to decipher ciphertext blocks $C_j$ would be to try and (slowly) encipher candidate plaintext until finding a match. Update: Otherwise said, there should be a security gap as wide as possible between decryption and encryption, expressed as a ratio of work; and that should remain sizable when the cost of encryption is raised using parameter $c$.

Is there some established (or arguably secure) construct for that? One idea is outlined in this interesting answer to a related question (but unfortunately, the one-wayness obtained using a permutation polynomial seems dubious).

Update: I'd also be satisfied with a slightly expanding injective function, e.g. $E_K: P\in\{0,1\}^b\mapsto C\in\{0,1\}^{b+1}$.

Updated example application: 2-D barcode cards (or other kind of write-once memory cards) are issued to individuals with data including a unique serial number $S$ of $s=32$ bits (sequentially assigned, thus largely guessable from another $S$), and other data $Q_S$ (which we assume has sizable entropy). The serial number is used for some initial purpose, and (interpretations of) regulatory requirements protecting individual's privacy prevent from storing that identifier for purposes unrelated to the initial purpose. Nevertheless, merchants would like to lawfully reuse the same cards in an existing loyalty application, identifying cards with an identifier of small size, and able to work off-line (at least, as a backup). We thus want to transform $S$ and $Q_S$ into a short digest (practically public), computable from $S$, $Q_S$, and a key $K$, that remains unique to a given card (as $S$ is); the digest should leak no information about $S$ and $Q_S$ without access to $K$; and, inasmuch as possible, the confidentiality of $S$ and $Q_S$ should be preserved from an attacker knowing digest and key (thus easing the requirements on secure storage and use of the key). Notice that a truncated MAC would not match the "remains unique to a given card" requirement.

With a function as in the question, we could use as digest $E_K(S||R_S)$ where $R_S$ has $b-s$ bits, and is obtained, say using Scrypt, from $Q_S$, $S$, and $K$. Notice that encryption slowness in the forward/encryption direction is necessary to prevent checking guesses of $S$ and enumerated $R_S$; and even more slowness (ideally, next to $2^b$ times as much slowness) is required in the backward/decryption direction, in order to prevent deciphering of the digest. Notice that either attack would reveal $S$, and also allow forged cards misappropriating the same $S$ and digest as the original, if not the same $Q_S$.

The main difficulty in designing what I asked, is coming up with a permutation over a relatively small set, that is easy to compute in the forward direction, but convincingly much more difficult to invert. The least unsatisfactory I have so far is based on the discrete logarithm problem in $\mathbb Z_p$. If $p$ and $(p-1)/2$ are primes, and $g\in\{2\dots p-2\}$ with $g^{(p-1)/2}\not\equiv1\pmod p$, then
$$P:\begin{cases}
 x\mapsto g^x\bmod p& \text{if } x\in\{1\dots p-1\}\\
  0\mapsto0
\end{cases}$$
is a permutation of $\{0\dots p-1\}$ which is easy to compute, but markedly harder to invert. At least, the problem is well-studied, with the best known algorithms the index calculus algorithm and some specialized GNFS variants. Bad news is that the problem is workable for 530-bit $p$, and here I'll be stuck with $p$ like 80-bit (for $b=64$ and other realistic parameters).

It seems possible to build a slow one-way pseudorandom permutation over $\{0,1\}^b$ from such $P$, while keeping about the same security gap (ratio of work in backward to forward direction) as in $P$. I sketch such a construction below. Again this is not fully satisfactory, for the above (family of) $P$ does not have a high-enough security gap, given the order of magnitude I can use for $p$. I badly need a better $P$ !!

Update: The best attacks on $P$ require a heavy pre-computation, then can go from $P(x)$ to $x$ at comparably low cost. I have tuned the following to account for that fact.

The construction requires an expected $c_0\cdot c_1$ evaluations of the above $P$ with $p\approx c_0\cdot2^b$, and forces an adversary trying to brute-force the forward direction to mobilize about $m\cdot2^m$ bits of memory for each few instances run in parallel. Realistic parameters could be $b=64$, $c_0=2^{12}$, $c_1=2^{12}$, $m=20$.

Derive from $K$ a pseudo-random $g$ in $\{2\dots c_0\cdot2^{b-1}\}$ ;
Derive from $K$ an arbitrary permutation $M$ of $\{0,1\}^m$, stored as $2^m$ words of $m$ bits of memory;
Repeat for $c_1$ rounds (identifier by round counter $r$) the following keyed permutation of the current $b$-bit state $s$:

derive from $K$ and $r$ a pseudo-random prime $p$ in range $\big[{3\over4}\cdot c_0\cdot2^b\dots{5\over4}\cdot c_0\cdot2^b\big]$, such that $(p-1)/2$ is prime and $(g^{(p-1)/2}\bmod p)=p-1$ (note: it is advantageous to perform the later test right after insuring that $p$ and $(p-1)/2$ have no small divisors);
Repeat

If $s<\big\lfloor p/2^m\big\rfloor\cdot2^m$ (which is, most of the time)

Replace the low $m$ bits of $s$ with their image through $M$;

If $s\ne0$ (which is, most of the time)

Replace $s$ with $g^s\bmod p$;

Until $s<2^b$.

Note: $s$ temporarily grows to at most $b+\big\lceil\log_2({5\over4}\cdot c_0)\big\rceil$ bits.

For each round, the repeat..until iteration is expected to be executed about $c_0$ times, with an exponential distribution. Increasing the number of rounds $c_1$ makes the runtime more predictable, and less likely that pre-computations for inverting $P$ can help an attack. Each iteration requires one memory lookup, and $\epsilon\cdot\log_2 p$ multiplications $\bmod p$ (we can have $\epsilon\ll1$ with some pre-computation).

(Optionally, the construction could end (or/and start) with some conventional $b$-bit block cipher using key $K_d$ derived from key $K$, perhaps TDES for $b=64$ (with additionally one bit of $K_d$ devoted to making the resulting permutation odd or even, by conditionally swapping output values $0$ and $1$). This, combined with use in other steps of permutations not chosen from $K_d$, convincingly insures that the overall construction is indistinguishable from a random permutation for one not knowing $K$).


Proof that a modified public-key encryption scheme is not CCA secure Let $\mathcal{E} = (G, E, D)$ be a CCA-secure public-key encryption scheme defined
over $(\mathcal{M, C})$ where $\mathcal{C} := \{0, 1\}^\ell$.

Let $\mathcal{E'} = (G, E', D')$ be a scheme (over $(\mathcal{M, C'})$ where $\mathcal{C'} := \{0, 1\}^{\ell + 1}$) where:

$E'(pk, m) = E(pk,m) \Vert 0$
$D'(sk, c) = D(sk, c[0...\ell - 1])$

That is, $E'$ always puts a $0$ in the ciphertext and $D'$ ignores the last bit of the ciphertext.

How can an attacker, with just $1$ query, break $\mathcal{E}'$ CCA security?

Additional information:

The query can be one of these:

Encryption query: the attacker sends a pair os messages $(m_0, m_1)$ and gets a ciphertext $c_i$ of one of them.

Decryption query: the attacker sends a ciphertext $c$ and gets its corresponding message.

So let's go through the CCA(2) game and see where things fall apart, shall we?

Challenger: Generates keys.
Adversary: Calls the encryption or decryption oracles a polynomial amount of times. We don't need this here.
Adversary: Picks two messages, eg $m_0=0$ and $m_1=1$.
Challenger: Chooses a bit $b$ uniformly at random, ie $b\in\{0,1\}$
Challenger: Encrypts $m_b$ and sends the result to the adversary as $C$, the challenge ciphertext.
Adversay: Perform a polynomial amount of operations including encryption or decryption oracle calls, e.g. to decrypt $C$ with the last bit flipped.
Adversary: Output a guess $b'$ for the bit $b$, eg the result of the decryption query in the last step.
If $b=b'$ the adversary wins. If the probability  of this happening is not negligbly higher than $1/2$, the scheme is broken.

Do you see now how CCA security is broken using 1 query?


GCM: Math behind update of AAD after ciphertext has been processed In the Bouncy Castle libraries, the GCM cipher implementation has an interesting property that does not seem described in the GCM papers (neither the NIST or the original paper):

  Some AAD was sent after the cipher started. We determine the difference b/w the hash value we actually used when the cipher started (S_atPre) and the final hash value calculated (S_at). Then we carry this difference forward by multiplying by H^c, where c is the number of (full or partial) cipher-text blocks produced, and adjust the current hash.

This scheme is present in the final calculations (in the doFinal() method).

Now what I understand is that addition of within the polynomial is equivalent to XOR. I can also see why exponentiation is required to carry the difference forward. What I don't see is how the complete scheme works, especially for partial 16 byte blocks.

Can somebody show how the adjustment in the doFinal method is defined  mathematically?

Note that the $\operatorname{GHASH}$ function is performed over the follwing data within GCM:

$S = \operatorname{GHASH}_H (A || 0^v || C || 0^u || [len(A)]_{64} || [len(C)]_{64})$

where

$0^v$ and $0^u$ is padding (0..127 bits of zero's) up to the block size

$\operatorname{GHASH}$ itself is defined as follows:

Steps:

Let $X_1, X_2, ... , X_{m-1}, X_m$ denote the unique sequence of blocks such that $X = X_1 || X_2 || ... || X_{m-1} || X_m$.
Let $Y_0$ be the “zero block,” $0^{128}$.
For $i = 1, ..., m$, let $Y_i = (Y_{i-1} \oplus X_i) • H$.
Return $Y_m$

and

$X•Y$ is the product of two blocks, $X$ and $Y$, regarded as elements within the binary Galois field

So in this scheme additional AAD ($A$) is send after ciphertext ($C$) was already put within the calculation.

Well, $\operatorname{GHASH}$ might be better understood as the polynomial:

$$\operatorname{GHASH}_H(X_1, X_2, ... , X_{m-1}, X_m) = X_1 H^{m} + X_2 H^{m-1} + ... + X_{m-1} H^2 + X_m H^1$$

where addition, multiplication and exponentiation are in the field $GF(2^{128})$.  These addition, multiplication and exponentiation operations act algebraically quite a lot like the operators in a more traditional field (say, the real numbers); the usual tricks for rearranging polynomials work exactly the same.

What Bouncy Castle is doing is taking the vector $X_1, X_2, ... , X_{m-1}, X_m$ in two pieces, the AAD vector $A_1, A_2, ..., A_a = A || 0^v$ and the ciphertext $C_1, C_2, ..., C_c = C || 0^u$, and evaluating $\operatorname{GHASH}_H(A_1, A_2, ..., A_a, C_1, C_2, ..., C_c, X_{final})$ (where $X_{final}=[len(A)]_{64} || [len(C)]_{64}$ encodes the length of the AAD and the ciphertext).  One way to rearrange this is:

$\operatorname{GHASH}_H(A_1, A_2, ..., A_a, C_1, C_2, ..., C_c, X_{final}) =$
$H^{c+1}\operatorname{GHASH}_H(A_1, A_2, ..., A_a) + H\operatorname{GHASH}_H(C_1, C_2, ..., C_c) + HX_{final}$

With this rearrangement, we can obviously evaluate $\operatorname{GHASH}_H(C_1, C_2, ..., C_c)$ before we see any AAD data (or even before we know how long it is).

Now, you ask about partial blocks.  It turns out that we don't need to worry about partial blocks; GCM is defined so that both the ciphertext and AAD vectors are zero padded to the next full block; hence we never need to worry about partial blocks.  If you are wondering a collision if we append a zero byte to the AAD, well, that's what $X_{final}$ is there for -- appending a 0 changes the AAD length, and hence the $X_{final}$ value.


Super-simple encryption of short strings I want to anonymise the initials of experiment participants by giving each a pseudonymic set of initials, by encrypting their true initials. Their initials are only two or three letters in length.

These are data from individual human experiment participants that I publish online and in scientific journals. The convention (from a more innocent time) is to inset each participant's initials in a graph of their data. Using Github I will publish all the code and anonymised data, excepting the key (more background: https://plus.google.com/+AlexHolcombe/posts/1sNgTnnAtYz). Symmetric encryption seems fine.

Is there a suitable algorithm simple enough to quickly implement in the R statistical language?  I came across the Vignere cipher, which seems to be exactly what I need, but I know almost nothing about cryptography so perhaps that is naive.
http://www.counton.org/explorer/codebreaking/vigenere-cipher.php

It seems you want some sort of anonymization, and you already jump to a conclusion with encrypting symbols. Maybe you should step away of that for a moment, and ask yourself what your actual goal is.

Encryption is useful, if you want to be able to reverse that process. If you don't hashing is a better choice in general.
Your set is small enough that you can just create a lookup table on the fly with a random number generator of your choice, as fgrieu already pointed out.

Instead of focusing on how to anonymize the initials, you might want to have a closer look on the anonymization of the actual data, if there is more than a single measurement for each participant. Aggregation of data can reveal information, that you wouldn't have imagined before. Simple pseudonymization might only work for those with common features and expose those with rare combinations. E.g. gender + age in a group with mostly men will give some anonymity to the men, while women of a certain ag can be identified much easier.

In general, I would say it is a bad idea to publish the raw data from any experiment with real people, and don't rely on pseudonyms as anonymization. Only publish the final aggregated data, which shows what you want to state.


Can the XOR of two non-collision-resistant hashes be collision resistant? Suppose I have two hash functions, of which neither (or only one) is collision resistant, and I want to create a new hash function by taking the bitwise exclusive or (XOR) of the results of those two functions.

Is it possible for this new function to be collision resistant? I suppose not, but I'm not sure why.

The answer to your edited question is "yes, it is possible".

As a trivial example, let $H$ be an ideal $k$-bit hash function.  Due to the existence of the generic birthday attack, $H$ provides only about $k/2$ bits of collision resistance — that is, an attack can, on average, find a collision after about $2^{k/2}$ hash function evaluations.  Denote the output of $H$, given the input $x$, as $$H(x) = (b_1(x), b_2(x), b_3(x), \dotsc, b_k(x)),$$ where $b_i$ denotes the $i$-th bit of the output.

Now define the $k$-bit hash functions $$H_L(x) = (b_1(x), b_2(x), b_3(x), \dotsc, b_{k/2}(x), 0, 0, \dotsc, 0)$$ and $$H_R(x) = (0, 0, \dotsc, 0, b_{k/2+1}(x), b_{k/2+2}(x), \dotsc, b_k(x)).$$

That is, $H_L$ is the same as $H$, except that the last $k/2$ bits of the output are replaced by zeros, and $H_R$ is the same as $H$ except that the first $k/2$ bits are replaced by zeros.

Now, clearly, either of $H_L$ or $H_R$ alone only provides $k/4$ bits of collision resistance.  If, say $k = 128$, then $H$ may still be considered practically collision-resistant (effort to break = $2^{64}$), but finding collisions for $H_L$ or $H_R$ would be trivial (effort to break = $2^{32}$).

However, by construction, $H_L(x) \oplus H_R(x) = H(x)$.  Thus, the hash function obtained by XORing the outputs of $H_L$ and $H_R$ is identical to, and thus equally strong as, the original hash $H$.

That said, this doesn't necessarily mean that the XOR of two hash function always has better collision resistance than the original hashes — in fact, it's easy to construct examples where the collision resistance of the XORed hashes is worse than that of either original hash.  (For a simple example, let $H$ be a collision-resistant hash, and let $H_A = H_B = H$.  The either of $H_A$ or $H_B$ alone is collision-resistant, but $H_A(x) \oplus H_B(x) = 0$ for all $x$!)

More to the point, for real-world hash functions, it depends on why and how the collision resistance of the original hashes is compromised.  In some cases, XORing two hashes might improve their collision resistance; in other cases, it might not, or it might even make it worse.