my @result = search(\%hash, 'foo');

sub search {
    my ($hash, $search) = @_;
    my @result;
    for my $key (keys %$hash) {
        my $found = search_data($hash->{ $key }, $search);
        push @result, $key if $found;
    }
    return @result;
}

sub search_data {
    my ($ref, $search) = @_;
    if (ref($ref) eq 'HASH') {
        for my $key (keys %$ref) {
            return 1 if $key =~ m/$search/;
            return 1 if search_data($ref->{ $key }, $search);
        }
    }
    elsif (ref($ref) eq 'ARRAY') {
        for my $item (@$ref) {
            return 1 if search_data($item, $search);
        }
    }
    elsif (ref($ref) eq 'SCALAR') {
        return search_data($$ref, $search);
    }
    elsif (ref($ref) eq 'REF') {
        return search_data($$ref, $search);
    }
    elsif (ref($ref) eq '') {
        return 1 if $ref =~ m/$search/;
    }
    return 0;
}