texts: Hardware Gaussian random numbers for lattice-based cryptography

texts:
I have been recently reading about lattice-based cryptography.

I read that a key aspect of such protocols rely on added Gaussian noise on lattices, and which therefore require highly efficient and constant-time Gaussian samplers, which appears to need non-trivial algorithms. For what I got this is still something that could be improved in lattice-based cryptography.

I know that there are hardware random number generators that naturally produce Gaussian distributions. For example, thermal electronic noise from active and passive components often shows Gaussian behaviour. Also some optical random number generators are known to produce unpredictable and normally distributed random numbers.

My question is: could Gaussian hardware random number generators play a role in adding the Gaussian noise required for the security of lattice-based cryptography?

Or is there something fundamental that I am missing about how these Gaussian sampler must be built? Perhaps related to the choice of the standard deviation? Or because some determinism is preferred?

Any help in understanding this would be helpful, and also any instruction to where to find a good, (simple :-D ) introduction to Gaussian sampling in lattice-based cryptography.

I am very new to the field, so forgive me if I said anything imprecise or incorrect

Kind Regards,
Rafa


texts:
I'm having trouble understanding why and how an oblivious transfer (OT) is used in e-voting systems.

According to many descriptions of OT's, a receiver (I suppose that's the ballot collector?) can choose whether he wants to receive $m_0$ or $m_1$ from the sender (the voter?).

How is it used in e-voting, and what security property does it help to achieve?


texts: Simplified Key Wrapping to Achieve Only Confidentiality?

texts:
I'm looking for help in understanding why the algorithm described here would not deliver adequate protection of confidentiality.  We don't care about other criteria such as authenticity or integrity.  In other words, we only want to make sure our key material is secret.

Given a key $k$ that is $l$ bits long, a hashing algorithm $H$ that produces an $l$ bit digest, a password $p$ of at least $n$ bits (smaller than $l$), and a randomly generated $l$ bit salt $s$, we produce an $l$ bit wrapped key $W$ by:

$$\begin{align}
    W &:= H(s||p) \oplus k &\text{(Wrap)}
\\  k' &:= H(s||p) \oplus W' &\text{(Unwrap)}
\end{align}$$
where $W'=W,k'=k$ if the transmission has not been tampered with (nb: we do not care if it has).

We know that authenticated encryption would be better.  At this time hashing is our only tool.

Are we falling prey to a fearsome Birthday Attack?

It appears that a related question was asked before though they were more ambitious and the answer isn't clear.

Hash Based Encryption (fast & simple), how well would this compare to AES?

Update (28 Apr): As my goal is to help eliminate some of the confusion, I'd like to amplify the answer.  I'm reading that malleability refers to the relatedness of ciphertexts, vis a vis Dolev, Dwork, Naor.  Specifically, we know that a certain number of bits in the ciphertext need to be inverted to recover the key.  We're also pretty certain that that all of the bits need to be inverted thereby reducing the search space.  The relationship between malleability and the chosen-ciphertext attacks is well known.

FWIW, if AES were available there would be no reason to consider anything other than one of the established key wrapping algorithms such as the NIST AES KeyWrap.

To summarize, the intention of using a hash function in the proposed construction is to build a reversible transformation from an inherently non-reversible function.  Because of the malleability introduced by the XOR there is no number of iterations of the hash to slow the pace of a brute-force search that would compensate for the fundamental weakness of the algorithm.

Many thanks.


texts: Sieving the sequence $x^2-n$ to recognize b-smooth numbers

texts:
I am currently programming the quadratic sieve and have several literature books / papers and will take an example out of [1] for my question:

[1] An Introduction to Mathemtaical Cryptography by J. Hoffstein, J. Pipher and H. Silverman.

[2] Prime Numbers by R. Crandall and C. Pomerance.

[3] Smooth numbers and the quadratic sieve by C. Pomerance.

To factorize a number $n$ with the quadratic sieve, we are looking for a product of numbers $x^2-n$ giving a perfect square. The numbers $x^2-n$ has to be B-smooth. We also only look prime numbers where the jacobi symbol is $(\frac{n}{p}) = 1$, so we can solve the equation $a^2 \equiv n\ \textrm{mod}\ p$ for every $p$ with $2 \leq p \leq B$. If $p = 2$ there is only one solution and for $p \gt 2$ there are either no solutions or two soluions. But in our case are always 2 solutions, because $n$ is a quadratic residue for our prime numbers.

I will now come to the point where my problem starts. In [1] and [3] is the sieve step explained to recognize B-smooth numbers in our sequence $x^2 - n$. We are looking for the numbers $x$ where $p\ |\ (x^2- n)$.

The values of $x$ can be found "easily" by the roots of $a^2 \equiv n\ \textrm{mod}\ p$ namely the number $x$ which are congruent to $a_1 \textrm{ mod } p$ or $a_2 \textrm{ mod } p$ ($a_1, a_2$ are the roots of $a^2$).

So, we start with the first number in our sequence $x^2-n$ where $x \equiv a_1 \textrm{ mod } p$ and then every $p$-th entry is divisible by $p$. We start again at some start point of $x^2 -n$ and look for a number $x$ for which $x \equiv a_2 \textrm{ mod } p$ hold.

Now I have tried to this with some example from the book but it will stop getting the correct entry of $x$:

In [1] is the example for the number $N = 9788111$. Also, the first 20 numbers which are 50-smooth are listed with the factorization of $x^2 - n$.

The first $x$ is $x = \Big\lceil\sqrt{N}\Big\rceil = 3129$.

It starts now with:

$3129^2 \equiv 2530 \textrm{ mod } 9788111$

$3130^2 \equiv 8789 \textrm{ mod } 9788111$

$3131^2 \equiv 15050 \textrm{ mod } 9788111$

...

$4394^2 \equiv 9519125 \textrm{ mod } 9788111$

Until this number everything works. My program gives the correct factorization. And if we test it with the prime number $p = 7$ and the roots $a_1 = 2$ and $a_2 = 5$, we see that $3131 \equiv 2 \textrm{ mod } 7$. So, we can divide $15050$ with $7$.

But the next number in the list, which is 50-smooth doesn't hold the procedure:

$4425^2 \equiv 4403 \textrm{ mod } 9788111$ and $4403 = 7 * 17 * 37$

We see, that $4403$ is divisible by $7$. That means that $4425$ has to be congruent to $2 \textrm{ mod } 7$ or $5 \textrm{ mod } 7$. But it's not. That means, that at some point I can't just count $x$ with $p$ to get the next number in the sequence which is divisible by $p$. I think its because that the result of $x^2 - n$ is bigger than $n$ self at some specifically $x$ like $4425$:

$4425^2 - n = 19580625 - 9788111 = 9792514 > 9788111$

So, my question is what is the reason that at some $x$ it doesn't work anymore? What can I do to restart the procedure with counting $x$ with $p$ to recognize the valid spot to divide with $p$.


texts: What is the origin of the phrase "Don't roll your own crypto"?

texts:
The phrase is well-known and widely used, it is often attributed to Bruce Schneier and is indeed relevant to his Schneier's Law. However, I wasn't able to find this specific wording among Schneier's publications.

Is there any single author of the phrase, or was it just collectively generated as a convenient "meme" version of the Schneier's law?


texts:
I using a microcontroller which only support AES-ECB encryption i.e. no decryption-mode, CBC, GCM or similar modes.

However, I'm wondering if it's possible to implement AES-CTR or similar on top of AES-ECB?

I'm grateful for help, tips, similar implementations etc.

Cheers


texts: Is it possible to guess encrypted data if we have multiple ciphertexts of it?

texts: If we have an array of ciphertexts based on the same data encrypted with different keys (e.g. sharing the data with different persons using different 128 bit keys), then is it easier to an attacker to guess the data without knowing any of the keys? If so, then is there a way to harden this kind of encryption? (To be more specific the data is a 128 bit group key encrypted with the personal key of each person.)


texts: Timestamping using a hashed linked list and public known events

texts:
Let's say we have a timestamping scheme of the following characteristics,

The hashes of the documents we are trying to timestamp are XOR'ed with "events" whose time of occurrence are very publicly known (i.e. the hash of the latest block on the blockchain),

$$M_{i}=(H_{D_{i}} \oplus B_{t_{i}})$$

Where,

$M_{i} =$ the hash of the document "mixed" with a known public event,

$H_{D_{i}} =$ hash of document to timestamp,

$B_{t_{i}} =$ hash of the latest block on the blockchain (a very known public event) at the time of timestamping ,

The concatenation of $M_{i}$ and the previous timestamp gets hashed together forming a new node on a hashed linked list,

$$H_{i} = Hash(M_{i} ||H_{i-1})$$

Where,

$H_{i} =$ the timestamp of the document.

Each $H_{i}$ is then published in "real time" into an independent (no relation to the timestamper) public third party platform so that anybody can potentially monitor any modification to the list. An example of this type of platform could be Twitter where each tweet is the concatenation of the current and previous timestamp,

$$T_{i} = H_{i} || H_{i-1}$$

Where,

$T_{i} =$ Public reference of the timestamping (i.e. a tweet).

That being said,

What are your thoughts of the following assertions?

Future-dating a document (even in collusion with the timestamping service) would be not feasibly because of the unpredictable nature of the public event (i.e. it is not feasibly to know what the hash of the next block in the blockchain is going to be unless someone mines it).
Backdating a document, even in collusion with the timestamping service, would not be feasibly because of the nature of the hashed linked list.

Does anybody know if a scheme like this is already described and/or implemented somewhere?
What are your thoughts about the weaknesses of a scheme like this?


texts: Will a list of all prime numbers upto certain number of bits compromise crytopgraphic algorithms based on prime factorization?

texts:
I understand that many cryptographic algorithms depend on the difficulty of large prime factorization.
Will a  list of all prime numbers upto certain number of bits make it easy for an attacker to compromise such algorithms?


texts: I am trying to understand what are the benefits of using Damgård–Jurik over Paillier. I understand that expansion factor decreases as s increases. But isn't it the case that this comes at the expense of security? If your goal is to reduce space overhead compared to Paillier then you might choose a smaller security parameter and a higher value for s. Or to put it otherwise for a fixed security parameter as s increases cipher-text size increases. So why not just use Paillier with a smaller security parameter?


texts: cryptographically good random elliptic curves?

texts:
After an answer here, about generate elliptic curves, I've start thinking about the algorithm. The mentioned algorithm will produce curves in the Weierstraß Reduced Form (WRF) over finite fields:

  $y^2 = x^3 + ax +b$ with $a,b\in \mathbb{F}_p$

And this WRF is the representation used in the NIST (where $a\equiv-3\pmod p$), Brainpool, and probably some others, that can be used in standards like the extension for OpenPGP or TLS.

But this is only one of many ways to describe elliptic curves. In TLS specification it opens to the possibility to use arbitrary curve definition. Or other alternatives are Montgomery curves like the  curve25519 "recently" proposed for EdDSA.

If I like to generate my curve (ignoring the fact that this would affect the maths in the implementations) are there differences between representations? I mean, would be faster to generate random cryptographically good curves depending on the representation? Will curves with different representation and the same bit length, have the same strength?


texts:
Trying to understand the well known property of these collisions when used with SHA1, SHA256, etc. where a given key is larger than the block size of the digest function. In these cases the smaller of the collisions will have a size of 20 characters for SHA1 and 32 for SHA256 (1/2 the hexadecimal digest length), so does this mean to brute force a PBKDF2-HMAC-SHA1 an attacker only needs to consider passphrases of 20 characters or less? And therefore 32 or less if using SHA256? Are longer passphrases effectively pointless?
Thanks.


texts: How can I determine the GPG/PGP key ID from the RSA modulus?

texts:
According to http://www.pgp.net/pgpnet/pgp-faq/pgp-faq-keys.html#key-public-key-forgery, key ID is some lower bits sequence from the modulus (i.e. the $n$ variable):

  A PGP key ID is just the bottom 64 bits of the public modulus (but only the bottom 32 bits are displayed with pgp -kv).

I have a key pair. According to pgpdump, my key ID (i.e. 64b) is the following one 0x6BA09C369E31148C. According to GPG, my key ID (i.e. 32b) is the following one: 0x9E31148C. Well, this is just the last 32 bits from the 64b key ID.

I'd like to see a relation to my public modulus. I haven't found any, even if I play with endianess.

The key id is also weird… if it was last 32b (or 64b) from the modulus, it should be an odd number (except if $p$ == $2$ || $q == 2$$, which is very unlikely).

However, when I search lower 32 bits in my modulus (dumped by pgpdump), I see 0x84cfe5c1, which is far different from 0x9E31148C:

RSA n(4096 bits) - c8 1a 2e 7d e5 22 84 5c 10 b9 02 3b 42 ff 09 4c 60 f9 8a ce 80 64 8a 95 6a 0e 53 23 a3 dc fb fb f5 96 c7 a2 de be a9 f0 c8 f8 d8 51
6d e8 bc 64 13 16 5e 25 f9 4d 44 bc 51 ef 7f 97 b4 05 a3 d9 9e e3 58 ef 88 c1 bb e5 23 65 45 1b 99 7b 68 c1 e4 1a 7d bc fb 51 c1 41 d6 10 33 34 90 c3 91 5c 5b
ae 48 63 4e 65 46 4e 35 8e 48 e6 85 e3 9b ff b2 4b e9 c6 aa f1 45 3f b8 b6 b5 be 56 f8 04 4e 1d 1a d4 78 4d 75 fa 5e aa 2d 6d dc 31 2b c8 28 db cb 10 34 1a 16
2c fd e2 67 e7 1d 0b e6 cc 53 92 5d 85 40 57 5c 9f 23 bb af 75 d9 11 2b 4a a0 6c ef c4 50 85 eb 79 46 b2 f7 03 54 8a c9 15 c0 ac d8 d4 5a 7c 5e 37 5e cc f2 13
8a 67 3c 1f 26 c5 f4 11 d0 38 19 9c 34 0f c0 3d e7 63 67 8e 3f 7d 82 2e b6 59 d3 da 74 61 68 1c 78 7b 4c ce c3 5a f0 18 8c 3b ab 3c 88 03 28 6b 93 f5 b9 eb eb
44 51 a7 b8 34 08 e9 a7 fa 81 d3 af 3d a0 f7 fa 6b f9 fb 98 97 38 32 d1 1f e4 e7 1a 4d af e3 e9 87 f8 ca b1 10 91 e5 9c fc db 4b 2d 23 3a 3f c3 fc 1b fe 15 c1
df ff a2 0e fb 51 fe c3 1c 67 26 f3 f3 9d 50 ff 8b a7 48 f4 57 1c e8 63 e9 1e 1b 4a 27 96 02 9c 06 5a 62 ed 99 80 02 13 b2 31 66 a8 ee 79 15 85 05 61 81 67 0f
b7 c6 4e d9 5f 31 81 64 d7 16 13 a8 70 a5 26 6f dc c3 cd f7 d3 8a 3d ab 79 60 34 6d 4e 9b f7 ef 32 eb 65 75 63 f4 79 1c 43 a8 ae 64 53 fd 56 77 d4 df 68 1e b6
05 b0 d1 1d 7c fc 10 5a a3 aa eb 90 90 a8 6d 15 a6 8c 03 85 97 7b 0f 15 fe 19 07 ff 12 ff 10 87 fe bb 85 7b d3 98 34 24 8e c0 cb 5f 9a 42 81 71 76 3c fc 2d fb
55 40 98 56 b0 b6 bd 26 8d bd 66 86 9a b2 49 cf a8 0f 4d 3c ed 62 34 79 4f 98 bd 5c 73 dc e5 45 cf 3f e0 a6 4a 59 e2 09 84 cf e5 c1

Where is the mistake in understanding the Key ID?


texts:
If I run openssl ec on a key that I have generated with openssl ecparam -genkey I get one extra prefixing 0x00 in the private key, and one 0x04 in the public key. While I understand the 0x04 which means uncompressed format, I don't understand the 0x00 in the private one. If I use the openssl asn1parse that 0x00 gets discarded correctly when showing the 32 bytes of the key.

read EC key
Private-Key: (256 bit)
priv:
    00:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:
    xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:
    xx:xx:xx
pub:
    04:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:
    xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:
    xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:
    xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:
    xx:xx:xx:xx:xx
ASN1 OID: prime256v1


texts: How does the Number Field Sieve find the target number for Diffie-Hellman?

texts:
I have read some papers relating to the Number Field Sieve, but I could not figure out how this algorithm helps in Logjam, or even what is meant by the number field. What is this? What is meant by factorization?

I am new to this topic and need a very simple description for the above questions...


texts: in Salsa20, the Key is 128 or 256 bits, the Nonce is 64 bits. the pair (k,r) should never be reused. Does it means, if the key is fixed, the encryption can only run 2^64 times? if the key is not fixed, after running 2^192 or 2^320 times, the pair must be used repeatedly. If I use the this stream cipher in a busy network, does it means it is vulnerable due to the two-times pad?


texts: I am new to ciphers and for my assignment i have to implement a stream cipher algorithm without libraries (on my own). So my question is: Does anyone know about any GOOD books which have examples and explanation of implementation?


texts: How can I create a fixed length output in my hash function?

texts:
I've been recently looking into the creation (and theory) of hash functions, however I just can't figure out how to turn a message into something of a fixed length.

At the moment, my theory of a hash function is like so:

Take in the message (e.g. "secret")
Split it into different 'blocks' (e.g. "sec" + "ret")
Mix them up, and interact different blocks depending on what block type
they are (perhaps block type would be determined by mathematical calculations
on the character values, and then certain blocks would interact with other
blocks to merge in a weird way to create another block).

This creates a message which cannot be undone (since at the end, you don't know what the block types are - and even if you do, you don't know how they interacted to get to those blocks) - however it is not of a fixed length.

What would I do to create a fixed length digest?


texts: Is the last step of an iterated cryptographic hash still as resistant to preimage attacks as the original hash?

texts:
Considering a cryptographic hash, such as MD5 or SHA2, denoted by the function $H(m)$ where $m$ is an arbitrary binary string, there is a lot of material available that deals with potential weakness to preimage attack. I am interested in resistance to preimage attack where the cryptographic hash is applied recursively a number of times.

A classical first-preimage attack asks to determine a message $m$ for a given hash $h$ such that $h=H(m)$.

A related question considers a known value for $H(H(m))$ and asks if $H(m)$ can be determined more easily than $m$ from $H(m)$. The extension asks if $H^{(n+1)}(m)$ is more vulnerable to preimage attacks to determine $H^n(m)$ than it is to first preimage attacks... and, if resistance deteriorates as $n$ increases, how many times can $H(·)$ be applied while it is safe to remain confident the last application of $H(·)$ remains non-invertible - i.e. how many times is it safe to chain this non-invertible function without significantly weakening its resistance to inversion?

I'm also interested to establish if different hashes have different strengths relative to this scenario of repeated application.


texts:
I have been given the task to test the security of our company software. Our company software generates ecdsa signed supply order files. One can generate as many files as he wants.

so my question is Is there any ECDSA Attack if I have millions of signatures?

we are using 112bit prime curve order: 4451685225093714776491891542548933

I have calculated 1 million signatures using the following method:

public void GenerateSignature()
{
    //curve order
    BigInteger n = ec.N;

    Ramdom rand = new Random();

    //private key
    BigInteger d = ((ECPrivateKeyParameters)key).D;

    //loop for 1 million signatures
    for (int i = 1; i <= 1000000; i++)
    {
        //random k and e
        BigInteger e = new BigInteger(112, rand).Mod(n);        //new biginteger by giving bitlength and random
        BigInteger k = new BigInteger(112, rand).Mod(n);

        //calculate r
        BigInteger r = key.Parameters.G.Multiply(k).X.ToBigInteger().Mod(n);

        //calculate s
        BigInteger s = k.ModInverse(n).Multiply(e.Add(d.Multiply(r))).Mod(n);

        //save generated signatures to database
        new DBCon().ExecuteNonQuery("Insert into signatures values ('" + e.ToString() + "', '" + r.ToString() + "', '" + s.ToString() + "')");
    }
}

I am using BouncyCastle crypto library with C#.

I know private key can be calculated if k value is known by d = (sk - e) / r

I also know private key can be calculated if two signatures have identical r value then we can calculate k by k = (e1 - e2) / (s1 - s2) and then d by using above formula.

I also know that private key can be calculated if some bits of k are known using about 100 signatures with lattice attacks, but in this case bits of k are unknown.

any help will be appreciated. Thanks.


texts: Difference between "one-way function" and "cryptographic hash function"

texts: What's the difference between a one-way function and a cryptographic hash function?


texts: Why authors of bcrypt have chosen blowfish and not some hash function like SHA-1?

texts: I wonder what are the advantages of using bcrypt over an iterated and salted KDF based on some cryptographic hash function like SHA-1 (or SHA-3)? I guess the authors of bcrypt chose Blowfish (a block cipher) for a serious reason, but we could barely replace it in with SHA-1/SHA-3 (a hash function). What is wrong with such an approach? What are security properties brought by a block cipher that are not by hash functions?


texts: Difference between the TLS cipher suites?

texts:
TLS_DHE_DSS_AES256_CBC_MAC / TLS_DHE_RSA_AES256_CBC_MAC

Hi, I have been studying to learn about various cipher suites and their performances. I gathered that DSS is efficient when compared with RSA. Is it correct and please anyone explain me about their performances and differences?


texts:
Let $c ≥ 2$. A code $C ⊂ Q^n$
is a $c$-frameproof code if for any set
$X ⊂ C$ with $|X| ≤ c$ we have
desc$(X) ∩ C = X$.
Thus the only codewords that a coalition of up to $c$ pirates is capable of producing are those
that already belong to members of that coalition. To see a definition of desc$(X)$, see here.

What I want to know is, from the definition above can I say the following is not a 2-frameproof code?

$012,011,222,112$

As for example $012$ and $011$ agree in more than one position but I don't know if it must be the case that for any two of the codewords, they will have to agree in more than one position?? As $222$ and $112$ only agree in one position for example.


texts: After downloading the Breach Compilation.torrent, how do I properly introduce new breach lists?

texts:
So I downloaded the Breach Compilation (the 1.4 billion usernames w/ respective passwords). When doing so, the friendly dev-like homies they are over @ github where the .torrent file for the latter is posted, were kind enough to implement a sort utility, among others (such as a lookup tool etc.).

just wondering how I add new breaches to the collection properly. Any help would be much obliged. Hopefully we're allowed to post links in here, not to sure on the rules yet so forgive me ahead of time if its a no-no.

the 1.4 billion breach list comp and tools can be found here:

     https://gist.github.com/scottlinux/9a3b11257ac575e4f71de811322ce6b3


texts: How does a cracker know if they've broken AES-CBC encryption?

texts: How does a cracker know if they've broken CBC or stream encryption? With hashe cracking one would know because you have the password that you started with to test. But for CBC decryption, you have a 16 bit block (AES), a key, and an IV. With the wrong key one will get random data as output. So how will one know when the right key was found? The output may be binary so how is it determined if the decryption was a success? Does the attacker require knowledge of the type of contents, to search for magic numbers or headers?


texts: How is it possible to parallelize a hashing function to crack an iteratively hashed password?

texts:
Suppose I have an algorithm that relies on multiple iterations of a hash function like SHA1 to slow down an attacker trying to bruteforce a hash.

digest[0] = hash(password + salt)
for i in 1..r:
    digest[i] = hash(digest[i-1] + password)

The final digest[r] is then used as the hash. How does this compare to a more standard implementation like PBKDF2 or bcrypt?

This website states:

  simply iteratively hashing the hash of the password isn't enough as it can be parallelized in hardware and executed as fast as a normal hash.

Is there any truth to this statement? Since every iteration of the hash function is dependent on the previous, how could this be possible?


texts: How likely is it that AES-256 is crackable within 100 years (2120)?

texts:
When people ask for a block-cipher with a larger key space than AES-256 replies usually just state that there is no need. I see where that is coming from the future is hard to predict.

The two main problems I can see are Grover's algorithm (see below) and the fact that we can not see all the problems.

I have no idea how powerful quantum computers will be in 2120 so we may consider upper bounds. e.g. At 20ºC, the Landauer limit* is about 2^-80 watt-hours per bit. I do know that some other ciphers (like threefish) have larger key spaces.

The fact that AES may be broken within 100 years (exactly) was apparently addressed by the OneHundredYearCryptography project by XORing it with XSalsa20.

To reiterate I want to know if AES-256 will be safe throughout our life time.

*To the best of my knowledge, experimental quantum computers that operate at the limit are actually much faster than other experimental computers that are also at/near the limit. I don't know if there is a price difference however.

Edit for background: Grover's algorithm is an attack that is analogous to brute force attack. The differences are that its complexity is the square root of the key space (2^(256/2)) rather than the key space itself, and that it can only be run on a quantum computer. I'm confident that no conventional or quantum computer will be able near-brute-force it, but I'm not that sure that a quantum computer won't be able to Grover it. Therefore, the power of quantum computers by 2120 is of more interest than the power of electrical computers at that time.


texts: Imposibility of bias-resistant coin tossing (Cleve'86) and its connection to modern notion of fairness in Secure Multiparty Computation

texts:
In modern Secure Multi-party Computation (SMPC) protocols (informally) the notion of Fairness and Guaranteed Output Delivery (GOD) is defined as follows:
Fairness: If the adversary gets the output of the protocol, every honest party should get the output as well.
GOD: Honest parties should always get the output independent of adversarial behavior.
As I understand the seminal paper of Cleve'86, it proves that bias-resistant two party coin tossing protocol is not possible in honest minority setting. In particular, Cleve86 shows
that if the honest party decides to output when the adversary aborts, then there exists an
adversarial strategy where the output will not be equivalent to the output of the ideal coin tossing protocol.
What bothers me is that several paper cites Cleve86 and state that it is not possible to have fair (modern notion of fairness) protocol in 2PC. I am not able to connect Cleve86 result to current notion of fairness we talk about it Secure MPC protocols. Specifically, Cleve86 do not say anything about whether the adversary (whenever it aborts) gets any information about the output of the protocol or not.
Consider a protocol where honest party do not produce an output whenever the adversary decides to abort. Is this protocol not fair (with modern notion of fairness)? In my understanding, Cleve86 result is not applicable to this scenario.


texts: Any historical accounts of cryptanalysis of Jefferson's wheel cipher?

texts:
David Kahn in his book "The Codebreakers" wrote about Jefferson's wheel cipher, saying
that

  To this day the Navy uses it…

(the book was first published in 1967)
Are there any historical accounts of successful cryptanalysis of that cipher?


texts: Is DSA vulnerable if verifier doesn't check r' > 0?

texts:
If a DSA implementation neglects to check $r' > 0$ when verifying signatures, what are the consequences? Creating a forged $s$ would seem to require solving for $k$

$g^k mod\ p = nq$

which is still a hard problem?

Assume that all other range checks for parameters are being carried out (particularly $r' < q$)


texts:
Is there an algorithm which allows  using multiple keys for decryption?
I had this scenario in mind:  think about being a boss of a corperation which has an encrypted data base with loads of secret files.
and you only want to allow employees access to the specific files they need to work with, would it be possible to give them keys to only a specific part of the encrypted data (while as the boss, holding a sort of master key to be able to read all)?


texts: Would it be more secure if we used multiple keys in a One-Time-Pad encryption?


texts: Feasible way to check n-dimensional equidistribution of PRNGs

texts:
I am currently gathering some test methods and test suites for random number generator qualities, and am a bit stuck at finding something feasible to test for n-dimensional equidistribution. As input I have an arbitrary amount of bits from that PRNG and a dimension N, and as output I want something like "I am reasonably sure that this is equidistributed in N dimensions". N should ideally be able to go up to more than 600 (It might be a good showcase to see mersenne twister hold up to, but break at 624 with this check)

Now "reasonably" here is quite a bit soft and depends on the efficiency of the tests and the resulting runtime. I don't want to wait days and weeks for an answer. Comparing e.g. with some primality tests, something ideal would be a check that for each iteration halves (or whatever is available) the probabilty of a negative result.

The problem is, I can't find anything reasonable, from an engineering point of view. It seems that for things like mersenne twister these are proven by formal mathematical proves, but that would not work for my testsuite and the desired input. I have found so far the following ideas, but they are not feasible for the mentioned reasons:

Similar to three dimensions I could take a point cloud, orient it "properly", project to lower dimensions and "see" that there are hyperplanes at some orientation that are much sparser/denser than the rest. But unless there is some good way to find that orientation, this is all randomly trying until something is found and it quickly takes up excessive resources when going up in dimensions.
I could just take pairs of N-dimensional coordinates and check those, but apart from getting only a few orientations in the resulting projection, this quickly gets into hundreds of thousand such pairs (which leads to millions of planes to be checked when I go through 1-N)

So is there anything that is relatively efficient with a useful level of confidence? I am thinking of maybe some N dimensional computation with coordinates that is inherently sensitive to a really good equidistribution and already small deviations from that distribution will make it fail/deviate.


texts: determinant of intersection of two lattices

texts:
Say $L_1,L_2$ are contained in $\mathbb Z^r$ with

\begin{gather*}
  \operatorname{rank}(L_1) = \operatorname{rank}(L_2) = r, \\
  \gcd(\det(L_1), \det(L_2)) = 1.
\end{gather*}

How do I prove $\operatorname{det}(L_1 \cap L_2) = \det(L_1)\cdot \det(L_2)$?

It's easy to show that $\det(L_1 \cap L_2)$ is divisible by $\det(L_1) \cdot \det(L_2)$.  My question is how to prove $\det(L_1 \cap L_2) \leq \det(L_1) \cdot \det(L_2)$?


texts: ECDH or RSA more secure for symmetric key wrapping?

texts:
Suppose a message is encrypted with a symmetric block cipher with a random key. RSA is often used to wrap the symmetric key using the recipient's public key.

In this case, the size of the message is increased, as the block size of the RSA encryption (depending on the modulus size) is much bigger than the actual size of the symmetric key. This also leads to using some special padding schemes (like OAEP).

For example: Assuming we want 128-bit security - 128-bit symmetric key, encrypted with 2048-bit RSA yields 256 byte output, which is 16 times the size of the symmetric key.

On the other hand, when the increase in size is an issue, one can make use of ECDH (with some safe curve). Take the recipient's public key $rP$, generate a random value $s$, compute $rsP$ and use KDF to obtain the symmetric key from its $x$-coordinate. The encrypted message is sent along with the sender's public key $sP$.

In this case (for 128-bit security), one uses some safe curve over 256-bit prime field, the size of $sP$ $x$-coordinate is 32 bytes, which is twice the size of the symmetric key.

Here comes my question - besides being more computationally demanding (two scalar point multiplications vs. one exponentiation), are there any additional security considerations one should take when substituting RSA with ECDH in this case?


texts: If a different plaintext may produce the same ciphertext, is the system perfectly secure?

texts:
Define the injective map $\phi: \Omega\rightarrow \mathbb{N}$, such that $\Omega=\mathcal{A}^n$ denotes the set of all strings of length $n\in\mathbb{N}^*$ from an alphabet $\mathcal{A}$ of elements $a_i$ and length $m$. Define a string (to be encoded) of finite length, $\mathcal{M}\in\Omega$. A cipher text $\mathcal{C}$, of arbitrary length $\ell$, exists and may be generated from the probability distribution for all positive integers $i\leq m$
\begin{equation}
p\left(a_i\right)=E\left(\phi\left(\mathcal{M}\right),\alpha,D\left(\mathcal{C},s,k\right)\right).
\end{equation}
Let the set of all ciphertexts $\bf{C}$ be generated from the set of all probability distributions $\bf{p}$$\left(a_i\right)/\sim$, such that there exists some $D'\neq D$ or $k'\neq k$ whereby
\begin{equation*}
        E\left(\phi\left(\mathcal{M}\right),\alpha,D\left(\mathcal{C},s,k\right)\right)\sim E\left(\phi\left(\mathcal{M}'\right),\alpha,D'\left(\mathcal{C},s,k'\right)\right),
    \end{equation*}
if and only if $\mathcal{M}\neq\mathcal{M}'$.
The previous relation means that if the message (plaintext) $\mathcal{M}$ is changed, then there exists a decryption function $D'$ or key $k'$ such that the ciphertext is the same.
If such a systems existed what would be its security? Since knowledge of the probability distribution provides no information of $\mathcal{M}$, I would expect it to be perfectly secure. If so, could this be shown using mutual information?
By the way, the distribution of ciphertext characters converges to $p(a_i)$ as $\ell\rightarrow\infty$, so the equivalence is at least asymptotically true. I would be grateful for any help.
Note that the encryption scheme is symmetric.


texts: How to calculate leaked information from a check digit

texts:
Given a check digit calculated using mod 11, of an encrypted numeric sequence of 8 digits, how much information can be known about the plaintext?

More specifically, a single 3DES encrypted CBC block for which the check digit of the plaintext is known, would reduce by what factor the complexity in discovering the plaintext (and key)?

A second question is whether using the check digit hash as the IV is a good idea?

Example:

Given

encrypted = 0x672985cdd0484611

How much the information

checkdigit= 9

Will help in finding

plaintext = 12345678
key = 0x5e8667a439c68f5145dd2fcbecf02209  # md5(87654321)
iv = 0x45c48cce2e2d7fbd  # md5(9)[:8]

The motivation is to know if the check digit can be stored in plaintext alongside the encrypted data (always one block), and used as seed for the IV.


texts: Why does choosing the first coprime e greater than half of φ(n) result in the same d (private exponent)

texts:
While reading on RSA's algorithm, I attempted a simplified implementation and noticed the following:

When choosing the public exponent $e$, if the value chosen is the first coprime after $φ(n)/2$ then the resulting public and private exponents are equal.

Example:
$p = 67\\q = 53\\n = 3551\\φ(n) = 3432$
$e = 1717$ i.e first coprime of 3432 greater than half
$d = 1717$ where $d \times e\ mod\ φ(n) = 1$
resulting in no encryption
$c(41) = 41^{1717}\ mod\ 3551 ≡ 41$

Problem might be in my code?

So I guess my questions are:

Why does this happen?
Is this even a problem?
What am I missing?

Selecting only public exponents that are primes might eliminate the possibility of this occurring, but I have neither tested nor seen that it's a requirement in the RSA algorithm.


texts:
To obfuscate data I made up this method on the spot without planning since the goal wasn't real encryption.

At first I though this cannot be real encryption but after revisiting the code and reading on block symmetric encryption, and including R in the method, it seems that it is( looks like a stream cypher, OFB specifically ).

The method is the following( pseudo code ):

-Hash function parameters, secret key, hash and array elements all have the same size in bits.
-Size is at least 128 bits for this example.
-Using a cryptographic random generator.

H - cryptographic hash function
K - secret key, randomly generated
A - array of plaintext
L - array length
R - randomly generated, is not encrypted and is stored with the resulting encrypted data

keyhash = H(K)
hash = R
for( i , i < L , i++ )
{
    hash = H( hash ^ keyhash )
    A[i] ^= hash
}

Could this be called encryption or it has some fundamental flaws that would break it immediately?


texts: Generalized Merkle Signatures, SHA-3 and Sakura

texts:
Sakura specifies a tree hash mode for e.g. Keccak (SHA-3). Are there any reasons to use the Sakura tree hash mode in a Generalized Merkle Signature Scheme? It seems to me Sakura primarily solves a uniqueness problem with using tree hashes for large data when the depth of the tree is variable.

Trivially, if Sakura mode is not used and the depth $d$ tree-hash of data $M = M_0|M_1|...|M_{n-1}$ is $D$, then the depth $d-1$ tree hash of data $M'$ (where $M'_0 = f(M_0)|f(M_1)$ etc) is also $D$. If Sakura is used, such trivial collisions will be impossible.

This problem doesn't seem to exist in GMSS, considering that the leaf-nodes consist of OTS public keys and not plain text fragments.


texts: Which block ciphers are considered staples for constructing hash functions?

texts:
I've been looking all over the internet for an answer, and I must not know how to search because I've been really surprised that I haven't been able to find one. I'd also love to know what makes a block cipher a good candidate for being the basis of a hash function.
Thanks!


texts: For data shorter than 32 bytes, is it sure that no collision exists?

texts:
I’m not talking about if a collision can be found but even simply exists.

The point is since it’s shorter than the length of the hash (since I’m talking about keccak256), normally there’s a hash value for each possible data. I mean in that case there’s more possible hash than possible values for input data.

So is the case ? Or by example, can 2 different 16 bytes long number share the same hash ?


texts: How does the certificate trust model work in detail?

texts:
How does the whole achitecture between the certificate authority (e.g VeriSign) and its clients (e.g foo.com) work.

How does my browser know that foo.com hasn't created its own certificate, wrote "VeriSign" as issuer, signed it with its own private key and wrote the corresponding public key into the certificate?

Where is the part in the certificate from foo.com (issued by
VeriSign) that creates the link to its certificate authority? I guess it's certainly not the literal of the issuer (VeriSign).

All the explanations I've got stopped at this point and just stated "the browser checks that it is issued by VeriSign". How does it check that? Is there an algorithm used which allows the clients certificate (e.g foo.com) also to be verified with the public key from the VeriSign and result in the same hash?

certificate from foo.com => client uses the public key from foo.com => receives hash x
certificate from foo.com => client uses the public key from the preinstalled VeriSign root certificate) => same hash x

How are those two certificates interrelated with each other?


texts: Can the premaster secret generated by SRP be used as a secure private key?

texts: It seems like the pre-master secret generated during the SRP protocol would make a good source to generate a shared private key using a secure hash to compress it down into a 128/256  symmetric key.  The random values that get hashed into it seem to make it good for that purpose.


texts: Can you create asymmetrical encryption algorithm from symmetrical, without knowing how the algorithm works?

texts: Let's imagine that we have some symmetrical encryption algorithm, that has only two functions: Encrypt(Data, Key) and Decrypt(Data, Key). Let's say that the algorithm is strong and quick, but we don't know how it works. Is it possible only using those two functions to create a usable asymmetrical encryption algorithm? If not, is there any way to add anything that will help us create one?


texts: How is Diffle Hellman with RSA immune to man in the middle?

texts:
Alice and Bob want to exchange keys, Alice sends his half (the public key of the ephemeral key pair) signed with his private key and makes the public key available. Eve is bridging the connection so he intercepts the message uses the public key and verifies the half. He then sends his half to Alice signed  and establishes a connection. Now Alice is communicating with Eve and Eve is decrypting the message and sending to Bob.

Isnt this exactly same as the raw Diffie Hellman ? How are we exactly preventing man in the middle attack if Alice thinks the whole time that Eve is Bob ? Is it correct to assume that the message(half key) is not encrypted ? Is a certification authority also required for ephemeral diffie hellman ?

Please correct me if I have misunderstood Ephemeral Diffie Hellman


texts: "Batched affine" short-Weierstrass elliptic-curve additions

texts: In https://safecurves.cr.yp.to/rho.html Bernstein talks about fastest possible rho method that uses "batched affine" additions and requires only 5 multiplications mod p, 1 squaring mod p and some small "extra" work that is negligible. Affine means conventional (X,Y) coordinates, no projective coordinates. How is it possible to do group operations on elliptic curve with so little computation and without doing inverse? What exactly he means by "batched affine"?


texts: Security proof of schnorr identification scheme

texts:
I have studied the Schnorr identification scheme, and I came across the security proof.
My question is regarding the following:
$$\begin{align}
\text{Pr}\left[\text{DLog}_{\mathcal{A}',\mathcal{G}}\left(n\right)=1\right]
&=
\text{Pr}_{\omega,r_1,r_2}\left[
  V\left(\omega,r_1\right)\wedge
  V\left(\omega,r_2\right)\wedge
  r_1\neq r_2
\right]
\\ &\geq
\text{Pr}_{\omega,r_1,r_2}\left[
  V\left(\omega,r_1\right)\wedge
  V\left(\omega,r_2\right)
\right]-
\text{Pr}_{\omega,r_1,r_2}\left[r_1=r_2\right]
\\ &=
\sum\nolimits_{\omega}{
  \text{Pr}\left[\omega\right]\cdot
  \left(\delta_\omega\right)^2}-
  1/q
\\
&\geq
\left(\sum\nolimits_{\omega}{
  \text{Pr}\left[\omega\right]\cdot
  \delta_\omega}\right
)^2
-1/q
\\
&=
\delta\left(n\right)^2-1/q
\end{align}$$
With $\delta_\omega \stackrel{def}{=} \text{Pr}_r\left[V\left(\omega,r\right)=1\right]$ being the probability that the adversary will succeed in the identification experiment given that we use $\omega$ (random choices) and $r$ (the challenge).
When we move from the 2nd row to the 3rd, we assume that the event that the adversary correctly responds to the challenge $r_1$ is independent of the event that the adversary correctly responds to the challenge $r_2$.
But, we have no knowledge on how $\mathcal{A}$ is acting - so how can we assume these events are independent?


texts:
I have a couple of related questions:

I read about an estimate, ascribed to Shannon, of the entropy of English text to be between 0.6 and 1.3 bits per letter. The modern day corpus, including the huge and exponentially ever expanding volume of materials accessible via the Internet, is different from the one available a century back. Is there a revised estimate?

If one simply takes two books from one's small private library (that contains e.g. only very common novels) and arbitrarily select two starting points to combine with xor the letters, then the resulting pseudo-random sequence presumably could be argued to have a non-negligible risk of being attacked through brute-force by a knowledgeable opponent. But the actual choice of materials (including especially those via the Internet) to be combined is nowadays virtually unlimited. If one could thus appropriately choose a sufficiently large number of text sources to be combined, wouldn't the result be practically secure for crypto usages in view of the combinatorial explosion of the complexity that the attacker has to deal with? One could certainly also employ some more complex operations than xor and even a couple of different operations either simultaneously or in variations. Are some good schemes in this direction already being used in non-trivial practical applications?

[Added on edit:] A later work of Cover and King give an estimate of 1.34 bit per letter, which implies that appropriately combining 4 text files should lead to sequences of full entropy. Several weeks ago I wrote a software for that but unfortunately, due to a bug in codes used in its design, it had to be retracted for not being satisfactory. I have just released a carefully tested replacement, named TEXTCOMBINE-REV, in which I wrote in Prologue:

What has been achieved by the present software can be tersely summarized as follows, assuming the general case where the text files are sufficiently large:

(1) The generated byte sequences pass, via design specifications of the software, Maurer's universal test and the autocorrelation test for all d in the range [1, 16] as well as the ENT test with an entropy value according to it of at least 7.99 bits per byte. The software is namely coded such that it would give up, reporting failure, after a certain specified maximum amount of processing has been done without finding a solution.

(2) An extensive expermiment of the present author done on all different combinations, totalling 3060 in number, of 4 source materials (of size 600 KB each) taken from 18 different books of English literature downloaded from Project Gutenberg resulted in the following:

(a) No case of failure was ever encountered. On the contrary, the above mentioned processing limit, which is in terms of rounds of certain preprocessing of source materials before they are xor-ed together, was by far not being approached in the experiment. For details, see Epilogue.

(b) The worst case of entropy according to ENT in the experiment was higher than 7.995 bits per byte and the average CPU-time was less than 15 sec on author's PC.

The software (new version 1.1) is available at http://mok-kong-shen.de


texts: Showing the pairwise XORed random variables are independent

texts:
If $X_i$'s are $3$ independent random variables defined over $\{0,1\}$ with biases $\epsilon_i$'s for $1\le i \le 3 \;$  and $\epsilon_1 = \epsilon_3 = 0.$ Then $X_1 \oplus X_2$ and $X_2 \oplus X_3$ are independent.

What I have done is, since $\epsilon_1 = \epsilon_3 =,$ hence $\Pr[X_1 = 0] = \frac{1}{2} = \Pr[X_3 =0].\\\\$ Also since $X_i$'s are independent, hence $X_1\oplus X_2, \;X_2 \oplus X_3$ and $X_3 \oplus X_1$ are uniform over $\{0,1\}.$
Now, $\Pr[X_1\oplus X_2 = b \mid X_2 \oplus X_3 = b] = \dfrac{\Pr[X_1\oplus X_2 = b, X_2 \oplus X_3 = b]}{\Pr[X_2 \oplus X_3 = b]}, b\in \{0,1\}.$
$X_1\oplus X_2 = b, X_2 \oplus X_3 = b \implies X_1 \oplus X_3 = 0$ and $\Pr[X_1 \oplus X_3 = 0] = \frac{1}{2},$
We know $\Pr[X_2 \oplus X_3 = b] =\frac{1}{2}.$ Hence $\Pr[X_1\oplus X_2 = b \mid X_2 \oplus X_3 = b] = 1.$
But $\Pr[X_1 \oplus X_2 = b] = \frac{1}{2}.$ Since $\Pr[X_1 \oplus X_2 = b] \neq \Pr[X_1\oplus X_2 = b \mid X_2 \oplus X_3 = b]$ so they are not independent.
What am I missing ? This is a question from Douglas R. Stinson's book "Cryptography-Theory and Practise" with question number $4.12$, page $134.$
Can anyone help me through this. Thank you.


texts:
What is the difference between CSPRNG and PRNG?

Is there performance differential between them? For example: We use PRNG for key generation which is very expensive and CSPRNG for IV/nonce in block ciphers which is fast?

What is the difference between the two types of RNGs?


texts: Can I combine two PRNGs to make use of more seed data?

texts: I have 320 bits of seed data (actually 512 bits of data with 320 bits of entropy, derived from a Diffie-Hellman shared secret and nonces). The PRNG I am using at the moment is the android version of SHA1PRNG. As far as I can tell, it has 160 bits of internal state, and so any entropy over 160 bits would be wasted. Could I create two instances, seeding each with half the data, and combine them somehow? The obvious possibilities would be to alternate which PRNG I pull each byte from, or to XOR the two streams together, but I don't know how that would affect the total entropy.


texts: Fully homomorphic encryption (over addition and multiplication) library in python

texts:
I was wondering if there is a commonly used library in Python (or another common language such as Java, C++, etc.) for fully homomorphic encryption over multiplication and addition that also supports floating point numbers. This means that if our encryption function is $f$ and our decryption function is $g$ and we have to plaintext messages $m_1,m_2$, then both the following hold:

$g(f(m_1)+f(m_2))=m_1+m_2$
$g(f(m_1)\cdot f(m_2))=m_1\cdot m_2$

Python-paillier implementing a Paillier cryptosystem seems to be pretty well documented and it actually does support floats (does so by fixing a precision and scaling all floats up to be integers), but unfortunately it is not fully homomorphic over multiplication (it does not support the multiplication of cipher texts, but rather has a weaker multiplicative property).

I've done a quick search and it seems that there's a lot of such cryptosystems (I don't care too much about runtime as of now), but I've been unable to find a library with concrete implementations.

Thanks in advance!


texts: ECC public key encryption and authentication - ECIES with ECDSA vs ECDH with AES

texts:
I'm currently working on a project where I want to establish a secure and authenticated communication channel between to entities, using Elliptic Curve Cryptography. Now I'm not really sure how to proceed after the key exchange. The current exchange looks like this:

$Alice$ sends her public key $K_A$ to $Bob$
$Bob$ sends back his public key and a signature, containing both public keys and her identity: $K_B, Sig_b(K_B, K_A, A)$
$Alice$ replies similarly with her signature: $Sig_a(K_A, K_B, B)$

As I see it, this authenticates Bob to Alice in a way that he now encrypts a message with Alice's public key and can sure that Alice is the correct recipient. So here are my assumptions at this point:

This does not guarantee to Alice that Bob is indeed the sender.
Therefore Bob would need to either sign every message to Alice, or use a shared secret.

Am I correct about that?

If so, then would there be any benefit in signing every message over generating a shared secret from the keys? I assume that a combination of ECIES and ECDSA is far more expensive than simply running AES. Since I'm working with very resource constrained devices, I'd like to keep the overhead as small as possible. Although I probably should use random padding and a KDF to increase the security in the AES scenario.


texts:
Assume the following simplified protocol:

seed = curve25519SharedKey(theirPublicKey, myPrivateKey)
sharedKey = scrypt(seed, salt, sufficientlyHardWorkFactors...)
cipherText = aes256(sharedKey, clearText)

Does using a slow-hash on the output of an asymmetric key-exchange offer any more protection in a quantum-computing era?  I know that quantum computing is supposed to make breaking diffie-hellman easy... what I don't know is exactly how easy.  Is the algorithm (greatly) diminished, or completely broken?


texts: Variant of Pollard rho using small factors of p - 1

texts:
Given an integer $N$ to factor which is divisible by some prime $p$, suppose you know (or guess) that $p - 1$ has a few small factors, e.g. $3, 2^2, 5$.  Define $B$ as a product of small prime powers so that $q \vert p
- 1$ and $q \vert B$ where $q$ is the largest such integer. With these assumptions it's possible to attempt to speed up Pollard's rho algorithm for factorization somewhat by using the function:

$$f(x) = x^{B} + 1 \bmod{n}$$

because $x^B$ will map elements of $(\mathbb{Z}/p\mathbb{Z})^\times$ into the subgroup $G_q$ generated by the $q$th root of unity modulo $p$, which has cardinality at most (and dividing) $\frac{p - 1}{q}$; this function will result in shorter cycles, faster. We expect the number of iterations to be proportional to $\sqrt{\frac{p - 1}{q}}$, though of course we do $\log_2(B)$ work each iteration rather than just a single squaring. If $B / q$ is not too large, this can be a win overall since the log function grows slower than the square root function; its speedup relative to rho can be estimated as

$$\frac{\sqrt{\frac{q}{2}}}{\log_2(B)}$$

This variant is a bit of a continuum between rho and the p - 1 algorithm though it is fairly pointless in practice; you usually don't know the small factors of p - 1, so you need a large $B$ relative to the product of primes that actually divide p - 1, increasing iteration overhead without speeding up the algorithm and it ends up less efficient than either algorithm on average, at least over the field of integers modulo $p$. I suppose that is why it is not mentioned anywhere in the literature.

The difficulty seems to be that while it's easy to get a pseudorandom function over the multiplicative group of integers by just combining multiplication and addition (the two field operations available), there's no fast way to do the same over $G_q$; you can stay within the subgroup using the group operation (multiplication) but this is insufficient to obtain a random function, since it's a permutation. And there is no convenient addition operation to introduce some nonlinearity either; the values of $G_q$ are distributed more or less randomly in $[1, p - 1]$ so naively adding a constant mod $p$ is sure to take you out of the subgroup, and then you need to spend $\log(B)$ work to recover a subgroup element. If there was a way to work completely within this subgroup efficiently, this variant might actually be useful.

My question is, is it possible to construct a proof that there exists no function $f: G_q \mapsto G_q$ which approximates a random function that could be evaluated in time independent of $q$ in the context of Pollard's rho algorithm?


texts: Attack being kind of completely puzzled?

texts:
I am reading this paper "The security of Hidden Field Equations (HFE)"

and at the end of the page 4 the author wrote:

  Thus, after all, this belief about every attack being kind of
  ”completely puzzled by the irreducible randomness of answers to all possible
  questions”, maybe it is not necessary at all to achieve security ?

I know what is irreducible randomness but sincerily I do not understand that sentence.

Could you explain me please what that sentence means?


texts: Error Detection/Correction technique for Encypted Data

texts:
I will be very pleased if anyone can clarify me that, can we use the same error detection/correction techniques like (Convolutional code) for the error detection/correction of encrypted data.
Or do we need separate techniques for plain data & encrypted data?

Thanks,


texts: Why does square root $\pmod n$ find $p$ and $q$ (as $n = p \cdot q$)?

texts:
Let $n = p*q$, with $p \neq q$ and $x^2=1 \pmod n$, $x+1 \neq 0 \pmod n, x-1 \neq 0 \pmod n$ (So x is a non-trivial square root mod n.)

I don't see how $\gcd(x+1,n) \in \{p,q\}$ follows.

I understand that $x^2=(x+1)(x-1)$, so $n=p*q$ is a factor of $(x+1)(x-1)$, but neither of $(x+1)$ nor of $(x-1)$ (as a x is a non-trivial solution). Every proof I've seen so far stops at this point, leaving me confused. In my opinion, it holds that $gcd(x+1,n) \in \{1,p,q\}$ (so the trivial solution 1 is indeed possible). How can we be sure that $x+1$ and n have common factors other than 1?  I'm sure I am missing something very obvious, but I just can't make it out.


texts: Split 32-bit LFSR into two 16-bit LFSR which xor to same sequence

texts:
Today I was thinking about exactly this.

Is it possible, for a 32-bit LFSR e.g.

x^32 + x^30 + x^28 + x^26 + x^22 + x^21 + x^20 + x^16 + x^14 + x^12 + x^10 + x^8 + x^7 + x^6 + x^2 + x^1 + 1

to generate two 16-bit LFSR which xor to each other generate the 32-bit sequence?

edit:
my wording wasn't exactly

there is a LFSR sequence with a known plaintext of 64 bit e.g.

1010111000000011
1111001010111001
0001010011010111
1001001111101101

it is known that this LFSR is built upon two 16bit LFSR which xor together give the same sequence as the LFSR above.

is it possible to generate the two unknown 16bit LFSR?

technically you have many lineary connections,

for example you know either the first bit in the first LFSR or the first bit in the second LFSR is 1


texts: Let $G$ be the generator of an elliptic curve $E$ of order $n$. Let $M$ denote a small (say, size $2^8$) message space. Elements of $M$ are mapped to points in $E$; the mapping is considered public. Let $s$ be a randomly choosen (secret) number from $[1,n-1]$. For some $m\in M$, is it computationally tractable to recover $m$ from an encoding of the form $sG+m$?


texts:
I am trying to understand how different assumptions might relate to each other and if they are absolute different or if they can be reduced to each other.

Can the random oracle be substituted with a PRP with a CRS?
Can a PRP construction with a CRS be substituted with a trusted random beacon?
is the random oracle a theoretical construction for a public random beacon?


texts: What is the security strength of an n-bit HMAC?

texts: HMACs depend on preimage resistance, or so I have read. The security strength of hash function with an $n$-bit output against collision attacks is $2^{\frac{n}{2}}$. Against preimage attacks, it is $2^{n}$. What is the security strength of an $n$-bit HMAC?


texts:
As the picture shows, need help with letter a).
Using F as pseudorandom function and G as pseudorandom generator with expansion factor of l(n) = n+1,
State wheter the scheme has indistinguishable encryptions in the presence of an eavesdropper and wheter it is CPA-secure, with shared key random k in {0,1}^n
a) To encrypt M in {0,1}^(n2+2), parse m as m1||m2 with |m1| = |m2| and send <G(k) xor m1, G(k+1) xor m2>


texts: Gaussian elimination to equations with errors

texts:
I am reading
this document and wondering the following part on page 13:
"Consider applying Gaussian elimination to the noisy samples
to find the first bit"

If we take, for example, $n = 3$, $s = (1,0,1)$, $x_1 = (1,1,0)$, $x_2=(1,1,1)$ and $ x_3=(0,1,0)$, what will $q$ and $S⊂[q]$ be?
Also, how to confirm the probability will be $1/2+2^{-Θ(3)}$?

I would be grateful for your help in advance.


texts: What is the "artificial abort" technique?

texts:
In the security proof of Brent Waters's paper Efficient Identity-Based Encryption Without
Random Oracles, he uses a novel “artificial abort” step on page 6.

  At this point the simulator is still unable to use the output from the adversary. An adversary’s probability of success could be correlated with the probability that the simulator needs to abort. This stems from the fact that two different sets of $q$ private key queries may cause the simulator to abort with different probabilities.

What is the purpose of this step?  Also, I am confused by the first sentence above.  What goes wrong if I just use the output from the adversary without this artificial abort step?


texts: Find IV and the key ? AES with CFB or OFB

texts:
I have a question about the AES-128 and AES-256 encryption method. I need to encrypt 64-bit size data in and out. I want to encrypt them with AES.
So I turned to AES-OFB or AES-CFB because these methods do not require padding. I have at my disposal a number of 256 bits which are shared by the source and the receiver (this number is created internally by both, this number is totally unknown to the rest of the world). I would like to use half of the number for the IV and the other half for the key. The IV and the key would be fixed.
In my specifications, it doesn't matter if someone can decipher the messages. However, someone should not be able to send encrypted messages that would be recognized by the recipient.
So my question is this:

Can someone find the IV and the key from the encrypted messages?
If so, can they then generate the encrypted messages to take control of the system?


texts: EAX vs CTR vs XTS + cascade ciphers in disk encryption hell

texts:
Often when I stumble across something interesting, I lose myself in the most overkill ways of implementing it. Today it was full disk encryption: I'm about to move to QubesOS, and I want to secure my data as much as possible, to a point where unauthorized viewing or even touching of the data becomes overly hard/nearly impossible. I don't care if it takes me minutes to decrypt my system on boot as long as it benefits my security.
As outlined in this answer I read (yes, I base my research mostly on StackExchange and wikipedia), there are three fundamental components of disk encryption I will have to decide on. These are the choices I've narrowed it down to:
Block cipher primitive: Serpent-256 (considered unbreached by Wikipedia), Twofish-256 (considered unbreached by Wikipedia, but is potentially more vulnerable to side-channel attacks) and AES-256 (considered theoretically breached by Wikipedia, but more mature). Seeing advantages in all three of these ciphers, I'm considering using them in a Cascading fashion like VeraCrypt offers. This would allow my system to stay secure even if one of these ciphers has been broken, right?
Mode of Operation: XTS seems pretty compelling (fixing issues from CBC->LRW and XEX), but is vulnerable to tampering (I'm using btrfs, so I'll at least be able to detect data manipulation) and traffic analysis. CTR also looks interesting, but yet again it is missing community support. To prevent tampering, I would have to use a diffuser. However, yet again, apart from Microsofts proprietary BitLocker diffuser (Elephant) there aren't any resources on this. Then there's EAX, assuring confidentiality and authenticity of the data. If so, EAX is arguably better than XTS, isn't it? Why is it so unpopular? Are there maturity issues?
Initialization vector: Anti-watermarking ESSIV for CBC-based modes, plain64 for XTS
As to be seen above, I'm especially insecure concerning the most secure Mode of Operation. Additionally, I'm not sure if there even is a disk encryption tool that provides f.e. cascade-serpent-twofish-aes-eax-plain64 (VeraCrypt supports the cascading part, but only allows for XTS). Also, most people use sha512 for hashing with a high iteration count. Is it possible to use a more sophisticated hashing algorithm like bcrypt instead?


texts: One Step Decryption For Multiple Chained Encryptions

texts: If we have a encrypting function f(x, y) (x for input, y for key) and let's say we composite this function n times inside itself with the same y (like f(f(f(x, y), y), y)) and set the output to be z. Does there exist another function g(v) so that g(z)=x? Can this be proven for any kind of encryption function f(x, y) stacked inside itself any times? Thanks.


texts: Weak Challenge Generation - Fiat-Shamir Heuristic

texts:
The Fiat-Shamir heuristic may be applied to transform a Sigma-Protocol on R(x,w) into a ZKPoK.

Let's call the prover's first message a and the verifier challenge e.

It is said that given a secure hash function H, one could have e = H(x,a) for Random-Oracle security.

But what happens if only a is hashed? What known attacks are made possible, or how is a proof of security made impossible?


texts: Difficult to guess the targeted receiver

texts:
The protocol is defined as  :
Bob want to send message to one of his friends say $k$ friends , he does not want his others friends (except one whom he want to send message ) to tell who is targeted recipient. Here public key of all  the participants are known. I read this is anonymous public key encryption in some paper ,but this paper said hat ElGamal public-key encryption  is able to provide this type of encryption but RSA cannot . I thought both can able to provide , my question is can we do some mathematical analysis (probabilistic one) to show that ElGamal public-key encryption  able to provide this type of encryption but not RSA. Can somebody share me some resources where detail analysis is done.


texts:
I was recently reading this paper on SIKE and I'm trying to understand the details of the implementation.

I've noticed the point tripling algorithm (algorithm 6) was already described in a different paper.
Nevertheless, the SIKE paper uses a slightly different algorithm for calculating [3]P. I've quickly checked - it seems to me that both algorithms give different result (am I wrong?).
Any idea why the algorithm from SIKE spec is preferred over the algorithm from the other paper. Is it somehow faster?


texts: Generate Elliptic Curve Private Key from User Passphrase?

texts:
I'd like to generate a private elliptic curve key from user input like pass phrase. Is the best way to do this with a key derivation function like PBKDF2? Is there a better way?

Edit (based upon @poncho's questions)

To be specific, this is for a Bitcoin ECC private key. It seems to me that if a user picks a passphrase like puppies, it makes sense to try to use PBKDF2, Bcrypt, or Scrypt to increase entropy.

Something like...

eccPrivateKey = pbkdf2(HMAC−SHA, "puppies", randomSalt, 10000, 256)

right? Should any inputs or outputs be hashed? So, is it acceptable (security perspective) for the output of the pbkdf2 to be the private key?

@poncho, hopefully my use case implicitly answers your questions regarding the brute forcing. i.e. don't care how long it takes to generate as long as it's under a few seconds. Care very much about dictionary and precomputational attacks.


texts: Multi-party computation with only 1 party?

texts:
MPC is $f(E_1(a), E_2(b)) = c$, where $E$ is encryption by different keys $k_1$ and $k_2$.

Homomorphic encryption is $f(E_1(a)) = E_1(c)$, where the input and output are encrypted.

I want $f(E_1(a)) = c$, because I'm going to use $c$ but can't see $a$.

One user will give me private inputs, I'll run a computation and get the results in plaintext. It seems to fall between MPC and FHE. Is there a technique that can do this?


texts: Advantages and disadvantages of hash-based signatures

texts: We know hash-based signatures (Winternitz signature, HORS(T) signature) that are quantum-safe and efficient. They can be stateful or stateless, one-time or multiple-time. But why are they not widely used in practice? Or maybe they are, please tell me some applications, advantages and disadvantages.


texts: How can I generate large primes for Pedersen commitment?

texts:
I want to make a commitment on Shamir's Secret Sharing, based on the work of Pedersen, "Non-Interactive and  Information-Theoretic Secure Verifiable Secret Sharing".

To implement the commitment protocol, I need two LARGE primes $q$ and $p$ such that $q \mid (p-1)$. How can one generate such primes?

Note: This is different from generating a safe prime since I'm required to generate a prime with specific characteristics.


texts: Is there an information theoretic equivalent of a trap door collision free function?

texts:
Warning: Possibly ill-posed question.

I'm using the following definition from a recent paper available here. I believe their terminology is slightly different but reproduce my understanding of it here.

  The concept of a 2 to 1 trapdoor collision free function
  satisfies the following properties. For every $y$ such that $f(x) = y$, there exists $f(x') = y$ and $x\neq x'$. If one has access to the
  trapdoor, it is easy to find $(x,x')$ for any $y$ and it is otherwise
  computationally hard.

In a recent talk posted online, the authors talk about information theoretic generalizations to this but give no further details. The obvious obstacle is that a computationally unbounded attacker can try all possible inputs to $f$ and eventually know the collisions. My guess is that somehow, $f$ is given in an obfuscated way so that the attacker cannot know of collisions. Is something like this possible at all and how might one achieve this?


texts: Is symmetric key encrypted with server's public key secure

texts:
I'm trying to implement lightweight yet secure protocol for communicating two trusted parties with each other.
Consider following scheme:

Alice wants to establish secure two-sided channel with Bob.
Alice knows Bob's public key from reliable source, so she generates random symmetric key, encrypts it with Bob's public key and sends result to Bob through untrusted channel.
Bob receives message, decrypts it with his private key and uses symmetric key found inside to write back to Alice, so they both share the same symmetric key. Alice and Bob then use any authentication scheme to verify identities of each other.
In case Mallory intercepts Alice's message, she won't be able to obtain Alice's symmetric key, but may forge her own, as Bob's public key is known. However Mallory will be unable to authenticate her, so she'll fail.

Are there any security drawbacks in this approach? Initially I've thought about Alice generating pair of asymmetric keys and using symmetric session keys for each message (GPG-style), but former seems more resource efficient to me.


texts: Efficient peer to peer untrusted signature aggregation

texts:
Suppose I had a peer to peer system, there are a few writers with the same signing key, and all readers have the verification key.
A naive system is that each document $d_1..d_n$ gets signed $s_i=sign(d_i)$. This would allow anybody to verify that every documents is written by authorized writers.
However it would be inefficient for a new user to join this group, as they need to verify every document, taking $O(n)$ time.
Now a writer can create a group signature $sign([d_1..d_n])$ in addition to the individual signatures. This means a new user can verify all documents in $O(1)$ time. This works because the writer has every document.
It will not work in a peer-to-peer system where no writer may observe the complete set of documents, for example due to being offline.
That suggests that readers need the power to merge the signature independent of the writers. Is there some system where a untrusted user can generate an aggregate signature like $sign([d_1..d_n])$ above by combining the $s_i$ values?


texts: How does PUF hardware help in software activation?

texts:
I have read that one of the PUF's application is software licensing, but do not know how. I have been reading different articles and forums (such as here), but still not clear for me.

One vague point for me is that PUF is a hardware and I do not think that vendors provide a separate hardware rather than maybe just a CD including the software.

I also want to know what is the functionality of PUF in this application? Key generator (like explained here)? or chip ID (like explained here - minute 16)? I found a protocol explained in here, but it is not very clear if PUF can act as product key, hardware ID, or activation number.

I was wondering if some one can explain it to me or give me some references.


texts: How can I resolve this basic MAC paradox I’m stumbling upon in my proof?

texts:
Suppose $S: K \times M \to T$ is a secure MAC. ($K$ = key space, $M$ = message space, $T = \{0,1\}^n$ = tag space.)

$S$ being secure means that no matter what messages $m_1,...,m_q$ we throw at $S$ to get back tags $t_1,...,t_q$:

$\{ (m_1,t_1),...,(m_q,t_q) \}$

we cannot subsequently find another message-tag pair $(m,t)$ that is not in the above set. In other words, we cannot find a forgery $(m,t)$.

Let's create a new MAC $S'$ based on $S$:

$S'(k,m) = (S(k,m), S(k,0^n))$

It is clear by example that $S'$ is not secure. The attack is simple: Throw at $S'$ some $m \neq 0^n$, and extract the value $s = S(k,0^n)$ out of the tag. Then, the message $0^n$ and tag $(s,s)$ is our forgery.

Here is the paradox. I believe I can prove that if $S'$ can be forged, than so can $S$. This would prove that if $S$ is secure (as we assumed), $S'$ is secure! There must be something wrong with my proof, so my question is, what is wrong with the following proof?

Assume $S'$ can be forged. In other words, we have thrown at $S'$ messages $m_1,...,m_q$ and gotten back the tags $t_1 = S'(k,m_1), ..., t_q = S'(k,m_q)$ and subsequently obtained a forgery message-tag pair $(m, t = S'(k,m))$ such that

$(m, S'(k,m)) \notin$ $\{ (m_1,S'(k,m_1)),...,(m_q,S'(k,m_q)) \} $

In other words,

$(m, (S(k,m),S(k,0^n))) \notin$ $\{ (m_1,(S(k,m_1),S(k,0^n))),...,(m_q,(S(k,m_q),S(k,0^n)))\}$ (*)

Then it seems obvious that the following is our forgery on $S$:

$(m, S(k,m)) \notin$ $\{ (m_1,S(k,m_1)),...,(m_q,S(k,m_q)) \} $

because $(m, S(k,m))$ being an element in that set would contradict (*).

That's the end of my proof. There must be something wrong with it. The question is, what?


texts:
Is there any notion of a periodic OWF?
I.e. an OWF $f$ that on every input $x$ in its domain it holds that $f(f(f\ldots f(x))\ldots )=x$ when $f$ applied many times, each time on the   previous output.

Also, if we take some One Way Permutation, it must be periodic of course. So is it guaranteed that its period is longer than any polynomial (in the security parameter)? (that is, if its period is of some polynomial length - is its security broken?)


texts: Time-locked Puzzles & Dead Man's Switch Intervention

texts:
I have been researching time-based puzzles. Specifically, computationally expensive algorithms for the purpose of a time-lock. This has lead me to sequential squaring, firstly, as well as some memory-hard approaches and of course trusted third parties. Creating a scheme that cannot be deciphered in N time, though not entirely trivial, is at least in theory doable. My question though is as this might relate to a dead man's switch.

Suppose we have Alice who wants to encrypt her message so that should N time pass without her intervention, Bob can decrypt it. What model of system could she come up with so that if she intervenes, perhaps complexity (Or something else that prevents decryption for more N) is added to the problem?

None of the approaches I've been reading about consider this possible scenario. In addition to accounting for time, how can we also account for periodic intervention, adding to N and/or difficulty?


texts: why to use a safe-prime in Diffie-Hellman key exchange?

texts:
In order for Diffie-Hellman to be extra secure we must use a safe prime which is (p – 1) / 2 will also be a prime.

so my question is what extra benefit of using such a prime, what's new does it bring to the table.

and does using a regular prime make the problem much easier to solve(make an attack practical).

g^ab mod safe-prime is more secure than g^ab mod prime ?


texts: Is it possible to encrypt a message stream with the same IV each time and for it to be secure?

texts: I know we should ideally never reuse the IV (Depending upon the mode of encryption used), but is it possible to have a protocol which uses the same IV for the message stream and is as safe as one which has a new IV every time?


texts:
Although I had a security course in school a long time ago, I am effectively new to cryptography.
I have an encrypted text, the encryption key of 44 characters, the encryption method, (Fernet, which uses AES), the mode (CBC), the length of the key (128-bit), the padding (PKCS7) and the authentication (SHA256).  The online decrypters I find do not provide the ability to enter all of these elements on one page.  Is it possible to decrypt it online?  Is there an order of steps that I have to use?


texts:
I am trying to understand the CTR DRBG specification in NIST SP 800-90A. It seems slightly different to a pure stream cipher in that the key and counter are reset after each generate call using the output pseudo-random bits. I understand that this is to provide backtracking resistance.

My question is, does this imply that the output bits produced by the DRBG are dependent on how the requests are 'chunked'? i.e.

$$
Generate(state, 8) || Generate(state, 12) \neq Generate(state, 12) || Generate(state, 8)
$$

...or have I not understood the specification correctly.


texts: Is inversion always cheap with Twisted Edwards curves?

texts:
I'm reading on Jubjub, which is planned for the next upgrade of Zcash. It is based on a Twisted Edwards curve with parameters $a = -1$ and $d = −(10240/10241)$. The reading says Jubjub does not need projective coordinates because inversion is cheap.

My question is, is the "cheap inversion" property that of Twisted Edwards curves in general, or the parameter selection of Jubjub in particular?


texts: Key rotation (or other measures) for PASETO v2 "local"

texts:
I was looking at using PASETO's v2 "local" encryption (XChaCha20-Poly1305) to implement short-lived tokens to share claims between microservices via an untrusted client. PASETO's documentation is strong on its implementation detail, but I'm left with questions at a higher level.

Specifically, I want to avoid a scenario where an attacker could breach a key and use it to forge claims. I'm under the impression that the likelihood of an attacker brute forcing a key increases with time and quantity of encrypted data samples, so key rotation seems like a great way to limit both the time and available data related to any single key, as well as to limit the duration which any breached key would be useful for.

I see from this answer that the primary purpose of key rotation for symmetric ciphers is to limit the damage that would result if a key was breached (e.g. only the data encrypted by that specific key would be exposed). In our use case, the claims would not contain any sensitive data, so this is not a concern.

Is key rotation a valid approach to avoid an attacker being able to forge claims? Is it overkill? Is there something else I should consider?


texts: Is Discrete Logarithmic assumption enough to design a secure searchable encryption scheme?

texts:
I have a basic question in my mind which is "Can we develop a scheme based on Discrete Logarithmic (DL) assumption only? "

Most of the "Searchable Encryption" schemes use assumptions like Decisional Bilinear Diffie–Hellman (DBDH) in their formal security proofs, (e.g. "Protecting Your Right: Verifiable Attribute-Based Keyword Search with Fine-Grained Owner-Enforced Search Authorization in the Cloud" by  Sun et al. SE). Can the formal security proof of my designed scheme be based on DL assumption only?


texts:
LRW and XEX modes of operation look similar. They are both tweakable narrow-block encryption with XORs before and after each single-block cipher.

I didn't really get the point where they differ or why one would be better than the other.

What I currently understand (could be wrong):

LRW: E_K1(P+K2*I)+K2*I
XEX: E_K1(P+K2*2^I)+K2*2^I

LRW could be a problem if plaintext contains 0||K2, allowing an attacker to discover K2.

Questions:

What kind of security could be compromised if K2 is discovered? It kinds of tells you some input-output pairs about the AES box, but not on the provided plaintext. Not sure what is the formal security notion about this.
Can I assume the tweak method (K2*I vs K2*2^I) is the only difference between LRW and XEX?


texts: Acceptable points of failure when applying encryption in an application

texts:
I am working an a Windows application that will encrypt and decrypt files using AES Encryption. The 32 byte key which is diversified and derived using a ATSHA204 unique serial number and some addition data via the SHA256 algorithm.

The key is stored on an ATAES132A serial EEPROM and is locked from reading and is only accessible using AES in CCM mode (MAC authentication). In my design, the ATAES132a communicates with a MicroChip (Atmel) microcontroller. The Micro Controller has a security bit which is set to prevent reading the firmware.

The Window's application is designed to only encrypt and decrypt using the unique key stored on the USB HID device. The key is transferred over the USB bus unencrypted to the Windows application. Additionally, the key is held in the PCs memory unencrypted.

My question; Are these acceptable points of failure in a system design? Meaning if someone has access to the USB bus, they may have access to the computers memory and the key is no longer secret. In my opinion, if someone has access to the PC with the USB HID connected, it is no different than being knocked on the head and someone stealing your car keys. It is almost impossible to prevent (at least I think its impossible to prevent).

I also thought that I could use AES-CCM to transfer the encrypted key over the USB bus, but both the USB HID device and Application must share another Key and additional data to encrypt and generate a MAC for the transmission. Even if I would do that, the unencrypted key is still being held in memory.

Here is a general overview of the scenario:


texts: Is there a block cipher mode that doesn't use the key input of the block cipher?

texts:
Is there a block cipher mode that does encryption and decryption without using the "key" input of the block cipher?

I ask this because rekeying a block cipher can be an expensive process, and I intend to encrypt many blocks with many different keys.

Is there some mode or construction that has the security of the underlying cipher, while not using it's key input?


texts: Designing hash function in space-efficient identity based encryption

texts:
Let $n$ be an RSA-prime and we know prime factorization of $n(=pq)$.

The hash function is the current context maps from a given user identity(id) to a positive integer less than $n$, whose jacobi symbol value is equal to 1.

Assume $id$ is any positive integer i.e., $id\in \mathbb{Z}^+$.

$H : id -> J(n)$

where $J(n)=\{x| x<n , (\frac{x}{n})=+1\}$

Method i am following :

i=0;
while(1) {
    MulMod(R,id+i,1,n);                      //R=(id+i)%n
    if((Jacobi(R,p)==1 && Jacobi(R,q)==1)||(Jacobi(R,p)== -1 && Jacobi(R,q)==-1)) break;
    else i++;
}

explanation :

1.$i=0$;

1.$temp=(id+i)\%n$.

2.if $temp \in J(n)$ output $temp$ else increment $i$ and continue .

Idea behind this is hash function is mapping to a value nearer to $id\%n$  whose Jacobi value is $+1$ in positive direction(increment of $id$) .

Is my method good enough ? or please provide any other good hash function  .


texts: Verification of encryption for ElGamal cryptosystem

texts:
Suppose Alice wants to convince Bob that ciphertext c = (a, b) = (gr, m*hr) is some properly encrypted plaintext (not just random numbers). Obviously she can use zk-proof of discrete logarithm knowledge for the first part of the ciphertext (a = gr). But what can she do with b-part?

One of my ideas: if m belongs to subgroup G (with a generator g) than we should prove that b belongs to G. But it's just a new problem.

Alice can also use exponential ElGamal (c = (gr, gm * hr)) if it makes things easier.


texts: Does there exist a highly irreversible hash function or a highly irreversible pseudo-random number generator?

texts: In my previous question, I asked about potential symmetric cryptosystems which are designed to be computed by a reversible computer. I am now wondering if there are any cryptographic hash functions which consist mainly of non-injective components. It seems like using too many irreversible components in a cryptographic hash function may destroy the security properties of a hash function since non-injective components may make it much easier to find a collision. Are there any good (fast, secure, not memory hard, preferrably used in practice; I also want to exclude the “provably secure” functions based upon difficult problems) cryptographic hash functions which are built using a large quantity of non-surjective components? Cellular automata based hash functions should fit some of these requirements, though I do not know if anyone is using or seriously considering using CA based hash functions in practice.


texts: Why does Encrypt-Then-Sign not yield a CCA-secure public-key encryption scheme?

texts:
In symmetric cryptography, combining an IND-CPA secure symmetric encryption scheme with a secure MAC with the encrypt-then-MAC method yields a IND-CCA secure symmetric encryption scheme.
I am trying to understand why this does not hold in the asymmetric case. Suppose you have an IND-CPA secure public-key encryption scheme and a EUF-CMA (or sEUF-CMA) secure signature scheme. When you combine them via encrypt-then-sign the resulting scheme is not CCA-secure.
I know that there are some related questions on this site (e.g. this one or this one). So I understand that the problem is that, when Alice sends a message to Bob, Mallory can intercept it, remove the signatue, sign it again with her own signature and forward it to Bob. Bob then successfully verifies and decrypts the ciphertext and gets the message, thinking that it came from Mallory (since it has a valid signature from Mallory).
But why does this imply that it is not IND-CCA secure? How can an adversary use this property to win the IND-CCA security experiment?
My own thoughts up to now: I am not sure how the IND-CCA experiment in this case works. I would assume that all keys are fixed by the challenger and the adversary only gets the public encryption key and the public verifikation key. Is this assumption correct? Because in this case I do not see how the above attack by Mallory helps the adversary - since all the keys are fixed.
Appendix: How encrypt-then-sign works (or at least how I understood it works):

Suppose everyone has an encryption key pair and a signing key pair
To encrypt a message, you first take the public encryption key of the recipient and encrypt your message with it. Then you use your own secret signing key and sign the ciphertext.
Then you send the final ciphertext (consisting of the signature and the actual ciphertext) to a recipient.
The recipient decrypts the ciphertext, using his secret decryption key and the senders public verification key. First the signature is verified and then the ciphertext is decrypted.


texts:
Possible Duplicate:
  CPA Secure Chosen plaintext scheme

The example for IND-CPA secure schemes given is generally:

for a random r,

$Enc_k(m) =(r|| E_k(r)$ $XOR$ $m)$ where $E$ is a $PRF$

But does the role of r and k really matter--i.e. isn't this equally secure?

$Enc_k(m) =(r|| E_r(k)$ $XOR$ $m)$ ?


texts: How can a user-input password be used to generate a natural-like dictionary corpus?

texts:
I'm curious about the implications of cryptography and the generation of natural text (i.e using Markov chains), and I am wondering if there has been any cryptographic protocols that involved generating a document key with legible English-language words from a user-supplied password (maybe hashed, or went through some one-way function). For example:

E(sha256(password)) = DocumentKey

If not, is there any proposed way of accomplishing something like this?


texts: Secure multiparty computation... where one entity owns all parties

texts:
Here's a corner case for you.

A user produces a small amount of confidential data and would like to delegate a third-party to perform some computation on it and return the results. Data and results are to be kept secret from the third-party, you can assume a "curious but honest" threat model.

My first naive intuition was that this would be an obvious application of FHE, but now I wonder... is there any way to tackle this use case using sMPC instead?

In other words: split the input data into a number of "workers" which are all controlled by the same third-party. Is there any sMPC scheme that is robust to such a scenario?

Thanks.


texts:
(i'm just trying to find what am I missing...)

Assuming John have a clear text message , he can create a regular hash ( like md5 , or sha256) and then encrypt the message.

John can now send Paul the message + its (clear text)hash and Paul can know if the message was altered. ( decrypt and then compare hashes).

Even if an attacker can change the encrpyted data ( without decrypt) -  - when paul will open the message - and recalc the hash - it wont generate the same hash as the one john sent him.

so why do we need hash by key ?


texts: How many signatures can a signing key (safely) produce

texts:
Given an AES key, there is a limit (of about $2^{64}$ blocks) of how much plaintext it is safe to encrypt with the key.

Is there a similar limit for how many signatures it is safe to produce with a signing key (such as RSA, DSA, or ECDSA)?

(I would also be interested if there is similar limit for asymmetric encryptions.)


texts: Relation between signature size and message-digest length in RSA PKCS#1v1.5 sign/verify

texts:
When using RSA-PKCS#1v1.5 to sign and verify a message-digest, is there a compulsory relation between the sizes of message-digest and the key/signature ?
For example, If I use key/signature length of 3072 bits, do I have to use message-digest of 384 bits (like SHA-384), or 256 bits (SHA-256) is sufficient ?


texts: Testing whether a secret value is zero without security bits (in SPDZ)

texts:
To test whether a secret value $[x]$ is zero, where $x \in [0,2^{k−1}]$, SPDZ uses the a based on the method of Catrina and de Hoogh [1].

This method requires to working on a field with modulus $p>2^{k+s}$, where $s$ is a is a statistical security parameter.

Does another method exist that perform this comparison but eliminate the need for security bits (performance is not my #1 concern)?

Thanks.

[1]-https://www1.cs.fau.de/filepool/publications/octavian_securescm/smcint-scn10.pdf


texts: Three party coin flipping protocol with only 2 active participants

texts:
Is there a coin flipping protocol where:

Alice, Bob and Carol don't trust each other, and
The coin is flipped only by Alice and Bob, and
The result must be trusted by all three participants.


texts: Is there necessarily an infinite number of inputs to any given output in a crypto hash function?

texts:
This might be a very easy question. Let's consider cryptographic hash functions with the usual properties, weak and strong collision resistance and preimage resistance.

For any given output, obviously there are multiple inputs. But is that necessarily an infinite number of preimages, for any given hash value?

How would I go about giving a formal proof that there exists no crypto hash function $h$ such that there is a given value $v = h(m)$ for which the possible set of inputs $m^*$ is finite? Would this necessarily break collision resistance?


texts: Is there a formal language to define a cryptographic protocol?

texts:
I wanted to work on a personal project where I would attempt to identify the flaws in a cryptographic protocol. Now for that to work properly, the program should understand the syntax of protocol definition (if any). So I wanted to know if there is any formal language to define a cryptographic protocol.
I found a paper but I don't know if everyone actually follows this or not.


texts: Constructing a custom protocol using well-vetted algorithms?

texts:
For the reasons I cannot go into details, I need to design my own protocol and overall security system which will be used to establish secure data exchange between various devices (most notably desktops of all three major OSes, Android and iOS devices and Raspberry Pi, with the possibility to extend it to other embedded systems). Since I wouldn't dare to do my own crypto algorithms implementation, this implies that I have to rely on tried and tested libraries available for those platforms (i.e. OpenSSL, BouncyCastle, CommonCrypto, …) so I settled with what they all support - RSA for signing/authentication, DHE/ECDHE for session establishment, AES for encryption, PBKDF2 for key derivation and SHA2 for general hashing needs. The key sizes and complexity will depend on the hardware ability of targeted platforms.

Now, I've done a fair bit of implementations of existing protocols and I like to think that I know my way around cryptography and perils that await if not applied properly, however I wouldn't dare to consider myself a cryptography expert and thus I decided to query the hive mind. Of course, once everything completed it will be properly audited and tested, but for now I need to know if I'm on the right track, that I haven't done some glaring omissions and if it is possible to improve it even further.

The system I'm building should both cover the storage on devices and the communication between them and to preserve forward and backward secrecy.

For the storage part I plan to utilize AES in CBC mode, storing the randomly generated IVs with each individual encrypted file. The 'master' key itself will be randomly generated and also AES-encrypted using a key derived from the user's password using PBKDF2, stored along with the salt and iterations used in it. My main concern is the IV part as if generated randomly it might repeat thus compromising the encrypted files if they happen to be similar enough or even the same. It's quite a low chance buy I don't like leaving anything to chance so the question is - given that the IV is public knowledge anyway, is it safe to use incremental progression/timestamp as IV in this case?

The communication part will be a bit trickier as the devices will never communicate directly - instead the data exchange between them will be relied through a third party database to which they periodically connect, which is one of the prime reasons I'm designing my own protocol. If we except this oddity, the data exchange itself should function quite the same as if they were communicating directly, namely the devices will establish a session each time they 'contact' each other and then use the session key for encryption.

To establish a session I plan to use a variation of STS protocol adapted to this environment. The only oddity here is that in some instances only one of the parties involved in communication will posses the RSA key of the other so it won't be fully authenticated - my understanding is that even in this case no successful MITM attack can be performed as at least one of the parties will reject communication if the signature doesn't match. Is that a safe assumption?

Once DH/ECDH keys are exchanged an actual session AES key will be derived from them using SHA2 and the rest of the data exchange will be encrypted using that key, again in CBC mode - until the session expires, when the process repeats. I'm still not clear on how to approach the message integrity and authenticity verification - at first I thought that signing the message with the device's RSA key will be enough, but since it may happen that only one of the parties has the other party's certificate I might add a HMAC alongside with the exchanged messages as well. What would be a recommended, cryptographically secure way to handle that?


texts: Can AES in CCM or GCM counter mode interoperate with AES in "plain" counter mode (CTR)?

texts:
I am exploring the use of Windows CNG to replace some OpenSSL-based code that takes advantage of AES in counter mode. From the outside, everything should look the same after the switch.

The section BCRYPT_CHAINING_MODE in this piece of CNG documentation gives me the impression that the only counter modes supported are BCRYPT_CHAIN_MODE_CCM, which sets the algorithm's chaining mode to counter with CBC-MAC mode (CCM) and BCRYPT_CHAIN_MODE_GCM, which sets the algorithm's chaining mode to Galois/counter mode (GCM)

I have no experience with CCM or GCM and would like to understand whether it is possible to use them in such a way that it can interoperate with CTR, by "disabling" the authentication part or in any other way. I did not find any indication that that is possible indeed, but on the other hand, I would be surprised if CNG does not support AES-CTR.

Maybe my question should have been "does Windows CNG support AES-CTR" to get a more direct answer :-)

Update: On another Microsoft webpage, in the section Cryptographic Algorithms, the table called "Table 12 – Advanced Encryption Standard (AES)" mentions "CTR( int only; 128 , 192 , 256 )", which I suppose means that it is internal functionality only.

I think this question is related: What is wrong with AES-CTR-HMAC-SHA256 - or why is it not in TLS?


texts:
I'm trying to implement an e-voting algorithm, which is described at the paper "Internet Voting Protocol Based on Improved Implicit Security" by Abhishek Parakh & Subhash Kak.

At the Example 1 described in the paper where we have m1=85, at the step 2 it says

"2. Choose randomly and uniformly a number r1 = 101
and compute r2 = m1*(r1)^-1 = 85*(101)^-1=85*28=67mod257"

How is this possible? I mean how can 101^-1 be 28?


texts: Is it true that first time RSA algorithm  was rejected by a journal?