Can I use a HMAC for Replay Attack protection? I am considering a system where a small device accepts messages/commands from another device over a wireless channel.  I am worried about replay attacks.  The messages will be encrypted.  What are well-vetted schemes for protection against these attacks?  I am not too keen on timestamps (as described in this Q&A) as I don't really want to have to keep clocks synchronised.  I am currently thinking of using HMAC but want to be sure that I'm doing the right thing.

An old but excellent paper on this topic is Tuomas Aura's Strategies against Replay Attacks.

The simplest version of the "Hashed Full Information" method would be to include the MAC of the previous message in the next message (you may also be able to use this as the nonce).  Then store the most recent MAC along with the session key and check new messages against that.  This would force serialization of messages within each session. (Assuming that is what you were thinking of when writing "use HMAC".)


How would a side channel attack be carried out in a real life situation? How would a timing attack against AES be carried out in a real situation? You could not guess the key from the processor's power usage after the plaintext is encrypted, right? And what would you need for this scenario? How long would it take? And if side channel leakage is really such a big deal, why is AES still used for the encryption of classified data?

In hardware, most of the implementations for AES are constant time. My experience is that the current is generally too far into the noise floor to get any real data out; however, I've attacked my AES implementation and a commercial hardware implementation as well with success.  In any software implementation of AES (or ones that I know), I can HALT the system, and dump the core via JTAG and get the keys.

To do a power attack on system, it helps if you know something about the system, but the math you are looking at on a per transistor basis is

$$I_{f,r} =I_{thn}\ln^2 \left[1+ e^{\left[{\left(\kappa \left(V_g-V_{thn}\right)\right)- \left(V_{s,d}\right)}\right]/\left({2 U_{T}}\right)}  \right]$$

$$I_{f,r} =I_{thp}\ln^2 \left[1+ e^{\left[{\left(\kappa \left(V_b -V_g+V_{thp}\right)\right)- \left(V_{b}-V_{s,d}\right)}\right]/\left({2 U_{T}}\right)}  \right]$$

for the N and P FETs respectively.  This model is called the compact EKV model, and if you push through the Taylor expansion, you'll get the subvt and abovevt currents.  Generally, you will see the nFETs to be stronger than the pFETs, which lets you get a feel for what the bit states of the system are.  Having said that, on 14nm SOI (this process is wonderful), my pFETs and nFETs are identical, except for a difference in threshold mismatch.  If you drive the voltage down to get the systems running in subthreshold and control the clock, you can get a really good picture of the circuits.  Once you know the circuits, you can then get the keys.

I use a Keithley 2000 DMM and Keithley 6485 picoammeter that are controlled through MATLAB and I can pretty much get anything I want out of the little black boxes.  (I also have a copper box to isolate noise)


Can an encryption method be used as a hash function? As I understand, there are a few requirements for a good hash function.

Hard to find any message from a given hash
Hard to find any 2 messages which give the same hash
A single bit change in the input message should lead to change of each bit of the output with a probability of 0.5 (as close as possible to 0.5)
Good collision resistance

So my question is if I have a asymmetric key encryption method, erase off the private key, encrypt the message with the public key, then take the least significant (say) 256 bits. Do I have a good hashing function? Does my hashing function provide some guarantees on the points 3,4? I am fairly sure points 1,2 are fine though. Aren't they?

My aim is to explore the possibility of creating a hash function out of an encryption function. So put aside the fact that messages are usually padded with random information before encryption. Just Encrypt(Message, Public-key).

edit : Some of the answers ask, how can i be sure I destroyed my private key properly. What I can do is even before generating a public/private key pair, I would just create a single random string and call it public key(if the public key has some requirements on the length or other properties, I would generate a string of that particular length). In general I would create a string which is acceptable as an public key by the encryption machine.

Provably secure cryptographic hash functions are often built using the same sort of operations as what are used in asymmetric crypto. The major problem with these constructions are that they are very inefficient. Also, a lot of these sorts of constructions have finite input domains. Thus, you have to figure out how to extend it to arbitrary length inputs.

Now, on to your specific construction. I wouldn't use it, inefficiencies aside. How do I know that you destroyed your private key? If you didn't, likely you would have a great advantage in breaking some of the properties listed above.


Block cipher information leakage using same key This is from a previous exam question and I'm not really sure how to approach this properly

  We're using a block-cipher mode that encrypts

  $C_i$ = $E_k$ ($P_i$ $\oplus$ $C_{i-1}$ $\oplus$ $P_{i-1}$) with $C_0$
  = IV and $P_0$ = 0.

  Indicate whether information leaks on the plaintext if too many
  plaintext blocks are encrypted under the same key (use as example
  DES).

Now I'm not really sure how to indicate this. But I assumed that if the IV is truly random that no leakage should happen.

My opinion even if you do a chosen-plaintext attack where $P_1$ = 0

$C_1$ = $E_k$ ($P_1$ $\oplus$ $IV$ $\oplus$ $P_0$) = $E_k$ ($0$ $\oplus$ $IV$ $\oplus$ $0$) which would give $C_1$ = $E_k$ ($IV$)

$C_2$ = $E_k$ ($P_2$ $\oplus$ $C_1$ $\oplus$ $P_1$) = $E_k$ ($P_2$ $\oplus$ $E_k$ ($IV$) $\oplus$ $0$)

$...$

I don't see how it would leak any information on the plaintext. I might be assessing the question wrong though.

The reason for the 'birthday bound' in block ciphers are collisions that may occur after an expected $2^{n/2}$ blocks (or lack there-of); cases where the inputs to the block cipher is exactly the same (and hence the output is as well).

How might someone, with a large amount of ciphertext, find such collisions in the mode in question?  Having found such a collision, how might they use it to deduce information about the plaintext?


True 128bit secured password length? assume we say 128bit keys are secure so a 16 character long password is safe, but if i even use lower case and upper case letters with numbers and special characters on my keyboard its about 80 different character i can choose, as we have 256 different byte in nature so it look like the 16 character random password i choose is about a 60 bit secure key ... ?!
how to fix it and what is secure length to use ?

If your alphabet (set of all possible characters) has size $s$ and your password has length $l$, a randomly generated password has a strength of $\log_2s^l = l\cdot\log_2s = l\cdot\frac{\log_{10}s}{\log_{10}2}$ bits.

This means if you want to create a 128-bit password using a 80-character alphabet, you need at least $\left\lceil128\cdot\frac{\log_{10}2}{\log_{10}80}\right\rceil = \left\lceil20.25\right\rceil = 21$ characters.

In practice, humans aren't very good at creating random passwords; and the greater the alphabet gets, the greater gets the bias. Non-random password (e.g., sets of dictionary words) are even worse (as low as 1 bit of entropy per character).

If possible, you should generate your passwords randomly (with a program, not by hand) and store them with a password manager, or use a KDF (as Thomas already suggested in the comments). Trucrypt actually uses PBKDF2 for key derivation. (source)


Can you use a "power of 2" gate in the BGW protocol I am learning about the BGW Protocol and I understand that for a MUL gate, you need to follow the degree reduction protocol. I am wondering if it is possible to implement a single input and single output "SQUARE" gate that computes the square of the input?
I imagine some sort of degree reduction protocol would be involved but when I try using it in the same way as for the MUL gate, it does not seem to be working. Does anyone know if implementing such a gate is possible for the BGW protocol?

I don't see why it shouldn't work. If you ran the multiplication protocol using the same polynomial for both inputs, doesn't that work? Each party would square its share and then run degree reduction.


Why is AES encryption decryption not platform agnostic? We work on C++ code which compiles on Windows and Linux. I have been told that AES encryption/decryption is platform dependent. Is it true? If so, why is it OS dependent?

No, it isn't.

As a C++ programmer you'll realise that the source code can be environment dependant - such as the 32 /64 bit thing.  Or memory capacity.  But you should also realise that an algorithm is OS agnostic.  Isn't this actually intuitive? One way to look at it are all the IOT devices out there.  They often use AES for encryption and they manage to talk to each other and control your hot water from your phone.  Those devices are all different, and some might  be 8 or 16 bit affairs. And some might even run on batteries like your phone.

See  the Advanced Encryption Standard Algorithm Validation System for test vectors.  This document shows you what should come out of your AES code.  You've just messed up either your native code implementation or the library API. If you can't understand section 6, Modes of Operation then you need to do some additional fundamental research regarding block ciphers.  Remember that AES itself is only the block primitive that accepts a key and a (plain/cipher/IV)text input.  Nothing else.

To reinforce what I've said, look at the referenced document, appendices B to E.  There is absolutely no mention of operating system, programming language,   hardware type or battery voltage.  AES is totally abstracted from it's environment.  If you have a problem with compatibility, it's an implementation issue.


Why does .NET's ECB mode implementation append a constant block to my ciphertext? Consider the following code and output:

    public static void Main() {
        DESCryptoServiceProvider symAlg = new DESCryptoServiceProvider();
        symAlg.BlockSize = 64;
        symAlg.GenerateKey();
        symAlg.Mode = CipherMode.ECB;

        testCipher(symAlg, new byte[] {
            0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08,
            0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08
        });
        testCipher(symAlg, new byte[] {
            0xC1, 0xC2, 0xC3, 0xC4, 0xC5, 0xC6, 0xC7, 0xC8,
            0xD1, 0xD2, 0xD3, 0xD4, 0xD5, 0xD6, 0xD7, 0xD8,
            0xE1, 0xE2, 0xE3, 0xE4, 0xE5, 0xE6, 0xE7, 0x8E,
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
        });

        Console.ReadKey();
    }

    public static void testCipher(SymmetricAlgorithm symAlg, byte[] plainText) {
        ICryptoTransform xfrm;

        xfrm = symAlg.CreateEncryptor();
        byte[] encrypted = xfrm.TransformFinalBlock(plainText, 0, plainText.Length);
        xfrm = symAlg.CreateDecryptor();
        byte[] decrypted = xfrm.TransformFinalBlock(encrypted, 0, encrypted.Length);

        Console.WriteLine(new string('=', 23));
        writeBlocks(plainText);
        writeBlocks(encrypted);
        writeBlocks(decrypted);
    }

    private static void writeBlocks(byte[] blocks){
        for (int i = 0; i < blocks.Length; i += 8) Console.WriteLine(BitConverter.ToString(blocks, i, 8));
        Console.WriteLine();
    }

Output:

=======================
01-02-03-04-05-06-07-08
01-02-03-04-05-06-07-08

1E-0C-3E-59-93-5C-23-6E
1E-0C-3E-59-93-5C-23-6E
6F-AC-50-69-34-D0-B1-61 // NOTE THIS

01-02-03-04-05-06-07-08
01-02-03-04-05-06-07-08

=======================
C1-C2-C3-C4-C5-C6-C7-C8
D1-D2-D3-D4-D5-D6-D7-D8
E1-E2-E3-E4-E5-E6-E7-8E
00-00-00-00-00-00-00-00

F9-9A-77-30-3B-31-7F-D2
D8-B5-B2-C6-E7-E7-0F-90
0E-90-DF-AF-56-C0-DE-84
65-5D-E0-7D-5A-7A-0F-D9
6F-AC-50-69-34-D0-B1-61 // AND THIS

C1-C2-C3-C4-C5-C6-C7-C8
D1-D2-D3-D4-D5-D6-D7-D8
E1-E2-E3-E4-E5-E6-E7-8E
00-00-00-00-00-00-00-00

I understand the weakness of ECB. What I don't understand, is why on earth would .NET force me to append a final block that is the length of the key and only varies with the key. No matter how weak the encryption was to start with, isn't this worse?

I have a specific reason for using ECB: Encrypt array of int for individual retrieval

However, decrypting just one block (without the constant final block) yields: System.Security.Cryptography.CryptographicException was unhandled  Message=Bad Data.

Now, knowing that it is constant by the key, I can perform a bogus encryption at application initialization and cache the final block, feeding it back in to my decryption operation rather than putting it in the data stream, but why in would .NET encourage me to store this with the data, and is it only .NET that does this?

I believe what you are seeing is that .NET automatically uses PKCS #7 padding. This will always add padding. Thus if your plaintext is a complete block length, one extra block of padding will be added.

The reason the ciphertext ends up being the same in both of your test cases is that it is adding the same padding in both cases (see PaddingMode Enumeration for details on PKCS #7).

You can have .NET use no padding by using the Padding Property.


LFS Kolmogorov Randomness Consider following LFS register (where + denotes addition modulo 2)

I have found the output sequence as 1,0,1,1.

I know that The K(s) of a string s is defined as the length of the shortest computer program that generates s and given a non-negative integer c,s incompressible if K(S)>= |s|- c.

My question is:

Is the output sequence Kolmogorov - random?

I could not understand how to find c or s in this question.

Edit: Kolmogorov complexity is most useful as an asymptotic concept as $n$, the length of the string increases. This is addressed in the general answer below.

Specifically one should use $s=1,0,1,1,1,0,0$ as the output, as suggested in the comments. Then the length is $|s|=7,$ and the question becomes

  Is there a $c\geq 1,$ such that $K(s)\geq |s|-c$?

Since this string is woefully short, the answer is No, the program length would be too large, as pointed out in the comment by @PaulUszak.

General Answer:

Given any linear (or nonlinear) shift register of fixed length $L$ and its output sequence $(x_k)_{k=1}^n $, its Kolmogorov complexity is $o(n)$ (thus not Kolmogorov random) since the program which says essentially:

Let $i=1.$
Load register with $x_i,\ldots,x_{i+L-1}$
Compute output bit $z_i=f(x_1,\ldots,x_L)$ and output it
Compute state update bit $x_{i+L}=f(x_i,\ldots,x_{i+L-1})$
Update state to $(x_{i+1},\ldots,x_{i+L})$
$i\leftarrow i+1$
If $i>n$ Output $(x_1,\ldots,x_n)$ and Halt else Go to 2,

can  generate a sequence of arbitrary length $n$ while $L$ is fixed.

More precisely, since the set of all functions $f:\{0,1\}^L \rightarrow \{0,1\}^L$ has cardinality $(2^L)^{2^L}=2^{L2^L}$ we can specify $f$ with $L2^L$ bits.

The program, and its input, obviously have length $O(L)$ bits. So the program complexity in bits is dominated by the $f$ specification.

Thus as $n\rightarrow \infty$ there is no finite constant $c,$ such that

$$K(z_1,\ldots,z_n)=O(L2^L) \geq n-c$$
holds. Hence the output is not Kolmogorov random.


How to implement the Salsa20 hash function? I am currently implementing Salsa20 from the specification as an exercise in learning and self-flagellation.

I have Sections 1-7 passing the test examples provided. I am now stuck on Section 8, The Salsa20 hash function (Page 6):

1) What is confusing is the doubleround$^1$$^0$. What does this mean exactly? Perform the doubleround function $10$ times on the $x$ words from earlier? I.e. I perform doubleround($x$) once, then feed the result of that back into the doubleround function again, then repeat that 8 more times?

2) After that it does a littleendian$^-$$^1$($z0 + x0$). I know what the littleendian function is as it was defined previously in Section 7. But what is littleendian$^-$$^1$? The inverse of it? Do I simply pass the result of the $z0$ and $x0$ addition back into the normal littleendian function again (which as a byproduct would reverse the results of the littleendian function)?

3) To produce the final output, do I concatenate the 16 words (4 bytes per word) from the littleendian$^-$$^1$ function together, then convert them to bytes to get the resulting 64-byte sequence?

Perhaps some psuedo code would answer these questions more succinctly.

Gracias amigos.

You are right about the interpretation of the power 10: it's a tenfold iteration. So we apply the function 10 times, starting with $x$, feeding the output as input for the next step. So C-like (I write x for the vector of 16 words $x_0,\ldots,x_{15}$):

y=x;
for (i=0; i< 10; i++){
    y = doubleround(y)
};
return y

The inverse of little-endian is indeed the function that sends a word (32 bits) back to the sequence of 4 bytes in a little endian way, so the least significant byte goes first, and the most significant byte goes last. So it maps $w$ to w & 0xff, (w >> 8) & 0xff, (w >> 16) & 0xff, (w >> 24) & 0xff

Finally, the iteration gives you a vector 16 words, which you add componentwise in the same order with the original input vector. Then you convert them to bytes again, in that same order, and every word in the little-endian fashion described above. (We could also have converted them to bytes first (using the inverse of litleenian) and then done 64 byte additions in order, but this is less efficient, as we then do 64 byte additions instead of 16 word additions).


For encryption with a passphrase, should you re-use the same salt for key generation? Let's say I have a simple "vault" application where users can enter data and a passphrase, and it will be encrypted, requiring them to re-enter the passphrase to decrypt it.

This would be implemented as follows:

generate salt for key generation
generate key from (salt, passphrase) with argon2, scrypt, or whatever else libsodium is using
generate nonce or iv
encrypt and sign (plaintext, key, nonce or iv) with chacha / aes-gcm / whatever else libsodium is using
store (ciphertext with signature, salt, iv or nonce) as I need all 3 to decrypt from the passphrase

My question: is there an advantage or disadvantage to re-using the salt everytime for the same user? Most crypto examples re-use keys, which is fine as long as the IV or nonce is different. However if I generate and store the salt everytime I'm effectively using a different key everytime. Is this good / bad / unimportant?

The purpose of a salt started with password storage. Within the very common use-case of using a hash function to store usernames and passwords, unsalted password hashes reveal which users have the same password. This reveals a lot of information about the underlying passwords and would make password hash "cracking" much more efficient.

In your use-case you are not dealing with hashed passwords but password-derived keys, however, the use-case for salts is similar. Would it be an acceptable design for your vault to reveal that all ciphertexts are encrypted using the same derived key? If, for example, your vault allowed users to specify per-file passwords for key derivation a static salt may reveal that multiple files used the same password to derive their encryption key.


Is it possible to have a signature that signs itself? This is a curiosity. I don't see any value (yet) of using this.

Is it possible to have a signature that signs itself?

What I mean is that when you send a signed message, you send something like $(message \mathbin\| signature)$, where $signature = Sign(message)$. Is there a signature scheme in which $signature = Sign(message \mathbin\| signature)$?

Because the message should be hashed, you can't solve for $signature$ or do some sort of meet-in-the-middle solution.

My initial thoughts are (1) using SHA-2 or some other hash functions vulnerable to a length extension attack or (2) use homomorphic hash in some fashion. (1) would still require brute-force, but it would reduce computation. I haven't figured out how to use (2), especially since all the homomorphic hashes I know about aren't homomorphic w/r/t concatenation.

Is there a signature scheme in which $\text{signature} = \mathsf{Sign}(\text{message} \mathbin\| \text{signature})$ ?

With standard RSA signatures (RSASSA-PKCS1-v1_5, RSASSA-PSS of PKCS#1), that's possible if one chooses the public/private key pair for that purpose, as a function of the message. On top of that one can even make the signature nearly anything (any bytestring the size of the public modulus except two¹: the all-zero bytestring, and its variation with the last byte 0x01).

I'll use RSASSA-PKCS1-v1_5 with RSA-2048 and SHA-256, because that's simple and common. I'll silently assimilate bitstrings to integers per big-endian convention.

Choose our arbitrary message $M$. Choose our 256-byte signature $S$ of 2048-bit, other than 0 or 1, and not overly close to $2^{2048}$ (say, the first byte is not 0xFF). Hash $M\mathbin\|S$ with SHA-256, yielding $H$, and form the 256-byte representative per EMSA-PKCS1-v1_5
$$R = \mathtt{00\,01}\,\underbrace{\mathtt{FF…FF}}_{202\text{ bytes}}\,\mathtt{00\,30\,31\,30\,0d\,06\,09\,60\,86\,48\,01\,65\,03\,04\,02\,01\,05\,00\,04\,20}\mathbin\|H$$

There remains to build a public/private RSA key pair $(N,e,d)$ with $N$ of 2048 bits such that $S^e\bmod N=R$ and $S<N$, which will insure that $S=\mathsf{Sign}_{(n,d)}(M\mathbin\|S)=S$, as asked.

The central idea is to choose $N$ the product of two primes $p$ and $q$ such that we can find odd $e_p$ with $S^{e_p}\equiv R\bmod p$ and $e_q$ with $S^{e_q}\equiv R\bmod q$, with $(p-1)/2$ and $(q-1)/2$ coprime, and product of distinct small primes. We'll then find $e$ by using the Chinese Remainder Theorem. Refer to this answer for details.

That takes like 30s in Python, Try It Online! (revised 2020-06-13).

¹ For deterministic schemes, there can be a few more forbidden signatures, depending on message. That's because when $R=S$ the method described won't work. However, exhibiting a concrete example would be a break of the hash.


How are the IVs of SHA-512/256 and SHA-512/224 calculated? This seems odd to me, because there are a lot of resources out there saying that the initializer values of SHA-512 and SHA-384 are the first 64 bits of the fractional parts of the square roots of prime numbers. For SHA-256 and SHA-224, the 32 LSBs or MSBs of those values are used.
But this question came into my mind that what about SHA-512/224? How on earth are 0x8C3D37C819544DA2 and others calculated? And I have searched a lot and ironically, had no luck.
So, how are those calculated?

Those are calculated using the "SHA-512/t IV Generation Function", as described in FIPS-180 (pdf, see 5.3.6), the Secure Hash Standard.

The procedure is to first modify the normal SHA-512 IV, then calculate the hash of a string describing the truncation mode used, and use that as the IV. Those IVs are essentially just predefined hash outputs and so not any particularly nice numbers.

The reason it is done like this is to allow arbitrary truncation lengths below 512 (except 384, which has its own hash which was defined earlier).


Is the AES Key Schedule weak? After reading this paper entitled Key Recovery Attacks of Practical Complexity on AES Variants With Up To 10 Rounds, I was left wondering why AES's key schedule is invertible.
In the paper, the authors use a related-key-attack to recover the round keys, bit by bit, making some guesses, but they are eventually able to recover the original key by simply putting the round keys through the inverse key schedule.
If the round keys were derived from some one-way function of the key, then this attack would not be possible. Why make the key schedule invertible? Doesn't this reduce the strength of the cipher?

Now, the AES Key Schedule may be weak (it certainly does appear to be the weakest part of AES); however, I don't believe invertibility is really the problem.
If someone has a way to get some information on the last-round subkey for an N round cipher, well, he has some information on the original key if the key schedule is invertible; if he determined $k$ bits of that subkey, that is equivalent to knowing $k$ bits of key. Using that to complete the attack is the easiest way to attack the key, and so that's what attacks on AES (and AES variants) do.
On the other hand, if the key scheduling were noninvertible, there is another avenue of attack; gaining information on the last-round subkeys also gives us information about what the cipher state was after N-1 rounds. Using this information, we can presumably use the same style of attack to get information about the N-1 round subkeys. And, since we're asking the distinguisher to go through one less round, it'd presumably be stronger, and hence can be expected to take less effort than recovering the round N subkeys. Then, after recovering the round N-1 subkeys, we can start attacking the round N-2 subkeys, etc.
With this hand-waved approach, the attacker can get the entire set of subkeys with an effort that is only a constant factor greater than obtaining the single round subkey. And, even if knowledge of all the subkeys cannot give us information of the real key, it is enough information to encrypt/decrypt with the keys (which is usually why we're interested in the key in the first place).
Again, published attacks against AES and AES-variants don't take this approach, because it is more work (and harder to specify) than inverting the key schedule; however, it does show that making the key schedule noninvertible won't, by itself, make things that much more secure. If it does make things more secure, it's because that change would prevent someone from finding the last round subkeys, instead of preventing him from parlaying that knowledge into knowledge of the original key.
In addition, making the key schedule invertible does have these benefits in practice:

It's easy to prove that each subkey is unbiased (that is, each of the possible $2^{128}$ values is equiprobable), given that the original key is unbiased. If the keyschedule were noninvertible, well, this might not hold (and, in fact, with a 128-bit key, there would likely be values that a particular round key cannot hold). It's not at all obvious if having nonuniform subkeys would lead to a weakness, however with an invertible key schedule, we don't have to worry about it.

One implementation approach that I've seen that some AES hardware take is that if the AES key was to be used for decryption, we give the hardware the last round subkey (and possibly next-to-last for 192 and 256 bit AES). Then, as the data was being decrypted, the hardware would run the key schedule in reverse, deriving the previous round key as required. This allows the hardware not to run the full AES key schedule before starting decryption, and also without having the full AES subround keys preprogrammed. This approach may be trickier with a noninvertible key schedule (depending, of course, on the details of how it works).


Ciphertext compression (Ring-LWE encryption and authentication system) after encryption? Recently I came across an interesting looking cryptography article Ring-LWE Ciphertext Compression and Error Correction: Tools for Lightweight Post-Quantum Cryptography by Markku-Juhani O. Saarinen, which specifically state

  Ciphertext compression can significantly increase the probability of decryption errors.

Which I wonder now, does this indeed mean compressing the ciphertext, which I undertand isn't sensible (basically since encryption should randomize the output so it doesn't really compress after the operation) or doing the compression in the same go? Analogously to how AEAD does encryption and authentication.

I tried to gleanse something from the paper and read about this from the Internet, but being a rather layman on encryption methdos certainly doesn't help.

It does indeed mean to compress the ciphertext.

In very simplified terms:

You can think of the ciphertext generated by a Ring-LWE scheme as a bunch of numbers modulo a number $p$, in this case the prime 12289. Indeed, this output is effectively indistinguishable from uniformly random for someone who doesn't know the private key, as per the worst-case hardness theorem for Ring-LWE.

Decryption involves manipulating these numbers using the private key, resulting in a bunch of other numbers modulo $p$. Then, it tests whether these numbers are closer to 0, or 12289. How far away these numbers are from either 0 or 12289 is the error. The error is introduced by the encryption process itself, and is essential to the security of the system. Obviously, if the error is bigger than 12289/2, decryption won't be correct! Parameters are chosen such that the probability that this happens is exceedingly small.

Now, the way that this compression works is by compressing the numbers modulo 12289 all the way down to modulo 256. So if (approximately) $x \in [0, 48)$, then we map: $x \mapsto 0$. If $x \in [48,96)$, we map: $x \mapsto 1$, etc.

Obviously, we lose information, and we introduce a bit more error. Due to the nature of the decryption process, this error is magnified further, quite significantly so. But if the error was small enough to begin with, we can get away with the compression, and we can utilize all the benefits of 8 bit modular arithmetic, which is huge on hardware like AVR.


How many trials does it take to break HMAC-MD5? I know that you can find collision in MD5 with 2^64 trials using Birthday paradox. Now everyone is saying that HMAC-MD5 is significantly more secure. How can I quantify this security? My question is how many trials does it take to find a collision in HMAC-MD5?

You can find a collision in MD5 at much lower cost than $2^{64}$ evaluations of MD5.  You could do the same for HMAC-MD5, if you knew the key, which renders it unfit for unusual applications such as commitments.

But the standard security conjecture of HMAC-MD5 is that it is a pseudorandom function family, which assumes the adversary doesn't know the key.  Any program the adversary writes which takes a function as a parameter and evaluates it as an oracle at arbitrary messages of its choice won't behave much differently whether you feed it (a) HMAC-MD5 under a uniform random choice of key, or (b) a uniform random choice of function.

f0_memo = {}
def f0(x):
    if x not in f0_memo:
        f0_memo[x] = os.urandom(16)
    return f0_memo[x]

k = os.urandom(32)
def f1(x):
    return hmac_md5(k, x)

def distinguisher(prf):
    y0 = prf('hello world')
    y1 = prf('query query quite contrary how does your crypto grow')
    ...
    return 1 if i_predict_it_was_f1 else 0

# Then the probability that distinguisher(f0) = 1 is not much different
# from the probability that distinguisher(f1) = 1.

Formally, we define the PRF-advantage of a random algorithm $D$ at distinguishing a family of functions $f_k$ (e.g., $\operatorname{HMAC-MD5}_k$) from uniform random to be:
\begin{equation*}
  \operatorname{Adv}^{\operatorname{PRF}}_f(D)
= \lvert\Pr[D(f_k) = 1] - \Pr[D(u) = 1]\rvert,
\end{equation*}
where $k$ is a uniform random key for the family $f_k$, and $u$ is a uniform random function.  We conjecture that for any distinguisher algorithm $D$, $\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D)$ is small enough we're not worried anyone can exploit it, as long as the computational cost of $D$ is within reason—fewer than $2^{128}$ bit operations, for instance.  This formalism will come in handy later, but let's look at distinguishing strategies first.

Let's suppose $k$ is 256 bits long.  It could be as long as 512 bits for MD5 and fill an entire block, or technically longer, but there are problems with using keys that fill or exceed a block in HMAC, and 256 bits is perfectly adequate for serious security.

You could try to guess $k$ and see if evaluating the oracle at some message $x$ yields $\operatorname{HMAC-MD5}_k(x)$, but there are $2^{256}$ possibilities for $k$, rendering that strategy computationally impossible—though formally we can conclude that there exists a distinguisher $D$ that queries the oracle only once such that $\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D) = c/2^{256}$, where $c$ is the number of times $D$ can afford to compute HMAC-MD5.*

What about collisions?
If you evaluate the oracle at $2^{64}$ different inputs, you would probably find a collision.  That is true for HMAC-MD5 under a uniform random key and true for a uniform random function, so a priori, finding a collision doesn't break the security of a PRF by distinguishing them on its own.  However, MD5 also has the property that if $x_0 \ne x_1$ collide under MD5, with $\operatorname{MD5}(x_0) = \operatorname{MD5}(x_1)$, then so do $x_0 \mathbin\Vert y$ and $x_1 \mathbin\Vert y$ for any common suffix $y$, as long as $x_0$ and $x_1$ have the same length.

So if you query the oracle on a whopping $q = 2^{64}$ inputs, with high probability you will find a collision $x_0 \ne x_1$; then to tell whether the oracle is HMAC-MD5 or a uniform random function, pick a suffix $y$, say a single zero bit or a GIF of a funny cat video, and query the oracle at two more inputs: $x_0 \mathbin\Vert y$ and $x_1 \mathbin\Vert y$.  If they still collide, the evidence is overwhelming in favor of HMAC-MD5 over a uniform random function.†  In particular, the conditional probability that $x_0 \mathbin\Vert y$ and $x_0 \mathbin\Vert y$ collides is 1 for HMAC-MD5, and $2^{-128}$ for a uniform random function.  For any number of queries $q$ with this distinguisher, by the birthday paradox, $$\Pr[D(\operatorname{HMAC-MD5}_k) = 1] \approx q^2\!/2^{128}.$$

It turns out that this generic attack on HMAC over any iterated hash function is the best known attack on the PRF security of HMAC-MD5.  (There are other distinguishers for HMAC-MD5 from ‘HMAC’ over a uniform random function, but this is not really important for applications like MACs below, and their area*time cost is infeasibly large, well over $2^{128}$.)  So the security conjecture for HMAC-MD5 is that $$\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D) \leq q^2\!/2^{128} + c/2^{256}$$ for any random algorithm $D$ making at most $q$ queries with area*time cost at most $c$.  And since $2^{256}$ is a very large denominator, you do not have enough spare change rattling around your pocket to afford a computer large enough for long enough to make a dent in it, so we might skip that term altogether and call it $q^2\!/2^{128}$.‡

What about using HMAC-MD5 in an application, for instance as a message authentication code?  It turns out that any pseudorandom function family makes a good message authentication code.  The security goal for a message authentication code is unforgeability: an adversary wins if, after querying an oracle to learn the authenticators on for $q$ messages of their choice, they can forge an authenticator on a message not previously sent to the oracle.

def forger(mac):
    y0 = mac('hello world')
    y1 = mac('The Magic Words are Lightning Sloth Race')
    ...
    return (authenticator, 'another message')

The MAC is secure if the forger has negligible probability of winning, which we formally define to be the MAC-advantage of a random algorithm $F$ at forging authenticators: $$\operatorname{Adv}^{\operatorname{MAC}}_f(F) = \Pr[(a, m) = F(f_k), f_k(m) = a],$$ for any random algorithm $F$ that returns a message it didn't send to the oracle.  As above, the forger could submit $2^{64}$ queries to the oracle and probably find a collision $x_0 \ne x_1$; then query the oracle to find the authenticator for $x_0 \mathbin\Vert y$, and forge it as the authenticator for the message $x_1 \mathbin\Vert y$.  Is this the only way?  We could study strategies for forging HMAC-MD5 directly, but there's a simpler way to understand the MAC security of HMAC-MD5 if we accept the PRF security of HMAC-MD5, using the formalism above.

Suppose we had a successful forger subroutine which and succeeds with probability $p$.  Then we can define a distinguisher:

def make_distinguisher(forger):
    def distinguisher(f):
        a, m = forger(f)
        return 1 if f(m) == a else 0
    return distinguisher

If $f$ is HMAC-MD5 under a uniform random key, the forger succeeds and the distinguisher returns 1 with probability $p$.  If $f$ is a uniform random function, the distinguisher returns 1 with probability $1/2^{128}$, because the probability that any fixed 128-bit string $a$ is equal to $f(m)$ when $f$ is a uniform random function is $1/2^{128}$.  So we have
\begin{align*}
  \Pr[D(f_k) = 1] &= p = \operatorname{Adv}^{\operatorname{MAC}}_{\operatorname{HMAC-MD5}}(F), \\
  \Pr[D(u) = 1] &= 1/2^{128},
\end{align*}
from which we find that $$\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D) = \lvert\operatorname{Adv}^{\operatorname{MAC}}_{\operatorname{HMAC-MD5}}(F) - 1/2^{128}\rvert.$$  But the security conjecture for HMAC-MD5 is that $\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D)$ is very small for any distinguisher $D$.  We can use that to conjecture that the forgery probability must also be very small: $$\operatorname{Adv}^{\operatorname{MAC}}_{\operatorname{HMAC-MD5}}(F) \leq \operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D) + 1/2^{128}.$$

So, what does it cost to find HMAC-MD5 collisions?
Without knowledge of the key, an adversary can find a collision in about $2^{64}$ trials by the birthday paradox.  With knowledge of the key, it's a parlor trick, but if you tell the adversary your key, you're violating the security contract of HMAC-MD5.  I recommend avoiding HMAC-MD5 for any applications with anywhere near $2^{64}$ messages under a single key!  I also recommend not telling the adversary your key.

* If $D$ tried 1000 keys, it would obviously have a higher chance of success than if it tried only 1, but there is a higher cost to trying 1000 keys, whether you try them on one computer sequentially or a thousand computers in parallel.  Note that multi-target attacks against $n$ targets at once may be cheaper than $n$ single-target attacks separately, but for a 256-bit key the difference doesn't matter for all imaginable numbers of targets $n$ in human existence.  But beware using HMAC-MD5 with 128-bit keys!

† Of course, exactly the same strategy will distinguish any iterated hash function from a uniform random function, but won't distinguish between two different iterated hash functions!  It could just as well be HMAC-HAVAL128 or anything else with a 128-bit state.  That's not the concern of the pseudorandom function family's security claim, which is only about distinguishing the family in question (HMAC-MD5) from a uniform random function of the same domain and codomain.

‡ It may sound like there is a high cost $c$ to storing all the outputs of the oracle to search among them for a collision, but actually the collision search can be done with negligible additional computation and storage using Pollard's $\rho$, and, if the oracle allows, can be parallelized to run faster (at the same total cost) with the van Oorschot–Wiener algorithm.


MARS and RC6 in CUDA I am working on a project where I am benchmarking the 5 AES finalists (Rijndael, Twofish, Serpent, MARS and RC6) on CUDA Hardware.

My problem is that I am no experienced CUDA programmer. My approach is to find open source projects that implement these algorithms in CUDA and modify them to match my needs.

It was obviously no big problem to find Rijndael implementations. Twofish and Serpent were also no big problem. But I can't find anything about MARS and RC6. I already heard that with these two algorithms there might be some problems with royalty but I am not sure how serious this is.

Anyway, does anybody know if there is some source where I can find CUDA implementations of these algorithms? If there isn't something I would have to write them myself but I think these won't be good for Benchmarking.

I did something similar last year with SHA-3 finalists. I can tell you from personal experience that the best course of action is to find the C/C++ reference implementations and port them to CUDA. Start naively by writing a kernel that does the entire operation in one GPU thread. Once you have it working, you can optimize for the hardware.


Statistical closeness implies computational indistinguishability This is so trivial that authors usually don't bother to give an explicit proof. But for me there is some vagueness.

We say that two ensembles $X_n$ and $Y_n$ are statistically close, if
$$ \Delta(n) = 1/2 \sum_{\alpha}|\mathbb{P}[X_n = \alpha] - \mathbb{P}[Y_n = \alpha]| $$ is negligible in n. The probability is taken over the randomness of $X_n$ and $Y_n$ respectively.

We say that two ensembles are computationally indistinguishable if for every PPT-adversary D we have
$$ |\mathbb{P}[D(X_n) \to 1] - \mathbb{P}[D(Y_n) \to 1]|$$
is negligible.

Why the former implies the latter?

I do understand that for every deterministic function $f$ we have
$\Delta(f(X), f(Y)) \le \Delta(X, Y),$ where $\Delta(\cdot, \cdot)$ is the statistical distance.

But in the case of PPT adversaries $D$ is not deterministic, there are implicit random coins. Why can we treat PPT-algorithm $D$ as deterministic function?

A probabilistic distinguisher is still a deterministic function of its input and random coins. So a probabilistic distinguisher trying to distinguish $X$ from $Y$ is equivalent to a deterministic distinguisher trying to distinguish $(X,R)$ from $(Y,R)$ where $R$ is a uniform distribution over random coins (importantly: independent of $X$/$Y$).

But:

\begin{align}
  \Delta\Bigl( (X,R), (Y,R) \Bigr) &= \frac12 \sum_{\alpha,r} \Bigl| \Pr[(X,R)=(\alpha,r)] - \Pr[(Y,R)=(\alpha,r)]\Bigr|
\\
   &= \frac12 \sum_{\alpha,r} \Bigl| \Pr[X=\alpha]\Pr[R=r] - \Pr[Y=\alpha]\Pr[R=r]\Bigr| \\
   &= \frac12 \sum_{\alpha,r} \Bigl| \Pr[X=\alpha] - \Pr[Y=\alpha]\Bigr| \Pr[R=r]
\\
   &= \frac12 \sum_{\alpha} \Bigl| \Pr[X=\alpha] - \Pr[Y=\alpha]\Bigr| \;\underbrace{\sum_r \Pr[R=r]}_{=1} \\
   &= \frac12 \sum_{\alpha} \Bigl| \Pr[X=\alpha] - \Pr[Y=\alpha]\Bigr|  \\
   &= \Delta(X,Y)
\end{align}

In short, having access to some distribution that is independent of $X$/$Y$ doesn't help (or hurt) to distinguish $X$ from $Y$.


Sum of digits flaw name request Let's say I am making an encryption algorithm, and in the algorithm in have the following step: "multiply the integer from the previous step by 9 and take the sum of the digits of the resulting number."  By doing this, I've guaranteed that the result will be divisible by 9 in base 10, which let's say I did not expect.  My question is:  What is this error called, if it is an error?  Is this a specific case of a general class of flaws in crypto algorithms?

It depends completely on the algorithm if it would matter that the result would be divisible. If it was a cryptographic error I don't think it would have a specific name. Possibly a side effect or unexpected property.


RSA 1024bit decryption performance i want to know how many RSA 1024 bit long key decryption can a regular pentium4  computer do per second ? how to calculate RSA performance and determine its remaining time ?

Good link: Crypto++ for pentium 4

                            Milliseconds/Operation     Megacycles/Operation
    RSA 1024 Encryptio       0.09                         0.27
    RSA 1024 Decryption      2.28                         6.68

CPU frequency of the test platform is 2.93e+009 Hz.
I think the performance depends on the language, library and CPU architecture.


Finding sum of two encrypted numbers Let's consider such process:

Two emitents emit two (integer) secret numbers independently
They encrypt (encode) these number in such a way that no-one (except emitent) can decode these numbers. Emitents also cannot decode/know numbers of each other.
Now having two block of decoded numbers we need to find the sum of these numbers

So, I need algorithms for achieving above

Number decoding (point 2 above)
Sum calculation (point 3 above)

Let $a$ and $b$ be the numbers emited rsp. by person A and person B. $E(x)$ means encoded form of $x$.

$E(a)$ and $E(b)$ are publicly known, right?

Note that if person A knows $a$, $E(a)$, $E(b)$ and person B knows $b$, $E(a)$, $E(b)$ and it is possible to calculate $a+b$ from $E(a)$ and $E(b)$ (that is what you want to do, right? So it must be possible) person A can calculate $a+b$ from the data he has. He also knows $a$ and calculating $b$ given $a+b$ and $a$ is trivial. Now person A knows the secret number of person B and person B can calculate the secret number of A same way.

I don't know what is this system going to be used for, but even if A and B trust each other there are still some security risks here.


Is there a cryptographic way (a la mental poker) two people can determine if they both Like each other, without revealing their personal preferences? Specifically: Alice and Bob want to know if they like each other, but won't admit it if the other person doesn't reciprocate. (They're teenagers, or physicists.) They don't trust anyone else, so want to do it cryptographically.

So, say A->B=1 if Alice likes Bob, 0 otherwise. And let B->A=1 if Bob likes Alice, and zero otherwise. They want to compute "(A->B) AND (B->A)", without revealing their individual rankings. Is there a way that the following sequence could be applied:

Alice encodes her answer (either flipping her bit, or not) and sends it to Bob
Bob applies some function to Alice's preference and his own, and sends the answer back to Alice (but also possibly sends some other information or output from the calculation)
Alice applies some inverse function to determine only whether both A->B and B->A were 1, and announces the outcome, without her being able to know (or determine) B->A (excluding repeated games, or Princess Bride style psychological arguments).

My gut instinct is that this can't be done (the AND operator destroys information, and providing any extra outputs would allow Alice to determine Bob's true feelings) but intuition is hard. I'm thinking of solutions along the lines of  poker by phone and the Three-Pass Protocol. It's similar but different to Yao's millionaire problem, which allows two parties to secretly decide if a>=b; that's not sufficient in this case (both because it doesn't distinguish between (1,1) and (0,0), and because it could allow them to quickly deduce their opposite's opinions.

More generally, it could apply to any situation where revealing the truth would be problematic unless the other person was on board.

Appreciate any thoughts!

The answer to your specific scenario is no, it cannot be done. As mentioned in a comment, if Bob knows his preference (B->A) and learns that the result of the calculation is $0$, then Bob now knows Alice's preference, i.e., A->B is 0.


Key and signature sizes of NTRU and NTRU Prime? I would have expected this info to be easier to Google Scholar for, but alas I'm asking here.

Partial answers:

NTRU key size (confused)

  the public key consists of one ring, and so it takes up $11 \times 439 = 4829$ bits, which compresses to 604 bytes.

what are the NTRU keysize and application in industry?

  For instance, with $N = 1171$ and $q = 2048$, which are recommended parameters, public and private keys are of size 1.57 KB.

So

Those don't agree.
What about the size of NTRUsign signatures?
Have Bernstein, Lange, Chuengsatiansup, and van Vredendaal published a signature variant of NTRU Prime yet? (I only see encryption [1]), but in the paper:

  Our public keys are field elements, easily squeezed into 1232 bytes.

Any idea what signature sizes of an NTRU Prime-based signature scheme would be?

[1]: NTRU Prime, 2016

The inconsistency of Ntru public key size is due to the fact that those are from two different parameter sets (targeting different security levels). The latest version of recommended parameter sets can be found from
https://eprint.iacr.org/2015/708.pdf

Ntru prime does not have a signature scheme as far as I know.

NtruSign signature scheme is broken and is not recommended for use. The same group of people come up with a new scheme named pqNTRUsign which is secure against the transcript attack that breaks ntrusign.
https://eprint.iacr.org/2014/457.pdf

The reference implementation of both Ntru and pqntrusign can be found from
https://github.com/NTRUOpenSourceProject/ntru-crypto


Decrypting data on client side for use inside program So I am developing a python program and encrypting the trained machine learning models which need to be decrypted when loading them on client side. My program will deployed on the client's machine with no internet access and I need to protect my models.

Now I'd like to ask the following

Whether using symmetric key encryption and then hiding the key inside my code is the right way to go about it or there is a better way?
If this is the only way then how to what is the best way to hide the key?

I am already obfuscating the code by compiling cythonized python code so should I just hide the key inside that?

If obfuscation id enough security, and you only want to protect the privacy of your data against meager adversaries and you have no requirements about authentication then your solution seems ok.
Also it isn't very crypto related.
Though there is a field of cryptographic obfuscation that is not practical to use.


Sigma protocol with Pedersen commitment and Hash function Suppose I construct a Pedersen commitment as $g^m h^r$. I could pick the randomness in a "pseudo-random" fashion, such that $r = H(m)$. My questions are as follows:

Given that $H$ is collision-resistant, does the security properties of the Pedersen commitment still hold? (i.e. is it still hiding and binding?)
Is there a way to construct a Sigma protocol which would prove in Zero-knowledge that a) I know $m$ and b) The commitment randomness is picked such that $r=H(m)$?

Edit: I do not require some specific hash function. Any pseudo-random function would serve my purposes.

This is no longer a secure commitment. Note that there should not be any way to efficiently verify if a given commitment value $c$ is to a message $m$. However, once you derive the randomness in this way, an attacker could try to guess $m$ and verify if this guess is correct by checking if $g^m\cdot h^{H(m)} = c$. Thus, this is not a secure commitment scheme.


Can `hash( messageA ) + messageB` be used to determine `hash( concat( messageA, messageB ) )`? In .NET and other programming platforms all hash functions (such as MD5, SHA256, etc) can be used with streams of bytes, potentially forever - so it isn't necessary to read an entire multigigabyte file into an in-memory buffer to compute the hash of the file, the hash algorithm simply considers new data as it arrives and updates its internal state accordingly.

...it makes me think of the arithmetic Mean function which can work in the same way below, using C# IEnumerable<Byte> to represent a potentially infinite stream of data:

public static int Mean(IEnumerable<Byte> bytes)
{
    UInt64 sum   = 0;
    UInt64 count = 0;

    foreach( Byte b in bytes )
    {
        count++;
        sum += b;
    }

    return (Double)sum / (Double)count;
}

I've long assumed that hash functions might work in the same way as accumulators (warning: considerable over-simplification, I know there's more at work):

public static Byte[] SomeHashFunction(IEnumerable<Byte> bytes)
{
    Byte[] hashState = new Byte[32];

    foreach( Byte b in bytes )
    {
        ConsiderByte( hashState, b );
    }

    return hashState;
}

With arithmetic-mean, provided you know the count and the mean so-far, then you can compute an updated average as new data arrives without needing to see all previous data. E.g. the high-school exam question "If the average height of 20 students is 157cm, and the 21st student is 181cm, what is the new average?" ( ( 157 * 20 ) + 181 ) / 21 == 158cm.

I'm assuming we can do the same for hash functions like SHA256, then SHA256( concat( messageA, messageB ) ) should be computable given SHA256( messageA ) and messageB separately.

But instantly I imagine there's some "final processing step" that non-trivial hash algorithms will do to prevent that (such as not processing individual bytes, but processing blocks of bytes and padding them to some amount if the input data isn't long enough (indeed, in .NET there's the TransformBlock function but also the TransformFinalBlock function so there definitely is special processing when the end of data is reached). This means that provided we can get the internal state of the hash function after processing messageA and persist it then we can compute hashes of concatenated messages. Are there any weaknesses in any algorithms like SHA256 where the internal state can be derived from the output? Is this a weakness at all? What techniques can be used to prevent the internal state being derivable from the output?

With a little more information, an attacker can indeed get up to some funny business by abusing this "internal state-revealing" property of Merkle-Damgard style hash functions (this includes MD5 and SHA-1 and SHA-2 but not SHA-3).

With hash(message1) and len(message1) but not message1 itself, there is one specific message2 such that an attacker can forge a valid hash(message1 || message2) by running further iterations of the hash algorithm starting with hash(m1).

When a hash of this style is used to generate a Message Authentication Code (MAC), that message is vulnerable to "length-extension attacks". That means an attacker can append the message with their own malicious message and forge a valid tag.

Of course, there are ways to prevent this kind of attack. One easy method is the "wide pipe" strategy -- simply generate your hash with more bits than you need, and truncate your final result! Now the hash code you output no longer represents a valid internal state of the algorithm.

Modern standards for hash functions use this or other such strategies to prevent this from being a problem in practice. For example, HMAC (the standard way to build a MAC from a hash) runs the hash function twice in a way that avoids length extension attacks.


Digital signatures under plain RSA Show that digital signatures under plain RSA are insecure (Plain RSA means that signing is done by calculating $m^d\bmod n$, with $0\le m<n$, and no padding or hashing of $m$).

Write an algorithm that, given someone’s public signature verification key ($e$, $n$), can easily generate a (message, signature) pair for some message that the private key holder never intended to sign. For full credit your algorithm should not require a signing oracle and your algorithm should generate “signed” messages where your message is different than its signature (Hints: The message need not have any meaning to count as a forgery. Think backwards).

I happened to see some similar question like this. The question mentioned about sending fake signature message. The method is like this:

Find some random string R.
Use the public key to encrypt the random string R, let the result be X.

(R,X) is your signature pair.(Think backwards)
When someone verifies the signature, he'll compare {R} with X which are equal.


With TLS and ECDHE, how does curve selection work? Given that a TLS client and server have already agreed upon ECDHE for session key establishment, how does the selection of the actual elliptic curve ("domain parameters") being used for deriving the DH keys work?

Is the curve somehow negotiated and if so how does that work (in the context of TLS)?

As described in section 5.1 of RFC 4492, the client announces what curves it supports in an extension message, included in the ClientHello message. This gives the server the possibility to check whether client and server both support at least one specific curve, before choosing whether elliptic curves will be used at all.

Then the server chooses the curve. The curves named in the Supported Elliptic Curves extension are ordered by client preferences, so a courteous server may elect to follow the client's preferences, i.e. the first one in the client's list that the server also supports (where "supports" means "has the code for it, and deems it acceptable"). But, really, the server chooses.


Can a zero knowledge proof be faked through http? I'm working on a small blockchain project and I came across the idea of using zero knowledge proofs to enforce anonymity. I think I generally understand the idea, but I'm unable to find an explanation of a reliable way to implement this system with a protocol like HTTP.

For example, given the classic sudoku example, where you have found the solution to the puzzle and want to prove to someone that you know the solution, without showing the solution, you can just create a mapping where you shuffle the numbers. Whenever the person asks for a row, you show them the row they asked for, with the valid numbers.

My question is: If you are implementing this in HTTP and one server is trying to prove to the other that it knows the answer, when the verifier asks for a row via HTTP, cant the prover just provide a fake row of the numbers 1-9?  The prover would only need to generate a random combination of the numbers, making sure theyre all only used once, and the prover would deem this as valid.

I must be missing something here, but I fail to see how this could possibly be implemented between two servers. Any help would be tremendously appreciated

Yes, you are missing something. :)

The trick is that the prover commits to the number in each square individually.

The verifier doesn't always get a row, column or block. The verifier choses to see one of those or the permutation of the original puzzle.

If the verifier choses the permutation he can check if the revealed number are indeed a permutation of the original puzzle, if he choses a row or column he checks if all the numbers from one to nine are in it.

Since the prover does not know what is requested he has to commit to a valid filled Sudoku field to make sure that the numbers in each row, column and block are the numbers from one to nine. Since the permutation could be selected it must also be a solution to the initial problem.

Note that you have to repeat this process many times to get security because the prover could guess what the verifier will ask for. In every iteration a new puzzle must be chosen and the verifier must select which part to query independently at random.


How is a Caesar (Shift) Cipher represented at Binary level? If I want to encrypt the letter H, represented by ASCII 01001000 in Binary, with a key of 1, represented by  00110001. We should get the letter I, represented by 01001001. (H+1 = I through a shift). What actually is the binary manipulation process to get I using the key of 1? How do we get to 01001001 using 00110001? Straight addition of the Binary values doesn't come to the answer.

A Caesar cipher commonly operates on letters. This is often true for classical ciphers. Modern ciphers instead operate on binary values; most of the time implementations consider bytes instead of bits as atomic values.

The 26 letters form the alphabet of the classical cipher. The alphabet is a sequence of characters; in this case it is simply the English alphabet or ABC. The shift of the Caesar cipher is performed using the location within the sequence, using modular addition. The modulus is the number of characters in the alphabet, in this case of course 26. For this reason it is better to use 0 as starting index for the letter A. Modular addition can simply consist of first adding the shift, and then performing the modulus operation.

Fortunately the characters of the alphabet are already in order within the ASCII table. So instead of doing any binary arithmetic you can simply subtract the value of the letter A from the character you need to encrypt/decrypt. This way you get the location in the sequence of the alphabet. Then you do the shift. Finally you can simply add the value of the letter A to get the ciphertext back.

Creating a larger alphabet, for instance containing letters and digits, is certainly possible. In that case the letters and digits combined are the ciphertext. Determining the index in the alphabet for the cipher will of course get a bit harder (e.g. if x is a digit then the location could be x - '0' + 26 to place it after the letter Z in the alphabet). Alternatively you could write down the alphabet "abcdefghijklmnopqrstuvwxyz0123456789" and then use an indexOf function to find the location in the alphabet string.

So in the end, no binary operations are necessary. Addition, subtraction and modulus are all the operations you need.

Notes

Characters outside the alphabet are often removed before performing encryption for the Caesar classical cipher.
There are multiple ways of handling case, but simply converting everything to upper or lowercase - whichever you decide to use - before encryption should do the trick nicely.
Many languages include a remainder operator rather than a modulus operator. This can be tricky when decrypting as subtraction may result in a negative value.


Pseudo Random Generator (PRG) from Rabin function I'm trying to make a PRG using the Rabin function. The code (in Java) I wrote to implement the function is:

poublic static int rabinFunction(int m, int publicKey) {
    return (int) Math.pow(m, 2) % publicKey;
}

A trivial usage (using the numbers from the wikipedia link) would be:

int m = 20;
int pq = 7 * 11;

// output will be 15
int output = rabinFunction(20, 77);

I'm using this one way function to create a pseudo random generator. Basically, I run the Rabin function and use the least significant bit from the function output as part of my pseudorandom value. I use the return value from the previous execution as the seed for the next execution and I repeat this process until I've generated enough bits to encrypt my message. The issue I'm having is that the Rabin function returns the same values after 4 iterations:

rabinFunction(20, 77); //==> 15
rabinFunction(15, 77); //==> 71
rabinFunction(71, 77); //==> 36
rabinFunction(36, 77); //==> 64
rabinFunction(64, 77); //==> 15! Back to where we started, etc

I'm assuming that using the output from a previous execution of the Rabin function as the seed for a new one isn't correct. Can someone explain why this is wrong? Thanks in advance.


What's a quadratic map and how do I invert it? I'd like to get just the mechanics of multivariate-quadratic cryptography, so I'm trying to understand the definitions involved.  From Wolfram's website, I get that a quadratic map is for example a recurrence of the form $x_{n+1} = 2 + (x_n)^2$.  I will need an initial value too, right?  I choose $x_0 = 3$.  What's the inverse of this map and how do I get it?

I'm guessing an inverse of a quadratic map would be the transformation that takes $x_n$ back to $x_{n-1}$ so the using the example given in the first paragraph, $x_0 = 3, x_1 = 11, x_2 = 123$.  So given $x_2 = 123$, I can return to 11 by subtracting 2 and taking square root: that is, $x_{n-1} = \sqrt{x_n - 2}$ is the inverse map of my example.

It's just a guess.  I've never seen these things before.  Can't find any reference that explains this in baby-steps.

Also, I'm wondering what would be an example of a quadratic map whose input is say a vector.  My example is a 1x1 vector.  What would it look if my input would be a 2x1 vector?

In cryptographic applications a quadratic map is generally conceived as a system of n quadratic equations in n variables.  Each equation is generally represented as an n-long vector of n variables x and a matrix Mi (for equation i of the system.  The equation is then:

(x^T)Mi(x) = ai

Your are then given the n matrices Mi, and a resultant vector of the ai.  The inversion you are looking for is to find a vector x such that:

(x^T)Mi(x) = ai for all i

If the Mi are chosen at random then the problem of finding a solution to this problem is believed to be intractably hard (NP-hard in fact).  If the Mi are specially chosen (not random at all) one can make inversion easy.  Mulivariate Quadratic cryptography tries to take an easy to solve quadratic map and transform it into a seemingly difficult to solve map.

If you look at the Unbalanced Oil and Vinegar schemes:

https://en.wikipedia.org/wiki/Unbalanced_Oil_and_Vinegar

you get an idea of one such system.


With HMAC, can an attacker recover the key, given many known plaintext/tag pairs? Given many pairs of $(m, t)$, can the attacker compute the key $k$ satisfying $\text{HMAC}(k,m) = t$?  (Assume that $k$ was chosen at random.)

No.  Assuming HMAC is secure against known-plaintext attacks (which is a plausible assumption), the key cannot be recovered.  This follows directly from the definition of a known-plaintext attack; if you could recover the key, you would have a successful known-plaintext attack on HMAC.


Why do the subexponential algoriths for the DLP not work for the ECDLP? Elliptic curve cryptography is much more secure for the same parameters because attacks that work on the DLP do not work on the ECDLP.  Why do the attacks fail in the latter case?

"Attacks that work on the DLP do not work on ECDLP" is a rather vague statement, as ECDLP is just a particular case of DLP, on elliptic curves. I suppose that you refer to DLP over $\mathbb{F}_q$ for some $q = p^k$, $p$ being a prime.
The intuitive reason why the DLP is harder to solve over (well-chosen) elliptic curves is that they are our best construction of a generic-like group, id est a group with seemingly no more structure than the group law. It is known that over a generic group of order $q$, the best algorithm to solve DLP takes $O(\sqrt{q})$ steps.
However, fields do obviously have way more structure than generic groups, and this structure can be exploited. More precisely, there is a family of algorithms, called Index Calculus, tailored to exploit this structure. Note that for some elliptic curves, DLP can be solved via index calculus, hence ECDLP requires "well-chosen" elliptic curves.
Index calculus algorithms work by creating a large base of the relation between the discrete logarithm of small prime values. This system of equations is then solved to get the discrete logarithm of each element of the factor base. Let $(g,h)$ be the DL instance. Next, the algorithm tries to write $g^sh$ as a product of powers of the factor base, for some $s$. Once it finds such an $s$, finding the discrete log of $h$ in base $g$ is easy.
The core notion to answer your question is the need for a base of small prime values: although well defined for a field, "prime" cannot be defined for generic groups, or for elliptic curves. Hence, the index calculus cannot be used on well-chosen elliptic curves. Still, some elliptic curves are affected by the index calculus when there is some map which moves the DLP problem from the curve to some field.


Algorithm for computing modular inverse in MPC Is there any known algorithm for calculating $a^{-1} \pmod{q}$, where $ q < p$ and $F_{p}$ is the prime field of the MPC, in a linear secret sharing scheme ?

I have tried using the standard algorithm, in which the parties generate $r$, then run secure multiplication on shared values to get $r⋅a$ and open it, and then each local invert the result. Finally, each uses local scalar multiplication of their share of $r$ to get shares of $a^{-1} \pmod{q}$.
However this doesn't work when the field of inverse is different from the MPC field.

In general: $a^{-1} \equiv a^{\phi (q)-1} \pmod q$ where $\phi$ is euler totient function. If $q$ is a prime, then $\phi (q)=q-1$ and thus $a^{-1} \equiv a^{q-2} \pmod q$.


Why is the definition of Special-honest verifier zero-knowledge probabilistic? Let $P$ be a prover willing to prove to a verifier $V$ that he knows a witness $w$ satisfying $(x,w) \in R$ for some relation $R$ and some common input $x$.

As found in the literature, $P$ can use a $\Sigma$-protocol for the relation $R$, defined as a 3-move protocol that satisfies the following properties:

Completeness.
Special soundness.
Special-honest verifier zero-knowledge.

My question is concerning the definition of the third property, which is the following:

Definition of Special-honest verifier zero-knowledge (as in the literature): There exists a polynomial-time simulator $M$, which on input $x$ and a challenge $e$, outputs an accepting conversation of the form $(a,e,z)$, with the same probability distribution as conversations between the honest $P,V$ on input $x$.

Clearly, the special-honest verifier zero-knowledge has a probabilistic interpretation (as noted in the part ``...with the same probability distribution as...'') and I wonder what the implications are of omitting it.

In other words, what would be wrong or how this could affect the protocol if the special-honest verifier zero-knowledge property was defined as follows instead?

Alternative (and possibly wrong, but I’d like to understand why) definition of Special-honest verifier zero-knowledge: There exists a polynomial-time simulator $M$, which on input $x$ and a challenge $e$, outputs an accepting conversation of the form $(a,e,z)$.

This other definition doesn't mention probabilities distributions, just the fact that the transcript generated by the simulator should be accepted by the verifier. To me, this implicitly implies that the generated transcript will have to have the same probability distribution as a real transcript (the one obtained from a conversation between a honest prover $P$ and a honest verifier $V$), otherwise the verifier wouldn't be accepting it. Or am I wrong? Do you know of any example in which this is not the case, i.e. the transcript generated by the simulator is accepted by the verifier but still it doesn't have the same distribution as a real transcript?

Any help or clarification with this will be very much appreciated.

The probabilistic nature is not specific to special-honest verifier zero-knowledge but that's what zero-knowledge is about. With zero-knowledge you want to formulate that such an interactive proof does not leak any
information besides the validity of the claim, as it is efficiently simulatable meaning that real and simulated transcripts are not distinguishable.

That a simulator produces accepting transcripts does not necessarily mean that this simulated transcript cannot be distinguished from a real interaction. Assume for instance an artificial simulator that always uses the same $a$ independent of the value $e$. So the transcript could be an accepting one, but one could distinguish transcripts coming from real interactions and simulated ones.


Why to try get key out of white box crypto? How can one protect WBC itself? Help me understand the following. With WBC the question is mainly being stated as can one try to break WBC to identify the key. My question is: Why would one ever want to do that anyways?

If one can locate the WBC itself it should be enough to enc/dec anything she wants with the embedded key. To me it comes to chicken and egg problem where now one would need to "hide" WBC itself within the code to make it any practical.

This is an excellent question.  Unfortunately, I'm afraid I don't know of any really convincing answer.

In principle, one possible application of white-box cryptography would be to build a public-key cipher out of a symmetric-key cipher.  If you could build a white-box cryptographic implementation of AES encryption (say) where no one can recover the key nor figure out how to perform the decryption process, you'd have a public-key cipher.

However in practice I don't think that's actually the motivation for most work on white-box cryptography.  For instance, most published white-box crypto schemes can be easily inverted: given a white-box implementation of encryption, you can easily derive a white-box implementation of decryption.  Most published schemes focus on preventing you from recovering the key, instead of preventing you from figuring out how to perform the decryption process.  So, building a public-key cipher does not appear to be their motivation.

I don't know any really good answer to your question.  I know of two not-very-good answers:

One possible answer is that the code of the white-box cipher might be a lot larger than the key, and if a cracker wants to share it with others, they'll have to spend a lot more bandwidth sharing it than they would sharing the key.  However, this seems very weak and unconvincing.
Another possible answer is that white-box encodings are usually randomized: you can give a million people a randomized white-box implementation of AES decryption under key $K$ (the same key for everyone, but they each get a separately randomized white-box implementation).  Thus, if someone shares the code of their white-box decryptor, it uniquely identifies them.  However, in practice, this doesn't seem like a very effective defense against copyright infringement (prosecution is usually too expensive, and false identity too easy to forge).

So, I'm afraid I don't know of a strong practical motivation for white-box crypto.  Maybe someone else will have a better answer for you.


Skein state size advantages Skein is defined for three different internal state sizes: 256 bits, 512 bits, and 1024 bits – with Skein-512 as the “primary proposal”.

Is there any advantage, other than potential memory or speed performance reasons, when picking a state size different from 512? If there is, what would the advantage(s) be?

Is there any advantage – other than potential memory or speed performance reasons – of picking a state size different from 512? If, what would the advantage(s) be?

Yes.

With 256-bit state, the main advantages are memory use and hardware implementation area.

With 1024-bit state, a hardware implementation can be faster, but there are also security advantages.

The paper (pdf) claims the following, given state size $n$, output length $l$ and $m = \min\{n, l\}$. I've included only the ones where a 512-bit hash with 1024-bit state has a higher security claim than a 512-bit hash with a 512-bit state:

$r$-multicollision resistance: $\min\{2^{n/2}, 2^{(r-1)m/r}\}$.
Key recovery, forgery and distinguishing resistance (as MAC, PRF or in HMAC): $\min\{2^{n/2}, 2^{m}\}$.

None of these are likely to matter in practice unless Skein is broken, which is why they recommended 512-bit state. However, it is potentially useful if collisions are eventually found after all, and as a security buffer (same paper):

  Even if one day finding collisions
  turns out to be somehow feasible—as for MD5—exploiting that weakness for creating either multi-
  collisions or meaningful collisions should remain infeasible. This requires us to increase the internal
  state size, which is the core idea for the failure friendly “wide-pipe” design [77]. Thus, if we want
  a 256-bit hash function to be failure friendly, we need 512 bits of internal state, and if we want a
  failure-friendly 512-bit hash function, we need 1024 bits of internal state.

Finally, the 1024-bit variant has been defined with eight more rounds to counteract slower diffusion (80 as opposed to 72 rounds). This has the effect of making some other attacks break a smaller percentage of total rounds: e.g. the attack mentioned on page 67 breaks 25/72 rounds with 512-bit state but only 26/80 rounds with 1024-bit state.

(You could define an 80-round 512-bit variant that shared the above advantage, but that would likely be slower than the 1024-bit variant even in software, at least on fast 64-bit CPUs.)


Calculating power consumption by a cipher program When a block cipher program is run it consumes some power, how that can be calculated using software aspects? Is there any way to prove a cipher a lightweight cipher without using hardware parts?

If any program is run it consumes some power. There is no way to programmatically calculate the power consumption for a given cryptographic primitive, because this not only depend on how you implemented said primitive but also on the hardware (mostly CPU) used. The best thing you can have is to measure the time it took to calculate the primitive.


Reducing size of hash function If I have some data I hash with SHA256 as hash=SHA256(data) and then copy only the first 8 bytes of the hash instead of the whole 32 bytes. How easy is it to find a hash collision with different data? Is it $2^{64}$ or $2^{32}$?

And uf I need to reduce a hash of some data to a smaller size ($n$ bits) is there any way to ensure the search space $2^n$?

Even in a perfect world (the random oracle model) there's no way to ensure first-preimage and second-preimage resistane of more than $2^n$ and collision resistance of more than $2^{n/2}$. (Wie $n$ bytes as the output size of the hash function.) That's the maximum you will ever be able to archive.

Cutting off some bytes of the output of a secure hash algorithm doesn't hurt the security more than you have to expect. With an output of $8$ bytes ($n = 64$ bits) from (for example) SHA-256 you have first-preimage and second-preimage resistance of $2^{64}$ and collision resistance of $2^{32}$.


Pre-determined points in Shamir's secret I have distinct sets of pairs of values $(a_1, b_1), ..., (a_i, b_i)$. This set of pairs is ordered, and each $a_i$ and $b_i$ are related.  I want to share the $a_i$ values publicly. I do not want to share the $b_i$ with anyone.

I want the $b_i$ values to correspond to a single Shamir secret $S$ (Perhaps concatenate them, and encrypt with AES).

Is there any way to use Shamir's secret to make $a_i$ be the shared points D($i$, f($x_i$)=$a_i$) that corresponds to the Shamir secret , such that the $a_i$ are the shared points?

In other words, have the $a_i$ be the solution to the (k-1) degree polynomials?

My end goal is to "transmit" all $a_i$, but be able to use compute the $b_i$ after I know ALL of the $a_i$. I thought polynomial interpretation might be useful for this scenario.

If not Shamir's, is there any other method that may work?

Based on your question, it is not entirely clear exactly how the $x_i$ and $y_i$ values are coupled.

As I understand it, you want to make a situation where when someone has all $x_i$, they can recover all $y_i$. A simple way to do this would be to encrypt all the $y_i$ with a strong symmetric algorithm, e.g. AES-256-GCM, using a key $k$ and make the encrypted blob public. Then use Shamir's with the $x_i$ to protect the key $k$. Then, when all $x_i$ are assembled, the key $k$ can be recovered and the encrypted blob decrypted, rendering the $y_i$ values.

This may or may not be what you actually want, depending on your use case.


Cryptographically correct way to roll a giveaway winner I'm looking to create a fair selection of a giveaway winner, but I am versed enough in cryptography theory to determine if the below would hold up to public scrutiny if published on github.
The reason I am not using random.choice is for a "suspense" factor, where participants will be removed one by one until only one is left. I first shuffle the list, then pick random participant entries to remove.
Can someone who is well versed on this topic maybe give me some pointers or tell me I am doing it completely wrong?
from Cryptodome.Random import random

    def __init__(self) -> None:
        """Initialize object."""

        self._participants = {}

    def roll(self) -> List[str]:
        winners = []
        logs = []

        for participant, entries in self._participants.items():
            for _ in range(entries):
                winners.append(participant)

        random.shuffle(winners)
        while len(winners) > 1:
            remove_entry = random.randint(0, len(winners) -1)
            del winners[remove_entry]

        return logs

    def add(self, name: str, entries: int):
        """Add an entry."""
        self._participants[name] = entries

It looks mostly sound.
Why are you returning logs?
It is initialized to [] but never written to after that.
Are you aware of Crypto.Random.random.sample(population, k)?


2PC Private Set Intersection Optimized for asymmetrically sized sets I am researching some concepts of practical 2 party computation and was curious if anyone could point me to a research paper that is focused on private set intersection where one party has a very large set and the other has a comparatively small set.  Specifically, a user has a small set and the server has a large set.  Since the server will handle thousands or millions of requests, I am more concerned about the performance for the server.

The specific use case that I had in mind is contact discovery.  Meaning, a user wants to know who else is using a service but does not want to disclose their contacts to the server in plain text.  Ideally the server does not learn the outcome of the intersection.  At a minimum the server should only learn the size of the users contact list and the results of the intersection.

I found this paper that appears to be a breakthrough in performance but it's benchmarks are based on two sets of equal size.  Is there existing research on a PSI that is optimized for non-equal set size?

It is easy to observe that any secure protocol must touch every bit of both parties' inputs -- otherwise it's not secure.

However recent work has shown that you can amortize the protocol complexity over several runs, with state stored between the runs, so that not every execution will touch every bit.   See here for the paper.  It doesn't address set intersection directly, but since it covers a generic function it applies to your case.


Why we need pixel data encryption (perceptual encryption), not the complete file encryption (conventional encryption)? Why we need pixel data encryption (perceptual encryption), not the complete file encryption (conventional encryption)?

I am working on securing medical images, but I could not find the answer to this question. Is the complete encryption of the file (image pixel data+ metadata(header file)) better than encrypting only pixel data (distorted image) which preserve the header information (codec information) of the encrypted image?

In the literature, I found the following: Security mechanisms developed in the existing digital medical image systems are mostly based on the conventional encryption techniques such as DES, AES, IDEA, RSA. These mechanisms have been widely recognized as the standard multimedia encryption mechanisms. However, conventional mechanisms have obvious limitations on the multimedia data such as images shown in the following papers:

Socek D, Magliveras S, C’ulibrk D, Marques O, Kalva H, Furht B. Digital video encryption algorithms based on correlation-preserving permutations. EURASIP J Inform Security 2007.
Yoon, Ji Won, and Hyoungshick Kim. "An image encryption scheme with a pseudorandom permutation based on chaotic maps." Communications in Nonlinear Science and Numerical Simulation 15.12 (2010): 3998-4006.
Pareek, Narendra K., and Vinod Patidar. "Medical image protection using genetic algorithm operations." Soft Computing 20.2 (2016): 763-772.

The one "obvious limitation" of conventional encryption applied to multimedia data is that once encrypted, multimedia data no longer is compressible, or recognized as multimedia data (with metadata) by non-decrypting devices. This is solved by compressing before encryption, and accordingly decrypting before decompression and rendering. Confidentiality of multimedia data is a problem fully solved by conventional encryption.

There however might be practical reasons for perceptual encryption, including

We want the encrypted version to pass thru devices designed exclusively for multimedia data, including compressing perhaps with perceptually acceptable loss, or/and lacking error-correction.
We want a subset of the true data (e.g. metadata, sound but not image, a low-definition version..) to remain accessible by non-decrypting devices (which goes straight against the normal objective of encryption: that an adversary without key can not learn anything).
As an interesting specialization of the previous point, we might want that the non-encrypted low-definition version and the encrypted high-definition version share as much bandwidth as possible, which implies some perceptual model.


Is there any cryptographic scheme with block size more than 128 bit I am asking this question out of curiosity if there are any cryptographic algorithm that has a block length more that 128 bit. I am new to cryptography and I didn't know any. AES 128, 192, 256 all have same block length of 128 bit. Also if the answer is 'NO' then what can be the possible challenges of having larger block size. Thanks a lot in advanced for your help.

In the designs, smaller block size typically results in better implementations (though, the extent of this may vary on the paradigm and the instruction set, e.g. ARX ciphers). That is, encrypting two 64-bit blocks would be faster than encrypting one 128-bit block (with the same key size and estimated security). Roughly speaking, diffusion and confusion happen much faster.
However, 64-bit blocks have issues in modes which have birthday-bound attacks (see https://sweet32.info/ ). So 128-bit block size is the most "optimal" choice.


Cracking short ciphertexts made by Vigenère cipher I've encrypted a couple of 10 letters words from https://www.bestwordlist.com/10letterwords.htm  using a key of 10 characters. This is done using Vigenere cipher. Decrypt the cipher and give the key

Ciphertext: XRPEFGMHNL XDBEWUMHNL

How we can decipher when we have only 2n size ciphertext where n is the key size

Can you please explain how it can be done? Frequency analysis is not effective in this case as the ciphertext is really short...

You used the same key for both words so we can start with the obvious: both words start with the same letter and end with the same four letters.  We can process your initial word list, picking out sets of words that match this pattern.  Then just brute force each possible pair within each set until we find one or more pairs.  Work back from the first possible word of a pair to the key, and then forward to the encryption of the second possible word.  Check whether or not it matches "XDBEWUMHNL".

If there is more than one matching pair, then we would need more information.


Mechanism of PBKDF in encryption key generation with passphrase I want to roughly understand how the mechanism works of generating an encryption key from a passphrase, by which we encrypt a volume or file.

I'm familiar with public key encryption, the concept of a salt and the password hashing approach to password verification. A salt prevents attackers from precomputing a dictionary of derived keys.

I don't understand the main merits of deriving an encryption key from a passphrase, by which we then encrypt the data. From what I've read, it's key stretching- and strengthening that accounts for the main merit; a longer- or higher entropy key is more secure that the supposedly weak passphrase.

My first confusion arises from the random nature of the derived encryption key. Shouldn't this be a deterministic process? A passphrase should correspond to a certain unique hash, in order to verify it?

As a whole, I find this mechanism quite vague at the moment, and would love some elaboration on it. :)

Update

The salt is the only random component, which is passed with the encryption key. Hence, the key derivation key is deterministic, indeed.

The salt is indeed randomly generated. If the salt is random then it becomes impossible to pre-calculate the hash, thus making it impossible to build a lookup table hash -> password called a rainbow table. The salt only has to be unpredictable and unique, so the amount of security relying on the salt to be unique is relatively small.

Once the salt is known it is stored so that the password derivation is otherwise deterministic. This lets you regenerate the same hash for the same salt & password combination (and the same work factor or iteration count).

Key stretching (or rather, key strengthening) may need to be used within PBKDF's because the input key material is generally not strong enough to be used as a key. A password commonly has only around 50 bits of security or so. Key strengthening can add a few bits of security if the password isn't strong enough. This adds an amount of of work to an adversary per password tested.

Key strengthening makes it infeasible to perform a dictionary attack against a large amount of hashes in a database, as each password / salt combination should be tested, and each test would be a relatively large amount of work. This comes at a cost of course: each time the password hash is generated the work factor is also incurred on the user.

Note that the output size of the resulting key doesn't increase the amount of randomness of the input keying material. So just outputting a larger amount of bits won't increase the security. Outputting a 128 or 256 bit AES key won't increase the security if the input keying material has a lot less entropy than the input key.

A password should not correspond to a unique hash. A password / salt combination should, for a given password hash and work factor, correspond to a certain hash.

Otherwise you or anybody else could be using the same password for different purposes, and the calculated hash would be identical at the different locations. This leaks information about the password, possibly even leading to compromise of the hash, for instance if somebody would use the same password and finds out that the hash is repeated elsewhere.


DH Elliptic Curves: Why choose a fixed base point? I am having a first look at the TLS key exchange using Diffie Hellman and try to understand the Elliptic Curve variant of it.
So if a client and a server agree on using ECDH for key exchange and they use the secp256r1 curve, it seems like the base point G is given and they take it from the standard (04 6B17D1F2 E12C4247 F8BCE6E5 63A440F2 77037D81 2DEB33A0F4A13945 D898C296 4FE342E2 FE1A7F9B 8EE7EB4A 7C0F9E16 2BCE33576B315ECE CBB64068 37BF51F5)
From my understanding, i could use an arbitrary base point G and obtain a group which i can use for my key-exchange. Whats the advantage of using a fixed one?
Knowing the base point, wouldnt it be possible to create some kind of rainbow-table and thus crack some connections?
To me it seems more intuite that picking a new base point G every time would increase security.
But as far as i understand it, it's not whats done in TLS.
Can anyone tell why we pick a fixed base point instead of generating a new one for each key-exchange?

Knowing the base point, wouldnt it be possible to create some kind of rainbow-table and thus crack some connections?

If you could create such a rainbow table that allows you to compute discrete logs of random values to a base $G$ with nontrivial probability $p$, then you can solve the discrete log to any base (with work that takes an expected $O(1/p)$ time.
Here's how it works:

You're given the point $H$ and $J$, and want to compute the discrete log of $J$ to base have $H$, that is, the value $x$ s.t. $xH = J$

First step, compute the discrete log of $H$ to the base $G$, that is, the value $y$ s.t. $yG = H$.  What you do is pick random values $r$, compute $rH$, and use your rainbow table to find try to find the discrete log $y'$ of $rH$.  This takes an expected $1/p$ attempts (because $rH$ is a random point), and one we stumble on an $r$ that works, we have $y = r^{-1}y'$

Second step, use the same procedure to compute the discrete log $z$ of $J$ to the base $G$; again, this takes an expected $1/p$ attempts.

Third step is easy; $x = y^{-1}z$; we're done; that works because $yH=G$ hence $H = y^{-1}G$, and $J = zG$, hence $J = z(y^{-1})H$

On the other hand, for any curve we believe is secure, creating such a rainbow table is infeasible; if the order of the curve is $n$, then the creation would take at least $pn$ point multiplications; for all practical purposes, the standard discrete log algorithms that take $O(\sqrt{n})$ time are more feasible.

Knowing the base point, wouldnt it be possible to create some kind of rainbow-table and thus crack some connections?

In addition to having the same security, it turns out that, if we know $G$ in advance, we can compute $rG$ considerably faster; hence it makes the system faster for the honest parties, and just as secure.


Enigma message decode errors, and protocols to prevent them I was looking at some Enigma messages for some random reasons, and I wondered if there were ever issue pulling the correct words out the strings of characters of if there was a protocol for it.  For instance, here is a decoded message from here:

KRKRALLEXXFOLGENDESISTSOFORTBEKANNTZUGEBENXXICHHABEFOLGELNBEBEFEHLERH
ALTENXXJANSTERLEDESBISHERIGXNREICHSMARSCHALLSJGOERINGJSETZTDERFUEHRER
SIEYHVRRGRZSSADMIRALYALSSEINENNACHFOLGEREINXSCHRIFTLSCHEVOLLMACHTUNTE
RWEGSXABSOFORTSOLLENSIESAEMTLICHEMASSNAHMENVERFUEGENYDIESICHAUSDERGEG
ENWAERTIGENLAGEERGEBENXGEZXREICHSLEITEIKKTULPEKKJBORMANNJXXOBXDXMMMDU
RNHFKSTXKOMXADMXUUUBOOIEXKP

As one can easily see, the words are just chained together, and therefore, strange things can happen.  An example I came up with in English:

kidsexchange

Which could be "kids exchange" or "kid sex change".

Were any protocols in place to protect against a vague message in Enigma or any other plain text encryption system?

On page 5 of the document you linked in the comment it says the following in section 22:

  Satzzeichen

  Es werden ausgedrückt:

  Punkt durch x, Doppelpunkt durch xx, Fragezeichen durch ud, Komma durch y, Trennungsstrich, Bruchstrich, Bindestrich durch yy, Klammer durch kk. Satzzeichen sind im allgemeinen nicht entbehrlich, Schlusspunkt ist nicht einzusetzen. Da Satzzeichen im Interesse der Kürzung des Spruches gestrichen werden, ist im Wortlaut auf Unmissverständlichkeit sorgfältig zu prüfen.

(My) Translation to English:

  Punctuation

  To express are:

  Dot by x, colon by xx, question mark by ud, Comma by y, hyphen, line break, hyphen in words by yy, bracket by kk. Punctuation marks are generally not dispensable, the final dot is not to be used. The punctuation marks shall be deleted in the interest of shortening the sentence, the wording shall be carefully checked for unambiguity.

In section 28 there's also a short overview:

  \begin{array}{|c|c|}
\hline
j - j & Highlighting \ signs \\ \hline
x & Dot \\ \hline
y & Comma \\ \hline
ud & Question \ mark \\ \hline
xx & Colon \\ \hline
kk - kk & Bracket \\ \hline
qu & Square \\ \hline
grqu & Big \ square \\ \hline
fpkt & Time \\ \hline
sm & nautical \ mile \\ \hline
yy & Hyphen, \space Line \ break, \space Hyphen \ in \ words \\ \hline
\end{array}

So, as we can see, there's no special procedure to prevent vague messages. I would even argue that this could have been done intentionally, because the German language can have (very) long words and if you know the length of certain words it might be easier to decrypt a message.

Edit:

Handwritten text on pages 23 & 25:

??? = The parts I can't quite read

  Gestrichen ??? Ergänzende Anweisung [Befehlsnummer / Datum] gef.  / gez. [Unterschrift]

English:

  Discarded ??? Additional instruction [Number of command / Date] private / signed [Signature]

I guess there was a command released that these instructions are not to be followed as written in this book. The soldier then crossed these pages out and signed it. "gef." is probably an abbreviation for "gefreiter" and is a rank in the military that can be compared to the English rank of private or soldier.

It could also be that it's "gez." (instead of "gef.") which would mean "signed" followed by the soldier's signature.


What is Perceptual Encryption? What is "Perceptual Encryption", and where do we use it?

I came across it whilst reading a paper on ECC in a multimedia context, from which I quote:

  Hence, to achieve perceptual encryption, the higher-order biplanes were selected to be encrypted.

In addition to a formal definition, I would appreciate some examples of using it.

Perceptual encryption is a term used to describe various applications of encryption methods intended for audio, speech, image and video data.

The basic idea is that one performs encryption for multimedia content in a way that only a certain amount of "perceptual information" is touched by the encryption. It may be considered as intentionally degrading the quality of the multimedia content by means of encryption, whereas the part of the data that remains untouched can be processed by the respective decoder without requiring access to the encryption key. However, the full "perceptual information", i.e., the full quality multimedia data, can only be recovered when given access to the the encryption key.

For instance, one may use perceptual encryption to downgrade the quality for a free online preview of some movie and only if one pays for the content one obtains access to the encryption key and thus to the full quality content.

There are various freely available
articles describing different techniques for this type of encryption (just do a Google or Google Scholar search) and also some parts of books (you can find via Google Books), e.g.:

“Recent Advances in Multimedia Signal Processing and Communications”
 by Mislav Grgic, Kresimir Delac, Mohammed Ghanbari
or
“Perceptual Digital Imaging: Methods and Applications”
by Rastislav Lukac

and just search for "perceptual encryption". I am not sure if there is something like a single definition because there are various techniques for perceptual encryption, but you should find classifications in the linked books.