The Daily WTF: Curious Perversions in Information Technology

RaceProUK · 2015-05-14 Reply Admin

Ah! Right! I was just reading last week, it turns out, slower code is more secure, cryptographically speaking.

I… *walks away, unwilling to acknowledge that level of ignorance*

JBert · 2015-05-14 Reply Admin

So, who is working at the contractor: Joey or Ross?

Filed under: FP-highlighted that for you.

boomzilla · 2015-05-14 Reply Admin

I think the solution is to introduce Joey and Monica to Haskell, which is so awesome for recursing tree stuff like this. Also, they'll be so busy proving their solutions are correct to commit any more bad code.

:passport_control:

swayde · 2015-05-14 Reply Admin

Did I miss the introduction of a new author?

RaceProUK · 2015-05-14 Reply Admin

Another thing about that three: child and sib? Odd choice of variable names; convention is either left/right or red/black, surely?

swayde:
Did I miss the introduction of a new author?

NoYes; she's been an author for a while now ;)

accalia · 2015-05-14 Reply Admin

"It's more secure that way. "

[image]

Jaloopa · 2015-05-14 Reply Admin

RaceProUK:
Ah! Right! I was just reading last week, it turns out, slower code is more secure, cryptographically speaking.

Security by "Fuck, I was going to hack this but it takes too damn long. I'm going to get a coffee"

boomzilla · 2015-05-14 Reply Admin

:wtf:

RaceProUK:
NoYes; she's been an author for a while now

RaceProUK · 2015-05-14 Reply Admin

boomzilla:
:wtf:

That's me! :wave:

swayde · 2015-05-14 Reply Admin

Well, the only introduction I can find is this:

Yamikuronue:
Yeah, Jane Bailey is my nome de plume, so I figured I'd use it for my author credit. ■■■■■■■ is [part of] my legal name, which I usually try to censor out of paranoia

boomzilla · 2015-05-14 Reply Admin

Her first article was in early February:

http://thedailywtf.com/authors/jane-bailey

There have been several new authors as a result of:

http://what.thedailywtf.com/t/the-daily-wtf-wants-writers-again/4028?u=boomzilla

Yamikuronue · 2015-05-14 Reply Admin

swayde:
Did I miss the introduction of a new author?

Hi!

I've been around the forums this whole time really. Used to lurk on the old forums, I think I had like 3 posts. So in that sense, I didn't do an introduction post to the forums because ya'll knew me more or less before I applied for the writing position.

hvd · 2015-05-14 Reply Admin

There's actually a minimal element of truth somewhere hidden in it. For some types of functions, code that takes the time needed for the worst case, and makes all other cases take equally long, can be more secure than code that returns quicker for the easy cases. The usual example is a password validation service: if the time needed to determine that a password is invalid depends on how close it is to the correct password, then timing attacks can easily be used to determine the password.

Unfortunately, Joey probably read something like this, and didn't actually understand any of it, simply remembering it as slow = good, even in cases where it makes no sense whatsoever.

Gaska · 2015-05-14 Reply Admin

Am I the only one who, after reading the title, thought of Happy Tree Friends?

Also, Joey seems to have not read the article about slow code carefully - slower code can be indeed more secure, but only in very specific cases, and against very specific attacks: when generating encryption keys, when the algorithm is heavily optimized for speed, the time spent on generating the key can give away what the key is.

Dammit, Hanzo'd.

boomzilla · 2015-05-14 Reply Admin

hvd:
There's actually a minimal element of truth somewhere hidden in it.

My first thought on that subject was about password hashing. Where you want to make it painful for someone trying to brute force passwords.

MattSmucker · 2015-05-14 Reply Admin

Where are Chandler, Phoebe, and Rachel?

Zemm · 2015-05-14 Reply Admin

Is it just me or wouldn't each node be visited many more times than twice?

(I hope I didn't introduce any more WTFs by porting this code to Perl)

#!/usr/bin/perl

use strict;
use warnings;

use Data::Dumper;

my $foo = {};

for (my $i=0; $i<10; $i++) {
	insert ($foo, $foo, { i => $i });
}

print Dumper($foo);

sub setReadOnly {
	my ($tree, $ro) = @_;
	
	if (ref $tree->{child} eq 'HASH') { setReadOnly($tree->{child}, $ro) }
	if (ref $tree->{sib} eq 'HASH') { setReadOnly($tree->{sib}, $ro) }
	
	$tree->{c}++;
}

sub updateReadOnly {
	my ($tree, $ro) = @_;
	
	setReadOnly($tree, $ro);
	
	if (ref $tree->{child} eq 'HASH') { updateReadOnly($tree->{child}, $ro) }
	if (ref $tree->{sib} eq 'HASH') { updateReadOnly($tree->{sib}, $ro) }

	$tree->{c}++;
	$tree->{t}++;
}

sub insert {
	my ($tree, $parent, $fng) = @_;
	
	updateReadOnly($tree, 0);
	
	if (ref $parent->{child} ne 'HASH') {
		$parent->{child} = $fng;
	} else {
		my $k = $parent->{child};
		while (ref $k->{sib} eq 'HASH') { $k = $k->{sib} }
		$k->{sib} = $fng;
	}
	
	updateReadOnly($tree, 1);
}

outputs

$VAR1 = {
          'c' => 40,
          'child' => {
                       'c' => 57,
                       'sib' => {
                                  'c' => 68,
                                  'sib' => {
                                             'c' => 75,
                                             'sib' => {
                                                        'c' => 78,
                                                        'sib' => {
                                                                   'c' => 77,
                                                                   'sib' => {
                                                                              'c' => 72,
                                                                              'sib' => {
                                                                                         'c' => 63,
                                                                                         'sib' => {
                                                                                                    'c' => 50,
                                                                                                    'sib' => {
                                                                                                               'c' => 33,
                                                                                                               'sib' => {
                                                                                                                          'c' => 12,
                                                                                                                          't' => 1,
                                                                                                                          'i' => 9
                                                                                                                        },
                                                                                                               't' => 3,
                                                                                                               'i' => 8
                                                                                                             },
                                                                                                    't' => 5,
                                                                                                    'i' => 7
                                                                                                  },
                                                                                         't' => 7,
                                                                                         'i' => 6
                                                                                       },
                                                                              't' => 9,
                                                                              'i' => 5
                                                                            },
                                                                   't' => 11,
                                                                   'i' => 4
                                                                 },
                                                        't' => 13,
                                                        'i' => 3
                                                      },
                                             't' => 15,
                                             'i' => 2
                                           },
                                  't' => 17,
                                  'i' => 1
                                },
                       't' => 19,
                       'i' => 0
                     },
          't' => 20
        };

't' is the "twice" per node and 'c' is the count of both recursive functions going twice.

Also, it's not a very balanced tree! But I CBF'd actually figuring out where I want my example nodes to appear.

Edit: commenting out the "updateReadOnly" calls in the insert and doing it once after all the inserts shows that the last leaf is touched 12 times. The count is the i+3. and t is once for each node, as expected.

swayde · 2015-05-14 Reply Admin

I realized that 😝 The thing I was missing was the link from Jane bailey to @Yamikuronue

CoyneTheDup · 2015-05-14 Reply Admin

"Ah! Right! I was just reading last week, it turns out, slower code is more secure, cryptographically speaking."

This, from years ago, seems appropriate: Ideas rattle in his head like mustard seeds in a bass drum.

sloosecannon · 2015-05-14 Reply Admin

That's probably because you haven't been to the Screenshot thread.

oh wait...

CoyneTheDup:
This, from years ago, seems appropriate: Ideas rattle in his head like mustard seeds in a bass drum.

You know what's more secure than that? Code that never works! How can you hack something that doesn't actually exist?

Or the Discourse security strategy: Make everything so confusing that anyone who tries to hack it goes insane. Bonus points because after a bout of insanity, you're more likely to join TCotCDCK

JBert · 2015-05-14 Reply Admin

Gaska:
Am I the only one who, after reading the title, thought of Happy Tree Friends?

In this case senseless violence would have been warranted, so it would no longer fit the theme.

Matt_Westwood · 2015-05-14 Reply Admin

Er, er, so TRWTF is the variable name "fng"? Short for "fing"? "finger"? Aha, I know!

That's right, guys, this is not a "tree", it's a "fungus".

Protoman · 2015-05-14 Reply Admin

RaceProUK:
Another thing about that three: child and sib? Odd choice of variable names; convention is either left/rightorred/black, surely?

No, that's actually a not-so-uncommon way of implementing an N-ary tree without using an arbitrary-length list of child nodes. It means that finding the kth child of a node is now O(k) instead of O(1), which is bad for random access, but if you only ever need to sequentially iterate through the tree, it doesn't hurt.

c = child
s = sibling

root
 |
 | c
 V   s       s
 A1 ---> A2 ---> A3
 |               |
 | c             | c
 V               V   s       s
 B1              B2 ---> B3 ---> B4

would be equivalent to

   root
   /|\
  / | \
 /  |  \
V   V   V
A1  A2  A3
|      /|\
|     / | \
|    /  |  \
V   V   V   V
B1  B2  B3  B4

Protoman · 2015-05-14 Reply Admin

Zemm:
Is it just me or wouldn't each node be visited many more times than twice?

~~Yep, it's actually an O(N^2) algorithm, not twice O(N). updateReadOnly() visits every node and calls setReadOnly() on it, and setReadOnly() is O(N), therefore O(N^2).~~

~~More precisely, it's ∑(size of the subtree over all nodes); I haven't done a formal analysis, but I'm pretty sure that that comes out to O(N^2) no matter how the tree is balanced.~~

Nope, I'm wrong. It's O(N^2) in the worst case, but still O(N log N) in the best case. In a balanced tree, it's N + 2*(N/2) + 4*(N/4) + 8*(N/8) + ... = O(N log N).

FrostCat · 2015-05-14 Reply Admin

RaceProUK:
that level of ignorance

bcrypt would like a word with you.

RaceProUK · 2015-05-14 Reply Admin

bcrypt is used for tree-walking?

FrostCat · 2015-05-14 Reply Admin

I haven't read the article yet. I was just disagreeing with the general proposition that slower code isn't more secure.

sloosecannon · 2015-05-14 Reply Admin

And @RaceProUK was disagreeing with the general proposition that slower code is always more secure :)

accalia · 2015-05-14 Reply Admin

FrostCat:
I was just disagreeing with the general proposition that slower code isn't more secure.

slower code does not imply secure code. secure code can be slow, and slow code can be secure. btu slow code could also be stupod

sloosecannon · 2015-05-14 Reply Admin

accalia:
stupod

:smile:

FrostCat · 2015-05-14 Reply Admin

accalia:
slower code does not imply secure code.

bcrypt, widely considered to be secure, is deliberately slow. Quit overthinking my joke. :stuck_out_tongue:

RaceProUK · 2015-05-14 Reply Admin

accalia:
stupod

[image]

accalia · 2015-05-14 Reply Admin

FrostCat:
bcrypt, widely considered to be secure, is deliberately slow.

yes. but that's slow designed by smart people. not slow designed by stupid people.

FrostCat:
Quit overthinking my joke

it's my brain and i'll overthink if i want to!

FrostCat · 2015-05-14 Reply Admin

accalia:
yes. but that's slow designed by smart people. not slow designed by stupid people.

Yes, but it proves the idea that "slower can be more secure" isn't 100% stupid.

xaade · 2015-05-14 Reply Admin

I guess that's correct?

If it takes longer to do things, the software responds slower.

Then it responds slower to brute force.

And it takes longer to complete the attack.

RaceProUK · 2015-05-14 Reply Admin

*waits for @xaade to realise the article is about tree-walking*

Yamikuronue · 2015-05-14 Reply Admin

FrostCat:
bcrypt

Behind-the-curtain peek: That's exactly what I was thinking Joey read :)

xaade · 2015-05-14 Reply Admin

[image]

sloosecannon · 2015-05-14 Reply Admin

+ :moving_goal_post: :deciduous_tree:

xaade · 2015-05-14 Reply Admin

accalia:
not slow designed by stupid people.

"As an added bonus, ____"

AKA

"It's a feature"

BaconBits · 2015-05-14 Reply Admin

TRWTF is that this wasn't called, "The One With the Data Tree."

dkf · 2015-05-14 Reply Admin

FrostCat:
Yes, but it proves the idea that "slower can be more secure" isn't 100% stupid.

But there are some astoundingly stupid ways you can implement them. For example, you don't want to run bcrypt on every request, just once a session. Otherwise you'll be like a racing driver towing round an anchor from an ocean liner.

BTDT…

Steve_The_Cynic · 2015-05-15 Reply Admin

Message for this member of Burnham Wood. Dunsinane is the other way, dude!

Steve_The_Cynic · 2015-05-15 Reply Admin

Not one person (up to now) has commented on the fact that inserting into the tree ignores the WTF-laden purpose of the readOnly flag, thus making "insert" a WTF in its own right.

And giving it an interesting side effect: it inserts the item AND makes the tree read-only. (If the tree wasn't read-only before, too bad, it is now.)

boomzilla · 2015-05-15 Reply Admin

Yamikuronue:
Behind-the-curtain peek: That's exactly what I was thinking Joey read

Sweet. So I was right when I :hanzo:'d @FrostCat

boomzilla:
My first thought on that subject was about password hashing. Where you want to make it painful for someone trying to brute force passwords.

PleegWat · 2015-05-15 Reply Admin

I'd assumed it was code pruning, though indeed a write-only readonly flag is an even bigger :wtf:

flabdablet · 2015-05-16 Reply Admin

Gaska:
Am I the only one who, after reading the title, thought of Happy Tree Friends?

No.

https://www.youtube.com/watch?v=RO7Q1tMGE7g

Edit:

:wtf: Political commentary, YouTube style:

[image]

urkerab · 2015-05-19 Reply Admin

Steve_The_Cynic:
Not one person (up to now) has commented on the fact that inserting into the tree ignores the WTF-laden purpose of the readOnly flag, thus making "insert" a WTF in its own right.

Maybe the accessors for child and sib check the readOnly flag. (But that still doesn't explain why you change the readOnly status of the whole tree.)

Steve_The_Cynic · 2015-05-19 Reply Admin

urkerab:

Steve_The_Cynic:
Not one person (up to now) has commented on the fact that inserting into the tree ignores the WTF-laden purpose of the readOnly flag, thus making "insert" a WTF in its own right.
Maybe the accessors for child and sib check the readOnly flag. (But that still doesn't explain why you change the readOnly status of the whole tree.)

Try again. Each node of the tree has a read-only flag. The :wtf: is strong in that fact(1). insert() clears the read-only flag of all nodes of the tree, modifies the tree by inserting the passed-in subtree (there are no checks to see if it has NULL child and sibling pointers, therefore it is a subtree, possibly of only one node), and then sets the read-only flag of all nodes of the tree.

All that implies that insert() is more :wtf: than the rest, because it contains all the :wtf: of the rest as well as ignoring the read-only flag and having an incorrect name. A name like insert() tends to suggest that we are inserting a single node in the tree, but it inserts a whole tree in the tree ("yo, dawg!"), and therefore should be called graft().(2)

(1) Seriously, it is. It is possible to have a tree which is read-only in some areas, and read-write in others.

(2) But even this name is :wtf: because nothing stops me calling x.insert(x); or even this.child.child.child.insert(this); (from inside a member function, duh), so the name should be mangle().

HardwareGeek · 2015-05-19 Reply Admin

Steve_The_Cynic:
should be called graft().(2) ... (2) But even this name is :wtf: because nothing stops me calling x.insert(x); or even this.child.child.child.insert(this); (from inside a member function, duh), so the name should be mangle().

graft() is sufficient; nothing stops one from grafting a tree to itself: [image][image]

Happy Little (Read-Only) Trees

Leave a comment on “Happy Little (Read-Only) Trees”