Problem with anonymously merging information from distributed sources Some Background:

There is an entity with an identifier and some information. The identifier of this entity is a string with a known scheme/pattern(Which means the total number of such possible entities is say 10-100 million).

Information about the entities is stored in two geographically distributed systems.
A third system is responsible for aggregating information about these entities.

And here is where the security comes into play - The third system should not know the actual identifiers of the entities and should not be able to derive the actual identifiers.

Existing proposed solution:

Both of the sites storing information about the entities decide upon a one way hashing algorithm to use, say 'PBKDF-2' and also securely communicate a long random salt that they will use while hashing. Both the sites do the one way hashing and send the hash as identifier to the third entity. The third entity can still merge the entities based on the hash but does not know the actual identifier.

Problem with the solution:

Since the set of all possible entity identifiers can be recreated(about 10-100 million), someone can execute a dictionary attack fairly easily. The salt makes it a bit more difficult but that's just some more additional overhead and does not provide a lot of comfort.

Alternatives proposed:

Use multiple hashing cycles with different salts
Use multiple hashing cycles with different salts and ciphers(scrypt, bcrypt and PBKDF-2)
Use mappings of identifiers to random strings (but that adds the overhead of always communicating the mappings between the two systems)

Please let me know if any of the three approaches listed above is acceptable. If there is some other more known/acceptable solution to scenarios like above(which I imagine must be plenty out there), I would gladly appreciate and accept them.

If you have a secret key (256-bits) shared between the two systems that see the entity identifiers, you can use HMAC-SHA256 to map entity identifiers to a random string.  Under the assumption that HMAC-SHA256 security is good (which is widely believed to be a reasonable one), this is just as secure as having generated a truly random mapping, but requires only communicating 256-bits instead of the full mapping.  If there are multiple rounds of this process of aggregation, you could use a different secret key or a different (public) nonce if it is not necessary for the aggregating system to know which entities are the same between rounds.

However, it sounds like the information associated with each entity will not be encrypted (since it needs to be processed in some fashion by the third system), and you therefore have to very carefully consider whether it may be possible to de-anonymize the entities based on their associated information.  There have been many cases of researchers de-anonymizing (http://en.wikipedia.org/wiki/De-anonymization) supposedly annoymized datasets.


RIBE Scheme Implementation - How to encrypt message This question is regarding "A Fully Secure Revocable ID-Based Encryption
in the Standard Model" - Tung-Tso TSAI, Yuh-Min TSENG, Tsu-Yang WU

The encryption method specifies part of the encryption process to be $\hat e(g_1, g_2)^r \cdot M$ where $g_1$ and $g_2$ are public parameters in cyclic group $G_1$, $\hat e$ is the pairing function and $M$ is the actual message.

My question is what this $\cdot$ operator actually implies for an implementation - is it taking chunks of the $M$ equal to the bit length of the result of $\hat e(g_1, g_2)^r$ and then adding* them together?

*My understanding, perhaps wrongly, is that the multiply operation for elliptic curve groups is  addition based on this

Given that the authors (as any sane person should¹) use multiplicative notation for all of the involved groups, "$\cdot$" simply represents the group operation in the target group $G_2$.

It does not seem to be explicitly specified as far as I can tell from skimming the paper, but this implies that the message space of the encryption scheme is exactly $G_2$, meaning that we always have $M\in G_2$. So there are no "chunks" involved.

If you want to encrypt a message directly with the scheme, this means that you will need to encode it as a $G_2$ element. If your message is too long for that, you will need to use one of the standard domain extension techniques, such as using the RIBE as a KEM in a hybrid encryption scheme.

¹This is a hill I'm willing to die on.


How can a good encryptor be made? I am making an encryptor software for a stream cipher with my own PRNG as a project for an inter school science competition. How can I make one so that after it generates the pseudo random nos. it can recognise each character and make the shifts. Can any one explain this either in Python or in a pseudo code algorithm.

I tried to make one myself, but I am not sure if it will work. This is how it works: first the programme starts counting and recording each character we enter, somewhat like a keylogger. It must beable to identify each of the characters exclusively. And then it does the shifting. If its good enough can  I use it as it is or must I make changes.

Say you have the value $n$ which is the size of the alphabet (i.e. the range of characters that make up your plaintext and ciphertext). And say $m = x \times n$ is the largest value you have that is not higher than $y$ where $y$ is the largest size produced by your random number generator.

For each character:

Take values from the random number generator until you have a value smaller than $m$, call this value $r_i$;
Calculate $s_i$ which is simply $r_i \bmod n$;
Calculate $p_i$ which is the location of the current character in your alphabet;
Calculate $c_i = (p_i + s_i) \bmod n$
Take the character at location $c_i$ of the alphabet and display.

To reverse:

Take values from the random number generator until you have a value smaller than $m$, call this value $r_i$;
Calculate $s_i$ which is simply $r_i \bmod n$;
Calculate $c_i$ which is the location of the current character in your alphabet (the first character in the alphabet is on position 0);
Calculate $p_i = (c_i - s_i) \bmod n$
Take the character at location $p_i$ of the alphabet and display.

In the above calculations I presume that the random number generator produces numbers from $0$ up to $y$ (so without $y$). The characters are in an alphabet where they have an index from $0$ up to $n$ (so without $n$).

If $y = n$ (the maximum value of the random number generator is the same as the size of the alphabet) then the scheme is of course simpler. You can just take the next value of the random number generator and call it $s_i$, skipping the first two steps.

Example implementation in Java (sorry, don't know Python that well):

import java.nio.charset.StandardCharsets;
import java.security.NoSuchAlgorithmException;
import java.security.SecureRandom;

public class StreamCryptUsingAlphabet {

    private String alphabet;
    private int n;
    private int y;
    private int m;

    private SecureRandom rng;

    public StreamCryptUsingAlphabet(String alphabet, int y) {
        this.alphabet = alphabet;
        this.n = alphabet.length();
        if (y < n) {
            throw new IllegalArgumentException("y is too small");
        }

        this.y = y;
        // % is the remainder operator, same as modulus for positive numbers
        this.m = y - y % n;
    }

    public void init(byte[] seed) {
        try {
            rng = SecureRandom.getInstance("SHA1PRNG");
        } catch (NoSuchAlgorithmException e) {
            throw new IllegalStateException("RNG not available");
        }
        rng.setSeed(seed);
    }

    private int nextS() {
        int r;
        do {
            r = rng.nextInt(y);
        } while (r >= m);
        return r % n;
    }

    public String encrypt(String plaintext) {
        String ciphertext = "";
        for (int i = 0; i < plaintext.length(); i++) {
            int p = indexInAlphabet(plaintext.charAt(i));
            int s = nextS();
            int c = (p + s) % n;
            ciphertext += characterInAlphabet(c);
        }
        return ciphertext;
    }

    public String decrypt(String ciphertext) {
        String plaintext = "";
        for (int i = 0; i < ciphertext.length(); i++) {
            int c = indexInAlphabet(ciphertext.charAt(i));
            int s = nextS();
            // Java's remainder requires me to add n first
            int p = (c - s + n) % n;
            plaintext += characterInAlphabet(p);
        }
        return plaintext;
    }

    private int indexInAlphabet(char c) {
        String s = String.valueOf(c);
        return alphabet.indexOf(s);
    }

    private char characterInAlphabet(int i) {
        return alphabet.charAt(i);
    }

    public static void main(String[] args) {
        byte[] key = "Khan".getBytes(StandardCharsets.US_ASCII);

        StreamCryptUsingAlphabet sc = new StreamCryptUsingAlphabet(
                "abcdefghijklmnopqrstuvwxyz", 80);

        sc.init(key);
        String ct = sc.encrypt("owlstead");

        sc.init("Khan".getBytes(StandardCharsets.US_ASCII));
        String pt = sc.decrypt(ct);
        System.out.println(pt);
    }
}

The next part explains what is usually done if a key stream which is a stream of pseudo random bits...

Normally, if you've generated a random key stream, then we use XOR to encrypt the plain text. For this the plaintext needs to be binary as well. So if the plaintext is actually text, we need to perform character encoding on it. Commonly used encodings are US ASCII and UTF-8. This will however result in a binary ciphertext, so if you want to represent it as a string, you can use base 64 encoding.

To decrypt you first base 64 decode the data you've received to retrieve the ciphertext. Then you decrypt, and afterwards you use character decoding to retrieve the text from the binary plaintext.

So the above is what is usually done within computers.


Calculating characters from the sum of ASCII pairs I have a series of messages (limited to only a-z and A-Z) that are encoded such that the sum is taken of every two ASCII values and concatenated. For instance, the message hello would be decomposed into the pairs he, ll, and o which would then become 104 + 101, 108 + 108, and 111 which finally is output as  205216111. Each pair is guaranteed to be 3 digits by zero-padding.

Is it possible to trivially decode this final number back into the plaintext? The words are in plain English and each word is capitalized. So far I have attempted to enumerate all possible permutations and identify words from a dictionary list but this has proven to be rather tedious with short messages alone.

It would be impossible i think. But if you consider evolving the encrypion system such as changing pair like  : "he","el","ll","lo","o" it would be way to easy to decrypt.


Cipher comparison chart/table? I'm more of a visual person, so a chart or table layout usually works best to help me "see".

I'm just trying to locate a resource that shows me where the various ciphers fall in relation to each other based on the various configurations they can be used.

Same for file hashing (using SHA-1 vs HMAC SHA-1, etc).

NOTE: As I cannot yet "comment" I am adding clarification here:

The challenge I am facing is that I am trying to appreciate the scope of what a single view of how the different ciphers compare to each other, but based on comments below I think I see why one does not exist (yet).

So I am trying to learn how best to compare and contrast the various ciphers to know which is best - for the sake of argument let's say for SFTP encryption for data in transit.

Maybe what I should be asking for is the process or method by which I should go about determining which cipher to use in any given situation.

Not trying to be difficult or vague, just a middle aged veteran trying to get better at understanding cyber as a new career is all (less than 3 years) and looking for ways to grock it. The text books haven't helped much and I find that usually someone on a forum can phrase it in such a way that I "get" it.

Thanks in advance.

Something like this (for AES)? If this is the kind of thing that you are looking for then I will expand it to include other ciphers, attributes, and hash algorithms.

--------------------------------------------------------
Symmetric Ciphers | Mode | IV Needed | Authenticated |
------------------+------+-----------+---------------+--
       AES        | CBC  |    yes    |      no       |
       AES        | CTR  |    yes    |      no       |
       AES        | CFB  |    yes    |      no       |
       AES        | OFB  |    yes    |      no       |
       AES        | ECB  |    no     |      no       |
       AES        | CCM  |    yes    |      yes      |
       AES        | GCM  |    yes    |      yes      |
       AES        | XTS  |    yes    |      no       |
       AES        | OCB  |    yes    |      yes      |
------------------+------------------+---------------+--


Curve25519 key structure In the paper regarding Curve25519, the set of public keys $q$ is $\{q : q\in \{ 0,1,2,...,2^{256} - 1\}\}$ and the set of private keys $n$ is $\{n : n\in 2^{254} + 8 \cdot \{ 0,1,2,...,2^{251} - 1\}\}$.
My main question is: Why is the structure of the public and private keys the way it is?
What I don't understand: In Theorem 2.1., $q$ is defined to be an element of $F_p$ and $q$ is also a parameter in the Curve25519 function: $Curve25519(n,q) = X_0(nQ) = s$ with $X_0 (Q) = q$. So why does the set of public keys not equal $\{q : q\in \{ 0,1,2,...,F_p - 1\}\}$?

From the same paper:

Use a fixed position for the leading 1 in the secret key;
Multiply the secret key by a small power of 2 to account for cofactors in the curve group and the twist group.

The first one is to make the scalar multiplication with always the same number of iterations of the loop, for constant-time reasons. The second one makes sure that the resulting point belongs to the prime order subgroup: if someone sends a point of small order, then the result of the scalar multiplication will be automatically $0$ since the secret key is a multiple of the cofactor (see page 8 of the paper).
For the public key, it is only that any value $q$ corresponds to a valid $x$-coordinate of a point that belongs either to the curve or its quadratic twist. Of course, you can take them only in $[0,2^{255}-20]$, but the main point is that it fits in $32$ bytes, and any $32$-byte values are valid.


Side Channel Attacks How to make cipher resist against Side channel Attacks. Specially Timing Attack, Cachet Timing Attach, Simple/ Differential Power Analysis.

Uptil now it seems all Standard Algorithms like AES, Cameillia etc have been successfully broken using side channel Attacks.

What are the design criteria to counter these?

Avoid:

Using secret data in table based lookups on machines that have a cache

The table is just a memoized function; Just compute the function explicitly each iteration instead of looking the answer up in a table

Accessing an array using indices whose values are supposed to be secret
Using functions that take a variable amount of time to compute on secret data

Do:

Use instructions that are generally implemented in a constant amount of time (at the hardware/gate level)

ADD, XOR, AND, shifts, and rotates are almost guaranteed to operate in a constant amount of time

Use functions that facilitate countermeasures more easily

Note that side channels target implementation details, and not the abstract algorithm. An implementer can still make choices that create vulnerabilities.

All that an algorithm designer can do is make the design straightforward to implement in a constant time manner. For example, AES can be implemented without a table lookup, but this tends to lower the overall throughput, potentially significantly.

There are apparently some tools for testing an implementation for weaknesses.


How to renew keys for a statically-encrypted database Preamble

Before I ask this question, please accept that I fully understand that 'rolling your own' is never a good idea, and that I am a relative n00b. The only reason I am doing this the way I am is that there are major constraints - I have no high-level crypto libraries (like, say, NaCl) available, and this will run on a mainframe. The crypto API I must use makes initialisation vectors my responsibility, but not keys -- I simply present a key token, and encryption and decryption are performed elsewhere in a 'leakproof' part of the system. So please don't criticise me for my environment, and please recognise that 'don't' do anything' is not an option.

Environment

A legacy database which will contain credit card numbers (PANs)
The PANs will be encrypted to protect against unauthorised online access by (eg) sysadmins and offline access to backups of the DB
A single key will be used for all PANs
Cipher will most likely be AES256 in CBC mode (the API may restrict me to ECB mode, but I'm trying to change that).
Each PAN will be encrypted with a different initialisation vector, which will be stored with the encrypted PAN
PANs are constantly being purged from the system. We can establish a maximum lifetime.
Storage space is limited -- I can pull an extra 16 bytes for the IV, but any more will be hard.
It is not practical to scan and update the database if I want to change the single key -- the DB runs at about 40,000 I/O per second for most of the 24-hour day and the system runs non-stop.

The Challenge

Find a way to be able to expire the single key and introduce a new one

The Proposal

Here's my current thinking, which I recognise has weak points.

Cryptographic keys are generated, and stored encrypted under a master key, in a completely separate component of the system, with its own access rules. Keys are identified for use by an alphanumeric key token.

At any time, I have two available keys, called 'A' and 'B'

For encryption:

Obtain a 16-byte cryptographically sound random number
Set the last bit on, signifying key A
Call the encryption API with the resulting IV, and key token A
Store the IV and the encrypted data

For decryption:

Test the last bit of the stored IV
If the bit is 1, select key Token A; if not, select key Token B
Call the decryption API with the IV and the selected key token

Now, when I need to expire the key, I simply need to change the encryption to set the last IV bit off and use key B. Decryption does not change.

Around six months later, when I have no more A IVs left in the system, I can swap again.

Each time I swap, I can generate a new key for encryption from this point on.

My questions are these:

If I cannot obtain a cryptographically sound random IV, just how bad would it be to use a high-resolution clock? The clock I have in mind is high-resolution (10 nanoseconds or better, and guaranteed not to repeat, as I won't be doing more than about 10k encryptions per second). I understand that the IV should not be predictable, but just how (precisely) predictable is such a clock?
I have to cater for the possibility that a PAN may get left over from a previous key which is no longer available; for example, a PAN which was encrypted with an earlier A key, but which fails to decrypt with the current A key. Assuming I don't want to increase the number of bits I 'steal' from the IV, is there a good, simple way to verify that the decryption is with correct key. I'd prefer to avoid the extra overhead of something more complex, like, say, an HMAC. Suggestions?
Any other comments or criticisms (within my constraints)?

Some remarks:

a 16 byte IV is required by CBC, but you may not require a 128 bit unique value for your protocol
CBC relies on an IV that is indistinguishable from random to an attacker, fixing bits in the IV is not a good idea
CBC requires a padding mechanism, unless you can use ciphertext stealing

Now a few calculations reveal that if you rely on the non-repeating counter, that you need an number of 8 bytes to have enough precision (584 years should be enough). Store just this number. You can create a good IV from this number by pre-pending the number with zero's and performing a single block encrypt (in the black box of course).

Now you have got 8 bytes left. I would suggest you use these for the key indicator (make it one byte instead of 1 bit, to avoid key management issues later on). You could use the additional 7 bytes for storing an authentication tag, so that nobody can change the ciphertext (and thus the PAN) unnoticed.

Finally note that the "default" padding mode for CBC mode of operation, PKCS#7 padding mode, will use 1 to 16 additional bytes of overhead. This is overhead you can sorely miss on size constrained systems, especially since it can be avoided without penalties on the security of the protocol. Look up ciphertext stealing, or go with another mode of operation that does not require padding.

This answer is provided as is. I remain convinced that you should hire a consultant that has experience protecting credit card related data.


The use of the term "sound" in cryptography In the context of interactive proof systems, we often see the term "sound" used. What is the sense of this word?

Look up the words sound/complete from logic. Complete roughly means that a method can solve every instance. Sound roughly means that the answer it gives is correct.

For example, assume that we have a program that's supposed to tell when an element belongs to a set. A sound program will only answer "yes" when the element actually belongs to the set. An unsound program might sometimes answer "yes" even though the element doesn't belong to the set. For some instances unsoundness might be OK, if it happens very rarely. An example is a primality tester, which might falsely claim with a very small probability that a composite number is prime.

This applies similarly to any decision procedure for example a program that has to declare whether $X$ is secure in some model $Y$.


How long does it take to brute force a Wordpress password? I'm not a cryptograhpy expert, I am a web developer trying to determine the origin of a Wordpress blog hack, and how likely it is that it was brute forced.

The administrator account username had been changed from the default "admin" and the password was, I believe, 8-10 characters comprising mixed case alphanumeric characters and symbols (the password has since been changed and extended in length).

Out of curiosity, I was looking at sites which supposedly estimate how long it would take to crack passwords. Supposedly:

Example Password: Vr%*zSR7mb

Length: 10 characters
Character Combinations: 77
Calculations Per Second: 4 billion
Possible Combinations: 7 quintillion

58 years to crack

But what does this mean in real world terms?

The site seemed to have been hacked by a rival company with a terrible website and poor English, which I would guess originates from Eastern Europe, Africa or Asia (basically, not even a real rival but someone attempting to make business in the same industry). All they did was post 2 entries of poorly written content promoting their own site.

If it takes 58 years to brute force the password, it's obviously not feasible that the password was hacked with a brute force according to that estimate.

How many calculations can one computer make?
What kind of computing power does the average hacker have access to?
How is a hacker able to leverage the use of multiple machines?

If a rival wanted to hack a website, how easy is it for someone with little experience to download and use tools to brute force a password? How easy is it to pay someone cheap money in a poorer country to perform the hack for you?

The bottom line here is I feel like a brute force attack on what is a fairly useless blog, in order to post fairly useless content which probably won't yield any return at all, is not very likely.

The problem is I don't know enough about the reality of brute force attacks, and how easy they are to perform. If it's something anyone can quickly and simply run, within a short amount of time, then it sounds possible that's what happened. Otherwise, I would like to be able to rule out a brute force attack and look at more likely options such as someone's machine being compromised with a key logger.

If the password was 8-10 random characters with alphanumerics and some symbols, a lower bound estimate of the entropy would be something like 48 bits (eight random base 64 characters). Coupled with WordPress' weak 8-round MD5, that's just over 50 bits of security. Not terribly secure.

A low-resource attacker like you assume could maybe crack it in a couple of weeks. If they had nothing else to do with their computer. Or they could buy some cloud computing resources to tackle the job. According to this blog post, an Amazon GPU instance (from a couple of years ago) could calculate about two billion MD5 hashes per second. With eight instances you'd have the search space covered in 24 hours. And that costs maybe a hundred bucks if that. (You could also do it quicker with more instances without a significant cost increase.)

However, if you assumed the high end of 10 characters out of all printable ASCII (95 possibilities), you would have a 65 bit strong password. Which would cost more like ten million dollars to brute force. So the actual entropy is rather important. If the initial password wasn't generated with a random number generator, its entropy was probably much less than something like the site you linked would predict.

While it is possible, brute forcing the password sounds like one of the less likely ways a WordPress blog would be compromised. An unpatched vulnerability in WordPress itself, some plugin, PHP, the SQL database or some other software seems more likely. Or in the case or a shared host, even a privilege escalation from another account.


Hash for use in embedded HMAC application I developed a GNSS logger (http://flysight.ca) which has become popular for scoring skydiving competitions. At the moment, there is little protection against competitors falsifying tracks, but I would like to change that.

The device uses an 8-bit AVR microcontroller. Memory and clock cycles are extremely limited. Because of the hardware design, the device has no warning when it is being turned off. This means it is not possible, e.g., to perform a computationally intensive signature only when the log file is closed.

The competition occurs over a few days. There is a central PC-based scoring system which is used to initialize and read data from the GNSS loggers.

Given these conditions, what I have in mind is the following:

The scoring system generates a unique random key at the start of the event.
Each GNSS logger is initialized with this key, which can be stored securely.
When a row is written to the log file, a cumulative signature is computed using an HMAC based on the key generated in (1).

Alas, even MD5 exceeds the resources I have available, so I am wondering if the modest security requirements (in particular, that signatures need only be secure for a few days) might allow me to use a faster hash function.

If you have a different idea, I'd love to hear that, too. Thanks so much for your help!

As cheaper alternatives to HMAC with modest security goals, consider:

SipHash—cheaper than MD5 because you don't have to pay for collision resistance; security is limited by the 64-bit output size
Maybe a Gimli-based PRF—Gimli is a new compact design
Derive a fresh key for each message, and use a one-time authenticator like a polynomial evaluation universal hash family such as Poly1305 or GHASH—extremely cheap to evaluate
Conceal a universal hash family output with a short-input, short-output PRF—faster than evaluating a generic long-input PRF

Of course, whether these actually provide security for your application depends on a lot more than the formal unforgeability properties of the cryptography.  No cryptography can prevent physical interference with the GNSS signals, for example!  With all of these systems, anyone who can verify log messages can also forge them—to separate the ability to verify from the ability to forge, you need public-key signatures, which are tremendously costlier.

To be clear: I don't suggest that you go out and invent new compositions of primitives right now along the lines I sketched above.  Rather, I suggest you spend effort now articulating your security model, so that you can focus your effort on implementing a design that confidently provides the security you're hoping for, rather than spend weeks micro-optimizing Poly1305 and SipHash for your AVR microcontroller, only to find that you actually need signatures, not authenticators.


Unicity-distance of Playfair Given the classical scheme Playfair, say, for 5*5 matrices, I am interested to determine its unicity-distance. How should one proceed to properly do that? I should appreciate it, if I could obtain a very terse recipe, listing the kind of computations such that I could effectively compute that value myself. (I am attempting to determine the unicity-distance of a suggested variant of Playfair.)

The unicity distance is defined to be the minimum number of ciphertext characters needed to have a unique significant decryption.
It answers the question 'if we try all the keys, how much ciphertext would we need to be sure our solution was the true solution?'.
The answer depends on the redundancy of the language in which the plaintext was written.

To find the unicity distance of a given cipher algorithm you calculate the ratio of the number of bits required to express the key divided by the redundacy of the language in question. Assuming the plaintext was written in English and that the Playfair Cipher is used to encipher it, we have that the unicity distance equals to 27 characters.

For a slightly more detailed discussion consider practicalcryptography.com


Shake 128/256 Output Length Restrictions Are there any restrictions on the specified output length when using shake-128 or shake-256, to the extent that certain output lengths should be avoided/or not used entirely?

Edit:

If someone decided to declare an output length equal to 1600 bits would there be a full block showing? If yes, is this of any concern?

Is there any issue with SHAKE-256(message,output_size_in_bits)=SHAKE-256(message,1600)

There is no standard limit on the output of SHAKE256.  No matter what output size you use, SHAKE256 advertises collision, preimage, and second-preimage resistance up to a 256-bit security level against a classical adversary, and up to a 128-bit security level against a quantum adversary, limited by the size of the output for small outputs (see Table 4 in Appendix A of the SHA-3 standard for details).

In particular, you are not limited to a 1600-bit output.  SHAKE256-$d$ does not simply reveal up to $d$ bits of the state and stop at 1600.  Rather, it reveals up to 1088 bits of the 1600-bit state, then permutes the state, and repeats until it has produced $d$ bits.  In spongy lexicon, it repeatedly squeezes up to 1088 bits at a time out of the sponge after absorbing the input.  It leaves 512 bits of the state secret at each iteration, far more than an adversary could ever hope to find even with a quantum computer.


How to prove that permutation and substitution ciphers satisfy H(X) = H(Y) in Shanon Entropy? I was not able to mathematically prove that all permutation and substitution ciphers satisfy H(X)=H(Y) if we say that Y is the set of ciphertexts while X is the corresponding set of plaintexts in Shanon Entropy?
More generally, how is it possible to mathematically prove that Shannon entropy does not change when applying any bijective function to X?

For any one to one encryption mapping, which these ciphers are assumed to be, say $E:{\cal M} \rightarrow {\cal C}$ under whatever key, we have:
$$
H(Y) =-\sum_{y \in {\cal C}}p(y)\log p(y)=
-\sum_{y \in {\cal C}} p(E^{-1}(y)) \log p(E^{-1}(y))
$$
which can be rewritten as
$$
H(Y)=-\sum_{x \in {\cal M}} p(\sigma(x)) \log p(\sigma(x))
$$
for some permutation $\sigma$ of the messages.
Note that the decryption mapping exists since $E$ is one to one.


The way to break Diffie-Hellman(small nonprime number) i am wondering how to break DH（small nonprime number）.
Let's say we don't know:

$a$: Alice's private key

$b$: Bob's private key

And we know:

$N$: nonprime number

$p$,$q$:  $N = p * q$ ($p$ and $q$ are prime number)

$g$: the base

$A$: Alice's public key   A = pow(g, a, N)

$B$: Bob's public key B = pow(g, b, N)

Now we want to calculate
shared_secret = pow(A, b, N) or shared_secret = pow(B, a, N)

If we want to find shared secret, we need to find private key $a$ or $b$ first.
We now have $g^{a} \equiv A \bmod pq$

And then
 ${x_p}$ with $g^{x_p} \equiv A \bmod p$
 ${x_q}$ with $g^{x_q} \equiv A \bmod q$

And then
$x_p \equiv x \bmod p-1$
$x_q \equiv x \bmod q-1$

I know we need to use the Chinese Reminder theorem after that, but i don't know how to start it. Any suggestions?

If we want to find shared secret, we need to find private key $a$ or $b$ first

No, for two reasons:

$a$ is not needed. Having found what the question notes $x_p$ and $x_q$, it is easy to compute the shared secret reduced modulo $p$, and modulo $q$, and then use the straight Chinese Reminder Theorem to find the shared secret. It tells when $p$ and $q$ are coprime (including, distinct primes as here and in RSA), and $0\le m<p\,q$, it holds
$$\begin{align}
&m_p=m\bmod p\quad\text{and}\quad m_q=m\bmod q\\
\iff&m=\left(\left(\left(q^{-1}\bmod p\right)\,(m_p-m_q)\right)\bmod p\right)q+m_q\end{align}$$
We can't find $a$ for certain, for there can be several equivalent $a$ (just as there are several equivalent private exponents $d$ in RSA). The best we can aim at is finding a working $a$, or best the smallest positive working $a$.

Hint if we want to find an $a$:

use Fermat's little theorem to define a modular equation involving only $a$, $x_p$ and $p$; and a similar one involving only $a$, $x_q$ and $q$. The question nearly does that, but extra parenthesis are required to fix the equations if we stick to proper notation as explained below, and the same quantity is designated by two different letters, creating confusion.
then solve for $a$ using a slight variant of the Chinese Reminder Theorem, applicable when the moduli are not coprime: we first divide one of the moduli by the Greated Common Divisor of the moduli, adjust the equation accordingly, and are back to the straight CRT.

Note: $u\equiv v\pmod n$ is a notation meaning that $n$ divides $u-v$, for some integer $n>0$. Whereas $v\bmod n$ without an opening parenthesis immediately before $\bmod$ is the uniquely defined integer $u$ with $0\le u<n$ and $u\equiv v\pmod n$. And $v^{-1}\bmod n$ is the uniquely defined integer $u$ with $0\le u<n$ and $u\,v\equiv1\pmod n$, assuming $\gcd(v,n)=1$. Baring parenthesis, operator $\bmod$ is understood to be evaluated after addition of what's on its left (stopping at the first $=$), but it is best to use explicit parenthesis when the modulus is a sum, as in $u\bmod(n-1)$. Also it is best to avoid $u\equiv v\bmod n$ and use \pmod instead of \bmod if  $u\equiv v\pmod n$ is meant, or use $u=v\bmod n$ if $0\le u<n$ is additionally implied.


The opponent possesses a string of ciphertext and has access to the encryption machinery as black box. What is the name of this attack? a quick example:

The encryption function:
y = E(x) = (13x + 9)(mod 27), when the letters A–Z are taken to be the numbers 0–25 and the Space (punctuation) is the number 26.

The opponent has the ciphertext y = "NZC"

For each letter, he will cipher it again and again until he gets the starting value.

I'll show the letter 'N': 'N' = 13

E(13) = 16

E(16) = 1

E(1) = 22

E(22) = 25

E(25) = 10

E(10) = 4

E(4) = 7

E(7) = 19

E(19) = 13

So, the opponent knows that the letter 'T' = 19 was encrypted to get 'N'

Same goes to 'Z' = 25, the letter 'W' = 22 was encrypted to get 'Z'

and for 'C' = 2, the letter 'O' = 14 was encrypted to get 'C'

From that, the opponent reveals the the plaintext: "TWO"

What is the name of this attack?

Thanks.

Actually, this specific attack against RSA is known as a 'cycling attack'; it works because RSA defines a permutation, and so by doing repeated encryptions a sufficient number of times, you'll always get back to where to started with eventually.

However, people have analyzed this attack, and shown that (with extremely high probability) the amount of work required by this attack (for a randomly chosen RSA modulus) takes more work than the known factorization methods.


Discrete logarithm algorithm for modulus power of 2 For those of you that don't know, the modular/discrete logarithm problem:

Calculate b given the others: $a^b≡c$ mod d

I am aware that there is no general algorithm for the discrete logarithm, making it intractable. ($O(n^2)$ and worse for n digits is generally considered intractable, though exponential is for sure)

Even though it isn't standard, for simplicity I'll label time complexities here with the first letter:

$M(n)$ for multiplication
$D(n)$ for division
$E(n)$ for exponentiation

I have two conditions to work with:

d is a power of 2, so $d=2^n$ for some known n (this is convenient because modulo, which is $D(n)$, can be replaced by bitwise AND, which is $O(n)$)
a and c are odd, if not primes, which they probably will be (this could be inferred, since a has to be odd to generate all other odd values, of which c is one)

Naive brute force search would then be $O(2^nE(n))$. The best any algorithm (that I've heard of) does is subexponential - still not polynomial, which is what I'm aiming for.

I have algorithms for some of the other (non-trivial) ones, namely:

(Modular) Division

$D(n)=O(n^2)$ or so
Tested with 65536-bit numbers (Python, took a few seconds)

(Modular) Exponentiation

$E(n)=O(M(n)n)$, in my case, $M(n)=O(n^2)$ so $E(n)=O(n^3)$
Tested with 16384-bit numbers (Python, took a few seconds)

Discrete logarithm has me stumped. Since modulus power of 2 allows usage of various bit twiddling hacks and other shortcuts that normally would never work, I think it can be done in polynomial time for this case. No idea how though.

Suppose multiplication of two $n$-bit integers can be done in $\mathrm M(n)$ operations.

Here's an $\mathcal O(n^2\cdot\mathrm M(n))$ algorithm for discrete logarithms modulo $2^n$, which is basically the Pohlig-Hellman algorithm adapted to this specific problem. (With naïve multiplication, the runtime therefore is in $\mathcal O(n^4)$.)

First, observe that the order of the group $(\mathbb Z/2^n)^\ast$ is $2^{n-1}$: An integer in $\{0,\dots,2^n-1\}$ is invertible modulo $2^n$ if and only if it is odd. However, that group is not cyclic; in fact, its exponent is $2^{n-2}$.
So, set $k:=n-2$ and suppose $a$ has order $2^k$ modulo $2^n$. This is the maximal order one can achieve modulo $2^n$; in particular, there are no "primitive roots" modulo $2^n$ for $n\geq3$. This also implies that $b$ can only be uniquely determined modulo $2^k$.

The algorithm essentially works by repeatedly "shifting out" the higher-valued bits in the exponent until there is only one unknown bit left, and then brute-forcing that bit. "Shifting out" bits can be done by raising $c$ to powers of two:
Suppose the binary expansion of $b$ is $b=\sum_{i=0}^{k-1}2^ib_i$. Then, since $a^{2^l}\equiv0\pmod{2^n}$ for all $l\geq k$,
$$
  c^{2^i}
  = (a^b)^{2^i}
  = a^{2^ib}
  = a^{\sum_{j=0}^{k-1}2^{i+j}b_j}
  \equiv a^{\sum_{j=0}^{k-1-i}2^{i+j}b_j}
  \pmod{2^n}
  \text,
$$
which only depends on the lower $k-i$ bits of $b$.

In particular, we can start out with $i=k-1$, which will give
$$
  c^{2^{k-1}} \equiv a^{2^{k-1}b_0}\pmod{2^n}\text,
$$
and we can easily determine $b_0$ from this by trying both values $0$ and $1$ and checking which one satisfies the congruence. (Since we know it must be either of them, plugging in only $0$ or $1$ and seeing if it matches is also sufficient.)

Subsequently using $i=k-2$ yields
$$
  c^{2^{k-2}} \equiv a^{2^{k-2}b_0+2^{k-1}b_1}\pmod{2^n}\text,
$$
and since we already know $b_0$, we can compute $b_1$ by trying both (or only one of the) possible values.

Repeating this process will obtain all bits of $b$.

As for the runtime: To determine a single bit, we need to compute $c^{2^i}\bmod2^n$ and $a^{\sum_{j=0}^{k-1-i}2^{i+j}b_j}\bmod2^n$. Using fast exponentiation, powers modulo $2^n$ can be computed in $\mathcal O(n\cdot\mathrm M(n))$ operations, hence as we need to figure out $k\in\mathcal O(n)$ bits, the total runtime is in $\mathcal O(n^2\cdot\mathrm M(n))$.

In practice, one can save a few operations by computing all the values $c^{2^i}\bmod n$ and $a^{2^i}\bmod n$ in advance using repeated squaring. However, this does not improve the asymptotic complexity, as one still needs $\mathcal O(n)$ multiplications per bit of $b$ to combine the cached values of $a^{2^i}\bmod n$ according to the concrete known bits of $b$.


Calculate the complexity of HKDF with a 96bit salt and a 128bit key? I have a 128 bit Pre-Shared Key. I don't want to use it directly. I'd much rather generated a session key with HKDF(PSK, SALT) = SESSIONKEY.

I'm however under strict size limits for packet size. So I'm looking at the option of a 12 byte (96 bit) salt.

Does this significantly weaken my 128 bit PSK down to 96 bit? What is the true complexity of the resulting SESSIONKEY? I don't think I get to combine them into something greater than 128bit because the salt (derivation seed) will be transmitted in the clear for the other side to use.

Does this significantly weaken my 128 bit PSK down to 96 bit? What is the true complexity of the resulting SESSIONKEY?

No it doesn't, key strength remains the same. It's remains at 128 bits. HKDF can even be run without a salt (although it's security proof strongly recommends you to use one).

However, if you use it many times, you might have a higher chance that a SESSIONKEY repeats. How that impacts security depends on the cipher mode and IV usage though:

If you use a 16 byte random IV and you'd use, say, AES-EAX then you'd still be as secure. If you'd use deterministic encryption and the each message differs then you'd still be as secure.
If the IV is static and you'd be using GCM then you're more likely to be in trouble and all security may be lost.

So the nasty answer is that we cannot really tell, it depends on the use case and threat vectors.


Database and End-to-End Encryption I'm currently designing a mobile/desktop application to synchronize some messages or notes. I'm searching for a way to secure it and to avoid letting the server be able to read the messages.

My goal is to have a client which encrypts a message on the client side, sending it to the server which stores it to the database. Then, if another client on the same account is connected, it will receive the encrypted message, decrypt it and store it in its local cache.

I can't just use one of the standard end-to-end encryption methods because I don't want to have a different key each time I use the application. I want to be able to store the messages in the database.

Another constraint is that I don't want the user to manually manage the keys. I just want a password for the account.

So, a solution I have imagined is to use an asymmetric algorithm like RSA and a symmetric one like Blowfish or CAST. I generate an RSA key pair when the user creates an account, encrypt it with CAST and the user's password as the key, and store the result locally on the phone. Then, the messages are encrypted with the public RSA key, sent to server and stored in the database. To be able to decrypt messages on another client (like on a PC, for example), I just send the encrypted key pair from the phone to the server that sent it back to the new client. The new client can now decrypt the RSA key pair with the user password and decrypt messages stored in the database.

Since I'm pretty new to all this stuff, I don't know whether this is a good idea, or whether there is a better way to do it.

You seem to be inventing your own ad-hoc protocol, without authenticated encryption, and using old algorithms with known security weaknesses such as small block size.

I strongly suggest you use a high level modern library such as libsodium and use its crypto_box function for authenticated encryption, as well as Argon for password key derivation to protect the private keys. This will supply fast modern authenticated encryption (which your proposed solution would not provide). There are libsodium "wrappers" for most popular high-level programming languages.

It is much more difficult to go wrong using a known-good, high-level toolbox such as libsodium. With out using something more pre-built, you will have to decide on many security-critical details which are easy to get wrong such as: symmetric modes, authentication mechanisms for your cipher text, padding, key generation, nonce generation and re-use protection, key-wrapping, padding, side-channel resistance, and encoding.

You will still have to compose a few high-level building blocks for your application with something like libsodium, but it won't be nearly as difficult or error-prone.


Digital sign HTML form data before sending it to server? I need to encrypt and digital sign an html form that contains sensitive data. The legal need is that the user can't deny that he filled the form and the data sent was not altered.

I was thinking to generate server side RSA public key and private key, and I will store the public key in  the database with a technical id.

Then I send the private key to the html page (ajax call or at load). The Javascript code will encrypt the form before sending it. The Javascript will send the encrypted data and the public key id so i can retrieve it server side and can decrypt it.

Is it the good approach, or do you see any security issues?

Is it the good approach?

No, it is not. You say you want to do this for legal reasons. If your server knows the private key (as it does in this case), the server or anyone with access to the server will also have access to the private key and can therefore sign any form they want. Therefore, your proposal does not meet your goals.


Type of values that can be accumulated in bilinear map (multiplicative) accumulator reg Is there any restriction that  the members to be accumulated in bilinear map (multiplicative) accumulator need to be relatively prime to $P$, where $P$ is the order of the group.

If the group order $P$ is prime, then you can accumulate any integer in $[0,P)$.


Simulation based proofs, what am I missing? In the example given by in the top answer of Simulation based proofs: Simple examples claims that this is insecure the semi-honest, and I need assistance in where I am failing to reason why that this is true.

By definition (at least put simply to my understanding), a protocol is secure under this simulation based definition if the output views of the simulator and the adversary are computationally indistinguishable.

In the case where $x_2$ is 0, the output of the computation is always 0. And in this case, the simulator has to guess the value of $x_1$, namely it can take either value of 0 or 1. In the case that the simulator guesses $x_1$ correctly, it's obvious that these views are identical. However, what I fail to understand is in the case the simulator guesses $x_1$ wrong, how are these views distinguishable? As far as I can see, no distinguisher should be able to tell if the view of $(1,0,0)$ with the message $1$ from $P_1$ was the real/ideal interaction, or if $(0,0,0)$ with the message $0$ from $P_1$ was the real/ideal interaction.

Basically, what you are missing is that the real view for a given input pair must be indistinguishable from the simulated view for the same input pair.

Remember that, put simply, the requirement is that the view of each party can be simulated based only on its input and output. So, in the case of $P_2$, for each pair of input bits the simulator is given the input $y$ of $P_2$ and the output bit $x \wedge y$, where $x$ is the input bit of $P_1$, and must simulate the view $(y,x)$ of $P_2$ (input and received message). Now, consider the two cases where $y = 0$. In both those cases, the simulator has input $(0,0)$, so its output in both cases will be the same. But the real view is not the same ($x$ can be $0$ or $1$), so the simulator, no matter what it does, can't possibly simulate both views.

Concretely, consider for example the following simulator $S_2$. On input $(y,w)$ (where $w = x \wedge y$),

if $y = 0$, chose $b \gets \{0,1\}$ randomly and output $(0,b)$;
if $y = 1$, output $(1,w)$.

Recall also that for all input pairs $(x,y)$, we have $\mathsf{view}_2(x,y) = (y,x)$. Consider now the following distinguisher $D$. $D$ gets as input a pair of bits $(a,b)$; if $(a,b) = (0,0)$, $D$ outputs $1$, and otherwise $D$ outputs $0$. The question is, if the inputs to the parties are $(0,0)$, what does $D$ output if we give it a real vs. simulated view of $P_2$? A real view will be $(0,0)$, so $D$ will always output $1$. A simulated view will be $(0,0)$ or $(0,1)$ each with probability $1/2$, so $D$ will output $1$ with probaility only $1/2$, hence the two probability ensembles (real and simulated views) are distinguishable.


Prove that pseudorandom generator is a one way function Suppose the following PRG $G : \{0,1\}^n \rightarrow  \{0,1\}^{n +l}$, I want to prove that $G$ is one way function (and not building one), for:

$l = \omega (\log n)$
$l = 1$

For $l = \log n$, suppose that $G$ isn't OWF, so there's an inverter $A$ which succeeds w.p. $\geq 1/p(n)$, trying to build a distinguisher $B$ from inverter $A$ to $G$, I can do as follows:

$B(y)$ assigns 1 to each input successfully inverted. So $\Pr[B(y) = 1 : y = f(x) = G(x)] \geq 1/p(n)$, and for random input $\Pr[B(U_{n + \log n})] \geq 2^{n}/2^{\log n + n}$. All in all, the distinguisher succeeds w.p.

$$|\Pr[B(y) = 1 : y = f(x) = G(x)] - \Pr[B(U_{n + \log n})]| \geq 1/n - 1/p(n) \geq 1/2n$$

But for $l=1$, I get a bound of $1/4$ ($1/2 -1/p(n) \geq 1/4$)... It doesn't feel correct, but does (?) follow the definition of distinguisher for PRGs.

What am I missing?

$$l = \log n: \Pr[B(Un+\log n)]≥2^n/2^{n+\log n} \cdot 1/p(n)$$
Since even if the input of $B$ is from the image of $G$, the probability to invert it is $1/p(n)$.
So you need to correct this case and it will help you with $l = 1$.


Encrypting 8 times with 8-bit key beneficial? I was trying to understand cryptography from the book Information Security by Mark Stamp and I am confused by something.

  Suppose that Alice has a secure block cipher, but the cipher only uses
  an 8-bit key. To make this cipher "more secure," Alice generates a
  random 64-bit key K, and iterates the cipher eight times, that is, she
  encrypts the plaintext P according to the rule

  $$C = E(E(E(E(E(E(E(E(P, K_0), K_1), K_2), K_3), K_4), K_5), K_6), K_7)$$

  where $K_0,...,K_7$  are the bytes of the 64-bit key $K$.

  Assuming known plaintext is available, how much work is required
  to determine the key $K_1$?
  Assuming a ciphertext-only attack, how much work is required to
  break this encryption scheme?

Here I believe that the author is trying to explain the meet in the middle attack, but how does this attribute to it? As far as I have understood things, by using a MIM attack, the answer will be $2^7$ for each block do is $2^7*8$, and ciphertext I believe there are no ciphertext shortcuts so is should be $2^{64}$?

Am I right or I am thinking in the wrong direction?

Is encrypting 8 times with 8-bit key beneficial?

For a meet-in-the-middle attack with known plaintext, you break all $K_i$ at the same time. The goal is to split the work into multiple sides, trading off some exponential work for some exponential space and some linear work.

Split the encryption and decryption sides evenly. You need $(2^8)^4 \times 2 = 2^{33}$ block cipher calls, because you need 4 layers of $2^8$ encryption calls and 4 layers of $2^8$ decryption calls. (The work for both sides combines linearly, rather than exponentially, which is where the power of MITM lies.) When a match in the middle is found (the more known plaintext the better, since false positives are possible), you retrieve the key that was used to generate the mid-state matches from both sides, combine the two halves, and get the full $K$.

There's a shortcut for that analysis: Double-layering a cipher using different keys attempts to build a key of length $2n$, but an MITM attack can reduce it back to an effective key length of $n+1$. So for the question at hand, pretend we actually had a cipher with a 32-bit key (it iterates the original cipher 4 times internally) and that hypothetical cipher itself was iterated twice. We take the hypothetical 32-bit key, double it to a 64-bit key, then MITM reduces it to a 33-bit key.

A work factor of $2^{33}$ to recover all of $K$ is much less than the attempted strength of $2^{64}$. At almost half the length, it's a break.

(Side note: Splitting the work in the middle of the layers is the most efficient, but, for fun, you could split it elsewhere. Consider doing the MITM split at, say, $K_1$ and $K_2$. It would require $(2^8)^6 + (2^8)^2 = 2^{48} + 2^{16}$ calls to the block cipher, as you need 6 layers of $2^8$ encryptions, and 2 layers of $2^8$ decryptions. To conceptualize how MITM works, it may help to think of brute-force as a special-case MITM with 0 rounds on one of the sides, resulting in $(2^8)^8 + 0 = 2^{64}$ work, which is the full key space.)

That uses just one encryption/decryption split, also known as one-dimensional MITM. For ciphers layered more than twice, there are multi-dimensional MITM attacks, which apply an encryption and decryption split at each layer. It's more complicated, but it enhances the attack even more.


Commitment which allows negative proof I need to create a commitment to a value X such that I can provide either proof that the commitment is to X or proof that the commitment is not to some other given value Y != X.

If I use a simple hash with a blinding factor

C = H(BF | X)

I can provide proof by revealing BF,X and "negative proof" that X!=Y by revealing BF, but this would defeat the purpose of the blinding factor, making X guessable as it has a small domain.

Is there some other way to create such commitment?

The immediately obvious idea is to use Pedersen commitments.  The idea here is that, in some group where the DLog problem is hard, we have two generators of unknown relation $g, h$, and a commitment to $x$ is the value $g^x h^r$ (for some random $r$).

To reveal the commitment is easy; you just give the values $x, r$ (and the verifier can check).

To prove that a value $x'$ is not the committed value to a commitment $g^x h^r$, the prover selects random values $s, t$, and publishes the value $h^t$, along with a zero knowledge proof that he knows the dlog of $h^t$ to the base $h$ (a standard cut-and-choose proof works).  Then, both sides compute $g^{-x'} h^t (g^x h^r) = g^{x - x'} h^{r+t}$, which we will call $j$.  Now, the prover computes $j^s = g^{s(x-x')} h^{s(r+t)}$, and outputs that, along with the values $s(x-x')$, $s(r+t)$.  He also outputs a zero knowledge proof that he knows the discrete log of $j^s$ to the base $j$.

The verifier can check that $s(x-x') \ne 0$, that the values $s(x-x')$, $s(r+t)$ make up the outputted value $j^s$, and that the proofs of knowledge of $s, t$ are valid.

Then, the verifier knows that the prover knows the value $s(x - x')$ and that it's not zero, hence $x - x' \ne 0$ and so whatever $x$ is, it ain't $x'$

There are also standard range techniques that would also work; I believe that this is more straight-forward...


Is there an asymmetric encryption that works in a reverse way of RSA (encrypt using private key and decrypt using public key)? I'm writing a program that needs to receive an encrypted message from the server and decrypt it on the client.

The problem in this case, is to prevent the client from being able to re-transmit messages encrypted with same key. RSA is designed to use the public key for encryption and private key for decryption. So if a client can decrypt a message (using private key), the client is also able to encrypt another message using it.

I know that it is possible to sign a hashed message using private key and then verify it using public key. But my scenario is not a digital signature problem. I just need a "read only" encryption.

Is it possible to do this using RSA or any other asymmetric encryption algorithm?

UPDATE:

I know that RSA cannot encrypt data longer than it's key size and this is the reason for hashing data to a fixed length data. My supplemental question is: Can we convert a long message to a few small and fixed length blocks and use the same algorithm used in signing and verification to do encryption and decryption?

The need you describe is called DRM, and to implement it you don't need asymmetric encryption - DRM typically uses symmetric encryption where the server encrypts the data using a symmetric key specific to the receiving client.

All that said, once the protected data is decrypted there is no technical way to prevent it from re-distribution. You can, at most, use legal means to deter unauthorized re-distribution. That holds true even if you were a multi-billion $$$ corporation such as Sony or other media behemoth.

The closest you can get to DRM protection on the technical side is to have the server transmit the data only after the client proves that it is genuine, and to have that in turn possible (to some extent) only if the client is hardware-based and non-rootable - e.g., a book reader, set-top box, game console, etc., depending on the media type.


How calculation over $GF(2^2)$ is executed? I was unable to understand the calculation procedure given for $GF(2^m)^2$ in the follwing pdf: http://faculty.washington.edu/manisoma/ee540/EE540finite.pdf

In page 21 of the pdf, "Inversion over Composite Field $GF((2^m)^2)$" is introduced using irreducible polynomial "$x^2+x+\phi$".
(The "$\phi$" represents a constant binary {10}.)

However, I can not understand some calculation procedures such as "$a_0\ \texttt{&}\ (a_0+a_1)$" and "$\phi\ \texttt{&}\ a_1$".

What is the calculation procedure in concrete digits ?

Summary: Addition is bit-wise xor. Multiplication (which you denote as $\&$), is polynomial multiplication in the field $\mathbb{F}_{2^m}$, i.e. modulo some irreducible polynomial of degree $m$ over $\mathbb{F}_2$.

We construct $\mathbb{F}_{(2^m)^2}$ in such a way that it contains an element $x$ such that $P(x)=0$. Since this is a polynomial of degree 2, and it splits in $\mathbb{F}_{(2^m)^2}$, there exist also a $y\in\mathbb{F}_{(2^m)^2}$ such that
$$X^2+X+\phi=(X-x)(X-y),$$
where $P(X)=X^2+X+\phi$ is a polynomial in $\mathbb{F}_{2^m}[X]$.

It follows that $xy=\phi$ and $x+y=-1$, hence $y=\frac{\phi}{x}$ and $y=-x-1$. Therefore
\begin{align}
(a_0+a_1x)^{-1} &= (a_0+a_1x)^{-1}(a_0+a_1y)^{-1}(a_0+a_1y) \\
                &= (a_0^2+a_0a_1y+a_0a_1x+a_1^2xy)^{-1}(a_0+a_1y) \\
                &= (a_0^2-a_0a_1+a_1^2\phi)^{-1}(a_0+a_1y) \\
                &= (a_0(a_0-a_1)+a_1^2\phi)^{-1}(a_0-a_1x-a_1) \\
                &= (a_0(a_0+a_1)+a_1^2\phi)^{-1}(a_0+a_1+a_1x). \\
\end{align}
This is how you arrive at the inverse.

Now note that $a_0,a_1,\phi\in\mathbb{F}_{2^m}$, so all operations to compute $(a_0(a_0+a_1)+a_1^2\phi)$ are in the field $\mathbb{F}_{2^m}$. In other words, addition is just bit-wise xor. Multiplication is polynomial multiplication modulo an irreducible polynomial over $\mathbb{F}_2$ of degree $m$.

Moreover, this means that the inversion $(a_0(a_0+a_1)+a_1^2\phi)^{-1}$ is also computed in the field $\mathbb{F}_{2^m}$, hence we have reduced inversion in $\mathbb{F}_{(2^m)^2}$ to an inversion in $\mathbb{F}_{2^m}$ plus some cheap stuff.


How does the encryption/decryption process work? I am not referring here to the process of Public Key exchange, but rather the process of encryption or decryption itself after the Public/Private keys have been generated. For instance, using Diffie-Hellman algorithm we ended up getting both Public and Private Keys of size 512 Bytes. How are we supposed then to use the Public Key to encrypt a given plain text message "Hello World!" and the Private Key to decrypt it?

Diffie-Hellman does not generate public and private keys. It generates an agreed number in such a way that:

An eavesdropper cannot work out what number has been agreed upon.
A man in the middle can either know the agreed number which party $A$ is using and the agreed number which party $B$ is using, or ensure that the agreed number which party $A$ is using is the same as the agreed number which party $B$ is using, but not both.

No encryption is involved in Diffie-Hellman and Diffie-Hellman does not generate encryption keys.

Of course one of the main uses of an agreed number would be to do encryption with it – or rather, with a key derived from it. But that is nothing to do with Diffie-Hellman per se.

To that extent, your question is "How, given a number, do I turn it into an encryption key and use it?" – to which the answer is, "In any way you like".


Additive Differential of XOR I'm studying about Additive differential of XOR

I saw two papers that are "H.Lipmaa et al., On the Additive Differential Probability of Exclusive-or" and "V.Velichkov et al., The Additive Differential Probability of ARX"

In this two paper, Limaa et al. and Velichkov et al. compute the probability of additive differential of xor in similar way.

But there is one difference between them.

That is matrix $A_i$ is different.

For example $A_{000}$ in first paper is  $A_{000}=\begin{pmatrix}
4& 0& 0& 1& 0& 1& 1& 0
\\0& 0& 0& 1& 0& 1& 0& 0
\\ \vdots & &  & \cdots & \cdots  & & & \vdots
\\ 0& 0& 0& 0& 0& 0& 0& 0
 \end{pmatrix}$

and $A_{000}$ in second paper is  $A_{000}=\begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0
\\0& 1& 0& 0& 0& 0& 0 & 0
\\ \vdots & &  & \cdots & \cdots  & & & \vdots
\\ 0& 0& 0& 0& 0& 0& 0& 1
 \end{pmatrix}$

I hope someone can tell me why there exists a difference.

The OP has provided the answer in a comment.

"In the second paper(V.Velichkov et al., The Additive Differential Probability of ARX), the table 2's order is not same as the original order.

For example, $S[i] =0$ when $(s_1[i],s_2[i],s_3[i])=(0,0,-1)$. So, there exists a difference.


public key certificate on TLS/SSL Currently I am working on a public key certificate. I got a question: Why is a public key certificate needed for TLS/SSL? Wouldn't TLS/SSL itself is enough? What is the role of the certificate?

The certificate makes sure that whoever you're talking to is who they claim they are. With TLS/SSL without certs you wouldn't notice if you're communicating with an impostor over an encrypted channel instead of whoever you're expecting to communicate with. This leads to so called man-in-the-middle attacks. You really should read this, if you're going to use TLS:

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


Preimage of SHA512 with a known suffix Is it possible to figure out what $arg1 is if I know both $arg2 and $arg3 in addition to $hash?

$hash = hash('sha512', $arg1 . $arg2 . $arg3);

Assuming that . represents concatenation, no, except in the specific case that $arg1 is the empty string.  You're trying to perform a preimage attack, which is one of the things that SHA512 is designed to be resistant to.

Further, knowing $arg2 and $arg3 does not let you speed up a brute-force attack on $arg1, because for each candidate value for $arg1, $arg2 and $arg3 will modify the checksum differently.  (If you knew $arg1 and $arg2 and were looking for $arg3, you could precompute the partial checksum of the first two values as the starting point for each try at finding $arg3)


Is it possible to insert a key derivation function when using EAX? I am currently investigating use of EAX mode for a dedicated application and following useful clarifications received from my previous post , to consider according to my applicable input security requirements (separate keys for encryption and authentication) either :

the  Baseline solution where EAX is used in strict respect of its
specification and so with one unique key K
or an eventual (only if it has a sense) alternate solution with insertion
before EAX, of a key derivation function allowing to generate from
the unique input key K, one KA key for OMAC functions and one KE
key for CTR function

Can such alternate solution be envisaged or may it violate EAX mode specification and associated security proof ?

As noted in archie's answer to your earlier question, the EAX paper first defines a generic encrypt-then-MAC composition method called EAX2, with separate keys for the encryption and MAC components, and proves its security (Appendix C).  It then defines EAX as EAX2 instantiated with CTR mode and OMAC, and with the same key used for both components, and then uses an additional result about OMAC (Appendix D) to prove that this composition remains secure even with the key reuse (Appendix E).

Anyway, what all this amounts to is that if you take EAX mode and modify it so that the OMAC key is independent from the CTR mode key, and make no other changes, then what you get is an instance of EAX2 (with CTR mode as the encryption method and OMAC as the PRF).  If you trust the proof that EAX is secure, then, by the same argument, you should also trust the sub-proof that shows EAX2 to be secure.

That said, there do exist some potential disadvantages to this change.  For example, even though the security proof of EAX2 is essentially a part of the security proof of EAX, that does not necessarily mean that authorities that have certified EAX to be secure necessarily accept EAX2 as certified as well.  Also, more practically, verifying the correctness of your implementation of EAX2 might be more difficult, since AFAIK there's no standard set of test vectors available for EAX2.

All in all, if at all possible, I'd recommend sticking with EAX and using an existing, known-to-be-good implementation of it.  However, if you do need to use generic encrypt-them-MAC composition with separately derived keys for regulatory or other reasons, EAX2 is a pretty good way to implement it.


What is meant by - computational complexity $2^x$? Recently Bi-clique Cryptanalysis allowed to obtain following results on full AES ES that claim to have

The first key recovery attack on the full AES-128 with computational
complexity $2^{126.1}$
The first key recovery attack on the full AES-192 with computational complexity $2^{189.7}$
The first key recovery attack on the full AES-256 with computational complexity $2^{254.4}$

What is meant by $2^{126.1}, 2^{189.7}, 2^{254.4}, ...$ and if I happen to create a crypto algorithm on my own (which I know is not a good idea) how can I measure it's strength?

The "many attacks" you're referring to, don't exist.
There are two main attacks on AES. One needs related keys and drops security level signifantly (to about the half of the bits).
You're referring to the other one, the biclique attack on AES.

This is the first attack on the full-rounded version of AES (without related keys) that performs better than brute-force. It weakens AES, but only by a mere 2 bits, which is negligible for practical applications.

  What is meant by $2^{126.1},...$?

These numbers identify the workload the attack requires. You need to perform $2^{126.1}$ "steps" to recover the AES-128 key. One step usually means one call to AES-128. The same applies for the other numbers and AES versions.

EDIT: The following paragraph was obsoleted by an edit to the question. The paragraph after this one now fully applies.

  How can I measure it's [my algorithm's] complexity?

First, I think you're using the wrong term. The complexity of an algorithm usually means the run-time the algorithm needs to be performed. (like ~3.5 cycles for AES with AES-NI). The complexity can aswell mean "how complex is it to describe the algorithm", which is usually measured in lines of code.

But from the context you give I assume you mean "How can I measure my algorithm's strength?".
The strength of an algorithm usually is equal to the complexity of the best known attack. So initially this is brute-force making an 128-bit keyed algorithm having a stength of 128-bit or $2^{128}$. Usually attacks sooner or later lower this boundary, whereas usually the impact on homebrew algorithms is rather severe against the moderate advances in the cryptanalysis against AES.


What is “Fast Prime”? In this note, the manufacturer of a RSA key generation gizmo vulnerable to the new ROCA attack (see second section) explains that

  it is common practice to employ acceleration algorithms in order to generate key pairs, especially if time resources are sparse. (We) also utilizes such an acceleration algorithm in time-restricted cases, called “Fast Prime”. This algorithm is software-based..

  The foundations of “Fast Prime” date back to the year 2000. Its use started around ten years later after thorough reviews. As a sub-part of one cryptographic software library which is supplied to customers as a basis for their own development, this software function was certified by the BSI (Federal Office for Information Security) in Germany. No mathematical weaknesses were known, nor have been discovered during the certification processes.

What is “Fast Prime” and where was it suggested?

The following (likely) tells a property of primes generated by this method; but not how it really works, if that's a deliberate and/or following some article/method, if there was some goof at some point; which I ask.

The ROCA vulnerability/attack targets some RSA keys generated using “Fast Prime”. Details are in the paper: Matus Nemec, Marek Sys, Petr Svenda, Dusan Klinec, Vashek Matyas; The Return of Coppersmith’s Attack: Practical Factorization of Widely Used RSA Moduli published at CCS 2017 (in a slightly earlier version).

Paraphrasing that article: the factors making the attack possible (presumably, those generated by “Fast Prime” ) are of the form
$$p=k\;M+(65537^a\bmod M) \ \ \text{ where } M=P_n\#=\prod_{i=1}^n p_i$$
with $p_i$ is the $i^\text{th}$ prime.

It follows that any public modulus $N$ made from primes generated in this way is such that $N\equiv65537^a\pmod{P_n\#}$ for some integer $a$.

The integer $n$ is chosen according to the desired bit size of $p$ (which is always multiple of 16), by discrete steps, in a way such that $P_n\#$ is a large fraction of the size of $p$
$$\begin{array}{c|ccc}
\text{bits in }p & n & p_n & \text{bits in }P_n\#\\
\hline
 256 \dots  480 &  39 &  167 &  220 \\
 496 \dots  976 &  71 &  353 &  475 \\
 992 \dots 1968 & 126 &  701 &  971 \\
1984 \dots 2048 & 225 & 1427 & 1963 \\
\end{array}$$

A former version of this question discussed the first published ROCA test for vulnerable keys. However that's obsolete: it turns out this test was intentionally simplified to limit disclosure about the vulnerability; the full test has even lower odds of false detection.

This is a tentative guess at answering my own question.

Perhaps the "Fast Prime" method alluded to in the question's citation is that of these two papers (the second polishing the first):

[JPV2000]: Marc Joye, Pascal Paillier, and Serge Vaudenay; Efficient generation of prime numbers, in proceedings of CHES 2000
[JP2006]: Marc Joye and Pascal Paillier; Fast Generation of Prime Numbers on Portable Devices: An Update, in proceedings of CHES 2006 (slides).

Several things match:

The objective of the articles is clearly the one pursued by the technique used.
"Fast Prime" is two words from the title of [JP2006].
"date back to the year 2000" is matched by the publication of [JPV2000].
"use started around ten years later after thorough reviews" allows [JP2006] to get published and reviewed.
From what we know, the prime generator makes heavy use of an $M=P_n\#=\displaystyle\prod_{i=1}^n p_i$, essentially as [JPV2000] and [JP2006] do (their $\Pi$ is $M/2$).

However, the technique in [JP2006] is proven to generate almost random primes, and is not susceptible to the ROCA attack. Hence if my theory is right, there has been a serious implementation goof.

The fact that $65537^a$ occurs makes me wonder if the cause of the goof might be a deliberate attempt, gone horribly wrong, to make it faster to compute $e^{-1}\bmod p$ with $e=65537$; or perhaps just insure that it is defined.

Update: as noticed in comment, Daniel J. Bernstein and Tanja Lange's blog confirms an attempt at implementing [JP2006] gone wrong:

  A related algorithm "GenPrime" was published by Joye and Paillier in 2006. The Joye–Paillier generator, like Lehmer's generator, starts from a new random number $r$ coprime to $L$ and then multiplies repeatedly by a constant $g$ modulo $L$, obtaining $r$ times a power of $g$. This can produce any number modulo $L$, and produces only a slight bias in the resulting primes. The guess was that (company) was oversimplifying and generating merely a power of $g$; this produces far fewer numbers modulo $L$.

  The authors wrote back promptly, confirming that this guess was correct but not revealing more details.


Key recovery when AES ECB is used for short but repeated messages My question is based on the specification of the protocol LoRaWAN and especially on the part 6.2.5 Join-accept message.

It is said that the join-accept message is encrypted using AES ECB. This is (normally) a single message created like that:

aes128_decrypt(AppKey, AppNonce | NetID | DevAddr | RFU | RxDelay | CFList | MIC)

Imagine that an attacker can listen the communications. He doesn't know AppKey (obviously), AppNonce and of course the MIC. If the attacker can make the end device send plenty join-request messages and if the server always responds with a corresponding join-accept message, can the attacker gain knowledge of the AppKey using the flaws in AES ECB?

Disclaimer: sorry if I'm not clear, cryptography is not my speciality.

If the attacker can make the end device send plenty join-request messages and if the server always responds with a corresponding join-accept message, can the attacker gain knowledge of the AppKey using the flaws in AES ECB?

No. ECB is flawed, but not that flawed.

At worst the attacker can know the encryption of a message if they have already seen the same message encrypted. (Or decrypted, as the case may be - LoRaWAN uses the decryption direction here to avoid having to implement both directions in the end-device.)

That can still lead to attacks, but key recovery is not possible.


Transparent, publicly updatable accumulator with constant-sized witnesses I am looking for an accumulator with the following properties:

Transparent: No trusted setup (rules out RSA and pairing-based accumulators)
Publicly updatable: No central authority (rules out digital signatures)
Constant-sized witnesses: (rules out Merkle accumulator)

Are there accumulators with all the above properties?

The intended use case is a public blockchain without a "super user"/"admin"/"authority" managing the accumulator. In particular, witnesses should be publicly verifiable, accumulator updates (additions and/or deletions) should be public, and witnesses should be updatable from publicly broadcasted auxiliary information.

Later edit: Actually, some new Stanford work shows how to obtain transparent RSA accumulators using class groups. This was also discussed in Secure Accumulators from Euclidean Rings without Trusted Setup, by Helger Lipmaa.

The Stanford work also shows how to publicly add and remove elements in the accumulator. And the proofs are constant-sized.

Original answer: If you're willing to generate RSA keys in a distributed fashion, then you might as well go for bilinear accumulators, since you can also generate $q$-SDH parameters for them in a distributed fashion and they will be faster for non-membership proofs and also support subset proofs.

Depending on how you squint your eyes, yes, bilinear accumulators have all of those properties.

No trusted setup: just use MPC to generate $q$-SDH public parameters.
Publicly updatable: given old set $X$ and updates $U$ s.t. new set $X' = X \cup U$, anybody can simply recompute $acc(X')$.
Constant-sized witnesses: bilinear accumulator witnesses are 1 group element for membership and 1 group element plus 1 field element for non-membership.
Witnesses should be publicly-verifiable: in bilinear accumulator they are
Accumulator updates (additions and/or deletions) should be public(ly made): anybody can recompute an updated bilinear accumulator
Witnesses should be updatable from publicly-broadcasted auxiliary information: I know membership witnesses can be easily updated in $O(1)$ time after 1 addition to the accumulator. Not sure about non-membership witnesses. However, given the new set $X'$, anybody can compute a new witness in $O(n)$ time.

Hope this helps!


Parity checking on DES key if using ASCII chars This is my first question here, so if I ask it to the wrong group or otherwise infringing the (written or unwritten) rules of the community, please bear with me.

My problem is this: In an exercise in futility, I am trying to write a small program (in C) that implements the DES (FIPS 46-3) standard. I stumbled upon that part in which, from each byte in the 8 byte key, the LSB is used for (odd) parity checking, and eventually discarded.

That, I assume, means that a key like "aaaaaaac" (ASCII encoding) is invalid, since "c" (0x63) has even parity.

Now, either this is correct (and my question would be how commercial / publicly - available packages treat this, since I believe I saw plain ASCII used as key) OR it is a wrong train of thoughts, in which case I would like to know what I am missing.

Thanks a lot in advance.

a key like "aaaaaaac" (ASCII encoding) is invalid, since "c" (0x63) has even parity

Right. Notice that restricting to ASCII ($2^7$ values per byte, of which $2^6$ with odd parity) severely reduces the already small keyspace of DES, from $2^{56}$ to $2^{48}$ keys ($<2^{45.5}$ if one restricts to printable ASCII). For this reason, DES keys are usually expressed in hexadecimal.

  how commercial / publicly - available packages treat this

A very common practice is to exclude parity checking of DES keys from the functionality offered, and simply ignore the low-order bit, treating a key byte of 0x63 (ASCII c) just as 0x62 (ASCII b).

Another practice is to reject a key as invalid if any of its byte has even parity. With 64-bit x and side-channel protection aside, that could be implemented on the tune of

x = (x>>4) ^ x;
x = (x>>2) ^ x;
if (( (~((x>>1) ^ x)) & 0x0101010101010101) != 0) // error

For why DES keys have parity, see Purpose of DES parity bits.


What is a safe maximum message size limit when encrypting files to disk with AES-GCM before the need to re-generate the key or NONCE The general limits from the NIST recommendation are as follows:

  Maximum Encrypted Plaintext Size ≤ 239 - 256 bits;

  Maximum Processed Additional Authenticated Data ≤ 264 - 1 bits;

This stack overflow answer (https://crypto.stackexchange.com/a/20340/44337) hints that the maximum invocation of 239 - 256 bits of encrypted plaintext is too big and “you should be advised to stay well away from those limits.” In this case what kind of limit makes sense where I can optimize the use of a generated key, but also not decrease the security of the cipher text? Is reaching the maximum invocations of the encryption operation of 232 operations considered too dangerous? Should I go ahead and limit the amount of invocations to 231? Or may be half that to 216? I have the ability to generate new keys at any time for any file. So the question is what is a good trade-off between maximum key use and security. Obviously I can’t process more than 239 - 256 bits with the same key.

Some of the comments on stack exchange mention the maximum number of 96 bit NONCEs to use with the same key is 228.9 which will keep the security above 264  (Is the length limit of AES-GCM per key or per (key, nonce) pair?). I am strictly trying to figure out what the maximum safe size of the processed message with the same key/NONCE is before the need to re-generate the key or change the NONCE.

Another stack exchange question deals directly with the size of the encrypted message but does not give a recommendation of the safe maximum size (Plain text size limits for AES-GCM mode just 64GB?). Instead it shows that the security depends on the tag and the number of encrypted message blocks. The relationship is n - k, where n is the tag length and k is the number of encrypted blocks. So for a 96 bit tag processing a message of size 232 blocks, this gives us 96 - 32 = 64 or 264 security. Which is pretty low. Other commenters say to chunk the encryption at around 10GB per chunk. But what kind of security are we achieving then?

It seems that AES-GCM is not well suited to encrypt large files unless more complexity is added in chunking the files appropriately at some safe limits such as 1 GB or 10 GB etc. May be a better solution would be to use ChaCha20/Poly1305, but that is out of the scope of this question. I want to see what the current limits of AES-GCM are before I decide to change the cipher.

Security analysis of AES-GCM for maximum key use

Note: I am not a cryptographer. As such there are probably mistakes in my analysis. Please help me fix my mistakes and built on top of this answer so we can collectively arrive at the correct conclusion.

AES-GCM Setup

Key: 256 bit
IV 96 bit (deterministic construction)
Tag: 128 bit

Analysis

The internal implementation of GCM is using CTR mode of operation with a 32 bit integer for a counter which sets a hard limit on the number of invocations of the encryption operation to 232 blocks. The first two counter values are reserved so this gives us 232 - 2 number of invocations. This corresponds to the first limit set by the NIST standard to 239 - 256 maximum bits that can be processed with a single key/IV pair.

The IV is recommended to be 96 bits and as such I’ll use this in my analysis. In the general deterministic construction the IV is made of a 64 bit (invocation field) counter and a fixed 32 bit field. The 32 bit field is not important in our discussion. Wrapping 64 bit counter will take 264 operations which far exceeds the actual maximum of the underlying CTR mode of operation: 232 - 2. Therefore the minimum of the two is the allowed usage of the GCM mode: 232 - 2.

The final security parameter for the GCM mode is the authentication tag length. I assume a 128 bit tag length as it is the recommended by most. Theoretically, all secure hash functions have at least one weakness defined from the Birthday Paradox. It states that in order to get 50% chance of collision you need to do half the hash output length number of operations. For our 128 bit hash this gives us a security of 264 for a 50% chance of collision. This is in contradiction to our desired security of 2128, but it is what we have to deal with. Since the number of hash operations is still limited by the actual internal CTR mode of operation to 232 - 2, the authentication security is 296 - 2 which is quite high for the 128 bit tag. This is outside of the reach of any attacker at the moment.

Niels Ferguson's message-forgery attack on GCM provides further limits on the authentication tag. It is primarily targeted to the truncated version of the tag, but we’ll look at the full 128 bit tag. The attack uses about 2t (n-bit) blocks to succeed where t is the tag length. Here is the explanation of the attack from Rogaway

  The adversary asks for the MAC of a single message having 2(t / 2 + 1) blocks and then forges after about 2(t / 2) expected tries, on messages again of 2(t / 2 + 1) blocks. Focusing on the case of 32-bit tags, for example, the attack begins by asking for the MAC of a single message of 217 blocks. After that, it needs about 216 verification messages, again of 217 blocks each, until the first forgery is expected.

This is not a concern for 128 bit authentication tag, because in order to succeed you need the tag of a message of size 2(128 / 2) 128 bit blocks to begin with. This is impossible to craft as the internal CTR limit is 232 - 2, 128 bit blocks.

However, the theoretical investigation of hashes deviates from the practical realization of the underlying GHASH algorithm. It has problems that have been identified which generally reduce its security somewhat. As such we are well advised to stay away of the theoretical birthday bound of 264 operations for the same key H. But since we have an upper limit of only 232 operations from the underlying CTR construct, this raises our security parameter from 264 to  128 - 32 = 96 or 296 for the same key H.

Conclusion

After considering all of the above, it appears that the limiting security factor is the internal CTR mode of operation for AES-CTR which is processing at most 232 - 2 blocks. If we process that number of blocks we should still achieve high security margins and no further data chunking should be necessary. Therefore it is safe to utilize the full range of AES-GCM encryption and process 239 - 256 bits of plaintext data with the same key when using a 128 bit tag and a 96 bit IV.

Update

I have summarized my research on how to use AES-GCM correctly in a blog post.


Why do algebraic proofs apply to cryptography? How do we know that the number theoretic and algebraic results used in cryptography provide a perfect model for the behavior of integers as implemented in computers? Does there exist a bijection between the purely mathematical integers and the two’s complement integers, and are subsets of the two’s complement integers under the modulus operator isomorphic to the corresponding (mathematical) integers mod n?

If so, are these conditions sufficient for all cryptographic proofs relying on algebra and number theory?

Integer operations as implemented on computers are isomorphic to a theoretical definition of integers. Otherwise operations would not give the correct results.

Given the terminology in your question, I suspect that when you think of integer operations on a computer, you're thinking of operations on machine words. Cryptography uses numbers that don't fit in machine words: any cryptography code that works on integers (i.e. generally speaking asymmetric cryptography) must include a bignum library (or rely on a third-party one).

Two's complement is a way to represent negative integers. It's irrelevant to cryptography because cryptography pretty much never uses negative integers: only nonnegative integers ($\mathbb{N}$, or integers modulo $n$ which are stored using their representative in the range $[0,n-1]$.

You can find a formal proof of the equivalence between Peano arithmetic and arithmetic on binary representations in many places, for example in the BitNat module of Coq.

Implementing integer operations is a non-problem as far as getting the correct result, but it does have an impact on security. If the implementation is not careful, side channels such as timing and memory access patterns may leak confidential data that compromises the security of a protocol that would be secure if the adversary could not find out any information about the intermediate values.


Why is $S(y) = y^{2^8-2} = y^{254}$ a one-to-one function and a permutation on $GF(2^8)$ I'm taking a course on cryptography and I have some confusions concerning the materials in our notes. Say we have the field $GF(2^8)$, we create a substitution algorithm (the S Box in AES) so we need a bijective function that maps from $GF(2^8)$ onto itself.

The total number of one-to-one functions is 256! because $| GF(2^8)| = 256$ and we can find a mapping by permutating all elements within the set.

We use the mapping function $S(y) = y^{2^8-2} = y^{254}$ which is a permutation on $GF(2^8)$

Why is this a permutation? How do we show this?

It is also mentioned in other notes such as here: SubBytes Transform circuit for AES Cipher (Version 1.0)

that

$S(y) = y^{-1}$ for all $y \neq 0$
and
$y^{255} = 1$

I don't understand why however.

Just to summarize, I don't understand
why  $S(y) = y^{2^8-2} = y^{254}$ is a one-to-one function and a permutation on  $GF(2^8)$ and why $S(y) = y^{-1}$ for all $y \neq 0$

Could someone help explain the details behind? Thanks!

Fact 1: the order of the field $GF(2^8)$ is $2^8$, hence the order of its multiplicative group $GF(2^8)^{\times} := GF(2^8) \setminus \{0\}$ is $2^8-1 = 255$.

Fact 2: For a group $G$ of order $q$, any element $g \in G$, when raised to the power of $q$ is equal to 1: mathematically put,  $g^q =1$.

Fact 3: for any element in a group there exists a unique inverse. An inverse to $g$ is an element (denoted by $g^{-1}$) that satisfies $g \cdot g^{-1} = 1$. In other words, the function $g \mapsto g^{-1}$ is one-to-one.

In our case, any element $g \in GF(2^8)^{\times}$ satisfies $g^{255} = 1$. Another, useful way to write this is that for any $g$ we have $g \cdot g^{254} =1$. Since $g \cdot g^{254}= g^{255} = 1$ we have that $g^{254}$ is equal to $g^{-1}$.

We conclude that the function $g \mapsto g^{254}$ is equal to the function $g \mapsto g^{-1}$ which is one-to-one, hence it is a permutation of the group  $GF(2^8)^{\times}$.

I'd be happy to elaborate on any unclear part.


md5: is reverse length-extension attack possible? If I know

H = md5( SECRET_KEY | DATA )

then I can calculate

H' = md5( SECRET_KEY | DATA | DATA' )

That's length-extension attack. But is the opposite possible? E.g. if I know

H = md5( SECRET_KEY | DATA )

can I find

H'' = md5( SECRET_KEY )

where DATA is known and lenght of DATA is known too???

Basically, can I find md5 of the KEY without DATA (once again, DATA is known, H is known, but SECRET_KEY is unknown)?

The short answer is: No, there is no known practical attack in the setup given.

But we do not have an argument/proof that there is not one, and we should be less confident in that than we are in HMAC-MD5, for which we have such an argument.


Padding Oracle: Why should padding be 0x01? I just finished reading about padding oracle attacks at https://blog.skullsecurity.org/2013/a-padding-oracle-example, and it blew my mind. I think I understand almost all of it, but I do not understand one critical thing:

When looking for good padding, why should the first one (last byte of the message) be 0x01 when you've found the right symbol? Additionally, why should the pattern for the next to last byte be 0x02 0x02 and the next 0x03 0x03 0x03, etc.

I understand the padding scheme requires that if you have 4 bytes of padding, the bytes should be 0x04, 0x04, 0x04, 0x04. And if you have 2 bytes of padding, it should be 0x02, 0x02, etc. That's not the problem. The problem I do not understand is: Why should you get padding when you decrypt your now-modified sequence of bytes?

In other words, pretend I had the string "Hello!" and a block size of 8 bytes. I would expect there to be two bytes of 0x02 padding after whatever the encrypted "Hello!" string turns out to be. Now, in the attack, I add 8 bytes of zeros before it, run it through decryption, incrementing the last byte until I get valid padding. I do not understand why the padding should be 0x01 at this point, not 0x02, as was in the original. Similarly, when it moves on to the next byte to figure out, they are looking for 0x02, and 0x03 for the next, etc. Why is this?

That is the way the PKCS#7 standard works. This standard is the "most used padding method in symmetric ciphers". Which is why most descriptions of the padding oracle attack simply assume that padding scheme. Other padding schemes are likely also vulnerable.


Running Key Gibbs Sampling I am trying to implement the algorithm described in this paper. It uses blocked Gibbs sampling to perform a ciphertext-only attack on text encrypted with a running key cipher. However, I am confused by what it means when it says 'Sample ___ according to ___'.

I have not used Gibbs sampling before so I have watched a few videos explaining it. From the algorithm given in the paper, I am thinking I need to sample the positions of the spaces from the distribution $\Pr(P)$, but I am not sure how I am supposed to sample from it. The same goes for sampling the words.

(Note that it says later on in the paper that $\Pr(P) = \lambda\Pr(P\mid\text{word LM}) + (1−\lambda) \Pr(P\mid\text{letter LM})$ and they fix $\lambda=0.7$. I believe that LM means 'language model'.)

Does anyone know how to sample from these distributions, or am I misinterpreting it?

In general, the idea of a Gibbs sampler is to sample from the joint distribution $\Pr(X_1, X_2, \dotsc, X_n)$ on many variables $(X_1, X_2, \dotsc, X_n)$ using samplers for the conditional distributions on each single variable given all the others: $\Pr(X_1 \mid X_2, \dotsc, X_n),$ $\Pr(X_2 \mid X_1, X_3, \dotsc, X_n),$ $\Pr(X_3 \mid X_1, X_2, X_4, \dotsc, X_n),$ and so on.  The process is simply to randomly pick an initial state $(X_1, X_2, \dotsc, X_n)$, and then iterate picking a variable $X_i$, discarding it, and replacing it by a sample from the conditional distribution on it given all the other variables.  Under certain assumptions, in the limit as the number of iterations grows without bound, the distribution of the resulting values for $(X_1, X_2, \dotsc, X_n)$ is the intended joint distribution.

Here, besides the known ciphertext $C$, a sequence of letters, we have a few random variables:

$P$, the unknown plaintext, a sequence of letters
$R$, the unknown key, also a sequence of letters, determined by the plaintext $P$ because $R = (P + C) \bmod 26$
the word boundaries of the unknown plaintext—e.g., if $P$ is expertsexchange, it could be broken down into words as experts exchange or as anything else
the word boundaries of the unknown key—e.g., if $R$ is iamtheverymodel, it could be i am the very model or iam th every mo del

At each step, you can pick some variable to change:

Pick new word boundaries for $P$: instead of uvular laryngeal, try uv ulary n geal, for example.

Exactly how the authors sample from the distribution on word boundaries is unclear, but one possibility is:

Choose a candidate uniformly at random from all possible word boundaries.
Evaluate the probability of the old sequence $\Pr(P)$ and the probability of the new sequence $\Pr(P')$ in the combined word/trigram model.
Flip a coin weighted by $\Pr(P')/\!\Pr(P)$; if it comes up heads, take the new sequence, but if it comes up tails, keep the old sequence.

(This is a kind of local Metropolis–Hastings sampler.  Maybe they have a more efficient way to sample from this distribution.)
Pick new word boundaries for $R$, by the same process.
Given a set of word boundaries for the plaintext, say careful with that, go through each word-length chunk and sample a new word of that length at random from the dictionary—for example, you might kick out careful and draw a new word verdant, or you might kick out the entire sequence of words and replace them by baleful were they.

The distribution on new words is determined by the probability of the new value for $P$ and the new value for $R$ in the combined word/trigram model.  Doing a single word at a time is cheaper, but may be more likely to get stuck; doing a block of words at a time is more expensive but moves around in the distribution more rapidly.

Again, you might use a kind of local Metropolis–Hastings sampler for this, or maybe they have a more efficient way to sample from this distribution.

Another possibility—if the words are independently distributed in a sequence in your word model, which they may not be—is to flip a coin weighted by $\lambda$, and if it turns up heads, pick a word at random from the dictionary, whereas if it turns up tails, pick a word at random from the trigraph model.  This sampler gives words $P$ with the probability distribution $\lambda \Pr(P \mid \text{word LM}) + (1 - \lambda) \Pr(P \mid \text{letter LM})$, under certain assumptions about the word LM and letter LM models.
Same for the words in the key.


Making both the IV and salt public for PBE with AES-CFB Is it okay to make both the IV for AES-CFB and the salt for PBKDF2 public? Does this action of mine compromise security in any way?

I have an implementation of this cipher and had previously asked a question about this cipher on stack Overflow. One of the users who answered my question told that it is OK to make the both password salt and IV  public. Not that I don't believe him but just wanted to be double sure to correct my implementation.

In cryptography an Initialisation Vector or IV is an input of fixed size required to randomize the output of a cryptographic primitive. It is not meant to be secret, so there is not problem in make it available to the attacker after the encryption. The crucial point about the IV is its uniqueness and, for some mode of operation, its unpredictability. So, if your implementation correctly generates the IV using the right random number generator there is no problem in making it public, after the encryption.
Quoting poncho:

  What this means that if you keep the IV secret, it doesn't really
  hinder any particular attack in any way. One way to see that is to
  assume the contrary; let us assume that, if we expose the IV to the
  attacker, that he can exploit some weakness. If we assume that, then
  the attacker can use that weakness to attack a CFB mode encrypted text
  without the IV; what he does is take the ciphertext (without the IV),
  and treat the initial ciphertext block as the IV, and the rest of the
  ciphertext as the "real" ciphertext; the plaintext this corresponds to
  is the normal plaintext with the initial block omitted.

  Because of this, if exposing the IV with CFB mode lead to a weakness,
  CFB mode in general is weak. Now, written this way, this might not
  sound very comforting; however athat statement is logically equivalent
  to "if CFB mode is strong, then CFB mode with the IV mode exposed is
  strong", which is really what we want to show.

A salt is a random value added as additional input to an hash function, or to a key derivation function to protect the construction from dictionary attacks, an attacker should create a dictionary per salt. As in the IV case, the crucial property is the uniqueness. You don't want all password share the same salt (otherwise an attacker may build a dictionary to attack many password at the same time).

In both cases you should authenticate the values.

So the answer to your question is "no, it does not compromise security". You should really pay more attention to the algorithm used to generate IVs and salts (and probably salt size). And add a mode to check the integrity of the ciphertext (+ the IV) before decrypt it.