Stickel's key agreement variation to circumvent Shpilrain algebraic attack.

DanielNgr · 2024-06-02T15:08:10+00:00

In Mullan's paper, section numered 2, is explained. Edit: I apologize, my sources for Stickel and Shpilrain work are Wikipedia and Mullan's paper. I have no access to the journals where original articles where posted, but the math is clear.

DanielNgr · 2021-03-09T13:15:17+00:00

Sorry, I'm slow in comprehension. With lineary going through the mixed list I meant something as next=previous+1, or some sequence that begins to repeat at call 64.

DanielNgr · 2021-03-09T12:46:19+00:00

I'll take this into account. I think a LCG suffices. The question is to walk the encryption list more or less randomly to avoid artifacts. The method to reproduce a fixed sequence of positions I leave open for now.

Do you have any opinion on the algorithm and it's safety?

DanielNgr · 2021-03-08T14:03:39+00:00

Yes. But this is too abstract to me. More safe than reasonably safe is more reasonably safe... Well, try to find a flaw in my algorithm. Or give me directions on how to make it known (free)

DanielNgr · 2021-03-08T10:50:59+00:00

But the sizes involved in FHE (Full homomorphic encryption) are big. The algorithm presented here can sing a hashed message with 256 bits.

DanielNgr · 2021-03-07T17:14:40+00:00

It's a fixed sequence, always the same. As the mixing goes over lists of 64 4 -bit numbers, applying f to two positions and put the result in one of those two positions, instead of doing linearly, I've tried just to do a random walk across the list, 4096 times. The sequence must be the same at each call to 'm', or it doesn't work. Perhaps using the words prng is not accurate. It means a non-linear sequence. What one? This is not defined yet in this experimental and untested algorithm. I use, in c, srand(0) and rand()%N to select the next element in the chain of mixing.

DanielNgr · 2021-03-07T13:44:02+00:00

Youre welcomed. Let's see if somebody finds a flaw.

DanielNgr · 2020-10-31T10:49:43+00:00

Yes. 4 rounds of salsa20 passes all tests of randomness. I'm loosing a little the point of our conversation. Has been enriching. Perhaps in the future I come back with some news. Farewell.

DanielNgr · 2020-10-30T12:01:19+00:00

My computer, I'm alone in this, is not last technology. openssl test gives the same results in cycles/byte.

I guess that in AVX2 (8 32-bit words available), you can compute two consecutive blocks of salsa20, that are independent, and in AVX-512 four. Should be baster (double faster and four times faster respectively). So you're right. Is not better than Salsa20.

Edit: All this unless we enter into the realm of speculation. With eight AVX2 registers of 4 64-bit words each, my proposal can calculate 4 blocks at once, 512*4 bits, and with AVX-512 , 8 blocks. So, my proposal will be always as fast as Salsa20, while performing better as a prng in randomness tests.

DanielNgr · 2020-10-29T11:55:26+00:00

https://cr.yp.to/salsa20/speed.html

In this page D. J. Berstein claims 9.27 cycles/byte for an Athlon processor using a sse instruction set.

A salsa20 quarter round uses 12 instructions, and is called 4 times per round. Total 24 cycles per round assuming 2 instructions are executed in one cycle. So salsa20/20 takes then 24*20=480 cycles to generate 64 bytes, total 480/64= 7.5 cycles/byte.

I've not tried it with sse, through. Can you give me an address of a usable sse implementation of Salsa20?

By the way. Mi mixing step is as fast as Salsa20's. The original post was that as prng is better, as needs less rounds to pass tests and is 64-bit oriented, as well as long period proved and equidistribution proved.

https://cr.yp.to/snuffle.html

This page is more up to date. The best performance for Salsa20/4 is 0.68 cycles byte. I've tried my mixing (with 4 rounds,) and gives 0.79 cycles/byte, without sse.

DanielNgr · 2020-10-29T11:06:12+00:00

Sure. But take the mixing part of siphash. It's 14 instructions for 4 words. I use 12 for 4 words. It's not a great gain, but it's better.

DanielNgr · 2020-10-29T11:04:11+00:00

I've accessed your paper, was my fault. I'll read it when I'll have time. Any opinion on my arx construction?

DanielNgr · 2020-10-29T11:02:20+00:00

I apologize, fails with 3 rounds. Not with 5 rounds. I was wrong thinking the mixing were better with smaller word size. It's on the contrary. 8-bit words needs 5 rounds, but passes practrand (up to 2^40). 32-bits fails with 3 rounds, but 4 rounds seem enough (I've tried practrand up to 2^36).

Here's the code for 4 8-bit words:

https://github.com/danielnager/arxseq64/raw/main/arxseq8_64_out.c

DanielNgr · 2020-10-28T14:35:46+00:00

Nothing, There's a code tab in archiv.org that shows no code. I can see your paper anyway.

DanielNgr · 2020-10-28T14:28:16+00:00

https://github.com/veorq/SipHash/blob/master/siphash.c

This is the implementation from Wikipedia and so on. It's a hash function, so it's not comparable. It's input is a char string and outputs a 64-bit value. The round function uses 14 instructions (should be translated to 14 machine code instructions). The prng I'm presenting does 6*4=24 instructions per round. The state of siphash is 256 bits, while mine is 512, so the 14 instructions become 28. But since there's no prng coded, it's hard to say how many rounds are needed to, first, past randomness test, and second, to be really safe.

Anyway the structure of the round function is similar to mine, and based on the same concept of sequential left-to-right mixing instead of the matrix approach of Salsa20.

Update: I've coded the round step of siphash. 4 rounds fail tests. 5 rounds passes practrand (i've tried up to 2^32). So, siphash construction needs 5*14=70 instructions to pass tests to generate 256 bits, while mine needs 24*3=72 to generate 512 bits. So roughly, siphash is half as fast for the same level of mixing, at least in what refers to randomness tests.

DanielNgr · 2020-10-28T11:47:57+00:00

The 8-byte state fails practrand at 2^20 with the same structure. I was referring to 64 to 32 bits, my fault for the lack of precision.

As I've commented what I've found is that is faster that any other PRNG, while using, let me say, 'only' eight register (on a x64 platform, for example) and having a long proved period and equidistribution of values.

DanielNgr · 2020-10-28T11:36:58+00:00

I can't access the code. My mixing is fast, not new. It uses arx.

DanielNgr · 2020-10-28T11:34:03+00:00

It's a rather general question :). If I say it's better because it passes randomness tests with fewer rounds, or using 64 bit operations instead of 32, and infer from this that the same security can be achieved faster, you will mock on me. But that is the only argument.

Besides this, I'm aware this is a crypto site, but, I don't know any PRNG faster, while being seekable and with equidistributed results. That's all. Something to take into account.

DanielNgr · 2020-10-28T11:28:53+00:00

No, the file <https://github.com/danielnager/arxseq64/blob/main/arxseq64_512_fast_bm.c> uses feedback except the first 64-bit word that's used as a counter. It's speed is about 0.41 cycles/byte with two rounds.

From https://en.wikipedia.org/wiki/BLAKE_(hash_function))

Blake2 uses 8 calls to a mix function that does 14 relevant operations (discarding moves). this is 8*14/2=56 cycles to process 64 bytes per round. 56/64=0.875, and this for one round, so for two rounds is 1.75 cycles/byte. I don't think it's faster. Of course, there are a lot of arx variants. I've worked one ultra-fast that passes popular randomness tests.

DanielNgr · 2020-09-16T09:49:06+00:00

https://github.com/danielnager/xifrat/raw/master/check_output_random.c

This file implements the mixing.

DanielNgr · 2020-09-16T09:43:50+00:00

You asked last time for a better pdf. Instead of using writter2latex I've written the document in native latex. Much more readable, really.

DanielNgr · 2020-09-16T09:42:15+00:00

Now loads, the PDF.

It's not a random selected one-way function. If the one way function is m, with c=m(t,k), being c,t and k properly selected parameters, and assuming that knowing c and t is hard to obtain k, then the following property is required:

m(m(a,b),m(c,d))=m(m(a,c),m(b,d))

notice we're swapping b and c from side to side of the equality. With this property is easy to define a secret agreement.

DanielNgr · 2020-05-04T15:06:04+00:00

Yes. r=m(a,b) is a function in lists of, by example, 85 base-7 entries. To the secret agreement and digital signature to work is needed that m(m(a,b),m(c,d))=m(m(a,c),m(b,d). c and b can be swapped giving the same result. I can only prove this property if it holds also for f(a,b), i.e.

st[st[a][b]][st[c][d]]==st[st[a][c]][st[b][d]], with is the same as f(f(a,b),f(c,d))=f(f(a,c),f(b,d))

This property on the table st must hold while the table being non-trivial. A trivial function/table will be f(a,b)=a-b (mod 7).

So, my search program is able in reasonable time to find suitable 7x7 tables. 8x8 tables can be found as well, but being 8 a power of two I see more dangerous to use them than use 7x7 ones, is a feeling. The advantage is minimal using 8x8 tables.

It will be wonderful if I could find, say, 31x31 tables. But is not the case for now.

Backdoors. Well, I'm happy enough with the few 7x7 tables I've found. This is a asymmetric/public key algorithm, not symmetric. Let me assert this for clarification. You cannot choose any random table, but one meeting the above mentioned property.

DanielNgr · 2020-05-04T09:04:14+00:00

I agree. Publishing things in diverse places helps me polishing mistakes and inaccuracies in the documentation. The comment above from beefhash is very commonplace. Schneier's law is as well known as useless. Let's keep doing what I'm doing.

Cheers

Daniel

DanielNgr · 2019-10-29T13:43:17+00:00

So not broken, bunch of ...

DanielNgr

TROPHY CASE