texts: What affect does the permutation layer have on the avalanche effect?

texts: If the permutation is not well thought out, how will this effect the cipher's avalanche effect. For example, if the permutation in PRESENT was in some way different (just made up without any thought) would this adversely affect the avalanche effect? How else might a poorly designed permutation adversely affect PRESENT or other block ciphers?


texts:
I'm a high school student taking IB and I'm doing my EE on Maths, more specifically on the effectiveness of Euler's totient function and Carmichael's totient function in RSA.

Am I right in thinking that Euler's and Carmichael's can be used interchangeably to generate the public key in RSA?
To compare their 'effectiveness' I will first compare the amount of time it takes to generate a public key using each function based on time complexity. Secondly, I want to compare the security of the public key (meaning 'how difficult it is to guess the private key given the public key'). But how? Is there an algorithm to use to test the security of an encryption key?

Many thanks!


texts: Is the CBC weakness in XML Encryption a new discovery? Are other applications vulnerable?

texts:
The RUB in Germany reports that XML encryption is broken.  This is essentially the W3C standard for protecting XML documents from prying eyes.

Does this mean that an attacker can only see a single message, or that they can actually infer the encryption key for all messages?

Is this a new vulnerability in CBC?

How is this relate to pre-existing applications that use CBC?


texts: Does AES-CTR require an IV for any purpose other than distinguishing identical inputs?

texts:
I'd like to encrypt files deterministically, such that any users encrypting the same plaintext will use the same key and end up with the same ciphertext. The ciphertext should be private as long as the plaintext is.

I plan to use AES-128-CTR with an IV of 0 and the SHA-256 of the plaintext as the key.

IV values are required to produce different output with the same key, but I am explicitly avoiding that behaviour here. I have heard that some ciphers/modes of operation also require the IV to provide randomness for the algorithm and that using an unrandom value (like zero) can be dangerous.

Aside from the repeatable output, is there any danger in using AES-128-CTR with an IV of zero?

Having done a bit more reading, here's my current understanding; verification or corrections appreciated:

NIST SP800-38A §6.5 describes CTR mode as just XORing each plaintext block with the result of ciphering the counter value with the key (where the initial counter value is called the IV).

If the a key is reused with the same IV (or a numerically-close one), this will will produce duplicate values in the stream with which your plaintext is hashed. This presents a large weakness to any attacker who can obtain multiple ciphertexts.

In my specific case, because I'm using a key that's unique to the plaintext it will have a unique stream of data to be XORed with the plaintext, making it secure.

The choice of zero for the IV is as theoretically dangerous as any other constant.


texts: Digital signature forging on a server, after entity authentication

texts:
Lets assume there is a guy called Ben, he contacts some server for a ticket number and the server returns a random number to him. Ben then signs that number and sends it back to the server, which checks if its valid or not and accepts Ben's connection if it is. Assuming Ben then signs and sends emails on this server using his private key.

Pretend he uses the same private key to log in to a server and sign his emails. How could Ben's emails be forged. Assuming that the authentication mechanism signs the bare challenge without hashing, while for emails Ben signs the hash of the message body.

Only idea that come to mind at this point is it could be more or less an attack such as a Kerberos attack, where a malicious entity pretends to be the server and gives false positives to Ben. It could also be a chosen message attack or possibly having used the onetime of ElGamal signature again. What other things could it be and if one were to run into such a thing, what could be done to prevent it happening?


texts: Differential cryptanalysis tutorial of Howard M. Heys

texts:
I am currently working on some research about differential cryptanalysis. There is a lot of literature about that topic in the internet. One of the most known paper is the tutorial on linear and differential cryptanalysis by Howard M. Heys. May be some of you know that paper, if not have a look here:

https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf

In the meanwhile I got a good idea about the attack and how it can be practically done. In the most tutorials on the net the process works a little bit different as by Heys. My focus here is the extraction of the key bits. This part is described in section 4.4 in the Heys paper. Heys starts the extraction at the end of the cipher, he wants to recover the last subkey. He is doing it by trying to decrypt the last round (How can the other keys be obtained? Heys does not tell about). As far as I currently understand the differential cryptoanalysis, it is not possible to encrypt single rounds (until now I read the paper of Heys). Because: All I have are some plaintext / ciphertext pair which I could obtain from the user of the cipher. The user encrypts with the key which I want to recover by doing the attack. So it should not be possible to obtain single outputs of a specific round or decrypt a single round by the user. (Me as an attacker should not be able to interfere the decryption and get input / outputs of a round while the user uses the algorithm)
Is my guess here wrong? How could the partial decryption could be done? I am referring to page 26 "A partial decryption..." and so on. Or what is Heys here doing?

Thanks for your attention and help.


texts: Question about IND-CPA with block cipher mode with random IV (CTR$ mutation)

texts: 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.


texts:
I'm trying to reverse engineer a key exchange protocol which is based on the Diffie-Hellman key exchange scheme and faced with the following problem:

Let $g$ be the generator, $m$ the modulus.

Alice has a private key $a$ and computes her public key $A = g^a\pmod{m}$.
Bob has a private key $b$ and computes his public key $B = g^b\pmod{m}$.

During exchanges Bob generates password check signature:

$C = f(A,B,password)$   where $f$ is cryptographic hash function.
$D = f(m,g,password)$
$X = \left(\left(D+A\right)\pmod{m}\right)^\left(C+b\right)\pmod{m} $

and then sends  $ f(X)$ to Alice.

Alice calculates $X$ on her side without $b$ and I can't figure out how.

Could somebody help me with the algorithm on Alice's side?


texts: Is it possible to break a hash-based block cipher?

texts:
Let's define the following block cipher:

$C_n = M_n \oplus H(k + n)$ where $C_n$ is the nth block of ciphertext, $M_n$ is the nth block of plaintext, $H$ is a cryptographic hash function, and $k$ is the secret key.

Decryption can be performed trivially, by computing $M_n = C_n \oplus H(k + n)$.

Assuming a proper mode of operation, such as CBC, how would we go about attacking such a scheme? Is this scheme provably as secure as $H$ is?


texts: Expressing a given linear transformation in Galois Field GF(256) in terms of another linear transformation with a different reduction polynomial

texts:
Before giving a better and detailed description of what I ask, let me first tell why I need what I am looking for: Intel processors already provide instructions (AES-NI) for very efficient AES MixColumns state transformation. Actually existing instruction performs a couple of steps combined  at once but it is easy to isolate MixColumn step and re-use it in isolated form. Standard AES MixColumn step being a linear transformation is represented in GF(256) with a 4x4 MDS matrix where reduction polynomial is x^4 + 1. This means that with Intel AES-NI, I can very very efficiently calculate the MDS matrix multiplication.

Suppose that I want to customize MixColumn step with a different linear transformation than the one AES standardizes. Then I will end up with a different MDS-custom (4x4) matrix as I will be using a different mixing polynomial and a different reduction polynomial.

Here is my primary goal: How can I implement my custom GF(256) matrix multiplication USING ALREADY AVAILABLE standard MDS matrix multiplication? Despite I am an engineer with some math ground university years are way too behind. Still I can "understand" basic matrix and/or GF algebra.

Maybe I should put it in that way: I am after implementing MDS-custom[4x4] * [s1, s2, s3, s4] with minimal computation which I hope would be possible if I express this transformation in a very simple-to calculate series of reusing MDS-original[4x4] * [s1, s2, s3, s4] results. Is there an algorithm to find the minimal-computation GF(256) transformation of a given transformation? MDS-custom = Some_Easy_To_Compute_Transformation_Of{MDS Standard AES}?

It would be pity if I cannot exploit standard MDS matrix multiplication (isolated) instructions for my custom MDS matrix.
Well if my custom MDS matrix would be simply k*MDS where k is in {GF(256), x^4+1} re-use would be obvious.Case when k is a [1x4] column vector is also obvious. But, first, my custom MDS might not be in that simple a relation with original MDS matrix, and secondly, my reduction polynomial is not x^4+1?
How should I proceed?


texts: TLS 1.3 clarification needed on hello_hash and subsequent hashes

texts:
I am exploring TLS, mainly from the server side at the moment. I am creating a server that will authenticate a client using TLS 1.3 and eventually I will be creating a client authenticating to a server. It is not intended for production, but merely for learning.
I am having a few question regarding the hashes, from what I understand hello_hash (used to calculate the handshake traffic secrets) would be :
Sha256( ClientHello[5:end] + ServerHello[5:end] )

and verify_hash (the one used to sign the certificate verification) would be :
Sha256( ClientHello[5:end] + ServerHello[5:end] + EncryptedExtensions[all] + Certificate[all] )

I am not sure if the 5 bytes record should be included in the verify_hash? We are excluding the ones from ClientHello and ServerHello, so I assumed that we should exclude this one as well?
and the handshake_hash (the one used to calculate the application traffic secrets) would be :
Sha256( ClientHello[5:end] + ServerHello[5:end] + EncryptedExtensions[all] + Certificate[all] + CertificateVerify[all] + HandshakeFinished[all] )

Again I am not sure if the record that encapsulate EncryptedExtensions, Certificate, CertificateVerify and HandshakeFinished should be included in this one, the documentation isn't very clear about this.
Finally, from the client side will the hash be the exact same as these ones? I mean the same order? I assume that they are as they probably need to match to create the matching keys and ivs


texts: Security of a security protocol for key exchange, using symmetric-key cryptography

texts:
This is an exam question:

$A \to B$: Alice, $nonce_A$

$B \to A$: $nonce_B$, $E_{k_{AB}}(nonce_A \| k_1)$

$A \to B$: $E_{k_{AB}}(nonce_B \| k_2)$
Alice and Bob both compute $k_s$ = $k_1$ xor $k_2$

$A \to B$: $E_{k_s}(...)$

$B \to A$: $E_{k_s}(...)$

The protocol is based on a long term secret $k_{AB}$ shared between Alice and Bob.The session, which begins at message 4, is supposed to be confidential and secure against reflection, replay, and re-ordering of the contents ( with $E_{k_s}(...)$ in step 4 and 5 can be anything as long as the protocol satisfy the above requirement).There does exist a flaw in the protocol, can you find it and explain why it constitute an attack on the protocol ?
I can tell that a man in the middle attack doesn't work because $k_1$ and $k_2$ are encrypted so the attacker can not know $k_s$ therefore can not continue to send messages to A and B after the authentication phase.
Another attack I can think of is when $nonce_A$ = $nonce_B$ a Dolev-Yao attacker can pose as B and send A $E_{k_{AB}}$$(nonce_A \| k_1)$ in message 3 then $k_s$ = $k_1$ xor $k_1$ = 0 then the attacker know $k_s$ then he can send message and decrypt message. But the chance $nonce_A$ = $nonce_B$ is very small so I'm not sure if it constitutes an attack.


texts: Even passwords are vulnerable to hash collision attacks?

texts:
As stated in this page large documents hashed using md5 maybe vulnerable to collision attacks. My question is even passwords of 6-30 character are vulnerable to such hash collision attacks? If yes, is there any proof available online or any example of two password phrase giving same md5 hash? I googled but of no help!.
Any how I am not going to store password hashed using md5, just asked this question out of curiosity.


texts:
Intro

For deduplication purposes, I need to split a stream of plaintext bytes into variable-sized chunks. The way this is traditionally done is using a rolling hash function defined over some window $w$ (e.g. 48 bytes). This window "slides" along the byte stream and is evaluated at each byte position, and when the value of the function is let's say $f(w) \equiv 0\ (\textrm{mod}\ 1024)$ a cutpoint is made, marking the end of the current chunk and beginning of the next one. The hash function is extremely fast to evaluate when the following is known:

The value of the rolling hash function at some window position
The byte entering the window
The byte leaving the window

The issue

Now if I encrypt each chunk and upload it to the server, I already leak some information about the plaintext:

The adversary knows that the hash value (a simple CRC32-like checksum) of the last $w$ bytes of each plaintext chunk $\equiv 0\ (\textrm{mod}\ 1024)$
All the other windows are hashed to a value $\not\equiv 0\ (\textrm{mod}\ 1024)$.

Related

Here is a similar question, but it seems people there did not realize that the hash value (output of the rolling hash function) is never published or known to the attacker. The only information disclosed is whether the hash value $\equiv 0\ (\textrm{mod}\ 1024)$ (true or false) for every window position in the input plaintext stream. So they recommend to use SipHash or $AES(f(w)) \equiv 0\ (\textrm{mod}\ 1024)$, but both solutions are just too slow compared to using the plain rolling hash.

There seem to be similarities with the hash-table flooding attacks, as the hash value is also never directly published. Besides the already-mentioned SipHash, Microsoft has proposed Marvin32 for this particular issue.

Questions

Besides the already mentioned solutions, what is the proper way to perform chunking without leaking information about the plaintext? Performance is very critical here though.
Would UMAC or Universal hashing have any application here?
Would this rolling hash function solve the information leakage on its own without encrypting the hash value with AES/SipHash? If not, what can be done to fix the information leakage? Pseudo-code for this hash function:

// My secret key, never shared or disclosed to anyone
var key = ....;

// Generate substitution table
var substitution = new uint32[256];
var substitutionKey = HMAC(key, SUBSTITUTION_SALT);
for (uint32 i = 0; i <= 255; i++)
{
    var randomBytes = HMAC(substitutionKey, UInt32ToBytes(i));
    substitution[i] = BytesToUInt32(randomBytes);
}

// Generate random irreducible polynomial of degree 33 (GF 2) and store it
// in a 32-bit register (33 coefficients, but the 33rd is implied because
// it's always 1)
// The algorithm is not shown here due to its complexity, but let's assume
// the polynomial is derived from the key
var polynomialKey = HMAC(key, POLYNOMIAL_SALT);
uint32 polynomial = RandomIrreduciblePolynomial33(polynomialKey);

// Hash an input window
uint8[] window = new uint8[48];
LoadPlaintext(ref window);
uint32 hash = 0;
for (uint32 i = 0; i < 48; i++)
{
    // Galois multiplication by x and subsequent reduction
    hash = (hash << 1) ^ ((hash >> 31) * polynomial);
    // Add the substitution polynomial
    hash = hash ^ substitution[window[i]];
}

...

// Now if we want to move the window forward by a single byte, there
// exist a very efficient algorithm that does that, but it's not
// relevant to the issue at hand


texts: What's the algorithm behind MySQL's sha256_password hashing scheme?

texts:
MySQL's old mysql_native_password hashing scheme was the equivalent of this in PHP:

sha1(sha1('password', true));

That's a hex-encoded SHA-1 hash of a binary SHA-1 hash of the password, without any salting.

MySQL 8.0 introduced a two variants of a new hashing scheme based on SHA256 called caching_sha2_password and sha256_password, the former being the default (docs). Despite their name, neither appears to be vanilla SHA256.

(Yes, I know SHA256 is not a great choice for password hashing, but it's a lot better than SHA-1 and it wasn't up to me!)

Here's an example. I created a hash for the password password, and it created a mysql.users password hash like this:

$A$005$wU"H/k5|5;f!kP_&N4cvqu6bppuYjCvqhg2blU.NcJHkkhaVj.QNt7pipg4p3

I'm guessing that (separating by $ chars), A means it's SHA256 (the scheme may support other SHA2 variants in future), and that the 005 is a salt, but the rest of the string isn't a common format - it doesn't look like either regular hex output or base64, nor is it raw binary.

Can anyone tell me the actual algorithms for these new schemes, in PHP or similar code?

Update

Thanks to @kelalaka for some important pointers, I had a crack at writing this in PHP:

$originalhash = 'wU"H/k5|5;f!kP_&N4cvqu6bppuYjCvqhg2blU.NcJHkkhaVj.QNt7pipg4p3';
$binaryhash = base64_decode($originalhash);
$salt_length = 20;
$hash_length = 43;
$rawsalt = substr($binaryhash, 0, $salt_length);
$rawhash = substr($binaryhash, $salt_length);

$password = 'password';
$iterations = 5;
$iteration_multiplier = 1000;
$it = $iterations * $iteration_multiplier;
$hash = $rawsalt . $password;
for ($i = 0; $i < $it; $i++) {
    $hash = substr(hash('sha256', $hash, true), 0, $hash_length);
}
$hashoutput = base64_encode($rawsalt . $hash);
var_dump($originalhash, $hashoutput);

However, this doesn't produce matching output:

string(61) "wU"H/k5|5;f!kP_&N4cvqu6bppuYjCvqhg2blU.NcJHkkhaVj.QNt7pipg4p3"
string(72) "wUH/k55fkPN4cvqu6bppuYjCvqgx75cg5UeVzAVpx0OzU7KS2Klujh3rbHzrAena3/MBAA=="

It's too long
I suspect the encoding scheme is not base64; notice the salt diverges from the original even though it is unchanged.
I'm not sure whether the starting string should be salt + password or password + salt.
I'm not clear when the truncation of the binary hash should be performed - in the loop, or after?


texts: How to prove that someone encrypted a specific (large) chunk of data

texts:
Alice encrypts her data with HER secret key. Then she sends the encrypted data to Bob who should encrypt it with HIS secret key.

Caroline should then eventually get this double encrypted data.
Caroline only wants to receive pseudo-random (looking) data which would only be decryptable for her if Alice and Bob BOTH tell her their secret key. She wants to be able to use this fact in court in case she and [Alice XOR Bob] get accused of deliberately saving and/or distributing intellectual property illegally.
Caroline therefore wants to be sure that Bob really takes the encrypted data of Alice, encrypts it with HIS secret key and then sends it to her.
How can that be achieved?
Alice and Bob are allowed to use different encryption algorithms.

I suppose AES is not suitable for this task.
I hope I was somehow able to express what I want in a comprehensible way.
I know, my English is bad.


texts: How can blockchain ensure uniqueness of a digital asset like a photograph?

texts:
If I take a picture with my beloved camera, the RAW file can be put into a blockchain, and thus it will have a unique hash.

If that unique hash is ever spotted anywhere we know it's a copy of my photo.

But if someone wants to steal my photo, they could just change a tiny bit of information in the RAW file, and it would result in a new unique hash.

So how can cryptography or the blockchain be used to protect digital assets?


texts:
I'm studying the Goldreich-Goldwasser-Micali construction from pseudo-random generators to pseudo-random functions. In this specific construction, assume $G:\{0,1\}^n\rightarrow \{0,1\}^{2n}$ is a PRG, mapping $x$ to $G(x)=(G_0(x),G_1(x))$. Then the PRF in this construction is given by
$$F_k(x)=G_{x_n}\circ\cdots\circ G_{x_1}(k),$$
with a random key $k$ in the same length as $x$. The proof is a hybrid argument, by replacing $G_{x_j}\circ\cdots\circ G_{x_1}(k)$ with a truly random function $\{0,1\}^j\rightarrow\{0,1\}^n$.

Now I wonder what if we swap the positions of $x$ and $k$ in this construction, that is to define
$$F'_k(x)=G_{k_n}\circ\cdots\circ G_{k_1}(x).$$
Intuitively one cannot use similar hybrid techniques like above to prove its pseudo-randomness. However I didn't figure out a counter example, as I wanted to keep some information of $x$ within $G(x)$, but the possiblility that this information is maintained after $n$-round of iterations is always negligible. For instance, if we keep the first bit of $G(x)$ being $x_1$, with only $2^{-n}$ probability we can still see the bit $x_1$ in $F_k'(x)$, when $k$ is random.

Are there any methods to prove or disprove the construction $F'_k(x)$ is pseudo-random? Thanks in advance.


texts: How to measure performance for ABE Schemes

texts:
I have these 3 Schemes:

1) J. Bethencourt, A. Sahai, and B. Waters, "Ciphertext-policy attribute-based encryption"

2) F. Guo, Y. Mu, W. Susilo, D. Wong, and V. Varadharajan, "Cp-abe
with constant-size keys for lightweight devices"

3) L. Ibraimi, M. Petkovic, S. Nikova, P. Hartel, and W. Jonker, "Ciphertext-policy attribute-based threshold decryption with flexible delegation and revocation of user attributes"

How can i measure the performance of a scheme in a network ? (i.e scalability, number of users (producers and consumers) supported, number of contents supported) ? How can i make the performance graphs and charts of a scheme ? Are there tools and tutorials ?


texts: What makes RSA secure by using prime numbers?

texts:
I am just learning about the RSA algorithm. Looking at the first two steps:

Choose two distinct prime numbers $p$ and $q$.
Compute $n = pq$.

I have some probably stupid questions:

Why do $p$ and $q$ have to be prime numbers? Why couldn't they be any integers or odd integers? Or does that break the whole algorithm?
Because prime numbers are rare in comparison to regular integers, does restricting the algorithm to only prime numbers reduce security? It would seem easier to find the private key if an attacker knows it's only going to be some prime number?


texts: Subscript R notation for the finite fields

texts:
I'm trying to understand the notation used in the literature for Pairing-based cryptography.
I know (and I hope I've understood it well) from Wikipedia that $\mathbb{Z}_p$ is the finite field of prime order $p$, where

$p$ is the order of the field
$q$ and the characteristic of the field and $q=p^n$

I came across this notation here and there while researching the Identity-Based Encryption (Boneh-Franklin): $$s \in_R\mathbb{Z}^*_q$$
The $\mathbb{Z}^*$ means that the finite field is provided with the multiplication operation.
But the $_R$ confuses me, as I can't find its meaning on the web.
Could somebody explain it?
PS: are the following notations equivalent? $GF(p)$, $\mathbb{Z}_p$, $\mathbb{Z}/p\mathbb{Z}$ and $\mathbb{F}_p$


texts: Is there a problem using Diffie-Hellman over a Mersenne prime?

texts:
Reductions modulo Mersenne primes are extremely fast, and there are several of a suitable size for modp-based Diffie-Hellman (such as $2^{2281}-1$). Is there any reason such primes are not commonly used for this purpose? Same question also applies to pseudo-Mersenne primes, of the form $2^{n}-c$ for small $c$, which also have fast reductions.

I'm assuming the reason they are not used is that something about the special form allows fast discrete logarithm computations, but I haven't been able to find any references to such an attack.


texts: How to provide mathematical proof of the security of a stream cipher against known attacks?

texts:
Suppose a person has invented a stream cipher and he/she wants to get it published.

I have a few questions:

In addition to providing detailed description of the algorithm, how would he/she give mathematical proof of its security against known attacks? Are there any things that are specifically expected to be described or proven in a paper that introduces a new cipher?
Are some kinds of attacks more important than others, or are they all equally important?


texts: Probabalistic Polynomial-time Algorithms & One-way functions

texts:
I've been reading up on probabilistic polynomial-time algorithms and one-way functions, and I was hoping to get some guidance on the topic.

A textbook I'm reading states the following for one of the conditions for one-way functions:

Hard to invert: For every probabilistic polynomial-time inverting algorithm A, there exists a negligible function negl such that
$$Pr[A(f(x))\in f^{-1}(f(x))] \leq negl(n)$$
where the probability is taken over the uniform choice of x in $\{0,1\}^n$ and random coin tosses of A.

What exactly does it mean by "random coin tosses of A"? Is it stating that the "inversion function" is randomly generated by such a process?


texts: How to beat a substitution cipher when adding a pseudo-random number stream?

texts:
From view-source:https://web.archive.org/web/19990224060310if_/http://www.cl.cam.ac.uk:80/PGP/pgpdoc1/pgpdoc1_29.html:

  When I was in college in the early seventies, I devised what I
  believed was a brilliant encryption scheme.  A simple pseudorandom
  number stream was added to the plaintext stream to create
  ciphertext.  This would seemingly thwart any frequency analysis of
  the ciphertext, and would be uncrackable even to the most resourceful
  Government intelligence agencies.  I felt so smug about my
  achievement.  So cock-sure.

  Years later, I discovered this same scheme in several introductory
  cryptography texts and tutorial papers.  How nice.  Other
  cryptographers had thought of the same scheme.  Unfortunately, the
  scheme was presented as a simple homework assignment on how to use
  elementary cryptanalytic techniques to trivially crack it.  So much
  for my brilliant scheme.

By Philip Zimmermann, according to the about page of that same website. Emphasis mine.

The crux of it is "A simple pseudorandom number stream was added to the plaintext stream to create ciphertext." This can be read multiple ways:

it is added to the end (unlikely)
it is interjected as in "h4e7l2l5o" (also unlikely, unless he meant the numbers are turned into letters, in which case I find it somewhat unlikely)
the numbers are added to each character

The latter seems like the only sensical option to me. But as far as I know, adding (equivalent to xor, security-wise) random numbers to each position is actually secure, assuming a good source of randomness. But it sounds like the scheme is broken using "elementary cryptanalytic techniques", not the underlying RNG. And of course the RNG (which has to qualify as CSPRNG) is the crux of such an algorithm, not the way of mixing its output with the plaintext.

The only thing I can think of is that it is unauthenticated, but that's rather a flaw in bad usage and not in this primitive itself. Does anyone know what "elementary cryptanalytic techniques" Phil is talking about? He makes it sound as though any basic cryptographer should have come across it and would know what it means (and how to break it), but I don't.


texts:
I'm implementing (for learning purposes) a file encryptor, which uses the following method (from http://en.wikipedia.org/wiki/Encrypting_File_System). I have 3 kinds of keys: RSA public/private, AES, and a user key derived from a phrase.

encrypt the file with AES (I use OFB mode).
encrypt the AES key with RSA.
write the encrypted AES key to the file header
generate a user key
with the user key I encrypt the RSA private key and the IV too, then place them in a database file.
I also hash the original AES key and store it in the database

A database file structure looks like this:
size_t fileID;
byte rsaPrivateEncrypted[RSA_KEY_LEN];
byte aesIVEncrypted[AES_BLOCK_LEN];
byte aesKeyHash[HASH_LEN];

The key hash is used to validate the key, before decrypting the file check if the hashes are the same.
I've just read that there is still no implementation of a key wrap algorithm in the Crypto++ library, so I use the method:

hash a user-defined string (phrase) with MD5 (128 bit) - this will be the KEK
hash the hash again with MD5, this is the IV for KEK
encrypt the RSA private key and AES IV with them using AES

I've chosen MD5 because its length fits AES's key/block size. (I know I could use the first n-bit of a longer hash too).
I assume this way is pretty insecure since I've read that there are special algorithms for this purpose (AESKW). What are the main drawbacks of this implementation? How can I make the key wrap/generation method more secure?
Also, in the wiki article, there is one more key:

FEK - KEK(RSA) - DPAPI - USER (hashed from PW).

What's the purpose of this key? As far as I understand, it is only used to decrypt the KEK. But the USER key could do this, since it is as secure as the USER key, no?


texts: Why programming languages don't provide simple encryption methods?

texts:
In c#, there is a namespace called System.Security.Cryptography and there are many classes in this namespace, which help developers encrypt and decrypt data. However, always they take byte[] array and they return byte[] array. So, as a developer, you have to always write a library to get the clear-text, turn it into byte of arrays, encrypt it, then turn the cipher array into an string, and return it.

I've talked to some other PHP and Java developers, and they told me that they have to undergo the same process there too. I haven't seen those languages though.

My question is, why frameworks like .NET framework, don't provide an straightforward mechanism for encryption and decryption?
I mean, from the point of view of a developer, cryptography means a black box into which you pass a string, and from which you will get an string, without the need to get into the complexity of creating streams like CryptoStream and without the need to converting strings into bytes of arrays, etc.

For example, look at this simple encryption example, taken from Microsoft's MSDN:

    static byte[] EncryptStringToBytes(string plainText, byte[] Key, byte[] IV)
    {
        // Check arguments.
        if (plainText == null || plainText.Length <= 0)
            throw new ArgumentNullException("plainText");
        if (Key == null || Key.Length <= 0)
            throw new ArgumentNullException("Key");
        if (IV == null || IV.Length <= 0)
            throw new ArgumentNullException("Key");
        byte[] encrypted;
        // Create an Rijndael object
        // with the specified key and IV.
        using (Rijndael rijAlg = Rijndael.Create())
        {
            rijAlg.Key = Key;
            rijAlg.IV = IV;

            // Create a decrytor to perform the stream transform.
            ICryptoTransform encryptor = rijAlg.CreateEncryptor(rijAlg.Key, rijAlg.IV);

            // Create the streams used for encryption.
            using (MemoryStream msEncrypt = new MemoryStream())
            {
                using (CryptoStream csEncrypt = new CryptoStream(msEncrypt, encryptor, CryptoStreamMode.Write))
                {
                    using (StreamWriter swEncrypt = new StreamWriter(csEncrypt))
                    {

                        //Write all data to the stream.
                        swEncrypt.Write(plainText);
                    }
                    encrypted = msEncrypt.ToArray();
                }
            }
        }

        // Return the encrypted bytes from the memory stream.
        return encrypted;

    }

This is just not simple and easy, and I think there should be a class in .NET Framework like TripleDesCryptoHelper with two methods as follow:

public string Encrypt(string clearText)
{
    // Doing the cryptography stuff here
    return cipherText;
}

public string Decrypt(string cipherText)
{
   // Doing the cryptography stuff here
   return clearText;
}


texts: Clarification of the terms "brute force" and "guess"

texts:
In the answer to the question “What exactly is a negligible (and non-negligible) function?”

There is a part in the explanation that – as far as my knowledge goes – is conflicting:

  But instead of brute force, the adversary can guess (a polynomial number of) random values and hope to chance upon the right one.

From what I understand, a “brute force attack” attempts to guess (to exhaustion)… or am I missing something here? Can someone please explain the distinction in this context?


texts: Finding collisions for XOR of many hashes

texts:
There's a collision-resistant hash function $H$.

Given $x$, how  hard would it be to find a set $a[i]$ such that:

$H(a[1]) \oplus H(a[1]) \oplus \cdots \oplus H(a[N]) = H(x)$

whereas none of $a[i]$ equals to $x$?


texts: How to securely compute AES where the key is splitted across different servers?

texts: How can we use secure multiparty computation in evaluating one AES circuit, where the key would not be stored at one computer instead it would be divided into pieces and given to multiple servers. Is there any good reference to follow ?


texts: Are there some well-known crypto APIs that leak information?

texts: Are there any well-known crypto APIs or libraries that leak or used to leak information (it can be the key or anything else)?


texts:
Am not a mathematician.

Every crypto specification I see uses the modulo operation. For example RSA -

If $e$ is the public key and $m$ is the plaintext with a modulus $n$ - the cipher text is $c = m^{e} \bmod n$

Why is this $\bmod\ n$ there? By definition isn't the modulo operation introduces an uncertainty? I mean  $3 \bmod 7 = 10 \bmod 7 = 3$.

Is it the idea to limit the result to a group? Why is there no uncertainty about the result?


texts:
I would like to understand how secure the permutation cipher is.

I would specifically like to understand the following concrete setup: If the alphabet is $L = \{0,1,\dots , 255\}$ and $\sigma_1, \sigma_2, \dots, \sigma_n $ are permutations on $L$, then we can create a cipher by encrypting the first character in the plaintext by $\sigma_1(\sigma_2(\dots \sigma_n(a_1)))$. Then we can (like with the Enigma machine) rotate $\sigma_1$. That is if for example
$$
\sigma_1 = \pmatrix{0 & 1 & 2 & \dots & 254 & 255 \\ 55 & 140 & 7 & \dots & 34 & 82}
$$
we rotate so that $\sigma_1$ become
$$
\pmatrix{0 & 1 & 2 & \dots & 254 & 255 \\ 140 & 7 & &\dots & 82 & 55}
$$
When we have rotated $\sigma_1$ 255 times we rotate $\sigma_2$.

This means that the key basically consists of the permutations $\sigma_1, \dots, \sigma_n$.

My general questions is: How secure is this cipher? I understand that the security will depend on $n$, so if the question is too hard to answer, I would be OK with assuming that $n$ is "large enough". I also understand that this will depend on whether or not one reuses the same key several times, so

Another question is: How does the security depend on whether or not one reuses a key?

(By large enough one could just choose $n$ so that $255^n$ is greater than the size of the cipher text.)

(${\tiny\text{ I am not trying to roll my own crypto. I promise never to use this for anything serious besides trying to learn}}$)


texts:
Bcrypt uses Blowfish to encrypt a derived key from the passphrase, and Blowfish is a cryptographic algorithm, but here it is said  that:

  Note that
     Salsa20/8 Core is not a cryptographic hash function since it is not
     collision-resistant.

so how this is useful in Scrypt?


texts: Seeking Fast Bloom Filter for Anonymous Address

texts:
I had an idea to use something like public message boards to pass secrets anonymously and non-interactively (similar to TV/Movie Trope : http://tvtropes.org/pmwiki/pmwiki.php/Main/PublicSecretMessage ). So here's the basic construction: Bob encrypts a message for Alice and then posts it with an anonymous address tag. Bob calculates this anonymous address using a pre-agreed elliptic curve (EC) by selecting a secure random value r and posting the address tag as (I, J) = (rG, rA), where G is the generator point and A is Alice's public address point. Alice then knows (wvhp) the message is for her if a * I = J. I postulate this is anonymous as it is basically the Decisional Diffie-Hellman assumption as I understand it (right?).

One concern I have is that given a significant number of messages it would become somewhat computationally expensive to perform a large number of scalar multiplications (especially if Alice were my thermostat or my front door lock).

So I'm looking for a much more efficient but not necessarily definitive mechanism for Alice to reject the majority of messages without divulging the intended recipient of the message. So here's the problem statement:

Alice must be able to calculate the bloom filter value efficiently (much more efficient that scalar multiplication of an arbitrary EC point), it can be substantially more expensive for Bob
Eve should not be able to infer that the message is more likely to be intended for Alice than any other message
There should be no false negatives (i.e. every message intended for Alice should pass the filter)
There should be a low false positive rate, potentially configurable (i.e. most of the messages not for Alice are rejected by the filer)
The bloom filter tag/element should not be large (or not significantly larger than two encoded EC points)
The plaintext message size for the tag could be relatively small (32 bits or even 16 bits) as even with a 16 bit tag the filter could have a false positive rate as low as 1/65536.

So given that problem statement, anybody got an idea on an implementation?

(btw, I've been looking into proposed cryptocurrency stealth addresses, which are essentially the same "ratio of EC Points"... but those designs don't seem to improve the performance)


texts: TLS 1.2 Cipher Suites With AES-GCM – What data (if any) is passed to the AES-GCM cipher as the Additional Authentication Data?

texts:
TLS 1.2 defines a number of cipher suites that employ AES-GCM, e.g.:

TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256
TLS_ECDHE_ECDSA_WITH_AES_256_GCM_SHA384
TLS_ECDH_ECDSA_WITH_AES_128_GCM_SHA256
TLS_ECDH_ECDSA_WITH_AES_256_GCM_SHA384
TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
TLS_ECDH_RSA_WITH_AES_128_GCM_SHA256
TLS_ECDH_RSA_WITH_AES_256_GCM_SHA384

Being that AES-GCM is an AEAD cipher, it handles both encryption and integrity verification.  Also, it can optionally accept additional authentication data as one of its inputs (in addition to the plaintext, the key, and the iv).  The additional authentication data is not encrypted, but it is included in the integrity verification process.

I’ve read RFC 5289, RFC 5288, RFC 5246, etc., but I’ve not found any mention of what data, if any, is passed to the AES-GCM cipher as the additional authentication data in a TLS 1.2 implementation such as one of the above.

My question is:  In a TLS 1.2 implementation that employs AES-GCM – what data (if any) is passed to the AES-GCM cipher as the additional authentication data?


texts:
Why is a HMAC using a 32bit tag not prone to birthday attacks?

I have read that it has something to do with the fact a birthday attack isn't really possible if the output size is not large enough. But then that asks the question of at what size does it become valid and a practical attack can be carried out?

If it isn't prone to birthday attack then what would be the probability of guessing a valid tag value for something as weak as a 32 bits in length?

Probability of a single hash collision$$\frac{1}{2^{32}}$$

However the birthday paradox mathematically suggests that this probability should be n^32/2...

Or am I missing something here?

Update: The goal of the attack is just guess what the tag might be.


texts: AEAD (for AES128-GCM): is it necessary to add a zero-length AAD?

texts:
In an implementation of AEAD_AES_128_GCM, if the AAD is defined as a "zero-length octet sequence", is it necessary to call the encryption code that adds an AAD at all? In particular, does an OpenSSL/LibreSSL libcrypto client need the EVP_En/DecryptUpdate invocation that adds the AAD, if its length is 0?

I'm working on an implementation of RFC 8188, a protocol for encrypting HTTP messages with AEAD_AES_128_GCM, which has this to say:

   The additional data passed to each invocation of AEAD_AES_128_GCM is
   a zero-length octet sequence.

Currently my test code (just in a mockup stage) has this:

static const unsigned char *aad = (const void *)&aad;
static const int aad_len = 0;

#if 0
    /* XXX not sure if this is necessary, examples work with & without */
    if (EVP_DecryptUpdate(&ctx, NULL, &len, aad, aad_len) != 1) {
        ERR("decryption: adding aad");
        return -1;
    }
#endif

The resulting code produces the expected decryptions and intermediate values for the examples in chapter 3 of the RFC. As you can see, this part is #if 0-d out, so in fact nothing is done to add an AAD.

Since this may seem like a remarkably silly question (already I'm pre-emptively embarrassed), let me explain why I'm asking:

The RFC has all of two examples, both of which decrypt ciphertext to "I am the walrus" (with two different record sizes). So the "it works" result may be a lucky accident of sparse test data.
Since the RFC goes to the trouble of saying "zero-length octet sequence", rather than something like "there is no AAD", it feels like there might be a reason for putting it that way.
An assumption on my part, a crypto layman, that "it's zero-length so I don't have to do anything" feels like the sort of thing that leads to errors and insecurity in code that uses cryptography. Operations on zero-length structures don't always mean the same thing as "do nothing" (consider SHA hashes of the empty string).

So I thought I'd ask others if there might be more going on here than meets the eye.


texts: Checking a file for integrity and authentication

texts:
A checksum is a small-sized datum derived from a block of digital data for the purpose of detecting errors which may have been introduced during its transmission or storage. It is usually applied to an installation file after it is received from the download server. By themselves, checksums are often used to verify data integrity but are not relied upon to verify data authenticity.
  [wikipedia]

How would you verify data authenticity then? Would transferring a file through the https protocol and then comparing it's hash confirm that it's genuine, or is there more to it than that?
And how would you hash a big 40+gb zip file, would you have to hash the entire contents of the file and, each file within the zip file?

I couldn't find any good resources on how to hash verify big files.


texts: Why SM2 ECC parameters does not specify cofactor h?

texts:
Recently I've been studying the ECC with the Chinese SM2 standard. One question is on standard part 5, parameters definition, it only defines $p, a, b, n, XG,$ and $YG$, but not cofactor $h$.

I found some useful discussion introducing all the parameters mathematics behind: What is the relationship between p, n, and h.It doesn't answer my question: Why SM2 does not specify h, while Key Exchange Agreement Protocol introduce in SM2 part 3 has used it.

On the standard part 1, section 5.2.2, it provides a method to verify Elliptic Curve Parameters. One option process uses to verify $h$ is:

(optional) Calculate $h'=\lfloor((p^{1/2} + 1) ^ 2)/n\rfloor$, and verify $h=h'$

This also means h can be calculated by the equation above. I calculate with an online big number calculator, the result is slightly greater than 1 (not fully equal).

Or have I misunderstood this cofactor? It is calculated instead. Elliptic curve can be perfectly defined only with $p, a, b, n, XG$, and $YG$.


texts:
I'm new to ECDSA and there is something I still not sure about.
If I have a classic Certificate Authority server that delivers PEM certificates containing public key with ECDSA, I can retrieve the coordinates of the Point on the curve, and the curve used.

My question, is regarding the coordinates of the point $x,y.$
Is it possible that two different generated certs can give me the same point?

Or points are sure to be unique?

Is it safe to set ownership from the combination of $x,y.$
For example, I have an asset and I want to set its owner to "$\{x\}:\{y\}$" ?

Thank you,


texts:
I have been going through a huge amount of papers to find a simple and a practical method to compare integer numbers without revealing their original values. I know that this falls within the area of secure multi party communication framework. However, I have very limited knowledge in cryptography and I can not really understand much of what the papers explains.

I have already tested the viff (viff.dk/) framework but the computation cost is quite high to compare just 5 numbers (about 500 milliseconds). I am looking for a solution with minimum security guarantees but low computation overhead. I would be grateful if someone point out a simple solution to start with or even an implementation which I can use. I know that my question may seem quite general, but I am kind of lost here and any pointers would help.

-------UPDATE--------

We would like to compare offers of different ISPs (internet service providers) in order to provide the best service to a customer (bidding). The ISPs don't want their offers to be revealed to the other ISPs but they want to know which one of them wins (the one with the best offer). They don't want to use a third party to do the comparison, they want to do it in a multi party fashion. The information provided by the ISPs currently is just a single integer of 8-bits length. The goal is to find the biggest integer. I don't know if this include multiple operations or just a single one !! ... And I guess it needs inequalities ... since this comparison needs to be done as fast as possible within 10th of milliseconds and we assume that the ISPs would be  mostly honest, we are looking for as simple and as practical as possible protocol to do it. Our concern is is speed more than the security.


texts: Why NaCL does not provide anonymous public key cryptography?

texts:
At the same time Sodium provides API for anonymous encryption without using ephemeral keys.
Is it a bad practice to just use other user public key to encrypt a message?


texts: How to actually compute the statistical distance?

texts:
I have an algorithm for discrete sampling that I've defined. This is to say that $A$, upon input some pdf $p(x)$, outputs samples from the pdf $p(x)$. There are some nuances (you have to make the support of $p$ finite, so you're really only sampling from some distribution within some statistical distance $SD$ of the distribution of $p$), but nothing too complicated.
By statistical distance I imean the "Total Variation Distance":

  $$d(D_1,D_2) = \sum_{x\in\mathsf{supp}(D_1)\cup\mathsf{supp}(D_2)}\lvert \Pr[D_1 =x] - \Pr[D_2 = x]\rvert$$

Imagine I can (theoretically) prove that this process truly does sample from a distribution that's within $SD$ of the true distribution, and I want to implement this sampler. What are the typical ways to show that $A$ produces the distribution that it theoretically should? Given a perfect implementation, this wouldn't be an issue, but I'm hoping to use this to catch bugs.

There are easy naive things to do --- for example, draw some number of samples $(x_1,\dots,x_n)$, treat this as an empirical distribution, and compute the statistical distance between that and the (true) pdf $p(x)$. My worry about this is that the Statistical Distance problem is complete for the complexity class Statistical Zero Knowledge (see chapter 4 of Vadhan's thesis for a survey), which might hint that this is a poor method of finding bugs.

Of course:

It could be that my instance of the problem is easy
My problem is presented in a slightly different form (SZK is a circuit class I believe)

Still, this makes me worry that checking the statistical distance of $A$ from $p(x)$ is an intractable problem. Is this true? Are there better algorithms for it than the naive one I mentioned above?


texts:
Are there digital signatures for which, given two documents signed by the same key, one could derive the key?

With such one-time signatures, one may be able to design a cryptocurrency based on proof-of-stake instead of proof-of-work. To disincentivise miners from cheating by mining several blocks, one could impose that miners sign with a one-time digital signature the blocks they mine. That way, if a miner did mine two different blocks with the same key, the key would be exposed and they would lose the funds associated with that key.


texts: How does Fialka manage to have a letter encipher unto itself?

texts:
http://www.cryptomuseum.com/crypto/fialka/index.htm

Fialka was an electromechanical rotor machine.

How does it manage to have a letter encipher unto itself. I realize it does something clever by using transistors, but it has a reflector. With direct current circuits, there has to be a negative and a positive connector. If one simply attached a positive current to itself, it wouldn't flow. So how does it work?


texts: Why is it impossible to find the private key from the public key?

texts:
From what I understand, based on the article A Beginner’s Guide: Private and Public Key Cryptography Deciphered, the public key is generated by performing $n$ tangent plus mirroring operations from the point $G$ over the elliptic curve, where $G$ is defined in secp256k1 and $n$ is a natural number that directly relates to the private key.

As I know the public key and the seed value $G$, I could start a process computing $$G + G, G + G + G, \dots$$ and comparing those results with the public key value until it matches.

If your answer would be that this process is very slow: if this process is slow, the same applies to computing the public key from the private key (because the operations are the same except for the check operation). So, how it is possible to compute the public key in a very fast way?


texts: Is there an accepted way to cryptographically enforce tracked changes on a document?

texts:
I'm working on a document-editor project, and I would like to add a feature to lock tracked changes, similar to Microsoft Office.  The goal is to allow one user to lock tracked changes with a password, which would allow other users to only edit the document with tracked changes.  Any edit to the document that is not tracked would be detectable.
The solution I've come up with so far is to split the binary file into two sections: the original state of the file when tracked changes was turned on, and a list of the changes made since then.  A checksum of the original file would be included and encrypted by the password provided.  This would prevent other users from editing the block and producing a new checksum.
However, I believe that this would constitute a vulnerability because it would expose the password to a brute-force attack.
Is there any commonly accepted way to approach this problem, or any documentation on how other software (i.e. MS Office) solves this problem?
Thanks


texts: For security, need a 1-1 crypto-mapping be NP-complete?

texts:
The book Foundations of Cryptography states:

  It was understood that problems related to breaking a 1-1 cryptographic mapping could not be NP-complete and, more important, that NP-hardness of the breaking task was poor evidence for cryptographic security.

But I thought the whole point of complexity theory was to determine which problems were NP so that we might be able to use the infeasibility of their solutions to produce security?


texts:
I got confused with the monotonic access structure definition.

Following definition is one of the answers to the following question:

What are monotonic and non monotonic access structures in ABE ?

Let $\{1,2,...,n\}$ be a set of indices. An access structure is a collection $\mathbb{A}$ of non-empty subsets of $\{1,2,3,...,n\}$. We say a collection (or an access structure) $\mathbb{A} \subseteq 2^{\{1,2,...,n\}}$ is monotonic if for any $B,C \in 2^{\{1,2,...,n\}}$, if $B \in \mathbb{A}$ and $B \subseteq C$ then $C \in \mathbb{A}$.

According to the above definition, every access structure $\mathbb{A}$ which not include $\{1,2,3,...,n\}$ is not monotonic!, because every arbitrary $B \in 2^{\{1,2,...,n\}}$ always is subset of ${\{1,2,...,n\} }$

Could you please clarify what I am going wrong?


texts: How does one verify a GPG/PGP key revocation?

texts:
After revoking a key and sending the revocation to MIT's keyserver, I noticed that the key is listed as such:

pub  2048R/XXXXXXXX 2011-01-01 *** KEY REVOKED *** [not verified]

Who is responsible for the 'verification of the revocation'? Does the owner of the key do this verification?  If so, how is this accomplished? Do other people sign the revocation and at a certain point it becomes verified?


texts: I am trying to generate a permutation of polynomial with order m

texts: Suppose m = 5 and N = 64. How do I choose the coefficients such that the polynomial is a permutation of nos from 0 to 63.?


texts: Implementing AES-CBC (Matasano Crypto Challenge 10)

texts:
I am currently doing the Matasano Crypto Challenge to learn a bit about cryptography. In that specific challenge one had to implement AES in CBC mode. I did that and verified that encryption and decryption are working using these test vectors. I can't manage to decrypt the message given in the challenge though. I am not asking you to decrypt it, but when I thought about it a bit more I got a bit confused due to the used IV (which is 0x00 for each byte). Doesn't this IV have no effect at all since the decrypted message just get's XORed against the IV? Shouldn't decryption also be possible using simple AES-ECB?

EDIT:
Sourcecode in Java: http://pastebin.com/cX8YZjD0


texts:
I have some spare time, and a few hundred DJB2-hashed values sitting around. I thought I'd try to do something "useful" and invert DJB2, such that I could calculate the plaintext of the hashes (which has long since been lost, a fact that is often bemoaned).

For those who don't know, DJB2 is implemented like this: (C#)

public int Djb2(string text)
{
    int r = 5381;
    foreach (char c in text)
    {
         r = (r * 33) + (int)c;
    }

    return r;
}

Text is a string of ASCII characters, so DJB2 has a lot of collisions, a fact that I knew full well going in to this. Fortunately, the plaintext I have has characteristics that will allow me to use heuristical filtering, so false positives shouldn't be much of an issue :)

My algorithm is essentially this, plus some recursion-control (pesudocode):

reverse(hash):
    y = hash mod 33
    for c in [65, 120]:
        if c mod 33 == y:
             print reverse((hash - c) / 33), c

In other words, find the remainder of the hash / 33. Then, for all the ASCII values from 65 to 120, check to see if the value / 33 has the same remainder. If it does, subtract it from the hash, divide the hash by 33, and continue the algorithm. In this way, we only investigate promising paths, because we know that the subtraction of C must leave a number that is evenly divisible by 33.

For example, here is the algorithm working to decode a simple hash:

$h = 177676$
$y = h\mod{33} = 4$
Values of $c$ where $4\equiv c\mod{33}$: $70$ and $103$
I can now pursue only those two values of $c$. (In this case, $103$, or 'g', was correct)

Thus, I know my algorithm works to reverse the hashing process. Unfortunately, I ran into a nasty problem. Djb2 will rapidly overflow the bounds of an int, often with plaintext as small as four characters. This overflow essentially results in r being implicitly modded by $2^{32}$.

Normal division won't work. I asked a question on programming SE about division in this case, and was informed about the multiplicative inverse of 33. Unfortunately, I don't need a division operation (yet), I need a remainder operation! This is proving to be much trickier, and I'm not sure it's even possible.

Here's an illustrative example:

$h = 2090289493$ <-- h is actually $6385256691\pmod2^{32}$ because of the overflow
$y = h\mod{33} = 28$ <-- Incorrect! Should be 32

Here is an example of the algorithm using the operation $\Omega$ and an $h$ that has overflowed. This is what I'd like to do, but I don't know what operation $\Omega$ represents.

$h = 2090289493$
$y = h\ \Omega\ {33} = 32$
Values of $c$ where $32\equiv c\mod{33}$: $65$ and $98$
I can now pursue only those two values of $c$.

Am I on the right track with reversing DJB2 (can it be reversed?)? Is there some way of finding the remainder of a large number that has been modded by $2^{32}$?


texts: How do fast multiplication algorithms deal with cryptanalysis?

texts: Math algorithms like Karatsuba and derivatives - do they have any applications for cryptanalysis of asymmetric cryptography algorithms?  What if we have very fast multiplier? How can it help with extracting the secret key from encoded text?


texts: Are there drawbacks to encrypting data locally before being encrypted in cloud backup (multiple encryption)?

texts:
I am planning on backing up my hard drive using a cloud backup service but have become skeptical of the industry based on incidents like these:

http://dbmsmusings.blogspot.com/2011/02/why-i-no-longer-trust-emc.html
https://security.stackexchange.com/questions/7142/online-backup-how-could-encryption-and-de-duplication-be-compatible

And this response to the question of losing one's private key by Altdrive:

"What if I lost my file encryption key?

We don't want to hear that! Your private encryption key is VERY important and personal. Without it, you cannot restore your data in event of a system loss. We highly recommend that when you create your encryption key, you store it in a safe place: e.g. printed out and in a safe deposit box, or backed up somewhere else on the Internet.
If you did, contact us immediately. There may be a few options depending on the circumstances."

Based on lack of trust of these providers, I am planning on encrypting my hard drive using EncFS on an external hard drive and then using Altdrive (the cheapest backup cloud service) to back up that external hard drive, so that regardless of whether I use Altdrive's user-defined private key or their own key, stored on their server, it should not be possible for them to access any of my data.

What are the risks to consider in this approach, eg is there more a chance of corrupting my data since it will be encrypted multiple times, will it be harder to access or obtain individual files, ie maybe I have to download the entire volume since I shouldn't be able to recognize each file on their server (not sure how it works to obtain data from cloud backup providers in general)?

I am using linux.


texts: Comparison of security definitions for signatures

texts:
The two main security definitions for signatures are EUF-CMA and the strong version of it sEUF-CMA.

What I see that their difference is that in EUF-CMA experiment, the adversary needs to produce a valid signature for a message of its choosing, where the message has not been queried before (i.e., a message for which the adversary hasn't made queries to the oracle).

Whereas in the sEUF-CMA experiment, similar thing happens, though now the adversary needs to make sure that it hasn't queried the oracle with the forged (message, signature) pair. So, simply the signature also enters into the equation in sEUF-CMA.

The part that I don't understand is why the sEUF-CMA actually constitutes a stronger definition than regular EUF-CMA definition? Why does including the signature makes it stronger?
Also, for example in ECDSA, for a message $m$ and a valid signature $\sigma = (r,s)$, the signature $\sigma' = (r, -s \bmod N)$ is also valid. So, in a sense you get a new signature $\sigma'$, but, actually the signed message is the same $m$.

So, this seems to me that it does violate sEUF-CMA as, although the message is the same one, the signature is different, so adversary wins. Whereas, this cannot violate EUF-CMA, while there we care only for the message, so we don't care if adversary can produce a forgery for an already queried message. So, it achieves EUF-CMA security, but not sEUF-CMA, right?.
I think the situation is also different in textbook RSA, where it has homomorphic properties, so given a valid $(m, \sigma)$ pair, using the homomorphic properties one can produce a valid signature $\sigma'$ for a new message $m'$, and it seem does not satisfy any of the provided security definitions, is that right?


texts: Can one make a secure AEAD from any secure cipher and any secure MAC?

texts:
Can one make a secure AEAD from any secure cipher and any secure MAC using encrypt-then-MAC:

with independent keys and IVs (any cipher and MAC)
if the cipher is a stream cipher (including a block cipher in CTR mode), using parts of the keystream (not used to encrypt plaintext) as the MAC key or keys and IV?

If so, then all of the following would be secure:

A stream cipher plus GHASH (of which GCM becomes a special case), with the stream cipher being used to mask the GHASH output.
A stream cipher plus any other Wegman-Carter authenticator, such as Poly1305, again with the stream cipher used to mask the output
A stream cipher plus HMAC.

Proof of the first two cases: since encrypt-then-MAC is secure we need only to show that

this is in fact an encrypt-then-MAC construction.
that the MAC is secure (we already know by assumption that the stream cipher is secure).

Firstly, we can assume that the parts of the keystream used for the MAC and to encrypt plaintext are independent, as any dependencies would be a distinguisher against the stream cipher.  Therefore:

is true because the construction uses a stream cipher to encrypt the plaintext, then applies a MAC to the ciphertext.

is true because the stream cipher is a secure PRF, so there is no way (for a resource-bounded attacker) to compute the (secret) MAC key (and block used to encrypt the MAC) from the (potentially known to attacker) part of the keystream used to encrypt plaintext.  Therefore, the attacker has no knowledge of the internal state of the MAC, and so the composition is secure if the MAC is.  For most Carter-Wegnam MACs, this is known unconditionally.

I have seen various special cases proven secure, but not the general case.


texts:
I'm a beginner to ECC crypto programming. Can anyone explain to me the difference between using ECDH for shared key exchange and the use of ECIES by encrypting a shared key with the public key of the receiver?

I feel that ECIES could also provide me with secure key exchange as long as the private key is kept secret.


texts: Definition of secure computation with more that two parties

texts:
In Definition of secure computation in m-party case with respect to semi-honest adversary (Definition 7.5.1 in Foundations of Cryptography: Volume 2, Basic Applications by Oded Goldriech) we say protocol $\Pi$ is secure if there exists simulator $S$, such that for every $I\subset [m] = \{1,2,...,m\}$ output of simulation and $VIEW^\Pi_I$ be indistinguishable.

I don't understand why it is not enough to construct a simulator only for every party $p\in{1,2,...,m}$ (instead of any subset of parties). Besides order of quantifiers seems confusing to me too. It is mentioned in the footnote that (page 697):

  Note that for a fixed $m$, it may make as much sense to reverse the order of quantifiers (i.e., require that “for
  every $I$ there exists an algorithm $S_I$ ”).

What does "may make as much sense" mean? The original order of quantifiers doesn't make sense to me, but the reverse does. (Reverse order just seems like definition of two-party case.)

I would appreciate:

1) explanation (maybe including simple example) that give me the intuition about why security is defined this way.

2) Suggestion of good reference (almost as good as Yehuda Lindell's tutorial) as an example of security proof in multiparty case.


texts: Why are there only 10 plugboard pairs in the enigma?

texts:
The plugboard provides a new layer of security for the enigma but why can we only swap at most 10 letters? I only found things like "10 was the most common." but why stop there? Isn't adding more going to provide more security?
At first, I thought it was not going to add more complexity at one point, because swapping two letters that have already been swapped by the rotors is not going to change anything. But after a rotor does a single turn, that wouldn't matter anymore.


texts:
I am doing a paper on textbook RSA (this is for high school btw) and in my example I need two very large primes, but I want my $e = 3$.

Is there a short way to calculate the values of $p$ and $q$ such that $gcd(e, φ(pq)) = 1$?


texts: Can one passively load-balance HTTPS traffic based on TLS SNI?

texts: Is it theoretically possible to passively snoop into the HTTPS traffic, reliably detect whether or not TLS SNI is attempted to be used by the client, and, if it is, redirect the stream of the connection as-is to one of the many different upstreams (each one of which requires HTTPS in order to connect and may have its own certificate not necessarily known to us)?


texts: How bad would it be to reuse the random blinding factor in a scheme like Paillier?

texts:
A secure and somewhat fast way to "re-encrypt" (refresh? anonymise?) a Paillier ciphertext, $c$, is to multiply it by an exponentiated random value:

$c \gets c \cdot r^n \mod n^2$ (with $r \in \mathbb{Z}_n$ random)

However, that mod exponentiation of a large $r$ is quite costly (many orders more than the other operations involved). So, in cases where many successive re-encrypt would be necessary, it seems very tempting to store and reuse the same $s = r^n \mod n^2$.

Hence, after two re-encryptions, the cipher would contain:

$c \cdot s^2 \mod n^2$

and so on...

Such a re-encrypt method would only use multiplications and be vastly cheaper that the common method.

Since multiplication by $s$ "should" be large-enough to trigger a modulo wrap-around, it seems like successive $s^i$ values would not give any information about any of the previous $s^k, k < i$ (and thus preserve the security of all ciphertexts). Is this correct?

The weakness seems to be in the risk that one such multiplication would not trigger a wrap-around, but maybe a solution to that would be to keep multiplying until we are guaranteed one has occurred.

As a variant: we could use a small pool of such pre-calculated exponentiated random values for each re-encryption, thus ensuring the wrap-around always occurs.

Am I missing an obvious security flaw here?


texts: It is reasonably safe to leave an AES encrypted RSA private key public?

texts:
The owner of the RSA key can't store the key, so they need to hand the key to an untrusted entity for storage. Before they hand it over they encrypt it using AES with a multi-word phrase they can remember.

The idea is that I could generate a private key and store it outside the entity in a non-secure location but not worry (as much) about it since it is protected by a passphrase.

The private key might be stored in several places - in fact and I have to assume they are all publicly-accessible (like a web page). But when the entity wants to do something with the key it requests it back from the storage places and then (with the users password) decrypts it and uses it for what is needed.


texts: Security of an Elliptic Curve Public Key with a "Small" x-coordinate

texts: Consider an elliptic curve over a finite field $F_p$ with $p$ prime and order $n$. Let $Q$ be a generator for the field. Given a public key point $P = aQ$, suppose we have an algorithm that finds an integer $b$ such that $P + bQ = R = (x, y)$ with $x \leqslant M$ for some fixed $M << n$. Is this new point $R$ any less secure than the original public key i.e., could we find $c$ such that $R = cQ$ yielding $a \equiv c - b \ (\!\!\!\!\mod n)$.


texts: What is the RFC order of peer certificate verification, trust chain or expiry first?

texts:
If a certificate received from a peer:

Is expired,
has a valid signature, but from an untrusted root CA

What error should be thrown?  Untrusted certificate or expired certificate? I can't seem to locate what the relevant RFC would suggest.


texts: Attacks on LCG with "self-XOR" output function?

texts:
Consider an ordinary LCG modulo $2^n$ with an internal state of $n$ bits and an output of $n/2$ bits, with the twist that instead of simply truncating the state to produce an output, we take the upper and lower $n/2$ bits of the state and XOR them together.

$$X_{i + 1} = A X_i + C \bmod{2^n}$$
$$Y_i = (X_i / 2^{n/2}) \oplus (X_i \bmod 2^{n/2})$$

Has this kind of pseudorandom number generator been analyzed in a paper somewhere? What are the core ideas to attacking it when $n$ is large (e.g. 64 or 128 bits or larger)? I am particularly interested in an output prediction or state recovery break, but a distinguisher is nice to have too. We may assume both LCG parameters (multiplier and increment) are known and odd.

It seems that the usual methods (e.g. lattice) fail to apply in this case due to the added state-dependent, nonlinear operation.

I made an attempt at approaching this as follows:

We're trying to recover the initial state $X_0$. We may collect a number of outputs $\{ Y_i \}$ and take a guess at the LSB of $X_0$. This immediately fixes the LSB of all other $X_i$ since $X_{i + 1} \equiv X_i + 1 \pmod{2}$, and thus fixes the LSB of the upper half of all $X_i$ by definition of the output function.

Some arithmetic shows that for all $i \geq 0$ we have

$$X_i \equiv A^i X_0 + C \sum_{k = 0}^{i - 1} A^k \equiv A^i X_0 + C_i \pmod{2^n}$$

We can now ignore every bit beyond the LSB of the upper half (T-function property) and focus on the first $n/2 + 1$ bits. If we find that there does not exist an assignment of the remaining $n/2 - 1$ bits of $X_0$ such that, for all $Y_i$ collected,
$$\mathrm{MSB}[\left ( A^i X_0 + C_i \right ) \bmod{2^{n/2 + 1}}] = \mathrm{LSB} \left [ Y_i \right ] \oplus \left ( \left ( X_0 + i \right ) \bmod{2} \right ) \tag{1}$$
then we have certainly guessed incorrectly. There's probably a better way to do this but we could just check satisfiability twice, once using our guess and once with the alternative guess, adding more $Y_i$ until either system becomes unsatisfiable, and thus recover two bits of $X_0$. Rinse and repeat on the next least significant bit until all bits of $X_0$ are recovered, in principle.

Checking for satisfiability exhaustively takes $O(2^{n/2})$ time, so if we need $m$ outputs at most recovering the state through this method in the most naive way takes time
$$O((n/2) \cdot 2^{n/2} \cdot m)$$
which is much faster than brute-forcing the internal state (assuming $m$ is reasonable; I have no proof of this but I suspect that $m$ is proportional to or at least polynomial in $n$). It should be (barely) viable for $n = 64$, whereas the $n = 128$ case remains hopelessly out of reach.

Using an SMT solver as part of the algorithm (I tried Z3 and boolector) doesn't really give any speedups and is in fact slower than an exhaustive search. This makes sense intuitively because the multiplication by the different $A^i$ is highly nonlinear over bitvectors so the solver just gets bogged down expanding and processing an ever-growing, exponential number of clauses.

Can we do better? What are some ideas that could be applied here?


texts: How to encrypt an image with logistic chaotic map?

texts:
I need to encrypt color images, using logistic chaotic map. Could you please recommend an algorithm for this?

All the articles that I've found on the Internet are completely unclear.


texts: Why is Dolev Yao a local Inference System but blind signatures aren't?

texts:
I am currently working on this tutorial: https://www.infsec.cs.uni-saarland.de/wp-content/uploads/sites/2/2017/04/CK-fntpl-14.pdf
However, I am struggling with the term "local inference system". If I understand it correctly, all terms in the proof tree have to be in the subtree of $S$ and $t$ where $S$ and $t$ are both sets of terms. I don't fully understand why in the proof for Proposition 3.2 we can say that the asymmetric encryption is in the set of subterms of $S$ (In the Dolev Yao Inference System). And based on this, I am struggling with the question from exercise 2, why the inference system for blind signatures is not local.
I really want to learn more about formally analyzing the security of protocols, so I am very thankful if someone could help me with this question.


texts: Which is better when the secret is leaked, RSA or Diffie-Hellman?

texts:
I know that DH can be used for perfect forward secrecy but for the sake of this example, let's say that RSA and Diffie-Hellman are both used to establish a symmetric key that will be used for future encryptions.

Which one is more secure or more vulnerable if the secret key was ever leaked?


texts: Is it secure to ECDSA-sign a public key without hashing it first?

texts:
I am trying to sign an ECDH public key with ECDSA. However, my hardware does not allow me to implement a hash algorithm, considering I am running out of memory already.

Therefore, I am currently just passing the ECDH public key as the message to be signed to the sign function without any hashing beforehand, which is usually advised in any algorithm explanation (see chapter 6.4, http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf).

I have yet to find any evidence or analysis about possible security implications of skipping the hashing step. My intuition would say, that hashing the message serves as a way to blur the original message, essentially avoiding any retracing if the algorithm was somehow compromised.

If this is the case, would it be applicable to simply leave out the hash in this case, considering I am sending the ECDH public key in plain text over the wire anyways?


texts: blowfish ecb with openssl doesn't give the expected result

texts:
I do the following via the Linux CLI:

printf '\xff\xff\xff\xff\xff\xff\xff\xff' > plaintext.txt
openssl enc -bf-ecb -e -in plaintext.txt -out ciphertext.txt -nosalt -K FFFFFFFFFFFFFFFF -p

I then read the contents of ciphertext.txt with <?= bin2hex(file_get_contents('ciphertext.txt')); ?> and I get this:

5aacfb5a8dc0155dd0269124c9e81789

According to https://www.schneier.com/code/vectors.txt, however, the result is this:

51866fd5b85ecb8a

That ciphertext.txt is twice as long as the test vector result makes sense because of padding. But shouldn't the first eight bytes of ciphertext.txt match the test vector?

Doing the above with des-ecb (same plaintext and same key) gives the same output that https://www.cosic.esat.kuleuven.be/nessie/testvectors/bc/des/Des-64-64.test-vectors mentions (Set 3, vector#255) so it seems like my test methodology is correct.

Any ideas?


texts:
I'm not a cryptologist, just an interested engineer (& now retired).
I used to design hardware with AES en/decryption blocks & generate test vectors using my own Tcl script using the embedded aes function.
However, I was wondering if modifying AES to use more than 1 SBox (& inverse), it would be "more secure", or is that not the case?
I've found 1108 SBoxes that meet the original criteria (out of 256! possible combinations). My view would be to have a short table to indicate which SBox to use for each round of 14 (assuming 256 key).  I realise this would complicate h/w a bit, but not be very complicated to modify a C program.
Initially just using 2 SBoxes, the original & one other, but easily expandable to use 3,4.. etc in software.
Just after thoughts really.


texts: Is it safe to use same private key in two or more EC signature algorithms?

texts:
Given two (or more) algorithms:

ed25519

private key is random blob of 32 bytes
public key is encoded point on Edwards 25519 curve.

ECDSA with secp256k1

private key is random blob of 32 bytes
public key is encoded point on secp256k1 curve.

Lets say, we have a message M and we sign it with both algorithms, with the same private key (public keys are calculated deterministically based on private key). Adversary is able to see both signatures, collect history of such signatures for different messages, messages are unencrypted.

Are there any security implications for this scheme?


texts: RSA padding and Least Significat Bit Oracle Attack

texts:
So my question is do padding schemes used in RSA protect it against Least Significant Bit Oracle attack?

The attack I am talking about is described here:
RSA least significant bit oracle attack

As far as I know the padding schemes add some random bytes to the end of the block so that it always gives a different value when encrypted. But if it is done this way we can continue doing the LSB oracle attack and get the deciphered block, then easily discard the random bytes. Am i missing something about how padding schemes work?


texts: Simulating a joint distribution of an *almost* deterministic function

texts:
The following is in the context of secure MPC.
Suppose that there is a functionality $f(x,y)$ which outputs 'answer' with probability $1-\textrm{negl}(n)$ for some security parameter $n$, and 'other answer' with negligible probability. Consider a Simulator $\mathcal{S}_1$. Now wlog, if I show that $\textrm{view}_1(\Pi)$ is computationally indistinguishable from $\mathcal{S}_1(x, f_1(x,y))$, can I conclude that the joint distribution $[\mathcal{S}_1(x, f_1(x,y)), f(x,y)]$ is computationally indistinguishable from $[\textrm{view}_1(\Pi), \textrm{output}(\Pi)]$?
The reasoning would be that the joint distribution is only affected by a negligible factor of the uncertainty of the output.


texts: Brute-force attack given small search-space and hash prefix

texts:
Suppose we have a value $secret which is a random 56-bit (7-byte) string. Suppose an adversary wishes to discover $secret.  The adversary cannot directly see $secret, but he can see substr(sha1_hex("$secret $salt"), 0, 8) (where $salt
is public -- and perhaps irrelevant to our calculations).

Since $secret is only 56-bit, it may be vulnerable to a brute-force attack by a modern supercomputer -- if you can find an offline test. An attacker might use the hash-prefix as a test:

    function brute_force_hash_prefix($targetHashPrefix, $salt)
      $candidates = array()
      foreach possible $candidate which is 56-bits long
        $candidateHashPrefix = substr(sha1_hex("$candidate $salt"), 0, 8)
        if ($candidateHashPrefix == $targetHashPrefix)
          $candidates->add($candidate)
      return $candidates

However, the test is not deterministic -- the attacker only has the first 8 hex digits (32-bits) of the SHA-1 hash. This creates a risk of false-positives (ie the brute-force attack may return multiple $candidates which all yield the same first 8 hex digits).

The question: statistically speaking, how many $candidates should one expect to produce?

(Why would one care? If the odds are that only one $candidate will come through, then it's basically over.  Then again, if there are thousands or millions of candidates, then the attacker has narrowed the field...  but still needs to find some additional means for testing/filtering $candidate.)


texts: Is a random circuit likely to compute a one-way function?

texts: I remember reading somewhere that (under certain reasonable assumptions) a Boolean circuit with many inputs and outputs (assume equal number for now) chosen at random will be a one-way function with high probability.  Is this true?


texts: Is it possible to actually verify a “sponge function” security claim?

texts:
When using a “sponge function” to create a cryptographic hash, we can look at the flat sponge claim, which flattens the claimed success probabilities of all attacks using a single parameter: the claimed capacity cclaim

Is there any way to actually verify the probability of that claim - in this case: potential probability of collisions of the “sponge function”-based cryptographic hash - and what would such a proof formula/calculation look like?


texts: Is script execution time a decent source of pseudorandom number generation?

texts:
This is for a PHP script for password generation.
Naturally there are other things being calculated before the password is generated.
But I figure the time it takes for the script to initialize and queue would make it decently pseudorandom.
Has there been studies on script execution time as a source of pseurandom number generation?

If not, any tips on how to conduct cryptanalysis on this?


texts: The 9 lives of Bleichenbacher's CAT, it puts another scratch again

texts:
Bleichenbacher demonstrated a padding oracle attack against RSA implementations that follow the PKCS #1 v1.5. Through the years, there are various mitigation techniques developed as OAEP and limiting the number of query execution over a period of time. OAEP has been proven secure in the random oracle model.

In November 2018, Ronen et. al demonstrated in The 9 Lives of Bleichenbacher’s CAT: New Cache ATtacks on TLS Implementations that Bleichenbacher is still applicable.

How does the new attack work at top level?
Which TLS implementations are affected?
How one can mitigate from the attack?


texts:
I was looking at RFC5647: AES Galois Counter Mode for the Secure Shell Transport Layer Protocol and had some questions about section 7.1 "IV and Counter Management". Here's that section:

7.  Processing Binary Packets in AES-GCM Secure Shell

7.1.  IV and Counter Management

   With AES-GCM, the 12-octet IV is broken into two fields: a 4-octet
   fixed field and an 8-octet invocation counter field.  The invocation
   field is treated as a 64-bit integer and is incremented after each
   invocation of AES-GCM to process a binary packet.

         uint32  fixed;                  // 4 octets
         uint64  invocation_counter;     // 8 octets

           Figure 3: Structure of an SSH AES-GCM Nonce

   AES-GCM produces a keystream in blocks of 16-octets that is used to
   encrypt the plaintext.  This keystream is produced by encrypting the
   following 16-octet data structure:

         uint32  fixed;                  // 4 octets
         uint64  invocation_counter;     // 8 octets
         uint32  block_counter;          // 4 octets

           Figure 4: Structure of an AES Input for SSH AES-GCM

   The block_counter is initially set to one (1) and incremented as each
   block of key is produced.

   The reader is reminded that SSH requires that the data to be
   encrypted MUST be padded out to a multiple of the block size
   (16-octets for AES-GCM).

So let's say you invoke AES GCM twice and that the invocation counter is 0 (for simplicity sake). The first invocation encrypts two blocks and the second invocation encrypts one. What would be the source material for the encrypted keystream the second invocation?

For the first invocation, first block, it'd be this:

     uint32  fixed;
     uint64  0;
     uint32  1;

For the first invocation, second block, it'd be this:

     uint32  fixed;
     uint64  0;
     uint32  2;

For the second invocation, first (only) block, does the block_counter advance, as well, or does it reset? Here's what it'd be in the case of the former:

     uint32  fixed;
     uint64  1;
     uint32  3;

Here's what it'd be in the case of the latter:

     uint32  fixed;
     uint64  1;
     uint32  0;

eg. is the block_counter reset or incremented when the invocation_counter incremented?

Also, unless I'm mistaken, this approach breaks with tradition for SSH encryption in that encrypt(S1) || encrypt(S2) == encrypt(S1 || S2) (where || is the concatenation operation). That's how pretty much how it works with every other symmetric cipher for SSH but not this one.


texts: Turing's (still?) classified inference engine algorithm?

texts:
Does anyone know the algorithm used by Turing's Colossus inference engine, so highly classified that the Brits kept it secret for decades after WW II?

Indeed, it may still be classified.  Several years ago a colleague of mine, the late Robert Johnson, sent me an email response to my announcement about the Hutter Prize for Lossless Compression of Human Knowledge.  Bob was the guy who designed the Burroughs zero address architecture used for so many years in banking (and incidentally invented magnetic ink used on checks).  He certainly had a lot of background he didn't advertise, including classified work.

  Computerdom does not have a lot of art in inference engines (making
  predictions).  The most effective inference engine that I know of is
  the software done for Colossus, Turing's code breaking "computer" of
  WWII.  The Brits still treat that software as classified even though
  the hardware has been declassified for years.  So far as I know,
  nobody outside of  UK knows the details of that software.  My point
  here is that drawing understanding from natural languages is a
  relatively small art practiced mostly by cryptoanalysts.  And my
  further point is that the natural language of interest (be it English,
  Chinese, Mayan or ...) has a major influence on how one (person or
  program) goes about doing analyses and making inferences.   From a
  practical perspective, the Hutter challenge would be much more
  tractable for at least me if I could do it in Chinese.  My first PhD
  student was Jun Gu who is currently Chief Information Scientist for
  PRC.  His thesis was on efficient compression technologies.   If you
  wish, you can share these thoughts with whomever you please.

  Bob Johnson Prof. Emeritus Computer Science Univ. of Utah


texts: What about using only XOR gates in homomorphic encryption?

texts:
What if we were substitute the ANDs with XORs in some homomorphic encryption scheme like BGV(https://eprint.iacr.org/2011/277.pdf), LTV ( https://eprint.iacr.org/2013/094.pdf) ? It may be more efficient ?
For example if we can substitute an AND with 6 XORs, we would achieve a better efficiency for some choice of the parameters.


texts:
I recently read Improved Generic Algorithms for 3-Collisions by Joux and Lucks (Asiacrypt 2009), available as http://eprint.iacr.org/2009/305.pdf. I was wondering about applications of this technique (excluding of course the applications already given in appendix).
So my question is: Are there interesting applications (constructive or cryptanalytic, preferably practical) of this method that have been proposed since 2009 ?


texts: Ensuring CSRNG integrity in reduced range

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

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

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

My suggestion is to:

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

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

In code (C#), I proposed:

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

}

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


texts: Assuming a randomize encoding scheme that takes as input a secret key $\mathsf{sk} \in \mathbb{Z}_p$ for a large prime number $p$. Then the algorithm outputs $g^{\mathsf{sk}x}, x \in \mathbb{Z}_p^*$. Analyzing the privacy of the scheme where we can reduce its security for dinstinguishing encodings of $x$ based on an indistinguishability based definition?


texts:
I know that there exist some attack when using same modulus.
Can two different pairs of RSA key have the same modulus?
RSA cracking: The same message is sent to two different people problem

But with a little modification,
$m$ is the plain-text
$N$ is the RSA modulus
$r_1, r_2$ is the random padding
$e, s$ is the public exponent
$C_e, C_s$ is the cipher-text

encrypt as follow
$$С_e = (m + r_1)^e   \bmod N$$
$$С_s = (m + r_2)^s   \bmod N$$

If attacker only knows $C_e, C_s, r_1, r_2, e, s, N$.
Is it possible to know $m$?

It seems the RSA cracking: The same message is sent to two different people problem does not work?


texts: Secret sharing where the combination of shares matters

texts:
In Shamir's secret sharing scheme, any combination of shares (that pass the threshold) will result in the secret being revealed. Is it possible to have a system where some combinations are invalid?

For example, imagine a company's trade secret is split into 10 shares with a threshold of 3. You give 3 to the CEO, 2 to each executive (of which there are 2), and the remaining 3 shares go out to 3 secretaries. This has this effect.

CEO(3)                      = 3 -> Secret recovered
Exec(2) + Exec(2)           = 4 -> Secret recovered
Exec(2)                     = 2 -> Secret NOT recovered
Secr(1) + Secr(1)           = 2 -> Secret NOT recovered
Secr(1) + Secr(1) + Secr(1) = 3 -> Secret recovered

It also allows for this case.

Exec(2) + Secr(1) = 3 -> Secret recovered

In this case, an executive needs only to consult a secretary before unlocking the trade secret.

Is it possible to have a scheme where an executive's shares and a secretary's share cannot be combined?

I can think of ways to extend Shamir's scheme to have this behavior in this example. For instance, using two instances of the Shamir scheme to make the executives' shares and the secretarys' shares be incompatible. This has the problem that you need to maintain two copies of the same secret. I'm looking for a better solution.


texts:
Let's assume that the Intel RDRAND instruction does not return fully random numbers, e.g. because it has been engineered with a backdoor for the NSA.

If the Intel RDRAND instruction is used directly by a software implementation, what post-processing could be performed to make sure that the output would be indistinguishable from random again? The procedure should not be CPU intensive as an application could as well use the OS provided random number generator if that was the case.

Presumption: the random numbers returned by RDRAND do at least comply with FIPS tests against the output for random numbers.


texts:
I'm currently working on a proof in the Random Oracle model, and could not find the formal argument on why the random oracle is one-way (i.e. for an Oracle $O$, it is easy to calculate $x=O(n)$, but not efficiently possible to compute $n = O^{-1}(x)$).

Now, I know that the random oracle has that property, and it is intuitively obvious why (as the output is randomly chosen, it is independent from the input and does not contain any information about it). However, as it is not part of the formal specification of a random oracle as per Bellare and Rogaway (as far as I know), I'd like to know how you would formally prove it, based only on the formal specification of a random oracle.


texts: How does the index of coincidence work in the Kasiki test?

texts:
I'm starting to learn about cryptanalysis and I am having a bit of difficulty understanding the Kasiski test's index of coincidence. I have a book (Cryptography Theory And Practice by Douglas Stinson) about it that I'm going through, but it seems to skip something, which is causing my confusion. More likely it's me who is constantly missing a line or something.

The book gives the example:

CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBWRVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGXWTRZXWIAK...

and uses CHR to find the possible keyword length. It occurs 5 times in the total ciphertext, which I did not type out completely. To show that the key is most likely 5 characters, the book also shows the index of coincidence for words of length m, from 1 to 5.

What I don't get is how it got the index of coincidences for the ms.

  With m = 1, the index of coincidence is 0.045. With m = 2, the two
  indices are 0.046 and 0.041. With m = 3, we get 0.043, 0.050, 0.047.
  With m = 4, we have indices 0.042, 0.039, 0.046, 0.040. Then trying
  m = 5, we obtain the values 0.063, 0.068, 0.069, 0.061 and 0.072.

Even with the formula to get the index of coincidence, I don't see how the values were gotten. Can someone please explain?


texts: Relying on a private public key for authentication

texts:
I'm Alice, and I generate a public/private key pair. I securely & confidentially share my public key with Bob and Carol, who securely & confidentially share it with various other benevolent users – all of whom can now send me encrypted messages that only I can decrypt.

I'd like to authenticate that the encrypted messages I'm receiving are from users that have been legitimately sent my public key. Malicious Mallory has not been sent my public key, but has access to the network and can see the encrypted messages that I'm being sent. I need to ensure she cannot deduce my public key to send me malicious encrypted messages.

What do I need to look for in a crypto library to achieve this?


texts: How can Alice enable Bob to look-up values in a private map

texts:
I think this problem is similar to private set intersection, yet distinct in a way where:
Alice has an extensive Mapping of say id to name

id1 -> John Doe
id2 -> Jane Doe
id3 -> Edgar Poe

Bob has a short-list of id's say

id1 (Alice knows the name of this person)
id3 (Alice knows the name of this person)
id4 (Alice doesn't know the name of this person)

Neither Bob, nor Alice wants to share all their data assets with each other. However Alice has agreed to share the names of the people for whom Bob has knows the id.
Bob on the other hand, doesn't want Alice to know which id's he has.
Are there any known, secure protocols which only involve two parties? (no-trusted 3rd parties etc)


texts: How to find g in Factoring-Based Trapdoor Hash Function

texts:
Please explain how to find a value of $g$ if
$p,q$ are safe primes having $p'=(p-1)/2$ and $q'=(q-1)/2$ are also primes
$n=p*q$
$\lambda() = \operatorname{lcm}( − 1,  − 1) = 2''$.
How to chose at random an element $g$ of order $\lambda()$?


texts: How much entropy do you need for a secure certificate generation?

texts:
So in OpenSSL you have the -engine tag for inputting your own entropy as a source for generating whatever.

So if you wanted to generate a 2048-bit RSA certificate how much entropy would you need for it to be secure?
Is 1 truly random byte or even one bit of entropy enough for generating a secure certificate?
Do you need more entropy for bigger certificates?
Is the entropy used raw or is it mixed with something else (in the case of openssl -engine)?


texts: Given a hash function; assuming domain % codomain = 0 and uniform collision distribution; how is entropy lost by collisions (not output truncation)?

texts:
Assuming our domain and codomain both have 4 elements, the uniform distribution of inputs to outputs means the function is injective. It is widely agreed that randomly selecting a domain element results in log2(4) = 2 bits of entropy in the selection, and that because of being injective, the output of said function input this selection will also contain 2 bits of entropy.

If we double our domain element count to 8, then a random selection will have log2(8) = 3 bits of entropy. Because of pigeonhole principle there are collisions, but we defined a uniform distribution, so each of the 4 codomain elements has two domain elements mapped to it.

In the second case, clearly the 3 bits of entropy of the input can't be preserved in the output, but why would fewer than two bits of entropy be preserved? Isn't it still just equiprobably selecting an element from the codomain, given the lack of bias as defined by the uniform distribution of collisions?

In both cases, is it not preserving the entropy of the input up to the bit length of the output? Which is log2(4) to cover the 4 elements of the codomain.


texts: How Shannon’s concept of perfect secrecy is linked with mutual information?

texts:
For a system to be unconditionally secure

  $H(K) \geq H(M)$, i.e entropy of the secret key must be at least as great as the entropy of the plaintext

The mutual information is:

  $I(X;Y)=H(X)-H(X\mathrel|Y)$

The mutual information will be equal to zero if $H(X\mathrel|Y)=H(X)$.  That means the ciphertext does not leak any information about the key.

is it correct?