RSA key pair generation using PRNG with same seed I see a lot of Q/A where persons are trying to generate a specific key pair using static data such as a password. Now say we use a known PRNG (dangerous assumption), seeded with a the data as a static seed, would this always generate the same key pair?

I presume it would generate the same key pair if you would use the exact same generation method - the application would be deterministic. I would however expect differences between implementations. The random data could be used differently, the sizes of p and q could differ and there may be subtle differences when choosing the prime numbers themselves.

To begin with, we have to assume your deterministic random bit generator is adequate for generating practically indefinite bit sequences given a single seed, and that your prime generation algorithm is such that it will always output a prime eventually, given any such indefinite pseudo random bit sequence.

Obviously, a 2048 bit two-prime RSA modulus can't have any factors in common with a 1024 bit two-prime RSA modulus, so, yes, changing the parameters might entail different output. Given my initial assumptions you will get an output in both cases, and they can't be the same for purely arithmetic reasons.

The same goes for implementation details: E.g. using a sieve or generating every candidate at random will also (likely) lead to different output, even if the DRBG sequence is the same.

Consequently, if you are asking e.g. because you want a way to store RSA private keys in a compressed format, your compressed format must contain an unambiguous indication of the number of primes to be generated, the bit sizes of these primes, the algorithm to be used for generating them, as well as any other parameter of the algorithm that might influence the output.

OTOH, if the problem is rather that you are looking for ways to tell if a given implementation suffers from RNG failures and has historically generated predictable RSA private keys, I am afraid this answer doesn't necessarily help much. In such case the conclusion would be that, no, you can't infer that your RNG is safe, just because your RSA private key generation procedure hasn't historically generated any prime number collisions.


What are the different use cases between an HMAC and digital signature? I understand that both an HMAC and digital signature are used to check the integrity and authenticity of a message. Further, I understand that a digital signature is non-repudiatible.

What I do not understand is when to use an HMAC vs a digital signature, in practice. I appreciate the help!

Generally a digital signature is created using a private key and verified with the public key of an asymmetric key pair. Public keys can be easily distributed to verify the signatures.

It is however required that the public key can be trusted to be part of the correct key pair; the public key needs to be trusted. For this a public key infrastructure or PKI can be used. Probably the best known PKI is the PKIX infrastructure used by browsers. Here the public keys are part of X.509 certificates where the certificates are part of a trust chain. If such an infrastructure was not present then the attacker may have substituted a public key of his own key pair.

One thing that is not possible with signature generation is to sign with the public key. This is what allows the public key to be publicly distributed.

HMAC (which is just a specific MAC) is used with a single secret key, which is required for both the generation of the authentication tag (the MAC signature) and the verification of the tag. Anybody who has this key can therefore be a verifier and signer. The secret MAC key cannot be part of a PKI because of this.

Due to the issues with key distribution MAC schemes are either used by one party, or by a limited number of parties that have exchanged keys.

A MAC and signature algorithm can both be used for message authentication / integrity or entity authentication. However, due to the differences in how the keys are handled, MAC doesn't scale as well as a signature generation scheme.

On the other hand, symmetric algorithms are much more efficient than asymmetric ciphers, so if there is a choice then a MAC can be used to speed things up. A MAC is generally also more secure than a signature generation algorithm with regard to the key strength and resistance against quantum crypt-analysis.

As an example, in TLS 1.3 for HTTPS, entity authentication of the server is performed using a digital signature where the server has a private key and the client trusts a chain of certificates from a root CA to the certificate of the server.

However, the messages themselves are protected by a fast MAC - nowadays part of an authenticated cipher - after the session keys have been established. These session keys are - as the name implies - only used for the specific connection.


Why PS does differ between PKCS1 v1.5 padding for signature and for encryption? As you may know, PKCS#1 defines two different padding in it's v1.5 : one for signature and one for encryption. Here they are :

The middle part is refered as PS in the standard.

There is only one thing bothering me : why does PS differ between signature and encryption ? I can't see any reason ti fixe PS to a '0xFF' string for both padding.

Maarten Bodewes answer is correct, but it is missing one important point.

It is actually NOT secure to have randomness in PKCS#1V1.5 padded signatures, otherwise signatures could be forged via bleichenbacher's e=3 attack.

Take a look at https://blog.filippo.io/bleichenbacher-06-signature-forgery-in-python-rsa/ to see what happens when signature verification implementations forget to assert that those bytes are actually 0xFF.


Where shall we use an authenticated encryption mode? I learned from Wikipedia that authenticated encryption modes include OCB, CCM, EAX, GCM, and so on. Does this mean that when we want to use authenticated encryption we shall use these modes? But these modes don't use public-key encryption or a hash-based MAC, which may be more advanced. So when shall we use an authenticated encryption mode, and when shall we use other MACs such as HMAC-SHA-256?

OCB, CCM, EAX, and GCM, being modes of operation, only work with block ciphers. Some of them, like GCM, are only defined for block ciphers with a particular block size. Note that these authenticated block modes do use MACs (GCM for example is essentially CTR mode with GMAC). Other MACs like HMAC and Poly1305 work with any symmetric cipher, including stream ciphers. So for example if you wanted to use ChaCha20 or were stuck with AES in CBC mode, you could use HMAC-SHA-256 or Poly1305.

These modes all work differently, and in fact are not always even based on the same concept. The only similarity they have is that they can all be used to turn an unauthenticated symmetric cryptosystem into an authenticated one. Internally, each construct is different. GCM for example is an authenticated cipher mode of operation, HMAC is a keyed pseudorandom function, and Poly1305 is a universal hashing one-time MAC. They are quite different, but they all happen to be useful for authenticated encryption.

Although the specific modes you provided all provide effective authentication, they're not always suitable for use everywhere. They are each based on completely different concepts, and they can each be used for only specific purposes. Their only similarity is that they can all be used to authenticate a symmetric cipher. Here is a quick summary of the various modes and where you might use them:

OCB, an authenticated mode of operation for cryptographic block ciphers, is fast and lightweight, but is patented so might not be legally viable for everyone.
CCM, an authenticated mode of operation for cryptographic block ciphers, was written as a non-patented alternative to OCB for use in 802.11, but is very slow.
EAX, an authenticated mode of operation for cryptographic block ciphers, was written to address several criticisms of CCM mode, but is just as slow as it is.
GCM, an authenticated mode of operation for cryptographic block ciphers, is fast and widely supported in hardware, but can be vulnerable to side-channel attacks.
HMAC, a specific type of message authentication code (MAC) involving a cryptographic hash function and a secret key, in ETM (Encrypt-Then-MAC) mode is easy to plug in to any cipher, but is not fast.
Poly1305, a universal hashing one-time MAC, is extremely fast and almost always a good choice. It's only recently gotten popular.

In general, you should not need to think about the specific authentication mode you use. You should be using a simple and friendly library that does all this for you, like NaCl (which I believe uses Poly1305).


DHE key exchange. Is it really secure? Context
I recently came across a video on the net showing the process of key exchange in Diffie Hellmann.
Alice and Bob want to communicate. Eve is the (wo)man in the middle.
This video is the basis of my question
http://youtu.be/YEBfamv-_do?t=6m22s
Question
Alice sends the modulo and the prefix to bob. Eve gets that.
What prevents Eve to have a giant table of all the calculations possible given a prefix and a modulo and the public value and intersect thos possibilities with the public value from bob ?
Yes the table would be very big but you can then iterate over the intersecting possibilities and try the numbers on the message up to the point to get something right.
i may miss something, but it is not that hard, even with very big numbers.
So what did I miss ?
Thanks

A lot of modern cryptography is based on some mathematical assumptions and aims to achieve what is called Computational Security. That means that the adversary (Eve) could get some information about the plaintext with a negligible probability and the adversary is modeled as someone with bounded computational power, storage and bounded time.
So all the (encryption) schemes are dimensioned in sort to achieve such level of security: that means that all mathematical elements are chosen to be large enough to make the best known attack feasible in a reasonable amount of time.

Even if this is a weaker notion of security, this assumption on the adversary is easy to accept in practice.

Other approach exists: Information theoretic Security or Perfect Security

So coming back to your solution based on a big table, if the scheme is correctly dimensioned the table you are supposed to use to attack the scheme would be so large that it cannot be stored in a (very very) large disk or to be (too) long to be generated.


Division property table of SBox In Table 12 (page 23) of the GIFT paper, the "Division property" table is given. I could not understand how it has been computed.
My questions:

May I have an algorithm on how to compute the table?
Is there any public implementation available? For example, Sage seems to have several SBox related implementations, but not this one.

Here's a simple Python implementation.
def anf(s):
    s = list(s)
    for i in range(n):
        for j in range(0, 2**n, 2*2**i):
            for o in range(2**i):
                s[j+o+2**i] ^= s[j+o]
    return s

def size_reduce(lst):
    res = set()
    for u in lst:
        if not any(u != v and u & v == v for v in lst):
            res.add(u)
    return sorted(res)

def expand(lst):
    res = set()
    for v in range(2**n):
        if any(v & u == u for u in lst):
            res.add(v)
    return sorted(res)

n = 4
# GIFT GS
sbox = 0x1, 0xa, 0x4, 0xc, 0x6, 0xf, 0x3, 0x9, 0x2, 0xd, 0xb, 0x7, 0x5, 0x0, 0x8, 0xe

# calculate ANFs of products
dppt = [set() for u in range(2**n)]
for v in range(2**n):
    a = anf([int(y & v == v) for y in sbox])
    for u, take in enumerate(a):
        if take:
            dppt[u].add(v)

# propagate larger monomials to smaller ones
for u1 in range(2**n):
    for u2 in range(u1):
        if u2 & u1 == u2:  # u2 \prec u1
            dppt[u2] = dppt[u2] | dppt[u1]

# remove redundant ones
dppt = [size_reduce(lst) for lst in dppt]
print("Reduced:")
for u, lst in enumerate(dppt):
    print(f"{u:04b}:", *[f"{v:04b}" for v in lst])

# or include all redundant ones
print("All:")
dppt = [expand(lst) for lst in dppt]
for u, lst in enumerate(dppt):
    print(f"{u:x}:", *[f"{v:x}" for v in lst])

Output:
Reduced:
0000: 0000
0001: 0001 0010 0100 1000
0010: 0001 0010 0100 1000
0011: 0001 0010 1100
0100: 0001 0010 0100 1000
0101: 0010 0101 1000
0110: 0011 0100 1001 1010
0111: 0101 1011 1110
1000: 0001 0010 0100 1000
1001: 0011 0100 1000
1010: 0011 0100 1000
1011: 0110 1011 1101
1100: 0011 0100 1000
1101: 0011 0101 1000
1110: 0100 1001 1010
1111: 1111
All:
0: 0 1 2 3 4 5 6 7 8 9 a b c d e f
1: 1 2 3 4 5 6 7 8 9 a b c d e f
2: 1 2 3 4 5 6 7 8 9 a b c d e f
3: 1 2 3 5 6 7 9 a b c d e f
4: 1 2 3 4 5 6 7 8 9 a b c d e f
5: 2 3 5 6 7 8 9 a b c d e f
6: 3 4 5 6 7 9 a b c d e f
7: 5 7 b d e f
8: 1 2 3 4 5 6 7 8 9 a b c d e f
9: 3 4 5 6 7 8 9 a b c d e f
a: 3 4 5 6 7 8 9 a b c d e f
b: 6 7 b d e f
c: 3 4 5 6 7 8 9 a b c d e f
d: 3 5 7 8 9 a b c d e f
e: 4 5 6 7 9 a b c d e f
f: f


Average number of multiplications in left-to-right k-ary exponentiation On page 617 in chapter 14 of  The Handbook of Applied Cryptography, the average number of multiplications in left-to-right k-ary exponentiation is $ l\times (2^k-1)/2^k$, where $l=\lfloor t/k\rfloor $, i.e. the number of k words in the $t+1$ bits exponent after excluding the leading 1. My question is, do the residual $t\;mod\; k$ bits require one extra multiplication when it is even, because we only precompute the odd number < $2^k$ ? If this argument is true, how should I calculate the correct average number of multiplications?

Thank @galvatron, especially for CPython implementation.  May I use an example to make my question clear.Let's say I want to calculate $x^{364086}$ with $k=4$. Because $364086=1011|0001|1100|0110|110_{2}$,$t+1=19$, $t=18$ and $l=\lfloor18/4\rfloor$=4. We will precompute $x^3$, $x^5$, $x^7$, $x^9$, $x^{11}$,$x^{13}$,$x^{15}$. Then calculate steps are

$x^{11}$ (from precomputation, no multiplication)
Square $x^{11}$ for 4 times we have $x^{176}$. Multiply it by $x$, we have $x^{177}$
Square $x^{177}$ for 2 times, we have $x^{708}$.  Multiply it by $x^3$, we have $x^{711}$. Sqaure $x^{711}$ for 2 times, we have $x^{2844}$
Square $x^{2844}$ for 3 times,we have $x^{22752}$.Multiply it by $x^3$, we have $x^{22755}$. Square $x^{22627}$ for 1 times, we have $x^{45510}$
Sqaure $x^{45510}$ for 2 times, we have $x^{182040}$. Multiply it by $x^3$, we have $x^{182043}$.Square it for one time, we have $x^{364086}$ (This is the residual bits which require one multiplication, but the chance this residual bits require multiplication is not precisely $(2^{4}-1)/2^{4}$, instead it is $(2^{3}-1)/2^{3}$)

I make a serious error that first k-bits word need one time of multiplication, and I apologize for it. However I still had some questions about this algorithm in the book.
The handbook also says the worst scenario require $l-1$ multiplication, but in this case we have to perform $4>l-1$ times of multiplication.

In Algorithm 14.82, you divide the exponent into $2^k$ windows. In the pre-compute stage, you encode those "bit-windows" into products of $x$. All of those bit-windows will be involved in multiplications except the $000...00_2$ window, which will be encoded as 1, hence no multiplication (I'm assuming $x\cdot 1$ is trivial).
Here's the trick: on average you're equally likely to be using the other $2^k - 1$ bit-windows. Another way of saying this is that you have a probability $\frac{2^k-1}{2^k}$ to pick a bit-window that isn't $000...000_2$. How many bit-windows did we split the exponent into? Precisely $\lfloor{t/k}\rfloor$, or $l$.
So the average number of multiplications (that aren't pre-computations or squarings) is $l\cdot \frac{2^k-1}{2^k}$. You don't have to worry about the evenness of the residual bits at all.
Advice
In practice, 14.85 (the sliding window method) is more efficient in practice, even if it's hard to count the number of steps it takes (as noted on page 617). If you're trying to implement something, check that one out. As a real-world example, CPython, the usual C implementation of Python, uses 14.82 for large modular exponentiation. They choose $k=5$ as that seems to work well in practice.
Example
I copied an example from here to count the multiplications.
Looking at Algorithm 14.82 on page 615, let's say I wanted to calculate $x^{250}$ and let $k=2$, or $b=2^2=4$. Write $250 = (11111010)_2$. With a window of $2$, you have $11|11|10|10$.
First, let's make the pre-computation table: even though we only need $11_2$ and $10_2$, let's follow 14.82 anyway:
$00_2\rightarrow 1$
$01_2\rightarrow x$
$10_2\rightarrow x\cdot x = x^2$
$11_2\rightarrow x^2 \cdot x = x^3$
We have four "bit-windows", only $3 = 4-1$ of which will be involved in multiplying something that isn't $1$.
Now, in the algorithm, step 3.1 is the "squaring" step, except we're multiplying by $x^{2^2}$ each time. After each "squaring" step, we have a multiplication step using the table above. So taking the bits two at a time we have:
$11_2: x^3, x^3$
$11_2: (x^3)^4=x^{12}, x^{12}\cdot x^3 = x^{15}$
$10_2: (x^{15})^4=x^{60}, x^{60}\cdot x^2 = x^{62}$
$10_2: (x^{62})^4=x^{248}, x^{248}\cdot x^2 = x^{250}$
The middle column is the squaring step (3.1), and the right column is the multiplication step (3.2).
So that gives us $2$ multiplications in the precompute stage, $6$ squarings (or $3$ "raising to the fourths"), and $3$ multiplications.
In this example, $t=8$, so $l = 4, 2^k = 4$, so the formula gives $4 \cdot 3/4 = 3$.
If you do the same thing with $k=3, b = 8$, you get $6$ precompute multiplications, $6$ squarings, and $2$ multiplications. In that case, our formula gives $l = \lfloor{8/3}\rfloor = 2$, and $2^k = 8$, so we calculate $14/8 \approx 2$ multiplications. Close enough?


Ring Signatures: Why is the combination function easy to solve? I'm reading Rivest's How To Leak A Secret and am on the part where they describe their signature scheme ("Generating a ring signature").

Why is computing $C_{k, v}(y_1, ..., y_r) = v$ easy? The computation seems to be "linear" or single-threaded, i.e. of the form $E_k(y_r \oplus E_k(y_{r-1} \oplus E_k(...E_k(y_1 \oplus v))))$. So let's say $r_i=s$ -- we require the value of $y_i$ to proceed with the computation (i.e. we can't continue to encrypt if we don't know its value), and so wouldn't we just be stuck trying all values of $y_i$ until we hit one that results in $v$ when the computation finishes?

Wikipedia also says that $C_{k, v}$ is trivially invertible given $r - 1$ parameters. I'm blanking out - why is this the case?

I did look at this answer but I didn't understand the line

  Start again at 12 o'clock and calculate going counter-clockwise until you arrive at 6 o'clock.

How can you "go counter-clockwise" when all the computations counter-clockwise have inputs dependent on all previous computation? All of the XORs have the previous computation as input.

Sorry if I've made any gaffs, this is my first *Exchange question.

I think I might have a potential solution, anyone care to confirm this? Let's take an example with 5 public keys (including ours). Let's assume our $s = 3$.

Let's borrow from that previous Stack Overflow post. Let's define a left var as

$$l = E(E(E(v \oplus y_1) \oplus y_2) \oplus y_3 )$$

and we know that

$$ z = r = E(E(l \oplus y_4) \oplus y_5))$$

Now let's start decrypting $z$:

$$D(z) = E(l \oplus y_4) \oplus y_5$$
$$D(z) \oplus y_5 = E(l \oplus y_4)$$
$$D(D(z) \oplus y_5) = l \oplus y_4$$
$$D(D(z) \oplus y_5) \oplus y_4 = l$$

We've solved for $l$! Solving for $y_s = y_3$ is easy now:

$$l = E(E(E(v \oplus y_1) \oplus y_2) \oplus y_3 )$$

$$D(l) = E(E(v \oplus y_1) \oplus y_2) \oplus y_3$$

$$D(l) \oplus E(E(v \oplus y_1) \oplus y_2) = y_3$$

And then we just do $g^{-1}(y_3)=x_3$, giving us our full signature.


Is there a maximum amount of data which can be encrypted using a symmetric (AES256) key? I am working on an application where we will be encrypting billions of small (< 2,000 bytes) records.  Combined, we are facing many TB of data.  Each record will be encrypted independently, using a unique IV/nonce.

We are aware of the restrictions around the reuse of IV/nonce values and the limits on the amount of data which can be encrypted using a key/IV pair (the NIST SP 800-38 series).  Given that each record will use a unique IV, this will likely be the primary factor driving the rotation of keys.

Is there a maximum amount of data - regardless of the number of encryption operations using a unique IV/nonce - where the AES key itself should be rotated, or is the retirement driven entirely by the restrictions set by block chaining mode?

You should generally never use a single AES key for more than a few petabytes of data because of the so-called birthday bound: Cryptosystems based on AES like AES-GCM tend to have distinguishing advantages bounded only by $$\frac{q(q - 1)/2}{2^b}$$ after processing $q$ blocks of data, where $b = 128$ is the block size, arising from the birthday paradox.

When $q \approx \sqrt{2^b} = 2^{64}$, the standard theorems provide essentially no security guarantees.  See sweet32 for what can go wrong when you reach the birthday bound of a block cipher—of course the birthday bound is much smaller for a 64-bit block cipher like Blowfish, where it is $2^{32}$, but the idea is still relevant to AES.

(Had we standardized a 256-bit block cipher like Rijndael-256 or Threefish, the birthday bound of $2^{128}$ would be completely irrelevant.  But we didn't, and while there are 256-bit block ciphers out there, hardly anyone ever uses them.)

Particular cryptosystems using AES may have smaller limits—for example, AES-GCM with a random nonce is unsafe for more than a few billion messages under the same key, because the nonce is only 96 bits long and the security degrades catastrophically in case of collision, which is expected to happen after only about $\sqrt{2^{96}} = 2^{48}$ messages.


Why bcrypt is one-way while Blowfish is reversible? While bcrypt is often regarded as an irreversible hashing function, it's based on the reversible Blowfish cipher. I'm just curious about how does this work. Here's the pseudocode from the wiki:

bcrypt(cost, salt, input)
  state ← EksBlowfishSetup(cost, salt, input)
  ctext ← "OrpheanBeholderScryDoubt" //three 64-bit blocks
  repeat (64)
    ctext ← EncryptECB(state, ctext) //encrypt using standard Blowfish in ECB mode
  return Concatenate(cost, salt, ctext)

I know that first bcrypt will go through EksBlowfishSetup key shcedule function which outputs a the state as a encryption key. Then it encrypts the text "OrpheanBeholderScryDoubt" with the key.

According to an answer in https://security.stackexchange.com/questions/66050/should-bcrypt-be-used-for-client-side-password-hashing/66056#66069, bcrypt is irreversible because BCrypt can be seen as encrypting with throwing away of the key. Although a known-plaintext attack is almost impossible with Blowfish, but is this what makes bcypt irreversible? Because I think a known-plaintext attack is still "computationally feasible".

What I want to know is that, if we get the encryption key (produced by EksBlowfishSetup(cost, salt, input)) with known-plaintext attack or in some other ways and we have the cost and salt which is passed to EksBlowfishSetup, is it possible to get the real password?

According to an answer here, EksBlowfishSetup is what makes brcypt one-way as you need to know all 3 arguments passed to it in order to retrieve the plaintext password. So can I say that it is EksBlowfishSetup that actually makes bcrypt irreversible?

Something might help you: Technology and Practice of Passwords

Because bcrypt uses Blowfish as a component inside an irreversible algorithm.  This is very common—many variable-input length cryptographic algorithms are built from smaller, fixed-input-length components that may or may not be reversible.

One example is the SHA-3 hash function, which is designed following an algorithm known as the sponge construction, which builds a hash function out of a reversible function (a permutation).


Using same AES-GCM setup for multiple packets? Most cryptographic libraries I've encountered uses some variant of processPlaintext(...) and then doFinal() to produce the ciphertext and resets the state.

In the context of packet communications, it feels like it would be optimal to setup key and IV once and then use that single initialisation in some way for all packets on the same channel.

In the case of CBC + padding, one could re-initialise the cipher with the last cipher block as IV.

(If I use a stream cipher, or manually implement CTR, it's straightforward of course.)

It would be nice to be able to use GCM to avoid manually adding authentication. However, it would appear that the usual implementations are geared towards encrypting a single packet - and resets all internal state on doFinal.

I would like to provide only a single IV for GCM, and then in some safe way either keeping the original state, or derive consequent IVs from the initial IV in a secure manner.

What I wonder is consequently:

Are there implementations that allow you not to reset the state when finalising a packet (i.e. making encryption and authentication dependent on the previous packet)? Failing that, what would be a safe way to derive consequent IVs from an initial IV value?

(I've not read about GCM sufficiently in depth - so I have no idea if there is a significant cost to setting up GCM with an IV)

In the context of packet communications, it feels like it would be optimal to setup key and IV once and then use that single initialisation in some way for all packets on the same channel.

It might be optimal for efficiency standpoint, but we also care about security; it isn't necessary very good for security.  You mentioned that, with CBC mode, you can use the last cipherblock as the next IV; well, you could, but there are known weaknesses with that involving chosen plaintext.  Other modes don't share this specific weakness.

As for GCM, well, it was designed to be used in a very specific manner (and proven to be safe in that manner).  However, if you use it in a different manner (such as reusing the same GCM state to both output an authenticate tag for one message, and continue to encrypt with another) would be, at best, playing with fire.

Now, to answer the questions you asked:

  Are there implementations that allow you not to reset the state when finalising a packet (i.e. making encryption and authentication dependent on the previous packet)?

I should hope not.  Using the same nonce with two different messages is known to be VERY BAD, and the obvious way to do it with continuing to use the current GCM state would appear to fall into that weakness.

  Failing that, what would be a safe way to derive consequent IVs from an initial IV value?

This one is easy: the only requirement that GCM has for IVs (nonces in GCM terminology) is that you can't use the same one twice; you can use any method of generating them that abides with this requirement.

Hence, one easy way to generate IVs is to generate them sequentially, as in:
 $$IV_{next} := IV_{previous} + 1$$

Oh, and you did mention that:

  I have no idea if there is a significant cost to setting up GCM with an IV

Assuming you use a 96 bit IV (which is the cheap size for GCM), the total cost is "one AES block encryption" operation.

Hence, selecting a new IV for each packet is both moderately cheap, and safe.

And, on a side topic: you mention that you were intending this for use with "packet communication".  Well, normally with this level of communication, you need to be able to deal with packet drops; that is, if the sender transmits a packet, but the receiver doesn't receive it correctly (or at all).  Because of this, I suspect you'll want to design you system so that the receiver can process packet 5, even if has never received packet 4.  Among other things, this implies that you might not be able to use implicit IVs; you may need to send them explicitly in the encrypted packet.


Do we have to consider the cryptographic properties of the decryption, if we're only using the encryption? Treyfer for example has slower diffusion in decryption. It has full diffusion between words in 2 rounds for encryption and 7 rounds for decryption.

Do we have to consider the (bad) cryptographic properties of the decryption algorithm, if we're only using the encryption algorithm? (For example we are using Treyfer in CTR mode.)

Differently worded: Do we have to consider the bad cryptographic properties of the decryption algorithm if the encryption algorithm can be considered strong as we're usually only using the encryption algorithm?

Diffusion is a requirement for a secure cipher, but it is not by itself sufficient. So even if a certain number of rounds has "full diffusion", it does not mean that the number of rounds is enough. In the case of Treyfer, the decryption direction requires five more rounds for full diffusion, but the suggested number of rounds is much higher at 32. (Even that is not really secure, because the key schedule is broken.)

However, if considering block ciphers more generally the question is whether a block cipher can be secure in the encryption direction without being secure in the decryption direction. The answer is probably yes. For example, Luby and Rackoff showed that a three round Feistel network with a secure PRF is secure against adversaries without access to a decryption oracle, but needed four rounds to prove security against adversaries with such access (which they called strong PRP).

So there seems to be a security difference between a block cipher used only in the forward direction and a block cipher used in both directions.


Verifying integrity of large files I'm looking for the most efficient in memory and time way to verify integrity of  large files which have to be encrypted as well.

Using SHA256 and other crypto hashes over the whole encrypted file?
Split it into blocks and encrypt+hash each one separately?
Use authenticated encryption? Again, block-wise or as a whole? GCM or are there any better options today?
Something else?

Thanks!

I am going to have to say splitting it into blocks. Although your definition of large may differ from mine, GCM is unsuitable for large files, and hashing the entire file can be problematic, especially if the file is spread across storage devices, and parts of it are not currently available for reading in the sequence you want.

Splitting it into blocks, say 4-16MB at a time, will incur very little overhead for storage of a hash, allow you to encrypt several blocks at a time in whatever order is currently available, and allow you to verify integrity of selected data out of sequence.

Each large file would be given an index file, which contains the IVs and integrity hashes for each block, which can then be encrypted and authenticated independently of the blocks. If you have verified the index data, you can perform random reads of the blocks by validating their hash and decrypting them.

As long as you are using secure methods for hashing, authenticating, and encrypting, (say SHA-512, HMAC-SHA-512, AES-CTR) the full system should be secure, and be very simple to implement, in addition to being extremely fast and being able to handle extremely large files. At least 36 index bytes would be required per block depending on implementation, so a 1TB file with 16MB blocks would require a 2.25MB index file, 100TB 225MB, and so on, and the ability to scale up to 64PB per large file, using a 144GB index, which could also be broken into blocks using the same method if necessary.

You would be looking at around a 60ms latency or less to access any 16MB block of the large file due to encryption/hashing overhead, if the index file is already authenticated. Smaller blocks would give lower latency but larger index files. Spinning storage latencies are larger and there is overlap between read and decrypt, so the performance hit on a modern cpu would be much smaller, probably well under 10ms per block, as decryption can be performed at the same time as hashing with the same read, in 1KB increments, and the decryption speed is not the limiting factor. When using faster storage such as NVME drives, a hash tree mode will improve performance if you have CPU cores to spare.


What are the current limitations (and capabilities) of Functional Encryption used for access control? I'm trying to make my way in Functional Encryption used for access control.

I read a lot of papers such as "How to Run Turing Machines on Encrypted Data", "Functional Encryption: New Perspectives and Lower Bounds", or "Attribute-based encryption for circuits" and I ended up with a feeling of uncertainty in my understanding as they are quite hard to digest.
What I'm looking for is an ABE-like scheme where policy may contain both logic and algebraic gates. For example:

"job=doctor" AND "age mod 2 = 0"

this (stupid) policy provides access to the plaintext to doctors whose age is even.

Pushing on the line, a policy could include arbitrary computation such as a signature verification algorithm. From what I read, I feel the only hope of achieving these goals lies in FE. Is there a scheme able to meet these requirements (at least the first policy)? At which cost?

How much of what I wrote is reality, what is achievable and what is fiction?

In functional encryption, the function don't apply on access policy. In FE the receiver obtain the function of message. Attribute Based Encryption for arithmetic circuits may help you. Fully key hommomorphic encryption for ABE for arithmetic circuits from Boneh et. al presented to this problem. Although the FE is the general of ABE.


Fortuna: With a Single Entropy Source I have worked on a random number generator that has turned out to give results pretty close to those of Fortuna with a single source.

I was wondering how it affects the performance and claims of Fortuna as a RNG in this special case of using a single source.

How will the recovery rate be affected?

I think a solution which does not compromise with a multi-pool system can be:
Use a single source to distribute secrets to a different pool. (i.e. my events processed though from one observation go to different pools as per the original design of Fortuna.)

This will be slower, but it will still be a good randomness generator without any compromise. Is this true?

The recovery rate is unaffected by feeding Fortuna with a single source.

This is Fortuna:

The 32 entropy pools live inside the accumulator.  The accumulator collects entropy via the following function:-

function AddRandomEvent
input: R prng state, modified by this function.
s Source number in range 0, ... , 255.
i Pool number in range 0, ... , 31. Each source must distribute its
  events over all the pools in a round-robin fashion.
e Event data. String of bytes; length in range 1, ... , 32.

Ferguson et al. suggest feeding the pools in a round robin fashion. I disagree as they never catered for a steady entropy rate.  They have developed /invented this equation to bound the recovery time:-

with t = time, i = 13 and t being time.  At 8 bits /s, this leads to t being 1/8th second. I can't get my head around it and believe it to be technobabble to paper over the fact that they have no input entropy estimator.  They explicitly state that input entropy measurement is irrelevant to the security of the PRNG. From the architectural diagram above, your entropy enters the accumulator at a rate of 8 bits /s.  Fortuna's creators have decided that 128 bits of security is sufficient.  It follows then that even with a fully compromised generator state, total recovery to design level security should occur in 8 seconds. And the generator is always seeded with at least pool 0, so I suggest feeding entropy directly into that pool only.

There is a get out of jail card for the authors in their statement limiting the feasible attack vectors. They disallow the attacker controlling the destination pool for his attack entropy.  Hence the round robin method of securing the reseeding.

For the life of me, I cannot fathom the wisdom of multiple entropy pools.  If all pools are eventually used for reseeding, why can't you have a single pool as the default Linux generator has?  That works. I think that some of the analysis problems might be to do with the huge complexity of design.  There are so many variables that it's difficult to perform a rigorous mathematical analysis.  The main confounding factor is the automatic reseed rate affected by rapid output.  I suspect that only a Monte Carlo simulation can resolve this accurately.  Remember that these guys invented Yarrow and that didn't work well enough to stay with. And I don't like it as it's too complicated and unpredictable(!).


What are Alternatives to basic ROT-n Ciphers which Don't Lose 'Context'? I've got this neural network running like a champ on my machine.  The data is concatenated works of shakespeare in a plaintext file.  RNN trains on the data, then gives you a 'sample', aka it tries to freestyle its own shakespeare based on what it has learned.

So now I've encrypted the dataset with a standard mid ROT cipher, and gave that to the NN to train on.  Which it did, and it returned a result which was ROT ciphered.  Decrypting that yielded valid results. As it should have, training on data that kept all its 'context', without randomness, unpredictability, or 'fuzz'.  Not sure if those are the exact words, but you get it.

I'm wondering if there are any other ciphers, or really any other algorithms like compression schemes or what have you, that may yield the same results as my previous experiment?  That training on its encrypted data would likely yield a sample that could then be decrypted accordingly?  Or would most other stuff be 'lossy' in some way?

Any letter (simple) substitution cipher will do (it might be necessary that it special-cases any character that your text-generating software special-cases, like space, tab, linefeed, perhaps punctuation).

ROT-n is a particular case of substitution cipher, with a much smaller key set (if we restrict to uppercase letters, ROT-n has $26<2^5$ keys, versus $26!>2^{88}$ keys for a general substitution cipher; that less than 5 bits versus more than 88).

Depending on what the text-generating software does, it might also work to substitute words, in addition to letters. That further increases the key space.

Substitution ciphers are hopelessly insecure, thus it is unclear what this achieves, or what is attempted.


Why does the Bombe not consider the Ringstellung when determining stecker pairs? I am doing research on the Bombe Machine, and I read that when the Bombe tries to find the stecker (plugboard) partners of letters, it only needs to use the rotor types and arrangement and also the "rotor core offset," which is just a combination of the rotor positions and the ring settings.

However, the ring setting does matter. If the 1st rotor position is A and the ring setting is A, the core offset would be the same as if the rotor position was B and the ring setting was B, but the 1st rotor output would be shifted down a letter, which would produce a drastically different output.

So, how do they account for that? I don't see how neglecting the ring setting is fine.

I didn't want to delete this question, but it seems like after pondering this for a week I finally understand right when I seek help online. When the ring setting and the rotor position all increase by the same amount, they cancel and so the ring pretty much stays the same. Although the contact points of the ring to the alphabet ring is different, it makes no difference, since it's not the contact on the alphabet ring that matters but instead the contact of the pin with respect to the next rotor.


How to distribute session keys in public key cryptography? In public key cryptography we can also use session keys which are symmetric. How do the sender (say a server) provides this session key information to its clients?

If the sender (here server) provides the session key by encrypting using its private key, all the clients (including a malicious one) can decrypt (using available public key) and see that session key , right? The server can't use public key to encrypt the session key since none of the clients have private key to decrypt it.

I am wondering what information I missed here to understand the basic idea of distribution of session key?

Normally, the client sends the session key.  This means that clients cannot decrypt other session keys.

Although this approach ensures each session is safe from information gathered in other sessions, it doesn't guard the session against an attacker later acquiring the server's key and retrospectively decoding all recorded sessions.

To guard against that threat is termed Perfect Forward Privacy.  This can be achieved using ephemeral Diffie-Hellman (EDH,DHE) key exchange.

There is an excellent blog explaining recent improvements in Perfect Forward Secrecy which is well worth reading.


poodle padding multiple blocks? I'm quite new to the topic and read a bit about poodle and padding oracle.

I quite understand the "regular" padding oracle attack, substituting the last byte of block(n-1) to determine the last byte of block(n) - by "myguess" XOR 0x01 for the last byte and so on.

Articles on poodle however state, that the attack is based on placing my target block to replace the padding. As the padding is not checked, the server will accept the message if the last byte of my replacement happens to be the length of the padding, as the server will cut the padding correctly and be able to check the MAC.

Now, as stated here there always is padding, as you could not otherwise know, if the message just happened to fit into blocks.

I understand poodle to work like this:

i forge request with javascript, forcing the victims' browser to copy the encrypted sessioncookie-block as padding
i create at max 256 of these requests, moving my cookie-block further down the line, thus creating longer and longer paddings until the server accepts the request, telling me that the decrypted last byte is the position of the last byte in the forged padding
i "write down" the last byte, drop it and repeat the process with the second to last byte  and so on.

if the last byte of my sessioncookie now happens to be FF, is would need a padding of 255 bytes length, which is multiple blocks of just padding.

Will sslv3.0 implementations just accept that i padded more than is reasonably neccessary?

Or have i misunderstood the concept? I have not found an article really explaining in detail.

I'm glad for links to detailed technical descriptions, videos, most of all for simple corrections in my description of the process if it isn't correct.

If the last byte in the block is larger than the block size, that would generate a padding error in SSL 3.0.

SSL 3.0 padding is up to $BlockSize-1$ bytes of unspecified data, and one byte with the length of the padding (not including the length byte itself).  TLS 1.0 and above allow padding longer than the block size, and requires that each byte contains the length.  The POODLE attack is against 3.0 (after downgrading the connection).

In the POODLE attack, you need to arrange two things, the length of the message (plus MAC) is exactly a multiple of the block size, and the byte you want to find out is moved to be the last byte in a block.

If you substitute the padding block with the block with the desired byte, it will occassionally (1 in 256) decode to be 15 (for a 128-bit block size), and the message will be accepted (because the padding byte now leads to a correct MAC, which is at the end of the previous block).  If it isn't accepted, generate a new encrypted message and try again (which will randomly change what that last byte decodes to, from any or all of a new key, a new IV, or any changed fields in the plaintext).

If you take the last byte, XOR it with the last byte of the previous block's ciphertext, then XOR it again with the last byte of the ciphertext preceding the original location of that block, you'll get the correct value of that byte.

Repeat after manipulating the plaintext so that another (unknown) byte is in the last byte of a block (without changing the required padding amount).

An earlier version of my answer was describing a Padding Oracle attack against PKCS#7 style padding, which relies on being able to distinguish between a padding error and a MAC error, the POODLE attack distinguishes between error and no error.

With TLS, padding can be longer than one block, and the implementation shouldn't distinguish between padding and MAC errors, but it's still susceptible to timing attacks, even if it calculates a MAC after detecting a padding error.


HMAC for short messages I am using HMAC (hmac-sha256 to be precise) message authentication without encryption.  My question is, is having a short message make it easy to determine what my secret key is?

My C# code is as follows

HMACSHA256 hmacSha256 = new HMACSHA256(new byte[]{0xfa, 0x35, 0x24, ..., 0x5e}); // 64 byte secret key

byte[] authForMessageA = hmacSha256.ComputeHash(new byte[]{0x25}); // very short message
byte[] authForMessageB = hmacSha256.ComputeHash(new byte[]{0x66}); // another message, same key

I am exposing both the message (0x25 and 0x66) along with their authentication hashes to the public, does this make it simple for a hacker to determine my secret key (brute force or otherwise)?

No, you are not leaking any information except how to MAC those specific values with the specific key you are using. Using a short message is exactly as secure as using a long message.

For the following, remember the definition HMAC (K,m) = H((K ⊕ opad) || H((K ⊕ ipad) || m)). There are two hashes here, an outer hash and an inner hash nested inside the outer one. The message is inside the inner hash.

Suppose I am an attacker who has your message and MAC result, and I want to derive your key. In order to get your key, I will need to do a brute-force guess. I already know the function H, I know the constants ipad and opad, and I know your message m. I need to try building lots of hashes using different key values until I come up with the right HMAC. The hardness of this task is dependent entirely on the length of K; the length of m is not a factor.

Note, however, that if you are not using a temporary key, then any message/HMAC pairs you give out will be valid for your key, so an attacker could impersonate you in a replay attack for any messages she has seen from you.


How to decode a Playfair message with a partial key? I've been given a Playfair ciphered message and a partial key, where a few key letters are missing:

Corrupted key (? stands for a missing letter): ?ENVGQ?RKBDXACU?LIOW
Ciphertext: LGOXMVYHIMISYSSQWMZX

I tried to solve this myself and got the plaintext WELCHOQLHNLRBHED, which is clearly wrong.

What methods can I use to decode this message?

The quick and dirty way would be to write a computer program to try all the remaining possible key letters in the ? positions and print out the resulting plaintexts.  Hopefully, one of them will stand out as being obviously correct.  Remember that each letter can occur only once in a Playfair key, and that your key is already pretty long, so there aren't a lot of unused letters left in the alphabet for the unknown positions.

The slightly more clever method (which is probably what you're supposed to use) would be to first see if any of the ciphertext letter pairs can already be decoded without knowing the missing key letters (or any of the letters on the last row of the key matrix, since they obviously depend on the missing letters too).  You can do this by hand (again, presumably the intended method, since that's the way you'll actually learn how a Playfair cipher works), or you can cheat and use any standard Playfair decoder tool and just try a couple of different variations of the key and see which letters of the plaintext change.

For example, here are the results of trying to decode the message (using this online decoder) with a few different choices of missing letters, out of the eight letters not already present in the key (F, H, M, P, S, T, Y and Z):

Ciphertext:              LG OX MV YH IM IS YS SQ WM ZX
Decoded with ??? = FHM:  WE LC OF SK LW LT TP PH OW SU
Decoded with ??? = PST:  WE LC YN MF AI LR HK QB IZ HU
Decoded with ??? = TYZ:  WE LC PN EL AI WM BH FB IS LD

You could try a few more choices, but what should be apparent here is that decoding the first two letter pairs clearly isn't affected by the missing key letters, and thus, that the plaintext begins with the letters WELC.  Now, there aren't a lot of English words that begin with those letters — in fact, I can only think of a single really likely one.

Assuming that the plaintext begins with "Welcome", you can now rule out any choices of missing letters that would result in MV decrypting to anything other than OM.  Even if that's not enough to solve the problem completely, you should at least be able to lock in some more plaintext letters, and so hopefully guess more words in the plaintext, and so get more known plaintext letter pairs, and so on.

In fact, if you consider the way the Playfair cipher works, knowing that OM encrypts to MV would immediately tell you something useful: namely, that the letters V, M and O must all appear in the same row or in the same column, and that they must be adjacent and in that specific order.  In this case, looking at the key matrix:

? E N V G
Q ? R K B
D X A C U
? L I O W
? ? ? ? ?

this tells you that, for this plaintext / ciphertext pair to be correct, M would have to appear in the fourth column of the last row, below O and above V.  (Remember that the rows and the columns wrap around.)

Unfortunately, using the standard Playfair key matrix setup, where any letters left over from the key are simply appended in alphabetical order, there is no way to get M in that position simply by filling in the ? marks in the key!  So either:

my guess that the first plaintext word should be "welcome" is wrong,
the ciphertext contains an error (always possible, although hopefully rare in well designed crypto puzzles),
the key is actually longer than what we're given, and we're supposed to arbitrarily assign the remaining five letters for the last row too, or
there's something else funny going on, and this isn't a standard Playfair cipher after all.

If we assume #3 above, and start shuffling the letters in the last row, it is in fact possible to get a plaintext that begins with "welcome to" and where the rest looks at least vaguely like English (although not obviously enough so for me to declare it as clearly the correct solution without knowing where the puzzle came from and what other clues might be available).  So, alas, I have not been able to definitively confirm that these steps will yields a correct solution to your puzzle.  But at least they do illustrate the general method by which such problems can be attacked.


Whats wrong with my El Gamal signature example I'm trying to digitally sign a message m using El Gamal. So far I've been unable to verify the digital signature ive made using El Gamal.

I am using prime number, p = 8369. prime root g = 3031. Private key parameter x = 61. and the message m = 9876

I am calculating y and r to be:

y = 3031^61 mod 8369 = 3400
r = 3031^11 mod 8369 = 2954

Signed message s, s = k^-1 (m – xr) mod (p-1)

s = 11^-1(9876 – 61*2954) mod 8368
s = 13788/11 which cannot be right

I then tried removing the inverse power from 11 which I had seen in another example which produced the following

s = 11(9876 – 61*2954) mod 8368 = 934

When i used v = g^m mod p and w = y^r r^s mod p I got

v = 3031^9876 mod 8369 = 6346
w = 3400^2954 * 2954^934 mod 8369 = 855

V and W dont match meaning the signature is invalid and I've made a mistake in my verification. Where did I go wrong and am i on the right track?

In general case, $k^{-1}$ is equal to $x$ such that $x \cdot k=1$. In your question, to computing $11^{-1}$, you must find $x$ such that $x\cdot11=1 \pmod {8368}$. You can compute $x$ by using the extended Euclidean algorithm.


Signing 14 bytes of data for an embedded device I need to sign a 14-byte string and want to verify that string on the device.

Since there is already an AES-Library on the device, I thought about using the following scheme:

Use AES with a fixed IV and a fixed secret key to encrypt the following string:

  "2byte Random Padding | 14byte data"

And send the 14byte data followed by the 16byte result of the encryption.

Is this scheme totally dumb?

Thanks!

Regards,
Philipp

@fgrieu is right.  I concur with the recommendation to use CMAC.  That is a simpler, more general solution.  Also, if space is at a premium, you can probably truncate the output of CMAC to 8 or 10 bytes, while still receiving adequate security.

One remaining vulnerability is that this scheme does not prevent an attacker from replaying, re-ordering, or deleting messages.  If you send messages A,B,C,D, the attacker can arrange for the recipient to receive D,B,C,B,B (for instance).  If you want to defend against that, you could use a sequence number (or possibly a timestamp).

Another vulnerability arises if you use this key for multiple connections.  For instance, let's suppose Alice, Bob, and Carol share a single CMAC key.  Then if Alice sends message M to Bob, the attacker can arrange to redirect the message to Carol and make Carol think that Alice sent M to her.  One defense is to never reuse the same CMAC key (make it unique to a pair of endpoints and a direction).  A different defense is to include the identity of the sender and the recipient in the input to CMAC, i.e., you compute T = CMAC(K, sender || recipient || message) and use T as the authentication tag.  This solution does not increase the size of the packet, so it is essentially free.


ElGamal signature: Forging a signature of a specific form I have a question I can't solve from one of the courses I'm currently taking:

  Show that given a legitimate ElGamal signature $(S,R)$ on a given message $m$, an attacker
  can compute a signature on messages of the form: $m'=(m+bS)a\mod p - 1$,
  when $b\in Z_p^*$ is chosen as the attacker wishes and $a=g^b\mod p$.

  Hint: Observe the value of $g^{ma+baS}$

I assume that the deadline for the homework is passed, so I will provide an answer:

Let us assume that we have the public key $y=g^x \pmod p$ and the private key to be $x$.

Computing an ElGamal signature for a message $m \in Z_p^*$ amounts to:

choosing $k\in Z_p^*$
$r\equiv g^k \pmod p$
$s\equiv (m-xk)k^{-1} \pmod{p-1}$ which is equivalent to  $m\equiv xr+sk \pmod{p-1}$

The signature for $m$ is the pair $(r,s)$ and verifying the signature amounts to checking whether $g^m \equiv y^r r^s$ holds and it is easy to check that this holds, since we have $y^r r^s \equiv g^{xr+sk} \equiv g^m \pmod p$.

We have to show that given a signature $(r,s)$ allows to forge signatures of the type $m'\equiv (m+bs)a \pmod{p−1}$ for $a=g^b$ with $b\in Z_p^*$ chosen by the adversary.

You got a hint $g^{m'} \equiv g^{am+abs}$, but it is better to see if you go one step further:

$g^{m'} \equiv g^{am+abs} \equiv g^{a(xr+sk)+abs}\equiv g^{axr+ask+abs} \pmod p.$

Now, on the right hand side of the verification equation $y$ is fixed. So we have to figure out how $r'$ and $s'$ need to look like such that the verification equation can hold:

$g^{axr+ask+abs} \equiv y^{r'}r'^{s'}$

Observe that for the first term we have to set $r'\equiv ra \pmod p$ which is equal to $g^{k+b}$. Consequently, we are still missing $a$ and thus set $s'\equiv as \pmod{p-1}$.

If we now look at the left hand side of the verification equation, we obtain:

$y^{r'}r'^{s'} \equiv y^{ra}r'^{as} \equiv g^{xra}(g^{k+b})^{as}\equiv g^{xra+ask+asb}\equiv g^{m'}$

which shows, that the verification relation holds for these types of forgeries.


Integrity of format preserving Encryption In this question regarding integrity of FPE, the main point of the answer is that:

  FFX is not malleable. [...] FFX can provide integrity protection in very limited circumstances.

So I was wondering, in practice how does one enforce integrity of the data? For instance if the systems stores credit card information and expects the correct format, it will be impossible to append a MAC or something like that.

What are the current best practices for FPE?

The non-malleability of FPE is not a property that can be universally or even most of the time relied on to provide strong integrity protection, as the answer you're quoting points at when it says that "FFX can provide integrity protection in very limited circumstances" (my boldface).  Such cases are the exception, not the rule.

For any cipher that produces ciphertexts no longer than the plaintexts, the best it can offer in terms of integrity is the very weak property that an attacker's forged ciphertexts will decrypt to pseudorandom plaintexts, which the attacker cannot in practice predict better than chance and thus exploit.  This really isn't much, because the defender is unable to detect the forgeries, but most encryption-only modes don't even offer that much.

The exception that the answer you link to talks about is cases where plaintexts are redundantly coded—where the alphabet and length of the strings in which the messages are coded allows for $M$ distinct combinations, but there's only $N < M$ distinct valid messages and you can unambiguously distinguish these $N$ coded messages from the other $M - N$ invalid ones.

In that circumstance, if we encrypt messages with a non-malleable cipher, an attacker who forges a ciphertext only manages to hit upon one that decrypts to a valid plaintext with $N/M$ probability.  In exceptional cases where $N/M$ is extremely small (say, $2^{-128}$) this could offer meaningful security, but if we're talking credit card numbers, which have a single checksum digit, it means an attacker's forgeries would be undetectable 10% of the time. Not good!

As for best practice, the thing I'd say that FPE should be avoided whenever you can, period.  It's not designed to offer optimal security, but rather it's a compromise for situations where legacy issues prevent you from using optimal solutions.


What the X stands for in the front of Elliptic curve names like X25519 I have seen Curve25519 and X25519, Curve448 and X448. I've seen a small note in this answer

(Historical note: Originally, X25519 was called Curve25519, but now Curve25519 just means the elliptic curve and X25519 means the cryptosystem.)

Is it a standard to say CurveABC is the Elliptic Curve and XABC is the cryptosystem?
Or, it is just a convention between the Elliptic Curve Cryptographers.

It is an open standard by IETF.org
We can find the details in the mail archive of IETF, D. J. Bernstein's response;

It has become increasingly common for "Curve25519" to refer to an
elliptic curve, while the original paper defined "Curve25519" as an
X-coordinate DH system using that curve. "Ed25519" unambiguously refers
to an Edwards-coordinate signature system using that curve.
Kenny and others in Toronto recommended changing terminology to clearly
separate these three items. Let me suggest the following terminology:

"X25519" is the recommended Montgomery-X-coordinate DH function.
"Ed25519" is the recommended Edwards-coordinate signature system.
"Curve25519" is the underlying elliptic curve.

All relevant coordinate systems already have standard names in the
literature, and I would suggest sticking to those names whenever it's
necessary to discuss the coordinate systems per se: [...]

Bolds are mine.


The internals of bcrypt I'm attempting to get a better understanding of cryptography and have run into some questions about bcrypt.

Bcrypt relies on the blowfish cipher, which is a reversible method of encryption. But bcrypt is not reversible. How is that possible? Or am I mistaken? What does bcrypt do on top of blowfish to make it irreversible?
Why does bcrypt use blowfish instead of twofish or threefish?

You are correct, Blowfish is a reversible cipher if you know the key. Bcrypt has three parameters it uses to hash a password:

Salt
Password
Cost

It derives a key using the salt, password and cost to encrypt the well known text "OrpheanBeholderScryDoubt" and not the password itself. So verification would be performing the encryption again on this string and see if the ciphertext is the same. The salt prevents scenarios where two users would use the same password to show up as the same ciphertext. So if you don't have the password you can't generate the ciphertext.

The reason why they are using Blowfish instead of twofish or threefish, is that it was published in 1999, whereas Twofish was from 1998 and threefish 2008. Bcrypt was seeking properties offered by Blowfish, namely slown key derivation so there was no reason to not use the already established blowfish (cryptographers are conservative and prefer to use proven solutions rather than cutting edge ones).


How to represent the point-at-infinity(Elliptic Curves) in code? I am writing code for Elliptic Curve Cryptography. I have a class class EllipticCurvePoint.

class EllipticCurvePoint{
    FieldElement x, y;
};

I need to support point-at-infinity (which should behave as if it is an object of type EllipticCurvePoint). Only thing I can think of is to reserve (-1, -1) for this but x and y can assume values only from {0, 1, ..., p-1} (p being the Field they belong to). If I want to represent it this way, I would need to add support for -1 in the classes FieldElement and Field too.

I have also overloaded the + and the * operators which work perfectly fine for other points. But I cannot think of a way to represent point-at-infinity which can work homogeneously with the rest of the code and I wouldn't have to change the parent classes(Field and FieldElement).

Is there any elegant way to achieve this? Thanks a lot for your time!

I suppose it is a short Weierstrass curve. There are several possibilities:

Projective coordinates: a point $P = (x,y)$ is stored with three coordinates, $X$, $Y$ and $Z$ that satisfy $x=X/Z$ and $y=Y/Z$. We note $P=(X:Y:Z)$. That means a point can have more than one representation (it is the same as fractions, $\frac 3 4$ is the same as $\frac{15}{20}$). The curve equation $y^2 = x^3 + Ax + B$ becomes $Y^2Z = X^3 + AXZ^2 + BZ^3$ and the point at infinity is the point that have $Z=0$, then you can check that $\infty = (0:1:0)$ (or more generally, $(0:\lambda:0)$ for any nonzero $\lambda$).
Jacobian projective coordinates, same as above but with $x=X/Z^2$ and $y=Y/Z^3$ and the infinity point is $(1:1:0)$ or more generally $(\lambda^2 : \lambda^3 : 0)$ for any nonzero $\lambda$.
If you keep only affine coordinates, you can add a boolean is_infinity in you class.

Anyway, depending of how you will implement addition formulas on the curve, you must know that most of them won't work flawlessly with all the points, unless you use complete unified formula (see here for Weierstrass curves).

On a side note, you can take a look at Edwards curves where the infinity point has an affine representation (the Edwards form of Curve25519 or Curve448 are used for the cryptographic primitive signature EdDSA).


Why is the Keyspace of a Substitution Cipher not 2^26 but 2^88 It is known that a cipher has a keyspace of cryptographic algorithm whose key length is $n$ is given by $2^n$, but the keyspace of the substitution cipher is $2^{88}$ which is an approximation of $26!$. (I am considering an alphabet of 26 letters)

Assuming the key length is 26 (which it should be for the alphabet) Why is it not $2^{26}$?

The key space of a cryptographic algorithm whose key length is $n$ is given by $2^n$

No. There is confusion between:

keyspace (or key space) $\mathcal K$, which is the set of possible keys.
keyspace size (or size of the keyspace) $\|\mathcal K\|$, which is the number of possible keys (an integer).
key length (or key size) in bit, which can be defined as the base-2 logarithm of the keyspace size (not necessarily an integer). If we note $k$ for the key length in bit, the keyspace $\mathcal K$ has $\|\mathcal K\|=2^k$ keys, and $k=\log_2(\|\mathcal K\|)$.
number of symbols used for a representation of a key. If the key is represented as $n$ symbols which each can take $s$ values, then $\|\mathcal K\|\le s^n$ and $k\le n\log_2(s)$. These inequalities turn to equalities when all combinations of symbols yield valid keys (which is typical in modern symmetric ciphers).

This is a slight simplification: often, and always when effective is added before key, equivalent keys (that is keys yielding the same effect on decryption) are aggregated and counted as one. However this distinction is not useful for a mono-alphabetic substitution cipher.

In a mono-alphabetic substitution cipher for an alphabet of 26 letters, with the key represented as a list of ciphertext letters for each plaintext letter in alphabetical order:

The keyspace is the set $\mathcal K$ of all permutations of the alphabet.
The keyspace size is the number of elements in that set, that is the integer $\|\mathcal K\|=26!=403291461126605635584000000$.That's because plaintext letter A can correspond to any of 26 ciphertext letters, plaintext letter B can correspond to any of the 25 ciphertext letters other than the one corresponding to plaintext letter A, plaintext letter C can correspond to any of the 24 ciphertext letters other than the two corresponding to plaintext letters A or B, and so on until plaintext letter Y corresponding to 2 possible ciphertext letters, and Z corresponding to the one remaining ciphertext letter.
The key length in bit is the base-2 logarithm of that: $k=\log_2(26!)=\log(26!)/\log(2)\approx88.38$ bit.
The number of symbols in the key is $n=26$, with $s=26$ possible symbols.

  Assuming the key length is 26, why is (keyspace size) not $2^{26}$ ?

That $2^{26}$ seems to be built as $2^n$, where $n$ is the number of symbols (not key length), when $2$ would be for the number of possible values taken by a single bit. The discrepancy makes $2^{26}$ irrelevant.

A relevant number is $s^n=26^{26}=6156119580207157310796674288400203776=2^{\approx122.21}$ : that's the number of character strings of $n=26$ characters each chosen among $s=26$ characters. But this is much larger than the keyspace, because the key of a mono-alphabetic substitution cipher must use different letters (otherwise decryption would be ambiguous).


6 Byte for HMAC in wireless system secure? A wireless system has 8 byte payload and 6 byte for message authentication.

Scheme:

m := 8 Byte Message
k := 128 bit key
c := Encrypt(m,k)
hmac := secure_hashfunction(c, k) //(6 byte output)

Questions:

Is bruteforce possible when transmitting a single wireless package will take 7ms? If an attacker do a bruteforce attack it will take $2^{48} * 0.007  /\  60 /\ 60 /\ 24/\ 365 = 62478.59\ years$ . So my assumption is that this system is secure if secure_hashfuncion is a cryptographically secure hash function.
Is there a hash algorithm that is cryptographically secure (only brute-force attacks possible) with a 6 byte output?
Can I maybe just use SHA-1 and only use the first 6 byte output?

Is bruteforce possible when transmitting a single wireless package will take 7ms? If an attacker do a bruteforce attack it will take $2^{48} * 0.007  /\  60 /\ 60 /\ 24/\ 365 = 62478.59\ years$ . So my assumption is that this system is secure if secure_hashfuncion is a cryptographically secure hash function.

Actually, I would look at it this way; if the adversary injects a packet, it has a probability $2^{-48} \approx 3.55 \times 10^{-15}$ of being accepted; the attacker can increase this by (say) a factor of a million by using a million packets (which he could do over the course of a couple hours).

Is this "secure"?  Well, that'd depend on your required level of security.  If the effect if the adversary was successful was an ICBM launch, I'd say that we'd want to security to be better.  However, if you're protecting a VoIP stream, and the effect would be to replace a 10msec sound segment, it'd probably be good enough.

  Is there a hash algorithm that is cryptographically secure (only brute-force attacks possible) with a 6 byte output?

For MACs, there are two possible attack approaches; one is to guess the MAC (as above); the other is to try to recover the key.  If you believe that you are sufficiently secure against the first attack, well, there certainly are MACs that are secure against key recovery attacks.

The only caution would be that there are MACs that, once you've found a forgery, make it easier to find other forgeries; GMAC is one such example.  For this application, I'd stay away from that, and use one that doesn't have such a vulnerability; such as HMAC or CMAC [1].

  Can I maybe just use SHA-1 and only use the first 6 byte output?

You'd have to stir in the key somehow.  Now, I suppose you could hash the key and the message together (we typically don't because of length extension attacks, which do not apply because of your truncation); however unless you need to minimize computation, I'd still advise you to use a more traditional MAC, such as HMAC (such is close to what you are proposing), or CMAC.

[1]: CMAC does have that vulnerability, but only if the attacker guesses the entire 128 bit tag; guessing a truncated version (without getting the rest of the bits right doesn't help him)


Appropriate length of the challenge string for challenge-response authentication? How to select the necessary length of the challenge string for challenge-response authentication to claim that there is no threat of the shared secret exposure?

I can think of the following:

Possible number of given responses in some time considered as "reasonable".
Algorithm used for calculating the response.

Are there other factors?

How to calculate the "safe" challenge size if, for example, my system can respond 10^12 times during the lifetime of the key, and the response is calculated with HMAC-MD5(key || challenge)?

Standard approach:

$n=10^{12}$ challenges are drawn;
assume each challenge is $k$ unbiased independent random bits;
odds that there is a collision is less than $(n^2/2)\cdot2^{-k}$, by a first order approximation of the birthday problem, always erring on the safe side, and negligibly so for large $n$ and low odds of collision (our goal);
we want the odds to be less than some acceptable residual odds $\epsilon$ that the challenge will repeat (potentially allowing replay); like, $\epsilon=2^{-30}$ (less than one chance in a thousand million).

Now, solve for $k$. Mentally: 3 decimal digits are worth 10 binary orders of magnitude, thus (slightly erring on the safe side) $n$ is 40 BOMs, $n^2$ is twice that, $n^2/2$ is 1 less, dividing by $\epsilon$ adds 30 BOMs, thus we need 109 bits; rounding up to the next multiple of 8, we want at least 14 bytes.

Beware: it is uneasy to build a random generator that will generate independent random bits if power loss between uses or adversarial upset is a possibility.

If we want to reduce $k$ to the max in order to conserve bandwidth, and have secure remanent read/write memory for a counter, and an secret extra key, we can use a 40-bit counter (numbers of BOMs in $n$), encrypted with a 40-bit block cipher and the key (which needs to be known only by the entity generating the challenge).

Not only will the challenge be smaller, it is guaranteed to never repeat (this is part of the Format Preserving Encryption folklore).

Beware: a reliable counter is extremely hard to get right if power loss during uses or adversarial upset is a possibility; thus if possible, the prudent approach is to stick to pure random challenge.

I second the opinion voiced by @CodesInChaos that a challenge-response should be part of an overall protocol giving the required security insurance; and in particular that it should not be possible to hijack a channel after the challenge/response; or/and insert in there as a Man in the Middle.


Is the length limit of AES-GCM per key or per (key, nonce) pair? AES-GCM has a limit on the length of the plaintext it encrypts: $2^{39} - 256$ bits. But is this limit per key or per (key, nonce)? That is, if I encrypt a message with the maximum length, and encrypt another message with the same key but different nonce, will it be secure still?

It is per message. I.e. per (key, nonce) -pair.

The reason it exists is that GCM uses CTR mode for encryption with (normally) a 32-bit counter. That means you can only encrypt $2^{32}$ blocks, i.e. $2^{39}$ bits with AES. The 256 bits that are subtracted are due to authentication.

So you can encrypt multiple maximum-length messages securely.


Why is a public key insufficient to decrypt a message? I'm curious about how E2EE encryption works, but the high-level descriptions I've been able to find aren't quite as clear as I'd like them to be. My current understanding is as follows:

Suppose one party, Alice, wishes to send a secret message to another, Bob. They both have "public" and "private" keys. Alice uses Bob's public key to encrypt her message, which is only decryptable using his private key.

This leads me to imagine that the public key basically specifies some kind of algorithm that Alice will need to run on the message before sending it, to make sure nobody but Bob will know what it says. But couldn't a third party, Claire, just use Bob's public key to determine exactly what algorithm Alice ran on her message and reverse those steps on Alice's encrypted message to determine what it said, with no private key involved? Why can you do this process one way with just the public key but not the other?

Put in other words, what information does the private key contain that the public key doesn't?

To give some idea of the level of depth I'm hoping for an answer in, I have a mathematical background but (obviously) no particular knowledge of cryptography.

But couldn't a third party ... reverse those steps?

Simply said - no, it is impossible to reverse those steps. (this is true under certain conditions, how the keys are generated, etc.)

Why not? One of reasons is that RSA uses modular arithmetic. All operations are done using some modulo. If you know that $X mod A = B$, can you find the X? There are unlimited solutions: X = B, X = A + B, X = 2A + B, X = 3A + B, etc. In the reality it is more complex, like $X^{C} mod A = B$. We can say that such operation is not (easily) reversible.

For further reading see the link suggested by @kelalaka. When you have then further questions, welcome.


Signing MD5 hashes with RSA? Lets say I need to update a project and allow anyone to distribute the updates, however I need it to be secure, so I hash the data and sign the hash, this project uses MD5.

How likely would it be that a person could obtain the signing key or falsely sign files that could be distributed using the following information? If so would switching to MD6 fix this issue or is it deeper. Do I need to pad my messages?

Signing:
$ \textrm{MD5}(M)^D \bmod(N) = S$

Retrieving hash:
$ \textrm{MD5}(M) = S ^ E \bmod (N)$

Variables:

$M$ = File contents (public)
$\textrm{MD5}(M)$ = Hashed file contents (public)
$S$ = Signed hash (public)
$D$ = Decryption key (private)
$N$ = Modulus (public)
$E$ = Exponent (public)

Summing up and fleshing out the comments: Generally, signing software updates is good practise and should definitely be done. However, you ask about the security of an unpadded RSA signature on an MD5 hash. There are at least two issues with this:

MD5 security

MD5 is no longer considered safe, and hasn't been for quite a while (we're already phasing out its successor, SHA-1, in favor of SHA-2 and eventually SHA-3). MD5 has been broken for a while, and in ways that make it unsuited for signatures. Edit: My old explanation was wrong. See the comments by @Gilles and the answer by @fgrieu for the details of why MD5 is bad. The conclusion of "don't use it" still stands.

Solution: Use SHA-256 or another up-to-date hash algorithm instead of MD5.

Unpadded RSA signatures

If you sign the hash with a primitive RSA signature without any padding, you can attack the scheme as described in this question and answer. This would, again, allow an attacker to forge a message with a valid signature. Even when using SHA-256 instead of MD5, the security margin is too low for comfort.

Solution: Use a proper padding like PKCS#1 v1.5 or, even better, PSS.

General remarks

Please consider using an established method and (ideally) implementation for this purpose. Take a look at how other systems do this. Even though the potential attacks mentioned here may seem like they would not apply to your use case, it is bad practise to use methods you know to be insecure, just because you think the insecurities may not apply to your specific system. Using good algorithms and padding has almost no additional cost, but gains you the peace of mind that your system is secure, instead of "probably secure because the attacks probably do not apply to it, I hope".

Finally, the standard caveats about "don't implement the crypto yourself, use an established library" apply, and this question has a large number of good answers concerning best practises for cryptography and can serve as a good starting point for further research.


Quick scan which data (hmac/fernet) can be decrypted with a key? I am designing a secure vault, which stores tens of thousands of encrypted messages and authenticated with Fernet/HMAC, A user query the vault with a key, could I use some kind of index to tell if the key can be used to decrypt any of the stored messages?

Or do I have to try decrypt them one by one?

Found a stupidly simple solution: Create an index of md5(key).

Alternatively, replace md5 with hash method of your choice.


Given a sequence of integers, would applying AES encryption to the sequence produce a unique set of strings? Let us say that we take a sequence of the integers from a to a+n-1: (a, a+1, a+2, a+n-1), where a and n are picked arbitrarily and have no lower or upper bounds on either, except that a < n, and we apply AES encryption to that sequence, one element at a time, utilizing the same key for each element in the sequence.

Assumption is that we encode the resulting ciphered values as Base64 or some other encoding to produce strings.

Would the resulting set of encrypted strings have any, irrespective of how infinitesimally small, chance for collisions?

Since any cipher must be able to decrypt every message that it encrypts, it follows that, given a fixed key, any cipher must be an injective function:

  In mathematics, an injective function or injection or one-to-one function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is the image of at most one element of its domain.

Or graphically, think of X as plaintexts and Y as ciphertexts:

Although often ciphers are more than just injective—they're also bijective:

And permutations as well: X and Y are normally the same set.  E.g., for AES, X and Y are the sets of 128-bit strings.


Is there a real purpose to use Twofish, Serpent or Threefish instead of AES? I am wondering if other ciphers like Serpent or Twofish or even Threefish have really an use in real life, because AES seems to be very efficient in most situations.

But for example TrueCrypt or VeraCrypt offer Serpent and Twofish to be the algorithm to encrypt your drive, so why would anyone choose those ciphers and not AES? (I know that Threefish is tweakable, therefore efficient in encrypting disks).

So to clarify my question:
Is there a real purpose to use Twofish, Serpent or Threefish instead of AES?

Serpent is straightforward to implement with side-channel resistance due to the bit-sliced design. Because AES incorporates an S-Box that is most simply implemented as a lookup table, implementations of it tend to be prone to side-channel attacks.

Threefish was designed for the SHA-3 competition, and was intended to be a part of a sort of package of cryptographic primitives, including encryption, hashing, and a MAC. If you wanted a crypto library that didn't require implementing a whole host of different algorithms, Threefish might be a good choice.

One compelling reason to use AES is that many modern CPUs support the AES-NI instruction, which will make encryption with AES almost certainly faster than any other algorithm. A faster algorithm is mostly always better, but unless you are encrypting large amounts of data you will likely never even notice the difference. It might save a couple of cents on your power bill since AES-NI requires fewer CPU cycles.

Of course, as a user, these implementation details may be invisible. And the libraries you mentioned already implement a whole host of different algorithms, so that advantage is negligible in the situation you are concerned with.

Offering multiple options is generally better than a single option (within reason - too many choices is bad). It's a bit like asking why a restaurant has more than one item on the menu. Some people might not care for that one item, for arbitrary reasons.

For a point-by-point overview of why Rijndael was selected as AES instead of Serpent or Twofish, you can investigate these other related questions


MIT says: mathematical theory behind encryption is wrong. What are the consequences? A friend shared with me the following link: Encryption is less secure than we thought

I'm not a security expert and could understand great part the article, except the section about noise, but what I haven't figured out is the impact of that research in real life.

What does it mean for mortals, in practice?

So the article is fluff, the details can be found in the linked paper.  The just of it is a refutation of the following assertion: if you have a set of symbols chosen with identical independent distributions and subject to some kind of coding, the result can be approximated as a uniform distribution.

The paper asserts, with a few citations to some examples, that this is a common cryptographic assumption. It is, as far as I can tell from reading the literature and talking to other practitioners, not a common assumption at all. In fact, in standard encryption systems, we assume that the plaintext is chosen with a known distribution that can be arbitrary(indeed, attacker chosen), and keys are chosen randomly.

In practice, keys are not chosen randomly, they are chosen using cryptographically secure random number generators. Those can fail, but not in the way the paper is talking about.

Certain papers, such as maybe the cited ones about biometrics and  passwords, might make this erroneous assumption, but it's not common and certainly  doesn't relate to what most non-practitioners would consider "encryption."

Moreover, it appears that you still can't make guesses about messages in polynomial time with this technique, you can just make them in faster exponential time. It depends highly on how the assumption was used if this maters in practice. Not having read the papers which do make this assumption, I can't say for sure, but if doing this breaks those systems in a practical sense, the schemes likely had other issues.

A better title for the article is: a few cryptographers made some dumb mistakes. Mistakes neither pervasive or of massive consequence.


Stateless proof-of-work system with 0-roundtrip time I'm designing an API. To avoid abuse, I need to rate limit the requests somehow, but I don't want to do it per user as it's very easy to create new accounts automatically. I think a proof of work algorithm would do this job well, but I thought I would ask an expert, i.e. this community.

These are the properties I would like:

Stateless, but ahead of time setup of state, such as creating a user account, is ok. Two subsequent requests may hit different servers before they have shared their state with each other.
Preferably zero round trip time, i.e. the user does not have to ask a server what work it should do before actually doing it. This basically implies that the requests are stateless.
Requests should be able to run in parallell, even for the same user.
Adjustable difficulty.

I can think of some systems that fulfill some of the above properties, but not all.

Hash on userid + (request id) + nonce until the prefix of the hash has n bits of zeroes. Request id is some unique number picked by the client. Has properties 2, 3, 4, since we have to keep track of what request-ids have been used already. Otherwise, the same proof-of-work can be used for multiple requests.
Hash on userid + (request-id) + nonce until the prefix of the hash has n bits of zeroes. Request-id is fetched from the server before each request. Has properties 3, 4 and optionally 1, if there's some way to validate that the request-id was generated by one of our servers without touching a database. Since we have to ask the server for a request-id, we need one additional roundtrip time.

Is there a proof of work system that provides all the properties I've listed?

Is the requirement to prevent replaying identical requests? If not, it seems trivial to use a partial inverse hash of the request body.

If you are concerned about replaying identical requests, one possibility might be to use the proof-of-work nonce for your load-balancing algorithm. For example, use the least significant 3 bits to distribute across 8 servers. The long run average should distribute fairly between workers but a replayed request will always end up going to the same worker. SO you can check for duplicates locally without needing access to a global state.


Estimate password cracking time given Shannon Entropy Is there some algorithm that, given the Shannon entropy of a string, compute an estimation of the time that an average home computer will take to crack the password?
Thank you.

Assuming knowing the entropy in the generation process is meaningful, the relationship between difficulty of brute force guessing an unknown random variable  and entropy (or entropies) is quite a delicate one, and depends on the assumptions about the attack scenario.

In particular, the direct use of Shannon entropy can give misleading results, and the best case brute force number of guesses can be much lower than that implied by shannon entropy (say $H_0$ bits, should imply roughly $2^{H_0}$ guesses in the worst case.

One result on the expectation is that the expected number of guesses to determine a random variable  (for the optimal guessing sequence) is upperbounded by

$$2^{_{1/2}()−1}$$
and lowerbounded by
$$\frac{2^{_{1/2}}()−1}{\log |X|}$$
where $H_{1/2}(X)$ is the Renyi entropy. In general Renyi entropy can be much lower than Shannon entropy, hence Shannon gives a misleading result for this problem. See the answers  to this question for details and references.


Does XORing a random block into a layer of CBC encrypted message add some bit strenght? Let's suppose I encrypt a message with a block cipher in CBC mode, keep the key and IV secret and XOR a random block of data in each encrypted CBC block, being the XORed block the same for each CBC block (constant).
Does it add some encryption strength?
(I know this question is weird, but I need to know).

In general: No.
You have to assume the attacker knows what you are doing. That's Kerckhoffs' principle.
If your random blocks are actually a real One-Time-Pad on top of the block cipher, then it would be stronger - but you could achieve the same without the block cipher. If all your blocks use the same pad, this is true if the length is 1 block,  the pad is truly random, only used once and communicated using another secure channel.
If you just mesh different things together to make it more complex - that does not add security at all.
As a side note: The IV in CBC is not secret. If you consider it secret, you need to clarify how the sender and receiver both know it. And following that - do you consider that secret as static and reuse it? That would violate the requirements of an IV.


Secret key model for a compression function cryptanalysis? How do we analyze the security of a compression function in the secret key model? More formally, let $H$ be a hash function and $F(IV,M)$ its compression function. Suppose we generate a MAC as follows:
$$
T=F(F(K,M),M_p),
$$
where $K$ is the MAC key and $M_p$ is the padded block. Can I say that if one observes the output of the inner compression function call, i.e., $F(K,M)$, and retrieves $K$, then this is a certificational weakness of the underlying compression function? (we do not consider it in any specific protocol)

Yes, if $K$ can be recovered from $H'=F(K,M)$, this is a weakness.  The function $F$ is not preimage-resistant, and an attacker may easily generate correct tags for new messages (this is called a forgery). The proposed MAC scheme, however, is terribly weak, and forged tags for other messages can be easily produced (length-extension property):
$$
T(M\mathbin\|M_p\mathbin\|M') = F(T(M\mathbin\|M_p),M').
$$
Still, if original $K$ can be recovered, forged tags can be produced for even shorter messages.

However, there could be many $K$'s that produce the same $H'$. If the cost of finding the original $K$ is still higher than the exhaustive search, then such attack is useless for forgery, as the attacker would have to use the length-extension attack. However, the compression function is still vulnerable to preimage attacks, which may be exploited in other constructions (for example, meet-in-the-middle attacks on hash functions).


Difference between SSHA512 and SHA512 I am using SSHA512 to encrypt email user's passwords. Manually doing this works using doveadm from dovecot. But I can't seem to implement this in my mail client. I can, however, use SHA512.
Is SHA512 less secure than SSHA512?

Is SHA512 less secure than SSHA512?

Hashing passwords plainly with SHA512 is indeed less secure than using SSHA512. But note that this doesn't imply that using SSHA512 is actually a good / secure method for hashing your passwords.

The reason for the inequality is simple:

$$\operatorname{SSHA512}(\text{pw},\text{salt})=\operatorname{SHA512}(\text{pw}\parallel \text{salt})\parallel \text{salt}$$

So as you can see it's a case of a single iteration of SHA-512 paired with some basic salting. Salting is a good thing as it (among other things) thwarts rainbow-tables but of course a modern GPU (like the Tesla V100 or with nearly the same speed the RTX 2080 Ti) achieves about 1.8GH/s per card. That is $1.8\cdot 10^9$ SHA512 evaluations per second and per card. Also note that for about 25 USD/hr you can rent 8 of these on AWS which gives you about 2.1 TH/USD, that is an attacker can try about $2\ 000\ 000\ 000\ 000$ password hashes for a single US-Dollar. So if the user has any even remotely weak password, it's a matter of a few USD to break it.

The more modern approach is then to use Argon2 or bcrypt instead which perform much worse on GPUs.


Demystifying homomorphic multiplication in RNS FV variant I am trying to understand a full RNS FV SWHE variant proposed in this paper.

My problem is with the homomorphic multiplication. Original ciphertexts are represented in RNS representation using base (say $q$ with $k$ co-prime moduli). In order to accommodate for coefficient growth, an auxiliary RNS base (say $\mathcal{B}_{sk}$ with $\ell$ co-prime moduli) is introduced. Note that $\{ q \cup \mathcal{B}_{sk} \}$ moduli are co-primes too and $k$ needs not to be equal to $\ell$. What I don't understand is the step (S3) in Algorithm 3 in page 13:

The function "FastBconv" takes as input an extended ciphertext$^*$ in base $\{ q \cup \mathcal{B}_{sk} \}$. How to convert it to obtain a ciphertext in base $ \mathcal{B}_{sk}$ only?
There is also a strange notation of dots ($\dots$) used in the same line in the algorithm, what is that supposed to mean?

*: an extended ciphertext can be viewed as a matrix of $k+\ell$ rows and $n$ columns where $n$ is the underlying ring's polynomial modulus degree.

I appreciate any help in explaining the algorithm.

Yes, this can be confusing at first. Maybe starting with a more recent paper could help: https://eprint.iacr.org/2018/117

In the paper I cited above they have improved the base conversion and scaling in RNS, but also made the procedures simpler as a side effect.

First, they expend the base of the ciphertext from $Q$ to $Q*P$, then they do the tensoring in $QP$, then they scale it down by $t/Q$ getting the result mod $P$, and then expend again the ciphertext (which is now in base $P$) to $Q*P$ and only keep the $Q$ part.

As for your question, if you have the ciphertext in base $QP$, and you want it  only in base $P$, you can simply throw away the base $Q$ (delete the rows of the polynomial mod each $q_{i}$). Of course this is only valide If the value of the coefficients are within $0,P-1$. But this will always be the case since the auxiliary base $P$ is at least as big as $Q$. After multiplication this is not anymore the case because the coefficients will be of size $Q^2$ (unless $P > Q^2$). However after having them scaled down, they are back within the range of $Q$.


Deterministic Encryption with AES GCM - how to choose the IV (nonce) I have not a very large background in cryptography so I hope these questions are not very dumb. I don't want to reinvent the wheel, I'm just looking for advise on the best practices about how to build the following.

I've seeking and reading for several hours now and didn't find any answer that fulfills my concerns. Therefore, I've came out with a solution which I want to have some feedback.

The Problem

I want to provide a stateless micro-service for deterministic encryption of sensitive information. Some of this information (i.e.: personal identification number) might be used as primary keys in databases, that's why the cipher text needs to be deterministic.

This microservice will have an oauth2 schema, so it will be the unique point for encryption and decryption. There won't be key sharing at all.

Different applications will call this service for encrypting sensitive information, sharing it among others and at some point, another application with right credentials will ask for it's decryption.

API pseudocode:

encrypt (sensitiveInfo: String): String
decrypt (ciptherTextStruct: String): String

Considerations

Using AES-GCM, IVs must be unique
IV must be returned along with ciphertext
IV should not be a hash of the plaintext since they don't provide confidentiality.
Ciphertext will be returned within a structure (which will contain a key "version" used for key rotation)

Proposed solution

Basically, I thought the IV to be another ciphertext:

mail (input) +--> hash() --> IV        \
             +--> mail   --> PlainText |-> Cipher text 1 (C1)
password (secret) ---------> Key       /

Then:

Cipher text 1 (C1) --> IV        \
mail ----------------> PlainText |-> Cipher text 2 (C2)
password (secret)  --> Key       /

Finally, the method encrypt (sensitiveInfo: String): String will return a structure with C1+C2 (maybe a json structure), and the method decrypt (ciptherTextStruct: String): String will take C1 from the structure, use as the IV, C2 and the secret key and return the plaintext as expected.

Feedback

I'm worried about having any kind of information disclosure on playing with C1 and C2 that I'm not seeing in this picture.

Edit: I could also use the second IV as a hash of C1, that way no playing between C1 and C2 would be possible.

I'm pretty sure that I am kind of reinventing the wheel on this, so I really appreciate some help about which is the best way to proceed.

Thanks!

Your proposed solution will work, mostly. The only thing that you have to change is, to use a different key in your calculation of $C1$ and $C2$. Both keys may be derived from a common master key but they must not be the same.

Your solution is a bit complicated, though. It would be a lot easier, to just calculate your deterministic IV as a MAC of the plain text (and the additional data, if there is any).

Putting this together, my suggestion would be:

encrypt

Input value: $S$ (password), $M$ (message)

$MK = scrypt(password), K_1 = HKDF(MK, "IV Key"), K_2 = HKDF(MK, "Enc Key")$

$IV = MSB_{96}(HMAC(K_1, M)), C=ENC(K_2, IV, M)$

Return Value: $IV, C$

decrypt

Input value: $S$ (password), $C$, $IV$

$MK = scrypt(password), K = HKDF(MK, "Enc Key")$

$M = DEC(K, IV, C)$

Return Value: $M$


Hill Cipher the point of a known plaintext attack question Is the point of a known plaintext attack on a Hill Cipher to get the matrix key?

Indeed. If the matrix is $n$ by $n$, and you have $n$ many known plaintext blocks with corresponding ciphertext, you get $n^2$ linear equations in $n^2$ unknowns (the matrix elements) (modulo the alphabet size), which very often can be solved uniquely.