@EllaRose My computer has been working for 12 hours to generate the primes for 512 bit security level and I have no idea its progress so far :P

ctrl-c inserts percentage bar restarts

that's what I usually do when in a similar situation, I swear it runs faster after there's a status bar to watch...

lol the problem is if I knew where I was counting down to, I could just skip to there :P

My progress bar is basically just the wall time

it could say it's done any second

maybe I should see if the numbers exploded and it's trying to generate a stupidly way too huge prime that I'll never find :P

percentage to completion: urandom()

that's why I like the status indicator, there's been some things I wouldn't have wanted to wait for

I do feel like "doh" because didn't start it multi-threaded :/

I never use threads cause CPython

I've never actually had to deal with true parallelism before

I have to use threads because 6 core CPU

to take advantage of that I'd have to use multiple processes

it's so heavyweight it kills the fun

ugh lol communicating between those is too much work

have to serialize your py_objects and deserialize them on the other side =\

lol noty

You have to think so hard to get a benefit when there's so much overhead

yep

makes it not worth doing in many cases, which is arguably a good thing

(cause if it can be done without it, maybe it should be?)

Lol when I just need to run a tool once like I don't mind doing nasty things like getting each thread started and then letting them run independently until one finds the solution, writes it out to disk, flushes it, and crashes the whole process to notify the other threads :P

I'm gonna go ahead and call that really bad coding, but it's fast for me and the software lol

whatever gets the file written huh

(and relying on the low density of prime numbers up in that huge range to protect the other threads from striking at the same time)

I probably didn't enable multithreading because unconsciously I don't trust that code

whys that?

I'd always feel like "what if" until I knew for sure that it's actually the right exact number

I mean any number in that size (that works) would work, but there's a specific one I intend to use

I could end up with the wrong one and never know for years and just wonder but not be willing to spend apparently >12 CPU hours on the result

what do you mean there's a specific one?

if you know the number already, why search through 512 bits of space for it? :o

@EllaRose lol if only it 512 bit of space I was searching in, I'd have found the first prime by now for sure.... oh shit

131072 bits

so that's why >12 hours :P

I wonder if I reached the never-ever zone

I need to consult prime number theorem

lol

131072 bit prime? why Mick, why?

because the general number field sieve is really good -_-

no point in scaling up the rest of the system to 512-bit without scaling up the discrete log group that big

@EllaRose I just got your email

Oh I just sent it not that long ago

forgot I was still in chat here :o

I responded now :P

two obscenely long passwords later...

lol

ok, til next time!

goodnight

this thing is still running... prime number theorem says I should only need around ~90852 guesses

I would hope my probabilistic prime test doesn't take more than a second, I should be at least halfway done

Why in god's name are you going for 512-bit security? With finite-field groups, no less?

Never Re-Key Until Quantum 2016!

looks over to see quantum scaling faste... and it's gone.

jk, mainly just because I wrote a key generator that automatically derives the size of the group based on the GNFS heurestic complexity, and it kept putting out somewhat reasonable values even as I went past 256, and 320 only took about 30 minutes so I said screw it, lets see if 512 is possible lol

I'm sorry, ok? I'm sorry.

lol

if that's a discrete logarithm groups, aren't you looking for a safe prime?

which is a lot harder to find than a usual RSA key

i.e. ~(p / log p)^2 tries instead of the usual p / log p

err (log p)^2 and log p, respectively

I also would like it to have a Schnorr group lol, my running time estimate might be way off

It has to be at least a little ways off... its been running for about 29 hours now

I think libgmp implements AKS for its probable prime test

Maybe that takes more than 1 second a pop on 100kbit numbers :/

AKS is too elaborate to be in libgmp, afaik it's simple Miller-Rabin

good call

I had that reversed, AKS isn't even probabilistic

@SamuelNeves Miller-Rabin does the job and provides a very good certainity that a number actually is a prime with much less work :)

that is true

morning all!

@EllaRose morning :)

hows the search for huge numbers going?

let me check

still going.

WTF what numbers are you searching for what!?

~29.8333 CPU hours and counting

@SEJPM 131072-bit prime with embedded 1024-bit Schnorr group

@MickLH ... why? (fun?)

yeah mostly just for fun

I plugged in 512-bit into security level on my group generator program

(BTW, IIRC finding 2 32kib primes took my ol' i7-930 8h)

this is gonna take muuuuuuch longer

yeah I'm scared I crossed the "complexity exploision" line lol

but I plugged in 352-bit and it worked in like 45 minutes!

wtf, it took you 45 min to find a 352-bit prime!?

nooo lol 352-bit security level discrete log group

isn't that like 25kib prime size?

my tool rounds up to power of two so it was 32kb :P

(w/ 704 bit schnorr group)

but you do realize that anything with more than (let's say) 192-bit security will never be broken except by a quantum computer anyway?

Yeah lmao

I actually aimed at 192-bit as "high security"

I just... well it did 320 in like a half hour

and 352 was not much worse, I said fuckeet! 512!!

so the big one should take 4^2=16x the amount of time?

(o it's already past that)

I think I got lucky with those previous ones, and also got unlucky with this one :P

maybe this doesn't scale quadratically due to your insane subgroup requirements :P

lol I am afraid of that

I should just do a test to see how long libgmp's miller-rabin takes on 100kbit numbers, so I can at least have a reasonable estimate of how long each step takes

but even that is still ignoring the subgroup

I was stupid enough to not only not include a "# attempts" counter... but no way to pause and resume either :/

miller reabin requires basically one modular exponentiation

Miller-Rabin scales as O(n^3), or O(n^2 log n) with FFT-based multiplication. Add a logarithmic factor for the number of retries.

@SamuelNeves so it should take 4^3=64x as long? (from 32kib to 128kib)

somewhere between 16x and 64x, I guess

assuming constant factors are more or less irrelevant

so any minute now! :D

By that estimate I have to wait 18 more hours before I get impatient though

so we'd end up at 128x as slow of progress?

because we get 16x-64x from miller-rabin and 16x from the prime density?

(which would mean 192h)

oh, right

@MickLH gl hf waiting then :P

I plan to let it run for at least a week if possible lol

which would be 168h < 192h

(-> try two weeks :P )

(if things go optimal)

lol I told the only other person in the house that it needs to run for months and not to disturb it, just to be safe

dat power bill?

as long as it's not a cloud computing instance :P

@EllaRose I think it's close enough to normal daily usage anyways, I can just say it's amortized

I usually leave my machine on overnight anyways because I never know when I'm really going to bed or not

and dude 512-bit security is soooo hype!

@MickLH that doesn't sound healthy

@MickLH *against classical adversaries :P

it's over halfway through 2016 according to the time keeping device on my machine :o

so does that mean rekey as soon as it's done?

Probably

time for the epic 1024-bit security then? :P

hahaha I'm just hoping it buys me enough time to understand and implement some quantum resistant pki

@MickLH Wanna work with me on that? I was really hoping to implement a post quantum scheme when redesigning my security stuff

(otherwise, what's the point?)

I'd love to but I have no idea what I'm doing there lmao

@MickLH any ideas yet which algorithms?

@SEJPM No clue, barely even figuring out where to start looking

FYI: for an overview, you may want to have a view at Post-Quantum Cryptography by Bernstein

fuck, I ran out of free pages and if I buy it right now I'll never get my application done :P

@MickLH free pages?

Springer lets me read a few pages for free to entice me towards buying it lol

I looked up the book you mentioned there

@MickLH I didn't link it, but there's also a pdf copy uploaded on the interwebz if you search for it

I'm tempted, I thought about it, but I really should support the author and it would be just as devastating to my implementation progress ;)

blog.cryptographyengineering.com/2016/07/…

It's fucking frustrating, the entire DMCA is an outrage really

I started to work on implementing your key exchange with my data transfer service, but managed to mix up a value or something somewhere because the shared secret turns out wrong >.<

but after I get that sorted out we could use it for chat maybe, unless you got that netcat idea sorted out?

@EllaRose haha well you know netcat just pipes a socket to stdio

actually I had no idea, never used it

It's like an "instant chat client" with no features of any kind :P

I can do marginally better then that by piping stdio to my dts

it's basically the same as sockets except for registered users instead of ip addresses

so at least then we'd have some kind of authentication and names and stuff

hrmm

I did make a command line variant a long time ago that I forgot about

let me see if I can dig that out

@EllaRose I'll go over this and see if I can spot anything

You rock! I was gonna bang my head against it a little more later, I have a feeling it's a small thing like switching an argument somewhere or something

I have unit tests for your key exchange so I do know that works

@EllaRose I'm struggling to figure out what the 3 phases are

I'm shit at reading high level code lol

mainly, I don't understand what continue_exchange maps to

sorry, it's kind of a messy translation in that it's both sides of the exchange in one

and I knew when I named that that the name sucked >.<

I turned on the air conditioning lol, I should be back to full mental functionality in about 2 degrees

if you initiated a key exchange with me by sending your public key and a token to me, "continue_exchange" is the part where I generate my own ephemeral key and token, and generate a secret before sending you my token

(I think)

I could have gotten the logic wrong/was thinking of reworking it

ohhhh public key is... the user's public key :P

imagine that :P

It's not authenticated if you trust the received public key, you have to already have it, or have a signature from an authority that confirms that it's their "real" pubkey

I should name them better maybe? clearly delineate which key belongs to who

right, I hadn't gotten that far yet

@EllaRose I'll sign your CA if you sign mine <3

haha sure, I think.

@EllaRose oh important result if you use my scheme, at the core it's the "static-static" DH secret driving the authentication, so if that's compromised then so is the authentication

that makes sense

it still seems simpler then using separate DH and RSA primitives

lol I just don't like RSA for some reason

I mean I love RSA and I think it's beautiful, but it just for some reason feels...

me either, especially now that the looming quantum threat seems to be materializing

sorry, I didn't mean to interrupt :x

lol nothing to interrupt, it's irrational, I'm just always scared someone's gonna gcd(mick, oscar) = q me and be like "lol gg"

lolwat

gcd(mick, oscar) = q ?

I'm not math-y enough to get the joke I think

I mean the modulus of each, if oscar's public key and my public key both shared a prime factor, a cheap evaluation of gcd would show it immediately

oh I getcha

you mean trusting your own crypto?

or maybe not?

lol well I meant that factoring systems just scare me because even though the chances are basically as good as you can hope for (basically arbitrarily strongly in your favor) it just makes RSA automatically scare me more than DH because it seems like even though it's leaking zero information, it's leaking that zero

and I could never trust my own crypto lmao

if someone else proved to me it worked, I would consider "trusting" it lol

I consider posting it here and not having it immediately smashed by folks like SEJPM/CodesInChaos/Poncho/etc to be a relatively good sign

lol it figured it means I annoyed them away :P