Should I read the whole logfile to an array and then go back?

Log files tend to get very large, so reading the whole lot might cause problems.

The following assumes that the relevant lines will be grouped together and only keeps 4 lines in memory at a time; change the constant if you need more.

It then runs the regex against the concatenation of the current 4 lines and outputs the relevant fields when a match is found.

It works on a test file consisting of a few dozen repetitions of your posted data with most of the sets of lines modified not to match; beyond that testing depends upon the nature of your data:

perl -nwle" if(push( @s, $_ ) > 4 ){ shift @s } qq[@s]=~m[.+from (\S+)
+.+identity ('[^']+').+verification failed]s and print qq[$1:$2]" junk
+.dat
[download]

Remember to change/adjust/escape the "s & 's for *nix.