Cipher feedback mode with shift registrers Can someone please explain to me how the Cipher Feedback Mode works? From what I have read some examples have a shift register in its explanation but some examples don't. Is there two versions of CFB and what is the difference? What is and how does a shift register work?
The first picture shows the process without a shift register and the second picture uses a shift register.
Screenshots from the related video:

Also, in the explanation of AES on Wikipedia it says that the four steps sub bytes, shift rows, mix columns and round key addition is done in 14 cycles for a 256 bit key. Is that the case for the CFB mode as well or is that just for a different mode of operation?

To address the last bit first: CFB and AES aren't really the same thing. AES is a block encryption algorithm (encrypts a single block of data, 128-bits in the case of AES). CFB is a mode of operation, which defines how multiple blocks are encrypted, and is agnostic to the algorithm. CFB is used the same way no matter what the "Encrypt" function in the middle is.

For your first question.. I'll start by saying that I have no idea what's going on in the second photo; between the hand writing and abbreviated notations, not to mention the literal hand, I can't follow it.

But the first one is much clearer.

For each block...

Either the IV or previous ciphertext is encrypted using the AES algorithm (or whatever algorithm is being used) to produce what's effectively a key stream (like a stream encryption algorithm)
The current block of plaintext is XOR'd with the key stream to produce the ciphertext

It's basically using a block encryption algorithm (AES) as a stream encryption algorithm.

The cool thing about this is that (with the key) you can easily decrypt arbitrary data from the middle of the stream - all you need is the ciphertext of the previous block (or the IV), which you encrypt and XOR with whatever you're decrypting. But you can't encrypt new data in the middle - changing a block changes the entire rest of the cipher. So it's optimized for encrypting in-order and decrypting in any order.

Typical attacks against stream ciphers may also work; for example, you don't get any real integrity protection. Somebody can XOR a byte from the block to change it to something they control (although I suspect this can only be done in the final block, otherwise it's going to change the remainder of the ciphertext).

But yeah, I think the first diagram is pretty straight forward. No clue what the second is talking about..


What exactly does a key do? I am getting to grips with cryptography as a total newbie, and am struggling with encryption "keys" and how to visualize them.  From http://computer.howstuffworks.com/encryption.htm/printable:

Symmetric-key encryption is essentially the same as a secret code that each of the two computers must know in order to decode the information. The code provides the key to decoding the message.
Think of it like this: You create a coded message to send to a friend in which each letter is substituted with the letter that is two down from it in the alphabet. So "A" becomes "C," and "B" becomes "D". You have already told a trusted friend that the code is "Shift by 2". Your friend gets the message and decodes it. Anyone else who sees the message will see only nonsense.
The same goes for computers, but, of course, the keys are usually much longer. [...] The DES uses a 56-bit key.

This doesn't make sense to me because the process of "shifting by 2" sounds like the algorithm that is being used, yet it is referred to as a "key"?  If this is the key, then what is the algorithm?
I also don't completely understand what it means the key is "56 bit" in length.  The linked article mentions

56-bit key offers more than 70 quadrillion possible combinations

Now, this huge number is just under $2^{56}$, so each of those $56$ bits can be either a $1$ or a $0$, but I don't see how this fits into it all.
Can someone please clarify this for me?

Picking up what has been said in the comments:

to simplify: symmetric ciphers are like mathematical operations with 2 operands and 1 result. There is The plaintext message $m$ and $k$ as the key and they result in the ciphertext $c$. In your example, the algorithm can be cut down to a addition and modulo:

$c = (m + k) \mod k_{max}$

And of course there is a reverse algorithm (or more simply operation) that will turn $c$ into $m$ again:

$m = \begin{cases} c - k,& \text{if } c\geq k\\ c + k_{max} - k,& \text{otherwise} \end{cases}$

To sum it up: The way of calculation (the algorithm) never changes. Instead, the parameter(s) to it, the key, are different.

In the computer world these operations are much more complex and involve operations that are easy to compute in the binary system (e.g. XOR or bit-shiftig) that are rather complex to express mathematically.


Is there a concept of embedding degree for non-pairing based elliptic curves? From this post, I learned the concept of embedding degree. Intuitively, if embedding degree of an elliptic curve $E(F_p)$ is $k$, it means there is a way to transform points in $E(F_p)$ to $F_{p^k}$. Is the concept of embedding degree only valid for pairing-based elliptic curves, or does the same hold even for non-pairing based elliptic curves?

As pointed out by @yyyyyyy, every curve does have an embedding degree, i.e., there is some $k$ for which $p^k - 1$ is a multiple of $r$, the order one of the subgroups of a curve defined over $\mathbb{F}_p$.

There is a relevant result from Koblitz and Balasubramanian that establishes that the probability that the embedding degree of a random $n$-bit curve of prime order is "small" is vanishingly low:
$$
\mathbf{Pr}[l \mid p^k - 1 \text{ and } k \le (\log p)^2] \le c_3 \frac{(\log 2^n)^9(\log \log 2^n)^2}{2^n} \,.
$$
As such, only "special" curves that are explicitly designed to have small embedding degree $k$, i.e., pairing-friendly curves, are effectively computable; but the pairing does exist for all of them.


Help converting sha256 to 32-bit stream I need some help with hash value calculation.
 I am a bit confused by this statement that I found on w3 website on calculation of a DigestValue for xmldsig ( http://www.w3.org/TR/2002/REC-xmlenc-core-20021210/Overview.html#sha256 ):

  A SHA-256 digest is a 256-bit string. The content of the DigestValue
  element shall be the base64 encoding of this bit string viewed as a
  32-octet octet stream.

Does that mean that the sha256 hash value has to be converted to a 32-bit string before encoding it to base64?
If yes, could someone please tell me how this can be done? I'm a kind of a n00b, but I haven't found info on how to do that on the internet.

No, you don't have to convert to a 32-bit string.

A "32-octet octet stream" means an octet stream with a length of 32 octets. An octet stream is also known as a byte array. In older times bytes could have different lengths (7 or 9 byte lengths have existed). An octet is always 8 bits; nowadays octets and bytes should be considered synonyms.

So basically they are saying: treat the bit string as a stream of octets of the same length (as $32*8=256$), then base-64 encode it. Now most crypto libraries already treats the output of SHA-256 as byte array (octet stream). So you just are left with encoding the output to base 64.

One small warning: some crypto libraries already contain encoding internally. You will need to explicitly choose raw byte output for those libraries, unless you can specify base64, of course.


Understanding Meet-in-the-Middle attack on block ciphers I understand how to implement a Meet-in-the-Middle attack on 2DES/3DES, by computing for one half all possible keys and storing the outcome and then subsequently do the same for the other half but compare with the previously stored outcome to see if there is a match somewhere. Very unprecise description I know but just to state that I know how to do it for 2DES/3DES

The problem is for Feistel ciphers, where it seems that the very same technique cannot be used. Consider the below (sorry for the poor drawing):

So for a simplified example let's say the Feistel structure above operates on 16-bit blocks and uses 8-bit independant round keys. Each branch block is thus of 8 bits.The S-box is an 8-bit AES S-box.

Given that the adversary knows the following:

Full access to the code which encrypts a 16-bit block using the Feistel above
Knows exactly two plaintext - ciphertext pairs.

So given the two pairs, the aim is to find the key which maps the plaintext to the ciphertext.

Given the assumptions above, how is a Meet-in-the-Middle attack applied here? I've tried to use the same approach as with the 2DES/3DES, but it just doesn't apply in the same way. I'm in need of a bit of guidance on how to proceed.

I can't see where the "middle" value is, and from where I should compute forwards and backwards to reach such a middle value.

Edit: Forgot to mention that there are 4 rounds in the Feistel cipher.

We really only need one plaintext-ciphertext pair, but the second can be used as a way to check candidate keys.

Make a guess to the final subkey (ie guess all of them).
Decrypt the final round of your ciphertext using your key. Store this result and the subkey you used.
Repeat for all 2^16 candidates for the final subkey.
Make a guess for the first three subkeys.
Using these keys, go through the first three rounds of encryption of your plaintext.
If there is a collision between your intermediary encrypted result and your partially decrypted ciphertext, good! You (probably) found the key! You can double check using your other ciphertext/plaintext pair.

Alternatively, if you have enough storage space, you could build your storage of partially-decrypted-ciphertexts by going through the first two rounds of decryption (which are the reverse of the final two rounds of encryption). In this case, you'd bruteforce all candidates for the final two subkeys instead of just the final one. This requires storing 2^(16 * 2) partially decrypted ciphertexts, but has a speedup of 2^16.


Good practice to separate RSA key pairs used for encryption and digital signatures I've got the following related questions:

If Alice is using the same RSA key pair for both digital signatures and encryption, explain how Bob could forge Alice’s signature on a message of his choice if Alice is ‘foolish’ enough to help him.
What other reasons are there for keeping these key pairs separate?

I can answer this as follows:

If Alice would decrypt a random "ciphertext" for Bob and then return the decrypted message then Alice would have created a signature. Bob simply sends the required input to create a signature by performing modular exponentiation with the private exponent (or CRT parameters, of course). This would however only work for plain/textbook RSA decryption, which is not something you should use in practice.
Key management reasons:

a. You may always want to decrypt your stored ciphertext, but you may not always want to generate signatures with that particular private key.

b. You may not want to make your private key available for the other operations if you only require to perform decryption or signature generation.

c. Flexibility. Maybe you want to put one key pair on a smart card and keep the other in memory. Maybe you don't want to install the signature key on a device that just needs to perform decryption. Protect one with a PIN or password and use the other in an automated environment.


CCA security of this scheme Let $k$ be uniformly sampled from $\{0,1\}^\lambda$, $F$ be a secure PRP with block length $\lambda$ and let $Enc(k, m)$ be such that it returns $c = (F(k,r), r \oplus F(k,m))$ with $r$ uniformly sampled from $\{0,1\}^\lambda$. How to prove that this scheme is not CCA secure? In particular, how can an attack be thought of?

I won't give the answer; here are some hints:

Suppose we have a valid cipher text $(A, B) = F(k, r), r \oplus F(k, m)$.  What happens if we modify the ciphertext to be $(A, B \oplus C)$ and get that decrypted?
How can we use this?  What can we do if we have two ciphertexts that encrypt the same message $m$?


One Way function and Merkle Damgård Is it possible keep the "one wayness property" of certain one way function in Merkle-Damgård construction? I'm asking this question because according to Collision-Resistant hashing: Towards making UOWHFs practical the target collision resistant property fail in Merkle-Damgård construction.

Yes, a Merkle–Damgård hash can be one-way. Even MD5 hasn't been broken in that way.

Target collision resistance (TCR) is a notion similar to second preimage resistance (but for keyed functions). Preimage resistance, i.e. one-wayness, does not imply second preimage resistance, so a hash function can be one-way without even having second preimage resistance.

Normal collision resistance, which Bellare and Rogaway call any collision resistance (ACR) in that paper implies target collision resistance, so if the function is collision resistant, it is also TCR. With Merkle–Damgård a collision resistant compression function gives you a collision resistant hash function. Likewise, a preimage resistant compression function gives a preimage resistant hash function.

So what's the point of their result?

They show that TCR of the compression function does not imply TCR of the keyed hash function, meaning that e.g. a 128-bit MD hash does not necessarily have 128-bit TCR.


Security analysis of this one time password based scheme for copy protection Imagine such protocol.
Client and server initially share secret K[0].

When client wants to contact server she sends server K[0] and her ID.
Server accepts request, and generated new random K[1] and sends it to client which should use this in next communication.
Again, if client wants to authenticate with server now, she sends K[1]. Server accepts it if correct, and sends here K[2] to use next time and so on.

My first question is: Is there some name to this protocol in the literature? (Where security of this protocol has been studied?).

I want to use it for detecting if someone copied software of my client.

For me this scheme works most of the time: because if someone copies the client software it means the copy of the original software, will send say K[n] th password to server who will generate next password for client K[n+1]. But this way original client will go out of synchronization with the server because she will use old K[n] to authenticate and we will detect this - and achieve our goal.

The only attack I can see on this protocol if man in the middle just forwards clients messages to server and servers response to client.
Someone can present security analysis of this scheme?

Is the motivation for this a copy protection scheme?

If so, the most obvious problem is that if $K[n]$ is transmitted by the server but not received by the client, then synchronisation is lost.

This could happen if there is a proxy in between as is often the case in corporate networks with HTTP (or more controversially HTTPS) traffic. The updated value could be transmitted to the proxy but not downstream to the client. At this point, the application is irreparably broken.

Is this one-time password being transmitted over a secure channel? If not, then the following problems also apply:

How does the client authenticate that the $K[n]$ really came from your server and not someone else?

How does the server authenticate that the $K[n]$ provided to it, came from the client and not some third party?

If the one-time password is used to authenticate a message came from a valid host, how do I stop the message being modified in transit?


What should I be aware of when implementing algorithms myself? I plan to build my own crypto library. The project will be primarily for me to learn (and if useful for no other purpose, that is fine). In the past I have implemented a few hashes, and AES quite a few times while learning about it, but those projects were solely for me to learn, not for any field use. With this one I'd like it to work on it as if it were be to used outside of myself.

I understand that using/implementing your own crypto is usually a bad idea (if not always), so the answer to how to approach this is always "just don't". What makes sense in my head is: if all the tests work, the implementations should be valid. So I guess what I mean to ask is, does matching all the test vectors mean my implementations are valid mathematically? Is implementing mathematics correctly not enough because there are other things I need to plan ahead for? I know pretty much nothing about side-channel attacks, so I don't know if that has to do with the primitives in use or the system using them.

tl;dr: I don't intend to put it into production, but I want to build as if I were, to learn.

Does matching all the test vectors mean my implementations are valid mathematically?

Basically the comments got it, but test vectors are designed to attempt to hit lots of cases, but with high probability will not catch every single mistake. Should you do it? Definitely. Does it mean everything is perfect? No.

  Is implementing mathematics correctly not enough because there are other things I need to plan ahead for?

Like you mention, side channel attacks are of concern. Another concern which has little to do with security is efficiency. That said, if your library is too slow, others might disable it. This could be developers or users (if that option exists in the software).

I am all for doing things for learning purposes. It is a good exercise and can teach a lot. I am a "do it to learn it" kind of person. So I don't want to discourage you from that. If projects you are writing need crypto, and they are to be used by others, you are probably better off using stuff that is out there and has presumably been reviewed by cryptographers.


Non-linearity of a boolean function What's the definition of non-linearity of a boolean function? Roughly saying it is minimum number of times it equals any affine function. But I don't get it mathematically.

For example, if $f = x_1x_2$, then all the affine functions are $g_1 = 0$, $g_2 = x_1$, $g_3 = x_2$ and $g_4 = x_1+x_2$, then the non-linearity of $f$ is the minimum Hamming distance between $f$ and $g_i$'s. But what is the Hamming distance between two functions?

Linear functions when expressed as polynomials only have terms of degree 1 or 0.  Non-linear functions have at least one term of degree 2 or higher.  For example, here is a linear boolean function: $y = ax + bz + c$, where $y$ is the output bit, $x$ and $z$ are input variables, and $a$, $b$, and $c$ are constants. Notice that none of the variables are multiplied by each other -- they are only ever multiplied by constants in a linear function.

But with non-linear boolean functions, there can be terms with more than one variable in them, e.g.: $y = axz + bx + c$.  The number of variables in a given term (including when a variable is multiplied by itself) determines the 'degree' of that term, so in this example there is a term of degree two in the polynomial.

Edit to add: So your question is now what is the Hamming distance?  Take two strings of equal length and xor them together, then count the number of 1's in the resulting string -- the more 1's, the greater the 'distance' between the two strings.  When you take the truth table of a non-linear function (truth tables can be thought of as just another binary string) and the truth table of any linear or affine function and xor them together, there will always be at least one 1 in the result, no matter which linear or affine function you are comparing the non-linear function with.  The greater the 'distance' from all linear functions, the more non-linear the function.


are there more efficient methods than HMAC to achieve convergent encryption? I’m thinking about the convergent encryption system described in the top answer to this question. However, it seems like preferred modern HMAC algorithms like HMAC-SHA256 (as used in step 2 to create the “key”) are much slower than the actual encryption. Then SHA256 is invoked again on data the size of the plaintext to create the locator.

It seems like the first SHA-256 invocation that’s part of the HMAC step could be replaced by any other transformation of the plaintext which cannot be reversed and which will produce the same output given the same plaintext data, like simply encrypting the data with the “specially-selected HMAC key”. I also read about authenticated encryption and am wondering if I could use the MAC created during e.g. AES256-GCM as the key.

Would either of those approaches allow sidestepping the performance overhead of traditional HMAC methods? The only problem that I could think of is that it may be difficult to come up with an IV if that is required, since all writers would somehow need to use the same one in order for the “locator” to be consistent for all instances of the same input data.

If not, are there any known techniques for reducing the overhead of HMACs (other than reducing the input size)?

The answer depends on how you define ‘convergent encryption’ and what threats you're hoping to defend against.  Here are two broad options that you might mean:

You're a storage service and you make lofty promises about encryption to your users, but you also do deduplication between unrelated parties.  (Maybe you abuse the term ‘zero-knowledge’; it's trendy among such companies!)  You just want to prevent an adversary from

recovering a plaintext they don't know, or
forging a plaintext for deduplication so that some hapless user who tried to store a file would get the forgery when they later try to retrieve it.

This is a very weak notion of security, but it roughly corresponds to, e.g., Dropbox, who presumably save a lot of money by deduplicating files unrelated people have shared many times, and who presumably earn a lot of brownie points by preemptively checking files for known child pornography and notifying the authorities (of course, exactly the same technique applied to subversive imagery would serve the interests of an authoritarian government, but we won't talk about that).

So you use $H(m)$ as the encryption key, and maybe $H(H(m))$ as the deduplication index, like Tahoe-LAFS does (without convergence secrets).  In this case, you need a collision-resistant hash function $H$—otherwise an adversary could find a collision between a benign file $m$ and a file $m'$ full of child pornography, and then persuade the victim to try uploading $m$.  There are no shortcuts.  Sorry.  If you really need to squeeze performance out of it, some collision-resistant hash functions are cheaper than others—see eBASH for fair performance comparisons on a wide variety of hardware.
You, or you and a small group of friends, have secrets that you can use to encrypt files, and you want to do deduplication among your (and your friends') files.  You want to prevent an adversary who doesn't know the key from even confirming a hypothesis about what files are stored, and, of course, from fooling you into accepting forged files.

What you need to derive the convergent encryption key and deduplication key is a pseudorandom function family: the output must be indistinguishable from uniform random to anyone who doesn't know the secret key.

SHA-256 is expensive mainly because you it pays for collision resistance, and while HMAC-SHA256 is a perfectly respectable and widely available PRF, you're still paying for that collision resistance when you use it.

Here are a couple of alternatives:

A cheaper PRF like Kravatte, which is based on 6-round Keccak, in contrast to the 24-round Keccak used in SHA-3.  There aren't a whole lot of widely available options here: most work in this area goes into short-input PRFs or collision-resistant hashes.
Pick a universal hash family $H$ with bounded collision probability, such as Poly1305, and a short-input PRF $f$, such as ChaCha or Salsa20 (or HChaCha or HSalsa20, slightly cheaper).  Then build a long-input PRF as follows:

\begin{equation*}
    F_{k_1,k_2}(m) := f_{k_1}(H_{k_2}(m)).
  \end{equation*}

That is, loosely, use $H$ to compress the message with low collision probability, and then use $f$ to scramble it.

Universal hash families like Poly1305 are considerably cheaper to compute than SHA-256 or any other collision-resistant hash functions, and can be vectorized effectively.  Poly1305 implementations are widely available, e.g. in NaCl/libsodium as crypto_onetimeauth_poly1305.

If the collision probability of $H$, that is $\Pr[H_{k_2}(x) = H_{k_2}(y)]$ for $x \ne y$, is at most $\varepsilon$, and if the best PRF-advantage against $f$ is $\delta$, then the best PRF-advantage against $F$ is at most $q^2 \varepsilon + \delta$ where $q$ is the number of messages you handle under a single key (proof).

For Poly1305, $\varepsilon = 8\lceil L/16\rceil/2^{106}$ for messages up to $L$ bytes long, so with Poly1305 and ChaCha, if you store—or if the adversary tries to forge—up to a billion megabyte-long files (a petabyte of data), the advantage of the adversary at distinguishing any of the convergence keys from uniform random strings will be at most about $2^{60} 2^{16} 8/2^{106} + \delta = 2^{-27} + \delta$.  If the adversary puts additional computational power to it, that only raises $\delta$—but unless they can break ChaCha, the additional computational power will pale in comparison to what they need to guess your 256-bit key.

This technique is part of how the deterministic authenticated cipher AES-GCM-SIV works—the output of $F$ is used both as an authentication tag and to derive a per-message subkey to encrypt the message.  (Of course, AES-GCM-SIV uses GHASH, not Poly1305, and AES, not ChaCha, so it's good for hardware implementations and bad for software implementations.)


When will AES be "upgraded"? AES is secure, but compared to other encryption algorithm which are marked as secure, it's slow. For example, ChaCha20 is faster than AES, but still secure.

Also other standard-algorithms like SHA were upgraded in the last few years, so can we expect a AES upgrade in the near future?

No.

Basically your question is:

  The car maker X recently updated its flag ship car and the motor cycle maker Y makes a bike that is accelerating faster in straight lines - will the Lorry maker Z make a new lorry soon?

And I‘ll try to put this in laymen’s terms:

AES as a successor of DES is - in comparison to the lifetime of DES - relatively young.

Additionally, you are comparing ciphers that are not equivalent. ChaCha20 is a stream cipher and AES is a block cipher. The SHA family of hashing functions got new family members because the existing ones were showing signs of age and were generally thought to be feasible to break in several years because of the increasing computing power as well as increased progress in the cryptanalysis of sha1.

As to why you think AES would be slow, as Steffen said in the comments: this only might be true for software implementations. Yet, even smartphones do have hardware accelerated AES.

The process of replacing a cipher is very lengthy and I didn’t yet hear a call for papers for a successor of AES, so there should be at least years until AES gets replaced, probably a decade or two.

That being said, post-quantum cryptography is an active field of research and depending on when good enough quantum computers will be possible, a paradigm shift in standard ciphers will be necessary - yet I don’t think this applies to AES.


Given plain text of given cipher text, can AES key be uncovered? How difficult is it to find the AES key if attacker has IV and ciphertext of a known plain text?

I am assuming 128 bit key size.

It is not possible to find an AES key from a known plaintext / ciphertext pair. If that was the case then AES would either have to be:

vulnerable with regard to the key size or;
vulnerable against attacks that invalidate the cipher.

AES has a security close to the key size (of 128 bits, in your question). Brute force or more intricate attacks against the key itself are therefore infeasible.

And, as indicated by the text above, the cipher has certainly not been broken in a sense that you can (easily) recalculate the key. Allowing an attacker to find the full key is as broken as a cipher can get; in general it is assumed that an attacker knows parts of the plaintext.

The mode of operation and IV are inconsequential to the security of the key as the key is only used as input of the block cipher - both in CBC and GCM mode. The key is therefore protected by the block cipher itself.


Weak One Way Function Show The function $mult(a,b)$ is weak one way if the Integer Factorization Assumption is true.

I am read the proof of this enunciated but I want know if I understand this in my way. The proof use the lemma:

  For $k$ big, the probability for one number with $k$ bits, choosen in random form, is prime is greater than $1/k$.

If I choose two numbers the probability that they are prime is $1/k^2$. Using this fact, I will be able to say given the fact that for the probability $ 1 / k ^ 2 $ a mult function is difficult to invert, then to $1/k^2$ cases the mult function will fail, then as $1 / k ^ 2$ is not negligence. The proof is completed.

Well, if "weak one way" means that you shouldn't be able to consistently find preimages, that is, inputs that generate a specific output, and $mult(a, b)$ is defined as the integer multiplication $a \times b$, then $mult$ would not meet that definition.

For an arbitrary output $C$, we can set $a = C$ and $b = 1$; hence $mult(a, b) = C$.


Cost model for different curve models Is there a cost model for each curve model and their conversions?

For example:

Take the curve models: Projective, Completed, Extended, Affine.

Is there a table which shows how many multiplications, additions and divisions it costs to do point addition and point doubling for example?

Maybe a guide on when to choose each curve model over the other and or when the conversion to another model is worth it in terms of cost. I do not have any references, however I remember some programs always converting back to either a completed point or an extended point.

The Explicit Formulas Database, EFD catalogs a variety of curve forms, coordinate systems, and algorithms for arithmetic operations, along with operation counts and references to the literature.


Is the risk of a collision for OCB mode mitigated by upping the block size of the cipher? A paper published by Niels Furguson Collision attacks on OCB indicates that processing large amounts of data (somewhere on the order of $2^{32}$ 128 bit blocks) with a single encryption operation (same key and nonce) makes it probable that an attacker could create a modified cipher text that would generate the same tag as a the original cipher text (pass authentication) and decrypt to a different plain text.

The probability of the necessary X collision occurring

$$(m−1)^2 2^{−128}$$

appears to be related to the block size of the cipher. In the paper a 128 bit cipher (the size originally recommended in the OCB specification) was used for all the probabilities cited.

Another surprising property observed is that using larger tag lengths increases the probability of a collision occurring.

My primary question is: does using a larger bit size cipher (say 512 bits) with a small tag size (say 64 bits) decrease the probability of this collision occurring? And if so does it decrease it enough that more than $2^{32}$ blocks of data can be written with less then a $2^{-64}$ chance of message forgery?

Niels advises against the widespread use of OCB; is this the consensus throughout the cryptographic community?

Using a larger blocksize in a cipher will always aid in mitigating collisions.

For a practical example, take what OWASP says about key management:

  If the amount of data encrypted grows beyond a certain threshold, a new key should be used. This certain threshold varies depending on the encryption algorithm used, but is typically 235 bytes (~34 gigabytes) for 64 bit block ciphers (DES, 3DES, Blowfish, RC5, ...) and 268 bytes (~ 295,147,905 terabytes) for 128 bit block ciphers (AES, TwoFish, Serpent). If encrypting with a modern cipher, this threshold is unlikely to be reached, but it should be considered when evaluating algorithms and rotation procedures.*

I think Niels' views on the use of OCB are more academic than most people who might implement such a system. The biggest reason why OCB isn't being used is because of its patent. It also didn't help that in OCBv1 it didn't allow additional authenticated data. It was later added in OCBv2, but it did hurt adoption.

To reiterate on the above, Niels presents a more academic and logical argument against the adoption of OCB, but the biggest reason why it wasn't adopted was due to the patent the author has on it.

*https://www.owasp.org/index.php/Cryptographic_Storage_Cheat_Sheet#Rule_-_Limit_quantity_of_data_encrypted_with_one_key


How to generate tokens from a secret key? The problem is simple: I want to be able to spit out 256-bit "tokens" that only I could've produced because I know my secret key $s$, and given any number of these tokens, no one can figure what $s$ is.
How could I do this? Or something similar?

Note that I want a "parallel" implementation: e.g. I could give different tokens to different people separately, and they'll all know it's me.

A "serial" implementation (which isn't what I want) would be much easier:

initially, pick a secret phrase $s_1$
Get the SHA digest $d_{i}$ of the current secret phrase, and pick your next secret phrase $s_{i+1}$.
post $(s_{i-1},d_i)$ publicly with the note that only you can produce the $s_i$ that corresponds to this $d_i$, and you will do that with your next post to prove it's you.
Go back to step 2

Ideally, the solution would be some function $F$ such that a token $t=F(s,r)$ can be verified to have come from $s$ no matter what random input $r$. And no one can figure out what $s$ is.

The scenario I'd have in mind is something like this: John Titor wants to post on 4chan, an anonymous forum, and verify that it's him posting every time by including a 256-bit token each time. How can he do this?

I know there's the potential security threat of some malicious entity trying to pass off old tokens, but ignore that (since there's dozens of ways around it).

Digital Signatures are the solution.

A very simple algorithm is

Just like RSA, generate a public key $(N, e)$ for everyone, and a private key $d$.
Whatever message $m$ you post, also post a digital signature $\sigma = m^d ~(mod ~ N)$
People can verify the post is by you by checking that $\sigma^e = m ~ (mod ~ N)$

For more rigorous schemes, see Digital Signature and Digital Signature Algorithm


Question about IND-CPA with block cipher mode with random IV (CTR$ mutation) I know for a fact that CTR random is IND-CPA secure due to if an adversary want to break it, it will have to run a long loop where the $$\mathit{Adv}^{ind-cpa}_{CTR~random} = C(2^{n},q) - 0$$ However, if we change the encryption to something where in the beginning a random $IV$ is picked from the space $\{0, 1, 2, ....2^k - 1\}$ ($k$ as the block size) and for each block starting from $i=1$ to $n$ $$C_{i} \leftarrow E_{k} \bigl(\langle IV + i\rangle\oplus M_{i}\bigr)$$return $$IV||C_{1}||C_{2}||...||C_{n}$$Why is this not IND-CPA secure? The only different I can see this is different from CTR random is the random IV pick from the beginning is not run with the encryption $E_k$ before it XOR with the message and is increments with a predictable +1 in each block.

It is not CPA secure, because we can exhibit an attack against the CPA security of your construction.
There are two key insights here:

The attacker has (limited) control over the input to the Permutation $E_k$.
$E_k(x) = E_k(x')$ if and only if $x = x'$, since $E_k$ is a deterministic Permutation.

The trick is now to find two messages $m_0,m_1$, such that $m_0$ will result in the same value being fed into $E_k$ twice, while $m_1$ will result in different values being fed into $E_k$.
The attack works as follows: The attacker $\mathcal{A}$ outputs messages¹ $$m_0 = 0^{2\ell-1} \Vert 1 \quad\text{and}\quad m_1 = 0^{2\ell}$$
and receives the challenge ciphertext $c^* = IV\Vert c_1\Vert c_2$. If $c_1=c_2$, $\mathcal{A}$ outputs $0$, otherwise it outputs $1$.
Now we need to analyse the success probability of $\mathcal{A}$. Let $m_b^i$ denote the $i$th block of message $m_b$. As we noted above, it holds that $E_k(x) = E_k(x')$ if and only if $x = x'$. Therefore,
$$c_1=c_2 \iff \langle IV +1\rangle \oplus m_b^1 = \langle IV +2\rangle \oplus m_b^2.$$
For $m_1$, we have that
$$\langle IV +1\rangle \oplus m_1^1 = \langle IV +1\rangle \oplus 0^\ell = \langle IV +1\rangle \neq \langle IV +2\rangle = \langle IV +2\rangle \oplus 0^\ell = \langle IV +2\rangle \oplus m_1^2$$
therefore, when given an encryption of $m_1$, $\mathcal{A}$ will always output $1$.
In the other case, for $m_0$ however, we have
$$\langle IV +1\rangle \oplus m_0^1 = \langle IV +1\rangle \quad \text{and}\quad \langle IV +2\rangle \oplus m_0^2=\langle IV +2\rangle \oplus 0^{\ell-1}\Vert 1.$$
Now observe, that if the least significant bit² of $IV$ is $1$, then $IV+1$  and $IV+2$ will differ only in the least significant bit. I.e. $$\langle IV +1\rangle = \langle IV +2\rangle \oplus 0^\ell\Vert 1.$$
It thus follows that if (and only if) the least significant bit² of $IV$ is $1$, then
$$\langle IV +1\rangle \oplus m_0^1 = \langle IV +1\rangle = \langle IV +2\rangle \oplus 0^\ell\Vert 1 = \langle IV +2\rangle \oplus m_0^2.$$
Since $IV$ is chosen uniformly at random, the lsb of $IV$ is $1$ with probabilty $1/2$. Therefore, the attacker has an overall success probability of $$\frac{1}{2}\cdot\left(1+\frac{1}{2}\right) = \frac{3}{4},$$
which is clearly non-negligibly greater than $1/2$.

¹Note that I'm using $\ell$ to denote the block-length, since $k$ would be confusing, given that it's also the key.
²Assuming appropriate endianess. If my endianess above seems wrong to you, just flip the bitstring around.


Point addition equation in projective co ordinates How can I get point addition equation for elliptic curves in projective co ordinate system? Can I get it by changing $$ x = X/Z $$ and $$ y =Y/Z $$ in the equation for affine co ordinates' group law?

I have done it using the above narrated step and made the denominator as $ Z $ in equation for binary super-singular curves. Unfortunately I am not able to get the correct output. I have used the equation $$x_3 = (y_1 +y_2/x_1 +x_2)^2 + x_1 + x_2$$
$$y_3 = (y_1 +y_2/x_1 +x_2)(x_1 +x_2) + y_1 + c$$ for the curve $y^2 + cy = x^3 + ax+b$.

Your second equation seems a bit off. In the curve of equation:
$$ y^2 + cy = x^3 + ax + b $$
in a binary field $\mathbb{F}_{2^m}$, to add point $P_1 = (x_1,y_1)$ to point $P_2 = (x_2,y_2)$, resulting in point $P_3 = (x_3,y_3)$, then the two equations are:
\begin{eqnarray*}
x_3 &=& \lambda^2 + x_1 + x_2\\
y_3 &=& \lambda (x_1+x_3) + y_1 + c
\end{eqnarray*}
where
$$ \lambda = \frac{y_1+y_2}{x_1+x_2} $$

In projective coordinates, the point $(x,y)$ is represented by the triplet $(X,Y,Z)$ such that $x = X/Z$ and $y = Y/Z$. It is important to realize that the projective coordinates are not unique; $(X,Y,Z)$ and $(\mu X, \mu Y, \mu Z)$ represent the same point, for any non-zero $\mu$. If we have projective coordinates for $P_1$ and $P_2$, then we get:
\begin{eqnarray*}
\lambda &=& \frac{\frac{Y_1}{Z_1}+\frac{Y_2}{Z_2}}{\frac{X_1}{Z_1}+\frac{X_2}{Z_2}} \\
        &=& \frac{\frac{Y_1 Z_2 + Y_2 Z_1}{Z_1 Z_2}}{\frac{X_1 Z_2 + X_2 Z_1}{Z_1 Z_2}} \\
        &=& \frac{Y_1 Z_2 + Y_2 Z_1}{X_1 Z_2 + X_2 Z_1}
\end{eqnarray*}
Then:
\begin{eqnarray*}
\frac{X_3}{Z_3} &=& \frac{(Y_1 Z_2 + Y_2 Z_1)^2}{(X_1 Z_2 + X_2 Z_1)^2} + \frac{X_1}{Z_1} + \frac{X_2}{Z_2} \\
\frac{Y_3}{Z_3} &=& \frac{Y_1 Z_2 + Y_2 Z_1}{X_1 Z_2 + X_2 Z_1} \cdot \left(\frac{X_1}{Z_1} + \frac{(Y_1 Z_2 + Y_2 Z_1)^2}{(X_1 Z_2 + X_2 Z_1)^2} + \frac{X_1}{Z_1} + \frac{X_2}{Z_2}\right) + \frac{Y_1}{Z_1} + c
\end{eqnarray*}

The goal is to compute without making divisions; thus, we need to define $Z_3$ such that all these inconvenient fractions disappear. One possible solution, given the equations above, is to set:
$$ Z_3 = Z_1 Z_2 (X_1 Z_2 + X_2 Z_1)^3 $$
from which we deduce:
\begin{eqnarray*}
X_3 &=& (X_1 Z_2 + X_2 Z_1)(Z_1 Z_2 (Y_1 Z_2 + Y_2 Z_1)^2 + (X_1 Z_2 + X_2 Z_1)^2(X_1 Z_2 + X_2 Z_1)) \\
    &=& Z_1 Z_2 (X_1 Z_2 + X_2 Z_1) (Y_1 Z_2 + Y_2 Z_1)^2 + (X_1 Z_2 + X_2 Z_1)^4
\end{eqnarray*}
and some even more complex -- but without any division -- expression for $Y_3$ (that I am too lazy to compute).

So you get the two main points:

yes, to get projective coordinates, you "just" replace $x$ with $X/Z$ and so on;
but ultimately you still get some choice in the expression for $Z_3$, since projective coordinates are not unique. You thus choose an expression which minimizes overall computational cost, which usually means "the simplest expression which avoids divisions".

Since you have a choice in $Z_3$, you do not necessarily end up with the same formulas as other people, and it is not necessarily mean that your formulas are wrong.


Can you create a strong blockcipher with small blocksize, given a strong blockcipher of conventional blocksize? Suppose I want a strong 20-bit blockcipher.  In other words, I want a function that takes a key (suppose the key is 128 bits), and implements a permutation from 20 bits to 20 bits.  The set of permutations should be close to a randomly-chosen subset of size $2^{128}$ of all $2^{20}!$ permutations on 20 bits.

I don't want you to build a new blockcipher from scratch.  Instead, assume you have a "strong" blockcipher like AES (128-bit blocksize, 128-bit keysize) and use this to build your 20-bit cipher.

Of course, your construction should be practical (i.e., you should be able to run it in both directions with reasonable amounts of time and memory).

What you're looking for can be done using existing schemes for format preserving encryption (FPE). In general, FPE schemes convert an existing strong algorithm like AES into a block cipher that operates on a set of any size. For instance, FPE can encrypt 15 digit integers to other 15 digit integers (eg for credit card numbers, one of the common reasons for using FPE). Most of these schemes can be easily adapted for the set [0...2^20), usually with no special changes. For further details see this paper or this wikipedia article.

I assume you're aware that any 20 bit block cipher suffers serious intrinsic weaknesses (eg collisions using it in CBC mode) and have a specific reason for needing a 20 bit permutation.


Do I need to prepare plain text before encryption? When I want to encrypt chat messages (in ASCII) before sending, whether it brings some bit of security if I add some extra bytes to the message or shuffle it in some way? I can even try to make data to look like uniform distribution.

Because chat messages consist only of letters and even words, but don't contain binary data and other bytes except that from ASCII, so it gives some information about unencrypted data to eavesdropper.

But I'm afraid that some manipulations over the text could bring much more information to the attacker than doing nothing.

If you are using a modern, secure cipher, there is no reason whatsoever to perform such manipulations of the plaintext.

I'm not sure how to elaborate much more on the topic than that. The entire purpose of a cipher is to perform the exact types of confusion and diffusion you describe. Only, the approach that it will use has been designed, peer-reviewed, and cryptanalyzed by professional cryptographers. Your hypothetical algorithm has not.

At best case, it will do nothing to improve the security of your ciphertexts. At worst case, you can introduce bugs that unintentionally cause plaintexts to be unrecoverable from the ciphertext, or ones that accidentally reveal information about the plaintext (for instance, via a leak of timing information).


How can one parallelize tasks in CTR-AES for maximum performance? From what I have read it seems like one of the purported benefits of using CTR mode AES, is that it can be parallelized to a greater degree, or maybe more easily than the other block cipher modes, leading to performance gains?

In NIST SP800-38A §6.5 , it says:

  In both CTR encryption and CTR decryption, the forward cipher functions can be performed in parallel...

And this answer to “Decryption a chunk of file with AES”, if I understand correctly, suggests that basically you have one task do $$O_j=CIPH_K(T_j) \text{ for } j=1,2...\frac{n}{2}$$ with another task doing $$O_j=CIPH_K(T_j) \text{ for } j=\frac{n}{2},\frac{n}{2}+1...n$$ in parallel.

Is this what NIST SP800-38A, was referring to, something along these lines?
Or are there more or better ways to parallelize things?

From the diagram on CTR mode

you can notice that there are no dependencies between any of the phases of the pipeline. If you have more than one block-size worth of data, you can process each block-size chunk completely independently of the others by calculating $\mathrm{ciphertext}_i = E(\mathrm{key}, \mathrm{nonce} \, || \, \mathrm{counter}_i) \oplus \mathrm{plaintext}_i$.


Security of AES after key expansion 4-MB with ECB and CBC My question is,

how does the security depend or change if I encrypt with AES-128 in total 4-MB of Data?

With Electronic Code Book Mode and
Cipher Block Chaining Mode ?
Does an adversary still need $2^{126}$ tries (like Wikipedia suggests) to guess the key or is it less (which in my opinion it should)?

The encrypted data would be a videostream.

A videostream should probably not be encrypted with either ECB or CBC.

ECB is insecure for almost anything and it should not / can not be used to turn a block cipher in a secure cipher. This is clearly shown even in the Wikipedia description of the mode: find the penguin.

CBC is secure to keep data confidential. It is, however, susceptible to padding oracle attacks when not used correctly - especially in real time communication. It also doesn't allow e.g. caching of the key stream or parallel encryption, so the performance may be subpar as well. And although it does support seeking, it does require the user to retrieve the ciphertext block before the one that needs decryption.

This is why commonly CTR mode is used instead. Sometimes CTR mode is used in combination with a MAC to offer fast authentication and integrity of the ciphertext. , e.g. GCM mode. GCM mode, however, does undo some of the benefits of CTR mode.

However, probably the most common methods of wrapping a stream is to perform TLS. It does have some overhead, but at least well reviewed implementations exists. It depends if it fits your need.

The amount of tries to get to the key will always be in the neighborhood of $2^{127}$ tries for a (largely) unbroken cipher such as AES. The key is protected by the block cipher itself, rather than the mode of operation.

However, the security of the key only is only part of the security of the cipher. It is perfectly possible for a mode of operation to leak information on the plaintext even if the key is kept perfectly secure. The ECB penguin is a prime example of that. Another is CTR mode with a repeated IV, which turns the cipher into a "many-time pad".


Does RSA padding have to be unpredictable if the payload is? I'm trying to understand the precise requirements on padding when using RSA for encryption.

Suppose Alice uses RSA to encrypt a payload $M$ that cannot be guessed (say, a random nonce): Alice send $\mathrm{RSA}_{B_{pub}}(\mathrm{pad}(\mathtt{?}) || M)$ to Bob, with a padding procedure to be determined. Assume reasonable sizes, say a 1024-bit RSA key and a 256-bit payload. Alice may send the same payload $M$ to multiple recipients, encrypted with each recipient's private key. Only a recipient must be able to recover $M$. But it's ok if an external observer can tell that Alice sent the same $M$ to Bob and Charlie (sent as $\mathrm{RSA}_{B_{pub}}(\mathrm{pad}(\mathtt{?}) || M)$ and $\mathrm{RSA}_{C_{pub}}(\mathrm{pad}(\mathtt{?}) || M)$ respectively)¹.

With no padding, this is broken: the plaintext can be reconstructed from $e$ ciphertexts. In general, RSA padding must be random and not recoverable without knowing the private key, if only because otherwise the attacker could verify a guess of the payload; but here I assume the payload is unguessable. So what are the requirements on padding in this scenario?

Is it ok to use a deterministic padding function that depends only the recipient, say $\mathrm{pad}(B) = \mathrm{SHA256}(B_{pub})$?
Is it ok to use a predictable padding function, say by incrementing global counter for each recipient (assume Alice does have a reliable monotonic counter)?
Is it ok to use random padding that is leaked? In other words, in this scenario, is the mere fact that the attacker knows the padding a problem?

¹  What prompted this line of thought was a message $M$ that was a single-use symmetric encryption key; the long message encrypted with that symmetric key would be identical for all recipients anyway.

From what I understand, you consider a scenario in which a fixed, random-looking message $M$ is sent to multiple recipients, encrypted using RSA with some padding (this is called the "broadcast RSA" setting).

Moreover, you consider affine paddings, in the sense that you apply the RSA function to an element of $\mathbb{Z}_N$ of the form $a_i M + b_i$ for some values $a_i, b_i$ depending on the recipient which may be known in part or in full by the adversary (in fact, we even have $a_i = 1$ in the cases you consider, but that doesn't really matter).

In that case, expanding a bit on fgrieu's answer:

No, it is not OK to use a public deterministic padding that depends on the recipient, even if the padded message is as long as the modulus. This type of padding is broken in the broadcast setting by a generalization due to Håstad of the simple CRT attack alluded to by fgrieu.
For the same reason, a predictable padding function will not do, nor indeed any affine padding where the values $a_i, b_i$ are known by the adversary.
Even using such a padding where the $b_i$'s are randomized can be dangerous. For example, a padding of the form $R_i \| M$ (with $R_i$ chosen at random for each recipient and long enough so that the padded message is as long as the modulus) can be attacked in the broadcast setting if $M$ is relatively long: see this paper (the attack is admittedly rather theoretical, but still).
This survey on RSA attacks by Boneh is over 10 years old already, but always good reading (you're especially interested in §4).

Generally speaking, I wouldn't recommend using an affine or polynomial padding function for any new application except for interoperability reasons; and I would especially advise against using a custom affine padding that "looks strong enough" (unless you want to make cryptanalysts happy by providing them with a fresh new target :-).

A better idea (which is essentially what Thomas Pornin suggested in the earlier discussion) is using RSA-KEM (RFC 5990): for each recipient, pick a random element $R_i$ in $\mathbb{Z}_N$, and send $C_i = R_i^e \mod N$ to the $i$-th recipient, together with the encryption of $M$ (with your favorite block cipher) under a key derived from $R_i$.

Other options include paddings like RSA-OAEP (part of PKCS#1 v2.1).


Why it is not recommended to create your own random generator number? I read in a book: mastering bitcoin that one should not create his own random number generator and instead use a cryptographic secure pseudorandom number generator (CSPRNG)

Why is it so? Say I'm writing a simple python code to choose a number between 1 and 2^256 in the following way: create an array with 256 bits, fill up each index with a random number (1 or 0)

Why, or in what way, it is inferior to the CSPRNG? and how is this code is predictable?

So, you use integrated Python random, instead of CSPRNG. The problem is here: integrated random functions in programming languages are designed to be very fast, and they have some small period. For example, in C#, standard Random class is seeded by 32 bit integer. Let imagine I use it to generate 256 bit number, like you.

In this case, it can generate only 2^32 different numbers (one for each seed). But we know, there are 2^256 such numbers. If I have generated 256 bit number with this method, anyone can hack my number. He just have to run generator for all possible seeds. 4 billions is very small number and anyone with PC can brute force it.

In case with bitcoins, that means, anyone can restore your private key and steal your bitcoins. Because you used weak random.


Factoring a polynomial over a GF I have the following question:

  What polynomial, when factored over the field $GF (2^8)$ based on the irreducible polynomial that is used in Rijndael, will factor into all the polynomials in the field?

As I understand it, the polynomial should be an irreducible polynomial and this polynomial must factor all the polynomials. How can I get this polynomial? What steps should I follow?

There are several questions hidden in your question.

You'll have to distinguish between the polynomial ring $\mathbb Z_2[X]$, and the factor field $GF(2^8) = \mathbb Z_2[X]/F$ (where $F$ is any irreductible polynomial of degree 8).

In $\mathbb Z_2[X]$, the only polynomial which is a factor of all others is the trivial polynomial $1$. (In general, in a (unitary) ring the set of elements with this property are called units, and this ring has just the trivial unit one.)

In $GF(2^8)$ (like in any field), every non-zero element is a unit and thus a factor of every other element, but we normally don't call them "polynomials".

But the original question actually asks something else:

  What polynomial when factored over the field $GF (2^8)$ based on the irreducible polynomial that is used in Rijndael will factor into all the polynomials in the field?

The expression "factors into" can be understood as "is a multiple of" ... and "when factored over $GF(2^8)$" could be understood as "when seen as a polynomial with coefficients in $GF(2^8)$ (i.e. an element of $GF(2^8)[X]$, and then factored (into its prime divisors)". But then the expression "into all the polynomials in the field" makes no sense, as a field element is either $0$ (which is not a factor other than for itself) or a unit (which is a factor for everything), and you likely don't want $0$ as the result.

Quite likely the original question was something else, but I have no idea, what.


Why do we truncate the hash when using DSA? All the articles I read on the web about DSA keep telling me that the size of the hash needs to be truncated so that the bit length is equal to or lesser than the bit length of the prime number of the field.

For example, Wikipedia says:

  Choose an approved cryptographic hash function H. [...] The hash output may be truncated to the size of a key pair.
  Choose an N-bit prime q. N must be less than or equal to the hash output length.

But why exactly do we need this? What's wrong with using a 256-bit hash with a 160-bit prime?

I tried looking on the web, but I keep getting results that explain me how to truncate the hash, not why.

During verification you perform $u_1 = H ( m ) w \bmod{q}$ would return the same $u_1$ for  multiple hash values. In general you only want one hash to succeed, even if it is unlikely that an adversary can generate a hash that equals $n q + H(m) w$.

Of course this means that any hash with the leftmost bits identical to the org. hash is also acceptable, but at least you don't have to perform $\bmod{q}$ over an extensively large number.

For modular arithmetic any input (base value for modular exponentiation) larger than the modulus contains spurious information.


What operations provide perfect secrecy other than modulo addition As far as I know OTP is the only algorithm proven to provide perfect secrecy. It can work with XOR which is addition modulo 2 and obviously it can work with additions modulo N. What other operations enable perfect secrecy? Can we for example have randomized tables to define the mixing of data and key and still prove the perfect secrecy property of OTP?

Any group operation works for a one-time-pad if you can shoehorn a message uniquely into a group element—addition modulo $n$, multiplication modulo $n$ if you can uniquely encode a message block as an integer coprime with $n$, addition or multiplication in finite extension fields, invertible matrix multiplication over finite fields, whatever group you want—and can be extended by a direct product to arbitrary-length messages: if you have a group operation $m \oplus k$, then you can extend it to an $\ell$-block message $(m_1, m_2, \dotsc, m_\ell)$ with an $\ell$-block key $(k_1, k_2, \dotsc, k_\ell)$ by $(m_1 \oplus k_1, \dotsc, m_\ell \oplus k_\ell)$.  Conventionally we talk about addition modulo 26 in English, or use addition modulo 2 for computers, of course.

Going beyond the one-time pad approach, to encrypt a $t$-bit message, you could choose a permutation $\pi$ uniformly at random from all $2^t!$ possibilities; then the one-time cipher $m \mapsto \pi(m)$ has ‘perfect secrecy’ too.  Of course, it's tremendously inefficient even compared to a one-time pad!  (Bonus: You could get built-in authentication with forgery probability bounded by $2^{-f}$ by using $m \mapsto \pi(m \mathbin\| 0^f)$.  Of course, still much cheaper to compose a one-time pad and one-time authenticator…)


How to use HMAC for large ciphertexts over TLS HMAC used to secure chosen cipher-text attacks. if we are encrypting a large file (video) and sending it over TLS for decryption, how server can check MAC for ciphertext when we didn't sent whole of ciphertext yet ?

Well, when TLS encrypts a stream of traffic, it breaks up the data into records.  Each record contains up to 16k of data, and includes its own HMAC.  Hence, there is no HMAC over the entire downloaded file; instead, there are a series of HMACs; every single byte of data is covered by one of those HMACs.


Safety when disclosing hashes of secrets used to calculate other secrets In my application, I am generating a big random number and publishing a SHA256 hash of it. After the hash it published (but not the secret), anyone can submit any number, and the system will calculate and present them a SHA256 hash of the number derived by concatenating their number at the end of the secret number from my system (SHA256(A+B)). The result of that operation should not be guessable without the secret number.

I am wondering if there are any security concerns with this approach that I should be weary about, such as if the random number is of certain length, would that make the result guessable? Or is this approach cryptographically safe?

The security concern is that the result of that operation will be guessable without the secret number, since the later part of that answer explains why it also applies to SHA-256.

(Also, $\:$ SHA256(A+"") = SHA256(A)$\:$.)

The random number should be long enough to make brute-force highly infeasible.

If it is and you publish HMAC(A,"") and present them with the values of HMAC(A,B),

then the result of those operations should not be guessable for non-empty strings B.


How to change the policy value of a CA identity in apple keychain? According to this guide, I made an intermediate CA, and successfully used it to sign app in Windows. However, after converted it into a Apple keychain (by this guide), this CA become having an "iChat" policy, which cannot be used to code signing:

$ security find-identity -p ichat /path/to/my_keychain
Policy: iChat
  Matching identities
  1) XXXXXXXXXXXXXXX "my_identity" (CSSMERR_TP_NOT_TRUSTED)
     1 identities found

  Valid identities only
  1) XXXXXXXXXXXXXXX "my_identity" (CSSMERR_TP_NOT_TRUSTED)
     1 identities found

So, how to make it to have "codesigning" policy? Thanks for a lot!

====

Yesterday I tried some more works. After reading the x509v3_config manual, I modified the CA generation, and the resultant intermediate CA has following attributes:

$ openssl x509 -in my_cert.pem -noout -text
Certificate:
    ......
    X509v3 extensions:
        X509v3 Subject Key Identifier:
            ......
        X509v3 Authority Key Identifier:
            keyid:......

        X509v3 Basic Constraints: critical
            CA:TRUE, pathlen: 0
        X509v3 Key Usage: critical
            Digital Signature, Certificate Sign, CRL Sign
        X509v3 Extended Key Usage:
            Code Signing
......

And I re-generated the keychain file:

$ rm my_keychain
$ certtool i my_cert.pem k=`pwd`/my_keychain r=my_private_key.pem c

However, the CA in keychain is still recognized to only have iChat policy.

In Keychain Access.app highlight the certificate, then "Get Info" ( ⌘ i ):

  Under "Trust" select "Code Signing" > "Always Trust"


Use of less than secure random numbers for 'a' during an SRP proof of password With Secure Remote Password protocol SRP6a random numbers are used for s, a and b. Where s is the salt registered with the user, a and b are random one time ephemeral keys of the user and host respectively. What would be the risk of letting some clients (old webbrowsers which don't have the WebCryptoAPI secure random numbers) perform a password proof using a which is less random than a good secure source. Lets say that they use the web browsers insecure Math.random and that is seeded with a timestamp.

Superficially if a was simply a nonce, not even a weak random, then an attacker can gain very little. With each login attempt a unique B is sent by the server which can always use secure random numbers. This random B is used with the nonce a to create a new S, then from that a new M1 and M2 proof of a new shared key.

Or is it the case that a being less than a high quality secure random would compromise the security of either the client or the server.

(Edit: Note that sending a from the server opens you up to a server sending a crafted a, s and B to attack the password using a dictionary lookup of M1 to give the password so that is not something that anyone should consider doing. The question is about whether a needs to be truly random not a question about suggested sources of secure random numbers for a)

It seems like a better solution would be to have the server that is providing the Javascript file, also provide a random seed.  The Javascript can then use that random seed (and anything other maybe-random bits it can scrounge up, such as the output from Math.random()) to see a cryptographic PRNG, and then use the output of that crypto-PRNG for generating s, a, b.  After all, the server who sends you the Javascript has to be trusted anyway, so you might as well trust it to give you some random numbers, too.

See https://security.stackexchange.com/a/34425/971 for more on this.


Can the SHA256 hashes of consecutive integers be attacked? Suppose that the attacker knows the SHA256 values of integers $n, n+1, n+2 ... n+k$.

$n$ is sufficiently big, so we do not expect to be able to brute force $n$ just by $\operatorname{SHA256}(n)$ itself. $k$ is very small compared to $n$.

Is there risk that he can calculate $n$ in reasonable time?

If we assume that the range of possible values of $n/k$ is sufficiently large that it is infeasible for the attacker to scan through $\operatorname{SHA256}(ik)$ values (and look for a match in one of the hashes), then it would appear to be secure.  There is no known weakness in SHA256 about hashing related messages.


Ciphertext notation where the ciphertext consists of two parts I've see in several places (here or there) the notation $c = (U, V)$ or $c =\langle U, V \rangle$, where $c$ is a ciphertext (to be transmitted).

But as both $U$ and $V$ are "key-like". I can't find if the key to be used on the other is $U$ or $V$.

From the context, I guessed it means "Encrypt $V$ with $U$ (ie the key) to produce $c$".

Can anyone confirm me this ? They are quite commons notations, but I can't find their meaning.

$c = (U,V)$ means that the ciphertext is actually a tuple, made of two parts, $U$ and $V$. It is very common to have ciphertexts that are actually tuples of elements. In this particular case, this scheme is reminiscent to Hashed ElGamal, where ciphertexts are composed of two parts: $U$, which essentially encodes the randomness used, and $V$, which contains the message XORed with a hashed value.

Apart from that, note that, in general, a ciphertext never includes the key...otherwise, they would be trivially decrypted. The key or keys needed for decryption are separate values, and must be kept secret by the intended recipient of the ciphertext.


Preimage resistance hash in digital signature I'm studying about preimage resistance property of the hash functions.
In particularly I'm reading as the missing of this property can be fatal in digital signatures that use RSA.

Further details:

Let $e$ be the public exponent, $d$ the private exponent and $n$ the modulus.

Let be C the attacker.

C could compute:

$y= z^e \mod n$
with $z$ random number, then he could find a $m'$ for the which $h(m') = y$ and finally
to state that Bob has sent {$m'$, $z$} where $m'$ is the message and $z$ is the digital signature.

Here my doubts:

C could choose $m'$ if he could compute:
$h(m') = y$ (the compute is easy, suppose that h is public) and resolve this equation;
$\log_x y = e$ (there is also $\mod n$ in this equation).
This problem seems similar to discrete logarithm but it is different.
In this case the unknown is the logarithm base.

I think that this problem is computationally intractable, do you confirm?

I'm having a hard time parsing your question.

If C can compute pre-images on $H$, then he can forge digital signatures from Bob. All C needs is one signature from Bob.

Bob signs message $m$, the signature is $S={H(m)}^d\bmod n$. All C needs to do is find an $m'$ where $H(m)=H(m')$. The forged message and signature will be $m'$ and the original $S$.


What are the advantages of mutual private set intersection methods over finding the intersection of hashed lists? I can understand the usefulness of one-way private set intersection methods. Where Alice and Bob both have listed but only Alice learns the intersection of those lists while Bob learns nothing.

I don't understand the usefulness of two-way private set intersection protocols though. If Alice and Bob both learn the intersection of their lists, can't the same result be achieved by a much more simpler method of using a one way hash on the lists, exchanging them and allowing each party to compute the intersection?

What are the privacy advantages of more complicated protocols? I feel like I'm missing something simple here...

I found this related question, however, none of the answers seem to address the question of whether these more sophisticated protocols offer security advantages over the matching hashes method.
Private set intersection, using a semi-trusted server

Naive hashing protocol

Suppose Alice has items $x_1, \ldots, x_n$ and Bob has items $y_1, \ldots, y_n$. In the naive hashing protocol, they agree on a common hash function $H$, and Alice sends $H(x_1), \ldots, H(x_n)$ to Bob. Bob can compute $H(y_1), \ldots, H(y_n)$ and then calculate the plaintext intersection between these two lists.

Insecurity of naive hashing

First of all, there is nothing inherently symmetric about this protocol. Bob doesn't have to send $H(y_1), \ldots, H(y_n)$. If he doesn't, then Alice doesn't learn anything. I think two-sided output vs one-sided output is a red herring for this question.

The naive hashing protocol is vulnerable to the following kind of attack. Suppose that after the protocol is finished Bob learns of a special value $v$ that he couldn't have predicted before the protocol (e.g., the $x_i$'s and $y_i$'s are email addresses and he just learned the email address $v$ of an important person, which he didn't know before). Now Bob can test with certainty whether $v$ was in Alice's set, by checking whether $H(v)$ was among the values she sent. The protocol continues leaking information after it's over.

In the extreme case, the $x_i$ values can come from a small domain (e.g., phone numbers, SSNs) and Bob can simply do an exhaustive brute force attack to learn all of Alice's $x_i$'s.

Difference with secure PSI

The important property of real PSI protocols is that they prevent this kind of an attack, where one of the parties can check after the fact whether their opponent was holding some value. In a truly secure PSI protocol, if Bob wants to know whether Alice has an item $v$, he has to include $v$ in his set at the time of interaction. It should do him no good to speculate about $v$ after the protocol is finished. The PSI protocol leaks the intersection of $X \cap Y$ once, and no more information about $X$ and $Y$ is leaked thereafter.

Example / better mental model for PSI

A good way to think about PSI protocols is that they do the naive hashing protocol, except the common hash function $H$ is something that requires a secret key from both parties. Something like $H(x) = H_{\alpha,\beta}(x)$ where $\alpha$ is a key that only Alice knows and $\beta$ is a key that only Bob knows.  Since both parties contribute a secret key to the computation, you have to assume that Alice & Bob have a way of computing such an $H$ interactively, in a way that no one learns the inputs to $H$ -- only the outputs.

(Note: not all PSI protocols actually work this way, but this approach is secure and it gives the right intuition about PSI security.)

If Bob tries to do this after-the-fact attack, he will find that he can't compute $H(v)$ on his own. He doesn't have Alice's key to this $H$. This is why the computation of $H$ was interactive in the protocol. And, since the protocol has terminated, Alice will not agree to help compute $H$ on additional inputs.


What does K stand for in frequency analysis It was from frequency analysis lecture and the professor mentioned but I cannot recall.
The K value for English was .067, German was .076. The lowest K was Russian which was .056. When the frequency is uniform among 26 letters, then K is .038.
What is the complete word that K stands for?

It probably refers to the Index of coincidence, or more accurately the un-normalized index of coincidence, referred to in the Wikipedia article as "kappa-plaintext".


Explaining Chaotic Cryptography I will venture myself into studying chaotic cryptography. However, I find it hard to explain what chaotic cryptography entails to those that have some knowledge of cryptography. Neither can I explain it - at a more basic level - to those that don't know what cryptography is.

Can you help me explain chaotic cryptography to others?

Explain the problem that the solution of "chaotic cryptography" is intended to solve

You have the question tagged with encryption, cryptanalysis, and symmetric. So it sounds like it is a method of symmetric encryption.

Explain why other pre-existing solutions are unsatisfactory

e.g. they're slow, not provably secure, not well understood, etc

Make sure these points are actually true and supported by references

Explain the algorithm and how it is an improvement or why it is a better solution than previously listed solutions

Explaining the algorithm may be lost on people who have no experience with cryptography, especially if they have no experience with math or algorithms in general. But the guts of what the algorithm does is not always as useful as what the algorithm accomplishes.

Note

I was going to leave this as a surprise to the user who asked the question, but it has been noted that the answer should state so explicitly:

Attempting to pursue this strategy with "chaotic cryptography" is going to fail at step 2 and step 3.

This is not because the strategy is insufficient, it is because there are no good reasons to pursue "chaotic cryptography".

Currently employed symmetric encryption algorithms are efficient, provide provable resistance to known attacks, are well understood, and importantly are standardized for public use.

To quote Geoffroy Couteau:

  There have been almost no (if any) serious work on chaotic crypto providing any tool to base its security on clear and well-defined fundamental problems which resist cryptanalytic attempts. Today's chaotic crypto is at best a buzzword variant of the security-by-obscurity approach to crypto, which consists into thinking that "well, if we do many complicated stuff, that's probably hard to invert".

"Chaotic cryptography" is frequently coupled with "image encryption", and the latter demonstrates lack of understanding of basic principles of information theory and programming: There are no special requirements when encrypting images as opposed to any other types of information. Symmetric ciphers simply operate on bits.


Obtain 384 bits from a 256bit MasterSecret I'm currently implementing, with crypto++, and AES tranmsission system, whose key is based on a previous MasterSecret of 256 bits (which has been expanded using PBKDF2).

This MasterSecret is then split into a key and an iv, to encrypt a message using AES-GCM.

I must work with AES-256, so my key must be 256-bit long. The iv for GCM is always 128-bit long.

So, briefly, I must extract from a 256-bit MasterSecret a 256-bit key and a 128-bit IV.

How to do it ?

I thought of taking the MasterSecret as the key, and then hashing the key to get then the iv of the desired length.

Is there a more efficient/elegant way to obtain 384 bits from a 256 bit MasterSecret ?

You don't actually need 384 bits of key material.  The IV for GCM does not need to be secret, and may be chosen deterministically, e.g. as an incremental counter.  Thus, you only need 256 bits for the AES key, which you already have.

That said, if you did actually need more key material, you could use any standard KDF to expand your 256 bits.  Since you presumably already have a 256-bit hash function available (for PBKDF2), I'd personally suggest using HKDF-Expand.  Since your master secret is already a pseudorandom bit string, you may safely skip the Extract part of HKDF; see §3.3 of the RFC.

(You could also request more bytes directly from PBKDF2, but this is rather needlessly inefficient.  If you need more than one hash block of output from PBKDF2, it's better to combine it with a key-based KDF such as HKDF.  Technically, you could also use a second PBKDF2 pass with an iteration count of 1 instead of HKDF, but this feels a bit "untidy", as PBKDF2 was not really designed to be used like this.)


Hashing large messages, how does it work? Is the message divided into chunks, each chunk hashed separately, or something else?

While hashing, the messages are divided into chunks and padded so that a message is fit into the chunks, properly. For example in SHA-256 the message appended 1, then many zeroes and finally the message size in 64-bit added. The total size must be $x$ multiple of 512 where $x$ is minimum.

No, they are not separately hashed, they are chained. If not it how would you combine the output? If you don't combine what is a hash there? There is actually, hash trees famously know as Merkle Trees used to verify data blocks, or many files where you only keep the root hash.

SHA-256, for example, uses  Merkle–Damgård (MD) construction in which a compression function $F$ which is

$$F:\{0,1\}^{256}\times\{0,1\}^{512}\to\{0,1\}^{256}$$

The 512-bit input space is the message space. 256-bit input space is the previous hash, if it is the first block then an IV is used.

let $$M\mathbin\|pad=m_1\mathbin\|m_2\mathbin\|\ldots\mathbin\|m_\ell $$ $$H_i = F(m_i,H_{i-1})$$ with $H_0 = IV$ then

$$\operatorname{SHA-256}(M||pad) = F(m_\ell, F\ldots F(IV,m_1)\ldots))$$

This tells you about the MD construction, MD5, SHA-1, SHA-2 uses MD. There is also sponge construction that SHA-3 is based on, which left the OP as an exercise.


Partial Homomorphic Schemes that are probabilistic As mentioned in wikipedia there are many Partial Homomorphic Encryption(PHE) scheme like RSA, Elgamal, Pailler etc.

Pailler encryption scheme seems to be probabilistic

Are there any other PHE schemes that are probabilistic in nature ?

Actually, only probabilistic schemes will be of interest, since all other schemes (such as the "plain" homomorphic version of RSA) will not provide semantic security. This is problematic, because for many applications of homomorphic encryption plaintext messages can then easily be guessed by "trial encrypting" potential candidates and comparing the ciphertexts. So you want only schemes that are IND-CPA secure.

Yes, Paillier is probabilistic by nature. ElGamal is also probabilistic by nature and as already said by Chris Peikert in the comments it provides IND-CPA security if used correctly (although the homomorphism may then not be of interest for practical applications anymore).

The impossibility of IND-CCA2 secure homomorphic encryption follows this argumentation: Recall the IND-CCA2 game. In the IND game, the avdersary submits two distinct messages $m_0\neq m_1$ and the challenger flips a random bit $b$, encrypts $m_b$ and gives the ciphertext to $m_b$ to the adversary. Now in the IND-CCA2 setting the adversary has access to a decryption oracle in the pre- and the post-challenge phase. Let us now consider the scheme is homomorphic. Thus the adversary can take the challenge ciphertext and any other message of its choice, say $m'$, compute the corresponding ciphertext and perform the homomorphic operation on the ciphertexts corresponding to $m_b$ and $m'$. Then, the adversary submits the resulting ciphertext to the decryption oracle (it is allowed to do so because the restriction on the decryption oracle is only not to submit the challenge ciphertext). Then, when given the plaintext message from the decryption oracle the adversary simply undoes the operation (from the homomorphism) with $m'$ on the plaintext space and if the resulting message equals $m_0$ it outputs $0$ and $1$ otherwise. Consequently, the adversary wins with probability $1$.

So the best you can hope to get for homomorphic schemes is IND-CCA1 security (so called lunch-time attacks, where the adversary has no longer access to a decryption oracle after seeing the ciphertext corresponding to the challenge message).


Galois field step in XEX mode I'm reading through the XEX mode spec, and I want to make sure I've understood the $\alpha^j$ step correctly:

$X = E_K(I) \oplus \alpha^j$

$C = E_K(M \oplus X) \oplus X$

where:

$M$ is the plaintext message
$I$ is the number of the sector
$\alpha$ is the polynomial $2^n$ over the finite field $GF(2^{128})$
$j$ is the block index within the sector

So, to compute $\alpha^j$, assuming that my language has native 128-bit int support, I envision something like this:

UInt128 a_j = 1 << (j % 128);

Is this literally it, or am I missing a key point here?

$GF(2^{128})$ is a finite field with $2^n$ elements. There are a number of ways to represent this field. For example, a binary vector of length 128, or polynomials of degree 127 where the coefficients are 0 or 1. You could even choose to represent them as integers between $0$ and $2^{128}-1$. These are the elements of the finite field. In addition to the elements you need two operations, call them $\boxplus$ and $\boxdot$ (we often call them addition and multiplication). To be a field, the elements must be closed under both operations, associative under both operations, commutative under both operations, there must exist an additive and multiplicative identity, there must exist additive and multiplicative inverses for every element, and multiplication must distribute over addition (see this for additional details).

So for a given representation, you must specify what $\boxplus$ and $\boxdot$ mean and show that the properties I just listed hold.

It is very tempting to want to think of $GF(2^{128})$ as simply the integers modulo $2^{128}$ ($\mathbb{Z}_{2^{128}}$). Part of this probably comes from the fact that $\mathbb{Z}_p$ where $p$ is prime, is in fact a finite field. It turns out that $\mathbb{Z}_{2^{128}}$ is not a finite field. In other words, using integer addition and multiplication modulo $2^{128}$ does not get us all the properties listed above.

So, $\alpha^j\neq 1<<j\ \%\ 128$. You could represent $\alpha$ as a 128 bit integer, but the operations to compute $\alpha^j$ would be very different from simple integer arithmetic. I'd suggest using a finite field library. For more details on the arithmetic, see the other question you asked.


When to use safe prime or Schnorr group Protocols that use $\mathbb{Z}_{p}^*$ arithmetic often choose $p$ to be a safe prime ($p = 2q + 1$, for prime $q$) or to have the Schnorr group form ($p = rq + 1$, for prime $q$). I understand that the reason for this is to  prevent the Pohlig–Hellman algorithm.

It appears that both are safe as long as $q$ is big enough. However, from what I've seen, safe primes are commonly used for Diffie-Hellman, while Schnorr group primes are used for DSA. (For example, the dhparam and dsaparam OpenSSL commands).

My question is: what is the reason for that? I see that Schnorr group primes are more efficient, since $q$ is smaller, making exponentiations faster. But if that is the case, why it seems to be avoided in Diffie-Hellman? Is it safe to use Diffie-Hellman with Schnorr group primes, or DSA with safe primes?

(This question is partially included in ElGamal and Schnorr groups, but was not answered there)

Is it safe to use Diffie-Hellman with Schnorr group primes, or DSA with safe primes?

Safe, yes; efficient, no.

For DSA, that signature algorithm includes a clever trick that reduces the size of the signature to twice the size of the subgroup (the size of $q$).  Because of this, we want to reduce the size of the subgroup as much as possible (without cutting into security).  You could use a safe prime, but that means that the signature would end up being much larger than required.

For DH, there is no corresponding clever trick; the key share is the size of $p$.  However, there are two things which allow a performance difference:

We use use a small $g$ (often $g=2$); such a $g$ has order $q$, and so works perfectly well.  Such a small $g$ makes the initial modular exponentiation cheaper.  In contrast, with a Schnorr group, you have to use the $g$ which came with the group (which will be larger)
We can safely reuse private exponents.  With a safe-prime, if someone gave us a bogus key share, they could deduce the lsbit of our private exponent, but nothing else; hence, the leakage is minimal.  In contrast, with a Schnorr group, they can deduce our private exponent modulo $s$ for every small $s$ which is a factor of $r$ (where $p = rq+1$ is the Schnorr group); you could defend against this by either selecting $r$ is 2 times a prime (I haven't heard of someone doing that, but they could), or by raising the key share to the power of $q$ (which would eliminate any potential performance gain by reusing the private exponent).

You state that Schnorr groups are more efficient because $q$ is smaller; that is not true, because with a safe prime, there is no reason to select your private exponent randomly from the entire range $[1, q-1]$; you can select from a smaller range (for example, the range you would use if you used a Schnorr group); there's no known discrete log method that could use the additional information.


What causes first block of AES decryption to be garbled, even with correct IV? I am attempting to duplicate wireshark's packet capture decryption for a TLS HTTP session, where I control the private key of the server.

The cipher suite number is 0x00002f, TLS_RSA_AES_128_CBC_SHA

I wrote a utility that takes apart the packet captures using libpcap, and so far can match what the logs from wireshark say they have in terms of MAC keys, Write keys, and IV's; printing out the binary data as hex characters.

Visually, I can confirm that the keyblock and ciphertext are identical to what wireshark's log display.

However, after I perform the following decryption steps:

... decrypt pre_master_secret, generate keyblock
... initialize cipher context

EVP_CIPHER_CTX_init(&myevp);
if (!EVP_CipherInit_ex(&myevp, cipher, NULL, wKey, IV, 0))
    LogError("evp_cipherinit_ex:", ERR_error_string(ERR_get_error(), NUL));

dec = EVP_DecryptUpdate(&myevp, outb, outlen, data, datalen);
totalcount += outlen;

if (!dec)
    LogError("evp_decryptupdate:", ERR_error_string(ERR_get_error(), NUL));

if (dec && blocklen != 1) {
    dec = EVP_DecryptFinal_ex(&myevp, outb + totalcount, outlen);
    totalcount += outlen;
}

...get padding from last bit of outb, and remove padding from outb (plaintext)
...remove the MAC from the plaintext

The resultant plaintext I get is identical to what wireshark spits out in their logs, with the execption of the first block of decrypted data.

I know that in general, this is usually caused by not having a correct initialization vector when you begin the decryption.  However, all my computed keyblock values seem correct (that is to say, they jive with what wireshark is spitting out).

here's the first few blocks of what wireshark shows...

Plaintext[432]:
47 45 54 20 2f 68 65 6c 6c 6f 2e 68 74 6d 6c 20
48 54 54 50 2f 31 2e 31 0d 0a 48 6f 73 74 3a 20
31 37 32 2e 31 36 2e 32 34 34 2e 31 39 36 0d 0a
...

and mine

plaintext_update[432]
e1 a2 f4 b3 2a 93 d1 c4 1b f4 60 d8 c9 92 03 25
48 54 54 50 2f 31 2e 31 0d 0a 48 6f 73 74 3a 20
31 37 32 2e 31 36 2e 32 34 34 2e 31 39 36 0d 0a
...

It's just that first block.  I can verify before the Decryption step that the evp context has the correct original IV value and the current are there.

LogData("evp oiv", &myevp->evp.oiv, &myevp->evp.cipher->iv_len);
LogData("evp iv", &myevp->evp.iv, &myevp->evp.cipher->iv_len);

here's the one from wireshark

Client Write IV[16]:
8b 55 c0 c5 3c 77 dc 91 09 22 18 8b 0c 53 16 66

here's mine

evp iv[16]
8b 55 c0 c5 3c 77 dc 91 09 22 18 8b 0c 53 16 66

Likewise, the keys are the same. I don't think I need to illustrate those values, as the remaining blocks do decrypt correctly.

I've also checked to make sure that first block isn't gzipped, or whatever.  I checked the wireshark code, and they are doing the same equivalent stuff I'm doing, albeit in libgpgcrypt.

Anybody ever seen anything like this?

For TLS the IV for the first packet is generated from the shared secrets; quoting the RFC 2246:

  To generate the key material, compute

  key_block = PRF(SecurityParameters.master_secret,
                     "key expansion",
                     SecurityParameters.server_random +
                     SecurityParameters.client_random);

  until enough output has been generated. Then the key_block is
    partitioned as follows:

  client_write_MAC_secret[SecurityParameters.hash_size]
  server_write_MAC_secret[SecurityParameters.hash_size]
  client_write_key[SecurityParameters.key_material_length]
  server_write_key[SecurityParameters.key_material_length]
  client_write_IV[SecurityParameters.IV_size]
  server_write_IV[SecurityParameters.IV_size]

I suppose that you have generated these, and checked them?
(You need 6 ·16 bytes in your cipher suite, and the last 32 are the IV's, one for each direction.)

Also, the IV for the next TLS-record is the last cipher text block of the previous record in the same direction. So you need to keep track of these as well. So the first IV is never sent, and you need to keep updating the IV as we get new packets in, or send new ones.


How do I generate a number for a lottery and later proves its existence I want to create a lottery that works like this: I choose a secret number A in the range [0:999] and publish an object B. People must try to guess the number A to win. When somebody wins, I want to publish an object C. The object C shall now together with B prove the existence of A, such that people know that A was determined from the beginning of the lottery.

Calculating A given B should be either impossible or unfeasible due to computational requirements.

I don't know much about cryptography, but have come up with the following proposal on my own:

p1, p2 = large prime numbers chosen at random, where p1 < p2
f = a hash function: N x N -> {0, 1, ..., 1000}

A = f(p1 | p2)
B = (p1*p2, f)
C = p1

My idea is that given B, it is easy to calculate A if C is also known, but computationally hard without C. Note that both the hash function and the product of p1 and p2 is given as the object B.

What do you think about my proposal, will it work? Is there any better or simpler methods?

You could use HMAC for this. HMAC is available in pretty much every crypto library out there.

The process would work like this. Randomly pick A and C. For simplicity, let's assume they are strings (of any length). Compute $B=HMAC(A,C)$. Publish $B$. Once someone guesses $A$, you publish $C$. Anyone can then verify that $B=HMAC(A,C)$.

As long as a good hash function is used, and $C$ is sufficiently long (say 128 bits), knowing $B$ should not help anyone compute $A$.

The benefits of doing this over what you propose in the question is that it is much simpler, faster, and the values generated are much smaller. For factorization to be hard enough, your primes will have to be around 1000 bits each.


Are modified implementations of cryptographic algorithms a good idea? Are modified implementations of standard cryptographic algorithms better that the standard versions?
Since the algorithm is not standard, is it harder to break? Is it safer?

No, modified algorithms they are unlikely to be harder to break, unless the changes were explicitly made by a cryptographer to make the algorithm more secure. They are certainly not any safer just because they are different.

Due to the Kerckhoff principle you should assume that the algorithm is known. So changes in the algorithm in itself does not increase security;
If there is a trivial change made then all the attacks on the algorithms are still valid;
If it is a non-trivial change then the algorithm requires a new security description or proof; basically it should be treated as a new algorithm.

Now in the latter case the algorithm could be safer of course, and many parts of the original security proof may hold. There are many algorithms that have been tweaked to a certain extend to make them more safe or more functional, often by their original authors. As example, for SHA-1 the original, untweaked variant called SHA-0 can be found in the wild.

But to change an algorithm without an explicit idea to fix the previous algorithm is not likely to make it more secure. Most of the time the algorithm will be less secure.

Note that even minor changes in the vectors (internal constants) of symmetric algorithms may completely destroy the security of algorithms. Often these tables were specifically created for the purpose of adding security. If you change one constant in there, you may already break security. Other specific constants may be as safe or even slightly more safe (see for example the changes made by the authors to many of the SHA-3 contestants). In other words, small changes may not equate to trivial changes.

If you change for instance the SHA-2 vectors of SHA-256 to a new, secure set, the you may make it harder to use rainbow tables. But if you use SHA-2 correctly then rainbow tables should not be an issue (because of using salt for password based key derivation). In this way, for very specific attack scenarios, using a modified algorithm may bring some localized benefit. But in general it would be wiser to change the key derivation primitive, of course.


Exchanging session keys over symmetric-key channel? I know session keys are exchanged (in SSL e.g.) over public-key cryptography channels but I was wondering if there are already known algorithms/methods for exchanging session keys over a symmetric-key channel? More specifically, is it possible/feasible to e.g. exchange 128-bit AES keys over a channel already using 128-bit AES keys?

If so, where can I read about them? IF not, why not? Is it not a good idea or can't be secured?

Possibly related: Deriving Keys for Symmetric Encryption and Authentication

With symmetric encryption, any key exchange protocol you run inside the encrypted channel must also be secure when run in plain text, if you want perfect forward secrecy. That means you can only rely on the previously established keys for authentication (you are using authenticated encryption, right?), but not for hiding the new keys.

Diffie–Hellman key exchange is probably the simplest option. Generate random keys, exchange the public parts inside the existing channel and derive the shared secret that you can use to derive any session keys you need. On its own it is vulnerable to MitM, but if you run it inside the authenticated channel you avoid that.

Related: Why do we need asymmetric algorithms for key exchange?


Why TLS uses in-band handshake signalling TLS uses handshake protocol to compute session keys to be used later to protect bulk of application data transfer. The handshake protocol and application protocol uses same transport layer port.

IPSec uses IKE for a key agreement between two endpoints. Here the key agreement protocol uses a separate UDP based transport channel. The data from applications is not sent through this UDP port.

In a way, IPSec uses out-of-band handshake whereas TLS uses in-band handshake.

Why TLS designers chose to use same transport layer port for both handshake and application protocol? What would be the implications if a TLS like security protocol is designed to run handshake and application protocols to run on different transport layer ports?

IPSec uses IKE for a key agreement between two endpoints. Here the key agreement protocol uses a separate UDP based transport channel. The data from applications is not sent through this UDP port.

Actually, I see two incorrect statements here

IPsec doesn't always use IKE to do key agreement.  Quite often it does, however there are real world implementations where IPsec is used with some other protocol.
Even if IPsec and IKE are used together, sometimes they use the same UDP port.  If they're are using NAT-T (RFC 3947, 3948), then all the traffic (both IKE and IPsec) will go through the same port.

However, to address your question:

  Why TLS designers chose to use same transport layer port for both handshake and application protocol?

I'm not Eric Rescorla, however I suspect they never really considered the possibility of using two separate ports for control and data.  If they had, they would have immediately seen that, for them, using one port was better because a) it simplified things for them, and b) they had no reason not to.

As for the simplified, for one, there's no ambiguity in the control records as to which data channel they're talking about.  In addition, TLS assumes that records flowing in the same direction are delivered in order, hence they don't need to worry about situations where they issue a control record, and then a data record, and the data record arrives first.  If they used different TLS ports, that would be a possibility that would need to be addressed.

  What would be the implications if a TLS like security protocol is designed to run handshake and application protocols to run on different transport layer ports?

There would need to take care about the concerns I mentioned above (not too hard), and they would also have to worry about middle boxes (firewalls, NAT devices) getting confused about the relationship of these two not-obviously-connected TCP flows.


Cryptographic hash where the hashing function input is similar to the result I was wondering if there is a cryptographic hash where the resulting hash is identical to the input for the hash function.

If this is the case, would it be a weakness in the hashing function?

If you mean that for all $x$, $H(x) = x$, this is usually known as the identity function.  It has the convenient property that it is guaranteed not only to be collision-resistant, but to have absolutely no collisions whatsoever.  However, it has the inconvenient property that finding preimages is slightly easier than one might hope, which one might consider to be a ‘weakness’.

That said, whether it is weak or not depends on what security goals you are hoping for it!  There are many kinds of things called hash functions, even in cryptography—universal hash families like Poly1305 and GHASH, message authentication codes like Poly1305-AES and AES-GMAC, stream ciphers like Salsa20, pseudorandom function families like SipHash, collision-resistant hashes like SHA3-256, password-based key derivation functions like argon2, etc.  But the identity function is usually not considered a hash function.

If you mean that there exists $x$ such that $H(x) = x$, called a fixed point of $H$, well, for a uniform random function $H$, what's the probability this can happen?  Let's suppose the input and output are $h$ bits long.  We can ask the complementary question of the probability that there are no fixed points, and note that for each distinct $x$ independently, $\Pr[H(x) = x] = 1/2^h$.  Then

\begin{align}
  \Pr[\exists x. H(x) = x]
  &= \Pr\bigl[\lnot \forall x. \lnot(H(x) = x)\bigr] \\
  &= 1 - \Pr[\forall x. H(x) \ne x] \\
  &= 1 - \prod_x \Pr[H(x) \ne x] \\
  &= 1 - \prod_x \bigl(1 - \Pr[H(x) = x]\bigr) \\
  &= 1 - \prod_x (1 - 1/2^h) \\
  &= 1 - (1 - 1/2^h)^{2^h} \\
  &\approx 1 - e^{-1} \approx 63\%.
\end{align}

So there are better than 50-50 odds that a fixed point exists in a uniform random choice of function.  We often use this to model functions like SHA3-256.  Does this indicate a weakness?  Well, there are two sides to this:

The traditional properties that we might think of when we hear ‘cryptographic hash function’ after reading Wikipedia without consulting any cryptography literature are preimage resistance, second-preimage resistance, and collision resistance.  Knowing a fixed point of SHA3-256 doesn't mean you can find preimages, second preimages, or collisions.  So in that sense, a fixed point does not indicate a weakness.  Indeed, it is very easy to find fixed points in the internal compression function of any Davies–Meyer hash function like MD5, SHA-256, etc., although that doesn't mean a fixed point on the full hash function.
On the other hand, the probability that you come upon a fixed point by happenstance in a single trial is $1/2^h$.  For, e.g., SHA3-256, this is unimaginably improbable for all imaginable numbers of trials—so the inference one might draw in practical terms is that there likely is a weakness in SHA3-256 that enabled you to find it, but the details would depend on how you found it and on details of SHA3-256, not on the general fact of a fixed point, and while it would cast serious doubt on the security of SHA-3, it might not actually have any practical consequences in any real protocols.