henry_flower

Раніше, коли пошукові рóботи не розуміли JS, деякі too clever by half індивідууми замість mykola@example.com писали \KX[YPrVLT\B_Q^[R]^>. Коли бовзери завантажували шматок JS, вони рядок розшифровували.

Хоча такий шифротекст може нагадувати rot47, зазвичай використовувався xor cipher з нескладним ключем (12345), через побоюванні що з rot* пошуковий рóбот Міг Здогадатися у чому справа і тоді бог його знає, що могло статися!

Про xor cipher я дізнався студентом зі книжки Страуструпа та навіщось марно намагався переконати кілька друзяк шифрувати своєю віндюковою аплікацією імейли.

Нещодавно я згадав про це, коли побачив як віндюковий антивайрус миттєво карантинує 'небезпечні' тільки-но завантажені файли. Чи можна тоді його надурити зберігаючи файла як curl | my-stream-cipher > file?

Найпростіший потоковий шифрувальника пишеться у кілька рядків на Рубі:

#!/usr/bin/env ruby
key = ($*[0] && $*[0].size > 0) ? $*[0] : abort
STDIN.each_byte.with_index do |c,i|
  STDOUT.write (c ^ key[i % key.size].ord).chr
end

Пароль передається як 1й аргумент:

$ echo їжачок | ./xor-cipher1.rb monkey | hexdump -C
00000000  bc f8 be dd b5 c9 bc e8  be d5 b5 c3 67           |............g|
0000000d
$ echo їжачок | ./xor-cipher1.rb monkey | ./xor-cipher1.rb monkey
їжачок

Єдиний помірно цікавий момента є лише у циклічності перебору символів у паролі. Наприклад, для паролю abc:

$ ruby -e "p='abc'; i=0; while (i < 10); print p[i % p.length]; i+=1; end"
abcabcabca

На жаль, така реалізація є дуже повільна. Для 100MB файлу і рубі 3.1.2:

$ head -c $((1024*1024*100)) /dev/urandom > 100M.bin
$ time cat 100M.bin | ./xor-cipher1.rb monkey >/dev/null
real    0m39.860s
user    0m39.729s
sys     0m0.655s

Я спробував читати блоками по 8KB, але різниці у швидкості не побачив. Вмикаючі jit (ruby --jit), вдалося зекономити 5.8 сек (14.5%).

Righty-ho, що у звичайного користувача є поряд завжди? Варіянт на sh+awk:

#!/bin/sh

[ -z "$1" ] && exit 1
export LC_ALL=C

dec() { od -An -vtu1 | awk '{for (i=1; i <= NF; i++) print $i}'; }
dec | gawk -v keydec="`printf '%s' "$1" | dec`" 'BEGIN {
  key_len=split(keydec, key); k=0
} {printf "%c", xor($1, key[k+1]); k = (k+1) % key_len}'

(Чомусь хфункція split() вертає хеш з ключами індексів починаючи з 1.)

dec() використовується для друкування потоку ув decimal:

$ printf abc | od -An -vtu1 | awk '{for (i=1; i <= NF; i++) print $i}'
97
98
99

На жаль, результат є маргінально ліпший за рубі:

$ time cat 100M.bin | ./xor-cipher7.sh monkey >/dev/null
real    0m36.538s
user    0m56.546s
sys     0m1.208s

Варіянт на ноуді:

#!/usr/bin/env node

let key = process.argv[2]?.length ? process.argv[2] : process.exit(1)
let keygen = key => {
    let idx = 0
    return () => key[idx++ % key.length].charCodeAt()
}
let k = keygen(key)
let enc = buf => buf.map( c => c ^ k())
process.stdin.on('data', chunk => process.stdout.write(enc(chunk)))

Нарешті щось приємне:

$ time cat 100M.bin | ./xor-cipher5.js monkey >/dev/null
real    0m1.507s
user    0m1.496s
sys     0m0.146s

Можна ще швидше? C з 0м витонченості:

#include <unistd.h>
#include <string.h>

void enc(char *key, char *buf, int len) {
  int key_len = strlen(key);
  for (int idx = 0; idx < len; idx++)
    buf[idx] = buf[idx] ^ key[idx % key_len];
}

int main(int _, char **argv) {
  char *key = argv[1]; if ( !(key && strlen(key))) return 1;
  int n;
  char buf[8*1024];
  while ( (n = read(0, buf, sizeof buf))) {
    enc(key, buf, n);
    write(1, buf, n);
  }
}

МИКОЛА ГНАТОВИЧ
Раніш люди ніколи не умивалися. І їли сало. А захоче помидора чи диню--то так зірве, навіть і не миє. І от таки в усіх пики були!

$ time cat 100M.bin | ./xor-cipher4 monkey >/dev/null
real    0m0.474s
user    0m0.449s
sys     0m0.172s

На цьому можна було б закінчити, але мені не давала спокію сумна швидкість рубі. Спочатку я спробував, вибачаюся, треди (з трохи іншим перебором символів ув паролі--потік читається блоками і лічильник прив'язаний до блоку, а не є глобальним):

#!/usr/bin/env ruby

key = ($*[0] && $*[0].size > 0) ? $*[0] : abort

def enc key, chunk
  chunk.each_byte.map.with_index {|c,i| (c ^ key[i%key.size].ord).chr }.join ""
end

threads = []
while (chunk = STDIN.read 8*1024)
  threads << Thread.new(chunk) {|chk| enc key, chk }
end

threads.each {|t| t.join; STDOUT.write t.value }

Але з GIL ув MRI це було гірше марного. Тоді я згадав що існує jruby:

$ rvm use jruby-9.3.4.0
$ time cat 100M.bin | ./xor-cipher2.threads.rb monkey >/dev/null
real    0m5.986s
user    0m45.193s
sys     0m3.770s

Ув рубі 3 з'явилися Ractors (actor-like concurrent abstraction). На жаль, jruby їх поки що не підтримує, а ув MRI вони періодично генерують coredumps.

#!/usr/bin/env ruby

KEY = ($*[0] && $*[0].size > 0) ? $*[0] : abort

def enc chunk
  chunk.each_byte.map.with_index {|c,i| (c ^ KEY[i%KEY.size].ord).chr }.join ""
end

ractors = []
while (chunk = STDIN.read 8*1024)
  r = Ractor.new { enc Ractor.receive }
  r.send chunk, move: true
  ractors << r
end

ractors.each {|rr| STDOUT.write rr.take }

Краще за 1й варіянт на рубі, але набагато гірше за комбінацію тредів під jruby:

$ time cat 100M.bin | ruby --jit xor-cipher8.ractors.rb monkey >/dev/null
<internal:ractor>:267: warning: Ractor is experimental, and the
behavior may change in future versions of Ruby! Also there are
many implementation issues.

real    0m27.245s
user    2m5.655s
sys     0m14.194s

Що буде, якщо ми розіб'ємо великий файла на N шматків і будемо запускати nproc процессів (N > nproc) доки всі N не будуть зашифровані? Все це вміє GNU Make:

#!/usr/bin/make -sf

$(if $(p),,$(error p=))

self    := $(lastword $(MAKEFILE_LIST))
t       := $(shell openssl rand -hex 4)
make    := $(MAKE) --no-print-directory -f $(self) t=$(t)
cipher  := $(dir $(self))/xor-cipher1.rb
chunk   := chunk_$(t)_
xor     := xor_$(t)_
nproc   := sysctl -n hw.ncpu
ifeq ($(shell uname), Linux)
nproc   := nproc
endif

all:
	split -b 409600 - $(chunk)
	echo $(chunk)* | sed 's/$(chunk)/$(xor)/g' | xargs $(make) -j `$(nproc)`
	cat $(xor)*
	rm $(xor)* $(chunk)*

$(xor)%: $(chunk)%; $(cipher) $(p) < $< > $@

Для шифрування тут використовується 1й рубі варіянт:

$ time cat 100M.bin | ./xor-cipher3.mk p=monkey >/dev/null
real    0m8.219s
user    1m23.892s
sys     0m3.525s

Підсумки для 100MB файлу:

Name	Score
C	0m0.474s
node	0m1.507s
jruby threads	0m5.986s
make + ruby	0m8.219s
ruby jit + ractors	0m27.245s
ruby jit	0m34.003s
sh + awk	0m36.538s
ruby	0m39.860s

⊕

no subject

no subject