A public key that any engineer is exposed to on github. https://github.com/ユーザー名.keys Will be published worldwide.
Then, please take a look at me @ umihico's public key.
ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIFUMIHICoCb3Sy2n1qPXOxc2mFBqW9Hg0dRigxl2F3nW
That's right. You have successfully inserted your own username. I made a one-liner that keeps generating keys until I find the specified string in the regular expression, and I ran it for about a week. Click here for one liner.
@Ress advised me to use cd $ (mktemp -d)
to reduce disk IO time. Thank you!
cd $(mktemp -d); while true; do seq 1000 | xargs -P 1000 -I NUM sh -c 'ssh-keygen -t ed25519 -f NUM.pem -N "" -C "" > /dev/null && if grep -vi umihico NUM.pem.pub > /dev/null; then rm NUM.pem NUM.pem.pub;fi' ; if find . -mindepth 1 | read; then for f in *.pem.pub; do echo $f >> files.txt; done; test -f files.txt && head -n1 files.txt | xargs -I F echo found; break; fi ; date ; done
The processing from key generation to regular expression judgment and deletion is performed in parallel with xargs
using multiple processes. As soon as it is found, it is missing from while
. By using ed25519 from RSA, you can create a large number in a short time. Moreover, the security of the key is improved and the character length is short.
@AKKYM gave us a suggestion from xargs
to use filter
to speed up multi-process. Performance is improved by 1.2 times. Thank you very much. Macbook split
has different arguments than Linux, so you need to use gsplit
which can be installed with brew install coreutils
.
cd $(mktemp -d); while true; do seq 1000 | gsplit -u -n r/32 --filter 'while read i; do ssh-keygen -t ed25519 -f $i.pem -N "" -C "" > /dev/null && if grep -vi umihico $i.pem.pub > /dev/null; then rm $i.pem $i.pem.pub;fi; done' ; if find . -mindepth 1 | read; then for f in *.pem.pub; do echo $f >> files.txt; done; test -f files.txt && head -n1 files.txt | xargs -I F echo found; break; fi ; date ; done
r / 32
is the number of divisions = the number of processes, but if you increase or decrease it and deviate from the best value, the performance will decrease and it will be about the same as xargs
. On the other hand, for xargs
, even if the number of processes is changed from 32 to 1000, there is not much difference.
If you want the server to process in the background using tmux etc., you want to be notified, so replace ʻecho found` with, for example, Slack's Webhook Incoming API. It will be as follows. (Xargs version)
cd $(mktemp -d); while true; do seq 1000 | xargs -P 1000 -I NUM sh -c 'ssh-keygen -t ed25519 -f NUM.pem -N "" -C "" > /dev/null && if grep -vi umihico NUM.pem.pub > /dev/null; then rm NUM.pem NUM.pem.pub;fi' ; if find . -mindepth 1 | read; then for f in *.pem.pub; do echo $f >> files.txt; done; test -f files.txt && head -n1 files.txt | xargs -I F curl -s -X POST -d '{"text":"F"}' https://hooks.slack.com/services/XXXXXXXXX/YYYYYYYYYYY/zzzZZZzZzzZzzZZzz; break; fi ; date ; done
By the way, if you can use an idle server, please note that EC2 will be charged + α depending on the CPU burst setting. I was charged if I violently attacked EC2 of CPU burst Unlimited
Now let's consider the probability and waiting time for the desired string to occur.
The chance that a random string of 7 characters base64 will accidentally become ʻumihico(case-insensitive) is
2 ^ 7/64 ^ 7. And since ed25519 has a changing string length of 43 characters, it can be interpreted that this trial can be performed 37 times at the same time with 7 characters. In other words, the probability of hitting once is
0.0000001076841726899147%`.
>>> 2**7/64**7*37
1.076841726899147e-09
The probability of being found by trying 1 billion times is the probability of not being found 1 billion times in a row by subtracting from 1. It is 65.9%.
>>> 1-(1-2**7/64**7*37)**(10**9)
0.6593302436744479
The following formula gives that you only have to try Z times to make the X character appear with a probability of Y. (Terminal of python3.6 or later)
>>> import math
>>> X=8
>>> Y=0.6
>>> Z=int(math.log(1-Y,1-2**X/64**X*(43-X+1)))
>>> f"{X}For letters{ '{:,}'.format(Z)}At times{Y*100}%"
'For 8 characters 27,985,342,058 times 60.0%'
Oneliner executes date
every time 1000 cases are generated, so if you look at it for a while, you can guess how many cases you can try in a day. Even if you can do 1000 cases per second, it will take 324 days for 27 billion times to hit 60% with 8 characters, so it seems that people with names of 8 characters or more are not realistic. sorry.
And note that the public key is, of course, not a random string. However, it is assumed that the proposition "probability of including an arbitrary character string" called a name can be treated as random. I tried various things and it seems to be correct, but ** it is unfounded. ** In other words, it is quite possible that there are strings that will not occur even if you try forever, or strings that have a more distorted probability than random. I would like to find out more about this area, but ~~ I shouldn't spend any more business hours. ~~
I received a supplement from @ angel_p_57 in the comments. It can be treated as random, but after the first I, it is limited to uppercase letters A to P. Thank you very much.
Thank you for reading.
reference
Recommended Posts